Complete Neural Networks for Complete Euclidean Graphs

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.

arXiv commentThe 38th AAAI Conference on Artificial Intelligence

References in corpus (22)

• Neural Message Passing for Quantum Chemistry
• Tensor field networks: Rotation- and translation-equivariant neural networks for 3D point clouds
• SchNet: A continuous-filter convolutional neural network for modeling quantum interactions
• MACE: Higher Order Equivariant Message Passing Neural Networks for Fast and Accurate Force Fields
• Principal Neighbourhood Aggregation for Graph Nets
• Stability Properties of Graph Neural Networks
• Learning from Protein Structure with Geometric Vector Perceptrons
• On the Completeness of Atomic Structure Representations
• GemNet: Universal Directional Graph Neural Networks for Molecules
• On the equivalence between graph isomorphism testing and function approximation with GNNs
• Scalars are universal: Equivariant machine learning, structured like classical physics
• ComENet: Towards Complete and Efficient Message Passing for 3D Molecular Graphs
• Sign and Basis Invariant Networks for Spectral Graph Representation Learning
• 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
• Frame Averaging for Invariant and Equivariant Network Design
• Polynomial-time algorithms for continuous metrics on atomic clouds of unordered points
• Incompleteness of graph neural networks for points clouds in three dimensions
• 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