# Graph Neural Networks with Learnable and Optimal Polynomial Bases

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 45 references that are in the map.
- First posted on arXiv 24 Feb 2023.

## Builds on (most cited first, 23 of 23)

- [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)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (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)
- [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)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [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)
- [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)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited](https://mlsanity.com/paper/2202.03580/) (2022)
- [Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth](https://mlsanity.com/paper/2105.04550/) (2021)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Node Dependent Local Smoothing for Scalable Graph Learning](https://mlsanity.com/paper/2110.14377/) (2021)
- [EdgeNets:Edge Varying Graph Neural Networks](https://mlsanity.com/paper/2001.07620/) (2020)
- [Improving Graph Attention Networks with Large Margin-based Constraints](https://mlsanity.com/paper/1910.11945/) (2019)

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

- [fKAN: Fractional Kolmogorov-Arnold Networks with trainable Jacobi basis functions](https://mlsanity.com/paper/2406.07456/) (2024)
- [How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing](https://mlsanity.com/paper/2405.12474/) (2024)
- [Breaking the Entanglement of Homophily and Heterophily in Semi-supervised Node Classification](https://mlsanity.com/paper/2312.04111/) (2023)
- [Spatio-Spectral Graph Neural Networks](https://mlsanity.com/paper/2405.19121/) (2024)
- [PolyFormer: Scalable Node-wise Filters via Polynomial Graph Transformer](https://mlsanity.com/paper/2407.14459/) (2024)
- [Spectral Heterogeneous Graph Convolutions via Positive Noncommutative Polynomials](https://mlsanity.com/paper/2305.19872/) (2023)
- [A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectiveness](https://mlsanity.com/paper/2406.09675/) (2024)
- [Clarify Confused Nodes via Separated Learning](https://mlsanity.com/paper/2306.02285/) (2023)
- [Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction](https://mlsanity.com/paper/2401.15603/) (2024)
- [Optimizing Polynomial Graph Filters: A Novel Adaptive Krylov Subspace Approach](https://mlsanity.com/paper/2403.07954/) (2024)
- [ERGNN: Spectral Graph Neural Network With Explicitly-Optimized Rational Graph Filters](https://mlsanity.com/paper/2412.19106/) (2024)
- [Rethinking Spectral Graph Neural Networks with Spatially Adaptive Filtering](https://mlsanity.com/paper/2401.09071/) (2024)
- [Homophily Heterogeneity Matters in Graph Federated Learning: A Spectrum Sharing and Complementing Perspective](https://mlsanity.com/paper/2502.13732/) (2025)
- [Simplified PCNet with Robustness](https://mlsanity.com/paper/2403.03676/) (2024)
- [Spectral GNN via Two-dimensional (2-D) Graph Convolution](https://mlsanity.com/paper/2404.04559/) (2024)
- [Equivariant Machine Learning on Graphs with Nonlinear Spectral Filters](https://mlsanity.com/paper/2406.01249/) (2024)
- [Scalable Graph Compressed Convolutions](https://mlsanity.com/paper/2407.18480/) (2024)
- [Toward Effective Digraph Representation Learning: A Magnetic Adaptive Propagation based Approach](https://mlsanity.com/paper/2501.11817/) (2025)
- [Addressing Noise and Stochasticity in Fraud Detection for Service Networks](https://mlsanity.com/paper/2505.00946/) (2025)
- [Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening](https://mlsanity.com/paper/2505.14033/) (2025)
- [Hyperbolic-PDE GNN: Spectral Graph Neural Networks in the Perspective of A System of Hyperbolic Partial Differential Equations](https://mlsanity.com/paper/2505.23014/) (2025)
- [Polynomial Selection in Spectral Graph Neural Networks: An Error-Sum of Function Slices Approach](https://mlsanity.com/paper/2404.15354/) (2024)
- [Piecewise Constant Spectral Graph Neural Network](https://mlsanity.com/paper/2505.04808/) (2025)
- [Heterogeneity-Aware Knowledge Sharing for Graph Federated Learning](https://mlsanity.com/paper/2601.21589/) (2026)
- [Position: Spectral GNNs Are Neither Spectral Nor Superior for Node Classification](https://mlsanity.com/paper/2603.19091/) (2026)
- [Full-Spectrum Graph Neural Networks: Expressive and Scalable](https://mlsanity.com/paper/2605.05759/) (2026)
- [An Effective Universal Polynomial Basis for Spectral Graph Neural Networks](https://mlsanity.com/paper/2311.18177/) (2023)
- [Toward Data-centric Directed Graph Learning: An Entropy-driven Approach](https://mlsanity.com/paper/2505.00983/) (2025)
- [Convexified Message-Passing Graph Neural Networks](https://mlsanity.com/paper/2505.18289/) (2025)
- [On the Impact of Downstream Tasks on Sampling and Reconstructing Noisy Graph Signals](https://mlsanity.com/paper/2509.10874/) (2025)

## Abstract (arXiv)

Polynomial filters, a kind of Graph Neural Networks, typically use a predetermined polynomial basis and learn the coefficients from the training data. It has been observed that the effectiveness of the model is highly dependent on the property of the polynomial basis. Consequently, two natural and fundamental questions arise: Can we learn a suitable polynomial basis from the training data? Can we determine the optimal polynomial basis for a given graph and node features? In this paper, we propose two spectral GNN models that provide positive answers to the questions posed above. First, inspired by Favard's Theorem, we propose the FavardGNN model, which learns a polynomial basis from the space of all possible orthonormal bases. Second, we examine the supposedly unsolvable definition of optimal polynomial basis from Wang & Zhang (2022) and propose a simple model, OptBasisGNN, which computes the optimal basis for a given graph structure and graph signal. Extensive experiments are conducted to demonstrate the effectiveness of our proposed models. Our code is available at https://github.com/yuziGuo/FarOptBasis.