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)} = ext{HASH}(c_v^{(h)}, {c_u^{(h)} : u in mathcal{N}(v)})$; (2) the label histogram $phi^{(h)}(G) = ext{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)
angle$.
- **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**
| Iteration | Node Label Represents | Distinguishing Power |
|-----------|----------------------|---------------------|
| **$h = 0$** | Node attribute (or constant) | Same attribute = same color |
| **$h = 1$** | Attribute + immediate neighbor attributes | Different 1-hop neighborhoods → different colors |
| **$h = 2$** | 2-hop subtree structure | Different 2-hop trees → different colors |
| **$h = H$** | $H$-hop subtree structure | Full $H$-hop neighborhood encoding |
**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.