PaperlayerView exact revision on arXiv

Source-linked AI summary

Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited

Mingguo He, Zhewei Wei, Ji-Rong Wen

arXiv:2202.03580v5cs.LGcs.AI

TL;DR

The paper addresses why ChebNet underperforms simpler or alternative polynomial spectral GNNs despite Chebyshev polynomials’ theoretical approximation advantages. It identifies illegal learned coefficients as a primary cause, proposes ChebNetII using Chebyshev interpolation, and reports strong node-classification performance with billion-scale applicability.

  • Problem

    The paper asks why ChebNet underperforms GCN, GPR-GNN, and BernNet despite greater theoretical expressiveness and Chebyshev polynomials’ near-optimum approximation properties.

  • Method

    ChebNetII reparameterizes filter values at Chebyshev interpolation nodes as learnable parameters, enabling arbitrary spectral filters while reducing the Runge phenomenon.

  • Results

    ChebNetII outperforms state-of-the-art methods across homophilic and heterophilic datasets, including new state-of-the-art results on 7 of 8 full-supervised datasets and over 10% improvement over GPR-GNN and BernNet on Squirrel.

  • Takeaways & Limitations

    The findings support ChebNetII as an effective and scalable spectral-based GNN for full- and semi-supervised node classification, including the billion-node ogbn-papers100M graph.

  • Takeaways & Limitations

    The authors identify further improving ChebNetII on large graphs and investigating the scalability of spectral-based GNNs as future work.

Abstract

from arXiv · show

Designing spectral convolutional networks is a challenging problem in graph learning. ChebNet, one of the early attempts, approximates the spectral graph convolutions using Chebyshev polynomials. GCN simplifies ChebNet by utilizing only the first two Chebyshev polynomials while still outperforming it on real-world datasets. GPR-GNN and BernNet demonstrate that the Monomial and Bernstein bases also outperform the Chebyshev basis in terms of learning the spectral graph convolutions. Such conclusions are counter-intuitive in the field of approximation theory, where it is established that the Chebyshev polynomial achieves the optimum convergent rate for approximating a function. In this paper, we revisit the problem of approximating the spectral graph convolutions with Chebyshev polynomials. We show that ChebNet's inferior performance is primarily due to illegal coefficients learnt by ChebNet approximating analytic filter functions, which leads to over-fitting. We then propose ChebNetII, a new GNN model based on Chebyshev interpolation, which enhances the original Chebyshev polynomial approximation while reducing the Runge phenomenon. We conducted an extensive experimental study to demonstrate that ChebNetII can learn arbitrary graph convolutions and achieve superior performance in both full- and semi-supervised node classification tasks. Most notably, we scale ChebNetII to a billion graph ogbn-papers100M, showing that spectral-based GNNs have superior performance. Our code is available at https://github.com/ivam-he/ChebNetII.

1 Introduction

Spectral-based GNNs learn graph convolutions in the graph-Laplacian spectral domain, but key questions remain about ChebNet’s unexpectedly weak empirical performance and the role of polynomial bases. The paper attributes these issues to learned Chebyshev coefficients and introduces ChebNetII to improve approximation and scalability.

  • Spectral-based GNNs construct graph convolutions in the spectral domain of the graph Laplacian, whereas spatial-based methods aggregate neighboring-node messages.
  • GCN uses only the first two Chebyshev polynomials yet outperforms the more expressive ChebNet on real-world datasets.ChebNet can theoretically learn arbitrary filters, while GCN is a fixed low-pass filter.
  • ChebNet also underperforms GPR-GNN and BernNet, despite approximation theory establishing near-optimum error for Chebyshev polynomials.GPR-GNN uses the Monomial basis, while BernNet uses the Bernstein basis.
  • The paper attributes ChebNet’s inferior performance primarily to illegal coefficients learned while approximating analytic filter functions, which leads to over-fitting.
  • ChebNetII uses Chebyshev interpolation to enhance Chebyshev approximation, reduce the Runge phenomenon, learn arbitrary graph convolutions, and scale to ogbn-papers100M.

2 Revisiting ChebNet

