Is Distance Matrix Enough for Geometric Deep Learning?
Authors: Zian Li
Xiyuan Wang
Yinan Huang
Muhan Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: geometric deep learning
expressiveness
equivariant neural networks
universality

Abstract: Graph Neural Networks (GNNs) are often used for tasks involving the 3D geometry of a given graph, such as molecular dynamics simulation. While incorporating Euclidean distance into Message Passing Neural Networks (referred to as Vanilla DisGNN) is a straightforward way to learn the geometry, it has been demonstrated that Vanilla DisGNN is geometrically incomplete. In this work, we first construct families of novel and symmetric geometric graphs that Vanilla DisGNN cannot distinguish even when considering all-pair distances, which greatly expands the existing counterexample families. Our counterexamples show the inherent limitation of Vanilla DisGNN to capture symmetric geometric structures. We then propose $k$-DisGNNs, which can effectively exploit the rich geometry contained in the distance matrix. We demonstrate the high expressive power of $k$-DisGNNs from three perspectives: 1. They can learn high-order geometric information that cannot be captured by Vanilla DisGNN. 2. They can unify some existing well-designed geometric models. 3. They are universal function approximators from geometric graphs to scalars (when $k\geq 2$) and vectors (when $k\geq 3$). Most importantly, we establish a connection between geometric deep learning (GDL) and traditional graph representation learning (GRL), showing that those highly expressive GNN models originally designed for GRL can also be applied to GDL with impressive performance, and that existing complicated, equivariant models are not the only solution. Experiments verify our theory. Our $k$-DisGNNs achieve many new state-of-the-art results on MD17.

