On the Completeness of Invariant Geometric Deep Learning Models

## Abstract

Abstract Invariant models, one important class of geometric deep learning models, are capable of generating meaningful geometric representations by leveraging informative geometric features in point clouds. 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 a wide range of invariant models. We first rigorously bound the expressiveness of the most classic invariant model, message-passing neural networks incorporating distance (DisGNN), restricting its unidentifiable cases to be only highly symmetric point clouds. We then show that GeoNGNN, the geometric counterpart of one of the simplest subgraph graph neural networks (subgraph GNNs), can effectively break these corner cases’ symmetry and thus achieve E(3)-completeness. By leveraging GeoNGNN as a theoretical tool, we further prove that: 1) most subgraph GNNs developed in traditional graph learning can be seamlessly extended to geometric scenarios with E(3)-completeness; 2) DimeNet, GemNet and SphereNet, three well-established invariant models, are also all capable of achieving E(3)-completeness. Our theoretical results fill the gap in the theoretical power of invariant models, contributing to a rigorous and comprehensive understanding of their capabilities. We also empirically evaluated GeoNGNN, the simplest model within the large E(3)-complete family we established, which achieves competitive results to models relying on high-order invariant/equivariant representations on molecule-relevant tasks.

## 1 Introduction

Learning geometric structural information from 3D point clouds constitutes a fundamental requirement for various real-world applications, including molecular property prediction, physical simulation, and point cloud classification/segmentation [, , , ].

In the context of designing geometric models for point clouds, 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 Euclidean transformation.

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) [], a representative class of Graph Neural Networks (GNNs), learn permutation symmetric functions over graphs. However, it has been shown that such functions are not universal [, ], leading to the development of more expressive GNN frameworks [, , ]. Similar challenges arise in the geometric setting, where models must additionally respect the Euclidean symmetry, and thus achieving geometric universality (E(3)-completeness) becomes a non-trivial task as well.

Regarding this, previous studies [, , ] have proposed complete invariants and continuous metrics for their comparison. However, these constructions do not directly correspond to neural function forms, thereby restricting their applications in downstream tasks. In neural-network context, some works [, , , ] proved their models can achieve geometric completeness by excluding some symmetric, difficult-to-deal cases (such as assuming non-degenerate frames). However, these cases are known to significantly impact downstream continuous function learning [, ]. A series of recent works [, , , ] proposed geometric models based on 2FWL methods [], which initializes and updates node-pair representations iteratively, and proved their completeness. However, these models significantly diverge from the node-based MPNN paradigm, and whether a wide range of invariant models, most with weaker aggregation schemes, are also complete remains unclear. For more discussion of related works, we refer the readers to Appendix A.

In this work, we systematically investigate the expressiveness of a wide range of invariant models. We begin by revisiting 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 DisGNN powerful enough? We establish that DisGNN is a nearly-E(3)-complete model by restricting all its unidentifiable cases into a 0-measure subspace which only contains well-defined highly-symmetric point clouds. Our results extend the findings of previous works that solely concentrated on individual hand-crafted counterexamples illustrating the incompleteness of DisGNN [, , ], and study that provided a strictly coarser characterization of DisGNN’s expressiveness [].

We then show that GeoNGNN, the geometric counterpart of NGNN [] (one simplest subgraph GNN), can effectively break all these unidentifiable cases’ symmetry through node marking, thereby achieving E(3)-completeness. Leveraging GeoNGNN as a theoretical tool, we proceed to establish the E(3)-completeness of a wide range of invariant models by showcasing their ability to implement [] GeoNGNN. Specifically, we systematically define the geometric counterparts of all subgraph GNNs within Zhang et al. []’s framework by generalizing their local operations to incorporate geometric information. We then prove that all of these subgraph GNNs are E(3)-complete. Furthermore, we establish that three well-established invariant geometric models, DimeNet [], SphereNet [] and GemNet [], are also all capable of achieving E(3)-completeness.

These established E(3)-complete models, except for GemNet [], are either known to be strictly weaker than 2FWL algorithm [] in traditional graph learning or utilize less informative aggregation schemes than 2FWL-like geometric models [, , , ]. Nevertheless, our investigation reveals that in geometric settings, these models are equally E(3)-complete. These surprising findings can deepen our understanding of the power of invariant models, while also suggesting that the bottleneck of invariant models may lie in generalization instead of expressiveness. As a side effect, by generalizing subgraph GNNs to the geometric setting, we greatly enlarge the design space of geometric deep learning models, which we hope could inspire future, more powerful model designs.

## 2 Preliminary

### 2.1 Notations and definitions

We study the expressiveness of invariant models on unlabeled point clouds with finite $n$ nodes(^1^11Notice that unlabeled point clouds are the most complicated case for geometric expressiveness [, ], surpassing the complexity posed by settings where point clouds possess initial features like molecules. We consider $P$ with more than 1 point; otherwise, the cases are trivial.), notated as $P\in\mathbb{R}^{n\times 3}$. We use $p_{i}$ to represent the $i$-th nodes’ coordinates in $P$. We use $\{\}$ to denote sets and use $\{\!\!\{\}\!\!\}$ to denote multisets. We use $[n]$ to denote the set $\{1,2,...,n\}$. Euclidean distance between node $i$ and $j$ is represented by $d_{ij}$.

Two point clouds are isomorphic if they are equivalent under permutation of nodes and Euclidean isometry (including rotation, translation and reflection). Invariant models explored in this work are permutation- and E(3)-invariant, meaning that they embed isomorphic point clouds into the same representation $s\in\mathbb{R}^{k}$.

We say that a model can distinguish a pair of non-isomorphic point clouds if their corresponding output $s_{1}$ and $s_{2}$ are different, and say that a model is (E(3)-)complete if it can distinguish all pairs of finite-size non-isomorphic point clouds. Since distinguishing point clouds with different node numbers is trivial, we only consider distinguishing abilities for clouds equally with finite $n$ nodes.

Instead of researching models’ ability to distinguish pairs of point clouds, we take a step further for their ability to identify each single point cloud: A model can identify a point cloud $P\in\mathbb{R}^{n\times 3}$, if for an arbitrary point cloud $P^{\prime}\in\mathbb{R}^{n\times 3}$ that is non-isomorphic to $P$, the model can always distinguish them. "Identify" allows us to understand the expressiveness of models in a finer-grained manner, since by definition, each "identify" results in infinite pairs of "distinguish". It is also obvious to see that identifying all point clouds implies E(3)-completeness.

Finally, we note that all the invariant models are parametric. However, Hornik et al. [], Dym & Gortler [], Amir et al. [] showed that there exist neural function forms and parameters ensuring the injectiveness of all multiset functions within polynomial complexity, leading to lossless encoding. Under such injective constructions, neural networks can always simulate their corresponding color-refinement algorithms [, , ] which represents their maximal expressiveness. We thus directly discuss expressiveness in neural-network contexts, which implicitly assumes the injectiveness of the models. Moreover, since models are highly parametric, the completeness directly implies their universal approximation ability for all E(3)- and permutation-invariant functions [], giving them great theoretical significance in practical applications.

### 2.2 DisGNN

To leverage the rich geometric information present in point clouds, a straightforward approach is to model the point cloud as a distance graph, where edges are present between nodes if their Euclidean distance is below a certain cutoff $r_{\text{cutoff}}$, and edge weights are Euclidean distance $d_{ij}$. Then, an MPNN is applied to it. We call models with such framework as DisGNN, and SchNet [] is a representative of such works.

To be specific, DisGNN models first embed nodes based on their initial node features $X\in\mathbb{R}^{n\times d}$ (if there exists), such as atomic numbers, obtaining $h_{i}^{(0)}$ for node $i$. They then perform message passing according to the following equation iteratively:

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

where $h_{i}^{(l)}$ represents the node embedding for node $i$ at layer $l$, $\mathcal{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}^{L}\mid i\in[n]\}\!\!\})$, where $L$ is the total number of layers and $n$ is the total number of nodes.

In the theoretical analysis for DisGNN (Section 3), we assume fully-connected distance graph modeling for point clouds, i.e., $\mathcal{N}(i)$ is $[n]$ by default, and sufficient iterations until convergence. This ensures maximal geometric expressiveness of DisGNN and aligns with existing works [, , ].

## 3 How powerful is DisGNN?

In Pozdnyakov & Ceriotti [], Li et al. [], researchers have carefully constructed pairs of symmetric point clouds that 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 point clouds that DisGNN cannot identify share in common? Only after theoretically characterizing these corner cases can we describe and bound the expressiveness of DisGNN in a rigorous way, and then design more powerful geometric models accordingly by “solving” these corner cases.

Naively, to determine whether a point cloud $P$ can be identified by DisGNN requires iterating through all other point clouds $P^{\prime}$ within the entire cloud space $\mathbb{R}^{n\times 3}$ according to its definition. Here, we propose a simple sufficient condition for a point cloud to be identifiable by DisGNN, which focuses solely on $P$. To achieve this, we first rigorously define the concept of $\mathcal{A}$-symmetry.

###### Definition 3.1 .

($\mathcal{A}$-symmetry) Given a point cloud $P\in\mathbb{R}^{n\times 3}$, let $\mathcal{A}$ be a permutation-equivariant and E(3)-invariant algorithm taking $P$ as input and produces node-level features $X^{\mathcal{A}}=\mathcal{A}(P)\in\mathbb{R}^{n\times d}$ (we use $x^{\mathcal{A}}_{i}\in\mathbb{R}^{d}$ to denote the $i$-th nodes’ feature). We define $\mathcal{A}$ center set of $P$ as $\mathcal{A}^{\text{set}}(P)=\{\frac{\sum_{i\in[n]}m(x^{\mathcal{A}}_{i})p_{i}}
{\sum_{i\in[n]}m(x^{\mathcal{A}}_{i})}\mid m:\mathbb{R}^{d}\to\mathbb{R}\}$, where $m$ represents a "mass" function that maps different features to different "masses"(^2^22Notice that the geometric center of $P$ is always present in $\mathcal{A}^{\text{set}}(P)$ by setting $m$ as a constant function.). Hence, $\mathcal{A}^{\text{set}}(P)$ represents the collection of "barycenters" under different masses. If $|\mathcal{A}^{\text{set}}(P)|=1$, then we say $P$ is $\mathcal{A}$-symmetric; otherwise, we say $P$ is $\mathcal{A}$-unsymmetric.

For example, we can consider $\mathcal{A}$ as the center distance encoding function $\mathcal{C}$, which computes the distance from each node to the geometric center as the node feature. A $\mathcal{C}$-unsymmetric case is shown in Figure 1(a).

Figure: Figure 1: (a) A $\mathcal{C}$-unsymmetric point cloud. The blue small node represents the geometric center, and each green node represents an element in $\mathcal{C}^{\text{set}}(P)$. The large nodes constitute the point cloud, with different node colors denoting different node features. (b) Illustration of the relations among different subspaces of the point cloud. $\mathcal{A}$-sym parts encompass all $\mathcal{A}$-symmetric graphs. Each subspace has a measure of 0 0 and strictly contains their sub-parts (proper subset relation).
Refer to caption: x1.png

Obviously, the cardinality of $\mathcal{A}^{\text{set}}(P)$ is solely dependent on the partition of node features $\mathcal{A}(P)$ and is independent of the specific feature values. Another algorithm, $\mathcal{A}$, could be $\mathcal{D}$, which applies DisGNN on point clouds until the partition of node features stabilizes. Notably, earlier studies by Delle Rose et al. [], Li et al. [] have demonstrated that $\mathcal{D}$ ensures a node feature partition that is no coarser compared to $\mathcal{C}$. As a consequence, $\mathcal{D}$-symmetry always implies $\mathcal{C}$-symmetry. However, determining $\mathcal{D}$-symmetry of a point cloud will need higher costs. We now present the primary theorem demonstrating that all such unsymmetric point clouds can be identified by DisGNN.

###### Theorem 3.2 .

(Unsymmetric point clouds are identifiable) Let $\mathcal{A}$ be either center distance encoding $\mathcal{C}$ or DisGNN encoding $\mathcal{D}$. Then, given an arbitrary point cloud $P\in\mathbb{R}^{n\times 3}$, $P$ is not $\mathcal{A}$-symmetric $\Rightarrow$ $P$ can be identified by DisGNN.

###### Definition 3.1 .

###### Theorem 3.2 .

##### Key idea

Given a point cloud $P$, when it has two global-level distinct anchors, such as geometric center or other centers that can be determined in a permutation-invariant and E(3)-equivariant way, DisGNN has the potential to learn triangular distance encoding for each node $i$ w.r.t. $i$ and these two global anchors, and produces complete representation for $P$ by leveraging such encoding information (Lemma E.6). For $\mathcal{C}$- or $\mathcal{D}$-unsymmetric point clouds, their center sets $\mathcal{C}^{\text{set}}(P)$ or $\mathcal{D}^{\text{set}}(P)$ have more than 1 element, within which any pair of distinct centers can be utilized by DisGNN for such encoding (Lemma E.4), thereby facilitating DisGNN to fully represent and identify $P$.

We provide rigorous proof in Appendix E.2 and highly encourage readers to refer to it, where we show the superior global geometric learning ability of DisGNN and can inspire the development of new complete model designs in the triangular distance encoding perspective, as exemplified by GeoNGNN proposed in the following section.

Notice that while in Theorem 3.2 DisGNN is also applied to determine $\mathcal{D}$-symmetry, the theorem indicates that to determine the identifiability of $P$, a single execution of DisGNN on $P$ suffices, sparing the need to iterate through all possible $P^{\prime}\in\mathbb{R}^{n\times 3}$. The theorem significantly constrains the unidentifiable space of DisGNN to a notably restricted subspace, demonstrating that, though with extremely simple and naive design, DisGNN is nearly E(3)-complete.
In Figure 1(b), we depict the containment relation between these well-defined subspaces. We notice that all the relations are proper subset relations, which is proved in Proposition B.1. In Appendix B, we also show the following theoretical/experimental evidence, demonstrating how restricted these subspaces are:

- •
We rigorously prove that the measure of $\mathcal{C}$- and $\mathcal{D}$-symmetric clouds, as well as the unidentifiable clouds’ measure, is $\mathbf{0}$ within the whole space $\mathbb{R}^{n\times 3}$ (Theorem B.4).
- •
Realizing that real-life point clouds are all sightly noisy, we investigate the proportion of $\mathcal{C}$- and $\mathcal{D}$-symmetric clouds in real-world datasets including QM9 and ModelNet40, with pre-defined tolerance errors (allowing them to be not exactly symmetric). We show that even with the largest tolerance, the proportion of unidentifiable cases amounts to less than $\mathbf{0.1}\%$ (Appendix B.3).

Finally, we note that a recent study [] also indicates the near-completeness of DisGNN, by showing that it can distinguish arbitrary pairs of point clouds from an unsymmetric point cloud $\mathbb{R}^{n\times 3}_{\text{distinct}}$. Nevertheless, our findings represent a significant advancement by introducing two strictly larger unsymmetric subsets and employing the concept of "identify" instead of "pair-wise distinguish". This provides a much finer characterization of the near completeness of DisGNN. Please refer to Appendix B for a detailed comparison.

## 4 On the completeness of invariant geometric models

In this section, we move on to demonstrate and prove the E(3)-completeness of a broad range of invariant models that leverage more geometric features or more complicated aggregation schemes than DisGNN. These models can effectively identify all those highly-symmetric point clouds that DisGNN can not. We first introduce a new simple invariant model design, which can precisely break such symmetry and achieve completeness. Consequently, we show how this new design serves as a theoretical tool for proving a wide range of invariant models’ expressiveness.

### 4.1 GeoNGNN: breaking symmetry through node marking

According to Theorem 3.2 (along with the lemmas emphasized in its key idea), the essential factor in identifying a point cloud by DisGNN is the existence of two distinct anchors. Although every point cloud inherently possesses one, i.e., the geometric center, the other may not exist in some highly symmetric cases, such as a sphere. This hinders DisGNN from achieving completeness. In this subsection, we show that GeoNGNN, the geometric counterpart of Nested GNN (NGNN) [], can fill in this last piece of the puzzle by applying DisGNN on point clouds with an additionally marked node, which breaks the symmetry and exactly acts as the other anchor.

NGNN [] is a subgraph GNN first proposed in traditional graph learning. It performs a two-level GNN on a given graph, where 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, and the second level, referred to as the outer GNN, runs on the original graph to obtain the final node and graph representations. We now extend NGNN to geometric settings as follows:

###### Definition 4.1 .

(GeoNGNN) GeoNGNN is the geometric counterpart of NGNN [], which takes point clouds $P\in\mathbb{R}^{n\times 3}$ (potentially with node features $X\in\mathbb{R}^{n\times d}$, such as atomic numbers) as input, treats it as a distance graph with cutoff $r_{\text{cutoff}}$, and