This section revisits spectral graph filtering with Chebyshev polynomials, examining why ChebNet underperforms despite greater theoretical expressiveness and approximation ability. It identifies unconstrained coefficients as a source of over-fitting and motivates coefficient-constrained alternatives.

  • 2.1 Spectral-based GNNs and ChebNet: Spectral-based GNNs construct graph convolutions in the Laplacian spectrum, while ChebNet approximates filtering with Chebyshev polynomials and trainable weights.The scaled Laplacian supports a recursive Chebyshev formulation, with polynomial coefficients implicitly encoded in the model’s weight matrices.
  • 2.1 Spectral-based GNNs and ChebNet: ChebNet is theoretically more expressive than GCN and can approximate arbitrary spectral filters as polynomial order increases, yet performs worse on citation-graph node classification.The disadvantage becomes especially pronounced when K increases from 2 to 10, despite GCN corresponding to a restricted ChebNet setting.
  • 2.2 The motivation of revisiting ChebNet: ChebBase performs worst among ChebBase, GPR-GNN, and BernNet, despite Chebyshev polynomials providing minimax approximation for analytic functions in theory.ChebBase replaces the Monomial and Bernstein bases with an explicit Chebyshev basis to compare approximation ability directly.
  • 2.2 The motivation of revisiting ChebNet: For analytic functions, Chebyshev coefficients must decrease asymptotically, constraining high-frequency polynomial components in the expansion.Theorem 2.1 states that coefficients decrease proportionally to 1/k^q for some positive q under the stated boundary and analyticity conditions.
  • 2.3 Coefficient Constraints: Unconstrained gradient learning can produce illegal Chebyshev coefficients that violate this convergence behavior and lead to over-fitting.The paper attributes ChebNet’s suboptimal performance primarily to these learned coefficients when approximating analytic filter functions.
  • 2.3 Coefficient Constraints: A simple 1/k coefficient reparameterization makes ChebBase/k more consistent with the convergence constraint and allows it to outperform ChebNet, ChebBase, and GCN.Additional results on Citeseer and Pubmed report that ChebBase/k coefficients more readily satisfy the constraint, validating Theorem 2.1.

3 ChebNetII model

ChebNetII uses Chebyshev interpolation to learn arbitrary spectral filters through values at Chebyshev nodes, improving approximation behavior while controlling Runge oscillations. Its analysis establishes near-minimax approximation, faster convergence than Bernstein approximation, and computational efficiency comparable to ChebNet and GPR-GNN.

  • Chebyshev interpolation: Chebyshev interpolation replaces uniformly spaced interpolation points with Chebyshev nodes to improve convergence and reduce the Runge phenomenon.Uniform interpolation can develop endpoint oscillations as polynomial degree increases; Chebyshev nodes address this behavior.
  • ChebNetII model: ChebNetII reparameterizes filter values at Chebyshev nodes as learnable γj, enabling gradient-based learning of arbitrary spectral filters.The model uses Chebyshev nodes xj and separates feature propagation from transformation through an MLP fθ(X).
  • ChebNetII model: ChebNetII directly controls the filter through γj, while its induced coefficients satisfy the theoretical constraints for approximating the filter.The coefficients are computed from the learned node values, which correspond directly to h(xj).
  • Approximation analysis: Chebyshev interpolation achieves near-best approximation with relative distance ρ ∼ log(K) as K →∞, compared with ρ ∼ 2^K for general interpolation.The comparison uses the uniform norm and a best polynomial approximation as the reference.
  • Approximation analysis: Chebyshev interpolation has a faster convergence rate than Bernstein approximation, with error scaling as Cω(K^-1) log(K) versus approximately (1 + (2K)^-2)ω(K^-1/2).These rates compare approximation errors for the same function under Chebyshev interpolation and Bernstein approximation.
  • Computational complexity: ChebNetII propagation costs O(K^2 + Kmd), with precomputation making O(Kmd) dominant and yielding linear scaling in K versus BernNet’s O(K^2md).The model is therefore described as more efficient than BernNet and similar in time complexity to GPR-GNN and ChebNet.

4 Experiments

