# On the Completeness of Invariant Geometric Deep Learning Models

Zian Li  Xiyuan Wang  Shijia Kang  Muhan Zhang

###### Abstract

Invariant models, one important class of geometric deep learning models, are
capable of generating meaningful geometric representations by leveraging
informative geometric features. These models are characterized by their
simplicity, good experimental results and computational efficiency. However,
their theoretical expressive power still remains unclear, restricting a deeper
understanding of the potential of such models. In this work, we concentrate on
characterizing the theoretical expressiveness of invariant models. We first
rigorously bound the expressiveness of the most classical invariant model,
Vanilla DisGNN (message passing neural networks incorporating distance),
restricting its unidentifiable cases to be only those highly symmetric
geometric graphs. To break these corner cases’ symmetry, we introduce a simple
yet E(3)-complete invariant design by nesting Vanilla DisGNN, named GeoNGNN.
Leveraging GeoNGNN as a theoretical tool, we for the first time prove the
E(3)-completeness of three well-established geometric models: DimeNet, GemNet
and SphereNet. Our results fill the gap in the theoretical power of invariant
models, contributing to a rigorous and comprehensive understanding of their
capabilities. Experimentally, GeoNGNN exhibits good inductive bias in
capturing local environments, and achieves competitive results w.r.t.
complicated models relying on high-order invariant/equivariant representations
while exhibiting significantly faster computational speed.

Machine Learning, ICML

##  1 Introduction

Learning geometric structural information from 3D point sets constitutes a
fundamental requirement for various real-world applications, including
molecular property prediction, physical simulation, and point cloud
classification/segmentation (Schmitz et al., 2019; Sanchez-Gonzalez et al.,
2020; Jumper et al., 2021; Guo et al., 2020).

In the context of designing geometric models for 3D point sets, a pivotal
consideration involves ensuring that the model respects both permutation
symmetry and Euclidean symmetry (i.e., symmetry of SE(3) or E(3) group). This
requirement necessitates the incorporation of appropriate inductive biases
into the architecture, ensuring that the model’s output remains invariant or
equivariant to point reordering and 3D rigid motion (and potentially
reflection).

However, these restrictions on symmetry can impose limitations on the ability
of models to approximate a broad range of symmetric functions. For example,
Message Passing Neural Networks (MPNNs) (Gilmer et al., 2017), a wide class of
Graph Neural Networks (GNNs), learn permutation symmetric functions w.r.t.
node reordering. However, it has been shown that such functions are not
universal (Xu et al., 2018; Morris et al., 2019), leading to the development
of more expressive GNN frameworks (Maron et al., 2018; Morris et al., 2019;
Zhang et al., 2023). Similar challenges arise in the geometric setting, where
models must additionally respect the Euclidean symmetry, and achieving
universality becomes a non-trivial task as well.

Recent studies (Pozdnyakov & Ceriotti, 2022; Li et al., 2023b) have
demonstrated that a simple invariant geometric model, SchNet (Schütt et al.,
2018), which incorporates Euclidean distance into MPNNs, is not E(3)-complete,
failing to distinguish pairs of non-E(3)-isomorphic geometric graphs. In order
to design more powerful invariant geometric models, recent works (Gasteiger et
al., 2019, 2022; Schütt et al., 2018) incorporate higher-order geometric
information or leverage spherical coordinates, making their models able to
identify some corner symmetric cases. However, these works do not provide a
theoretical completeness guarantee; thus, whether these models have the
potential to achieve completeness is still to be studied.

In this work, we for the first time analyze the completeness, i.e., ability to
distinguish any non-isomorphic geometric graphs, across a wide range of
invariant geometric models. Completeness is important since it is equivalent
to the ability of models to universally approximate corresponding functions
(Hordan et al., 2023).

We begin by revisiting Vanilla DisGNN, the simplest conceptual invariant model
augmenting MPNNs with distance as an edge feature (SchNet is a concrete
implementation of it), with a specific emphasis on addressing the question:
when is Vanilla DisGNN powerful enough? We demonstrate that Vanilla DisGNN can
effectively acquire global geometric information and achieve lossless encoding
for geometric graphs under the condition that there exists two distinct global
anchors. Consequently, we establish that Vanilla DisGNN is a
nearly-E(3)-complete model by restricting all its unidentifiable cases into a
small subspace that only contains well-defined highly-symmetric geometric
graphs.

To break these unidentifiable cases’ symmetry and enhance Vanilla DisGNN’s
expressiveness, we introduce GeoNGNN, the geometric counterpart of NGNN (Zhang
& Li, 2021) (one of the simplest subgraph GNNs), which runs Vanilla DisGNN in
a nested way. We theoretically establish that GeoNGNN is an E(3)-complete
geometric model, capable of identifying all geometric graphs. We also propose
an SE(3)-complete variant of GeoNGNN, named GeoNGNN-C, which is capable of
bracing chirality and learning different representations for pairs of
enantiomers.

Importantly, GeoNGNN serves as a tool for proving other invariant models’
expressiveness: By reducing three well-established invariant geometric models,
DimeNet (Gasteiger et al., 2019), SphereNet (Liu et al., 2021) and GemNet
(Gasteiger et al., 2021), onto GeoNGNN, we for the first time demonstrate that
these models are all capable of achieving E(3)-completeness under certain
conditions.

Our theoretical findings narrow the gap between experimental advancements and
theoretical characterizations of invariant geometric models during these
years, contributing to a rigorous and comprehensive understanding of their
capabilities. Most importantly, the findings suggest that the geometric graph
isomorphism problem is fundamentally easier than the traditional graph
isomorphism problem, indicating that achieving geometric completeness is not
as intractable as that in the traditional setting.

Despite not focusing on model enhancement, we still thoroughly evaluate
GeoNGNN on diverse datasets. GeoNGNN achieves competitive performance to
models that incorporate complicated high-order invariant or equivariant
representations, and demonstrates significantly faster speed when applied to
large molecules (with up to 300 atoms).

##  2 Preliminary

###  2.1 Notations and Definitions

Notation. We represent a 3D geometric graph with $n$ nodes as its minimal
representation, i.e., point clouds: $G=(X,P)$, where $X\in\mathbb{R}^{n\times
d}$ and $P\in\mathbb{R}^{n\times 3}$ represents the initial node features and
3D Cartesian coordinates of the $n$ nodes respectively. Euclidean distance
between node $i$ and $j$ is represented by $d_{ij}$.

######  Definition 2.1.

(E(3)-isomorphic) Two geometric graphs $G^{(1)},G^{(2)}$ are E(3)-isomorphic
if they have the same node number $n$, and there exist permutation matrix
$\mathcal{P}\in\\{0,1\\}^{n\times n}$, rotation/reflection matrix
$\mathcal{R}\in O(3)$ and translation matrix $\mathcal{T}\in\mathbb{R}^{3}$
such that $\mathcal{P}X^{(1)}=X^{(2)}$ and
$(\mathcal{P}P^{(1)})\mathcal{R}^{T}+\mathcal{T}=P^{(2)}$ ($+$ considers
broadcast).

######  Definition 2.2.

(Identifiability and E(3)-completeness) Let $f$ be a permutation- and
E(3)-invariant algorithm that takes geometric graphs $G$ with arbitrary size
as input, and outputs scalars $s\in\mathbb{R}^{k}$. We say $f$ can identify
$G$, if for an arbitrary geometric graph $G^{\prime}$ that is not
E(3)-isomorphic to $G$, $f(G)\neq f(G^{\prime})$. We say $f$ is E(3)-complete,
if given two arbitrary geometric graphs $G^{(1)}$ and $G^{(2)}$,
$f(G^{(1)})=f(G^{(2)})\iff G^{(1)}$ and $G^{(2)}$ are E(3)-isomorphic.

It is easy to see that identifiability and E(3)-completeness are related: $f$
can identify all geometric graphs $\iff$ $f$ is E(3)-complete. However,
identifiability provides a more fine-grained characterization of
E(3)-incomplete models. In the analysis of Vanilla DisGNN’s
E(3)-incompleteness, we concentrate on the commonality of its unidentifiable
graphs.

Depending on the context, the terms expressiveness or power are used to
describe the capability of algorithms to distinguish between non-isomorphic
topological graphs or non-E(3)-isomorphic geometric graphs.

During the theoretical analysis, we are particularly concerned about powerful
encoders that encode input representations without significant information
loss. We provide a formal definition of an important concept derive below:

######  Definition 2.3.

(Derive) Given input representations $I\in\mathcal{I}$, let
$f:\mathcal{I}\to\mathcal{O}_{1}$ and $g:\mathcal{I}\to\mathcal{O}_{2}$ be two
property encoders defined on $\mathcal{I}$. If there exists a function
$h:\mathcal{O}_{1}\to\mathcal{O}_{2}$ such that for all $I\in\mathcal{I}$,
$h(f(I))=g(I)$, we say that $f$ can derive $g$. With a slight abuse of
notation, we say that $f(I)$ can derive $g(I)$, denoted as $f(I)\to g(I)$.

For example, consider the space $\mathcal{I}$ comprising all geometric graphs.
Let $f$ denote an encoder that computes $f(I)=(\sum_{i=0}^{n-1}P_{i},n)$,
which represents the sum of the nodes’ coordinates and the number of nodes,
while $g$ being an encoder calculating the geometric center of $I$, it follows
that $f(I)\to g(I)$. Note that derivation exhibits transitivity: if $f_{1}\to
f_{2}$ and $f_{2}\to f_{3}$, it follows that $f_{1}\to f_{3}$.

Different from identifiability, which describes a given algorithm’s ability to
distinguish geometric graphs, “derive” is a broader concept describing the
relation of two intermediate properties, i.e., whether a property $f(I)$
contains all the information needed to calculate $g(I)$. However, they are
also related: consider $\mathcal{I}$ being the geometric graph space and $f$
satisfying permutation- and E(3)-invariance, then: $f(I)\to I$ up to
permutation and E(3)-transformation $\iff$ $f$ is E(3)-complete $\iff$ $f$ can
identify all $I\in\mathcal{I}$. The proof is presented in Appendix F.1.

###  2.2 Vanilla DisGNN

To leverage the rich geometric information present in geometric graphs, an
early and straightforward approach is to use the pair-wise Euclidean distance
$d_{ij}$ as a basic geometric feature. This approach applies MPNNs on the
distance graph with a weighted edge $e_{ij}$ between any pairs of nodes $i,j$
if $d_{ij}\leq r$ ($r$ is some predefined cutoff). SchNet (Schütt et al.,
2018) is a representative of such works.

To be specific, Vanilla DisGNN models first embed atoms based on their initial
feature $X$, such as atomic numbers, obtaining $h_{i}^{(0)}$ for node $i$.
They then perform message passing according to the following equation
iteratively:

$h_{i}^{(t+1)}=f_{\text{update}}^{(t)}\left(h_{i}^{(t)},f_{\text{aggr}}^{(t)}\left(\\{\\!\\!\\{(h_{j}^{(t)},d_{ij})\mid
j\in N(i)\\}\\!\\!\\}\right)\right),$ (1)

where $h_{i}^{(t)}$ represents the node embedding for node $i$ at time step
$t$, $N(i)$ denotes the neighbor set of node $i$. The global graph embedding
is then obtained by aggregating the representations of all nodes using a
permutation-invariant function $f_{\text{out}}(\\{\\!\\!\\{h_{i}^{T}\mid
i\in[n]\\}\\!\\!\\})$, where $T$ is the total number of layers and $n$ is the
total number of nodes.

If the hidden dimension is sufficiently large and the intermediate functions
used are powerful enough (Hornik et al., 1989; Zaheer et al., 2017; Xu et al.,
2018), the intermediate functions can be learned to be nearly injective,
resulting in lossless transformation. We regard this as a default assumption
throughout the theoretical analysis. This assumption is reasonable since the
expressive power of models/algorithms is fundamentally limited by their
framework design (Xu et al., 2018; Maron et al., 2018; Morris et al., 2019),
rather than layer width. Furthermore, in our theoretical analysis, we assume
that $N(i)$ is $[n]$ by default, i.e., global message passing, which grants
models the maximum expressiveness (we aim to study their maximal potential).
Note that both assumptions align with existing works in the literature (Li et
al., 2023b; Pozdnyakov & Ceriotti, 2022; Delle Rose et al., 2023; Dym & Maron,
2020; Hordan et al., 2023).

###  2.3 Nested Graph Neural Network

Nested GNN (NGNN) (Zhang & Li, 2021) is a subgraph GNN proposed initially in
traditional graph representation learning field. The algorithm performs a two-
level GNN on a given graph. The first level, known as the inner GNN, runs
concurrently on each node’s $k$-hop ego subgraph with the center node
optionally marked (gives it a distinct feature), summarizing the local
subgraph information as the nodes’ initial embedding in the original graph.
Then, the second level, referred to as the outer GNN, runs on the original
graph to obtain the final node and graph representations.

NGNN encodes nodes’ local subgraph information as their initial embeddings,
rather than subtree information, which makes it strictly more powerful than
MPNNs such as GIN (Xu et al., 2018). However, Zhang et al. (2023) pointed out
that NGNN is a relatively weaker subgraph GNN in learning topological graph
structures than Qian et al. (2022); Zhao et al. (2021); Bevilacqua et al.
(2021); Frasca et al. (2022), since it does not contain cross-subgraph
operations which pass messages across different subgraphs. In our work, we
present a surprising result, showing that in geometric settings, NGNN is
indeed sufficient.

##  3 How powerful is Vanilla DisGNN?

In Pozdnyakov & Ceriotti (2022); Li et al. (2023b), researchers have carefully
constructed pairs of symmetric geometric graphs that Vanilla DisGNN cannot
distinguish to illustrate its E(3)-incompleteness. However, rather than
relying on hand-crafted finite pairs of counterexamples and intuitive
illustration, a more significant question arises: what properties do all the
geometric graphs that Vanilla DisGNN cannot identify share in common? Only
after theoretically characterizing these corner cases can we describe and
bound the expressiveness of Vanilla DisGNN in a finer way, and then design
more powerful geometric models accordingly by “solving” these corner cases.

In this section, we begin by demonstrating the inherent ability of Vanilla
DisGNN to locate “anchors”, which enables the model to capture global
geometric information. Subsequently, we present an essential theorem that
establishes how Vanilla DisGNN can achieve lossless encoding of a geometric
graph with the presence of two distinct anchors. With these findings, we
finally restrict the unidentifiable cases of Vanilla DisGNN solely to those
highly symmetric graphs naturally lacking multiple anchors.

###  3.1 Ability to Locate Global Anchors

Before proceeding, we provide a formal definition of anchors. Given a
geometric graph $G$, we define an anchor function as $A(G):\mathbb{R}^{n\times
d}\times\mathbb{R}^{n\times 3}\to\mathbb{R}^{3}$, which calculates an anchor
coordinate in a permutation invariant and E(3)-equivariant manner. If the
context is clear, we omit $(G)$ and use $A$ to represent the anchor’s 3D
coordinates and use $d_{i,A}$ to denote the distance between node $i$ and the
anchor.

We then introduce a simple but comprehensive set of anchors, referred to as
global anchors. Each global anchor is characterized by a “mass function”
$m:\mathbb{R}^{d}\to\mathbb{R}$, which maps the features of a node to a
generalized node mass. Subsequently, we define the global anchor as follows:

######  Definition 3.1.

(Global Anchor, GA) Given a geometric graph $G=(X,P)$ and a mass function
$m:\mathbb{R}^{d}\to\mathbb{R}$ that satisfies $\sum_{i\in[n]}m(X_{i})\neq 0$,
the corresponding global anchor is defined as:
$A^{m}(G)=\frac{\sum_{i\in[n]}m(X_{i})P_{i}}{\sum_{i\in[n]}m(X_{i})}$.

Global anchor encompasses a broad range of anchors. Representative global
anchors include: 1) Geometric center, where $m$ maps all $X_{i}$ to $1$. 2)
Barycenter (in chemical/physical systems), where $m$ maps $X_{i}$ to the
physical mass of node $i$. 3) $X^{*}$-type geometric center, where $m$ maps
$X_{i}=X^{*}$ to $1$ and $X_{i}\neq X^{*}$ to $0$.

We denote the set of all global anchors of graph $G$ as
$\mathbf{A}(G)=\\{A^{m}(G)\mid
m:\mathbb{R}^{d}\to\mathbb{R},\sum_{i\in[n]}m(X_{i})\neq 0\\}$. Note that
since we iterate all $m$ functions, $\mathbf{A}(G)$ is dependent only on the
individualization of node features but invariant to feature values. An
illustration of global anchor sets is shown in Figure 1.

