Skip to content

When are two graphs the same shape? Graph fingerprints (Weisfeiler–Leman)

A service that recomputes a plan for every graph snapshot can save work by noticing that today's snapshot has the same shape as one it has already solved. That needs a cheap fingerprint of a graph's shape. This page explains the standard fingerprint (colour refinement), where it fails, why its stronger versions get expensive quickly, and why the library's router caps how strong a fingerprint it will compute.

It covers Weisfeiler–Leman complexity (catalog result 133). It assumes you know what a graph is. Symbols are in How to read these pages; terms in the glossary.

The question, in product terms

The matching_marketplace case builds a driver–rider feasibility graph every few seconds per zone. Before running the matching it asks the router for a fingerprint, so a plan computed for one snapshot can be reused when the same shape repeats. When two different shapes get the same fingerprint, the temptation is a config flag — wl_k: 5 — to "make the hash more exact". That flag multiplies the cost by a factor of roughly \(n\) per step of \(k\), where \(n\) is the number of vertices. The router refuses \(k > 2\) before any work starts.

Intuition: colour refinement by hand

Colour refinement gives every vertex the same colour, then repeatedly recolours each vertex by "my colour plus the multiset of my neighbours' colours", until nothing changes. Two graphs whose final colour counts differ are certainly not the same shape. Two graphs whose counts agree might be.

Take a path a–b–c. Round 0: all colour 0. Round 1: a and c see one neighbour, b sees two, so b gets a new colour. Round 2 changes nothing. The fingerprint is "two vertices of one colour, one of another".

Now the failure case. A 6-cycle and two separate triangles are clearly different shapes (one is connected, one is not):

graph LR
    subgraph "6-cycle"
    a1((1)) --- a2((2)) --- a3((3)) --- a4((4)) --- a5((5)) --- a6((6)) --- a1
    end
    subgraph "two triangles"
    b1((1)) --- b2((2)) --- b3((3)) --- b1
    b4((4)) --- b5((5)) --- b6((6)) --- b4
    end

But every vertex in both graphs has exactly two neighbours, so colour refinement never splits anything: both graphs end with six vertices of one colour. The fingerprints collide.

Higher-dimensional versions colour pairs, triples, … of vertices instead of single vertices. The classical pair-colouring algorithm of Weisfeiler and Leman (1968) asks, for each pair \((i, j)\), how many \(k\) give each combination of colours of \((i, k)\) and \((k, j)\). That counts triangles through each edge, so it separates the 6-cycle from two triangles. Each step up in dimension costs about another factor of \(n\).

Worked example

uv run grounded-decision examples matching_marketplace

tick 2  WL fingerprint: k=1 allowed, k=5 refused
  DECISION
         k ≤ 2 runs (polynomial); k > 2 is refused before it starts
         k=1 ok=True; k=5 ok=False
         a WL fingerprint can collide; verify before reusing a cached plan
  OUTPUT wl1 ok=True
         wl5 ok=False  k=5 exceeds cap 2: k-WL takes about n^(k+1) steps, so cost grows exponentially with k (catalog 133)

From Python, on the marketplace's 6-vertex cycle:

from grounded_decision import Envelope, Subgoal, dispatch

adj = {0: {3, 4}, 1: {3, 5}, 2: {4, 5}, 3: {0, 1}, 4: {0, 2}, 5: {1, 2}}
dispatch(Subgoal("wl", Envelope.P_EXACT, {"adj": adj, "k": 1})).to_dict()
# {'subgoal': 'wl', 'envelope': 'p_exact', 'ok': True,
#  'detail': 'WL-1 colors', 'value': (0, 0, 0, 0, 0, 0)}
dispatch(Subgoal("wl", Envelope.P_EXACT, {"adj": adj, "k": 5})).to_dict()
# {'subgoal': 'wl', 'envelope': 'exptime_trap', 'ok': False,
#  'detail': 'k=5 exceeds cap 2: k-WL takes about n^(k+1) steps, so cost grows exponentially with k (catalog 133)', 'value': None}

The single colour at \(k=1\) is correct colour refinement: every vertex of a cycle looks alike. The refusal at \(k=5\) comes back as a result with ok=False, not an exception.

The collision from the intuition section, run through the library's own functions:

from collections import Counter
from grounded_decision.router.wl import color_refinement, wl2_hash

cycle = {i: {(i + 1) % 6, (i - 1) % 6} for i in range(6)}
triangles = {0: {1, 2}, 1: {0, 2}, 2: {0, 1}, 3: {4, 5}, 4: {3, 5}, 5: {3, 4}}
color_refinement(cycle), color_refinement(triangles)
# ((0, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0))
Counter(wl2_hash(cycle)) == Counter(wl2_hash(triangles))
# True: both are {0: 6, 1: 12, 2: 18}

So the library's \(k=2\) hash does not separate these two graphs either (see the differences below).

The precise statements

Indexing conventions. Papers number these algorithms differently, which causes real confusion:

  • 1-WL is colour refinement (single vertices).
  • In the convention used by Grohe and most recent work, \(k\)-WL for \(k \ge 2\) colours \(k\)-tuples, and the folklore variant \(k\)-FWL is as strong as \((k+1)\)-WL.
  • The original 1968 pair algorithm is 2-FWL in that convention, so as strong as 3-WL. Some papers call it "2-WL".

