🎓How I Study AIHISA
📖Read
📄Papers📰Blogs🎬Courses
💡Learn
🛤️Paths📚Topics💡Concepts🎴Shorts
🎯Practice
⏱️Coach🧩Problems🧠Thinking🎯Prompts🧠Review
SearchSettings
How I Study AI - Learn AI Papers & Lectures the Easy Way
📚TheoryAdvanced

Weisfeiler-Leman Hierarchy

Key Points

  • •
    The Weisfeiler–Leman (WL) hierarchy is a family of color-refinement procedures that iteratively color vertices (or k-tuples of vertices) to capture graph structure for isomorphism testing.
  • •
    1-WL (color refinement) updates each vertex color from the multiset of its neighbors’ colors and stabilizes in at most n − 1 rounds.
  • •
    k-WL generalizes this by coloring ordered k-tuples and looking at how the color changes when one coordinate is replaced by every vertex, which greatly increases distinguishing power but also costs nk memory.
  • •
    Two graphs that end with the same WL color histograms are indistinguishable by that k-WL level, but they may still be non-isomorphic.
  • •
    1-WL runs in roughly O(ℓ (n + m) log n) time and O(n + m) space, where ℓ is the number of refinement rounds until stabilization.
  • •
    k-WL for k≥2 typically costs O(ℓ k nk+1) time and O(nk) space, so it is only practical for small k and small graphs.
  • •
    WL colors are isomorphism invariants and are widely used as fast filters in graph isomorphism solvers and as features in machine learning on graphs.
  • •
    There are known counterexamples (e.g., Cai–Fürer–Immerman graphs) where even high-dimensional WL fails, so WL is powerful but not complete.

Prerequisites

  • →Graphs and adjacency representations — WL operates on graphs; you must understand vertices, edges, neighborhoods, and adjacency lists/matrices.
  • →Hashing and maps — WL uses signatures mapped to integer colors; efficient and deterministic hashing is essential.
  • →Time and space complexity — k-WL costs grow as n^k; understanding asymptotics guides feasible choices of k.
  • →Partitions and equivalence relations — 1-WL produces equitable partitions; reasoning about refinement and fixed points uses these ideas.
  • →Basic finite model theory (optional) — WL connects to counting logic; this deepens theoretical understanding but is not required for coding.

Detailed Explanation

Tap terms for definitions

01Overview

The Weisfeiler–Leman (WL) hierarchy is a family of increasingly powerful algorithms for distinguishing non-isomorphic graphs. The simplest member, 1-WL—also called color refinement—assigns a color (an integer label) to each vertex and repeatedly refines these colors by summarizing the multiset of colors of each vertex’s neighbors. This process continues until the coloring stabilizes (no change occurs). If two graphs stabilize to different color histograms, they are certainly non-isomorphic; if their histograms match, they are indistinguishable by 1-WL (but not guaranteed to be isomorphic). The k-dimensional version, k-WL, operates on ordered k-tuples of vertices. It refines the color of each tuple using the colors of all tuples obtained by replacing one coordinate with every vertex in the graph. This greatly increases expressiveness and can distinguish many graphs that 1-WL cannot. However, the computational cost grows steeply with k because there are n^k tuples. WL methods are central in theory (connections to finite model theory and counting logic) and practice (fast graph isomorphism heuristics, graph kernels, and features for graph neural networks). They provide a tunable trade-off between power and cost: higher k gives more distinguishing power but quickly becomes expensive.

02Intuition & Analogies

Imagine every vertex is a house in a city, initially painted the same color. In the first round, each house repaints itself based on the colors of the houses on its street—perhaps by writing down, in sorted order, the colors it sees and then hashing that list to a new paint color. Houses on streets with the same patterns end up with the same new color. In the next round, they do this again, now using the new colors they and their neighbors have. Over time, neighborhoods that are structurally different (e.g., different degree patterns or arrangements) settle on different colors. When no house changes color anymore, the process stabilizes: that’s 1-WL. If two cities end with different final color histograms, they clearly are not the same; but if the histograms match, they could still be different cities that happen to fool this particular coloring rule. Now zoom out to k-WL: instead of painting individual houses, we paint small ordered teams of k houses. To refine a team’s color, we perform a thought experiment: for each position in the team, we try replacing that house with every other house in the city and look at the resulting teams’ colors. This is like stress-testing how the team relates to the city from each member’s perspective. Collecting all these colors yields a rich signature that better captures the city’s layout. Increasing k is like upgrading from a blurry snapshot (k = 1) to a higher-resolution camera (k ≥ 2). You see more structure, but each photo takes far more storage and processing. Eventually, you hit practical limits: even though the camera could, in principle, resolve most differences, the cost becomes prohibitive. That’s the key trade-off behind the WL hierarchy: more detail versus more computation.

