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.

Procedure of k-WL algorithm

It introduces a hierarchy of representational capacity.

Representation Advantage of k-WL algorithm

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

University of Michigan - Ann Arbor

1. Relational Pooling.
2. Invariant and equivariant k-order GNNs
3. The k-WL test and k-GNNs

Three Major Directions of Modifying WL Algorithm

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

We simply add a unique, one-hot indicator feature for each node. The ID will make graphs distinguishable. Relational Pooling involves marginalizing over all possible node permutations.

Learn Before

Related

Learn After