On the combinatorial power of the Weisfeiler-Lehman algorithm

DOI10.1007/978-3-319-57586-5_22MaRDI QIDQ5283372zbMATH OpenOpenAlexFDO

Authors Martin Fürer

Publication date 21 July 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.01023

zbMATH Keywords

graph isomorphismgraph invariantsWeisfeiler-Lehman algorithmcounting cycles

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Abstract: The classical Weisfeiler-Lehman method WL[2] uses edge colors to produce a powerful graph invariant. It is at least as powerful in its ability to distinguish non-isomorphic graphs as the most prominent algebraic graph invariants. It determines not only the spectrum of a graph, and the angles between standard basis vectors and the eigenspaces, but even the angles between projections of standard basis vectors into the eigenspaces. Here, we investigate the combinatorial power of WL[2]. For sufficiently large k, WL[k] determines all combinatorial properties of a graph. Many traditionally used combinatorial invariants are determined by WL[k] for small k. We focus on two fundamental invariants, the num- ber of cycles Cp of length p, and the number of cliques Kp of size p. We show that WL[2] determines the number of cycles of lengths up to 6, but not those of length 8. Also, WL[2] does not determine the number of 4-cliques.

Recommendations

• On Weisfeiler-Leman invariance: subgraph counts and related graph properties
• The Weisfeiler-Leman algorithm and recognition of graph properties
• The Weisfeiler-Leman algorithm and recognition of graph properties
• Local WL invariance and hidden shades of regularity
• Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements

Cites work

• scientific article; zbMATH DE number 910921 (Why is no real title available?)
• 6-transitive graphs
• An optimal lower bound on the number of variables for graph identification
• Finding and counting given length cycles
• Graph isomorphism in quasipolynomial time (extended abstract)
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Multiplying matrices faster than coppersmith-winograd
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• On the power of combinatorial and spectral invariants
• Random Graph Isomorphism
• Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements
• The Parameterized Complexity of Counting Problems
• The graph isomorphism disease

Cited in

(18)

• Local WL invariance and hidden shades of regularity
• Subjectively interesting connecting trees and forests
• On the expressive power of linear algebra on graphs
• The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
• Weisfeiler-Leman indistinguishability of graphons
• On WL-rank and WL-dimension of some Deza circulant graphs
• Almost all trees have quantum symmetry
• scientific article; zbMATH DE number 5013903 (Why is no real title available?)
• On the expressive power of linear algebra on graphs
• Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm
• Nonlocal games and quantum permutation groups
• The power of the Weisfeiler-Leman algorithm to decompose graphs
• scientific article; zbMATH DE number 7561610 (Why is no real title available?)
• Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements
• The Weisfeiler-Leman algorithm and recognition of graph properties
• On Weisfeiler-Leman invariance: subgraph counts and related graph properties
• The Weisfeiler-Leman algorithm and recognition of graph properties
• The Weisfeiler-Leman algorithm and the diameter of Schreier graphs

This page was built for publication: On the combinatorial power of the Weisfeiler-Lehman algorithm

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