# The Iteration Number of the Weisfeiler-Leman Algorithm

arXiv: https://arxiv.org/abs/2301.13317 · HTML: https://mlsanity.com/paper/2301.13317/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jan 2023.

## Built on by (most cited first, 2 of 2)

- [Fine-grained Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2306.03698/) (2023)
- [Bridging Theory and Practice in Link Representation with Graph Neural Networks](https://mlsanity.com/paper/2506.24018/) (2025)

## Abstract (arXiv)

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 ≥ 3, we show that k-WL stabilizes after at most O(knk-1log n) iterations (where n denotes the number of vertices of the input structures), obtaining the first improvement over the trivial upper bound of nk-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 nOmega(k) iterations to stabilize. This improves over a previous lower bound of nOmega(k / log k) [Berkholz, Nordstr"om, LICS 2016]. We also investigate tradeoffs between the dimension and the iteration number of WL, and show that d-WL, where d = lceilfrac3(k+1)2rceil, can simulate the k-WL algorithm using only O(k2 · nlfloor k/2rfloor + 1 log n) many iterations, but still requires at least nOmega(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 Ck+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 Ck+1, as well as tradeoffs between variable number and quantifier rank.