The Iteration Number of the Weisfeiler-Leman Algorithm

Abstract

We prove new upper and lower bounds on the number of iterations the $k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) requires until stabilization. For $k\ge 3$, we show that $k$-WL stabilizes after at most $O(k{n}^{k-1}\log n)$ iterations (where $n$ denotes the number of vertices of the input structures), obtaining the first improvement over the trivial upper bound of $n^k-1$ and extending a previous upper bound of $O(n\log n)$ for $k=2$ [Lichter et al., LICS 2019]. We complement our upper bounds by constructing $k$-ary relational structures on which $k$-WL requires at least $n^{\hat{I}\text{c◯}(k)}$ iterations to stabilize. This improves over a previous lower bound of $n^{\hat{I}\text{c◯}(k/\log k)}$ [Berkholz, Nordström, LICS 2016]. We also investigate tradeoffs between the dimension and the iteration number of WL, and show that $d$-WL, where $d=\lceil \frac{3(k+1)}{2}\rceil$, can simulate the $k$-WL algorithm using only $O(k^2\cdot n^{\lfloor k/2\rfloor +1}\log n)$ many iterations, but still requires at least $n^{\hat{I}\text{c◯}(k)}$ iterations for any $d$ (that is sufficiently smaller than $n$). The number of iterations required by $k$-WL to distinguish two structures corresponds to the quantifier rank of a sentence distinguishing them in the $(k+1)$-variable fragment $C_{k+1}$ of first-order logic with counting quantifiers. Hence, our results also imply new upper and lower bounds on the quantifier rank required in the logic $C_{k+1}$, as well as tradeoffs between variable number and quantifier rank.

30 pages, 1 figure, full version of a paper accepted at LICS 2023; second version improves the presentation of the results