# Incompleteness of graph neural networks for points clouds in three dimensions

arXiv: https://arxiv.org/abs/2201.07136 · HTML: https://mlsanity.com/paper/2201.07136/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 2 references that are in the map.
- First posted on arXiv 18 Jan 2022.

## Built on by (most cited first, 19 of 19)

- [Smooth, exact rotational symmetrization for deep learning on point clouds](https://mlsanity.com/paper/2305.19302/) (2023)
- [Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem](https://mlsanity.com/paper/2306.06529/) (2023)
- [Symphony: Symmetry-Equivariant Point-Centered Spherical Harmonics for 3D Molecule Generation](https://mlsanity.com/paper/2311.16199/) (2023)
- [Crystalformer: Infinitely Connected Attention for Periodic Structure Encoding](https://mlsanity.com/paper/2403.11686/) (2024)
- [Molecular geometric deep learning](https://mlsanity.com/paper/2306.15065/) (2023)
- [Higher-Order Equivariant Neural Networks for Charge Density Prediction in Materials](https://mlsanity.com/paper/2312.05388/) (2023)
- [Complete Neural Networks for Complete Euclidean Graphs](https://mlsanity.com/paper/2301.13821/) (2023)
- [Weisfeiler Leman for Euclidean Equivariant Machine Learning](https://mlsanity.com/paper/2402.02484/) (2024)
- [Three iterations of (d-1)-WL test distinguish non isometric clouds of d-dimensional points](https://mlsanity.com/paper/2303.12853/) (2023)
- [Completeness of Atomic Structure Representations](https://mlsanity.com/paper/2302.14770/) (2023)
- [A Clifford Algebraic Approach to E(n)-Equivariant High-order Graph Neural Networks](https://mlsanity.com/paper/2410.04692/) (2024)
- [Geometric Deep Learning for Molecular Crystal Structure Prediction](https://mlsanity.com/paper/2303.10140/) (2023)
- [Multi-Type Point Cloud Autoencoder: A Complete Equivariant Embedding for Molecule Conformation and Pose](https://mlsanity.com/paper/2405.13791/) (2024)
- [Learning Ordering in Crystalline Materials with Symmetry-Aware Graph Neural Networks](https://mlsanity.com/paper/2409.13851/) (2024)
- [Quantitative Approximation Rates for Group Equivariant Learning](https://mlsanity.com/paper/2602.20370/) (2026)
- [How unconstrained machine-learning models learn physical symmetries](https://mlsanity.com/paper/2603.24638/) (2026)
- [DisGNet: A Distance Graph Neural Network for Forward Kinematics Learning of Gough-Stewart Platform](https://mlsanity.com/paper/2402.09077/) (2024)
- [CrystalFramer: Rethinking the Role of Frames for SE(3)-Invariant Crystal Structure Modeling](https://mlsanity.com/paper/2503.02209/) (2025)
- [Using large language models to probe the limits of atom-centered structural descriptors](https://mlsanity.com/paper/2607.26984/) (2026)

## Abstract (arXiv)

Graph neural networks (GNN) are very popular methods in machine learning and have been applied very successfully to the prediction of the properties of molecules and materials. First-order GNNs are well known to be incomplete, i.e., there exist graphs that are distinct but appear identical when seen through the lens of the GNN. More complicated schemes have thus been designed to increase their resolving power. Applications to molecules (and more generally, point clouds), however, add a geometric dimension to the problem. The most straightforward and prevalent approach to construct graph representation for molecules regards atoms as vertices in a graph and draws a bond between each pair of atoms within a chosen cutoff. Bonds can be decorated with the distance between atoms, and the resulting "distance graph NNs" (dGNN) have empirically demonstrated excellent resolving power and are widely used in chemical ML, with all known indistinguishable configurations being resolved in the fully-connected limit, which is equivalent to infinite or sufficiently large cutoff. Here we present a counterexample that proves that dGNNs are not complete even for the restricted case of fully-connected graphs induced by 3D atom clouds. We construct pairs of distinct point clouds whose associated graphs are, for any cutoff radius, equivalent based on a first-order Weisfeiler-Lehman test. This class of degenerate structures includes chemically-plausible configurations, both for isolated structures and for infinite structures that are periodic in 1, 2, and 3 dimensions. The existence of indistinguishable configurations sets an ultimate limit to the expressive power of some of the well-established GNN architectures for atomistic machine learning. Models that explicitly use angular or directional information in the description of atomic environments can resolve this class of degeneracies.