mlsanityData to 14 Oct 2026

An Effective Universal Polynomial Basis for Spectral Graph Neural Networks

arXiv 2311.18177 ↗First posted 30 Nov 2023cs.LG cs.SI eess.SPcited by 0

Not on the map. Why?

Abstract (arXiv)

Spectral Graph Neural Networks (GNNs), also referred to 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 the prohibitive computations, numerous polynomial filters by leveraging distinct polynomials have been proposed to approximate the desired graph filters. However, polynomials in the majority of polynomial filters are predefined and remain fixed across all graphs, failing to accommodate the diverse heterophily degrees across different graphs. To tackle this issue, we first investigate the correlation between polynomial bases of desired graph filters and the degrees of graph heterophily via a thorough theoretical analysis. Afterward, we develop an adaptive heterophily basis by incorporating graph heterophily degrees. Subsequently, we integrate this heterophily basis with the homophily basis, creating a universal polynomial basis UniBasis. In consequence, we devise a general polynomial filter UniFilter. Comprehensive experiments on both real-world and synthetic datasets with varying heterophily degrees significantly support the superiority of UniFilter, demonstrating the effectiveness and generality of UniBasis, as well as its promising capability as a new method for graph analysis.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 33 of its 48 references that are in the map. First posted on arXiv 30 Nov 2023.

Builds on

33 of 48 references.

References · 33

  1. 2017Attention Is All You Needcited by 60,361
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2017Graph Attention Networkscited by 8,923
  4. 2017Inductive Representation Learning on Large Graphscited by 6,320
  5. 2021Convex optimizationcited by 2,515
  6. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  7. 2019Simplifying Graph Convolutional Networkscited by 1,477
  8. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 993
  9. 2020Simple and Deep Graph Convolutional Networkscited by 860
  10. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 826
  11. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 595
  12. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
21 more
  1. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 443
  2. 2019Diffusion Improves Graph Learningcited by 414
  3. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 311
  4. 2020SIGN: Scalable Inception Graph Neural Networkscited by 284
  5. 2021BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximationcited by 195
  6. 2022Finding Global Homophily in Graph Neural Networks When Meeting Heterophilycited by 179
  7. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  8. 2022Revisiting Heterophily For Graph Neural Networkscited by 169
  9. 2019Drop an Octave: Reducing Spatial Redundancy in Convolutional Neural Networks with Octave Convolutioncited by 140
  10. 2021Interpreting and Unifying Graph Neural Networks with An Optimization Frameworkcited by 131
  11. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 105
  12. 2023Specformer: Spectral Graph Neural Networks Meet Transformerscited by 102
  13. 2021Dirichlet Energy Constrained Learning for Deep Graph Neural Networkscited by 97
  14. 2021Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patternscited by 95
  15. 2021Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?cited by 82
  16. 2023Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothingcited by 67
  17. 2023Graph Neural Networks with Learnable and Optimal Polynomial Basescited by 36
  18. 2019Optimizing Generalized PageRank Methods for Seed-Expansion Community Detectioncited by 35
  19. 2020Bridging the Gap Between Spectral and Spatial Domains in Graph Neural Networkscited by 27
  20. 2022EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networkscited by 26
  21. 2022Simplified Graph Convolution with Heterophilycited by 17

Built on by

Not cited yet.