 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.

Theorem 4

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

Theorem 5

University of Illinois at Urbana-Champaign

1. The key distinction between GNN and WL.
2. The relationship between GNNs and the WL algorithm.

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

1.  The WL algorithm aggregates and updates discrete labels (using a hash function) while GNN models aggregate and update node embeddings using neural networks.
2. GNNs have been motivated and derived as a continuous and differentiable analog of the WL algorithm.


Learn Before

Related

Learn After