Weisfeiler-Leman Algorithm

graph-theory representation-learning

Definition

Weisfeiler-Leman Algorithm

The Weisfeiler-Leman algorithm is an iterative procedure used to test for graph isomorphism and generate structural embeddings. Formally, given a graph $G=(V,E)$ with initial vertex colours $c^{(0)}(v)$, the algorithm update rule for iteration $k+1$ is:

$$c^{(k+1)}(v)=\text{hash}\left(c^{(k)}(v),\{\{c^{(k)}(u):u\in \mathcal{N}(v)\}\}\right)$$

where $\mathcal{N}(v)$ is the set of neighbours of $v$, and $\{\{\dots \}\}$ denotes a multiset. The process terminates when the partition of vertices induced by the colours remains stable.

Applications in Machine Learning

Expressive Power of GNNs: The message-passing mechanism in standard Graph Neural Networks is a differentiable generalisation of the WL-algorithm. The WL-test provides a theoretical upper bound on the ability of GNNs to distinguish non-isomorphic graph structures.

Graph Kernels: The WL-kernel measures similarity between graphs by comparing the distribution of vertex colours across multiple refinement iterations.

Algorithm Properties

Incompleteness: The WL-algorithm is a necessary but not sufficient test for graph isomorphism. Certain pairs of non-isomorphic graphs (e.g., strongly regular graphs) cannot be distinguished by the 1-WL test.

Efficiency: The procedure is highly scalable, requiring only linear time complexity per iteration with respect to the number of edges.

Example

Simple Example

Consider a path graph $G=(V,E)$ with $V=\{1,2,3,4\}$.

Step 0 (Initialisation): All vertices are assigned the same initial colour $c^{(0)}(v)=1$.

Step 1 (First Iteration): Colours are updated based on neighbour multisets. Terminal nodes (1, 4) receive colour 2, while internal nodes (2, 3) receive colour 3.

Step 2 (Convergence): The algorithm checks if the partition changes. Since nodes with colour 2 still see the same neighbour colour distribution (one 3), and nodes with colour 3 see (one 2, one 3), the partition into $\{1,4\}$ and $\{2,3\}$ is stable.

Complex Example

Consider the “House Graph” which demonstrates how the algorithm refines colours beyond just vertex degrees.

Step 0 (Initialisation): All vertices start with the same colour.

Step 1 (First Iteration): Nodes are coloured by degree. Vertices $\{v_1,v_2,v_5\}$ have degree 2 (colour 2), while $\{v_3,v_4\}$ have degree 3 (colour 3).

Step 2 (Second Iteration): Nodes now look at the “types” of neighbours they have from the previous step:

• $v_1$ and $v_2$: Each has one neighbour of colour 2 and one of colour 3.
• $v_5$: Both of its neighbours are colour 3.

Because $v_5$ sees a different “neighbourhood” than $v_1$ and $v_2$, it realised it is structurally different and gets its own unique colour (6).

Step 3 (Convergence): The partition remains stable as $\{v_1,v_2\},\{v_3,v_4\},\{v_5\}$. No further refinement is possible.