Is Distance Matrix Enough for Geometric Deep Learning?
Zian Like, Xiyuan Wangh. Yinan Huang', Muhan Zhang Institute for Artificial Intelligence, Peking University "School of Intelligence Science and Technology. Peking University
Abstract
Graph Neural Networks (GNNs) are often used for tasks involving the 3D geometry of given graph, such as molecular dynamics simulation. While incorporating Euclidean distance into Message Passing Neural Networks (referred to Vanilla DisGNN) is a straightforward way to learn the geometry, it has been demonstrated that Vanilla DisGNN is geometrically incomplete. In this work, we first construct families of novel and symmetric geometric graphs that Vanilla DisGNN cannot distinguish even when considering all- all-pair distances, which greatly expands the existing counterexample families. Our counterexamples show the inherent lim- itation of Vanilla DisGNN to capture symmetric geometric structures. We then propose k-DisGNNs, which can effectively exploit the rich geometry contained in the distance matrix. We demonstrate the high expressive power of k-DisGNNs from three perspectives: 1. They can learn high-order geometric information that cannot be captured by Vanilla DisGNN. 2. They can unify some existing well-designed geometric models. 3. They are universal function approximators from geometric graphs to scalars (when k > 2) and vectors (when k: 2 3). Most importantly, we establish a connection between geometric deep learning (GDL) and traditional graph representation learning (GRL), showing that those highly expressive GNN models originally designed for GRL can also be applied to GDL with impressive performance, and that existing complicated, equivariant models are not the only solution. Experiments verify our theory. Our k-DisGNNS achieve many new ofte-of-the--e results on MD17.
Introduction
Many real-world tasks are relevant to learning the geometric structure of given graph, such as molecular dynamics simulation, physical simulation, drug designing and protein structure predic-
tion [Schmitz al.] 2019 (Sanchez- Gonzalez al., 2020 Jumper et al., 2021 Guo et al. 2020]. Usually in these tasks, the coordinates of nodes and their individual properties, such as atomic numbers, are given. The goal is to accurately predict both invariant properties, such as the energy of the molecule, and equivariant properties, such the force acting on each atom. This kind of graphs also referred to as geometric graphs by researchers [Brostein et al. 202T Han al,, 2022).
In recent years, Graph Neural Networks (GNNs) have achieved outstanding performance on such tasks, as they can learn representation for each graph node in an end-to-end fashion, rather than relying on handcrafted features. In such setting, straightforward idea is to incorporate Euclidean distance, the most basic geometric feature, into Message Passing Neural Network (Gilmer al.) 2017) (we call these models Vanilla DisGNN) (Schütt et al., 2018 Kearnes et al.] [016]. While Vanilla DisGNN simple yet powerful when considering all-pair distances (we assume all-pair
"Corresponding author: Muhan Zhang (muhan (.nbaan@ku..ed.cc))
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

distance is used by default to research a model's maximal expressive power), it has been proved to be geometrically incomplete [Zhang et al. |021 Garg et al. 2020 Schütt et al. 2021 Pozdnyakov and Ceriotii [022]. i.e., there exist pairs of geometric graphs which Vanilla DisGNN cannot distinguish. It has led to the development of various GNNs which go beyond simply using distance as input. Instead, these models use complex group irreducible representations, first-order equivariant representations or complex invariant geometric features such as angles or dihedral angles to learn better representations from geometric graphs. It is generally believed that pure distance information is insufficient for complex GDL tasks [Klicpera et al. 2020a SSchitt et al. 2021].
On the other hand, it is well known that the distance matrix. which contains the distances between all pairs of nodes geometric graph, holds all of the geometric structure information [Satorras et al.) 2021]. This suggests that it is possible to obtain all of the desired geometric structure information from distance graphs, i.e., complete weighted graphs with Euclidean distance as edge weight. Therefore, the complex GDL task with node coordinates as input (i.e., 3D graph) may be transformed into an equivalent graph representation learning task with distance graphs as input (i.e., 2D graph).
Thus, desired question is: Can we design theoretically and experimentally powerful geometric models, which can learn the rich geometric patterns purely from distance matrix?
In this work, we first revisit the counterexamples in previous work used to show the incompleteness of Vanilla DisGNN. These existing counterexamples either consider only finite pairs of distance (a cutoff distance is used to remove long edges) (Schütt et al., 2021] Zhang et al.) 2021 Garg et al.) 2020), which can limit the representation power of Vanilla DisGNN, lack diversity thus may not effectively reveal the inherent limitation of Vanilla DIsGNN (Pozdnyakov and Ceriotti 2022). In this regard, we further constructed plenty of novel and symmetrie counterexamples, as well as novel method to construct families of counterexamples based on several basic units. These counterexamples significantly enrich the current set of counterexample families, and can reveal the inherent limitations of MPNNs in capturing symmetric configurations, which can explain the reason why they perform badly in real-world tasks where lots of symmetric (sub-)structures are included.
Given the limitations of Vanilla DisGNN, we propose k-DisGNNs, models that take pair- distance as input and aim for learning the rich geometric information contained in geometric graphs. k-DisGNNs are mainly based on the well known k-IF)WL. test (Cai et al. 1992), and include three versions: k-DisGNN, k-F-DisGNN and k-E-DisGNN. We demonstrate the superior geometric learning ability of k-DisGNNs from three perspectives. We first show that k- D-DiGNNNs can capture arbitrary k- or (K- + 1) -order geometric information (multi-node features), which cannot be achieved by Vanilla DisGNN. Then, we demonstrate the high generality of our framework by showing that k-DisGNNS can implement DimeNet (Klicpera et al. 2020a] and GemNet [Gatteiger al. [02]], }, two well-designed state-of-the-art models. A key insight is that these two models are both augmented with manually-desigme high-order geometric features, including angles (three-node features) and dihedral angles (four-node features), which correspond to the k-tuples in k- O-DisGNNs. However, k- 4-DisGNNs can learn more than these handcrafted features in an end-to-end fashion. Finally, we demonstrate that k- DisGGNNs can act as universal function approximators from geometric graphs to scalars (i.e., E(3) invariant properties) when & 2 2 and vectors (i.e., first-order 0(3) equivariant and translation invariant properties) when k 2 3. This essentially answers the question posed in our title: distance matrix sufficient for GDL. We conduct experiments on benchmark datasets where our models achieve state-of bate-of-theeart results on wide range of the targets in the MD17 dataset.
Our method reveals the high potential of the most basic geometric feature, distance. Highly expressive GNNs originally designed for traditional GRL can naturally leverage such information as edge weight, and achieve high theoretical and experimental performance in geometric settings. This opens up a new door for GDL research by transferring knowledge from traditional GRL, and suggests that existing complex, equivariant models may not be the only solution.
2 Related Work
Equivariant neural networks. Symmetry is a rather important design principle for GDL [Bronstein] ett al., 2021]. In the context of geometric graphs, desirable for models to be equivariant or
invariant under the group (such as E(3) and SO(3)) actions of the input graphs. These models include
those using group irreducible representations [Thomas et al. 2018 Batzner et al. 2022 Anderson
et al. 2019 Fuchs et al. 2020]. complex invariant geometric features (Schütt et al. 2018 Klicpera

---

et a..
2020a Gasteiger et al., [021] and first-order equivariant representations [Satorras et al. 2021
Schütt et al. 2021 Thölke and De Fabritiis 2021]. Particularly, Dym and Maron [0020] proved that both Thomas et al. [2018] Fuchs et al. [2020 are universal for SO(3)-equivariant functions. Besides, Villar et al. [021 showed that one could construct powerful (firtt-oder) equivariant outputs
by leveraging invariances, highlighting the potential of invariant models to learn equivariant targets.
GNNs with distance. In geometric settings, incorporating 3D distance between nodes as edge weight is simple yet efficient way to improve geometric learning. Previous work [Maron et al.) 2019
Morris et al. 2019 Zhang and Li 2021 Zhao et al. 2022] mostly treat distance as an auxiliary edge feature for better experimental performance and do not explore the expressiveness or performance of using pure distance for geometric learning. |Schit et al. (2018) proposes to expand distance using a radial basis function as a continuous-file
and perform convolutions on the geometric graph, which can be essentially unified into the Vanilla DisGNN category. ZZang et al. [022]] J. Garg et al.
[,020], (Schütt et al. [202T]. Pooddyykovv and Ceriotti [2022] demonstrated the limitation of Vanilla DisGNN by constructing pairs non-congruent geometric graphs which cannot be distinguished by it, thus explaining the poor performance of such models (Schütt et al.] 2018 Kearnes et al., 20166). However, none of these studies proposed a complete purely distance-based geometric model. Recent work [Hordan et al. 2023 proposed theoretically complete GNNs for distinguishing geometric graphs, but they go beyond pair-wise distance and instead utilize gram matrices or coordinate projection.
Expressive GNNs. In traditional GRL (no 3D information), it has been proven that the expressiveness of MPNNs is limited by the Weisfeiler-Leman test (Weisfeiler and Leman 1968 Xu al.. 2018
Morris et al., 2019), classical algorithm for graph isomorphism test. While MPNNs can distinguish
most graphs (Babai and Kucera 1979]. they are unable to count rings, triangles, or distinguish regular
graphs, which are common in real-world data such as molecules (Huang et al. 2202). To increase the
expressiveness and design space of GNNs, MMoris et al. [019 2020 proposed high-order GNNs based on k-WL. et al. [019 designed GNNs based on the folklore WL (FWL) test [Cai et al. 1992] and Azizian and Le aarge 2020] showed that these GNNs are the most powerful GNNs for a given tensor order. Beyond these, there are subgraph GNNs (Zhang and Li [02T Bevilacqua et al.
2021 Frasca et al. 2022 Zhao et al. 2021]. substructure- based GNNs [Bouritsas et al., [222 Horn al. 202 Bodnar et al. 202 and so on, which are also strictly more expressive than MPNNs. For
a comprehensive review on expressive GNNs, we refer the readers to Zhang et al. 22033.
More related work can be referred to Appendix E
3 Preliminaries
In this paper, we denote multiset with B. We use [n]] to represent the set {1, 2,.,,..., n]. weighted graph with nodes is denoted by G = (V, E), where V = [n]] and E [eay] (xn R The neighborhoods of node i are denoted by (1)..
A complete
Distance graph vs. geometric graph. In many tasks, we need to deal with geometric graphs, where each node attached with its 3D coordinates x; E R3 in addition to other invariant features. Geometric graphs contain rich geometric information useful for learning chemical or physical properties. However, due to the significant variation of coordinates under E(3) transformations, they can be redundant when it comes to capturing geometric structure information.
Corresponding to geometric graphs are distance graphs, i.c., complete weighted graph with Euclidean distance as edge weight. Unlike geometric graphs, distance graphs do not have explicit coordinates attached to each node, but instead, they possess distance features that are naturally invariant under E(3) transformation and can be readily utilized by most GNNs originally designed for traditional GRL. Distance also provides an inherent inductive bias for effectively modeling the interaction/reaationnhhp between nodes. Moreover, a distance graph maintains all the essential geometric structure information, as stated the following theorem:
Theorem 3.1. [Satorras et al. 2021] Two geometric graphs are congruent (i.e., they are equivalent by permutation of nodes and E(3) transformation of coordinates) + their corresponding distance graphs are isomorphic.
By additionally incorporating orientation information, we can learn equivariant features as well (iillar al. 2021). Hence, distance graphs provide way to represent geometrie graphs without referring to canonical coordinate system. This urges to study their full potential for GDL.
3

---

Weisfeiler-Leman Algorithms. Weisfeiler-Lehmal test (also called as 1-WL) Weisfeiler and Leman [968] is a well-known efficient algorithm for graph isomorphism test (traditional setting, no 3D information). It iteratively updates the labels of nodes according to nodes' own labels and their neighbors' labels, and compares the histograms of the labels to distinguish two graphs. Specifically, we use 14 to denote the label of node at iteration i, then 1-WI. updates the node label by
(I) where HASH is an injective function that maps different inputs to different labels. However, 1-WL cannot distinguish all the graphs (Zhang and Li, 202I], and thus k-dimensional WL (k-WL) and k-dimensional Folklore WL (k-FWL), A 2 2, are proposed to boost the expressiveness of WL test.
G+1 HASH(!, U0 j E B))
Instead of updating the label of nodes, A-WL and k-FWL update the label of k-tuples (V1, 1/2, ..., Ux) E V denoted by 4. Both methods initialize k-tuples' labels according to their isomorphic types and update the labels iteratively according to their j-neighbors N1).). The dif- ference between k-WL and A-FWLL mainly lies in the definition of (w). To be specific, tuple v's j-neighbors in k-WL and k-FWL, are defined as follows respectively
N₂ (v) = [(111..... 1- w, fj+1....., U%) w E V
(2)
Nff(0 (v) (Li, ..., 2k), (11, J.... vx), .... (u1, 222 .... 1)).
(3)
To update the label of each tuple, kL and k-FWL iterates as follows
k-WL: : 4
[[+1 HASH (,, (f
w E N i E [+)).
(4)
k-FWL: : 0
ge1
HASH 1, (1t,. w E Nf 1 E (III)).
(5)
[992]. there always exists pair of non-isomorphic graphs that cannot be distinguished by (LL but can be distinguished by (k: + 1)- This means that W-L forms strict hierarchy, which, however, still cannot solve the graph isomorphism problem with finite k:
According to Cai et al.
4 Revisiting the Incompleteness of Vanilla DisGNN
As mentioned in previous sections, Vanilla DisGNN is the edge-enhanced version of MPNN, which can unify many model frameworks [Schütt al. 20188] Kearnes et al.) 2016). Its message passing formula can be generalized from its discrete version, which we call 1-WL-E (oozdnykkov and Ceriotii 2022
e+ HASH(C, e(G) Jj E (V]B).
(6)
To provide valid counterexamples that Vanilla DisGNN can- not distinguish, PPozdnyakov and Ceriotti [0022) proposed both finite-size and periodic counterexamples and showed that they included real chemical structures. This work demonstrated for the first time the inherent limitations of Vanilla DisGNN. However, it should be noted that the essential change between these counterexamples is merely the distortion of C atoms, which lacks diversity despite having high manifold dimensions. In this regard, constructing new families of counterexamples cannot only enrich the diversity of existing families, but also demonstrate Vanilla DisGNN's limitations from different an- gles.
A pair of geometric graphs that are non-congruent but cannot be distinguished by Vanilla DisGNN. Only red nodes belong to the two geometric graphs. The grey nodes and the "edges" are for visu- alization purpose only. Note that the nodes of the geometric graphs are sampled from regular icosahe- drons.
Figure 1:
In this paper, we give a simple valid counterexample which Vanilla DisGNN cannot distinguish even with an infinite cutoff, as shown in Figure [ In both geometric graphs, all nodes have exactly the same unordered list of distances (infinite cutoff con- sidered), which means that Vanilla DisGNN will always label them identically. Nevertheless, the two geometric graphs are obviously non-congruent, since there are two small equilateral triangles on the right, and zero on the left. Beyond this, we construct three kinds of counterexamples in Appendix [A] which can significantly enrich the counterexamples found by Pozdnyakov and Ceriotti 2022), including:

---

1. Individual counterexamples sampled from regular polyhedrons that can be directly verified.
2. Small families of counterexamples that can be transformed in one dimension.
3. Families of counterexamples constructed by arbitrary combinations of basic symmetrie units.
These counterexamples further demonstrate the incompleteness of Vanilla DisGNN in learning the geometry: even quite simple geometric graphs as shown in Figure | cannot be distinguished by it. While the counterexamples we constructed may not correspond to real molecules, such symmetric structures are commonly seen in other geometry releeatt-relevant tasks, such as physical simulations and point clouds. The inability distinguish these symmetric structures can have a significant impact on the geometric learning performance of models, even for non-degenerated configurations, as demonstrated by Pozdnyakov and Ceriotti [2022]. This perspective can provide an additional explanation for the poor performance of models such as SchNet (Schütt et al. 2018 and inspire the design of more powerful and efficient geometric models.
k-DisGNNs: k-order Distance Graph Neural Networks
In this section, we propose the framework of B-DisGNNS, complete and universal geometric models learning from pure distance features. k-DisGNNS consist of three versions: h-DisGNN, k-F-DisGNN, and k-E-DisGNN. Detailed implementation is referred to Appendix C
Initialization Block. Given a geometric k-tuple v. high-order DisGNNs initialize it with an injective
function by hy finit (Z., E [k:),, (erçe, ú E [k), < E IR where K is the hidden dimension. This function can injectively embed the ordered distance matrix along with the 2 type of each node within the k-tuple, thus preserving all the geometric information within it.
Message Passing Block. The key difference between the three versions of high-order DisGNNs lies in their message passing blocks. The message passing blocks of k- B-DisGNN and k-F-DisGNN based on the paradigms of k-WL and k-FWLL, respectively. Their core message passing function K
and FF MP are formulated simply by replacing the discrete tuple labels ( in WLL (Equation
5
with continuous geometric tuple representation 14 E R see Equation 7 8) Tuples containing
local geometric information interact with each other in message passing blocks, thus allowing models
to learn considerable global geometric information (as explained in Section 6.1.
k DiSGGNN ho+1 Shar (hhr, (Hh w (,( 1 1 F. k-F - DisGNN NC+1 = fuL (ho, fl (M Ef(()) 1 E [|VI1B).
(8)
However, during message passing in k-DisGNN, the information about distance is not explicitly used but is embedded implicitly in the initialization block when each geometric tuple is embedded according to its distance matrix and node types. This means that k- B-DisGNN is unable to capture the relationship between a k-tuple v and its neighbor w during message passing, which could be very helpful for learning the geometric struetural information of the graph. For example, in a physical system, a tuple w far from v should have much less influence on u than another tuple w near v.
Based on this observation, we propose k-E-DisGNN, which maintains a representation ety for each edge Eg at every time step and explicitly incorporates it into the message passing procedure. The edge representation ety is defined as
c/ = fc (1h
w V w. = w. = j}
| u, [6),,<+))) v))
<
(9)
Note that ely not only contains the distance between nodes and j. but also pools all the tuples related edge ij, making it informative and general. For example, in the special case ie Equation equivalent to efy- (e Mty).
We realize the message passing function of k K-E-DisGNN, MMP by replacing the neighbor represen- tation, hi in p with (hi ( where v' w gives the only element but not in w, see Equation 10 In other words, et w. gives the representation of the edge connecting v, By this means, tuple can be aware of how far it is to its neighbors and by what kind of edges each neighbor
5

---

(AI)
(A2)
(B1)
(B2)
Figure 2: A: High-order geometric information contained in the distance matrix of k-tuples. We mark different orders with different colors, with brown, green, blue for 2-re-,4-order respectively. (AI) High-order geometric information contained in 4-tuples, including distances, angles and dihedral angles. (A2) More 3-order geometric features, such as vertical lines, middle lines and the area of triangles. B: Examples explaining that neighboring 3-tuples can form a 4-tuple Blue represents the center tuple, the other colors represent neighbor tuples, and the red node is the one node that neighbor tuple which is not in the center tuple. (B1) Example for 3-E-DisGNN, With the green edge, two 3-tuples can form a 4-tuple. (B2) Example for 3-F-DisGNN, Four 3-tuples form 4-tupee
connected. This can boost the ability of geometric structure learning (as explained in Section 6.1
k-E DiSGNN hot1 - h/, (H (m) w E (
[k])
(10)
Output Block. The output function = fout (? v U V*B). where I' is the final iteration, injectively pools all the tuple representations, and generates the E(3) and permutation invariant geometric target t E IR.
Like the conclusion about k-LFWWL for unweighted graphs, the expressiveness (in terms of approxi- mating functions) of DisGNNs does not decrease as l increases. This simply because all k-tuples contained within some (K: + 1)-tuples, and by designing message passing that ignores the last index, we can implement k-DisGNNs with (k: + -)DDiGGNNS.
6 Rich Geometric Information Learned by k-DisGNNs
In this section, we aim to delve deeper into the geometry learning capability of k-DisGNNs from various perspectives. In Subsection 6.1 we will examine the high-order geometric features that the models can extract from geometric graphs. This analysis more intuitive and aids in comprehending the high geometric expressiveness of k-DisGNNs. In Subsection [.2]] we will show that DimeNet and GemNet, two classical and widely-used GNNs for GDL employing invariant geometric representations, are special cases of k- D-DisGNNs. highlighting the generality of k-DisGNNs. In the final subsection, we will show the completeness (distinguishing geometric graphs) and universality (approximating functions over geometric graphs) of k-DisGNNs, thus answering the question posed in the title: distance matrix is enough for GDL.
6.1 Ability Learning High-Order Geometry
We first give the concept of high-order geometric information for better understanding. Definition 6.1. k-order geometric information is the E(3)-invariant features calculable from k nodes' 3D coordinates.
For example, in a 4-tuple, (2-order), angles (3-order) and dihedral angles (4-order), as shown Figure AAI). Note that high- order information is not limited to the common features listed above: we show some of other possible 3-order geometric features in Figure 2 A22).
find various high-order geometric information, including distance
We first note that 4-DisGNNs can learn and process at least k-order geometric information. Theo- rem 3.I states that we can reconstruct the whole geometry of the k-tuple from the embedding of its distance matrix. In other words, we can extract all the desired k-order geometric information solely from the embedding of the k-tuple's distance matrix, which is calculated at the initialization step of k D-DiGNNNs, with learnable function.

---

Furthermore, both k-E-DisGNN and K-F-DisGNN can actually learn (k + 1 -order geometric infor- mation in their message passing layers. For k-E-DisGNN, information about A Aw Gn where w is some j-neighbor of v, is included in the input of its update function. Since the distance matrices of tuples v and un can be reconstructed from he and hww the all-pair dis- tances of (V1, v2,...., Uk: u)) can be reconstructed from (he hww Cel we) as shown in Fig- ure BI) Similarly, the distance matrix of (v1. U2 .... Dx. can also be reconstructed from (Ne, (he w E Nf (u))) in update function of k-F-DisGNN as shown in Figure B2). These enable k-E-DisGNN and k-F-DisGNN to reconstruct all (k + 1)-tuples' distance matrices during message passing and thus learn all the (k + 1)-order geometric information contained in the graph.
With the ability to learn bigh-order geometric information, k-DisGNNS can learn geometric structures that cannot be captured by Vanilla DisGNNs. For example, consider the counterexample shown in Figure | The two geometric graphs have a different number of small equilateral triangles, which cannot be distinguished by Vanilla DisGNNs even with infinite message passing layers. However, 3-DisGNN and EE/F-DisGNN can easily distinguish the graphs by counting the number of small equilateral triangles, which is actually kind of 3-order geometric information. This example also illustrates that high-order DisGNNs are strictly more powerful than Vanilla DisGNNs.
6.2 Unifying Existing Geometric Models with DisGNNs
There have been many attempts to improve GDL models by manually designing and incorporating high-order geometric features such angles (3-order) and dihedral angles (4-order). These features are all invariant geometric features that can be learned by some k-DisGNNs. It is therefore natural to ask whether these models can be implemented by k D-DiGGNNs In this subsection, show that two classical models, DimeNet [Klicpera et al. 2020a] and GemNet [Gasteiger et al.) 200T)) are just special cases of k-DisGNNs, thus unifying existing methods based on cand-crafted features with learning paradigm that learns arbitrury high-order features from distance matrix.
DimeNet embeds atom i with set of incoming messages mjts i.c., h4 ESEN, mys and updates the message mjj by
++1 m
SMP ( Σ k
Put (mig djc okj:)),
(1I)
where djs is the distance between node j and node i, and Φkjs is the angle kjj. We simplify the subscript of Σ, same for that in Equation (12). The detailed ones are referred to Appendix B.2 B.1
DimeNet is one early approach that uses geometric features to improve the geometry learning ability of GNNs, especially useful for learning the angle-relevant energy or other chemical properties. Note that the angle information that DimeNet explicitly incorporates into its message passing function is actually kind of 3-order geometrie information, which can be exploited from distance matrices by our 2-E//FDDiSNN with a learning paradigm. This gives the key insight for the following proposition.
Proposition 6.2. 2-E D-DiGsGNN and 2-F DisGNN can implement DimeNet.
GemNet also graph neural network designed to process graphs embedded in Euclidean space. Unlike DimeNet, GemNet incorporates both angle and dihedral angle information into the message passing functions, with a 2-step message passing scheme. The core procedure as follows:
1+1 maa
SGG (mica
Σ b,d
fla (m'ae, dab. Deab, Dabd. @eabd))
(12)
where Beabd is the dihedral angle of planes cab and abd. The use of dihedral angle information allows GemNet to learn at least 4-order geometric information, making much more powerful than models that only consider angle information. We now prove that GemNet is just special case of 3-E/F-DisGNN, which can also learn 4-order geometric information during its message passing stage.
Proposition 6.3. 3-E-DisGNN and 3-F-DisGNN can implement GemNet.
is worth noting that while both k-DisGNNs and existing models can learn some k-order geometric information, k-DisGNNs have the advantage of learning arbitrary k-order geometric information. This means that we can learn different high-order geometric features according to specific tasks in data-driver manner, including but not limited to angles and dihedral angles.
7

---

6.3 Completeness and Universality of k-DisGNNs
We have provided an illustrative example in Section 6.1 that demonstrates the ability of k- k-DisGNNS to distinguish certain geometric graphs, which is not achievable by Vanilla DisGNNs, Actually, all counterexamples presented Appendix can be distinguished by 3-DisGNNs or 2-E/F-DisGNNs. This leads to natural question: Can k- D-DisGNNs distinguish all geometric graphs with finite and small value of k? Furthermore, can they approximate arbitrary functions over geometric graphs?
We now present our main findings that elaborate on the completeness and universality of k-DisGNNS with finite and small k, which essentially highlight the high theoretical expressiveness of k-DisGNNS.
Theorem 6.4. (informal) Let M(0) E MinMods [l-round 4-DisGNN, 2-round 3-F/F-DisGNN) with parameters 0. Denote hm fuode ( k vo mD) E RK' node m 's representation produced by M where fuode is an injective multiset function, and xm as node m m's coordinates w.r.t.
the center. Denote MLPs R.K' - IR. as a multi-layer perceptron. Then we have:
1. (Completeness) There exists On such that M(00) can distinguish all pairs of non-congruent geometric graphs.
2. (Universality for scalars) M(0) is universal function approximator for continuous, E(3) and permutatiin invariant functions R3xx -> RR over geometric graphs.
3. (Universality for vectors) jequiv = EMVL MLP X a universal funttiooo approximator for continuous, ((3) equivariant and translation and permulation invariant finctions
R3xa + R over geometric graphs.
In fact, completeness directly implies universality for sealars (Hordan al. 2023 Since we can actually recover the whole geometry from arbitrary node representation /tm. universality for vectors can be proved with conclusions from Villar et al. [2021]. Also note that as order and round number go higher, the completeness and universality still hold. Formal theorems and detailed proof are provided in Appendix B.3
There is a concurrent work by Delle Rose et al. 2023 which also investigates the completeness of k-WL distance graphs. In contrast to approach of using only one tuple's s final representation to reconstruct the geometry, they leverage all tuples' final representations. They prove that with the distance matrix, 3-round geometric 2-FWL and I-round geometric 3-FWL are complete for geometry. This conclusion can also be extended to k-DisGNNs, leading to the following theorem:
Theorem 6.5. The completeness and universality for scalars stated in Theorem 6.4 hold for M(0) MinModsext 33-ruund 2 2-E/F- E/FNND,G 1-round SF/F-DisNNN with parameters O.
This essentially lowers the required order k for achieving universality on scalars However, due to the lower order and fewer rounds, the expressiveness of single node's representation may be limited, thus the universality for vectors stated in Theorems 6.4 may not be guaranteed.
7 Experiments
In this section, we evaluate the experimental performance of k-DisGNNs. Our main objectives are to answer the following questions:
Q1 Does 2/3-E/F-DisGNN outperform their counterparts in experiments (corresponding to Sec- tion 6.2h?
Q2 As universal models for sealars (when 2 2), do k-DisGNNs also have good experimental
performance (corresponding to Section 6.3
Q3 Does incorporating well-designed edge representations in the k-E-DisGNN result in improved performance?
The best and the second best results shown in bold and underline respectively in tables. Detailed experiment configuration and supplementary experiment information can be found in Appendix D Our code is available htttthtt///// http:://ggttttttee com/ GraphPKU/DisCUN
MD17. MD17 [Chmiela et al. 2017 is dataset commonly used to evaluate the performance of machine learning models in the field of molecular dynamics. It contains collection of molecular

---

Table I: MAE loss on MD17. Energy (E) in kcal/mol, force (F) in kcal/mol/A. We color the cell if DisGNNs outperforms its counterpart. The improvement ratio is calculated relative to DimeNet.
k- DisGNNN rank top 2 on force prediction (which determines the accuracy of molecular dynam- ics GGatteiger et al. 2021) on average.
Target
FCHL
PaINN
NequiP
TorchMD
GNN-LF
DimeNet
2F-Dis.
GemNet
3E-Dis.
0.182
0.167
0.124
0.1342
0.204
0.1305
0.1466
aspirin
0.478
0.338
0.348
0.255
0.2018
0.499
0.1393
0.2168
0.2060
0.056
0,0686
0.078
0.0683
0.0795
benzene
0.187
0.201
0.1506
0.187
0.1474
0.1453
0.1471
E
0.054
0.064
0.054
0.0520
0.064
0.0502
0.0541
cthanol
F
0.136
0.224
0.208
0,116
0.0814
0.230
0.0478
0.0853
0.0617
0,081
0.091
0.079
0.0764
0.104
0,0730
0.0739
malonal.
0.245
0.319
0.337
0.176
0.1259
0.383
0.0786
0.1545
0.0974
napthal.
0.117
0.166
0.085
0.1136
0.122
0.1146
0.1135
F
0.151
0.U77
0.097
0.06
0.0550
0.215
0.0518
0.0553
0,0478
E
0.114
0.166
0.094
0.1081
0.134
0.70
0. 1084
salicyl.
F
0.221
0.195
0.238
0.135
0.1005
0.374
0.0862
0.1048
0.1186
0,098
0.095
0.074
0.0930
0.102
0.0922
0.1004
toluene
0.203
0.094
0.101
0.066
0.0543
0.216
0.0395
0.0600
0,0455
uracil
0.104
0.106
0.096
0.1037
0.115
O. 1036
0.1037
F
0.105
0.139
0.173
0.094
0,0751
0.301
0,0876
0.0969
0.0921
Avg improv.
T1.58%
-2.09%
26.40%
17.05%
0.00%%
18.18% 2
13.51%
Rank
5
3
6
4
Avg improv.
31.85%
39.13%
29.86%
52,40%
63.53%
0.00% 9
69.68% 1
60,96% 4
65.27%
F
Rank
2
dynamics simulations of small organic molecules such aspirin and ethanol. Given the atomic numbers and coordinates, the task is to predict the energy of the molecule and the atomic forces. We mainly focus the comparison between D.-DiiiNNN/3-E-DisSNN and DimeNet/GemNet.. At the
same time. we also compare k- DiDiGNNN with the state-of saate-of-thh-eeee the-art models: FCHL [Christensen et al.
2020), PaiNN (Schütt et al. [021], NequlP [atznnr al.) 2022], TorchMD (Thölke and De Fabritiis 202T]. GNN-LF [Wang and Zhang 2022 The results are shown in Table !J 2-F-DisGNN and 3-E-DisGNN outperform their counterparts on 16/16 and 6/8 targets, respectively, with an average improvement of 43.9% and 12.23%, suggesting that data-driven models can subsume carefully designed manual features given high expressiveness. In addition, k-DisGNNS also achieve the best performance on 8/16 targets, and achieve the second-best performance on all the other targets, outperforming the best baselines GNN-LF and TorchMD by 10. 19% and 12.32%, respectively. Note that GNN-LF and TorchMD are all complex equivariant models. Beyond these, we perform experiments on revised MD17, which has better data quality, and k-DisGNNs outperforms the SOTA wide range of targets. The results are referred to Appendix D.2] The results firmly answer Q1 and Q2 posed at the beginning of this section and demonstrate the potential of pure sasaance-bbsed methods for graph deep learning.
models [Batatia et al.) 2022 Musaclian et al., 2023]
QM9. QM9 [Ramakrishnan al.) 2014 Wu et al., 2018 consists of 1 134k stable small organic molecules with 19 regression targets. The task is like that in MD17, but this time we want to predict the molecule's 's properties such as the dipole moment. We mainly compare 2-F-DNGGNN with DimeNet on this dataset and the results are shown in Table 2-F-DisGNN outperforms DimeNet targets, by 14.27% on average, especially on targets μ (65.0%) and (R²) (90.4%), which also answers Q1 well. A full comparison to other state-of-the-arr models is included in Appendix D.2]
11/12
Effectiveness of edge representations. To answer Q3, we split the edge representation ei (Equa- tion (D) into two parts, namely the pure distance (the first element) and the tuple representations (the second element), and explore whether incorporating the two elements is beneficial. We conduct experiments on MD17 with three versions of 2- 2-DisGNNs, including 2-DisGNN (no edge represen- tation), 2-e-DisGNN (add only edge weight) and 2-E- --DGGNN (add full edge representation). The results are shown in Table 3 Both 2-e-DisGNV and 2-E B-E-DiGGNN exhibit significant performance improvements over 2-DisGNN, highlighting the significance of edge representation. Furthermore, 2-F-DisGNN outperforms 2-DisGNN and 2-e- on 16/16 and 12/16 targets, respectively, with average improvements of 39.99.... 99.8% and 3.8%. This verifies our theory that captuiig the full edge representation connecting two tuples can boost the model's 's representation power.

---

Table 3: Effectiveness of edge representations on MD17. Energy (E) in kcal/mol, force (F)
in kcal/mol/A.
Table 2: Comparison of 2-F-DisGNN and
DimeNet on QM9.
Target
2-Dis.
2e-Dis.
2E-IDss.
E
0.2120
0.1362
0.1280
Target
Unit
DimeNet
2F-Dis.
aspirin
F
0.4483
0.1749
0.1279
D
0.0286
0.0100
E
0.1533
0.0723
0.0700
a
ag
0.0469
0.0431
benzene
F
0.2049
0.1475
0.1529
еHооо
meV
27.8
21.81
E
0.0529
0.0506
0.0502
éLUM
meV V
19.7
21.22
ethanol
0.0850 F
0.0533
0.0438
Ae
meV
34.8
31.3
0.0868
0.0736
0.0732
R
of
0.331
0.0299
malonal.
F
0.2124
0.0981
0.0861
ZPVE
meV
1.29
1.26
0.1163
0.1133
0.1149
UO
meV
8.02
7.33
napthal.
F
0.1318
0.0407
0.0531
U
meV
7.89
7.37
E
0.1209
0.1089
0.1074
H
meV
8.11
7.36
salicyl.
F
0.2723
0.0960
0.0806
G
meV
8.98
8.56
0.1437
0.0924
0.0920
Cv
cal/mol/K
0.0249
0.0233
toluene
F
0.1229
0.0528
0.0431
0.1152
0.1041
0.1037
uracil
F
0.2631
0.0874
0.0933
Conclusions and Limitations
Conclusions. In this work we have thoroughly studied the ability of GNNs to learn the geometry of a graph solely from its distance matrix. We expand the families of counterexamples that Vanilla DisGNNs are unable to distinguish from their distance matrices by constructing families of symmetric and diverse geometric graphs, revealing the inherent limitation of Vanilla DisGNNs in capturing symmetric configurations. To better leverage the geometric structure information contained in distance graphs, unify two classical and widely-used models, DimeNet and GemNet), provable completeness (ability distinguish all pairs of non-congruent geometric graphs) and universality (ability to universally approximate scalar functions when k: 2 and vector functions when k 2 3). In experiments, k-DisGNNs outperformed previous state-of-the-att models on wide range of targets of the MD17 dataset. Our work reveals the potential of using expressive GNN models, which were originally designed for traditional GRL, for the GDL tasks, and opens up new opportunities for this domain.
proposed k-DisGNNs, geometric models with high generality (ability to
Limitations. Although DisGNNs can achieve universality (for scalars) with a small order of 2, the results still generated under the assumption that the distance graph is complete. In practice, for large geometric graphs such as proteins, this assumption may lead to intractable computation due to the Onn²) time complexity and O space complexity. However, universality and experimental tractability by using either an appropriate cutoff, which can furthest preserve the completeness of the distance matrix in local clusters while cutting long dependencies to improve efficiency (and generalization), or using sparse but expressive GNNs such as subgraph GNNs [Zhang and 2021]. We leave it for future work.
can still balance theoretical
Acknowledgement
Muhan Zhang is partially supported by the National Natural Science Foundation of China (62276003) and Alibaba Innovative Research Program.
References
Gunnar Schmitz, Ian Heide Godtliebsen, and Ove Christiansen. Machine learning for potential energy surfaces: An extensive database and assessment of methods. The Journal of chemical physics, 150 (24):244113, 2019.
10

---

Alvaro Sanzaez-Gonzalez, Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovec, and Peter Battaglia. Learning to simulate complex physics with graph networks. International Conference on Machine Learning, pages 8459-8446 8468. PMLR, 2020.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool. Russ Bates, Augustin Zidek, Anna Potapenko, al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873)
2021.
Yulan Guo, Hanyun Wang. Qingyong Hu, Hao Liu, Li Liu, and Mohammed Bennamoun. Deep learning for 3d point clouds: A survey. IEEE transactions on pattern analysis and machine intelligence, 43(12):4338-4333 4364, 2020.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104. 13478, 2021.
J. Han, Y. Rong, T. Xu, and W. Huang. Geometrically equivariant graph neural networks: A survey. 2022.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272. PMLR, 2017.
Kristof T Schütt, Huziel E Sauceda, P-J Kindermans, Alexandre Tkatchenko, and K-R Müller. Schner-a deep learning architecture for molecules and materials. The Journal of Chemical Physics, 148(24)244122, 2018.
Steven Kearnes, Kevin McCloskey, Mare Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of computer-aided molecular design, 30: 595-608, 2016.
Yaolong Zhang, Junfan Xia, and Bin Jiang. Physically motivated recursively embedded atom neural networks: incorporating local completeness and nonlocality. Physical Review Letters, 127(15): 156002, 2021.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pages 3419-3430. PMLR, 2020.
Kristof Schütt, Oliver Unke, and Michael Gastegger. Equivariant message passing for the prediction of tensorial properties and molecular spectra. In International Conference on Machine Learning, pages 9377-9388. PMLR, 2021.
Sergey N Pozdnyakov and Michele Ceriotti. Incompleteness of graph convolutional neural networks for points clouds in three dimensions. arXiv preprint arXiv:2201.07133, 2022.
Johannes Klicpera, Janek Groß, and Stephan Günnemann. Directional message passing for molecular graphs. arXiv preprint arXiv:2003.03/23 2020a.
Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E (n) equivariant graph neural networks. In International conference on machine learning, pages 9323-9332. PMLR, 2021.
Jin Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389 410, 1992.
Johannes Gasteiger, Florian Becker, and Stephan Günnemann. Gemnet: Universal directional graph neural networks for molecules. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and
J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 6790-6802. Curran Associates, Inc., 2021. URL https: http::///oooeeenns.eeeeo www.:iinnnnn..ui....e. cc/ Paper pdf
Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang. Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation-and translation-equiivrrann neural networks for 3d point clouds. arXiv preprint 1802 2018.

---

Simon Batzner, Albert Musaelian, Lixin Sun, Mario Geiger, Jonathan P Mailoa, Mordechai Kornbluth, Nicola Molinari, Tess Smidt, and Boris Kozinsky. E equiivarin graph neural networks for data-efficient and accurate interatomic potentials. Nature communications, 1311):1111,200
Brandon Anderson, Truong Son Hy, and Risi Kondor. Cormorant: Covariant molecular neural networks. Advances in neural information processing systems, 32, 2019.
Fabian Fuchs, Daniel Worrall, Volker Fischer, and Max Welling. Se (r)ntsaafform:::: 3d roto- translation equivariant attention networks. Advances in Neural Information Processing Systems, 33:1970-1981, 2020.
Philipp Thölke and Gianni De Fabritiis. Equivariant transformers for neural network based molecular potentials. In International Conference Learning Representations, 2021.
Nadav Dym and Haggai Maron. On the universality of rotation equivariant point cloud networks. arXiv preprint urXiv:2010.02449, 2020.
Soledad Villar, David W Hogg, Kate Storey-Fisher, Weichi Yao, and Ben Blum-Smith. Scalars are universal: Equivariant machine learning, structured like classical physics. Advances in Neural Information Processing Systems, 01-2888--28666 2021.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gauray Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602-4609, 2019.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Processing Systems, 34:15734-15744 2021.
Lingxiao Zhao, Louis Härtel, Neil Shah, and Leman Akoglu. A practical, progressively-expeessve gnn. arXiv preprint arXiv:2210.09521, 2022.
Snir Hordan, Tal Amir, Steven J Gortler, and Nadav Dym. Complete neural networks for euclidean graphs. arXiv preprint 2rXiv:23001.1382) 2023.
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Series, 229): 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00822 2018.
László Babai and Ludik Kucera. Canonical labelling of graphs linear average time. In 20th Annual Symposium Foundations of Computer Science (sfes 1979), pages 39-46. IEEE, 1979.
Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang. Boosting the cycle counting power of graph neural networks with i2-gnns. 2023.
Christopher Morris, Gauray Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 33: 21824-21840, 2020.
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural networks. arXiv preprint ar0iv: /5646, 2020.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. arXiv preprint arXiv:2110.02910, 2021.
Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understanding and ex- tending subgraph gnns by rethinking their symmetries. Advances in Neural Information Processing Systems, 35:31376-31 2022.
12

---

Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. arXiv preprint arXiv:2110.03753, 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions Puttern Analysis and Machine Intelligence, 45( 15(1):657-668, 2022.
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt. Topological graph neural networks. arXiv preprint arXiv:2102.07835, 2021.
Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lio, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. In International Conference on Machine Learning, pages 1026-1037. PMLR, 2021.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. arXiv preprint arXi::2301.09500 009000 2023.
Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas, Mircea Petrache, and Pablo Barceló. Three iterations of (d 1)-wl test distinguish non isometric clouds of d-dimensional points. arXiv e-prints, pages aivv-23003 2023.
Stefan Chmiela, Alexandre Tkatchenko, Huziel E Sauceda, Igor Poltavsky, Kristof Schütt, and Klaus-Robert Müller. Machine learning of accurate energy-conserving molecular force fields. Science advances, 365)xe16 2017.
Anders S Christensen, Lars A Bratholm, Felix A Faber, and O Anatole von Lilienfeld. Fehl revisited: Faster and more accurate quantum machine learning. The Journal of chemical physics, 152(4): 044107, 2020.
Xiyuan Wang and Muhan Zhang. Graph neural network with local frame for molecular potential energy surface. arXiv preprint arXi::2208.0071 2022.
Ilyes Batatia, David P Kovacs, Gregor Simm, Christoph Ortner, and Gábor Csányi. Mace: Higher order equivariant message passing neural networks for fast and accurate force fields. Advances in Neural Information Processing Systems, 35:1 1423 11436, 2022.
Albert Musaelian, Simon Batzner, Anders Johansson, Lixin Sun, Cameron Owen, Mordechai Kornbluth, and Boris Kozinsky. Learning local equivariant representations for large-scale atomistic dynamics. Nature Communications, 14(1):579, 2023.
Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):177,2) 2014.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chemical science, 9():513-530, 2018.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint arXiv:1812.09900 2018
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint WrXiv:14/2.6956 2014.
Anders S Christensen and O Anatole Von Lilienfeld. On the role of gradients for machine learning of molecular energies and forces. Machine Learning: Science and Technology, 1(4):045018, 2020.
Johannes Klicpera, Shankari Giri, Johannes T Margraf, and Stephan Günnemann. Fast and
uncertainty-await directional message passing for non-equilibrium molecules. arXiv preprint vrXiv:20/1.14155 2020b.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners. Advances in neural information processing systems, 13:1 2020.
13

---

Jacob Devlin, Ming- bidirectional transformers for language understanding. arXiv preprint arXiv:1810.0480) 2018.
Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre- Pre-training of deep
Ilya Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Un- terthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, et al. Mlp-mixer: An all-mlp architecture for vision. Advances in neural information processing systems, 34:24261- 24272, 2021.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF international conference on computer vision, pages 10012-10022. 2021.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition scale. arXiv preprint arXiv:2010.11929, 2020.
Jun Xia, Chengshuai Zhao, Bozhen Hu, Zhangyang Gao, Cheng Tan, Yue Liu, Siyuan Li, and Stan Z Li. Mole-bert: Rethinking pre-training graph neural networks for molecules. 2023.
Shuqi Lu, Zhifeng Gao, Di He, Linfeng Zhang, and Guolin Ke. Highly accurate quantum chemical property prediction with uni-mol++ arXiv preprint arXiv:2303. 2023.
Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity-
aware permutation--cuuiariann graph networks. arXiv preprint urXiv:2203.139) 2022.
Albert P Bartók, Mike C Payne, Risi Kondor, and Gábor Csányi. Gaussian approximation potentials: The accuracy of quantum mechanics, without the electrons. Physical review letters, 104(13): 136403, 2010.
Albert P Bartók, Risi Kondor, and Gábor Csányi. On representing chemical environments. Physical Review B, 87818))184115, 2013.
Alexander V Shapeev. Moment tensor potentials: A class of systematically improvable interatomic potentials. Multiscale Modeling & Simulation, 14(3):1153-1177 2016.
Jörg Behler and Michele Parrinello. Generalized neural-network representation of high-dimensional potential-energy surfaces. Physical review letters, 98( 14):146401, 2007.
Ralf Drautz. Atomic cluster expansion for accurate and transferable interatomic potentials. Physical Review B, 99(1):014104, 2019.
Chaitanya K Joshi, Cristian Bodnar, Simon V Mathis, Taco Cohen, and Pietro Liò. On the expressive power of geometric graph neural networks. arXiv preprint arXiv:2301.09308 2023.
14

---

A Counterexamples for Vanilla DisGNNs
In this section, we will give some counterexamples, i.e., pairs of geometric graphs that are not congruent but cannot distinguished by Vanilla DisGNNs. We will organize the section as follows: First, we will give some isolated counterexamples that can be directly verifie;; Then, we will give some counterexamples that can hold the property (i.e., to be counterexamples) after some simple continuous transformation; Finally, will give family of counterexamples that can be obtained by the combination of some basic units. Since the latter two cases cannot be directly verified, we will also give the detailed proof.
We say there are M kinds of nodes there are M different labels after infinite iterations of Vanilla DisGNNs. Note that in this section, all the grey nodes and the "edges" are just for visualization purpose. Only colored nodes belong to the geometric graph.
Note that we provide verification programs in our code for all the counterexamples. The first type of counterexamples (Appendix A.I) Ip is limited in quantity and can be directly verified. The remaining two types (Appendix A.2 and Appendix A.3) are families of counterexamples and have an infinite number of cases. Our code can verify them some extent by randomly selecting
some parameters. Theoretical proofs for these two types are also provided in Appendix A.2 and
Appendix A.3 respectively.
A.1
Counterexamples That Can Be Directly Verified
Since the distance graph, which DisGNNs take input, is kind of complete graph and contains lots of geometric constraints, we want to get pair of non-congruent geometric graphs that cannot be distinguished by DisGNNs, they must exhibit great symmetry and have just minor difference. Inspired by this, we can try to sample nodes from regular polyhedrons, which themselves exhibit high symmetry. The first pair of geometric graphs sampled from regular icosahedrons, which is referred to the main body of our paper, see Figure Since all the nodes from both graphs have the same unordered distance list, there is only kind of nodes for both graphs. We note that is the only counterexample we can sample from just regular icosahedron.
The following pairs of geometric graphs are all sampled from regular dodecahedrons. We will distinguish them by the graph size.
6-size and 14-size counterexamples.
A pair of 6-size geometric graphs (red nodes) and pair of 14-size geometric graphs (blue nodes) that are counterexamples are shown the figure above. They are actually complementary in terms of forming all vertices of regular dodecahedron.
15

---

For the 6-size counterexample, the label distribution after infinite rounds of Vanilla DisGNN is shown in the picture above, and the nodes are colored differently represent different labels. It can be directly verified that there are 2 kinds of nodes. Note that the two geometric graphs are non-congruent: The isosceles triangle of the two geometric graphs formed by one green point and two pink nodes have the same leg length but different base lengths.
For the 14-size counterexample, number of nodes of each kind is 2, 4, 4, 4 respectively. Since the counterexamples here and in the following are complex and not so intuitionistic, we recommend readers directly verify them with our programs.
give the conclusion that there are 4 kinds of nodes and the
8-size and 12-size counterexamples.
pair of 8-size geometric graphs (red nodes) and pair of 12-size geometric graphs (blue nodes) that are counterexamples are shown in the figure above.
For the 8-size counterexample, note that it is actually obtained by carefully inserting two nodes into the 6-size counterexample mentioned just before. We note that there are 2 kinds of nodes in this counterexample, and the numbers of nodes of each kind are 4, 4 respectively.
For the 12-size counterexample, it is actually obtained by carefully deleting two nodes from the 14-size counterexample (corresponds to the way to obtain the 8-size counterexample) mentioned just before. There are 4 kinds nodes in this countercxample, and the numbers of nodes cach kind are 4. 4, 2, 2 respectively.
Two pairs of 10-size counterexamples.
The above figure shows the first pair of 10-size counterexamples. There are 3 kinds of nodes and the numbers of nodes of each kind are 4, 4, 2 respectively.
The above figure shows the second pair of 10-size counterexamples. There actually only kind of
nodes, all the nodes of both graphs have the same unordered distance list. It is interesting because
16

---

the same surface, but there are two regular pentagons in the left graph and ring in the right graph, which means that the two graphs are non-congreent and it is quite similar to the case shown in Figure I two equilateral triangles in the left graph and also ring in the right graph.
where there are
In the end, we note that the above counterexamples are probably all the counterexamples one can sample from a single regular polyhedron.
A.2 Counterexamples That Hold After Some Continuous Transformation
Inspired by the intuition mentioned in Appendix A.I we can also sample nodes from the combination of regular polyhedrons, which also have great symmetry but with more nodes.
Cube regular octahedron.
scale cube
scale cube
The first two counterexamples sampled from the combination of cube and regular octahedron. We combine them in the following way: Bring the center of both polyhedrons together, and align the vertex of the regular octahedron, the center of the cube's 's face, and the center of the polyhedrons in straight line. We do not limit the relative size of the two polyhedrons: one can scale the cube to any size long the constraints not broken. In this way, small family of counterexamples is given (we say small here because the dimension the transformation space is small).
Proof of the red case. Let the side length of the cube be 2a, the diagonal of the regular octahedron be 2b. Initially, all nodes are labeled lo- We now simulate Vanilla DisGNNs on both graphs.
At the first iteration, there are actually two kinds of unordered distance lists for both of the graphs: For the vertexes on the regular octahedron, the list is ((2b, lo), 1), ((V3a² 3 + 1 2ab, lo). 2), ((V3e2 + 12 2)b, the cube, the list is { ((2a,4). ((2V2a,
For the 10), 1). ((2v3a, 10), 1),
vertexes
((V3a2 + 2ab, 40), 1), ((v 3a² + 62 2ab, lo), }) Thus they will be labeled differently at this step, let the labels be 1 and la respectively.
At the second iteration, the lists of all the vertexes the regular octahedron from both graphs still the same, i.e. ((26,4), 1), ((V3a² 2 + 122 20b, 12), 2). ((v 3a2 + B 2ab,12),21 2) well as the lists of all the vertexes the cube from both graphs, i.e. { ((2a, (2,, 1), ((2 (2), 1),
((2v3a, 12) 1), ((V3a² + 62 2ab, 1), ((V3a² 1 2ab, 1))
Since Vanilla DisGNNs cannot subdivide the vertexes at the second step, they can still not at the following steps. So it cannot distinguish the two geometric graphs. But they are non-congruent: the left graph, the nodes on the regular octahedron can only form isosceles triangles with the nodes on the face diagonal of the cube. On the right graph, they nodes on the cubes that are on the same side. We note that the counterexample in Figure is not a special case of this, because the left graph of this case all the nodes none of graphs in Figure have all nodes on the same surface.
only form isosceles triangles with
Proof of the blue case. The proof of the blue case is quite similar to that of the red case; thus, we omit the proof here. Note that the labels will stabilize after the first iteration. At the end of Vanilla DisGNN, there are 2 kinds of nodes, each kind has 4 nodes. And the two geometric graphs are
17

---

non-congruent because the plane formed by four nodes on the regular octahedron is perpendicular to the plane formed by four nodes on the cube in the left graph, and is not in the right graph.
2 cubes.
scale cube
scale cube
The second case is the combination of 2 cubes. We combine them in the following way: Let the center of the two cubes coincide as well as the axis formed by the centers of two opposite faces. Also, we do not limit the relative size of the two cubes: one can scale the cube to any size as long as the constraints are not broken. The proof of this case is quite similar to that in Cube + regular octahedron; thus, we omit the proof here. Note that the labels will stabilize after the first iteration. the sizes of the two cubes are the same, then the end of Vanilla DisGNN, there is only kind of node. If not, there are 2 kinds of nodes, each kind has 4 nodes.
A.3 Families of Counterexamples
In this section, we will prove that any one of the counterexamples given in Appendix A.1 can be augmented to family. To facilitate the discussion, we will introduce some notations.
Notation. Consider an arbitrary counterexample (G G given in Appendix A.1 It is worth noting that for each graph, the nodes are sampled from a regular polyhedron and located on the same spherical surface. We can denote the geometric graph on this sphere as Govi.r. where r represents the radius of the sphere. Since the nodes are sampled from some regular polyhedron (denoted by Gall,r), there must be nodes that aren't 't sampled, which we call as complementary nodes. We denote the corresponding geometric graph as Goom.r- Given two graphs GQ GQuir where Qi E {ori, com, all) for E [2], we say that we align them if we make sure that the spherical centers of the two geometric graphs coincide and one can get G by just scaling all the nodes of G along the spherical center. We use L = { (v. (.)
V) to represent label state for some graph G. and call it a stable state if Vanilla DisGNN cannot further refine the labels of the graph G with initial label L. We say that C is the final state of G if it is the label state obtained by performing Vanilla DisGNN on G with no initial labels for infinite rounds. Note that final state is a special stable state. We denote the final state of Gors and Geom as Lori and Zoom respectively.
Now, let us introduce an augmentation method for arbitrary counterexample (Gbri, GBR)) shown in Appendix A.1 For a given set QR = {(Q1, (Q2. r,,,..., (Qx. } where r; > 0, Qi E fori, com, all} and r # ry for i + j. we get the pair of augmented geometric graphs (R)) = AUG (G GRR) by the following steps (take GL for example):
1. Generate geometric graphs Go i E [k] according to QR+
2. Align the k geometric graphs.
3. Combine the l geometric graphs Gh G...., i [k]] to obtain G².
We give an example of the augmentation in Figure Now we give our theorem.
Theorem A.I. Consider arbitrary counterexanple (G'r.. G given in Appendix A.1 Let
QRa = (QQ1, (Q2, (2)...)... Tw)) be arbitrary set, where Qs {ori, com, all and
18

---

Figure 3: An example of the augmentation. In this example, (G G from Figure 1 and QR3 (ori, rr); (all, rp); (com, (with r, p.g representing red, purple and green respectively). Nodes with different colors indicate that they are derived from different Go.r generations. The augmented graphs (G GR) AUG (G G Brr) consist of all the colored nodes.
Ti A for Bf [k] such that Qi + all, then the augmented geometric graphs AUGOR, (G G form a counterexample
Before presenting the proof of the theorem, we will introduce several lemmas that will be used the proof.
Lemma A.2. If Vanilla DisGNN cannot distinguish (G*, Gt) with some initial label (Ct C),,, then Vanilla DisGNN cannot distinguish (G G without initial label (with identical labels).
Proof of Lemma We use It. to represent the label of after iterations of Vanilla DisGNN without initial labels, and use 1.c.t to represent the label of u after iterations of Vanilla DisGNN with initial label L. We use 1:0 and 1C,00 to represent the corresponding final label. In order to prove this lemma, we first prove conclusion: for arbitrary graphs G (V, E) and arbitrary initial label C, (h.t a
let u, e be two arbitrary nodes in V, then we have vt E Zt, 1 1 the conclusion by induction.
f C.,t, We'll prove
6 =1 1 holds.
If (1o, (duss 12)
E Nu))B) # (1. (dd.s, I N(b) then we have (dus | E N(v) since 10 are all identical for E V. Then it is obvious that E (()))) + (If.0, (ddaa, E
N(O) B o (due
(15.0, ((dus, 12.0)
For Vk & tt k holds f = k holds.
Assume i. = k does not hold, i.e., Fu, V, ((+1) + (k+1) but c.(++) (.,(+))) We can derive from lf.(k+1) ff((++1) that
11 (f((+11) 1((k+1)
k ((duss 15:)) I E (IS*t (dhss (SEFA)/SE((CC
= Jh = kf.k and (duss 16.x) E N(u)D ((dos 16.kk (SE N(v)) (13)
Since = k holds, for V81, 82, we have
C.kk 1
1 1b
Together with Equation
13 we have t = t and (duus, |se (eE = ((de.)
(()) B. This means ( (k+1) 1 (k+1) which is contradictory to assumptions.
19

---

This means that the conclusion holds for Vt E Z+, as well as = cc. In other words, specifying an initial label L will only result in the subdivision of the final labels.
Back to Lemma A.2 if Vanilla DisGNN cannot distinguish (GL, GR) even when the final labels furthermore subdivided, it can still not when the final labels are not subdivided, i.e., cannot distinguish (G+, l without initial labels.
Lemma A.3. Consider an arbitrary counterexample (G G ors) given in Appendix A. We have that (Corr U Cl Cor U C is a pair of stable states of (G Gat)). Denote the labels as C and al respectively. Moreover, we have that Vanilla DisGNN cannot distinguish (G Gan G with initial labels f and CR
Proof of Lemma A.3 Since the number of situations is finite, this lemma can be directly verified using a computer program. is worth noting that we have also included the verification program in our code.
This lemma allows to draw several useful prior conclusions. In the graph Gall. the node set Vall can be split into two subsets by definition, namely Vort and V.om- Now for arbitrary node u from Gh with initial label C/u and from Gftt with initial label C if the initial labels of node u and node e are the same, they must be in the same subset, i.e., respectively in yors and V or VL and VR. coom Without loss of generality, let assume that both and are in Vori- Since (C Cay is stable state of (G' Git)), we can obtain the following equation:
(lu, 8 (dus: 1.) Valt B) = (lo, (doss 1.) I s E Vall B).
(14)
Since (Co. f is a stable state of the induced subgraphs (G G where the node sets are (Vor V we can obtain the following equation:
(Lus if (due: s E B) = (L., ((eeedd (2) E V)
(15)
we can obtain a new equation by replacing VL or Val with (VL - u) or (V2l u) and doing the same for the v side, while keeping the equation valid, since
Notice that in Equation 14
15
by 1. By subtracting Equation (15) from Equation (14), we obtain the following equation:
(Lu, ((uus, 1,) s E Volmmi) = (Lu. (e) E V& DD)
(16)
It is important to note that the same conclusion holds if both and v are from type com. These equations provide valuable prior knowledge that we can use to prove Theorem A.I
Now, let us prove Theorem A. Our proof is divided into four steps:
1. Construct an initial state (C', for the augmented geometric graphs (G',
2. Prove that (C',,L) is pair of stable states for (G', G
3. Explain that Vanilla DisGNN cannot distinguish (G4, G with initial labels
4. Explain that (G", Gd)) are non-congruent.
By applying Lemma A.2 we can get the conclusion from step 2 and 3 that Vanilla DisGNN cannot distinguish (GL, G without initial labels. Since (GL, R are non-congruent (as established in step 4), it follows that (GL, Gft) is a counterexample.
Proof of Theorem A.7
Step 1. We first construct initial state for the augmented graphs
For simplicity, we omit the superscripts, as the rules are the same for both graphs. For each layer (i.e., the sphere of some radius) of the graph G, we label the nodes with Lip if the layer is of type tp, for tp E (ori, com, all}. Note that we also ensure that the labels in different layers are distinct.
Step 2.
Now we prove that (C", L.) is a stable state for (G R). This is equivalent to proving that for arbitrary node in (GL, (-) and node in (GR, ) if 12 1. then 12 41
Since G is considered as a complete distance graph by DisGNNs, the neighbors of node u are all the nodes in & except itself. We denote the neighbor nodes from the layer with radius r3 by Nr, (u).
20

---

This is similar for node v. Now we need to prove that (lu (du.. (2)
E USE(K) Nr. (v) (u)
(ch, (ddos (2) Use(k Nr, (v) Since 12 th we only need to prove that & (dus: (2)
Usera (1) = ((dus; (2) | USERR) Nr. (v)B-
We split the multiset (duss: (2)
UiERN (u) into k multisets, namely [ddss 12) Nr. (u) B. i E [k]]. and do the same for the multiset of node u. Our goal is to prove that ([dus (2)
E Nr, (u)) (dd.: E (v) for each i E [k].
Let the coordinates of node a spherical coordinate system be (rs: Φ.). Since nodes u and have the same initial label, they must be from the same layer, meaning that Tu To- Addition- ally, we always realign the coordinate systems of G and G to ensure that the direction of the polyhedra is the same. The distance between node and node in a spherical coordinate system is given by Vr + r 2ruTs( sin O2 sin 0g cos( Φ,) cos On cos 0z). We denote the angle term (sin 0n sin 8g cos( o²) + cos ti cos by Oue for simplicty.
For each value of r,. it can be one of three types: ori, com, or all. Similarly, nodes and v can belong to one of three categories: ori, com, all. Regardless of the combination, these situations can always
be found the Equations (14) 15 16) derived from Lemma A.3 and can produce the following conclusion:
(Lu ((Ous, (2) & N,, = (1), (O... 12) I S Nr,(c))
Then we have:
(Cu, 1l ((V + - 2r
Nr, (u)B)
-(p [(( r +r O (2) SE Nr, (v)})
since ro rr- This means that for all values of ri. &f (duss: 19) 1 E Nr (u) = (doss 12) (v)]. H. By merging all the multisets of radius r; we can get ((dus, 12) s E UsEM Nr, (w)
((d,. 12) s Usetay (v)B. B. which concludes the proof.
Step 3. Since the stable states (c4, () are obtained by assigning the stable states of each layer, i.e. from. Lori or Calt, that cannot be distinguished by Vanilla DisGNN, the histogram of both graphs are exactly the same, which means that Vanilla DisGNN cannot distinguish the two graphs.
Step 4. Notice that the construction of isomorphic mapping requires that the radius of the layer of node u in G and node in G must be the same. If there exists pair of layers in the two geometric graphs that are non-congruent, then the two geometric graphs are non-congruent. According to the definition of (G', GR), such layers always exist, therefore the two geometric graphs non-congruent.
21

---

B Proofs
B.1
Proof of Proposition 6.3
The main proof of our proposition is to construct the key procedures in GemNet [Gasteiger et al. 2021] using basic message passing layers of 3-E/F-DisGNN, and the whole model can be constructed by stacking these message passing layers up. Since the k-E-DisGNN and k-F-DisGNN share the same initialization and output blocks and have similar update procedure (they can both learn 4- 4-order geometric information), we mainly focus on the proof of E version, and one can check easily that the derivation for F version also holds.
Basic methods. Assume that we want to learn Otar = Star (Tarr with our function Ons = Jin (Zri) In our proof, the form of Ouar and Oft, as well as the form of Tear and Iat, are quite different. For example, consider the case where Oāt is an embedding habe for a 3-tuple abc and Ia. = Llabe) contains the information of all the neighbors of abc, while Otar is embedding mab for 2-tuple ab and Iew = I(ab) contains the information of all the neighbors of ab. Therefore, directly learning functions by füt that produces exactly the same output as ftar is inappropriate. Instead, we will learn functions that can calculate several different outputs in a way ftar does and appropriately embeds them into the output of fat- For example, still consider the case mentioned before, and want to learn function füt that can extract I(ab) II(e)) I I:(la) I(ce) II(e) from I(abe) respectively, tar
and calculates mab, Mac: Tabe Tiba meas Meb with these information like frar. and embed them into the output habe in an injective way.
Since we realize fū as a universal function approximator (such as MLPs and deep multisets), fa can always learn the function we want. So the only concern is that whether we can extract exact Iar from Zft. i.e., whether there exists an injective function (I(1) I(2) I(x) will mainly discuss about this in our proof.
tar tax = Sex (Inz). We
Notations. We use the superscript G to represent functions in GemNet and 3E to represent functions in 3-E- E-D-iGGNN,, and use I with the same superscript and subscript to represent the input of a function. We use the superscript (a1a2..ax) to represent some input I if it 's for tuple (a (a1ag..ak). If there exists an injective function I ( (Int), then denote it by Iat be derived from Iit- If some geometric information Zgeo (such as distance and angles) is contained in the distance matrix of tuple an 02..0k, then we denote it by Igoo 0102..0k- For simplicity, We omit all the time superscript é if the context is clear.
Irar meaning that Tear can
B.1.1 Construction of Embedding Block
Initialization of directional embeddings. GemNet initialize all the two-tuples (also called directional embeddings) at the embedding block by the following paradigm
mab flat (Za, 2b, dab).
(17)
At the initial step, 3-E-DisGNN follows the paradigm outlined below:
habe funt (Zas 2b. Ze; dub, daes dbe).
(18)
Then we have
(a,b))) I
+ (I(i((t))
G.((a) G.(be) IG,(ba) ICi(co) (G,(()))
meaning that we can extract all the information to calculate mab. Mac: Mher Miaa Mea, Meb from the input of A3E And thanks to the universal property of f3E we can approximate function that accurately calculates these variables and injectively embeds them into habe, such that habe +
(mab, mae, mèc. Mia- Mee- met).
Initialization of atom embeddings. GemNet initializes all the one-tuples i, (also called atom embeddings) the embedding block simply by passing atomic number 2; through embedding
layer.
Note that since we can learn all the my and embed them into habe by f it is also possible to learn all the u, E (a, b, cf and embed them into hade at the same time with some function, since (abe) contains 2,, ė {a,b, c}. Therefore, habe (Mar Wh, u.) holds. Tiit
22

---

Initialization of geometric information. It is an important observation that since Jinit take all the pair-wise distance within 3-tuple abc as input, all the geometric information within the tuple can be included in habe- This makes geometric information rich in the 3-tuple embedding habe-
To remind the readers, now prove that there exists function fin which correctly calculate maj (i & j, E {a. b, c)), (i E {a, b, c)) and all the geometric information Igoo within the triangle abc, and injectively embed them into habei
habe + ((mes l j.i,j E {a, (a), (us I l (a,b, (Igeo Igoo abc)):
B.1.2 Construction of Atom Embedding Block
Atom embedding block. GemNet updates the 1-tuple embeddings by summing up all the relevant 2-tuple embeddings m in the atom emb block. The process can be formulated as
faom (8 (miaa (ka) k E [N]B)-
Ua
(19)
Since this function involves the process of pooling, it cannot be learned by fin However, it can be easily learned by the basic message passing layers of 3-E-DisGNN SMP which is formulated as
habe = J3
(hates (hesee Cak)
[N]], (hakee ena) [N]], [hhass: eak) [N]B);
(20)
where Eab = 33 (dab: Kkaa lo [N]]] (haks & [N]], &habe & E [N]B).
(21)
We want learn function M&P that updates the ua: ub, uhe embedded in habe like f and keep the other variables and information unchanged. Note that habe is the first input of MPP, all the old information maintained. As what we talked about earlier, the main focus is to check whether the information to update is contained in fMP 's input. In fact, the following derivation holds
IMP
(abe)
- & (hake: ebs) le [N]] hakke & [N]B
+ (miaa dRa) k E [M]] - (miaa (Ka)
E [
GG((a) atom
Note that dıa E abc, and (ka)
CBF can be calculated from dRa- Similarly, we can derive that IMP (abe) 4
G.G(()) and IMP (abc)
+ G.(()) This means we can update u in using a basic message passing layer
3-B-DiGNN..
B.1.3 Construction of Interaction Block
Message passing, There are two key procedures in GemNet's message passing block, namely two-hop geometric message passing (Q-MP) and one-hop geometric message passing (T-MP), which can be abstracted as follows
T MP Mab = fGMP (f(
RAP: (abk)) &o E (NT, aB)
(22)
Q MP mab = SQMP ( (m
CRBF CBB <sBr
(kzkk) kb)) (adkikal) his h2 [N], ki + a, k2 # b, a}
(23)
Note that what we need to construct is function JMP that can update the information about Maj, 1,j E {a, b, c), # embedded in habe just like what STP and variables and information unchanged. Since it is quite similar among different m,j. we will just take the update process of mas for example.
f fQMP do, and keep the other
First, T-MP. For this procedure, the following derivation holds
(abe) (hates (hybee tak) ) 1 E [N]B) - $ (Habee busee eak) k E [N]]
+ { (mis, dya, dab, dabk) k E [N]] + {mms, e (abk) | [N], k + a} = G.(ab)
Note that in the derivation above, there is an important conclusion implicitly used: the tuple (habes habe, Cak) actually contains all the geometrie information in the 4-tuple abck, because the
23

---

distance matrix of the four nodes can be obtained from it. Thus dab. deb. Pubk can be obtained from it, and since (kb)
(abk) CRBF and CCBF are just calculated from these geometric variables, the derivation holds.
And we can exclude the element in the multiset where the index k: = a, simply because these tuples have different patterns from others.
Second, Q-MP. Q-MP, the pooling objects consist of two indices (which we call two-order pooling), namely 11 and 22 in Equation (23). One alternative way to do this is two-step pooling, i.c. pool two times and once for one index. For example we can pool index b1 before we pool index kę as follows:
SQMP (migk) C .CBF
(k2ka) (2k,k2) essTE (abk)kk)) ki E ( + a la E [N] K2 + b. aa))
Mab
CSSB
(24)
Note that the expressiveness of two-step pooling is not less than two-order pooling, i.e.
{ ll (migkk (kgh1) (b (abk)kz)
RBB CCBF , SBF
l E [N],k # aL 1/2 E [N], k2 + b, a
* (magk) CBF CBBF CSBF
(bakk) ) (bk2
kg) ka))
k1, K2 E [N], # a, h2 + b, a..
Thus, if we use two-step pooling implement Q-MP, it does not reduce expressiveness, Inspired by this, in order to update mab in habe like f &QMP> we first learn function by SMP that calculates an
intermediate variable we = Sinterz (f ((mckk, CRBP' (bkc) <SBF ((bkk)) k E [N], & + aB} by pooling all the mick index k, which is feasible because the following derivation holds (abe) MP
+ (habes &f (habks Eck) E [MIB) + (haber habk: Cok) E [N]
+ E (mik, dak, dak, Pabk, Oahkec) k E [N]]
{ (mick CRBP; CCBF SSBP
(ek) (bke) (abkc)) k: E [N], [ 3.3B.cc)
Note that in the derivation process above, mek is directly derived from eek because it contains the information by definition 21 Then we apply another message passing layer 3E but this time we learn function that just pools all the we in habe and finally updates Mabi
3E, (abe) + (habee, eck) k E [N]] + hhabk & E [N]] + Fwx l E b.
MP
This means we can realize SyMP by stacking two message passing layers up.
Atom self-interaction. This sub-block actually involves two procedures:
First, update atom em- beddings u according to the updated directional embeddings m. Second, update the directional embeddings m according to the updated atom embeddings u. The first step is actually an atom embedding block, which already realized by our f3E in Appendix B.1.1 The second procedure can be formulated as
Mab = f -Sell-intee inter (May Wh, mab).
(25)
It is obvious that we can update mab habe by /MP because the following derivation holds
(ab(e) - habe > (Mo: Ub Mab)
(ab)) self self-inter inter"
IMP
B.1.4 Construction of Output Block
In GemNet, the final output t is obtained by summing up all the sub-outputs from each interaction block. While is possible to add additional sub-output blocks our model, in our proof we only consider the case where the output is obtained solely from the final interaction block.
The following function produces the output of GemNet
t
Σ Wont (farom (H (Mka, ( | & [N]D)),
(26)
aE[M]
where Wout is learnable matrix. And our output function is
Son (Khave a,,, E [N]B).
(27)
We can realize Equation (26 by stacking message passing layer and an output block. First, the message passing layer updates all the atom embeddings u in hate. and then the output block extracts u from h as follows, and calculates t like GemNet.
(abe)) - (hoaa la [N] + qua | [N]].
24

---

B.2 Proof of Proposition 6.2
In this section, we will follow the basic method and notations in Appendix B.1 We will mainly prove for 2-F-DisGNN, and since when & 2, k- E-DiGGN''s update function can implement i-F-DisGNN'' (See Appendix B.4). the derivations also holds for 2-E-DisGNN. We will use the superscript D to represent functions in DimeNet and 2F to represent functions in 2-F-DisGNN.
B.2.1
Construction of Embedding Block
DimeNet initializes all the tuples in the embedding block just like GemNet, which can be formulated as
Mib Piitt (Za; 2b, dab)-
(28)
What 2-F-DisGNN does at the initialization step is
hab
2F (Za, Rb. dab)).
(29)
Now assume we want to learn such a function that can learn both mab and Thaa then embed into hab. As what we talked about in Appendix B.I it possible because the following derivation holds
(22 Ait
(i _Imit ID.(ba)).
Note that hab also contains the geometric information, but in this case, just the distance. Different from GemNet, DimeNet does not "track" the 1-tuple embeddings: does not initialize and update the atom embeddings in the model, and only pool the 2-tuples into I-tuples in the output block. So there is no need to embed the embeddings of atom a and atom b into hab-
B.2.2 Construction of Interaction Block
The message passing framework of DimeNet (so-called directional message passing) can be formu- lated as
Mab MMP (il (MAsa (ab) (kab) k [N], + b)).
(30)
And the message passing framework of 2-F-DisGNN can formulated as
hab = 22 (hab: (hupb, hak) e [N], k bb).
(31)
Now we want to learn a function RMP that can updates the mab and mho embedded in has like what MMP does. We need to check if MP have sufficient information to update mab and mba embedded in its output hab- The derivation holds:
22F. + (hab, hggs Rak) & E [N]] - +X [ITikaa dab, dea drab) [N], k # (ab)
(maa, CRFF (kab) | E [N],
DD((bb)
Note that we again used the observation that tuple (hab. hgg, hak) contains all the geometric informa- tion of 3-tuple abk. Similarly we can get (22 (ab)
I IMP DD(ba))
B.2.3
Construction of Output Block
The output block of DimeNet is quite similar to that of GemNet (Appendix B.1.4). which can be formulated
(A(mka (ka) k E [N]B),
(32)
Σ
Ug-
(33)
aE[M]
This can be realized by stacking message passing layer of 2-F-DisGNN and its output block up.
The message passing layer of 2-F-DisGNN can learn us and us and embed into the output hab because the following derivation holds
728
(lisa, bak)
l: [N]] (hat & E [N]B
+ 8f (maa: dra) [N]] + (m (lke) le [N]] = DD((a)
25

---

Similarly we can get (22b((ab) And the output block of 2-F-DisGNN is formulated as follows
atom
for Soutput (Hab l, E [N]B).
(34)
Note that the following derivation holds
I Phaa | [N]] fua l [N]].
This means that the output block of 2-F-DisGNN can implement the sum operation in Equation 33
B.3 Proof of Theorem 6.4
We first restate the theorem formally.
Theorem B.1. Let M(0) E MinMods = {1-round 4-DisGNN, 2-round 3-E-DisGNN, 2-round 3- 3-F-DisGNNY with parameters 0. Denote hm. = fuode ( v E V* v0 = mB) E R K" m's representation produced by M where Jnode an injective multiset function, and x,, as node m''s 's coordinates w.r.t. the center. Denote MLPs(0') RK' + R as a multi-layer perceptron with parameters 6'.
as node
1. (Completeness) Given arbitrary two geometric graphs X1, X2 E R3xn then there exists 0 such that M(X1: fo) = MMX2; bo) + X, and X₃ are congruent.
2. (Universality for scalars) Let f Rx + R be an arbitrary continuous, F(3) invariant and permutation invariant function over geometric graphs, then for any compact set M C RR3x
and > 0, there exists 0g such that VX M, MMX 0o) S
3. (Universality for vectors) Let f ariant, permutation and translation invariant function over geometric graphs, let fout EMV AhLPs(hm)ea then for any compact set M C 333 and e 0, there exists og for M and for MLPs such that VX E (,) - -Jont
R2 + IR3 be an arbitrary continuous, 0(3) equiv- pequiv
pequiv (X; 8o 0b) S.
In the forthcoming proof for completeness part, examine the optimal scenario for k-EE/F- DisGNNs, namely the geometric version k-(E/F)WL, where the hyper-parameters such as hidden dimensions set and parameters of ((0) are learned ensure that all the relevant functions are hash functions. To simplify the analysis for k-EWL, we substitute the edge representation in k-E-DisGNN with the edge weight (distance) alone, which is already enough.
Basic idea for proof of completeness. We prove the completeness part of the theorem, which demonstrates that the optimal DisGNNs have the ability to distinguish all geometric graphs, through a reconstruction method. Specifically, if we can obtain all points' coordinates up to permutation and E(3) translation from the output of DisGNNs, it implies that DisGNNs can differentiate between all geometric graphs.
B.3.1 Proof of Completeness for One-Round 4-WL
Proof. We begin by assuming the existence of four affinely independent nodes, meaning that there exists a 4-tuple of nodes that can form a tetrahedron. If this condition is not met, and all the nodes lie on the same plane, the problem is simplified, as the cloud degenerates into 2D space. We will address this case later in the discussion. We assume the point number is N.
Our first step is to prove that we can recover the 4-tuple formed by the four affinely independent nodes from the output of one-round 4- 4-WL, denoted by ( i E [N]' B. Since all the tuple colors are initialized injectively according to the tuple's 's distance matrices, there exists function fo such that (c()) = D. where D; is the distance matrix of tuple i. Note that since the update procedures of
the colors are HASH functions, cf HASH( f-1 Ch11 C 2, Cha1)) where Ch denotes the color multiset of tuple i's m-th neighbors, there also exists a series functions f" such that ('())) c This simply means that the latter colors of tuple will contain all the information of its former colors. Given the fact, we can use the function ft o f to reconstruct the distance matrices
of the tuples, and find the one that represents a tetrahedron geometry (Theorem 3.T). We mark the found tuple with k.
26

---

Now we prove that one can reconstruct the whole geometry from just ck.
First, reconstruct the 4 points' 3D coordinates (given any arbitrary center and orientation) from k's distance matrix (Theorem 3.1 Formally, there exists a function fP(D)) XR. where X E R4+3 represents the coordinates. And since (c() DE. have that f o f (c)) XK-
The update function of Ck is c - HASH( Co Ci,,, C2 Ca,)), where C = ff (k.j)) j [N] m E [4] and 4n (k replaces the m-th element in tuple & with j. Since the function HASH function, we can also reconstruct each of Cn,k from d/- In C there exists N 4-tuples' initial color, from which we can reconstruct the 4-tuple's distance ma- trix. Note that given a color ca (k.j) in the multiset, we reconstruct 3 distances, namely d( (m d(zrj Th (m44)a))) where 2y representes the 3D coordinates of point j and d(x y) calculates the l2 norm of x. y-
There a strong geometric constrain in 3D space: Given the distances between point and 3 affinely independent points (whose postions are known), one can calculate at most 2 possible positions the point, and the possible postions are mirror-symmetrie relative to the plane formed by the 3 affinely independent points. Moreover, the point is on the plane formed by the 3 affinely independent points iff there is only one solution of the distance equations.
Now since have already reconstructed XR. and ((m++))%4 2)n+2)%4 (m++3)%4 affinely independent, we calculate 2 possible positions of point j. And for the whole multiset Co Cm caleulate N-size multiset where each element is pair of possible positions of some point, denoted as Pm, = { (aft)) ) | [N]]. Note that now the possible geometry of the N points form O-dimension manifold, with no more than 2 elements.
There two important properties of P k.
1. Given arbitrary two elements (pairs) of Pm, denoted as Pya and Pja we have P₁t Pia or Pý OPjz = (.. These correspond to two possible situations: j1 and ja are either relative the plane formed by kmm+ ls 22)4)4 (m+3))% or not.
2. Arbitrary element Pj of P has multiplicity value at most 2. This corresponds two pos- sible situations: either has mirror-symmetric point relative to the plane formed by kmm+1)%4 (m++2%% ks (m+4%)% or does not.
The follows proves that the four O-dimension manifolds determined by Pm, m [4] can intersect at a unique solution, which is the real geometry.
We first "refine" the multiset Pm.k k- There are kinds of pairs in Pm.
(1) 1. The pair {z,") x5 (2) that have multiplicity value 2. This means that there are two mirror- symmetric points relative to the plane formed by k (m++1)% (m+2)% (m443)94- So we can ensure that the two points with coordinates oij 2
(2) both exist.
2. The pair where 2 (2 z.. This means that by solving the 3 distance equations, there is only one solution. So we can uniquely determine the coordinates of point j (and the point is on the plane).
3. The other pairs.
We can determine the real coordinates of the points from the first two kinds of pairs, so we record the real coordinates and delete them from the multiset Pm,k (for the first kind, delete both two pairs). We denote the real coordinates determined by Pm.. as Am. Now we have preliminarily refined sets, denoted as P A Note that now in each p' m.kk
1. Arbitrary two elements intersect at 0.
2. Arbitrary element has two distinct possible coordinates, one is real and the other is fake.
27

---

3. The two properties above also mean that elements in multiset UPEP: P has only multiplicity 1.
Since the real coordinates Am determined by different mm.. may be not the same, we further refine the P m. by removing the pairs that contain coordinates in (Ao U A U A2 U As) Am- Note that according to the property of P" m, mentioned above, each coordinates in (Ao U Ai U A2 Aa) Am will and will only corresponds to one pair in P m. Denote the further refined sets m After the refinement, each Im, has equally M N |A A1 A2 U Aal elements (pairs), corresponding to M undetermined real coordinates.
We use p E P denote the multiset Hp' p E P.p' Op + 4}. Now we prove that 3m E [4]. 3p
pM m. 3m' E [4] m, s.t. (pr P" &k by contradiction.
Note that Vm E [4], Vp E P Vm' E [4] m, 1p P" {1, That's because each element in PM m, contains one real coordinates and one fake coordinates, each real/fake coordinates can at most intersect with one pair in m' k. and there must exist one element in P mi that contains the
same real coordinates.
So opposite to the conclusion is: Vm E [4], Vp PM m, Vm' E [4] m, Ip PW 2, assume this holds. Now there are also two properties:
1. For all m E [4]. elements multiset Upern, p has multiplicity
2. For all m E [4), UpEr mi p with different m shares the same M real coordinates.
So we have that: UPEPn P is the same across all m [4]. Note that for each E P since m.. the two coordinates in p mirror-symmetre relative to plane (mm+1) (2)+ (m++3))44 the midpoint of the two points is on the plane. This means that by averaging all the coordinates in UpE P. have center point the plane (mx+1)74>> (m (m++3)% However, since UpEr p for all m E [4] are the same, we have one same center point on each four planes (m++1)% (m+2%)% (3+3)444 m E [4]. This contradicts to the assumption that k k2, ka, ka are affinely independent points. So the conclusion that 3m E [4]. 3p E P" m, 3m. E [4] m, s.t. lp n PM vel = holds.
Since the conclusion holds, we can obtain the and the unique element p' E un P Moreover, we have that Ip' O pl = 1. This is because, the two pairs share one real coordinates, and the fake coordinates must be different (The two planes formed by (m++1)% (m (m+3)44 and not the same). So we obtain the real coordinates by p'
(1n'+1)%4 k ((m' + 2)% ((m'+3)%
Now we further refine the 4 po m. by deleting the pair that contains the real coordinates we just found, which makes each p A have only M - pairs now. Then we loop the procedure above to find all the remaining real coordinates.
Note that all the information, including the final geometry, obtained in the above proof is derived from only c.. This means that when generating ch. 4-WL injectively embeds the whole geometry using HASH function. For two non-congruent geometric graph, their 4-tuple's (where nodes are affinely independent) colors will always be different, giving the 4- 4-WL the power to distinguish them.
For the degenerated situation (there does not exist 4 affinely independent nodes), the points form 2D plane. Then with similar proof idea, we can prove that 3-WL can be universal on 2D plane. Since 3-WI. is not stronger than 4-WI., 4-WI. can also distinguish all the degenerated cases.
B.3.2 Proof of Completeness for Two-Round 3-FWL
Proof. As previous, our discussion is under the fact that the point cloud does not degenerates to a 2D or ID point cloud. Otherwise, the problem is quite trivial.
We first find the tuple containing three nodes that are affinely independent from the 2-round 3-FWL's output Tee i [N] Denote the founded tuple k. We first calculate the 3 nodes' coordinates according to the of derived from oz.
28

---

As the update procedure, c = HASH(Ck Hf (C) co (k.j)) (o.(k)))) 1 E NN), each tuple (k,)))))
(k.) So ( (R.))* (k. in the multiset contains the distance dko.j. .s dk.jk... Thus, we can calculate at most two possible coordinates of node j. and the two coordinates are mirror-symmetre relative to plane k. Like in the proof of 4-WL, denote the final calculaoed possible coordinates-pair
(2) multiset as Px = [-) 3 } E B-
We then further find a node jo that not on plane & from the multiset term in c. and its colors' tuple (cou(k..o) Ca. (k.jo): (o)()e))))) Note that the three colors are at time-step which means that they already aggregated neighbors' information for one-round. So by repeating the above procedure, we can again get a possible coordinates-pp pair multiset Pa (Pe.oo)) from each of c (k.io) where m E [3].
Note that the four plane, k, Po jo), D (k, jo), Ø2 (2 we can do as what we do in the proof of 4- WL, to repeatedly refine each multiset P and get all the real coordinates, thus reconstruct the whole geometry.
ju), do not intersect at common point. So
B.3.3 Proof of Completeness for Two-Round 3-E-DisGNN
Proof. As previous, our discussion is under the fact that the point cloud does not degenerates to a 2D or ID point cloud. Otherwise, the problem is quite trivial.
So we first find the tuple containing three nodes that are affinely independent from the 2-round 3-E-DisGNN's output (cc | [M] and refer to it tuple k. Its output color o& can derive the three points' coordinates. The update procedure is of HASH(C), & (Cbbo(k)) do
[M]], 1 (( dr j E [N]], i ((bbz(k.))) )2) 1 j E [N]]). Since in the first multiset ((bo.(t)) djRa)) 1 E [M]] the element (k.)) dy contains distances dy dedk dj we can calculate a possible coordinates- multiset as Ps I (2 x (
[N]]. As we discussed before, the elements in Ps. may only have multiplieity value 1 or 2. So diseuss for two possible situations:
1. All the elements (coordinates pairs) in Ps either have multiplicity value 2 or the two coordinates within the pair are the same. This means that we can determine all the real coordinates from Pk. as we discussed in the proof of 4-WL.
2. There exists some element in Pk. that have two distinct coordinates within the pair, and have multiplicity value 1. We denote the node corresponding to such element jo. We can uniquely find its relevant color (i.e., (o((k.o))' oj, Ce, (k.)o)' (b2().)))) among the three multisets of c 's input, because only one (c} (k.j)) dy. will derive the pair of possible coordinates of jo. which is unique. Now, as we discussed in the proof of 3-FWL, we can reconstruct the whole geometry.
B.3.4 Proof of Universality for Scalars
We have shown in the preceding three subsections that for each M(O) E MinMods, there exists a parameter On such that M(O)) is complete for distinguishing all geometric graphs that are not congruent. Specifically, M(0s) generates a unique K Kddimensional intermediate representation for geometric graphs that are not congruent at the output block. According to Theorem 1 in Hordan et al. [2023). J. by passing the intermediate representation through MLP, M(0g) can achieve universality for scalars (note that MLPs are already included in the output block of MM).
B.3.5 Proof of Universality for Vectors
The key to proving universality for vectors of function gequiv is Proposition 10 proposed by Villar et al. 2022]. The goal is to prove that function f f= MLPs(hm/) can approximate all functions that are Iivarntt and permutation-invariat with respect nodes except the m-th node (We denote the corresponding group Gm.)
29

---

First of all, note that hm is 9m -ivvrrian... That's because he (v E V²) is invariant under 0(3) actions, and hn is obtained by pooling all the k-tuples whose first index is m. When permuting nodes except the w-th one, the multiset { vo = m. v E V* does not change. According to Theorem 4.1 in Hordan et al. 2023). prove that fontty is universal, we need to show that hm can distinguish inputs X E R on different Gm orbits.
To see this, recall that h... Soode [h vo = =m)), and as we demonstrated in the first three subsections, there always exists some h in the multiset hh" Vo m D that can reconstruct the entire geometry. For example, in the case of 3-F-DisGNN, if the point cloud does not degenerate into I-D point cloud, there must exist where Vo independent (for arbitrary m), which can reconstruct the entire geometry as demonstrated in [33.2] is worth noting that this reconstruction is started at the m-th node, thus if two point clouds share the same lmm. they must be related by a 9m action.
and which contains three nodes that are affinely
Finally, it is worth noting that an alternative perspective to understand the role of group 9m is through the universality for node-wise representation. fm- The statement "Two geometric graphs are related by Gm action" is equivalent to the statement "the two geometric graphs congruent, and the m-th nodes in the two geometric graphs are related by an autoisomorphism. " The ability of models to generate node representations that can separate different Im orbits implies their capability to generate universal node-wise representations, which is indeed a more powerful property than global universality.
B.4 Proof of Theorem 6.5
Delle Rose et al. [2023] is our concurrent work, which demonstrated that geometric 3-round 2-FWL and 1-round 3-FWL can distinguish all non-congruent geometric graphs. We refer the readers to read the proof provided by the work, and in comparison to our previous proof, they further make good use of the global properties, i.e., the multiset of all the tuple representations, to get several desired conclusions. In this subsection, we make use of their findings: Since 3-round 2-F-DisGNN and --round 3- 3-F-DisGNN are continuous versions of these methods and can achieve injectiveness with a parameter 0g they can also achieve completeness.
It is important to note that the update function of 2-F-DisGNNN can be used to implement that of 2-F-DisGNN: When the order is 2, the edge representation ely is simplified as e/j = (eij, hig). As
a result, the neighbor component of 2-F-DisGNN { (ha,, hxg)) ) E V is encompassed in the 1 1-neighbor component of 2-E-DisGNN (haj, e k E V Hence, the 3-round 2-E-DisGNN is also complete. When the round number is limited to 1, the update function of 3-E-DisGNN can also implement that of 3-F 3-F-DisGNN. This is due to the fact that during the initialization step. each 3-tuple is embedded based on the distance matrix. Consequently, the neighbor component of 3 3-F-DisGNN, & (hmmkk hamk, hijm)) m V}. solely represents the distance matrix of ijkm, which can be obtained from any s-neighbor component (s E [3)) of 3-E-DisGNN (It should be noted that when the iteration number is not 1, determining whether the update function of 3-E 3-E-DisGNN can implement that of 3-F-DisGNN is not trivial). Thus, the E-version DisGNNs are also complete. Moreover, as per our proof in Section B.3.4 they are also universal for scalars.
Discussion of universality for vectors. The primary obstacle to proving the universality of M E Minmodsext for vectors lies in the limited expressive power of individual nodes, which may not reconstruct the whole geometry. The problem cannot be easily solved by concating hy with the global universal representation h The two N -ode point clouds, if the two tuples are the same, we know that the two point clouds are related by an E(3) transformation and permutation of the N nodes. However, we cannot guarantee that the permutation (or there exists another permutation) maps the m-th node in the first point cloud to the m-th node in the second. For instance, even though two points in point cloud may not be related by an autoisomorphism, they may still have the same representation after applying M E Minmodsext (Possible counterexamples may be derived from this situation). As result, may not be universal for all Gm -invariaat functions, and requly may not be universal for all vector functions. We leave this as an open question.
V* J. Specifically, given (Ama h1) and (hma, h2) for
30

---

C
Detailed Model Design and Analysis
Radial basis f'unction. In k-DisGNNs, we use radial basis functions (RBF) febt - He to expand the distance between two nodes into an H He-dimension vector. This can reduce the number of learnable parameters and additionally provides a helpful inductive bias [Klicpera et al. 2020a]. The appropriate choice of RBF is beneficial, and we use nexpnorm RBF defined as
Sebt (eig)[k] = (e(exp((es))
(35)
where 3R are coefficients of the hth basis. Experiments show that this RBF performs better than others, such as the Bessel function used Klicpera al. [2020a] Gasteiger al. [202]]
Initialization function. We realize fint of k-DisGNNs' initialization block in Section 5 ass follows
finit (v)
(36)
iE[
where @ represents Hadamard product and O represents Hadamard product over all the elements in the subscript. fr Z + R= is learnable embedding function, fot R + R is radial basis function, and f2. f are neural networks such MLPs that maps the embeddings of and to the common continuous vector space RRK
finit can learn injective representation for long as the embedding dimensions high enough, just like passing the concatenation of že; and Evroy through an MLP. We chose this function form for the better experimental performance.
Note that by this means, tuples with different equality patterns [Maron et al. 2018 can be dis- tinguished, i.e., get different representations, without explicitly incorporating the representation of equality pattern. This is because in the context of distance graphs, tuples with different equality patterns will have quite different distance matrices (clements zero at the positions where two nodes are the same) and thus can be captured by finit-
Injective functions. We realize all the message passing functions as injective functions to ensure expressiveness. To be specific, we embed the multisets Equation 7
T0) and in output function with the injective multiset function proposed in Xu et al. [2018), and use the matrix multiplication methods proposed in Maron al. [019]] to implement the message passing functions k-F-DisGNN
(Equation
Inductive bias. Although theoretically there is need to distinguish tuples with different equality patterns explicitly. we still do so to incorporate inductive bias into the model for better learning. Specifically, we modify the initialization function and the output function as follows: 1. At the initialization step, we learn embeddings for different equality patterns and incorporate them into the results of Equation (36) through Hadamard product. At the output step, we separate tuples where all sub-nodes are the same and the others into different multisets. These modifications are both beneficial for training and generalization.
31

---

D Detailed Experiments
D.I Experimental Setup
Table Training settings.
MD17
revised MD17
QM9
Train set size Val. set size batch size
1000
950
100000
1000
50
10000
2
2
16
warm-up epochs
25
25
5
initial learning rate
0.001
0.001
0.0005
decay plateau patience (epochs)
15
15
10
decay on plateau cooldown (epochs)
15
15
10
decay plateau threshold
0.001
0.001
0.001
decay on plateau factor
0.7
0.7
0.5
Training Setting, For QM9, we use the mean squared error (MSE) loss for training. For MD17, we use the weighted loss function
(fo(X,z)
= (-xx,)) -
Pio (X,,)) (37)
Dxin
where the force ratio is fixed as 0.999 (For revised MD17, we set to 0.99 for several targets since the data quality is better).
We follow the same dataset split as GemNet [Gasteiger et al. 2021]. We optimize all models using Adam [Kingma and Ba 2014) with exponential decay and plateau decay learning rate schedulers, and also a linear learning rate warm-up. To prevent overfitting, we use early stopping on validation loss and exponential moving average (EMA) with decay rate 0.99 for model parameters during validation and test. We follow DimeNet's (Klicpera et al.. 2020a setting to calculate A by taking éLUMO éHоMO and the atomization energy for Uo, U, H and G on QM9. Experiments conducted on Nvidia RTX 3090 and Nvidia RTX 4090. Results are average of three runs with different random seeds. Detailed training setting can be referred to Table
Model hy pyprraaraseters. The key model hyperparameters we coarsely tune are the rbf dimension, hidden dimension, and number of message passing blocks. For rbf dimension,
use 16 for MD17 and 32 for QM9. We choose the number of message passing blocks from (4,5, 6). For hidden dimension, use 512 for 2-DisGNNs and 320 for 3-DisGNNs. The detailed hyperparameters can be found in our codes.
D.2 Supplementary Experimental Information
Discussion of results in MD17. In experiments MD17, most of the state-of-the-art perfor- mance we achieve is on force targets, and the loss on energy targets is relatively higher, see Table [] On force prediction tasks, k- A-DisGNNs rank top 2 on foree prediction tasks average, and outperform the best results by a significant margin on several molecules, such as aspirin and malonaldehyde. However, the results the energy prediction tasks relatively lower, with 2-F-DisGNN ranking 2nd and 3-F.DisGGNN ranking 4th
This is due to the fact that have assigned quite high weight (0.999) to the force loss during training, similar to what GemNet Gasteeigr et al. 2021] does. In comparison, TorchMD (Thöke and De Fabritiis 202T assigned weight of 0.8 to the force loss, resulting better results on energy targets, but not as good results on force targets.
Actually, in molecular simulations, force prediction is more challenging task. It determines the accuracy of molecular simulations and reflects performance of model better [Gasteiger et al.) 2021 (One can see that the energy performance of different models does not vary much). Therefore. makes more sense to focus on force prediction. Furthermore, previous researches [Batzner et al.) Christensen and Von Lilienfeld 2020 have found that models can achieve significantly lower
2022
32

---

energy loss on the revised MD17 dataset than on the original MD17 dataset, while holding similar force accuracy on the two datasets. As analyzed in Batzner et [022]. this suggests that the noise floor on the original MD17 dataset is higher on the energies, indicating that better force prediction results are more meaningful than energy prediction results on the original MD17 datasets.
Table 5: MAE loss revised MD17. Energy (E) in kcal/mol, force (F) in kcal/mol/A.
Target
MACE
Allegro
2F-Dis.
0.0507
0.0530
0.0465
aspirin
F
0.1522
0.1683
0.1515
E
0.0277
0.0277
0,0315
azobenz.
F
0.0692
0.0600
0.1121
E
0.0092
0.0069
0.0013
benzene
F
0.0069
0.0046
0.0085
E
0.0092
0.0092
0.0065
ethanol
F
0.0484
0.0484
0.0379
E
0.0184
0.0138
0.0129
malonal.
F
0.0945
0.0830
0.0782
E
0.0115
0.0046
0.0103
napthal.
F
0.0369
0.0208
0.0478
E
0.0300
0.0346
0.0310
paracet.
F
0.1107
0.1130
0.1178
E
0.0208
0.0208
0.0174
salicyl.
F
0.0715
0.0669
0.0860
E
0.0115
0.0092
0.0051
toluene
F
0.0346
0.0415
0.0284
E
0.0115
0.0138
0.0131
uracil
F
0.0484
0.0415
0.0828
Revised MD17. For a comprehensive comparison, also conducted experiments the revised MD17 dataset, which has higher data quality than original MD17, and compared with two state-of- the-art models, MACE [Batatia et al. [022] and Allegro [Musaelian al. 2023]. The results shown in Table 2-F- F-F-DisGNN achieved 10 best and 4 the second best results out of 20 targets. Note that MACE and Allegro are both models that leverage complex equivariant representations. This further demonstrates the high potential of distance-based models in geometry learning and molecular dynamic simulation.
Supplementary Results on QM9, We present the full results on QM9 Table We compare our model with 7 other models, including those that invariant geometric features: SchNet [Schütt) ct al. 2018). DimeNet [Klicpera al. 2020a), DimeNet++/KInn
uses group irreducible representations: Cormorant[Anderss (Klicpera et al. 2020b). a model that et al. 2019 those that use first-order
equivariant representations: TorchMD TThöke and De Fabritiis] 2021], PaiNN [Schütt et al.) 2021] and model that uses local frame methods: GNN-LF [Wang and Zhang 2022 We calculate the average improvements of all the models relative to DimeNet and list them in the table.
Table 6: MAE loss on QM9.
Target
Unit SchNet
Cormor.
Dim+Net+
Torchidd
PaiNN
GNN-LF
DimeNet
2F-Dis.
0.033
0.038
0.0297
0.002
0.012
0.013
0.0286
0.0100
dg
0.235
0.085
0.0435
0.01
0.045
0.0353
0.0469
0.0431
GHMо
meV
23.5
27.8
21.81
FLUMO
meV
17.8
20.4
17
19.7
21.22
Ac
meV
63
61
32.6
45.7
37.1
34.8
31.3
(R2))
of
0.073
0.961
0.331
0.015
0.066
0.037
0.331
0.0299
ZPVE
meV
1.7
2.027
1.21
2.12
1.28
1.19
1.29
1.26
Up
meV
14
22
6.32
6.24
5.85
5.3
8.02
7.33
me V
19
21
6.28
6.3
5.83
5.24
7.89
7.37
meV
21
6.53
6,48
5.98
5.48
8.11
7.36
meV
7.35
8.98
cal/ ral/mol/KK
0.033
0.026
0.023
0.026
0.024
0.022
0.0249
0.0233
Avg improv.
-78.99%
.98 22%
9.42%
25.00%
17.50%
27.82%
0.00%
18.83%
Rank
6
3
33

---

Although our models exhibit significant improvements on the MD17 datasets, their performance on the QM9 datasets is relatively less remarkable. This discrepancy may be attributed the fact that the QM9 datasets pose a greater challenge in terms of a model's generalization performance: Unlike MD17, QM9 comprises various kinds of molecules and regression targets. However, since k-DisGNNs rely purely on the fundamental geometric feature of distance, they may inherently require a larger amount of data to learn the significant geometric patterns within geometric structures and enhance their generalization performance, compared to models that explicitly incorporate equivariant representations or pre-calculated high-order geometric features. Nevertheless, we believe that such learning paradigm, which employs highly expressive models to extract information from the most basic components in a data- data-driven manner, has immense performance potential and will exhibit even greater performance gains when provided with more data points, increased model scales, better data quality or advanced pre-training methods, as already validated in fields such as natural language processing [Brown al. 20200 Devlin al., 2018), computer vision (Tolstikhin al., 2021 Liu et al. 2021 Dosovitskiy et al. 2020]. and molecule-related pre-training methods [Xia et al. 2023
Lu et al. 2023
D.3 Time and Memory Consumption
We performed experiments on the MD17 dataset to compare the training and inference time, as well as the GPU memory consumption of our models with their counterparts DimeNet and GemNet. The experiments are conducted on Nvidia RTX 3090, and the results are shown in Table
Table 7: Training time, inference time and GPU memory consumption on MD17. The batch size is
32 for 2-F-DisGNN, DimeNet and TorchMD, and 12 for 3-E-DisGNN and GemNet. Training time in ms, inference time in ms, inference GPU memory consumption in MB. Evaluated on Nvidia A100.
2FDis.
DimeNet
TorchMD
3EDis.
GemNet
Asp.
234/66/2985
270/74/5691
101/39/2072
873/273/18588
556/182/716 169
Ben.
92/24/1058
162/44/1815
110/41/905
224/61/3644
380/130/1789
Eth.
61/18/637
163/43/791
103/43/532
112/30/1561
462/158/804
Mal.
61/18/640
161/43/791
103/42/532
113/30/1561
356/1 18//1
Nap.
184/50/2193
238/68/4578
111/45/1692
652/185/1 1804
444/141/5253
Sal.
137/37/1758
206/58/3468
119/42/1401
458/127/8281
405/136/3778
Tol.
131/36/1560
200/54/3126
107/25/1326
399/109/6915
473/153/3328
Ura.
93/24/1058
169/45/1782
113/42/906
225/61/3644
369/136/1776
Avg.
124/34/1486
196/53/2755
108/39/1170
382/109/6999
430/144/3087
2-F-DisGNN demonstrates significantly better time and memory efficiency compared to DimeNet and GemNet. Even when compared to the quite efficient model, TorchMD, 2-F-DisGNN shows competitive efficiency. This is partly because it utilizes high-order tensors and employs dense calculation, resulting in significant acceleration complexity and high hidden dimension, 3-E 3-E-DisGNN shows relatively worse performance. Regarding this limitation, we have listed several possible solutions Section and recent work on simplifying and accelerating k-WL [Zhao et al. 2022 Morris et al. 2022] when k is large may also be applied, which is left for future work. Nonetheless, given that 2- 2-F-DiGGNN already satisfies the requirements for both theoretical (Section(6.) (6.3) and experimental (Section 7
GPUs. However, due to the high theoretical
performance, our primary focus lies on this model, and the analysis further emphasizes the practical potential of 2-F-DisGNN.
E Supplenmentary Related Work
There is a wealth of research in the field of interatomic potentials, which introduced various methods for modeling the atomic environment as representations [Bartók et al. 2010, 2013 Shapeev 2016)) Behler and Parrinello 2007]. In particular, ACE (Atomic Cluster Expansion) [rautz 2019 has presented framework that serves as unifying approach for these methods and can calculate high- order complete polynomial basis features with small cost regardless of the body order. Building on
Drautz 2019). Batatia et al. [2022 proposed GNN variant called MACE that can effectively exploit the rich geometric information in atoms' local environment. Additionally, Joshi et al. 20233 proposed
34

---

geometric variants of the WL test to characterize the expressiveness of invariant and equivariant geometric GNNs for the general graph setting. All Drautz [2019] Batatia al.] [2022]. Joshi et al. 2023 leverage the many-body expansion and can include k-tuples during embedding atom's neighbors, allowing atoms to obtain k-orderr geometric information from their local environments
like k-DisGNNS.
However, we note that there are key differences between these works (based many-body expansion) and k-DisGNNs in terms of their message passing units and use of representations. The former assumes that the total energy can be approximated by the sum of energies of atomic environments of individual atoms and therefore use atoms as their message passing units, while k- k-DisGNNs pass messages among k-tuples and pool tuple representations obtain global representation. In addition, while interatomic potential methods leverage equivariant representations to enhance their expres- siveness, k- d-DisGNNs completely decouple E(3)-symmetry and only use the most basic geometric invariant feature, distance, to achieve universality and good experimental results.
35


Reviews:
[{"review_id": "PHNyoOuAXd", "reviewer": "Reviewer_UsYi", "summary": "This work proposes neural networks for operating on distance matrices obtained from 3D/Euclidean point clouds. New architectures which generalise the k-WL/k-tuple higher order GNN framework (Morris et al.) to distance matrices are proposed, along with proofs of their universality/completeness for k=2 (scalar) and k=3 (vector predictions). The approach is evaluated to work as well or better than current geometric GNNs for small molecular tasks like MD17 and QM9.", "questions": "Questions and clarifications:\n\n- In Related Work, for Hordan-etal, 2023: I realise this is probably concurrent work, but isn't the Gram matrix and distance matrix interchangable?\n\n- In Section 4, for the family of counterexamples for 1-EWL and vanilla disGNNs: how do you see these counterexamples being useful or informing future research? (Beyond telling us what we already know from the counterexample of Pozdnyakov-Ceriotti.)\n\nSuggestions:\n\n- Lines 85-88: I would suggest stating that these results are for complete graphs.\n\n- Lines 130-135: It was unclear what orientation information meant in this context without a coordinate system. Orientation w.r.t. what?\n\n- Line 1293 - typo.\n\n- I would personally go with Geometric Graph Learning instead of GDL. I realise this is opinionated.", "limitations": "The authors have adequately addressed technical limitations but have not stated potential negative social impact. \n\nBeyond what the authors mention regarding scalability of their models, one major theoretical limitation of the proposed framework is that it is restricted to full geometric graphs, and the construction of complete/universal models for the general sparse graph setting remains an open question. This my be worth reiterating.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- This work presents a **novel** k-WL framework for complete distance graphs from Euclidean point clouds. New architectures for processing k-tuple distance graphs are proposed, in a spirit similar to influential work by Morris et al. (https://arxiv.org/abs/1810.02244) on higher order GNNs for standard graphs.\n\n- I believe the theoretical results showing that architectures based on 2-WL and 3-WL variants of the proposed test are complete for scalar/vector predictions on distance graphs is **significant**.\n\n- The proposed architectures are shown to **work as well or better** than existing geometric GNNs for small molecular simulation tasks (QM9, MD17, rMD17).\n\n- The procedures to construct families of counterexamples for 1-EWL and vanilla disGNNs are described in detail and seem interesting.", "weaknesses": "- I don't have major concerns.\n\n- Ambiguous claim re. Geometric Deep Learning: \n    - Geometric Deep Learning is a pretty broad field beyond point clouds embedded in Euclidean space. It includes Groups, Gauges, Meshes, Grids, and Graphs. I personally felt the title and claims within the paper could be perceived ambiguously because the findings of this paper are not directly applicable across **the entire** spectrum covered by GDL; it only covers geometric *graph* learning.\n    - Is this work relevant to other areas of GDL? If so, how?\n\n- Scalability: One major downside of the proposed approach of adapting higher order tuple-based GNNs to operate on distance graphs will be the computational cost of working with anything other than small molecules.\n    - On MD17/rMD17, the models use a batch size of 2. I suppose this is due to high memory usage.\n    - Regarding the experiments on timings in the appendix: this seems like an unfair comparison b/c one would naturally expect using dense tensor-based implementations like yours to be much faster than PyG implementations of DimeNet/GemNet (especially for small molecule graphs with tens of nodes). \n    - **Is it possible to compare apples-to-apples the timing/memory usage of dense implementations of DimeNet/GemNet, too?**\n    - I see this paper's main contribution to be theoretical, so I don't think this is a major concern.\n\n- I had difficulty following Proof B.3.1. Perhaps proving a proof sketch or some warmup text outlining the proof techniques may be helpful, especially as it spans several pages. \n    - (It may be that I need more time to study the proof in further detail.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer UsYi for their detailed and insightful review. We address the comments below.\n\n> W1: Ambiguous claim re. Geometric Deep Learning\n\nThanks for the insightful comment. Indeed, in this paper, we mainly use the term geometric deep learning to refer to learning over points embedded in 3D Euclidean space, such as general point clouds and molecules, but do not cover the more broad types of non-Euclidean data such as manifolds and meshes. We will make it clear in the revision. Beyond that, we also notice that the most important applications of GDL lie in networks, graphics, particle physics, molecules, etc., which can all be represented by points with some coordinates and/or local affinity defined, thus may be solved by our methods. Therefore, we expect our k-DisGNNs to become a general technique for a wide range of GDL problems beyond the problems considered in the paper.\n\n> W2-1: … to compare apples-to-apples … with dense … DimeNet/GemNet.\n\nWe agree that it’s necessary to compare their performance and efficiency apples-to-apples. We’ve implemented a dense-version DimeNet/GemNet by replacing all the sparse operations (mainly “scatter”) with dense matrix multiplications and tested their performance. The results are shown in Table 1 in the PDF (in global rebuttal). As can be observed, the dense operation **does not bring obvious performance boost for the two models**. This is expected, since the graphs they process have relatively high sparsity. And GemNet’s official code has already been optimized to be much efficient. Thus its performance did not change much after we rewrote it.\n\nThe results show that our universal (scalar) model 2F-DisGNN is more efficient compared to the two models and also achieves much better performance. Please refer to our response to W1 raised by Reviewer fGWC for more analysis of Table 1.\n\n> W2-2: … I suppose this is due to high memory usage.\n\nWe clarify that it is not due to memory usage, but rather for improved generalization performance. This approach is similar to what is mentioned in Appendix E of GemNet.\n\n> W3: I had difficulty following Proof B.3.1. Perhaps proving a proof sketch … may be helpful …\n\nThanks for the valuable suggestion, and we will include a proof sketch in our revised paper for better elaboration. Due to words limit of author rebuttal, we would like to provide the proof sketch in discussion period.\n\n> Q1: … isn't the Gram matrix and distance matrix interchangable?\n\nWhile they are interchangeable when they represent the entire graph, this interchangeability diminishes when they are **constrained to represent local tuples**. For example, if one takes the Gram matrix of a 3-tuple ijk as its initial representation (as done in Appendix B.2. in Hordan-etal), actually 6 distances are encompassed: 3 distances among ijk, and additional 3 distances from ijk to the center c. However if one takes the distance matrix of ijk (as we done), only the distances among ijk are given. So it could be more challenging to recover the whole geometry from distance matrix, **and it can be more “clean” and significant**: pair-wise distance can provide more **inductive bias** for modeling interaction intensity or relationship between nodes (compared to pair-wise angles w.r.t. center).\n\nFurthermore, it is noteworthy that Hordan-etal's primary model, as detailed in their main body, leverages coordinate projection more than Gram matrix (see Eq. 3 of Hordan-etal's). This approach, while potentially more straightforward, could negatively impact the inductive bias mentioned previously, thereby may limit its real-world applicability (see Table 2 of Hordan-etal 2023).\n\n> Q2: … how do you see these counterexamples being useful or informing future research?\n\nBy understanding the symmetry contained in the counterexamples, researchers can design more powerful geometric models by breaking such symmetry. This is in spirit similar to those works in traditional GRL, such as subgraph GNNs$^{[1]}$: For example, by just embedding the 1-hop geometric subgraph around each node in Fig.1 in our paper, Vanilla DisGNN can easily distinguish the two geometric graphs. This approach could inspire complete but more efficient models. We are exploring it in our future work.\n\n> Suggestion: … Orientation w.r.t. what?\n\nWe clarify that what we mean in line 128 is, by combining the universal scalar with coordinates in a specific coordinate system (what orientation means here), powerful equivariant values can be produced. We do not suggest that orientation can be represented without a coordinate system. However, coordinate systems here only provide a reference to characterize the orientation of equivariant targets, and only appear at the output head of models, resulting in a cleaner model design. Examples include Theorem 6.2’s third property and calculating the derivative of molecule’s energy w.r.t. atoms’ coordinates to obtain force vectors acting on atoms.\n\nAnd thanks a lot for the other suggestions! We will continue to refine our statements.\n\n> Limit: One major theoretical limitation …\n\nWe thank the insightful comment from the reviewer; it's indeed an interesting topic for discussion. Our opinion on this point inclines towards a positive outlook: distance matrix itself can be somehow abundant, since it contains n*n elements while only corresponds to n individual nodes. Appropriately sparsifying it may not influence the geometric structure represented by it, thus may not influence the theoretical completeness. An intuitive understanding is: a point’s position can be determined with at most 4 distances (to 4 affinely independent points), so the remaining n-5 distances might be deemed redundant. It is an intriguing subject to study how to appropriately sparsify it while maintaining the good experimental results. We will explore it in our future work.\n\nThanks again for the comments! We hope our response can address the problems.\n\n[1] Zhang, Muhan, and Pan Li. \"Nested graph neural networks.\""}, {"review_id": "kURvPkgloj", "reviewer": "Reviewer_w5WJ", "summary": "In this paper, the authors argue that the distance matrix associated with a geometric graph is sufficient to build powerful geometric neural networks.\nIn particular, the paper proposes a new family of graph architectures, named k-DisGNN, operating on a complete graph with node distances on the edges.\nThese architectures, inspired by the k-WL test (and its variations like the k-FWL or k-EWL tests), are able to model higher-order geometric information, which makes them more expressive than vanilla message-passing networks and ensures their universal approximator property.\n", "questions": "I am not sure I understand the difference between Eq. 4 and 5.\nIt seems to me that the indices $j$ and $w$ are just swapped, but in the end the set contains the same tuples.\nCould you clarify this?\n\n\nlines 197-203: I think that writing the message passing block explicitly would improve the clarity of the paper (rather than explaining it by discussing how it differs from Eq. 4 and 5).\nSimilarly, in line 216, it would be useful to explicitly include the message passing equation of k-E-DisGNN.\n\n\nIn Sec. 5 k-DisGNN and k-F-DisGNN refer to two different models (using respectively the k-WL and k-FWL paradigms for message passing) but in Sec. 7 k-DisGNN seems to be used to refer to both 2-F-DisGNN and 3-E-DisGNN in an abstract way.\nThis seems confusing.\n\n\nAre you results valid only for 3D data or do these results generalize to any dimension?\n", "limitations": "The authors explicitly addressed the limitations of the work in the main paper.\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and well motivated.\nThe proposed ideas lead to a relatively simple yet expressive design to process geometric graphs.\nThe experiments support the theoretical results in the main paper.\n\n\nIn addition, the supplementary materials include a number of examples where message-passing networks fail to distinguish geometric graphs.\nThese interpretable examples can be useful to understand the limitations of existing and future architectures.\n", "weaknesses": "\nSome details about the proposed models were not completely clear to me, although this might be due to my little familiarity with Weisfeiler-Leman algorithms.\nStill, I think the presentation could be made a bit clearer, see Questions section.\n\nI don't see major flaws in this paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer w5WJ for the insightful and detailed comments. We address the comments below.\n\n> I am not sure I understand the difference between Eq. 4 and 5. It seems to me that the indices j and w are just swapped, but in the end the set contains the same tuples. Could you clarify this?\n\nThanks for the question. It is correct that WL and FWL process identical tuples, but they are different in their ways of grouping these tuples. FWL groups tuples in a more compact way: It first groups all tuples associated with a given point $j$ (Eq. 3), then proceeds to iterate through such points (Eq. 5) in a multiset. WL first groups all tuples associated with the $j$-th position (Eq. 2), then enumerates the position (Eq. 4). Notably, while it's possible to derive WL's input from that of FWL, the reverse process is not feasible. This asymmetry highlights the expressiveness advantage of FWL over WL methods intuitively.\n\n> I think that writing the message passing block explicitly would improve the clarity of the paper (rather than explaining it by discussing how it differs from Eq. 4 and 5). Similarly, in line 216, it would be useful to explicitly include the message passing equation of k-E-DisGNN.\n\nWe thank the valuable suggestions from the reviewer. Due to the page limit, the details of the message passing blocks are included in Appendix C. We will add a hyperlink to it in the main paper.\n\n> in Sec. 7, k-DisGNN seems to be used to refer to both 2-F-DisGNN and 3-E-DisGNN in an abstract way. This seems confusing.\n\nWe thank the reminder from the reviewer. Indeed, we define k-DisGNN**s** (with an additional \"s\" at the end) as a general term for various versions of k-DisGNN models, see the first paragraph in Sec. 5. Throughout Sec. 7, we continue to refer to these models as \"k-DisGNNs\" by a general name. We will highlight this definition in the text.\n\n> Are you results valid only for 3D data or do these results generalize to any dimension?\n\nThe theoretical results, specifically theorems 6.4 and 6.5, can generalize to high-dimension situations since $n$D Euclidean space ($n > 3$) shares similar topological properties as 3D space. For example, in $n$D space, one point’s position can be determined to at most two possible candidates if given the distances between the point to n affinely independent points. And these two candidates are mirrorly symmetric w.r.t. the hyper-plane formed by the n points, which is a strong geometric constraint in $n$D space -- similar to the one we repeatedly use in the proof of 3D situations. Thus one could, for example, similarly prove that 3-round $(n-1)$-E/F-DisGNN or 1-round $n$-E/F-DisGNN are universal scalar function approximators over geometric graphs in $n$D space. However, we mainly focus on 3D situations because the real-world structures of most concerns, such as molecules or general point clouds, are 3D data. Nevertheless, we all agree on the importance of generalizing the results to the $n$D situation, which we will refine in our future work.\n\n\n\nThanks again for the comments, and we hope our response can address the problems."}, {"review_id": "hU7AkJ04ql", "reviewer": "Reviewer_5v5F", "summary": "The paper proposes $k$-DistGNNs, a sequence of k-(F)WL-like models that operate on the distance matrix of a geometric graphs. These models are able to compute higher-order geometric invariants, generalise existent models, and for certain values of $k$ are shown to be able to approximate any geometrically invariant or equivariant functions. The model is evaluated against other SOTA models on standard molecular benchmarks. Additionally, the paper proposes a procedure to generate new counter-examples of geometric graphs that cannot be distinguished by MPNNs operating on the distance matrix. ", "questions": "N/A", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-\tThe paper is very well written and easy to follow. \n-\tThe expressive power of Geometric GNNs is a relatively new and unstudied topic, and the paper makes an important contribution in this regard. \n-\tThe proposed approach is a simple, but powerful, extension of k-WL to distance matrices and implicitly geometric graphs.\n-\tThe evaluation shows that the proposed models perform very well on standard benchmarks against the latest geometric models (outperforming them in some tasks)\n-\tThe universal approximation properties of the model are very attractive and back up the claim that the distance matrix is “enough”. Although, the question in the title is somewhat rhetorical since the distance matrix fully determines geometric graphs. So just from that, it follows the information contained inside is enough. \n-\tThe new counterexamples that the paper provides are very welcome as well as the general procedure used to generate them.\n", "weaknesses": "- Note that WL generalisations for Geometric GNNs were also studied in _On the Expressive Power of Geometric Graph Neural Networks_ (ICML 2023), which is not mentioned in the text as far as I could see. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer 5v5F for the careful review. We address the comments below.\n\n> Note that WL generalisations for Geometric GNNs were also studied in On the Expressive Power of Geometric Graph Neural Networks (ICML 2023), which is not mentioned in the text as far as I could see.\n> \n\nThanks for the reminder. Indeed, we have noticed the great work \"On the Expressive Power...\", which offers a comprehensive analysis of the expressive abilities of geometric graph neural networks. In Appendix E of our paper, we briefly discussed the similarities and differences between our work and theirs, and will further discuss the work in detail in the revised version.\n\nWe hope our response can address the problems, and please let us know if you have additional questions."}, {"review_id": "b1NstaLoSh", "reviewer": "Reviewer_fGWC", "summary": "This paper proposes k-DisGNNs, that can use distances alone to represent higher-order interactions, instead of the direct use of angles, torsional angles, and dihedral angles. The authors try to build a bridge between geometric deep learning and the traditional expressiveness of graph representation learning without geometric information. They conduct experiments mainly on MD17 and show results on QM9 in the appendix. For MD17, 2F-Dis. and 3E-Dis. are comparable and SOTA, but for QM9 (still small geometric graphs), 2F-Dis. is worse than several previous works and 3E-Dis. can not be implemented due to high complexity, which means their method with higher k cannot extend to larger geometric graphs with more nodes.", "questions": "As listed above in weaknesses.", "limitations": "They mentioned the limitations in the main paper. More potential limitations are listed above. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The first work to use distances alone to represent higher order geometric information including angles, torsional angles, and dihedral angles.\n2. They establish a connection between geometric deep learning (GDL) and traditional graph representation learning (GRL).\n3. Good performances of k=2 model on MD17.\n4. Figures are good and informative. ", "weaknesses": "1. Prohibitive Computational Costs for k > 2: The computational demands associated with the proposed method escalate dramatically when k > 2, as demonstrated in the appendix. Specifically, when k is set to 3, the model becomes computationally infeasible for the QM9 dataset, which comprises small molecules.\n\n2. Lack of Scalability and Performance for k = 2: When applied to the modestly-sized MD17 dataset, the method exhibits satisfactory performance with k = 2. However, this performance deteriorates markedly when transitioning to the more extensive QM9 dataset. The method's performance, as evaluated with 2F-Dis, fails to measure up to that of prior approaches such as TorchMD, GNN-LF, and PaiNN. \n\n3. The writing about the message passing mechanism lacks clarity and is hard to follow.\n\nMajor Concern: The major limitation of the proposed method is its inability to maintain the good performances when scaling to larger datasets, particularly QM9 concerning small molecules with not so many atoms. This significantly constrains the method's applicability and undermines its contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer fGWC for the careful and detailed review. We address the comments below.\n\n> W1: Prohibitive Computational Costs for k > 2: The computational demands ... escalate dramatically when k > 2, ..., when k is set to 3, the model becomes computationally infeasible for the QM9 dataset, ...\n> \n\nThanks for raising the concern. To respond, we re-measured the computational cost of all models presented in Table 7 of our paper, and added an additional efficient and high-performing model, TorchMD$^{[1]}$, for comparison. The new results are shown in Table 1 of the PDF (see global rebuttal). Additionally, we tested the dense version of Dime/GemNet for reference (please see Weakness 2 raised by Reviewer UsYi and our response).\n\n1. We first recognize that the memory usage does increase dramatically due to the global message passing for k > 2. Nevertheless, we have already **discussed potential solutions** in both Sec. 8 and Appendix D.4 of our paper. Also, please note that 3-E-DisGNN is even **faster than** its counterpart GemNet on MD17.\n2. We clarify that 3-E-DisGNN is still **computationally feasible** for QM9, although taking longer to train and tune due to the larger amount of training data points. In Fig. 1 of the PDF, we show the train/validation loss curves of 3-E-DisGNN on QM9 in the first tens of epochs, which are converging normally and approaching the validation accuracy of 2-F-DisGNN, thus validating the feasibility. Please note that 2-F-DisGNN is already a complete model on QM9, therefore we mainly focus on its performance.\n3. We finally would like to emphasize that **the primary model we propose is 2-F-DisGNN**, which is proven to be universal for scalar functions (the most cases concerned) and exhibited great experimental performance. As shown in Table 1, 2-F-DisGNN is \\~2x more efficient (both in speed and memory usage) compared with DimeNet and 4x\\~7x more efficient compared with GemNet on md17, while having significantly better prediction results. It is competitive even when compared to the efficient model TorchMD.\n\n> W2: Lack of Scalability and Performance for k = 2: ... performance deteriorates markedly when transitioning to the more extensive QM9 dataset ... method's performance ... fails to measure up to that of prior approaches such as TorchMD ...\n> \n\nWe first clarify that the performance of 2-F-DisGNN does not “deteriorate markedly” on QM9: As shown in Table 6 in the appendix, 2-F-DisGNN is highly competitive with the baselines, with 14.27% gain over DimeNet compared to the SOTA models TorchMD (25%) and GNN-LF (27.82%).\n\nNevertheless, we acknowledge that we have spent less time tuning 2-F-DisGNN on QM9 compared to MD17. Therefore, we further tuned it during the rebuttal period. The results are now presented in Table 2 of the new PDF.\n\nWe believe a data-driven model relying on pure distance needs a bit more layers to extract the various geometric information from more extensive dataset like QM9, as we discussed in Appendix D.3 of the paper. So what we have added to the model is just several residual layers in interaction or output blocks. Note that this addition does minor effect to the efficiency of the model.\n\nAs shown in Table 2, though we have limited time to perform tuning and only tuned several targets, the model gains a **consistent improvement** on all targets we tuned, especially on $\\epsilon_{HOMO}$, $\\epsilon_{LUMO}$ and $\\Delta \\epsilon$. On $\\Delta \\epsilon$, it even achieves a **new SOTA** result of 31.96. Also please note that target $U$ to $G$ share similar property with $U_0$, thus will also  We believe with further tuning, maybe by stacking more residual layers to extract the intermediate geometric reprentations (as is commonly done in chemical/physical models such as Phys$^{[2]}$/Dime/GemNet) or applying pre-training methods$^{[3,4]}$, one could further release the potential of DisGNNs. Additional discussion regarding potential methods to enhance performance can be seen in Appendix D.3 of our paper.\n\nMoreover, we also conduct some preliminary experiments on 3BPA during rebuttal, a dataset testing the performance of models on out-of-domain data (See Sec. 5.3.2 in [5] for more details). We compared our models to SOTA models shown in [5], and the results are shown in Table 3 in the PDF. As one can see, our model shows competitive or better performance compared to the other models using complicated equivariant representations. Additional improvements could be achieved by further tuning (we only tuned for two rounds due to the time limit).\n\nFinally, we emphasize that DisGNNs are purely data-driven models based on distance matrices, without using any domain-specifc knowledge like the angles in DimeNet and dihedral angles in GemNet. We believe the potential of such a highly-expressive data-driven model is significant, as already validated in fields like NLP, CV and molecule pretraining methods$^{[3,4]}$. We will continue to improve and evaluate our models. Thanks again for the insightful comment!\n\n> W3: The writing about the message passing mechanism lacks clarity and is hard to follow.\n> \n\nThanks for the valuable comment. Due to the page limit, the formulaic details of the message passing blocks are included in Appendix C, and we will add a hyperlink in the main body for better presentation.\n\nFor the Major Concern, Please see our response to W1 and W2.\n\n[1] Thölke, et al. \"Torchmd-net: equivariant transformers for neural network based molecular potentials.\" (2022).\n\n[2] Unke, et al. \"PhysNet: A neural network for predicting energies, forces, dipole moments, and partial charges.\" (2019).\n\n[3] Zhou, Gengmo, et al. \"Uni-Mol: a universal 3D molecular representation learning framework.\" (2023).\n\n[4] Zaidi, Sheheryar, et al. \"Pre-training via denoising for molecular property prediction.\" (2022).\n\n[5] Batatia, et al. \"MACE: Higher order equivariant message passing neural networks for fast and accurate force fields.\" (2022)."}]

Author rebuttal:
We sincerely thank all the reviewers for their careful reading, and the thoughtful and detailed comments! The **figures** and **tables** referred to in separate responses are included in the following supplementary **PDF** file.

Best,

Authors.

Meta-review: The paper studies the expressive power of GNNs on geometric graphs, i.e., graphs with Euclidean node embeddings. The paper discusses several failure cases and suggests novel GNN architecture that solves these failures. All reviewers as well as the AC appreciated the contributions in this paper and supported acceptance.
Decision: Accept (poster)