The computational complexity of Weisfeiler–Leman refinement

The explanation

Take six points. In graph A, join them in one ring, like a hexagon. In graph B, join them as two separate triangles. In both graphs every point has exactly two neighbours. Yet B contains triangles and A contains none. The two graphs are clearly different.

A standard test, called colour refinement, cannot see this. Every point starts with the same colour. In each round, a point records the colours of its neighbours. Here every point always sees two neighbours of one colour. So the colour counts match forever, and the test calls the graphs alike.

Weisfeiler–Leman refinement is the stronger version. At dimension k, it colours every ordered list of k points, called a tuple. At dimension 2 it colours pairs. A joined pair in B has a shared neighbour, and a joined pair in A does not. After one round, the pair colour counts differ, so dimension 2 tells A from B. Two graphs are called k-equivalent when the colour counts agree at every round. Equivalent graphs need not be the same graph.

The catch is cost. A graph with n points has n^k tuples. With 100 points, dimension 2 means 10,000 pairs. Dimension 10 means 10^20 tuples. For each fixed dimension the test runs in polynomial time. But the direct methods take time n^O(k), so the power of n grows with k. The open question was whether any algorithm at all must pay that growing power. A cleverer method might reach the same verdict without colouring every tuple.

Earlier lower bounds missed this question. In 1992, Cai, Fürer and Immerman showed that some graphs need high dimension to be told apart. Those are limits on the dimension, not on every algorithm. Grohe, Lichter, Neuen and Schweitzer built graphs needing about n^(k/2) rounds of refinement. That bound concerns the refinement process itself. It does not exclude a faster method that decides the final answer another way. Lichter, Raßmann and Schweitzer expected that no algorithm runs in time n^o(k). That means a power growing more slowly than k.

The main paper proves that expectation for equivalence. For every large enough fixed k, any correct step-by-step algorithm needs at least n^(ck) steps on some input pairSource 1. Here c is a fixed positive number that does not depend on k or on the algorithmSource 2. The bound holds at every large enough number of points, not only at some sizesSource 3. It holds without any unproven assumptionSource 4. It holds even for uncoloured connected graphs where any two points are at most two steps apartSource 5.

The one obstacle is size. The proof makes graph equivalence act out a long computation. A computation with a power proportional to k touches too many places to list in a small graphSource 6. The paper writes each place as an address in short pieces. Each local block records only two neighbouring pieces of an addressSource 7. A classic diagonal argument then supplies a problem that no fast program can solve at any large size.

The other three papers settle nearby questions. When k is part of the input, deciding equivalence is EXPTIME-completeSource 8. That means it is among the hardest problems solvable in exponential time. This holds even for connected graphs where no point has more than three neighboursSource 9. Deciding whether dimension k tells one graph apart from every other graph is also EXPTIME-completeSource 10. The third gives a weaker time bound that rests on an unproven assumptionSource 11. That bound applies even to colour counts after two rounds of the joint testSource 12.

These results have firm limits. They cover deterministic algorithms, not ones that flip coins or use outside adviceSource 13. They cover graphs written out as full tables of which points are joined. The main paper makes no claim about graphs with few links per point at fixed kSource 14. None of this gives a faster test or decides when two graphs are truly the same.

How sure is this? A computer proof checker called Lean has checked formal versions of all four main statements. These are the time lower bound, the two EXPTIME-completeness results, and the graph construction in the parity-lift paper. That paper's conditional time bounds are outside the Lean check. No specialist review has been published.

What it doesn't show. This does not give a faster test, and it says nothing about randomised algorithms.