Weisfeiler-Leman Algorithm

The Isomorphism Question

Two graphs are isomorphic when one can be relabeled to become the other: there is a bijection between vertices that preserves adjacency and, when present, vertex or edge labels. The difficulty is that vertex names carry no structural meaning. A useful test must describe vertices in a way that survives renaming.

The one-dimensional Weisfeiler–Leman algorithm, or 1-WL, maintains a partition of the vertices into color classes. Same color means “not yet distinguished by this test.” Different colors certify different rooted local structures at the current depth.

Colors as Local Structural Summaries

At round $t+1$, vertex $v$ combines its old color with the multiset of colors on its neighbors:

1. Read every vertex's colors from round $t$; do not update in place.
2. Sort or count the neighbor colors so the signature is independent of adjacency-list order.
3. Include the vertex's own old color, ensuring refinement may split a class but never merge two old classes.
4. Assign the same new integer to identical signatures using one shared compression map.
5. Stop when no color class splits.

Worked Refinement Trace

Consider edges $A-B$, $B-C$, $C-D$, and $C-E$. All vertices begin navy. Round one separates vertices by degree. Round two notices that leaf $A$ touches the degree-two vertex $B$, while leaves $D$ and $E$ touch the degree-three vertex $C$.

How to Compare Two Graphs Correctly

Color numbers have meaning only inside the compression system that created them. Refining two graphs independently and comparing only sorted class sizes is unsafe: two graphs can have classes of the same sizes produced by different signatures.

1. Reject immediately if vertex counts or compatible input-label histograms differ.
2. Form the disjoint union of the two graphs—no cross edges—and refine both components with one shared signature-to-color map.
3. After every round, compare the color histogram in the first component with the histogram in the second.
4. If a histogram differs, return definitely non-isomorphic. If refinement stabilizes with equal histograms, return inconclusive, not “isomorphic.”

A Visual Failure Case

A six-cycle $C_6$ and two disjoint triangles $2C_3$ are plainly non-isomorphic—one graph is connected and the other is not. Yet every vertex has degree two and sees two neighbors of the same color in every round. Starting from one unlabeled color, 1-WL never splits either graph.

Soundness and Stabilization

Soundness follows by induction. An isomorphism preserves initial labels. If corresponding vertices have equal colors at round $t$, the isomorphism bijects their neighbors and therefore preserves the multiset of neighbor colors. Their next signatures—and compressed colors—remain equal. Thus an isomorphic pair can never develop different synchronized histograms.

Termination follows from refinement monotonicity. Including the old color means old classes never merge. Every non-stable round splits at least one class and increases the number of classes, which is at most $V$. The final partition is equitable: vertices in one class have the same number of neighbors in every color class.

Connection to Message-Passing GNNs

A typical message-passing layer aggregates neighbor representations with a permutation-invariant operation, then updates each vertex from its previous representation and the aggregate. That mirrors the 1-WL signature rule.

Under the standard message-passing model, such GNNs are at most as discriminative as 1-WL. With sufficiently expressive injective aggregation and update functions, architectures can match 1-WL's distinguishing power. Weaker aggregators may lose information—for example, a mean can erase multiplicity—so “bounded by 1-WL” does not mean every GNN automatically reaches the bound.

Higher-Dimensional WL

$k$-WL colors ordered $k$-tuples of vertices rather than individual vertices. Tuple relationships expose interactions that 1-WL cannot see, and increasing $k$ yields a stronger hierarchy of tests. The cost also rises sharply: there are $V^k$ tuples before refinement overhead, so higher-dimensional methods trade tractability for expressive power.

Implementation

The safest comparison implementation refines the disjoint union of the two input graphs. That guarantees equal signatures in either component receive the same color ID. The routine below returns the full refinement history for inspection and uses a three-valued comparison result: different or inconclusive.

from collections import Counter

def compress(values):
    """Equal hashable values receive equal compact integer IDs."""
    palette, result = {}, []
    for value in values:
        if value not in palette:
            palette[value] = len(palette)
        result.append(palette[value])
    return result

def wl_refine(adj, initial_labels=None, max_rounds=None):
    n = len(adj)
    labels = [0] * n if initial_labels is None else list(initial_labels)
    if len(labels) != n:
        raise ValueError("one initial label is required per vertex")

    color = compress(labels)
    history = [color[:]]
    limit = n if max_rounds is None else max_rounds

    for _ in range(limit):
        signatures = [
            (color[v], tuple(sorted(color[u] for u in adj[v])))
            for v in range(n)
        ]
        new_color = compress(signatures)
        history.append(new_color[:])

        # Because the old color is in every signature, classes only split.
        stable = len(set(new_color)) == len(set(color))
        color = new_color
        if stable:
            break

    return color, history

