2 GNNs that are sufficient to match the power of the WL algorithm.

Which MP-GNNs are most powerful?

 There exist message-passing GNNs that are as powerful as the WL test.

University of Illinois at Urbana-Champaign

The relationship between GNNs and the 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

 GNNs are no more powerful than the WL algorithm when we have discrete information as node features.
 If the WL algorithm assigns the same label to two nodes, then any message-passing GNN will also assign the same embedding to these two nodes. This result on node
labeling also extends to isomorphism testing. If the WL test cannot distinguish between two graphs, then a MP-GNN is also incapable of distinguishing between
these two graphs.

Learn Before

Related

Learn After