# Three iterations of (d-1)-WL test distinguish non isometric clouds of d-dimensional points

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 28 references that are in the map.
- First posted on arXiv 22 Mar 2023.

## Builds on (most cited first, 13 of 13)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [MACE: Higher Order Equivariant Message Passing Neural Networks for Fast and Accurate Force Fields](https://mlsanity.com/paper/2206.07697/) (2022)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [On the Expressive Power of Geometric Graph Neural Networks](https://mlsanity.com/paper/2301.09308/) (2023)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [Weisfeiler and Leman Go Relational](https://mlsanity.com/paper/2211.17113/) (2022)
- [Is Distance Matrix Enough for Geometric Deep Learning?](https://mlsanity.com/paper/2302.05743/) (2023)
- [Incompleteness of graph neural networks for points clouds in three dimensions](https://mlsanity.com/paper/2201.07136/) (2022)

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

- [Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem](https://mlsanity.com/paper/2306.06529/) (2023)
- [Comparing Graph Transformers via Positional Encodings](https://mlsanity.com/paper/2402.14202/) (2024)
- [On the Completeness of Invariant Geometric Deep Learning Models](https://mlsanity.com/paper/2402.04836/) (2024)
- [Weisfeiler Leman for Euclidean Equivariant Machine Learning](https://mlsanity.com/paper/2402.02484/) (2024)
- [On the Expressive Power of Sparse Geometric MPNNs](https://mlsanity.com/paper/2407.02025/) (2024)
- [Universally Invariant Learning in Equivariant GNNs](https://mlsanity.com/paper/2510.13169/) (2025)
- [Toward bilipshiz geometric models](https://mlsanity.com/paper/2511.11735/) (2025)
- [Quantitative Approximation Rates for Group Equivariant Learning](https://mlsanity.com/paper/2602.20370/) (2026)
- [Why Multi-Layer Message Passing Works: Completeness Theory for Graph Neural Network Interatomic Potentials](https://mlsanity.com/paper/2609.00528/) (2026)

## Abstract (arXiv)

The Weisfeiler--Lehman (WL) test is a fundamental iterative algorithm for checking isomorphism of graphs. It has also been observed that it underlies the design of several graph neural network architectures, whose capabilities and performance can be understood in terms of the expressive power of this test. Motivated by recent developments in machine learning applications to datasets involving three-dimensional objects, we study when the WL test is em complete for clouds of euclidean points represented by complete distance graphs, i.e., when it can distinguish, up to isometry, any arbitrary such cloud. %arbitrary clouds of euclidean points represented by complete distance graphs. % How many dimensions of the Weisfeiler--Lehman test is enough to distinguish any two non-isometric point clouds in d-dimensional Euclidean space, assuming that these point clouds are given as complete graphs labeled by distances between the points? This question is important for understanding, which architectures of graph neural networks are capable of fully exploiting the spacial structure of a point cloud. Our main result states that the (d-1)-dimensional WL test is complete for point clouds in d-dimensional Euclidean space, for any d≥ 2, and that only three iterations of the test suffice. We also observe that the d-dimensional WL test only requires one iteration to achieve completeness. Our paper thus provides complete understanding of the 3-dimensional case: it was shown in previous works that 1-WL is not complete in ℝ3, and we show that 2-WL is complete there. We also strengthen the lower bound for 1-WL by showing that it is unable to recognize planar point clouds in ℝ3. Finally, we show that 2-WL is not complete in ℝ6, leaving as an open question, whether it is complete in ℝd for d = 4,5.