# How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 57 references that are in the map.
- First posted on arXiv 21 May 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [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)
- [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)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [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)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (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)
- [A Survey on Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2303.10993/) (2023)
- [BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation](https://mlsanity.com/paper/2106.10994/) (2021)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Revisiting Heterophily For Graph Neural Networks](https://mlsanity.com/paper/2210.07606/) (2022)
- [On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology](https://mlsanity.com/paper/2302.02941/) (2023)
- [Drop an Octave: Reducing Spatial Redundancy in Convolutional Neural Networks with Octave Convolution](https://mlsanity.com/paper/1904.05049/) (2019)
- [Interpreting and Unifying Graph Neural Networks with An Optimization Framework](https://mlsanity.com/paper/2101.11859/) (2021)
- [FoSR: First-order spectral rewiring for addressing oversquashing in GNNs](https://mlsanity.com/paper/2210.11790/) (2022)
- [Specformer: Spectral Graph Neural Networks Meet Transformers](https://mlsanity.com/paper/2303.01028/) (2023)
- [Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature](https://mlsanity.com/paper/2211.15779/) (2022)

## Built on by (most cited first, 24 of 24)

- [Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning](https://mlsanity.com/paper/2505.15547/) (2025)
- [Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models](https://mlsanity.com/paper/2510.17457/) (2025)
- [A General Graph Spectral Wavelet Convolution via Chebyshev Order Decomposition](https://mlsanity.com/paper/2405.13806/) (2024)
- [Homophily Heterogeneity Matters in Graph Federated Learning: A Spectrum Sharing and Complementing Perspective](https://mlsanity.com/paper/2502.13732/) (2025)
- [Flexible Diffusion Scopes with Parameterized Laplacian for Heterophilic Graph Learning](https://mlsanity.com/paper/2409.09888/) (2024)
- [Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness-Generalization Perspective](https://mlsanity.com/paper/2412.09805/) (2024)
- [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)
- [Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing](https://mlsanity.com/paper/2506.06582/) (2025)
- [Q-AGNN: Quantum-Enhanced Attentive Graph Neural Network for Intrusion Detection](https://mlsanity.com/paper/2603.22365/) (2026)
- [Bridging Smoothness and Approximation: Theoretical Insights into Over-Smoothing in Graph Neural Networks](https://mlsanity.com/paper/2407.01281/) (2024)
- [DLGNet: Hyperedge Classification through Directed Line Graphs for Chemical Reactions](https://mlsanity.com/paper/2410.06969/) (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)
- [Full-Spectrum Graph Neural Networks: Expressive and Scalable](https://mlsanity.com/paper/2605.05759/) (2026)
- [Heterophilous Distribution Propagation for Graph Neural Networks](https://mlsanity.com/paper/2405.20640/) (2024)
- [Enhancing Spectral Graph Neural Networks with LLM-Predicted Homophily](https://mlsanity.com/paper/2506.14220/) (2025)
- [HeSRN: Representation Learning On Heterogeneous Graphs via Slot-Aware Retentive Network](https://mlsanity.com/paper/2510.09767/) (2025)
- [How Wide and How Deep? Mitigating Over-Squashing of GNNs via Channel Capacity Constrained Estimation](https://mlsanity.com/paper/2511.06443/) (2025)
- [Beyond Rigid Alignment: Graph Federated Learning via Dual Manifold Calibration](https://mlsanity.com/paper/2605.06260/) (2026)
- [Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation](https://mlsanity.com/paper/2605.10975/) (2026)
- [Graph Navier Stokes Networks](https://mlsanity.com/paper/2605.21247/) (2026)
- [Convex--Concave Quadratic Spectral Filtering for Graph Neural Networks](https://mlsanity.com/paper/2606.24956/) (2026)
- [Continuous-Time Quantum Walks based Graph Neural Network](https://mlsanity.com/paper/2608.20738/) (2026)
- [Spectral Graph Neural Networks with Hermite Polynomials: A Comprehensive Study](https://mlsanity.com/paper/2609.28979/) (2026)

## Abstract (arXiv)

Spectral Graph Neural Networks (GNNs), alternatively known as graph filters, have gained increasing prevalence for heterophily graphs. Optimal graph filters rely on Laplacian eigendecomposition for Fourier transform. In an attempt to avert prohibitive computations, numerous polynomial filters have been proposed. However, polynomials in the majority of these filters are predefined and remain fixed across different graphs, failing to accommodate the varying degrees of heterophily. Addressing this gap, we demystify the intrinsic correlation between the spectral property of desired polynomial bases and the heterophily degrees via thorough theoretical analyses. Subsequently, we develop a novel adaptive heterophily basis wherein the basis vectors mutually form angles reflecting the heterophily degree of the graph. We integrate this heterophily basis with the homophily basis to construct a universal polynomial basis UniBasis, which devises a polynomial filter based graph neural network - UniFilter. It optimizes the convolution and propagation in GNN, thus effectively limiting over-smoothing and alleviating over-squashing. Our extensive experiments, conducted on a diverse range of real-world and synthetic datasets with varying degrees of heterophily, support the superiority of UniFilter. These results not only demonstrate the universality of UniBasis but also highlight its proficiency in graph explanation.