On the Expressive Power of Sparse Geometric MPNNs
Authors: Yonatan Sverdlov
Nadav Dym
Venue: ICLR 2025 Poster (2025)
Keywords: WL
GWL
GNNS
geometric GNNS
point clouds
completness
Primary area: learning on graphs and other geometries & topologies
TL;DR: The expressvness power of 1-GWL test.

Abstract: Motivated by applications in chemistry and other sciences, we study the expressive
power of message-passing neural networks for geometric graphs, whose node
features correspond to 3-dimensional positions. Recent work has shown that such
models can separate generic pairs of non-isomorphic geometric graphs, though they
may fail to separate some rare and complicated instances. However, these results
assume a fully connected graph, where each node possesses complete knowledge
of all other nodes. In contrast, often, in application, every node only possesses
knowledge of a small number of nearest neighbors.
This paper shows that generic pairs of non-isomorphic geometric graphs can
be separated by message-passing networks with rotation equivariant features as
long as the underlying graph is connected. When only invariant intermediate
features are allowed, generic separation is guaranteed for generically globally
rigid graphs. We introduce a simple architecture, EGENNET, which achieves our
theoretical guarantees and compares favorably with alternative architecture on
synthetic and chemical benchmarks

Published as a conference paper at ICLR 2025
ON THE EXPRESSIVE POWER OF SPARSE GEOMETRIC MPNNS
Yonatan Sverdlov', Nadav Dym 1.2
Faculty of Mathematics
2 Faculty of Computer Science
Technion - Israel Institute of Technology
yonat (aaassecammuaa technion. ac.il
ABSTRACT
Motivated by applications in chemistry and other sciences, we study the expressive power of message-passingg neural networks for geometric graphs, whose node features correspond to 3-dimensional positions. Recent work has shown that such models can separate generic pairs of non-isomorphic geometric graphs, though they may fail to separate some rare and complicated instances. However, these results assume fully connected graph, where each node possesses complete knowledge of all other nodes. In contrast, often, in application, every node only possesses knowledge of a small number nearest neighbors.
This paper shows that generic pairs of non-isomorpar non-isomorphic geometric graphs can be separated by message-passing networks with rotation equivariant features as long as the underlying graph is connected. When only invariant intermediate features are allowed, generic separation is guaranteed for generically globally rigid graphs. We introduce simple architecture, EGENNET, which achieves our theoretical guarantees and compares favorably with alternative architectures on synthetic and chemical benchmarks. Our code is available at GitHub
INTRODUCTION
Geometric graphs are graphs whose nodes are a 'position' vector R.d (typically 3) and whose symmetries include the permutation symmetries of combinatorial graphs and translation and rotation of the node positions. Geometric graphs arise naturally in learning applications for chemistry, physical dynamics, and computer vision natural models for molecules, particle systems, and 3D point clouds. These applications motivated the introduction of many learning models for geometric graphs, which were often inspired by 'standard' graph neural networks (GNNs) for combinatorial graphs (Saoorras et al. [021 Han et al., 20024; Gasteiger et al.) 2021). Subsequently, several theoretical works aimed primarily at understanding the expressive power and limitations of GNNs for geometric graphs.
GNNs for geometric graphs produce global graph features invariant geometric graph symmetries. The expressive power of GNNs is typically assessed primarily by their ability to assign different global features pairs of geometric graphs that are not geometrically isomorphic.
Recent research on this problem has uncovered several interesting results, mainly assuming that the graphs are full (an edge connects each pair of nodes). Under the full graph assumptions, several models for geometric GNNs are complete, that is. capable of separating all pairs of non- non-isomorphic graphs. However, this typically comes a relatively high computational price. Examples of complete models include (d 1)-WL-bassed GNNs (Delle Rose et al. 2023 Hordan et al. 2023 Li et al. 2024a), GNNs based on sub- uub-graph aggregation (Li et al. 2024b), and message passing models based on arbitrarily high-dimensional irreducible representations (Thomas et al. 2018: Gasteiger et al.) 2021 Dym & Maron 2020) Finkelshtein et al. (2022). This paper focuses on more efficient geometric GNNs: message- neural networks (MPNN) based on simple invariant and equivariant features. In (Pozdnyakov & Ceriotti 2022] Li et al.) 2024a), was shown that, even under the full graph assumption, invariant MIPNN-based networks complete. In contrast, Li et al. (2024b) and

---

