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

counting cyclesgraph invariantsgraph isomorphismWeisfeiler-Lehman algorithm

Mathematics Subject Classification ID

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

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

• 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)
• scientific article; zbMATH DE number 910921 (Why is no real title available?)
• 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 graph isomorphism disease
• The Parameterized Complexity of Counting Problems

Cited in

(24)

• On the expressive power of linear algebra on graphs
• On WL-rank and WL-dimension of some Deza circulant graphs
• Nonlocal games and quantum permutation groups
• Almost all trees have quantum symmetry
• Subjectively interesting connecting trees and forests
• Local WL invariance and hidden shades of regularity
• The Weisfeiler-Leman algorithm and the diameter of Schreier graphs
• scientific article; zbMATH DE number 5013903 (Why is no real title available?)
• Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm
• The power of the Weisfeiler-Leman algorithm to decompose graphs
• On the expressive power of linear algebra on graphs
• scientific article; zbMATH DE number 7561610 (Why is no real title available?)
• The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
• On Weisfeiler-Leman invariance: subgraph counts and related 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 recognition of graph properties
• Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements
• Weisfeiler-Leman indistinguishability of graphons
• Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity
• The iteration number of colour refinement
• Homomorphism-distinguishing closedness for graphs of bounded tree-width
• Rethinking graph classification problem in presence of isomorphism
• Equi-rank homomorphism preservation theorem on finite structures

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)