- •
Both the inner and outer GNN adopt DisGNN, with $N_{\text{in}}$ and $N_{\text{out}}$ layers each.
- •
The ego subgraph of each node $i$ contains all nodes and edges within Euclidean distance cutoff $r_{\text{sub}}$, with node $i$ being explicitly marked.

Overall, GeoNGNN adopts the same framework as 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 model, DisGNN. We are now ready to prove the completeness of GeoNGNN:

###### Theorem 4.2 .

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

- •
$N_{\text{in}}>=5$ and $N_{\text{out}}>=0$ (where 0 0 indicates that the outer GNN only performs final pooling).
- •
The distance graph is fully-connected ($r_{\text{cutoff}}=+\infty$).
- •
All subgraphs are the original graph ($r_{\text{sub}}=+\infty$).

###### Definition 4.1 .

###### Theorem 4.2 .

##### Key idea

Given an arbitrary point cloud $P$, consider a specific node $i$ within it that differs from the geometric center. As node $i$ is explicitly marked within its own subgraph, there are now two anchors in this subgraph, namely node $i$ and the geometric center, that facilitate triangular distance encoding by DisGNN. Consequently, DisGNN can fully represent and identify $P$ through the representation of node $i$’s subgraph, as underscored in the key idea of Theorem 3.2. Notice that in a point cloud with more than two nodes, a node that is distinct from the geometric center always exists, and through the outer pooling, overall completeness and permutation invariance are guaranteed.

While Theorem 4.2 establishes that infinite subgraph radius and distance cutoff guarantee completeness over all point clouds, in Appendix C.2 we show that finite values also lead to boosted expressiveness compared to DisGNN. And we notice that the conditions specified in Theorem 4.2 ultimately result in polynomial-time complexity w.r.t. the size of the point cloud even when considering the complexity involved in obtaining intermediate injective functions, which aligns with prior studies [, , , , ]. The detailed complexity analysis is provided in Appendix C.1.

### 4.2 Completeness of geometric subgraph GNNs

GeoNGNN provides a simple approach to extend traditional subgraph GNNs to geometric scenarios with remarkable geometric expressiveness. Indeed, the realm of traditional graph learning literature contains a multitude of subgraph GNNs such as DSS-GNN [], GNN-AK [], OSAN [] and so on [, ]. Extending these models to geometric settings can significantly enlarge the design space of geometric models, and potentially introduce valuable inductive biases. In this section, we take a pioneering step to do this, subsequently establishing the geometric completeness of all these models.

We first formally define general geometric subgraph GNN, which represents a large family of geometric models. The definition extends the general subgraph GNNs defined in the seminal work [], which operate on unweighted graphs, to geometric scenarios wherein they operate on point clouds. We briefly introduce modifications here, while self-contained definitions can be found in Appendix D.

###### Definition 4.3 .

(General geometric subgraph GNN, informal)
A general geometric subgraph GNN takes point clouds $P\in\mathbb{R}^{n\times 3}$ (potentially with node features $X\in\mathbb{R}^{n\times d}$, such as atomic numbers) as input, treats it as a distance graph with cutoff $r_{\text{cutoff}}$, and:

- •
It employs node marking with $r_{\text{sub}}$-size ego subgraph as the subgraph generation policy.
- •
It stacks multiple geometric subgraph GNN layers, each of which has the form of Definition 2.1 in [], with the only modifications on local operations: The two local operations for updating $h_{uv}$ (node $v$’s representation in $u$’s subgraph) additionally integrate distance information, which are represented by $\{\!\!\{\big{(}h_{uw},d_{vw}\big{)}\mid w\in\mathcal{N}(v)\}\!\!\}$ and $\{\!\!\{\big{(}h_{wv},d_{uw}\big{)}\mid w\in\mathcal{N}(u)\}\!\!\}$.
- •
It adopts vertex-subgraph or subgraph-vertex pooling schemes [] to obtain graph representation.

It is noteworthy that GeoNGNN (without outer layers) represents a particular instance of general geometric subgraph GNNs, focusing solely on intra-subgraph message propagation. Beyond this scope, general geometric subgraph GNNs have the capability to engage in inter-subgraph message passing in diverse manners and adopt different pooling schemes. Now, we show that the whole family, with at least one local aggregation, is complete under exactly the same conditions as GeoNGNN.

###### Theorem 4.4 .

(Completeness for general geometric subgraph GNNs) Under the conditions specified in Theorem 4.2, all general geometric subgraph GNNs in Definition 4.3 with at least one local aggregation are E(3)-complete.

###### Definition 4.3 .

###### Theorem 4.4 .

##### Key idea

It can be shown that any type of general geometric subgraph GNNs, which could employ any combination of aggregation and pooling schemes, can implement [] GeoNGNN, which is established as an E(3)-complete model in Theorem 4.2. As a consequence, any general geometric subgraph GNN can also achieve E(3)-completeness under the same conditions as GeoNGNN.

Concerning prior research on traditional subgraph GNNs [, , , , ], their geometric counterparts can be defined correspondingly by substituting all local aggregation schemes with distance-aware counterparts. We denote their geometric counterpart by prefixing Geo to their original names, for instance, GeoSUN []. Consequently, it can be established that some of them precisely fall into the general definition 4.3, such as GeoOSAN [], and for the others such as GeoGNN-AK [] and GeoSUN [], while even though they do not exactly match the general definition, they can still implement GeoNGNN, thereby exhibiting E(3)-completeness (Theorem D.2). Please refer to Appendix D.2 for details about all of these.

We note that all subgraph GNNs discussed in this section have been proven to be strictly weaker than 2FWL [] in traditional graph learning context []. Specifically, there exist pairs of unweighted graphs that can be distinguished by 2FWL but remain indistinguishable by these subgraph GNNs. Moreover, these subgraph GNNs themselves establish a strict expressiveness hierarchy []. Interestingly, our findings reveal that all of these discrepancies diminish when these models are extended to geometric scenarios with point clouds by leveraging distance graphs. This phenomenon could be attributed to the low-rank nature of distance graphs, whose intrinsic dimension is less than the point cloud space dimension $3n$ rather than equals to their ambient dimension $n^{2}$.

### 4.3 Completeness of well-established invariant models

Based on the completeness of GeoNGNN, we move on to establish the E(3)-completeness of several well-established invariant models, including DimeNet [], GemNet [] and SphereNet []. These models do not exactly learn on subgraphs, however, can still be mathematically aligned with GeoNGNN. Descriptions of these models and proofs can be found in Appendix E.5.

###### Theorem 4.5 .

(E(3)-Completeness of DimeNet, SphereNet, GemNet) When the following conditions are met, DimeNet, SphereNet(^3^33Here 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.

- •
The aggregation layer number is larger than some constant $C$, which is irrelevant to the node number.
- •
They initialize and update all edge representations, i.e., $r_{\text{embed}}=+\infty$.
- •
They interact with all neighbors, i.e., $r_{\text{int}}=+\infty$.(^4^44In DimeNet and GemNet, nodes $i$ or $j$ are excluded when aggregating neighbors for edge $ij$. The condition requires the inclusion of these end nodes.).

###### Theorem 4.5 .

##### Key idea

The key insight underlying is that all these models track edge representations ($h_{ij}^{\text{edge}}$ for edge $(i,j)$), which can be mathematically aligned with the node-subgraph representations tracked in GeoNGNN ($h_{ij}^{\text{subg}}$ for node $i$ in subgraph $j$). Moreover, the additionally incorporated features, such as angles, can all be equivalently expressed by multiple distances. Consequently, these three models can all implement GeoNGNN, and thereby achieving completeness.

Notice that DimeNet is a relatively simpler invariant model that aggregates neighbor information in a weaker manner compared to existing 2FWL-like complete geometric models such as 2F-DisGNN []. Specifically, when updating $h_{ij}$, DimeNet can be equivalently considered as aggregating $(h_{ki},d_{kj})$ for a specific neighbor $k$, while 2F-DisGNN aggregates $(h_{ik},h_{kj})$. The latter incorporates a more informative hidden representation $h_{kj}$, which is essential in the proof of 2F-DisGNN’s completeness [, ], instead of $d_{kj}$ in the former. Nevertheless, our findings for the first time show that these models are equally E(3)-complete under similar conditions (i.e., fully connected distance graphs). Consequently, future developments like GemNet, which integrate higher-order geometry, could be unnecessary in terms of boosting theoretical expressiveness under such conditions.

In summary of this entire section, we have characterized a broad collection of E(3)-complete invariant models under the similar conditions. However, it is essential to acknowledge that while two models may exhibit equivalence in terms of completeness, they may encompass distinct inductive biases that could lead to differing levels of generalization capability and experimental performance, as exemplified in Li et al. [] and in our experiment sections.

## 5 Experiments

In this section, we additionally evaluate GeoNGNN, the simplest complete model within the large family we established, to assess its practical performance. We specifically focus on its capacity to effectively distinguish symmetric point clouds in practical scenarios where numerical precision could potentially impact the outcomes despite the theoretical assurance of completeness. Furthermore, we also explore the performance of GeoNGNN in molecule-relevant downstream tasks, where the capability for geometric learning is essential for accurately approximating target functions.

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 [], NequIP [] and MACE []. 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 [], GemNet [] and 2-F-DisGNN []. Note that all of these models can capture high-order geometry, enabling them to achieve state-of-the-art performance on downstream tasks. Given that GeoNGNN can be regarded as the subgraph-enhanced version of DisGNN, we also implement and evaluate DisGNN, which includes more complicated residual layers than its special case SchNet [], as a baseline to assess the direct improvement achieved through subgraph representation. Detailed experimental settings are provided in Appendix G.

**Table 1: MAE loss on revised MD17. Energy (E) in kcal/mol, force (F) in kcal/mol/Å. The best and the second best results are shown in bold and \ulunderline. We color the cell if GeoNGNN outperforms Vanilla DisGNN. The average rank is the average of the rank of each row.**
|  |  | Equivariant models | Invariant models |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Molecule | Target | PaiNN | NequIP | MACE | DimeNet | GemNet | 2F-Dis. | Vanilla DisGNN | GeoNGNN |
|  | E | 0.1591 | 0.0530 | 0.0507 | 0.1321 | - | 0.0465 | 0.1565 | \ul0.0502 |
| Aspirin | F | 0.3713 | 0.1891 | \ul0.1522 | 0.3549 | 0.2191 | 0.1515 | 0.4855 | 0.1720 |
|  | E | - | 0.0161 | \ul0.0277 | 0.1063 | - | 0.0315 | 0.2312 | 0.0315 |
| Azobenzene | F | - | 0.0669 | \ul0.0692 | 0.2174 | - | 0.1121 | 0.5050 | 0.1157 |
|  | E | - | 0.0009 | 0.0092 | 0.0061 | - | \ul0.0013 | 0.0308 | 0.0014 |
| Benzene | F | - | 0.0069 | \ul0.0069 | 0.0170 | 0.0115 | 0.0085 | 0.2209 | 0.0065 |
|  | E | 0.0623 | 0.0092 | 0.0092 | 0.0345 | - | 0.0065 | 0.0117 | \ul0.0074 |
| Ethanol | F | 0.2306 | 0.0646 | 0.0484 | 0.1859 | 0.0830 | 0.0379 | 0.0774 | \ul0.0482 |
|  | E | 0.0899 | 0.0184 | 0.0184 | 0.0507 | - | 0.0129 | 0.2814 | \ul0.0143 |
| Malonaldehyde | F | 0.3182 | 0.1176 | 0.0945 | 0.2743 | 0.1522 | 0.0782 | 0.1661 | \ul0.0875 |
|  | E | 0.1176 | 0.0208 | 0.0115 | 0.0445 | - | \ul0.0103 | 0.1269 | 0.0069 |
| Naphthalene | F | 0.0830 | 0.0300 | \ul0.0369 | 0.1105 | 0.0438 | 0.0478 | 0.4144 | 0.0377 |
|  | E | - | 0.0323 | 0.0300 | 0.1176 | - | \ul0.0310 | 0.1534 | 0.0352 |
| Paracetamol | F | - | 0.1361 | 0.1107 | 0.3028 | - | \ul0.1178 | 0.4698 | 0.1385 |
|  | E | 0.1130 | 0.0161 | 0.0208 | 0.0590 | - | 0.0174 | 0.0791 | \ul0.0168 |
| Salicylic acid | F | 0.2099 | 0.0922 | 0.0715 | 0.2428 | 0.1222 | \ul0.0860 | 0.3481 | 0.0881 |
|  | E | 0.0969 | 0.0069 | 0.0115 | 0.0228 | - | 0.0051 | 0.0918 | \ul0.0069 |
| Toluene | F | 0.1015 | 0.0369 | \ul0.0346 | 0.1085 | 0.0507 | 0.0284 | 0.3070 | 0.0375 |
|  | E | 0.1038 | 0.0092 | 0.0115 | 0.0338 | - | 0.0139 | 0.0363 | \ul0.0096 |
| Uracil | F | 0.1407 | 0.0715 | 0.0484 | 0.1634 | 0.0876 | 0.0828 | 0.1973 | \ul0.0577 |
| AVG RANK | 6.71 | 2.80 | 2.50 | 5.70 | 5.00 | 2.25 | 6.55 | 2.55 |  |

### 5.1 Separation power: synthetic counterexamples

We construct a geometric expressiveness dataset based on counterexamples proposed by Li et al. [] 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 point clouds (all of which are $\mathcal{D}$-symmetric described in Section 3) that are non-isomorphic but indistinguishable by 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% |

Results shown in Table 2 validate our theoretical findings. SchNet and DisGNN both fail to distinguish any counterexample, as expected. Conversely, the remaining models all effectively distinguish all pairs, which suggests that models integrating higher-order geometry or advanced aggregation strategies all possess the discrimination ability for existing carefully designed symmetric structures [] despite potential numerical precision problems. We notice that we cannot conclude that PaiNN and MACE are theoretically complete from these results, and whether they are, with a finite degree of tensor order, still remains unclear and needs future investigation.

### 5.2 Molecule structure learning: revised MD17

We further evaluate GeoNGNN on the rMD17 dataset [], which poses a substantial challenge to models’ geometric learning ability. This dataset encompasses trajectories from molecular dynamics simulations of several small molecules, and the objective is to predict the energy and atomic forces of a given molecule conformation, which contains all atoms’ positions and atomic numbers. The comprehensive results and comparison is shown in Table 1.

There are several important observations: 1) GeoNGNN exhibits substantial improvements over DisGNN. The ratio of the loss for GeoNGNN to that of DisGNN averages 1:8.6 and reaches a maximum of 1:34.2, validating the significance of capturing subgraph representations. 2) Though equally being E(3)-complete, DimeNet and GemNet show worse performance than GeoNGNN. This finding suggests that different model designs can exhibit quite different inductive biases, while learning more refined subgraph representations may be superior to directional message passing in certain molecule-relevant tasks. Although GeoNGNN demonstrates comparatively lower performance than another complete model 2F-DisGNN [], in the subsequent subsection, we will show that on large point clouds (MD22 dataset) where 2F-DisGNN can hardly be applied due to computational infeasibility, GeoNGNN can still exhibit good performance while ensuring faster speed than existing SOTA models. 3) GeoNGNN shows competitive and even better performance in comparison to other well-designed state-of-the-art models. However, it does not consistently achieve SOTA performance, which may be due to its simple design, leveraging distance only, and the weak base GNN it adopts.

### 5.3 Supplementary experiments

In Appendix F, we show further evaluations of GeoNGNN, including: 1) Evaluation on MD22 [], a dataset containing much larger molecules than MD17. Results show competitive performance and faster speed of GeoNGNN w.r.t. SOTA models such as MACE [] and Equiformer []. 2) Evaluation on 3BPA dataset [], where test sets comprise out-of-domain data, thereby emphasizing the significance of generalization ability. GeoNGNN shows competitive performance compared to Allegro [], a well-designed equivariant geometric model. 3) Effect of subgraph size $r_{\text{sub}}$. Results imply that there exists a conflict between theoretical expressiveness and experimental performance, and striking a balance between them is important.

In Appendix H, we also defined, proved and evaluated GeoNGNN-C, an SE(3)-complete variant of GeoNGNN, designed by simply replacing the undirected distances in GeoNGNN with directed ones. GeoNGNN-C shows competitive or even better performance than SOTA models, such as ChiENN [], on chirality-relevant datasets, even though it is not specifically designed for those tasks where additional symmetry, such as invariance under conformer-level transformation, could provide better inductive bias.

## 6 Conclusion and limitation

##### Conclusion

