Weisfeiler–Leman refinement: the cost of deciding what it can distinguish

← All digests

Family 133 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

Graph comparison often begins by repeatedly summarizing local structure. Give every vertex a color, then refine that color according to the colors of its neighbors. Vertices with different neighborhoods eventually receive different descriptions; vertices with matching descriptions remain unresolved.

Weisfeiler–Leman refinement, abbreviated WL, extends this idea from vertices to ordered tuples of vertices. Higher-dimensional tuples see more structure, but there are many more of them. A graph with $n$ vertices has $n^k$ ordered $k$-tuples.

Is the resulting computational cost unavoidable? Perhaps an algorithm could decide whether WL will distinguish two graphs without explicitly carrying out the full refinement. A second question asks whether a chosen dimension identifies one graph among all possible comparison graphs.

This family contains four manuscripts addressing these questions. They claim an unconditional time lower bound whose exponent grows linearly with fixed dimension, and EXPTIME-completeness when the dimension is supplied as input. A companion parity construction gives explicit finite-choice reductions and early-round conditional lower bounds.

These are statements about deciding the outcome or identifying power of WL. They are not interchangeable with graph-isomorphism complexity or with the number of rounds taken by one implementation.

2. Background and essential definitions

For $k\ge2$, a tuple $\bar v=(v_1,\ldots,v_k)$ initially records which positions contain the same vertex and which contain adjacent vertices. Refinement repeatedly enriches this description. A color is a finite label for all the information accumulated so far, with labels assigned consistently across the graphs being compared.

Write $\bar v[i\leftarrow z]$ for replacement of coordinate $i$ by vertex $z$. In the joint convention, the next color records the old color and the multiset of vectors

$$\bigl(C_r(\bar v[1\leftarrow z]),\ldots, C_r(\bar v[k\leftarrow z])\bigr), \qquad z\in V.$$

A multiset retains multiplicities. The same replacement vertex is used across all coordinates of each vector, preserving correlations. In the separate convention, the algorithm records one multiset for each coordinate independently. These conventions have different dimension shifts and must be named explicitly.

Two graphs are $k$-WL equivalent if their tuple-color histograms agree at every round, or equivalently after stabilization. Isomorphic graphs are equivalent, but some nonisomorphic graphs can remain equivalent.

WL identifies $G$ at dimension $k$ if every graph $H$ equivalent to $G$ is actually isomorphic to it. Pair equivalence takes two specified graphs; identification quantifies over all possible mates of one graph.

EXPTIME is the class of decision problems solvable in time $2^{p(L)}$ for some polynomial $p$ in input length $L$. EXPTIME-completeness means both membership and that every problem in the class reduces to the problem by a polynomial-time transformation.

3. Development history and previous partial results

Weisfeiler and Leman introduced their refinement method in work on graph canonization. Its connections with counting logic and pebble games made it a central tool in finite model theory as well as graph algorithms.

Cai, Fürer, and Immerman constructed graph pairs requiring many variables to distinguish, establishing a fundamental dimension lower bound. Their parity gadgets can hide a global inconsistency from local tests. Later compressed constructions produced long refinement sequences; see Grohe, Lichter, Neuen, and Schweitzer.

A lower bound on rounds constrains refinement itself. It does not exclude a different algorithm that directly decides the final answer. Similarly, a graph pair requiring large dimension measures expressive power, not the running time of every decider at a fixed dimension.

For dimension supplied as input, Seppelt proved coNP-hardness of pair equivalence. Lichter, Raßmann, and Schweitzer independently obtained related hardness and studied identification, including fixed-dimension P-hardness and variable-dimension NP-hardness. Their WL-dimension paper separates these questions carefully.

The new family claims to go beyond those hardness classifications and beyond round-count lower bounds. Its methods combine parity constructions, bounded pebble games, compressed descriptions of long computations, and time-hierarchy arguments. The four manuscripts develop related components, but their quantifiers and graph restrictions differ.

4. What the new manuscripts claim

Fixed dimension: an unconditional exponent lower bound

M3 states that there are absolute constants $c>0$ and $k_0$ such that, for every fixed $k\ge k_0$ and every correct deterministic decider $A$, its worst-case time on pairs of $n$-vertex graphs satisfies

$$T_A(n)\ge n^{ck}$$

for every sufficiently large $n$. The threshold may depend on $A$ and $k$, but $c$ does not. Both joint and separate conventions are covered.

Inputs are explicit adjacency matrices. The stated models are multitape Turing machines and sequential RAMs with logarithmic-size words, boundedly many accesses per instruction, and fixed instructions computable in polynomial bit time. The bound remains valid on simple connected uncolored graphs of diameter at most two. It makes no bounded-degree claim.

This is unconditional: no Exponential Time Hypothesis is assumed. It also concerns every sufficiently large graph order, not merely infinitely many sizes.

Supplied dimension: two EXPTIME classifications

M4 claims EXPTIME-completeness of joint-update pair equivalence when $k\ge2$ is part of the input. The claim remains true for connected simple uncolored graphs of equal positive order and maximum degree at most three. Such graphs are subcubic, not necessarily regular.

M2 separately claims EXPTIME-completeness of deciding whether $\mathrm{WLdim}(G)\le k$. It uses ordinary neighbor refinement at dimension one and joint updates at higher dimensions. Graphs are nonempty, simple, uncolored, and explicitly represented.

Both variable-dimension results allow binary encoding of $k$, and both remain EXPTIME-complete with unary encoding. Their hardness therefore does not rely on hiding an exponentially large number in a short dimension field.

An explicit parity reduction with early detection

