pith. sign in

arxiv: 2605.23446 · v1 · pith:6OXXOJZZnew · submitted 2026-05-22 · 💻 cs.LG · math.CO

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

Snir Hordan , Nadav Dym , Tim Seppelt This is my paper

Pith reviewed 2026-05-25 04:43 UTC · model grok-4.3

classification 💻 cs.LG math.CO
keywords graph isomorphismWeisfeiler-Lemansimple spectrumgraph neural networkscanonicalizationspectral methodsexpressivity
0
0 comments X

The pith

The k-Weisfeiler-Leman test cannot distinguish all non-isomorphic graphs with simple spectra for any k.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that even though graphs with distinct eigenvalues permit cubic-time isomorphism testing, the entire Weisfeiler-Leman hierarchy remains incomplete on this class: for every natural number k there exist non-isomorphic simple-spectrum graphs that k-WL cannot separate. Because k-WL upper-bounds the power of standard graph neural networks, the same incompleteness holds for every k-WL-aligned GNN family. The authors respond by introducing PRiSM, a procedure that canonically processes simple-spectrum eigendecompositions and supplies the completeness guarantee missing from earlier spectral methods. When PRiSM is paired with DeepSets or a Transformer, the resulting models become universal approximators on the simple-spectrum class.

Core claim

For every k the k-WL test fails to separate all non-isomorphic simple-spectrum graphs, even though the class admits polynomial-time isomorphism; PRiSM supplies the first provably complete canonicalization of their eigendecompositions by partitioning, refining, solving and matching, thereby resolving the open question of complete expressivity on this class.

What carries the argument

PRiSM (Partition, Refine, Solve, Match), the procedure that produces a canonical form from a simple-spectrum eigendecomposition and thereby guarantees completeness where prior canonicalizations do not.

If this is right

  • Every family of k-WL-aligned graph neural networks is incomplete on simple-spectrum graphs.
  • PRiSM is the first method that provably achieves complete expressivity on the simple-spectrum class.
  • Composing PRiSM with DeepSets or a Transformer yields universal approximation on simple-spectrum graphs.
  • PRiSM performs at least as well as existing spectral canonicalizations on regression, classification, and expressivity benchmarks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Simple-spectrum graphs form a natural test class for measuring the gap between polynomial isomorphism and higher-order WL power.
  • The cubic isomorphism algorithm could be combined with PRiSM to produce hybrid exact-matching pipelines.
  • PRiSM-style refinement steps might be adapted to graphs whose spectra are nearly simple.

Load-bearing premise

The graphs under consideration have a simple spectrum, that is, all eigenvalues are distinct.

What would settle it

An explicit construction, for some fixed k, of a family of simple-spectrum graphs on which k-WL distinguishes every pair of non-isomorphic members would falsify the incompleteness claim.

Figures

Figures reproduced from arXiv: 2605.23446 by Nadav Dym, Snir Hordan, Tim Seppelt.