In this study, we thoroughly analyze a wide range of invariant models’ theoretical expressiveness. Specifically, we rigorously characterize the expressiveness of DisGNN, showcasing that all its unidentifiable cases exhibit $\mathcal{D}$-symmetry and have a measure of 0. We then establish a large family of E(3)-complete models, which encompasses GeoNGNN, geometric subgraph GNNs, as well as three established models - DimeNet, GemNet, and SphereNet. This contributes significantly to a comprehensive understanding of invariant geometric models. Moreover, the newly introduced geometric subgraph GNNs notably enlarge the design space of expressive geometric models. Experiments demonstrate the competitive performance of GeoNGNN, the simplest complete model, in comparison to geometric models utilizing high-order invariant and equivariant representations. Our experimental findings also suggest that models of equal completeness could exhibit distinct inductive biases on downstream tasks, thereby motivating further exploration to shift more focus from expressiveness towards generalization analysis.

##### Limitation

The E(3)-completeness for invariant models is under the conditions of fully connected graphs. 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 and adopt atom-level representations, such as PaiNN [], which show promising experimental results but still lack theoretical expressiveness characterization.

## Appendix A Extended discussion of related work

##### Invaraint geometric models

To leverage the rich 3D geometric information contained in point clouds in permutation- and E(3)-invariant manner, early work Schütt et al. [] integrated 3D Euclidean distance into the MPNN framework [] and aggregate geometric information iteratively. Nevertheless, this model exhibits a restricted capacity to distinguish non-isomorphic point clouds even on fully-connected graphs as substantiated by Li et al. [], Pozdnyakov & Ceriotti [], Pozdnyakov et al. [], Hordan et al. []. Subsequent invariant models [, , , , , , ] have endeavored to enhance their geometric expressiveness through the incorporation of carefully designed high-order geometric features, or adopting local spherical representations. These designs have greatly improved the models’ performance on downstream tasks, however, most of them lack theoretical guarantees of geometric completeness over the whole point cloud spaces.

##### Expressiveness of DisGNN

Prior work [, , ] first analyzed expressiveness of DisGNN through pair-wise separation of point clouds. However, they rely on individual carefully constructed counterexamples, which is not sufficient for rigorously characterize its expressiveness. Hordan et al. [] establishes the completeness of DisGNN over a restricted subspace, which contains only point clouds with entirely distinct nodes, and therefore could be a coarse characterization.

##### General Geometric Expressiveness

Prior work Widdowson & Kurlin [, ], Kurlin [] proposed complete invariants for point clouds, and continuous metrics for their comparison. However, these works involve no learnable parameters and do not directly correspond to neural function forms, restricting their applications in various downstream tasks. Joshi et al. [] formally defines the expressiveness of geometric models through the separation of geometric graphs, extending similar concepts from traditional graph learning [, , ] to geometric settings. However, it does not fully characterize existing models’ expressiveness, such as revealing under what conditions can these models achieve E(3)-completeness. Moreover, it focuses on the expressiveness over geometric graphs, where node-level scalar and vector features are present, which do not exactly match our settings. Recently,  [, , , ] have proposed 2FWL-like invariant models with theoretical completeness, but such design space is restricted and whether weaker aggregation schemes, such as the scheme DimeNet [] adopts, can achieve completeness remains unclear.

There are also lots of geometric completeness results in the literature, which, however, are somehow restricted. For example, Wang et al. [] leverages the nearest neighboring node as a reference for computing higher-order geometric information. However, this leads to ambiguity when the point clouds are symmetric enough such that nodes have multiple nearest neighbors. This finally results in the completeness over a subspace of point clouds with only unsymmetric ones. Moreover, many frame-based methods project the coordinates or vector features onto local or global equivariant frames to ensure models’ Euclidean symmetry [, , , ]. Then, arbitrary powerful architectures, such as MLPs, are applied to these projected features without losing the Euclidean symmetry. Similarly, for most symmetric point clouds, which are exactly the corner cases that we aim to capture, the frames degenerate (can not be finitely determined). This implies that these methods may not be theoretically complete over all point clouds. We notice that there are several recent works that propose architectures based on weighted continuous frames [, , ] which could mitigate the degeneration and discontinuous problems. However, whether or under what conditions such models can achieve E(3)-completeness while maintaining exact symmetry over all point clouds remains unclear.

Finally, a significant proportion of geometric models leverage high-order SO(3) irreducible representations [, , , , , ], which come with the theoretical guarantee of universality []. However, the results [] show that models need arbitrarily high-order spherical tensors for approximating high-order polynomials, and whether a finite order is sufficient still remains unclear.

## Appendix B Extended analysis of DisGNN

### B.1 The proper subset relation in Figure 1 (b)

###### Proposition B.1 .

(Proper Subset)

- •
$\mathcal{D}$-symmetric point cloud set is a proper subset of $\mathcal{C}$-symmetric point cloud set.
- •
The unidentifiable point cloud set is a proper subset of $\mathcal{D}$-symmetric point cloud set.

###### Proof.

The first $\subseteq$ relation is a direct consequence of results in Delle Rose et al. [], Li et al. [], which have shown that DisGNN can capture node-center distances. While the second $\subseteq$ relation is a direct consequence of Theorem 3.2. Therefore, we only need to prove the $\subset$ relation for both cases. To see this, we construct a point cloud $P$ for each case, showing that $P$ is in the second set but not in the first set.

The first constructed $P$ is shown in Figure 2. This point cloud $P$ is $\mathcal{C}$-symmetric but not $\mathcal{D}$-symmetric

Figure: Figure 2: A point cloud $P$ that exhibits ${\mathcal{C}}$-symmetry but not ${\mathcal{D}}$-symmetry. (a) The point cloud $P$, which consists of an equilateral triangle and two additional nodes. (b) The labeled point cloud $(P,X^{\mathcal{C}})$ after calculating $\mathcal{C}$ features. Note that each node has the same distance to the geometric center, therefore the nodes still remain undivided. (c) The labeled point cloud $(P,X^{\mathcal{V}D})$ after calculating $\mathcal{D}$ features.
Refer to caption: x2.png

We describe the second case as follows. Consider an equilateral triangle of arbitrary length. For any other point cloud $P^{\prime}$ with three points that is non-isomorphic to $P$, we encounter only two scenarios: 1) $P^{\prime}$ consists of 3 nodes forming an equilateral triangle but with a distinct length; (2) $P^{\prime}$ consists of 3 nodes arranged in a manner that does not form an equilateral triangle. Importantly, DisGNN possesses the capability to distinguish between $P$ and $P^{\prime}$ for both cases, due to its ability to embed node numbers and all distance lengths. Consequently, DisGNN successfully identifies $P$ (i.e., $P$ is not in the unidentifiable set). However, it’s easy to check that $P$ is $\mathcal{D}$-symmetric.

∎

###### Proposition B.1 .

###### Proof.

### B.2 Measure of symmetric and unidentifiable point clouds

In this subsection, we aim to prove the Lebesgue measure on $\mathbb{R}^{n\times 3}$ of $\mathcal{C}$-symmetric point cloud set, $\mathcal{D}$-symmetric point cloud set and unidentifiable point cloud set are all 0. Since the subset relation has already been proved in Proposition B.1, showing that the largest $\mathcal{C}$-symmetric point cloud set has 0 measure is enough. We denote the complementary set (in $\mathbb{R}^{n\times 3}$) of $\mathcal{C}$-symmetric point cloud set as $\mathbb{R}^{n\times 3}_{\text{not }\mathcal{C}}$, which includes all $\mathcal{C}$-unsymmetric clouds.

To prove this, we first revisit the results from Hordan et al. [], which defines an unsymmetric point cloud subspace $\mathbb{R}^{n\times 3}_{\text{distinct}}$ and shows that its complementary set has a measure of 0. Consequently, to prove $\mathcal{C}$-symmetric point cloud set has 0 measure, it suffices to show that $\mathbb{R}^{n\times 3}_{\text{distinct}}\subset\mathbb{R}^{n\times 3}_{\text{
not }\mathcal{C}}$.

###### Definition B.2 .

($\mathbb{R}^{n\times 3}_{\text{distinct}}$ set [])
We define $\mathbb{R}^{n\times 3}_{\text{distinct}}\subset\mathbb{R}^{n\times 3}$ as $\mathbb{R}^{n\times 3}_{\text{distinct}}:=\{P\in\mathbb{R}^{n\times 3}\mid d(i
,P)\neq d(j,P)\mid\forall i,j\in[n],i\neq j\}$, where the geometric degree of $i$ is defined as $d(i,X)=\{\!\!\{\|p_{1}-p_{i}\|,\ldots,\|p_{n}-p_{i}\|\}\!\!\}$.

It is obvious that the point clouds from $\mathbb{R}^{n\times 3}_{\text{distinct}}$ are all quite unsymmetric: all points within the point cloud are "different". Therefore, one can expect that DisGNN can easily distinguish two point clouds $P_{1}$, $P_{2}$ $\in\mathbb{R}^{n\times 3}_{\text{distinct}}$, as shown in Theorem 2 from Hordan et al. []. In the following proposition, we show that our defined unsymmetry is strictly milder than that defined in $\mathbb{R}^{n\times 3}_{\text{distinct}}$.

###### Proposition B.3 .

$\mathbb{R}^{n\times 3}_{\text{distinct}}\subset\mathbb{R}^{n\times 3}_{\text{
not }\mathcal{C}}$.

###### Proof.

We first prove that $\mathbb{R}^{n\times 3}_{\text{distinct}}\subseteq\mathbb{R}^{n\times 3}_{\text
{not }\mathcal{C}}$. It suffices to show that, given an arbitrary point cloud $P$ $\in\mathbb{R}^{n\times 3}_{\text{distinct}}$, $P\in\mathbb{R}^{n\times 3}_{\text{not }\mathcal{C}}$.

Denote the geometric center of $P$ as $c$, and denote the distance from $i$ to $c$ as $d_{ic}$. From the Barycenter Lemma presented in Delle Rose et al. [], we have:

$$ $\displaystyle d_{ic}^{2}=\frac{1}{n}\left(f(i)-\frac{1}{2n}\sum_{j\in[n]}f(j)\right)$ (2) $$

where $f(i)=\sum_{j\in[n]}d_{ij}^{2}$.

Obviously, given arbitrary $i,j\in[n]$, $P\in\mathbb{R}^{n\times 3}_{\text{distinct}}$ implies $f(i)\neq f(j)$. Consequently, $d_{ic}\neq d_{jc}$, which means that the center distance encoding $\mathcal{C}(P)$ will give $n$ distinct node features. Since we consider point clouds with node number $n>1$, it directly implies that $|\mathcal{C}^{\text{set}}(P)|>1|$ (simply consider two $m:\mathbb{R}\to\mathbb{R}$ functions $m_{1},m_{2}$ such that $m_{1}(d)=1$ only when $d=d_{1c}$ and 0 0 otherwise, and $m_{2}(d)=1$ only when $d=d_{2c}$ and 0 0 otherwise; these two functions can already contribute two elements in $\mathcal{C}^{\text{set}}(P)$). Therefore, $P\in\mathbb{R}^{n\times 3}_{\text{not }\mathcal{C}}$.

Now, we prove that $\mathbb{R}^{n\times 3}_{\text{distinct}}\subset\mathbb{R}^{n\times 3}_{\text{
not }\mathcal{C}}$. It suffices to give an example of a point cloud $P$ $\in\mathbb{R}^{n\times 3}_{\text{not }\mathcal{C}}$ but $P\notin\mathbb{R}^{n\times 3}_{\text{distinct}}$. Simply look at the case shown in the leftmost of Figure 1(a). This point cloud is already shown as $\mathcal{C}$-unsymmetric, i.e., $P\in\mathbb{R}^{n\times 3}_{\text{not }\mathcal{C}}$. However, it is easy to see that $P\notin\mathbb{R}^{n\times 3}_{\text{distinct}}$, since the two upper points share the same geometric degree.

Actually, other examples can be very easily constructed, such as isosceles triangles whose leg length is different from the base length. The root cause of that $\mathbb{R}^{n\times 3}_{\text{not }\mathcal{C}}$ contains much more point clouds than $\mathbb{R}^{n\times 3}_{\text{distinct}}$ is that $\mathbb{R}^{n\times 3}_{\text{distinct}}$ restricts too much on the unsymmetry of point clouds, requiring all pairs of nodes to be distinct, while $\mathbb{R}^{n\times 3}_{\text{not }\mathcal{C}}$ cares more about the global unsymmetry of the whole point cloud.
∎

Figure: Figure 3: The relation of our proposed symmetric point cloud sets with the symmetric set $\mathbb{R}^{n\times 3}\backslash\mathbb{R}^{n\times 3}_{\text{distinct}}$ characterized in prior work []. The $\mathcal{C}$-symmetric point cloud set is a proper subset of $\mathbb{R}^{n\times 3}\backslash\mathbb{R}^{n\times 3}_{\text{distinct}}$, as indicated in Proposition B.3.
Refer to caption: x3.png

###### Theorem B.4 .

The Lebesgue measure on $\mathbb{R}^{n\times 3}$ of $\mathcal{C}$-symmetric point cloud set, $\mathcal{D}$-symmetric point cloud set and unidentifiable point cloud set are all 0.

###### Proof.

This theorem is a direct consequence of Proposition B.1, Proposition B.3 and Theorem 8 in Hordan et al. [] (which shows that the Lebesgue measure of the complementary set of $\mathbb{R}^{n\times 3}_{\text{distinct}}$ is 0).
∎

To conclude, we notice that Theorem 3.2 indicates much more pairs of distinguishable point clouds than Theorem 2 in Hordan et al. [] (which shows that given any two point clouds $P_{1},P_{2}$ $\in\mathbb{R}^{n\times 3}_{\text{distinct}}$, DisGNN can distinguish them). Strictly:

- •
Theorem 3.2 shows that arbitrary pairs of point clouds $P_{1},P_{2}$ $\in\mathbb{R}^{n\times 3}_{\text{not }\mathcal{C}}$, and a larger unsymmetric point cloud set $\mathbb{R}^{n\times 3}_{\text{not }\mathcal{D}}$, can be distinguished by DisGNN. These two sets are both larger than $\mathbb{R}^{n\times 3}_{\text{distinct}}$, as indicated in Proposition B.1 and Proposition B.3. This relation is illustrated in Figure 3.
- •
Theorem 3.2 further shows identifiability. This further means, for arbitrary $P_{1}\in\mathbb{R}^{n\times 3}_{\text{not }\mathcal{C}}$ (or the larger set $\mathbb{R}^{n\times 3}_{\text{not }\mathcal{D}}$), and $P_{2}$ from the whole point cloud set $\mathbb{R}^{n\times 3}$, DisGNN can still distinguish them.

###### Definition B.2 .

###### Proposition B.3 .

###### Proof.

###### Theorem B.4 .

###### Proof.

### B.3 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: With some tolerance error, what is the proportion of unidentifiable cases for DisGNN in real-world point clouds? We answer this question by assessing the proportion of unidentifiable cases’ supersets, namely $\mathcal{C}$- and $\mathcal{D}$-symmetric point clouds, and therefore indirectly assessing the proportion of unidentifiable cases. Our findings demonstrate that, experimentally, DisGNN can identify nearly all point clouds present in real-world datasets.

We first give a simple proposition, which can determine whether a given point cloud is $\mathcal{A}$-symmetric without the need to consider mass functions $m$, and can convenite the tolerance error setting.

###### Proposition B.5 .

(Equivalent definition for $\mathcal{A}$-symmetry)
Given an arbitrary point cloud $P\in\mathbb{R}^{n\times 3}$ and a E(3)-invaraint and permutation-equivariant algorithm $\mathcal{A}$, let $K$ denote the number of distinct node features in $\mathcal{A}(P)$, and we consider $K$ point clouds each only contain nodes from $P$ with the same node feature. Then we have: $P$ is $\mathcal{A}$-symmetric $\iff$ all these $K$ point clouds’ geometric centers coincide.

###### Proof.

We first prove that $P$ is $\mathcal{A}$-symmetric $\implies$ all these $K$ point clouds’ geometric centers coincide. This is actually a direct consequence of the original definition of $\mathcal{A}$-symmetry: each geometric center of the $K$ point clouds is in $\mathcal{A}^{\text{set}}(P)$, and $P$ is $\mathcal{A}$-symmetric means that $\mathcal{A}^{\text{set}}(P)$ contains only one element, therefore all $\mathcal{A}(P)^{*}_{k}$-type nodes’ geometric centers coincide.

We then prove the reverse direction. We denote $I_{k}$ as the index set of the nodes with the $k$-th kind of node features in $\mathcal{A}(P)$. For an arbitrary element $\mathcal{A}(G)^{m}$ from collections $\mathcal{A}^{\text{set}}(P)$ calculated by function $m$, we have $\mathcal{A}(G)^{m}=\frac{\sum_{i\in[n]}m(x_{i}^{\mathcal{A}})p_{i}}{\sum_{i\in
[n]}m(x_{i}^{\mathcal{A}})}$ by definition, which can be decomposed as follows:

$$ $\displaystyle\mathcal{A}(G)^{m}$ $\displaystyle=\frac{\sum_{i\in[n]}m(x_{i}^{\mathcal{A}})p_{i}}{\sum_{i\in[n]}m (x_{i}^{\mathcal{A}})}$ $\displaystyle=\frac{\sum_{k\in[K]}\sum_{i\in I_{k}}m(x_{i}^{\mathcal{A}})p_{i} }{\sum_{k\in[K]}\sum_{i\in I_{k}}m(x_{i}^{\mathcal{A}})}$ $\displaystyle=\frac{\sum_{k\in[K]}M_{k}c_{k}}{\sum_{k\in[K]}M_{k}},$ (3) $$

where $c_{k}\in\mathbb{R}^{3}$ denotes the geometric center of the $k$-th point cloud, $M_{k}=\sum_{i\in I_{k}}m(x_{i}^{\mathcal{A}})$ denotes the sum of "masses" associated with the $k$-th point cloud. Since all $c_{k}$ coincide, i.e., $c_{1}=c_{2}=\ldots=c_{K}$, we have: $\mathcal{A}(G)^{m}=\frac{c_{1}\sum_{k\in[K]}M_{k}}{\sum_{k\in[K]}M_{k}}=c_{1}$. Thus, all the possible elements from $\mathcal{A}^{\text{set}}(P)$ coincide with $c_{1}$. Obviously, since the geometric center $c$ of the whole point cloud is also in $\mathcal{A}^{\text{set}}(P)$, $c_{1}=c$. Therefore, $P$ is $\mathcal{A}$-symmetric.
∎

Now, considering that practical computational calculations are subjected to floating-point errors, and real-life point clouds are often noisy, based on Proposition B.5, we can introduce two tolerance errors to determine whether a point cloud is symmetric in a more tolerant way.

###### Proposition B.5 .

###### Proof.

##### Tolerance Error

1) The rounding number $r$ for distance-related calculation. When applying $\mathcal{C}$ and $\mathcal{D}$, we calculate 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 determine the symmetry of noisy point clouds, a point cloud is considered symmetric if all the $K$ point cloud’s (defined in Proposition B.5) geometric centers are located within a ball 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 tolerance of a point cloud being determined as symmetric.

##### Real-world datasets

We select two representative datasets, namely QM9 and ModelNet40, for the assessment. The QM9 dataset comprises approximately 130K molecules, while the ModelNet40 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 point clouds, and our objective is to count the occurrence of symmetric ones within them. We ignore all the initial node labels in QM9 to augment the challenge, and downsample each point cloud in ModelNet40 to 256 points.

##### 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 point clouds 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 ModelNet40 (which is thus 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 point cloud located within a unit sphere. As a result, many non-symmetric clouds may still be determined as symmetric under such criteria. We use this as a rough upper bound only for reference.

##### Results

The assessment results in Figure 4 reveal the following observations. 1) Concerning the QM9 dataset, even when utilizing the largest deviation error (1e-1), the proportion of ${\mathcal{C}}$- and ${\mathcal{D}}$-symmetric point clouds are less than $\sim$0.15% of the entire dataset. Since ${\mathcal{C}}$- and ${\mathcal{D}}$-symmetric point cloud spaces are supersets of the unidentifiable space of DisGNN, therefore the unidentifiable proportion can only be less than $\sim$0.15%. With the strictest deviation error, only 0.0046% of the graphs (6 out of $\sim$130K) exhibit ${\mathcal{D}}$-symmetry. 2) In the ModelNet40 dataset, when deviation error is less than 1e-1, only 1 or 2 point clouds demonstrate symmetry. And there is no ${\mathcal{D}}$-symmetric point clouds found at all across all deviation errors.

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

Figure: Figure 4: Assessment of symmetric point clouds in real-world datasets. (a) Proportion of symmetric point clouds in the QM9 dataset. (b) Proportion of symmetric point clouds in the ModelNet40 dataset. The proportions of ${\mathcal{D}}$-symmetric point clouds in ModelNet40 is zero across all deviation errors.
Refer to caption: x4.png

## Appendix C Extended analysis of GeoNGNN

### C.1 Complexity analysis

For a $n$-sized point cloud, 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 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 [], DimeNet [], and SphereNet [], when their conditions for achieving E(3)-completeness are met.

We leverage the findings introduced by Amir et al. [] to analyze the complexity involving the realization of injective neural functions. Within each aggregation layer, GeoNGNN embeds the multiset $\{\!\!\{(h_{ij}^{(l)},d_{ij})\mid j\in[n]\}\!\!\}$ to update the representation of $h_{ij}^{(l)}$. As per the study conducted by Amir et al. [], an embedding dimension of $O(kn)$ is sufficient for injectively embedding such a multiset, with $k$ representing the embedding dimension of $(h_{ij}^{(l)},d_{ij})$. In the initial layer, $(h_{ij}^{(0)},d_{ij})$ possesses a constant dimension independent of $n$. Therefore, the sufficient embedding dimension for $h^{(1)}_{ij}$ is $O(n)$. Though it seems that the sufficient embedding dimension will grow exponentially with respect to the layer number $l$, Hordan et al. [] has demonstrated that the crucial dimension is the intrinsic dimension of the multiset, which maintains $O(n)$ throughout all layers, rather than $kn$, the ambient dimension. Consequently, the sufficient embedding dimension for any given layer is $O(n)$. By following the neural function form proposed by Amir et al. [], we apply a shallow MLP individually to each element within the multiset and sum them up to obtain the multiset embedding. This leads to a complexity of $O(n^{2})\times n=O(n^{3})$, where $O(n^{2})$ represents the complexity of forwardness of MLP whose input and output dimension are both $O(n)$, and $n$ represents the $n$ elements in the multiset. Considering the updating of all $h_{ij}^{(l)},i,j\in[n]$, the complexity in each layer becomes $O(n^{3})\times n^{2}=O(n^{5})$. During the final pooling stage, the nodes are initially pooled into subgraph representations, resulting in $n\times O(n^{2})\times n=O(n^{4})$, where the first $n$ denotes $n$ subgraphs, and the last $n$ denotes $n$ nodes within each subgraph. Subsequently, all subgraph representations are further pooled into a graph-level representation, culminating in a complexity of $O(n^{2})\times n=O(n^{3})$, where $n$ represents $n$ nodes. Consequently, the overall complexity amounts to $O(n^{5})$.

Practical GeoNGNN achieves an asymptotic time complexity of $O(n)$ by restricting the subgraph cutoff, the message passing cutoff and the hidden neuron number 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 DisGNN.

### C.2 Theoretical expressiveness with finite subgraph radius and distance cutoff

While Theorem 4.2 establishes that infinite subgraph radius and distance cutoff guarantees completeness over all point clouds, this section explores how finite values can also enhance geometric expressiveness compared to DisGNN. We demonstrate this through an example.

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

Figure: Figure 5: 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.
Refer to caption: x6.png

## Appendix D Geometric subgraph graph neural networks

In this section, we provide self-contained definitions of general geometric subgraph GNNs as delineated in Definition 4.3 as well as definitions of the geometric counterparts of well-established traditional subgraph GNNs, all of which are proven to be E(3)-complete under specific conditions.

### D.1 Basic definitions

We first notice that the main definition of general geometric subgraph GNN is based on the general definitions of subgraph GNNs in traditional graph settings from Zhang et al. [], where the input graphs are unweighted graphs. The difference is that the geometric subgraph GNN is applied to point clouds, treating it as distance graphs with distance cutoff $r_{\text{cutoff}}$, and applies geometric aggregations.

We separately introduce the main components in Definition 4.3. We will use $G=(\mathcal{V}_{G},\mathcal{E}_{G})$ to denote the original distance graph, where $\mathcal{V}_{G}=[n]$ contains all the nodes in the distance graph, and $\mathcal{E}_{G}=\{(u,v)\mid u,v\in\mathcal{V}_{G},d_{uv}\leq r_{\text{cutoff}}\}$ contains all the weighted edges with weight (distance) less than $r_{\text{cutoff}}$, by definition of distance graph. We use $G^{u}=(\mathcal{V}_{G^{u}},\mathcal{E}_{G^{u}})$ to denote node $u$’s subgraph. We use $\mathcal{N}_{G^{v}}(u)$ to denote $u$’s neighbor in $v$’s subgraph, i.e., $\mathcal{N}_{G^{v}}(u)=\{i\mid i\in\mathcal{V}_{G^{v}},(i,u)\in\mathcal{E}_{G^
{v}}\}$.

##### Subgraph generation

General geometric subgraph GNNs adopt node marking with $r_{\text{sub}}$-size ego subgraph as the subgraph generation policy. This essentially means that node $u$’s subgraph, $G^{u}=(\mathcal{V}_{G^{u}},\mathcal{E}_{G^{u}})$, contains all the nodes and edges within Euclidean distance $r_{\text{sub}}$, i.e., $\mathcal{V}_{G^{u}}=\{i\mid i\in\mathcal{V}_{G},d_{iu}\leq r_{\text{sub}}\}$, $\mathcal{E}_{G^{u}}=\{(i,j)\mid(i,j)\in\mathcal{E}_{G},i,j\in V_{G^{u}}\}$. And node $v$ in $u$’s subgraph’s initial representation is $h^{(0)}_{uv}=f^{\text{init}}(\mathds{1}_{u=v},x_{u},x_{v})$, where $\mathds{1}_{u=v}$ represents indicator function that equals $1$ when $u=v$ and 0 0 otherwise, and $x_{u},x_{v}$ are the potential node features.

##### Geometric aggregation schemes

As defined in Definition 4.3, geometric subgraph GNN adopts general geometric subgraph GNN layers as the basic aggregation layer, which is formally defined as follows:

###### Definition D.1 .

A general geometric subgraph GNN layer has the form

$$ $h^{(l+1)}_{uv}=f^{(l+1)}(h^{(l)}_{uv},\mathsf{op}_{1}(u,v,h^{(l)},G),\cdots, \mathsf{op}_{r}(u,v,h^{(l)},G)),$ $$

where $f^{(l+1)}$ is an arbitrary parameterized continuous function, and each atomic operation $\mathsf{op}_{i}(u,v,h,G)$ can take any of the following expressions:

- •
Single-point: $h_{vu}$, $h_{uu}$, or $h_{vv}$;
- •
Global: $\{\!\!\{h_{uw}\mid w\in\mathcal{V}_{G}\}\!\!\}$ or $\{\!\!\{h_{wv}\mid w\in\mathcal{V}_{G}\}\!\!\}$;
- •
Local: $\{\!\!\{(h_{uw},d_{vw})\mid w\in\mathcal{N}_{G^{u}}(v)\}\!\!\}$ or $\{\!\!\{(h_{wv},d_{uw})\mid w\in\mathcal{N}_{G^{v}}(u)\}\!\!\}$

Notice that $h(u,v)$ is always in the input to ensure that geometric subgraph GNN can always refine the node feature partition. These operations are denoted as $\mathsf{agg}^{\mathsf{P}}_{\mathsf{uu}},\mathsf{agg}^{\mathsf{P}}_{\mathsf{vv}
},\mathsf{agg}^{\mathsf{P}}_{\mathsf{vu}},\mathsf{agg}^{\mathsf{G}}_{\mathsf{u
}},\mathsf{agg}^{\mathsf{G}}_{\mathsf{v}},{\color[rgb]{0,0,1}\mathsf{Geoagg}^{
\mathsf{L}}_{\mathsf{u}}},{\color[rgb]{0,0,1}\mathsf{Geoagg}^{\mathsf{L}}_{
\mathsf{v}}}$, respectively. Here, we color the local operations with blue and name it with an additional "Geo" prefix since all the aggregation schemes do not incorporate geometric information and are the same as those in Zhang et al. [], except for the local operations, which additionally incorporates distance information.

###### Definition D.1 .

##### Pooling layer

After $L$ geometric aggregation layers, geometric subgraph GNN outputs a graph-level representation $f(G)$ through a two-level pooling of the collected features $\{\mskip-5.0mu\{h^{(L)}_{uv}:u,v\in\mathcal{V}_{G}\}\mskip-5.0mu\}$ the same as Zhang et al. [] do. Specifically, there are two approaches, named VS (vertex-subgraph pooling) and SV (subgraph-vertex pooling). The first approach first pools all node features in each subgraph $G^{u}$ to obtain the subgraph representation, i.e., $h_{u}=f^{\mathsf{S}}\left(\{\!\!\{h^{(L)}_{uv}\mid v\in\mathcal{V}_{G}\}\!\!\}\right)$, and then pools all subgraph representations to obtain the final output $h_{G}=f^{\mathsf{G}}(\{\!\!\{h_{u}\mid u\in\mathcal{V}_{G}\}\!\!\})$. Here, $f^{\mathsf{S}}$ and $f^{\mathsf{G}}$ can be any parameterized function. The second approach first generates node representations $h_{u}=f^{\mathsf{V}}\left(\{\!\!\{h^{(L)}_{uv}\mid u\in\mathcal{V}_{G}\}\!\!\}\right)$, and then pools all these node representations to obtain the graph representation, i.e., $h_{G}=f^{\mathsf{G}}(\{\!\!\{h_{u}\mid u\in\mathcal{V}_{G}\}\!\!\})$.

We denote a general geometric subgraph GNN with $L$ layers, each with aggregation scheme $\mathcal{A}=\mathcal{B}\cup\mathsf{agg}^{\mathsf{P}}_{\mathsf{uv}}$, and with parameters $r_{\text{sub}},r_{\text{cutoff}}$ as $\mathsf{GeoA}(\mathcal{A},\mathsf{Pool},L,r_{\text{sub}},r_{\text{cutoff}})$, where $\mathsf{Pool}\in\{\mathsf{VS},\mathsf{SV}\}$, and

$$ $\mathcal{B}\subset\{\mathsf{agg}^{\mathsf{P}}_{\mathsf{uu}},\mathsf{agg}^{ \mathsf{P}}_{\mathsf{vv}},\mathsf{agg}^{\mathsf{P}}_{\mathsf{vu}},\mathsf{agg} ^{\mathsf{G}}_{\mathsf{u}},\mathsf{agg}^{\mathsf{G}}_{\mathsf{v}},{\color[rgb] {0,0,1}\mathsf{Geoagg}^{\mathsf{L}}_{\mathsf{u}}},{\color[rgb]{0,0,1}\mathsf{ Geoagg}^{\mathsf{L}}_{\mathsf{v}}}\}.$ $$

It is obvious that GeoNGNN without outer GNN, defined in Definition 4.1, is a specific kind of general subgraph GNN, which can be denoted as $\mathsf{GeoA}(\{\mathsf{agg}^{\mathsf{P}}_{\mathsf{uv}},\mathsf{Geoagg}^{
\mathsf{L}}_{\mathsf{u}}\},VS,N_{\text{inner}},r_{\text{sub}},r_{\text{cutoff}})$.

### D.2 Geometric counterparts of well-known traditional subgraph GNNs

In the main body, we have extended one of the simplest subgraph GNNs, NGNN, to geometric scenarios, and shown that GeoNGNN is already E(3)-complete. Similar efforts can be made to other well known subgraph GNNs, including DS-GNN [], DSS-GNN [], GNN-AK [], OSAN [] and so on. We now give a general definition of the geometric counterparts of these subgraph GNNs, and show that they, even though does not exactly match the general forms in Definition 4.3, are also E(3)-complete under exactly the same conditions as Theorem 4.4.

Similar to Zhang et al. [], we consider the following well-known subgraph GNNs: IDGNN [], DS-GNN [], OSAN [], GNN-AK [], DSS-GNN (ESAN) [], GNN-AK-ctx [], SUN []. Generally, all these traditional subgraph GNNs involve local aggregations. In a manner akin to the modification detailed in Definition 4.3, to get the geometric counterpart of these models, we replace the node representations aggregated by local operations with node representations that integrate the distances between the aggregated node and the base node (i.e., the node performing the aggregation).

Notably, GNN-AK, GNN-AK-ctx, IDGNN, OSAN, DS-GNN, and DSS-GNN all employ base GNNs, which can operate on graphs, subgraphs, or a combination of subgraphs (as in DSS-GNN). In these cases, the proposed adjustment simply involves replacing these base GNNs with DisGNN. In certain architectures like SUN, they may have more complicated operations, such as aggregating $\{\!\!\{h_{ww^{\prime}}\mid w^{\prime}\in\mathcal{N}(v),w\in\mathcal{V}_{G}\}
\!\!\}$ to update $h_{uv}$, which involve a combination of global ($w$) and local ($w^{\prime}$) aggregation. Consistent with the modification rule, we selectively incorporate distance information solely for these local operations. Therefore, the featured geometric counterpart aggregates $\{\!\!\{(h_{w,w^{\prime}},d_{w^{\prime}v})\mid w^{\prime}\in\mathcal{N}(v),w
\in\mathcal{V}_{G}\}\!\!\}$ instead. One can also incorporate distance information into those global operations. However, they are unnecessary in terms of boosting expressiveness, as current modifications are enough for them to achieve completeness, as shown in the following. We name all the geometric counterparts with a Geo prefix, such as GeoSun.

