A Theoretically-Principled Sparse, Connected, and Rigid Graph Representation of Molecules
Authors: Shih-Hsin Wang
Yuhao Huang
Justin M. Baker
Yuan-En Sun
Qi Tang
Bao Wang
Venue: ICLR 2025 Oral (2025)
Keywords: Graph representation
sparsity
connectivity
rigidity
molecules
learning
Primary area: learning on graphs and other geometries & topologies
TL;DR: We introduce a new sparse, connected, and rigid graph representation for molecules.

Abstract: Graph neural networks (GNNs) -- learn graph representations by exploiting the graph's sparsity, connectivity, and symmetries -- have become indispensable for learning geometric data like molecules. However, the most used graphs (e.g., radial cutoff graphs) in molecular modeling lack theoretical guarantees for achieving connectivity and sparsity simultaneously, which are essential for the performance and scalability of GNNs. Furthermore, existing widely used graph construction methods for molecules lack rigidity, limiting GNNs' ability to exploit graph nodes' spatial arrangement. In this paper, we introduce a new hyperparameter-free graph construction of molecules and beyond with sparsity, connectivity, and rigidity guarantees. Remarkably, our method consistently generates connected and sparse graphs with the edge-to-node ratio being bounded above by 3. Our graphs' rigidity guarantees that edge distances and dihedral angles are sufficient to uniquely determine the general spatial arrangements of atoms. We substantiate the effectiveness and efficiency of our proposed graphs in various molecular modeling benchmarks. Code is available at https://github.com/shihhsinwang0214/SCHull.

Published as a conference paper at ICLR 2025
A THEORETICALLY-PRINCPPEE SPARSE, CONNECTED, AND RIGID GRAPH REPRESENTATION OF MOLECULES
Shih-Hsin Wang', Yuhao Huang': Justin Baker?, Yuan-En Sun Qi Tang & Bao Wang' DDepartment of Mathematics and Scientific Computing and Imaging (SCI) Institute University of Utah, Salt Lake City, UT 84102, USA
*Department of Mathematics, UCLA, Los Angeles, CA 90095, USA
3 "Department of Biochemistry, University of Utah, Salt Lake City, UT 84102, USA *School of Computational Science and Engineering. Georgia Tech, Atlanta, GA 30332, USA
ABSTRACT
Graph neural networks (GNNs) - learn graph representations by exploiting the graph's 's sparsity, connectivity, and symmetries have become indispensable for learning geometric data like molecules. However, the most used graphs (e.g., radial cutoff graphs) in molecular modeling lack theoretical guarantees for achieving con- nectivity and sparsity simultaneously. which are essential for the performance and scalability of GNNs. Furthermore, existing widely used graph construction methods for molecules lack rigidity, limiting GNNs' ability to exploit graph nodes' spatial graph construc-
arrangement. In this paper, we introduce a new hyperparameter- tion of molecules and beyond with sparsity, connectivity, and rigidity guarantees. Remarkably, our method consistently generates connected and sparse graphs with the edge-to-node ratio being bounded above by 3. Our graphs' rigidity guarantees that edge distances and dihedral angles are sufficient to uniquely determine the general spatial arrangements of atoms. We substantiate the effectiivnness and effi- ciency of our proposed graphs in various molecular modeling benchmarks. Code is available at https: / thu... com/ sh hhs www.gg/11///ecc../m
INTRODUCTION
Graph neural networks (GNNs) have emerged indispensable tools for learning graphs, e.g., social networks (Perozzi et al.) 2014 and molecules (Duvenaud et al.] 2015 Gilmer et al. 2017). GNNs operate by exchanging messages between neighboring nodes for learning features at both node and graph levels; see, e.g. (Gilmer et al. 2017 Satorras et al. 2021). Constructing sparse and connected graph representations of the input data plays a pivotal role in the success of GNNs, especially in molecular modeling. Graph sparsity enables computational efficiency, and connectivity ensures that information can flow seamlessly throughout the network - it has been shown that the disconnectivity of graph can degrade the model's performance; see, e.g., (Sverdlov & Dym 2024
common method for creating molecular graphs involves setting a radial cutoff distance; atoms connected by edges if their Euclidean distance falls below the cutoff threshold (Schütt al.) 2017:2018 Unke & Meuwly| 2009)). To limit the number of connections per atom, ad-hoc post- pruning be applied, removing edges between distant atoms if a node has too many connections. However, determining an optimal cutoff for molecular graphs presents a significant challenge. A large cutoff might guarantee that all atoms are connected, but it can result in overly dense graphs. Conversely, while post-pruning can reduce the density of graphs, it might introduce the risk of disconnectivity. Furthermore, for large molecules like proteins with thousands of atoms, a fixed cutoff is often insufficient to ensure connectivity. Examples include long-range atomic interactions in protein allosteric regulation (Süel al.
2003] Zhu et al. (022) and inter-chain interactions in 2021 Chen & Bell 2021). lb. To illustrate the limitations of the
protein oligomerization (Chen et al. radial cutoff method, we present Fig. Iaa, which depicts a protein molecule with colored residues.
These colored residues represent single instance from the Fold biomolecule dataset (Murzin et al.) 1995. Hou et al. 2018). As shown in Fig. [b). applying a cutoff of 10Å on the data consisting of C., atoms of amino acids results in disconnected but quite dense graph. To further solidify
"Shih-Hsin Wang and Yuhao Huang are co-first authors. Correspond wangbaon @mgai com

---