Experiments evaluate ChebNetII across semi- and full-supervised node classification, heterogeneous and homophilic graphs, and large-scale datasets. ChebNetII generally outperforms competing methods and remains scalable through precomputed polynomial propagations.

  • Experimental setup: ChebNetII is evaluated on homophilic, heterophilic, citation, and large graph datasets for semi- and full-supervised node classification.The experiments include Cora, Citeseer, Pubmed, Chameleon, Squirrel, Actor, Texas, Cornell, ogbn-arxiv, ogbn-papers100M, and six large heterophilic graphs.
  • Semi-supervised node classification: In semi-supervised classification, ChebNetII outperforms other methods on every dataset except Pubmed, where it achieves top-2 accuracy.The authors attribute this to parameters corresponding directly to filter values at Chebyshev nodes, preventing illegal filters.
  • Full-supervised node classification: ChebNetII achieves new state-of-the-art results on 7 of 8 full-supervised datasets and competitive results on Pubmed.ChebNet also surpasses GCN when more training data are available, supporting the effectiveness of Chebyshev approximation.
  • Scalability: ChebNetII outperforms all other methods on 4 of 6 large heterophilic datasets and achieves a new state-of-the-art result on wiki.LINK and LINKX outperform it on arXiv-year because they use directed graphs, whereas current spectral graph theory applies only to undirected graphs.
  • Scalability: ChebNetII outperforms both datasets on ogbn-arxiv and ogbn-papers100M, while BernNet fails to finish preprocessing on ogbn-papers100M within 24 hours.Precomputing Tk(L-hat)X enables mini-batch training and supports scaling to large graphs.
  • Approximation study: For a Runge filter, the Chebyshev basis converges faster than the Bernstein basis and does not exhibit the Runge phenomenon compared with the reported alternatives.The comparison uses approximation results and errors across polynomial bases.

5 Conclusion

The paper concludes that ChebNet’s inferior performance stems primarily from illegal coefficients that overfit analytic filters, and introduces ChebNetII to address this issue. Experiments support its effectiveness on homophilic and heterophilic graphs.

  • 5 Conclusion: ChebNetII uses Chebyshev interpolation to enhance Chebyshev approximation while reducing the Runge phenomenon.The model is presented as a new spectral GNN for learning graph convolutions.
  • 5 Conclusion: ChebNet’s inferior performance is attributed primarily to illegal coefficients learned when approximating analytic filter functions, causing over-fitting.This conclusion revisits the discrepancy between ChebNet’s theoretical expressiveness and its empirical performance.
  • 5 Conclusion: The experiments report that ChebNetII outperforms state-of-the-art methods on real-world homophilic and heterophilic datasets.The authors identify further improvement on large graphs and scalability investigation as future work.
  • 5 Conclusion: Spectral filtering is crucial because different filters can support classification of homophilic, heterophilic, and mixed-label graph structures.The ring-graph examples connect low-, high-, and band-pass filters to different label patterns.

C Chebyshev basis

Chebyshev polynomials are generated by a three-term recurrence and represent increasingly oscillatory components as their order grows. Higher-order terms therefore require constrained coefficients when approximating analytic functions.

  • C Chebyshev basis: The first six Chebyshev polynomials are illustrated in Figure 4.The figure covers Tk(x) for k = 0, 1, 2, 3, 4, 5.
  • C Chebyshev basis: Chebyshev polynomials satisfy Tk(x) = 2xTk−1(x) − Tk−2(x), with T0(x) = 1 and T1(x) = x.The recurrence defines the polynomial sequence on x ∈ [−1, 1].
  • C Chebyshev basis: Larger-order Chebyshev polynomials correspond to higher-frequency oscillations.The paper links this increasing oscillation to constraints on coefficients for analytic-function approximation.

D More details for Polynomial Interpolation

Polynomial interpolation uniquely determines a degree-bounded polynomial from filter values at selected points. Chebyshev interpolation replaces equispaced points with Chebyshev nodes, while Lagrange interpolation avoids the expense of solving a large Vandermonde system.

  • Polynomial interpolation: Given K + 1 filter values at ordered points in [−1, 1], a unique polynomial of degree at most K interpolates those values.Its polynomial coefficients can be obtained from a Vandermonde linear system.
  • Polynomial interpolation: Solving the Vandermonde system becomes expensive for many data points, motivating the equivalent Lagrange interpolation formulation.The computational issue concerns direct coefficient recovery from the interpolation equations.
  • Chebyshev interpolation: Chebyshev interpolation uses Chebyshev nodes instead of equispaced interpolation points.The paper distinguishes the node choice while treating general and Lagrange interpolation as essentially equivalent.
  • Coefficient behavior: Figure 5 illustrates Chebyshev coefficients learned by ChebBase and ChebBase/k on Citeseer and Pubmed.The figure supports comparison of coefficient behavior across the two parameterizations.

