Weisfeiler-Leman Algorithm

A Bit of History

Boris Weisfeiler and Andrey Leman published this algorithm in 1968 as a practical heuristic for the graph isomorphism problem previewed in Part 18 — decades before Babai's 2015 quasipolynomial breakthrough, and long before anyone could have predicted its second life. That second life arrived once graph neural networks (Part 26) became widespread: researchers proved that the message-passing architecture underlying essentially every mainstream GNN can never distinguish two graphs the 1-dimensional Weisfeiler-Leman test itself cannot distinguish — turning a 50-year-old isomorphism heuristic into the precise mathematical ceiling on modern deep learning's graph-reasoning power.

Working Principle: Color Refinement

The 1-dimensional Weisfeiler-Leman algorithm (often called simply "color refinement") is disarmingly close in spirit to the message-passing framework from Part 26:

1. Assign every vertex the same initial "color" (or, in the labeled-graph case, its own label).
2. Refine: simultaneously recompute every vertex's color as a hash of its current color together with the multiset of its neighbors' current colors — vertices with identical local neighborhoods (in terms of color) get identical new colors; vertices with even slightly different neighborhoods get different new colors.
3. Repeat step 2 until the partition of vertices into color classes stops changing (guaranteed to happen within \(V\) rounds).
4. Two graphs are declared possibly isomorphic if their final color-class multisets match exactly; if the multisets differ, the graphs are certainly non-isomorphic.

Worked Example

On two 6-vertex graphs that are not isomorphic but happen to be locally indistinguishable everywhere (a specific pair of 3-regular graphs constructed precisely to fool color refinement), every vertex in both graphs converges to the exact same final color after refinement stabilizes — 1-WL incorrectly reports "possibly isomorphic" on a pair that is provably not. This isn't a bug in the algorithm's implementation; it's a fundamental limitation of the test itself, and such graph pairs are the standard textbook example used to demonstrate 1-WL's real expressive ceiling.

Correctness & Its Limits

The algorithm is a one-directional test: if the final color-class multisets differ, the graphs are guaranteed non-isomorphic (a sound, reliable negative result), but if the multisets match, the graphs might still be non-isomorphic — 1-WL cannot distinguish certain genuinely different graphs, most famously all pairs of regular graphs with the same degree (since every vertex already has an identical initial neighborhood-multiset by symmetry, refinement can never break the tie). Higher-dimensional generalizations (\(k\)-WL, considering tuples of \(k\) vertices at once rather than single vertices) are strictly more powerful for larger \(k\), forming an infinite hierarchy of increasingly expressive (and increasingly expensive) isomorphism tests.

Complexity Analysis

Each refinement round touches every edge once, and the number of rounds needed is bounded by the number of vertices (since the number of distinct color classes strictly increases each round it changes, up to a maximum of \(V\)):

$$\text{Time: } O(VE) \qquad \text{(naive bound; } O(E\log V) \text{ achievable with careful bucket-based refinement)}$$

Fast enough to run as a cheap, reliable "no" filter before attempting expensive exact isomorphism algorithms — most practical isomorphism-checking pipelines run 1-WL first, only falling back to slower exact methods when 1-WL fails to rule out isomorphism.

Implementation

def weisfeiler_leman(n, adj, rounds=None):
    """
    n: number of vertices. adj[v]: list of neighbors.
    Returns the final sorted multiset of color-class sizes (a canonical
    "fingerprint" usable to compare against another graph's fingerprint).
    """
    if rounds is None:
        rounds = n  # guaranteed to stabilize within n rounds

    color = [0] * n  # all vertices start with the same initial color

    for _ in range(rounds):
        signatures = []
        for v in range(n):
            neighbor_colors = tuple(sorted(color[u] for u in adj[v]))
            signatures.append((color[v], neighbor_colors))

        # Assign new colors: identical signatures get identical new colors
        unique_sigs = sorted(set(signatures))
        sig_to_color = {sig: i for i, sig in enumerate(unique_sigs)}
        new_color = [sig_to_color[sig] for sig in signatures]

        if new_color == color:
            break  # stabilized
        color = new_color

    from collections import Counter
    return tuple(sorted(Counter(color).values()))

adj_a = [[1,2],[0,2],[0,1,3],[2,4],[3]]
adj_b = [[1,2],[0,2],[0,1,3],[2,4],[3]]  # identical shape here for illustration
print(weisfeiler_leman(5, adj_a) == weisfeiler_leman(5, adj_b))  # True (same fingerprint)

#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int> weisfeilerLeman(int n, vector<vector<int>>& adj, int rounds) {
    vector<int> color(n, 0);

    for (int r = 0; r < rounds; r++) {
        vector<pair<int, vector<int>>> signatures(n);
        for (int v = 0; v < n; v++) {
            vector<int> neighborColors;
            for (int u : adj[v]) neighborColors.push_back(color[u]);
            sort(neighborColors.begin(), neighborColors.end());
            signatures[v] = {color[v], neighborColors};
        }

        map<pair<int, vector<int>>, int> sigToColor;
        vector<int> newColor(n);
        for (int v = 0; v < n; v++) {
            auto it = sigToColor.find(signatures[v]);
            if (it == sigToColor.end()) {
                int newId = sigToColor.size();
                sigToColor[signatures[v]] = newId;
                newColor[v] = newId;
            } else {
                newColor[v] = it->second;
            }
        }

        if (newColor == color) break;
        color = newColor;
    }
    return color;
}

int main() {
    int n = 5;
    vector<vector<int>> adj = {{1,2},{0,2},{0,1,3},{2,4},{3}};
    vector<int> colors = weisfeilerLeman(n, adj, n);
    for (int c : colors) cout << c << " ";
    return 0;
}

import java.util.*;

class WeisfeilerLeman {
    static int[] refine(int n, List<List<Integer>> adj, int rounds) {
        int[] color = new int[n];

        for (int r = 0; r < rounds; r++) {
            List<String> signatures = new ArrayList<>();
            for (int v = 0; v < n; v++) {
                List<Integer> neighborColors = new ArrayList<>();
                for (int u : adj.get(v)) neighborColors.add(color[u]);
                Collections.sort(neighborColors);
                signatures.add(color[v] + ":" + neighborColors);
            }

            Map<String, Integer> sigToColor = new HashMap<>();
            int[] newColor = new int[n];
            for (int v = 0; v < n; v++) {
                newColor[v] = sigToColor.computeIfAbsent(signatures.get(v), k -> sigToColor.size());
            }

            if (Arrays.equals(newColor, color)) break;
            color = newColor;
        }
        return color;
    }

    public static void main(String[] args) {
        int n = 5;
        List<List<Integer>> adj = Arrays.asList(
            Arrays.asList(1,2), Arrays.asList(0,2), Arrays.asList(0,1,3),
            Arrays.asList(2,4), Arrays.asList(3)
        );
        int[] colors = refine(n, adj, n);
        System.out.println(Arrays.toString(colors));
    }
}

Real-World Applications

Exercises

1. Run color refinement by hand on two small triangles (3-cycles) versus one 6-cycle, and verify the algorithm correctly distinguishes them as non-isomorphic.
2. Explain why 1-WL can never distinguish two different regular graphs with the same degree, using the "identical initial neighborhood multiset" argument.
3. Connect the color-refinement update rule directly to the message-passing update rule from Part 26 — which parts of each algorithm correspond to each other?
4. Challenge: Research the specific pair of 3-regular graphs commonly used to demonstrate 1-WL's limitation (sometimes called the "CFI graphs" or similar constructions) and explain informally why they fool the test.

Limitations