###### Theorem D.2 .

(Completeness for geometric counterparts of well-known subgraph GNNs) Under the node marking with $r_{\text{sub}}$-size ego subgraph policy, when the conditions described in Theorem 4.4 are met, GeoIDGNN, GeoDS-GNN, GeoOSAN, GeoGNN-AK, GeoDSS-GNN (ESAN), GeoGNN-AK-ctx, GeoSUN are all E(3)-complete.

###### Proof.

- •
Among these models, GeoIDGNN, GeoDS-GNN, GeoOSAN fall under the general definition of geometric subgraph GNNs (see Definition 4.3), and they all incorporate at least one local operation, therefore they are inherently complete given these conditions according to Theorem 4.4.
- •
Under node marking with original graph ($r_{\text{sub}}=\infty$) policy, the other models can all be well abstracted and summarized, which have been done by Zhang et al. []. We list here for convenience (non-blue parts represent the geometric modification):
GeoGNN-AK [].
$\displaystyle h^{(l+1)}_{uv}=\left\{\begin{array}[]{ll}\begin{aligned} f^{(l)}
(&h^{(l)}_{uv},\\
&h^{(l)}_{vv},\\
&\{\mskip-5.0mu\{{\color[rgb]{0,0,1}(}h^{(l)}_{uw}{\color[rgb]{0,0,1},d_{vw})}
:w\in\mathcal{N}_{G}(v)\}\mskip-5.0mu\})\end{aligned}&\text{if }u\neq v,\\
\begin{aligned} f^{(l)}(&h^{(l)}_{vv},\\
&\{\mskip-5.0mu\{{\color[rgb]{0,0,1}(}h^{(l)}_{uw}{\color[rgb]{0,0,1},d_{vw})}
:w\in\mathcal{N}_{G}(v)\}\mskip-5.0mu\},\\
&\{\mskip-5.0mu\{h^{(l)}_{uw}:w\in\mathcal{V}_{G}\}\mskip-5.0mu\})\end{aligned
}&\text{if }u=v.\end{array}\right.$
It adopts VS pooling.
Geo$\mathsf{GNN}\text{-}\mathsf{AK}\text{-}\mathsf{ctx}$ []. The GNN aggregation scheme can be written as
$\displaystyle h^{(l+1)}_{uv}=\left\{\begin{array}[]{ll}\begin{aligned} f^{(l)}
(&h^{(l)}_{uv},\\
&h^{(l)}_{vv},\\
&\{\mskip-5.0mu\{{\color[rgb]{0,0,1}(}h^{(l)}_{uw}{\color[rgb]{0,0,1},d_{vw})}
:w\in\mathcal{N}_{G}(v)\}\mskip-5.0mu\})\end{aligned}&\text{if }u\neq v,\\
\begin{aligned} f^{(l)}(&h^{(l)}_{vv},\\
&\{\mskip-5.0mu\{{\color[rgb]{0,0,1}(}h^{(l)}_{uw}{\color[rgb]{0,0,1},d_{vw})}
:w\in\mathcal{N}_{G}(v)\}\mskip-5.0mu\},\\
&\{\mskip-5.0mu\{h^{(l)}_{uw}:w\in\mathcal{V}_{G}\}\mskip-5.0mu\},\\
&\{\mskip-5.0mu\{h^{(l)}_{wv}:w\in\mathcal{V}_{G}\}\mskip-5.0mu\})\end{aligned
}&\text{if }u=v.\end{array}\right.$
It adopts VS pooling.
GeoDSS-GNN []. The aggregation scheme of DSS-GNN can be written as
$\displaystyle h^{(l+1)}_{uv}=f^{(l)}($
$\displaystyle h^{(l)}_{uv},$
$\displaystyle\{\mskip-5.0mu\{{\color[rgb]{0,0,1}(}h^{(l)}_{uw}{\color[rgb]{
0,0,1},d_{vw})}:w\in\mathcal{N}_{G}(v)\}\mskip-5.0mu\},$
$\displaystyle\{\mskip-5.0mu\{h^{(l)}_{wv}:w\in\mathcal{V}_{G}\}\mskip-5.0mu\},$
$\displaystyle\{\mskip-5.0mu\{{\color[rgb]{0,0,1}(}h^{(l)}_{w,w^{\prime}}{
\color[rgb]{0,0,1},d_{w^{\prime}v})}:w\in\mathcal{V}_{G},w^{\prime}\in\mathcal
{N}_{G}(v)\}\mskip-5.0mu\}).$
It adopts VS pooling.
GeoSUN []. The WL aggregation scheme can be written as
$\displaystyle h^{(l+1)}_{uv}=f^{(l)}($
$\displaystyle h^{(l)}_{uv},h^{(l)}_{uu},h^{(l)}_{vv},$
$\displaystyle\{\mskip-5.0mu\{{\color[rgb]{0,0,1}(}h^{(l)}_{uw}{\color[rgb]{
0,0,1},d_{vw})}:w\in\mathcal{N}_{G}(v)\}\mskip-5.0mu\},$
$\displaystyle\{\mskip-5.0mu\{h^{(l)}_{uw}:w\in\mathcal{V}_{G}\}\mskip-5.0mu\},$
$\displaystyle\{\mskip-5.0mu\{h^{(l)}_{wv}:w\in\mathcal{V}_{G}\}\mskip-5.0mu\},$
$\displaystyle\{\mskip-5.0mu\{{\color[rgb]{0,0,1}(}h^{(l)}_{w,w^{\prime}}{
\color[rgb]{0,0,1},d_{w^{\prime}v})}:w\in\mathcal{V}_{G},w^{\prime}\in\mathcal
{N}_{G}(v)\}\mskip-5.0mu\}).$
It can adopt VS or SV pooling.

Regarding these models, it is observed that they all exhibit the local operation $\mathsf{Geoagg}^{L}_{u}$, thus enabling them to implement the GeoNGNN inner layer with a single aggregation layer, as demonstrated in the proof of Theorem 4.4. Moreover, irrespective of whether they employ SV or VS pooling, they are all capable of implementing VS pooling, which is adopted by GeoNGNN, as evidenced in the proof of Theorem 4.4. Hence, under the given conditions, these models can also implement GeoNGNN under the given conditions and consequently achieve completeness, as GeoNGNN itself is complete.

∎

###### Theorem D.2 .

###### Proof.

## Appendix E Proof of conclusions in main body

### E.1 Preparation

In the following proof, we particularly focus on models’ ability to encode input representations without significant information loss. We provide a formal definition of an important concept derive below:

###### Definition E.1 .

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

For example, consider the space $\mathbb{P}=\mathbb{R}^{n\times 3}$ comprising all point clouds of size $n$. Let $f$ denote an encoder that computes $f(P)=(\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 $P$, it follows that $f(P)\to g(P)$, since we can calculate the geometric center from the sum of the nodes’ coordinates and the number of nodes. In the following analysis, we consider $\mathbb{P}=\mathbb{R}^{n\times 3}$ by default. Notice that derivation exhibits transitivity: if $f_{1}\to f_{2}$ and $f_{2}\to f_{3}$, it follows that $f_{1}\to f_{3}$.

Intuitively, “derive" is a concept describing the relation of two properties, i.e., whether property $f(P)$ contains all the information needed to calculate $g(P)$. Obviously, if an encoder $f$ can embed all the information needed for reconstructing a given point cloud, then it is E(3)-complete:

###### Proposition E.2 .

Consider $\mathbb{P}=\mathbb{R}^{n\times 3}$ being the space of all point clouds of size $n$, and $f$ satisfying permutation- and E(3)-invariance, then: $f(P)\to P$ up to permutation and Euclidean isometry $\iff$ $f$ is E(3)-complete.

###### Proof.

We first prove the reverse direction.
Since $f$ is E(3)-complete, it will give distinct graph embeddings/features $s\in\mathbb{R}^{d}$ for non-isomorphic finite-size point clouds. We can thus let $h:\mathbb{R}^{d}\to\mathbb{R}^{n\times 3}$ be a mapping which exactly maps the graph embeddings to the original point clouds up to permutation and Euclidean isometry. The existence of such $h$ implies that $f(P)\to P$ up to permutation and Euclidean isometry.

For the forward direction, we prove by contradiction. Assume that $f$ is not E(3)-complete, i.e., there exists two non-isomorphic point clouds $P_{1},P_{2}$ such that $f(P_{1})=f(P_{2})$. Since $f(P)\to P$ up to permutation and Euclidean isometry, we have that there exists a function $h$ that can reconstruct the point cloud from the embedding. However, since $f(P_{1})=f(P_{2})$, their reconstruction $h(f(P_{1})),h(f(P_{2}))$ will be the same up to permutation and Euclidean isometry, which contradicts the assumption that $P_{1}$ and $P_{2}$ are non-isomorphic. Therefore, $f$ is E(3)-complete.
∎

###### Definition E.1 .

###### Proposition E.2 .

###### Proof.

### E.2 Proof of Theorem 3.2

As indicated in Figure 1(b), all $\mathcal{D}$-symmetric point clouds are also $\mathcal{C}$-symmetric, and therefore. Here, we first formally prove it.

###### Proposition E.3 .

($\mathcal{D}$-symmetry implies $\mathcal{C}$-symmetry)
For any point cloud $P\in\mathbb{R}^{n\times 3}$, if $P$ is $\mathcal{D}$-symmetric, then $P$ is $\mathcal{C}$-symmetric.

###### Proof.

As indicated by the conclusions of Delle Rose et al. [], Li et al. [], with the "derive" notations we introduced in the previous subsection, we have that: $x^{\mathcal{D}}_{i}\to x^{\mathcal{C}}_{i}$, where $P\in\mathbb{R}^{n\times 3}$. This essentially implies that DisGNN’s node-level output contains the information of the distance between nodes to the geometric center. As a direct consequence, for any point cloud $P$, the node partition based on node features $X^{\mathcal{D}}$ will be no coarser than that based on $\mathcal{C}(P)$. (Otherwise, assume that there exists some $P^{\prime}$ and nodes $i,j$ such that $x^{\mathcal{D}}_{i}=x^{\mathcal{D}}_{j}$ but $x^{\mathcal{C}}_{i}\neq x^{\mathcal{C}}_{j}$. Then the implicit function $h$ that takes $x^{\mathcal{D}}_{i}$ as input and output $x^{\mathcal{C}}_{i}$ will not exist, which contradicts the assumption that $x^{\mathcal{D}}_{i}\to x^{\mathcal{C}}_{i}$.)

If $P$ is $\mathcal{D}$-symmetric, the center set $\mathcal{D}^{\text{set}}(P)$ will obtain only one element. By definition, the cardinality of the center sets only depends on the node features partitions, and no coarser partition will lead to no smaller center set. Therefore, $\mathcal{C}^{\text{set}}(P)$ will also contain only one element, and thus $P$ is $\mathcal{C}$-symmetric.
∎

Based on Proposition E.3, to prove Theorem 3.2, it suffices to prove that point clouds that are not $\mathcal{D}$-symmetric are identifiable. To prove this, we first show the ability of DisGNN to learn global geometric information:

###### Lemma E.4 .

(Locate $\mathcal{A}$ centers) Given a point cloud $P\in\mathbb{R}^{n\times 3}$ with node features calculated by algorithm $\mathcal{A}$, $X^{\mathcal{A}}$. Denote the $\mathcal{D}$-center calculated by mass function $m$ as $c^{m}\in\mathbb{R}^{n\times 3}$. With a bit notation abuse, we use $d_{ic^{m}}$ to represent the distance between node $i$ and $c^{m}$.

We now run a DisGNN on $(P,X^{\mathcal{A}})$, and denote the node $i$’s representations at layer $l$ as $h_{i}^{(l)}$ (we let $h_{i}^{(0)}=x_{i}^{\mathcal{A}}$). Then we have:

- •
(Node-center distance) Given an arbitrary mass function $m$, $h_{i}^{(2)}$ can derive $d_{i,c^{m}}$.
- •
(Center-center distance) Given two arbitrary mass functions $m_{1}$ and $m_{2}$, $\{\!\!\{h_{i}^{(2)}\mid i\in[n]\}\!\!\}$ can derive $d_{c^{m_{1}},c^{m_{2}}}$.
- •
(Counting centers) $\{\!\!\{h_{i}^{(2)}\mid i\in[n]\}\!\!\}$ can derive $\mathds{1}_{|\mathcal{A}^{\text{set}}(P)|=1}$.

This proposition essentially extends the Barycenter Lemma in Delle Rose et al. [], Li et al. [] to the general case of centers defined by $\mathcal{D}$ features. Such information can enable DisGNN to obtain many global geometric features, facilitating it to distinguish non-isomorphic point clouds. Moreover, the ability to count centers is crucial for DisGNN to distinguish any point cloud that is not $\mathcal{A}$-symmetric from a $\mathcal{A}$-symmetric one, thereby achieving "identifiability". Now we give the formal proof.

###### Proof.

###### Proposition E.3 .

###### Proof.

###### Lemma E.4 .

###### Proof.

##### Node-center distance

We first denote the weighted distance profile of node $i$ as $f(m,i)$, which is defined as $f(m,i)=\sum_{j\in[n]}m(x^{\mathcal{A}}_{j})d_{ij}^{2}$. According to the aggregation scheme of DisGNN, $f(m,i)$ can be derived from $h^{(1)}_{i}$, since when $m$ is given: $h^{(1)}_{i}\to(h^{(0)}_{i},\{\!\!\{(h^{(0)}_{j},d_{ij})\mid j\in[n]\}\!\!\})
\to\{\!\!\{(x^{\mathcal{A}}_{j},d_{ij})\mid j\in[n]\}\!\!\}\to\sum_{j\in[n]}m(
x^{\mathcal{A}}_{j})d_{ij}^{2}$. All the $\to$ here hold because we assume that DisGNN uses injective function forms and parameterizations (thereby resulting in no information loss), and $j\in[n]$ since DisGNN treats point clouds as fully connected distance graphs, as mentioned at the beginning of the main body.

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

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

where $M=\sum_{j\in[n]}m(x^{\mathcal{A}}_{j})$ and $\langle\rangle$ denotes the inner product.

By definition of $c^{m}$, $\sum_{j\in[n]}m(x^{\mathcal{A}}_{j})(p_{j}-c^{m})=0$. Therefore, we have:

$$ $f(m,i)=M\|p_{i}-c^{m}\|^{2}+\sum_{j\in[n]}m(x^{\mathcal{A}}_{j})\|p_{j}-c^{m} \|^{2}$ $$

Therefore, the distance from $i$ to $c^{m}$ can be calculated as:

$$ $\displaystyle\frac{1}{M}\left(f(m,i)-\frac{1}{2M}\sum_{j\in[n]}m(x^{\mathcal{A }}_{j})f(m,j)\right)$ $\displaystyle=||p_{i}-c^{m}||^{2}=d_{i,c^{m}}^{2}$ (4) $$

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^{\mathcal{A}}_{j}),f(m,j))\mid j\in[n]\} \!\!\}),$ (5) $$

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

##### Center-center distance

Based on the conclusion of Node-center distance, at round 2, each node is aware of its distance to the two centers defined by $m_{1}$ and $m_{2}$:

$$ $\displaystyle h_{i}^{(2)}\to(d_{i,c^{m_{1}}},d_{i,c^{m_{2}}}).$ (6) $$

Therefore,

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

.

Therefore, the multiset of all node representations at round 2 can derive the distance between the two centers:

$$ $\displaystyle\{\!\!\{h_{i}^{(2)}\mid i\in[n]\}\!\!\}$ $\displaystyle\to\{\!\!\{(h_{i}^{(2)},m_{1}(x^{\mathcal{A}}_{i}))\mid i\in[n]\} \!\!\}$ $\displaystyle\to\frac{1}{M_{1}}\sum_{i\in[n]}m_{1}(x^{\mathcal{A}}_{i})\langle -c^{m_{1}}+c^{m_{2}},2p_{i}-c^{m_{1}}-c^{m_{2}}\rangle$ $\displaystyle=\langle-c^{m_{1}}+c^{m_{2}},\big{(}\frac{2}{M_{1}}\sum_{i\in[n]} m_{1}(x^{\mathcal{A}}_{i})p_{i}\big{)}-c^{m_{1}}-c^{m_{2}}\rangle$ $\displaystyle=\langle-c^{m_{1}}+c^{m_{2}},2A^{m_{1}}-c^{m_{1}}-c^{m_{2}}\rangle$ $\displaystyle=\langle-c^{m_{1}}+c^{m_{2}},c^{m_{1}}-c^{m_{2}}\rangle$ $\displaystyle=-||c^{m_{1}}-c^{m_{2}}||^{2},$ (7) $$

