mlsanityData to 14 Oct 2026

Complete Neural Networks for Complete Euclidean Graphs

arXiv 2301.13821 ↗First posted 31 Jan 2023cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 33 of its 59 references that are in the map. First posted on arXiv 31 Jan 2023.

Builds on

33 of 59 references.

References · 33

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2018How Powerful are Graph Neural Networks?cited by 4,393
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  4. 2021E(n) Equivariant Graph Neural Networkscited by 965
  5. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  6. 2018Tensor field networks: Rotation- and translation-equivariant neural networks for 3D point cloudscited by 746
  7. 2017SchNet: A continuous-filter convolutional neural network for modeling quantum interactionscited by 571
  8. 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
  9. 2022MACE: Higher Order Equivariant Message Passing Neural Networks for Fast and Accurate Force Fieldscited by 474
  10. 2019Provably Powerful Graph Networkscited by 389
  11. 2021GemNet: Universal Directional Graph Neural Networks for Moleculescited by 343
  12. 2020Learning from Protein Structure with Geometric Vector Perceptronscited by 313
21 more
  1. 2020Fast Differentiable Sorting and Rankingcited by 197
  2. 2021A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groupscited by 187
  3. 2022Graph neural networks for materials science and chemistrycited by 182
  4. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 179
  5. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  6. 2021Frame Averaging for Invariant and Equivariant Network Designcited by 168
  7. 2019Stability Properties of Graph Neural Networkscited by 127
  8. 2021Scalars are universal: Equivariant machine learning, structured like classical physicscited by 127
  9. 2023On the Expressive Power of Geometric Graph Neural Networkscited by 90
  10. 2020On the Universality of Rotation Equivariant Point Cloud Networkscited by 80
  11. 2022ComENet: Towards Complete and Efficient Message Passing for 3D Molecular Graphscited by 69
  12. 2021Universal Approximation of Functions on Setscited by 62
  13. 2019FSPool: Learning Set Representations with Featurewise Sort Poolingcited by 53
  14. 2022Low Dimensional Invariant Embeddings for Universal Geometric Learningcited by 38
  15. 2022Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networkscited by 21
  16. 2022Permutation Invariant Representations with Applications to Graph Deep Learningcited by 20
  17. 2022Incompleteness of graph neural networks for points clouds in three dimensionscited by 19
  18. 2021ZZ-Net: A Universal Rotation Equivariant Architecture for 2D Point Cloudscited by 15
  19. 2022A Simple and Universal Rotation Equivariant Point-cloud Networkcited by 11
  20. 2022Polynomial-time algorithms for continuous metrics on atomic clouds of unordered pointscited by 8
  21. 2019Linearly Converging Quasi Branch and Bound Algorithms for Global Rigid Registrationcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 2; 2025: 2; 2026: 4.

10 papers.

  1. 2023Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theoremcited by 34
  2. 2024On the Completeness of Invariant Geometric Deep Learning Modelscited by 11
  3. 2023Universal Representation of Permutation-Invariant Functions on Vectors and Tensorscited by 10
  4. 2024FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Networkcited by 8
  5. 2025Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrumcited by 3
  6. 2026Any-Subgroup Equivariant Networks via Symmetry Breakingcited by 2
  7. 2025On the (Non) Injectivity of Piecewise Linear Janossy Poolingcited by 1
  8. 2026Quantitative Approximation Rates for Group Equivariant Learningcited by 1
  9. 2026Using large language models to probe the limits of atom-centered structural descriptorscited by 0
  10. 2026Why Multi-Layer Message Passing Works: Completeness Theory for Graph Neural Network Interatomic Potentialscited by 0