Figure 1: Global anchor set. The three colored balls represent a triangle-
shaped geometric graph, where different colors indicate different node
features. The small green balls indicate global anchors with different mass
functions. From left to right, geometric graphs with more global anchors
exhibit worse symmetry.

Intuitively, by learning the Euclidean distance between nodes and anchors, the
model can acquire significant global geometric information about a given
graph, enabling itself to produce more meaningful geometric representations.
Now, we present a preliminary conclusion regarding such geometric learning
capability of Vanilla DisGNN:

######  Proposition 3.2.

(Locate Global Anchors) Given a geometric graph $G$, denote node $i$’s
representation produced by 2-round Vanilla DisGNN as $h_{i}^{(2)}$, then we
have:

  * •

(Node-GA distance) Given an arbitrary mass function $m$, $h_{i}^{(2)}$ can
derive $d_{i,A^{m}}$.

  * •

(GA-GA distance) Given two arbitrary mass functions $m_{1}$ and $m_{2}$,
$\\{\\!\\!\\{h_{i}^{(2)}\mid i\in[n]\\}\\!\\!\\}$ can derive
$d_{A^{m_{1}},A^{m_{2}}}$.

  * •

(Counting GA) $\\{\\!\\!\\{h_{i}^{(2)}\mid i\in[n]\\}\\!\\!\\}$ can derive
$\mathds{1}_{|\mathbf{A}(G)|=1}$.

Proposition 3.2 can be regarded as a generalization of the Barycenter Lemma
presented in Delle Rose et al. (2023), which only shows the ability of Vanilla
DisGNN to learn distance from nodes to geometric center. It establishes that
Vanilla DisGNN possesses the ability to automatically incorporate the triangle
information, formed by the node and any two global anchors, into the node
features. In the subsequent subsection, we will demonstrate the theoretical
utilization of such ability to fully encode a given geometric graph.

###  3.2 Two Anchors are Enough for Lossless Encoding

We first introduce the concept of Anchor Positional Encoding (APE) and
subsequently establish an important theorem relating to APE which
characterizes the geometric encoding capability of Vanilla DisGNN.

######  Definition 3.3.

(Anchor Positional Encoding, APE) Given a geometric graph $G=(X,P)$, assume
there are two distinct anchors on it, represented as
$A_{1},A_{2}\in\mathbb{R}^{3}$. APE enhances node $i$’s feature $X_{i}$ to
$X^{\prime}_{i}$ through an injective function
$X^{\prime}_{i}=f_{\text{APE}}(X_{i},d_{i,A_{1}},d_{i,A_{2}},d_{A_{1},A_{2}})$.
We denote the application of $f_{\text{APE}}$ on $X$ row-wisely as
$X^{\prime}=f^{*}_{\text{APE}}(X_{i},d_{i,A_{1}},d_{i,A_{2}},d_{A_{1},A_{2}})$.

By definition, APE is performed relative to two distinct anchors (not limited
to global anchors), enhancing node features with the triangle information
w.r.t. the node and the two anchors. APE can enhance the encoding power of
Vanilla DisGNN, as stated in the following theorem:

######  Theorem 3.4.

(Vanilla DisGNNs’ encoding power with APE) Given a geometric graph $G=(X,P)$,
assume there are two distinct anchors on it, represented as
$A_{1},A_{2}\in\mathbb{R}^{3}$. We first enhance the geometric graph to
$G^{\prime}=(f^{*}_{\text{APE}}(X),P)$ through APE, then we have: $G^{\prime}$
can be derived from a two-layer Vanilla DisGNN’s output on $G^{\prime}$ up to
permutation and E(3)-transformation.

Theorem 3.4 essentially demonstrates that Vanilla DisGNN with APE can attain
E(3)-completeness on the subspace $\mathcal{G}^{\prime}$ of the geometric
graph space $\mathcal{G}$, where all $G\in\mathcal{G}^{\prime}$ satisfy the
assumption that there exist two distinct anchors on $G$. In the following
text, we use Theorem 3.4 as a base theorem to analyze Vanilla DisGNN’s
inherent expressiveness and motivate new powerful designs.

###  3.3 Restricting Unidenfiable Cases into a Small Space

By combining Proposition 3.2 and Definition 3.3, we can conclude that Vanilla
DisGNN can automatically perform APE w.r.t. two global anchors. And as
indicated by Theorem 3.4, with such ability, Vanilla DisGNN can losslessly
encode all geometric graphs with more than two global anchors, leading to the
following necessary condition:

######  Theorem 3.5.

(Necessary condition for unidentifiable cases) Given a geometric graph $G$,
Vanilla DisGNN cannot identify $G$ only if $|\mathbf{A}(G)|=1$.

Indeed, all geometric graphs whose global anchor set degenerates, namely
$|\mathbf{A}(G)|=1$, are highly symmetric, which we define as GA-
symmetric111The determination of whether a graph is GA-symmetric does not
require iterating through all $m$ functions. We provide a simplified, finite-
step algorithm in Proposition A.3 in Appendix A.1.. See Figure 1 for an
illustration of how $|\mathbf{A}(G)|$ reflects the degree of symmetry of a
given geometric graph. Therefore, Theorem 3.5 gives the commonality that all
unidentifiable cases of Vanilla DisGNN possess, essentially limiting the space
of unidentifiable cases to a significantly restricted region that contains
only those highly symmetric geometric graphs, as shown by the purple part in
Figure 2. Note that the intuitive unidentifiable constructions by Pozdnyakov &
Ceriotti (2022); Li et al. (2023b) all validate our conclusion, but Theorem
3.5 for the first time gives a formal definition of “symmetry”.

From Theorem 3.5, one can readily determine which geometric graphs can be
identified by Vanilla DisGNN. For example, nearly all molecules such as
aspirin and ethanol are not GA-symmetric, thus can be identified by Vanilla
DisGNN. As a consequence, Vanilla DisGNN can produce a unique geometric
representation/fingerprint for them safely.

Figure 2: Illustration of the unidentifiable cases of Vanilla DisGNN. Parts
with GAS contains all the GAS-symmetric graphs, where $\mathcal{S}$ can be
empty, $\mathcal{C}$ or $\mathcal{VD}$. All the parts strictly contain their
sub-parts (proper subset relation), which is detailed in Appendix A. The
unidentifiable graphs by Vanilla DisGNN are constrained to be highly
symmetric, i.e., GAVD-symmetric, geometric graphs.

However, up to this point, one may find that the restriction of unidentifiable
cases is relatively loose: All raw point clouds lacking initial node features
(i.e., with identical node features) are naturally GA-symmetric due to the
absence of node individualization, and consequently, we are still unable to
determine if Vanilla DisGNN can identify these cases based on the necessary
condition 3.5. To address this limitation, we introduce two higher-level
symmetries, namely GAC\- and GAVD-symmetry, which further limit the scope of
unidentifiable cases to a significantly smaller subset of GA-symmetric graphs,
and show that most point clouds without node features are still identifiable
by Vanilla DisGNN. This refinement allows us to characterize the expressive
power of Vanilla DisGNN much more precisely. An informative visual
representation of the relation graph is in Figure 2. To further understand how
rare the cases Vanilla DisGNN cannot identify are, we investigate the
proportion of GAVD-symmetric graphs in real-world datasets, including QM9 and
ModelNet. Even with the largest tolerance error, the proportion of
unidentifiable cases amounts to less than $\mathbf{0.1}\%$ of the whole set of
examined geometric graphs. For these extended analysis of Vanilla DisGNN, we
direct the readers to Appendix A.

##  4 On the Completeness of Invariant Models

In this section, we demonstrate and prove the E(3)-completeness of a wide
range of invariant models under certain conditions. These models can
effectively “solve” all the highly-symmetric, i.e., GA-symmetric, geometric
graphs that Vanilla DisGNN may not identify. We first introduce a new simple
invariant model design, which can break such symmetry and identify these
graphs. Consequently, we show how this new design serves as a theoretical tool
for proving a series of invariant models’ expressiveness.

###  4.1 Breaking Symmetry Utilizing Local Anchors

Based on the analysis in Section 3.2 and 3.3, it is evident that for GA-
symmetric graphs, if we are able to determine and specify an additional anchor
beyond the unique global anchor, Vanilla DisGNN becomes able to identify all
of them. However, for certain extremely symmetric graphs such as a sphere, all
possible anchors naturally degenerate into the geometric center. Consequently,
no additional anchors beyond the global anchor can be obtained.

We now demonstrate that the geometric counterpart of NGNN (Zhang & Li, 2021),
named GeoNGNN, can precisely break such symmetry utilizing local anchors. We
first formally give the definition of GeoNGNN:

######  Definition 4.1.

(GeoNGNN) GeoNGNN is the geometric version of NGNN (Zhang & Li, 2021), which
takes geometric graphs $G=(X,P)$ as input, and:

  * •

Both the inner and outer GNN adopt Vanilla DisGNN, with each consisting of
$N_{in}$ and $N_{out}$ layers, respectively.

  * •

The node marking policy is employed.

  * •

The ego subgraph of each node contains all nodes within a Euclidean distance
cutoff $r_{sub}$.

GeoNGNN adopts the same framework of NGNN, except that it is tailored for
geometric settings: the subgraph cutoff is defined on Euclidean distance
instead of “hop”, while the base model is the simplest invariant geometric
model, Vanilla DisGNN. Leveraging Theorem 3.4, we give the conditions for
GeoNGNN to achieve E(3)-completeness:

######  Theorem 4.2.

(E(3)-Completeness of GeoNGNN) When the following conditions are met, GeoNGNN
is E(3)-complete:

  * •

$N_{in}>=5$ and $N_{out}>=0$ ($0$ means that outer GNN only performs an
injective pooling).

  * •

$r_{sub}=+\infty$.

  * •

Inner GNN performs global message passing.

The key idea behind Theorem 4.2 is intuitive: the additionally marked node $i$
in its subgraph acts as an extra anchor, i.e., the local anchor. Together,
this additional anchor and the geometric center (a global anchor) serve as two
distinct anchors, therefore satisfying the assumptions specified in Theorem
3.4, and ultimately leading to the completeness of Vanilla DisGNN. Despite
that node $i$ can still coincide with the geometric center, GeoNGNN applies
Vanilla DisGNN to every node in parallel, ensuring that there always exists
some node $i$ which is distinct from the geometric center.

Unlike global anchors which are calculated in a permutation-invariant manner,
local anchors do not maintain invariance but break it. However, since GeoNGNN
pools all the local anchors, the overall permutation invariance is preserved.

###  4.2 Completeness of Well-Established Invariant Models

Now, based on the completeness of GeoNGNN, we move on to establish that
several well-known invariant models, DimeNet (Gasteiger et al., 2019), GemNet
(Gasteiger et al., 2021) and SphereNet (Liu et al., 2021) can all achieve
E(3)-completeness under certain conditions, by reducing them onto GeoNGNN (see
Appendix F.7 for the description of these models and the formal proof).

######  Theorem 4.3.

(E(3)-Completeness of DimeNet, SphereNet, GemNet) When the following
conditions are met, DimeNet, SphereNet222Here in SphereNet we do not consider
the relative azimuthal angle $\varphi$, since SphereNet with $\varphi$ is not
E(3)-invariant, while E(3)-completeness is defined on E(3)-invariant models.
Note that the exclusion of $\varphi$ only results in weaker expressiveness.
and GemNet are E(3)-complete.

  * •

They initialize and update all edge representations.

  * •

They perform global message passing333In DimeNet and GemNet, nodes $i$ or $j$
are excluded when aggregating neighbors for edge $ij$. The condition requires
the inclusion of these end nodes..

  * •

The message passing layer number is larger than some constant $C$.

A key insight behind Theorem 4.3 is that, all these models track edge
representations ($h_{ij}^{\text{e}dge}$ for edge $(i,j)$), which can be
mathematically aligned with the node-subgraph representations tracked in
GeoNGNN ($h_{ij}^{\text{s}ubg}$ for node $i$ in subgraph $j$). Consequently,
these three models can be mathematically reduced to GeoNGNN.

Theorem 4.3 for the first time highlights that the relatively simple invariant
model, DimeNet, is already E(3)-complete. Consequently, subsequent efforts
like GemNet, which incorporates higher-order geometry, could be unnecessary in
terms of boosting theoretical expressiveness. However, we note that even
though a wide range of invariant models are equally expressive, they may
possess differing inductive biases, leading to distinct levels of
generalization power and experimental performance, as validated in Li et al.
(2023b).

##  5 Related Work

Geometric models leverage the rich 3D geometric information contained in
geometric graphs (Han et al., 2022), and aim to learn meaningful geometric
representations while respecting permutation and Euclidean symmetry. Earlier
work by Schütt et al. (2018) integrated 3D Euclidean distance into the MPNN
framework (Gilmer et al., 2017), making the model invariant to permutations
and E(3) transformations. Nevertheless, this model exhibits a restricted
capacity to distinguish non-E(3)-isomorphic geometric graphs even on fully-
connected graphs as substantiated by Li et al. (2023b); Pozdnyakov & Ceriotti
(2022). Subsequent invariant models (Gasteiger et al., 2019, 2020, 2021, 2022;
Liu et al., 2021) have endeavored to enhance expressiveness by incorporating
invariant high-order geometric features or adopting local spherical
representations. Several works also adopt vector representations to enhance
model’s theoretical and experimental performance (Satorras et al., 2021;
Schütt et al., 2021; Thölke & De Fabritiis, 2021; Deng et al., 2021). However,
all these methods suffer from a lack of theoretical guarantee of 3D
completeness.

Another line of equivariant methods leverage high-order SO(3) irreducible
representations (Thomas et al., 2018; Fuchs et al., 2020; Batatia et al.,
2022; Batzner et al., 2022; Brandstetter et al., 2021; Musaelian et al.,
2023), which come with the theoretical guarantee of universality (Dym & Maron,
2020). However, these models necessitate infinite-order spherical tensors for
approximating high-order polynomials, which is intractable due to the need for
expensive tensor products (in practice, the order is less than 3). Other
methods project the coordinates or vector features onto local or global
equivariant frames to ensure models’ Euclidean symmetry (Wang & Zhang, 2022;
Duval et al., 2023; Puny et al., 2021). These methods, however, are based on
the assumption of non-degenerate frames, thereby making them incapable of
processing almost all symmetric geometric graphs, which are exactly the corner
cases we aim to capture. Recently, (Li et al., 2023b) proposed a theoretically
complete invariant framework by generalizing $k$-(F)WL methods (Weisfeiler &
Leman, 1968; Cai et al., 1992) for graph isomorphism test to the geometric
setting. Nonetheless, the framework faces difficulty in scaling to large
geometric graphs. Moreover, Li et al. (2023b) cannot be extended to
SE(3)-completeness cases, which are quite important for capturing the
chirality of molecules or general 3D geometric graphs.

##  6 Experiments

In this section, we aim to answer the following questions:

  * •

Q1. Can GeoNGNN effectively distinguish counterexample pairs of geometric
graphs that cannot be distinguished by Vanilla DisGNN?444Despite theoretical
completeness, experimental performance may still be hindered by numerical
errors, thus failing to distinguish pairs of geometric graphs experimentally.

  * •

Q2. Can the practical GeoNGNN555“Practical” means that in experiments we
leverage local message passing and finite subgraph size for tractability and
scalability., which simply enhances Vanilla DisGNN with local subgraphs,
achieve competitive performance compared to complex models adopting high-order
invariant/equivariant representations, while exhibiting faster inference due
to the simple design?

  * •

Q3. How do subgraph sizes, which serve as a trade-off between theoretical
completeness and experimental tractability, affect the performance of GeoNGNN?

Variants of GeoNGNN. Beyond aforehead questions, we also introduce and
evaluate two important variants of GeoNGNN in Appendix D, E. The first one is
GeoNGNN-C, an SE(3)-complete variant of GeoNGNN, designed by simply replacing
the undirected distances in GeoNGNN with directed ones. GeoNGNN-C embraces
chirality and is capable of learning meaningful chirality-relevant
representations for achieving good performances in downstream tasks. The
second one is GeoNGNN with sampling policies, which improves the efficiency of
GeoNGNN by avoiding running Vanilla DisGNN on all local anchors’ subgraphs.
Nonetheless, this design yields primarily negative results, underscoring the
importance of leveraging all local anchors for both theoretical soundness and
faithfulness for practical physical and chemical systems.

Models to compare with. We compare GeoNGNN with two main types of geometric
models. The first type integrates high-order SO(3) irreducible representations
(including 1-order, i.e., vectors) and mostly employs tensor products to
produce equivariant outputs. These models are referred to as equivariant
models, including PaiNN (Schütt et al., 2021), MACE (Batatia et al., 2022),
Allegro (Musaelian et al., 2023), NequIP (Batzner et al., 2022), Equiformer
(Liao & Smidt, 2022). The second type integrates high-order invariant
geometry, such as angle, dihedral angle, or learned representations. We refer
to these models as invariant models, including DimeNet (Gasteiger et al.,
2019), GemNet (Gasteiger et al., 2021) and 2-F-DisGNN (Li et al., 2023b). Note
that all of these models can capture high-order geometry, enabling them to
achieve state-of-the-art performance on geometric structure learning tasks.

