PaperlayerView exact revision on arXiv

Source-linked AI summary

BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation

Mingguo He, Zhewei Wei, Zengfeng Huang, Hongteng Xu

arXiv:2106.10994v3cs.LGcs.AI

TL;DR

Existing graph neural networks may focus on simple filters or learn filters with poor interpretability and insufficient constraints. BernNet uses Bernstein polynomial approximation to design and learn arbitrary spectral filters, with experiments showing complex-filter capability and superior performance on synthetic and real-world datasets.

  • Problem

    Existing methods often focus on simple filters, while learned filters may have poor interpretability and GPR-GNN or ChebNet may be ill-posed.

  • Method

    BernNet designs and learns arbitrary spectral filters by approximating filters over the normalized Laplacian spectrum with Bernstein polynomials and tuning their coefficients.

  • Results

    BernNet learns complex filters including band-rejection and comb filters and outperforms state-of-the-art methods on synthetic and real-world datasets.

  • Takeaways & Limitations

    BernNet provides an interpretable mechanism for designing arbitrary filters, and its learned polynomial filters are always valid.

  • Takeaways & Limitations

    The paper notes that GCN can violate the non-negative constraint because its filter takes negative values for eigenvalues greater than 1.

Abstract

from arXiv · show

Many representative graph neural networks, e.g., GPR-GNN and ChebNet, approximate graph convolutions with graph spectral filters. However, existing work either applies predefined filter weights or learns them without necessary constraints, which may lead to oversimplified or ill-posed filters. To overcome these issues, we propose BernNet, a novel graph neural network with theoretical support that provides a simple but effective scheme for designing and learning arbitrary graph spectral filters. In particular, for any filter over the normalized Laplacian spectrum of a graph, our BernNet estimates it by an order-$K$ Bernstein polynomial approximation and designs its spectral property by setting the coefficients of the Bernstein basis. Moreover, we can learn the coefficients (and the corresponding filter weights) based on observed graphs and their associated signals and thus achieve the BernNet specialized for the data. Our experiments demonstrate that BernNet can learn arbitrary spectral filters, including complicated band-rejection and comb filters, and it achieves superior performance in real-world graph modeling tasks. Code is available at https://github.com/ivam-he/BernNet.

1 Introduction

Existing GNNs commonly use polynomial graph spectral filters, but they generally focus on simple filters or sacrifice interpretability when learning arbitrary ones. BernNet addresses this by approximating arbitrary spectral filters with Bernstein polynomials whose coefficients can be designed or learned.

  • Existing spectral filtering: Many GNNs formulate graph convolution as polynomial filtering using the normalized Laplacian or normalized adjacency matrix.The normalized Laplacian is L = I − D^−1/2AD^−1/2, while an equivalent formulation uses normalized adjacency powers.
  • Existing spectral filtering: Filter-based GNNs either design weights for predefined behaviors such as low-pass filtering or learn weights with polynomial or rational bases.Examples include GCN, APPNP, GNN-LF/HF, ChebNet, GPR-GNN, and ARMA.
  • Limitations: Existing methods mainly target simple filters, while complex band-rejection and comb filters are often required in real-world applications.Learning-based methods can theoretically learn arbitrary filters, but the learned filter shape is not intuitively exposed.
  • BernNet: BernNet approximates an arbitrary normalized-Laplacian spectral filter with a K-order Bernstein polynomial and treats its basis coefficients as designable or learnable parameters.The coefficients can be interpreted as filter values uniformly sampled over the spectrum [0, 2].
  • BernNet: BernNet provides an algorithmic framework for designing and learning arbitrary graph spectral filters while addressing interpretability concerns.The introduction presents the method as a response to the limitations of existing designed and learned filters.

2 BernNet

BernNet uses Bernstein polynomial approximation to design or learn spectral filters over the normalized Laplacian spectrum, with coefficients tied to sampled filter values. The framework can represent standard and complex filters, while approximation quality improves with order K but remains limited for sharp peaks and valleys.

  • Bernstein approximation: BernNet approximates an arbitrary continuous filter h on [0, 2] using an order-K Bernstein polynomial over the normalized Laplacian spectrum.The approximation converges to h(L)x as K approaches infinity when θ_k = h(2k/K).
  • Bernstein approximation: Each coefficient θ_k can be set to a sampled target value h(2k/K) or learned end-to-end from graph structure and signals.The coefficients correspond to uniformly sampled filter values over [0, 2].
  • Realizing existing filters: BernNet exactly realizes all-pass, linear low-pass, and linear high-pass filters through appropriate Bernstein coefficient settings.The linear low-pass setting also matches the pre-renormalization GCN convolution.
  • Realizing existing filters: BernNet also approximates impulse low-pass, high-pass, and band-pass filters, including non-continuous cases when K is sufficiently large.Impulse band-pass uses K/2 for the central coefficient, requiring even K.
  • Realizing existing filters: Large or small θ_k values indicate whether spectral components near λ ≈ 2k/K are passed or rejected, making filter design interpretable.This coefficient-to-spectrum correspondence is identified as an advantage of BernNet.
  • Learning complex filters: BernNet learns smoothed approximations of complex band-rejection, comb, and low-band-pass filters, with precision improving as K increases.Finite K prevents exact comb-filter peaks and zero-valued valleys, although BernNet is reported to outperform other GNNs on these complex filters.