03Formal Definition

Let G = (V, E) be a finite graph with n = ∣V∣. For 1-WL, we maintain a coloring c(t): V → N at round t. Given c(t), define the next coloring by c(t+1)(v) = \operatorname{hash}\big( c(t)(v), \ \multisetc(t)(u)∣u∈N(v) \big), where N(v) is the neighborhood of v and the multiset records neighbor colors with multiplicity. Colors are then canonically relabeled to a contiguous range to avoid accidental ties. Refinement continues until stabilization, i.e., c^{(t+1)} = c^{(t)}. Two graphs G and H are 1-WL equivalent if the multisets of colors over V(G) and V(H) match after stabilization. For k-WL, we color ordered k-tuples of vertices. Let Vk be the set of k-tuples and let s(t): Vk → N. The refinement is s(t+1)(vˉ) = \operatorname{hash}\Big( s(t)(vˉ), \ \big\{\!\big\{\ (i,\ s(t)(vˉ[i ← w])) ∣ i ∈ [k],\ w ∈ V \ \big\}\!\big\} \Big), where vˉ[i ← w] denotes the tuple obtained by replacing the i-th coordinate of vˉ with w, and [k] = \{1,…,k\}. Stabilization and equivalence are defined analogously by comparing the color multisets over Vk. The hierarchy is monotone: if two graphs are distinguished by k-WL, they are also distinguished by (k+1)-WL, but not conversely.

04When to Use

Use 1-WL as a fast, memory-light prefilter in graph isomorphism pipelines: it quickly separates many non-isomorphic graphs by degree and local neighborhood patterns. It is also a strong baseline feature for tasks like graph classification or clustering: the stabilized color histogram (or per-vertex colors) provides a structural fingerprint. When initial vertex/edge labels exist (e.g., atom types in molecules), include them in the initial coloring to respect domain-specific information. Use k-WL with small k (typically k = 2 or 3) when 1-WL is too weak—for example, distinguishing many regular graphs that 1-WL cannot tell apart, or when richer features are required for learning tasks. 2-WL often offers a substantial power jump at acceptable cost for small and medium graphs (n in the low thousands for well-engineered implementations, often much less for naive ones). Avoid large k unless graphs are tiny: time and memory blow up as n^k. Do not rely on WL as a complete isomorphism test: there are families of non-isomorphic graphs (e.g., Cai–Fürer–Immerman) that defeat every fixed k. Instead, combine WL with backtracking, individualization-refinement, or canonical labeling for exact isomorphism. In ML settings, WL features (and WL-inspired GNNs) are strong but have expressivity limits matching their WL level.

⚠️Common Mistakes

• Non-deterministic hashing: Using unordered maps without canonical relabeling can assign different color IDs across runs or across graphs, breaking cross-graph comparisons. Fix by rebuilding color IDs each round using a consistent, order-independent mapping from signatures to consecutive integers, or by sharing the same palette across both graphs in each round. • Mixing labels incorrectly: If your input has initial labels (e.g., types), forgetting to include them in the initial coloring (or in signatures) loses crucial information; conversely, adding degree into the initial color changes the formal 1-WL variant. Be explicit about what your initial colors encode. • Early-stopping errors: Declaring graphs indistinguishable because current round histograms match, without running to stabilization, can yield false conclusions. Always iterate until no color changes occur in either graph (or until a mismatch appears). • Memory blow-ups in k-WL: Storing explicit signatures as vectors of length k·n per tuple is straightforward but quickly becomes infeasible. Use compressed hashing or counting and keep k small; profile memory. • Ignoring graph direction/multigraphs: WL formulas and code must be adapted for directed graphs, edge labels, or multiedges. Ensure signatures reflect the graph model you intend. • Comparing raw color IDs across separate runs: Even with deterministic mapping, color integers are arbitrary labels. For equivalence, compare frequency histograms (or distributions) of colors, not the exact integers, unless colors were assigned using a shared palette in the same round.

Key Formulas

1-WL Update

c(t+1)(v)=hash(c(t)(v), {{ c(t)(u) : u∈N(v) }})

