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.

University of Michigan - Ann Arbor

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

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

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

Learn Before

Related