The $k$-Dimensional Weisfeiler-Leman Algorithm

Neil Immerman; Rik Sengupta

arxiv: 1907.09582 · v1 · pith:X6USANQ3new · submitted 2019-07-22 · 💻 cs.CC · cs.DS· math.LO

The k-Dimensional Weisfeiler-Leman Algorithm

Neil Immerman , Rik Sengupta This is my paper

Pith reviewed 2026-05-24 17:24 UTC · model grok-4.3

classification 💻 cs.CC cs.DSmath.LO

keywords Weisfeiler-Leman algorithmgraph isomorphismcolor refinementk-dimensionalcomputational complexityalgorithm optimizationImmerman-Lander

0 comments

The pith

The k-dimensional Weisfeiler-Leman algorithm admits an optimized implementation running in O(n^{k+1} log n) time for fixed k.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This note supplies the full details of the k-dimensional Weisfeiler-Leman algorithm and its analysis from the 1990 Immerman-Lander paper. It then gives a concrete optimization that achieves O(n^{k+1} log n) runtime while k stays constant. A reader cares because the algorithm decides whether two graphs are distinguishable by k-tuple color refinement, a core subroutine in graph-isomorphism testing and related problems. The improved bound makes the procedure scale to larger vertex sets without changing its logical guarantees.

Core claim

The k-dimensional Weisfeiler-Leman algorithm can be realized so that it runs in O(n^{k+1} log n) time for any fixed k.

What carries the argument

The k-dimensional Weisfeiler-Leman procedure, which maintains and iteratively refines a coloring of all ordered k-tuples of vertices according to their adjacency patterns.

If this is right

Graph-isomorphism instances that are solvable by k-dimensional refinement become decidable in the improved time bound.
The number of refinement rounds remains bounded by the same function of n that was proved in 1990.
Work per round is reduced to O(n^k log n) through the use of faster bookkeeping for tuple counts.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same bookkeeping trick might be reusable on other tuple-refinement procedures that appear in descriptive complexity.
For moderate fixed k the new bound could bring the algorithm inside the feasible range for certain real-world network-analysis tasks.
If the log n term can later be removed, the running time would match the obvious lower bound of Omega(n^k) needed simply to read the input.

Load-bearing premise

The optimized counting and data-structure changes are assumed to leave the original 1990 correctness argument and round bound intact.

What would settle it

Any pair of graphs on which the optimized procedure produces a different stable coloring of k-tuples than the original 1990 version would show that correctness was not preserved.

read the original abstract

In this note, we provide details of the $k$-dimensional Weisfeiler-Leman Algorithm and its analysis from Immerman-Lander (1990). In particular, we present an optimized version of the algorithm that runs in time $O(n^{k+1}\log n)$, where $k$ is fixed (not varying with $n$).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

A short note that reproduces the 1990 Immerman-Lander k-WL details and claims an O(n^{k+1} log n) optimized implementation.

read the letter

This note lays out the k-dimensional Weisfeiler-Leman algorithm from the 1990 Immerman-Lander paper and presents an optimized version said to run in O(n^{k+1} log n) for fixed k. The main service is making the procedure and its analysis explicit in one place, which can help readers who need the pseudocode or the specific bound without going back to the original source. The optimization is the stated addition, and the authors position it as an incremental improvement to the running-time analysis. That part is straightforward if the changes are just implementation tweaks that do not alter the iteration count or per-round cost. The soft spot is exactly the one in the stress-test note. The abstract gives no counting argument or adapted lemmas showing that the optimizations leave the round bound and work-per-round analysis intact. If the full text simply re-states the 1990 argument without checking how the new data structures or refinement steps affect those quantities, the claimed bound does not follow. That gap sits at the center of the contribution. The paper is aimed at people already working with Weisfeiler-Leman methods in complexity or graph algorithms who want the optimized runtime written down. It does not open new questions or reorganize the literature. I would not bring it to a reading group. I would not cite it. It does not look like it needs a serious referee; the evidence supplied for the new bound is too thin.

Referee Report

1 major / 0 minor

Summary. The manuscript is a note that reproduces the details and analysis of the k-dimensional Weisfeiler-Leman algorithm from Immerman and Lander (1990) and presents an optimized version of the procedure claimed to run in O(n^{k+1} log n) time for fixed k.

Significance. If the optimized procedure and its runtime analysis are correct, the note would provide a useful reference clarifying how logarithmic factors can be achieved in the implementation of k-WL, which remains a foundational subroutine in graph-isomorphism testing and descriptive complexity.

major comments (1)

[section presenting the optimized algorithm and its analysis] The central claim of an O(n^{k+1} log n) bound requires both that the number of color-refinement rounds remains bounded by the original Immerman-Lander argument and that the per-round work is reduced by the optimizations. The manuscript reproduces the 1990 analysis but presents the optimizations without an explicit re-derivation or adaptation of the round-counting or work-per-round lemmas for the modified refinement or data-structure steps.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for recognizing its potential utility as a reference. We address the major comment point by point below.

read point-by-point responses

Referee: [section presenting the optimized algorithm and its analysis] The central claim of an O(n^{k+1} log n) bound requires both that the number of color-refinement rounds remains bounded by the original Immerman-Lander argument and that the per-round work is reduced by the optimizations. The manuscript reproduces the 1990 analysis but presents the optimizations without an explicit re-derivation or adaptation of the round-counting or work-per-round lemmas for the modified refinement or data-structure steps.

Authors: The optimizations described are confined to the data structures and implementation details used to realize each color-refinement step (e.g., maintaining ordered lists of color classes and using logarithmic-time operations for counting and re-coloring tuples). These changes do not alter the refinement operator itself or the sequence of partitions that the algorithm produces; consequently the round bound established by Immerman and Lander carries over verbatim. The per-round work is reduced from the naïve O(n^{k+1}) to an amortized O(n^{k+1} log n) total by replacing linear scans with sorting or priority-queue operations whose cost is charged across rounds. While the manuscript states these facts, we agree that an explicit paragraph adapting the original lemmas to the new implementation would improve readability. We will add such a paragraph in the revised version. revision: yes

Circularity Check

0 steps flagged

No circularity: algorithmic description references external 1990 analysis

full rationale

The paper is an explanatory note reproducing details of the k-WL algorithm and its analysis from the cited Immerman-Lander 1990 work, then describing an optimized implementation claimed to achieve O(n^{k+1} log n). No equations, fitted parameters, or self-referential definitions appear that would reduce the runtime claim to the inputs by construction. The central bound is presented as inheriting from the referenced prior analysis (with optimizations applied), which is independent external support rather than a self-citation chain or ansatz smuggling. This is a standard case of an algorithmic paper with no detectable circular steps.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper is an expository note whose central claim rests on the correctness of the 1990 analysis plus standard algorithmic counting. No free parameters, invented entities, or non-standard axioms are visible in the abstract.

axioms (1)

standard math Standard RAM-model counting of color-refinement operations on k-tuples yields an O(n^{k+1} log n) bound once the number of rounds is bounded by n^k.
The time bound is obtained by ordinary operation counting once the stabilization time is known; this is background knowledge in algorithm analysis.

pith-pipeline@v0.9.0 · 5575 in / 1342 out tokens · 30848 ms · 2026-05-24T17:24:19.351868+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
cs.CC 2026-05 unverdicted novelty 7.0

Introduces the k-Tinhofer hierarchy between general graphs and Tinhofer graphs, gives algebraic and combinatorial characterizations, proves strict separations for each k, shows P-hardness of deciding membership in the...