Given that GeoNGNN can be regarded as the subgraph-enhanced version of Vanilla
DisGNN, we also implement and evaluate Vanilla DisGNN, which includes more
complicated residual layers than its special case SchNet (Schütt et al.,
2018), as a baseline to assess the direct improvement achieved through
subgraph representation.

Detailed experimental settings are provided in Appendix C.

Table 1: MAE loss on revised MD17. Energy (E) in kcal/mol, force (F) in
kcal/mol/Å. We color the cell if GeoNGNN outperforms Vanilla DisGNN. The
average rank is the average of the rank of each row.

|  | Equivariant models | Scalar models
---|---|---|---
Mol | Target | PaiNN | Allegro | NequIP | MACE | DimeNet | GemNet | 2F-Dis. | Vanilla Dis. | GeoNGNN
| E | 0.1591 | 0.0530 | 0.0530 | 0.0507 | 0.1321 | - | 0.0465 | 0.1348 |  0.0490
aspirin | F | 0.3713 | 0.1683 | 0.1891 |  0.1522 | 0.3549 | 0.2191 | 0.1515 | 0.4468 | 0.1733
| E | - |  0.0277 | 0.0161 |  0.0277 | 0.1063 | - | 0.0315 | 0.2997 | 0.0301
azobenzene | F | - | 0.0600 |  0.0669 | 0.0692 | 0.2174 | - | 0.1121 | 0.5814 | 0.1206
| E | - | 0.0069 | 0.0009 | 0.0092 | 0.0061 | - |  0.0013 | 0.0634 | 0.0018
benzene | F | - | 0.0046 | 0.0069 |  0.0069 | 0.0170 | 0.0115 | 0.0085 | 0.3055 | 0.0083
| E | 0.0623 | 0.0092 | 0.0092 | 0.0092 | 0.0345 | - | 0.0065 | 0.0129 |  0.0090
ethanol | F | 0.2306 |  0.0484 | 0.0646 |  0.0484 | 0.1859 | 0.0830 | 0.0379 | 0.0825 | 0.0616
| E | 0.0899 |  0.0138 | 0.0184 | 0.0184 | 0.0507 | - | 0.0129 | 0.0329 | 0.0145
malonaldehyde | F | 0.3182 |  0.0830 | 0.1176 | 0.0945 | 0.2743 | 0.1522 | 0.0782 | 0.1922 | 0.0923
| E | 0.1176 | 0.0046 | 0.0208 | 0.0115 | 0.0445 | - | 0.0103 | 0.1496 |  0.0083
naphthalene | F | 0.0830 | 0.0208 |  0.0300 | 0.0369 | 0.1105 | 0.0438 | 0.0478 | 0.4608 | 0.0437
| E | - | 0.0346 | 0.0323 | 0.0300 | 0.1176 | - |  0.0310 | 0.2457 | 0.0426
paracetamol | F | - |  0.1130 | 0.1361 | 0.1107 | 0.3028 | - | 0.1178 | 0.5393 | 0.1612
| E | 0.1130 | 0.0208 | 0.0161 | 0.0208 | 0.0590 | - | 0.0174 | 0.0800 |  0.0165
salicylic acid | F | 0.2099 | 0.0669 | 0.0922 |  0.0715 | 0.2428 | 0.1222 | 0.0860 | 0.3703 | 0.0897
| E | 0.0969 | 0.0092 |  0.0069 | 0.0115 | 0.0228 | - | 0.0051 | 0.0507 | 0.0087
toluene | F | 0.1015 | 0.0415 | 0.0369 |  0.0346 | 0.1085 | 0.0507 | 0.0284 | 0.2296 | 0.0424
| E | 0.1038 | 0.0138 | 0.0092 | 0.0115 | 0.0338 | - | 0.0139 | 0.0381 |  0.0108
uracil | F | 0.1407 | 0.0415 | 0.0715 |  0.0484 | 0.1634 | 0.0876 | 0.0828 | 0.2331 | 0.0716
AVG RANK | 7.79 | 2.55 | 3.30 | 2.90 | 6.70 | 6.00 | 2.70 | 7.45 | 3.50

###  6.1 Separation Power: Synthetic Counterexamples

We constructed an expressiveness dataset based on counterexamples proposed by
Li et al. (2023b) to evaluate the separation power of practical models. The
synthetic dataset comprises 10 isolated and 7 combinatorial counterexamples.
Each counterexample consists of a pair of highly symmetric geometric graphs
that are non-E(3)-isomorphic but indistinguishable by Vanilla DisGNN.

Table 2: The separation results on the constructed dataset.

| SchNet | Vanilla Dis. | DimeNet | PaiNN | MACE | GeoNGNN
---|---|---|---|---|---|---
Isolated (10 cases) | 0% | 0% | 100% | 100% | 100% | 100%
Combin. (7 cases) | 0% | 0% | 100% | 100% | 100% | 100%

As observed in Table 2, SchNet and Vanilla DisGNN both fail to distinguish any
counterexample, while the remaining models all effectively discriminate
between all pairs, which aligns with our theoretical findings. Indeed, these
results suggest that as long as models incorporate some higher-order geometry
than distance, they can possess the ability to differentiate the carefully
designed corner cases by Li et al. (2023b), implying that 3D isomorphism
problem is much easier than the classical one.

###  6.2 Molecule Structure Learning: Revised MD17

We further evaluate the geometric learning ability of GeoNGNN on the rMD17
dataset (Chmiela et al., 2017), which poses a substantial challenge to models’
geometric expressiveness and generalization power. This dataset encompasses
trajectories from molecular dynamics simulations of several small molecules.
The objective is to predict the energy and atomic forces of a given molecule
conformer which contains all atoms’ positions and atomic numbers.

There are several important observations, as depicted in Table 1: 1) GeoNGNN
exhibits substantial improvements over Vanilla DisGNN. The ratio of the loss
for GeoNGNN to that of Vanilla DisGNN averages 1:8 and reaches a maximum of
1:37. 2) Though also being E(3)-complete, DimeNet and GemNet show worse
performance than GeoNGNN. This finding suggests that different model designs
can exhibit different inductive biases, while learning more refined subgraph
(local environment) representations may be superior to directional message
passing in certain molecule-relevant tasks. 3) GeoNGNN shows competitive
performance on the majority of molecules in comparison to other well-designed
state-of-the-art models. However, it does not achieve SOTA performance, which
may be due to its simple design, leveraging distance only, and the weak base
GNN it adopts.

###  6.3 Scaling to Large Graph Size: MD22

A significant concern for geometric models is the scalability for larger
geometric graphs. In this subsection, we show that GeoNGNN, though simple, can
achieve high performance on relatively large molecules (Chmiela et al., 2023),
while exhibiting much faster speed than current SOTA models.

As presented in Table 3 in Appendix B.3, GeoNGNN outperforms Vanilla DisGNN
across almost all targets. It exhibits competitive results and achieves
several new SOTA results on Stachyose and the two largest molecules, Buckyball
catcher and Double-walled nanotube. On average, GeoNGNN performs better than
all the equivariant models except for MACE, ranking the 2nd among all models.

We further evaluated the inference time and GPU memory consumption of GeoNGNN
and several high-performance models. As shown in Table 4 in Appendix B.3,
GeoNGNN is more than 2x faster than MACE and more than 8x faster than
Equiformer, which both utilize high-order equivariant representations and
perform tensor products. Additionally, GeoNGNN demonstrates efficient memory
usage, particularly when compared to 2-F-DisGNN and Equiformer.

###  6.4 Effect of Subgraph Size

In this section, we delve into the impact of subgraph size, which serves as a
form of receptive field for each node. Theoretically, a larger receptive
field, facilitated by distance encoding, should always result in the same or
better expressiveness. To explore how subgraph size affects experimental
performance, we selected three molecules of different representative scales
and observed the effects, as depicted in Figure 7 in Appendix B.3. As
anticipated, performance generally improves with increased subgraph size,
roughly matching the improved theoretical expressiveness. However, the rule
does not always hold: there are cases where increasing the subgraph size leads
to degraded performance, which can be attributed to the potential noise and
redundant information. It implies that there exists a conflict between
theoretical expressiveness and experimental performance, and striking a
balance between them is important.

##  7 Conclusion and Limitation

Conclusion. In this paper, we throughoutly analyze a wide range of invariant
models’ theoretical expressiveness. Specifically, we rigorously characterize
the expressiveness of Vanilla DisGNN, showcasing that all its unidentifiable
cases are highly symmetric graphs with only one global anchor. We then
introduce GeoNGNN capable of breaking such symmetry utilizing local anchors
which achieves E(3)-completeness. We leverage GeoNGNN as a tool to prove the
E(3)-completeness of three well-known invariant models, DimeNet, GemNet and
SphereNet, for the first time. Experiments show the competitive performance
and faster speed of GeoNGNN compared to geometric models using high-order
invariant and equivariant representations.

Limitation. The E(3) completeness proof for invariant models are under the
assumption of global message passing, i.e., the geometric graphs are fully
connected. However, the extent to which these models can exhibit high
expressiveness on general sparse graphs remains an open question that needs
further investigation. Additionally, future research is needed to characterize
the expressiveness of vector models that rely solely on 1-order equivariant
representations, which have shown promising experimental results but lack a
guarantee of completeness.

##  8 Impact Statements

This paper contributes by characterizing the theoretical expressiveness of
invariant geometric models, with the goal of helping researchers better
understand the potential and limits of existing geometric models and develop
better geometric models for downstream tasks that are beneficial for
scientific development. There are many potential societal consequences of our
work, none of which we feel must be specifically highlighted here.

## References

  * Abou-Rjeili & Karypis (2006) Abou-Rjeili, A. and Karypis, G.  Multilevel algorithms for partitioning power-law graphs.  In _Proceedings 20th IEEE International Parallel & Distributed Processing Symposium_, pp. 10–pp. IEEE, 2006.
  * Adams et al. (2021) Adams, K., Pattanaik, L., and Coley, C. W.  Learning 3d representations of molecular chirality with invariance to bond rotations.  In _International Conference on Learning Representations_ , 2021.
  * Batatia et al. (2022) Batatia, I., Kovacs, D. P., Simm, G., Ortner, C., and Csányi, G.  Mace: Higher order equivariant message passing neural networks for fast and accurate force fields.  _Advances in Neural Information Processing Systems_ , 35:11423–11436, 2022.
  * Batzner et al. (2022) Batzner, S., Musaelian, A., Sun, L., Geiger, M., Mailoa, J. P., Kornbluth, M., Molinari, N., Smidt, T. E., and Kozinsky, B.  E (3)-equivariant graph neural networks for data-efficient and accurate interatomic potentials.  _Nature communications_ , 13(1):1–11, 2022.
  * Bevilacqua et al. (2021) Bevilacqua, B., Frasca, F., Lim, D., Srinivasan, B., Cai, C., Balamurugan, G., Bronstein, M. M., and Maron, H.  Equivariant subgraph aggregation networks.  In _International Conference on Learning Representations_ , 2021.
  * Brandstetter et al. (2021) Brandstetter, J., Hesselink, R., van der Pol, E., Bekkers, E. J., and Welling, M.  Geometric and physical quantities improve e (3) equivariant message passing.  In _International Conference on Learning Representations_ , 2021.
  * Cai et al. (1992) Cai, J.-Y., Fürer, M., and Immerman, N.  An optimal lower bound on the number of variables for graph identification.  _Combinatorica_ , 12(4):389–410, 1992.
  * Chmiela et al. (2017) Chmiela, S., Tkatchenko, A., Sauceda, H. E., Poltavsky, I., Schütt, K. T., and Müller, K.-R.  Machine learning of accurate energy-conserving molecular force fields.  _Science advances_ , 3(5):e1603015, 2017.
  * Chmiela et al. (2023) Chmiela, S., Vassilev-Galindo, V., Unke, O. T., Kabylda, A., Sauceda, H. E., Tkatchenko, A., and Müller, K.-R.  Accurate global machine learning force fields for molecules with hundreds of atoms.  _Science Advances_ , 9(2):eadf0873, 2023.
  * Degen et al. (2008) Degen, J., Wegscheid-Gerlach, C., Zaliani, A., and Rarey, M.  On the art of compiling and using’drug-like’chemical fragment spaces.  _ChemMedChem: Chemistry Enabling Drug Discovery_ , 3(10):1503–1507, 2008.
  * Delle Rose et al. (2023) Delle Rose, V., Kozachinskiy, A., Rojas, C., Petrache, M., and Barceló, P.  Three iterations of $(d-1)$-wl test distinguish non isometric clouds of $d$-dimensional points.  _arXiv e-prints_ , pp. arXiv–2303, 2023.
  * Deng et al. (2021) Deng, C., Litany, O., Duan, Y., Poulenard, A., Tagliasacchi, A., and Guibas, L. J.  Vector neurons: A general framework for so (3)-equivariant networks.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 12200–12209, 2021.
  * Duval et al. (2023) Duval, A. A., Schmidt, V., Hernández-García, A., Miret, S., Malliaros, F. D., Bengio, Y., and Rolnick, D.  Faenet: Frame averaging equivariant gnn for materials modeling.  In _International Conference on Machine Learning_ , pp. 9013–9033. PMLR, 2023.
  * Dym & Maron (2020) Dym, N. and Maron, H.  On the universality of rotation equivariant point cloud networks.  In _International Conference on Learning Representations_ , 2020.
  * Fey & Lenssen (2019) Fey, M. and Lenssen, J. E.  Fast graph representation learning with pytorch geometric.  _arXiv preprint arXiv:1903.02428_ , 2019.
  * Frasca et al. (2022) Frasca, F., Bevilacqua, B., Bronstein, M., and Maron, H.  Understanding and extending subgraph gnns by rethinking their symmetries.  _Advances in Neural Information Processing Systems_ , 35:31376–31390, 2022.
  * Fuchs et al. (2020) Fuchs, F., Worrall, D., Fischer, V., and Welling, M.  Se (3)-transformers: 3d roto-translation equivariant attention networks.  _Advances in Neural Information Processing Systems_ , 33:1970–1981, 2020.
  * Gaiński et al. (2023) Gaiński, P., Koziarski, M., Tabor, J., and Śmieja, M.  Chienn: Embracing molecular chirality with graph neural networks.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pp. 36–52. Springer, 2023.
  * Gasteiger et al. (2019) Gasteiger, J., Groß, J., and Günnemann, S.  Directional message passing for molecular graphs.  In _International Conference on Learning Representations_ , 2019.
  * Gasteiger et al. (2020) Gasteiger, J., Giri, S., Margraf, J. T., and Günnemann, S.  Fast and uncertainty-aware directional message passing for non-equilibrium molecules.  _arXiv preprint arXiv:2011.14115_ , 2020.
  * Gasteiger et al. (2021) Gasteiger, J., Becker, F., and Günnemann, S.  Gemnet: Universal directional graph neural networks for molecules.  In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), _Advances in Neural Information Processing Systems_ , volume 34, pp. 6790–6802. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper/2021/file/35cf8659cfcb13224cbd47863a34fc58-Paper.pdf.
  * Gasteiger et al. (2022) Gasteiger, J., Shuaibi, M., Sriram, A., Günnemann, S., Ulissi, Z. W., Zitnick, C. L., and Das, A.  Gemnet-oc: Developing graph neural networks for large and diverse molecular simulation datasets.  _Transactions on Machine Learning Research_ , 2022.
  * Gilmer et al. (2017) Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E.  Neural message passing for quantum chemistry.  In _International conference on machine learning_ , pp. 1263–1272. PMLR, 2017.
  * Guo et al. (2020) Guo, Y., Wang, H., Hu, Q., Liu, H., Liu, L., and Bennamoun, M.  Deep learning for 3d point clouds: A survey.  _IEEE transactions on pattern analysis and machine intelligence_ , 43(12):4338–4364, 2020.
  * Han et al. (2022) Han, J., Rong, Y., Xu, T., and Huang, W.  Geometrically equivariant graph neural networks: A survey.  2022\.
  * Hordan et al. (2023) Hordan, S., Amir, T., Gortler, S. J., and Dym, N.  Complete neural networks for euclidean graphs.  _arXiv preprint arXiv:2301.13821_ , 2023.
  * Hornik et al. (1989) Hornik, K., Stinchcombe, M., and White, H.  Multilayer feedforward networks are universal approximators.  _Neural networks_ , 2(5):359–366, 1989.
  * Jumper et al. (2021) Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Žídek, A., Potapenko, A., et al.  Highly accurate protein structure prediction with alphafold.  _Nature_ , 596(7873):583–589, 2021.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Kovacs et al. (2023) Kovacs, D. P., Batatia, I., Arany, E. S., and Csanyi, G.  Evaluation of the mace force field architecture: from medicinal chemistry to materials science.  _arXiv preprint arXiv:2305.14247_ , 2023.
  * Li et al. (2023a) Li, Y., Wang, Y., Huang, L., Yang, H., Wei, X., Zhang, J., Wang, T., Wang, Z., Shao, B., and Liu, T.-Y.  Long-short-range message-passing: A physics-informed framework to capture non-local interaction for scalable molecular dynamics simulation.  _arXiv preprint arXiv:2304.13542_ , 2023a.
  * Li et al. (2023b) Li, Z., Wang, X., Huang, Y., and Zhang, M.  Is distance matrix enough for geometric deep learning?  _Advances in Neural Information Processing Systems_ , 2023b.
  * Liao & Smidt (2022) Liao, Y.-L. and Smidt, T.  Equiformer: Equivariant graph attention transformer for 3d atomistic graphs.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Liu et al. (2021) Liu, Y., Wang, L., Liu, M., Lin, Y., Zhang, X., Oztekin, B., and Ji, S.  Spherical message passing for 3d molecular graphs.  In _International Conference on Learning Representations_ , 2021.
  * Maron et al. (2018) Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y.  Invariant and equivariant graph networks.  In _International Conference on Learning Representations_ , 2018.
  * Morris et al. (2019) Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 33, pp. 4602–4609, 2019.
  * Musaelian et al. (2023) Musaelian, A., Batzner, S., Johansson, A., Sun, L., Owen, C. J., Kornbluth, M., and Kozinsky, B.  Learning local equivariant representations for large-scale atomistic dynamics.  _Nature Communications_ , 14(1):579, 2023.
  * Pattanaik et al. (2020) Pattanaik, L., Ganea, O.-E., Coley, I., Jensen, K. F., Green, W. H., and Coley, C. W.  Message passing networks for molecules with tetrahedral chirality, 2020\.
  * Pozdnyakov & Ceriotti (2022) Pozdnyakov, S. N. and Ceriotti, M.  Incompleteness of graph convolutional neural networks for points clouds in three dimensions.  _arXiv preprint arXiv:2201.07136_ , 2022.
  * Puny et al. (2021) Puny, O., Atzmon, M., Smith, E. J., Misra, I., Grover, A., Ben-Hamu, H., and Lipman, Y.  Frame averaging for invariant and equivariant network design.  In _International Conference on Learning Representations_ , 2021.
  * Qian et al. (2022) Qian, C., Rattan, G., Geerts, F., Niepert, M., and Morris, C.  Ordered subgraph aggregation networks.  _Advances in Neural Information Processing Systems_ , 35:21030–21045, 2022.
  * Sanchez-Gonzalez et al. (2020) Sanchez-Gonzalez, A., Godwin, J., Pfaff, T., Ying, R., Leskovec, J., and Battaglia, P.  Learning to simulate complex physics with graph networks.  In _International Conference on Machine Learning_ , pp. 8459–8468. PMLR, 2020.
  * Satorras et al. (2021) Satorras, V. G., Hoogeboom, E., and Welling, M.  E (n) equivariant graph neural networks.  In _International conference on machine learning_ , pp. 9323–9332. PMLR, 2021.
  * Schmitz et al. (2019) Schmitz, G., Godtliebsen, I. H., and Christiansen, O.  Machine learning for potential energy surfaces: An extensive database and assessment of methods.  _The Journal of chemical physics_ , 150(24):244113, 2019.
  * Schütt et al. (2021) Schütt, K., Unke, O., and Gastegger, M.  Equivariant message passing for the prediction of tensorial properties and molecular spectra.  In _International Conference on Machine Learning_ , pp. 9377–9388. PMLR, 2021.
  * Schütt et al. (2018) Schütt, K. T., Sauceda, H. E., Kindermans, P.-J., Tkatchenko, A., and Müller, K.-R.  Schnet–a deep learning architecture for molecules and materials.  _The Journal of Chemical Physics_ , 148(24):241722, 2018.
  * Thölke & De Fabritiis (2021) Thölke, P. and De Fabritiis, G.  Equivariant transformers for neural network based molecular potentials.  In _International Conference on Learning Representations_ , 2021.
  * Thomas et al. (2018) Thomas, N., Smidt, T., Kearnes, S., Yang, L., Li, L., Kohlhoff, K., and Riley, P.  Tensor field networks: Rotation-and translation-equivariant neural networks for 3d point clouds.  _arXiv preprint arXiv:1802.08219_ , 2018.
  * Wang & Zhang (2022) Wang, X. and Zhang, M.  Graph neural network with local frame for molecular potential energy surface.  In _Learning on Graphs Conference_ , pp. 19–1. PMLR, 2022.
  * Weisfeiler & Leman (1968) Weisfeiler, B. and Leman, A.  The reduction of a graph to canonical form and the algebra which appears therein.  _NTI, Series_ , 2(9):12–16, 1968.
  * Xu et al. (2018) Xu, K., Hu, W., Leskovec, J., and Jegelka, S.  How powerful are graph neural networks?  In _International Conference on Learning Representations_ , 2018.
  * Zaheer et al. (2017) Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R. R., and Smola, A. J.  Deep sets.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Zhang et al. (2023) Zhang, B., Feng, G., Du, Y., He, D., and Wang, L.  A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests.  _arXiv preprint arXiv:2302.07090_ , 2023.
  * Zhang & Li (2021) Zhang, M. and Li, P.  Nested graph neural networks.  _Advances in Neural Information Processing Systems_ , 34:15734–15747, 2021.
  * Zhao et al. (2021) Zhao, L., Jin, W., Akoglu, L., and Shah, N.  From stars to subgraphs: Uplifting any gnn with local structure awareness.  In _International Conference on Learning Representations_ , 2021.