Published as a conference paper at ICLR 2025
(A)
(B)
G1 22
G1 de 22
G1 de G2
LGGNN E-GGNN
(B)
Figure 1: (A) and (B) are pairs of hon-isomorphic geometric graphs with the same distances along edges. I-GGNN cannot distinguish such pairs, while E-GGNN can (generically) the graph is connected, as in (B). Subplot (C) depicts example of globally rigid graphs, where non-isomorphic geometrie graphs do not share the same distances across edges (in the figure, the edge between pink and light green). Such examples can be separated by both I-GGNN and E-GGNN.
Hordan et al. 2023) proved that these models are "generically complete.' which means that, under the full graph assumption, they are capable of separating most geometric graphs and only fail on Lebesgue measure zero of corner cases, which are difficult to separate.
In practical applications, the full graph assumption is often not fulfilled: to improve computational efficiency, geometric GNNs often operate on sparse graphs, where each node only connected to few nearest neighbors. Accordingly, the first question we address in this paper is:
Question 1. For which graphs, other than the full graphs, are geometric pesssag--passingg neural networks generically complete?
Our answer to this question is inspired by the results of Joshi et al. (2023). They divided Message- passing-based networks for geometric graphs into Equivariant Geometric Graph Neural Networks (E-GGNNs), which use rotation equivariant hidden features, and Invariant Geometric Graph Neural Networks (I-GGNNs), which use rotation invariant hidden features, and showed that E-GGNNs have substantial advantages over I-GGNNs in terms their expressive power.
Our answer to Question 1 is also strongly related to this dichotomy. We prove in Theorem 4. that E-GGNNs are generically complete for a given graph if and only if the graph is connected. This is visualized in Figure] I E-GGNNs will not be able differentiate between the pair of geometric graphs in Figure
as the underlying graph is disconnected but will be able to differentiate between the pairs in (B) and (C). In contrast, I-GGNNs will not be able to differentiate between the non- isomorphic pairs in Figure (aarre[AAA-a (B)) as the distances across all graph edges are the same. On the other hand, in (C), the distances along graph edges determine the positions of all nodes up rotation and translation. In rigidity theory, such graphs are called generically globally rigid.' In Theorem 3.1 we prove that I-GGNNs are generically complete and only if the underlying graph is generically globally rigid. These two theorems give complete answer to Question 1.
To guarantee generic separation, our theorems make the standard assumption (Jshh et al. 2023) that the I-GGNN and E-GGNN we consider are maximally expressive, meaning that all aggregation and readout functions used throughout the networks are injective. Recent work has shown that relatively standard and simple I-GGNN can fulfill this assumption (Amir al.) [003). However, for E-GGNN, is unclear how this assumption can be fulfilled. Accordingly, our second question is
Question 2.
Can we devise simple E-GGNN architecture that is maximally expressive hence, generically complete on connected graphs?
We answer this question affirmatively by devising simple architecture, which name EGENNET, and proving in Theorem 5.1 that is maximally expressive (for generic graphs). This architecture is based on simple message- message-passing architecture that resembles EGNN (Satorras al. 2021 but uses multiple equivariant channels as in (Levy et al. 2023).
We experimentally find that EGENNET is highly successful in synthetic separation tasks and on several learning tasks involving medium-sizen molecules, with a performance comparable to, or better than, state-of-the-ar methods. These results indicate that simple, generically complete methods
2

---

Published as a conference paper at ICLR 2025
like EGENNET are sufficient for the tasks considered. However, we acknowledge that there may be other tasks, perhaps involving molecules with non-trivial symmetry groups, where more complex geometric graph neural networks that offer full separation could be beneficial.
Contributions
To summarize, our main results are
Showing generic separation of E-GGNNs depends on graph connectivity,
Showing generic separation of I-GGNNs depends on graph rigidity.
Proposing simple E-GGNN architecture that is provably (generically) maximally expres- sive and performs well in practical tasks.
Appendix
See the appendix for all full proofs and related work.
SETUP: GEOMETRIC GRAPH NEURAL NETWORKS AND RIGIDITY THEORY
Geometric Graphs. In our discussion of geometric graphs and GNNs, we loosely follow the definitions of Joshi et al. (2023). We define geometric graph as pair G = X). The matrix A (0, 1 is an adjacency matrix, which fully defines a combinatorial graph. The neighborhood of a node is denoted by N₁. Accordingly, we sometimes use statements like 'the graph A.' We assume for simplicity that the graph nodes are the integers 1...., n. The matrix X= ( Fn.) E 1a denotes node positions. We denote the set of all geometric graphs with coordinates in Idd by G(d), and the subset of graphs with S N nodes by G y (d). Appendix H we discuss incorporating additional node and edge features into model and theoretical results.
The symmetry group of geometric graphs is the product of the permutation group S₂ and the group of rigid motions El Ed). The action of a permutation matrix P on a geometric graph is given by Pg == (PAPT, P.). J. A rigid motion in (d) is a rotation Q E (d) and a translation vector E R.d They act X by applying the rotation and translation to all its coordinates, æ; Qx, +
Two geometric graphs G and H. are geometrically isomorphic if there exists a transformation in Sn x E(d) which can be applied invariant if F(G)= = F(H) for all G and H which are geometrically isomorphic.
obtain H. We will say that function F defined G(d) is
The expressive power of invariant model F is closely related to its ability separate pairs G, H that are not geometrically isomorphic: clearly, if F cannot separate & from H. then F will not be good approximation for functions/ f for which f()) * (HH). Conversely, if F can separate all pairs of geometric graphs. then it can be used to approximate all continuous invariant (Dym & Gortler 2024; Hordan et al. (2023) and equivariant (Villar et al., 2021] Hordan al.) (002)) functions. In Appendix F we discuss the connection between approximation and separation in the context of our results.
Constructing an F which can separate all geometric graphs is at least as challenging distinguishing all combinatorial graphs (by setting all node features zero). Without any assumptions on the point cloud, achieving this is infeasible. To address this, we employ the concept of generic geometric graphs which originates from rigidity theory.
Generic separation and Rigidity Theory As discussed in the introduction, our paper focuses on generic separation. The results we present in this section are primarily influenced by rigidity theory, so we also use this field's common notion of "geeeric". We will say that X dx is generic if is not the root of any multivariate polynomial p: [Rdxn + R with rational coefficients. The genericity assumption guarantees that X avoids many degeneracies, making separation easier. For example, for generic X all pairs of points have different norms, and every d tuple of points ....... Zi, is full rank because ||=,|| ||> and det[æ,, ......... Iiy] are polynomials with natural coefficients. We note that Lebesgue almost all point clouds in R are generic (Mityagin 2020).
A globally rigid graph is central topic in rigidity theory:
Definition 2.1 (Globally rigid). (Garamvölgyi et al. (2022) geometric graph g = (A, is globally rigid in Rd, if the only X' E - which satisfy that I 2,y1 || 2/11 for all edges (i,j) in A, are those that are related to X by rigid motion.
3

---

Published as a conference paper at ICLR 2025
A combinatorial graph A is generically globally rigid in R if the geometric graph g (A, is globally rigid in IR" for every generic X E R=xd
The geometric graphs in Figure I (A)-(B) are not globally rigid, as they have the same distances along edges but are not related by a rigid motion. The underlying combinatorial graph, disconnected in (A) or line graph in (B), is not generically globally rigid. In contrast, the underlying combinatorial graph in (C) is generically globally rigid. Another simple example of a generically globally rigid graph is the full graph. Additional non-trivial examples can be found in (Jordán & Tanigawa 2022 Cheung & Whiteley 2005), A necessary condition for generic global rigidity of graph with n 2 d 2 nodes in I is to be d+1 connected which explains why the graphs in (A)-(B) are not generically globally
rigid.
Note that global rigidity definitions focus on reconstructing X when A is known. In the study of GGNNs, we are interested identifying both X and A:
Definition 2.2. Let d be natural number. Following Li al. (2024b), we will say that an invariant function F defined on Gdd), identifies a geometric graph G. if for every 9 E G(d), we have that F(g)= = F()) if and only if G and & are geometrically isomorphic,
We say that F generically identifies combinatorial graph A in R. if F can identify g = (A for every generic X E Raxd
We say that F generically fails identify combinatorial graph A in Rd, if F does not identify g - (A, X) for every generic X E B
Note that the fact that F does not generically identify A only guarantees that there exists a generic X that F fails to identify (A, X). The statement "F generically fails identify' is, apriori, significantly stronger. Also note that invariant F separates all non-isomorphic graphs (is complete) if and only if identifies all graphs. As discussed in the introduction, our goal will be classify which graphs are generically identifiable by standard message-passing seteeepppssssnsssseee baaedg networks for geometric graphs, which can be classified as either I-GGNN or E-GGNN. We will now define these concepts.
E-GGNN In the context of combinatorial graphs (with no geometric information), Gilmer et al. (0017):Jop) et al. (203)) and Veličkovid (2022) showed that many famous graph neural networks are instantiations of MPNNs. The goal of Joshi et al. (2023) was to show, analogously, that many neural networks for geometric graphs follow a generalized MPNN framework. Loosely following Joshi jet al. (2023), we define Equivariant Geometric Graph Neural Networks (E-GGNN) to be functions defined by sequence of layers that propagates vector features from iteration to + via learnable function f(e) (at initialization we set u 0).
(++1) fa) a. (0
(1)
To ensure the equivariance of the construction, the function f(z) is required to be rotation equivariant. Translation invariance is implicitly guaranteed by the translation invariance of x; Zy, and the requirement that f(y is defined on multi-sets implicitly enforces permutation equivariance. We will often refer to (() as aggregation function.
We note that for the sake of simplicity, we don't 't require combine step that incorporates o/ in the process of computing ii (t+1) since we find that this step has little influence on our theoretical and empirical results. We also note that the vector e is not necessarily dimensional, and the action of (dd) on (t) is allowed to change from layer to layer. For example, in the EGENNET architecture we will introduce later on, each (* will be a x m matrix, and the action of (d) will be multiplication on each of the m coordinates.
After T iterations of E-GGNNs, a permutation, rotation, and translation invariant feature vector can be obtained via two-step process involving a rotation-invarian function finy and a multi-set READOUT function:
8, = fun (v) (T),
globall
READOUT
(2)
Wee say a graph G l connected if the graph remains connected after removing any l vertices.
4

---

Published as a conference paper at ICLR 2025
As shown by Joshi et al. (2023), many popular geometric graph neural networks be as instances of E- GGNNN with specific choice of functions fit) and readout functions. Examples include EGNN (Satorras et al. 2021). TFN (Thomas et al. 2018), GVP (Jing et al. 2020), and MACE we present EGENNET, our instantiation of this framework.
(Batatia et al. 2022). In Section 5.1
I-GGNNs An important subset of E-GGNNs invariant GGNNs (I-GGNNs). These networks only maintain scalar features 8; and replace D; æt with its norm to obtain
(++1) = [1 ||, = 20,-,,1..j s
A global invariant feature is obtained via permutation invariant readout function in equation An advantage of I-GGNNs that there are no rotation cquivariance constraints on f(y) Therefore, any standard message- message-passing neural network that process continuous edge weights can be employed as an I-GGNN by setting the edge weights to ||a,y| Examples of I-GGNNs in the literature include a variant of EGNN used for invariant tasks (Satorras al. 2021), SchNet (Schütt al.) (018), DimeNet
Gasttiggr et al. 2020b) and SphereNet (Liu et al. 2021 Our definition of I-GGNN follows the
2024a). In Appendix we explain that the definition from (Pozdnyakov & Ceriotii 2022 Li et al.
definition of I-GGNNJJsse et al. (2023)
has a seemingly minor difference that renders it significantly
stronger.
The separation power of E-GGNN and I-GGNN architectures depends on the specific instance used. For example, if we choose the final readout function as the zero function, all geometric graphs will be assigned the same value. To address this, it customary to assume that all functions f(t), as well as fin and the readout function, are injective, up to the ambiguities these functions have by construction. Following Joshi et al. (2023), E-GGNN (respectively I-GGNN) architectures, which are composed of injective functions, maximally expressive E-GGNN (respectively I-GGNN) architectures. We note that the existence of the injective functions necessary for maximal expressivity follows from set-theoretic considerations, similar to those used by [Wang et al. (2024). The question of whether practical differentiable aggregation functions are injective is discussed in Section
Maximally expressive E-GGNN and I-GGNNs
will call
EXPRESSIVE POWER OF I-GGNN
Our next goal is to analyze the separation abilities of I-GGNN.
Theorem 3.1. /expressive power of I-GGNN] Let d be natural number. Let F be I-GGNN. Let A be a graph not generically globally rigid on Rd. Then, generically fails to identify Conversely, if A generically globally rigid on d and F is a maximally expressive I-GGNN with depth T = 1, then F' generically identifies A.
Proof idea. if A is not globally rigid, then according to Gortler et al. (2010), for every generic X there exists X' for which distances along edges are preserved, but X, X' are related by a rigid motion. It's easy to see any I-GGNN, which is based only on distances along edges, can't separate such graphs.
On the other hand, generic geometric graphs have distinct pairwise distances. The full proof (see Appendix G shows that this can be used reconstruct the combinatorial graph A. By global rigidity, we can then reconstruct X, up to rigid motion.
Note that Theorem 3.1 is generalization Hordan al. (023) that showed maximally expressive I-GGNN generically identify full graphs. We now showed this is true for all generically globally rigid graphs.
DimeNet (Gasteiger et al. 2020b) and SphereNet (Liu et al. 2021 have access to the power graph g (defined later in the paper) and thus are invariant models on G and have potential expressive power stronger than invariant I-GGNN g.
5

---

Published as a conference paper at ICLR 2025
I-GGNN generic separation by power graph preprocessing A natural strategy to overcome the lack of generic separation for graphs that are not generically globally rigid. as proven in Theorem 3.1 is to replace these graphs with graphs that are generically globally rigid. This replacement can be done using power graphs: For given graph & and natural number k, the power graph g is defined to have the same nodes the original graph g. A pair of nodes are connected by an edge in the power graph if and only if there is a path between them in the original graph of length S k.
In (Jordán & Tanigawa 2022; Cheung & Whiteley, (000)) it was shown that if the original graph G is connected, then the power graph ga is generically globally rigid in IR Accordingly, when the input graph G is connected but not generically globally rigid, our theory suggests that applying I-GGNN not to the original graph but to its d + power may benefit separation. An experiment illustrating this idea is presented in Table I
4 EXPRESSIVE POWER OF E-GGNN
When using E-GGNN rather than I-GGNN, we will have generic separation if and only if the graph connected.
Theorem 4.1. fexpressive power of E-GGNN] Let d be natural number. Let F be E-GGNN. Let A be a disconnected graph. Then, F generically fails to identify A. Conversely, if A is connected and F is maximally expressive E-GGNN with depth T 2 d + 1, then F generically identifies A.
Proof idea. Suppose a geometric graph 9 isn't connected. We can apply two distinct rigid motions to two connected components and obtain new geometric graph, G which cannot be separated from G using E-GGNN. This illustrated in Figure AA) Conversely, in the appendix Theorem G| we show that the features 8; obtained after d I ittraaionn of maximally expressive E-GGNN can encode the multi-set of all distances |a.; æyyl for all which are d + 1-hop neighbors of (a similar claim was shown by Joshi et al. (202))) Thus, d d++ iterations of maximally expressive E-GGNN
simulate the application of a single iteration of an I-GGNN on the d + I power graph. The proof then follows from the fact that the (d 1) power graph is generically globally rigid (Jordán & Tanigawa, 2022
Cheung & Whiteley 2005).
An immediate result of this theorem is that generic graph separation is a local problem with problem radius of d + 1 (Alon Yahav 2020) We note that the generic assumption allows us to reconstruct the coordinates of the nodes and the combinatorial graph. Without the generic assumption, even models based on 2-WL that are complete on full graphs cannot reconstruct the combinatorial graph. Setting all positions to zero nullifies the geometric information, and 2-WL is insufficient to distinguish all combinatorial graphs.
5 BUILDING A GENERICALLY MAXIMALLY EXPRESSIVE E-GGNN
To obtain generic separation guarantees as in Theorems F-GGNN (or I-GGNN), will need to show that the instantiation is fully expressive. This type of question was studied rather extensively for combinatorial graphs (Amir et al. 2023] AAamand et al.) 2022), and these results can be used to show that some simple realizations of I-GGNN are maximally expressive. We discuss this in more detail in Appendix C
for a practical instantiation of
For E-GGNN, the requirement that ((1) is simultaneously injective (up to permutation) and equivariant to rotations seems to be challenging to attain with simple E-GGNN construction, and indeed, Joshi al, (223) who suggested the notions of maximally expressive E-GGNN, did not give any indication of how they could be constructed in practice. Moreover, in Appendix D we show that a maximally expressive E-GGNN can separate all pairs of full graphs and separate geometrically all pairs of connected g indicating constructing such a network may be computationally expensive, as
AA task's problem radius denoted by the minimal integer where the task becomes solvable upon each node ohserving its neighborhood within a r-o radius and aggregating all node's information.
'We define the geometric separation of a geometric graph if we can separate the point clouds up to group action, without necessarily reconstructing the combinatorial graph.

---

Published as a conference paper at ICLR 2025
currently, such guarantees are only achieved by networks of relatively high complexity based on 2- WL subgraph aggregation techniques.
In our setting, however, the problem is less severe since, from the outset, are only interested in analyzing network behavior on generic graphs. Accordingly, we would like to require our E-GGNN to be maximally expressive only for generic graphs. turns that this goal can be achieved with straightforward E-GGNN architecture, which we name EGENNET. Our next step will be to present this architecture.
5.1 THE EGENNET ARCHITECTURE
Our goal in this section is to build maximally expressive EGNN. For this, we need to implement injective readout and aggregation functions Jiv. READOUT (see equations 12 The EGENNET architecture we suggest resembles equivariant channels as in (Levy et al. 2023). The EGENNET architecture depends on two hyper- parameters: depth T (the term 'depth' refers to the number of MPNN iterations) and channel number C. The imput to the architecture is a geometric graph X).
EGNN architecture (Satorras et al.) 2021 with multiple
Aggregation The architectures then maintains, each iteration & and node an 'equivariant" node feature with C' channels
(v
(0) Fie
Rdd. c= : II
These feature values are initialized zero and are updated via the rotation and permutation equivariant aggregation formula
(+++) 0ig
Σ
( myyl (0, m.))
Σ 2 (Lac
æ2l1, || 100o)
(5)
JEN:
where ||u,|] is the C' ddimensional vector containing the norms of the vectors Use, c= ,,...,C..
Construction of finv and READOUT After T' iterations, we obtain rotation and permutation invariant node features 8; E ERC and global feature gglobal E ERC via
81gg = Dc 11.
gglobal
(n) global (s:), q= -=1...,C C
(6)
Where 9 is Iearnable matrix, and the functions @ Pglobal ((t.9.)) are all fully connected neural networks with single layer, an output dimension of 1, and an analytic non-polynomial activation (in our implementation. TanH activation). The complexity of EGENNET is linear in N C. as discuss in Appendix G.2
The next theorem shows that EGENNET is generically maximally expressive:
Theorem 5.1. Let d, N, T be natural numbers. Let F be maximally expressive E-GGNN of depth T, and let Fg denote the EGENNET architecture with depth and C = 2N +1 channels. Then, for Lebesgue almost every choice of network parameters 0, we have that for all generic g E Gx(d),
F(g) F(G) - Fo(g) Fo(l)
Proof idea. The proof relies on the methodology developed by Dym & Gortler (024)) ) Amir et al. (2023) and Hordan et al. (2023). We note that each step in EGENNET employs C identical analytic functions indexed by q T...., C, with independent parameters, Dym & Gortler (002) and Amir al. (2023) showed that in this setting, if every pair of non -somoooooiipiic inputs can be separated by some parameter of the original function, then C' = 2Nd + copies of this function with random parameters will suffice to separate all pairs uniformly. The proof is then reduced to showing that any pair of non-isomorphic inputs can be separated by some parameter vector, which we prove in the appendix G.I
Joining this theorem with theorem on maximally expressive E-GGNN, we deduce
7

---

Published as a conference paper at ICLR 2025
chain
(Pair a)
(Pair b)
1
G2
G1 de G2
1 ~e G2
Figure 2: From Left to Right: k-chain pair graphs that are non-generic and require ~ k/2 blocks for separation, Pair a in which 2-power graph is enough for I-GGNN distinguish and Pair in which 3-power graph is necessary and sufficient for separation.
Corollary 5.2. Let N natural numbers. let Fg denote the EGENNET architecture with depth T = d+1 and C 2Nd + channels. Then for Lebesgue almost every 0, for every pair of graphs G.G g' E which are generic and connected,
(g Fo(G) G, are geometrically isomorphic
Note that by Joshi et al. at least nd ald
2023). theorems 20, 22, the dimension of any injective embedding must be
showing embedding dimension 2nd + 1 is optimal up to factor of 2 (when
n > d).
EXPERIMENTS
In the experiments section, we have three main objectives. First, we aim to demonstrate that invariant models are indeed strictly less expressive than equivariant models and that power graphs help to mitigate this gap. Second, we seek to show that our model can distinguish challenging graph examples, including those requiring multiple layers for separation, thereby avoiding the bottleneck phenomenon encountered in other geometric models. Finally, we aim to demonstrate the improved performance of model real-world benchmarks.
6.1 SEPARATION EXPERIMENTS
Enhancing Model Expressiveness: Power Graphs in Invariant vs. Equivariant Comparisons begin with experiments to corroborate our theoretical findings. We consider examples where the graph A is a line graph, which is connected but generically globally rigid. We choose two pairs of geometric line graphs, Pair a and Pair b, depicted in Figure 2 These pairs have identical distances along graph edges but not isomorphic. Therefore, they cannot be distinguished by any I-GGNN but (at least when generic) can distinguished by E-GGNN and our EGENNET architectures. Following the protocol from Joshi et al. (2023), we construct binary classification problems from Pair and Pair b and apply our E-GGNN architecture EGENNET, as well as three popular I-GGNN architectures: SchNet (Schütt et al. 2018 DimeNet (Gasteiger al. 2020b). and SphereNet (Liu et al. 2021)
The results are shown in the first column Table I As expected, EGENNET perfectly separates pairs and b. while SchNet fails to separate both. Note that DimeNet and SphereNet separate Pair a but not Pair b. This is because DimeNet and SphereNet compute angles at edges, which utilizes information not contained in the graph G but only in the power graph g². Indeed, distances between two-hop neighbors are sufficient for discriminating between the two geometric graphs in Pair a but not in Pair b, where the distance between the three-hop red and orange nodes is needed for separation. Next, as we suggested Section 3 we apply the same algorithms to the powers the original graph. As shown in Table II] this improves the separation capabilities of the I-GGNN models. All invariant models succeed when the third power taken, as expected since a connected graph's 's + power (here d 2) is generically globally rigid.
8

---

Published as a conference paper at ICLR 2025
Table E-GGNN models like EGENNET can separate the two pairs of connected graph in Figure I-GGNN models cannot separate unless power graphs are considered.
Power graph
GNN Layer
2
Maximal L-GGNN
50%
100%
100%
SchNettSchütt al. 20188)
50.0 0.0
100.0
100.0
Pair
DimeNet Gastegger et al (0200)
100.0 0.0
100.0 0.0
100.0 a: 0.0
SphereNet al.
100.0
100.0 0.0
100.0
SchNet graph
100.0
100.0 0.0
100,0 0.0
SchNetggloall
100.0 =
100.0 2.0
100.0 0.0
(G)NN
100.0 0.0
100.0 0.0
100.0 0.0
Maximal L-GGNN
50%
50%
100%
Pair b
SchNet Schütt et al. (0118)
50.0 0.0
50.0 0.0
100.0 0.0
DimeNet Gasteiger et al. 2020b)
50.0 0.0
100.0 0.0
100.0 +
SphereNet Liu et al.
50.0 0.0
100.0 0.0
100.0 #.0
SchNet full graph
100.0 0.0
100.0 0.0
100.0 0.0
SchNetglobal feat
100.0
100.0 = 0.0
100.0 0.0
EGENNET (us)
100.0 +
100.0 + 0.0
100.0 0.0
Unpacking the Bottleneck: Layer Requirements for Complex Graph Separation
k-chains Next, we consider the k chain pairs suggested in Joshi et al. (2023) and illustrated in the left of Figure By design, this is a pair graphs with & nodes, which can only be separated by k hop distances. In Joshi et al. (2023), it was shown that depth of least [k/2] necessary to achieve separation by E-GGNN in this setting. Note that as most nodes in the chain graphs are the same line, this point cloud is not generic, the fact that for large k; more than +++ iterations are needed does not contradict our theory. In our experiments, we include two variations of SchNet (Schütt et al., 2018): full graph and global feature. Those variations use all pairwise distances, thus showing better results than other invariant models. In the first experiment, we set 4. Theoretically, blocks are needed for propagating the information, and 2 blocks are insufficient. As shown in Appendix 3 we succeed with probability of over 10 trials with 3 blocks. For checking long-term dependencies, we choose k = 12 again; blocks are needed, and 6 is insufficient. We examined all models with 7, 8, 9, 10, 11 blocks, each 10 times. As shown in 4 we are the only ones succeeding with blocks, and all other models need a much higher number of blocks. This may suggest our model is less influenced by over-squashing Alon & Yahav/ (2020). In the appendix, Table 7 we add a time comparison table for all models using the 128 dimensional feature.
is
Hard examples In 5 the appendix. we show that our model can also perfectly separate challenging examples from (Pozdnyakov et al., 2020; Pozdnyakov Ceriotti 2022). using the experiment setup taken from Hordan al. (2023). These geometric graph pairs cannot be separated by I-GGNN, even on full graphs, and are also difficult to separate using equivariant methods like EGNN.
Chemical property experiments Finally, we check our model's 's ability to learn regression-nvarrinn real-world chemical properties, critical task in computational chemistry and material science. Learning chemical properties accurately is essential for predicting the behaviors of compounds, enabling advancements in drug discovery, material design, and environmental science. By effectively capturing these properties, the model demonstrates its potential to assist in solving complex chemical problems, where precise property prediction can reduce experimental costs and guide targeted research. As in (Zhu et al. 2024), we compare to the following models: Random Forest (Breiman 2001), LSTM (Hochreiter & Schmidhuber 1997). Transformer (Vaswani al. 2017). GIN (Xu et al.
Here, SchNet global and full are invariant models utilizing the full graph structure (unlike other models utilizing the given combinatorial structure).

---

Published as a conference paper at ICLR 2025
Table Performance of ID, 2D, and 3D baseline MRL models and the best results from ensemble learning strategies on 3D GNNs. The metric used is the Mean Absolute Error (MAE, 4). The bold indicates the pest-perforning model, while underlined denotes the second-bess best.
Drugs
Kraken
BDE
Category
Model
IP
EA
X
Bs
L
BurBs
BurL
BE
Random Forest
0.4987
0.4747
0.2732
0.4760
0.4303
0.2758
0.1521
3.0335
ID
LSTM
0.4788
0.4648
0.2505
0.4879
0,5142
0.2813
0.1924
2.8279
Transformer
0.6617
0.5850
0.4073
0.9611
0.8389
0.4929
0.2781
10.0771
GIN
0.4354
0.4169
0.2260
0.3128
0.4003
0.1719
0.1200
2.6368
GIN+VN
0.4361
0,4169
0.2267
0.3567
0.4344
0.2422
0.1741
2.7417
2D
ChemProp
0.4595
0.4417
0.2441
0,4850
0.5452
0.3002
0.1948
2.6616
GraphGPS
0.4351
0.4085
0,2212
0.3450
0.4363
0.2066
0.1500
2.4827
SchNet
0.4394
0.4207
0.2243
0.3293
0.5458
0.2295
0.1861
2.5488
DimeNet+++
0.4441
0.4233
0.2436
0.3510
0.4174
0.2097
0.1526
1.4503
GemNet
0.4069
0.3922
0.1970
0.2789
0.3754
0.1782
0.1635
1.6530
PaiNN
0.4505
0.4495
0.2324
0.3443
0.4471
0.2395
0.1673
2.1261
3D
ClofNet
0.4393
0.4251
0,2378
0.4873
0.6417
0.2884
0,2529
2.6057
LEFTNet
0.4174
0.3964
0.2083
0.3072
0,4493
0.2176
0.1486
1.5328
Marcel
0.4066
0.3910
0.2027
0.2225
0.3386
0.1589
0.0947
1.4741
EGENNET(OUrS)
0.3965
0.3686
0.2068
0.1878
0.1738
0.1530
0.0626
0.3170
2018), GI (Hu et al. 2020), ChemProp (Heid et al. 2023). GraphGPS (Rampášek et al. 2022
SchNet Schütt et al. 2018 8), DimeNet++ (Gasteiger et al. (0200a). GemNet (Gasteiger et al. 202 )
PaiNN Schuit et al. 2021). ClofNet (Du et al. 2022). LEF (Du et al., 2024), and Marcel (Zhu
ct al. 2024). Our task learning chemical property prediction on three datasets: Drugs (Axelrod &
Gomez- Boannzll 2022), Kraken (Gensch al. 2022). and BDE (Meyer et al. 2018). Drugs are the
largest and most challenging dataset, containing 560K samples; BDE is a medium-sized dataset with 80K datasets; and Kraken is the smallest, with 22K samples. The baseline model performance, data split, and training procedure are taken from Zhu et al. (2024). In particular, we ran each experiment three times and reported the model's test error with the best validation performance. In Table 6 in the appendix, we report the mean and standard deviation.
we show comparable or improved results in all tasks. For example, in BDE, we have an improvement of 78%, in Kraken property burL 33%, and in the property L 48%. Remarkably. our method outperforms competing more complex methods like GemNet, which employs high-order irreducible representations. This can be explained by the generic completeness of our method, coupled with results we will show in the appendix Table 8) which shows that these datasets have small number of norm-repetitions, indicating that they are "close generic".
As see in Table 2
LIMITATION AND FUTURE WORK
In this work, we characterized the generic expressive power of I-GGNN and E-GGNN, showed that EGENNET is generically maximally expressive E-GGNN, and showed the effectiveness of this architecture on chemical regression tasks. A limitation of our work is that it may struggle with symmetric and non-generic input. Future work could consider assessing the expressive power of Mon-MPNN models like geometric 2-WL on sparse graphs to address such input efficiently.
8 ACKNOWLEDGMENTS
We thank Snir Hordan for reviewing manuscript and for the helpful discussions and suggestions. We would like to thank Idan Tankel for his technical help and support. N.D. and Y.S. are funded by Israeli Science Foundation grant no. 272/23.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Anders Aamand, Justin Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer, Sandeep Silwal, and Tal Wagner. Exponentially improving the complexity of simulating the weisfeiler-lchman test with graph neural networks. Advances in Neural Information Processing Systems, 35:27333-27346, 2022.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. arXiv preprint M.Xiv:000600500,0 2020.
Tal Amir, Steven Gortler, llai Avni, Ravina Ravina, and Nadav Dym, Neural injective functions for multisets, measures and graphs via finite witness theorem. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 42516-42551. Curran Associates, Inc., 2023.
Brandon Anderson, Truong Son Hy, and Risi Kondor. Cormorant: Covariant molecular neu- ral networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bii Buc. E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019, U meurips cttpppee..pp..pppppprrr.ee.ppeee fi willesppaper
pdf
Simon Axelrod and Rafael Gomez- Bombarel. Geom, emergy-annotated molecular conformations for property prediction and molecular generation. Scientific Data, 9(1):185, 2022.
Ilyes Batatia, David P Kovacs, Gregor Simm, Christoph Ortner, and Gábor Csányi. Mace: Higher order equivariant message passing neural networks for fast and accurate force fields. Advances in Neural Information Processing Systems, 35:1 1112--114466 2022.
Georg Bökman, Fredrik Kahl, and Axel Flinth. Zz-net: A universal rotation equivariant architecture for 2d point clouds. In Proceedings of the IEFE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10976-10985, 2022.
Leo Breiman. Random forests. Machine learning, 45:5-32,20 2001.
Lawrence Cayton et al. Algorithms for manifold learning. eScholarship, University of California, 2008.
Matthew Cheung and Walter Whiteley. Transfer of global rigidity results among dimensions: Graph powers and coning. Preprint, York Universily, 2005.
Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas, Mircea Petrache, and Pablo Barceló. Three iterations of (d- 1)-wl test distinguish non isometric clouds of d-dimensional points. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Congyue Deng, Or Litany, Yueqi Duan, Adrien Poulenard, Andrea Tagliasacchi, and Leonidas J Guibas. Vector neurons: A general framework for so (3)-equivariant networks. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 12200-12209, 2021.
Weitao Du, He Zhang, Yuanqi Du, Qi Meng, Wei Chen, Nanning Zheng, Bin Shao, and Tie-Yan Liu. Se (3) equivariant graph neural networks with complete local frames. In International Conference on Machine Learning, pp. 5583-5608. PMLR, 2022.
Yuanqi Du, Limei Wang, Dieqiao Feng, Guifeng Wang, Shuiwang Ji, Carla P Gomes, Zhi-Ming Ma, et al. A new perspective on building efficient and expressive 3d equivariant graph neural networks. Advances in Neural Information Processing Systems. 36, 2024.
Nadav Dym and Steven Gortler. Low-dimensional invariant embeddings for universal geometric learning. Foundations of Computational Mathematics, pp. 1-41, 2024.
Nadav Dym and Haggai Maron. On the universality of rotation equivariant point cloud networks. In International Conference Learning Representations, 2020.
Ben Finkelshtein, Chaim Baskin, Haggai Maron, and Nadav Dym. A simple and universal rotation equivariant point-cloud network. In Topological, Algebraic and Geometric Learning Workshops 2022, pp. 107-115. PMLR, 2022.
11

