On the Expressive Power of Geometric Graph Neural Networks

We propose a geometric version of the Weisfeiler-Leman graph isomorphism test (GWL) for discriminating geometric graphs while respecting the underlying symmetries such as permutation, rotation, and translation.We use GWL to characterise the expressive power of Graph Neural Networks (GNNs) for geometric graphs and provide formal results for the following: (1) What geometric graphs can and cannot be distinguished by GNNs invariant or equivariant to spatial symmetries;(2) Equivariant GNNs are strictly more powerful than their invariant counterparts.