Weisfeiler-Leman equivalence transfers depend on graph operations
Transfer of Weisfeiler-Leman equivalence under graph operations
Discrete Mathematics
Summary
Graphs can be tested for sameness using a method called Weisfeiler-Leman (WL) algorithms, which become stronger with higher levels. This paper studies how applying specific graph changes affects the ability of these tests to recognize equivalent graphs. The authors find exact relationships between the test levels needed before and after certain operations, like creating line graphs or generalizing edges to cliques. Their work combines detailed analysis and clever examples to show these connections precisely. This helps understand how graph properties behave when transformed.
What this means in practice
- •For graph algorithm developers: Set precise requirements on equivalence checks when transforming graphs with line or clique-based operations to optimize isomorphism testing methods.
- •For network science analysts: Understand how structural similarity measures behave under clique or edge aggregation operations for comparing complex networks.
A theory result. No direct application yet.
Authors
Dmitriy Kunisky, Hamilton Sawczuk
Abstract
The Weisfeiler-Leman algorithms WL(k) for $k\ge1$ form a hierarchy of increasingly powerful tests for graph isomorphism. We study how the equivalence relations they induce on graphs transfer through a graph operation $Φ$: for a given $k$, what level of WL-equivalence between graphs $H_1$ and $H_2$ guarantees WL(k)-equivalence of graphs $Φ(H_1)$ and $Φ(H_2)$? We call the least such level the transfer parameter $τ_Φ(k)$ and determine it exactly for the line graph operation $Φ= L$: $τ_L(k)=2k+1$ for $k\ge2$, while $τ_L(1)=1$. We also extend these results to the $(r,S)$-line graphs, which generalize the line graph from edges to $r$-cliques by connecting two cliques when their intersection size lies in a prescribed set $S$. For these operations we prove that $τ_{r,S}(1)=r-1$ for every $S$ and, for certain choices of $S$, that $τ_{r,S}(k)=rk+r-1$ for $k\ge r$, and we bound the transfer parameter in the remaining range. Our upper bounds on transfer parameters follow from a treewidth analysis of diagrammatic expansions of homomorphism counts into $Φ(H)$ as linear combinations of homomorphism counts into $H$. The matching lower bounds combine explicit constructions of witness graphs with the homomorphism-distinguishing closedness of graphs of bounded treewidth.