Graph Isomorphism, in depth: colour refinement, individualisation and backtracking, canonical forms, and the WL limit of GNNs

Where the problem sits in complexity theory

Graph isomorphism (GI) is in NP: a proposed bijection can be checked in polynomial time. No polynomial algorithm is known. Yet GI is not believed to be NP-complete: if it were, the polynomial hierarchy would collapse to its second level, which most complexity theorists consider very unlikely. That puts it in the small club of natural problems thought to be in between.

In late 2015 László Babai announced a quasi-polynomial algorithm, running in time exp((log n)^O(1)). In January 2017 Harald Helfgott found an error in the analysis; Babai repaired it within days, and the quasi-polynomial claim stands. The algorithm is a theoretical milestone, not something you run. Many restricted classes are solved in polynomial time: trees and planar graphs in linear time, and graphs of bounded degree by Luks's group-theoretic method from 1982.

Invariants: fast filters, never proofs

Start cheap. Count vertices and edges. Compare sorted degree sequences, the number of triangles, connected component sizes, eigenvalues of the adjacency matrix. Each of these is an invariant: isomorphic graphs always agree on it. If any differs, you have a proof of non-isomorphism in polynomial time, and on real data most non-isomorphic pairs die here.

The converse fails. Agreement on any set of cheap invariants never proves isomorphism. Non-isomorphic graphs with the same spectrum (cospectral graphs) are common. The pair in the figure below has identical degree sequences and defeats colour refinement, yet the triangle count (0 against 2), the spectrum ({2, 1, 1, -1, -1, -2} against {2, 2, -1, -1, -1, -1}) and connectivity each separate it, which is why real pipelines run several invariants side by side. To prove isomorphism you need a bijection, and to find one you need search.

Colour refinement (1-WL)

Colour refinement, also called the 1-dimensional Weisfeiler-Leman algorithm (1-WL), turns the degree idea into an iterative process. Start with every vertex the same colour (or coloured by its label, if vertices are labelled). In each round, give each vertex a new colour determined by its old colour and the multiset of its neighbours' colours. Stop when a round does not split any colour class. With the right data structures this runs in O((n + m) log n).

The output is a partition of the vertices that any isomorphism must respect: a vertex can only map to a vertex of the same final colour. Running it on the disjoint union of the two graphs gives both graphs one shared palette, so comparing their colour histograms is meaningful. Different histograms prove non-isomorphism. If every class is a single vertex on each side, the bijection is forced and can be checked directly.

Refinement is fooled by regular graphs. In a k-regular graph every vertex has the same degree, so round one assigns every vertex the same signature and the partition is already stable. The figure shows the smallest familiar case: the 6-cycle and two disjoint triangles are both 2-regular on six vertices, and 1-WL cannot tell them apart. Higher-dimensional k-WL colours k-tuples of vertices and is strictly stronger, but Cai, Fürer and Immerman showed in 1992 that for every fixed k there are non-isomorphic graph pairs k-WL cannot distinguish.

Individualisation, refinement and backtracking

When refinement stalls with a non-trivial partition, practical solvers individualise: pick a vertex x in a non-singleton class of the first graph, give it a fresh colour, give the same fresh colour to one candidate y in the matching class of the second graph, and refine again. If that branch fails, try the next y. This is backtracking where refinement does most of the pruning.

def refine(adj, colors):
    """1-WL to the coarsest stable colouring. Colours depend only on structure,
    never on vertex ids, so two graphs refined together share one palette."""
    while True:
        sig = {v: (colors[v], tuple(sorted(colors[u] for u in adj[v]))) for v in adj}
        palette = {s: i for i, s in enumerate(sorted(set(sig.values())))}
        new = {v: palette[sig[v]] for v in adj}
        if len(palette) == len(set(colors.values())):
            return new                       # no class split: stable
        colors = new

def union(g, h):                             # tag vertices with the side they came from
    adj = {(0, v): [(0, u) for u in g[v]] for v in g}
    adj.update({(1, v): [(1, u) for u in h[v]] for v in h})
    return adj

def histogram(colors, side):
    return sorted(c for (s, _), c in colors.items() if s == side)

def isomorphism(g, h):
    """A dict mapping g's vertices to h's, or None."""
    if len(g) != len(h) or sum(map(len, g.values())) != sum(map(len, h.values())):
        return None
    adj = union(g, h)
    return _search(adj, refine(adj, {v: 0 for v in adj}), g, h)

def _search(adj, colors, g, h):
    if histogram(colors, 0) != histogram(colors, 1):
        return None
    cells = {}
    for (s, v), c in colors.items():
        cells.setdefault(c, ([], []))[s].append(v)
    if all(len(a) == 1 for a, _ in cells.values()):          # discrete: forced map
        f = {a[0]: b[0] for a, b in cells.values()}
        ok = all(sorted(f[u] for u in g[v]) == sorted(h[f[v]]) for v in g)
        return f if ok else None
    a, b = min((cl for cl in cells.values() if len(cl[0]) > 1), key=lambda cl: len(cl[0]))
    x, fresh = a[0], max(colors.values()) + 1
    for y in b:                                               # try each partner for x
        trial = dict(colors)
        trial[(0, x)] = trial[(1, y)] = fresh
        f = _search(adj, refine(adj, trial), g, h)
        if f is not None:
            return f
    return None

