Weisfeiler-Leman dimension linked to graph rank width improves isomorphism tests
Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width
Discrete MathematicsLogic in Computer Science
Summary
Graphs are mathematical objects made of points connected by lines, and checking if two graphs are the same is often difficult. The Weisfeiler-Leman (WL) algorithm tries to tell graphs apart by coloring groups of points based on their connections, but using more groups gets slow. The authors connect how complicated a graph is, measured by something called rank width, to the number of groups the WL algorithm needs. They show that by looking at certain structural features, you can know the exact WL dimension needed to distinguish a graph from any other, which helps understand when the test works well.
What this means in practice
- •For graph algorithm designers: Determine precise WL algorithm dimensions for efficiently distinguishing graphs with bounded rank width in isomorphism tests.
- •For network analysis engineers: Use graph structure parameters such as rank width to optimize graph matching and comparison algorithms in communication network data.
A theory result. No direct application yet.
Authors
Antonios Kalampakas
Abstract
The Weisfeiler-Leman (WL) algorithm tests graph isomorphism by assigning colours to $d$-tuples of vertices and iteratively refining the colouring according to neighbourhood configurations until it stabilizes. Increasing $d$ allows the test to detect finer structural differences between graphs, but the computational cost grows exponentially with $d$. The central question is which dimension allows us to distinguish nonisomorphic graphs. We relate a sufficient such dimension to the structure of a graph $G$ through a rank decomposition over $\mathbb F_2$. The two parameters governing the bound are the maximum cut rank $w$ and the fork load $\ell$, which is the largest sum of the parent and two child cut ranks at a fork in the decomposition tree. We prove that WL in dimension $\max\{\ell+1,2w+2\}$ distinguishes every finite nonempty vertex-coloured graph $G$ with such a decomposition from every graph not isomorphic to $G$. Consequently, for $k\geq1$, graphs of rank width at most $k$ can be distinguished from every nonisomorphic graph in dimension $3k+1$, graphs of linear rank width at most $k$ in dimension $2k+2$, and edgeless graphs in dimension one. Uncoloured Cai-Fürer-Immerman (CFI) constructions give linear lower bounds for both width parameters, so the upper bounds are tight up to constant factors.