##  Appendix A Extended Analysis of Vanilla DisGNN

###  A.1 Stronger Necessary Condition for Unidentifiable Cases

In the case of geometric graphs where all node features are identical, such as
raw point clouds, the global anchor set naturally degenerates, as shown in the
left figure of Figure 4. As a consequence, based on the necessary condition
3.5, we cannot determine whether these geometric graphs can be identified by
Vanilla DisGNN. Here, we define two higher-level symmetries, i.e., GAC\- and
GAVD-symmetry, of a given geometric graph $G$ and, therefore, enhance the
necessary condition to finerly bound the expressiveness of Vanilla DisGNN, as
illustrated in Figure 2.

We first define an enlarged global anchor set on a given graph $G$ through the
graphs’ spatial environments. Formally, we first use some permutation-
equivariant and E(3)-invariant algorithm $\mathcal{S}(G):\mathbb{R}^{n\times
d}\times\mathbb{R}^{n\times 3}\to\mathbb{R}^{n\times d_{\text{pre}}}$ to
extract nodes’ spatial features from their environments as a pre-processing.
These spatial features are then fused with the nodes’ initial features using
an injective function, resulting the enhanced node features. Subsequently, the
mass function $m$ is applied to the graph $G$ but with enhanced node features
to calculate the anchor.

We denote the resulting global anchor as $A^{\mathcal{S},m}(G)$, and use
$\mathbf{A}^{\mathcal{S}}(G)$ to denote the corresponding set. Accordingly, we
define graph $G$ to be GAS-symmetric if $|\mathbf{A}^{\mathcal{S}}(G)|=1$.

It should be emphasized that
$\mathbf{A}(G)\subseteq\mathbf{A}^{\mathcal{S}}(G)$ for all $\mathcal{S}$ and
$G$, as the use of $\mathcal{S}$ always results in a no-coarser node
individualization, and therefore, GAS-symmetric $\Rightarrow$ GA-symmetric,
meaning that GAS-symmetry always represents a higher-level symmetry than GA-
symmetry.

We introduce two simple types of color refinement algorithms that effectively
generate more global anchors, and more importantly, these refinement
algorithms can both be performed by Vanilla DisGNN automatically:

  * •

Center enhancement $\mathcal{C}$, which enhances node features by
incorporating the distance of each node to the geometric center. See Figure 4
for illustration.

  * •

Vanilla DisGNN enhancement $\mathcal{VD}$, which refines node features by
applying Vanilla DisGNN onto the graph. It is important to note that Vanilla
DisGNN here is used as a color refinement algorithm, and different
parameterizations (as long as they satisfy the injective assumption) will
yield the same individualization of node features, thus the same
$\mathbf{A}^{\mathcal{VD}}(G)$.

By taking a geometric graph $G$ as input, Vanilla DisGNN is able to learn to
perform APE related to the largest global anchor set
$\mathbf{A}^{\mathcal{VD}}(G)$ automatically:

######  Proposition A.1.

(Locate Enhanced Global Anchors) Given a geometric graph G, denote node $i$’s
representation produced by infinite-round Vanilla DisGNN as $h_{i}$, then we
have:

  * •

(Inclusion relation)
$\mathbf{A}^{\mathcal{C}}(G)\subseteq\mathbf{A}^{\mathcal{VD}}(G)$

  * •

(Node-GA distance) For an arbitrary mass function $m$, $h_{i}$ can derive
$d_{i,A^{\mathcal{VD},m}}$.

  * •

(GA-GA distance) For arbitrary two mass functions $m_{1}$ and $m_{2}$,
$\\{\\!\\!\\{h_{i}\mid i\in[n]\\}\\!\\!\\}$ can derive
$d_{A^{\mathcal{VD},m_{1}},A^{\mathcal{VD},m_{2}}}$.

  * •

(Counting enhanced GA) $\\{\\!\\!\\{h_{i}^{(2)}\mid i\in[n]\\}\\!\\!\\}$ can
derive $\mathds{1}_{|\mathbf{A}^{\mathcal{VD}}(G)|=1}$.

Proposition A.1 is the enhanced version of Proposition 3.2, demonstrating that
Vanilla DisGNN possesses the geometric capability to acquire global geometric
information not only w.r.t. global anchors defined on initial node features
but also w.r.t. the enhanced global anchors defined on $\mathcal{VD}$ enhanced
node features. In practice, there is no necessity for an infinite number of
rounds. Instead, the process can terminate when the equivalence partition of
features is not further refined, and with two more rounds of Vanilla DisGNN,
the global geometric information can be extracted.

We note that the first conclusion of Proposition A.1 implies that GAVD
$\Rightarrow$ GAC, suggesting that GAVD is a higher-level symmetry.
Consequently, the space in which graphs exhibit GAVD-symmetry is a subset of
the space of GAC-symmetric graphs. Furthermore, we can demonstrate that the
space of GAVD-symmetric graphs is strictly contained within the space of GAC-
symmetric graphs. This is because there exist geometric graphs that display
GAC-symmetry but not GAVD-symmetry, as illustrated in Figure 3.

Figure 3: A geometric graph $G$ that exhibits GAC-symmetry but not GAVD-
symmetry. (a) The geometric graph $G$, consisting of an equilateral triangle
and two additional nodes. (b) The graph $G$ after center enhancement. Note
that each node has the same distance to the geometric center, therefore the
nodes still remain undivided. (c) The graph $G$ after Vanilla DisGNN
enhancement.

Consequently, we can prove the following stronger necessary condition:

######  Theorem A.2.

(Necessary condition for unidentifiable cases) Given a geometric graph $G$,
Vanilla DisGNN cannot identify $G$ only if $G$ is GAVD-symmetric.

Condition A.2 demonstrates that all unidentifiable cases by Vanilla DisGNN are
GAVD-symmetric, a much higher-level symmetry. Therefore, we further restrict
the unidentifiable cases into a much smaller geometric graph subspace,
illustrated in Figure 2.

With such a condition, we can determine more geometric graphs that Vanilla
DisGNN can identify. For example, with the weaker necessary condition 3.5
shown in the main body, we do not know whether the left-most geometric graphs
in Figure 3 and Figure 4 are identifiable by Vanilla DisGNN, since they are
all GA-symmetric. However, we can now determine they are identifiable indeed,
since the graph in Figure 3 is not GAVD-symmetric, and the graph in Figure 4
is even not GAC-symmetric.

At last, we demonstrate that there exist geometric graphs that are GAVD-
symmetric but can be identified by Vanilla DisGNN. Specifically, we establish
that the relationship between the red and purple subspaces in Figure 2 can be
accurately described as a proper subset. To illustrate this, let us consider
an equilateral triangle of arbitrary length without any initial node features
as the base geometric graph $G$ (i.e., the left-most figure in Figure 1). For
any other geometric graph $G^{\prime}$ that is non-E(3)-isomorphic to $G$, we
encounter only three scenarios: (1) $G^{\prime}$ has a different number of
nodes than 3, (2) $G^{\prime}$ consists of 3 nodes forming an equilateral
triangle but with a distinct length, or (3) $G^{\prime}$ consists of 3 nodes
arranged in a manner that does not form an equilateral triangle. Importantly,
Vanilla DisGNN possesses the capability to distinguish between $G$ and
$G^{\prime}$ for all three cases, due to its ability to embed node numbers and
all distance lengths. Consequently, Vanilla DisGNN successfully identifies
$G$. However, $G$ is GAVD-symmetric, as all three nodes are isomorphic at the
node-level.

Figure 4: Center enhancement for the global anchor set. Prior to the
enhancement, the global anchor set degenerates into a single point, i.e.,
$|\mathbf{A}(G)=1|$. After the enhancement, the global anchor set expands to
form a line with an infinite number of anchors, i.e.,
$|\mathbf{A}^{\mathcal{C}}(G)>1|$.

###  A.2 Assessment of Symmetric Graphs on Real-World Datasets

In this subsection, we perform assessments on real-world datasets with the
objective of addressing the following question: What is the proportion of
unidentifiable cases for Vanilla DisGNN in real-world geometric graphs? We
answer this question by assessing the proportion of unidentifiable cases’
supersets, namely GA-, GAC\- and GAC-symmetric geometric graphs, and therefore
indirectly assessing the proportion of unidentifiable cases. Our findings
demonstrate that, theoretically, Vanilla DisGNN can identify nearly all
geometric graphs present in real-world datasets.

We first give a proposition, which can determine whether a given geometric
graph is GA-symmetric in finite-step without the need to iterate all mass
functions $m$:

######  Proposition A.3.

(Degeneration of Global Anchor Set) Given an arbitrary geometric graph
$G=(X,P)$, let $K$ denote the number of distinct node features, i.e.,
$|\\{X_{i}\mid i\in[n]\\}|=K$, and let $X^{*}_{k}$ represent the $k$-th type
of node features. Then we have: $G$ is GA-symmetric $\iff$ all
$X^{*}_{k}$-type geometric centers of $G$ coincide.

Note that GAS-symmetry of a given geometric graph $G$ can also be readily
determined using Proposition A.3, with the only distinction being that
$X^{*}_{k}$ defined on the enhanced node features.

Next, we outline several evaluation criteria that serve as guidelines for
determining whether a given geometric graph is symmetric in real-world
datasets.

Evaluation criteria. In the context of real-world geometric graphs, it is
pertinent to acknowledge the presence of inherent coordinate noise, which
renders them deviant from being inherently symmetric in an ideal sense.
Additionally, computational calculations are subjected to floating-point
errors. Accordingly, we propose the introduction of two tolerance errors that
govern the sensitivity of the aforementioned noise and errors when determining
whether a geometric graph is symmetric: 1) The rounding number $r$ for
distance-related enhancement. During $\mathcal{C}$\- or
$\mathcal{VD}$-enhancement, we augment node features by incorporating distance
information. We round the distance values to $r$ decimal places for more
insensitive to noise. 2) The deviation error $\epsilon$. In order to ascertain
the symmetry of a graph, Proposition A.3 is employed. Accounting for errors, a
geometric graph is considered symmetric if all the type-centers are located
within a ball centered at the type-centers’ center, with a radius of
$\epsilon$.

Note that the lower the rounding number or the larger the deviation error, the
less sensitive the criteria is to noise. As a consequence, there is a higher
likelihood of a graph being determined as symmetric.

Real-world datasets. We select two representative datasets, namely QM9 and
ModelNet, for the assessment. The QM9 dataset comprises approximately 130K
molecules, while the ModelNet dataset consists of roughly 12K real-world point
clouds categorized into 40 classes, including objects such as chairs, beds,
and more. Both datasets encompass numeric geometric graphs, and our objective
is to count the occurrence of symmetric graphs within them. Notably, in the
case of the ModelNet dataset, initial node features are absent, resulting in
all graphs being inherently GA-symmetric, as we demonstrated previously.
However, they may not necessarily exhibit GAC-symmetry, therefore can further
be identifiable cases of Vanilla DisGNN.