Cost. For fixed \(k\), \(k\)-WL runs in polynomial time, about \(n^{k+1} \log n\) steps (Immerman and Lander). It is polynomial for every fixed \(k\), but the exponent grows with \(k\): at \(n = 1000\), \(n^{k+1}\) is \(10^9\) for \(k=2\) and \(10^{12}\) for \(k=3\).

Power. No fixed \(k\) identifies every graph: Cai, Fürer and Immerman built pairs of graphs that \(k\)-WL cannot tell apart unless \(k\) grows linearly with \(n\). Berkholz and Nordström showed the number of refinement rounds can be \(n^{\Omega(k)}\).

Where this result stands

In the wider literature: fixed-\(k\) Weisfeiler–Leman is polynomial for each \(k\) (Immerman–Lander), cannot identify all graphs at any fixed \(k\) (Cai–Fürer–Immerman), and can need \(n^{\Omega(k)}\) rounds (Berkholz–Nordström). To our knowledge, unconditional \(n^{\Omega(k)}\) time lower bounds for deciding \(k\)-WL equivalence, and EXPTIME-completeness when \(k\) is part of the input, are not established outside the catalog.

In this project's math catalog (result 133): for sufficiently large fixed \(k\), deciding \(k\)-WL equivalence needs \(n^{ck}\) time in the stated sequential machine models, for one absolute \(c > 0\); with \(k\) given in binary as part of the input, equivalence and identification are EXPTIME-complete (even on graphs of maximum degree 3); and parity-lift constructions give WL-equivalent pairs for every \(k \ge 4\). Checked by Lean statements in the companion math catalog.

What this library relies on: only the practical fact that cost grows like \(n^{k+1}\). The cap of 2 is a cost budget. See Where each result stands.

REF_WL has trust level lean (trust levels): a machine-checked statement exists in the catalog; the library does not run it.

What the code does, and how it differs

grounded_decision.router.wl provides refine(graph, k, limits), reached through dispatch(Subgoal("wl", envelope, {"adj": ..., "k": ...})):

k What runs Result
1 color_refinement: standard colour refinement, at most \(n\) rounds ok=True, envelope p_exact, one colour per vertex
2 wl2_hash: colours ordered pairs ok=True, envelope p_exact, \(n^2\) colours
below 1, or above Limits.max_wl_k (default 2) nothing ok=False, envelope exptime_trap

Differences from the theory that a user must know:

  • The \(k=2\) hash is not 2-FWL and not the 1968 algorithm. Each pair \((i, j)\) is recoloured from its own colour, the multiset of colours of \((i, k)\) over all \(k\), and separately the multiset of colours of \((k, j)\). It never looks at the combination \((i, k), (k, j)\) for the same \(k\), so it cannot count triangles. It fails on the 6-cycle against two triangles, shown above. To our knowledge, this "oblivious" pair refinement has the same distinguishing power as colour refinement, so k=2 adds cost without adding much power. Treat it as a hash.
  • The returned tuple depends on vertex numbering. Colours come back in sorted vertex order. The same path numbered two ways gives (0, 1, 0) and (1, 0, 0). To use either result as a shape fingerprint, compare the multiset of colours (for example tuple(sorted(colours)) or a Counter), not the raw tuple.
  • EXPTIME_TRAP is a budget label. A refusal at \(k = 3\) or \(k = 5\) means "too expensive under our budget". It does not mean that \(k\)-WL at that fixed \(k\) is EXPTIME-hard; it is polynomial. The catalog's EXPTIME result concerns \(k\) supplied as part of the input.
  • Cost of what does run. Colour refinement is fast. The pair hash touches \(n^2\) pairs and \(n\) neighbours of each per round, so about \(n^3\) per round in pure Python: on a 200-vertex 4-regular graph it took about 1.1 s on the machine these pages were written on, against well under a millisecond for colour refinement. That alone can blow a 50 ms decision budget.
  • Envelope tags. A caller who tags the request UNDEC or EXPTIME_TRAP is refused before \(k\) is read ("envelope EXPTIME_TRAP: refuse"). A missing "adj" raises KeyError. Undirected graphs must list both directions of every edge.

API details: router API, router internals.

Limits, and when this matters in practice

A matching fingerprint does not establish that two graphs are the same shape. Colour refinement collides on every pair of regular graphs with the same degree and size; the library's \(k=2\) hash collides on at least the 6-cycle against two triangles. Before reusing a cached plan, verify.

What to do instead of raising \(k\):

  • Use a canonical-labelling tool when you need an exact answer. nauty and Traces (also exposed by several graph libraries) decide isomorphism quickly on real-world graphs.
  • Add cheap invariants to the key: vertex and edge counts, degree sequence, number of connected components, triangle count.
  • Keep the cap. Limits.max_wl_k can be lowered to 1 for a tenant that does not need pair colours; raising it buys cost, not correctness. See Choosing parameters and Limits.