3 BernNet in the Lens of Graph Optimization

BernNet is motivated by graph optimization as a way to characterize valid polynomial spectral filters. Positive semidefinite energy functions yield filters constrained to [0,1], and Bernstein bases provide a representation that preserves this validity while supporting arbitrary polynomial filters.

  • Graph optimization motivation: BernNet is motivated by showing that valid polynomial filters approximating the optimization solution have a Bernstein-basis form.The section frames this as a graph-optimization perspective on the model.
  • Generalized graph optimization problem: The generalized optimization problem uses α as a trade-off parameter, z as the propagated signal representation, and γ(L) as an energy function controlling propagation.The energy function operates spectrally through γ(L) = Udiag[γ(λ1), ..., γ(λn)]U^T.
  • Generalized graph optimization problem: Existing polynomial filtering operations, including APPNP and heat-kernel-based filters, can be modeled as optimal solutions of the generalized graph optimization problem.Specific choices of γ(L) recover filtering operations associated with APPNP, GCN, DAGNN, JKNet, GDC, and GraphHeat.
  • Non-negative constraint on polynomial filters: Positive semidefiniteness of γ(L) is required because otherwise the optimization may have a saddle point or become unbounded below.The negative-eigenvalue direction can drive the objective toward −∞.
  • Non-negative constraint on polynomial filters: Valid filters satisfy 0 ≤ g(λ) ≤ 1 on λ ∈ [0,2], but nonnegative monomial coefficients alone cannot represent arbitrary valid filters because they correspond only to low-pass filters.The upper bound can be enforced by rescaling, whereas nonnegativity requires the Bernstein-basis argument.
  • Non-negative constraint on polynomial filters: GCN can violate the nonnegative-filter constraint because g(λ) = 1 − λ becomes negative when λ > 1, even after renormalization may shrink the spectrum.The maximum eigenvalue of the renormalized Laplacian can still exceed 1.
  • Non-negative polynomials and Bernstein basis: Any polynomial nonnegative on [0,2] can be expressed as a nonnegative linear combination of Bernstein basis functions after setting x = λ/2.This property motivates BernNet’s parameterization and its validity guarantee.

4 Related Work

Spectral-based GNNs design or learn graph filters in the spectral domain, whereas spatial-based GNNs propagate and aggregate information directly over graph neighborhoods. Prior methods include polynomial, heat-kernel, PageRank, rational, and attention-based approaches.

  • Spectral and spatial GNNs: GNNs are broadly divided into spectral-based methods that design filters spectrally and spatial-based methods that aggregate graph information directly.This distinction organizes the related-work discussion.
  • Spectral-based GNNs: ChebNet, GCN, GraphHeat, APPNP, GPR-GNN, and ARMA represent spectral approaches using polynomial, heat-kernel, PageRank, or rational filters.Their filter parameters are either approximated, predefined, or learned in the spectral domain.
  • Spatial-based GNNs: Spatial approaches include GCN’s one-hop aggregation and GAT’s attention-based aggregation, while other work unifies spectral and spatial interpretations.The cited unification shows that GNNs can be interpreted as sophisticated data-dependent propagation mechanisms.

5 Experiments

