Concept

Theorem 4

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.

Image 0

0

1

Updated 2022-07-24

Tags

Deep Learning

Data Science

Related