---

Published as a conference paper at ICLR 2025
Fabian Fuchs, Daniel Worrall, Volker Fischer, and Max Welling. Se (r).transformm:s: 3d roto- translation equivariant attention networks. Advances in neural information processing systems, 33: 1970-1981, 2020.
Dániel Garamvölgyi, Steven J Gortler, and Tibor Jordán. Globally rigid graphs are fully recon- structible. In Forum of Mathematics, Sigma, volume 10, pp. e51. Cambridge University Press, 2022.
Johannes Gasteiger, Shankari Giri, Johannes T Margraf, and Stephan Günnnemann. Fast and uncertainty-aware directional message passing for non-equilibrium molecules. arXiv preprini arXiv:2011.14115. 2020a.
Johannes Gasteiger, Janek GroB, and Stephan Günnemann. Directional message passing for molecular graphs. arXiv preprint arXiv:2003.03/23, 2020b.
Johannes Gasteiger, Florian Becker, and Stephan Günnemann. Gemnet: Universal directional graph neural networks for molecules. Advances in Neural Information Processing Systems, 34: 6790-6802, 2021.
Tobias Gensch, Gabriel dos Passos Gomes, Paseal Friederich, Ellyn Peters, Théophile Gaudin, Robert Pollice, Kjell Jomner, AkshatKumar Nigam, Michael Lindner-DD D' Addario, Matthew S Sigman, et al. A comprehensive discovery platform for organophosphorus ligands for catalysis. Journal of the American Chemical Sociely, 144(3):1055-1111) 2022.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 2663-1272. PMLR, 2017.
Steven Gortler, Alexander Healy, and Dylan Thurston. Characterizing generic global rigidity. American Journal of Mathematics, (32(4):877-935 2010.
Jiaqi Han, Jiacheng Cen, Liming Wu, Zongzhao Li, Xiangzhe Kong, Rui Jiao, Ziyang Yu, Tingyang Xu, Fandi Wu, Zihe Wang, Hongteng Xu, Zhewei Wei, Yang Liu, Yu Rong, and Wenbing Huang. A survey of geometric graph neural networks: Data structures, models and applications, 2024.
Esther Heid, Kevin Greenman, Yunsie Chung, Shih-Cheng Li, David Graff, Florence Vermeire, Haoyang Wu, William H Green, and Charles J McGill. Chemprop: A machine learning package for chemical property prediction. Journal of Chemical Information and Modeling, 64(1):9-17, 2023.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-173 1780, 1997.
Snir Hordan, Tal Amir, Steven J Gortler, and Nadav Dym. Complete neural networks for euclidean graphs. arXiv preprint arXiv:2301. 13821, 2023.
Snir Hordan, Tal Amir, and Nadav Dym. Weisfeiler leman for euclidean equivariant machine learning. arXiv e-prints, pp. arXiv-2402. 2024.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen I. Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems, 33:221 33:22118-22133 18-22133, 2020.
Bowen Jing, Stephan Eismann, Patricia Suriana, Raphael John Lamarre Townshend, and Ron Dror. Learning from protein structure with geometric vector perceptrons. In International Conference on Learning Representations, 2020.
Fabian Jogl. Maximilian Thiessen, and Thomas Gärtner. Expressivity-preseving GNN simulation. In Thirty-eevnnth Conference on Neural Information Processing Systems, 2023. URL https: //operevviww...m net./ forumm wiw.ttttnnddttdoononon... 9wd
Tibor Jordán and Shin-ichi Tanigawa. Globally rigid powers of graphs. Journal of Combinatorial Theory, Seriey B, 155:1 11-140, 2022.
12

---

Published as a conference paper at ICLR 2025
Chaitanya K. Joshi, Cristian Bodnar, Simon V Mathis, Taco Cohen, and Pietro Lio. On the expressive power of geometric graph neural networks. arXiv preprint 0rXiv:2301.93303 2023.
Vitaliy Kurlin. Polynomial-time algorithms for continuous metrics on atomic clouds of unordered points. Match: Communications in Mathematical and in Computer Chemistry, 2023.
Daniel Levy, Sékou-Ouma Kaba, Carmelo Gonzales, Santiago Miret, and Siamak Ravanbakhsh. Using multiple vector channels improves e (q)iiurvrria graph neural networks. arXiv preprint arXiv:2309.03 2023.
Zian Li, Xiyuan Wang, Yinan Huang, and Muhan Zhang. Is distance matrix enough for geometric deep learning? Advances in Neural Information Processing Systems, 36, 2024a.
Zian Li, Xiyuan Wang. Shijia Kang, and Muhan Zhang. On the completeness of invariant geometric deep learning models. arXiv preprint arXiv:2402.04 04836, 2024b.
Yi Liu, Limei Wang, Meng Liu, Yuchao Lin, Xuan Zhang. Bora Oztekin, and Shuiwang Ji. Spherical message passing for 3d molecular graphs. In International Conference on Learning Representations, 2021.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05011, 2017.
Benjamin Meyer, Boodsarin Sawatlon, Stefan Heinen, O Anatole Von Lilienfeld, and Clémence Corminboeuf. Machine learning meets volcano plots: computational discovery of cross-coupling catalysts. Chemical science, 9(35):009--7077, 2018.
BS Mityagin. The zero set of a real analytic function. Mathematical Notes, 107:529-530, 2020.
Jigyasa Nigam, Sergey Pozdnyakov, and Michele Ceriotti. Recursive evaluation and iterative contrac- tion of n-body equivariant features. The Journal of chemical physics, 153(12), 2020.
Allan Pinkus. Approximation theory of the mip model in neural networks. Acta numerica, 8:143-195, 1999.
Sergey Pozdnyakov and Michele Ceriotti. Incompleteness of graph convolutional neural networks for points clouds in three dimensions. 01 2022. URL arXiv:2201 07136v4
Sergey N. Pozdnyakov, Michael J. Willatt, Albert P. Bartók, Christoph Ortner, Gábor Csányi, and Michele Ceriotti. Incompleteness of atomic structure representations. Phys. Rev. Lent, 125:166001, Oct 2020. doi: 10. 10.1103/hy.RevLeett 166001. URL httth:tts://iit oroo/////// 1103/PhysRevLett. 125. 166001
aps. org/
Onri Puny, Matan Atzmon, Edward Smith, Ishan Misra, Aditya Grover, Heli Ben-Hamu, and Yaron Lipman. Frame averaging for invariant and equivariant network design. In International Conference on Learning Representations, 2021.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, -5051115511155,,, 2022.
Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling, (n) equivariant graph neural networks. In International conference machine learning, pp. 9323-9332. PMLR, 2021.
Kristof Schütt, Oliver Unke, and Michael Gastegger. Equivariant message passing for the prediction of tensorial properties and molecular spectra. International Conference on Machine Learning, pp. 9377-9388. PMLR, 2021.
Kristof T Schütt, Huziel E Sauceda, P-J Kindermans, Alexandre Tkatchenko, and K-R Müller. Schnet-a deep learning architecture for molecules and materials. The Journal of Chemical Physics, 148(24), 2018
Alexander V. Shapeev. Moment tensor potentials: A class of systematically improvable interatomic potentials. Multiscale Modeling & Simulation, 14(3) 1173, 2016. doi: 10.1137/5 URL httpstt:::// //dtis org/ 0. 1..1117/15M111 054183
13

---

Published as a conference paper at ICLR 2025
Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation and translation-equivee neural networks for 3d point clouds. arXiv preprint wwX.v:1802.08222 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Petar Veličković. Message passing all the way up. arXiv preprint arXiv:2202. 2022.
Soledad Villar, David W Hogg, Kate Storey-Fisher, Weichi Yao, and Ben Blum-Smith. Scalars are universal: Equivariant machine learning, structured like classical physics. Advances in Neural Information Processing Systems, 34:28848- -28433,, 2021.
Limei Wang, Yi Liu, Yuchao Lin, Haoran Liu, and Shuiwang Ji. Comenet: Towards complete and efficient message passing for 3d molecular graphs. Advances in Neural Information Processing Systems, 35:650-664, 2022.
Shih-Hsin Wang. Yung-Chang Hsu, Justin Baker, Andrea L. Bertozzi, Jack Xin, and Bao Wang. Rethinking the benefits of steerable features 3d equivariant graph neural networks. In The Twelfth International Conference Learning Representations, 2024. URL
Xiyuan Wang and Muhan Zhang. Graph neural network with local frame for molecular po- tential energy surface. In The First Learning Graphs Conference, 2022. URL https
/ooeeneviie net fort:/formmmii -ol.d-0150 01Sm 1100001mmmm111-11 R82jBR
Daniel Widdowson and Vitaliy Kurlin. Recognizing rigid patterns of unlabeled point clouds by
complete and continuous isometry invariants with no false negatives and no false positives. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1275-1284, 2023.
Daniel Widdowson, Marco Mosca, Angeles Pulido, Vitaliy Kurlin, and Andrew I Cooper. Average minimum distances of periodic point fundamental invariants for mapping all periodic crystals. MATCH Communications in Mathematical and in Computer Chemistry, (73))599-555, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 181000000000 2018.
Yanqiao Zhu, Jeehyun Hwang, Keir Adams, Zhen Liu, Bozhao Nan, Brock Stenfors, Yuanqi Du, Jatin Chauhan, Olaf Wiest, Olexandr Isayev, Connor W. Coley, Yizhou Sun, and Wei Wang. Learning molecular conformer ensembles: Datasets and benchmarks. In The Twelfth International Conference on Learning Representations, 2024. URL htl.http::/ /atpss///ppeeeiii ew net./ forum? Id=NNDDz7J2uTV
14

