On the Expressive Power of Sparse Geometric MPNNs

Motivated by applications in chemistry and other sciences, we study the expressivepower of message-passing neural networks for geometric graphs, whose nodefeatures correspond to 3-dimensional positions. Recent work has shown that suchmodels can separate generic pairs of non-isomorphic geometric graphs, though theymay fail to separate some rare and complicated instances. However, these resultsassume a fully connected graph, where each node possesses complete knowledgeof all other nodes. In contrast, often, in application, every node only possessesknowledge of a small number of nearest neighbors.This paper shows that generic pairs of non-isomorphic geometric graphs canbe separated by message-passing networks with rotation equivariant features aslong as the underlying graph is connected. When only invariant intermediatefeatures are allowed, generic separation is guaranteed for generically globallyrigid graphs. We introduce a simple architecture, EGENNET, which achieves ourtheoretical guarantees and compares favorably with alternative architecture onsynthetic and chemical benchmarks