def wl_compare(adj_g, adj_h):
    """Return ('different', round) or ('inconclusive', stable_round)."""
    if len(adj_g) != len(adj_h):
        return "different", 0

    n = len(adj_g)
    disjoint_union = [list(neighbors) for neighbors in adj_g]
    disjoint_union += [[u + n for u in neighbors] for neighbors in adj_h]
    _, history = wl_refine(disjoint_union)

    for round_no, colors in enumerate(history):
        if Counter(colors[:n]) != Counter(colors[n:]):
            return "different", round_no
    return "inconclusive", len(history) - 1

path4 = [[1], [0, 2], [1, 3], [2]]
star4 = [[1, 2, 3], [0], [0], [0]]
cycle6 = [[1, 5], [0, 2], [1, 3], [2, 4], [3, 5], [4, 0]]
two_triangles = [[1, 2], [0, 2], [0, 1], [4, 5], [3, 5], [3, 4]]

print(wl_compare(path4, star4))            # ('different', 1)
print(wl_compare(cycle6, two_triangles))   # ('inconclusive', 1)

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

using Signature = pair<int, vector<int>>;

vector<int> refine(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> color(n, 0);

    for (int r = 0; r < n; r++) {
        vector<Signature> 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<Signature, int> palette;
        vector<int> newColor(n);
        for (int v = 0; v < n; v++) {
            if (!palette.count(signatures[v]))
                palette[signatures[v]] = palette.size();
            newColor[v] = palette[signatures[v]];
        }

        int oldClasses = set<int>(color.begin(), color.end()).size();
        int newClasses = set<int>(newColor.begin(), newColor.end()).size();
        color = move(newColor);
        if (oldClasses == newClasses) break;
    }
    return color;
}

int main() {
    vector<vector<int>> adj = {{1}, {0,2}, {1,3}, {2}};
    vector<int> colors = refine(adj);
    for (int c : colors) cout << c << " ";
}

import java.util.*;

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

        for (int r = 0; r < n; r++) {
            List<List<Integer>> 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);
                List<Integer> signature = new ArrayList<>();
                signature.add(color[v]);
                signature.add(-1); // separator; color IDs are nonnegative
                signature.addAll(neighborColors);
                signatures.add(signature);
            }

            Map<List<Integer>, Integer> palette = new HashMap<>();
            int[] newColor = new int[n];
            for (int v = 0; v < n; v++) {
                if (!palette.containsKey(signatures.get(v)))
                    palette.put(signatures.get(v), palette.size());
                newColor[v] = palette.get(signatures.get(v));
            }

            long oldClasses = Arrays.stream(color).distinct().count();
            long newClasses = Arrays.stream(newColor).distinct().count();
            color = newColor;
            if (oldClasses == newClasses) break;
        }
        return color;
    }

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

Complexity and Alternatives

There are at most $V-1$ strict splitting rounds. In the straightforward code above, sorting neighbor colors costs $\sum_v O(d(v)\log d(v))$ per round, bounded by $O(E\log V)$. Including signature construction and compression gives the conservative bound

That bound describes the readable implementation, not the best possible color-refinement engine. Counting small integer colors and refining partitions with worklists avoids repeatedly sorting every neighborhood; established partition-refinement implementations can compute the stable coloring in $O((V+E)\log V)$ time.

Where 1-WL Is Useful

• Isomorphism prefilter: discard pairs proved different before invoking an exact algorithm.
• Graph indexing: use refinement-derived summaries as inexpensive search keys, while remembering they are not unique canonical identifiers.
• Feature engineering: count refined labels to summarize recurring local structures in graph classification pipelines.
• Model diagnostics: build controlled graph pairs that expose what a GNN's aggregation rule preserves or loses.

Common Pitfalls and a Reliable Checklist

Exercises

1. Trace: reproduce the three rounds in the first diagram, writing the exact signature of each vertex before compression.
2. Failure case: run the Python comparison on $C_6$ and $2C_3$. Explain why every vertex receives the same signature forever even though connectedness differs.
3. Relabeling: randomly permute the indices of a graph. Verify that synchronized histograms stay equal even if the numeric color IDs or vertex order look different.
4. Directed extension: replace one neighbor multiset with separate incoming- and outgoing-color multisets. Which orientation patterns become distinguishable?
5. GNN connection: identify the 1-WL counterparts of AGG and UPDATE. Give an example in which mean aggregation loses multiplicity information.

Historical Note and Takeaway

The method stems from work by Boris Weisfeiler and Andrei Leman in the late 1960s. Decades later, color refinement supplied the right abstraction for characterizing the expressive limits of neighborhood-aggregation graph neural networks.