Figure 1
Figure 1. Figure 1: The CFI construction applied to the base graph G = C3. (a) Trivial lift G∅ ∼= 2 C3: the (i, ∅) vertices and (i, E(i)) vertices each form an independent triangle. (b) Non-trivial lift G{0} ∼= C6: the parity twist at vertex 0 bridges the two triangles into a single 6-cycle (dashed circles mark the twisted fiber). Colors indicate base-graph vertex correspondence and are for visualization purposes only. 4 Inco… view at source ↗
Figure 2
Figure 2. Figure 2: Integral encoding matrices for the CFI construction on [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗
read the original abstract

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

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proves that for every natural number k the k-WL test fails to distinguish all non-isomorphic graphs whose adjacency (or Laplacian) matrices have simple spectra, shows that this incompleteness carries over to k-WL-aligned GNNs, and introduces the PRiSM canonicalization procedure that is claimed to be the first provably complete method for simple-spectrum eigendecompositions, yielding universal approximation when composed with DeepSets or Transformers.

Significance. If the incompleteness result and the completeness proof for PRiSM both hold, the work identifies a natural polynomial-time isomorphism class on which the entire WL hierarchy (and therefore standard GNNs) is provably incomplete, while supplying an explicit, canonicalization-based route to full expressivity; the empirical section further indicates that the method is competitive on regression and classification tasks.

major comments (2)
  1. [§3, Theorem 3.4] §3 (Incompleteness of k-WL on simple-spectrum graphs), Theorem 3.4 and Construction 3.3: the argument that the constructed family remains simple-spectrum for every k must be checked for an explicit verification that the perturbation (or weighting) used to enforce distinct eigenvalues does not alter the k-WL colorings or the non-isomorphism; a generic-density claim is insufficient for a discrete, finite-k statement.
  2. [§4.2, Theorem 4.7] §4.2 (PRiSM algorithm), Algorithm 1 and Theorem 4.7: the proof that the Partition-Refine-Solve-Match procedure produces a unique canonical form relies on the assumption that the input spectrum is simple; it is unclear whether the algorithm includes an explicit check or recovery step when floating-point eigendecomposition produces near-collisions, which would be required for the completeness guarantee to be robust.
minor comments (2)
  1. [Experiments] The abstract states that PRiSM 'performs comparably to or outperforms existing spectral canonicalizations' but the experimental section should report exact numbers, baselines, and statistical significance for each task.
  2. [§2] Notation for the Laplacian versus adjacency matrix is used interchangeably in several places; a single consistent definition should be fixed in §2.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We respond to each major comment below, indicating where revisions will be made.

read point-by-point responses

  1. Referee: [§3, Theorem 3.4] §3 (Incompleteness of k-WL on simple-spectrum graphs), Theorem 3.4 and Construction 3.3: the argument that the constructed family remains simple-spectrum for every k must be checked for an explicit verification that the perturbation (or weighting) used to enforce distinct eigenvalues does not alter the k-WL colorings or the non-isomorphism; a generic-density claim is insufficient for a discrete, finite-k statement.

    Authors: We agree that a generic-density argument, while sufficient to show existence in the continuous case, does not provide the explicit verification needed for a fixed finite k. In the revised version we will replace the density claim with an explicit perturbation construction: for each base graph in the family we add a diagonal weighting matrix whose entries are multiples of a sufficiently small ε (chosen smaller than the minimal eigenvalue gap detectable after k iterations of color refinement, which is bounded by the graph size and the number of distinct colors). We will include a short lemma verifying that this perturbation preserves the k-WL color partition while making all eigenvalues distinct. The non-isomorphism of the resulting graphs is unchanged because the perturbation is applied symmetrically to both members of each pair. revision: yes

  2. Referee: [§4.2, Theorem 4.7] §4.2 (PRiSM algorithm), Algorithm 1 and Theorem 4.7: the proof that the Partition-Refine-Solve-Match procedure produces a unique canonical form relies on the assumption that the input spectrum is simple; it is unclear whether the algorithm includes an explicit check or recovery step when floating-point eigendecomposition produces near-collisions, which would be required for the completeness guarantee to be robust.

    Authors: Theorem 4.7 and the completeness proof are stated under the exact-arithmetic assumption that the input spectrum is simple. The algorithm description therefore contains no numerical safeguard. We acknowledge that floating-point eigendecomposition can produce near-collisions in practice. In the revision we will add a short practical note after Algorithm 1: if any two computed eigenvalues differ by less than a user-specified tolerance (e.g., 10^{-10}), the procedure issues a warning and may optionally apply a tiny random perturbation before proceeding; the theoretical guarantee remains conditional on an exactly simple spectrum. This does not alter the main completeness result but clarifies the numerical setting. revision: partial

Circularity Check

0 steps flagged

No circularity detected; derivation is self-contained

full rationale

The paper's central claims rest on a mathematical proof that k-WL fails to distinguish certain non-isomorphic simple-spectrum graphs for every k, followed by an explicit construction of the PRiSM canonicalization procedure. No equations, parameters, or results are shown to reduce to fitted inputs or prior self-citations by construction. The incompleteness result is established via explicit counterexample families whose simple-spectrum property is part of the stated premise rather than derived from the WL equivalence itself. PRiSM is introduced as a new algorithmic procedure whose completeness guarantee is argued directly from its partition-refine-solve-match steps, without relying on load-bearing self-citations or renaming of known empirical patterns. The derivation chain therefore remains independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper rests on the domain assumption that the input graphs have distinct eigenvalues and introduces the new algorithmic procedure PRiSM whose correctness is asserted without external verification artifacts.

axioms (1)
  • domain assumption Input graphs have a simple spectrum (all eigenvalues distinct)
    Defines the graph class for which both the WL incompleteness and the PRiSM completeness are claimed.
invented entities (1)
  • PRiSM canonicalization procedure no independent evidence
    purpose: Produce a unique canonical form from the eigendecomposition that is provably complete for isomorphism on simple-spectrum graphs
    New algorithmic entity introduced to achieve the completeness guarantee; no independent evidence outside the paper is referenced in the abstract.

pith-pipeline@v0.9.0 · 5726 in / 1280 out tokens · 27902 ms · 2026-05-25T04:43:23.313862+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

75 extracted references · 75 canonical work pages · 3 internal anchors

  1. [1]

    Convolutional networks on graphs for learning molecular fingerprints.Advances in neural information processing systems, 28, 2015

    David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints.Advances in neural information processing systems, 28, 2015

    work page 2015

  2. [2]

    Neural message passing for quantum chemistry

    Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. InInternational conference on machine learning, pages 1263–1272. Pmlr, 2017

    work page 2017

  3. [3]

    Graph neural networks.Nature Reviews Methods Primers, 4(1):17, 2024

    Gabriele Corso, Hannes Stark, Stefanie Jegelka, Tommi Jaakkola, and Regina Barzilay. Graph neural networks.Nature Reviews Methods Primers, 4(1):17, 2024

    work page 2024

  4. [4]

    The graph neural network model.IEEE transactions on neural networks, 20(1):61–80, 2008

    Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model.IEEE transactions on neural networks, 20(1):61–80, 2008

    work page 2008

  5. [5]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. InInternational Conference on Learning Representations, 2017. URL https: //openreview.net/forum?id=SJU4ayYgl

    work page 2017

  6. [6]

    Graph attention networks

    Petar Veliˇckovi´c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. InInternational Conference on Learning Representations, 2018

    work page 2018

  7. [7]

    How Powerful are Graph Neural Networks?

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?arXiv preprint arXiv:1810.00826, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  8. [8]

    Provably powerful graph networks.Advances in neural information processing systems, 32, 2019

    Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks.Advances in neural information processing systems, 32, 2019

    work page 2019

  9. [9]

    Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe

    Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks.Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):4602–4609, Jul. 2019. doi:10.1609/aaai.v33i01.33014602. URL https://ojs.aaai.org/index.php/ AAAI/a...

    work page doi:10.1609/aaai.v33i01.33014602 2019

  10. [10]

    Boris Weisfeiler and A. A. Lehman. A reduction of a graph to a canonical form and an algebra arising during this reduction.Nauchno-Technicheskaya Informatsia, 9, 1968

    work page 1968

  11. [11]

    Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings.Advances in Neural Information Processing Systems, 33:21824–21840, 2020

    Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings.Advances in Neural Information Processing Systems, 33:21824–21840, 2020

    work page 2020

  12. [12]

    Weisfeiler and leman go machine learning: The story so far.Journal of Machine Learning Research, 24(333):1–59, 2023

    Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far.Journal of Machine Learning Research, 24(333):1–59, 2023

    work page 2023

  13. [13]

    Aligning transformers with weisfeiler-leman

    Luis Müller and Christopher Morris. Aligning transformers with weisfeiler-leman. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors,Proceedings of the 41st International Conference on Machine Learn- ing, volume 235 ofProceedings of Machine Learning Research, pages 36654–367...

    work page 2024

  14. [14]

    Thomson Leighton and Gary l

    F. Thomson Leighton and Gary l. Miller. Certificates for graphs with distinct eigen values. Orginal Manuscript, 1979

    work page 1979

  15. [15]

    Parameterized complexity of graph isomorphism testing.Computer Science Review, 60:100918, May 2026

    Daniel Neuen. Parameterized complexity of graph isomorphism testing.Computer Science Review, 60:100918, May 2026. ISSN 15740137. doi:10.1016/j.cosrev.2026.100918. URL https://linkinghub.elsevier.com/retrieve/pii/S1574013726000274

    work page doi:10.1016/j.cosrev.2026.100918 2026

  16. [16]

    Spectral graph neural networks are incomplete on graphs with a simple spectrum

    Snir Hordan, Maya Bechler-Speicher, Gur Lifshitz, and Nadav Dym. Spectral graph neural networks are incomplete on graphs with a simple spectrum. InThe Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025

    work page 2025

  17. [17]

    An optimal lower bound on the number of variables for graph identification.Combinatorica, 12(4):389–410, 1992

    Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification.Combinatorica, 12(4):389–410, 1992. ISSN 1439-6912. doi:10.1007/BF01305232. URLhttps://doi.org/10.1007/BF01305232

    work page doi:10.1007/bf01305232 1992

  18. [18]

    Lecture Notes in Logic

    Martin Grohe.Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Lecture Notes in Logic. Cambridge University Press, 2017

    work page 2017

  19. [19]

    Benchmarking graph neural networks.Journal of Machine Learning Research, 24(43):1–48, 2023

    Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks.Journal of Machine Learning Research, 24(43):1–48, 2023

    work page 2023

  20. [20]

    Sign and basis invariant networks for spectral graph representation learning

    Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. InThe Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=Q-UHqMorzil

    work page 2023

  21. [21]

    Laplacian canonization: A minimalist approach to sign and basis invariant spectral embedding

    George Ma, Yifei Wang, and Yisen Wang. Laplacian canonization: A minimalist approach to sign and basis invariant spectral embedding. InThirty-seventh Conference on Neural Information Processing Systems, 2023. URLhttps://openreview.net/forum?id=1mAYtdoYw6

    work page 2023

  22. [22]

    A canonicalization perspective on invariant and equivariant learning

    George Ma, Yifei Wang, Derek Lim, Stefanie Jegelka, and Yisen Wang. A canonicalization perspective on invariant and equivariant learning. InThe Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id= jjcY92FX4R

    work page 2024

  23. [23]

    Deep sets

    Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. In I. Guyon, U. V on Luxburg, S. Bengio, H. Wallach, R. Fer- gus, S. Vishwanathan, and R. Garnett, editors,Advances in Neural Information Processing Sys- tems, volume 30. Curran Associates, Inc., 2017. URL https://proceedings.neurips....

    work page 2017

  24. [24]

    Attention is all you need.Advances in neural information processing systems, 30, 2017

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need.Advances in neural information processing systems, 30, 2017

    work page 2017

  25. [25]

    Transformers generalize deepsets and can be extended to graphs & hypergraphs.Advances in Neural Information Processing Systems, 34: 28016–28028, 2021

    Jinwoo Kim, Saeyoon Oh, and Seunghoon Hong. Transformers generalize deepsets and can be extended to graphs & hypergraphs.Advances in Neural Information Processing Systems, 34: 28016–28028, 2021

    work page 2021

  26. [26]

    An empirical study of realized GNN expressiveness

    Yanbo Wang and Muhan Zhang. An empirical study of realized GNN expressiveness. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors,Proceedings of the 41st International Conference on Machine Learning, volume 235 ofProceedings of Machine Learning Research, pages 52134–52155. ...

    work page 2024

  27. [27]

    Open graph benchmark: Datasets for machine learning on graphs

    Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118–22133, 2020

    work page 2020

  28. [28]

    Zinc: a free tool to discover chemistry for biology.Journal of chemical information and modeling, 52 (7):1757–1768, 2012

    John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zinc: a free tool to discover chemistry for biology.Journal of chemical information and modeling, 52 (7):1757–1768, 2012. 11

    work page 2012

  29. [29]

    Alchemy: A Quantum Chemistry Dataset for Benchmarking AI Models

    Guangyong Chen, Pengfei Chen, Chang-Yu Hsieh, Chee-Kong Lee, Benben Liao, Renjie Liao, Weiwen Liu, Jiezhong Qiu, Qiming Sun, Jie Tang, et al. Alchemy: A quantum chemistry dataset for benchmarking ai models.arXiv preprint arXiv:1906.09427, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1906

  30. [30]

    Distance-restricted folklore weisfeiler-leman gnns with provable cycle counting power.Advances in Neural Information Processing Systems, 36:14293–14337, 2023

    Junru Zhou, Jiarui Feng, Xiyuan Wang, and Muhan Zhang. Distance-restricted folklore weisfeiler-leman gnns with provable cycle counting power.Advances in Neural Information Processing Systems, 36:14293–14337, 2023

    work page 2023

  31. [31]

    Extending the design space of graph neural networks by rethinking folklore weisfeiler-lehman

    Jiarui Feng, Lecheng Kong, Hao Liu, Dacheng Tao, Fuhai Li, Muhan Zhang, and Yixin Chen. Extending the design space of graph neural networks by rethinking folklore weisfeiler-lehman. Advances in Neural Information Processing Systems, 36:9029–9064, 2023

    work page 2023

  32. [32]

    Understanding and extending subgraph gnns by rethinking their symmetries.Advances in Neural Information Processing Systems, 35:31376–31390, 2022

    Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries.Advances in Neural Information Processing Systems, 35:31376–31390, 2022

    work page 2022

  33. [33]

    Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width

    Daniel Neuen. Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width. In Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov, editors,41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), volume 289 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 53:1– 53:12, ...

    work page doi:10.4230/lipics.stacs.2024.53 2024

  34. [34]

    László Babai, D. Yu. Grigoryev, and David M. Mount. Isomorphism of graphs with bounded eigenvalue multiplicity. InProceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC ’82, page 310–324, New York, NY , USA, 1982. Association for Computing Machinery. ISBN 0897910702. doi:10.1145/800070.802206. URL https://doi.org/10. 1145/800070.802206

    work page doi:10.1145/800070.802206 1982

  35. [35]

    Rethinking graph transformers with spectral attention.Advances in neural information process- ing systems, 34:21618–21629, 2021

    Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention.Advances in neural information process- ing systems, 34:21618–21629, 2021

    work page 2021

  36. [36]

    A generalization of transformer networks to graphs

    Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021

    work page 2021

  37. [37]

    Homomorphism expressivity of spectral invariant graph neural networks

    Jingchu Gai, Yiheng Du, Bohang Zhang, Haggai Maron, and Liwei Wang. Homomorphism expressivity of spectral invariant graph neural networks. InThe Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum? id=rdv6yeMFpn

    work page 2025

  38. [38]

    On the expressive power of spectral invariant graph neural networks

    Bohang Zhang, Lingxiao Zhao, and Haggai Maron. On the expressive power of spectral invariant graph neural networks. InForty-first International Conference on Machine Learning

    work page

  39. [39]

    Random matrices have simple spectrum.Combinatorica, 37(3): 539–553, 2017

    Terence Tao and Van Vu. Random matrices have simple spectrum.Combinatorica, 37(3): 539–553, 2017. doi:10.1007/s00493-016-3363-4

    work page doi:10.1007/s00493-016-3363-4 2017

  40. [40]

    Pebble games and linear equations.The Journal of Symbolic Logic, 80(3):797–844, 2015

    Martin Grohe and Martin Otto. Pebble games and linear equations.The Journal of Symbolic Logic, 80(3):797–844, 2015

    work page 2015

  41. [41]

    Roberson

    David E. Roberson. Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree, June 2022. URLhttp://arxiv.org/abs/2206.10321

    work page arXiv 2022

  42. [42]

    In: 2021 36th Annual ACM/IEEE Sym- posium on Logic in Computer Science (LICS)

    Martin Grohe. The Logic of Graph Neural Networks. In36th Annual ACM/IEEE Sym- posium on Logic in Computer Science, LICS, pages 1–17, Rome, Italy, 2021. IEEE. doi:10.1109/LICS52264.2021.9470677. URL https://doi.org/10.1109/LICS52264. 2021.9470677

    work page doi:10.1109/lics52264.2021.9470677 2021

  43. [43]

    Strongly Sublinear Separators and Polynomial Expansion

    Zdenˇek Dvoˇrák and Sergey Norin. Strongly Sublinear Separators and Polynomial Expansion. SIAM Journal on Discrete Mathematics, 30(2):1095–1101, January 2016. ISSN 0895-4801, 1095-7146. doi:10.1137/15M1017569. 12

    work page doi:10.1137/15m1017569 2016

  44. [44]

    Lower Bounds for the Isoperimetric Numbers of Random Regular Graphs.SIAM Journal on Discrete Mathematics, 28(1):553–575, January 2014

    Brett Kolesnik and Nick Wormald. Lower Bounds for the Isoperimetric Numbers of Random Regular Graphs.SIAM Journal on Discrete Mathematics, 28(1):553–575, January 2014. ISSN 0895-4801, 1095-7146. doi:10.1137/120891265

    work page doi:10.1137/120891265 2014

  45. [45]

    Spielman

    Daniel A. Spielman. Spectral and algebraic graph theory. 2025. URL http://cs-www.cs. yale.edu/homes/spielman/sagt/sagt.pdf

    work page 2025

  46. [46]

    Smith, Ishan Misra, Aditya Grover, Heli Ben-Hamu, and Yaron Lipman

    Omri Puny, Matan Atzmon, Edward J. Smith, Ishan Misra, Aditya Grover, Heli Ben-Hamu, and Yaron Lipman. Frame averaging for invariant and equivariant network design. InInternational Conference on Learning Representations, 2022. URL https://openreview.net/forum? id=zIUyj55nXR

    work page 2022

  47. [47]

    Equivariance with learned canonicalization functions

    Sékou-Oumar Kaba, Arnab Kumar Mondal, Yan Zhang, Yoshua Bengio, and Siamak Ravan- bakhsh. Equivariance with learned canonicalization functions. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 ofPro- ceedings ...

    work page 2023

  48. [48]

    Neural injective functions for multisets, measures and graphs via a finite witness theorem.Advances in Neural Information Processing Systems, 36:42516–42551, 2023

    Tal Amir, Steven Gortler, Ilai Avni, Ravina Ravina, and Nadav Dym. Neural injective functions for multisets, measures and graphs via a finite witness theorem.Advances in Neural Information Processing Systems, 36:42516–42551, 2023

    work page 2023

  49. [49]

    Universal approximation of functions on sets.Journal of Machine Learning Research, 23(151): 1–56, 2022

    Edward Wagstaff, Fabian B Fuchs, Martin Engelcke, Michael A Osborne, and Ingmar Posner. Universal approximation of functions on sets.Journal of Machine Learning Research, 23(151): 1–56, 2022

    work page 2022

  50. [50]

    Residual Gated Graph ConvNets

    Xavier Bresson and Thomas Laurent. Residual gated graph convnets.arXiv preprint arXiv:1711.07553, 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  51. [51]

    Principal neighbourhood aggregation for graph nets.Advances in neural information processing systems, 33:13260–13271, 2020

    Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veliˇckovi´c. Principal neighbourhood aggregation for graph nets.Advances in neural information processing systems, 33:13260–13271, 2020

    work page 2020

  52. [52]

    Equivariant frames and the impos- sibility of continuous canonicalization

    Nadav Dym, Hannah Lawrence, and Jonathan W Siegel. Equivariant frames and the impos- sibility of continuous canonicalization. InForty-first International Conference on Machine Learning

    work page

  53. [53]

    Dissertation, RWTH Aachen University, Aachen, 2024

    Tim Seppelt.Homomorphism Indistinguishability. Dissertation, RWTH Aachen University, Aachen, 2024. URLhttps://publications.rwth-aachen.de/record/998785

    work page 2024

  54. [54]

    Hermann V on Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung).Mathema- tische Annalen, 71:441–479, 1912. URL https://api.semanticscholar.org/CorpusID: 120278241

    work page 1912

  55. [55]

    Recipe for a general, powerful, scalable graph transformer.Advances in Neural Information Processing Systems, 35:14501–14515, 2022

    Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer.Advances in Neural Information Processing Systems, 35:14501–14515, 2022

    work page 2022

  56. [56]

    Roformer: Enhanced transformer with rotary position embedding.Neurocomputing, 568:127063, 2024

    Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding.Neurocomputing, 568:127063, 2024. A Incompleteness of Weisfeiler–Leman on Simple Spectrum Graphs A.1 Weisfeiler–Leman Definitions For completeness we record here the general k-dimensional Weisfeiler–Leman test and its as...

    work page 2024

  57. [57]

    This matrix will serve as the matrix of eigenvectors for the multigraphs, which we construct subsequently

    For some suitable base graph G and U∈ {0,1} , we define a matrix ˜XG,U based on the CFI graph GU . This matrix will serve as the matrix of eigenvectors for the multigraphs, which we construct subsequently

    work page

  58. [58]

    In order for ˜XG,U to encode an eigenbasis of a simple-spectrum graph, we show in Lemma 5 that the columns of ˜XG,U are orthogonal. 14

    work page

  59. [59]

    Our construction will be such that AG,U can be ensured to have only non-negative integral entries

    Now we choose a diagonal matrix with distinct diagonal entries D and consider the matrices AG,U := ˜XG,U D( ˜XG,U)⊤. Our construction will be such that AG,U can be ensured to have only non-negative integral entries. Hence,A G,U is a multigraph with simple spectrum

    work page

  60. [60]

    To argue that AG,0 and AG,1 are non-isomorphic, we show that AG,0 ∼= AG,1 would imply that the CFI graphsG 0 andG 1 are isomorphic, which is known not to hold [41]

    work page

  61. [61]

    To that end, we show that running Weisfeiler–Leman onAG,0 and AG,1 can be simulated by running Weisfeiler–Leman on G0 and G1

    Lastly, we show that the Weisfeiler–Leman algorithm fails to distinguish AG,0 and AG,1. To that end, we show that running Weisfeiler–Leman onAG,0 and AG,1 can be simulated by running Weisfeiler–Leman on G0 and G1. By the choice of G as a high-treewidth graph, it follows that G0 and G1 are not distinguished by Weisfeiler–Leman [33] and hence the same holds...

    work page

  62. [62]

    The entries are given by XG,U((v, S), e) :=    1,ife∈E(v)ande∈S, −1,ife∈E(v)ande /∈S, 0,ife /∈E(v)

    The columns ofX G,U are indexed byE(G). The entries are given by XG,U((v, S), e) :=    1,ife∈E(v)ande∈S, −1,ife∈E(v)ande /∈S, 0,ife /∈E(v). (2)

    work page

  63. [63]

    The entries are given by X ′ G,U((v, S), e) :=    XG,U((v, S), e),ifvis the first vertex ine, −XG,U((v, S), e),ifvis the second vertex ine, 0,otherwise

    The columns ofX ′ G,U are indexed byE(G). The entries are given by X ′ G,U((v, S), e) :=    XG,U((v, S), e),ifvis the first vertex ine, −XG,U((v, S), e),ifvis the second vertex ine, 0,otherwise. (3)

    work page

  64. [64]

    The columns of IG,U are indexed by V(G) . Let W be the following V(G)×V(G) matrix; its first column is the all-ones vector and its remaining columns are pairwise orthogonal and orthogonal to the first column, hence form a basis for the orthogonal complement of the all-ones direction inR |V(G)| . W :=   1 1 1 1· · ·1 1 1−1 1 1· · ·1 1 1 0−2 1· · ...

    work page

  65. [65]

    The rows of ˜XG,U are indexed byV(G U)

    Define ˜XG,U as the concatenation ofXG,U , X ′ G,U , and IG,U . The rows of ˜XG,U are indexed byV(G U). The columns of ˜XG,U are indexed byE(G)⊎E(G)⊎V(G). We observe that ˜XG,U is a square matrix whenGis a3-regular graph. Lemma 1.IfGis a3-regular2n-vertex graph, then ˜XG,U is an8n×8nmatrix. Proof. The number of edges in a 3-regular 2n-vertex graph is 3n. ...

    work page

  66. [66]

    The crucial observation is that the columns of IG,U are constant on sets of vertices (v, S) belonging to the same vertex v∈V(G)

    One columne∈E(G)fromX G,U orX ′ G,U and one columnu∈V(G)fromI G,U . The crucial observation is that the columns of IG,U are constant on sets of vertices (v, S) belonging to the same vertex v∈V(G) . We argue that the columns of XG,U and X ′ G,U are orthogonal to the subspace of vectors in RV(G U ) that are constant on these fibers. Let u∈V(G) and consider ...

    work page

  67. [67]

    The case when e and e′ intersect only in one vertex is similar to what has been argued in Lemma 3

    One columne∈E(G)fromX G,U and one columne ′ ∈E(G)fromX ′ G,U . The case when e and e′ intersect only in one vertex is similar to what has been argued in Lemma 3. If e=e ′ =uv where wlog u precedes v in the ordering on G, then the inner product is X S⊆E(u) |S|≡|U∩{u}|(mod 2) (−1)e∈S(−1)e′∈S − X T⊆E(v) |T|≡|U∩{v}|(mod 2) (−1)e∈T (−1)e′∈T = X S⊆E(u) |S|≡|U∩{...

    work page

  68. [68]

    contains e

    By [33, Lemma 12] and [42, Corollary 4.7], the vertex-colored CFI graphs G∗ n,0 and G∗ n,1 of Gn are not distinguished by the n 12 −1 -dimensional Weisfeiler–Leman algorithm. By Lemma 8, so are multigraphs AGn,0 and AGn,1. By Lemma 6, the multigraphs AGn,0 and AGn,1 are non-isomorphic. They have simple spectrum by construction in Section A.2.3. A.3 CFI Co...

    work page

  69. [69]

    We note that when U has no non-trivial automorphisms, the second condition coincides with the standard notion of equivariance ofs, namelys(t.U) =t⊕s(U)for allUandt∈Z k 2

    Sign equivariance: s(t.U)⊕(t⊕s(U)) is a sign automorphism of U, for all U and t∈Z k 2. We note that when U has no non-trivial automorphisms, the second condition coincides with the standard notion of equivariance ofs, namelys(t.U) =t⊕s(U)for allUandt∈Z k 2. Lemma 9.If s is a sign canonicalization, then a canonicalization c(U) can be defined by ordering s(...

    work page

  70. [70]

    By definition, there exists a τ∈S n such that g= (τ, a)∈Aut(U)

    Proof of A⊆ ˆW :Let a∈A . By definition, there exists a τ∈S n such that g= (τ, a)∈Aut(U) . By construction of the partition {Cℓ}L ℓ=1 from absolute-value signatures (Algorithms 3 and 4), any g∈Aut(U) has its associated permutation τ mapping each partition class to itself. (Permutations preserve absolute-value signatures, so τ(v)∈C ℓ whenever v∈C ℓ.) This ...

    work page

  71. [71]

    By definition, a∈ ˆWℓ for every ℓ∈[L]

    Proof of ˆW⊆A :Let a∈ ˆW=∩ L ℓ=1 ˆWℓ. By definition, a∈ ˆWℓ for every ℓ∈[L] . The fact that a∈ ˆWℓ means that a stabilizes the set of rows {Ui}i∈Cℓ. This implies that for each ℓ, the set {a·U i}i∈Cℓ is a permutation of {Ui}i∈Cℓ. Therefore, for each class ℓ, there exists a permutation τℓ :C ℓ →C ℓ such that a·U i =U τℓ(i) for all i∈C ℓ. Since the classes {...

    work page

  72. [72]

    Solving E·s=f over Z2 via Gaussian elimination on a matrix with at most k rows and k columns:O(k 3)

    work page

  73. [73]

    1 block

    Lex-minimizing over the coset s0 ⊕ker(E) : finding the lex-min element of an affine subspace of Zk 2 by a greedy pass over the basis of ker(E) costs O(k2), dominated by the O(k3)solve. Combining, the stage total isO(nk 2 +k 3). Total.Summing over all stages, the overall complexity is O(nklogn+k 3 +nk 2), matching the bound stated in the main text. Complex...

    work page

  74. [74]

    Sequential refinement

    InvariantFor any graph g∈ K(N, M, δ) with n≤N nodes, any n×n permutation matrix Pand diagonal matrixSwith diagonal entries in{−1,1}, we have that ˜f(P V S, ⃗λ) =f(P V Sdiag( ⃗λ)SV T P T ) (∗) =f(Udiag( ⃗λ)U T ) = ˜f(U, ⃗λ), where (∗) is because f is isomorphism-invariant, diagonal matrices commute, and S2 =I n. 30 3.ConsistentBy which we mean that ˜f(U g,...

    work page

  75. [75]

    Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects

    Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or ...

    work page