Explanation: The next color of vertex v is a function of its current color and the multiset of its neighbors’ current colors. The multiset keeps multiplicities, so repeated neighbor colors matter.

Stabilization Condition

c(t+1)=c(t)

Explanation: The process stops when applying the update rule yields the same coloring as before. At this fixed point, the coloring is equitable.

k-WL Update

s(t+1)(vˉ)=hash(s(t)(vˉ), {{ (i,s(t)(vˉ[i←w])) : i∈[k], w∈V }})

Explanation: For each k-tuple, we look at all tuples formed by replacing one coordinate by every vertex and aggregate their colors. This captures richer relational structure than 1-WL.

Number of k-Tuples

∣Vk∣=nk

Explanation: There are n choices for each position in a k-tuple, so the space of tuples grows exponentially with k. This drives the memory and time cost of k-WL.

1-WL Complexity

T1-WL​(n,m)=O(ℓ(n+m)logn)

Explanation: Each round processes all vertices and incident edges and sorts or hashes neighbor-color multisets. The factor ℓ is the number of rounds until stabilization (at most n − 1, usually much smaller).

k-WL Complexity

Tk-WL​(n,k)=O(ℓknk+1),Sk-WL​(n,k)=O(nk)

Explanation: For each of nk tuples, we examine k replacement positions and n replacements, leading to k nk+1 operations per round. We store one color per tuple, so memory is nk.

Round Bound

t∗≤n−1

Explanation: 1-WL refines a partition of V and can strictly increase the number of color classes at most n − 1 times. Thus stabilization occurs within n − 1 rounds.

1-WL Indistinguishability Test

\multisetc(∗)(v)∣v∈V(G)=\multisetc(∗)(v)∣v∈V(H) ⇒ G≡1-WL​H

Explanation: If the final color histograms match, the graphs are indistinguishable by 1-WL. This is necessary for isomorphism but not sufficient.

Complexity Analysis

For 1-WL, each round computes a signature per vertex consisting of its previous color and the multiset of neighbor colors. Using sorting of neighbor color lists, the per-round time is O(n + m + Σ_v deg(v) log deg(v)) = O((n + m) log Δ) in the worst case, where Δ is the maximum degree. With a global sort by color ID or bucket counting, this is commonly summarized as O((n + m) log n) per round. Hash-based aggregation with careful stable relabeling often yields near-linear expected time per round. The number of rounds to stabilization, ℓ, is at most n − 1 but is typically small (often O(log n) or even constant on many inputs). Space is O(n + m) for the graph plus O(n) for colors. For k-WL, there are nk tuples to color. In the naive implementation, each round and each tuple inspects k positions and, for each position, iterates over all n replacements, for O(k n) work per tuple. The total per-round time is therefore O(k nk+1), and space is O(nk) for storing tuple colors (plus overhead for maps). As k grows, these costs quickly become prohibitive; even k=3 can be heavy past a few hundred vertices without specialized optimizations (e.g., sparse techniques, hashing compression, or avoiding explicit storage of all tuples). When comparing two graphs, using a shared signature-to-color mapping within each round ensures consistent color IDs and allows early rejection if histograms diverge at any round. In all cases, WL provides isomorphism invariants: differing WL histograms prove non-isomorphism immediately, while matching histograms only indicate indistinguishability at that WL level.

Code Examples