Graphs are adjacency dictionaries. The function returns a verified bijection, never just a yes, so a caller can check the answer independently. It was compared with brute-force permutation search on 3,000 random pairs of graphs with up to 7 vertices; 1,963 pairs were isomorphic and every verdict agreed, with every returned mapping checked edge by edge.

Worked examples

The 6-cycle against two triangles. Refining the union gives all twelve vertices one colour, so the histograms match. The search individualises vertex 0 of the cycle and pairs it with each triangle vertex in turn. After refinement, the cycle splits into distance classes from vertex 0 (sizes 1, 2, 2, 1), while the triangles split differently (1, 2, and 3 for the other triangle), so every branch fails on the histogram check and the function returns None. A connectivity check would have caught this pair earlier, which is why real tools combine invariants with search.

The Petersen graph against a relabelled copy. The Petersen graph is 3-regular, so refinement does nothing at first. Individualising one vertex splits the rest into its 3 neighbours and 6 non-neighbours, and a few more individualisations make the partition discrete. The function returns a valid mapping for a randomly shuffled copy. Highly symmetric graphs like this one are where search costs grow: many branches succeed equivalently, and without automorphism pruning a non-isomorphic pair with similar symmetry makes the search explore them all.

Canonical forms and deduplication at scale

Comparing graphs pairwise does not scale to deduplicating a million of them. A canonical form solves that: a function that maps every graph to a representative labelling such that two graphs get the same form exactly when they are isomorphic. Hash the canonical form and deduplication becomes a hash-table lookup. Production tools compute canonical forms with individualisation-refinement plus automorphism pruning: once the search discovers a symmetry of the graph, it skips branches that symmetry maps onto ones already explored. Brendan McKay's nauty and the Traces program by McKay and Piperno, and bliss by Junttila and Kaski, are the widely used implementations; saucy specialises in finding automorphisms of large sparse graphs.

In chemistry, canonical identifiers such as InChI and canonical SMILES rest on the same principle, with atom and bond types as initial colours. In circuit verification, layout-versus-schematic tools match device netlists with refinement-style partitioning.

Weisfeiler-Leman and graph neural networks

Message-passing graph neural networks update each node from its own state and an aggregate of its neighbours' states, which is colour refinement with learned colours. In 2019, Xu and colleagues (the GIN paper) and Morris and colleagues showed that such networks can distinguish at most the graphs 1-WL distinguishes, and that sum aggregation with injective update functions reaches that limit. A standard message-passing GNN therefore produces the same graph embedding for the 6-cycle and two triangles, whatever its weights.

That has practical consequences. If your task depends on cycle structure or on regular substructures, add features refinement cannot compute (cycle counts, random node identifiers, positional encodings) or use higher-order architectures. And when deduplicating a graph dataset, a WL hash is a fast first filter, but colliding pairs need an exact check before you call them duplicates.

Failure modes

• Treating an invariant or hash as proof. Equal WL hashes, spectra or degree sequences only mean maybe. Confirm with a bijection.
• Ignoring labels and direction. Labelled vertices or edges must seed the initial colours, and directed graphs need in- and out-neighbour multisets as separate parts of the signature, or you match graphs that differ.
• Exponential blow-up on hard families. Strongly regular graphs and Cai-Fürer-Immerman constructions defeat refinement, and Neuen and Schweitzer proved exponential lower bounds for the individualisation-refinement framework itself. Set a time budget per pair.
• No automorphism pruning. The search on this page lacks it; on symmetric inputs it explores equivalent branches repeatedly. Use nauty, Traces or bliss in production.
• Floating-point invariants. Eigenvalues compared with exact equality give false negatives; compare with tolerance and treat them as filters only.

Operational guidance

• Build a pipeline: cheap invariants, then WL hash bucketing, then exact canonical forms or pairwise search inside each bucket.
• Log how many pairs reach each stage and the slowest pairs; a new family of symmetric inputs shows up there first.
• Store the returned mapping or canonical labelling with each match so a reviewer or test can re-verify it.
• Fix the exact encoding of labels and edge types before hashing; a change silently splits or merges every bucket.

Trade-offs

What to do next

1. Run the code above on the 6-cycle and two triangles, print the colours after each individualisation, and confirm every branch fails.
2. Add vertex labels as initial colours and test with labelled molecules from your own data.
3. Hash your dataset's graphs with 1-WL, count collisions, and check a sample of colliding pairs exactly; report how many were true duplicates.
4. Try nauty, Traces or bliss on your hardest symmetric inputs and compare with the search here.
5. If you train GNNs, test whether your model separates the 6-cycle from two triangles; if it must and does not, add cycle-count or positional features.
6. Review BFS and DFS for the connectivity and distance invariants that catch many pairs before any search.