# Weisfeiler--Leman and Graph Spectra

arXiv: https://arxiv.org/abs/2103.02972 · HTML: https://mlsanity.com/paper/2103.02972/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2021.

## Built on by (most cited first, 5 of 5)

- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings](https://mlsanity.com/paper/2201.13410/) (2022)
- [Facilitating Graph Neural Networks with Random Walk on Simplicial Complexes](https://mlsanity.com/paper/2310.19285/) (2023)
- [Subgraph Permutation Equivariant Networks](https://mlsanity.com/paper/2111.11840/) (2021)
- [Caterpillar GNN: Replacing Message Passing with Efficient Aggregation](https://mlsanity.com/paper/2506.06784/) (2025)

## Abstract (arXiv)

Two simple undirected graphs are cospectral if their respective adjacency matrices have the same multiset of eigenvalues. Cospectrality yields an equivalence relation on the family of graphs which is provably weaker than isomorphism. In this paper, we study cospectrality in relation to another well-studied relaxation of isomorphism, namely k-dimensional Weisfeiler-Leman (k-WL) indistinguishability. Cospectrality with respect to standard graph matrices such as the adjacency or the Laplacian matrix yields a strictly finer equivalence relation than 2-WL indistinguishability. We show that individualising one vertex plus running 1-WL already subsumes cospectrality with respect to all such graph matrices. Building on this result, we resolve an open problem of F"urer (2010) about spectral invariants. Looking beyond 2-WL, we devise a hierarchy of graph matrices generalising the adjacency matrix such that k-WL indistinguishability after a fixed number of iterations can be captured as a spectral condition on these matrices. Precisely, we provide a spectral characterisation of k-WL indistinguishability after d iterations, for k,d ∈ mathbbN. Our results can be viewed as characterisations of homomorphism indistinguishability over certain graph classes in terms of matrix equations. The study of homomorphism indistinguishability is an emerging field, to which we contribute by extending the algebraic framework of Manvcinska and Roberson (2020) and Grohe et al. (2022).