Rescaling and criteria settings. Since the two datasets under consideration
exhibit different scales, making the use of fixed tolerance errors
inapplicable. To address this, a preprocessing step is performed on both
datasets by rescaling all geometric graphs to ensure that the distance between
the geometric center and the farthest node is $1$. We then fix the rounding
number to $2$ for QM9 and $1$ for ModelNet (which is quite robust against
noise in this scale), and conduct the assessment with the deviation error
ranging from 1e-6 to 1e-1. Note that a deviation error of 1e-1 is quite large
for a geometric graph located within a unit sphere. As a result, many non-
symmetric graphs may still be identified as symmetric under such criteria. We
use this as a rough upper bound only for reference.

Results. The assessment results in Figure 5 reveal the following observations:
1) Concerning the QM9 dataset, even when utilizing the largest deviation error
(1e-1), the proportion of GAC\- and GAVD-symmetric geometric graphs are less
than $\sim$0.1% of the entire dataset. Since GAC\- and GAVD-symmetric
geometric graph spaces are supersets of the unidentifiable space of Vanilla
DisGNN, therefore the unidentifiable proportion can only be less than
$\sim$0.1%. When considering a relatively stricter deviation error (1e-2),
even the simplest symmetric graphs, i.e, GA-symmetric graphs, amount to less
than $\sim$0.25% of the whole dataset. With the strictest deviation error,
only 0.0046% of the graphs (6 out of $\sim$130K) exhibit symmetry across all
symmetric types. 2) In the ModelNet dataset, as anticipated, all the geometric
graphs inherently possess GA-symmetry. However, when deviation error is less
than 1e-1, only 1 or 2 geometric graphs demonstrate GAC-symmetry. And there is
no GAVD-symmetric graphs found across all deviation errors.

To summarize, the statistical results imply that the occurrence of
unidentifiable graphs of Vanilla DisGNN is exceedingly rare and practically
negligible in real-world scenarios.

Figure 5: Assessment of symmetric geometric graphs in real-world datasets. (a)
Proportion of symmetric geometric graphs in the QM9 dataset. (b) Proportion of
symmetric geometric graphs in the ModelNet dataset. The proportions of GAVD-
symmetric geometric graphs in ModelNet is zero across all deviation errors.

##  Appendix B Supplementary Analysis for GeoNGNN

###  B.1 Complexity Analysis

Without considering the complexity of achieving injective intermediate
functions, GeoNGNN achieves theoretical completeness with an asymptotic time
complexity of $O(n^{3})$. This complexity arises from the fact that there are
$n$ subgraphs, each of which undergoes the complete-version Vanilla DisGNN
operation, resulting in an overall complexity of $O(n^{2})$ per subgraph.
Importantly, this time complexity is consistent with that of 2-F-DisGNN (Li et
al., 2023b), DimeNet (Gasteiger et al., 2019), and SphereNet (Liu et al.,
2021), when their conditions for achieving E(3)-completeness is met.

Practical GeoNGNN achieves an asymptotic time complexity of $O(n)$ by
restricting the subgraph cutoff and the message passing cutoff to fixed
values. Experiments show that practical GeoNGNN exhibits good inductive bias
through capturing local subgraph environments. In the following subsection, we
provide a demonstration that practical GeoNGNN also possesses better
theoretical expressiveness compared to Vanilla DisGNN.

###  B.2 Theoretical Expressiveness with finite subgraph radius

Though in practice we have to set finite subgraph radius for GeoNGNN, this
still leads to boosted expressiveness compared to Vanilla DisGNN. We
demonstrate this through an example.

Take the left pair of geometric graphs in Figure 8 for example, note that this
pair of geometric graphs cannot be distinguished by Vanilla DisGNN. Assuming
that the subgraph radius for each node is finite, only covering nodes’ one-hop
neighbors, as illustrated in Figure 6. The representation of the green node
produced by inner Vanilla DisGNN will differ between the two graphs, due to
the presence of long-distance information on the left graph, whereas it is
absent on the right graph. Therefore, GeoNGNN with such a small subgraph
radius can easily distinguish the two geometric graphs.

Figure 6:  An example that illustrates the separation power of finite-
subgraph-size GeoNGNN. The green node represents the central node, while the
green sphere depicts the subgraph environment surrounding the central node.
The brown line signifies the distance information that will be aggregated
during the message passing.

###  B.3 Supplementary Experiment Information

  1. 1.

Performance of GeoNGNN on MD22 (Table 3) in Section 6.3.

Table 3: MAE loss on MD22. Energy (E) in meV/atom, force (F) in meV/Å. We
color the cell if GeoNGNN outperforms Vanilla DisGNN. The average rank is the
average of the rank of each row. We also show the number of atoms for each
molecule.

|  |  |  | Equivariant models | Invariant models
---|---|---|---|---|---
Molecule | # atoms | Target | sGDML | PaiNN | TorchMD-NET | Allegro | Equiformer | MACE | Vanilla Dis. | GeoNGNN
|  | E | 0.4 | 0.121 | 0.116 |  0.105 | 0.106 | 0.064 | 0.158 | 0.106
Ac-Ala3-NHMe | 42 | F | 34 | 10.0 | 8.1 | 4.6 |  3.9 | 3.8 | 9.5 | 4.9
|  | E | 1 | 0.089 |  0.093 | 0.089 | 0.214 | 0.102 | 0.281 | 0.105
Docosahexaenoic acid | 56 | F | 33 | 5.9 | 5.2 | 3.2 | 2.5 |  2.8 | 11.3 | 3.8
|  | E | 2 | 0.076 |  0.069 | 0.124 | 0.078 | 0.062 | 0.077 | 0.091
Stachyose | 87 | F | 29 | 10.1 | 8.3 | 4.2 |  3.0 | 3.8 | 4.1 | 2.9
|  | E | 0.52 | 0.121 | 0.139 | 0.103 | 0.109 |  0.079 | 0.085 | 0.073
AT-AT | 60 | F | 30 | 10.3 | 8.8 | 4.1 |  4.3 |  4.3 | 8.463 | 5.8
|  | E | 0.52 | 0.097 | 0.193 | 0.145 | 0.055 |  0.058 | 0.082 | 0.078
AT-AT-CG-CG | 118 | F | 31 | 16.0 | 20.4 | 5.6 |  5.4 | 5 | 13.8 | 8.1
|  | E | 0.34 | - | - | - | - |  0.141 | 0.158 | 0.113
Buckyball catcher | 148 | F | 29 | - | - | - | - | 3.7 | 19.3 |  4.8
|  | E | 0.47 | - | - | - | - | 0.194 | 0.383 |  0.204
Double-walled nanotube | 370 | F | 23 | - | - | - | - |  12 | 16.5 | 11.2
AVG RANK | 6.86 | 5.40 | 5.30 | 3.50 | 3.00 | 1.79 | 4.57 | 2.93

  2. 2.

Efficiency analysis (Table 4) in Section 6.3.

Table 4: Efficiency Analysis of Models. The batch size for all molecules is
set to 16, except for Bu and Do where it is 4. Models marked with an asterisk
(*) utilize a batch size of 8, except for Bu and Do, which use a batch size of
2. The evaluation is conducted on Nvidia A100.

Molecule | # atoms | MACE | 2F-DisGNN | Equiformer* | GeoNGNN
---|---|---|---|---|---
Ac-Ala3-NHMe | 42 | 0.166 | 0.130 | 0.305 | 0.070
13400 | 20542 | 38895 | 12997
Docosahexaenoic acid | 56 | 0.209 | 0.215 | 0.397 | 0.088
17875 | 35844 | 51565 | 16980
Stachyose | 87 | 0.388 | OOM | OOM | 0.161
33146 | OOM | OOM | 32430
AT-AT | 60 | 0.195 | 0.244 | 0.361 | 0.083
17310 | 41125 | 50032 | 15864
AT-AT-CG-CG | 118 | 0.437 | OOM | OOM | 0.175
38090 | OOM | OOM | 34951
Buckyball catcher | 148 | 0.183 | 0.382 | 0.382 | 0.074
14466 | 62790 | 47702 | 13891
Double-walled nanotube | 370 | 0.545 | OOM | OOM | 0.180
44923 | OOM | OOM | 36849

  3. 3.

Subgraph size effect analysis (Figure 7) in Section 6.4.

Figure 7: Effect of subgraph size for energy and force prediction on Ac-
Ala3-NHMe, AT-AT and Buckyball catcher in MD22. Subgraph size in Å, energy (E)
in meV/atom, force (F) in meV/Å.

##  Appendix C Detailed Experimental Settings

###  C.1 Dataset Settings

Synthetic dataset. We generate the synthetic dataset by implementing the
counterexamples proposed by Li et al. (2023b).

The dataset includes 10 isolated cases and 7 combinatorial cases, where each
case consists of a pair of symmetric geometric graphs that cannot be
distinguished by Vanilla DisGNN. Figure 8 shows two pairs of selected
counterexamples.

Figure 8: Selected counterexamples in the synthetic dataset. Only colored
nodes belong to the geometric graphs. The grey nodes and “edges” are for
visualization purposes only. (a) One isolated case. (b) One combinatorial
case.

The 10 isolated cases comprise the following: 6 pairs of geometric graphs
sampled from regular dodecahedrons, 1 pair from icosahedrons, 2 pairs from a
combination of one cube and one regular octahedron, and 1 pair from a
combination of two cubes. In the combination cases, the relative size is set
to 1/2.

The 7 combinatorial cases are obtained through the augmentation of the 6 pairs
of graphs sampled from regular dodecahedrons and 1 pair from icosahedrons,
using the method outlined in Theorem A.1 of Li et al. (2023b). When augmenting
the base graph, we consider the original, complementary, and all types of the
base graph, respectively.

Given that the counterexamples are designed to test the maximal expressiveness
of geometric models, we configure all graphs in the dataset to be fully
connected.

rMD17 and MD22. The data split (training/validation/testing) in rMD17 is 950 /
50 / the rest, following the convention used in related works such as Batatia
et al. (2022); Gasteiger et al. (2021). For MD22, we adopt the data split
specified in Chmiela et al. (2023), which is also consistent with the other
works. We train the models using a batch size of 4.

To optimize the parameters $\theta$ of the model $f_{\theta}$, we use a
weighted loss function:

$\mathcal{L}(\boldsymbol{X},\boldsymbol{z})=(1-\rho)|f_{\theta}(\boldsymbol{X},\boldsymbol{z})-\hat{t}(\boldsymbol{X},\boldsymbol{z})|+\frac{\rho}{N}\sum_{i=1}^{N}\sqrt{\sum_{\alpha=1}^{3}(-\frac{\partial
f_{\theta}(\boldsymbol{X},\boldsymbol{z})}{\partial\boldsymbol{x}_{i\alpha}}-\hat{F}_{i\alpha}(\boldsymbol{X},\boldsymbol{z}))^{2}},$

where $X\in\mathbb{R}^{N\times 3}$ and $z\in\mathbb{R}^{N}$ represents the $n$
atoms’ coordinates and atomic number respectively, $\hat{t}$ and $\hat{F}$
represents the molecule’s energy and forces acting on atoms respectively. The
force ratio $\rho$ is chosen as 0.99 or 0.999.

In rMD17, the experimental results of Allegro (Musaelian et al., 2023), NequIP
(Batzner et al., 2022), GemNet (Gasteiger et al., 2021), are sourced from
Musaelian et al. (2023). The result of PaiNN (Schütt et al., 2021) is sourced
from Batatia et al. (2022). The results of 2-F-DisGNN (Li et al., 2023b) and
MACE (Batatia et al., 2022) are reported by their original papers. We trained
and evaluated DimeNet (Gasteiger et al., 2019) using its implementation in
Pytorch Geometric (Fey & Lenssen, 2019) and the default parameters (We find
that the default parameters produce the best performance).

In MD22, the results of sGDML and MACE (Kovacs et al., 2023) are sourced from
Kovacs et al. (2023). The results of PaiNN (Schütt et al., 2021), TorchMD-Net
(Thölke & De Fabritiis, 2021), Allegro (Musaelian et al., 2023), and
Equiformer (Liao & Smidt, 2022) are obtained from the work presented by Li et
al. (2023a).

###  C.2 Model Settings.

RBF. Following previous work, we use radial basis functions (RBF) $f^{\rm
rbf}_{\rm e}:\mathbb{R}\to\mathbb{R}^{H_{\rm rbf}}$ to expand the euclidean
distance between two nodes into a vector, which is shown to be beneficial for
inductive bias Gasteiger et al. (2019); Li et al. (2023b). We use the same
nexpnorm RBF function like Li et al. (2023b), defined as

$f_{e}^{\rm rbf}(e_{ij})_{k}=e^{-\beta_{k}({\rm exp}(-e_{ij})-\mu_{k})^{2}},$
(2)

where $\beta_{k},\mu_{k}$ are coefficients of the $k^{\rm th}$ basis.

Vanilla DisGNN. In each stage of the Vanilla DisGNN, we augment its
expressiveness and experimental performance by stacking dense layers or
residual layers, which together with summation aggregation essentially forming
the multiset function described in Xu et al. (2018). Vanilla DisGNN’s
architecture is described in Figure 9.

Figure 9: Architecture of Vanilla DisGNN. $z,d,t$ represent the atomic number,
euclidean distance and the target output, respectively. Each Linear block
represents an affine transformation with learnable parameters $W,b$, while the
Dense block extends the Linear block by incorporating a non-linear activation
function. $\odot$ represents Hadamard product.

We set the number of VD-Conv layers to 6. The hidden dimension is set to 512
and the dimension of radial basis functions (RBF) is set to 16. The message
passing cutoff is set to $13$Å for rMD17 and $7$Å for MD22. We employ the
polynomial envelope with $p=5$, as proposed in Gasteiger et al. (2019), along
with the corresponding cutoff.

GeoNGNN. The high-level architecture of GeoNGNN is described in Definition
4.1. The inner Vanilla DisGNN, which runs on the ego subgraph of each node, is
similar to the Vanilla DisGNN block shown in Figure 9. However, the inner
Vanilla DisGNN additionally performs node marking and distance encoding for
each node $j$ in node $i$’s subgraph before passing their representations to
VD-Conv layers:

$h_{ij}\leftarrow
h_{j}\odot\text{MLPs}(\text{RBF}(d_{ij}))\odot\text{MLPs}(\text{Emb}(\mathds{1}_{j=i})))$
(3)

where $h_{ij}$ represents node $j$’s representation in $i$’s subgraph.

The outer Vanilla DisGNN additionally fuses the subgraph representation
$t_{i}$ produced by the inner Vanilla DisGNN for node $i$ with $h_{i}$
obtained from the embedding layer:

$h_{i}\leftarrow\text{MLPs}([h_{i},t_{i}]))$ (4)

The hidden dimension and message passing cutoff are set to the same values as
those in Vanilla DisGNN. The subgraph size is set to 13 Å for rMD17 and 5 Å
for MD22, and the maximal subgraph size is set to 25. We set
$(N_{in},N_{out})$ as $(5,1)$ for rMD17 and $(3,3)$ for MD22. It is worth
mentioning that the total number of convolutional layers is the same as that
of Vanilla DisGNN. This ensures that the receptive field of the two models is
roughly the same, thereby guaranteeing a relatively fair comparison.

We optimize all models using the Adam optimizer (Kingma & Ba, 2014),
incorporating exponential decay and plateau decay learning rate schedulers, as
well as a linear learning rate warm-up. To mitigate the risk of overfitting,
we employ early stopping based on validation loss and apply exponential moving
average (EMA) with a decay rate of 0.99 to the model parameters during the
validation and testing phases. The models are trained on Nvidia RTX 3090 and
Nvidia A100 GPUs.

##  Appendix D GeoNGNN-C: SE(3)-complete variant of GeoNGNN

###  D.1 Definition and Theoretical Analysis of GeoNGNN-C

As mentioned in Section 4.1, GeoNGNN-C is designed by simply replacing the
undirected distance in GeoNGNN with directed distance. The formal definition
is as follows:

######  Definition D.1.

The fundamental architecture of GeoNGNN remains the same, with the exception
that the inner GNN for node $k$’s subgraph performs the subsequent message-
passing operation:

$h_{k,i}^{(t+1)}=f_{\rm
mp}(h_{k,i}^{(t)},\\{\\!\\!\\{(h_{k,j}^{(t)},d_{k,ij})\mid j\in
N_{k}(i)\\}\\!\\!\\}),$

where $h^{(t)}_{k,j}$ represents node $i$’s representation at timestep $t$ in
node $k$’s subgraph, and the directed distance, $d_{k,ij}$, is defined as:

$d_{k,ij}=f_{\rm
dist}(sign(\vec{r}_{ci}\times\vec{r}_{cj}\cdot\vec{r}_{ck}),d_{ij}),$

where $c$ is the geometric center of the geometric graph.

As can be easily validated, directed distance is invariant under
SE(3)-transformation while undergoing a sign reversal after reflecting the
geometric graph. Consequently, GeoNGNN-C retains SE(3)-invariance while
possessing the potential to discriminate enantiomers. Significantly, we show
that GeoNGNN-C is SE(3)-complete, able to distinguish all pairs of
enantiomers:

######  Theorem D.2.

(SE(3)-Completeness of GeoNGNN-C) When the conditions described in Theorem 4.2
are met, GeoNGNN-C is SE(3)-complete.

The formal proof is referred to Appendix F.8.

###  D.2 Experimental Evaluation of GeoNGNN-C

Datasets and tasks. We evaluate the ability of GeoNGNN-C to distinguish
enantiomers and learn meaningful chirality-relevant representations through
three tasks on two datasets (Adams et al., 2021; Gaiński et al., 2023): 1)
Classification of tetrahedral chiral centers as R/S. R/S offers a fundamental
measure of molecular chirality, and this classification task serves as an
initial evaluation of the model’s capacity to discriminate enantiomers. The
underlying dataset contains a total of 466K conformers of 78K enantiomers with
a single tetrahedral chiral center. 2) Enantiomer ranking task and binding
affinity prediction task. The two tasks share the same underlying dataset,
while the second task requires models to predict the binding affinity value
for each enantiomer directly, and the first requires the model to predict
which enantiomer between the corresponding pair exhibits higher such values.
Chirality is essential here because enantiomers often exhibit distinct
behaviors when docking in a chiral protein pocket, thus leading to differences
in binding affinity. The underlying dataset contains 335K conformers from 69K
enantiomers carefully selected and labeled by Adams et al. (2021).

Model architecture and training/evaluation details. In the task of R/S
classification, GeoNGNN-C adopts a three-layer outer GNN positioned before the
inner GNNs. This configuration is designed to enhance the node features first,
facilitating the subsequent extraction of chirality-related properties within
the inner GNNs. For the other two tasks, GeoNGNN-C consists of five inner
layers and one outer layer, with the outer GNN placed after the inner GNN. The
model is trained with L1 loss. Specifically, if predicted affinity difference
between two enantiomers falls below the threshold of 0.001, it is considered
that the model lacks the capability to discriminate between the two
enantiomers. Note that all the evaluation criteria are consistent with
previous works (Adams et al., 2021; Gaiński et al., 2023) for fair
comparisons.

Models to compare with. We compare GeoNGNN-C against previous high-performance
models, SphereNet (Liu et al., 2021), ChiRo (Adams et al., 2021), ChiENN
(Gaiński et al., 2023), and other baseline models in (Pattanaik et al., 2020;
Adams et al., 2021; Gaiński et al., 2023). It is worth noting that, for the
last two tasks, the docking scores are labeled at the stereoisomer level,
meaning that all different conformers of a given enantiomer are assigned the
same label, specifically the best score, by Adams et al. (2021). As a result,
2D Graph Neural Networks (GNNs) such as DMPNN+tags and models that possess
invariance to conformer-level transformations, such as bond rotations,
including ChiRo (Adams et al., 2021), Tetra-DMPNN (Pattanaik et al., 2020) and
ChiENN (Gaiński et al., 2023), inherently exhibit significantly better data
efficiency and usually exhibit better performance. GeoNGNN-C and SphereNet do
not exhibit such invariance, and are trained on 5 conformers for each
enantiomer as data augmentation.

Results. The experimental results for the three tasks are presented in Table
5. It can be observed that GeoNGNN-C demonstrates a competitive performance
compared to SOTA methods on the R/S classification task. Importantly, despite
the simple and general model design, GeoNGNN-C outperforms models specifically
tailored for the last two tasks, such as ChIRo and ChiENN, which incorporates
invariance to bond rotations. It successfully learns the approximate
invariance from only 5 conformers per enantiomer and achieves the second-best
result (very close to the best one) on the enantiomer ranking task and new
SOTA results on the binding affinity prediction task. These results reveal the
potential of GeoNGNN-C as a simple but theoretically chirality-aware
expressive geometric model.

Table 5: Results on chiral-sensitive tasks compared to reference models. We
bold the best result among models and underline the second best ones.

| R/S | Enantiomer ranking | Binding affinity
---|---|---|---
Model | Accuracy ↑ | R. Accuracy ↑ | MAE ↓
DMPNN+tags | - | 0.701$\pm$0.003 | 0.285$\pm$0.001
SphereNet | 0.982$\pm$0.002 | 0.686$\pm$0.003 | -
Tetra-DMPNN | 0.935$\pm$0.001 | 0.690$\pm$0.006 | 0.324$\pm$0.02
ChIRo | 0.968$\pm$0.019 | 0.691$\pm$0.006 | 0.359$\pm$0.009
ChiENN | 0.989$\pm$0.000 | 0.760$\pm$0.002 | 0.275$\pm$0.003
GeoNGNN-C | 0.980$\pm$0.002 | 0.751$\pm$0.003 | 0.254$\pm$0.000

##  Appendix E GeoNGNN with Sampling Policies

In this appendix, we explore several efficient sampling policies for local
anchors that maintain permutation invariance, without requiring the pooling of
all local anchors like GeoNGNN. We evaluate the experimental performance of
these sampling policies on a subset of representative molecules from the rMD17
dataset.

Surprisingly, our results demonstrate that all of the sampling strategies
consistently lead to a decrease in performance. This observation may be
attributed to the unfaithfulness of these alternative sampling methods in
capturing the characteristics of physical/chemical systems. Consequently,
these theoretical results mainly serve as negative results, demonstrating that
the proposed GeoNGNN, described in the main body of this paper, is a much
better choice, which is superior in both theoretical and experimental
performance.

###  E.1 Node-type Sampling

Table 6: MAE loss of node-type sampling policy on revised MD17. Energy (E) in
kcal/mol, force (F) in kcal/mol/Å. $C$, $H$ $N$, $O$ represents the GeoNGNN
employing sampling policy with corresponding atoms. We bold the best result
among models adopting sampling policies, and underlines the second best.

Molecule | Target | GeoNGNN | C | H | O
---|---|---|---|---|---
aspirin | E | 0.0490 | 0.0698 |  0.0887 | 0.0984
F | 0.1733 | 0.2304 |  0.3003 | 0.3237
ethanol | E | 0.0090 |  0.0113 | 0.0104 | 0.0164
F | 0.0616 |  0.0758 | 0.0678 | 0.1019
naphthalene | E | 0.0083 |  0.0129 | 0.0112 | -
F | 0.0437 | 0.0451 |  0.0616 | -
salicylic acid | E | 0.0165 | 0.0243 |  0.0261 | 0.0740
F | 0.0897 | 0.1175 |  0.1379 | 0.2779
uracil | E | 0.0108 |  0.0230 | 0.0216 | 0.0277
F | 0.0716 | 0.1355 |  0.1403 | 0.1735

In this case, we only sample the subgraphs of local anchors $i$ that satisfy
$X_{i}=X^{*}$, where $X^{*}$ is the specified initial node feature, and run
inner GNN only on these subgraphs. For example, in molecule systems, we only
sample subgraphs of all $C$ atoms or $H$ atoms.

In outer GNN, the initial representation of a node depends on whether it is
the sampled local anchor. If the node is sampled, its initial representation
is obtained by fusing its given initial feature with the subgraph
representation summarized by inner GNN. On the other hand, if the node is not
sampled, its initial representation is calculated by only embedding its
initial feature, but with different parameters.

We evaluate the sampling policy on $C$-type, $H$-type, and $O$-type,
respectively, with the results outlined in Table 6. There are two main
phenomena. 1) Models that adopt node-type sampling policies consistently
demonstrate worse performance compared to the main model, GeoNGNN, which
leverages Vanilla DisGNN on all atoms. 2) A common trend can be observed:
typically, the model yields better performance when more local anchors are
sampled. For example, in the cases of aspirin, where there are 9, 8, and 4
atoms of C, H, O respectively, the performance matches the aforementioned
pattern. Likewise, for ethanol, with 2, 6, and 1 atoms of C, H, O
respectively, the pattern persists. This phenomenon may be attributed to the
fact that the learning of more balanced representations of subgraphs
translates to a more favorable inductive bias for prediction.

###  E.2 GeoNGNN-P

Another possible sampling way, which can be more general, is to first perform
graph partition based on Euclidean distance metric, splitting the graph into
$K$ clusters, where $K$ is a hyper-parameter that can be controlled. Then, for
each cluster, we can introduce a virtual node by simply calculate the
cluster’s geometric center. Finnaly, we only sample these virtual nodes as the
local anchors. We name this design as GeoNGNN-P, where $P$ represents
partitioning. The overall architecture is illustrated in Figure 10.

Figure 10: Overview of GeoNGNN-P. There are three main steps: Graph partition,
subgraph extraction, and prediction. In Graph Partition figure, colors
indicate partitions, while in Prediction figure, colors indicates initial node
features for outer GNN.

There are three main design principles for this:

  1. 1.

Partitioning method. We provide two candidate partitioning methods for
GeoNGNN-P. The first is METIS (Abou-Rjeili & Karypis, 2006), a widely
recognized and efficient graph clustering method. We utilize the inverse of
Euclidean distance as the metric, ensuring that nodes close to each other are
more likely to be assigned to the same cluster. This approach effectively
incorporates a geometric prior into the geometric graph. The second is BRICS
(Degen et al., 2008), a chemical-specific method designed for partitioning
molecules into 16 fragment prototypes (chemical motifs). While BRICS is
tailored for chemical settings, it may not possess the same level of
generality as METIS. Nevertheless, BRICS incorporates good chemical prior into
the geometric graph, offering potential advantages in domain-specific
applications.

In METIS, the value of cluster number $K$ is adjustable, whereas in BRICS it
is not. It is worth noting that when considering BRICS or METIS with a fixed
finite $K$, there is no assurance that all geometric graphs can be identified,
as the virtual nodes may all coincide with the geometric center. Nevertheless,
METIS can effectively identify all known unidentifiable cases for Vanilla
DisGNN, thereby greatly boosting expressiveness.

  2. 2.

Subgraph radius. Theoretically, in order to achieve theoretical completeness,
the subgraph radius for each local anchor should be infinite, as stated in
Theorem 4.2. However, for practical reasons, we set the subgraph radii to
finite numbers to enhance efficiency. Specifically, the subgraph radius $r$
can be decomposed into two terms: $r=r_{\text{cluster}}+r_{\text{overlap}}$.
Here, $r_{\text{cluster}}$ represents the maximum distance between the cluster
center and the nodes within the cluster, while $r_{\text{overlap}}$ is a
hyper-parameter that determines the extent of overlap between different
cluster subgraphs.

  3. 3.

Initial node representations in the outer GNN. We assign each node $i$ its
initial representation in the outer GNN as the average representation
calculated within all the subgraph it belongs to, ensuring smoothness and
maximum geometric information reservation.

We evaluate GeoNGNN-P with BRICS and METIS (with different $k$ ratio) on
rMD17, and the results are reported in Table 7. 1) Similarly to the node-
sampling policy, the accuracy of predictions improves as METIS produces more
clusters. The performance closest to the main model, GeoNGNN, is achieved when
METIS produces clusters with $K=N\times 0.5$. 2) Despite incorporating
chemical priors, BRICS produces too few clusters (such as naphthalene and
uracil, where it even cannot further split the molecule), and therefore
produce bad prediction.

These findings highlight that while adopting partition methods and sampling
fewer local anchors can enhance efficiency and valuable geometric/chemical
prior, having too few local anchors significantly worsens performance. This
observation aligns with the trends observed in node-sampling policies.

Table 7: MAE loss of GeoNGNN-P on revised MD17. Energy (E) in kcal/mol, force
(F) in kcal/mol/Å. METIS ($k$) represents the model adopts splitting which
splits the graph into $K=k*N$ clusters. We bold the best result among all
GeoNGNN-P designs, and underlines the second best.

Molecule | Target | GeoNGNN | METIS (0.1) | METIS (0.3) | METIS (0.5) | BRICS
---|---|---|---|---|---|---
aspirin | E | 0.0490 | 0.3476 | 0.4892 |  0.3401 | 0.1508
F | 0.1733 | 0.6734 | 0.5702 | 0.4025 |  0.4833
ethanol | E | 0.0090 | 0.0160 |  0.0157 | 0.0134 | 0.0190
F | 0.0616 |  0.1028 | 0.1040 | 0.0910 | 0.1169
naphthalene | E | 0.0083 | 0.1277 |  0.1203 | 0.0129 | 0.1411
F | 0.0437 | 0.4416 |  0.3664 | 0.0682 | 0.4567
salicylic acid | E | 0.0165 | 0.1637 |  0.0601 | 0.0225 | 0.0661
F | 0.0897 | 0.5908 |  0.2674 | 0.1175 | 0.3465
uracil | E | 0.0108 | 0.2404 |  0.0714 | 0.0127 | 0.1182
F | 0.0716 | 0.7274 |  0.3995 | 0.0816 | 0.5546

##  Appendix F Proof

###  F.1 Equivalence of Reconstruction and Completeness

Given a permutation- and E(3)-invariant function $f$, it is apparent that $f$
is E(3)-complete $\iff$ $f$ is capable of identifying all geometric graphs,
simply by definition. Hence, our goal is to show that for any geometric graph
$G$, $f(G)\rightarrow G$ up to permutation and $E(3)$-transformation $\iff$ if
$f$ is $E(3)$-complete.

We now consider all E(3)-isomorphic geometric graphs as one single element in
a new input space $\mathcal{I}$. Consequently, $f(G)\rightarrow G$ up to
permutation and $E(3)$-transformation is equivalent to asserting that
$f(I)\rightarrow I$, and the definition of E(3)-completeness is: $\forall
I_{1},I_{2}\in\mathcal{I}$, $f(I_{1})=f(I_{2})\iff I_{1}=I_{2}$. Note that
both statements are equivalent to that $f$ is an injective encoder on
$\mathcal{I}$. Thus, the two statements are equivalent to each other.

###  F.2 Proof of Proposition A.3

  1. 1.

$|\mathbf{A}(G)|=1\implies$ all $X_{k}^{*}$-type geometric centers coincide.

This is trivially true, because the $X_{k}^{*}$-type geometric center is
simply a specific type of global anchor. Since all global anchors coincide, it
follows that all $X_{k}^{*}$-type geometric centers also coincide.

  2. 2.

All $X_{k}^{*}$-type geometric centers coincide $\implies$
$|\mathbf{A}(G)|=1$.

Denote $I_{k}=\\{i\mid X_{i}=X_{k}^{*},\forall i\in[n]\\}$ as the index set.
Let $m_{k}^{*}=m(X_{k}^{*})$ represent the mass of the $X_{k}^{*}$ global
anchor. Let $M_{k}^{*}=\sum_{i\in I_{k}}m_{k}^{*}$ denote the sum of masses
associated with the $X_{k}^{*}$ global anchor. Represent the $X_{k}^{*}$-type
geometric centers as $A_{k}^{*}\in\mathbb{R}^{3}$.

For an arbitrary global anchor $A^{m}(G)$ defined by $m$, we have
$A^{m}(G)=\frac{\sum_{i\in[n]}m(X_{i})P_{i}}{\sum_{i\in[n]}m(X_{i})}$ by
definition, which can be decomposed as follows:

$\displaystyle A^{m}(G)$
$\displaystyle=\frac{\sum_{i\in[n]}m(X_{i})P_{i}}{\sum_{i\in[n]}m(X_{i})}$
$\displaystyle=\frac{\sum_{k\in[K]}\sum_{i\in
I_{k}}m_{k}^{*}P_{i}}{\sum_{k\in[K]}\sum_{i\in I_{k}}m_{k}^{*}}$
$\displaystyle=\frac{\sum_{k\in[K]}A_{k}^{*}M_{k}^{*}}{\sum_{k\in[K]}M^{*}_{k}}$
(5)

Since all $A_{k}^{*}$ coincide, denoted as $A$, we have:
$A^{m}(G)=\frac{A\sum_{k\in[K]}M_{k}^{*}}{\sum_{k\in[K]}M^{*}_{k}}=A$. Thus,
all the global anchors coincide.

###  F.3 Proof of Theorem 3.4

We describe the reconstruction function $f$ that takes Vanilla DisGNNs’ output
$v$ as input and produces the geometric graph $G$ up to permutation and
E(3)-transformation. We initially assume that the point cloud does not
degenerate into 2D, which is a trivial case and will be discussed at the end
of the proof.

