mlsanityData to 7 Oct 2026

Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them

arXiv 2605.23446 ↗First posted 22 May 2026cs.LG math.COcited by 0

Not on the map. Why?

Abstract (arXiv)

Graphs with a simple spectrum admit cubic-time isomorphism testing, yet we prove that for every natural number k, the k-Weisfeiler-Leman (k-WL) test cannot distinguish all non-isomorphic graphs with a simple spectrum. As the WL hierarchy upper-bounds the distinguishing power of widely-used Graph Neural Networks (GNNs), this incompleteness applies to all such GNNs, ruling out completeness for every k-WL-aligned GNN family. To close this gap, we introduce PRiSM (Partition, Refine, Solve, Match), the first provably complete canonicalization of simple-spectrum eigendecompositions. PRiSM obtains the completeness guarantee that prior canonicalizations provably lack, and resolves the open problem of achieving complete expressivity on simple-spectrum graphs. When composed with DeepSets or a Transformer, PRiSM achieves universal approximation on simple-spectrum graphs, justifying the use of canonicalized Laplacian positional encodings. Empirically, PRiSM performs comparably to or outperforms existing spectral canonicalizations on graph regression, classification, and expressivity

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 37 of its 58 references that are in the map. First posted on arXiv 22 May 2026.

Builds on

37 of 58 references.

References · 37

  1. 2017Attention Is All You Needcited by 59,932
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2021RoFormer: Enhanced Transformer with Rotary Position Embeddingcited by 4,581
  5. 2018How Powerful are Graph Neural Networks?cited by 4,355
  6. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  7. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  8. 2017Deep Setscited by 1,394
  9. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  10. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  11. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  12. 2020Benchmarking Graph Neural Networkscited by 672
25 more
  1. 2020A Generalization of Transformer Networks to Graphscited by 653
  2. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  3. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  4. 2019Provably Powerful Graph Networkscited by 385
  5. 2017Residual Gated Graph ConvNetscited by 341
  6. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  7. 2021Frame Averaging for Invariant and Equivariant Network Designcited by 166
  8. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  9. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  10. 2022Equivariance with Learned Canonicalization Functionscited by 106
  11. 2021The Logic of Graph Neural Networkscited by 84
  12. 2021Universal Approximation of Functions on Setscited by 62
  13. 2024Equivariant Frames and the Impossibility of Continuous Canonicalizationcited by 41
  14. 2019Alchemy: A Quantum Chemistry Dataset for Benchmarking AI Modelscited by 36
  15. 2021Transformers Generalize DeepSets and Can be Extended to Graphs and Hypergraphscited by 35
  16. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  17. 2023Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theoremcited by 33
  18. 2024A Canonicalization Perspective on Invariant and Equivariant Learningcited by 25
  19. 2023Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embeddingcited by 21
  20. 2024On the Expressive Power of Spectral Invariant Graph Neural Networkscited by 15
  21. 2023Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehmancited by 13
  22. 2023Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Powercited by 11
  23. 2024Aligning Transformers with Weisfeiler-Lemancited by 8
  24. 2025Homomorphism Expressivity of Spectral Invariant Graph Neural Networkscited by 4
  25. 2025Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrumcited by 3

Built on by

Not cited yet.