On the Expressive Power of Sparse Geometric MPNNs
This work addresses a fundamental limitation in geometric graph neural networks for applications like chemistry, where nodes typically only know a few neighbors, by providing theoretical guarantees for expressive power with sparse connectivity.
The paper tackles the problem of distinguishing non-isomorphic geometric graphs using message-passing neural networks with sparse connectivity, showing that generic separation is possible with rotation equivariant features for connected graphs and with invariant features for generically globally rigid graphs. It introduces EGENNET, which achieves these theoretical guarantees and performs favorably on synthetic and chemical benchmarks.
Motivated by applications in chemistry and other sciences, we study the expressive power of message-passing neural networks for geometric graphs, whose node features correspond to 3-dimensional positions. Recent work has shown that such models can separate generic pairs of non-isomorphic geometric graphs, though they may fail to separate some rare and complicated instances. However, these results assume a fully connected graph, where each node possesses complete knowledge of all other nodes. In contrast, often, in application, every node only possesses knowledge of a small number of nearest neighbors. This paper shows that generic pairs of non-isomorphic geometric graphs can be separated by message-passing networks with rotation equivariant features as long as the underlying graph is connected. When only invariant intermediate features are allowed, generic separation is guaranteed for generically globally rigid graphs. We introduce a simple architecture, EGENNET, which achieves our theoretical guarantees and compares favorably with alternative architecture on synthetic and chemical benchmarks. Our code is available at https://github.com/yonatansverdlov/E-GenNet.