mlsanityData to 7 Oct 2026

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

arXiv 2405.12474 ↗First posted 21 May 2024cs.LG cs.SIcited by 24

Not on the map. Why?

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.

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

Builds on

43 of 57 references.

References · 43

  1. 2017Attention Is All You Needcited by 59,932
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2017Inductive Representation Learning on Large Graphscited by 6,284
  5. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  6. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  7. 2019Simplifying Graph Convolutional Networkscited by 1,470
  8. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  9. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  10. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  11. 2020Simple and Deep Graph Convolutional Networkscited by 857
  12. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
31 more
  1. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  2. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  3. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  4. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 442
  5. 2019Diffusion Improves Graph Learningcited by 414
  6. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 309
  7. 2020SIGN: Scalable Inception Graph Neural Networkscited by 283
  8. 2023A Survey on Oversmoothing in Graph Neural Networkscited by 246
  9. 2021BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximationcited by 195
  10. 2022Finding Global Homophily in Graph Neural Networks When Meeting Heterophilycited by 179
  11. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  12. 2022Revisiting Heterophily For Graph Neural Networkscited by 169
  13. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 163
  14. 2019Drop an Octave: Reducing Spatial Redundancy in Convolutional Neural Networks with Octave Convolutioncited by 140
  15. 2021Interpreting and Unifying Graph Neural Networks with An Optimization Frameworkcited by 131
  16. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 104
  17. 2023Specformer: Spectral Graph Neural Networks Meet Transformerscited by 102
  18. 2021Dirichlet Energy Constrained Learning for Deep Graph Neural Networkscited by 97
  19. 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 96
  20. 2021Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patternscited by 95
  21. 2022Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisitedcited by 87
  22. 2023Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothingcited by 67
  23. 2021How Framelets Enhance Graph Neural Networkscited by 46
  24. 2023Graph Neural Networks with Learnable and Optimal Polynomial Basescited by 36
  25. 2019Optimizing Generalized PageRank Methods for Seed-Expansion Community Detectioncited by 35
  26. 2020Bridging the Gap Between Spectral and Spatial Domains in Graph Neural Networkscited by 26
  27. 2022EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networkscited by 26
  28. 2023A Survey on Spectral Graph Neural Networkscited by 26
  29. 2022Simplified Graph Convolution with Heterophilycited by 17
  30. 2023Node-wise Diffusion for Scalable Graph Learningcited by 17
  31. 2024Optimizing Polynomial Graph Filters: A Novel Adaptive Krylov Subspace Approachcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 6; 2025: 9; 2026: 9.

24 papers.

Sort:

  1. 2025Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learningcited by 18
  2. 2025Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Modelscited by 6
  3. 2024A General Graph Spectral Wavelet Convolution via Chebyshev Order Decompositioncited by 4
  4. 2025Homophily Heterogeneity Matters in Graph Federated Learning: A Spectrum Sharing and Complementing Perspectivecited by 4
  5. 2024Flexible Diffusion Scopes with Parameterized Laplacian for Heterophilic Graph Learningcited by 3
  6. 2024Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness-Generalization Perspectivecited by 2
  7. 2025Hyperbolic-PDE GNN: Spectral Graph Neural Networks in the Perspective of A System of Hyperbolic Partial Differential Equationscited by 2
  8. 2025Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passingcited by 2
  9. 2026Q-AGNN: Quantum-Enhanced Attentive Graph Neural Network for Intrusion Detectioncited by 2
  10. 2024Bridging Smoothness and Approximation: Theoretical Insights into Over-Smoothing in Graph Neural Networkscited by 1
  11. 2024DLGNet: Hyperedge Classification through Directed Line Graphs for Chemical Reactionscited by 1
  12. 2025Piecewise Constant Spectral Graph Neural Networkcited by 1
12 more
  1. 2026Heterogeneity-Aware Knowledge Sharing for Graph Federated Learningcited by 1
  2. 2024Heterophilous Distribution Propagation for Graph Neural Networkscited by 0
  3. 2025Enhancing Spectral Graph Neural Networks with LLM-Predicted Homophilycited by 0
  4. 2025HeSRN: Representation Learning On Heterogeneous Graphs via Slot-Aware Retentive Networkcited by 0
  5. 2025How Wide and How Deep? Mitigating Over-Squashing of GNNs via Channel Capacity Constrained Estimationcited by 0
  6. 2026Full-Spectrum Graph Neural Networks: Expressive and Scalablecited by 0
  7. 2026Beyond Rigid Alignment: Graph Federated Learning via Dual Manifold Calibrationcited by 0
  8. 2026Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigationcited by 0
  9. 2026Graph Navier Stokes Networkscited by 0
  10. 2026Convex--Concave Quadratic Spectral Filtering for Graph Neural Networkscited by 0
  11. 2026Continuous-Time Quantum Walks based Graph Neural Networkcited by 0
  12. 2026Spectral Graph Neural Networks with Hermite Polynomials: A Comprehensive Studycited by 0