Message passing approaches generally fail to identify closed triangles in a graph, which is a critical limitation.

Why We need Relational Pooling?

1. The full algorithm is computationally intractable.
2. We know that RP-GNNs are more powerful than the WL test, but we have no way to characterize how much more powerful they are.

Limitation of Relational Pooling

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.

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

Relational Pooling

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

Learn Before

Related

Learn After