Weisfeiler-Leman algorithm stabilizes faster in graph processing
The Classical Weisfeiler-Leman Algorithm Stabilizes in $O(n)$ Rounds
Data Structures and AlgorithmsDiscrete MathematicsLogic in Computer Science
Summary
The Weisfeiler-Leman algorithm is a method used to compare graphs, which are like networks of connected points. The authors found that this method completes much faster than previously thought, taking only about five times the number of points in a graph to finish. They also improved the understanding of how the method works for more complex versions. These findings help researchers know exactly how efficiently the algorithm works when telling graphs apart.
What this means in practice
- •For graph algorithm developers: Optimize graph isomorphism checks by knowing the exact maximum rounds required by this classical algorithm.
- •For machine learning engineers: Improve feature extraction in graph-based machine learning models by applying faster Weisfeiler-Leman stabilizations.
A theory result. No direct application yet.
Authors
Simon Döring, Daniel Neuen
Abstract
The classical Weisfeiler-Leman algorithm (also known as the $2$-dimensional Weisfeiler-Leman algorithm) is a simple combinatorial algorithm that was originally designed as a heuristic for the graph isomorphism problem. However, it has also numerous connections to other areas such as algebraic graph theory, logics, proof complexity, combinatorial optimization and machine learning. We prove that the classical Weisfeiler-Leman algorithm terminates after $5(n-1)$ iterations. This improves over the previous best upper bound of $O(n \log n)$ by Lichter, Ponomarenko and Schweitzer [LICS 2019], and asymptotically matches the known lower bound of $Ω(n)$ by Fürer [ICALP 2001]. Additionally, building on our results for the $2$-dimensional case, we obtain an improved upper bound of $O(n^{k-1}/(k-2)! + n^{k-2})$ on the number of iterations performed by the $k$-dimensional Weisfeiler-Leman algorithm, for every $k \geq 3$. Our arguments actually hold for a larger class of sequences of colorings of $k$-tuples; in this larger class our upper bounds are essentially tight for all $k \geq 3$.