Weisfeiler-Lehman Kernel

Weisfeiler-Lehman (WL) Kernel is a graph similarity measure based on the iterative Weisfeiler-Lehman color refinement procedure — which assigns increasingly fine-grained labels to nodes by hashing each node's current label with its sorted neighbors' labels — then compares graphs by the overlap of their label histograms, establishing the theoretical expressiveness ceiling for all standard message-passing Graph Neural Networks.

What Is the Weisfeiler-Lehman Kernel?

• Definition: The WL kernel computes graph similarity by running $H$ iterations of the WL color refinement algorithm on both graphs simultaneously and comparing the resulting label frequency vectors. At each iteration $h$: (1) each node's new label is a hash of its current label concatenated with its sorted neighbors' labels: $c_v^{(h+1)} = \text{HASH}(c_v^{(h)}, {c_u^{(h)} : u \in \mathcal{N}(v)})$; (2) the label histogram $\phi^{(h)}(G) = \text{count of each unique label in } G$ is computed; (3) the kernel value is the sum of inner products across all iterations: $K_{WL}(G_1, G_2) = \sum_{h=0}^{H} \langle \phi^{(h)}(G_1), \phi^{(h)}(G_2) \rangle$.
• Color Refinement: Initially, all nodes receive the same color (or their attribute label). After one iteration, nodes with different neighborhood structures receive different colors. After $H$ iterations, two nodes have the same color if and only if their $H$-hop neighborhoods are identical in structure and labeling. This is the 1-dimensional Weisfeiler-Lehman isomorphism test (1-WL test).
• Subtree Pattern Counting: Each WL color at iteration $h$ encodes a unique rooted subtree of depth $h$ — the color captures the exact structure of the node's $h$-hop neighborhood tree. The WL kernel therefore counts matching subtree patterns between two graphs, weighted across all depths from 0 to $H$.

Why the WL Kernel Matters

• GNN Expressiveness Ceiling: Xu et al. (GIN, 2019) proved that the most powerful standard message-passing GNN is exactly as expressive as the 1-WL test. This means: (1) no standard MPNN can distinguish graphs that the WL test cannot distinguish; (2) any distinguishable pair of graphs can be separated by GIN. The WL kernel thus defines the theoretical limit of what standard GNNs can learn.
• Failure Cases: The WL test (and therefore all standard GNNs) fails to distinguish certain graph pairs — most notably, regular graphs where every node has identical degree and identical neighborhood structure. Circular skip graphs, Cai-Fürer-Immerman gadgets, and strongly regular graphs all have identical WL colorings despite being non-isomorphic. These failure cases motivate higher-order GNN architectures (k-WL, k-FWL).
• Practical Effectiveness: Despite its theoretical limitations, the WL kernel performs remarkably well on real-world graph classification tasks — molecular datasets, protein structures, social networks. Most real graphs are not pathological regular graphs, and the subtree patterns captured by WL iterations provide highly discriminative features for practical classification.
• Higher-Order Extensions: The $k$-WL test (operating on $k$-tuples of nodes rather than individual nodes) is strictly more powerful than the 1-WL test for $k \geq 3$. This hierarchy motivates higher-order GNN architectures — $k$-GNN, Provably Powerful Graph Networks — that sacrifice computational efficiency for increased expressiveness beyond the 1-WL ceiling.

WL Refinement Process

Weisfeiler-Lehman Kernel is iterative neighborhood coloring — differentiating nodes and graphs by the structural complexity of their neighborhood trees, providing the exact theoretical yardstick against which all message-passing GNN architectures measure their expressiveness.