Research map / Graph learning / GNN architectures
On the Expressive Power of Spectral Invariant Graph Neural Networks
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.
Introduces Eigenspace Projection GNN (EPNN) as a unified framework for spectral invariant GNNs, proves its expressive power is bounded by PSWL and hence strictly below 3-WL, and places distance-based, Basisnet, SPE, and higher-order spectral models in a single expressiveness hierarchy.
Problem
Characterize the expressive power of spectral invariant GNNs, which use eigenspace projections or spectral distances as invariant features.
Approach
EPNN treats the multiset of eigenspace projection values and eigenvalues for each node pair as an edge feature inside message passing on a fully connected graph; the authors show this unifies prior spectral invariant models, bound it by PSWL (a Subgraph GNN), and prove strict gaps across Siamese IGN, Weak Spectral IGN and Spectral IGN.
Key results
- On BREC, EPNN scores 53.8 total, versus 19.8 for Graphormer (SPD-WL) and 41.5 for NGNN (SWL).
- EPNN reaches 100.0 on Basic and 100.0 on Ext, matching PPGN on those subsets, but only 5.0 on CFI versus PPGN's 23.0.
- Theory: EPWL is bounded by PSWL and hence strictly bounded by 3-WL; Spectral k-IGN is as expressive as k-WL for k>2, so spectral features add no power to k-IGN.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use EPNN instead of Graphormer | BREC · BREC Total | accuracy: 19.8 -> 53.8 | Helped |
| Use EPNN instead of NGNN | BREC · BREC Total | accuracy: 41.5 -> 53.8 | Helped |
| Use EPNN instead of ESAN | BREC · BREC Total | accuracy: 55.2 -> 53.8 | Hurt |
| Use EPNN instead of PPGN | BREC · BREC Total | accuracy: 58.2 -> 53.8 | Hurt |
Surprising findings
- Spectral k-IGN and Spectral k-FGNN are no more expressive than k-IGN/k-FGNN, so commonly used spectral features add nothing to highly expressive higher-order GNNs.
- EPNN is strictly more expressive than BasisNet while storing only node representations, unlike BasisNet's O(n^3) per-triple representations.
Limitations
- Expressiveness results are theoretical; the only experiment is BREC, where EPNN underperforms PPGN on CFI (5.0 vs 23.0).
- Open question whether the Laplacian matrix is strictly more expressive than the adjacency matrix is not fully resolved.
- Higher-order spectral features (token graphs) are left as an open direction without an architecture or tight bound.
Experimental setup
Datasets: BREC
Benchmarks: BREC
Metrics: number of distinguished graph pairs (Basic, Reg, Ext, CFI, T
Baselines: Graphormer NGNN ESAN PPGN BasisNet SPE SignNet
Builds on: BasisNet SPE Subgraph GNN (PSWL) Generalized Distance WL k-IGN
Closest papers by meaning
- Homomorphism Expressivity of Spectral Invariant Graph Neural Networks (ICLR 2025 · similarity 0.94)
- Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum (NeurIPS 2025 · similarity 0.93)
- Enhancing Spectral GNNs: From Topology and Perturbation Perspectives (ICML 2025 · similarity 0.91)
- Position: Spectral GNNs Rely Less on Graph Fourier Basis than Conceived (ICML 2025 · similarity 0.91)
- Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction (AAAI 2024 · similarity 0.91)
- Graph Neural Networks Are More Than Filters: Revisiting and Benchmarking from A Spectral Perspective (ICLR 2025 · similarity 0.90)
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.