where $M_{1}=\sum_{i\in[n]}m_{1}(x^{\mathcal{A}}_{i})$.

##### Counting centers

In this case, we are not given any specific mass function $m$. It seems like we need to iterate all possible mass functions to determine the number of centers, which is infeasible due to the infinite number of mass functions. However, thanks to Proposition B.5, we can determine whether $\mathcal{A}^{\text{set}}(P)$’s cardinality is 1 (i.e., whether $P$ is $\mathcal{A}$-symmetric) by checking whether the geometric centers of all corresponding sub point clouds coincide with each other.

Now, assume that there are $K$ types of node features in $X^{\mathcal{A}}$, and we use $m_{k}$ to represent the mass function that maps all $x^{\mathcal{A}}_{i}$ to 1 if $x^{\mathcal{A}}_{i}=X^{*}_{k}$ and 0 otherwise, and use $m_{c}$ to represent the mass function that maps all $x^{\mathcal{A}}_{i}$ to 1.

Based on the conclusion of center-center distance part, we know that $\{\!\!\{h_{i}^{(2)}\mid i\in[n]\}\!\!\}$ can derive the distance between $c^{m_{c}}$ to all $c^{m_{k}}$, $k\in[K]$, i.e., $\{\!\!\{h_{i}^{(2)}\mid i\in[n]\}\!\!\}\to\{d_{c^{m_{c}},c^{m_{k}}}\mid k\in[K]\}$. We can easily check the cardinality of the set $\{d_{c^{m_{c}},c^{m_{k}}}\mid k\in[K]\}$ to determine whether the geometric centers of all these $K$ sub point clouds coincide, and according to Proposition B.5, this is equivalent to determining whether $|\mathcal{A}^{\text{set}}(P)|=1$.

Therefore, $\{\!\!\{h_{i}^{(2)}\mid i\in[n]\}\!\!\}\to\mathds{1}_{|\mathcal{A}^{\text{set}
}(P)|=1}$.
∎

Notice that DisGNN can itself calculate $\mathcal{C}$ and $\mathcal{D}$ feature, therefore, it can simply take unlabeled point clouds as input, and eventually is able to learn distance information related to all centers in set $\mathcal{D}^{\text{set}}(P)$. This is concluded in the following corollary:

###### Corollary E.5 .

Given an unlabelled point cloud $P\in\mathbb{R}^{n\times 3}$. DisGNN can derive the "node-center", "center-center" and "center count" information defined in Lemma E.4 w.r.t. center sets $\mathcal{A}^{\text{set}}(P)$ after $k$ rounds, where $\mathcal{A}$ and $k$ can be:

- •
$\mathcal{A}=\text{NULL}$, $k=2$. In such case, $\mathcal{A}^{\text{set}}(P)$ contains only the geometric center of $P$.
- •
$\mathcal{A}=\mathcal{C}$, $k=4$.
- •
$\mathcal{A}=\mathcal{D}$, $k$’s upper bound is $(n+2)$ ($n$ means that we need to first ensure that DisGNN stabilizes).

In the case of where $\mathcal{A}$ is NULL, the conclusion degenerates to the Barycenter Lemma in Delle Rose et al. [], Li et al. [].

We now give an essential lemma. In previous work [, ], it has been shown that DisGNN is E(3)-incomplete, i.e., there exist pairs of non-isomorphic point clouds that DisGNN cannot distinguish. This essentially means that we cannot prove that DisGNN’s output $s$ can derive the point cloud $P$ up to permutation and Euclidean isometry. However, in the following lemma and corollary, we will show that, if we restrict the underlying space $\mathbb{P}$ to be all point clouds that are not $\mathcal{A}$-symmetric
for arbitrary $\mathcal{A}$ algorithm, we can prove that DisGNN’s output can derive the input point cloud up to permutation and Euclidean isometry. This implies that DisGNN is complete on such subspaces.

###### Lemma E.6 .

Given a point cloud $P\in\mathbb{R}^{n\times 3}_{\text{not }\mathcal{A}}$ with node features calculated by algorithm $\mathcal{A}$, $X^{\mathcal{A}}$, where $\mathbb{R}^{n\times 3}_{\text{not}\mathcal{A}}$ contains all $\mathcal{A}$-unsymmetric point clouds in $\mathbb{R}^{n\times 3}$. Then, $4$-round DisGNN’s output $s$ can derive $P$ up to permutation and Euclidean isometry.

###### Proof.

By definition of "derive", we describe the reconstruction function that takes DisGNNs’ output $s$ as input and produces the point cloud $P$ up to permutation and Euclidean isometry. 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.

Since $P$ is not $\mathcal{A}$-symmetric, there are at least two centers in $\mathcal{A}^{\text{set}}(P)$. We now take two arbitrary such centers and denote them as $c_{1}$ and $c_{2}$. According to Corollary E.5, $2$-round DisGNN’s node-level features can derive the distance information related to these two centers, namely, $h^{(2)}_{i}\to(d_{i,c_{1}},d_{i,c_{2}},d_{c_{1},c_{2}})$. In the following, we show how DisGNN can reconstruct the whole geometry based on triangular distance encoding.

By defnition of DisGNN and the injectivity assumption, its output $s$ can derive the multiset $\{\!\!\{h_{i}^{(4)}\mid i\in[n]\}\!\!\}$. And since $h_{i}^{(4)}\to h_{i}^{(3)}\to h_{i}^{(2)}\to(d_{i,c_{1}},d_{i,c_{2}},d_{c_{1},
c_{2}})$, we know that from $h_{i}^{(4)}$ we can reconstruct the triangle formed by $i,c_{1},c_{2}$. Consequently, it is feasible to determine the following dihedral angle list from $h_{i}^{(4)}$:

$$ $\displaystyle h_{i}^{(4)}$ $\displaystyle=\text{HASH}(h_{i}^{(3)},\{\!\!\{(h_{j}^{(3)},d_{ij})\mid j\in[n] \}\!\!\})$ $\displaystyle\to\{\!\!\{(h_{i}^{(3)},h_{j}^{(3)},d_{ij})\mid j\in[n]\}\!\!\}$ $\displaystyle\to\{\!\!\{(h_{i}^{(2)},h_{j}^{(2)},d_{ij})\mid j\in[n]\}\!\!\}$ $\displaystyle\to\{\!\!\{(d_{ij},d_{i,c_{1}},d_{i,c_{2}},d_{j,c_{1}},d_{j,c_{2} },d_{c_{1},c_{2}})\mid j\in[n]\}\!\!\}$ $\displaystyle\to\{\!\!\{\theta(ic_{1}c_{2},jc_{1}c_{2})\mid j\in[n]\}\!\!\}.$ $$

