Three Iterations of (d − 1)-WL Test Distinguish Non Isometric Clouds of d-dimensional Points
Authors: Valentino delle Rose
Alexander Kozachinskiy
Cristobal Rojas
Mircea Petrache
Pablo Barcelo
Venue: NeurIPS 2023 poster (2023)
Keywords: euclidean graphs
point clouds
WL test
graph neural networks
TL;DR: We show that the (d − 1)-dimensional WL test is complete for point clouds in d-dimensional Euclidean space, for any d ≥ 2.

Abstract: The Weisfeiler-Lehman (WL) test is a fundamental iterative algorithm for checking the 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. Our main result states that the $(d-1)$-dimensional WL test is complete for point clouds in $d$-dimensional Euclidean space, for any $d\ge 2$, and only three iterations of the test suffice. Our result is tight for $d = 2, 3$. We also observe that the $d$-dimensional WL test only requires one iteration to achieve completeness.

Three Iterations of (d- Test Distinguish Non Isometric Clouds of d-dimensional Points
Valentino Delle Rose 122, Alexander Kozachinskiy 1.3 Cristóbal Rojas
Mircea Petrache 2.244 Paalo Barceló 1.2,3
Centro Nacional de Inteligencia Artificial, Chile
2 Instituto de Ingeniería Matemática y Computacional, Universidad Católica de Chile
3 Instituto Milenio Fundamentos de los Datos, Chile Departamento de Matemática, Universidad Católica Chile valentino de dellerose@cenia cl, alexander cristobal roj as@mat. uc. cl, mpetrachedmat. uc. cl, pbarcelo@uc. cl
Abstract
The Weisfeiler-Lehman (WL) test is fundamental iterative algorithm for checking the isomorphism of graphs. has also been observed that underlies the design several graph neural network architectures, whose capabilities and performance can be understood in terms of expressive power of this test. Motivated by recent developments in machine learning applications datasets involving three- dimensional objects, we study when the WL test is complete for clouds of Euclidean points represented by complete distance graphs, i.c., when it can distinguish, up to isometry, any arbitrary such cloud. Our main result states that the (d 1)- dimensional WL test is complete for point clouds in d-dimensional Euclidean space, for any 2 2, and only three iterations the test suffice. Our result is tight for d 2, 3. We also observe that the d-dimensional WL test only requires one iteration to achieve completeness.
Introduction
Context. Recent work in machine learning has raised the need to develop effective and efficient tests for checking if two three-dimensional point clouds, i.e., finite sets of points in R.3 are isometric 13 [2]. Recall that, given two such point clouds and Q, an isometry a distance-preservee bijection between the points in P and Q. The importance of these tests is that they provide the foundations for designing neural network architectures on point clouds that are capable of fully exploiting the structure of the data [18 14]. It has been observed that the incompleteness of any such an architecture, i.e., the inability to recognize a point cloud up to isometry, can affect its learning performance [16). Understanding which is the simplest that allows detecting isometries this scenario is thus essential not only for developing "complete" architectures but also to make them as efficient as possible in of the computational resources they need use.
Point clouds can be represented as complete graphs in which each edge is labeled with the distance between the corresponding points. Under this representation, detecting the isometry of two point clouds is reduced to detecting an isomorphism between their graph representation. Not surprisingly, then, much of the work on developing so-called geometric tests for detecting isometries over point clouds inspired by the literature on isomorphism tests from graph theory. Of particular importance
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

in this context has been the use of geometric versions of the well-known Weisfeiler-Lehman test (WL test) for graph isomorphism [77]
Intuitively, the f-dimensional geometric WL test (&-WI, test), for l 2 1, iteratively colors each tuple of points in point cloud. 'Te color of in round 0 is complete description of the mutual distances between the points that belong to the tuple. In round t + 1, for 2 O, the color of E is updated by combining in a suitable manner its color in iteration with the color of each one of its neighbors, i.e., the tuples E' that are obtained from ö by exchanging exactly one component of o with another point in the cloud. The dimensionality of the WL test is therefore a measure of its computational cost: the higher the É, the more costly it is to implement the Ł-dimensional WL test.
For checking if two point clouds are isometric, the geometric WL test compares the resulting color pattern.. If they differ, then we can be sure the point clouds are not isometric (that is, the test is sound). An important question, therefore, is what is the minimal & 2 for which the geometric (-WL. test is complete, i.e., the fact that the color patterns obtained two point clouds are the same implies that they are isometric.
There has been important progress on this problem recently: (a) Pozdnyakov and Ceriotti have shown that the geometric 1-WL test is incomplete for point clouds in 3D; that is, there exist isometric point clouds in three dimensions that cannot be distinguished by the geometric 1-WL test [5]: : (b) Hordan et al. have proved that 3-WL test is complete in 3D after 1 iteration when initialized with Gram matrices of the triples of points instead of the mutual distances in these triples. A similar result has recently been obtained in [1]. Hordan al. also gave complete "2-WI--like" test, but this test.
explicitly uses coordinates of the points.
As further related results, in [10. geometric WL tests have been compared to the expressivity of invariant and equivariant graph neural networks. Non-geometric related results include e.g. [5). where for explicit graphs on vertices it is shown that f-WL requires (nn) iterations for distinguishing them, whereas 2L-WL requires O( and (36- -) requires Olog n1) iterations, and [9], which has promising proposal for generalized distances non-geometric graphs, based on biconnectivity.
Main theoretical results. Our previous observation show an evident gap in our understanding of the problem: What is the minimum É, where f = 2, 3, for which the geometric f-dimensional WL test is complete over chree-dimensional point clouds? Our main contributions are the following:
We show that for any d the geometrie (d 1)-WL test is complete for detecting isometries point clouds in Rd This is the positive counterpart of the result in [14] (namely, that geometric 1-WL test is incomplete in dimension d = 3), by showing that geometric 1- is complete for d 2 and that geometric 2-WL test is complete for d=3. 3. Further, only three rounds of the geometric (d - 1)-WL. test suffice to obtain this completeness result.
We provide a simple proof that single round of the geometric d-WL test is sufficient for identifying point clouds in I2 up to isometry, for each d 2 1. This can be seen as a refinement of the result in [9], with the difference that our test is initialized with the mutual distances inside d-tuples of points (as in the classical setting) while theirs is initialized with Gram matrices of d-tuples of points. In other words, the initial coloring of [9, for each d-tuple of points, in addition to their pairwise distances, includes their distances to the origin, while in result we do not require this additional information.
These results, as well as previously mentioned results obtained in the literature, are all based on the standard folklore version of the E-WL test (as defined, e.g., in (3) This is important because another version of the test, known as the oblivious {-WL test, has also been studied in the machine learning literature 14 13. It is known that, for each / 2 1, the folklore & WL test has the same discriminating power the oblivious (e + 1)-WI. test
Table I summarizes the state of the art concerning the distinguishing power of the geometric (-WL. test; note that it is not known whether the (d WL test is incomplete for d 2 4.
Relationship with graph neural networks. Graph Neural Networks (GNNs) are specialized neural networks designed to process data structured as graphs [8] 11 Among GNNs, Message Passing GNNs (MPGNNs) use a message-passing algorithm to disseminate information between nodes in a graph [6]. The relationship between the 1-WL test and MPGNNs is now a fundamental subject in

---

Is B-WL complete for Rd?
1-WL
2-WL
3-WL
Complete
Complete
1R2
in iterations
in iteration Theorem 5.1
Theorem 2.1
Incomplete
Complete
Complete
I
in 3 iterations Theorem 2.1
in 1 iteration Theorem 5.1
[14]
Complete
I²4
Open
in 3 iterations Thcorem 2.1
(d - 21-
(d 1)-WL
d-WL Complete
Complete
Rd
Open
in 3 iterations
in 1 iteration
Theorem 2.1
Theorem 5.1
Table 1: What is known about the distinguish power of geometric E-WL.
this field. Seminal research has shown that these approaches essentially equivalent in their ability to distinguish non non-isomorphic graph pairs 14 18 Additionally, Morris et al. [14] proposed higher-dimensional (-MPGNNs that have the same discriminating power as the oblivious f-WL test, and hence as the folkiore (e WL test, for l 1.
The geometric WL test studied here corresponds to particular case of the relational WL test, i.c., a suitable version of the WL. test that is tailored for edge-labeled graphs. Connections between the relational WL test and so-called relational MPGNNs have recently been established by M. In particular, relational Ł-MPGNNs have the same discriminating power as the (folklore) geometric test),WL for & 1. Our main result implies then that there no need create specialized GNN architectures for distinguishing non-isometric point clouds in RR Instead, relational d-MPGNNs sufficient for this task.
Experimental evaluation of MPGNNs, based on the folklore 2- WL. test, data sets from molecular physics, and their comparison with state-of-art models, was recently performed in [2
Formal Statement of the Main Result
Consider cloud of n points S {Pi..... : Po. in Rd. We are interested in the problem of finding representations of such clouds that completely characterize them up to isometries, while at the same time being efficient from algorithmic point of view. Our main motivation to understand the expressiveness of the WL algorithm when applied to point clouds euclidean space seen as complete distance graphs. Let briefly recall how this algorithm works.
function whose domain is S will be called an l-coloring of S. The &-WL algorithm an iterative (i)
procedure which acts on S by assigning, at iteration i, an Ê-coloring X2.5 of S.
(0) Initial coloring. The initial coloring, Xe.s. assigns to each É-tuple = (æ).... xz) E S the color (0) X (x) given by the & x l matrix
(0) (x))s = d(z,, 23) i.j = I....,f
of the relative distances inside the ttuple (for f = we have trivial coloring by the 0 matrix).
(x) Iterative coloring. At each iteration, the 6-WL algorithm updates the current coloring X obtain
(1+1) The update operation is defined slightly differently depending whether refined coloring Xi,s
f = 1 or e 2.
For L. 1, we have:
XL.5 (x) (xis (dl
That is, first, X (x) remembers the coloring of x from the previous step. Then goes through all points y E S. For each y, it stores the distance from y and also the coloring
3

---

of from the previous step, and it remembers the multiset of these pairs. Note that one can determine which of these pairs comes from y itself since this is the only point with d(x, y) = O. We also note that (1) (1) corresponds to the multiset of distances from & to the points of S.
To define the update operation for 2 2, we first introduce additional notation. Let x (ZI....,Ze) .T)) E S and E S. By xly/i] we mean the tuple obtained from x by replacing its coordinate by y. Then the update operation can be defined as follows:
(1+1) (x) Xe,8
(8) (X,,s(x) (x), 8 (x,, (x/u/1)) X (x(v/()) y E SH)
(8)
(1)
In other words, first, Xi.S (x) remembers the coloring of x from the previous step, as before. Then, it goes through all y E S and considers the l tuples x(y/Il..... x x(y/ then takes the colorings of these tuples from the previous step and puts them into a tuple. The new coloring now remembers the multiset of these tuples.
(1+1)
.....
In this paper we show that the coloring obtained after 3 iterations of (d - 1)-WL is a complete isometry invariant for point clouds in IR More precisely, we show:
Theorem 2.1 (Main Theorem). For any d 2 2 and for any finite set S [ R. the following holds.
(3) X be the coloring of S obtained after iterations of the (d - 1)-WL algorithm on the Let
distance graph of S. Then, knowing the multiset
M xxxx0 [xx=1,s(s) SE Sd
one can determine S up an isometry.
Our proof is constructive in the sense that we exhibit an algorithm which, upon input M M (S).
computes the coordinates of point cloud S' which is isometric to S. In particular, if S C Rd is another point cloud such that M (3) - (S), then and 5 are isometric.
Our result is also true for point clouds that are multisets S C Rd (for which distance graphs can have edges, labeled by 0, connecting two nodes, representing the same point in space), but for simplicity, we now present the argument for sets (although no significant changes are needed).
Organization of the paper. We start in Section 3 with the proof of the two-dimensional case, which while somewhat simpler, will allow us to introduce the general strategy. In Section 4 we explain how to implement this strategy in general for d > 2. Then, in Section 5 we discuss the completeness of one round of d- WI. Finally, Section 6 we present open problems and limitations. Due to space constraints, some proofs have been relegated to the appendix.
3 Three iterations of 1- 1-WL distinguish clouds in the plane
Let C R be a cloud of n points the plane. Our task is to reconstruct S up to an isometry, using as input the information contained in X1.s- (3) This means to find a point cloud S' in the plane which is
an image of S under some isometry. Our proof has two main steps: Initialization and Reconstruction. In the Initialization Step we show how to extract from X1,9 the relevant information need, which we call initialization data. In the Reconstruction step, we describe algorithm that, given some initialization data, computes the coordinates of the desired isometric cloud.
(3)
In our reconstruction algorithm, we employ the notion of the barycenter of point cloud (also known as the center of mass), which we denote by b, and is defined by:
b
Σ W. WES
For simplicity, we translate S by -b so that the new barycenter sits at b 0. Notice that since our reconstruction is up isometries, this assumption does not affect the gerenality our result. For each w E S, let || denote its norm (its distance to b= 0).
We say that two points u, S satisfy the cone condition if + 0, v o 0, and, moreover,

---

if 0, ut v lie on the same line, then all points of S lie on this line;
if 0, u, v do not lie on the same line, then the interior of Cone(u, v) {ar + 3e a, 8 E [0, +o0) does not contain points from S (see the first picture on Figure ! the red area between (0, u) and (0, v) is disjoint from S).
In order to initialize our reconstruction algorithm, we need the following information about S. We assume that S has more than 1 point (otherwise there is nothing to do).
Initialization Data: the initialization data consists of real number do and two multisets M, M' such that for some u, V E S, satisfying the cone condition, it holds that do = d(u, v) and
M M, B (d(u,v)
Iwll)) y E ES:: M' = Mo [( (d(v, v), llvll) y SJ.
We will start by describing the Reconstruction Algorithm, assuming that the initialization data is given. We will then show how extract this data from X1.5 in the Initialization Step bellow.
(3)
Reconstruction algorithm. Assume that initialization data (do, M. M') is given. Our task is to determine up to isometry. Note that from M we can determine ||ul]. Indeed, in M there exists exactly one element whose first coordinate is O, and this element is (0, |/]]). Likewise, from M' we can determine ||=|]. We are also given do = d(u, u, v). Overall, we have all the distances between 0, u, and v. Up rotation of S, there is only one way to put u, it has to be somewhere radius ||u]|, centered at the origin. We fix any point of this circle as u. After that, there are at most two points where can have More specifically, v belongs to the intersection of two circles: one of radius ||u|] centered at the origin, and the other radius d(u, v) centered at u. These two circles different (remember that the cone condition includes requirement that u o 0). Hence, they intersect by at most two points. These points are symmetric w.r.t. the line that connects the centers of the circles, i.e., 0 and u. Thus, up a reflection through this line (which preserves the origin and w), we know where to put v.
the circle of
Henceforth, we can assume the coordinates of u and v are known to us. Note that so far, have applied to S translation (to put the barycenter at the origin), a rotation (to fix u), and a reflection (to fix v). We claim that, up to this isometry, S can be determined uniquely.
Let Refl, and Refl, denote the reflections through the lines (0, u) and (0, v). respectively. We first observe that from M we can restore each point of S up to a reflection through the line (0, u). Likewise, from M' we can do the same with respect to the line (0, v). More precisely, we can compute the following multisets:
Lu -f (...R Refl.yl 1 E SH
= fu 1 EE
Indeed, consider any (d(u, y), [yll) E M. What can we learn about y E S from this pair of numbers? These numbers are distances from y to u and to O. Thus, must belong to the intersection of two circles: one with the center
and radius d(u, and the other with the center at 0 and radius ||y|l- Again, since u + O, these two circles are different. Thus, we obtain at most two points 21, 22 where one can put y. We will refer to these points candidate locations for y w.r.t. They can be obtained one from the other by the reflection Refl,, through the line connecting 0 and u. Hence, (21 {y, Refl.. To compute Lu, go through (d( u, y), [|v/]) E M, compute candidate locations 21, 22 for y, and put (21, 22) into T.,. In a similar fashion, one can compute I., from M'.
element Let us remark that elements of L. and L, are sets of size 2 or 1. A set of size 2 appears of Ly when some y has two distinct candidate locations w.r.t. u. that is when y does not lie on the line (0, u). In turn, when y does lie this line, we have 21 22 y for two of its candidate locations, giving us an element {y} E Lu, determining y uniquely. The same thing happens with respect to L, for points that lie on the line (0,v). v).
The idea of our reconstruction algorithm is to gradually exclude some candidate locations so that more and more points get unique possible location. What allows us to start is that and satisfy the cone condition; this condition gives us some area that is free of points from S (thus, one can exclude candidates belonging this area).
5

---

The easy case is when O, u, and belong to the same line, Then, by the cone condition, all points of S belong to this line. this case. every point of S has just one candidate location. Hence, both multisets L., and T, uniquely determine S.
Assume now that O, u, and do not belong the same line. As in the previous case, restore all points that belong to the line connecting 0 and u, or to the line connecting 0 and v (although now these are w.r.t. u or w.r.t. U. They can be identified by going through Lu and Ly (we are interested in points with {2} E L, L.).
uniquely
different lines). Indeed, these are points that have exactly one candidate location
The pseudocode for our reconstruction algorithm is given in Algorithm [ description. Let make a general remark about our algorithm. Once we find unique location for some y E S, we remove it from our set in order to reduce everything to the smaller set 5 {y). This implemented by updating the multisets T_ and Tap so that y not taken into account in them. For that, we just remove {v, R from Lu and {y, Refl.y) } from Ly (more precisely, decrease their multiplicities by 1).
We now give its verbal
From now on, we assume that these two lines (connecting and u, and 0 and v, respectively) are free of the points of S. These lines contain the border of the cone Cone(u, v). At the same time, the interior of this cone is disjoint from S due to the cone condition. Thus, in fact, the whole Cone u, v) is disjoint from S.
We now go through I., and T., in search of points for which one of the candidate locations (either w.r.t. u or w.r.t. v) falls into the "forbidden area", that is, into Cone(u, v). After restoring these points and deleting them, we notice that the "forbidden area" becomes larger. Indeed, now in there are no points that fall into Cone(u, v) under one of the reflections Refl,, or Refl,- In other words, the updated "forbidden area" is F Cone(u, u, v) Refl., Cone(u, v) U Refl, Cone(u, v). If the absolute angle between and is Ques then, F has total amplitude 30 We now iterate this process, updating I' successively. At each step, we know that after all removals made so far, S does not have points in F. Thus, points of S that fall into F under Refl,, or under Refl, can be restored uniquely. After deleting them, we repeat the same operation with Refl,, Refl, place F.
Algorithm 1: Reconstruction algorithm
S == Ø;
2 for {2] E L. Lg do
// Restoring points from the lines (0, u) and (0,v)
Put into S:
Remove {=} from Ly U Luy
5 end for
F : Cone(u, v);
while F' # R² do
for {=1, } E Lu U L, do // Restoring points that have one candidate location in the forbidden area
21 E F or 22 E F then
10
Set = 21 if 22 E F and 22 if F;
11
Put y into S: Remove {y, Refl.y) from Ln and (v, Refl.y) from L.;
12
13
end for // Updating forbidden area
14
F = FU Re Re
15 end while
Output S;
After k such "updates", F will consist of 24 + adjacent angles, each of size Osos with Cone(u, (u, v) being in the center. In each update, we replace F with F U Refl, F Refl, F. This results in adding two angles of size Oue to both sides F. Indeed, we look at the ray (0, u). splits our current F into two angles, of size (k + 1)w and the other of size ka Under Refl,.. the part whose size

---

u
(b)
71
(c)
Figure 1: Growth of the "forbidden" area.
(k: + 1)a.. adds an angle of size Que to the other part. Analogously, Refl, adds an angle of size Own from the opposite side of F. See Figure for the illustration of this process.
such steps, F covers all angular directions, thus completing the reconstruction Within at most 1 Cuwe of S.
Initialization step. We explain how to obtain the Initialization Data about S from M (S))
We start by observing that from the first iteration of 1-WL, we compute ||=||| for all S. As the following lemma shows, this holds in any dimension, with the same proof. We temporarily omit the current hypothesis b 0, in order to use the lemma later without this hypothesis.
Lemma 3.1 (The Barycenter Lemma). Take any n-point cloud S C IRd and let
D. dd(z, v) y E SB.
Then for every x E S, knowing D2 and the multiset (Dy E SB, one can determine the distance from x to the barycenter of S.
Proof. Consider the function f: Rd + [0, +00) defined as f(x) Eyes | y1 namely fx)
the sum of the squares of all elements of D, (with multiplicities). It follows that Eyes [(y) is determined by ff D SB. The lemma is thus proved if we prove the following equality
||
b112
f(x)
(2)
n
2n
DES
To prove the above, we first write:
f(x)
Σ
- 2/1
Σ [1 - + (b w)1l
VES
DE
Σ
|| - 6112 + 2(x - b, - y) + ||b - y/l
yES
n || b112 + 2(x b, Σ い) Σ
b 2/
wE
n || b1l2 Σ
b v/
(by definition of barycenter).
DES

---

Denote = Eyes s -bb - yll².
Substituting the expression for f(x and fly from above into the
right-hand side of (2, we get:
1 n
f(z)
1
Σ f(y)
f())
=
n- 1 b112
+I
Σ
nn . 11 -b12 + +1)
2n yES
2n
yES
n || b112
+
1
(nI' + nd)) = 1| -b1?,
2n.
as required.
By definition, (z) determines the multiset D2 = (d(x,)) y S}} of distances from to points of S. Since we are given the multiset M (S). we also know the multset ( = I (x) x E S} (labels after the third iterations determine labels from previous iterations). In particular, this gives us the multiset { DD x E $.). Overall, due to the Barycenter lemma, we conclude that (x) can be converted into ||=:|]- Now, remember that
(1)
(x) (x),s()), ((d((,))) xi(()) vES)).
By converting (1) (v) into |yll for all y E S here, one can convert xi (x) into the multiset
(2)
M₂ (d(2, y). lllll) 1 y ES..
We need one more iteration to find d(u, v), Mu M, for some u, v E S satisfying the cone condition. In fact, only need
(b)(2) (x)s((),, (lll.,)).iixs))) vESB)
sB)
(3) for arbitrary u E S with u * O. Since (3) (u) determines |u/, such X1,s (u) can indeed be selected from M (S) (and since we assume that S has more than one point, we know that there are points in S that different from 0).
in turn convert Xi.s (u) into the multiset A = {l (d(u, y), M2)): y E S S}. J In particular, since y = u is the only point for which d(u, v) = O, can compute M, from A. Once we have Ma, the rest of the initialization goes follows. First note that for a given element (d(u, y). My) in A with d(u, > O (so that * u), we can look in My for the only element with 0 the first entry, whose second entry then ||y||. So we can obtain (d(u, v), llvll). As in the Reconstruction Algorithm, we then have only two possibilities for the location of y relative to u, say y1 and y2 Refl,, ). follows that the absolute value of the angle Gug between u and is uniquely determined (if ||>l|| = O. we set Gay = 0), and we can compute from A. In order select v, we go though and look for such that Qur is the smallest angle among {auy E 5,0 < aug < J.. If such a does not exist, all points of S must lie on the line connecting 0 and In this case, the cone condition satisfied, for example, for u and we can initialize with du 0, M M' M,. If v as above exists, there can be no point in the interior of Cone(u, u, v), since otherwise there would be y with < aug < Que < n, contradicting the minimality of O'av- Thus, the cone condition is satisfied for v. We can then set do = d(u, v), M = M,, and M' = M
(2) Due to the fact that Xi.s (v) can be converted to My,
(3)
u. Thus,
Proof of Main Theorem for d > 2
We now present the proof for the case d 2. The strategy of the proof has the same structure as for d 2. Since the objects involved now are more general, it will be convenient to introduce some terminology. Let x (I1,..., x4) E (Red)& be a k-tuple of points in Rdd The distance matrix of is the k x k matrix A given by Ag xz), i.j k.
8

---

Now, let S _ Id be finite set. Then the distance profile of x w.r.t. S is the multiset
xx= (d(a11 yitii,.))............. v)) E SB.
As before, we let b [s] Eves y denote the barycenter of S. For a finite set G C R2, denote by LinearSpan(G) the linear space spanned by G, and by AffineSpan(G) the corresponding affine one. Their respective dimensions will be denoted by LinearDim(G) and AffineDim(G).
As for the case d 2. we start by distilling the Initialization Data required for the reconstruction, which is described relative to the barycenter b of S. For convenience, we have decided not to assume at this stage that S has been translated first to put at the origin, as we did for the sake of the exposition in the case d = 2. This is now the task of the isometry we apply to S when choosing locations for its points, which we now completely relegate the reconstruction phase.
Definition 1. Let S Rdd be finite set and let be its barycenter. A d-tuple (#1,..., ... S satisfies the cone condition
AffineDim(b, .,...., Fa) ) AffineDimSS):
if AffineDim(S) = d, then there is no E S such that b belongs to the interior of Cone(z) b,..., Id b).
Definition 2. For a tuple x = (I1,..., Ia) E Sdd we define its enhanced profile as EP
(1, Ma),
where the distance matrix of the tuple (b, (b, za) and M, Dxpa/j the distance profile of the tuple (.1....,, 24- b, (i+1)...;;a) Ra) with respect S.
Definition Let S E gd be finite set and let be its barycenter. An initialization data for S is a tuple (A, MM,...,M, such that (A, M,,
EP( xa) for some d-tuple
x = (#i,..., Ta) E St satisfying the cone condition.
Remark 4.1. The interested reader can verify that the Initialization Data condition extends the definition for d = 2. Note that the first bullet of the Cone Condition is automatically verified for but nontrivial for d >
The fact that initialization data (A,M1, M1,..., Ma) can be recovered from Ma-1(S) is ensured by the following proposition.
(3) Proposition 4.2 (Initialization Lemma). Take any C Rd, Then, knowing the multiset X
s E 5d-11 one can determine an initialization data for S.
We now proceed with the reconstruction phase.
4.1 Reconstruction Algorithm
Assume an Initialization Data (A, .I.M..,, Ma) for a finite S C Rd given. Our first task is to choose, up to isometry, positions for the points in the (d + 1)-tuple (b, (b, corresponding to the matrix A. We use the following classical lemma, whose proof given e.g. in [4] Sec. 2.2.1].
Lemma 4.3 (Anchor Lemma). If (ui,..., uR) Rd and (Vi,..., v&) Rd have the same distance matrix, then there exists isometry f: Fdd Rd such that f(u,) vs for all = L....,, k.
As for 2, we put the barycenter of the cloud at the origin. Then, we simply apply the Anchor Lemma to any collection of points 21..... Fd E Rd such that our given A is also the distance matrix of the tuple (0, 21. zd). The Lemma then gives us an isometry f: RRd - Rd such that 21. 21....,f(e f(za)
Zd- As distance profiles are invariant under isometries. our given M, is also the distance profile the tuple (Z1,.... ž4-1, 0, 2;-1. =d) w.r.t f(S). Our task now is, from My.... Ma, to uniquely determine the locations of all points in f(S). This would give us 5 up to an isometry. Since now we have locations for (2i,...,
f(b) 0, fx1
(ag....,,,) 2d), we can in fact compute:
AffineDim(S) (S) AffineDim(b 21. Fa) AffineDim(O, (1,21,,,..) 21, 2a) LinearDim 2d),
where the first equality is guaranteed by the cone condition. The reconstruction algorithm depends on whether AffineDim(S) = d or not.

---

Consider first the case when AffineDim(S) = LinearDim ............ (2........... 2d) < d. Then there exists i E {I...., d} such that LinearDim( .1.............................. 2d) LinearDim( 21,.... 2 .......... 2g). This means that ((S) c AffineSpan(21, 21, ....... 1,,,, 0, =.+1,-.... =d), since otherwise f(S) would have larger affine dimension. We claim that, in this case, from Mr we can restore the location of all points in ((S). Indeed, from M, we know, for each E f(S), tuple with the distances from to 21,.... 24-1, 0 Zi+11..., Ed. As the next lemma shows, this information is enough to uniquely determine the location of z.
Lemma 4.4. Take any I1,, F.m E Rd. Assume that a, b AffineSpam(?i,.... Fm) are such that d(a, x.)) = d(b, x1) for all i = ....., m. Then a = b.
It remains to reconstruct ((S) when AffineDim(S) = d. in which case our pivot points 21, Zd are linearly independent. Recall that Mr is the distance profile of the tuple (z1,..., 2i- 0, Z4+ zd) w.r.t f(S). Moreover, since no r in S is such that x - b lies in the interior of Cone( - ...1........ we know that f(S) must be disjoint from the interior of Cone(21,.... .d)) As the next proposition shows, this information is enough to reconstruct f(S) in this case as well, which finishes the proof of Theorem 2.1 d > 2.
b).
Proposition 4.5 (The Reconstruction Lemma). Assume that 21,...,, 2d E Rd are linearly independent. Let T S Rdd be finite and disjoint from the interior of Cone (2....., zd) If. for every i 1..... d, we are given 2; and also the distance profile of the tuple (Z), (21,..,, 2-,, 0, 2i+1 2d) w.r.t. T. then we can uniquely determine T.
5 On the distinguishing power of one iteration of d-WL
In this section, we discuss a somewhat different strategy to reconstruct S. It is clear that for point E I2 we are given the distances from it to d d points in general position with known coordinates, then the position of is uniquely determined (see c.g. Lemma 4.4) Since d-WL colors d-tuples of points in S, natural strategy to recover S' is to use the barycenter as an additional point. By Lemma 3.1. we know that distances to the barycenter from points of can be obtained after one iteration of d-WL. However, the information that allows us to match d(z. b) to the distances from this 2 to a d-tuple, is readily available only after two iterations of d-WL. It follows that this simple strategy can be used to directly reconstruct S from the second iteration of d-WL. We remark that this strategy is similar to the one used in |9 to uniquely determine S up to isometries when the coloring we are initially given corresponds to certain Gram Matrices for d-tuples of points. Essentially, after one interaction of d-WL over this initial data, we obtain enough information to directly determine the location of each relative to collection of d + 1 points. In fact, it is not hard to show that from the first iteration of d-WL, applied to the distance graph of S, one can compute these Gram Matrices, thus providing alternative proof that two iterations suffice for distinguishing geometric graphs.
We show instead that only one iteration suffices. Our approach differs and depends on certain geometric principles that allow us to simplify the problem by conducting an exhaustive search across an exponentially large range of possibilities.
Theorem 5.1. For any d 2 1 for any finite set C Rd, knowing the multiset (x E SdB. one can determine S up to an isometry.
6 Final remarks
Open problems. An interesting open question about our work is what is the minimum number of rounds needed for the (d - W) test to be complete with respect to point clouds in Rd. Our result shows that three rounds suffice, but we do not know the completeness status of the test when only one or two rounds are allowed. Another open problem is the completeness status of the (d - 2L test for d-dimensional point clouds when d > 3.
Limitations. A consequence of our main result and is that distance d-MPGNNs possess sufficient expressive capability to learn d-dimensional point clouds up to isometry. However, the computational complexity of implementing d' d-MPGNNs is major concern, as it involves Onz)) operations per iteration, where n denotes the number of nodes in the graph. This computational cost can quickly become unmanageable, even for relatively small values of d, such as d = 3. It remains to be studied which kind of optimizations on higher-order GNNs can be implemented for improved performance without much sacrifice on their expressive power.
10

---

7 Acknowledgements
Barceló and Kozachinskiy are funded by ANID WNIDD-Millennium Science Initiative Program ICN17002. All authors are funded by the National Center for Artificial Intelligence CENIA FB210017, Basal ANID. Delle Rose is funded by ANID Fondecyt Postdoctorado 3230263. Petrache is funded by ANID Fondecyt Regular 1210462.
References
[1] Pablo Barceló, Mikhail Galkin, Christopher Morris, and Miguel A. Romero Orth. Weisfeiler and leman go relational. In LOG, volume 198, page 46. PMLR, 2022.
[2] Ilyes Batatia, Dávid Péter Kovács, Gregor N. C. Simm, Christoph Ortner, and Gábor Csányi. Mace: Higher order equivariant message passing neural networks for fast and accurate force fields, 2022.
[3] Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Comb., 12(4):389 410, 1992.
[4] Trevor F. Cox and Michael A. A. Cox. Multidimensional Scaling (2nd edition). Chapman and Hall / CRC, 2001.
[5] Martin Fürer. Weisfeiler-lehman refinement requires at least linear number iterations. In Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 821 2001 Proceedings 28, pages 322-333. Springer, 2001.
[6] Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
[7] Martin Grohe. The logic of graph neural networks. In LICS, pages 1-17. IEEE, 2021.
[8] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurlPS, pages 1024-1034, 2017.
[9] Snir Hordan, Tal Amir, Steven Gortler, and Nadav Dym. Complete neural networks for euclidean graphs, 2023.
[10] Chaitanya K Joshi, Cristian Bodnar, Simon V Mathis, Taco Cohen, and Pietro Lio. On the expressive power of geometric graph neural networks. arXiv preprint arXiv:2301.09330 2023.
[11] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[12] Zian Li, Xiyuan Wang, Yinan Huang, and Muhan Zhang. distance matrix enough for geometric deep learning?, 2023.
[13] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten M. Borgwardt. Weisfeiler and leman go machine learning: The story far. CoRR, abs/21 12.0992, 2021.
[14] Christopher Morri, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks, AAAI, pages 4602 4609, 2019.
[15] Sergey N. Pozdnyakov and Michele Ceriotti. Incompleteness of graph convolutional neural networks for points clouds in three dimensions. CoRR, abs/2201.07136, 2022.
[16] Sergey N. Pozdnyakov, Michael J. Willatt, Albert P. Bartók, Christoph Ortner, Gábor Csányi, and Michele Ceriotti. Incompleteness of atomic structure representations. Phys. Rev. Lett., 125: 166:16 Oct 2020.
[17] Boris Weisfeiler and A.A. Leman. The reduction of graph canonical form and the algebra which appears therein, 1968.

---

[18] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[19] Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. arXiv preprint wrXiv:2301.09005 2023.
12

---

A Appendix
A.1 Proofs for Initialization
Here we provide the proof of Proposition 4.2 We will need the following extension of the Barycenter Lemma.
Lemma A.1. Let b be the barycenter of S C R d > 2. For any x = : E S
knowing (1) (d-1,s(x) and the multiser (xd-11s(y) y E su-1B, one can determine the tuple of distances (..
We claim that we can determine (D Day .) and DDly E S} from the information given the lemma statement. By Lemma 3.1 this allows to determine (d(x), (el.,,,),............. d(xa-1,b)).
Proof. Let Dr be as in Lemma 3.1
We have
Xd-1,s(x)= = (x
(Xd-1.s(x), -
&f (x (x ..... Xa- (x...sxx//dd 121) y sT).
By definition, from (0) (x-1,s(xly/11] one can determine the tuple distances (((22,).....d((.. d(sa-1,9)). Hence, from the multiset Wxa- (xl=1)) y E SB one can (0)
determine (Dz..... Dea_.). In turn, Dz, can be determined from, say, fixi 1 (xly/2) y E SB. We have just shown that (1) xx) uniquely determines D Hence, from the multiset 1x
y y Sd- one can compute the multiset (D yy (vi,..., ....... we- E S But this multiset coincides with the multiset Dy y E S} except that multiplicities are |S|d-2 times larger.
Now, we show that after the second iteration, we can restore the distance profile of (b, (b., Td-1) for all (Ii,...,,Id) Id--1) S
Lemma A.2. For any x III. E Sd-1, knowing x and the multiset (x y E Id-1B, one can determine the distance profile of (b, F. xa-1) w.r. S.
Proof. Since d > 2, we have
(2) (x) (xx)(x), (1)
(xl-1s(xll/11),...... xx_.s(x///1)) "xa
E 5B). restore the tuple of distances
From the tuple (x (Xd-1.s
(0)
(d(y,z1),... xd)1))
In turn, by Lemma A.1 from Xd- (u//1) and lxd- E St-1]] we can restore d(y. b). Hence, restore the whole distance profile of (b, (dd.).
(1)
(x
Finally, we show that knowing (x-1,5(x) for x = (II, and the multiset (1) (xd-1,s(y) | y gd-11. B. we can compute
1EP(,))...,441..1)) S}.
Since dl > have
(x) = (x.2) (xx-,.((x), Ef (2) ( (x (xtp (x(u/kk)) 1 E (B).
For every y E S. knowing (x-1,s(x) and (x 1]), ... (x ki)) we have to
compute P(1(....... Td-1, v). that is, the distance matrix of (b, ". v) and the distance profiles of the tuples
(b, 22 Id-1, 2), y)...... (01 ... b. (2)...,, Ta-1..))
13

---

Distance profiles can be computed by Lemma A.2 The distances amongst el- ements of ( (0)
can be computed by definition from (0) (xx-1,s(x(y//) (x(y//I)) .aal....,aaaa.....
(x) and
Distances to b from these points can be computed by Lemma A.I from (2 sxx and (1) Xx
Xa- xx
X2 (x/1s(((v//)))
Now that we have the enhanced profiles, we have to select one for which (#11.... Ta) satisfies the cone condition. We first observe that, knowing E( Fd) we can reconstruct (b, .1...., (td up to an isometry by Lemma 4.3 (because inside I Fd) we are given the distance matrix of (b, :1,....... Ra)). This means that from E ................................ Fa) we can compute any function of b, 21..... which is invariant under isometries. particular, we can compute AffineDim(b, Fi,..... (.d).. We will refer to AffineDim(44xx,) (1,,, 2ad) as the dimension of the corresponding enhanced profile.
We show that AffineDim(S) is equal the maximal dimension of an enhanced profile. Indeed, first notice that AffineDim( (S) = AffineDim {b} S) because b is a convex combination of points of S. In turn, AffineDim( [b} U 5) equal to the maximal for which one can choose points a E S such that - b......u Ft. b are linearly independent. Obviously, & is bounded by the dimension of the space. Hence, there will be an enhanced profile with the same maximal dimension k.
If Aff)n < d, any enhanced profile with maximal dimension satisfies the initialization requirement, and we are done. Assume therefore that AffineDim(S) = d. Our task is to output some EP(x1,.... ,., Id)) such that
1. AffineDim(l. .1, = d. and
2. there no x E S such that x b belongs to the interior of Cone(æ) - bb...,244 Fd b).
For that, among all d-dimensional enhanced profiles, we output one which minimizes the solid angle at the origin, defined as
Angle(æ; - b....,,,y Fz b) 1 Vol fa E Cone(z) - b..... .......2. Fa b) || S 1}
(3)
d
(the solid angle is invariant under isometries, and hence can computed from Fs ra)).
We have to show that for all æ S we have that - b lies outside the interior of Cone(æ) b...., Fd b). To prove this, we need an extra lemma. We will say that cone C' is simple if C' Cone(w1.... ..... ua). for some linearly independent uj,..., Uu. Observe that if C Cone(u1..... a simple cone, then the interior of C' is the
int(C") = {A141 +... + Adua Ai....,, Ad E (0, +00))
Note also that the boundary of C consists of d faces
Fj = C n LinearSpan(u U4-1; Ui+11-..,,.. ua), i 1= d.
Lemma A.3. Let = Cone(u) C Rd for foru- (ui,..., ua) be a simple cone and let y belong to the interior of C. Then Cone(uly/1] is simple cone and Angle(u(y/1)) < Angle(u).
Proof. Since y belongs to the interior of Cone(u), we have that
iary + AaUa,
for some A > O...., Ad O. The fact that X1 > implies that y, u2,... uy are linearly independent, and hence Cone(u(y/11 [1] is a simple cone. Since y E Cone(u), we have that Cone(u(y/11) S Cone(u). Thus, to show that Angle(uly/1)) < Angle(u), it suffices to show that the volume of
{ar E Cone(u): ||^|| S 1) \ far E Cone(uly/1)) ||^||| 1
is positive. We claim that for any point = M4 U1 + + Hada E Cone(uiy/11) we have μr > P2/P1 2 A2/ / Au. This because x can be written as a non-negative linear combination of y. U2...., thg Since μ1 0, the coefficient in front of y in this linear combination must be positive. Now, if the coefficient in front of U2 O, then the ratio between #22 and #1 exactly as the ratio between dg and '₁, and if the coefficient before u2 is positive, μ2 can only increase.
14

---

This means that no point of the form
M1 U1 +
+ paulds
0 < Hr, p2/P1 < X2/D1
(4)
belongs to Cone(uly/ (age//ggg]]]1 /1])- It remains show that the set of points that satisfy 4 and lie in for Cone(u): | S 1 has positive volume.
Indeed, for any 0 and 6 > 0, consider a d-dimensional parallelepiped:
P [1121 +... pazza Na [c/2,, P2,.... Ad E [8/2,6]]-
Regardless of & and 5, we have that P subset of Cone(u) and its volume is positive. For all sufficiently small E, 6, we have that P is subset of the unit ball {ar E R4 ||==|| S 1}. In turn, by choosing to be sufficiently big compared to ō, we ensure that all points of satisfy (4)
Let E S minimize Angle( 6, ..... Fd 6) amongst Sd such that AffineDim(b, 21,...,, Fd) d. Assume that does not satisfy the cone condition, and let x E S be such that x - E Int(CCne([a - b..... Id - b)) holds. Then, by Lemma A.3 Angle( b, b..., Fd b) is strictly smaller than Angle(æ1 Cone( 1, - b..., Id - b) is a simple cone, x - b, 02 - b,..., Ft - b are linearly independent, and thus AffineDim(l. xr 22, -.. ra) = d, contradicting the minimality hypothesis x, desired.
Now we can finish the proof of Proposition
4.2
b, 22 b.... Fd b). As
A.2 Proofs for Reconstruction
Proof of Lemma 4.4 We claim that for every i ...... we have (a I1 21) (b-
T1, 21). This is because 21 and b 21 have the same distance z; (which is equal to d((a, -.)
d(b, 3; and, moreover, the norms of a Ii and I coincide (and are equal to d(a, = d(b, )). Hence, both Iı and b Iι are solutions to the following linear system of cquations:
(0 - m) = (a 31 1n),
= 2
This system has at most solution over E LinearSpan(xz Ii...., Im z1). Moreover, I and 11 are both from LinearSpann(22-100 ..,.....4....................... 21) because a, b AffineSpan(T1 Fm Hence, a - = b - 21, and a = b.
Let P: AffineSpan(2 2- ,, za). As the following lemma shows, knowing the distances from E T to 21, 2i-1, 0, 2+11, Zd, we can determine the position of s uniquely up to the reflection through P..
Proof of Proposition
Lemma A.4 (The Symmetric Lemma). Let 21...., E RRd be such that AffineSpan(21.... (1,, Fmn has dimension d - 1. Assume that a, b E Rd are such that d(a, x;) = ((b,,x)) ( for all 1,.... m. and are symmetric w.r.l. AffineSpan 1... J.m)
Then either
Proof. As in the proof of Lemma 4.4 we have that (a- - x1) (b-rI, for every =
2.... m. Consider orthogonal projections of a aa-20 21 and b- LinearSpan I I1.... I' 2)).
Both these projections are solutions to the system
(x, r; x1) (a I1, x1), i = 2,... m.
This system has at most one solution over LinearSpan F1 ... 2m 21). Hence, projections of a 21 and b- Ii coincide. We also have that ||0 - xi || = ||b æIll, ll. which implies that a æ and b æ1 have the same distance LinearSpan(1z2 of LinearSpan(22 - F1,-.., Im 21) is 1, we get that either a - σn = - #1 or they can be obtained from each other by the reflection through LinearSpan(z2 Ti ... Fm x1). After
F,,,-. ... , ..mm x1). Since the dimension
translating everything by I1, we obtain the claim of the lemma.
In fact, if belongs to Pt. then there is just one possibility for s. Thus, we can restore all the points in that belong to the union U P.. Let us remove these points from and update distance profiles by deleting the tuples of distances that correspond to the points that we have removed.
From now on, we may assume that T is disjoint from U P.. Hence, T is also disjoint from the boundary of C Cone( F.a) not only from its interior (every face of this cone lies on P; for some i).
15

---

For 2: E RR, we define p(x) min dist(z, P.). Since T' is disjoint from U P., we have that p(s) > 0 for every s E T. Moreover, from, say, the distance profile of (0, 22..... z4). we can compute some >> O such that p(s) 2 for all E T. Indeed, recall that from the distance profile of (0, 22, ..................... =d); we get at most potential positions for each point of T. This gives us a finite set T (at most 2 times larger than 7) which is a superset of T. Moreover, as T is disjoint from U P. we have that 7" \ U P: 2 T Thus, we can define as the minimum of p(z) over T" \ U P. We conclude that is disjoint from
Ao = Cu p(x) <
(moreover, the set Ao is known to us).
Our reconstruction procedure starts follows. We go through all distance profiles, and through all tuples of distances in them. Each tuple gives candidates for point in T (that can be obtained from each other by the reflection through P,). If one of the candidates lies in Ag, we know that we should take the other candidate. In this way. we may possibly uniquely determine some points in T.. If so, we remove them from T' and update our distance profiles.
Which points of will be found in this way? Those that, for some i, fall into Ag under the reflection through P.. Indeed, these are precisely the points that give 2 candidates (when go through the äth distance profile) one of which is in Ag. In other words, we will determine all the points that lic in _ Refl; (Ao). where Refl, denotes the reflection through P.. After we remove these points, we know that the remaining I' is disjoint from A Ao U (Ao).
We then continue in exactly the same way, but with Ai instead of Ao, and then with A2 = A U U i==1 Refl; (1), and so on. remains to show that all the points of 7 will be recovered in this way. In other words, we have argue that each point of I' belongs to some A,, where
Ao = Cu=CufEER p(x) =)
A+t1 A. (A.).
We will show this not only for points in T but for all points in IR., Equivalently, we have show that for every x E Id there exists finite sequence of reflections Tı,..., E [Refl,.... Refly] which brings x inside Ag, that is, Tк .... (I) Ag-
We construct this sequence reflections as follows. Let x be outside Ag. In particular, x is outside the cone C = Cone( #1 ....... za). Then there exists face of this cone such that C' is from one side of this face and x is from the other side. Assume that this face belongs to the hyperplane P.. We then reflect through P., and repeat this operation until get inside Ag- We next show that the above process stops within a finite number of steps. For that, we introduce the quantity (xx) = (ar 21) +... (Ir, za). We claim that with each step, 7<x) increases by at least e where
c= min dist(z;, 1si5d
d, we have that 2; & P., by the linear independency of 21,..., Zg- Also observe that 7(x) < [x] Σ; | and reflections across the subspaces P; do not change |r]. Hence, 7<x) cannot increase infinitely many times by some fixed positive amount.
Note that c >> 0 because, for every i=
remains to show that 7(x) increases by at least c 5 at each step, as claimed. Note that reflection of across some P. does not change the scalar product of with those vectors among ..,..., Za that belong to P.. The only scalar product that changes is (z, 2;), and the only direction which contributes to the change is the one orthogonal to P.. Before the reflection, the contribution of this direction to the scalar product was -d(z, P.) d(z,, P:) (remember that x and 2; were from different sides of P, because 2; E C). After the reflection, the contribution is the same, but with positive sign. Thus, the scalar product increases by 2d(x, P.) d(2;, P.). Now, we have d(z,, P.) 2 c/2 by definition of c and d(x P.) if x is not yet in Ag-
B Proofs for Theorem 5.1
Proof of Theorem 5.7 From Xa.s we can determine the tuple s (Si...., s2) up an isometry,
since x (s) gives us (s), which is the distance matrix s. In order determine S, we consider
(1)
(0)
two cases:
16

---

Case I: For all E 5 it holds AffineDim(s) < d. Then take Xd.s with maximal Amfine and fix locations of points from compatible with the distance specification, according to Lemma 4.3 All points of S belong to AffineSpan(s), otherwise we could increase AffineDim(s). Indeed, since (ffi < d 1, we could throw away one of the points from the tuple without decreasing the dimension and replace with a point outside AffineSpan(s). We now can reconstruct the rest of
uniquely up to isometry. Indeed, in Xd.s (s) are given the multiset of d-tuples of distances to ($1....;5al sd) from the points of S, and it remains to use Lemma 4.4
(1)
Case 2: There are tuples with AffineSpan(s) d 1. We first observe that from the multiset (xd, s E Sh we can compute the pairwise sum of distances between the points in S, i.e.
Ds = -E d(x,y).
BES YES
Indeed, from ( we determine 82)) Hence, we can compute the sum:
Σ
[2) = Ds 15/
In our reconstruction of S, we go through all Xa.s (s) with AffineDim(s) = d d. we fix positions of the points of the tuple s in any way that agrees with the distance matrix of this tuple. As before, Xd.s (s) gives the multiset of d-tuples of distances to from the points of S. We call "candidates for S given s" the set of point clouds S' which have one point associated with each such d-tuple of distances, and realizing these distances to points in s. We aim to find for which, exactly one of these candidates can be isometric S. We start with the following lemma:
1. For each of them,
(1)
Lemma B.1. For any finite set S C Rd with AffineDim(S) 2 d - 1 there exist II....,
Zd E S with 1 such that all points of S belong to the same half-space with respect T.)).
AffineDim (z.............................. .xa) ......,,,,............. to the hyperplane
Proof. The general idea of the proof the following. Dff then the extreme points of the convex hull of S contain an affinely independent set of cardinality d, which then gives the desired s. The half-space condition in the lemma automatically verified in this case. Aff) d then to find s we can proceed by moving (d - 1)-plane from infinity towards until touches S at least one point, then iteratively we rotate the plane around the subspace containing the already touched points of S, until a new point in S prohibits to continue that rotation. We stop within at most iterations, when no further rotation is allowed, in which case the plane has an affinely independent subset in common with S.
Formally, we need find a hyperplane such that, first, all points of belong to the same half-space w.r.t. H, and second, AffineDim H n S) = d d-1. 1.
To start, we need find hyperplane H such that, first, all points of S belong to the same half- space w.r.t. H, and second, n S * Ø. For instance, take any non-zero vector a E Rdd consider m maxxex (ax, .²) and define H by the equation (a, m. Now, take any iy E H N.S. After translating S by 11,, we may assume that 21 = 0.
Now, among all hyperplanes H that contain I 0 and satisfy the condition that all points of lie in the same half-space w.r.t. H. we take one that contains most points of S. We claim that AffineDim(H S) d for this H. Assume for contradiction that AffineDim H n S) < d 1. Define U = AffineSpan(EI n S). Since H n S contains 1 = O, we have that C H a linear subspace, and its dimension is less than d 1. Hence, since AffineDim(S) 2 d - 1, there exists I2 E S U. Note that x2 & H because otherwise x2 belongs to H INSCU.
Let be the normal vector to H. Since all points of S lie in the same half-space w.r.t. H, w.l.o.g. we may assume that (a, s) 2 for all s E S. In particular, (o, .22)
because .r2 & H.
Let U denote the orthogonal complement to U. Since is the normal vector to H 2 U, we have that a E U We need to find some 3 E U which is not a multiple of a but satisfies (3, > O. Indeed, the dimension of U is at most d - 2, and hence the dimension of U- least 2. Now, since (a, x222 > O, we can take any 3 U- which is sufficiently close a.
17

---

For any À 2 O, let Hy be the hyperplane, defined by (a \3, a) = 0 (this is a hyperplane and not the whole space because 3 is not multiple of a). We claim that for some 0, we have that HA, has more points of S than H while still all points of S lie in the same half-space w.r.t. Hx. This would be a contradiction.
Indeed, define S3 = {s E S (s, B) > 0}. Note that Sg. by definition of 3, contains 22 and hence is non-empty. Moreover, Si is disjoint from H n S. This is because H nS C U and B E U-.
Define
X min {a, =ESa (3,8)
First, H2 2 HNS because a A3 E U+. Moreover, H2 contains at least one point of S which is not in H. Namely, it HA contains any 8 Sg, establishing the minimum in the definition of À (and recall that S3 is disjoint from H S). Indeed, for this we have (a.s) Hence, (3,))
sa,s) - +) 0 = (a- db, 8) - SEE/ H
It remains to show that all points of S lie in the same half-space w.r.t. Hx. More specifically, will show that (a - A3, s) 2 0 for all s E S. First, assume that (s, B) = 0. Then (a - X3, s) =
s) 0 because all points of S lie in the "non-negative" half-space w.r.t. a. Second, assume (a.s). This means that
that (s, B) > 0. Then 8 E Sg. Hence, by definition of X, we have À S (8,5)
(a (3, s) = (o., s) (B3 s) 2 0, as required.
LI
Next, consider the following simple geometric observation:
Lemma B.2. Let P PE Rdd be a hyperplane and consider two points a, b E TRd P that lie in same half-space w.E.t P. Let a', be the reflections of a, b through P. Then d(a', b') d(a, b) < d(a, B).
Proof. It suffices to restrict to the plane AffineSpan((a,by b, a))), and thus we take d = 2 and up to isometry we may fix P to be the x-axis, a (0. (x..y), = (a,-v'), with y, v/ > Then it follows that d(a, b)2 x² + (y - v²)² < <x² (y v/ d(a, B¹) As reflections are isometries, +
d(a, b) = d(a', b').
Claim: If is in Lemma B.1 then we have the following:
Exactly one of the candidates for S given s. up to reflection across AffineSpan(s). is completely contained in one of the half-spaces determined by AffineSpan(s).
A candidate S' as in the previous point is the only one of the candidates for S given s, up to reflection across AffineSpanss), for which Ds
Ds.
To prove the first item, we use only the property that AffineDim(s) = 1, with which by Lemma A.4 each point of candidate for S given has either two possible locations (related by reflection across AffineSpanss) or a single possible location if it belongs to AffineSpan(s). For the second item, let 5" be as above and let S" be candidate for S given s, which is not completely contained in one of the halfspaces determined by AffineSpan (s). We now consider each term d(a', v/) in the sum defining Ds,, comparing the corresponding term d(x", v/" from Ds",, where x x/' or is reflection across s of x' and similarly for y" and y'_ By Lemma B.2 either d(ø", v/") = d(x', v/) in case x".y" are in the same half-space determined by AffineSpan(s), or d(æ" v/") > d(x',
otherwise. Summing all terms, by the property of S" S" we find Dy < DDw.. By the same reasoning with S instead of S" since are assuming that s satisfies Lemma B.2 have Dg Ds completing the proof of the second item and of the claim.
The reconstruction of S in Case 2, can therefore be done as follows: run through all such that (ffineDim(s) = d - 1, and for each such we construct all candidates S for S given s, and calculate D3 for each of them. Lemma guarantees that we run into some s for which, up to isometry, only
one such Š realizes D3 = Dg. This is our unique reconstruction of S.
18


Reviews:
[{"review_id": "n6u5xAGdMq", "reviewer": "Reviewer_Z3UF", "summary": "The paper addresses the question of testing the existence of a one-to-one application between two point clouds such that the distances are preserved. This information can be used, for example, to build better structured graph neural network architectures to optimize their performance. The starting point is that the distances between elements of a point cloud can be used to label the edges of a graph connecting them. Hence, the problem boils down to the detection of isometry between two graphs, for which the Weisfeiler-Lehman test is the classic tool. However, the latter makes it possible to conclude if two clouds are not isometric, but not necessarily that they are, depending on the computation cost. This paper sheds light on the issue in terms of the size of the ambient space", "questions": "The proofs are sometimes very verbose and would benefit from geometric illustration rather than prosaic text. The proof of lemma 3.1 (which seems connected to Konig-Huygens theorem) can easily go in the appendix to save space. As it is, I find it difficult to follow the entire logic of the proofs beyond a line-by-line follow-up.\n\nThe corollary 6.1 seems constructive. It woulds be helpful to describe the algorithm in a pseudo-code and maybe illustrate the proposed MPGNN. \n\nI believe this will make the paper more accessible to a wider audience. \nSince I don't have the necessary knowledge, I can hardly judge the impact and practical importance of such a result. ", "limitations": "NA", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The document is fairly well written and the contributions are clearly stated. Since the results are theoretical in nature, they essentially consist of a succession of proofs. But they seem to be rigorously executed.\nNot being a specialist in the field, I can't really appreciate the impact of such a theoretical result. This brings me to my next comment on the weaknesses.", "weaknesses": "The stated result, i.e. the ability to answer affirmatively if isometry between point clouds is proven from the WL test, is in itself very interesting. It squarely fits into \"understanding ML results\".\nHowever, the authors stressed the importance of their results in improving the design of neural net architecture. This is unfortunately not clarified and it should be nice if the authors could comment more on that.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Reviewer's comment: \"the authors stressed the importance of their results in improving the design of neural net architecture. This is unfortunately not clarified and it should be nice if the authors could comment more on that.\"\n\nRESPONSE:   What we mean is simply that, when working with cloud points in dimension d, our results inform the decisions regarding the choice of parameters of the geometric GNN: as far as expressivity is concerned, order d and three layers are sufficient.  \n\n\nQuestions:\nThe proofs are sometimes very verbose and would benefit from geometric illustration rather than prosaic text. The proof of lemma 3.1 (which seems connected to Konig-Huygens theorem) can easily go in the appendix to save space. As it is, I find it difficult to follow the entire logic of the proofs beyond a line-by-line follow-up.\nThe corollary 6.1 seems constructive. It woulds be helpful to describe the algorithm in a pseudo-code and maybe illustrate the proposed MPGNN. I believe this will make the paper more accessible to a wider audience. Since I don't have the necessary knowledge, I can hardly judge the impact and practical importance of such a result.\n\nRESPONSE:  see “GENERAL RESPONSE” in the Author Rebuttal box at the beginning.  \n"}, {"review_id": "D7nGmeFs8H", "reviewer": "Reviewer_q73v", "summary": "The expressive power of GNNs has long been a central topic in the GNN community. WL test serves as a fundamental algorithm in guiding designing expressive GNNs. For each k-WL, it has been shown that there always exist non-isomorphic graphs that cannot be distinguished by k-WL, and thus k-WL is incomplete for any k. However, things become different for geometric graphs, which are point clouds lying on a finite d-dimensional Euclidean space and the isomorphism is characterized by isometry. This paper makes a significant contribution by proving that k-WL is complete for distinguishing (k+1)-dimensional geometric graphs. Moreover, a constructive method shows that three-iteration suffices, which contrasts to a well-known result that there exist non-isomorphic graphs that cannot be distinguished by standard k-WL within o(n) iterations where n is the number of nodes. The authors further proved that k-WL can distinguish k-dimensional geometric graphs in only one iteration.", "questions": "See the weakness part above.", "limitations": "The limitation has been clearly stated in the paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. **Fundamental problem**. I believe characterizing the upper and lower bound of k such that k-WL is complete for distinguishing d-dimensional geometric graphs is a fundamental problem. This is due to a series of reasons.\n   - First, k-WL is a very elegant algorithm and applies to geometric graphs straightforwardly.\n   - Second, there have been debates whether equivariant architectures that use coordinate-wise information is necessary for learning geometric graphs, or purely distance information suffices. This paper answers this question timely and affirmatively.\nOverall, the problem formulation is very *clean* and are likely to have decent impact in the geometric deep learning community.\n\n2. **Strong theoretical result**. After going through the proof technique, I feel that the proof is non-trivial, despite presentation is very clear, well-organized, and rigorous. After checking several of the proofs, I am confident that the proofs are correct.\n   - Related to prior works: to my knowledge, the theoretical result seems to be new. While I mainly focus on standard GNN expressivity theory, I have read several works related to this paper, such as Pozdnyakov & Ceriotti et al., Hordan et al., and Zhang et al..\n   - Regarding completeness of theoretical result: this paper only gives upper bounds on the required k for distinguishing d dimensional geometric graphs. However, the bound is tight for 2 or 3 dimensional data. Other cases are highlighted in the limitation part and left as open problems. In this sense, the contribution seems to be sufficient for an acceptance. \n\n3. **Great presentation**. This paper is very well-written and easy to read. The organization is great, the proof sketch is carefully written, and the proof in the Appendix is also well-written (I couldn't even find a typo). I really enjoy reading this paper.\n", "weaknesses": "1. This is mainly a theoretical paper, without any experimental evaluation. However, I understand that showing experimental result is not very necessary given this paper focuses on a fundamental theoretical problem.\n2. Regarding theoretical results, I have several concerns and questions. While all of them are not major weaknesses, I would like the authors to answer these questions and revise the manuscript accordingly in the camera-ready version.\n   - The authors focus on the setting where all points are distinct, i.e., S is a set rather than multiset. The proof in Line 146-157 requires such a condition. But I think similar result should hold when S is a multiset. The authors may add a brief remark to illustrate this point.\n   - The authors wrote that Hordan et al. have proved that in the same setting, the geometric 3-WL test is in fact complete. However, I cannot find this result in their paper. Instead, they consider a different algorithm that requires the coordinates as input (although the output is invariant under isometric transformation). Moreover, they also considered higher dimensions. So could the authors give an explanation for the paragraph in Line 43-49 (if I miss something)?\n   \n3. The number of related work seems to be a bit insufficient. I can list several works which I think is relevant to this paper.\n   - Martin Furer. Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations.\n     \n     This paper proved that, for any k, there exist non-isomorphic graphs that cannot be distinguished by standard k-WL within o(n) iterations where n is the number of nodes and can be distinguished by standard k-WL within $\\Theta(n)$ iterations. Moreover, the same pair of graphs can be distinguished within much fewer iterations by increasing k. These results surprisingly parallels your results.\n   - Bohang Zhang, et al.. Rethinking the Expressive Power of GNNs via Graph Biconnectivity.\n\n     This paper proposed the expressive power of generalized distance WL test, which is basically the same as 1-WL in this paper while using different distance metrics.\n\n4. Minor issue: in Line 54, the citation [12] seems to be wrong. Do you mean [13]?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Reviewer's comment: \"This is mainly a theoretical paper, without any experimental evaluation. However, I understand that showing experimental result is not very necessary given this paper focuses on a fundamental theoretical problem.\"\n\nRESPONSE: Indeed, as the referee points out, the aim of the paper is to give theoretical guarantees and proofs. It is nevertheless important to point out, however, that relevant experiments have in fact been performed by other groups, such as described in (table 1, third column from the right, in) the preprint [Li, Z., Wang, X., Huang, Y., & Zhang, M. (2023), Is Distance Matrix Enough for Geometric Deep Learning? arXiv preprint arXiv:2302.05743, (version 4)]. We shall highlight these experiments further in the camera-ready version of the paper, in case it is accepted.\n\nReviewer's comment: \"The authors focus on the setting where all points are distinct, i.e., S is a set rather than multiset. The proof in Line 146-157 requires such a condition. But I think similar result should hold when S is a multiset. The authors may add a brief remark to illustrate this point.\"\n\nRESPONSE: We thank the referee for pointing this out. While some of the wordings of the proofs include reference to the hypothesis that S is a set, the proof strategy works without changes for the extension to the case S is a multiset. In case we get accepted, we shall add this extension of the theorem statements for the final version. \n \nReviewer's comment: \"The authors wrote that Hordan et al. have proved that in the same setting, the geometric 3-WL test is in fact complete. However, I cannot find this result in their paper. Instead, they consider a different algorithm that requires the coordinates as input (although the output is invariant under isometric transformation). Moreover, they also considered higher dimensions. So could the authors give an explanation for the paragraph in Line 43-49 (if I miss something)?\"\n\nRESPONSE: Although the geometric 3-WL algorithm of Hordan et al. uses coordinates as inputs, it can be turned into a proof that 3-WL, as defined in our paper (that only uses pairwise distances) is complete in R^3 after 2 iterations. We discusse this in more detail at the beginning of Section 5, and we plan to add a reference to this in the introduction (lines 43-49) for a final version of the paper. We thank the reviewer for pointing out that Hordan et al. also consider higher dimensions. We will add a remark that the algorithm of Hordan et al., although it explicitly uses coordinates, can be turned into a proof (modulo the Barycenter lemma that we establish in our paper) that d-WL is complete in R^d after 2 iterations.\n\nReviewer's comment: \"The number of related work seems to be a bit insufficient. I can list several works which I think is relevant to this paper: \n\n- Martin Furer. Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations.\nThis paper proved that, for any k, there exist non-isomorphic graphs that cannot be distinguished by standard k-WL within o(n) iterations where n is the number of nodes and can be distinguished by standard k-WL within $\\Theta(n)$ iterations. Moreover, the same pair of graphs can be distinguished within much fewer iterations by increasing k. These results surprisingly parallels your results.\n\n- Bohang Zhang, et al.. Rethinking the Expressive Power of GNNs via Graph Biconnectivity.\nThis paper proposed the expressive power of generalized distance WL test, which is basically the same as 1-WL in this paper while using different distance metrics.\"\n\nRESPONSE: We were not aware of the above papers. They are certainly very relevant and we will cite them, and we thank the referee for pointing them out to us. \n\nReviewer's comment: \"Minor issue: in Line 54, the citation [12] seems to be wrong. Do you mean [13]?\n\nRESPONSE: Indeed, the referee is correct, we will change this citation accordingly.\n"}, {"review_id": "7EbKqFclWk", "reviewer": "Reviewer_4J2w", "summary": "The authors rigorously prove that applying the d-1 WL to the distance matrices of point clouds in d dimensions is complete: that is, two point clouds are related by an isometry (and relabeling of the points) if and only if they are not separated by the d-1 WL test", "questions": "In lines 43-49 in the discussion of Hordan et al.: The authors of that paper discuss not only a 3-WL algorithm but also what the call in the abstract `a 2-WL-like algorithm', when d=3. To avoid confusion it may be helpful  to address this claim in the discussion somehow. \n\nI had some issues with Section 6: \n(a) Firstly, defining MPGNNs for point clouds has been discussed in various ways in previous works: in  [9]-[10] cited in the paper and in \"On the expressive power of geometric graph neural networks\" by Joshi et al which should be cited as well. It would make sense to discuss the relationships to the definitions there or at least mention they exist\n(b) In the described MPGNN each x is given a `one hot encoding'. Since there are infinite possible x, how exactly is this accomplished?\n(c) I was confused at why Corollary 6.1 was stated for (d-1)-MPGNN instead of d-MPGNN. Later I saw that this is explained in lines 75-80 and is due to the differences between WL and Folklore-WL but I think it should be retierated in Corollary 6.1 \n(d) Generally, I feel like this paper does a great job re the WL tests themselves, but the discussion of MPNNs is somewhat short and non-convincing, and perhaps it would be better just to ref to the other papers mentioned above which discussed these issues in more depth (at the authors discretion, I support acceptance either way)\n\nI think the proof of Lemma 3.1 can be shortened and simplified. Once the equation in line 211 is established, you can immediately show that plugging it into the right hand side of (2), for both f(x) and f(y), gives the equality you want.\n\nWith the space the freed up, you could consider adding an illustration for the cone condition (lines 137-138)\n\nTiny comments:\nLine 129: `Algorithm' should not be capitalized\nLine 137: **line** on this line\nLine 142: Initialization Data: instead of `it consists..' I would prefer something like `the initialization data consists..'\n\n\n\n", "limitations": "Yes", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The questions the authors address is a fundamental theoretical question in the study of geometric machine learning. They give a rigorous and non-trivial proof that essentially solves the question. Very good work.  ", "weaknesses": "No significant weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Reviewer's comment: \"In lines 43-49 in the discussion of Hordan et al.: The authors of that paper discuss not only a 3-WL algorithm but also what the call in the abstract `a 2-WL-like algorithm', when d=3. To avoid confusion it may be helpful to address this claim in the discussion somehow.”\n\nRESPONSE: Both algorithms in Hordan et al. explicitly use coordinates of the points. Thus, formally, they do not fall into our framework. However, a 3-WL algorithm of Hordan et al., after additional observations, can be used to show that 3-WL, as defined in our paper, is complete in R^3 after 2 iterations (we discuss this in Section 5 where we also improve their result by showing that 3-WL is complete in R^3 after 1 iteration). At the same time, we do not see how to convert the ‘2-WL-like’ algorithm of Hordan et al. into an algorithm in our setting. Nevertheless, we will mention their ‘2-WL-like’ algorithm with these remarks in the introduction.\n\n\nReviewer's comment: “I had some issues with Section 6: \n(a) Firstly, defining MPGNNs for point clouds has been discussed in various ways in previous works: in [9]-[10] cited in the paper and in \"On the expressive power of geometric graph neural networks\" by Joshi et al which should be cited as well. It would make sense to discuss the relationships to the definitions there or at least mention they exist”  \n\nRESPONSE: We were not aware of the paper by Joshi et al. It is certainly relevant and we will cite it. Other than that, we plan to completely rewrite this section as explained in point (d) below. \n\nReviewer's comment: “(b) In the described MPGNN each x is given a `one hot encoding'. Since there are infinite possible x, how exactly is this accomplished?\" \n\nRESPONSE: We were thinking of having a one-hot encoding only with respect to the “atomic types” of mutual distances that can be achieved in the given cloud of points S. There is a finite number of them. Hence, two tuples x and y in S achieve the same one-hot encoding if and only if they have the same atomic type of mutual distances.   \n\n\nReviewer's comment: “(c) I was confused at why Corollary 6.1 was stated for (d-1)-MPGNN instead of d-MPGNN. Later I saw that this is explained in lines 75-80 and is due to the differences between WL and Folklore-WL but I think it should be retierated in Corollary 6.1\"\n\nRESPONSE: Sure, we can do that, but please see our response to the next point. \n\nReviewer's comment: “(d) Generally, I feel like this paper does a great job re the WL tests themselves, but the discussion of MPNNs is somewhat short and non-convincing, and perhaps it would be better just to ref to the other papers mentioned above which discussed these issues in more depth (at the authors discretion, I support acceptance either way)\"\n\nRESPONSE: After careful consideration, we believe that the reviewer is right. This section is too short and is not adding anything essentially new to the paper. In case we get accepted we will add a more succinct explanation saying that, by using previously established techniques, it is possible to construct efficient MPGNNs that achieve the expressive power of the WL test on clouds of points.\n\nReviewer's comment: “I think the proof of Lemma 3.1 can be shortened and simplified. Once the equation in line 211 is established, you can immediately show that plugging it into the right hand side of (2), for both f(x) and f(y), gives the equality you want.\"\n\nRESPONSE: We thank the reviewer for the suggestion: indeed, it seems to make the proof shorter and simpler. \n\nReviewer's comment: “With the space the freed up, you could consider adding an illustration for the cone condition (lines 137-138)\"\n\nRESPONSE: That’s a good idea, thanks. We will definitely add such a figure in the final version of the paper. \n"}, {"review_id": "d3DQolY2Sg", "reviewer": "Reviewer_yTgF", "summary": "This paper studies the completeness of $l$-WL test for Euclidean point sets. It shows an algorithm that certifies two Euclidean point sets of dimension $d$ are isometric using $(d-1)$-WL test, where only three iterations suffice. The results extend to $d$-WL test which only requires one iteration.\n\nThe punchline is to study \"how pair-wise distances determine the identity of all points\", which is well-developed for Euclidean scenarios. Taking the plane as an example, the proposed method shows that storing single-source all-pair distances of 2 points and the norm of the rest points suffice to uniquely reconstruct the whole point set. Such data can be obtained through several rounds of WL-test, which completes the claim that WL-test is able to distinguish the isometry of Euclidean point sets.", "questions": "See above.", "limitations": "I would say the result itself is interesting, only that as a theory paper the technical novelty is quite limited, especially if this can be done even without WL-test. The connection to GNN is in a phase of \"Good to know\" but does not seem to have application implications.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The problem is well-motivated, most of the paper is written clearly.\n- The results characterize well on three parameters involved for isometry-test of Euclidean point sets: the data dimension $d$, the WL-test dimension $l$ and number of rounds needed ($r=3$ for $l=d-1$, $r=1$ for $l=d$). It should be an interesting result to be announced.", "weaknesses": "I think overall the paper is not hard to follow, but the presentation can be better\n- The contents on page 4 and 5 would be a lot easier to understand if there is a picture. \n- The algorithms deserve a box highlighting each step either in description or pseudocode, though I personally prefer just words. \n\nAnother issue is that it seems knowing the distance profiles is sufficient for the isometry test. Then why do we have to converge to WL test? The time and space consumption of WL-test is non-trivial. Since we have the two point sets at our hand, just consider a simple algorithm calculating the profile tuple $(A, M_1, M_2, ...)$ and use the proposed reconstruction algorithm, what is wrong with this? I believe the space might be the same, but the time would be much better.\n\nminor: line 268, $d$-tuple?.\n\nAnother suggestion on Table 1.  I think using $l>d$ WL test is no longer of interest, maybe you can replace the dots with a slash. You can consider different colors for previous work, this work, and open. Last, there could be general $d$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Reviewer's comment:  \"I think overall the paper is not hard to follow, but the presentation can be better\nThe contents on page 4 and 5 would be a lot easier to understand if there is a picture.\nThe algorithms deserve a box highlighting each step either in description or pseudocode, though I personally prefer just words.\"\n\nRESPONSE:  see “GENERAL RESPONSE” in the Author Rebuttal box at the beginning. \n\nReviewer's comment: \"Another issue is that it seems knowing the distance profiles is sufficient for the isometry test. Then why do we have to converge to WL test? The time and space consumption of WL-test is non-trivial. Since we have the two point sets at our hand, just consider a simple algorithm calculating the profile tuple and use the proposed reconstruction algorithm, what is wrong with this? I believe the space might be the same, but the time would be much better.\"\n\n\nREPONSE: The reviewer is right in that the point of the paper is not to provide an efficient algorithm to test isometry between two given point clouds, but to provide a characterization of the expressive power of geometric GNN’s. In particular, it informs the practical decision related to the choice of parameters in the design of a MPGNN’s when working with d-dimensional point clouds:  order d and three layers are sufficient (as far as expressivity is concerned). \n\n"}]

Author rebuttal:
GENERAL RESPONSE:  Many thanks for your comments and suggestions. Regarding presentation, we acknowledge that adding a figure to illustrate the main idea behind the proof of our main result, as well as giving a high-level description of the underlying algorithm in a framed box, will greatly improve the presentation. In case our paper is accepted we will definitely implement all these. We now proceed to respond to the individual comments.  


Meta-review: All the reviewers agreed that the paper is well-written the problematic is important and the contributions are significant. They have also raised some concerns about improving the clarity and missing citations; however, they are rather minor concerns. Hence, I am recommending an acceptance. Please implement all the promised changes in the camera-ready version.
Decision: Accept (poster)