Experiments evaluate BernNet on synthetic filtering tasks and real-world node classification, showing strong filter-learning capability and competitive performance. The experiments also identify a computational-efficiency trade-off from BernNet’s quadratic dependence on filter degree K.

  • Learning filters from the signal: On 50 100×100 real images represented as 10,000-node grid graphs, BernNet learns low-pass, high-pass, band-pass, band-rejection, and comb filters from supervised input-output signals.The task minimizes squared error between the model output and the filtered signal, comparing BernNet with GCN, GAT, GPR-GNN, ARMA, and ChebNet.
  • Learning filters from the signal: BernNet consistently outperformed the competing models on both sum of squared error and R2 across the synthetic filtering tasks.Lower sum of squared error and higher R2 indicate better filtering accuracy under the reported metrics.
  • Node classification on real-world datasets: BernNet provides the best micro-F1 results on seven of ten real-world benchmark datasets and competitive results on the remaining three.The evaluation uses mean micro-F1 accuracy with a 95% confidence interval across homophilic and heterophilic graph datasets.
  • Node classification on real-world datasets: With only node-label supervision, BernNet learns an all-pass-alike filter on Actor and comb-alike filters on Chameleon and Squirrel.The authors report that BernNet outperforms all competitors by at least 1% on Chameleon and Squirrel, and that learned coefficients closely track filter curves.
  • Node classification on real-world datasets: BernNet is slower than other methods because its propagation has quadratic rather than linear time complexity in filter degree K.The reported runtime margin versus GPR-GNN is generally less than 2, while converting BernNet to linear complexity remains future work.

6 Conclusion

The conclusion presents BernNet as a theoretically supported mechanism for designing and learning arbitrary graph spectral filters through Bernstein polynomial approximation. It reports improved interpretability and effectiveness on synthetic and real-world datasets, while identifying efficiency improvement as future work.

  • 6 Conclusion: BernNet designs and learns arbitrary spectral filters through a simple, intuitive Bernstein polynomial approximation mechanism.The conclusion highlights complex filters, including band-rejection and comb filters, as supported examples.
  • 6 Conclusion: BernNet’s polynomial filters are always valid and provide better interpretability than previous methods.The conclusion also reports improved effectiveness on synthetic and real-world datasets.
  • 6 Conclusion: Improving BernNet’s efficiency is identified as an interesting direction for future work.This follows the reported computational cost of the method.

Broader Impact

The paper frames BernNet as a general technical and theoretical contribution for designing and learning arbitrary graph spectral filters. It identifies possible applications across several domains without claiming foreseeable specific impacts.

  • Broader Impact: BernNet is presented as a general technical and theoretical contribution for arbitrary graph spectral filtering on graphs.The broader-impact statement does not identify a specific foreseeable impact.
  • Broader Impact: Potential applications include bioinformatics, computer vision, and natural language processing, where BernNet may improve existing GNN performance.The exploration of other potential impacts is left to future work.

A.1 Learning filters from the signal (Section 5.1)

The appendix describes implementation settings for the signal-filtering experiment, including matched model sizes and the released GPR-GNN code reference. It notes that the image setup follows the main experiment’s configuration.

  • A.1 Learning filters from the signal (Section 5.1): All models use approximately 2k trainable parameters, with hidden units tuned to keep model sizes similar.The models use two convolutional layers and a linear output layer, without regularization or dropout.
  • A.1 Learning filters from the signal (Section 5.1): The appendix specifies architecture settings for GCN, GAT, ARMA, ChebNet, and GPR-GNN in the filtering experiment.These settings include hidden units, attention heads, propagation steps, and linear-layer dimensions.
  • A.1 Learning filters from the signal (Section 5.1): The GPR-GNN implementation is identified by its URL and commit number in the supplementary materials.This supports reproducibility of the baseline comparison.
  • A.1 Learning filters from the signal (Section 5.1): BernNet’s settings for the analysis experiment match the preceding settings, and the image used is Figure 3.The appendix directly links the analysis configuration to the earlier experiment setup.

A.2 Node classification on real-world datasets (Section 5.2)

On real-world datasets, BernNet was evaluated under standardized training settings and learned dataset-specific spectral filters. It learned low-pass filters on Cora and CiteSeer, while its Bernstein coefficients closely tracked the learned filter shapes.

  • Experimental settings: All models use two convolutional layers, Adam optimization, early stopping at 200 epochs, and a maximum of 1000 epochs.Learning rate and weight decay are selected from the specified search grids for each dataset.
  • Experimental settings: The baselines use specified architecture and propagation settings, including 64 hidden units for GCN and MLP, K=10 for APPNP, and K=2 for ChebNet.GAT uses eight attention heads with eight hidden units in its first layer and one attention head with 64 hidden units in its second layer.
  • Learned spectral filters: BernNet learns dataset-specific spectral filters from real-world graph datasets.Figure 6 presents the learned filters, while Figure 7 presents the corresponding Bernstein coefficients.
  • Learned spectral filters: BernNet learns low-pass filters on Cora and CiteSeer, consistent with prior analysis cited by the authors.
  • Coefficient interpretation: The learned coefficient curves are almost identical to the filter curves because BernNet’s coefficients are highly correlated with the target filter’s spectral property.
Loading 2106.10994v3…