---

Published as a conference paper at ICLR 2025
A
RELATED WORK
This section discusses related work that is not discussed in the main text.
Equivariant models In the context of learning on geometric graphs, models should be equivariant the joint action of permutations, rotations, and translations. Besides the models discussed in the paper, some prominent models with this equivariant structure include Cormorant (Anderson et al. 2019
Vector Neurons (Deng al., 202T), and SE(3) transformers (Fuchs et 2020).
Completeness, universality and generic completeness The main text discusses related works on completeness focused on methods coming from the geometric learning community. Other complete methods, generally using similar ideas, appeared independently in the more chemistry- oriented community (Kuulin 2023 Widdowson & Kurlin 2023 Shapeev 2016 Nigam et al., (2200). Completeness in 2D was ach in Bökman et al. (2022), and completeness with respect to rigid motions (without permutations) was achieved by Comenet (Wang et al.) 2022). Comenet also uses some genericity assumptions (e.g.. that there is a well-defined notion of nearest neighbors).
The main text discussed how generic completeness globally rigid. A similar result can be obtained when considering the list of all distances (Garamvölgyi al. 2022). Generic completeness for full graphs can also be obtained using more complex distance- based features (Widdowson et al. (2022) or shape principal axes (Puny et al. 2021 (under the generic assumption that the principal eigenvalues are distinct).
be achieved using I-GGNN when the graph is
Comparison with Wang Zhang 2022) Generic completeness without the full graph assumption, employing only the assumption that local neighborhoods are not symmetric, is discussed by Wang & 'Zhang (2022). However, there are notable differences in key aspects of the results. Specifically, Theorem 4.2 in Wang & Zhang (2022) demonstrates that their proposed equivariant model can identify generic molecules using L message-passing iterations, where L is the graph's 's diameter. In contrast, our Theorem [arooremm4]]]qquueeeee requires only d iterations (where d 3 in typical applications, resulting in total of just four iterations).
Moreover, while Theorem 4.2 in Wang & Zhang (022) focuses recovering the 3D structure, it does not address the combinatorial structure. Our Theorem 4.1] however, guarantees the recovery of both combinatorial and geometric structures in the generic case.
Additionally, our Theorem 3.1 precisely describes the conditions under which invariant models are, and are not, generically complete- result not covered in Wang & Zhang (2022).
B IMPLEMENTATION DETAILS
Here, we detail the parameer choice. For all experiments, we use AdamW optimizer Loshchilov & Hutter (2017). We use varying weight decay of 1e 1e and learning rate of le Reduce On Platue scheduler is used with a rate decrease of 0.75 with the patience of 15 epochs. We use two blocks with 40 channels in the challenging point cloud separation experiments. For k-chain experiments, we repeat each experiment 10 times, with 10 different seeds, and set the number of channels be 60, and a varying number of blocks, detailed in the table. For power graph experiments, we repeat each experiment 10 times, with 10 different seeds, and set the number of channels to be 60 and blocks. For chemical property experiments, all the procedure is taken from Zhu et al. (2024): each dataset is partitioned randomly into three subsets: 70% for training, 10% for validation, and 20% for test. We set the number of channels be 256 and used 6 blocks. Each model is trained over 1, 500 epochs. Experiments are repeated three times for all eight regression targets, and the results reported correspond to the model that performs best on the validation set in terms of Mean Absolute Error (MAE). In contrast to the experiments in Zhu al. (2024), we didn't 't consider the EE dataset as it's currently not public on GitHub. We utilize Py Torch and PyTorch- PyTorch-Geemetric to implement all deep learning models. All experiments conducted servers with NVIDIA A40 GPUs, each with 48GB memory. All dataset details, including statistics, can be found in Zhu et al. (2024).
15

---

Published as a conference paper at ICLR 2025
C BUILDING PERFECT I-GGNN
Here, we describe in detail how to construct a perfect I-GGNN. We will assume that we consider geometric graphs with up N nodes. The main ingredients needed aggregation functions and READOUT function that are injective on the space of all multisets of size < N. Amir et al. (2023) proved that the sum of projections and analytic activation can be used to construct such layers. Formally, be M semi-analyln set of dimension D, and N vectors in R denoted by X. Be E R(2D+1)xd b E RR2++1 a - analytic non-polynomial activation, then for Lebesgue almost every A,
SAM(X)= = Σ ( (A+
is injective up to permutation. Thus, the composition of such blocks and such READOUT function with dimension d- N yields a maximally expressive model on all input domain. Here, the intrinsic dimension of all features, ultimately produced by the D dimensional input space.
D SEPARATION POWER OF FULLY MAXIMALLY EXPRESSIVE E-GGNN
In the main text, we proposed EGENNET a simple generically maximal expressive E-GGNN. In this section, we show that we have a maximally expressive E-GGNN on all input domain, we can reconstruct full graph up to group action, and if the graph is connected, we reconstruct its point cloud. This indicates that fully maximally expressive E-GGNN is as challenging as achieving completeness, which generally requires complex methods like 2- 2-WL-based GNNs.
Theorem D.1. Let G = (A, X) be a geometric graph, where A is the full graph on n nodes, and X an arbitrary n matrix, then one iteration of maximally expressive E-GGNN can reconstruct X.
Proof. Assume we run one iteration of E-GGNN our geometric graph, then for each node i, know up to some rotation Q;
fQ (z; - z,)l E [m]]
Choosing i = 1, and x; = 0, we have all other positions Qi - -r.. F i, thus up to translation (as we set v.), rotation Q; and node permutation, can reconstruct point cloud.
We now show that using iterations of E-GGNN can reconstruct the point cloud of each connected graph.
Theorem D.2. Assuming a connected geometric graph G XA, with nodes, then iteration of maximally expressive E-GGNN can reconstruct the point cloud.
Proof. Assume we run iterations of a maximally expressive E-GGNN on our connected graph. Then, by Theorem 4.1 can reconstruct for each node i its n-hopp up to rotation Qi. As the n-hop of a node is all other nodes (the graph's 's diameter at most n),, we reconstruct the full geometric graph up to rotation, and by theorem D.I reconstruct the point cloud.
E I-GGNN+
Here, we present the definition of I-GGNN presented by Joshi et al. (2023). denoted by I-GGNN+ and show that it can separate all geometric full graphs. After, we explain why this model strictly stronger than our I-GGNN.
Joshi et al. 2023 defines (neglecting the update step also used there)
((+1) f² (( x. æz, j E NN:B)
Such that f holds that for all QIQQOR Oc))
f (1o)) x. xz 15 E N..) = ((o))
Q. (z. -1,)
16