M1 starts with finite domains and pairwise compatibility labels. It constructs two uncolored graphs that are WL equivalent exactly when there is no compatible simultaneous choice. Joint dimension $k$ uses $k+1$ domains; separate dimension $k$ uses $k$.

When a compatible choice exists, the histograms differ after at most two joint rounds or one separate round. Under positive-rate ETH, this yields fixed-dimension $n^{\Omega(k)}$ time exclusions even for these early histograms. M3 supersedes its conditional bound for stable equivalence, but does not erase the separate early-round reduction and its structural contribution.

5. Why the advance matters

Provisional importance: 4/5. The family claims a substantial complexity classification for a widely studied graph-comparison method. The fixed-dimension theorem would show that the growing exponent is inherent to deterministic sequential decision, even when the algorithm need not materialize every tuple color.

The variable-dimension results identify a different boundary: allowing dimension to vary turns a collection of polynomial-time problems into an EXPTIME-complete problem. The identification theorem adds the universal comparison over all mates, which needs its own reduction rather than following automatically from pair equivalence.

The subcubic result is especially revealing. Bounded-degree graph isomorphism is polynomial-time solvable by Luks’s classical theory, yet asking whether a prescribed WL dimension distinguishes a pair is a different question. A nonisomorphic pair can still be WL equivalent. Thus the claim does not contradict efficient bounded-degree isomorphism testing.

The score reflects both the central method and the strength of the proposed lower bounds, while retaining the computational-model and quantifier restrictions that give those bounds their meaning.

6. The main idea

Express indistinguishability as a game

The joint $k$-dimensional convention corresponds to a bijective game with $k+1$ pair slots. Each occupied slot marks one vertex in each graph. Before a new vertex is chosen, Duplicator announces a bijection between the entire vertex sets; Spoiler then selects a vertex and its mate is determined by that bijection.

Duplicator must always preserve equality and adjacency among marked vertices. Winning indefinitely characterizes WL equivalence. The order of moves matters: responding to one already chosen vertex would be a weaker requirement than announcing a whole bijection first.

The constructions encode local binary equations into graphs so that game moves test compatible local assignments. A global parity obstruction can remain invisible to small collections of marked pieces.

Store a long computation through short address fragments

A computation can have exponentially many locations, too many to list in a polynomial-size graph. The manuscripts describe locations by tuples of address coordinates. Small graph blocks store only adjacent coordinate fragments. A full cycle of blocks reconstructs an address; one spare game pair transports information between addressed constraints.

The key extension property says that every retained local assignment can be extended when another permitted block is added. It is not enough that some compatible assignment exists somewhere: the game must preserve the particular choices already made.

Auxiliary potentials at block corners absorb changes of local offsets on collections that do not wrap around a full address cycle. A complete ring exposes the intended constraint. Two-coordinate buffers allow symmetric consistency equations to encode directed computation without forcing unwanted information backward.

M4 makes every dependence on the growing address dimension explicit and then replaces high-degree components by paths, trees, and equality connections. Recognition gadgets preserve the needed information while keeping maximum degree three.

Handle every mate, or every sufficiently large size

Identification requires an additional reconstruction argument. M2 shows that any graph equivalent to its constructed graph must correspond to some shifted version of the encoded constraints. In the accepting case, every permitted shift extends to one global isomorphism. In the rejecting case, a locally consistent shift lacks a global solution, producing a nonisomorphic equivalent mate.

M3 instead combines a fixed-dimension compressed computation with a diagonal language that is hard at every sufficiently large input length. Padding and a transfer across intervals of graph orders rule out isolated large sizes at which a correct decider might be unusually fast. This is why its conclusion is stronger than an infinitely-often lower bound.

M1 has a complementary viewpoint through graph homomorphisms, which preserve edges under vertex maps. Bounded-treewidth test graphs can characterize WL equivalence. Parity lifts make the difference between two homomorphism counts nonnegative for each projection, preventing cancellation. Small decomposition bags and helper vertices then extract a compatible choice whenever a distinguishing test exists.

7. Scope, limitations, and open questions

The fixed-dimension lower bound is deterministic and sequential in explicit adjacency-matrix models. It does not automatically cover randomized algorithms, nonuniform advice, parallel computation, or unit-cost arithmetic on unbounded integers.

The diameter-two restriction in M3 and the degree-three restriction in M4 belong to different theorems. They should not be combined into one stronger graph promise. Likewise, M1 and M3 cover both refinement conventions, while the variable-dimension classifications stated here use joint refinement.

Identification and pair equivalence remain distinct despite having the same claimed complexity class when dimension varies. Refinement-round counts are a third quantity. Maintaining these distinctions is essential when applying the results to graph algorithms or logical methods.

The family leaves room for faster algorithms on restricted graph classes, improved constants and parameter tradeoffs, and analyses under other computational models. Its lower bounds and reductions are presented as manuscript claims, not independently verified results.

8. Sources and further reading

Cai–Fürer–Immerman explains the original parity obstruction; the compressed-CFI work concerns refinement rounds. Seppelt and Lichter–Raßmann–Schweitzer supply the earlier decision-hardness landscape. The source manuscripts below respectively cover the finite-choice reduction, identification, unconditional fixed-dimension time, and variable-dimension pair equivalence.

Source manuscripts

• M1. OpenAI, Parity lifts and bounded-treewidth witnesses for Weisfeiler–Leman equivalence (September 25, 2026).
• M2. OpenAI, The complexity of identifying a graph by Weisfeiler–Leman refinement (September 25, 2026).
• M3. OpenAI, Unconditional time lower bounds for Weisfeiler–Leman equivalence (September 25, 2026).
• M4. OpenAI, Variable-dimension Weisfeiler–Leman equivalence on general and subcubic graphs (September 25, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.