Volume 6 • Issue 1 • PP: 2 2– 26 • 2026
Spectral Moment Invariants and the Weisfeiler–Leman Hierarchy: Separating Power, a Fundamental Limitation, and Three Open Problems
Open Access & Copyright
© 2026 The Author(s). Published by ASPG. This article is licensed under the Creative Commons Attribution 4.0 International License (CC BY 4.0).
View PDF Abstract
We study spectral moment invariants Σp(G) = (trAG, . . . , trApG), built from the adjacency spectrum of a graph G, as graph isomorphism invariants positioned relative to the Weisfeiler–Leman (WL) hierarchy used to characterize graph neural network (GNN) expressivity. We give three fully verified case studies. First, C6 vs. 2K3: a 1- WL-indistinguishable pair separated by Σ3 but not Σ2 or Σ4. Second, K3,3 vs. the triangular prism: a second 1-WL-indistinguishable, cubic pair, also separated at order 3, but where the fourth moment separates as well, showing separating power is graph-family dependent even at fixed order. Both examples are grounded in a general fourth-moment identity (Proposition 2.8) and a homomorphism-counting identity (Proposition 2.5) that we prove from first principles. Third, and in the opposite direction, we prove that spectral moment invariants of every finite order fail on the classical cospectral, non-isomorphic strongly regular pair srg(16,6,2,2) (the Shrikhande graph and the 4×4 rook’s graph), verified numerically to fourth order by two independent methods. We situate both directions within published enumeration data and the Godsil–McKay switching construction, compare the computational complexity of spectral-moment, WL, and general isomorphism testing, connect the limitation to Laplacian eigenvector positional encodings in Graph Transformers, and pose three precise open problems.
Keywords
References
[1] B. Weisfeiler and A. Leman, “The reduction of a graph to canonical form and the algebra which appears therein,” Nauchno-Technicheskaya Informatsia, Series 2, no. 9, pp. 12–16, 1968.
[2] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” in Proceedings of the International Conference on Learning Representations, 2019.
[3] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe, “Weisfeiler and leman go neural: Higher-order graph neural networks,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, no. 1, 2019, pp. 4602–4609.
[4] S. Kiefer and D. Neuen, “The power of the Weisfeiler– Leman algorithm to decompose graphs,” SIAM Journal on Discrete Mathematics, vol. 36, no. 1, pp. 252–298, 2022.
[5] V. P. Dwivedi and X. Bresson, “A generalization of transformer networks to graphs,” 2020, arXiv preprint arXiv:2012.09699.
[6] E. R. van Dam and W. H. Haemers, “Which graphs are determined by their spectrum?” Linear Algebra and its Applications, vol. 373, pp. 241–272, 2003.
[7] W. H. Haemers and E. Spence, “Enumeration of cospectral graphs,” European Journal of Combinatorics, vol. 25, no. 2, pp. 199–211, 2004.
[8] L. Babai, X. Chen, X. Sun, S.-H. Teng, and J. Wilmes, “Faster canonical forms for strongly regular graphs,” in Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013, pp. 157–166.
[9] L. Babai, “Graph isomorphism in quasipolynomial time,” in Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016, pp. 684–697.
[10] J.-Y. Cai, M. Fürer, and N. Immerman, “An optimal lower bound on the number of variables for graph identification,” Combinatorica, vol. 12, no. 4, pp. 389–410, 1992.
[11] L. Lovász, Large Networks and Graph Limits, ser. AMS Colloquium Publications. Providence, RI: American Mathematical Society, 2012, vol. 60.
[12] L. Lovász and B. Szegedy, “Limits of dense graph sequences,” Journal of Combinatorial Theory, Series B, vol. 96, no. 6, pp. 933–957, 2006.
[13] A. E. Brouwer and W. H. Haemers, Spectra of Graphs. New York: Springer, 2012.
[14] V. Arvind, J. Köbler, G. Rattan, and O. Verbitsky, “Graph isomorphism, color refinement, and compactness,” Computational Complexity, vol. 26, no. 3, pp. 627–685, 2017.
[15] V. Arvind, F. Fuhlbrück, J. Köbler, and O. Verbitsky, “On Weisfeiler–Leman invariance: Subgraph counts and related graph properties,” 2019, arXiv preprint arXiv:1811.04801.
[16] C. D. Godsil and B. D. McKay, “Constructing cospectral graphs,” Aequationes Mathematicae, vol. 25, pp. 257– 268, 1982.
Cite This Article
Choose your preferred format
Publisher's Note
The statements, opinions, and data presented in this article are solely those of the author(s) and do not necessarily represent those of ASPG, the journal, or its editors. ASPG and the editors disclaim responsibility for any harm arising from the use of any ideas, methods, instructions, or products described in this article, to the fullest extent permitted by applicable law.