Here, $\theta(ic_{1}c_{2},jc_{1}c_{2})$ represents the dihedral angle formed by plane $ic_{1}c_{2}$ and plane $jc_{1}c_{2}$. If $i$ or $j$ lies on the line $c_{1}c_{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}^{(4)}\mid i\in[n]\}\!\!\}$ to find the node $x$ which can derive the smallest $\theta(xc_{1}c_{2},yc_{1}c_{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}^{(4)}$. And note that since $\theta(xc_{1}c_{2},yc_{1}c_{2})$ is derived from $(h_{x}^{(4)},h_{y}^{(3)},d_{xy})$, the corresponding $(h_{y}^{(3)},d_{xy})$ in the calculation of $h_{x}^{(4)}$ can also be recorded. We now aim to prove that the entire geometry can be reconstructed using $h_{x}^{(4)}$ and the corresponding $(h_{y}^{(3)},d_{xy})$.

First of all, having found the node $y$ in the multiset, we can calculate the exact 3D coordinates of nodes $x,y,c_{1},c_{2}$ up to Euclidean isometry given $(h_{x}^{(4)},h_{y}^{(3)},d_{xy})$. This is because $(h_{x}^{(4)},h_{y}^{(3)},d_{xy})\to(d_{xy},d_{x,c_{1}},d_{x,c_{2}},d_{y,c_{1}}
,d_{y,c_{2}},d_{c_{1},c_{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}^{(4)}$ by definition. For each node $j$, with information $(h_{x}^{(1)},h_{j}^{(1)},d_{xj})$, we can derive $(d_{jx},d_{j,c_{1}},d_{j,c_{2}})$. Consequently, we can determine the 3D coordinates of $j$ to at most two positions, which are symmetrically mirroring w.r.t. the plane $xc_{1}c_{2}$. Notably, $j$’s position is unique if and only if it lies on the plane $xc_{1}c_{2}$ (denoted as $x$-plane). We first identify all nodes on the $x$-plane, since their calculated positions are unique.

Additionally, from $h_{y}^{(3)}$, we can also derive $(d_{jy},d_{j,c_{1}},d_{j,c_{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_{xc_{1}c_{2},yc_{1}c_{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}^{(4)}$, as their another possible position calculated by $h_{x}^{(4)}$ 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}^{(3)}$. 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 point cloud degenerates into 2D, we can initially derive a node $i$’s representation $h_{i}^{(4)}$ from the output $s$ of DisGNN that does not lie on the line $c_{1}c_{2}$. By leveraging $h_{i}^{(4)}$, we can extract the necessary distance information to compute the coordinates of $i$, $c_{1}$, and $c_{2}$ up to Euclidean isometry. Given that $h_{i}^{(4)}\to\{\!\!\{(h_{j}^{(3)},d_{ij})\mid j\in[n]\}\!\!\}$, we can derive $(d_{ij},d_{jA_{1}},d_{jA_{2}})$ from each $(h_{j}^{(3)},d_{ij})$. Consequently, the coordinates of node $j$ can be uniquely determined (2D setting). And therefore, the complete geometry can be reconstructed up to Euclidean isometry.

∎

As an insightful takeaway from Lemma E.6, we notice that the key in reconstruction is the initial triangular distance encoding that can be captured by DisGNN. The triangular distance encoding enhances each node $i$’s feature with distance information $(d_{ic_{1}},d_{ic_{2}},d_{c_{1}c_{2}})$, where $c_{1}$ and $c_{2}$ are two global anchors. In Lemma E.6, the two anchors are from $\mathcal{A}$ center sets, and DisGNN can capture the corresponding distance encoding according to Lemma E.4. In Section 4.1, we show that we can mark a node as an additional anchor, which can also be captured by DisGNN due to the distinct mark. Other designs may also be proposed by considering this insightful idea.

Similarly to Corollary E.5, DisGNN can take unlabelled point clouds as input and finally reconstruct them when the unlabelled point clouds are $\mathcal{C}$-unsymmetric or $\mathcal{D}$-unsymmetric.

###### Corollary E.7 .

Given a point cloud $P\in\mathbb{R}^{n\times 3}$, assume that $P$ is $\mathcal{A}$-unsymmetric. Then, $k$-round DisGNN’s output $s$ can derive $P$ up to permutation and Euclidean isometry, where $\mathcal{A}$ and $k$ can be:

- •
$\mathcal{A}=\mathcal{C}$, $k=6$.
- •
$\mathcal{A}=\mathcal{D}$, $k$’s upper bound is $(n+4)$.

Now, we are ready to prove Theorem 3.2 based on all the above propositions and theorems.

Theorem 3.2. *(Unsymmetric point clouds are identifiable) Let $\mathcal{A}$ be either center distance encoding $\mathcal{C}$ or DisGNN encoding $\mathcal{D}$. Then, given an arbitrary point cloud $P\in\mathbb{R}^{n\times 3}$, $P$ is not $\mathcal{A}$-symmetric $\Rightarrow$ $P$ can be identified by DisGNN.*

###### Proof.

It suffices to show that $P$ is not $\mathcal{D}$-symmetric $\Rightarrow$ $P$ can be identified by DisGNN by Proposition E.3.

Now, given another $P^{\prime}\in\mathbb{R}^{n\times 3}$, there are two cases:

- •
$P^{\prime}$ is not $\mathcal{D}$-symmetric. As a direct consequence of Lemma E.6 and Remark E.2, DisGNN can distinguish $P$ and $P^{\prime}$.
- •
$P^{\prime}$ is $\mathcal{D}$-symmetric. According to Lemma E.4 and Corollary E.5, DisGNN’s output for $P$ and $P^{\prime}$ can derive $\mathds{1}_{|\mathcal{D}^{\text{set}}(P)|=1}$ and $\mathds{1}_{|\mathcal{D}^{\text{set}}(P^{\prime})|=1}$ respectively. Since $P$ is not $\mathcal{D}$-symmetric while $P^{\prime}$ is, by definition, we know that $\mathds{1}_{|\mathcal{D}^{\text{set}}(P)|=1}\neq\mathds{1}_{|\mathcal{D}^{
\text{set}}(P^{\prime})|=1}$, and thus DisGNN can distinguish $P$ and $P^{\prime}$.

∎

###### Corollary E.5 .

###### Lemma E.6 .

###### Proof.

###### Corollary E.7 .

###### Proof.

### E.3 Proof of Theorem 4.2

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

- •
$N_{\text{in}}>=5$* and *$N_{\text{out}}>=0$ (where 0 0 indicates that the outer GNN only performs final pooling).
- •
*The distance graph is fully-connected (*$r_{\text{cutoff}}=+\infty$).
- •
*All subgraphs are the original graph (*$r_{\text{sub}}=+\infty$).

###### Proof.

Based on the condition that $r_{\text{sub}}=\infty$, all subgraphs are exactly the original distance graph, with the exception that the central node (the subgraph around which is generated) is explicitly marked.

We consider the GeoNGNN with exactly 5 inner layers and 0 outer layers, and since we assume the injectiveness of intermediate functions, more layers will only lead to no-worse expressiveness.

Now consider node $i$’s subgraph. We first assume that node $i$ is distinct to the geometric center $c$. We denote node $j$’s representation in subgraph $i$ using $h_{j}$ instead of $h_{ij}$ for brevity when the context is clear. We can now prove the following:

- 1.
After 1 round of DisGNN, for all $j\in[n]$, $h_{j}^{(1)}\to d_{ij}$ (since node $i$ is explictly marked in its subgraph).
- 2.
After 2 rounds of DisGNN, according to Lemma E.4, for all $j\in[n]$, $h_{j}^{(2)}\to d_{jc}$.
- 3.
After 3 rounds of DisGNN, for all $j\in[n]$, $h_{j}^{(3)}\to h_{i}^{(2)}\to d_{ic}$.

At this point, for all nodes $j$, $h_{j}^{(3)}$ can derive $d_{ji}$, $d_{jc}$, and $d_{ic}$, thus completing the triangular distance encoding necessary for reconstruction in Lemma E.6. Therefore, similar to the proof of Lemma E.6, with another two more rounds of DisGNN, the output can derive the point cloud up to permutation and Euclidean isometry.

- 4.
At round 5, the output of DisGNN w.r.t. the subgraph of node $i$, $s_{i}=f_{\text{output}}(\{\!\!\{h_{j}^{(5)}\mid j\in[n]\}\!\!\})$, can derive the point cloud up to permutation and Euclidean isometry.

There is still a potential problem with the above proof: node $i$ may coincide with the geometric center. In such case, we can not anymore obtain triangle distance information formed by each node $j$ and $i,c$, which is essential in Lemma E.6 for reconstruction. However, since $P$ has more than 2 nodes, there is at least one node that satisfies the assumption.

Notice that GeoNGNN injectively pools all the subgraph representations in the outer GNN and obtains the final output $s=f_{\text{outer}}(\{\!\!\{s_{i}\mid i\in[n]\}\!\!\})$. Each subgraph represnetation $s_{i}$ can derive the distence between node $i$ and the geometric center $c$ as following: $s_{i}\to h_{i}^{(5)}\to h_{i}^{(4)}\to...\to h_{i}^{(2)}\to d_{ic}$, according to Lemma E.4. This can be leveraged as an indicator, telling us whether node $i$ coincides with the $c$. As a consequence, we can derive the point cloud from $s$ as follows: first, search across all subgraph representations $s_{i}$ to find the one that does not coincide with the geometric center, then reconstruct the point cloud based on this subgraph representation according to Lemma E.6. This finishes the proof.

∎

###### Proof.

### E.4 Proof of Theorem 4.4

Theorem 4.4 *(Completeness for general geometric subgraph GNNs) Under the conditions specified in Theorem 4.2, all general geometric subgraph GNNs in Definition 4.3 with at least one local aggregation are E(3)-complete.
*

###### Proof.

We establish by demonstrating that all general geometric subgraph GNNs $\mathsf{GeoA}(\mathcal{A},\mathsf{Pool},L,r_{\text{sub}}=+\infty,r_{\text{
cutoff}}=+\infty)$, abbreviated as $\mathsf{GeoA}$ hereafter, are capable of implementing [] GeoNGNN (with $N_{\text{inner}}$ inner layers, $r_{\text{sub}}=+\infty,r_{\text{cutoff}}=+\infty$ and without outer GNN) – denoted as complete GeoNGNN – with a fixed number of layers $L$. Since complete GeoNGNN is E(3)-complete when $N_{\text{inner}}\geq 5$, $\mathsf{GeoA}$ can also achieve E(3)-completeness when $L$ is larger than some constant.

Two scenarios are considered: when $\mathsf{Geoagg}^{\mathsf{L}}_{\mathsf{u}}\in\mathcal{A}$ and when $\mathsf{Geoagg}^{\mathsf{L}}_{\mathsf{u}}\notin\mathcal{A}$.

In the scenario where $\mathsf{Geoagg}^{\mathsf{L}}_{\mathsf{u}}\in\mathcal{A}$, a single aggregation layer in $\mathsf{GeoA}$ can implement a complete GeoNGNN layer by learning an aggregation function $f^{(l)}$, defined in Section D, that only maintains $\mathsf{Geoagg}^{\mathsf{P}}_{\mathsf{u,v}}$ and $\mathsf{Geoagg}^{\mathsf{L}}_{\mathsf{u}}$ while disregarding other aggregation operations.

Notably, complete GeoNGNN utilizes VS pooling, while $\mathsf{Pool}$ in $\mathsf{GeoA}$ encompasses the options of VS or SV pooling. If $\mathsf{Pool}$ is VS, then consequently $\mathsf{GeoA}$ with $L=N_{\text{inner}}$ has the capability to implement complete GeoNGNN.

On the other hand, should $\mathsf{Pool}$ be SV, $\mathsf{GeoA}$ can deploy an additional aggregation layer in conjunction with SV pooling to implement VS pooling. In the following, we mainly elaborate on this simulation process.

First, it is crucial to note that SV pooling learns the global representation $h_{G}$ through the function $f^{\text{SV}}$ as follows:

$$ $h_{G}=f^{\text{SV}}(\{\!\!\{\{\!\!\{h^{(L_{\text{SV}})}_{uv}\mid u\in\mathcal{ V}_{G}\}\!\!\}\mid v\in\mathcal{V}_{G}\}\!\!\}),$ $$

and VS pooling learns through $f^{\text{VS}}$ in the subsequent manner:

$$ $h_{G}=f^{\text{VS}}(\{\!\!\{\{\!\!\{h^{(L_{\text{VS}})}_{uv}\mid v\in\mathcal{ V}_{G}\}\!\!\}\mid u\in\mathcal{V}_{G}\}\!\!\}).$ $$

With $L_{\text{SV}}=L_{\text{VS}}+1$, the last aggregation layer can be utilized to accumulate all subgraph information to the central node representation, i.e., $h^{(L_{\text{SV}})}(u,u)=h^{(L_{\text{VS}}+1)}(u,u)\to\{\!\!\{h^{(L_{\text{VS}
})}_{uv}\mid v\in\mathcal{V}_{G}\}\!\!\}$, given that $\mathsf{Geoagg}^{\mathsf{L}}_{\mathsf{u}}\in\mathcal{A}$. Notice that this is feasible since each subgraph is the original graph and is fully connected. Consequently:

$$ $\displaystyle\{\!\!\{\{\!\!\{h^{(L_{\text{SV}})}_{uv}\mid u\in\mathcal{V}_{G} \}\!\!\}\mid v\in\mathcal{V}_{G}\}\!\!\}$ $\displaystyle\to$ $\displaystyle\{\!\!\{h^{(L_{\text{SV}})}(v,v)\mid v\in\mathcal{V}_{G}\}\!\!\}$ $\displaystyle\to$ $\displaystyle\{\!\!\{\{\!\!\{h^{(L_{\text{VS}})}(v,u)\mid u\in\mathcal{V}_{G} \}\!\!\}\mid v\in\mathcal{V}_{G}\}\!\!\}$ $\displaystyle=$ $\displaystyle\{\!\!\{\{\!\!\{h^{(L_{\text{VS}})}_{uv}\mid v\in\mathcal{V}_{G} \}\!\!\}\mid u\in\mathcal{V}_{G}\}\!\!\},$ $$

indicating that $f^{\text{SV}}$ can acquire a function that initially converts $\{\!\!\{\{\!\!\{h^{(L_{\text{SV}})}_{uv}\mid u\in\mathcal{V}_{G}\}\!\!\}\mid v
\in\mathcal{V}_{G}\}\!\!\}$ to $\{\!\!\{\{\!\!\{h^{(L_{\text{VS}})}_{uv}\mid v\in\mathcal{V}_{G}\}\!\!\}\mid u
\in\mathcal{V}_{G}\}\!\!\}$, and subsequently emulates $f^{\text{VS}}$. Thus, $\mathsf{GeoA}$ with $L=N_{\text{inner}}+1$ has the capability to implement complete GeoNGNN.

Finally, consider the case where $\mathsf{Geoagg}^{\mathsf{L}}_{\mathsf{u}}\notin\mathcal{A}$. And since we assume the existence of at least one local operation, it follows that $\mathsf{Geoagg}^{\mathsf{L}}_{\mathsf{v}}\in\mathcal{A}$. By presenting a proposition that essentially underscores symmetry, we can affirm that this case is equivalent to the first case, and therefore the conclusion still holds.

###### Proposition E.8 .

Let $\mathsf{GeoA}$ be any general geometric subgraph GNN defined in Section D. Denote $\mathcal{A}^{\mathsf{u}\leftrightarrow\mathsf{v}}$ as the aggregation scheme obtained from $\mathcal{A}$ by exchanging the element $\mathsf{agg}^{\mathsf{P}}_{\mathsf{uu}}$ with $\mathsf{agg}^{\mathsf{P}}_{\mathsf{vv}}$, exchanging $\mathsf{Geoagg}^{\mathsf{L}}_{\mathsf{u}}$ with $\mathsf{Geoagg}^{\mathsf{L}}_{\mathsf{v}}$, and exchanging $\mathsf{agg}^{\mathsf{G}}_{\mathsf{u}}$ with $\mathsf{agg}^{\mathsf{G}}_{\mathsf{v}}$. Then, $\mathsf{GeoA}(\mathcal{A},\mathsf{VS},L,r_{\text{sub}},r_{\text{cutoff}})$ and $\mathsf{GeoA}(\mathcal{A}^{\mathsf{u}\leftrightarrow\mathsf{v}},\mathsf{SV},L,
r_{\text{sub}},r_{\text{cutoff}})$ can implement each other.

###### Proof.

Similar to the original proof of Proposition 4.5. in Zhang et al. [], the proof is almost trivial by symmetry: All functions within $\mathsf{GeoA}(\mathcal{A},\mathsf{VS})$ can inherently learn to ensure that $h^{(l)}_{uv}$ in $\mathsf{GeoA}(\mathcal{A},\mathsf{VS})$ precisely corresponds to $h^{(l)}(v,u)$ in $\mathsf{GeoA}(\mathcal{A}^{\mathsf{u}\leftrightarrow\mathsf{v}},\mathsf{SV})$ for any arbitrary $u,v,l$, with the reverse equivalence also holding. Additionally, given the symmetry of the pooling method, consistency in the output can be guaranteed.
∎

As a direct consequence of Proposition E.8, all of the general subgraph GNN with $\mathsf{Geoagg}^{\mathsf{L}}_{\mathsf{v}}$ can implement another one with $\mathsf{Geoagg}^{\mathsf{L}}_{\mathsf{u}}$, and according to the previous proof, they are also E(3)-complete under the conditions specified in Theorem. This ends the proof.

∎

###### Proof.

###### Proposition E.8 .

###### Proof.

### E.5 Proof of Theorem 4.5

Theorem 4.5 *(E(3)-Completeness of DimeNet, SphereNet, GemNet) When the following conditions are met, DimeNet, SphereNet(^5^55Here 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.*

- •
*The aggregation layer number is larger than some constant *$C$, which is irrelevant to the node number.
- •
*They initialize and update all edge representations, i.e., *$r_{\text{embed}}=+\infty$.
- •
*They interact with all neighbors, i.e., *$r_{\text{int}}=+\infty$.(^6^66In 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 main idea to prove this theorem is to also show that DimeNet, SphereNet and GemNet can implement [] GeoNGNN, which is E(3)-complete, and thus they are E(3)-complete as well. We elaborate on these models in separate subsections.

#### E.5.1 E(3)-completeness of DimeNet

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.

We formally state these procedures:

##### Initialization (DimeNet)

In DimeNet, the initial representation $h_{ij}$ of the edge $ij$ is initialized based on the tuple $(x_{i},x_{j},d_{ij})$, where $x_{i}$ and $x_{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}}(x_{i},x_{j},d_{ij})$ (8) $$

##### 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\mathcal{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\mathcal{N}(i)\}\!\!\}\right)$ $$

When the interaction cutoff of DimeNet is infinite, $\mathcal{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)$ (9) $$

##### 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]\}\!\!\})$ (10) $$

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}}(x_{j},d_{ij})$ (11) $$

##### 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]\}\!\!\})$ (12) $$

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]\}\!\!\})$ (13) $$

##### 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. 8) takes more information than $f_{\text{init}}^{\text{GeoNGNN}}$ (Eq. 11) as input. Therefore, by learning a function $f_{\text{init}}^{\text{DimeNet}}$ that simply disregards the $x_{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. 9) and $f_{\text{update}}^{\text{GeoNGNN}}$ (Eq. 12) 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}^{(l)}$, calculates $h_{ij}^{(l+\frac{1}{2})}$ to store the information of $h_{ji}^{(l)}$, i.e., $h_{ij}^{(l+\frac{1}{2})}\to h_{ji}^{(l)}$.
This is feasible due to the property that in Eq.9, $(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}^{(l+\frac{1}{2})},\{\!\!\{(d_{kj},h_{ki}^{(l+\frac{1}{2})})\mid k
\in[n]\}\!\!\}\big{)}$ into $\big{(}h_{ij}^{(l)},\{\!\!\{(d_{kj},h_{ik}^{(l)})\mid k\in[n]\}\!\!\}\big{)}$. At this stage, the function form aligns with that of $f_{\text{update}}^{\text{GeoNGNN}}$ (Eq.12).

Finally, we consider the output step. Similarly, the only distinction between $f_{\text{output}}^{\text{DimeNet}}$ (Eq.10) and $f_{\text{update}}^{\text{GeoNGNN}}$ (Eq.13) 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.

#### E.5.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}}(x_{i},x_{j},d_{ij})$ (14) $$

##### 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]\}\!\!\})$ (15) $$

##### 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]\}\!\!\})$ (16) $$

##### Implementing DimeNet with SphereNet

Now we show how to use SphereNet to implement DimeNet.

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

At the update step, $f_{\text{update}}^{\text{SphereNet}}$ (Eq. 15) takes strictly more information, i.e., the node representations, than $f_{\text{update}}^{\text{DimeNet}}$ (Eq. 9). 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. 16) and $f_{\text{output}}^{\text{DimeNet}}$ (Eq. 10) 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.

#### E.5.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)$ (17) $$

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

## Appendix F Supplementary experiment information

### F.1 Scaling to large graphs: MD22

A significant concern for geometric models is the scalability for larger point clouds. In this subsection, we evaluate GeoNGNN on MD22 [], a dataset with relatively large molecules (up to 370 atoms).

**Table 3: MAE loss on MD22. Energy (E) in meV/atom, force (F) in meV/Å. The best and the second best results are shown in bold and \ulunderline. 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 | Allegro | Equiformer | MACE | Vanilla Dis. | GeoNGNN |
|  |  | E | 0.4 | 0.121 | 0.116 | \ul0.105 | 0.106 | 0.064 | 0.158 | 0.106 |
| Ac-Ala3-NHMe | 42 | F | 34 | 10.0 | 8.1 | 4.6 | \ul3.9 | 3.8 | 9.5 | 4.9 |
|  |  | E | 1 | 0.089 | \ul0.093 | 0.089 | 0.214 | 0.102 | 0.281 | 0.105 |
| Docosahexaenoic acid | 56 | F | 33 | 5.9 | 5.2 | 3.2 | 2.5 | \ul2.8 | 11.3 | 3.8 |
|  |  | E | 2 | 0.076 | \ul0.069 | 0.124 | 0.078 | 0.062 | 0.077 | 0.091 |
| Stachyose | 87 | F | 29 | 10.1 | 8.3 | 4.2 | \ul3.0 | 3.8 | 4.1 | 2.9 |
|  |  | E | 0.52 | 0.121 | 0.139 | 0.103 | 0.109 | \ul0.079 | 0.085 | 0.073 |
| AT-AT | 60 | F | 30 | 10.3 | 8.8 | 4.1 | \ul4.3 | \ul4.3 | 8.463 | 5.8 |
|  |  | E | 0.52 | 0.097 | 0.193 | 0.145 | 0.055 | \ul0.058 | 0.082 | 0.078 |
| AT-AT-CG-CG | 118 | F | 31 | 16.0 | 20.4 | 5.6 | \ul5.4 | 5 | 13.8 | 8.1 |
|  |  | E | 0.34 | - | - | - | - | \ul0.141 | 0.158 | 0.113 |
| Buckyball catcher | 148 | F | 29 | - | - | - | - | 3.7 | 19.3 | \ul4.8 |
|  |  | E | 0.47 | - | - | - | - | 0.194 | 0.383 | \ul0.204 |
| Double-walled nanotube | 370 | F | 23 | - | - | - | - | \ul12 | 16.5 | 11.2 |
| AVG RANK | 6.86 | 5.40 | 5.30 | 3.50 | 3.00 | 1.79 | 4.57 | 2.93 |  |  |

As presented in Table 3, we can see that GeoNGNN outperforms DisGNN across almost all targets. It also 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, 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. This could be attributed to the invariant representation and the simple architecture GeoNGNN adopts.

**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 |  |  |

### F.2 Generalization on out-of-domain data: 3BPA

GeoNGNN has demonstrated remarkable expressiveness. However, higher expressiveness only implies a better capability to fit data, and whether this leads to improved inductive bias and generalization power remains uncertain. Therefore, we conducted further evaluations of GeoNGNN on the 3BPA dataset [], which includes lots of out-of-domain data in its test set, providing a good assessment of the generalization power of geometric models. The dataset comprises molecular dynamic simulations of the molecule 3-(benzyloxy)pyridin-2-amine, with the training set consisting of samples from the trajectory at 300K, and the test sets containing samples from trajectories at 300K, 600K, and 1200K.

**Table 5: Root-mean-square errors (RMSE) on 3BPA. Energy (E) in meV, force (F) in meV/Å. Standard deviations are computed over three runs.**
|  |  | NequIP | Allegro | MACE | GeoNGNN |
| --- | --- | --- | --- | --- | --- |
| 300K | E | 3.1$\pm$0.1 | 3.84$\pm$0.08 | 3$\pm$0.2 | 3.76$\pm$0.29 |
| F | 11.3$\pm$0.2 | 12.98$\pm$0.7 | 8.8$\pm$0.3 | 11.77$\pm$0.34 |  |
| 600K | E | 11.3$\pm$0.31 | 12.07$\pm$0.45 | 9.7$\pm$0.5 | 12.49$\pm$0.38 |
| F | 27.3$\pm$0.3 | 29.17$\pm$0.22 | 21.8$\pm$0.6 | 28.91$\pm$0.71 |  |
| 1200K | E | 40.8$\pm$1.3 | 42.57$\pm$1.46 | 29.8$\pm$1.0 | 44.82$\pm$0.88 |
| F | 86.4$\pm$1.5 | 82.96$\pm$1.77 | 62$\pm$0.7 | 89.62$\pm$1.58 |  |

Consistent with prior studies, we present the Root Mean Square Error for energy and force predictions, comparing GeoNGNN with MACE [], NequIP [], and Allegro []. The results are detailed in Table 5. GeoNGNN demonstrates competitiveness with Allegro, an equivariant model equipped with high-order tensors for learning local equivariant representations. However, when compared to the SOTA method MACE, GeoNGNN exhibits relatively worse performance, especially under higher temperatures, which signifies a greater distribution shift between the testing and training sets. This underscores that despite GeoNGNN’s strong theoretical expressiveness, its generalization power may lag behind that of those well-designed equivariant models. This discrepancy could potentially be attributed to the fact that GeoNGNN only adopts invariant representations, whereas equivariant representations could offer superior generalization abilities, particularly in sparse graph cases, as demonstrated in Du et al. []. Therefore, future research could focus on improving GeoNGNN’s generalization abilities by integrating additional equivariant representations, like the vectors used in [, ], or higher-order tensors applied in [].

### F.3 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 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 6. 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.

Figure: Figure 6: 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/Å.
Refer to caption: x7.png

