Research map / Graph learning / GNN architectures
Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Tasks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Revisits ChebNet as a long-range GNN and proposes Stable-ChebNet, an antisymmetric forward-Euler discretization of ChebNet that stabilizes propagation without eigendecomposition, positional encodings, or rewiring.
Problem
MPNNs struggle to capture long-range dependencies (over-squashing, oversmoothing), while rewiring and graph transformers add computational cost. ChebNet, a high-order spectral GNN, is rarely evaluated as a long-range baseline and its high-order polynomial filters cause unstable training dynamics.
Approach
Cast ChebNet as an ODE dX/dt = sum_k T_k(L) X W_k, constrain the weights to be antisymmetric (W_k - W_k^T - gamma I form) and discretize with forward Euler, yielding a non-dissipative, stable propagation with purely imaginary Jacobian eigenvalues while keeping ChebNet's cost.
Key results
- On ogbn-arxiv Stable-ChebNet reaches 75.73% accuracy vs 73.27% for vanilla ChebNet and above the listed graph transformers.
- On peptides-func Stable-ChebNet achieves 70.32 AP vs 69.61 for ChebNet, and on peptides-struct 0.2542 MAE, while S2GCN is best at 72.75 AP.
- On barbell graphs with N=100 and K=20, ChebNet has MSE 0.87 while Stable-ChebNet reaches 0.21.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the standard ChebNet update with Stable-ChebNet's stable Euler formulation | ChebNet · Diameter | log10(MSE): -0.1517 -> -0.2477 | Helped |
| Replace the standard ChebNet update with Stable-ChebNet's stable Euler formulation | ChebNet · SSSP | log10(MSE): -1.8519 -> -2.2111 | Helped |
| Replace the standard ChebNet update with Stable-ChebNet's stable Euler formulation | ChebNet · Eccentricity | log10(MSE): -1.2151 -> -2.1043 | Helped |
| Use the stable Euler formulation instead of the standard ChebNet update at K=10 | ChebNet · Barbell N=70 K=10 | MSE: 1.08 ± 0.01 -> 0.06 ± 0.03 | Helped |
| Use the stable Euler formulation instead of the standard ChebNet update | ChebNet · Barbell N=100 K=20 | MSE: 0.87 ± 0.05 -> 0.21 ± 0.27 | Helped |
| Use the stable Euler formulation instead of the standard ChebNet update | ChebNet · Barbell N=50 K=10 | MSE: 0.05 ± 0.00 -> 0.05 ± 0.00 | No clear effect |
| Add the stable Euler formulation | ChebNet · ogbn-arxiv | accuracy: 73.27 ± 0.23 -> 75.73 ± 0.51 | Helped |
| Add the stable Euler formulation | ChebNet · ogbn-proteins | accuracy: 77.55 ± 0.43 -> 79.55 ± 0.34 | Helped |
| Add the stable Euler formulation | ChebNet · peptides-func | AP: 69.61 ± 0.33 -> 70.32 ± 0.26 | Helped |
| Add the stable Euler formulation | ChebNet · peptides-struct | MAE: 0.2627 ± 0.0033 -> 0.2542 ± 0.0030 | Helped |
| Use Stable-ChebNet instead of ChebNet | ChebNet · Amazon-ratings | accuracy | Mixed |
| Use Stable-ChebNet instead of ChebNet | ChebNet · Roman-empire | accuracy | Mixed |
Surprising findings
- Vanilla ChebNet is competitive with or better than many MPNNs, rewiring methods and graph transformers on long-range benchmarks despite being rarely included in such studies.
- Stable-ChebNet does not outperform all baselines on heterophilic benchmarks (e.g., Amazon-ratings 53.15 vs Polynormer 54.81), and the authors caution these results do not establish long-range propagation.
Limitations
- Scope limited to ChebNet; extension to other spectral GNN families left to future work.
- Stable-ChebNet is below the best reported results on several benchmarks (e.g., peptides-func vs S2GCN, ogbn-proteins vs SPEXPHORMER), so it is only near state-of-the-art.
- Heterophilic results do not by themselves demonstrate long-range propagation.
Experimental setup
Datasets: Graph property prediction synthetic dataset (Corso et al.) Barbell graphs ogbn-arxiv ogbn-proteins peptides-func peptides-struct Roman-empire Amazon-ratings Minesweeper Tolokers RingTransfer
Benchmarks: ogbn-arxiv ogbn-proteins peptides-func peptides-struct Roman-empire Amazon-ratings Minesweeper Tolokers Graph property prediction (Diameter, SSSP, Eccentricity) Barbell over-squashing
Metrics: accuracy average precision MAE ROC-AUC MSE
Baselines: ChebNet GCN GCNII DRew-GCN GraphGPS Exphormer SGFormer NodeFormer S2GCN Graph Mamba
Builds on: ChebNet GCN GraphCON A-DGN DRew
Closest papers by meaning
- Graph Neural Networks Are More Than Filters: Revisiting and Benchmarking from A Spectral Perspective (ICLR 2025 · similarity 0.88)
- On the Expressive Power of Spectral Invariant Graph Neural Networks (ICML 2024 · similarity 0.87)
- SLOG: An Inductive Spectral Graph Neural Network Beyond Polynomial Filter (ICML 2024 · similarity 0.87)
- Spatio-Spectral Graph Neural Networks (NeurIPS 2024 · similarity 0.87)
- Position: Spectral GNNs Rely Less on Graph Fourier Basis than Conceived (ICML 2025 · similarity 0.87)
- Higher-Order Graphon Neural Networks: Approximation and Cut Distance (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.