Weisfeiler-Leman Graph Kernel

graph-theory kernel-methods representation-learning

Definition

Weisfeiler-Leman Graph Kernel

The Weisfeiler-Leman graph kernel is a method for computing the similarity between two graphs $G$ and $G^{\prime }$ by leveraging the structural information discovered by the Weisfeiler-Leman algorithm. It maps each graph to a vector $\mathbf{v}$ where the $i$-th component $v_i$ represents the frequency of the $i$-th unique colour (node label) identified during the refinement process.

Similarity Computation

Vectorisation: After $h$ iterations of the WL algorithm, each graph is represented by a concatenated vector of colour counts across all steps:

$${\varphi }_{WL}(G)=({\text{counts}}^{(0)},{\text{counts}}^{(1)},\dots ,{\text{counts}}^{(h)})$$

Kernel Evaluation: The similarity between two graphs is defined as the inner product of their corresponding vectors:

$$k_{WL}(G,G^{\prime })=⟨{\varphi }_{WL}(G),{\varphi }_{WL}(G^{\prime })⟩$$

This kernel provides a computationally efficient way to compare graph topologies while respecting isomorphism properties up to the expressivity limit of the WL-test.