## Appendix G Experiment settings

### G.1 Dataset settings

##### Synthetic dataset

We generate the synthetic dataset by implementing the counterexamples proposed by Li et al. [].

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

Figure: Figure 7: Selected counterexamples in the synthetic dataset. Only colored nodes belong to the point clouds. The grey nodes and “edges" are for visualization purposes only. (a) One isolated case. (b) One combinatorial case.
Refer to caption: x9.png

The 10 isolated cases comprise the following: 6 pairs of point clouds 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 point clouds sampled from regular dodecahedrons and 1 pair from icosahedrons, using the method outlined in Theorem A.1 of Li et al. []. When augmenting the base point cloud, 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 point clouds in the dataset to be fully connected.

##### rMD17 and MD22

The data split (training/validation/testing) in rMD17 is 950/50/the rest, following related works such as Batatia et al. [], Gasteiger et al. []. For MD22, we adopt the data split specified in Chmiela et al. [], 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 NequIP [], GemNet [], are sourced from Musaelian et al. []. The result of PaiNN [] is sourced from Batatia et al. []. The results of 2-F-DisGNN [] and MACE [] are reported by their original papers. We trained and evaluated DimeNet [] using its implementation in Pytorch Geometric [] since the original paper did not report results on this dataset, and we use the default parameters (We find that the default parameters produce the best performance).

In MD22, the results of sGDML and MACE [] are sourced from Kovacs et al. []. The results of PaiNN [], TorchMD-Net [], Allegro [], and Equiformer [] are obtained from the work presented by Li et al. [].

##### 3BPA

Following Batatia et al. [],we split the training set and validation set at a ratio of 450/50, utilizing pre-split test sets for evaluation. We use a batch size of 4, an identical objective function to that in rMD17 and MD22, and a force ratio of 0.999 were employed. The results of all other models are sourced from Batatia et al. [].

### G.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. [], Li et al. []. We use the same expnorm RBF function as Li et al. [], defined as

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

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

##### DisGNN

In each stage of the DisGNN, we augment its expressiveness and experimental performance by stacking dense layers or residual layers DisGNN’s architecture is described in Figure 8.

Figure: Figure 8: Architecture of 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 (pre-activation). $\odot$ represents Hadamard product.
Refer to caption: x10.png

We set the number of VD-Conv layers to 7 for rMD17 and 6 for MD22. 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=6$, as proposed in Gasteiger et al. [], along with the corresponding cutoff.

##### GeoNGNN

The high-level architecture of GeoNGNN is described in Definition 4.1. The inner DisGNN, which runs on the ego subgraph of each node, is similar to the DisGNN block shown in Figure 8. However, the inner 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})))$ (19) $$

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

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

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

The hidden dimension and message passing cutoff are set to the same values as those in DisGNN. The subgraph size is set to 13 Å for rMD17, 5 Å for MD22 and 6 Å for 3BPA, and the maximal subgraph size is set to 25. We set $(N_{\text{in}},N_{\text{out}})$ as $(5,2)$ for rMD17, $(3,3)$ for MD22 and $(6,2)$ for 3BPA. It is worth mentioning that the total number of convolutional layers is the same as that of 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 [], 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 4090 and Nvidia A100 (80GB) GPUs. For rMD17, training hours for each molecule range from 20 to 70. For MD22, the training hours ranged from 35 to 150 on Nvidia 4090 for all molecules except Stachyose (due to longer convergence time) and Double-walled nanotube (the largest molecule necessitating an A100), which required about 210 and 70 GPU hours on the Nvidia 4090 and 80GB A100, respectively. For 3BPA, the training hours is around 10 GPU hours on Nvidia 4090.

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

### H.1 Definition and theoretical analysis of GeoNGNN-C

In certain chemical-related scenarios, it is important to guarantee that the outputs of models exhibit invariance under permutations, transformations, and rotations of point clouds, while exhibiting differentiation when the point cloud undergoes mere reflection. This distinction is crucial as pairs of enantiomers, may demonstrate vastly contrasting properties, such as binding affinity. In this section, we propose the SE(3)-complete invariant of GeoNGNN, which is capable of embracing chirality and producing complete representations for downstream tasks.

Generally speaking, GeoNGNN-C is designed by simply replacing the undirected distance in GeoNGNN with the directed distance. The formal definition is:

###### Definition H.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_{ki}^{(l+1)}=f_{\rm mp}(h_{ki}^{(l)},\{\!\!\{(h_{kj}^{(l)},d_{k,ij})\mid j \in N_{k}(i)\}\!\!\}),$ $$

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

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

where $c$ is the geometric center of the point cloud.

As can be easily validated, directed distance is invariant under SE(3)-transformation while undergoing a sign reversal after reflecting the point cloud. 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 H.2 .

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

###### Proof.

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 DisGNN (i.e., the DisGNN that incorporates the directed distance as a geometric representation as described in Definition H.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 triangular distance encoding necessary for reconstruction in Lemma E.6.

Next, we employ a modified version of the proof from Lemma E.6 to demonstrate that with an additional two rounds of the Chiral DisGNN, we can derive the SE(3)- and permutation-invariant identifier of the point cloud $P$.

In the proof of Lemma E.6, we first search across all the nodes to find two nodes $a$ and $b$ that form the minimal dihedral angles $\theta(aic,bic)$, and then identifies the coordinates of $a,b,i,c$ up to Euclidean isometry from the all-pair distances $D=\{(m,n,d_{mn})\mid m,n\in\{a,b,i,c\}\}$. However, since Chiral 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 (i.e., Euclidean isometry without reflection) from $D_{i}$ in the following way:

- 1.
Fix $x_{i}=(0,0,0)$.
- 2.
Fix $x_{c}=(d_{ic},0,0)$.
- 3.
Fix $x_{a}$ in plane $xOy+$ and calculate its coordinates using $d_{ia},d_{ca}$.
- 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 Lemma E.6 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.

∎

###### Definition H.1 .

###### Theorem H.2 .

###### Proof.

### H.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 [, ]: 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. [].

##### 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 [, ] for fair comparisons.

**Table 6: 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 |

##### Models to compare with

We compare GeoNGNN-C against previous high-performance models, SphereNet [], ChiRo [], ChiENN [], and other baseline models in [, , ]. 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. []. 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 [], Tetra-DMPNN [] and ChiENN [], 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 6. 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.

## Peer Reviews

confidence: 3
contribution: 4
initial_rating: 5
presentation: 2
questions: Please address the concerns I raised in the weaknesses section. Additionally, I recommend revising the introduction to better reflect the paper's contributions. In my view, the primary contribution is the proposal of the geometric counterpart of NGNN and the proof that this approach effectively resolves the limitation of DisGNN in identifying **symmetric point clouds when the graphs are even fully connected**. 
The authors should also consider relevant experiments in this direction to emphasize the novelty and significance of this work.
soundness: 2
strengths: - The paper attempts to address a crucial problem that enhances our understanding of the potential of invariant neural networks and can guide future model design.
- Investigating the geometric counterparts of subgraph GNNs is a novel contribution.
- The results extend beyond specific cases, such as asymmetric point clouds, broadening our understanding of how these models perform on symmetric point clouds as well.
summary: This paper explores the geometric completeness of a significant class of geometric deep learning models: invariant neural networks. These networks leverage invariant features to impose strong inductive biases on spatial information, yet their theoretical expressive power remains somewhat unclear. This study aims to bridge that gap, enhancing both our theoretical understanding and practical application of these models.

The authors first demonstrate that incorporating distance into message-passing neural networks (like DisGNN) allows for the identification of asymmetric point clouds but struggles with highly symmetric ones. They then investigate geometric extensions of subgraph-based GNNs and prove that these models, specifically GeoNGNN, can successfully distinguish symmetric point clouds, achieving E(3)-completeness.
weaknesses: - The paper lacks clarity and structure in some areas. The detailed explanation of NGNN, which serves as the backbone of their main contribution, the GeoNGNN framework, is left in the appendix. I recommend the authors integrate key aspects of NGNN, such as its core equations or an architectural diagram, into the main text. Additionally, including a comparison with the original DisGNN would be helpful—highlighting the differences and explaining what enables NGNN (intuitively) to overcome the limitations of DisGNN. This would give readers a clearer understanding of how the proposed approach builds on previous work and addresses specific challenges without disrupting the flow. Instead, a brief overview of NGNN, along with key formulas and a comparison with GNN, could benefit the flow of the whole paper.

- The results are primarily constrained to cases with global connectivity, which is often impractical in real-world applications due to the significant computational costs. Several studies [1], [2], [3], [4] have explored scenarios where the graph is not fully connected, underscoring the need to evaluate the performance of invariant neural networks in sparse graph settings. In practice, invariant neural networks tend to perform worse than equivariant ones in these cases. While the authors have left these cases in the future direction, it would greatly strengthen the paper if they could extend their analysis to sparse graphs or at least discuss how their completeness results may vary with different levels of graph sparsity. Providing theoretical bounds on performance degradation as connectivity decreases would also be valuable.

- The experimental results, while showing some improvement, are relatively marginal, which limits the empirical impact of the work. I suspect this might be due to the sparsity of the graphs used in practical applications. The authors should aim to demonstrate the significance of their approach by clarifying in which specific cases their method outperforms existing methods. Providing examples or scenarios where GeoNGNN has a clear advantage would strengthen the empirical contributions.


[1] Wang, L., Liu, Y., Lin, Y., Liu, H., & Ji, S. (2022). ComENet: Towards complete and efficient message passing for 3D molecular graphs. Advances in Neural Information Processing Systems, 35, 650-664.
[2] Joshi, C. K., Bodnar, C., Mathis, S. V., Cohen, T., & Lio, P. (2023, July). On the expressive power of geometric graph neural networks. In International Conference on Machine Learning (pp. 15330-15355). PMLR.
[3] Wang, S. H., Hsu, Y. C., Baker, J., Bertozzi, A. L., Xin, J., & Wang, B. (2024). Rethinking the benefits of steerable features in 3D equivariant graph neural networks. In The Twelfth International Conference on Learning Representations, ICLR
[4] Sverdlov, Y., & Dym, N. (2024). On the Expressive Power of Sparse Geometric MPNNs.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 1
questions: 1) The excessive use of bold text and the absence of a clear outline make the paper’s contributions difficult to discern. Could the authors consider restructuring the introduction for better clarity?

2) I find that the statements in the section **Theoretical Characterization vs Practical Use** rely on the example C.2. How increasing the sparsity beyond this simple example is understudied despite the authors strong claims that relaxing the fully-connected condition leads to better expressiveness of GeoNGNN compared to DisGNN.

3) There is no supporting evidence for GeoNGNN over existing architectures in the primary paper. Additionally, there is no comparative analysis involving node feature information generated by a complete invariant function. Could the authors address this gap?

4) A significant portion of the QM9 dataset consists of non-symmetric structures. What are the proportions of indistinguishable data restricted to the subset of QM9 that includes only symmetric structures?

5) In the QM9 noise study, the significant reduction in non-distinguishable point clouds occurs near what appears to be the level of reported error in the QM9 dataset. Given the reported error of 0.1Å, how is this error rescaled based on the applied scaling coefficient? 

6) Distinguishing structures on QM9, which lacks conformers, does not seem to be as important as datasets which contain conformers or very nearly isomorphic point clouds.The most compelling analysis appears to come from the study of MD17 but with mixed results. GeoNGNN appears to do particularly well on Benzene which is highly symmetric. How does Benzene behave under the noise tolerance study?

7) Typically, ModelNet40 is sampled to avoid handling large point clouds. It is unclear from the text whether the entire mesh or a sampled version is used. If sampled uniformly, there is no guarantee that the symmetries are preserved. Could the authors clarify this in the text?

8) The selection of ModelNet40 does not seem to rigorously test the theoretical claims of the paper, which focus on nearly isomorphic point clouds. Could the authors provide more rigorous testing on datasets that better align with their theoretical focus?

9) It is unclear from the text and appendix what each structure in the synthetic dataset represents, how these structures were constructed, and why they are significant. Could the authors provide more detailed explanations on the construction and relevance of these synthetic structures?
soundness: 3
strengths: The paper introduces a novel conceptual framework for understanding the efficacy of certain invariant architectures. This is further supported through theoretical analysis and empirical studies. Additionally, it proposes a framework for the development of future architectures extending the impact and significance of the work.
summary: The paper offers the following contributions:
1) Introduces and defines the notion of "Identify" for invariant GNNs, positioned between distinguishability and completeness.
2) Provides a characterization for the incompleteness of DisGNN
3) Proposes GeoNGNN to ensure indentification of the cases where DisGNN is incomplete
4) Demonstrates that several established invariant GNNs are capable of completeness
weaknesses: The paper lacks sufficient empirical evidence to support its theoretical analysis, significantly reducing the overall significance and impact of the work. The selected real world experiments emphasize datasets which lack conformers or nearly isomorphic point clouds. Furthermore, the main text does not provide adequate evidence to demonstrate the advantages of GeoNGNN over the existing complete invariant architectures.

Additionally, the excessive use of bold text and the absence of a clear outline in the introduction make it challenging to follow and clearly understand the contributions of the paper.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 2
questions: - How does this method for expressivity generalize to different types of architectures? To the reviewer it seems that this method for showing is very specific and would be difficult to generalize to other types of equivariant architectures acting on point clouds.
soundness: 3
strengths: The authors have provided both extensive proofs as well as extensive analysis
to their claims. Overall the presentation and intend is clear and definitions
are well-thought out and the authors provide a good heuristic insight with each
introduced theorem and definition which is nice. The extensive analysis of both
DisGNN and GeoNGNN shows that the work is of good quality and looks to be of
good quality to the reviewer. All theorems come with extensive proofs and with
a intuition which is helpful for the non-mathmatical audience. The quality of
the content, such as originality and potential impact, is harder to asses since
the reviewer is not familiar expressivity research.
summary: The authors of the paper prove that certain families of models are not only
invariant with respect to the Euclidian group and permutation group, but also
that classes of models distinguish the orbits of $\mathbb{R}^3$ under the
action of $E(3)$. An extended analysis of the expressivity of DisGNN is
provided and it is shown that this network architecture is nearly $E(3)$
complete. As a last contribution an analysis is provided for various families
of neural networks and conditions are provided under which they are
$E(3)$-complete. The   theoretical   results   are   verified   by experiments
on  the QM9  dataset  and  a synthetic  dataset  with designed edge cases.
weaknesses: To the reader it seems that some of the definitions are somewhat convolved and
some simplification and clarity in the definitions might improve reading. Some
of the definitions, while they might be customary in the machine learning
literature, are somewhat unfortunately choses from a mathematical perspective.
Completeness of a space in the mathematical sense implies that each Cauchy
sequence has a limit within that space. A second example is the use of the term
isomorphism. While not wrong, a better phrasing is to say that the two point
cloud lie in the same orbit with respect to the action of the Euclidian group
acting on the tensor product of copies of $\mathbb{R}^3$. The current phrasing
might be better if is more in line with terminology used in machine learning.

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 3
questions: I have two questions.

1. Do you have any insight on achieving E(3)-completeness for frame-based approaches?

2. Can you comment on achieving E(3)-completeness by using node features beyond pairwise distances, e.g., dihedral angles?
soundness: 2
strengths: The paper symmetrically studies the problem of E(3)-completeness geometric graph neural networks.
summary: This paper studies the expressiveness power of message-passing neural networks incorporating pairwise distance between graph nodes, showing the near E(3)-completeness. Furthermore, the authors study the subgraph graph neural networks, which can achieve E(3)-completeness. Therefore, it is possible to make DimeNet, GemNet, and SphereNet to achieve E(3)-completeness.
weaknesses: The work is based on global connectivity assumption, and this assumption significantly limits this work. Also, the experimental results seem to be quite weak.

Meta-review: This paper analyzes the theoretical expressive power of invariant geometric deep learning models, focusing on their ability to represent point cloud geometry under fully-connected conditions. It establishes that DisGNN (message-passing neural networks incorporating distance) is limited only by highly symmetric point clouds and demonstrates that GeoNGNN ( the geometric counterpart of one of the simplest subgraph graph neural networks) achieves E(3)-completeness, resolving these cases. The work further shows that other models like DimeNet, GemNet, and SphereNet can also achieve E(3)-completeness. These results enhance the understanding of invariant models' capabilities, bridging the gap between theoretical expressiveness and practical applications.

One of the main criticism, shared by reviewers, was targeted toward the clarity of exposition of this work. Authors provided revisions of their text, that was in general approved and acknowledged by reviewers. The scores are consistently given as borderline accept. After reading the paper, I believe that the contributions are above the threshold for a publication at ICLR, and I recommend an accept. Nevertheless, I strongly encourage authors to thoroughly take into account the reviewers remarks regarding the final version of their paper.

Decision: Accept (Poster)