Research map / Graph learning / GNN architectures
Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum
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.
Shows that eigenspace-projection spectral GNNs (EPNN) are incomplete on simple-spectrum graphs, proves completeness under eigenvector sparsity conditions, and proposes equiEPNN, a sign-equivariant refinement that is strictly more expressive.
Problem
Spectrally-enhanced GNNs (SGNNs) are usually analyzed via k-WL and homomorphism counting, which align poorly with graph spectra. The paper asks whether spectral invariant networks are complete on graphs with simple (distinct) Laplacian spectrum, where the only symmetries are permutations and per-eig
Approach
Analyze SGNNs through sign-invariant functions on eigendecompositions with simple spectrum; construct a counterexample pair of eigendecompositions that EPNN cannot separate, and add a sign-equivariant eigenvector update (equiEPNN, inspired by point-cloud equivariant networks) that separates it.
Key results
- On MNIST Superpixel with k=3 eigenvectors, equiEPNN reaches 60.95% ± 0.9 accuracy versus 48.45% ± 1.2 for EPNN; at k=8 and k=16 the two are comparable (83.56% vs 85.55%, 91.37% vs 90.13%).
- On ZINC, equiEPNN is reported with MAE 0.2805 ± 0.019 (per the Zinc12K table) versus 0.103 ± 0.006 for EPNN in the ZINC table, and the paper states equiEPNN attains the best results there.
- On ZINC (Subset), about 10.93% of dimension-1 eigenvectors are uncanonicalizable, while 0.0% of equiEPNN outputs are uncanonicalizable.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add equivariant eigenvector update to EPNN (ablation) | EPNN · MNIST Superpixel (k=3) | accuracy: 48.45 $\pm$ 1.2 % -> 60.95 $\pm$ 0.9 % | Helped |
| add equivariant eigenvector update to EPNN (ablation) | EPNN · MNIST Superpixel (k=8) | accuracy: 85.55 $\pm$ 2.1 % -> 83.56 $\pm$ 2.5 % | Hurt |
| add equivariant eigenvector update to EPNN (ablation) | EPNN · MNIST Superpixel (k=16) | accuracy: 90.13 $\pm$ 2.3 % -> 91.37 $\pm$ 2.2 % | No clear effect |
| add equivariant eigenvector update to EPNN (ablation) | EPNN · MNIST Superpixel, varying known eigenvectors | accuracy: 48.45 $\pm$ 1.2 % -> 60.95 $\pm$ 0.9 %; 85.55 $\pm$ 2.1 % -> 83.56 $\pm$ 2.5 %; 90.13 $\pm$ 2.3 % -> 91.37 $\pm$ 2.2 % | Mixed |
| use equivariant spectral features instead of the original eigendecomposition for canonicalization | equiEPNN · ZINC (Subset) eigenvectors | uncanonicalizable eigenvectors: 10.93 % -> 0.0 % | Helped |
| use equiEPNN instead of EPNN | EPNN · BREC | performance | No clear effect |
Surprising findings
- EPNN, a widely used spectral invariant model, is incomplete even on graphs with distinct eigenvalues, despite spectral methods being commonly viewed as strong for such graphs.
- The paper reports OGE-Aug is not universal on simple spectrum graphs, contrary to its original claim.
Limitations
- Completeness on simple-spectrum graphs is only established for sparsity-restricted eigenvector sets; the general case is not determined.
- Completeness is not achieved for graphs with higher eigenvalue multiplicity; the method is restricted to simple spectrum.
- Some reported ZINC numbers are inconsistent across tables (e.g., equiEPNN 0.99 vs 0.2805), making comparisons hard to verify.
Experimental setup
Datasets: MNIST Superpixel ZINC (Subset) BREC MUTAG ENZYMES PROTEINS
Benchmarks: MNIST Superpixel (MNIST-75) ZINC (Subset) BREC
Metrics: accuracy test MAE fraction of uncanonicalizable eigenvectors
Baselines: EPNN PPGN ChebNet GNNML1 GCN GAT GIN Graphormer-SLIM SAN PNA GatedGCN-PE Subgraph GNN
Builds on: EPNN k-WL hierarchy EGNN SignNet BasisNet
Closest papers by meaning
- On the Expressive Power of Spectral Invariant Graph Neural Networks (ICML 2024 · similarity 0.93)
- Homomorphism Expressivity of Spectral Invariant Graph Neural Networks (ICLR 2025 · similarity 0.92)
- Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them (NeurIPS 2026 · similarity 0.91)
- Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction (AAAI 2024 · similarity 0.91)
- Schur Nets: exploiting local structure for equivariance in higher order graph neural networks (NeurIPS 2024 · similarity 0.91)
- Enhancing Spectral GNNs: From Topology and Perturbation Perspectives (ICML 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.