# Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited

arXiv: https://arxiv.org/abs/2202.03580 · HTML: https://mlsanity.com/paper/2202.03580/

## Key facts

- Cited by 87 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 58 references that are in the map.
- First posted on arXiv 4 Feb 2022.

## Builds on (most cited first, 30 of 34)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Multi-Label Image Recognition with Graph Convolutional Networks](https://mlsanity.com/paper/1904.03582/) (2019)
- [Session-based Recommendation with Graph Neural Networks](https://mlsanity.com/paper/1811.00855/) (2018)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Semantic Graph Convolutional Networks for 3D Human Pose Regression](https://mlsanity.com/paper/1904.03345/) (2019)
- [CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filters](https://mlsanity.com/paper/1705.07664/) (2017)
- [BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation](https://mlsanity.com/paper/2106.10994/) (2021)
- [Graph Neural Networks with convolutional ARMA filters](https://mlsanity.com/paper/1901.01343/) (2019)
- [Traffic Graph Convolutional Recurrent Neural Network: A Deep Learning Framework for Network-Scale Traffic Learning and Forecasting](https://mlsanity.com/paper/1802.07007/) (2018)
- [Interpreting and Unifying Graph Neural Networks with An Optimization Framework](https://mlsanity.com/paper/2101.11859/) (2021)
- [DeepInf: Social Influence Prediction with Deep Learning](https://mlsanity.com/paper/1807.05560/) (2018)
- [PDE-GCN: Novel Architectures for Graph Neural Networks Motivated by Partial Differential Equations](https://mlsanity.com/paper/2108.01938/) (2021)
- [Dirichlet Energy Constrained Learning for Deep Graph Neural Networks](https://mlsanity.com/paper/2107.02392/) (2021)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)

## Built on by (most cited first, 30 of 87)

- [Specformer: Spectral Graph Neural Networks Meet Transformers](https://mlsanity.com/paper/2303.01028/) (2023)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Graph Neural Networks with Learnable and Optimal Polynomial Bases](https://mlsanity.com/paper/2302.12432/) (2023)
- [A Review of Graph Neural Networks in Epidemic Modeling](https://mlsanity.com/paper/2403.19852/) (2024)
- [Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions](https://mlsanity.com/paper/2306.15427/) (2023)
- [A Survey on Spectral Graph Neural Networks](https://mlsanity.com/paper/2302.05631/) (2023)
- [How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing](https://mlsanity.com/paper/2405.12474/) (2024)
- [HoloNets: Spectral Convolutions do extend to Directed Graphs](https://mlsanity.com/paper/2310.02232/) (2023)
- [Spatio-Spectral Graph Neural Networks](https://mlsanity.com/paper/2405.19121/) (2024)
- [Node-wise Filtering in Graph Neural Networks: A Mixture of Experts Approach](https://mlsanity.com/paper/2406.03464/) (2024)
- [Graph Distillation with Eigenbasis Matching](https://mlsanity.com/paper/2310.09202/) (2023)
- [FedSSP: Federated Graph Learning with Spectral Knowledge and Personalized Preference](https://mlsanity.com/paper/2410.20105/) (2024)
- [Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier](https://mlsanity.com/paper/2408.09212/) (2024)
- [Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Tasks](https://mlsanity.com/paper/2506.07624/) (2025)
- [LightDiC: A Simple yet Effective Approach for Large-scale Digraph Representation Learning](https://mlsanity.com/paper/2401.11772/) (2024)
- [FUGNN: Harmonizing Fairness and Utility in Graph Neural Networks](https://mlsanity.com/paper/2405.17034/) (2024)
- [PolyFormer: Scalable Node-wise Filters via Polynomial Graph Transformer](https://mlsanity.com/paper/2407.14459/) (2024)
- [TEAM: Topological Evolution-aware Framework for Traffic Forecasting--Extended Version](https://mlsanity.com/paper/2410.19192/) (2024)
- [On Manipulating Signals of User-Item Graph: A Jacobi Polynomial-based Graph Collaborative Filtering](https://mlsanity.com/paper/2306.03624/) (2023)
- [Spectral Heterogeneous Graph Convolutions via Positive Noncommutative Polynomials](https://mlsanity.com/paper/2305.19872/) (2023)
- [Fairness-aware Message Passing for Graph Neural Networks](https://mlsanity.com/paper/2306.11132/) (2023)
- [PGODE: Towards High-quality System Dynamics Modeling](https://mlsanity.com/paper/2311.06554/) (2023)
- [Graph Spectral Filtering with Chebyshev Interpolation for Recommendation](https://mlsanity.com/paper/2505.00552/) (2025)
- [S2FGL: Spatial Spectral Federated Graph Learning](https://mlsanity.com/paper/2507.02409/) (2025)
- [From Cluster Assumption to Graph Convolution: Graph-based Semi-Supervised Learning Revisited](https://mlsanity.com/paper/2309.13599/) (2023)
- [Shape-aware Graph Spectral Learning](https://mlsanity.com/paper/2310.10064/) (2023)
- [Learning to Approximate Adaptive Kernel Convolution on Graphs](https://mlsanity.com/paper/2401.11840/) (2024)
- [Graph convolutional network as a fast statistical emulator for numerical ice sheet modeling](https://mlsanity.com/paper/2402.05291/) (2024)
- [AGS-GNN: Attribute-guided Sampling for Graph Neural Networks](https://mlsanity.com/paper/2405.15218/) (2024)
- [A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectiveness](https://mlsanity.com/paper/2406.09675/) (2024)

## Abstract (arXiv)

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.