1-WL (Color Refinement) for a Single Graph
1#include <bits/stdc++.h>
2using namespace std;
3
4// Hash for vector<int> to use as a key in unordered_map
5struct VecHash {
6    size_t operator()(const vector<int>& v) const noexcept {
7        // 64-bit splitmix-like hash combine
8        uint64_t h = 1469598103934665603ull; // FNV offset
9        for (int x : v) {
10            uint64_t y = static_cast<uint64_t>(x) + 0x9e3779b97f4a7c15ull;
11            h ^= y;
12            h *= 1099511628211ull; // FNV prime
13        }
14        return static_cast<size_t>(h);
15    }
16};
17
18// Perform 1-WL color refinement until stabilization.
19// adj: undirected adjacency list (0..n-1)
20// init_colors: optional initial colors; if empty, all zeros.
21vector<int> oneWL_color_refinement(const vector<vector<int>>& adj, const vector<int>& init_colors = {}) {
22    int n = (int)adj.size();
23    vector<int> color(n, 0);
24    if (!init_colors.empty()) color = init_colors;
25    // Optionally include degree in the first iteration by seeding with (label, degree)
26    // to accelerate convergence while preserving correctness for labeled graphs.
27
28    vector<int> new_color(n, 0);
29
30    while (true) {
31        // Build signatures for all vertices: (old_color, sorted multiset of neighbor colors)
32        vector<vector<int>> signatures(n);
33        signatures.reserve(n);
34        for (int v = 0; v < n; ++v) {
35            vector<int> sig;
36            sig.push_back(color[v]);
37            // Collect neighbor colors
38            sig.reserve(1 + (int)adj[v].size());
39            for (int u : adj[v]) sig.push_back(color[u]);
40            sort(sig.begin() + 1, sig.end()); // sort only neighbor colors
41            signatures[v] = move(sig);
42        }
43        // Canonically relabel signatures to consecutive colors
44        unordered_map<vector<int>, int, VecHash> id;
45        id.reserve(n * 2);
46        int next_id = 0;
47        for (int v = 0; v < n; ++v) {
48            auto it = id.find(signatures[v]);
49            if (it == id.end()) {
50                id.emplace(signatures[v], next_id);
51                new_color[v] = next_id++;
52            } else {
53                new_color[v] = it->second;
54            }
55        }
56        if (new_color == color) break; // stabilized
57        color.swap(new_color);
58    }
59    return color;
60}
61
62int main() {
63    ios::sync_with_stdio(false);
64    cin.tie(nullptr);
65
66    // Example: Two triangles connected by a bridge (6 vertices)
67    int n = 6;
68    vector<vector<int>> adj(n);
69    auto add_edge = [&](int u, int v){ adj[u].push_back(v); adj[v].push_back(u); };
70
71    add_edge(0,1); add_edge(1,2); add_edge(2,0); // triangle 0-1-2
72    add_edge(3,4); add_edge(4,5); add_edge(5,3); // triangle 3-4-5
73    add_edge(2,3); // bridge
74
75    for (int v = 0; v < n; ++v) sort(adj[v].begin(), adj[v].end());
76
77    vector<int> colors = oneWL_color_refinement(adj);
78
79    cout << "Final 1-WL colors:\n";
80    for (int v = 0; v < n; ++v) {
81        cout << "v=" << v << " color=" << colors[v] << "\n";
82    }
83    return 0;
84}
85

This program implements 1-WL (color refinement). Each round forms a vertex signature comprising its current color and the sorted multiset of neighbor colors. Signatures are mapped to consecutive integers to produce new colors. The process repeats until no vertex changes color. The output colors partition vertices into classes with identical local structure as seen by 1-WL.

