Bi-Weekly Talk: Tim Seppelt: How Indistinguishable are Cospectral Graphs? Weisfeiler–Leman, Graph Spectra, and Graph Powers

Wednesday, December 16, 2020, 10:30am

Location: Online session

Speaker: Tim Seppelt

 

Abstract: 

Arvind et al. (2020) asked which graph invariants are detected by the k-dimensional Weisfeiler–Leman algorithm. Fürer and Alzaga et al. (2010) have shown that 2-WL-equivalent graphs are cospectral with respect to their adjacency matrices.
Strengthening this result, it is shown that 2-WL-equivalent graphs are cospectral with respect to a wide range of matrices that are studied in spectral and algebraic graph theory, and data science.

As a corollary, this implies that the edge partition obtained by classifying pairs of nodes according to their commute distance in a random walk is not finer than the edge partition obtained by 2-WL.

Furthermore, it is shown that these spectral graph invariants are strictly weaker than 2-WL. In fact, a logarithmic number of iterations of 2-WL suffices to distinguish non-cospectral graphs.

This reasoning also applies to k > 2, answering a question by Alzaga et al. (2010).
A logarithmic number of iterations of 2k-WL suffices to distinguish graphs that are not cospectral with respect to their k-th symmetric power adjacency matrices.

This talk gives an overview over these results and some of the techniques involved in their proofs.