On the Expressive Power of Sparse Geometric MPNNs
Yonatan Sverdlov Nadav Dym
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
WL, GWL, GNNS, geometric GNNS, point clouds, completness
The expressvness power of 1-GWL test.