Time: O(ℓ · ((n + m) + Σ_v deg(v) log deg(v))) ≈ O(ℓ (n + m) log n)Space: O(n + m) for the graph plus O(n) for colors and signatures per round
Comparing Two Graphs with Shared-Palette 1-WL
1#include <bits/stdc++.h>
2using namespace std;
3
4struct VecHash { size_t operator()(const vector<int>& v) const noexcept {
5    uint64_t h = 1469598103934665603ull; for (int x : v){ uint64_t y = (uint64_t)x + 0x9e3779b97f4a7c15ull; h ^= y; h *= 1099511628211ull; } return (size_t)h; } };
6
7// One round of 1-WL on two graphs using a shared signature->color palette.
8static void one_round_shared(const vector<vector<int>>& A, const vector<int>& cA,
9                             const vector<vector<int>>& B, const vector<int>& cB,
10                             vector<int>& nA, vector<int>& nB) {
11    int n = (int)A.size();
12    // Build signatures for both graphs
13    vector<vector<int>> sigA(n), sigB(n);
14    for (int v = 0; v < n; ++v) {
15        vector<int> s; s.push_back(cA[v]);
16        for (int u : A[v]) s.push_back(cA[u]);
17        sort(s.begin() + 1, s.end());
18        sigA[v] = move(s);
19    }
20    for (int v = 0; v < n; ++v) {
21        vector<int> s; s.push_back(cB[v]);
22        for (int u : B[v]) s.push_back(cB[u]);
23        sort(s.begin() + 1, s.end());
24        sigB[v] = move(s);
25    }
26    // Shared palette: same signature gets the same ID across both graphs in this round
27    unordered_map<vector<int>, int, VecHash> id; id.reserve(2*n);
28    int next_id = 0;
29    for (int v = 0; v < n; ++v) {
30        auto it = id.find(sigA[v]);
31        if (it == id.end()) { id.emplace(sigA[v], next_id); nA[v] = next_id++; }
32        else { nA[v] = it->second; }
33    }
34    for (int v = 0; v < n; ++v) {
35        auto it = id.find(sigB[v]);
36        if (it == id.end()) { id.emplace(sigB[v], next_id); nB[v] = next_id++; }
37        else { nB[v] = it->second; }
38    }
39}
40
41// Return true if graphs are indistinguishable by 1-WL (same stabilized color histogram)
42bool indistinguishable_1WL(const vector<vector<int>>& A, const vector<vector<int>>& B,
43                           const vector<int>& initA = {}, const vector<int>& initB = {}) {
44    int n = (int)A.size(); if ((int)B.size() != n) return false;
45    vector<int> cA(n,0), cB(n,0); if (!initA.empty()) cA = initA; if (!initB.empty()) cB = initB;
46    vector<int> nA(n,0), nB(n,0);
47    while (true) {
48        one_round_shared(A, cA, B, cB, nA, nB);
49        // Early rejection: compare histograms this round
50        unordered_map<int,int> hA, hB; hA.reserve(n); hB.reserve(n);
51        for (int x : nA) ++hA[x]; for (int x : nB) ++hB[x];
52        if (hA != hB) return false;
53        if (nA == cA && nB == cB) return true; // stabilized with matching histograms
54        cA.swap(nA); cB.swap(nB);
55    }
56}
57
58int main(){
59    ios::sync_with_stdio(false);
60    cin.tie(nullptr);
61
62    // Build a graph and a permuted isomorphic copy
63    int n = 6;
64    vector<vector<int>> G(n), H(n);
65    auto add = [&](vector<vector<int>>& adj, int u, int v){ adj[u].push_back(v); adj[v].push_back(u); };
66
67    // G: square 0-1-2-3-0 with diagonals 0-2 and 1-3 (K4), plus two isolated vertices 4,5 connected as edge 4-5
68    add(G,0,1); add(G,1,2); add(G,2,3); add(G,3,0); add(G,0,2); add(G,1,3); add(G,4,5);
69    for (int i=0;i<n;++i) sort(G[i].begin(), G[i].end());
70
71    // Permute vertices: p = [2,3,0,1,5,4]
72    vector<int> p = {2,3,0,1,5,4};
73    vector<int> inv(n); for (int i=0;i<n;++i) inv[p[i]] = i;
74    H.assign(n, {});
75    for (int u=0;u<n;++u) for (int v: G[u]) if (u < v) { add(H, p[u], p[v]); }
76    for (int i=0;i<n;++i) sort(H[i].begin(), H[i].end());
77
78    bool same = indistinguishable_1WL(G, H);
79    cout << (same ? "Indistinguishable by 1-WL (likely isomorphic).\n" : "Distinguished by 1-WL (non-isomorphic).\n");
80
81    return 0;
82}
83

This code refines two graphs in lockstep using a shared signature-to-color map each round. Sharing the palette guarantees that identical signatures in either graph receive the same color ID, making cross-graph histogram comparisons meaningful. The function returns true if, after stabilization, both graphs have identical color histograms (i.e., they are indistinguishable by 1-WL).

