The Weisfeiler-Leman Test: Theoretical Expressiveness Bound for GNNs

The Weisfeiler-Leman (WL) test is a graph isomorphism algorithm that defines the theoretical upper bound on what standard message passing graph neural networks can distinguish. Proposed in 1968, the WL test iteratively refines node colors based on neighborhood structure. In 2019, Xu et al. proved that the computational process of standard message passing GNNs is exactly equivalent to the 1-WL color refinement procedure. Any two graphs that 1-WL cannot distinguish will receive identical representations from any standard message passing GNN.

Why it matters for enterprise data

The WL bound tells you which structural patterns your GNN can capture and which it cannot. For enterprise relational databases, this determines whether the model can distinguish different types of network patterns: fraud rings vs. star patterns, tightly clustered communities vs. loosely connected networks, supply chain bottlenecks vs. redundant supplier networks.

The practical impact varies by data type. Enterprise relational graphs are typically heterogeneous (customers, orders, products have different feature types), which makes most real-world structures distinguishable by 1-WL. The limitation is most relevant for homogeneous graphs where nodes have identical feature distributions.

How the 1-WL test works

The 1-WL test (also called color refinement) follows these steps:

1. Initialize: Assign all nodes the same color (or use node features as initial colors)
2. Collect: For each node, gather the multiset of its neighbors' colors
3. Hash: Map (own color, neighbor multiset) to a new color via an injective hash function
4. Repeat: Continue until colors stabilize (no node changes color)
5. Compare: If two graphs have different color histograms, they are non-isomorphic

def wl_color_refinement(adj_list, num_iterations=5):
    """1-WL color refinement algorithm."""
    n = len(adj_list)
    colors = [0] * n  # all nodes start with same color

    for iteration in range(num_iterations):
        new_colors = {}
        color_map = {}
        counter = 0

        for node in range(n):
            # Collect neighbor colors as a sorted tuple (multiset)
            neighbor_colors = tuple(sorted(colors[j] for j in adj_list[node]))
            key = (colors[node], neighbor_colors)

            if key not in color_map:
                color_map[key] = counter
                counter += 1

            new_colors[node] = color_map[key]

        colors = [new_colors[i] for i in range(n)]

    return colors

# This is EXACTLY what message passing GNNs do:
# Step 1: aggregate neighbor features (= collect neighbor colors)
# Step 2: combine with own features (= hash own + neighbor colors)
# Step 3: transform through neural network (= injective mapping to new color)

The GNN connection: why GINConv matches 1-WL

The key insight from Xu et al. (GIN paper, 2019): for a message passing GNN to match 1-WL expressiveness, two conditions must hold:

• Injective aggregation: The aggregation function must distinguish different multisets of neighbor features. Sum is injective on multisets of bounded features. Mean and max are not (they map different multisets to the same value).
• Injective update: The update function must distinguish different (self, aggregated) pairs. An MLP with sufficient width is a universal injective function. A single linear layer is not.

GINConv satisfies both: it uses sum aggregation and an MLP update. GCNConv uses mean-like aggregation and a linear update, making it strictly less expressive.

Concrete example: what 1-WL cannot distinguish

Consider two graphs, each with 6 nodes where every node has degree 2:

• Graph A: A single 6-cycle (1-2-3-4-5-6-1)
• Graph B: Two disjoint triangles (1-2-3-1 and 4-5-6-4)

After WL color refinement with uniform initial colors: every node has 2 neighbors with the same color. The hash (own color, {color, color}) is identical for all nodes in both graphs. The color histograms match. 1-WL declares them indistinguishable, and so does any standard message passing GNN.

Going beyond 1-WL

• Positional encodings: Laplacian eigenvectors give each node a unique position-based feature, breaking the symmetry that fools 1-WL. Equivalent to giving each WL node a unique initial color.
• Structural encodings: Encoding local topology (triangle counts, cycle memberships) as additional features lets the GNN see structural patterns that 1-WL misses.
• Higher-order GNNs (k-WL): Operate on k-tuples of nodes. 2-WL distinguishes the 6-cycle from two triangles. But complexity is O(n^k), impractical for large graphs.
• Graph transformers: Global attention with positional encodings provides beyond-1-WL expressiveness with better scalability than k-WL GNNs.

Limitations and what comes next

1. 1-WL is a worst-case bound: Most real-world graphs are easily distinguished by 1-WL. The problematic cases (regular graphs with uniform features) are rare in enterprise data.
2. Higher-order WL is expensive: k-WL GNNs have O(n^k) complexity. For enterprise graphs with millions of nodes, even 2-WL is prohibitive.
3. Expressiveness vs. generalization: Maximum expressiveness (GINConv) does not always yield the best performance. The inductive bias of less expressive layers (GCNConv) can improve generalization on tasks where the 1-WL limitation is irrelevant.