Geometric Deep Learning IX: Message-Passing GNNs Are No More Powerful Than the Weisfeiler–Lehman Test — Equal Colour Histograms Force Equal OutputsTextbook
Graph neural networks (GNNs) compute representations of nodes and whole graphs by repeatedly combining each node's state with information from its neighbours. Soon after they became a standard tool, the question arose of what they cannot do. A natural test case is graph isomorphism: given two graphs that are not isomorphic, can the network attach different…