Initially, the output $v$ of a 2-round Vanilla DisGNN is provided. Under the
injectivity assumption of Vanilla DisGNN, it can be inferred that
$v\to\\{\\!\\!\\{h_{i}^{(2)}\mid i\in[n]\\}\\!\\!\\}$. Note that
$h_{i}^{(2)}\to h_{i}^{(1)}\to
h_{i}^{(0)}\to(d_{i,A_{1}}d_{i,A_{2}},d_{A_{1},A_{2}})$, implying that the
structure of the triangle formed by $i,A_{1},A_{2}$ can be ascertained from
$h^{(2)}_{i}$. Since nodes can receive information about the triangular shapes
formed by other nodes and the two anchors during the message passing process,
it is feasible to determine the following dihedral angle list from
$h_{i}^{(2)}$:

$\displaystyle h_{i}^{(2)}$
$\displaystyle=\text{HASH}(h_{i}^{(1)},\\{\\!\\!\\{(h_{j}^{(1)},d_{ij})\mid
j\in[n]\\}\\!\\!\\})$
$\displaystyle\to\\{\\!\\!\\{(h_{i}^{(1)},h_{j}^{(1)},d_{ij})\mid
j\in[n]\\}\\!\\!\\}$
$\displaystyle\to\\{\\!\\!\\{(h_{i}^{(0)},h_{j}^{(0)},d_{ij})\mid
j\in[n]\\}\\!\\!\\}$
$\displaystyle\to\\{\\!\\!\\{(d_{ij},d_{i,A_{1}},d_{i,A_{2}},d_{j,A_{1}},d_{j,A_{2}},d_{A_{1},A_{2}})\mid
j\in[n]\\}\\!\\!\\}$
$\displaystyle\to\\{\\!\\!\\{\theta(iA_{1}A_{2},jA_{1}A_{2})\mid
j\in[n]\\}\\!\\!\\}.$

Here, $\theta(iA_{1}A_{2},jA_{1}A_{2})$ represents the dihedral angle formed
by plane $iA_{1}A_{2}$ and plane $jA_{1}A_{2}$. If $i$ or $j$ lies on the line
$A_{1}A_{2}$, or the angle $\theta$ is 0, we define/overwrite $\theta$ as
$+\infty$.

Given this observation, we now conduct a search across the multiset
$\\{\\!\\!\\{h_{i}^{(2)}\mid i\in[n]\\}\\!\\!\\}$ to find the node $x$ which
can derive the smallest $\theta(xA_{1}A_{2},yA_{1}A_{2})$ relative to some
other node $y$ (In case of multiple minimal angles, an arbitrary $x$ is
chosen.). Denote the minimal angle as $\alpha$, and we record the
corresponding $h_{x}^{(2)}$. And note that since
$\theta(xA_{1}A_{2},yA_{1}A_{2})$ is derived from
$(h_{x}^{(1)},h_{y}^{(1)},d_{xy})$, the corresponding $(h_{y}^{(1)},d_{xy})$
in the calculation of $h_{x}^{(2)}$ can also be recorded. We now aim to prove
that the entire geometry can be reconstructed using $h_{x}^{(2)}$ and the
corresponding $(h_{y}^{(1)},d_{xy})$.

First of all, having found the node $y$ in the multiset, we can calculate the
exact 3D coordinates of nodes $x,y,A_{1},A_{2}$ up to E(3) transformation
given $(h_{x}^{(2)},h_{y}^{(1)},d_{xy})$. This is because
$(h_{x}^{(2)},h_{y}^{(1)},d_{xy})\to(d_{xy},d_{x,A_{1}},d_{x,A_{2}},d_{y,A_{1}},d_{y,A_{2}},d_{A_{1},A_{2}})$.
At this stage, the coordinates of $n-2$ nodes remain undetermined.

We proceed to traverse all nodes in the multiset
$\\{\\!\\!\\{(h^{(1)}_{j},d_{xj})\mid j\in[n]\\}\\!\\!\\}$ that can be derived
from $h_{x}^{(2)}$ by definition. For each node $j$, with information
$(h_{x}^{(1)},h_{j}^{(1)},d_{xj})$, we can derive
$(d_{jx},d_{j,A_{1}},d_{j,A_{2}})$. Consequently, we can determine the 3D
coordinates of $j$ to at most two positions, which are symmetrically mirroring
w.r.t. the plane $xA_{1}A_{2}$. Notably, $j$’s position is unique if and only
if it lies on the plane $xA_{1}A_{2}$ (denoted as $x$-plane). We first
identify all nodes on the $x$-plane, since their calculated positions are
unique.

Additionally, from $h_{y}^{(1)}$, we can also derive
$(d_{jy},d_{j,A_{1}},d_{j,A_{2}})$ for each node $j$, allowing us to identify
all nodes on the $y$-plane.

The coordinates of these nodes are added to the “known” set of nodes $K$,
while the remaining nodes are labeled as “unknown.”

It is established that there are no “unknown” nodes in the interior (as
$\theta_{xA_{1}A_{2},yA_{1}A_{2}}$ is minimal) and border (since we have
identified these points) of the $x$-plane and $y$-plane. We denote the
interior and border of the two planes as $P_{0}$.

Now, we reflect the $y$-plane mirrorly w.r.t. the $x$-plane which yields the
$p_{-1}$-plane. The interior and border formed by $p_{-1}$-plane and $x$-plane
are denoted as $P_{-1}$. Since there are no “unknown” nodes in $P_{0}$, the
remaining undetermined nodes in $P_{-1}$ can be determined from $h_{x}^{(2)}$,
as their another possible position calculated by $h_{x}^{(2)}$ lie in the
“dead area” $P_{0}$, where it is ensured to be empty (no undetermined nodes
left). Similarly, reflecting the $x$-plane w.r.t. the $y$-plane produces the
$p_{1}$-plane, and the corresponding area by $p_{1}$-plane and $y$-plane is
denoted as $P_{1}$. Nodes in $P_{1}$ are determined likewise from
$h_{y}^{(1)}$. This process continues by reflecting the $p_{1}$-plane w.r.t.
the $x$-plane to obtain the $p_{-2}$-plane, determining the nodes in $P_{-2}$,
and so forth, until all $P$ areas collectively cover the entire 3D space.
Consequently, all nodes can be determined, and the geometric structure can be
reconstructed.

When the geometric graph degenerates into 2D, we can initially derive a node
$i$’s representation $h_{i}^{(2)}$ from the output $v$ of Vanilla DisGNN that
does not lie on the line $A_{1}A_{2}$. By leveraging $h_{i}^{(2)}$, we can
extract the necessary distance information to compute the coordinates of $i$,
$A_{1}$, and $A_{2}$ up to E(3)-transformation. Given that
$h_{i}^{(2)}\to\\{\\!\\!\\{(h_{j}^{(1)},d_{ij})\mid j\in[n]\\}\\!\\!\\}$, we
can derive $(d_{ij},d_{jA_{1}},d_{jA_{2}})$ from each $(h_{j}^{(1)},d_{ij})$.
Consequently, the coordinates of node $j$ can be uniquely determined (2D
setting). And therefore, the complete geometry can be reconstructed up to
E(3)-transformation.

###  F.4 Proof of Proposition 3.2 and Proposition A.1

Like the previous subsection, we describe the algorithm $f$ that takes the
left-end representations of “derive” as input and outputs the right-end
representations. We first give the proof of Proposition 3.2, and at the end,
we additionally explain the proof of Proposition A.1.

Node-GA distance.

Denote $f(m,i)=\sum_{j\in[n]}m(X_{j})d_{ij}^{2}$. It is noteworthy that
$f(m,i)$ can be derived from $h^{(1)}_{i}$, since
$h^{(1)}_{i}\to(h^{(0)}_{i},\\{\\!\\!\\{(h^{(0)}_{j},d_{ij})\mid
j\in[n]\\}\\!\\!\\})\to\\{\\!\\!\\{(X_{j},d_{ij})\mid j\in[n]\\}\\!\\!\\}$
(note that $m$ is given).

$f(m,i)$ can be decomposed as:

$\displaystyle f(m,i)$ $\displaystyle=\sum_{j\in[n]}m(X_{j})d_{ij}^{2}$
$\displaystyle=\sum_{j\in[n]}m(X_{j})||P_{i}-P_{j}||^{2}$
$\displaystyle=\sum_{j\in[n]}m(X_{j})||P_{i}-A^{m}+A^{m}-P_{j}||^{2}$
$\displaystyle=\sum_{j\in[n]}m(X_{j})\big{(}||P_{i}-A^{m}||^{2}+||P_{j}-A^{m}||^{2}-2\langle
P_{i}-A^{m},P_{j}-A^{m}\rangle\big{)}$
$\displaystyle=M||P_{i}-A^{m}||^{2}+\sum_{j\in[n]}m(X_{j})||P_{j}-A^{m}||^{2}-2\langle
P_{i}-A^{m},\sum_{j\in[n]}m(X_{j})(P_{j}-A^{m})\rangle$

where $M=\sum_{j\in[n]}m(X_{j})$ and $\langle\rangle$ denotes the inner
product. By definition, $\sum_{j\in[n]}m(X_{j})(P_{j}-A^{m})=0$. Thus, we
have:

$f(m,i)=M\|P_{i}-A^{m}\|^{2}+\sum_{j\in[n]}m(X_{j})\|P_{j}-A^{m}\|^{2}$

The distance from $i$ to $A^{m}$ can be calculated as:

$\displaystyle\frac{1}{M}\left(f(m,i)-\frac{1}{2M}\sum_{j\in[n]}m(X_{j})f(m,j)\right)$
$\displaystyle=||P_{i}-A^{m}||^{2}=d_{i,A^{m}}^{2}$ (6)

And since

$\displaystyle h^{(2)}_{i}$
$\displaystyle\to(h^{(1)}_{i},\\{\\!\\!\\{(h^{(1)}_{j},d_{ij})\mid
j\in[n]\\}\\!\\!\\})$
$\displaystyle\to(f(m,i),\\{\\!\\!\\{(m(X_{j}),f(m,j))\mid
j\in[n]\\}\\!\\!\\}),$ (7)

we have: $h^{(2)}_{i}\to d_{i,A^{m}}$.

GA-GA distance.

According to Node-GA distance, at round 2, each node is aware of its distance
to the two anchors:

$\displaystyle h_{i}^{(2)}\to(d_{i,A^{m_{1}}},d_{i,A^{m_{2}}})$ (8)

Then, we have:

$\displaystyle h_{i}^{(2)}$
$\displaystyle\to\|P_{i}-A^{m_{1}}\|^{2}-\|P_{i}-A^{m_{2}}\|^{2}$
$\displaystyle=\langle A^{m_{2}}-A^{m_{1}},2P_{i}-A^{m_{1}}-A^{m_{2}}\rangle$

The following derivation holds:

$\displaystyle\\{\\!\\!\\{h_{i}^{(2)}\mid i\in[n]\\}\\!\\!\\}$
$\displaystyle\to\\{\\!\\!\\{(h_{i}^{(2)},m_{1}(X_{i}))\mid
i\in[n]\\}\\!\\!\\}$
$\displaystyle\to\frac{1}{M_{1}}\sum_{i\in[n]}m_{1}(X_{i})\langle-A^{m_{1}}+A^{m_{2}},2P_{i}-A^{m_{1}}-A^{m_{2}}\rangle$
$\displaystyle=\langle-A^{m_{1}}+A^{m_{2}},\big{(}\frac{2}{M_{1}}\sum_{i\in[n]}m_{1}(X_{i})P_{i}\big{)}-A^{m_{1}}-A^{m_{2}}\rangle$
$\displaystyle=\langle-A^{m_{1}}+A^{m_{2}},2A^{m_{1}}-A^{m_{1}}-A^{m_{2}}\rangle$
$\displaystyle=\langle-A^{m_{1}}+A^{m_{2}},A^{m_{1}}-A^{m_{2}}\rangle$
$\displaystyle=-||A^{m_{1}}-A^{m_{2}}||^{2}$ (9)

where $M_{1}=\sum_{i\in[n]}m_{1}(X_{i})$. This provides the distance between
the two anchors.

Counting Global Anchors.

According to previous proof, $v_{G}$ can derive the set
$AD=\\{d_{A^{X^{*}},A^{c}}\mid X^{*}\in\\{X_{i}\mid i\in[n]\\}\\}$. Here,
$A^{X^{*}}$ represents the $X^{*}$-type center of $G$, while $A^{c}$
represents the geometric center.

According to Proposition A.3, global anchor set degenerates into one point
$\iff$ all $A^{X^{*}}$ coincide. Therefore, we can determine whether the
global anchor set degenerates based on $AD$.

If $AD=\\{0\\}$, we can conclude that all the $X^{*}$-type center coincide
with the geometric center; therefore, global anchor degenerates, i.e.,
$|\mathbf{A}(G)|=1$.

And if $AD$ contains non-zero elements, then at least one $X^{*}$-type center
is different from the geometric center. Note that $A^{X^{*}}$ and $A^{c}$ are
all in $\mathbf{A}(G)$; therefore, $\mathbf{A}(G)>1$.

As such, the sequence proceeds as follows: $v_{G}\to AD\to\mathds{1}_{AD\text{
contains non-zero elements}}\to\mathds{1}_{|\mathbf{A}(G)|=1}$.

Proof of Proposition A.1

Based on previous proof, it has been shown that starting from the node
representation $h_{i}^{(2)}$ generated by a two-round Vanilla DisGNN, we have
that $h_{i}^{(2)}\to d_{i,A^{c}}$. This indicates that a two-round Vanilla
DisGNN is capable of performing Center Enhancement ($\mathcal{C}$).
Furthermore, since the node individualization performed by an infinite-round
Vanilla DisGNN is no coarser than that of the two-round Vanilla DisGNN, we can
conclude that
$\mathbf{A}^{\mathcal{C}}(G)\subseteq\mathbf{A}^{\mathcal{VD}}(G)$.

The iterations of Vanilla DisGNN can be manually divided into two distinct
phases. In the first phase, the algorithm continues to run until there is no
further change in the node individualization. This phase focuses on enhancing
the node features and expanding the global anchors to $\mathcal{VD}$ enhanced
global anchors. In the second phase, Vanilla DisGNN operates on the augmented
geometric graph for two additional rounds. Analogous to the previous proof, we
can derive all the distance encoding information pertaining to GAVD.

###  F.5 Proof of Theorem 3.5 and Theorem A.2

Here, we first prove Theorem 3.5, and at the end explains the proof of Theorem
A.2.

We prove the equivalent converse condition: Given a geometric graph $G$, if
$|\mathbf{A}(G)|>1$, then for any graph $G^{\prime}$ that is not
E(3)-isomorphic to $G$, Vanilla DisGNN will produce different outputs for
them.

Let $A_{1}$ and $A_{2}$ be two arbitrary distinct anchors in $\mathbf{A}(G)$.
According to Proposition 3.2, Vanilla DisGNN can automatically learn the
distance information among node $i$, $A_{1}$ and $A_{2}$, enabling it to
perform APE w.r.t. the two anchors. Then, based on Theorem 3.4, one can
reconstruct $G$ up to permutation and E(3) transformation from the encoding
vector $v_{G}\in\mathbb{R}^{k}$ produced by Vanilla DisGNN for $G$.

Now, consider an arbitrary geometric graph $G^{\prime}$ that is not
E(3)-isomorphic to $G$.

If $|\mathbf{A}^{\mathcal{VD}}(G^{\prime})|>1$, we can reconstruct
$G^{\prime}$ up to permutation and E(3)-transformation from the encoding
vector $v_{G^{\prime}}$ produced by Vanilla DisGNN. By comparing these two
reconstructed geometric graphs, we can conclude $v_{G^{\prime}}\neq v_{G}$.

If $|\mathbf{A}^{\mathcal{VD}}(G^{\prime})|=1$, based on the “Counting GA”
item in Proposition 3.2, we can also prove that $v_{G^{\prime}}\neq v_{G}$,
since $v_{G^{\prime}}\to False$ (No more than 1 global anchor) while
$v_{G^{\prime}}\to True$ (Multiple global anchor).

We can similarly prove Theorem 3.5 by leveraging Proposition A.1 instead of
Proposition 3.2.

###  F.6 Proof of Theorem 4.2

Based on the condition that $r_{\text{sub}}=\infty$, all the subgraphs contain
all the nodes in the entire graph.

Considering a subgraph of some node $i$, and let’s first assume that node $i$
is distinct to the geometric center $c$. Here, for simplicity, we denote node
$j$’s representation in subgraph $i$ using $h_{j}$ instead of $h_{ij}$ since
the context is clear.

  1. 1.

