1. Define subgraph tuples of size k and initialize labels according to the isomorphism class of this subgraph.
2. Iteratively assign a new label to each subgraph by hashing the multi-set of the current labels within this subgraph’s neighborhood.
3. Repeat Step 2 until the labels for all subgraphs converge.
4. Construct the multi-set.

University of Michigan - Ann Arbor

The key idea behind the k-WL algorithms is that we label subgraphs of size k rather than individual nodes.

The k-WL test and k-GNNs


Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Graph Representation Learning by William Hamilton

Procedure of k-WL algorithm

It introduces a hierarchy of representational capacity.

Learn Before

Related