On the combinatorial power of the Weisfeiler-Lehman algorithm

DOI10.1007/978-3-319-57586-5_22zbMATH Open1489.05146arXiv1704.01023OpenAlexW2605912794MaRDI QIDQ5283372FDOQ5283372

Authors: Martin Fürer 

Publication date: 21 July 2017

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

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.

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

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

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)

Cites Work

• Multiplying matrices faster than coppersmith-winograd
• Finding and counting given length cycles
• Random Graph Isomorphism
• The graph isomorphism disease
• An optimal lower bound on the number of variables for graph identification
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• 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
• The Parameterized Complexity of Counting Problems
• Graph isomorphism in quasipolynomial time [extended abstract]
• Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements
• Title not available (Why is that?)
• 6-transitive graphs
• On the power of combinatorial and spectral invariants

Cited In (15)

• Subjectively interesting connecting trees and forests
• On the expressive power of linear algebra on graphs
• Nonlocal games and quantum permutation groups
• The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs
• The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
• Title not available (Why is that?)
• Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm
• On Weisfeiler-Leman invariance: subgraph counts and related graph properties
• Local WL invariance and hidden shades of regularity
• The Weisfeiler-Leman algorithm and recognition of graph properties
• Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements
• Title not available (Why is that?)
• Almost all trees have quantum symmetry
• The Weisfeiler-Leman algorithm and recognition of graph properties
• Title not available (Why is that?)

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)