Weisfeiler-Leman Algorithm

Definition

1-dimensional Weisfeiler–Leman Algorithm

The 1-dimensional Weisfeiler–Leman algorithm (1-WL), also called colour refinement, iteratively refines a colouring of the vertices of a graph according to the colours in each vertex’s neighbourhood.

Given a colouring $c_t:V\to C_t$, define the signature

$$s_t(v)=\left(c_t(v),\{\{c_t(u):u\in N_G(v)\}\}\right).$$

The next colouring assigns equal colours exactly to equal signatures:

$$c_{t+1}(v)=c_{t+1}(w)⟺s_t(v)=s_t(w).$$

Thus, each round may split existing colour classes but never merges them. For an unlabelled graph, $c_0$ is constant. The algorithm stops when the partition induced by the colours no longer changes.

Example

Refining a path

Let $P_5$ be the path $1-2-3-4-5$. Starting from one colour class, the first round separates the endpoints by degree. The second separates the centre from the other internal vertices:

$$\begin{array}{rl}{\Pi }_0& =\{\{1,2,3,4,5\}\},\\ {\Pi }_1& =\{\{1,5\},\{2,3,4\}\},\\ {\Pi }_2& =\{\{1,5\},\{2,4\},\{3\}\}={\Pi }_3.\end{array}$$