Published as a conference paper at ICLR 2025
(a) A protein molecule
(b) Radial cutoff graph (10A)
(c) SCHull graph
E/N Ratio
102
Conn Rate(%
100
outoff-21 outoff=4
cutoff-48 cutoff-6
80
cutofi-8 SCHull
10
60
10"
100
500 of Nodes
1000
1500
100
500
1000
1500
Nodes
(d) Edge-to-node ratio
(c) Percent of connected graphs
Figure 1: Illustration of challenges of radial cutoff graphs in balancing sparsity and connectivity for the Fold biomolecule dataset. (a) Colored residues (b) A radial cutoff graph with a cutoff of 10A for the colored residues, demonstrating disconnectivity and density; in contrast, (c) showcases our proposed SCHull graphs, ensuring sparsity and connectivity. Panels (d) and (c) plot the number of nodes against the edge-to-node ratio and the percentage of connected graphs, respectively, for radial cutoff graphs using different thresholds and SCHull graph construction. The results highlight that radial cutoff has to trade sparsity for connectivity, while our SCHull graphs maintain both properties.
large protein, representing a single instance from the Fold dataset.
the challenges in balancing sparsity and connectivity using radial cutoff graphs, we investigate the sparsity and connectivity tradeoff using various cutoff thresholds to construct graphs for proteins in the Fold dataset. Next, for these radial cutoff graphs, we calculate the edge-to-node ratio and the proportion of connected graphs for different cutoff thresholds. As shown Fig. fe.. a cutoff of 48A required to achieve connectivity for large proteins with more than 1000 amino acids. However, as shown Fig. [d), connectivity comes at the cost of dramatically increased density, e.g., a cutoff of 48A results in graphs with over 100 times more edges than graphs constructed with 6λ cutoff. We further discuss other popular graph representations of molecules like chemical graphs and k-nearest neighbor graphs in Section
Besides sparsity and connectivity, it's essential to con- sider whether geometric graph could contain sufficient information to determine its nodes' spatial arrangement (geometries). Pairwise distances between all nodes theo- retically determine the geometric arrangement (Satorras al.) 2021] up to rigid motions, but computing pairwise distances between all nodes amounts to involving a dense graph in the operation. Alternatively, researchers have explored sparse edge distributions with specific geomet- ric features to identify the spatial arrangement of graph nodes. (Sverdlov & Dym (2024) connect identifying nodes' arrangement to graph rigidity and have demonstrated that graph rigidity ensure GNN's ability distinguish general geometric configurations of nodes. Nevertheless, radial cutoff graphs often lack sufficient rigidity, leading to ambiguity in spatial arrangements (Joshi et al., 20233
A
B
Figure 2: Illustration two distinct, non- isometric arrangements of nodes in Euclidean space. When applying radial cutoff to the arrangements in A and B. obtain nected and sparse graphs. However, the corre- sponding edges in both graphs have identical lengths, making it challenging for graph neu- ral networks distinguish between them.
Wang et al., 2024). Figure illustrates this limitation using synthetic example: A and are two distinct, non-isometric arrangements of five points in Euclidean space; while applying radial cutoff to these arrangements results in connected and sparse graphs. However, the edges in both graphs have the same lengths, making it challenging for GNNs to distinguish between them.
1.1 OUR CONTRIBUTIONS
In response to the limitation of existing graph constructions of molecules, propose Spherical Convex Hull (SCHull) a new hyperparameter-ffee graph construction method tailored for data with 3D coordinates, especially molecules. SCHull constructs graph representations of the underlying
2

---

Published as a conference paper at ICLR 2025
points in two computationally efficient steps: (1) project points onto the unit sphere centered at the center of points, and (2) construct a convex hull for the projected points and add an edge to connect two original points if the convex hull has an edge connecting the corresponding projected points; see details in Section 3.1 SCHull graphs enjoy a few advantages with theoretical guarantees:
SCHull graphs are connected and sparse. In particular, the edge-to-node ratio is bounded above by 3; see detailed theoretical results in Section 3.2
SCHull graph mirrors the spatial arrangement of the underlying point clouds, ensuring that encoding edge distances and dihedral angles are sufficient for GNNs to uniquely determine the geometric configurations of nodes up to isometries; see Section 3.3 for details.
Furthermore, the SCHull graph can be seamlessly coupled with existing GNN learning techniques to boost the performance of off-the-shelf models. We substantiate the effectiveness and efficiency of the proposed SCHull graph using a few molecular modeling benchmarks, including predicting atomic forces for small chemicals, protein fold classification, enzyme reaction classification, and protein- ligand binding affinity prediction; see details in Section Our numerical results show that using SCHull can consistently improve the prediction accuracy of existing remarkable GNNs by significant margin at the cost of a tiny computational overhead.
1.2 ORGANIZATION
We organize this paper as follows: In Section 2 we recap on necessary background materials and some related results. We present the construction process of our proposed SCHull graphs in Section 3.1] followed by their sparsity and connectivity analysis in Section 3.2 We further analyze the rigidity of SCHull graphs and their benefits in improving GNN's performance in Section 3.3 We substantiate the performance of SCHull in Section 4 using various benchmark tasks in molecular modeling. Technical proofs and additional experimental details are provided in the appendix.
BACKGROUND AND SOME RELATED WORKS
In this section, we provide brief review of key concepts and related results. Specifically, we revisit concepts of geometric graphs as discussed by Joshi et al. (023); Wang et al. (2024), review existing graph construction methods for molecules, and introduce convex hulls and polyhedral graphs along with a key result on their rigidity. An overview of graph rigidity is provided in Appendix B along with quick example. For more in-depth exploration, we refer readers (Asimow & Roth 1978 Connelly 2005). Furthermore, we will recap on message-passing GNNs and their separation power.
Point clouds and geometric graphs. A 3D point cloud, consisting of points æ1; 22; Bmn can be viewed as a spatial arrangement of a set of m nodes V {1, 2, m]. where each index i is associated with a node with coordinate x; E R We can represent a point cloud set { 1m or as a spatial arrangement of nodes (V, X = [ .,,...,,,,,....... Optionally, each node may be associated with features f. E R beyond coordinates. Extending from a point cloud to a geometric graph denoted as G (V. E, X) (resp. (V. E, X, F)) inttroduccss graph structure by connecting nodes using edges in the set to include relationships between points in (V,, X) (resp. (V, (V,XPF F)). Here, (i.j) E & denotes an edge and F = = [f,...., fm] represents node features.
Existing graph representations of molecules. As mentioned earlier, radial cutoff is one of the prevailing approaches to constructing graph representations of molecules. Besides radial cutoff, there are several other methods have also been used to construct graphs for molecules, including k-nearest neighbor graphs (kNN) (Jörgensen et al. 2018) and chemical graphs (Gilmer et al., 2017). Similar to the radial cutoff graphs, k k-nearest neighbor graphs, and chemical graphs also struggle to achieve sparsity, connectivity, and rigidity at the same time; we contrast different graphs properties in Table
Table I: Contrasting different graph construction methods in achieving sparsity, connectivity, and rigidity.
Construction method
Sparsity
Connectivity
Rigidity
Radial cutoff (small threshold)
Radial cutoff (large threshold)
XX
k-nearest neighbors
x
Chemical graphs
X
SCHull (ours)
Rigid motions and geometric isomorphism. A rigid motion, a.k.a. an isometry, is a transformation defined by an orthogonal matrix Q 03) and a translation vector t TR3 It acts on the point cloud
3

---

Published as a conference paper at ICLR 2025
by transforming all its points according to 2; + Qz, +t. The group of 3D rigid motions is called the Euclidean group and is denoted by E(3). Two geometric graphs 91 = (V1, E1, X1, Fi) and
G2 = (V2, Eg, X2, F2) are said to be geometrically isomorphic if and only if there exists bijection b: Vi + 1/2 and a rigid motion (Q, t) E E(3) such that for any (i.j) E & (b(i), b()) E &,, and for
any f, =b()); x, Q + t. Notice that the condition requiring rigid motion (Q, t) E(3))
such that x; Q for all is equivalent to the condition ||z: æyl ( Zb(j)] for
all i.j. A function F defined on the geometric graphs is said to be invariant if F(Gi) F F(22) for any two geometrically isomorphic geometric graphs G1. 92.
Convex hull and polyhedral graph. A convex hull of a set of points {z ........ Lm C R is defined as Conv (f Zm3) = (2. 0 Σ; aq = 1, a......... Om E [0, 1]. which is the smallest convex set containing these points. When the points are not coplanar, the convex hull is also known as a convex polyhedron, whose graph structure comprises its vertices, edges, and faces. Any graph derived from this structure is referred to a combinatorial polyhedron or polyhedral graph. Steinitz's Theorem (Grünbaum] 2007) establishes a one-to-one correspondence between polyhedral graphs and 3-connected simple planar graph This means every polyhedral graph can be represented as 3-connected simple planar graph and vice versa.
geometric polyhedral graph is geometric graph (V, (V) whose underlying graph structure is a polyhedral graph. It can be considered as assigning node coordinates to polyhedral graph (V: 8). A
well-known rigidity theorem for polyhedral graphs by [Stoker (9688) (see also (Cho Kim 2023 )
states that a strictly-convex geometric polyhedral graph is uniquely determined by its edge lengths dı and dihedral angle Tiy on edge (i.j), where the dihedral angle on edge (i. is defined as the angle between two faces that contain edge (i. More precisely, we have the following theorem:
Theorem 2.1 (Stoker (1968). Let G = EV, X) and g' = "V X')
be two strictly-conver
geometric polyhedral graphs. Suppose there exists a graph isomorphism b. V - V satisfying Tij = To(DG)) and dij- = de(1)b5)) for any (i, E E, where diy and Tış denote the length of edge (i,j) E E and dihedral angle associated with edge (i,5). Then g and g' must be geometrically isomorphic, i.e., there a rigid motion (Q,t) E E(3 such that x; Qui(()) + +t any E V.
Message-passing GNNs and their separation power. For any geometric graph 9 = (V,E, message- saaagggg-asingggggo GNN propagates features, with f!()) fú, as follows:
!!(+)) UPD (F AGG((F. f/ eeg 1j (.D))
(1)
where Giy are edge attributes (eg can be æ; - 2, or pre-determined invariant edge attributes like relative distance ||æ; æ; [I), Ny denotes the one-hop neighbors of node i, i.e., the set of nodes in V that are reachable from i through an edge in E, and UPD and AGG are learnable update and aggregate functions operating the graph G. respectively. After T message-passing steps, we apply a multiset Readout function to obtain the graph level global features
gloobal
Readout
(f (
(2)
common approach to evaluating GNN's performance is to assess its ability to learn distinct global features from non-isomorphic geometric graphs. In particular, a standard assumption in this analysis is to consider maximally expressive GNNs, where the update, aggregation, and readout functions are all injective (Joshi al. 2023 Wang et al. 2024 Sverdlov & Dym 2024). We say maximally expressive GNN F with depth T can distinguish two geometric graphs G1 and G2 if, after T iterations, global
the learned global features for Gi and G2 are distinct, that is, s global =: F(G)) + F(G2) = 822
3 MAIN RESULTS
In response to the limitation of existing graph representations - in achieving sparsity. connectivity, and rigidity - for geometric data with 3D coordinates, we propose SCHull new graph construction method for molecules and beyond. SCHull eliminates hyperparameter tuning and ensures connectivity while maintaining sparsity and rigidity. In this section, we will outline the two steps in constructing SCHull graphs, followed by proving how these steps achieve the desired properties and how the resulting graph benefits GNNs' performance.
In this context, simple graph is one without self- or multiple edges. A graph is 3-connected if removing fewer than three vertices doesn't 't disconnect it. A graph is planar if it can be drawn plane without edge crossings.
4

---

Published as a conference paper at ICLR 2025
3.1 SCHULL- A NEW GRAPH CONSTRUCTION
SCHull constructs graphs in two steps: (1) project points (nodes) onto the unit sphere centered at the center of the points, and (2) construct the convex hull for the projected points and connect two original points the convex hull contains an edge connecting the two corresponding projected points.
Step 1: Project points onto the unit sphere. Let (V, X [ F2. ................................ Fmm) be point cloud, e.g.. representing atoms in a protein molecule. Denote the center X by ===== > Z. Consider the pro- jection PF 3 + 2 defined by +
||== where g = {xr E TR3 ||>||| 1) is the unit sphere. That is, Pa projects points onto the unit sphere centered Σ. Applying this projection to all points, we obtain new point cloud (V, Ps (X)) on S?, where Pm X) = [Px (a Pan Pm Pa (2 )-
a--
In cases, there may be points such that æ; E for some i, which prevents from defining its projection. To ease our analysis, we assume that the projections of all points in a given point cloud (V, X) are well-defined and these projections g are distinct. This implies that [V] (P (a:)) i E V More precisely, we assume the following generic condition holds:
xz + x and (x, # PT(x)) for any i + E.
(3)
Point clouds satisfy this condition with probability if they are uniformly distributed; see Lemma 3.4 We focus this case in the main context and present strategy in Appendix [ to maintain the desired properties of our graph when the generic condition equation 33 does not hold.
Figure 3: Visualizing the SCHull graph construction process: (left panel) The blue points æ,s represent the given point cloud, and the gray node T denotes the center of this point cloud. Each point is projected onto the green unit sphere centered T., resulting in the corresponding orange points z; Pa (a::). (middle panel) The convex hull of the orange points z; = (a(x:;) is constructed, with its edges highlighted in gray. (right panel) The gray edges on the convex hull of the projected points induce the graph structure on the original point cloud.
Construct the convex hull and SCHull graph. Next, we construct a convex hull - using the QuickHull algorithm (Barber et al., 1996) for the projected points (V, PT (x)) obtained from Step 1, and we denote the resulting convex hull as Conv (fp=(x,) i E V)). In particular, the boundary of this convex hull is a polyhedral graph with nodes, edges, and faces. By disregarding the face structure, we obtain a graph (V,E) that includes all points in V thanks to the generic condition equation 3.. Our graph construction for the given point cloud (V, X) is then defined as = (V. E. X). This graph includes the original point cloud (V,X) X). with edges defined by those the convex hull of (V, Pa (x)). Specifically, nodes j, are connected by an edge in if and only if their projected points the unit sphere p= (x,), Pm( are connected by an edge the convex hull Conv ((p=(a),
Step 2:
V}).
We demonstrate an example of applying our SCHull graph construction for synthetic point cloud in Fig. 3 For simplicity, we assume all points { are coplanar. The green circle represents the unit sphere centered at the mean point x: = - 2; Each == p= denotes the projection of ar onto the green unit sphere. We then construct the convex hull Conv ([2:)) }) of the projected points, with solid gray lines indicating the edges. Finally, the SCHull graph is created by connecting points 2; and 2y if their corresponding projections z; and zj are connected by an edge in the convex hull.
Computational complexity. To analyze the computational complexity of constructing SCHull graphs, let m be the number of points in the point cloud. The overall cost is dominated by the convex hull construction, which utilizes QuickHull with computational complexity of O(m log m) (Barber jet al.) 1996). Other steps, including projecting points to the unit sphere and attributes computation (see Section 3.3). result in (m) additional computational complexity.
5

---

Published as a conference paper at ICLR 2025
3.2 CONNECTIVITY AND SPARSITY OF SCHULL GRAPHS
In this section, we prove that SCHull graphs are connected and sparse. We begin by presenting fundamental proposition that outlines the properties of convex hulls formed by points on a sphere.
Proposition 3.1. Let Z { be set of points a sphere where [2] 2 3 (the number of points is at least 3), and let (2) denote the convex hull of 2 with its associated graph structure consisting of nodes, edges, and faces defined by its boundary. Then, we have
1. Connectivity; Any two points in Z are connected by sequence of edges in Conv(2)
2. Sparsity: The number of edges in C2nv(2) is no greater than 3| 6.
Moreover, C2nv(2) a strictly convex geometric polyhedral graph if zjs are not coplanar.
Proposition 3.1 ensures that the convex hull of finite set of points sphere is always connected, eliminating the possibility of isolated points. Additionally, the number of edges is bounded above by three times the number of nodes, ensuring sparsity. Notice the SCHull graph directly inherits the graph structure from the convex hull of the projected points on the unit sphere, along with its connectivity and sparsity. We summarize these implications in the following corollary:
Corollary 3.2. For any point cloud (V,X) X) with more than 2 points and satisfying the generic condition equation (3), the SCHull graph E, xx) is connected geometric polyhedral graph and has linear relationship between the number of edges and the number of nodes. Specifically, the edge-to-node ratio is bounded above by 3, i.e. 181 <3
The theoretical results in Corollary 3.2 are numerically substantiated by the results in Fig. In particular, SCHull graphs are always connected, and the ratios between the number of edges and the number of nodes are always bounded above by for all molecules in the benchmark Fold dataset.
3.3 RIGIDITY OF SCHULL GRAPHS AND ITS ROLE IN GNN'S S PERFORMANCE
SCHull graphs guarantee both sparsity and connectivity. However, a crucial question remains:
How do SCHull graphs impact the performance of GNNs?
To answer this affirmatively, we delve into the rigidity of SCHull graphs; see Appendix B for an overview of rigidity. We first introduce a common assumption about the genericity of point clouds in graph rigidity studies; see e.g., (Laman) 1970, Asimow & Roth 1978] Connelly) 2005). We then propose a simple attribute-based design for SCHull graphs and provide a theoretical analysis demonstrating that our SCHull graphs with their geometric attributes on both edges and nodes can effectively enable GNNs to distinguish between any two non-isomorphic generic point clouds.
Definition 3.3 (Genericity of point clouds). A point cloud (V, X) is said to be generia if
No multivariate polynomial P with rational coefficients satisfies P( Tm) = O. (4)
The genericity of a point cloud means that the points are arranged in way that cannot be described
by simple polynomial equation with rational coefficients. It's important to note that almost all point clouds are generic, with exceptions forming a set of Lebesgue measure zero (Mityagin (015)). In particular, the genericity of point clouds presented in Definition 3.3 is stronger than the generic condition equation (3) that we have assumed in Section
Lemma 3.4. Any generic point cloud satisfies the generic assumption equation
Moreover, generic point clouds also avoid the cases where all the projected points {p=( are coplanar, this leads to the following result, allowing us to apply Theorem 2.1
Lemma 3.5. Let (V, X) be a generic point cloud. Then Conv (1p=(x)) i E V)) the convex hull on the sphere constructed in Section 3.1 is strictly convex geometric polyhedral graph.
According to Lemma 3.5 and Theorem 2.1 edge lengths dis and dihedral angles Tr are sufficient to uniquely determine the spatial arrangement of Conv ((pa( (x:) E V)) due to its convexity. While the SCHull graph is also a geometric polyhedral graph, its lack of convexity raises concerns about whether edge lengths and dihedral angles are sufficient determine the spatial arrangement of points.
Ass known algehraically independent.

---

Published as a conference paper at ICLR 2025
However, by including the original distances of the nodes from the center of the point clouds as node attributes, we can prove that any maximally expressive GNN a standard framework for analyzing GNNs' performance can distinguish between any two con-isomorphic point clouds (see Section for a brief overview). Specifically, for a given point cloud (V, X), we consider the attributed version of our SCHull graph 9 = (V, X, F), where encode
the edge attributes ejj (I|æ; zyl1 Tay) for any (i.5) E &, and the node attributes fi = || - I|| for any é E V.
(5)
Notice that Ti are the dihedral angles between faces computed on Conv ((Pm(Z;)) | E VJ). Under these settings, we have
Theorem 3.6. Let F be maximally expressive GNN with depth T = 1. Then F can distinguish between the attributed SCHull graphs defined in equation of any two non-isomorphic generic point clouds.
Remark 3.7. The node attribute design of SCHull in equation can be omitted without affecting the theorem's 's result we consider removing an additional measure zero subset of point clouds. Due to page limitations, this version of Theorem 3.6 is provided in Appendix F Additionally, while we do not address the coplanar case in the main text, the corresponding theory and discussion regarding the effectiveness of our SCHull graph for coplanar cases can be found in Appendix [
Remark 3.8. As discussed in the introduction, the rigidity property does not generally hold for other While[Sverdlov graph construction methods, e.g., radial cutoff. While [verdlov & Dym (0024) propose power graphs
as a solution to ensure rigidity in these methods, power graphs often lead to increased graph density and do not address cases where the original graph is disconnected. A more detailed introduction to power graphs is provided in Appendix A and an empirical study provided in Appendix B In contrast, the SCHull graph when dealing with generic point clouds naturally strikes balance between rigidity and sparsity, making an efficient and suitable option for GNN applications.
Remark 3.9. Existing works, such as (Joshi et al. 2023 Li et al., 2024 Hordan et al. 2024), have established theoretical frameworks that address both generic and non-generic point clouds. In particular, Li et a (2024) highlights the challenges of distinguishing ambiguous symmetric point clouds. While our method does not currently provide theoretical guarantee for such cases, we present empirical evidence in Appendix B showing that even shallow graph neural networks using our approach can effectively distinguish ambiguous symmetric point clouds- cases where incorporating all edge lengths on complete graphs fall short.
To solidify Theorem 3.6. we design synthetic dataset named NestedSquares. The NestedSquares dataset com- prises ten graphs, each consisting of two nested squares. In each graph, the inner square is rotated by an angle (0, n/2): see Fig. 4 for an example. Each graph is labeled with the angular rotation, and the objective to minimize the mean squared error when predicting this angle. The data is split into 6 training graphs, 2 test graphs, and validation graphs. This task evaluates GNNs' ability to learn both local and global geometric information. To show the effectiveness of SCHull graphs, we compare message passing using solely the information provided by SCHull against existing geometric GNNs with common graph constructions. We introduce MPNN+SCHul, that takes the SCHull graph as input, incorporating both graph structure and the constructed edge attributes and node features defined in equation (5) see Appendix G.2 for the detailed architecture of the used MPNN, and Appendix H.T for experimental details.
Figure 4: Depicting the rotation of the graph from the NestedSquares dataset. Ten rotated graphs are generated by randomly choosing
message- passing neural network (MPNN)
Radial cutoff
JNN (k 3)
Voranai
SCHull (ours)
MPNN
0.657 0.165
0.213 0.013
0.281 1. 0.049
0.068 1 0.049
DimeNet++
0.281 1 0.049
0.281 1 0.049
0.292 1. 0.018
SphereNet
0.661 0.212
0.450 0.121
0.494 + 0.1
ComENet
0.885 + 0.287
0.502 + 0.28
0,816 + 0.275
Table 2: Test mean squared error (MSE) of single-layer invariant GNNs for the NestedShapes dataset. MCNN+SCHull utilizes the SCHull graph structure. Our method outperforms all other models and graph constructions. The mean 1 standard deviation is reported from 10 random trials.
In particular, we cover several representative invariant GNN models, including DimeNet++ (Gasteiger et al. 2020a), SphereNet (Liu al. 2022). and ComENet (Wang al. 2022b). These invariant GNNs,
7

---

Published as a conference paper at ICLR 2025
along with the simple MPNN, were equipped with various graphs, including Radial cutoff, ANN, and Voronoi. Notably, we did not implement other invariant GNNs on SCHull to avoid any potential biases introduced by their specific designs. Table 2 shows the advantage of SCHull over other graphs with different invariant GNN models. Notice that MPNN+SCHull significantly outperforms all other models almost by order of magnitude.
3.4 SOME FURTHER DISCUSSIONS
While SCHull graphs have connectivity, sparsity, and rigidity guarantees, their performance in practice may vary depending on the complexity of the problem. Our proposed SCHull graph is more likely connect distant nodes, capturing global information but potentially overlooking local details. To fully leverage the strengths of SCHull graphs, we recommend using them in conjunction with an additional informative sparse graph, such as a radial cutoff graph with a small cutoff' threshold or chemical graph. This combined approach can ensure both global geometric completeness and capture of local information while maintaining connectivity and sparsity.
To demonstrate the integration of SCHull graphs with existing GNNs that use radial cutoff graphs we consider geometric graph 9 EV, X, FF) constructed using the radial cutoff method from the point cloud X) We then construct the corresponding SCHull graph 9 (V, X, F). Notice that most GNNs e.g., (Wang et al. 2022al Liu et al., 2022, Jing al. 2020 utilize predesigned embedding function EMB(E, E X, F), to obtain the edge attributes e E (i, E E} and the embedded node features F' = [f Sm on the graph G. These attributed graphs are then input into the GNN model. We apply the same embedding function to compute the edge attributes é = {eag I (1, E E) and the embedded node features F' = i fmm] for the SCHull graph G. It is worth mentioning that the embedded features ē and F' contain the features mentioned in equation 5 We then define the integrated node features as F = FF + F', and the integrated edges and edge attributes as Ex =
=EU EU and e* = U é, respectively. Finally, we obtain the SCHull integrated graph G (V,E* X, F"), which serves as the input to the GNNs.
NUMERICAL RESULTS
We present comprehensive empirical results to show the effectiveness of SCHull-integrated GNNs. Across various tasks, we highlight that: (1) The SCHull graph's 's connectivity and sparsity properties effectively capture geometric information while maintaining computational efficiency. (2) The enriched graph structure, coupled with comprehensive node and edge features, significantly enhances cassage-passing capabilities. To validate our approach, we integrate SCHull into several GNN models and evaluate their performance on both small- and large-scall scale graph tasks, including atom force prediction, protein fold and enzyme reaction classification, and protein property prediction. The results consistently demonstrate that SCHull- SCHull-integrate GNN models outperform the baseline models across multiple metrics while maintaining computational efficiency.
Software and equipment:
Our implementation relies on the PyTorch Geometric (Fey & I Lenssen 2019) and SciPy (Virtanen et al. 2020) frameworks. Experiments are conducted single NVIDIA RTX 3090 GPU, and T4 and 1100GPUS provided by Google Colab (Google Colaboratory
2023
Training setup: The training setups for different tasks are available in Appendices 1.2 and I.3
We integrate SCHull graphs into DimeNet (Gasteiger et al. (020b), SphereNet (Liu et al. 2022) and LEFTNet (Du et al. 2024) for learning node-level equivariant features molecule dataset MD17 (Chmiela et al. 2017). Also, we integrate SCHull into CroNet-Backboone ProNet-Amino- Acid (Wang al.) 2022a), and GVP-GNN (Jing et al.
2020) for benchmark tasks of protein fold
classification (Fold) and enzyme reaction classification (React) (Hou et al. 2018). and protein-ligand
binding affinity prediction (LBA) (Wang et al. 2004 Liu et al. 2015).
Metrics: For prediction, we use various metrics depending on the tasks e.g., mean absolute error (MAE), root mean square error (RMSE), Pearson Correlation (Uebersax 1987), Spearman Corre- lation (Panda & Patil 2015) and Kendall Correlation (Bradley) 1976). For each task, we run the experiment five times and record the standard deviation of the corresponding metric.
4.1 PREDICTING ATOMIC FORCES FOR MD17 SMALL MOLECULES
In this experiment, we evaluate how effectively the SCHull framework enhances different models in learning equivariant features by predicting atomic forces the MD17 dataset. We integrate
8

---

Published as a conference paper at ICLR 2025
SCHull into LEFTNet, DimeNet, and SphereNet. Following prior research (Schitt et al.
2018 Liu
iet al., 2022 Du et al. 2024), we train individual models for each of the seven molecules: Aspirin. Benzene, Ethanol, Malonaldehyde, Naphthalene, Toluene, and Uracil. Detailed experimental and hyperparameter settings are provided in Appendices Land[. [.2] respectively. Both the training and validation sets consist of 1,000 samples each, with the remaining data reserved for testing.
We use MAE to assess model performance on the test dataset. The results in TableBsshon that all SCHull-integrated models outperform baselines MD17 while maintaining comparable runtime. This indicates that SCHull enhances the models' ability to capture equivariant information without significantly affecting pesssae--psssing efficiency.
Molecule
DimeNot
DimeNessSCooll
SphereNat
SphrrearsSCHull
L.FTNel
1FFTNet-SCHall
Aspitin
0.427 1 .014
0.387:2000 005
0.240 .055
Benzene
1.187
0.157 .06
0.178
0.155 006
0.098 0022
Eihuno)
0.230
0.198 003
0.208
0.181 1 003
0.138
0. 0.109: 1. 002
Malonaldeoyde
D.3853
0,3344 .008
0.340
0.298. 008
0.205
0.151 + .002
Naphthalene
0.215
0.178
0.178
0.144:
0.074
0.058 1.01
Tolaen:
0.210
0. 0.1094
0.155
0.129 002
0.083
0.0764
Uracil
0.301
0,288 1. 002
0.267
0.242 003
0.117
0.095
Training TmeoFgochh))
43...9
5010.8
51.1.0
62_1.5
24g0.5
28
Table 3: Test MAEs of MD17 dataset vector-valued properties prediction.
4.2 LEARNING PROTEINS
We demonstrate the importance of ensuring connectivity and sparsity in large-scale graph tasks, such as protein classification and property prediction. Protein graphs can contain thousands of nodes, making it crucial to maintain graph sparsity for computational efficiency while preserving connectivity to allow GNNs to capture global geometric information. We integrate SCHull into protein-task specific GNNs such as ProNet-Backbong ProNet-Amino-Acid. GVP-GNN, SEGNN, and MACE and evaluate them on three protein datasets. Details of the model training and hyperparameters are provided in Appendix I.3 The experimental results highlight the significance of capturing global information during message passing using SCHull features, particularly in large graphs. Additionally, including SCHull does not introduce significant overhead in terms of runtime.
4.2.1 FOLD CLASSIFICATION
Protein fold classification (Levitt & Chothia 1976) informs the connection between protein structure and function, as well protein evolution. In this experiment, we assess our SCHull integrated models for the protein fold classification task by following the fold dataset and experimental frameworks in Wang et al. (2022a). To evaluate generalization performance, three test sets used:
* Family: includes proteins from the same family in the training data.
* Superfamily: excludes proteins from the same family appearing in the training data.
Fold: excludes proteins from the same superfamily appearing in the training data.
More dataset information and splits can be found in Appendix H.3 Table demonstrates that SCHull improves model accuracy across all three test datasets, with only marginal increase in runtime. Furthermore, to assess how SCHull aids models in capturing global information, we divide each test set into four subsets based the number of nodes (with most 150, 300, 450, and 600 nodes). Fig. shows that as graph size increases, the SCHull-integrated ProNet-Backbone achieves progressively higher accuracy over its original model. This result supports our claim that preserving connectivity is crucial for GNNs to learn global information and predict the class of protein data. Indeed, our proposed SCHull graph ensures connectivity, as shown in Fig. I
ProNet-Backee Backbone
100
Accuracy(8%)
70-
Accuracy(%)
70
Accuracy/%/
95
60-
60
90
50
150
300
450
600
150
300
450
600
150
3000
450
600
Number of Nodes
Number of Nodes
Number of Nodes
(a)
(b)
(c)
Figure 5:
Comparison of the accuracy (%) different sizes of graphs in the Fold classification dataset (a) Accuracy on test(Fold) dataset; (b) Accuracy on
using ProNet(Backbon) and ProNe((Becbon)+ test(Super) dataset; (c) Accuracy on test(Family) dataset with at most 150, 300, 450, and 600 nodes.

---

Published as a conference paper at ICLR 2025
React
Arg. Time
Avg. Time
Fold
Super
Family
Avg.
Kipt Welling 2017
16.8
21.3
82.8
40.3
Jermooilla
45.0
69.7
98.9
71.2
DWNN
2022
76.7
31.8
57.8
85.2
51.5
GearNet
Zhang el
2022
79.4
28.4
42.6
95.3
55,4
HoloPPro
Summath et m
2021
78.9
MACF Bataii al
2022
2..
21.4
60.2=0.2
35.1
114:0.5
MACE+
27.0+0.0
23.1+0.6
63.0=0.2
38.4
135
SEONN (Brandsteter
28.810
30.3
77. 2..3
45,4
121
SECNN+SCTall
0..0
06.8
$6, 2..3
51.9
152:20.5
GVP-GNN (ling of 2020
53045
16.0
22.5
83.8
40.8
106.1.0.5
GVP&GNN
77.1-0.5
345+5
24.5+0.33
27.1+0.22
111.5+0.5
ProNet-Aiino-Add (Wang ct
21015
51.5
69.9
99.0
73.
705.0.:5
PruNet-Amiso
87.90.33
22146
56.2+0022
73.9+0.2
19.1=0.1
76.1
738+0.5
ProNee-Backbune PraNet-Backbonrras
21311
52.7
70.3
71.4
28.1
23015
56.10.33
74.6.0.2
99.4
75.8.0.5
Table 4:
enzyme reaction classification tasks. Ave. Time denotes the average time per training epoch. The top results are in boldface. SCHull consistently improves baseline models.
Accuracy (%) on protein
4.2.2 REACTION CLASSIFICATION
Enzymes proteins functioning as biological catalysts. They can be categorized using enzyme com- mission (EC) numbers which classify enzymes according to the reactions they facilitate (Omelchenko)
al. 2010). In this experiment, we evaluate the SCHull-integrated models on the reaction classifica- tion task using the same reaction dataset and experimental settings as outlined in (Wang et al. 2022a Hou et 2018). Additional details on the dataset and the training, validation, and splits are provided in Appendix H.3 Similar to the fold classification results in Section 1, Table shows
that SCHull consistently outperforms the original models, with a minimal increase in runtime.
4.2.3 LIGAND BINDING AFFINITY
Predicting protein-ligand binding affinity (LBA) plays a crucial role in various downstream processes in drug discovery. For this task,
models predict LBA. The dataset is sourced from PDBbind (Wang et al.) 2004 Liu et al. 2015) along with the experimental protocols established by (Jing al. (2020). We employ default dataset split. See Appendix H.. for more details of the dataset. We use a variety of statistical metrics, including RMSE, Pearson, Spearman, and Kendall correlations, to evaluate how SCHull enhances the learning capacity and generalization of GNNs. Again, Table shows that SCHull -ittellinteeratedd models consistently outperform the original models across different metrics while maintaining high computational efficiency.
the SCHull-integren
Methed
IBA
Avg, Time
RMSEL
Pearsont
Spearman
Kendall
IEClov [Bermoilla ot a!
1,554
0.44
0.438
HoloProt Full Surface
Sommath clal
2021
1.464
0,509
0.500
Superpiel
(ommath al.
202
1,491
0.491
0.482
GVP-GNN Ding
1.520 20.001
0.441
0.441
20.001
0.42220.002
0.301 20.002
48.6g..8
GVP-GNN
1,01 14.1
0.475 001
0.49
0.355
53.640.6
ProNer-Amino-Aue Wang al.
0.526
00.0n1
31.740.6
ProNet-Amino Acid+SCHoll
1: 002
0.556 001
1558220.01 10.001
031220..0 001
33910.5
ProNer Buckbone (Wang 2022A
1,458
0,546
0.550
20.001
32.1
ProNdt-Rachhme-SCHHll
1.321 20.002
0L581
20.001
0.578
0.535
20.01
34A20.5
Table RMSE/Pearson Correlation/peermaan Correlation/Kendall Correlation on the LBA Test Dataset. Ave. Time refers to the average running time of one epoch in model training.
5 CONCLUDING REMARKS
In this paper, introduce SCHull constructing graph representations of molecules, large proteins, and general data with 3D point clouds. The SCHull graphs are guaranteed be sparse, connected, and rigid; these properties essential for learning biomolecules using graph neural networks. Furthermore, our proposed SCHull graph can be seamlessly integrated into the existing learning framework to boost the performance of existing models. There are a few avenues for future work. An important avenue is investigating whether the SCHull graph can ensure the maximal expressive power of GNNs for distinguishing non-generic point clouds, as demonstrated in the experiments in Appendix B
computationally efficient and scalable method for
10

---

Published as a conference paper at ICLR 2025
6 ACKNOWLEDGEMENT
This material is based research sponsored by NSF grants DMS- 2152762. MMS-2228361, DMS- 2219956, and 244-44,,,,4, and DOE grants DE-SC0023490, DE-SCC025589, and DE-SC0025801. Moreover, this work is also partially supported by the U.S. Department of Energy Advanced Scientific Computing Research (ASCR) under DOE-FOA-2493 "Data-intensive scientific machine learning".
ETHICS STATEMENT
In this paper, we propose a new graph representation for geometric data with 3D coordinates, especially molecules. The new graph solves some fundamental challenges of existing graph rep- resentations for molecules. In particular, existing graphs struggle to ensure sparsity, connectivity, and rigidity. These merits are essential for the success of machine learning for molecular modeling. Our work belongs to fundamental research and are expect to improve existing models for learning geometric data. Our work is methodological, and we validate our proposed approaches on the benchmark datasets. We do not expect to cause negative societal problems. Furthermore, we do not see any issues with potential conflicts of interest and sponsorship, discriminationbiasffiiness concerns, privacy and security issues, legal compliance, and research integrity issues (e.g., IRB, documentation, research ethics.
REPRODUCIBILITY STATEMENT
We are committed to conducting reproducible research. To ensure the integrity and transparency of our work, we employ multifaceted approach: First, we meticulously compare the novelty of our research against existing literature. This involves a thorough examination of the current state of the field identify gaps in knowledge and demonstrate the unique contributions of our work. Second, we provide detailed derivations of our proposed approaches and theoretical results. By carefully outlining the mathematical underpinnings of our methods, we enhance the understanding of our work and facilitate its verification by others. Third, we conduct rigorous experiments using widely recognized benchmark datasets. This allows us to evaluate the performance of our methods against established standards and provides solid foundation for comparison with other approaches. Fourth, we meticulously report experimental details, including the specific datasets used, parameters chosen, and evaluation metrics employed. Finally, make all experimental codes, accompanied by comprehensive documentation, publicly available. This
approach empowers researchers inspect our methods, verify our results, and build upon work. By sharing our code, foster collaboration, advance the field, and contribute to the overall reproducibility of scientific research.
REFERENCES
Leonard Asimow and Ben Roth. The rigidity of graphs. Transactions of the American Mathematical Society, 245:279-288 2899 1978.
Justin Baker, Shih-Hsin Wang, Tommaso De Fernex, and Bao Wang. An explicit frame construction for normalizing 3D point clouds. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 2456 2473. PMLR, 21-27 Jul 2024. URL https::/ https://proceddnggs mlr press/v235/baeer2...
C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa. The quickhull algorithm for convex hulls. ACM Trans. Math. Sofiw, 22(() 483, dec 1996. ISSN 0098-3500. doi: 10.1145/235815. 235821. URL /tt.://ppe///.............11111.
Ilyes Batatia. Dávid Péter Kovács, Gregor NC Simm, Christoph Ortner, and Gábor Csányi. Mace: Higher order equivariant message passing neural networks for fast and accurate force fields. arXiv preprint arXiv:2206.077 27667777000..779 2022.
11

---

Published as a conference paper at ICLR 2025
Claudio Battiloro, Ege Karaismailoğlu, Mauricio Tec, George Dasoulas, Michelle Audirac, and Francesca Dominici. arXiv:2405.15429, 2024.
(n) equivariant topological neural networks. arXiv preprint
Helen M Berman, John Westbrook, Zukang Feng, Gary Gilliland, Talapady N Bhat, Helge Weissig, Ilya N Shindyalov, and Philip E Bourne. The protein data bank. Nucleic acids research, 28(1): 235-242, 2000.
Ralph Allan Bradley. Kendall's tau and spearman's rank correlation coefficient in the context of the theory of probabilistic dependence. Biometrika, 63(3):403 414, 1976. doi: 10.2307/2335758.
Johannes Brandstetter, Rob Hesselink, Elise van der Pol. Erik J Bekkers, and Max Welling. Geometric and physical quantities improve e (3) equivariant message passing, 2021. URL https://axxiv. 1eggabs//110002900
Serena H. Chen and David R. Bell. Evolution of thyroglobulin loop kinetics in epeam. Life, (9), 2021. ISSN 1729. doi: 10.3390/life 1090915. URL htt.:::tt/////tt http://wwwwmpppp mdpi com/ 2075-1729 1975-1729/119/911
Serena H. Chen, M. Todd Young, John Gounley, Christopher Stanley, and Debsindhu Bhowmik. How distinct structural flexibility within sars-cov-2 spike protein reveals potential therapeutic targets. In 202/ IEEE International Conference on Big Data (Big Data), pp. 4333 1341, 2021. doi: 10.1 2t0.8iiDaa522892222..9999
Shiing Shen Chern. Curves and surfaces in euclidean space. Studies in global geometry and analysis, 4(1):967, 1967.
Stefan Chmiela, Alexandre Tkatchenko, Huziel E Sauceda, Igor Poltavsky, Kristof Schütt, and Klaus-Robert Müller. Machine learning of accurate energy-conserving molecular force fields. Science advances, 365)xe660001, 2017.
Yunhi Cho and Seonhwa Kim. Rigidity of nonconvex polyhedra with respect to edge lengths and dihedral angles. arXiv preprint arXiv:2307.14400 2023.
Robert Connelly. Generic global rigidity. Discrete Computational Geometry, 33:549-563, 2005,
Jose M Dana, Aleksandras Gutmanas, Nidhi Tyagi, Guoying Qi, Claire O'Donovan, Maria Martin, and Sameer Velankar. Sifts: updated structure integration with function, taxonomy and sequences resource allows 40-fold increase coverage of structure- based annotations for proteins. Nucleic acids research, 47(D1):D482 D489, 2019.
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.
David K. Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. Advances in neural information processing systems, 2015.
Floor Eijkelboom, Rob Hesselink, and Erik J Bekkers. E (n) equivariant message passing simplicial networks. In International Conference on Machine Learning, pp. 9071 1081- PMLR, 2023.
Matthias Fey and Jan Lenssen. Fast graph representation learning with PyToh Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Patrick J Fleming and Karen G Fleming. Hullrad: fast calculations of folded and disordered protein and nucleic acid hydrodynamic properties. Biophysical journal, 114(4):856889) 2018
Johannes Gasteiger, Shankari Giri, Johannes Margraf, and Stephan Günnemann. Fast and uncertainty- directional message passing for non-equilibrium molecules. In Machine Learn- for Molecules Workshop, NeurIPS, 2020a.
Johannes Gasteiger, Janek GroB, and Stephan Günnemann. Directional message passing for molecular graphs. arXiv preprint 2XVv:2003.03/23 2020b.
12

---

Published as a conference paper at ICLR 2025
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. 2021.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
Google Colaboratory. Google colaboratory: Free jupyter notebooks in the cloud. https://colab
research. www.:e.ccccoooleccccoccoc com/ 2023. Accessed: 2023-05-22.
Branko Grünbaum. Graphs of polyhedra; polyhedra as graphs. Discrete Mathematics, 307(3-5): 445 463, 2007.
Pedro Hermosilla, Marco Schäfer, Matěj Lang. Gloria Fackelmann, Pere Pau Vázquez, Barbora Kozliková, Michael Krone, Tobias Ritschel, and Timo Ropinski. Intrinsic-extrinsic convolution and pooling for learning 3d protein structures. arXiv preprint arXiv:2007.06252 2020.
Snir Hordan, Tal Amir, and Nadav Dym. Weisfeiler leman for euclidean equivariant machine learning. arXiv preprint arXiv:2402.02488. 2024.
Jie Hou, Badri Adhikari, and Jianlin Cheng. Deepsf: deep convolutional neural network for mapping protein sequences to folds. Bioinformatics, 3498):1295-1333, 2018.
Bowen Jing, Stephan Eismann, Patricia Suriana, Raphael John Lamarre Townshend, and Ron Dror. Learning from protein structure with geometric vector perceptrons. International Conference on Learning Representations, 2020.
Peter Bjør Jørgensen, Karsten Wedel Jacobsen, and Mikkel N Schmidt. Neural message passing with edge updates for predicting properties of molecules and materials. arXiv preprint arXiv:1806.03144 2018.
Chaitanya K Joshi, Cristian Bodnar, Simon V Mathis, Taco Cohen, and Pietro Lio. On the expressive power of geometric graph neural networks. arXiv preprint arXiv:2301.09300 2023.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Representations, 2017.
Gerard Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering mathemat- ics, 4(4):331-340, 1970.
Isaac E Leonard and James Edward Lewis. Geometry of convex sets. John Wiley Sons, 2015.
Michael Levitt and Cyrus Chothia. Structural patterns in globular proteins. Nature, 261(55)1): 552-558, 1976.
Jiahan Li. Directed weight neural networks for protein structure representation learning. arXiv preprint arXiv:2201. 13299, 2022.
Zian Li, Xiyuan Wang. Yinan Huang, and Muhan Zhang. Is distance matrix enough for geometric deep learning? Advances in Neural Information Processing Systems, 36, 2024.
Richard J Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979.
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 Learning Representations (ICLR), 2022.
Zhihai Liu, Yan Li, Li Han, Jie Li, Jie Liu, Zhixiong Zhao, Wei Nie, Yuchen Liu, and Renxiao Wang. Pdb-wide collection of binding data: current status of the pdbbind database. Bioinformatics, 31(3): 405-412, 2015.
Boris Mityagin. The set of real analytic function. arXiv preprint arxiv:1512.007276 2015.
13

---

Published as a conference paper at ICLR 2025
Alexey G Murzin, Steven E Brenner, Tim Hubbard, and Cyrus Chothia. Scop: structural classifica- tion of proteins database for the investigation of sequences and structures. Journal of molecular biology, 247(4):536-544 1995.
Marina V Omelchenko, Michael Y Galperin, Yuri I Wolf, and Eugene V Koonin. Non-homologous isofunctional enzymes: systematic analysis of alternatiee solutions in enzyme evolution. Biology direct, 5:1-20, 2010.
Joseph O' O'Rourke.
Computational geometry in C. Cambridge University Press, 1998.
Priyadarshini Panda and Dipankar Pati. Spearman's 's rank correlation: A comprehensive review and application. International Journal of Engineering Science and Research Technology, 4(11): 143-148, 2015, doi: w/zemo/o...oo..... 1933629,
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E(n) equivariant graph neural networks. In International conference on machine learning, pp. 9323-9332. PMLR, 2021.
Kristof Schütt, Pieter-Jan Kindermans, Huziel Enoc Sauceda Felix, Stefan Chmiela, Alexandre Tkatchenko, and Klaus-Robert Müller. Schnet: continuous-filee convolutional neural network for modeling quantum interactions. Advances in neural information processing systems, 30, 2017.
Kristof T Schütt, Huziel 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.
Vignesh Ram Somnath, Charlotte Bunne, and Andreas Krause. Multi-scale representation learning on proteins. Advances in Neural Information Processing Systems, 34:25244-25221 2021.
James Stoker. Geometrical problems concerning polyhedra in the large. Communications on pure and applied mathematics, 21(2): 1681 1968.
Gürol M Süel, Steve W Lockless, Mark A Wall, and Rama Ranganathan. Evolutionarily conserved networks of residues mediate allosteric communication proteins. Nature structural biology, 10 (1):59-69, 69, 2003.
Yonatan Sverdlov and Nadav Dym. On the expressive power of sparse geometric mpnns. arXiv preprint arXiv:2407.0200 2024.
John S. Uebersax. On the use of the pearson correlation coefficient for assessing agreement with ordinal data. Journal of the Royal Statistical Society: Series C (Applied Statistics), 36(4):427-432, 1987. doi: 10.2307/2347808.
Oliver T Unke and Markus Meuwly. Physnet: A neural network for predicting energies, forces, dipole moments, and partial charges. Journal of chemical theory and computation, 1566)3367-3363, 2019.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. Nelson, Eric Jones, Robert Kern, Eric Larson, C Carey, ilhan Polat, Yu Feng. Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, António H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing Python. Nature Methods, 17:261-272. 2020. doi: 1031038//4 592-019-0686--.
Limei Wang, Haoran Liu, Yi Liu, Jerry Kurtin, and Shuiwang Ji. Learning hierarchical protein representations via complete 3d graph networks. arXiv preprint 22Xiv:2207.12666 2022a.
14

---

Published as a conference paper at ICLR 2025
Limei Wang, Yi Liu, Yuchao Lin, Haoran Liu, and Shuiwang Ji. ComENet: Towards complete and efficient message passing for 3d molecular graphs. Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022b. URL httpttttsss///ppreeeeeeeeee
net net/fortttnnoee forum? d=mC2MMeWWFF
Renxiao Wang, Xueliang Fang. Yipin Lu, and Shaomeng Wang. The pdbbind database: Collection of binding affinities for protein- ligand complexes with known tiree-dimensional structures. Journal of medicinal chemistry, 47 2004.
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. The Twelfth International Conference Learning Representations, 2024. URL htppattt////peeeeiiiie het//Eooun?2ic-mmHllA2RRRRR
Emo Weizl, H. Alt, Kurt Mehlhorn, and Hubert Wagener. Congruence, similarity, and symmetries of geometric objects. Discrete & compulational geometry, 3(3):237-256, 1988. URL http
Zuobai Zhang, Minghao Xu, Arian Jamasb, Vijil Chenthamarakshan, Aurelie Lozano, Payel Das, and Jian Tang. Protein representation learning by geometric structure pretraining. arXiv preprint arXiv:2203.06125,, 2022.
Jingxuan Zhu, Juexin Wang, Weiwei Han, and Dong Xu. Neural relational inference learn long-range allosteric interactions in proteins from molecular dynamics simulations. Nature communications, 13(1):1661, 2022.
15

---

Published as a conference paper at ICLR 2025
A ADDITIONAL RELATED WORKS.
Invariant graph neural networks and completeness of geometric attributes. Invariant graph neural networks (GNNs) have emerged as powerful tools for analyzing geometric graphs by leveraging invariant geometrie features (attributes) that remain unchanged under transformations like rotation and translation. The effectiveness of invariant GNNs hinges on the development of such features that not only remain invariant but also truly capture the essential geometric information carried by the graph. Several studies have explored methods for learning different meaningful invariant geometric features that effectively capture the underlying geometric structure of the data. SchNet (Schütt et al.) 2018) utilizes pairwise distances between nodes as basic invariant geometric attributes. Neh (Liu et al. 2022) employs a local spherical coordinate system around each node to generate invariant distance and angular features. GemNet (Gasteiger al. 202T) and ComENet (Wang al.. 2022b) incorporate torsion angles computed on node quadruplets, which is particularly useful for predicting the properties of molecular conformers. Similar to the way torsion angles capture the angles between local structures, LEFTNet (Du et al., (024) leverages local frames centered on each node, allowing them to scalarize all spatial information into a set invariant features and then combine them with frame transition information to capture global features.
Notably. Wang et al. (2022b) introduced the notion of completeness of geometric attributes on the graph, which is closely related to rigidity. Geometric attributes the graph are considered complete they can uniquely determine the spatial arrangement of the nodes within the graph. In fact, WWang] et al. (2022b) demonstrated that their proposed framework ComENet is complete. However, as noted in (Wang et al. 2024). most existing methods, including all the models mentioned above, rely on fixed-size neighborhoods, which may be insufficient to capture all relevant global geometric features. While our graph rigidity proof hinges on the assumption of generic point clouds, it's crucial to recognize that the graph structure, formed through global assessment of geometric arrangement, cannot be inferred solely from local information.
Power graphs. The ht -ooer graph of given graph connects any two nodes if there exists a path between them in the original graph with length I k. [Sverdoov & Dym (024 propose -ooer graphs as a potential solution to achieve rigidity in 3D geometric graphs. While power graphs may offer potential approach to achieve rigidity in generic point clouds, they can lead to overly dense graphs, which can be inefficient for large-scale structures. Additionally, power graphs require the original graph be connected for the resulting power graph remain connected. Furthermore, they may fail to help GNNs distinguish between two ambiguous, non-generic point clouds. These limitations are demonstrated in Tables d and 7
High-order graphs. Several studies have explored incorporating higher-order structures into graphs to capture more detailed geometric information. Notable examples include simplicial complexes (Eijkelboom et al., 2023) and combinatorial complexes (Battiloro et al. 2024). While these ap- proaches show promise for encoding and learning geometric properties, they often suffer from high computational complexity during their construction, making them less efficient than our approach, especially when dealing with large proteins, along with other potential limitations. Specifically, simplicial complexes, constructed in (Eijkelboom et al. 2023). rely on radius-basse connectivity. which may not guarantee connectivity (and hence may not guarantee rigidity) in all cases, as shown in Fig. D However, it would interesting to explore how our graph construction method could be used as foundation for generating simplicial complexes and how these resulting complexes might perform in capturing geometric and structural properties. Combinatorial complexes provide a more general framework for higher-order structures, encompassing simplicial complexes particular interest is the concept of molecular combinatorial complexes introduced in (Battiloro et al. 2024). These complexes incorporate atoms, bonds, rings, and functional groups as cells of complexes. Developing invariant features to ensure the rigidity of these complexes presents an exciting avenue for future research. To the best of our knowledge, however, no prior work has explored this direction. We believe it would be worthwhile to investigate whether sparse, connected, and rigid simplicial or combinatorial complexes can be effectively constructed and applied in higher-order models.
subset. Of
Graph construction for symmetric detections The graph construction method we propose shares similarities with the one introduced in (Welzl et al. 1988) for symmetry detection, later adapted in the ML community construct equivariant frames (Baker et al. 2024). However, our approach defines the graph on the original point clouds, rather than solely on the projected point clouds as in the referenced work. Furthermore, design of graph attributes differs significantly: while Welzi
16

---

Published as a conference paper at ICLR 2025
et al. (988) uses interior angles of facets, employ dihedral angles between facets the key attribute in our graph construction.
B ADDITIONAL DISCUSSIONS
Rigidity of graphs. Graph rigidity, in its traditional definition, examines the geometric constraints imposed graph by fixed edge lengths. A graph with fixed edge lengths is considered rigid if allows only one possible realization of node positions, up to rigid motions; for a comprehensive understanding, we direct readers (Asimow & Roth 1978: Connelly 2005). To illustrate this concept, consider a simple 2D convex graph with four nodes and four equal-length edges. As demonstrated Fig. this graph is not rigid: can take different geometric forms, such square or rhombus. To make this convex graph rigid in 2D space, we add a diagonal edge (see Fig. ( This addition results in a structure where edge lengths uniquely determine node coordinates, up to isometry. However, rigidity can be generalized beyond edge lengths. Incorporating geometric invariants like interior or dihedral angles provides a broader perspective. For instance, fixing the four interior angles of our example graph also ensures rigidity as shown in Fig. 7 This extended notion, initially explored by Cauchy and further developed recent studies such as Cho & Kim (2023), addresses the rigidity of nonconvex polyhedra with respect both edge lengths and dihedral angles. Building upon this extended notion of rigidity, we establish theoretical guarantees for the performance of Schull graph-based graph neural networks general point clouds in Section 3.3
Figure 6: four-node graph with four edges of equal fixed length, which can form either square (left) or a rhombus (right), illustrating its non-rigidity.
Two approaches to achieving graph rigidity: on the left, square with diagonal, demonstrat- ing rigidity through fixed edge lengths; on the right, the same square with shaded angles, illustrating rigidity via fixed interior angles.
Figure 7:
Non-generic point clouds. Several existing works have explored the expressivity of GNNs
non-generic point clouds. For instance, k--isGGNS (Li et al. 2024) aim to address the limitations of GNNs in fully leveraging the distance graph (i.e., complete graph with distance edge attributes) by designing higher-order GNN models that can better distinguish non-generic point clouds. Similarly, Hordan et al. (2024) propose WeLNet, which utilizes the distance graph and provides a theoretical guarantee that it can distinguish between all non non-isometric 3D point clouds.
In this section, we apply our method non-generic point clouds, particularly focusing on symmetric point clouds to assess if it improves traditional GNNs' ability to distinguish them. Prior work, such as (Li et al. 2024). has shown that even when distances are incorporated into complete graph where every pair of nodes is connected GNNs can still struggle with special cases, such as collections of nodes from the vertices of convex regular polyhedrons.
17

---

Published as a conference paper at ICLR 2025
To investigate whether incorporating our SCHull graph addresses these challenges, we test it us- ing counterexamples of 6-point and 14-point configurations from et et al. 2024); see Fig. g for a visualization. Specificallyy y, we adapt the EGNN architecture from (Satorras et al. [022]) by removing equivariant updates and replac- ing edge attributes with invariant features such as distances and dihedral angles. Experiments were conducted on a dataset consisting of aug- mented counterexample pairs, each subjected to 20 random rotations, over 100 epochs, with results averaged over 10 independent runs. We report the mean accuracy and standard deviation to ensure robustness. The empirical results in Tables 6 and 7 demonstrate that the edge attribute design of the SCHull graph (equation (5) enables even shallow GNNs to distinguish between two non-isomorphic geometric graphs successfully.
Figure 8: Visualization of pairs of 6-point (green) and 14-point (purple) configurations from (Li ct al. 2024).
where the edges represent the dodccahedron.
To provide further validation and comparisons, have also tested the efficacy of using only edge distances within the SCHull graph and evaluated alternative graph construction methods, including radial cutoff graphs with varying thresholds, power graphs (Sverdlov & Dyml 2024), and complete graphs (Li et al., 2024: Hordan et al. 2024). The graph properties and performance for all methods are summarized in Tables and [ with tuple notations representing distinct graph properties on paired point clouds. Additionally, visualizations of the graphs for the 14-point configurations are provided Table offering a clearer geometric perspective on the differences between the approaches.
1 Layer
2 Layers
# EEdges /# Nodes
Components
Radius Graph 1.8) w/ Distance
50.0 = 0.0
60.0
0.33
Radius Graph 2.5) w/ Distance
50.0 0.0
0.00
Radius Graph (r 3.0) w/ Distance
50.0 0.0
50.0 +:00::0 0.0
1.67
4 -power Radius Graph (r 1.8) w/ Distance
50.0 = 0.0
50.0 00.0::0..0 0.0
0.33
4 "power Radius Gruph (r 2.5) w/ Distunce
100.0 1 0.0
100.0 0.0
(1,
(2, I)
ppower Radius Graph (r = 3.0) w/ Distance
50.0 10 0.0
50.0 0.0
2,5
Complete Graph w/ Distance
50.0 = 0.0
50.0 0.0
SCHoll w/ Distance
50.0 0.0
0.0
2.0
SCHall w/ Distance and Dihedral Angles
100.0 1: 0.0
100.0 0.0
2.0
Table 6:
Comparison of graph properties and GNN performance (Unit:%) on 6-point symmetric point clouds using different graph construction methods. Tuple notations represent distinct graph properties on paired point clouds.
Layer
Layers
Edges/# # Nodes
# Compooennts
Rudius Graph (r 1.8) w/ d.3
50.0 1.0.1.000
50.0 1 0.0
(1.2)
Radius Graph (r 2.5) w/ d.
5..0
51.0 3.0
3.0
Radius Graph (r = 3.0) w/ dej
60.5 11.1
57.2 + 9.1
5.0
1 '"-power Radius Graph (r 1.8) w/ dej
100.0 1: 0.0
100.0 1 0.0
(5.3)
(1,2) 2)
"power Radius Graph (r = 2.5) w/ dej
50.0 1:00::0 0.0
50.0 1. 0.0
6.5
T "o-pww Radius Graph (r = 3.0) w/ dig
5.00
50.0 0.0
6.5
Complete Graph w/ d.y
6.60
50.0 0.0
SCHull w/ di
1.0
100.0 0.0
2,57
SCHull w/ d: and Tt
100.0 + 0.0
100.0 + 0.0
2.57
Table 7: Comparison of graph properties and GNN performance (Unit:%) on 14-point symmetric point clouds using different graph construction methods. Tuple notations represent distinct graph properties on paired point clouds.
The results showcase the limitations of alternative methods: radius graphs face issues of disconnectiv- ity at small radii and edge redundancy at larger radii, neither of which ensures consistent performance; power graphs exhibit inconsistent performance that depends heavily on careful parameter tuning, and they fail to address issues of sparsity or connectivity effectively; complete graphs while providing exhaustive connectivity are computationally expensive and do not improve accuracy. In contrast, the SCHull graph achieves a balance of sparsity and rigidity, offering compact yet expressive representation that enhances GNN performance. Its efficiency and scalability make it particularly appealing for large datasets, enabling effective learning with minimal computational overhead.
18

---

Published as a conference paper at ICLR 2025
Radius graph with cutoff 1.8
4th power radius graph with cutoff 1.8
Radius graph with cutoff 2.5
4th power radius graph with cutoff 2.5
Radius graph with cutoff 3.0
4h power radius graph with cutoff 3.0
SCHull graph
Complete graph
Table 8:
We visualize the graphs of 14-points point clouds used in the experiments whose graph properties and performance with GNNs are presented in Table 7
These findings emphasize the SCHull graph's robustness and efficiency in distinguishing symmetric point clouds, confirming its design as both expressive and computationally efficient. However, a formal theoretical analysis of this approach for non-generie point clouds left as direction for future work.
Geometric Interpretation. We present an intuitive explanation of the SCHull graph construction to clarify its connection to the convex hull and its advantages in representing point clouds.
The convex hull captures only the outermost boundary of a point cloud, omitting information about interior points. This is evident in Fig. where the convex hull of {æ; )6 (left) aligns with the SCHull graph for those points. However, for { (right), the convex hull remains the same as for {x 16 failing account for interior points 27, Zg. In contrast, SCHull connects interior points, preserving the structural relationships necessary to recover both the convex hull and the full geometry of the point cloud.
19

---

Published as a conference paper at ICLR 2025
SCHull's design addresses this limitation by leveraging spherical projection. Points mapped onto the unit sphere, where the graph structure is computed. This ensures that interior points contribute to the graph's structure. Conceptually, this transformation is akin to converting 3D Cartesian coordinates (x, y, 2) into spherical coordinates (r, 0, Φ). where the radial distance r is excluded in the graph construction. The SCHull graph, therefore, relies only the angular coordinates (0,, Φ), capturing the intrinsic geometry of the point cloud. One can see this rationale through the polar grid in Fig. 2 Importantly, the radial coordinate is retained of the original 3D coordinates (r. 0, Φ) and allows SCHull to represent global geometric properties
node feature. This allows for the reconstruction
effectively. For example, as shown in Fig. edge lengths like | æ7 || and ||| Iel || can be used
together with node features || |l. [ [r7| ||a]| Toll-
compute information the convex hull, such as
In summary, SCHull preserves the global geometry of the convex hull while enriching it with the structural representation interior points. This makes SCHull an effective tool for capturing the full spatial structure of point clouds and their intrinsic relationships. We note that Fleming & Fleming (2018) uses the convex hull to estimate hydrodynamic volume, and we believe that the SCHull graph could not only improve the prediction of this property but also offer additional insights.
IP
11
Z8
Figure 9: This figure highlights the close relationship between the convex hull of point clouds and SCHull graphs. While the convex hull captures only the outer boundary, potentially discarding information about interior points, the SCHull graph retains this information by connecting interior points. The edges of the SCHull graph are represented by solid gray lines, while the dashed gray lines indicate convex hull edges that differ from those of the SCHull graph. This distinction emphasizes SCHull's 's ability to preserve and enrich geometric relationships beyond the convex hull.
Discontinuous intrinsic properties of graph construction. The discrete nature of graph data inherently prevents the possibility of truly continuous graph construction, a limitation shared by all graph construction methods, including the one proposed in this work. While this was not the primary focus of our discussion, it raises an intriguing question: how does the choice of graph construction, especially those with attribute designs, affect the smoothness properties of end-to-end neural network models? Specifically, if the input data is perturbed by noise or errors, can we theoretically analyze how different graph construction methods influence the resulting impact on the neural network's 's output? For instance, does the output exhibit stability under input perturbations such that the end-to-end models are still continuous?
C MISSING PROOFS AND ADDITIONAL DETAILS
Proposition 3.1. Let 2 (2,) be set of points on a sphere where |2| 2 3 (the number of points at least 3), and let Conv(2) denote the convex hull of with its associated graph structure consisting of nodes, edges, and faces defined by its boundary. Then, we have
1. Connectivity: Any two points in Z are connected by sequence of edges in Conv(Z),
2. Sparsity: The number of edges in Conv is greater than 3|2 6.
20

---

Published as a conference paper at ICLR 2025
Moreover, Conv(Z) is strictly convex geometric polyhedral graph if z are not coplanar.
Proof of Proposition 3.7 Since the point cloud Z lies on a sphere, each point in is an extreme point (Leonard & Lewis 2015) of (Z)y Consequently, each point appears as a node in the graph structure of the convex hull. If the points in Z are not coplanar, then Conv () is convex polyhedron, and, hence by definition, Conv(2) 2) is a strictly convex polyhedral graph. Since each convex polyhedron can be represented as 3-connected planar graph by Steinitz's 's theorem, Conv is connected, and the number of its edges is bounded above by 3 2| 6 (Lipton & Tarjan 1979 O'Rourke 1998). If the points 2 are coplanar, then Conv(2) itself a connected planar graph. Therefore, the same bound of 3 z 6 on the number of edges holds.
Lemma 3.4. Any generic point cloud satisfies the generic assumption equation
Proof of Lemma 3.4 If æt; = æ for some E V. it directly defines a linear algebraic dependence on
the coordinates, leading to contradiction. Similarly, suppose Px P=());) = (T,) for some i, E V.
Then we have
(=) [|]l= implying that (z), क) (2z क) = |z I |||| - ø||. Taking the square of both sides, we obtain an algebraic dependence on the coordinates, which leads to contradiction.
(2n; [| -
Lemma 3.5. Let (V.X) be a generic point cloud. Then Conv ((pz(x,) i V)) the convex hull on the sphere we constructed in Section 3.7
is strictly convex geometric polyhedral graph.
Proof of Lemma 3.5 Due to Proposition 3.1 it suffices to show that (p=(..) i E V) are not copla-
nar. This is true unless the original point cloud lies on a plane, which contradicts the genericity assumption.
Theorem 3.6. Let F be a maximally expressive GNN with depth T = 1. Then F can distinguish between the attributed SCHull graphs defined in equation (5) of any two non-isomorphic generic point clouds.
The proof is inspired by the work Sverdlov & Dym (024). Consider two SCHull graphs, 9 and G', generated from point clouds (V,X) and (V", X respectively. the maximally expressive GNN F assigns the same global feature G and G' after one iteration, then the multisets of node features { and & are identical. This implies [V| = [V* By relabeling, necessary, we assume that s; = s/ for all E V. This further implies that for each node i V, the node features f: = f and the multisets of edge features Yei 1 E = f'', j E W are also the same. That is, ||=; क|| = =|1 x' and {[|=; xz, 1l, Tby) l E Nº. [[1= x T/y)) j E A/ Notice that the number of edges |g| equal to 1 E. d,, where d, denotes the degree of the node i. Since the degrees of corresponding nodes on graphs 9, g' are equal, both graphs have the same sum of node degrees and hence the same number of edges, i.e., |8| = =E'|. Due to the generic nature of point clouds, for any edge (i,j) E, the distance ||ar] 18--2j 21'ل will appear exactly once in the multisets corresponding to nodes and j on both graphs. This means that (i,j) is also edge in E' and hence the underlying graph (V, and (V",'" are isomorphic. also follows that the edge attributes of corresponding edges the same, i.e., ||z; æ;y1 = ||a. - 2z/1 and Tiy T Next, observe that the triple (||z; - æzyll |Il ||æ; क||, |æ, x uniquely determines the distance between projected points Pa (=)),,=(2r,)) on the unit sphere as we show in Lemma C. below. Therefore, the equality between triples (||æe - I| क 1|,,, T)) [) (I|=²) - -= 2311. -o'll 1| x')) implies (x,) - Pan (x; (V,E) and (V", are isomorphic. we can conclude that (VE.))x()) and (v", E', ,'' (XX)) are geometrically isomorphic using Lemma 3.5 and Theorem 2.1] Finally, because we can recover the original coordinates X from the projected points (x) by T[x Æ p=((x))))))))))>))))>))><))))p = E; (V, (V,E, X, F) and (V", E' X', X'FF) are also geometrically isomorphic.
Proof of Theorem 3.6
2
(x() - Pa- (z/) I| Combined with the identity Tú Thy and the fact that
Lemma C.1. The triple (1|z; -1ll [x; - H ||x, æ[I) uniquely determines the distance between projected points P= (x:),, Pa (a);) on the unit sphere.
21

---

Published as a conference paper at ICLR 2025
We denote the projection Pæ by p for simplicity. Notice that the angle formed by the vertices 24, T; 2j is the same as the angle formed by the vertices p(z;), E, p(æ,), since projection preserves the angle subtended by these points. Denote this angle by Following the Law of Cosines, we have:
Proof of Lemma C.1
cos(a) = [2: x
11
(6)
2 21
I
2
and
[lp(x;) p(ar))l1 = [p({;)) - x=1 |1p(;;) æ²1² -=1lp((=;) - 2 []]lp(a;)) æi| cos(a)
= - 2 c0s)
where we have used the fact that IIx(a;;) - I = and ll((zy) क = as both points lie
on the unit sphere. From equation 66). we compute cos(a:) using the given triple (I|æ; æzll. ||,, æ|I, : | =|). Substituting this value of cos(a) into equation (7). we can then solve for [pp(;;) - p(æ,))|| which gives the distance between the projected points.
D MAINTAINING THE CONNECTIVITY OF SCHULL
In the SCHull graph construction presented in the main text, we assume the following condition holds:
2; * x: and (=,);) * (m,,) for any i + E
(8)
Here, we outline strategy to maintain the connectivity and sparsity of our graph when the generic condition equation (3) does not hold.
When x; = τ for some node i: To preserve graph connectivity, we employ a strategy similar to k-nearest neighbors. We connect æ; its nearest neighbor(s) in the point cloud. Unless there is a significant number of points exactly at the center of the point cloud, this modification will not substantially compromise sparsity.
When Pa(xx) # (xy ) for some nodes j.j In these cases, we compare the norms ||>,|| and || ||- If ||al|| > ||ay we treat æ; as the representative of the point p= the unit sphere and then connect edges to æ; following the original SCHull graph construction. Subsequently, we connect v.. This approach ensures that sparsity is preserved.
E SCHULL GRAPHS OF 2D POINT CLOUDS.
Figure 10: A visualization illustrating how the edge lengths of polygon on the unit circle uniquely determine the spatial arrangement of its vertices.
When point cloud lies on the plane, its associated SCHull graph corresponds to polygon, with each vertex positioned on the unit circle, as illustrated in Fig. 10] In this case, the dihedral angles, as defined in equation (5). become zero since there is only single facet.
Nevertheless, the SCHull graph with edge attributes ||=: Iz, and node attributes I T|| provides sufficient information for maximally expressive GNN distinguish non-isomorphic generic point clouds on the plane. Here the genericity of point clouds (Definition 333) is characterized by 2D coordinates the plane. The formal result is stated in the following theorem:
22

---

Published as a conference paper at ICLR 2025
Theorem E.1. Let F be a maximally expressive GNN with depth T = 1. Then, F can distinguish between the attributed SCHull graphs defined in equation (3) of any two -soioooooppicc generic point clouds on the plane.
The proof of this theorem follows a similar approach to Theorem 3.6 relying on an analogous result to Theorem 2.1 for polygons on the unit circle. Specifically, we need to show that the edge lengths of a polygon uniquely determine its structure on the unit circle, up to isometry:
Lemma E.2. The coordinates of the vertices of an n-polygon inscribed in a circle are uniquely determined by the sequence of its edge lengths, up to isometry.
Proof of Lemma E.2 Let the coordinates of the vertices on the circle be denoted as 21, 22, ..,.... Zn. ordered counterclockwise. We aim to show that the edge lengths || x; || for 1 < i S n and || =,,/| are sufficient to uniquely determine the vertices #1, 22, ................................ Fn. up to isometry. Each edge length || - zill determines the triangle formed by 2,, Zi+1. and the circle's s center using the side-side-side (SSS) triangle congruence criterion. Similarly, the edge length ||=] zn.ll determines the triangle formed by 21, and O. By sequentially composing these triangles in order, the shape of the entire polygon is fully determined by Cauchy's Arm Lemma (Chern 1967) up isometry. A visualization is demonstrated in Fig. 10
Proof of Theorem E.1
we first establish that the underlying graphs (V, and E"), Additionally, the distances between corresponding nodes satisfy ( Pz (1, = (x²) - Pa paz (r)))) From the graph structure of the polygons, it follows that the sequence of edge lengths is identical for the two graphs. By Lemma E.2 this
Following the same steps as in the proof of Theorem 3.6
implies that the projected point clouds on the circle are identical up to isometry. Using the node
features { {| æiI} and {||ar æ') æ'I]), we conclude that the underlying point clouds are identical up to isometry.
F RIGIDITY OF ATTRIBUTED SCHULL GRAPHS WITHOUT NODE ATTRIBUTES
In Section we demonstrated that the attributed design defined in equation (5) is sufficient for maximally expressive GNNs to distinguish non-isomorphic generic point clouds in Theorem (3.6] Here, we investigate when the node attributes f. ||æ; क| representing the original distance of each point to the center of the point cloud, can be omitted. We will show that edge lengths and dihedral angles are sufficient to guarantee the rigidity of SCHull graphs of generic point clouds under the following additional generic assumption:
Any four projected points (ax( are not coplanar.
(9)
Point clouds that do not satisfy this condition are included in a finite union of zero sets of analytic functions, which has Lebesgue measure zero (Mityagin 2015).
Specifically, we aim to prove the following theorem:
Theorem F.1. Let F be a maximally expressive GNN with depth T = 1. Then F can distinguish between the SCHull graphs using only edge-attribute defined in equation of any two non- isomorphic generic point clouds satisfying equation
Note that the proof of Theorem 3.6 relies on the rigidity of strictly-convex geometric polyhedral graphs stated in Theorem 2.1 Similarly, our proof of Theorem F.T relies on the following rigidity theorem for geometric polyhedral graphs from (Cho & Kim 2023):
Theorem F22. If a geometric, possibly nonconvex and ielfffnttrrsecting, polyhedral graph satisfies that (i) every face is convex, (ii) there are no coplanar adjacent faces and no set of seven vertices lies on the same plane, and (ii) any triple of vertices is not collinear, then its geometric arrangement is uniquely determined up to rigid motions by its dihedral angles and edge lengths.
To prove Theorem F. it suffices to show that generic point clouds satisfying equation required conditions in Theorem F2
9 fulfill the
First, the genericity of point clouds ensures the conditions (ii) and (iii,, as they can be expressed as polynomials of points' coordinates with rational coefficients. To demonstrate that all faces on the
23

---

Published as a conference paper at ICLR 2025
SCHull graph convex, observe that since any four projected points {p=(#,)) are coplanar, their convex hull can only have triangles as its faces. This implies that the faces of the SCHull graph all triangular, and triangles inherently convex.
G ALGORIHHMM AND ARCHITECTURE DETAILS
G.1 GRAPH CONSTRUCTION ALGORITHMS
Radial cutoff. The Radial cutoff graph construction is implemented using the PyTorchGeo- metric (Fey & Lenssen 2019) data transform RadiusGraph. This constructs the set of edges {ez [ xy < r for fixed radius In the NestedSquares dataset 4, this is the side length of the outer square. In all other tasks, where the baseline models use RadiusGraph to construct the graph, we use the default radius r.
:NN. The ENN graph construction is implemented using the Py PorchGeeemrrri (Fey & Lenssen 2019) data transform KNNGraph. This constructs a directed set of edges such that each node has exactly neighbors. The graph then made undirected. In all tasks k 3.
The Voronoi graph construction is implemented using the SciPy (Virtanen et al. 2020 spatial transform Voronoi. This constructs an undirected graph from the ridges of the Voronol diagram.
Voronoi.
G.2 MESSAGE PASSING NEURAL NETWORK
The following message-passing neural network:
mij = &m (1/r eiy)
m. Σ mij
JEN(()
h Φn (h!: m,)
In particular, for the architecture MPNN+SCHull, we utilize the attributed version of SCHull defined in equation (5). For the base MPNN architecture, the edge attributes are discarded, i.e., m,j = Φm (h h)))
used for the experiments in Section 3.3
H BENCHMARK DETAILS
H.1 NESTEDSQUARES
The NestedSquares dataset is graph property prediction task designed to test the expressivity of geometric GNNs. The training, validation, and test splits contain rotated graphs depicted in Fig. There are 6 training graphs, 2 test graphs, and 2 validation graphs, and they contain randomly rotated graphs. The training procedure uses the Adam optimizer to minimize the mean squared error (MSE) loss between the model predictions and ground truth graph labels. The training uses the Adam optimizer with learning rate of le-4 and a learning rate scheduler, which reduces by factor of 0.9, has patience of 25, and minimum Ir of le-5. The model is trained for 100 epochs, with the test loss reported for the epoch with the best validation loss.
H.2 MD17
The MD17 dataset a node property prediction task, which contains a variety of molecular dynamics trajectories. Both the training and validation sets contain IK samples, with the remaining data used for testing. The training procedure uses the Adam optimizer to minimize the LI loss between the model predictions and ground truth molecular energy and forces. The training uses the Adam optimizer with learning rate 5e-4 and learning rate scheduler which reduces by a factor 0.5 and has a patience of 50. The model is trained for 1100 epochs, with the test loss reported for the final epoch.
24

---

Published as a conference paper at ICLR 2025
H.3 PROTEIN DATASET
Fold dataset. We utilize the same dataset as that used by Hou et al. 201 8); Wang et al. (2022a). The dataset includes 16,292 proteins across 1,195 folds. To assess generalization performance, three test sets are employed: Fold, where proteins from the same superfamily are excluded from training; Superfamily, where proteins from the same family are not included in training; and Family, where proteins from the same family are part of the training data. Among these, Fold poses the greatest challenge, its proteins differ the most from those in the training set. For this task, 12,312 proteins are used for training. 736 for validation, 718 for Fold, 1,254 for Superfamily, and 1,272 for Family.
Reaction dataset. For the reaction classification task, 3D structures of 37,428 proteins corresponding to 384 EC numbers are obtained from PDB (Berman et al. 2000), with EC annotations for each protein retrieved from the SIFTS database (Dana et al. 2019). The dataset is divided into 29,215 proteins for training, 2,562 for validation, and 5,651 for testing. Each EC number is represented across all three splits, and protein chains sharing more than 50% sequence similarity are grouped.
LBA dataset. Following (Jing al. 2020), we perform ligand binding affinity predictions on subset of the commonly-usee PDBbind refined set (Wang et al. 2004 Liu et al. 2015). The curated dataset of 3,507 complexes is split into train/val/test splits based verify the model generalization ability for unseen proteins. For a protein-ligame complex, we predict the negative log-transformed binding affinity pk logio (K) in Molar units.
30% sequence identity threshold to
I HYPERPARAMETER DETAILS
1.1 NESTEDSQUARES
Table 9 reports the hyperparameters for each invariant GNN which are adjusted from the baseline models. Additionally, we find that models are particularly sensitive the cutoff which serves as soft threshold parameter in each of the models. We report the results from the best cutoff using grid search from to 10. The chosen cutoff parameter is reported Table TO
num_radial
num.spherical
DimeNete+
128
SphereNet
256
ComENet
128
8
MPNN+SCHall
Table 9: Hyperparameter selection for the NestedSquares dataset.
Radial cutoff
ANN 3)
Voronoi
SCHoll (ours)
MPNN
6
DimeNete+
SphereNet
ComENer
Table 10: Cutoff hyperparameter in the NestedSquarse task for each model and graph connectivity.
I.2
MD17
Model and training hyperparameters for the MD17 task are listed in Table 11
1.3
PROTEIN DATASET
Model and training hyperparameters search space for the protein tasks are listed in Table 12
25

---

Published as a conference paper at ICLR 2025
Hyperparaneter
Valnes/Search Space
Number of layers
4,6
Hidden channels
Number of radial basis
32, 64
Cutoff
6, 10
Epochs
1200
Batch size
64
Teamming mote
Leamiigg rate scheduler
steplr
Learning rase docay factor
Learning rute decay epochs
180
Weight decay rate
le-12
Table 11: Model and training hyperparameters search space for MD17 tasks.
Values/Search Space Fold
Hlpeepurammter
Number of layers
4,
4,
4,
Hidden channels
64, 128, 256
64, 128, 256
128, 192, 256
Cutoff
8,
6,8, 10
SCIlull-Cutoff
6, 7,
7,
6,8
Dropout
0.2,
Epoochs
500, 1000
500, 1000
300, 500
Batch size
16, 32
16, 32
16,
Learning
1o-4,56 5e-4
Ie-4, 5c-4 stoplr
5e-5, le-4, 2c-4 steplr
Learning rate scheduler
steplr
Learning decay factor
0.5
0.5
0.5
Learning rate decay opochs
50. 100
100, 200
50, 100
Table 12: Model and training hyperparameters for protein-related datasets.
26


Reviews:
[{"review_id": "w1K3lRjy7r", "reviewer": "Reviewer_SxaB", "summary": "The present manuscript proposes a novel graph construction method, SCHull for molecular modeling thorugh GNNs. The authors start by introducing limitations of the currently existing graph construction  methods (e.g. radial cuttoff, and knn graphs), that cannot deal with sparsity, connectivity, and rigidity at the same time.\n\nThe method constructs graphs in two steps, first by projecting points onto the unit sphere. and secondly by constructing a convex hull for the projected points, and adding edges to the graph, based on the convex hull. According to the authors' motivation, the resulting graphs are sparse, connected, and rigid, making them suitable for learning molecular representations using GNNs.\n\nThe authors show the impact of SCHull, by integrating it into current molecular Gnns, and test it in various benchmarks, including MD17, as well as protein modeling tasks (fold, enzyme reaction classification, Protein-ligand binding).", "questions": "Based on my comments in the weaknesses section: \n\n1. Can the authors provide a comparison (at least conceptual, but ideally an empirical one) with methods that include power graphs, or higher-order structures?\n\n2. Do the authors think that such a method can provide interpretability benefits? If yes, I think that the motivation could be much strengthened. In that case, is it possible to provide an interoperability analysis?\n\n3. Can the authors show the impact of the method empirically on each graph property mentioned in the paper (I..econnectivity, and rigidity)", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. I particularly find Theorem 3.6 interesting, and useful for the distinction of point clouds through their corresponding SCHull graphs. In general, the authors provide a well-defined set of propositions for defining connectivity, rigidity, and sparsity for the SChull graphs, making it useful for predicting their impact on GNN's performance and scalability.\n\n2. The motivation for a hyper-parameter free approach for graph construction is very intriguing, and can be proven very useful for molecular modeling tasks, where the distance thresholds can play an important role. \n\n3. The empirical results show that in both small- and large-molecular modeling tasks, SChull has a positive impact in a couple of GNNs. \n\n4. The paper is well-written, the formulations are clear, and the experimentation setup is nicely described.\n\n5. It's very interesting that Tables 4, and 5 show a comparable increase of the runtime cost, with respect to the methods without the SChull. I would expect a much longer runtime discrepancy, due to the point projection, and the CH computation.\n\n5. The code is available, seemingly containing all variants of models and benchmarks appeared in the manuscript. I cannot assess its validity, as I did not run it.", "weaknesses": "1.  The paper primarily compares SCHull to radial cutoff and k-nearest neighbor graphs, as well as chemical graphs. It lacks  some compariso with more recent or complex molecular graph construction methods, such as power graphs [1] (which are by the way already mentioned by the authors but not benchmarked) or methods focusing on higher-order graphs, such as simplicial complexes [2] ( that define volumes of data points), or combinatorial complexes [3] (that particularly make use of convex hulls and their corresponding volumes in point clouds).\n\n2. An approach on learning new geometric interactions might be useful in better interpreting the correlation of geometry and function, which could be particularly a motivation for this paper. The paper should focus on exploring or at least mention how such a convex hull approach, despite a comparable computational cost can help on finding interpretable structures.\n\n3. Since the method is focusing on the three properties of sparsity, connectivity, and rigidity, it'd be great if the authors can show empirically the impact of SChull on each of these properties independently. \n\n[1] On the Expressive Power of Sparse Geometric MPNNs. Sverdlov et al 2024.\n[2] E(n) Equivariant Message Passing Simplicial Networks. Eijkelboom et al 2023.\n[3] E(n) Equivariant Topological Neural Networks. Battiloro et al 2024.", "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": "Bv5RDwgDNZ", "reviewer": "Reviewer_NBfx", "summary": "This paper proposes a novel method for constructing sparse yet connected geometric graphs: Project the points onto a sphere, construct a polyhedron, and construct a graph from its edge structure. This aims to mitigate earlier costly approaches of taking the power graph of the original graph. The authors first prove theoretical properties of their construction and show that maximally expressive MPNNs with particular initializations for node and edge features can distinguish among generic graphs, essentially proving that via a sparse graph structure (degree bounded by 3) 1-WL can distinguish all generic point cloud configurations (i.e. not assuming a fully connected point cloud as in earlier works). The authors then empirically show the construction's efficacy and value of the SCHull face angles that allow for universality on sparse configurations, by obtaining consistently better results on synthetic, classification, and regression tasks.", "questions": "1. Overall I think the proof of Theorem 3.6 is correct. I do have a few questions though:\na) \"Since the degrees of corresponding nodes are equal, both graphs have the same number of edges, i.e., |E| = |E′|.\" I don't see why this is true, later you discuss how the corresponding edges match because of the generic nature of the point cloud, and then by equality of multisets you could have claimed the number of edges is equivalent.I might be missing something.\nb) \"Next, we observe that the triple (∥xi − xj ∥, ∥xi − x∥ , ∥xj − x∥) uniquely determines the distance between\nprojected points px(xi), px(xj ) on the unit sphere.\" \nI don't see how I recover $|| \\frac{x_i - \\bar{x}}{|| x_i - \\bar{x}||} - \\frac{x_j - \\bar{x}}{|| x_j - \\bar{x}||} ||$ from those three distances, please enlighten me.\n\n2. There exist known counterexamples for fully connected geometric graphs that 1-WL cannot distinguish. It may be the case that your maximally expressive SCHull-MPNN with edge features and node features can distinguish. One such example is depicted in Figure 1 in [Li et al.]. They have code for the coordinates of these shapes or I can also provide them if necessary. Is the maximally expressive architecture you propose able to distinguish among them?\n\n\n[Li et al.]Li, Zian, et al. \"Is distance matrix enough for geometric deep learning?.\" Advances in Neural Information Processing Systems 36 (2024).", "limitations": "", "rating": 10, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. Novel technique relying on a fast (n*log(n)) algorithm is scalable and empirically also negligible computational overhead\n2. Introduces a novel technique to a paradigm not challenged much in research: the distance cutoff construction for geometric graphs. Theoretical and empirical proof this approach is sound.\n3. An architecture-agnostic method that can be applied to a large variety of MPNN-like models", "weaknesses": "1. Proofs mainly rely on previous work and the construction of the graph is also backed by a known algorithm, thus there is a notion of an incremental advance. Although, I believe that tying these two areas together constitutes a strong advancement for ML.\n\n2. The empirical results are consistent yet are not pushing the boundary on SOTA, but rather give a `boost' to low expressive models. It would be nice to see the performance of working on SCHull graphs with the initial edge and node features for more expressive architecture, for instance, MACE or SEGNN (\"Geometric and physical quantities improve equivariant message passing\", Brandstetter et al.) I suspect it would make less of a difference but please prove me wrong. Anyway, only having a comparable result to these architectures (when they process distance-restricted graphs) with faster inference is still a great achievement. If this is performed I may increase my score.\n\n3. The background for geometric deep learning is insufficient in my opinion. For instance, there is no discussion on research on expressivity when point clouds are not necessarily generic and a comparison of your approach with models that are universal (or complete) on **all** point clouds. For a couple of papers on this topic please note:\n\nHordan, S., Amir, T. and Dym, N., 2024. Weisfeiler Leman for Euclidean Equivariant Machine Learning. ICML 2024\n\nLi, Zian, et al. \"Is distance matrix enough for geometric deep learning?.\" Advances in Neural Information Processing Systems 36 (2024).\n\nOverall this paper has strong potential, addressing these weaknesses will likely increase the rating.", "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": "A0hC6jaA6n", "reviewer": "Reviewer_asjR", "summary": "The paper presents a hyperparameter-free graph construction method for molecular modeling that ensures sparsity, connectivity, and rigidity. It addresses the limitations of traditional methods, like radial cutoff graphs, which lack guarantees for both connectivity and sparsity and fail to leverage spatial arrangements effectively. The proposed method consistently generates connected, sparse graphs with an edge-to-node ratio capped at 3, and ensures rigidity, making spatial arrangements uniquely determinable. The approach is proven effective and efficient in various molecular modeling benchmarks.", "questions": "1.Since the method is primarily applied to molecular analysis, do the conclusions require alignment with relevant chemical principles? The paper explains the utility of the SCHull graph in enhancing GNN capabilities, but could such a projection result in the loss of certain chemical properties?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.The proposed SCHull method is quite innovative. I appreciate the author's idea of introducing unit spherical mapping, which makes the graph construction more reasonable and reliable. The implementation is also very clever.\n\n2.The paper provides thorough validation of the proposed method in well-justified experimental settings.\n\n3.The paper conducts comprehensive theoretical validation to demonstrate the effectiveness of the method.", "weaknesses": "1.The discussion primarily focuses on molecular analysis, which may make the paper lean somewhat towards chemistry and biology. However, this does not detract from it being a strong paper. It may be worth considering whether this method could be applied to other types of graph data analysis.\n\n2.Could consider conducting some visualization experiments, if the level of difficulty permits.", "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": "u4ulzAovTE", "reviewer": "Reviewer_exXC", "summary": "Overall, the paper provides valuable contributions and should be accepted, though it requires both minor and significant revisions. I have given a lower score to ensure that all issues are addressed. The paper effectively tackles the challenge of defining the underlying combinatorial graph, which is crucial for performing accurate analysis and properly separating point clouds.", "questions": "First of all your algorithm is very similar to the one proposed in the paper Congruence, Similarity, and Symmetries of Geometric Objects, 1987. You didn't cite but this citation must be added, as the first two steps are identical to it. No problem with it but citation must be added.\n\n**Technical Issues:**\n1. Line 167 should use \"if and only if\" in reference to edge isomorphism.\n2. After Theorem 3.6, add a remark noting that implementations of maximally expressive GNNs for generic point clouds exist, such as in Sverdlov & Dym.\n3. Figure 4 and its details should be moved to the experiments section.\n4. All theorems and propositions should either be restated in the appendix or, at the very least, have a mention of what is to be proven there.\n\n**Conceptual Issues:**\n1. In your framework, you separate complete generic geometric graphs, unlike Joshi [23] and Sverdlov [24], who work with given combinatorial graphs. This difference should be explicitly stated in your setup, and it should be clear that the goal is to construct the underlying graph.\n2. The discontinuity of your graph construction should be discussed. Since the function is discrete, it cannot be continuous, but this point should be acknowledged.\n3. Proposition 3.1 is not proven at all. Some minimal proof or explanation is necessary.\n4. Regarding the MD17 experiments, I would like to know which models you considered in your comparison and, specifically, if your method improved in the SOTA method. Same for protein folding.\n5. What is the computational running time for complete graphs? Does considering the complete structure degrade performance?\n6. When you combine the k-hop/threshold graph, how do you choose the parameters to ensure connectivity, sparseness, and constructability?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Here’s an expanded version of your statement:\n\n\"The paper presents a pioneering approach for constructing an underlying combinatorial graph for a given point cloud, addressing several crucial challenges in graph-based data representation. The proposed method ensures key properties such as connectivity, sparsity of the graph, and the ability to accurately reconstruct the original point cloud. These properties are essential for both efficient computation and the preservation of the inherent structure of the data.\n\nBy focusing on these aspects, the authors effectively balance the need for a graph that is sufficiently sparse—thereby reducing computational complexity—while still maintaining connectivity, which is necessary for capturing the relationships between points in the cloud. This delicate balance is often difficult to achieve, as sparse graphs may lose critical information, and densely connected graphs can lead to inefficiency and overfitting. The authors’ method overcomes this trade-off and ensures that the graph retains the essential features of the point cloud, enabling reliable downstream analysis.\n\nAdditionally, the paper demonstrates how the performance of existing methods can be significantly improved by replacing the traditional graph construction techniques with the newly proposed combinatorial graph. The empirical results presented show notable enhancements in areas such as classification accuracy, clustering performance, and point cloud segmentation, underscoring the practical benefits of the new graph structure. These improvements are a testament to the robustness and effectiveness of the method, positioning it as a valuable tool for a wide range of applications in fields such as computer vision, machine learning, and graph signal processing.\n\nThe introduction of this novel graph construction framework represents a substantial step forward in the field, potentially opening new avenues for research on graph-based point cloud analysis. It not only improves existing methodologies but also provides a foundation for further exploration of how combinatorial structures can be leveraged to better understand and manipulate high-dimensional data.\"", "weaknesses": "The main weakness of the paper is that the proposed graph construction is not continuous and doesn't operate on a pre-existing attributed graph. Instead, it creates its own selected graph, which may limit its applicability in cases where the underlying graph already contains valuable domain-specific information. This approach lacks flexibility, especially in scenarios where a smooth transition or integration with existing graph structures is required. As a result, the method may overlook important attributes or contextual details in real-world applications, reducing its versatility. The main concern is that the point cloud may become copolar and thus, the convex hull would become 2-dimensional. Does it happen in real-world datasets?", "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 (Oral)