Research map / Graph learning / GNN architectures
Position: Spectral GNNs Rely Less on Graph Fourier Basis than Conceived
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
A position paper arguing that spectral GNNs rely less on the graph Fourier basis than assumed, supported by eigenvector localization visualizations and stability/generalization bounds showing expressive polynomial filters hurt stability and generalization.
Problem
Spectral GNNs are motivated by graph Fourier analysis, but it is unclear whether Laplacian eigenvectors preserve the semantic properties of classical Fourier bases, and why expressive polynomial filters are avoided in practice.
Approach
Critically examines the graph Fourier basis analogy (via concept migration, localization of eigenvectors, and historical sources) and argues that limits on polynomial filter expressiveness are fundamental stability and generalization barriers, so spectral GNNs may not work as truly spectral methods.
Key results
- High-frequency Laplacian eigenvectors on Cora show significant localization, partially alleviated by normalizing the Laplacian.
- Theoretical bounds show spectral GNN output stability and transductive generalization gap grow with polynomial order K and coefficient magnitude.
- Ideal spectral filter interpolating all eigenvalue responses would have large max value, large Lipschitz constant, and require large order.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase polynomial filter order K | Spectral GNN polynomial filters · Graph structure perturbation | filter stability | Hurt |
| increase polynomial coefficient magnitude | Spectral GNNs · Inductive graph classification | out-of-domain generalization | Hurt |
| use a normalized rather than unnormalized Laplacian | Graph Fourier eigenvectors · Cora | eigenvector localization | Helped |
Surprising findings
- High-frequency eigenvectors on a sphere mesh show Fourier-like patterns, while those on a horse mesh are highly localized, suggesting the Fourier analogy depends heavily on graph structure.
- Expressive polynomial filters that would exploit the Fourier basis are argued to be fundamentally unstable, so the avoidance of complex filters may hide questions about the basis's role.
Limitations
- Experimental evidence is limited to visualizations and localization measures on Cora and two meshes, without downstream performance experiments.
- Theoretical bounds are upper bounds and do not show that expressive filters necessarily fail in practice.
Experimental setup
Datasets: Cora horse mesh sphere mesh
Metrics: eigenvector localization (sum of fourth powers of entries)
Builds on: Tree mover's distance (Chuang & Jegelka, 2022) Gama et al. 2020 stability of graph filters Kenlay et al. 2020 BernNet/ChebNet-style spectral polynomial filters
Closest papers by meaning
- How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing (ICML 2024 · similarity 0.93)
- HoloNets: Spectral Convolutions do extend to Directed Graphs (ICLR 2024 · similarity 0.91)
- SLOG: An Inductive Spectral Graph Neural Network Beyond Polynomial Filter (ICML 2024 · similarity 0.91)
- Unifying Homophily and Heterophily for Spectral Graph Neural Networks via Triple Filter Ensembles (NeurIPS 2024 · similarity 0.91)
- WaveNet: Tackling Non-stationary Graph Signals via Graph Spectral Wavelets (AAAI 2024 · similarity 0.91)
- On the Expressive Power of Spectral Invariant Graph Neural Networks (ICML 2024 · similarity 0.91)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.