Time: O(ℓ (n + m) log n) expected, for both graphs togetherSpace: O(n + m) for both graphs plus O(n) for colors and the shared palette per round
Educational k-WL (generic, small k) on Unlabeled, Undirected Graphs
1#include <bits/stdc++.h>
2using namespace std;
3
4struct VecHash { size_t operator()(const vector<int>& v) const noexcept {
5    uint64_t h = 1469598103934665603ull; for (int x : v){ uint64_t y = (uint64_t)x + 0x9e3779b97f4a7c15ull; h ^= y; h *= 1099511628211ull; } return (size_t)h; } };
6
7// Convert between tuple index and vector<int> tuple under base-n encoding
8static size_t tuple_to_index(const vector<int>& t, int n){ size_t idx=0; for (int x: t){ idx = idx * (size_t)n + (size_t)x; } return idx; }
9static vector<int> index_to_tuple(size_t idx, int n, int k){ vector<int> t(k); for (int i=k-1;i>=0;--i){ t[i] = (int)(idx % (size_t)n); idx /= (size_t)n; } return t; }
10
11// Build initial color of a k-tuple from equality pattern and pairwise adjacency among tuple entries
12static vector<int> build_initial_colors_kWL(const vector<vector<int>>& adj, int k){
13    int n = (int)adj.size();
14    vector<vector<char>> A(n, vector<char>(n, 0));
15    for (int u=0; u<n; ++u) for (int v: adj[u]) A[u][v] = 1;
16    size_t NK = 1; for (int i=0;i<k;++i) NK *= (size_t)n;
17    vector<int> color(NK, 0);
18    unordered_map<vector<int>, int, VecHash> id; id.reserve(NK/2 + 1);
19    int next_id = 0;
20    vector<int> key; key.reserve(k + k*k);
21    for (size_t idx=0; idx<NK; ++idx){
22        vector<int> t = index_to_tuple(idx, n, k);
23        key.clear();
24        // equality pattern: for each pair (i,j), record 1 if t[i]==t[j], else 0
25        for (int i=0;i<k;++i) for (int j=0;j<k;++j) key.push_back(t[i]==t[j]);
26        // adjacency pattern among tuple entries (undirected; include both (i,j) entries for simplicity)
27        for (int i=0;i<k;++i) for (int j=0;j<k;++j) key.push_back(A[t[i]][t[j]]);
28        auto it = id.find(key);
29        if (it == id.end()) { id.emplace(key, next_id); color[idx] = next_id++; }
30        else { color[idx] = it->second; }
31    }
32    return color;
33}
34
35// One educational (naive) round of k-WL: builds huge deterministic signatures
36static vector<int> kWL_round(const vector<vector<int>>& adj, const vector<int>& prev, int k){
37    int n = (int)adj.size();
38    size_t NK = prev.size();
39    unordered_map<vector<int>, int, VecHash> id; id.reserve(NK/2 + 1);
40    vector<int> next(prev.size());
41    vector<int> key; key.reserve(1 + k * n);
42
43    for (size_t idx=0; idx<NK; ++idx){
44        vector<int> t = index_to_tuple(idx, n, k);
45        key.clear();
46        key.push_back(prev[idx]); // include old color
47        // For each position i, append colors of tuples with t[i] replaced by all w in V in fixed order (0..n-1)
48        for (int i=0;i<k;++i){
49            for (int w=0; w<n; ++w){
50                int old = t[i];
51                t[i] = w;
52                size_t jdx = tuple_to_index(t, n);
53                key.push_back(prev[jdx]);
54                t[i] = old; // restore
55            }
56        }
57        auto it = id.find(key);
58        if (it == id.end()) { int nid = (int)id.size(); id.emplace(key, nid); next[idx] = nid; }
59        else { next[idx] = it->second; }
60    }
61    return next;
62}
63
64// Run k-WL until stabilization. WARNING: Only feasible for very small n and k.
65vector<int> kWL_refine(const vector<vector<int>>& adj, int k, int max_rounds = 100) {
66    int n = (int)adj.size();
67    // Initial colors from equality + adjacency pattern
68    vector<int> color = build_initial_colors_kWL(adj, k);
69    for (int round=0; round<max_rounds; ++round){
70        vector<int> next = kWL_round(adj, color, k);
71        if (next == color) break; // stabilized
72        color.swap(next);
73    }
74    return color;
75}
76
77int main(){
78    ios::sync_with_stdio(false);
79    cin.tie(nullptr);
80
81    // Tiny example: 4-cycle C4
82    int n = 4; vector<vector<int>> adj(n);
83    auto add=[&](int u,int v){ adj[u].push_back(v); adj[v].push_back(u); };
84    add(0,1); add(1,2); add(2,3); add(3,0);
85    for (int i=0;i<n;++i) sort(adj[i].begin(), adj[i].end());
86
87    int k = 2; // 2-WL on ordered pairs
88    vector<int> colors2 = kWL_refine(adj, k);
89    cout << "Number of distinct 2-WL colors on V^2: "
90         << unordered_set<int>(colors2.begin(), colors2.end()).size() << "\n";
91
92    return 0;
93}
94

This educational 2/3/…-WL implementation explicitly builds deterministic signatures by listing, for each tuple, the colors of all tuples obtained by replacing one coordinate with every vertex in order. It also initializes tuple colors using equality and pairwise adjacency among tuple coordinates. The code is correct but extremely costly: it is meant for tiny graphs and for learning purposes.

Time: Per round O(k · n^{k+1}); total O(ℓ · k · n^{k+1})Space: O(n^k) colors plus signature-map overhead
#weisfeiler-leman#color refinement#graph isomorphism#k-wl#equitable partition#graph hashing#tuple coloring#counting logic#graph kernel#graph neural networks#partition refinement#cai-furer-immerman#isomorphism invariant#wl test#2-wl