Weisfeiler--Leman and Graph Spectra

DOI10.1137/1.9781611977554.CH87MaRDI QIDQ6362126zbMATH OpenOpenAlexFDO

Authors Gaurav Rattan, Tim Seppelt

Publication date 4 March 2021

Full work available at URL https://doi.org/10.1137/1.9781611977554.ch87

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: 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,dinmathbbN$. 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 Manv{c}inska and Roberson (2020) and Grohe et al. (2022).

Cited in

(9)

• Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability
• Logical equivalences, homomorphism indistinguishability, and forbidden minors
• Going deep and going wide: counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
• On homomorphism indistinguishability and hypertree depth
• On a hierarchy of spectral isomorphism invariants
• On a hierarchy of spectral invariants for graphs
• Power spectrum signatures of graphs
• Going deep and going wide: counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
• NPA hierarchy for quantum isomorphism and homomorphism indistinguishability

This page was built for publication: Weisfeiler--Leman and Graph Spectra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6362126)