Complete Neural Networks for Complete Euclidean Graphs
arXiv:2301.13821 · doi:10.1609/aaai.v38i11.29141
Abstract
Neural networks for point clouds, which respect their natural invariance to permutation and rigid motion, have enjoyed recent success in modeling geometric phenomena, from molecular dynamics to recommender systems. Yet, to date, no model with polynomial complexity is known to be complete, that is, able to distinguish between any pair of non-isomorphic point clouds. We fill this theoretical gap by showing that point clouds can be completely determined, up to permutation and rigid motion, by applying the 3-WL graph isomorphism test to the point cloud's centralized Gram matrix. Moreover, we formulate an Euclidean variant of the 2-WL test and show that it is also sufficient to achieve completeness. We then show how our complete Euclidean WL tests can be simulated by an Euclidean graph neural network of moderate size and demonstrate their separation capability on highly symmetrical point clouds.
The 38th AAAI Conference on Artificial Intelligence
References in corpus (7)
- SchNet: A continuous-filter convolutional neural network for modeling quantum interactions
- A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups
- On the Expressive Power of Geometric Graph Neural Networks
- On the Universality of Rotation Equivariant Point Cloud Networks
- Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
- Recognizing Rigid Patterns of Unlabeled Point Clouds by Complete and Continuous Isometry Invariants with no False Negatives and no False Positives
- A Simple and Universal Rotation Equivariant Point-cloud Network