The seminal works of Xu et al. [1]} and Morris et al. [2]} (see also [3]}) showed that GNNs are exactly as powerful in distinguishing graphs as the Weisfeiler-Lehman (WL) test [4]}, also known as color refinement. This combinatorial procedure is a necessary but not sufficient test for graph isomorphism. It proceeds in repeated rounds: in each round, a node labels itself with the “hash” of the multiset of labels of its neighbors. The aforementioned papers show that (i) GNNs can simulate the WL test and (ii) GNNs can only distinguish those graphs that the WL test determines to be different. This provides a complete characterization of the expressive power of GNN architectures.