---

Published as a conference paper at ICLR 2025
I-GGNN+ is maximally expressive if holds:
ft * (o)) 2, ----a - jE EM. = = ((o, " -z, =NiB)
EQ ((3) 10 =. - =, 1 E EV (0)) (000. Q (c. d E EV.
We now prove that if we run one iteration of maximally expressive I-GGNN+ on a full graph, we can reconstruct it.
Theorem E.1. Let G = (A be geometric graph, where A is the full graph nodes, and X is an arbitrary d x n. matrix, then one iteration of maximally expressive I-GGNN+ can reconstruct X.
Proof. Assume we run one iteration of I-GGNN+ Then, for each node i, have
(1 æ3 1 [x]]]
then up to some rotation Qi E (3).. we know
Q (x. - 2z), ieljjr [m]]]
Then, we can reconstruct the point cloud by Theorem D.I
It's easy to see that I-GGNN+ simulate our I-GGNN the norm function is invariant under multiplication by Q E (3)). But (Pozdnyakov et al. 20200 Pozdnyakov Ceriotti (022) gave examples of full-graphs each I-GGNN can't t separate, but by what we proved above, maximally expressive I-GGNN+ can separate them. Thus, I-GGNN+ is strictly more powerful than I-GGNN in its expressive power.
F APPROXIMATION AND SEPARATION
It is known that tight connection exists between the approximation of invariant functions and complete invariant models Hordan et al. (2023).
In the context of our paper, discussed generic completeness. In particular, we showed in Corollary 5.2 that EGENNET with random parameters is complete on Gyenerie (d, N),, which denotes the set of all geometric graphs g = (A, X) with exactly N nodes, A connected, and E Rdx= generic. Accordingly,
obtain the following theorem:
Theorem F.1. Let K C Gg,nerield, N) be a compact set, feep K T continuous function invariant to rotations, translations, and permutations. Then feep is injective on K (up to symmetries) and only if every continuous invariant K RM can be approximated uniformly on K using functions of the form (fsep), where N is a fully connected neural network.
Proof. Assume, the one hand, faeP is injective on K (up to symmetries). Given continuous f: + RM we want to approximate, then, by Hordan et al. 2023). Ve >> 0 neural network N:
supgek N(f <E
On the other hand, assume by contradiction there exists G1 (A1. X1) and G2 (A2, X²) which are not related by translation, rotation or permutation, such that fren (91) = (Gz).
Define f()) Infgect XA g X1)ll, where g (), and G is the group of permutations, rotations, and translation. Note that this minimum is obtained as the product group of rotation and permutation is compact, and the translation can be bounded by the sum of the norms of the two graphs. Then, according to the Tikhonov theorem, our group is compact, and we take a minimum continuous function over compact set. Note that f is an invariant, continuous function such that f(G)) 0, and f(G)) > 0, but for each neural network (fF=eePP( = ((F=EP(())) and we
can't approximate desired function f with f(S2) accuracy, yielding contradiction.
n
17

---

Published as a conference paper at ICLR 2025
G PROOFS
In this section, we restate and prove theorems that have not been fully proved in the main text.
Theorem 3.1. [expressive power of I-GGNN] Let d be a natural number. Let F be an I-GGNN. Let A be a gruph not generically globally rigid on Rd. Then, generically fails to identify A. Conversely, if A is generically globally rigid on Rd and F is maximally expressive I-GGNN with depth = 1, then F generically identifies A.
Proof. Let (A, X) be a geometric graph, and assume that X is generic. First, assume that A is generically globally rigid. Assume that there is some geometric graph g' which is assigned the same global feature as G after single iteration. We need show the two graphs are geometrically isomorphic. The multisets of 8; and sf features in equation are equal, and in particular, both graphs have the same number of nodes n. and by relabeling if necessary, we can assume that s; = s for all i == ,,.... n. This equation, in turn, implies that for every node i,
{ [Imy]lii E = ( | E NN
In particular, the i'th node in G and G' have the same degree, so both graphs have the same number of edges. For any fixed (i which is edge of G, the distance ||a,a|| will appear exactly once in the multiset corresponding to s/ and s'J and will not appear in the other multisets. This observation implies that (i,j) is also an edge in the graph g'. Since the number of edges in both graphs is the same, deduce that A A'. By global rigidity, deduce that all pairwise distances are the same, and by Satorras et al. 2022 1, the two graphs are geometrically isomorphic.
We mention a theorem proved in Gortler et al.) (2010) for the other direction. Gortler et al. (2010) proved A is globally rigid if exists generic X such that (A, X)) is globally rigid. Thus if A is not globally rigid, for every generic X, there exists X' for whom distances along edges are preserved, but X and X' aren't 't geometrically isomorphic. By immediate induction on the number of layers, it can be shown that any I-GGNN cannot separate any pair of geometric graphs whose distances across edges are preserved. This concludes the proof.
Theorem 4.1. fexpressive power of E-GGNNJ Let d be a natural number. Let F be an E-GGNN. Let A be disconnected graph. Then, F generically fails identify A. Conversely, if A is connected and F is a maximally expressive E-GGNN with depth T 2 d + 1, then F generically identifies A.
Proof. Assume A is not connected. Let X E [g Let V1, V2 be two connected components of the graph, and let G' be the geometric graph whose adjacency matrix A' A, and where X' is obtained from X by applying non-trivial rotation Q not in the symmetry group of V2 z; Q Q. for all E V1, and setting dt = zj for all j E V/2. The two graphs are not geometrically isomorphic by construction. However, for any E-GGNN, we can easily see recursively that all features o!!)) constructed from X and X', respectively, will be the same, and therefore, the E-GGNN will assign the same global features to G and g'.
Now assume A is connected, and (Ggenerie (d, N), (d)).. By assumption, X is generic. Assume that the E-GGNN assigns the same value of G and G. We need to show that the two graphs are geometrically isomorphic. First, we note that since the two graphs have the same global features, they have the same number of nodes n, and by applying relabeling if necessary,
given two geometric graphs G and I in
assume that
Sü.
Vi - 1,..,..,,7
which implies that for every node there is some rotation R; E O(d) such that u. rotation equivariance, we know that R. (T) is the feature that we would have obtained by applying the maximally expressive E-GGNN to R₁ X. We deduce that T0 J xx. xz N. [R,,
(T) R
R (T) By
RR ".,
ش,)رة e NoB
The equality of multisets above implies that the node i has the same degree in A and Á. Since this is true for all nodes, A and Á have the same number of edges. Moreover
[||m 2111, E EN
|||a: æ3 j N;
18

---

Published as a conference paper at ICLR 2025
Since X is generic, for every edge (t.j) A the distance ||,, - =z,l will appear only in the 1-hop multi-sets corresponding to the and j nodes. Thus, they will appear only once in the I-hop multisets corresponding to the second graph's 's and j nodes. This implies that (i,j) is an edge in A too, and
( 20) z; By. Vj NG
Since the two graphs have the same number of edges, it follows that A - A. We now show recursively that for all 1 I S - we have of -t = R - and æ; 22 Ra(ă; &t) for all j that is a t-hop neighbor of (we say j an t-hop neighbor of i, if there is path of length most from i to j).
We have already proved the claim for & 1. Now we assume correctness for and show for t 1. Since by the induction hypothesis we know that 0² R, -t for every j which is hop neighbor of i, we deduce the multi-set equality
T' (t+1) B. - mylk E NN 1 R (R (1+1) R,( . E EN | k
Since we know that the pairwise norms of X are all distinct to to the genericity of X, and also that for every edge (j, k) we have the norm equality ||æz, æxl = || - æx/1, we see that necessarily
T-(++1)
0 12 T+1+1 and x, 3 R, ..))
Uk
Now, every k, an t + hop neighbor of i, is connected by an edge to node j. an t hop neighbor of i. By the induction assumption we know that æ; 22 = R3 ( # We deduce that 32 32 2; 3jj + 2j 2t R& 3 + .t. xx) R2 .x))
for all + 1 hop neighbors of i. Continuing with this argument inductively, we see that for all T d + hop neighbors i of i, we obtain
T; 3b Ra .xk)
and in particular
xx
|
tx
for all d + 1 hop neighbors. By global generic rigidity of the d + power graph of connected
graph (Jordán & Tanigawal 2022; Cheung Whiteley (005), it follows that the two graphs are geometrically isomorphic. Thus, previously, reconstructed the combinatorial graph, and now reconstructed the geometric graphs; we are done.
n
G.1 PROOF OF MAXIMAL EXPRESSIVITY OF EGENNET
This subsection is devoted proving Theorem 5.1 oon the generic maximal expressivity of EGENNET. This proof will require some background on the finite witness theorem from Amir et al. (023):
Background on the finite witness theorem Before we prove the theorem, we review some definitions and results from Amir et al. (2023), which we will use for the proof. The main tool we require from Amir et al. (2023) is Theorem A.2 from that paper, the finite witness theorem. We state it here in the special case where the parameter space is Euclidean, and the function F is analytic in the parameters:
Theorem G.1 (Finite Witness Theorem, Amir et al. (2023). ). Let M R be a r-sub-analtic set of dimension D. Let F M. x IR99 + R. be o-sub-unalylic fanction, and assume thut F(z; 0) is analytic as a function of for all fixed z E M. Define the set
N {z Ml F(z; 0) 0, A0 R?).
Then for Lebesgue almost every
@ ((0+1)) (D+1)
= = [ F(z;0
0, Vi = 1,... D + 1}.
(8)
The original statement in Amir al. (202)) discussed generic (Q() ...., @(D+1) D+1 in the sense defined in Amir al. (2023) particular, this implies the "Lehesgue almost every" statement used here.
19

---

Published as a conference paper at ICLR 2025
We note that this theorem also holds when the output of F is a vector in R which is what will use in our proofs below. To the theorem holds for function F M x RR9 IR can define a new parametric function F with additional parameters a E Rdd
Remark:
0 = (F(z:
and use the theorem for F, which has scalar output, to deduce the theorem for F.
The finite witness theorem assumes the domain is a a sub-analytic set. The full definition of a-sub- analytic sets is rather involved, and we refer the reader to Appendix A in/Amir et al. (2023) for full definition. Rather than giving a full definition here, we will recall the properties of these sets, which will need.
The class of a subanaltyic sets in Ied is rather large. In particular, it contains all open sets in Rd, all semi-algebraic sets in 12d (sets defined by polynomial equalities and inequalities, like spheres and linear sub-spaces), as well as sets defined by analytic equality and inequality constraints. The class of subanaltyic sets is closed under countable unions and finite intersections.
--sub-analyti sets are always a countable union of smooth manifolds. The dimension of sub-anal -nalytnl set the maximal dimension of the manifolds composing it.
A o-sub-analytic function is function whose graph is a a sub-analytic set. Analytic functions are, in particular, o-sub-analytic. When a sub-analytic function is applied to a sub-analytic set, the image is a a sub-analytic set whose dimension is no larger than the dimension of the a sub-analytic domain Amir et al. (2023).
We can now restate and prove Theorem 5.1
Theorem 5.1. Let d, N, T be natural numbers. Let F be maximally expressive E-GGNN of depth T, and let Fg denote the EGENNET architecture with depth and 2N channels. Then, for Lebesgue almost every choice of network parameters 0, we have that for all generic 9, G Cx((),
F(G) F(() + Fo(G) =o(()
Proof. In the proof, we consider the set of all generic geometric graphs in Gv (d). We will prove the theorem for an even larger set: the set G Gdistinct (d) of all geometric graphs in Gy Gy(d). which
additionally satisfies that for any distinct edges (i.j) and (s,t) in the graph, < || - 2; * ||æ. lr. Since polynomial incqualities with integer coefficients define it, we note that Gdistinet (d) contains all generic graphs with & N nodes. The advantage of considering G Gdistinct (d) is that the set of all geometric graphs in G (ddistintt()) (d) of the same cardinality n S N can be thought of as subset of Rax. ④ Rn Since a constant number of polynomial inequalities defines it, it is semi-algebraic set, and hence, in particular, o o-subanaltycc, so the finite witness theorem can be applied. In contrast, it is unclear that the of all generic points of fixed dimension a subanaltyic set.
Our goal is to show that for the networks described in the theorem, for almost every choice of parameter values, all functions described in the procedure are injective. To be more accurate, let us introduce some notation given an arbitrary pair of geometric graphs
g = XA, 9 = X)
in our domain Gdistinct (d), we denote the features corresponding to the first graph by ()))) 8, and gglobal as in the main text, and the features corresponding to the second graph by 6!0) 8; and galobal The neighborhood of a node i in I is denoted by Ni. The number of nodes the two graphs is denoted by and m, respectively.
We need to show that for all t O...., - and all nodes of G and k of g.
(++1)
(I+11 if and only if ((;; - ",,,-x,,00 v/ (0)) ).j EN = (2 - 2, 25,08/065 )b E N (9)
k
8, a if and only if 3Q E Od)) Q (T) =
(10)
gklobal galobal if and only if {s,li 1,...,n,, n (3 1.....,m m
(11)
20

---

Published as a conference paper at ICLR 2025
Our first step for reaching this result is using the finite witness theorem, similar to what done in
Hordan et al. (2023). ) We note that the features we are interested in are composed of C = 2Nd + 1
coordinates, denoted by q 1, ,,..., C, which are of the general form
Fig Li
((+1)
(1+1) F((X, V(O, X, V0 t= --
(12)
$1
(t+1)
b.g
(1+1) Fr(Va) ;
(13)
global gainbal FFFiI((1)) ( Bn, 8 smi 0g.T+1)
(14)
q
g
where ag,t denote the parameters of the appropriate function, v(t) is the concatenation of all
features v. (t) and ()) is the concatenation of all features og In essence, we claim that by the
finite witness theorem, for almost every choice of network parameters, we will have the following equalities for all geometric graphs G, 9 satisfying the theorem's assumptions:
((+1)
k ((+1) 0 if and only (X V X, V( ar) = 0, Va
(15)
8; $t = 0 if and only if (V V a.) V/a
(16)
global
gelobal 0 if and only if Fr+1 ($1 ..... nn
mm a 0, Va
(17)
In other words, the finite witness theorem enables us to reduce the problem the problem of showing that some choice of network parameter exists, which enables separation.
Some explanation is needed to the details of how the finite witness theorem is applicd. It is convenient to think of the network parameters being chosen recursively. For t = 0, the finite witness theorem allows applies. Formally, to do this, we need to split into a finite number of cases: once the number of nodes n and m in the two graphs are specified, as well as the combinatorial graphs A, Á and the nodes i, k, we can think of Fo as a function which analytic in the parameters, and --suanallytic on its domain (the norms used in the network are semi-algebraii functions, and hence o-subnaltyic functions. All other functions used in the network are analytic). The function Fo operates on the domain of pairs X E _dxx X E gdxm which satisfy a finite number of polynomial inequalities. This domain is semi-algebraic and has dimensions d(n + m) < 2Nd. Therefore, we can apply the finite witness theorem with C = 2Nd + 1. Next, once the parameters aig.t are chosen for all t < tt, we can choose the parameters ag again using the finite witness theorem. Central to the usage here is that, once the previous parameters were fixed, the features the step are an image of a o-subanaltyic function applied to a pair (X, X)). Therefore, the intrinsic dimension of the t' generation features is no larger than 2.d + 1 C' (for more on this argument, see Hordan al. (023 This concludes the recursive definition of parameter choice. By Fubini's ' theorem, one can verify that, in fact, for Lebesgue almost every parameter will be 'good'' It remains to show that
choose the parameters 02g.0: 9 ..... C in equation 12 so that the theorem
The right hand side of equation 9 holds if and only if the right hand side of equation 1 holds
(18)
The right hand side of equation 10 holds and only if the right hand side of equation 16 holds
(19)
The right hand side of equation holds if and only if the right hand side of equation 17 holds
(20)
We now reformulate these three claims as three lemmas.
We use some fixed analytic non-polynomial function in the following lemmas. We say that ø is basic analytic network it is of the form
o( a, = o(a-))=(a++
for some a E R E R.
Our first lemma will show 18 where 2/ will assume the role of x; Zz.-
Lemma G.2. Let 21,..., 2n and .,...., &m be non-zero vectors Rd. Additionally assume that || < ||2||| ... ||=||| and || | <... < ||
21

---

finite number Published as a conference paper at ICLR 2025
Let U1...., Un and Ui,.... Bm be matrices in R and denote v, (v1,1-- .... V1,C) and (fi,1 (,,c). If for all basic analytie neural networks (0)0) (i have that
m
l (I3)))))))))
R (13))))aee)
(13)))
6 (12,g
(21)
then
(11, (Zn, Un) B = U (21, 01), (2m, 0m )
We note that this lemma is slightly stronger than we need since, in contrast with the original MPNN, we do not use the norms of Vie as features.
Our second lemma will show T9
Lemma G.3. Let v = (V),.... vC) E RdxC and = (f)...., 00) E Rdxc If for all E RC we have that
C
1 Uvvll Σ 0,uell
c=1
then there exists an Q E (dd such that Qu de for all =I,.,... I,...,C. C.
For proof of this lemma, see Section 3.2 in Dym & Gortler 2024 Our third lemma will show 20
Lemma G.4. Let , Sn and .,...., 8m be vectors in R2d
If for all basic analytic Φ, we have that Ei ((s:) > d(B:) then 1 8n
(.,,..., 8mB. J.
For proof of this lemma, see Proposition 3.2 in Amir al. (023)
remains to prove Lemma G.2 We note that equation 21 holds for all basic analytic networks (f0))cc= O,..., C, This equality is also true if each g(e) a linear combination
of shallow neural networks. Next, since we are only considering the values of dfe)) on a fixed finite collection of inputs, and since linear combinations of shallow neural networks with analytic (or even continuous) non-polynomial functions can approximate any continuous function uniformly on a compact set (and in particular finite set) Pinkus (1999), it follows that equation G.2 holds for all continuous g(e).
Next, we consider the norn multisets:
S = [ [II I... $ = 11 || Il-
We claim that S. We first show that S C S. Fix some in {1...., .l....,,,,, n), need show that || S. We define continuous function f such that f*[[2z,])) for all i o s, and for all j = 1,..., ......,, such that the norms ||ققا| and ||=,|| are not equal. We claim that there exists for which the norms are equal. Otherwise, we choose the continuous functions ((e)) c 1...., .. to be the zero functions. and choose ((0) be f*. This will lead the equation
and ([1 0 ["( Il)
2, G.2 which contradicts the assumption that 2, + 0, so we see that S C S. symmetric argument shows that $ C S and so S. We deduce that m and || || || for all n). i 1..... n. We can now conclude the proof: fix an arbitrary n1....,n). Choose 2i()) = f and take the other ((() be zero. Then G.2 gives
Similarly, for an arbitrary index g in (1, (l...., in (0, 1, C}. In this case G.2 gives
C',, we can choose Φf9) = fc and Ø(c)) = for all c e
0gg 0jg O.
This concludes the proof of the lemma and the proof of the theorem.
22

---

Published as a conference paper at ICLR 2025
G.2 COMPLEXITY
Running EGENNET for T' iterations with C' channels requires OCC d degs) elementary arithmetic operation for every node i, every iteration (. Overall, this requires OC d N davg T) to run EGENNET, where dang denotes the average degree in the graph. This is linear in N, which dominates the other terms the complexity bound. If we set C = 2Nd
as required for maximal expressivity in Theorem 5.1 then the complexity will be quadratic in N. which is less by factor of n then (Delle Rose et al. 2023 Li et al. 2024a), and by a factor of n² than Hordan et al. (002)). We also note that the cardinality in the finite witness theorem, the main tool for our proof, depends on the intrinsic dimension of the input and not the ambient dimension. Thus, under the standard manifold assumption Cayton et al. (2008), which asserts that data in learning tasks typically resides in manifold of low dimension r, embedded in a high dimensional Euclidean space, the proof can be adapted show that the number channels necessary for maximal expressivity is only 2r Thus, under the manifold assumption, the complexity of EGENNET is linear in the number of nodes N.
H ADDING NODE AND EDGE FEATURES
This section explains how we incorporate node and edge features into our architecture and theory.
A featured geometric graph is 4-tuple G = (A1. X1, F1, E1) where as before A is n by adjacency matrix, and is a n by d matrix denoting node positions. F is a n by d, matrix denoting node features (without the action of rigid motions), and E is We denote the feature at a node and edge (i, by fa (a column of F) and fi.j. respectively.
de tensor of edge features.
We incorporate edge and node features into EGENNET by slightly modifying the aggregation step to
(I+1) U2g
Σ
(f)
(6.0 æ3y1. [15l)) x.,)+
Vn
JEN;
In our analysis we will take w/!h.)) dRd R and wh(a))) Rd E be simple linear functions (f+) (((0)) + b((-0),
a..0)) fúg + blt.0)
In practice, in code, in Li et al. (2024a).
slightly more complex function involving radial basis functions as
To extend our analysis the case of node and edge features, we first extend our definition of isomorphism of geometric graphs to include edge and node features.
Definition H.1. Given two featured geometric graphs
G = X FI,
H X2,
and H are featured geometrically isomorphic if there exists permutation matrix P, rotation matrix Q, and a translation t such that:
1. A. = P. A PT.
2. X, P X1 Q +
3. F. P.FF
4. Eg = P. pT
where P. E, p should be understood as operating element-wise on the n,, matrices of dimension which compose the tensor E.
We then prove the following theorem: generalization of Theorem 5.2 the featured graph case.
23

---

Published as a conference paper at ICLR 2025
Theorem H.2. Let N, d. de. d, be natural numbers. Let F6 denote the EGENNET architecture for featured geometric graphs, with depth T = d and C = 2Nd + de + +d + channels. Then for Lebesgue almost every 0, we have for all featured graphs 9, E Gx(d) which are generic and connected,
Fg Fo(G) = 9.6 are featured geometrically isomorphic
We note that the assumption that the geometric graph is generic is only on the position coordinates X. The statement will hold for all node and edge features in this case.
Proof. We explain how to modify the proof of Theorem 5.1 to obtain this result. First, we note that the number of channels was adapted to take into account the higher dimensionality of the data now that node and edge features are included. The finite witness theorem can be applied with this adapted dimension, as explained in Theorem [5. Thus, we only need show that, for given featured graphs G, 9 satisfying the conditions of the theorem, if for all 0 we have that Fo( = (9) then G and 9 are featured geometrically isomorphic.
Now, let assume that, for all & we have Fo( (9). We can obtain all the results we had for the case where there were no additional features by choosing the parameters
! (1.4) ((6-)
((-9)) b(..2)
so that whf-0) = 1 = whe and the effect of node and edge features on the architectures 'cancelled out'. In particular, can deduce that, after appropriate permutation and rigid motion applied to the data, the graphs have the same number of nodes n,, and for all node i and iteration I, we have
0.0 E;
Now, by setting (((-).)) 0 for c 2 1, and considering ((t...0) which depend only on the first coordinate, deduce that
Σ JEN;
(wilt (ft) (f.)) w11h00 (f:) (f.nt (olt.00) 2,11)(z - 22,)
for all choices of parameters of the functions (t.g) (lt-)) and (tt.n.0), As we showed the proof of Theorem 5.1, this equation implies that this equation will also hold for any continuous (f(t-9.0) (and any choice of parameters of the other functions) since the span of all such basic analytic functions is dense. In particular, for fixed i.j. we can choose (ft.a.0) to be a continuous functions with ((t.,. - æzyl)> = and (f(t-9.0) (I|æ: æxll) if l + j. Inserting this into the last equality
obtain
(1(l (ft) (f.s)) (() vel.o0 (fri)) (æ:; xz5)
by genericity x;; 2j + O, and so we deduce that (lt (fi) (1(1.) (fr)) (1-0)) (fi) v.l1-)) =0 =0
for every choice of function parameters. Setting a (t-9) 0, (1.9) =1,b(
0 we obtain that
a. (fg fu)) 0. Va. Rdd
and therefore fuj fug O. Similarly, setting de (t.9) 0, (1.4) 1, (6.0)) 0 we obtain that
On (f. f.) 0, Va, Rd and therefore Si f: =0. This concludes the proof of the theorem.
I ADDITIONAL EMPIRICAL RESULTS
k-chain results Here, we show the results of the k-chain experiment for k = 4. As can see, only our method EGENNET and GVP et al. (2020) succeed using the minimal number of blocks. This experiment illustrates results for = 12. As can be seen, we are the only ones succeeding with the minimal number of blocks, and other models need higher number of blocks to succeed in distinguishing.
model's 's ability to distinguish very sparse graphs. Next, show
24

---

Published as a conference paper at ICLR 2025
Table 3:
Separation Learning of 4-chain paths Figure We show the learned accuracy over ten trials for each model, depending on the number of blocks. We show the minimal needed number of blocks (3) is sufficient for separation, and only [ing et al. (2020) also succeeded (among equivariant models working the sparse graph) all 10 trials using 3 blocks.
(k = 4-chains)
Number of layers
GNN Layer
[ +
| +
2 +
GWL
50%
100%
100%
100%
100%
Equiv.
E-GNN Satorras
2021
50.0
50.0
50.0
200
100.0
GVP- Jing et al. 2020
50.0
100.0 1:00
100.0
100.0 1.00
100.0
TFN Thomas el al. 2018
5..0
50.0 2.0
50.0
80.0 24.5
MACF Batatia et al.
2022
+0.
90.0 - 2000
90.0
95.0 15.0
95.00 +1.00+15.0
(GENNET(OurS)
50.0
100.0 0.0
100.0 0.0
100.0 6.0.0
100.0 0.0
IGWL
50%
50%
50%
50%
50%
Inv.
SchNet Schütt et al.
2018
50.0 =000
50.0 +.0
50.0 =00
50.0 +0.0
50.0 +.0
DimeNer Dinteer[Gasteiger
2020b
50.0
50.0 -.0
50.0 -00
50.0 +0.0
50.0 a.
SphereNet Lau 2021
50.0
50.0
50.0
50.0
50.0 ::00
SchNet grap Schütt ct al.
2018
100.0 a.
100.0 0.0
100.0 a.0
100.0 2.0.0
100.0 a.0
SchNetglobal Schütl al.
2018
100.0 a.
100.0 0.0
100.0 2.0
100.0 0.0
100.0 0.0
Hard examples This section presents the results mentioned in Section 6.1 We use a dataset of four Seefeaultto--eppaatee pairs of point clouds. Three (Hard 1, (ard2,Hardd are taken from Pozdnyakov ctt al. (2020). The last pair, "Harder," taken from (ooddnyyyy & Ceriotti (2022) and is an example of non-isomorphic pair that I-GGNN models cannot distinguish. We show succeeded in separating all tuples with a probability of 1. The tested models are EGENNET, GramNet Hordan et al. (2023), GeoEGNN Hordan et al.) (2023), EGNN Satorras et al. (2021). LinearEGNN, MACE Batatia et al.
(2022). TFN Thomas et al. (2018), DimeNet Gasteiger et al. 2020b), GVPGNN Jing et al. (2020)
and are taken from Hordan et al. 2023).
Chemical property experiments with full statistics the table for the chemical property prediction tasks in the main text, Table was produced using the protocol from Zhu et al. (2024). In particular, The seed that did best on the validation set was chosen, and its results on the test set were reported.
each method was run with three different seeds.
Table presents each task's 's mean and standard deviation over 3 seeds. As we can see, in most tasks, the standard deviation is rather low, and the results are qualitatively similar to those obtained Table 2 In particular, in the tasks in the Kraken and BDE datasets, outperform the competitors, often
Table 4: Separation Learning of 12-chain paths Figure 2 trials for each model depending on the number of blocks. As we can see, we are the only ones that succeed with the minimal number of blocks (7), and other models need many more layers to show high Performance.
We show the learned accuracy over ten
(k = 12-chains)
Number of layers
GNN Layer
[
[ +1
[5
[ +
[ +
Maximally expressiveness E.GNNN
50%
100%
100%
100%
100%
Equiv.
E-GNN Sutorras al. 2021
50.0
50.0 2:0
=0.0
50.0 200
95 15.0
GVP-GNN Jing et al. 2020
50.0 =00
50.0
60.0 2u0
50.0 200
60.0 20,0
TFN Thomas et al. 2018
50.0 =0.
50.0 o.0
50.0 =o0
50.0 =00
50.0 0.0
MACE Batatia
2022
50.0 =00
50.0 om
50.0 =00
50.0 =00
50.0 +.0
EGENNET(OUrS)
50.0 -00
100.0 n.0
100.0 +0.0
100.0
100.0 a.0
Maximally exprossivenent L-GGNN
50%
50%
50%
50%
50%
SccheetSchitte et al. 2018
50.0 =0.
50.0 0.0
50.0 +0.0
50.0 0.
$0.0
Inv.
DimeNet Gasteiger
20206
50.0 =.o
50.0 0.0
50.0 +0.0
50.0 o.
50.0
SphereNet Lm et al. 2021
50.0 =oo
50.0 0.0
50.0 +..0
50.0 o
50.0 a0
SchNetran grap Schütt 2018
100.0
100.0
100.0
100.0 =00
100.0
SchNet, fer Schutt
2018
100.0 +
100.0 0.0
100.0 +.0
100.0
100.0
25

---

Published as a conference paper at ICLR 2025
Table 5: Results on challenging point clouds Pozdnyakov Ceriotti 2022);
Pozdnyakov et al. (2020).
The table shows the performance of different models on progressively more diffcult tasks (Hard] to Harder).
Point Clouds
Hard1
Hard2
Hard3
Harder
GramNet
1.0
1.0
GeoEGNN
0.998
0.97
0.85
0.899
EGNN
0.5
0.5
0.5
0.5
Results
LinearEGNN
1.0
1.0
1.0
0.5
MACE
1.0
1.0
1.0
1.0
TFN
0.5
0.5
0.55
0.5
DimeNet
1.0
1.0
1.0
1.0
GVPGNN
1.0
1.0
1.0
EGENNET (ours)
1.0
1.0
1.0
1.0
by a large margin. In the Drugs 75K, we obtain comparable, but somewhat higher, results than the best method (while in Table 2 in two of three Drugs-75K cases, our results were the best by small margin).
Time measurements To compare running time with other models, measured the execution time for each model on the 12-chain task with all models using 128 hidden feature size. The results] show that our running time is on par with the competitors.
Norm Accuracies To heuristically estimate 'how generic" the molecules in the chemical property datasets (Axelrod Gromez-Bombarellyy 2022, Gensch al. 2022 Meyer et al. 2018) we considered are, we computed all norms of atoms in each (centralized) molecule and counted the number of unique norms relative to the total number of points. We considered a norm unique its distance from all other norms exceeded a specified threshold and considered various threshold values. The results g indicate that the norms exhibit considerable variation, suggesting that the molecules are close to being generic. This supports the conjecture stated in the main text that the surprising success of our simple method, compared to more expressive methods, is related to the near-genericity of the molecules these datasets.
26

---

Published as a conference paper at ICLR 2025
Table 6: Raw performance data (mean + standard deviation) of ID, 2D. 3D, and conformer ensemble MRL models all taken from Zhu et al. (2024) in terms of absolute test error. Our model the 3D category, named EGENNET.
Model
FA
Burfs,
Burl
RDR
Rondam Forrst
0-485--0.007 0010
044477-00000
022032400001
0.400000
O 4001-00000000
0.2758-0,0180
O. 0.1521-00088
N0140.27
1.TM
0.4
0:4648:00002
0,2505200000
051424004111
0.201366
0.192440 0023
2.220007
Tramsfomer
0.66170000033
03611200013
049299000399
0.254400.0099
0436
0312
40006000041
0.1200e1
GIN VN
04361600009
0416
033667000051
0,242200.0555
27469.2
2D
ChemPPa
0.4955000004
0:4417-00045
03441-00022
0 54534000444
O. 0.N03-6..0886
0.1948-0015
6660
20
GrapHCPS
0435150020
022124000244
0,2056601155
2.466011
3D
SchNNe
043944000002
0:207:00001
0.2343000009
0.3293800068
0:549220041
0,29%66.0111
0.186120
2.5400.00
DineNette 0,444220.0077
04233
022655800075
0.310H200007
04:744200097
0,20975000100
0.152660
14442000
GenNNi 0.006900:0007
0.39224000044
022000000225
037544000056
0.179266.0099
0.1635
16510.30
0,45050000411
02334600000
0364
0.477
ClotNet
0105
02575000002
8647760022
0.285
2000000
30
LRPTNe
0.4144000007
0:306-00000
0:3073400012
01 6401-000000
0.217666.0010
1
EGeKNerTOun)
04251=00163
0.185680.0044
0.154599.0019
3D Sampling
SchNei
0,4422000000
042322000422
022433000022
03235200147
04598220041
0.20666.0111
0.1739400422
19760.01
Sampling
DiaeNetee
0,3955800032
0:2177200400
02232200043
033233000300
041536200206
0,2377600122
0.1561200241
1.4750000
Sampling
GenNei
0,406:1000155
0:3910:00004
02644
346330002222
0.17666.0009
08418000003
16000.00
Sampling
02331
03444100161
1.9260.01
Sampling
ClotNet
0.4330000004
04257
02535601034)
05524
0196022000744
0.28420001009
0.1752
25120
3D Sampling
IRPTN
0418040110
02141-00084
0.212066.0077
SchNee
Mean
DAS83-00000
0:4410000015
02371-000
0:9075400111
0,22334000000
01661960000
2
DaupSee
0:437:000065
0.4196000010
023855000066
03105100081
0422400444
0.249:6.0234
0.1335
2060..22
Attetion
0,45568800055
0:4822200225
0228002000077
02704400187
045176200322
0,202450,0855
0.1443200043
2.4220000
DimeNees
Meas
0,4485200086
0:4302200079
024255800000
02
038284300031
0,195950.0059
0.126540
1.7950112
Deeptet
03668000000
1.7560011
Anention 0,4155:000044
0463
0370
03369600.2299
0.189960.000
2.760.21
Mean
0,505500053
04344-00221
02635400051
57530000000
0.1071-0015
1940.06
DespSct 0,187:000022
0:402:000122
02169
02313100006
6 039610000000
0.1580
009474000122
25500
Arsmtion 0/2122000017
04221-00007
0 0:20000
022200000000
0 055440001777
0.178H6.0155
0. 01138600009
PuNN
Meas
0,49912000024
0.4125200044
022602000022
02677200222
033902200233
0.181760.009
0.147220
1.8760166
DeepSet 0/46714800071
04266
02224480066
033099900192
0.1099800111
0.1324480001
206000
Attenion 0,4641280016
0:4567200004
02477280049
03495500040
04:092300177
021135000005
0.1506En
2260011
DaspSat 0439600077
040033000044
021994000033
047422000111
23500.04
Amtmiion
04107-00045
D2 0222600001
039744000767
02177-000866
206-0 14
LEFTNe:
Meas
0,4402200002
044677800066
021835000077
022499000001
0 033643200052
0,29980000166
0.13
2,042.000
DeepSet 04166600003
0.30522000000
02069800222
0226-8800130
033866000070
0.202
2.160030
Atcenionn 0:4299000009
0:4072200047
021955200011
03161200116
043346200222
0,201726.00233
0,150540
2.6360.15
27

---

Published as a conference paper at ICLR 2025
Table 7: Running times of different methods the 12-chain problem.
Method
Time (in secs)
SchNet Schütt et al. (2018
53.3
DimeNet Gasteiger et al.
(0020b
222.6
Sphere-Net Liu al.
(002))
360.9
EGNN Satorras et al.
2021
98.8
GVP Jing et al.
2020
222.4
TFN Thomas al.
2018)
268.1
MACE Batatia al.
2022
440.6
EGENNET (ours)
112.0
Table 8: Norms repetition percentages at various thresholds for each dataset.
Threshold
Drugs
Kraken
BDE
0.0
1.0
1.0
1.0
le-4
0.9967
0.9804
0.9950
1e-3
0.9678
0.9139
0.9573
le-2
0.7230
0.5217
0.6698
28


Reviews:
[{"review_id": "FPNI6KX970", "reviewer": "Reviewer_CwLH", "summary": "The paper proposes a method for distinguishing between geometric graphs based on the connectivity of the graph structure. Moreover they propose an equivariant architecture which they claim to be maximal in expressivity.", "questions": "Below is a partial list of incomplete work:\n\n1) The paper is not formatted to the ICLR standard, e.g. it is missing the header **Under review as a conference paper at ICLR 2025**.\n\n2) The inline citation format is incorrect.\n\n3) Section 6.2 contains a \"TODO\" placeholder.\n\n4) The second paragraph of Section 5 is two egregiously run on sentences.\n\n5) Tables 2, 4, 5, and 6 extend beyond the page margins, with Table 5 exceeding the page to the point where the results are unreadable.\n\n6) Table 4 uses an incorrect title for the model, referring to it as GenNet.\n\n7) Table 6 is a low resolution image of a table and has discrepancies in the reported results by comparison to Table 2.\n\n---\n\n1) The definition of \"identifies\" appears to be equivalent to the definition of a complete invariant function F. Per Section 1 and Appendix B: \"The main text discussed (sic) how generic completeness can be achieved using I-GGNN when the graph is globally rigid.\" Is there a reason that the terminology of completeness that appears in the introduction and appendix is dropped in the definitions of Section 2 in favor of identifies? Maintaining consistent terminology would significantly enhance clarity.\n\n2) The cutoff tables 5 and inconsistencies between Table 6 and Table 3 make it difficult to interpret the significance of the reported results. Could the authors please explain the discrepancies between the Tables.\n\n3) In Kraken BurL and BDE it appears that EGenNet significantly outperforms the previous state of the art, especially for BDE. Could the authors provide an explanation for why this major improvement occurs for the BDE dataset?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper utilizes global rigidity to develop a novel direction for developing geometric graph neural networks.\n\n EGenNet achieves state of the art performance and makes significant improvements on a few datasets.", "weaknesses": "I have two major concerns regarding the submitted work.\n\n1) Incomplete Submission: The paper contains 'TODO' placeholders and formatting issues, indicating it is an unfinished draft. This severely hinders the ability to conduct a thorough and fair review and compromises the integrity of the review process and the conference's high standards.\n\n2) Lack of Consistency and Discussion in Empirical Results: The empirical results lack completeness and coherence. Key sections are marked TODO, and there are inconsistencies between tables, making it difficult to interpret the significance of the findings. A more thorough discussion and clear presentation of results are necessary to support the paper's claims.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "t5TGocwG9P", "reviewer": "Reviewer_BXAA", "summary": "The present manuscript  investigates the expressive capabilities of MPNNs for sparse geometric graphs, and it focuses on applications in fields such as chemistry for benchmarking. The authors differentiate between Equivariant Geometric GNNs (E-GGNNs) and Invariant Geometric GNNs (I-GGNNs), claiming that E-GGNNs can separate connected graphs, while I-GGNNs require globally rigid graphs for separation.\n\nThey propose EGENNET, a simple E-GGNN model intended to maximize expressiveness in sparse settings, and benchmark its performance against alternative models.", "questions": "Given the reliance of the paper's results on the genericity assumption, can the authors motivate clearly the need to study the genericity case? What can we say about non-generic spaces, and why are they important to their experimental results? e.g. for the molecular property prediction tasks.\n\n\nUPDATE: Given the answer by the authors and their efforts to fix the presentation issues of the paper, I'm raising my rating.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "1. The paper is clear on addressing the question of expressivity on the specific area of sparse graphs, which is relevant to applications like molecular modeling, where the computational cost of fully connected graphs is prohibitive.\n\n2. The authors provide a theoretical analysis distinguishing the separation power of E-GGNNs and I-GGNNs based on graph connectivity and rigidity, which adds clarity to the strengths and limitations of each approach.\n\n3. The proposed architecture seems to be fairly simple, providing a potentially expressive model that is easier to implement than complex alternatives like (d−1)-WL-based models, aligning with the need for practical applications in sparse graph settings.", "weaknesses": "- I find the connection of generic matrices with the use cases of graphs complicated. The authors do not show a clear motivation on defining expressivity over generic spaces for the use over graphs. Can the authors motivate better the analysis over generic spaces? What happens in the non-genericity direction?\n\n- The tradeoff between efficiency and expressiveness is confusing. It seems that still if we want to achieve maximal expressiveness leads to quadratic complexity (G.2 Section), not having a clear understanding of the expressivity loss, once we set C < 2Nd + 1.\n- The presentation is very poor. The theoretical analysis is hard to follow. There are a lot of typos, and inconsistencies. There are forgotten TODOs in the main text (check Section 6.2), and elements of the paper are not even visible (for example Table 5 does not fit the page).\n\nOverall, the paper shows some elements of haste, and I would suggest the improvement of the writing and the presentation of the theoretical as well as the empirical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "P4kgBhPiHa", "reviewer": "Reviewer_X9UN", "summary": "In this work, the expressive power of in- and equivariant message-passing neural networks (MPNNs) on geometric graphs is studied, where in contrast to prior results that assume full graphs, arbitrary graph topologies are considered. Here, the authors focus on *generic* separation, meaning that the analysis is restricted to graphs without certain symmetries. The analysis reveals that a graph can be generically identified by an invariant GNN iff it is generically globally rigid, and by an equivariant GNN iff it is connected. The authors then introduce a maximally expressive equivariant GNN, called EGenNet, which can generically separate all connected graphs. The expressivity is empirically verified on toy graphs, and significant improvements on benchmarks for chemical property prediction are reported.", "questions": "- Did you conduct experiments on how EGenNet compares to the other benchmarks on non-generic geometric graphs? A step towards this could be looking at the levels of symmetry that the graphs in the chemical dataset exhibit (i.e., distances between nodes or graph automorphisms), and analyzing the performance of EGenNet vs. the other benchmarks on such graphs.\n- In section 5.1, the EGenNet architecture comes a bit out of nowhere. Perhaps, a paragraph with an intuitive explanation why the update step is defined as it is in equation 5 and how it relates to maximal expressivity would add to the overall understanding of the method.\n- The results for chemical property prediction could be discussed in more detail. Specifically, a further analysis of the number of parameters or training runtimes of the different models compared in Table 2 would be interesting to see.\n- There are lots of presentation issues in the script that should be fixed, e.g., inconsistent usage of `\\citep`/`\\citet`, misalignment of tables (Table 2, Table 4, Table 5, Table 6), inconsistent caption alignment, Table 6 seeming to be a screenshot from its original source, or \"todo\" comments (line 451).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Analyzing the expressive power of sparse geometric GNNs is a relevant research direction, closing the gap between theory (where the attention has been mostly on full graphs) and practive (where typically sparse graphs are considered, e.g., via distance cutoffs).\n- The characterizations for the expressivity of in- and equivariant GNNs are simple and practical, and are therefore relevant to the research community, in my opinion.\n- The empirical results are quite strong, as EGenNet outperforms practically all graph ML methods and geometric GNNs on the Drugs-75k, Kraken, and BDE benchmarks.", "weaknesses": "Although I understand that the assumption of genericity makes the analysis tractable, this remains a significant limitation. Real-world geometric graphs, particularly in the chemical domain, can exhibit lots of symmetries that cannot be overlooked.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sjrvkrUmyu", "reviewer": "Reviewer_K13L", "summary": "This study studies expressivity of message-passing neural networks (MPNNs) for 3D graphs. Unlike earlier research that assuming fully connected graphs, this work demonstrates that MPNNs with equivariant features can distinguish between generic non-isomorphic geometric graphs when the graphs are connected. For cases where only invariant features are used, the ability to differentiate graphs is ensured for those that are generically globally rigid. This work also proposes a new architecture called EGENNET, which utilizes equivariant features and performs well on both synthetic and chemical benchmarks.", "questions": "Please refer to weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Solid theoretic results. The \"generic\" describes degeneracies cases well.\n2. Separation experiments are clear.", "weaknesses": "1. Considering generic geometric graphs only rather than all geometric graphs significantly weakens the significance of theoretic results. Though degenerated cases are rare, they can affect model's performance on generic graphs as neural networks are smooth. The inclusion of high-order irreducible representations solves these cases and boosts performance significantly.[1, 2]\n\n2. Previous work also considers expressivity on geometric graph without assuming fully connection. [3] proves in that in non-degenerated cases, MPNN with equivariant feature can distinguish connected graphs, while MPNN with invariant features only cannot.\n\n3. Experiment should includes graph force field tasks on qm9 and md17 as previous works [2].\n\n[1] Nadav Dym, Haggai Maron. On the Universality of Rotation Equivariant Point Cloud Networks. ICLR 2021.\n[2] https://www.nature.com/articles/s41467-022-29939-5\n[3] Xiyuan Wang, Muhan Zhang. Graph Neural Network With Local Frame for Molecular Potential Energy Surface. LoG 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)