After 1 round of Vanilla DisGNN, for all $j\in[n]$, $h_{j}^{(1)}$ can derive
$d_{ij}$.

  2. 2.

After 2 rounds of Vanilla DisGNN, according to Proposition 3.2, for all
$j\in[n]$, $h_{j}^{(2)}$ can derive $d_{jc}$.

  3. 3.

After 3 rounds of Vanilla DisGNN, for all $j\in[n]$, $h_{j}^{(3)}$ can derive
$d_{ic}$.

At this point, for all nodes $j$, $h_{j}^{(3)}$ can derive $d_{ji}$, $d_{jc}$,
and $d_{ic}$, thus completing the APE related to $i$ and $c$. Then:

  1. 4.

At round 5, according to Theorem 3.4, the output of Vanilla DisGNN w.r.t. the
subgraph of node $i$, $s_{i}=f_{\text{output}}(\\{\\!\\!\\{h_{j}^{(5)}\mid
j\in[n]\\}\\!\\!\\})$, can derive the unique E(3)- and permutation-invariant
identifier of the geometric graph.

Note that there is still a problem with the above proof: node $i$ may coincide
with the geometric center, which does not satisfy the assumption that two
anchors are distinct in Theorem 3.4. For instance, consider a point cloud that
forms a sphere and has a spherical center. If we choose the spherical center
as node $i$, then there is only one anchor, which is node $i$ itself. However,
since GeoNGNN pools all the subgraph representations $s_{i}$ injectively in
the outer GNN and obtains the final output $s$, there must exist one node that
does not coincide with any global anchor. And since the outer GNN is
injective, $s$ can always derive the E(3)- and permutation-invariant
identifier of the geometric graph.

###  F.7 Proof of Theorem 4.3

####  F.7.1 DimeNet’s E(3)-Completeness

To begin, let us abstract the functions utilized in DimeNet. Fundamentally,
DimeNet employs edge representations, iteratively updating these
representations based on the neighbors of edges within a specified neighbor
cutoff. During aggregation, DimeNet incorporates angle information formed by
the center edge and its neighbor edges. Finally, all these edge
representations are aggregated to produce a graph-level output.

Let us formally state these procedures.

Initialization (DimeNet). In DimeNet, the initial representation $h_{ij}$ of
the edge $ij$ is initialized based on the tuple $(z_{i},z_{j},d_{ij})$, where
$z_{i}$ and $z_{j}$ are the features of nodes $i$ and $j$, and $d_{ij}$ is the
distance between these nodes:

$h_{ij}=f_{\text{init}}^{\text{DimeNet}}(z_{i},z_{j},d_{ij})$ (10)

Message Passing (DimeNet). The message passing in DimeNet updates the edge
representation $h_{ij}$ based on the features of neighboring edges and their
respective geometric information. It aggregates information from all neighbors
$k$ of node $i$:

$h_{ij}=f_{\text{update}}^{\text{DimeNet}}\left(h_{ij},\\{\\!\\!\\{(\theta_{kij},h_{ki},d_{ij})\mid
k\in N(i)\\}\\!\\!\\}\right)$

Note that $h_{ij}$ is initialized by fusing $d_{ij}$ and atomic information,
therefore we have: $h_{ij}\to d_{ij}$. And clearly
$d_{ij},d_{ik},d_{kj}\to\theta_{kij}$. Therefore, the above function is
expressively equivalent to:

$h_{ij}=f_{\text{update}}^{\text{DimeNet}}\left(h_{ij},\\{\\!\\!\\{(d_{kj},h_{ki})\mid
k\in N(i)\\}\\!\\!\\}\right)$

When the message passing cutoff of DimeNet is infinite, $N(i)=[n]$, giving the
final update function:

$h_{ij}=f_{\text{update}}^{\text{DimeNet}}\left(h_{ij},\\{\\!\\!\\{(h_{ki},d_{kj})\mid
k\in[n]\\}\\!\\!\\}\right)$ (11)

Output Pooling (DimeNet). Finally, DimeNet pools over all node pairs to obtain
the final representation $t$:

$t=f_{\text{output}}^{\text{DimeNet}}(\\{\\!\\!\\{\\{\\!\\!\\{h_{ij}\mid
i\in[n]\\}\\!\\!\\}\mid j\in[n]\\}\\!\\!\\})$ (12)

GeoNGNN, as a subtype of subgraph GNN, initializes and updates the node $j$’s
represnetation in node $i$’s subgraph based on its atomic number and its
distance to node $i$. Representing the node $j$’s representation in node $i$’s
subgraph as $h_{ij}$, then we can samely abstract its function forms.

Initialization (GeoNGNN). GeoNGNN initializes $h_{ij}$ based on node $j$’s
initial node feature and distance encoding w.r.t. $i$:

$h_{ij}=f_{\text{init}}^{\text{GeoNGNN}}(z_{j},d_{ij})$ (13)

Message Passing (GeoNGNN). GeoNGNN’s inner GNN iteratively updates $h_{ij}$
based on the following procedure:

$h_{ij}=f_{\text{update}}^{\text{GeoNGNN}}(h_{ij},\\{\\!\\!\\{(h_{ik},d_{kj})\mid
k\in[n]\\}\\!\\!\\})$ (14)

Note that $k$ iterates all nodes, because according to Theorem 4.2, the
complete version GeoNGNN has infinite subgraph size and message passing
cutoff.

Output Pooling (GeoNGNN). In the absence of an outer GNN, GeoNGNN produces the
scalar output by respectively aggregating all in-subgraph nodes’
representations as the subgraph representation, and then aggregating all
subgraphs’ representations:

$t=f_{\text{output}}^{\text{GeoNGNN}}(\\{\\!\\!\\{\\{\\!\\!\\{h_{ij}\mid
j\in[n]\\}\\!\\!\\}\mid i\in[n]\\}\\!\\!\\})$ (15)

Implementing GeoNGNN with DimeNet. Now we show how to use DimeNet to implement
GeoNGNN. Since GeoNGNN is E(3)-complete, it can be observed that if DimeNet
can successfully implement GeoNGNN, then DimeNet is also E(3)-complete.

Let us start by examining the initialization step. Note that
$f_{\text{init}}^{\text{DimeNet}}$ (Eq. 10) takes more information than
$f_{\text{init}}^{\text{GeoNGNN}}$ (Eq. 13) as input. Therefore, by learning a
function $f_{\text{init}}^{\text{DimeNet}}$ that simply disregards the $z_{i}$
term, $f_{\text{init}}^{\text{DimeNet}}$ can achieve the same function form as
$f_{\text{init}}^{\text{GeoNGNN}}$.

Next, we move on to the update (message passing) step. The only difference
between $f_{\text{update}}^{\text{DimeNet}}$ (Eq. 11) and
$f_{\text{update}}^{\text{GeoNGNN}}$ (Eq. 14) lies in their input
arrangements. Specifically, $f_{\text{update}}^{\text{DimeNet}}$ takes
$h_{ki},k\in[n]$ as part of input, while $f_{\text{update}}^{\text{GeoNGNN}}$
takes $h_{ik},k\in[n]$ as the corresponding part of input. This index swap can
be mathematically aligned: We can stack two DimeNet update layers to implement
one GeoNGNN update layer. The first DimeNet layer, starting from
$h_{ij}^{(t)}$, calculates $h_{ij}^{(t+\frac{1}{2})}$ to store the information
of $h_{ji}^{(t)}$, i.e., $h_{ij}^{(t+\frac{1}{2})}\to h_{ji}^{(t)}$. This is
feasible due to the property that in Eq.11, $(d_{jj},h_{ji})$ can be selected
uniquely from the multiset by $f_{\text{update}}^{\text{DimeNet}}$, as
$d_{kj}=0$ if and only if $k=j$. Subsequently, the second DimeNet layer swaps
the indices within the multiset, transforming
$\big{(}h_{ij}^{(t+\frac{1}{2})},\\{\\!\\!\\{(d_{kj},h_{ki}^{(t+\frac{1}{2})})\mid
k\in[n]\\}\\!\\!\\}\big{)}$ into
$\big{(}h_{ij}^{(t)},\\{\\!\\!\\{(d_{kj},h_{ik}^{(t)})\mid
k\in[n]\\}\\!\\!\\}\big{)}$. At this stage, the function form aligns with that
of $f_{\text{update}}^{\text{GeoNGNN}}$ (Eq.14).

Finally, we consider the output step. Similarly, the only distinction between
$f_{\text{output}}^{\text{DimeNet}}$ (Eq.12) and
$f_{\text{update}}^{\text{GeoNGNN}}$ (Eq.15) lies in the swapping of input
indices. By stacking one DimeNet update layer and one DimeNet output layer, we
can similarly implement the GeoNGNN output layer, as discussed in the prior
paragraph.

In conclusion, we have shown that DimeNet’s layers can be utilized to
implement GeoNGNN’s layers. By doing so, we establish that DimeNet is also
E(3)-complete with a constant number of layers.

####  F.7.2 E(3)-completeness of SphereNet

We aim to demonstrate the E(3)-completeness of SphereNet by illustrating that
SphereNet can implement DimeNet, which has already been established as
E(3)-complete in the preceding subsection. We begin by abstracting the layers
of SphereNet.

Initialization (SphereNet). Similar to DimeNet, SphereNet also initializes
edge representations by integrating atom properties and distance information:

$h_{ij}=f_{\text{init}}^{\text{SphereNet}}(z_{i},z_{j},d_{ij})$ (16)

Message Passing (SphereNet). During message passing, SphereNet aggregates
neighbor edge information into the center edge, while additionally considering
end nodes’ embeddings and spherical coordinates. Since we consider SphereNet∗,
which drops the relative azimuthal angle $\varphi_{k}$ of end node $k$, the
function form is highly similar to that of DimeNet:

$h_{ij}=f_{\text{update}}^{\text{SphereNet}}(h_{ij},v_{i},v_{j},\\{\\!\\!\\{(h_{ki},d_{ki},\theta_{kij})\mid
k\in[n]\\}\\!\\!\\})$

Note that the original SphereNet can only be more powerful than SphereNet∗.

Since $h_{ij}\to d_{ij}$, $(d_{ij},d_{ki},\theta_{kij})\to d_{kj}$, the above
function is equivalently expressive as

$h_{ij}=f_{\text{update}}^{\text{SphereNet}}(h_{ij},v_{i},v_{j},\\{\\!\\!\\{(h_{ki},d_{kj})\mid
k\in[n]\\}\\!\\!\\})$ (17)

Output (SphereNet). The output block of SphereNet first aggregates edge
representations into node representations as follows:

$v_{j}=f_{\text{node}}^{\text{SphereNet}}(\\{\\!\\!\\{h_{ij}\mid
i\in[n]\\}\\!\\!\\})$

Then, in order to calculate graph/global embedding, it further aggregates node
representations as follows:

$t=f_{\text{graph}}^{\text{SphereNet}}(\\{\\!\\!\\{v_{j}\mid
j\in[n]\\}\\!\\!\\})$

Therefore, the overall output function can be abstracted as:

$t=f_{\text{output}}^{\text{SphereNet}}(\\{\\!\\!\\{\\{\\!\\!\\{h_{ij}\mid
i\in[n]\\}\\!\\!\\}\mid j\in[n]\\}\\!\\!\\})$ (18)

Implementing DimeNet with SphereNet. Now we show how to use SphereNet to
implement DimeNet.

At the initialization step, $f_{\text{init}}^{\text{SphereNet}}$ (Eq. 16) and
$f_{\text{init}}^{\text{DimeNet}}$ (Eq. 10) exhibit exactly the same function
form.

At the update step, $f_{\text{update}}^{\text{SphereNet}}$ (Eq. 17) takes
strictly more information, i.e., the node representations, than
$f_{\text{update}}^{\text{DimeNet}}$ (Eq. 11). Therefore, by learning a
function $f_{\text{update}}^{\text{SphereNet}}$ that simply ignores node
representations $v_{i},v_{j}$, $f_{\text{update}}^{\text{SphereNet}}$ and
$f_{\text{update}}^{\text{DimeNet}}$ can share the same function form.

At the output step, $f_{\text{output}}^{\text{SphereNet}}$ (Eq. 18) and
$f_{\text{output}}^{\text{DimeNet}}$ (Eq. 12) share exactly the same function
form.

In conclusion, we have shown that SphereNet’s layers can be utilized to
implement DimeNet’s layers. By doing so, we establish that SphereNet is also
E(3)-complete with a constant number of layers.

####  F.7.3 E(3)-completeness of GemNet

GemNet(-Q) and DimeNet share the same initialization and output block. The
difference between them lies in the update block. Specifically, GemNet adopts
a three-hop message passing to incorporate higher-order geometric information,
dihedral angle. The update function can be abstracted as:

$h_{ij}=f_{\text{update}}^{\text{GemNet}}\big{(}h_{ij},\\{\\!\\!\\{(h_{ab},d_{ij},d_{bj},d_{ab},\theta_{ijb},\theta_{jba},\theta_{ijba})\mid
b\in[n],a\in[n]\\}\\!\\!\\}\big{)}$

Here, $\theta_{ijba}$ that has 4 subscripts represents the dihedral angle of
plane $ijb$ and $jba$. By learning a function that simply selects all $b=i$
from the multiset and ignores some terms (Note that this is feasible, since
$(h_{ab},d_{ij},\theta_{ijb},\theta_{ijba},d_{bj},\theta_{jba},d_{ab})\to(d_{ij},\theta_{ijb},d_{bj})\to
d_{bi}$, while only $b=i$ results in $d_{bi}=0$),
$f_{\text{update}}^{\text{GemNet}}$ can be simplified as follows:

$h_{ij}=f_{\text{update}}^{\text{GemNet}}\left(h_{ij},\\{\\!\\!\\{(\theta_{aij},h_{ai},d_{ij})\mid
a\in[n]\\}\\!\\!\\}\right)$ (19)

Now, the simplified $f_{\text{update}}^{\text{GemNet}}$ has the same form as
$f_{\text{update}}^{\text{DimeNet}}$ (Eq. 11), indicating that GemNet can
implement DimeNet, and therefore is also E(3)-complete.

###  F.8 Proof of Theorem D.2

We first note that the proof is highly similar to that in the proof of Theorem
4.2.

Let us consider a subgraph containing a node $i$, where we assume that $i$ is
distinct from the geometric center $c$. By imitating the proof of Theorem 4.2,
we can ascertain the following:

After three rounds of the Chiral Vanilla DisGNN (i.e., the Vanilla DisGNN that
incorporates the directed distance as a geometric representation as described
in Definition D.1), node representations $h_{j}^{(3)}$ for any node $j$ can
encode the directed distances $d_{ji}$, $d_{jc}$, and $d_{ic}$. This enables
the completion of the APE related to nodes $i$ and $c$.

Next, we employ a modified version of the proof from Theorem 3.4 to
demonstrate that with an additional two rounds of the Chiral Vanilla DisGNN,
we can derive the SE(3)- and permutation-invariant identifier of the geometric
graph $G$.

In the proof of Theorem 3.4, we first search across all the nodes to find two
nodes $a$ and $b$ that forms the minimal dihedral angles $\theta(aic,bic)$,
and then identifies the coordinates of $a,b,i,c$ up to E(3)-transformation
from the all-pair distances $D=\\{(m,n,d_{mn})\mid m,n\in\\{a,b,i,c\\}\\}$.
However, since Chiral Vanilla DisGNN embeds the geometry using directed
distance, we now have $D_{i}=\\{(m,n,d_{i,mn})\mid m,n\in\\{a,b,i,c\\}\\}$
instead. We are now able to identify the coordinates of $a,b,i,c$ up to
SE(3)-transformation from $D_{i}$ in the following way:

  1. 1.

Fix $x_{i}=(0,0,0)$.

  2. 2.

Fix $x_{c}=(d_{ic},0,0)$.

  3. 3.

Fix $x_{a}$ in plane $xOy+$ and calculate its coordinates using
$d_{ia},d_{ca}$.

  4. 4.

Calculate the coordinates of $x_{b}$ using $d_{ib},d_{cb},d_{ab}$, and
determine whether $b$ is on $z+$ side or $z-$ side using the signal embedded
in $d_{i,ab}$.

Note that the orientation relevant to SE(3) transformation is already
determined at this stage. We proceed with the remaining steps of the proof
outlined in Theorem 3.4 and reconstruct the whole geometry in a deterministic
way based on the known 4-tuple $abic$, and therefore reconstruct the whole
geometry up to permutation and SE(3)-transformation.

Similarly, note that such subgraphs $i$, where $i$ is distinct from the
geometric center $c$, always exist as GeoNGNN-C traverses all node subgraphs.
Hence, we have established the SE(3)-Completeness of GeoNGNN-C.