# The Iteration Number of Colour Refinement

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2020.

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

- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks](https://mlsanity.com/paper/2203.13913/) (2022)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [Fine-grained Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2306.03698/) (2023)
- [The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs](https://mlsanity.com/paper/2105.05911/) (2021)
- [Probabilistic Graph Rewiring via Virtual Nodes](https://mlsanity.com/paper/2405.17311/) (2024)
- [Weisfeiler-Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs](https://mlsanity.com/paper/2210.03990/) (2022)
- [Towards Bridging Generalization and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2410.10051/) (2024)
- [On the approximation capability of GNNs in node classification/regression tasks](https://mlsanity.com/paper/2106.08992/) (2021)
- [Gradual Weisfeiler-Leman: Slow and Steady Wins the Race](https://mlsanity.com/paper/2209.09048/) (2022)
- [How Hard Is It for Message-Passing GNNs to Simulate One Weisfeiler-Lehman Color-Refinement Step?](https://mlsanity.com/paper/2410.01308/) (2024)
- [A method for the systematic generation of graph XAI benchmarks via Weisfeiler-Leman coloring](https://mlsanity.com/paper/2505.12437/) (2025)

## Abstract (arXiv)

The Colour Refinement procedure and its generalisation to higher dimensions, the Weisfeiler-Leman algorithm, are central subroutines in approaches to the graph isomorphism problem. In an iterative fashion, Colour Refinement computes a colouring of the vertices of its input graph. A trivial upper bound on the iteration number of Colour Refinement on graphs of order n is n-1. We show that this bound is tight. More precisely, we prove via explicit constructions that there are infinitely many graphs G on which Colour Refinement takes |G|-1 iterations to stabilise. Modifying the infinite families that we present, we show that for every natural number n >= 10, there are graphs on n vertices on which Colour Refinement requires at least n-2 iterations to reach stabilisation.