mlsanityData to 14 Oct 2026

Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum

arXiv 2506.05530 ↗First posted 5 Jun 2025cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

Spectral features are widely incorporated within Graph Neural Networks (GNNs) to improve their expressive power, or their ability to distinguish among non-isomorphic graphs. One popular example is the usage of graph Laplacian eigenvectors for positional encoding in MPNNs and Graph Transformers. The expressive power of such Spectrally-enhanced GNNs (SGNNs) is usually evaluated via the k-WL graph isomorphism test hierarchy and homomorphism counting. Yet, these frameworks align poorly with the graph spectra, yielding limited insight into SGNNs' expressive power. We leverage a well-studied paradigm of classifying graphs by their largest eigenvalue multiplicity to introduce an expressivity hierarchy for SGNNs. We then prove that many SGNNs are incomplete even on graphs with distinct eigenvalues. To mitigate this deficiency, we adapt rotation equivariant neural networks to the graph spectra setting to propose a method to provably improve SGNNs' expressivity on simple spectrum graphs. We empirically verify our theoretical claims via an image classification experiment on the MNIST Superpixel dataset and eigenvector canonicalization on graphs from ZINC.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 45 of its 54 references that are in the map. First posted on arXiv 5 Jun 2025.

Builds on

45 of 54 references.

References · 45

  1. 2018How Powerful are Graph Neural Networks?cited by 4,393
  2. 2021E(n) Equivariant Graph Neural Networkscited by 965
  3. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  4. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  5. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  6. 2020Benchmarking Graph Neural Networkscited by 680
  7. 2017SchNet: A continuous-filter convolutional neural network for modeling quantum interactionscited by 571
  8. 2021Rethinking Graph Transformers with Spectral Attentioncited by 473
  9. 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
  10. 2019Provably Powerful Graph Networkscited by 389
  11. 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
  12. 2017CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filterscited by 203
33 more
  1. 2019What graph neural networks cannot learn: depth vs widthcited by 201
  2. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 179
  3. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  4. 2021Equivariant Subgraph Aggregation Networkscited by 154
  5. 2023Graph Inductive Biases in Transformers without Message Passingcited by 153
  6. 2021GraphiT: Encoding Graph Structure in Transformerscited by 147
  7. 2021Scalars are universal: Equivariant machine learning, structured like classical physicscited by 127
  8. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  9. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  10. 2023On the Expressive Power of Geometric Graph Neural Networkscited by 90
  11. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  12. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  13. 2022A Short Tutorial on The Weisfeiler-Lehman Test And Its Variantscited by 52
  14. 2024Equivariant Frames and the Impossibility of Continuous Canonicalizationcited by 43
  15. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  16. 2023On the Stability of Expressive Positional Encodings for Graphscited by 33
  17. 2024A Canonicalization Perspective on Invariant and Equivariant Learningcited by 27
  18. 2023Graph Neural Networks Use Graphs When They Shouldn'tcited by 26
  19. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  20. 2023Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embeddingcited by 21
  21. 2021Implicit Bias of Linear Equivariant Networkscited by 19
  22. 2022Affinity-Aware Graph Networkscited by 17
  23. 2025Improving Equivariant Networks with Probabilistic Symmetry Breakingcited by 16
  24. 2022Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Coloringscited by 15
  25. 2024On the Expressive Power of Spectral Invariant Graph Neural Networkscited by 15
  26. 2024Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphscited by 14
  27. 2023Complete Neural Networks for Complete Euclidean Graphscited by 10
  28. 2024Weisfeiler Leman for Euclidean Equivariant Machine Learningcited by 10
  29. 2024A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarseningcited by 8
  30. 2024On the Expressive Power of Sparse Geometric MPNNscited by 7
  31. 2025Towards Invariance to Node Identifiers in Graph Neural Networkscited by 4
  32. 2025Homomorphism Expressivity of Spectral Invariant Graph Neural Networkscited by 4
  33. 2024Towards Stable, Globally Expressive Graph Representations with Laplacian Eigenvectorscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025Adaptive Canonicalization with Application to Invariant Anisotropic Geometric Networkscited by 3
  2. 2026When and How to Canonize: A Generalization Perspectivecited by 0
  3. 2026Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Themcited by 0