E Additional experimental details

The experiments use standard library implementations for several baselines and author-released implementations for the remaining methods.

  • MLP, GCN, ChebNet, AMAR, and APPNP use implementations from PyTorch Geometric.
  • Other baseline methods use implementations released by their authors.

E.1 Experiments in Section 2

Experiments on Cora, Citeseer, and Pubmed use fixed citation-graph splits, matched parameter budgets, and mean results over 10 runs. Additional coefficient results support the convergence constraint predicted by Theorem 2.1.

  • Experiments use Cora, Citeseer, and Pubmed with 20 training nodes per class, 500 validation nodes, and 1,000 test nodes.Results are averaged over 10 runs for each model.
  • ChebNet uses two convolutional layers, with K = 2 or K = 10 and corresponding hidden-unit settings of 32 or 16.GCN uses two layers with 64 hidden units, while GPR-GNN and BernNet use two-layer MLPs with 64 hidden units and K = 10.
  • Each model has approximately 100k parameters on Cora, supporting parameter-count fairness across methods.For ChebNet with K = 10, hidden units are already 16; reducing them further deteriorates results.
  • ChebBase/k coefficients more readily satisfy the convergence constraint than ChebBase coefficients on Citeseer and Pubmed.These observations validate Theorem 2.1.

E.2 Semi-supervised node classification with polynomial based methods

Semi-supervised experiments compare polynomial-based methods under paper-following baseline settings and separately tuned layers. ChebNetII performs nearly identically across split strategies and leads on most datasets.

  • Baseline hyperparameters follow the original papers, while ARMA uses two parallel stacks, one layer, and skip-dropout optimized over {0.25, 0.75}.
  • ChebNetII uses a two-layer MLP with 64 hidden units and separately optimizes linear-layer and propagation-layer hyperparameters.
  • ChebNetII achieves the best performance on seven of eight datasets with fixed splits, nearly matching its random-split results.The authors interpret this as evidence of the Chebyshev basis’s superior expression power.

E.3 Full-supervised node classification

Full-supervised experiments use matched baseline settings and separately tuned ChebNetII linear and propagation components.

  • Baseline settings are kept consistent for semi-supervised experiments, while several methods use full-supervised settings reported in their original papers.
  • ChebNetII uses Equation (8) for propagation and a two-layer MLP with 64 hidden units across all datasets.Linear-layer and propagation-layer hyperparameters are optimized separately.

E.4 Scalability of ChebNetII

ChebNetII is evaluated under dataset-specific experimental settings for large heterophilic and OGB graphs. Its learned filters exhibit dataset-dependent spectral shapes, including comb-like, band-rejection, and low-pass responses.

  • Large heterophilic graphs: Large heterophilic graphs use five shared random 50/25/25 train/validation/test splits per dataset, with accuracy or ROC AUC as the evaluation metric.ROC AUC is used for genius; accuracy is used for most other datasets.
  • OGB datasets: For OGB datasets, ChebNetII uses Equation (12) and pre-computes Tk(ˆL)X for k = 0, · · · , K with K = 10.The settings and hyper-parameters are taken from the baseline papers.
  • OGB datasets: Table 15 reports the hyper-parameters used by ChebNetII on OGB datasets.These hyper-parameters accompany the OGB experimental configuration.
  • Learned filters: Figure 6 presents the filters learned by BernNet and ChebNetII on real-world datasets.The figure concerns full-supervised node classification.
  • Learned filters: ChebNetII and BernNet learn comb-like filters on Chameleon and Squirrel, band-rejection pass filters on Texas, and low-pass filters on Citeseer.ChebNetII's learned filter shape is relatively more complex than BernNet's.
Loading 2202.03580v5…