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.

Relational Pooling

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


EXPRESSIVE POWER OF INVARIANT AND EQUIVARIANT GRAPH NEURAL NETWORKS

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

University of Michigan - Ann Arbor

1. Given two graphs, we assign each node an initial label in each graph. 
2. We iteratively assign a new label to each node in each graph by hashing the multi-set of the current labels within the node’s neighborhood, as well as the node’s current label.
3. We repeat Step 2 until the labels for all nodes in both graphs converge.
4. Finally, we construct  multi-sets summarizing all the node labels in each graph, and we declare G1 and G2 to be isomorphic if and only if the multi-sets for both graphs are identical.

The Weisfieler-Lehman(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

Learn Before

Related

Learn After