Rhomboid Tiling for Geometric Graph Deep Learning
Authors: Yipeng Zhang
Longlong Li
Kelin Xia
Venue: ICML 2025 poster (2025)
Keywords: Rhomboid tiling
geometric deep learning
molecule property classification
graph pooling
Primary area: applications->chemistry_physics_and_earth_sciences

Abstract: Graph Neural Networks (GNNs) have proven effective for learning from graph-structured data through their neighborhood-based message passing framework. Many hierarchical graph clustering pooling methods modify this framework by introducing clustering-based strategies, enabling the construction of more expressive and powerful models. However, all of these message passing framework heavily rely on the connectivity structure of graphs, limiting their ability to capture the rich geometric features inherent in geometric graphs. To address this, we propose Rhomboid Tiling (RT) clustering, a novel clustering method based on the rhomboid tiling structure, which performs clustering by leveraging the complex geometric information of the data and effectively extracts its higher-order geometric structures. Moreover, we design RTPool, a hierarchical graph clustering pooling model based on RT clustering for graph classification tasks. The proposed model demonstrates superior performance, outperforming 21 state-of-the-art competitors on all the 7 benchmark datasets.

Rhomboid Tiling for Geometric Graph Deep Learning
Yipeng Zhang"
Longlong Li
Kelin Xia
Abstract
within the graph, extracting deep structural features for var- ious graph-related tasks, such node classification, link prediction, and graph classification. The versatility of GNNs enables them to address a range of real-world challenges, including identifying user roles or group memberships in social networks (Hamilton et al., 2017), predicting molecu- lar interactions or protein-proteto interactions (Huang et al., 2020; Réau al., 2023). and predicting molecular prop- erties (Wieder et al., 2020; Shen al., 2023; Cai al., 2022).
Graph Neural Networks (GNNs) have proven ef- fective for learning from graph-structured data through their neighborhood- -based message pass- ing framework. Many hierarchical graph cluster- ing pooling methods modify this framework by introducing clustering- based strategies, enabling the construction of more expressive and powerful models. However, all of these message passing framework heavily rely on the connectivity struc- ture of graphs, limiting their ability to capture the rich geometric features inherent in geometric graphs. To address this, we propose Rhomboid Tiling (RT) clustering, novel clustering method based on the rhomboid tiling structure, which per- forms clustering by leveraging the complex geo- metric information of the data and effectively ex- tracts its higher-order geometric structures. More- over, we design RTPool, a hierarchical graph clus- tering pooling model based on RT clustering for graph classification tasks. The proposed model demonstrates superior performance, outperform- ing 21 state-of-the-art competitors on all the 7 benchmark datasets.
The message aggregation process is a fundamental com- ponent of GNNs, and the development of novel message aggregation mechanisms constitutes a critical direction for advancing GNN architectures. Traditional models such as GCN and GAT aggregate messages from node's neighbors and update the node's 's representation based on the aggre- gated information. An alternative approach involves clus- tering nodes in the original graph into clusters, followed by aggregating messages within each cluster. A coarser graph is naturally generated through this process, with each cluster represented as a new node, enabling hierarchical representation of the graph. This paradigm has led the development of models referred to as hierarchical graph clustering pooling, such as DiffPool (Ying et al., 201 8) and MinCutPool (Bianchi et al., 2020). These models have shown considerable improvements in performance over tra- ditional GNNs models. However, these clustering- based pooling methods primarily depend on the graph's 's connectiv- ity structure and often utilize learnable matrices to determine node assignments clusters, instead of leveraging prede- fined clusters derived from prior knowledge. In the case of geometric graphs, such as molecular graphs, the connec- tivity information alone may be insufficient to capture the rich geometric features inherent in the data. As a result, these methods face challenges in effectively incorporating geometric properties. limiting their ability to fully exploit the underlying structure of geometric graphs.
1. Introduction
Graph Neural Networks (GNNs) have emerged as a pow- erful framework for learning from graph-structured data, which pervasive in diverse domains such as social net- works (Guo& & Wang, 2020; Min et al., 2021), cheminformat- ics (Jiang et al., 2021; Kojima et al., 2020), and computa- tional biology (Li et al., 2021). The foundation of GNNs lies in message passing, where nodes and edges exchange and aggregate message from their neighbors. This mechanism enables GNNs to capture both local and global relationships
'Equal contribution 'Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Tech- nological University, Singapore, 637371, Singapore "School of Mathematics, Shandong University, Jinan, 250100, China. Corre- spondence to: Kelin Xia <xiakelin@ etu.c.u.sg>
We propose novel clustering method based on the rhom- boid tiling structure for geometric graph deep learning. This method is inspired by the concept of A Alpha shape, which is widely used in reconstructing 3D shapes from data, such as molecular surface reconstruction (Edelsbrunner & Mücke, 1994; Liang et al., 1998). The core idea of Alpha shapes is to partition data using spheres, naturally enabling the
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Rhomboid Tiling for Geometric Graph Deep Learning
construction of clustering methods. In fact, Alpha shapes have already been applied in clustering tasks in fields like cosmology (Gerke et al., 2012). Rhomboid tiling struc- tures generalize Alpha shapes by capturing higher-order geometric information of point clouds while maintaining a natural hierarchical structure. Each layer of this structure corresponds to a high-order Delaunay complex (see Fig- ure D), where each vertex represents a substructure of the point cloud separated by sphere from the remaining points. Consequentl,, each vertex can be regarded as a clus- ter of the point cloud. Moreover, the hierarchical nature of rhomboid tiling allows for further clustering of these clus- ters, enabling a hierarchical clustering method. This new clustering method entirely driven by the geometric struc- ture of the data and effectively uncovers complex geometric information that is difficult extract using standard graph representations. Based this method, we designed graph clustering pooling model for graph classification tasks.
updating the underlying graph into a coarsened graph where clusters act nodes. Models based on this mechanism referred to as graph clustering pooling models. DoffPool learns a differentiable cluster assignment matrix that maps nodes to clusters, jointly optimizing node representations and cluster assignments to generate a coarsened graph (Ying et al., 2018). MinCutPool, inspired by spectral clustering, performs pooling by minimizing the normalized cut of the graph while encouraging orthogonality in the cluster assign- ment matrix (Bianchi et al., 2020).
Voronoi Tessellation and Delaunay Complex Voronoi tessellation and Delaunay complex are fundamental con- cepts in computational geometry (Fortune, 2017). Voronoi tessellation partitions space into regions around set of points, such that each region consists of all points closer to its corresponding seed point than to any other. The Delau- nay complex, on the other hand, is a dual structure of the Voronoi tessellation, comprising simplices formed by con- necting points whose Voronoi cells share a common bound- ary. These two concepts have been widely applied across various domains due to their versatility and robustness in analyzing spatial relationships. For instance, in astron- omy. Voronoi tessellation and Delaunay complexes are used to identify and characterize galaxy groups in large-scale cosmic surveys (Gerke et al., 2012). In material science, Voronoi-Delaunay analysis has been applied to study voids in systems of nonspherical particles, providing insights into structural properties of disordered systems (Luchnikov et al., 1999). In protein structure analysis, it facilitates the com- putation of solvent-accessible surfaces and atomic packing densities (Richards, 1974).
Our main contributions are as follows:
1. We design a hierarchical clustering method, RT cluster- ing, based on the rhomboid tiling structure to geometrically cluster data.
2. We provide a theoretical analysis of the optimal architec- tures for RT clustering and introduce a weighting mecha- nism to represent the importance of individual points within clusters.
3. We develop a graph clustering pooling model, RTPool, based on RT clustering and validate its performance on multiple graph classification tasks. Our model outperforms 21 state-of-the-art competitors on 7 benchmark datasets from chemistry and bioinformatics.
3. Method
2. Related Work
3.1. Rhomboid Tiling
Graph Neural network and Graph Clustering Pooling Graph Neural Networks (GNNs) have emerged as power- ful tools for learning graph-structured data, with various architectures differing in their message aggregation mech- anisms. The Graph Convolutional Network (GCN) aggre- gates node information using a neighborhood averaging approach weighted by normalized adjacency matrix entries, effectively capturing local smoothness (Kipf & Welling, 2017). The Graph Attention Network (GAT), on the other hand, employs attention mechanisms to learn the importance of neighboring nodes dynamically, allowing for more flex- ible aggregation based on node relationships. (Veličković et al., 2018) The Graph Isomorphism Network (GIN) uti- lizes sum- sumebased aggregation, theoretically achieving maxi- mal expressiveness among GNNs by distinguishing different graph structures (Xu et al., 2018). Another message aggre- gation mechanism involves clustering the nodes in graph, performing message aggregation within each cluster, and
High-Order Voronoi Tessellation High-order Voronoi tessellation generalizes the concept of the classical Voronoi tessellation, providing a method to partition space based on subsets of a given point set. For a point set X C RRd, consider each subset Q C X. The Voronoi cell associated with Q, denoted as dom(Q). is defined as:
dom (Q) = (p E TR ||p==|| < - VI E E
It important to note that dom(Q) is non-empty only when the points in Q can be separated from all other points in X by sphere. That is, there must exist sphere S such that Q lies inside or on S, while X Q lies outside S. This implies that such subsets Q are, in some geometric sense, clustered together.
All the subsets Q C X containing exactly k points define a
2

---

Rhomboid Tiling for Geometric Graph Deep Learning
A
B
D
E
Geometric graph
Point Cloud
High-order Voronoi Tessellation
High-order Delaunay complex
Rhomboid Tiling
Rhomboid Tiling clustering
Figure Flowchart the Rhomboid Tiling clustering process.
example geometric graph and corresponding point cloud X. obtained by embedding the graph's vertices into R² B: 1-, 2-, and 3-order Voronoi tessellations constructed from X. C: I-, 2-, and 3-order Delaunay complexes obtained as the nerves the corresponding Voronoi tessellations. D: The Rhomhoid Tiling constructed based X. E: Illustration of I-layer Rhomboid Tiling clustering, focusing single rhomboid.
partition of the entire space Rdd expressed as:
Rhomboid Tiling To establish a natural relationship be- tween Delaunay complexes of different orders, Edelsbrunner introduced the concept of Rhomboid Tiling (Edelsbrunner & Osang, 2021). The core idea of this concept is to generalize the use of spheres for partitioning a given point set X C Rd to relate Delaunay complexes of different orders. To achieve this, we first consider a way describe the partition induced by sphere S. Let Inx (S), Onx(S), and Outx (S) denote the subsets of X that are inside, on, and outside S, respec- tively. Then each vertex Eq e Delg(X) (X) is mapped to Rd+1 using the following transformation:
gd
dom (Q).
QCX,1Q1=k
The collection of these partitions, denoted as
(X) = (Q)m(Q) Q c XQ| = k. dom (Q) # 0},
referred as the order-k Voronoi tessellation. This struc- ture enables the exploration of higher-order relationships and geometric properties of point clusters within the space.
UQ + UQ :=
Σ TEQ
x, -
E Rd+1
(1)
High-Order Delaunay Complex Similar to how the tradi- tional Delaunay complex is defined as the nerve of the clas- sical Voronoi tessellation, the high-order Delaunay complex defined the nerve of the high-order Voronoi tessellation:
It can be seen that we map the vertices of Delx to the hyperplane {[x1 :,....;:++1)) E Id+11 Ød+1 = -kj. The first d coordinates of yq are the sum of the coordinates of all points the subset Q C X. UQ is the geometric realization of eq Rd++1 Henceforth, unless otherwise specified where ambiguity arises, will not distinguish between eq and yQ-
Delg (X) = Nrv(Vorx
This means each vertex vo E (X) corresponds cell dom Q) (org(X). which is associated with the subset Q C X. A set vertices uQ1: ti2...., "Q... forms an (m-1) 1)-simplex in (elx(X) if and only if the corresponding cells dom(() (Q1). dom Q2),..... ..., dom(Q..) have a non-empty intersection.
Using the vertices from different Delg(X) complexes and an arbitrary (d -i-dimensional sphere S, a rhomboid constructed based on S is defined as:
If interpret each subset Q1, Q2 ....... ... Qm cluster, the simplex (vQ,, UQ:: ... uQ.... E Del; (X) signifies that these clusters are geometrically close. Thus, the high-order Delaunay complex (X) encodes the relationships be- tween these clusters, allowing us to analyze high-order in- teractions within the given point set.
Px (S) == conv yQ Inx (S) c Q C Inx (Sn
The collection of all such rhomboids forms a complex called the Rhomboid Tiling:
Rhomb XX) == (Px(S) is sphere TR.).
3

---

Rhomboid Tiling for Geometric Graph Deep Learning
Rhomb(X) is polyhedral complex. To ensure that this poly- hedral complex exhibits good combinatorial properties, we assume that X is in general position in IR The concept of general position is commonly used in geometry and carries different meanings in various contexts. In this paper, we define X to be in general position in 12 if no d + points in X lie on the same (d - -ddmennnsoa plane, and no d + points lie on the same (d -immenssill sphere. All the data used in this study satisfy this condition.
condition for 'i belong to the cluster CQ offering geometric explanation of the Rhomboid Tiling Clustering:
Theorem 3.1. Verfice eq E Delk, (X) belongs to the clus- ter Co if and only if 3(d 1) 1)-dimensional sphere S such that:
vQ E &Delig (X) with l22 > k1
C QQN)) QUQ'' C
Edelsbrunner proved that the intersection of Rhomb(X) with the hyperplane { .2....,, Id+1) E Rd+ Ød+1 = -k} corresponds precisely to the order-k Delaunay com- plex Delg (X) when X is in general position in R (Edels-
This theorem illustrates that the underlying idea of Rhom- boid Tiling Clustering is similar to concepts like Alpha shapes, where spheres are used to partition given point set X. These partitions are then used define geometric rela- tionships among the points, enabling clustering of the points or further clustering of the already-formed clusters. This method ensures that points within the same cluster are close in the sense of geometric proximity, while the clustering structure also encodes higher-order geometric relationships within the point set X.
brunner& & Osang, 2021). Moreover, it can be proven that Rhomb(X) n (2,,
Id+1) gd+1 Id+1 2 -k} is homotopy equivalent to (X) (Corbet et al., 2023). This indicates that if the portion of Rhomb(X) X) where the last coordinate is less than k is discarded, the remaining part can be continuously deformed into Dela (X).
To aid understanding, we provide a concrete example in the Appendix G that illustrates how to construct a rhomboid tiling from a 2D point cloud.
Next, we discuss a more specific and practical scenario: the point set X lies in Rd and is in general position. In this case, the following theorem provides guidance on how to choose appropriate values of h and 222 to cluster the points in Dela, (X) into the clusters corresponding to the points in Delg, (X).
3.2. Rhomboid Tiling Clustering (RT Clustering)
As previously mentioned, each vertex of Del, (X) can be interpreted as a cluster of the point cloud X C IRd, where the cluster contains exactly k points. This cluster arises from partitioning the point cloud using spheres, ensuring that geometrically close points are grouped into the same cluster while avoiding the formation of excessive clusters in dense regions.
Theorem 3.2. Suppose X is in general position in R3. Considering the vertices in Dely, (X) and Dels, with k1 < l2 S [X], we have:
Case 1: lo kn > 4, then any eq E Delk, (X), uq does not belong to any cluster corresponding to the vertices in Delx, (X).
This concept can be extended further. Instead of clustering the points in X form the vertices of Dela, (X), we can de- fine second-level clustering the vertex set of Del,, (X), such that the resulting clusters correspond bijectively to the vertices of Delk, (X) > kz). This second-level cluster- ing is defined through the following relation:
Case 2: 1 S k2 - ki S 2, then for any uo E Delk, (X), there exists Vqy E Delx, (X) such that UQ E Cq'-
Case 3: h2-
- k1 = 1, then for any Q C Q' with iq Dele, (X) and uqy E Dela, (X), we have uq E Cor-
eq ~ eqy
-
3o E (X) such that no, nqr E E.O,
Note: In the theorem above, there is one additional case that has not been explicilly discussed: 3 < l 1a-ki ki S 4. For this range of k2 - K1, we observe in our empirical data that there exist certain point clouds X and vertices uo E Dele, (X) such that eq does not belong to any cluster corresponding to the vertices in Deli, (X).
where Eq and vo are vertices in Del,, (X) and Dela, (X) (k2 > k.).
Using this relation, we can define the cluster associated with vertex vay as:
Cqr= = tuQ Delk, (X) eq ~ v
This theorem indicates that the step size ko k for clus- tering should be chosen within an appropriate range. From Theorem 3.2 Case 1, we know that l₂ - ki cannot exceed 4, as otherwise, none of the points will be clustered into any cluster. Additionally, as noted above, l₂ - k, should preferably not be 3 or 4, as in this case, some points may still fail to be clustered into any cluster.
where Q' is subset of X such that tir E Dela, (X). In this way, the vertices in Dele, (X) are clustered into groups that correspond bijectively to the vertices in Dels, (X). Figure shows the flowchart of rhomboid tiling clustering.
The following theorem provides a necessary and sufficient
4

---

Rhomboid Tiling for Geometric Graph Deep Learning
The ideal choice for 42 ky is or 2. According to Theorem 3.2 Case 2, in this range, all points are guaranteed be clustered into at least one cluster. And the optimal choice might be h2 - h1 1, as per Theorem 3.2 Case 3, where n will be clustered into Co. as long as Q C Q' If we sequentially cluster the original information on every point in X into (el,(X), then cluster (el2(X) into (X), and so on, eventually reaching (X), the cluster Cq' corresponding point in Delx (X) will contain all the original information from points in Q' C X.
3.3. RT Clustering-Bant -ased Model
RT Clustering-Based Basee Pooling Model (RTPool) It is a very natural idea to design clustering pooling model based RT clustering, We start by using the incident matrix 4g to represent which vertices of (X)) are contained in which maximal rhomboids:
(Tw) = -00 11, 0, otherwise.
oj E o;
Weight for RT Clustering When performing RT cluster- ing. introducing a weight for each point in a cluster Co might be beneficial choice. Although points EQ, and rQu may belong the same cluster Cor, the geometric proxim- ity or significance of the subsets Q1 and Q2 relative to Q' may differ. This motivates the introduction of a weight for each point Eq in Co to quantify such relationships.
Here, o, denotes the i-th maximal rhomboid in Rhomb(X), and vy represents the j-th vertex of Delx
To cluster the vertices of Dels, (X) onto Dele, (X), we con- sider Ch2- : (1az)² Ikk as the clustering matrix. In fact, it is not difficult to prove that (CH))a.) = (Q; Qÿ), where eq, is the i-th vertex of Delk, (X), and v/2 is the j-th ver- tex of Dele, (X). In other words, the clustering matrix Ch defined in this way not only accounts for whether eq; be- longs to the cluster Co; but also incorporates the weight N (Q,, Q2) discussed in the previous section.
We propose using (Q)QQ) := # {or is a depth-(d+1) rhom- boid| | 10, "o' E ). which counts the number of depth- (d + 1) thomboids simultaneously containing eq and uQ', as suitable weight to measure this relationship. Note that a depth-k: rhomboid refers to k-dimensional cell in Rhomb(X)) (X), where the corresponding sphere S satisfies (S) = k. A depth-(d + 1) rhomboid is the max- imal rhomboid in R))mb(X), assuming X is in general position in Rd
To construct a hierarchical pooling structure, we introduce a tunable hyperparameter Ak that specifies the step size in the order of the Delaunay complexes, i.e., we let 122 ki Ak. This means that at the (-th pooling layer (1 = 0, 1,2, ..), node features are clustered from the order- order-(1kk + 1) De- launay complex to the order-((1 + 1) + 1) Delaunay complex. Specifically, we use the matrix CiA++ ((++1)A++1 for the clustering process. Each row of (Ak+1
The following theorem explains why NQQ, Q') is an appro- priate choice for this weight:
Theorem 3.3. Suppose X is in general position in RS, and uQ eQ2 E Dele, (X), uQr E Dela, (X). If uq uQ= E Co,, then the following hold:
((++))k++1 is normal-
ized by dividing each element by the sum of the elements in that row. The resulting row-normalized matrix is denoted as O E Ruxx+++ where ny and m4+1 are the numbers of ver- tices in Del (X) and De)(+1)AR+11 (X), respectively. The normalized matrix E₁ is used as the clustering matrix for pooling from layer I to layer I + 1:
1. 1f3 S h:2 ki 54, 4, then Q1 c Q' and N()
5- -kkk-- (k2-k1).
2. 1fQ1 & Q', then N(Q1, 3 (k22 -k))
z = (9)
(2)
3. 1fQinq S Q2 na, then N(Q1, Q') S N(Q2.Q)).
where H()) is the node feature matrix at layer 1. Then we update the node features obtained after pooling using a given underlying graph G1+1 layer (1 ((+1) and a GNNs model. This process produces the node features for the (1 + 1)-th layer follows:
When 121-1Q)) is large or Q g Q', it can be inferred that Q and Q' are not geometrically closely connected. The first and second points of the theorem above indicate that, in such cases. (Q2 Q') does not exceed 2.
Furthermore, when Q1 n Ç Q2 n Q', it is evident that Q2 has a closer geometric relationship with Q' than Q does. The third point of the theorem also confirms that, in this situation, NQ11, Q'= & (Q2,, Q'). Thus, the theorem demonstrates that N(QQQ) Q') serves as a good metric for measuring the geometric relationship between Q and Q'.
((+)) = (2NN((((1))
(3)
where A!_ is the adjacency matrix of the underlying graph G And after pooling reaches the final layer L, we com- pute the final embedding Fina using the following formula:
5

---

Rhomboid Tiling for Geometric Graph Deep Learning
4. Experiments
Hunal= H (H.
4.1. Datasets
where W is learnable matrix of size f x 1, and f is the feature dimension. We use 1-layer MLP to map the final
We evaluate the performance of RTPool on graph classifi- cation tasks using seven real-world graph datasets from the commonly utilized TUDataset benchmark. Among these, three datasets represent chemical compounds, while the remaining four datasets are molecular compounds datasets.
embedding into a 2-dimensional vector, representing the classification scores for label 0 and label 1, respectively.
The underlying graph G₁ used at layer 1 for updating the node feature can be defined arbitrarily, as long as its vertices correspond one-to-one with the vertices of (el,(X). In this paper, we consider two methods for constructing Gr:
Chemical Compound Datasets The chemical compound datasets include COX-2 (Sutherland et al., 2003), BZR (Sutherland et al., 2003), and MUTAG (Debnath et al., 1991). The COX-2 dataset comprises cyclooxygenase-2 (COX-2) inhibitors tested for their ability to inhibit the human recom- binant COX-2 enzyme, with compounds classified as active or inactive. The BZR dataset includes ligands for the ben- zodiazepine receptor (BZR), with labels indicating activity or inactivity. The MUTAG dataset consists of chemical compounds categorized by their mutagenic effect on a spe- cific bacterium, with labels distinguishing mutagenic from non-mutagenic compounds.
1. The first method directly uses the I-skeleton of (X) as Gg. We refer to this type of underlying graphs as Delau- nay graphs.
2. The second method assumes that the original point cloud X is associated with given graph Geni. In our paper, Git is naturally defined as the corresponding chemical or molecular graph. The vertex set of Gi is given by the vertex set of (X), {UO) "Q........ ). where Q1, Q..... correspond to subsets of X of size I. An edge (VQ,, VQ,) exists in G2 if and only if there exist points p E Q, and q E Qj such that (p, q) is an edge in the initial graph Gini- We refer to this type of underlying graphs as generated graphs.
Molecular Compound Datasets The molecular com- pound datasets include PTC_MM. PTC.MR, PTC.FM, and PTC FR (Chen et al., 2007). These datasets classify chem- ical compounds based on their carcinogenicity in rodents: PTC_ (male mice), PTC.MR (male rats), PTC FM (female mice), and PTC_ER (female rats). Labels indicate whether compound is carcinogenic or non-carcinogenic.
3.4. Time Complexity Analysis
We theoretically analyze the time complexity of the pro- posed RTPool model. The following theorem characterizes the overall computational cost:
For all datasets, compounds are represented as graphs where vertices correspond to atoms, and edges represent chemical bonds. Hydrogen atoms are removed during preprocessing.
Theorem 3.4. Let K = Ak- L+ 1, where Ak is the step size and I is the number of pooling layers. Then the total time complexity of RTPool on a point cloud in Idd of size n is
4.2. Baselines
O [K]]
n2 - + K3n²)
Wit- Wit-TopoPool achieves state-of-the- art performance across the above datasets (Chen & Gel, 2023), making it our pri- mary baseline for comparison. To ensure a fair and consis- tent evaluation, we adopt the same seeds as Wot for a 90/10 random training/test split, guaranteeing identical training and test sets.
The first term corresponds to the cost of constructing the rhomboid tiling up to order K, and the second term ac- counts for the cumulative computation over all L. pooling layers. Here, [-] and [-] denote the floor and ceiling func- tions, respectively.
We evaluate the performance of RTPool by comparing it against 21 state-of-the-art methods across four cate- gories: (I) Graph kernel- -Baed Methods, including (1) Weis- feiler-Lehman Kernel (WL) (Shervashidze et al., 2011), (2) Weisfeiler-Lehmee Optimal Assignment Kernel (WL-OA) (Kriege et al., 2016), (3) Weismeiler-Lehmann Hash Graph Kernel (HGK-WL) (Morris et al., 2016), (4) Shortest Path Hash Graph Kernel (HGK-SP) (Morris et al., 2016), and (5) Subgraph Matching Kernel (CSM) (Kriege & Mutzel, 2012); (II) Graph Neural Network-Based Methods, in- cluding (6) Graph Convolutional Network (GCN) (Kipf
In our experiments, the step size Ak and the number of pooling layers L are both set to at most 2, so the total order K= Ak L + 1 remains a small constant. Moreover, all of the point clouds are in dimension d 3. Under this setting, the overall time complexity of RTPool simplifies to O(n²). making it suitable for practical use.
Furthermore, empirical results in Appendix F support the theoretical analysis, demonstrating that RTPool achieves competitive efficiency compared to other state-of-the graph pooling methods.
& Welling, 2017), (7) Deep Graph Convolutional Neural
6

---

Rhomboid Tiling for Geometric Graph Deep Learning
Table Performance of different models on henchmark datasets. The best performance for each dataset highlighted in bold.
Model
BZR
COX2
MUTAG
PTC.MR
PTC_MM
PTC.FM
PTC_ER
No. graphs
405
467
188
344
336
349
351
No. avg nodes
35.75
41.22
17.93
25.56
24.25
25.00
24.96
WL
86.16+0.97
79.67+1.32
85.75+1.96
57.97=0.49
67.28+0.97
64.80=0.85
67.6440.74
WL-OA
87.43+0.81
81.08+0.89
86.10=1.95
62.70=1.40
66.6011.16
66.28+1.83
67.82+5.05
HGK-WL
81.42+00.0
78.16+0.00
1..5
59.90=4.30
67.22+5.98
64.72*1.66
67.90+
HGK-SP
81.99+0.30
78.16+0.00
80.90=0.48
57.26=1.41
57.52+9.98
52.41
16.91
CSM
84.5420.65
79.78 1.04
87.29+1.25
58.2442.44
63.30+1.70
63.80=1.00
63.5149.82
GCN
79.34+2.43
76,53#1.82
80.42+2.07
62.26+4.80
67.80+4.00
62.39+0.85
69.80+4.40
DGCNN
19.40=1.71
79.85+2.64
85.83+1.66
58.5942.47
62. 10.10944.09
60.28+6.67
65.43+11.30
GIN
85.60+2.00
80.30+5.17
89.39+5.60
64.60+7.00
67.18+7.35
64.19+2.43
66.97+6.17
SAGPool
82.9544.91
79.45+2.98
76.78+2.12
69.4114.40
66.6748.57
67.65+3.72
65.71+10.69
EigenGCN
83.05+6.00
80.
79.50=0.66
N/A
N/A
N/A
N/A
MinCutPool
82.64+5.05
80.07+3.85
19.17
64.16+3.47
N/A
N/A
N/A
Top-K
19.40=1.20
80.30+4.21
67.61+3.36
64.70=6.80
67.51
65.88+4.26
66.28+3.71
DiffPool
83.93+4.41
79.66+2.64
79.22+1.02
64.85+4.30
66.00+5.33
63.00#3.40
69.80+4.40
HaarPool
83.9545.68
82.61+2.69
90.00+3.60
66.68+3.22
69.6945.10
65.5945.00
69.40+5.21
PersLay
82.16+3.18
80.90+1.00 1.00
89.80#0.90
N/A
N/A
N/A
N/A
MPR
N/A
N/A
84.00+8.60
66.36#6.55
68.6016.30
63.94+5.19
64.27+3.78
FC-V
85.61=0.59
81.01+0.88
87.31
N/A
N/A
N/A
N/A
SIN
N/A
N/A
N/A
66.80+4.56
70.55+4.79
68.68=6.80
69.80+4.36
Wit-TopoPool
87,80+2.44
87.2443.15
93.1614.11
70.57+4.43
49.12+4.45
71.71
75.00+3.51
HopPool
85.37+4.36
85.1113.74
94.74+4.76
65.71+2.85
73.59+5.27
64.15+4.62
65.71+3.71
MvPool
78.05+3.38
82.9845.24
89.64+2.43
68.5842.61
70.65+4.83
62.86+3.37
65.72+2.14
RTPool
88.29#0.98
92.76+11.00
94.74+3.33
78.86+1.57
82.94+2.20
77.72*1.14
82.2942.80
Network (DGCNN) (Zhang et al., 2018), and (8) Graph Isomorphism Network (GIN) (Xu et al., 2018); (III) Graph Pooling- Based Methods, including (9) Self-Attention Graph Pooling (SAGPool) (Lee al., 2019), (10) GCNs with Eigen Pooling (EigenGCN) (Ma et al., 2019), (11) Spec- tral Clustering Pooling (MinCutPool) (Bianchi et al., 2020), (12) TopKPooling with Graph U-Nets (Top-K) (Gao & Ji, 2019), (13) Differentiable Pooling (DiffPool) (Ying et al.,
ious datasets, we carefully selected appropriate hyperpa- rameter settings, including learning rate, dropout ratio, and number of pooling layers, detailed in the Appendix Materi- als. The number of epochs was set to 500, and each dataset was evaluated five times, with the mean value used as the final metric and the standard deviation recorded.
For the baseline results, the performance of HopPool and MyPool was obtained by running the original implementa- tions with grid search to determine the best hyperparameters. For all other baseline methods, we directly cite the results from (Chen & Gel, 2023), which also adopted grid search based on the settings specified in each original paper.
2018), (14) Haar Graph Pooling (HaarPool) (Wang et al.,
2020), (15) Multi-hop Graph pooling (HopPool) (Zhang
al., 2024), and (16) Multi-view Graph pooling (MvPool) -aased
(Ma et al., 2024); and (IV) Topology- -aased Methods, in- cluding (17) Neural Networks for Persistence Diagrams (PersLay) (Carrière et al., 2020), (18) Deep Graph Mapper (MPR) (Bodnar et al., 2021a), (19) Filtration Curves with a Random Forest (FC-V) (O' Bray et al., 2021), (20) Message Passing Simplicial Networks (SIN) (Bodnar al., 2021b), and (21) Witness complex-based topological pooling (Wit- TopoPool) (Chen & Gel, 2023).
4.4. Experiment Results
The comparison of our model with 21 baseline methods across benchmark datasets is summarized in Table 1. We also conducted an ablation study on the COX2, MUTAG, and PTC.MR datasets to analyze the impact of replacing RTPooling with trivial mean pooling in the model, the ef- fect of different GNNs models used for feature updates in the pooling layers, and the influence of the choice of the underlying graph during updates. The detailed results are presented in Table 2, 3 and 4. Furthermore, provide
4.3. Experiment Settings
In our study, the experiments were conducted on a machine equipped with NVIDIA RTX A5000 GPUs with 32GB of memory. To enhance the model's performance across var-

---

Rhomboid Tiling for Geometric Graph Deep Learning
additional experimental analyses in Appendix, including (i) hyperparameter sensitivity studies, (ii) graph regression task performance, (iii) social network dataset evaluation, and (iv) computational efficiency analysis. In all these tables. N/A indicates that the result is not available. Values are reported as mean accuracy = standard deviation.
performance of our model.
Table 2. Performance comparison of replacing RTPooling with trivial mean pooling. The best performance for cach dataset is highlighted in bold
Dataset
Pooling Method
Accuracy
Molecular and Chemical Graphs Table I presents the performance comparison among 21 baseline models on the BZR, COX-2, MUTAG,, and the four PTC datasets (PTC MR, PTC MM, PTC FM, and PTC FR) for graph classifi- cation tasks. The performance results for all other models are directly from (Chen & Gel, 2023). To ensure a fair comparison of results, we follow the same train-test split strategy used in their work, utilize the corresponding molec- ular or chemical compound graphs the initial graphs, and adopt the same node features: simple I-hot vectors encod- ing the atom types represented by the nodes. Our RTPool consistently outperforms all baseline models across these 7 datasets, with the runner-up being Wit-TopoPool in all cases. Notably, RTPool achieves an average relative im- provement of 5.94% over the uunner-up, demonstrating its effectiveness. This significant performance gain highlights the limitations of existing methods. All baseline models are constrained by their reliance on graph structures and do not fully exploit the geometric information inherent in molec- ular or compound graphs. Our RTPool model employs a rhomboid tiling structure that is sensitive to geometric in- formation. It performs well in detecting subtle geometric variations in densely packed regions of the point cloud, en- abling it to fully leverage this geometric data. As a result, our model can make full use of this geometric information and consistently outperforms all the baseline approaches.
mcan pool
78.72+0.85
COX2
max pool
78.31+0.81
RTPool
92.76=+1.00
mean pool
84.21=1.37
MUTAG
max pool
75.53+2.26
RTPool
94.74+3.33
mean pool
65.71+0.00
PTC_MR
max pool
67.43=1.40 1.0
RTPool
78.8
The results in Table 2 highlight significant advantage of RTPool over trivial mean and max pooling across all three datasets. Our model achieved relative accuracy gains of 10% 20%, underscoring the value of an advanced pooling mechanism. This substantial performance gap demonstrates RTPool's 's effectiveness in capturing both geometric and topo- logical information, establishing it as a robust graph pooling model that consistently drives superior performance across tasks.
Table 3. Performance of different GNNs models used for node fea- ture updates. The best performance for each dataset is highlighted in bold.
Dataset
GNNs Model
Accuracy
GCN
88.93+0.84
COX2
GAT
87.23+1.15
Ablation Study To assess the impact of each component in our RTPool model, we conducted comprehensive abla- tion experiments across multiple datasets, including COX2, MUTAG, and PTC MR, to gain deeper insights into their individual contributions. We designed three experiments for the ablation study: In the first experiment, we replaced the entire pooling component of our RTPool model with the commonly used mean pooling and max pooling. This experiment was conducted to validate the effectiveness of RTPool as the pooling mechanism in graph deep learning. In the second experiment, we used GCN, GAT, and GIN as the models for updating node features after pooling, as described in Equation 3. This allowed us to explore the impact of employing different GNNs architectures for fea- considered
GIN
92.76+1.90
GCN
89.4742.33
MUTAG
GAT
88.73+1.48
GIN
94.74+3.33
GCN
74.28+0.86
PTC.MR
GAT
71.43+1. .40
GIN
78.86+1.57
Table demonstrates that while the choice of GNN model for feature updates impacts performance, the differences are relatively modest. For example, on the COX2 dataset, the accuracy gap between the top-performing model (GIN) and others (GCN, GAT) is around 4%, increasing to about 5% on the MUTAG and PTC MR datasets. Notably, GIN con- sistently achieves the highest accuracy across all datasets, likely due to its expressiveness and alignment with the Weisfeiler-Lehmee graph isomorphism test, which enhances its effectiveness in graph classification tasks. These results
ture updates. Lastly, in the third experiment, two types of graphs: Delaunay graphs and generated graphs. These graphs were used as the underlying structures for updating node features at each new layer after RT clustering pooling (see equation 3). This experiment aimed to inves- tigate how the choice of the underlying graph affects the
8

---

Rhomboid Tiling for Geometric Graph Deep Learning
suggest that GIN is the optimal choice for node feature updates in the RTPool model.
Table 5. Sensitivity the hyperparameter Ak 02 k1 The best performance for each dataset is highlighted in bold.
Dataset
A
Accuracy
Table Performance comparison based on the choice of the derlying graph for feature updates. The best performance for each dataset highlighted in bold.
1
89.36+2.33
COX2
2
92.76=+1.00
86.38+1.90 3
Dataset
Underlying Graph
Accuracy
1
94.74+3.33
Delaunay
88.9440.85
MUTAG
2
39.6442.36
COX2
generated
92.76=+1.90
3
88.4242.10
Delaunay
86.32+2.58
1
16.57=1.14
MUTAG
generated
94.74+3.33
PTC.MR
2
78.86+1.57
Delaunay
71.43+0..0
3
19.71
PTC_MR
generated
78.86+1.57
5. Conclusion
Table 4 summarizes the third experiment's results, showing the impact of different underlying graph constructions on model performance. As discussed in Section 3.3, we ex- plored two approaches for constructing underlying graphs after pooling: Delaunay graphs and generated graphs. The table highlights a performance gap of up to 8% on the MU- TAG dataset, underscoring the importance of graph choice. This gap arises because RT clustering already captures ge- ometric structure, so Delaunay graphs provide little addi- tional information, as many Delaunay-connecte
This paper introduces Rhomboid Tiling (RT) clustering, hierarchical method designed to capture intricate high-order geometric information from geometric graphs. Building on this foundation, we developed RTPool, a pooling model that achieves exceptional performance across various tasks. In the future, we plan to extend RT clustering topological deep learning models.
nodes are already clustered together. Moreover, RT clustering ignores the edge semantics of the input graph, which are critical in domains like molecular modeling where chemical bonds encode key functional information. By reconstructing post- pooling graphs using the original graph's 's connectivity, we preserve high-order graph structural details and better in- tegrate both geometric and graph connectivity information. This explains why using generated graphs consistently leads to better performance.
Software and Data
The code for our proposed method is available at https: / //github. com cttpe//haangggpggggggg/ooooooooo
Acknowledgements
This work supported in part by Singapore Min- istry of Education Academic Research fund Tier 1 grant RG16/23, Tier 2 grants MOE-T2EP201 20-0010 and MOE- T2EP20221-0005 Program of China Scholarship Council (Grant No. 202306220143).
Hy perraaarreee Sensitivity Analysis Theorem 3.2 sug- gests that the difference AA = k2 k, between consecutive clustering levels should be set to or 2, as larger values may result in some nodes being left unclustered, leading to information loss during pooling.
Author Contributions
Yipeng Zhang contributed to the method design, theoretical analysis. model implementation, and writing and revision of the manuscript. Longlong Li was responsible for data preprocessing, model development, reproduction of base- line methods, and revision of the manuscript. Kelin Xia proposed the original idea, provided critical feedback on the manuseript, and supported the project with computational resources.
To validate this theoretical insight, we conduct sensitivity analysis on Ak. The results, shown in Table 5.
observe that RTPool achieves robust and competitive results when A 1 or 2, aligning well with the geometric guarantees of Theorem 3.2. contrast, Ak 3 leads to consistent performance drops across all datasets, likely due to some nodes failing to be grouped into valid clusters. We thus recommend setting Ak = 1 as the default choice, with Ak = 2 being a viable alternative that can yield even better results on some datasets. Additional sensitivity experiments on other hyperparameters are provided in Appendix C.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal

---

Rhomboid Tiling for Geometric Graph Deep Learning
consequences of work, none which feel must be specifically highlighted here.
Fortune, S. Voronoi Diagrams and Delaunay Triangulations. In Handbook of discrete and computational geometry, pp- 705-721. Chapman and Hall/CRC, 2017.
References
Gao, H. and Ji, S. Graph U-Nets. In international conference machine learning, pp.
Bianchi, F. M., Grattarola, D., and Alippi, C. Spectral clustering with graph neural networks for graph pooling. In International conference on machine learning. 874 883. PMLR, 2020.
PMLR, 2019.
Gerke, B. F., Newman, J. A., Davis, M., Coil, A. L., Cooper, M. C., Dutton, A. A., Faber, S., Guhathakurta, P., Konidaris, N., Koo, D. C., et al. The DEEP2 Galaxy Redshift Survey: The galaxy groups. The Astrophysical Journal, 751(1):50, 2012.
Bodnar, C., Cangea, C., and Liò, P. Deep Graph Mapper: Seeing Graphs Throughh the Neural Lens. Frontiers in big Data, 4:680535, 2021a.
Method catalog
Bodnar, C., Frasca, F., Wang, Y., Otter, N., Montufar, G. F., Lio, P., and Bronstein, M. Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks. In International Conference on Machine Learning, pp. 1026- 1037. PMLR, 2021b.
Guo, Z. and Wang, H. A Deep Graph Neural Network- Based Mechanism for Social Recommendations. IEEE Transactions on Industrial Informatics, 17(4):776-27833, 2020.
Hamilton, W. L., Ying. R., and Leskovee, J. Representation Learning Graphs: Methods and Applications. IEEE Data Eng. Bull., 40:52-74, 2017.
Cai, H., Zhang, H., Zhao, D., Wu, J., and Wang, L. FP-GNN: versatile deep learning architecture for enhanced molec- ular property prediction. Briefings in bioinformatics, 23 (6):bbac408, 2022.
Huang, K., Xiao, C., Glass, M., Zitnik, M., and Sun, J. SkipGNN: predicting molecular interactions with skip- graph networks. Scientific reports, 10(1):21092, 2020.
Carrière, M., Chazal, F. Ike, Y., Lacombe, T., Royer, M., and Umeda, Y. Perslay: A neural network layer for per- sistence diagrams and new graph topological signatures. In International Conference on Artificial Intelligence and Statistics, pp. 2786-776277777 7796. PMLR, 2020.
Jiang, D., Wu, Z.,, Hsieh, C.-Y., Chen, G., Liao, B., Wang, Z. Shen, C., Cao, D., Wu, J., and Hou, T. Could graph neural networks learn better molecular representation for drug discovery? comparison study of descriptor- and graph-based models. Journal of cheminformatics, 13: 1-23, 2021.
Chen, J. H., Linstead, E., Swamidass, S. J., Wang, D., and Baldi, P. Chemdb ut search and vir- tual chemical space. Bioinformatics, 23(17):2348-2351 2007.
full-text
Kipf, T. N. and Welling, M. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations, 2017.
Chen, Y. and Gel, Y. R. Topological pooling on graphs. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 37, pp. 7096-7103, 2023.
Kojima, R., Ishida, S., Ohta, M., Iwata, H., Honma, T., and Okuno, Y. kGCN: a graph-based deep learning framework for chemical structures. Journal of Cheminformatics, 12: 1-10, 2020.
Corbet, R., Kerber, M., Lesnick, M., and Osang, G. Comput- ing the multicover bifiltration. Discrete & Computational Geometry, 70(2):376 405, 2023.
Debnath, A. K., Lopez de Compadre, R. L., Debnath, G., Shusterman, A. J., and Hansch, C. Structure-activity rela- tionship of mutagenic aromatic and heteroaromatic nitro compounds, correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, (2):786-797, 1991.
Kriege, N. and Mutzel, P. Subgraph matching kemness for attributed graphs. In Proceedings of the 29th Interna- tional Coference on International Conference Machine Learning, pp. 291-298, 2012.
Kriege, N. M., Giscard, P.-.., and Wilson, R. On valid optimal assignment kernels and applications to graph classification.. Advances in neural information processing systems, 29, 2016.
Edelsbrunner, H. and Mücke, E. Three-dimensional alpha shapes. ACM Transactions On Graphics (TOG), 13(1): 43-72, 1994.
Edelsbrunner, H. and Osang, G. The Multi-Cover Persis- tence of Euclidean Balls. Discrete & Computational Geometry, 15:1296-1313 2021.
Lee, D.-T. On k-Nearest Neighbor Voronoi Diagrams the Plane. IEEE transactions on computers, 100(6):478-45) 1982.
10

---

Rhomboid Tiling for Geometric Graph Deep Learning
Lee, J., Lee, I., and Kang, J. Self-Attention Graph Pool- ing. In International conference machine learning, pp- 3734-3743, pmlr, 2019.
Shervashidze, N., Schweitzer, P., Van Leeuwen, E. J.,
Mehlhorn, K., and Borgwardt, K. M. Weisfeiler-Lchman Graph Kernels Journal of Machine Learning Research, 12(9), 2011.
Li, R., Yuan, X., Radfar, M., Marendy, P., Ni, W., O' O'Brien, T. J., and Casillas-Espinosse P. M. Graph Signal Pro- cessing, Graph Neural Network and Graph Learning on Biological Data: A Systematic Review. IEEE Reviews in Biomedical Engineering, 16: 109-135, 2021.
Sutherland, J., O'brien, L. A., and Weaver, D. F. Spline- Fitting with a Genetic Algorithm: A Method for De- veloping Classification Structure-Activity Relationships. Journal of chemical information and computer sciences, 13(6):990-11155 2003.
Liang, J., Edelsbrunner, H., Fu, P., Sudhakar, P. V., and Subramaniam, S. Analytical shape computation of macro- molecules: I. molecular area and volume through alpha shape. Proteins: Structure, Function, and Bioinformatics, 13(1):1-17, 1998.
Veličković, P., Cucurull, G., Casanova, A., Romero, A.. Liò, P., and Bengio, Y. Graph Attention Networks. In International Conference on Learning Representations, 2018.
Luchnikov, V., Medvedev, N., Oger, L., and Troadec, J.- P. Voronoi-Delaunay analysis of voids in systems of nonspherical particles. Physical review E, 59(6)7205, 1999.
Wang, Y. Li, Ma. Z., Montufar, G., Zhuang, X., and Fan, Y. Haar Graph Pooling. In International conference on machine learning, pp. 9952-9962. PMLR, 2020.
Wieder, O., Kohlbacher, S., Kuenemann, M., Garon, A., Ducrot, P., Seidel, T., and Langer, T. compact review of molecular property prediction with graph neural networks. Drug Discovery Today: Technologies, 37:1-12, 2020.
Ma, X., Fu, X., Wang, T., Zhuo, L.,, and Zou, Q- Graphadt: empowering interpretable predictions of acute dermal tox- icity with multi multi-view graph pooling and structure remap- ping. Bioinformatics, 40(7):btac438, 2024.
Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Ge- niesse, C., Pappu, A. S., Leswing, K., and Pande, V. Moleculenet: benchmark for molecular machine learn- ing. Chemical science, 9()): 2018
Ma. Y., Wang, S., Aggarwal, C. C., and Tang, J. Graph Con- volutional Networks with EigenPooling. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 723-731, 2019.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How Powerful are Graph Neural Networks? International Conference Learning Representations, 2018
Min, S., Gao, Z., Peng. J., Wang, L., Qin, K., and Fang, B. STGSN A Spatial-Temporal Graph Neural Network framework for time-evolving social networks. Beawledge-Basede Systems, 214:106746, 2021.
Ying, Z., You, J., Morris, C., Ren, X., Hamilton, W., and Leskovec, J. Hierarchical graph representation learning with differentiable pooling. Advances in neural informa- tion processing systems, 31, 2018.
Morris, C., Kriege, N. M., Kersting, K., and Mutzel, P. Faster Kernels for Graphs with Continuous Attributes via Hashing. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pp. 1095-1100. IEEE, 2016.
Zhang, J., Tian, J., Yan, P., Wu, S., Luo, H., and Yin, Multi-hop graph pooling adversarial network for cross- domain remaining useful life prediction: A distributed federated learning perspective. Reliability Engineering & System Safety, 244: 109950, 2024.
O'Bray, I.., Rieck, B., and Borgwardt, K. Filtration Curves for Graph Representation. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pp. 1267-1275, 2021.
Zhang, M., Cui, Z., Neumann, M., and Chen, Y. An end-to- end deep learning architecture for graph classification. In Proceedings of the AAAI conference on artificial intelli- gence, volume 32, 2018.
Réau, M., Renaud, N., Xue, L. C., and Bonvin, A. M.
DeepRank- :NN: a graph neural network framework to learn patterns in mooeinn-proeen interfaces. Bioinformar- ics, 39(1 (:btaccc,7 2023.
Richards, F. M. The interpretation of protein structures: total volume, group volume distributions and packing density. Journal of molecular biology, 1211):1-14, 1974.
Shen, C., Luo, J., and Xia, K. Molecular geometric deep learning. Cell reports methods, 3(11), 2023.

---

Rhomboid Tiling for Geometric Graph Deep Learning
A. Proofs of Theorems
Theorem A.I. vertex Ui E Dele, (X) belongs to the cluster Co if and only if there exists a (d - 1) d-mmennsional sphere such that:
uq E (elx,()) with k2 > k1,
Inx(S) C Qnq',
QUQ' c In (I)(S))UOXX)
Proof.
From the definition of the rhomboid associated with S, we have Inx Q Inx(S) Onx (S) and Inx (S) c
Q' C Inx(S) (5) U (n) Using these properties, it follows directly that the stated conditions sufficient and necessary
forve uQ E CQ.
Theorem A.2. Suppose X is in general position in R3. Considering the vertices in Dela, (X) and Del (X) with
h < l22 1 [X), we have:
Case 1: K2- - K1 > 4, then for any eq E Delg, (X), eq does not belong to any cluster corresponding to the vertices in Dela, (X).
Case 2: 1 E k22
k1 $ 2, then for any vq E Delki (X), there exists vor E Deekk (X) such that VQ E Cq'.
Case 3: K2 ki 1, then for any C Q' with uo Delx, (X) and vor Delx, (X), we have UQ Co.
Proof:
Case 1: 1s2 k > 4. Actually we can prove more general case: Suppose X is in general position in Rd, then for any vertex 1Q E Delk, (X) and any vertex uoy E Dele, (X) with k 2 ha + d++1 1, uq & Cqv:
From Theorem A.1, we know that QUQ' - QQQQ' C QUUQ' (S) Onx (S). When ky > h1 + d 1, we have 2 [S) that for any (d - 1) dimmennsia sphere C Rd, there can be at most + 1 vertices of X exactly on S. Therefore, no such cluster exists in this case.
QUQ' Q 2 22 ki > d + 1. This contradicts the general position assumption, which states
Case 2: 1 S k2 k < 2. Since rq Delg, (X), there exists a sphere So C IRd such that Inx C Q C Inx (S%) U Onx (So). Our goal is to find additional points .,....,Um that:
Um (1 S m S 2) and construct sphere S,, such
So C. Dm. here we use Dm to denote the ball bounded by the sphere Sm-
-
Uly..., Um lie exactly on Sm
- All other points in X Q fUi,..., um do not lie inside Sm-
If such points V1.... Um and sphere Sm can be found, we define Q' = Q J {U1, U2...., Um. Then, it follows that In (S... C QQQQ Q' and Q QUQ QU C Inx (Sm) U Onx (Sm). By Theorem A. we can conclude that eq E Cqr.
Subcase 2.1: m = 1. Let O and R denote the center and radius of Sg, respectively. For each point E X Q. calculate Euclidean distance to O. Select the point vi that is closest to O, and define S as the sphere centered at O with radius |1(O, 01)l, where 1(O v1) denotes the line segment between the points Og and U1; this notation will be used to represent the line segment between any points throughout the proof. It is straightforward to verify that S satisfies:
So C Dr.
V1 lies exactly on S1,
All other points in X - Q - {v1) do not lie inside S..
Subcase 2.2: m = 2. First, construct Uj and Sj as in the previous case. Next, for each v E X (vih consider the perpendicular bisector ij and u, and find its intersection O,, with the line passing through O and 21- Let [T(O,, vi)l denote the distance between O, and U1. Select the point bt such that [((O,, 21)l is minimized. Define S₂ as the sphere centered at O.,, with radius [?(O.,) v1)l. Then:
12

---

Rhomboid Tiling for Geometric Graph Deep Learning
U1 and U2 lie exactly on S2.
It is obvious by the construction of S2--
- S1 is contained within D2.
To demonstrate this, observe that Owg: O, and in are collinear, and the radii of the spheres S2 and S satisfy the inequality I1(O U1 Z (1(O,,)) vi)l. This ensures that, apart from the common point v1, the sphere S is entirely enclosed within S2-
- All other points in X - Q - {u), 22) do not lie inside S2.
To prove this, note that by construction, for any u E X - Q O, lies on the perpendicular bisector of 01 and v. Hence, the angle a(O,, V1, v) satisfies a(O,. v1 a(O,, v, v1) (Here a aOO,, U1, v) denotes the angle between the line segments vn O2 and u1e; this notation will be used to represent the angle between any two line segments throughout the proof). Since I1(O,, v1)l 2 |1(0,g, U1)1, we have a(O v, v1) S a(OO,, U, v1) a(O,. U1, v)= = aQ.... U1, v). Since the greater side of a triangle is opposite the greater angle, [[(O e) 2 [1(Oug, v1)l, ensuring that v does not lie inside S2. Thus, V1, 22, and S2 satisfy the required conditions.
Case 3: h2- 11 1. For any Q Q' with uQ E Delka (X) and eQr E Delkg (X), we can write Q' Q U {v). The condition eq E Delk, (X) implies that there exists a ball D2 C R containing Q, and all other points in X lie outside Dr. Similarly, eqr E Dels, (X) implies that there exists ball D2 C R containing Q U {v), and all other points in X lie outside D2. The intersection D1 n D2 is non-empty because Q C D2.
We aim to prove the existence of a ball D such that D2 n D2 C C D1 D2 and v lies on the boundary of D. Let O₁ and O2 be the centers of D2 and D2, respectively, and Tı and r2 their radii. We consider two subcases to complete the proof:
Subcase 3.1: D1 C C2. First, consider the distance (1(02, w]|: [((O2, v)] 2 I1(O,, Ot)l + TI, then the ball D, centered at O2 with radius [1(02, e)), satisfies D1 C D C D2, and v lies on the boundary of D.
If [2(O2, w)1l < 11(02: 01)l + rı, consider the farthest point P on D₁ along the line segment 1(0,, O1), such that [1(02, P)] = 1102,, 0.)1 + ri > v)). The perpendicular bisector of P and intersects ((2,, a point O.
We can prove that O lies on the line segment 1(O,, O2) because u does not lie inside D1, implying [[(0,, r) 2 r = [)], Hence, the perpendicular bisector cannot intersect 1(O,, P) outside P, and O must lie on [(O), O2).
Let D be the ball centered at O with radius (1,O, r) [1(O,)) By construction, lies on the boundary of D, and D contains Dj because O E 1(0, P) and [1(O,, P)] ri- Furthermore, since 0 E I(O2, P) and [1(O2, P)] S r2, we have D C D2. Thus, in this subcase, we can always find a ball D such that D1 n D2 D1 DCCCCCD D2 = D1 U D2. and v lies on the boundary of D.
Subcase 3.2: Di & Dz. We first prove the following lemma:
Lemma. For two intersecting balls Dj and D2 with centers O and O2, respectively, let C' be the circle formed by the intersection of their boundaries. For any point O3 on the line segment 1(O), O2), the ball D centered at O3 with radius equal to the distance from O3 to any point / E C satisfies D2 n D2 c D C D1 U D2.
To prove this lemma, consider the plane 1I containing l' and the line segment ((O), O2). and establish a 3D coordinate system on II: - Let the projection of P onto 1(O,, O2) be the origin O(0, 0, 0). Take the direction of O2 as the x-axis, the direction of OP as the y-axis, and the direction orthogonal to II as the 2 a-axis Let the coordinates of O and Og be (æ1, 0, 0) and (x22, 0, 0), respectively, and let P be at (0, h 0). Then, r = of + 122 and r = x² + h?? A point (z. y, 2) lies in D2 if and only if: (x (x- + 1 +2 S
which simplifies to:
x² 2x x + 132 + 2² < R2.
(1)
Similarly, a point lies in D2 if and only if:
x - 2xyx +
2 +
(2)
A point lies in D and only if:
n22 2(121 + (1 - -))x)) + 52 + 2² $12,
(3)
13

---

Rhomboid Tiling for Geometric Graph Deep Learning
where O3(33, 0, 0) with v33 = Lxg (1 1)ar is the center of D. By taking (1) xt + (2) x(1 - 1). we obtain (3). This implies Dj n D2 C D.
Furthermore, the third inequality is equivalent to:
1(x² - 2x, x + 1/2 + + + ()=1)(x² 2x2x + +²²+²²) S 1.2.
Now, suppose that the third inequality holds while neither the first nor the second inequalities is satisfied. Then we have: 1²= = + (1 - 1)h² < Ux² 1x + y² + =²) (1 ()(2² - 2x2x + 5²² + =²) S h?
which is a contradiction. This contradiction implies that if the third inequality holds, at least one of the first second inequalities must also hold. This ensures that D D1 U D2. And we finish the proof of the lemma.
Returning to Subcase 3.2, consider a point P E C' on the intersection of D2 and D2. Let H be the perpendicular bisector of and v. Since [1(O2, o)] I r2 = 11(O,, P)], , H intersects 1(O2, P). Since (1(Oz, e) 2 r = [1(O1, H does not intersect 1(O1, P) internally.
By the geometric property that a line intersecting a triangle must intersect two sides and the fact that H does not intersect I(O,, P). intersects the triangle O at a point O on 1(O,, O2). Let D be the ball centered at with radius [[[O, P)1 = [t(O, v)]. By construction, v lies on the boundary D, and the lemma ensures D2 n nD2 C D C D D2.
In conclusion, we have proven the existence of ball D such that v lies on the boundary of D, i..., v E (n) where 5 = OD. Furthermore, we have Q C D2 n D2 C D C D2 U D2- This implies that Q = In In)((S), because the interiors of D1 and D2 do not contain any points of X other than those in Q U {v}. By Theorem A. it follows that eq E Ca'
Theorem A.3. Suppose X is in general position in RS, and uQ UQ2 Dela, (X), var E Dele, (X). , ff UQ2 E Co then the following hold:
1. 3 S K2 - k1 S 4, then Q1 C. Q' and (Q1 Q') < (k2 k1).
2. 1fQ1 & Q', then (Q1, Q3) S 3 (k2 - k1).
3. IfQi n Q' ç Q2 n Q,, then N N(Q1, (") S N Q').
Proof: Let 11 = 1Q 1Q' IQ' n nQi and n2 = IQ'1 - IQ' n Q1 Then we have:
-n1 2 0, n2 2
-12 11 l22 ki < 4, because n2 - = =Q'1 - 1Q k22 -i, and from Case I of Theorem A.2, we know
k2 k1 < 4,
12 + n1 < 4, because n2 + n1 = (QQa + 1Q- 1Q' nQ.)) -10 1 IQ' n Q1l- From Theorem A.1 1Q' 12' n2l S (S) - [Inx (S) = [Onx S 4 for
and the fact that VQ2 E C(Q'), we have IQ' Q'UQ1 - some sphere C R
From these facts, we can enumerate all possible values for the pair (n2, n): ((4,0), (3. (3,0), (3. 1), (2.0), (2, (1,0))
s S 4, then Q1 C Q' and N(Q1, Q') < 5 (k2 k1).
First, consider the case k- - kj = 4. In this scenario, n2 n1 = 4. From the above analysis, we know (n22 n1) = (4, 0),
which implies |Q - QQ' n Q 0, i.e., Q1 C Q'. Therefore, uq, and uq can only lie in the depth-4 rhomboid (S), where In, (S) = Q: and Onx (S) Q' Q1. meaning N NQ1 Q') S 1.
Next, consider the case h/ - k1 = 3. Similarly, we have n1) = (3, 0), which implies Q1 C Q' and the fact that the minimal rhomboid (X) containing eq, and EQ' could be either a depth-3 or depth-4 rhomboid with (Q'- - ()) U (Q1 Q') c On (S). If (X) is a depth-4 rhomboid, then N( Q') S 1. If (x(X) is a depth-3 rhomboid, it can serve as facet for at most two depth-4 rhomboids. Therefore, N(1, (()]Q')= s 2.
If Q1 Ø Q', then N(Q1, Q') S 3 (l:2 kj).
14

---

Rhomboid Tiling for Geometric Graph Deep Learning
From the above analysis. Q1 g Q' implies k2 k1 3 and n1 |Qil -Q' n Qil >
First, consider the case
l2 1 Here, T22 n1 2, so (22, n1) (3, In this case, "Qq and uor can only lie in the depth-4 rhomboid px (S) where (S) = Qi n Q' and Onx(5) (Q' (Q: Q'). This means (QQ1, S 1.
(Q)
Now, consider the case 42 1 1. Similarly, n1) (2, 1). The minimal rhomboid (s(X) containing Uo, and eq'' can be either depth-3 or depth-4 rhomboid. Thus, NQI,, Q*) S 2.
If Q1 0 Q' _ Q2 n Q', then N(Q1, Q²) _ N2Q2. Q').
Since [Q1 = [22l = k1, the condition Q1 n Q' _ Q2 n Q' implies Qi & Q'. From the above analysis, k2 hn 3. and (ng, n1) = (3, 1) or (2, Let - and n/2 1Q'l=1''nQ2) The condition Qi & Q2nQ'
implies n/ = [Q2l IQ' n @21 < [Q:l [Q' n nQill nn = 1, which forces n' = 0. Hence, Q2 C C
For any rhomboid px (5) containing tiQ and uq', we have (S) C Q1 n & Q2 n Q', and Q2 U Q' = Q' c
QiUQ'S C (S) (0)0()x(xx).)))) Therefore, px also contains UQ2- This implies NQ1,, Q') S (Q2,,01)
Theorem AA.. Let K = Âk L + 1, where Ak is the step size and L is the number of pooling layers. Then the total time complexity of RTPool point cloud in Ra of size is
0 ((K) 1 [
n + + k
The first term corresponds to the cost of constructing the rhomboid tiling up to order K, and the second term accounts for the cumulative computation over all L pooling layers. Here, L-1 and [-] denote the floor and ceiling functions, respectively.
Proof: The time complexity analysis of RTPool consists of two components: (1) constructing the rhomboid tiling structure from the input point cloud, and (2) performing graph pooling based on the rhomboid tiling.
1. Rhomboid Tiling Construction. According to Proposition 5 and Remark 8 in (Corbet et al., 2023), the number of rhomboid cells in the tiling up to order K for a point cloud of size n C IR is bounded by
o
(K
nl nl(:11 1).
Furthermore, from (Corbet et al., 2023), the time complexity of constructing a single order-k rhomboid cell is O(k). Therefore, the total time complexity for generating the rhomboid tiling up to order K is
o (K. OK K 1 + =0 (K 1+1 In
2. Graph Pooling via Rhomboid Tiling, According to (Lee, 1982), the number of regions in the order-k Voronoi diagram in RR3 is bounded by (n - k:), and thus the number of vertices in the corresponding order-k Delaunay complex is also (n-2(nn 1:)).
This implies that the clustering matrix constructed from the rhomboid tiling at order-k has size and the associated node feature matrix has size O (n- - k)) x O()). The pooling process for each layer consists of two steps:
Matrix multiplication between the clustering matrix and the node feature matrix, with time complexity O(k47²).
Applying GIN layer to update the features, which has time complexity O(k² k)), assuming the graph remains sparse.
As the matrix multiplication dominates, the overall complexity per layer is O(k*n²). Summing all orders up to K, the total pooling cost becomes
O(K
n²)
Combining both parts, the total time complexity of RTPool is
0 K
00KK
113 ml
411
+ kzn²)
This completes the proof.
15

---

Rhomboid Tiling for Geometric Graph Deep Learning
B. Hlppepparameter Settings
The hyperparameters of our RTPool model follow a default configuration, as shown Table 6. For different datasets, specific hyperparameters were adjusted optimize performance, with the detailed settings presented Table
Table 6. Default Hyperparameter Settings for RTPool
batch size
#epochs
LR
#poo ling layers
Ak:
final dropout
weight decay
16
500
0.001
2
0.5
0.0001
The hyperparameters in Table define the key settings for the RTPool model. The batch si specifies the number of samples processed simultaneously during training, while #epochs represents the total number of complete passes through the training dataset. The LR (learning rate) controls the step size during the optimization process. The #poo ling layers denotes the number of pooling layers in the RTPool model, determining the hierarchical depth of the pooling process. Ak is the step size the pooling process. The final dropout rate helps prevent overfitting by randomly zeroing out fraction of neurons in the final layer. Lastly, the weight decay regularization term reduces the magnitude of model weights to improve generalization.
Table Hyperparameter Settings for Different Datasets
Dataset
#poo1 ing
layers
LR
final dropout
Ak
Others
COX2
0.001
0.5
2
Default
BZR
0.001
0.5
1
Default
PTC.MR
0.0002
0.3
2
Default
PTC.MM
0.0002
0.3
1
Default
PTC FR
0.0002
0.3
Default
PTC.FM
2
0.0002
0.3
Default
MUTAG
0.001
0.5
Default
In experiments, only tuned three hyperparameters: #pooling layers, LR, and final drepout. For hyperparameter sensitivity analysis, predefined range of candidate values and performed grid search to identify the best-performing configuration each dataset. Specifically, the optimal setting for each dataset was selected based on the validation performance, while other hyperparameters were kept at their default values.
Table 8. Hyperparameter sensitivity analysis. Best performance is highlighted in bold.
(a) Learning rate sensitivity
(b) #pooling layers sensitivity
(c) final dropout sensitivity
Dataset
LR
Accuracy
Dataset
#pooling Accuracy layers
Dataset
final dropout
Accuracy
0,0002
87.23+1.50
0.0005
87.66+0.95
1
92.76+1.90
0.4
18.51
COX2
COX2
0.001
92.76+1.90
2
88.50+1.17
COX2
0.5
92.76+1.90
0,002
88.93+1.78
0.6
88.93+1.78
1
94.74+3.33
MUTAG
0,0002
89.47=0.00
2
90.52+2.35
0.4
92.63+2.88
0.0005
91.57+2.88
MUTAG
0.5
94.74+3.33
MUTAG
1
78.86+1.57
0.001
94.7443.33
PTC_MR
0.6
93.69+2.36
2
72.57+2.56
0.002
93.68+2.10
0.2
14.86+1.27
0,0001
73.7242.39
PTC.MR
0.3
78.86+1.57
0,0002
7..8621.57
0.4
75.43+1.56
PTC
0.0005
72.57+1.44 4.0
0.001
10.2
16

---

Rhomboid Tiling for Geometric Graph Deep Learning
C. Hyperparameter Sensitivity Analysis
To evaluate the robustness our method, we conducted a sensitivity analysis on four hyperparameters: the number of pooling layers (#pooling layers), learning rate (LR), final dropout ratio (final dropout), and the step size Åk in the pooling process. While our main experiments only tuned the first three, we later performed additional evaluations of Ak on three datasets (COX2, MUTAG, and PTC.MR) to further investigate its impact.
The sensitivity analysis of the step size A 122 k1 is presented in the main text (see Table 5) along with detailed discussion of its impact on model performance. Table 8 reports the sensitivity results for the other three hyperparameters across the same datasets.
In general, we find that our model RTPool relatively stable across range of values, but optimal performance does depend on careful tuning.
D. RTPool for Graph Regresssion Tasks
We demonstrate that RTPool's applicability extends beyond graph classification to regression tasks, owing to its geometry- preserving pooling mechanism. By explicitly incorporating geometric information during pooling, RTPool generates graph-level representations that robustly capture essential structural features, making them universally applicable across diverse learning objectives.
To validate this claim, evaluate RTPool on three commonly used molecular property regression benchmarks(War et al., 2018) under identical experimental conditions our main experiments. All models, including baselines, were tuned via grid search to ensure fair comparison. Table 9 presents the root mean square error (RMSE) comparisons with seven state-of-the-art graph pooling methods:
Table Performance comparison (RMSE) molecular property regression datasets under standardized experimental conditions. Lower values indicate better performance. Best results are highlighted in bold.
Model
Esol
FreeSolv
Lipo
No. graphs
1128
642
4200
No. avg nodes
26
18
49
MinCutPool
2.1913+0.0374
4.0111#0.0170
StructPool
2.1749#0.0411
4.0077+0.0150
1.342240. 1264
DifiPool
3.769940.2033
5,2877+0.2044
2.7431
HaarPool
2.1035+0.0340
3.889240.00 0098
1.3361#0.0627
Wit-TopoPool
1.8783+0.
4.2159+0.08
Hop-Pool
2.08610
10030=0009900
1.3725=0.0738
My-Pool
2.5691
4.0627#0.106 1048
1.3746#0.0682
RTPool 2.0195+0.5318
3.666620.2112
1.0789+0.0496
As shown in the table, RTPool achieves the best or near-best performance across all three datasets, demonstrating its effectiveness in graph regression tasks compared to other pooling baselines.
E. RTPool on Social Network Datasets
To extend the applicability of our RTPool model, we further explore its performance on non-geometric spaphhs-peeificallyy. social network datasets such as IMDB-BINARY and IMDB-MULTI. These graphs lack explicit node features or spatial coordinates; thus, adapt RTPool, a crucial step is embedding the nodes into Euclidean space based on the graph structure alone.
Spectral Embedding via Graph Laplacian. Given unweighted, undirected graph G EV, we construct the normalized graph Laplacian L = - 1-----D1- A0-1/2AA-11 where A is the adjacency matrix and D is the diagonal degree matrix. We then compute the eigen-decomposition of L and select the eigenvectors corresponding to the three smallest non-zero eigenvalues (excluding the trivial eigenvector for eigenvalue zero). These three cigenvectors form a spectral embedding that maps each node a point in 3R3 capturing global structural information through diffusion geometry. This embedding serves
17

---

Rhomboid Tiling for Geometric Graph Deep Learning
surrogate spatial coordinate input for RTPool, enabling it to perform pooling in non-geometric graphs.
We applied this Laplacian based spectral embedding approach to the IMDB-BINARY and IMDB-MULTI datasets, which contain only graph connectivity information. We compare our model with 20 baselines, including classical graph kernels (e.g., WL, HGK) and pooling-base based GNNs (e.g., DifiPool, SAGPool, Wit-TopoPool), with most results cited from (Chen & Gel, 2023). For Hop-Pool(Zhang et al., 2024) and Mv-Pool(MMa et al., 2024), which were not reported in that benchmark, we implemented them based on their original papers and tuned hyperparameters via grid search to ensure fair comparison. The performance summarized in Table 10.
Table 10. Comparison classification accuracy (%) on social network datasets.
Model
IMDB-BINARY
IMDB-MULTI
No. graphs
1000
1500
No. avg nodes
19.77
13.00
HGK-SP
73.34+0.47
51.58+0.42
HGK-WL
72.75+1.02
60.73+0.63
WL
71.15+0.47
50.25 72
WL-OA
74.01=0.66
49.95=0.46
DGCNN
70.00=0.90
47.80=0.90
GCN
66.53+2.33
48.93+0.88
GIN
75.10=5.10
52.30+2.80
Top-K
73.1744.84 84
48.80#3.19
MinCutPool
70.77+4.89
49.00=2.83
DifiPool
68.60+3.10
45.70=3.40
EigenGCN
70.40#1.30
47.20#3.00
SAGPool
74.87+4.09
49.33+4.90
HaarPool
73.29+3.44 3.0
49.98+5.70
PersLay
71,20+0.70
48.80+0.60
FC-V
73.84+0.36
46.80+0.37
MPR
73. 53.80+4.50
50.90=2.50
SIN
75.60#3.20 20
52.50
Wit-TopoPood
78.40+1.50
53.33+2.47
Hop-Pool
68.04+2.04
49.33=5.09
My-Pool
69.75+3.61
51.67+0.74
RTPool
73.06#3.84
53.33+1.26
As shown in Table 10, RTPool achieves competitive results across both datasets. On IMDE-MULTI, RTPool matches the cest-performing baseline (Wit-TopoPool) with an accuracy of 53.33%. Notably, this is achieved despite the lack of native geometric information, highlighting the effectiveness of using spectral embeddings generalize RTPool abstract graph domains like social networks.
F. Empirical Model Efficiency
To further evaluate the efficiency of RTPool, we compare with several representative clustering-based pooling methods under controlled training conditions. Specifically, all models are trained for only 100 epochs per run (rather than the default 500), and each experiment is repeated five times to report average performance and runtime. This setup helps assess how quickly each model converges high-quality results.
Early-Stage Performance. Table 1l shows the classification performance of different pooling methods after only 100 training epochs. Despite the reduced training time, RTPool already achieves outstanding accuracy on most datasets, often surpassing or closely matching state-of of-the-at models that typically require longer training. This demonstrates the rapid convergence and high early-stage expressiveness of our model.
18

---

Rhomboid Tiling for Geometric Graph Deep Learning
Table 11, Accuracy (mean std) after only 100 training epochs. Fach model trained times. RTPool shows strong early-stage
performance compared to other methods.
Model
BZR
COX2
MUTAG
PTC MR
PTC MM
PTC FM
PTC FR
MinCutPool
76.47+2.32
79.86+2.47
69.4742.11
66.86+2.91
72.94
56.74+5.63
62.86+1.
StructPool
75.63+1.00 .04
78.72+1.79
70.53+2.58
65.74+2.68
72.90+1.18
57.71+7.32
62.29+2. 14
DiffPool
78.54+0.98
77.93+3.18
73.68+3.33
69.14+2.80
67.06+2.20
68.57+3.61
68.57+1881
HaarPool
78.05+0.00
80.6424.58
68.42400.8
62.29+4.20
64.7113.72
61.1426.66
65.67+2.25
Wit-TopoPool
80.98+2.39
10.43+1.59
85.3242.58
71.84+1.14
72.82+4.71
68.56+4.84
68.57+4.04
Hop-Pool
78.05+1.39
80.00#1.70
87.5614.41
61.71+2.91
70.59+0.78
58.29+1.40
63.43+1.14
Mv-Pool
75.60+1.98
19.68+1.27
73.68+10.53
64.57+4.64
68.24
57.14+0.00
65.71+1.77
RTPool
84.39+1.19
85.96+1.04
83.1645.16
72.86+3.65
72.9413.43
68.8648.59
67.71
Runtime Comparison. Table 12 presents the total training time (in seconds) under the same 100-epoch setup. For RTPool, we additionally break down the cost into the one-time tiling structure construction and model training time. While some methods incur large computation costs (e.g.. Mv-Pool, Wit-TopoPool), RTPool maintains reasonable runtime and even outperforms most baselines in both speed and accuracy.
Table Runtime seconds) over trials (each with 100 epochs). For RTPool, both tiling construction time and training time are reported.
Model
BZR
COX2
MUTAG
PTC.MR
PTC.MM
PTC. FM
PTC FR
MinCutPool
2297.74
2554.96
1999.89
2016.22
2482.84
2470.79
2355.13
StructPool
1602.96
1647.23
1387.76
1412.16
1663.12
1623.40
1578.65
DiffPool
2507.53
2813.80
2144.75
2235.34
2637.06
2621.80
2529.79
HaarPool
3238.15
2666.93
1787.79
1412.01
1407.39
2075.04
2022.91
Wit-TopoPool
4512.64
4904.08
7475.70
7390.13
7332.05
7370.51
7357.56
Hop-Pool
1483.80
1420.63
1190.00
1171.09
1450.05
1421.54
1355.92
Mv-Pool
11244.74
9137.48
5828.78
8935.74
8327.48
8326.58
8907.54
RTPool (constructor)
1616.06
2356.41
189.59
341.39
321.39
331.57
360.00
RTPool (training)
1117.62
1053.07
1041.59
673.77
1268.01
1708.35
306.10
These results highlight RTPool's ' fast convergence and favorable runtime-accuracy trade-off, making it practical and scalable choice for large-scale or resource-conssrrained applications.
G. Illustrative Examples
To provide more intuitive understanding of RTpool and the rhomboid tiling mechanism, include two illustrative examples in this appendix.
Pooled graph at level
Pooled graph at level
Pooled graph level
Molecular graph
Original graph
Figure 2. Visualization of the hicrarchical clustering process performed by RTpool on the molecular graph of Formaldehyde. The original molecular structure shown the left, followed by three successive clustering layers. Each cluster center (colored cirele) is positioned based on the geometric realization of rhomboid tiling, and connected to its members by dashed lines.
19

---

Rhomboid Tiling for Geometric Graph Deep Learning
Figure demonstrates how RTpool performs hierarchical clustering the molecular graph of Formaldehyde. The graph is progressively pooled through multiple layers, with nodes being aggregated into clusters each level. The position of each cluster center is determined by the rhomboid tiling structure, providing geometric guidance for the pooling process. This example reveals RTpool's s strong locality-aware awareness, as it consistently merges spatially adjacent nodes. In this example, we observe that RTToool tends to group geometrically close nodes into the same cluster, phenomenon particularly evident from pooling layer to layer 2.
A
C
D
51
Molecule
52
P1
B
S3
P2
Rhomboid Tiling
15
v4
Point cloud
S4
Circum Circle
Rhomboid
Figure An illustrative example of generating rhomboid tiling from point cloud. A: Molecular graph of Formaldehyde. B: Point cloud obtained by embedding the molecular graph into IR2 C: Minimal circumcircles corresponding to each local point cluster in the point cloud. Rhomboids associated with the circumcircles. E: Rhomboid tiling structure of Formaldehyde formed by the union of all rhomboids.
Figure illustrates the process of constructing rhomboid tiling from a 2D point cloud X derived from the molecular graph of Formaldehyde. We begin by identifying minimal circumcircles that pass through exactly three points. These circles are used define the rhomboids that make up the tiling.
Taking such minimal circumeirele S example, suppose In (S,) 0 and Onx (S,) U1 U2 U.. With (a,, b;) denoting the coordinates of e; the associated rhomboid is formed from the convex hull of set of lifted points:
Px (Si) == conv(uq (Si) C C (Si) Un
Σ x, k
VQ
FEQ
In this case, we generate such points corresponding to all subsets of (wi, U2, v3). at levels ranging from 3:
yg = (0, 0, 0) (origin, at level 0),
20

---

Rhomboid Tiling for Geometric Graph Deep Learning
V(e)) (a1,b1, -1), M(v2) (ag, b2, 1}, M[v3) (ag, b3, -1) (three points at level 1),
[e = (ar + + bi + b2: -2), M/v..05) (ar + 0z bi + ba. -2), 3(veaes) (a2 + ag, b2 + bs, 22) (three points at level 2),
M(o1,22,0) (a1 + 02 + 0g, b1 by + by, -3) (one point at level 3).
The convex hull of these lifted points defines a rhomboid in R As shown in the figure, four such rhomboids constructed from four distinct minimal circumeircles. Their union forms the complete rhomboid tiling structure for the Formaldehyde point cloud.
21


Reviews:
[{"review_id": "Hy5cczx8tP", "reviewer": "Reviewer_FBWn", "summary": "The paper introduces a novel hierarchical clustering method—Rhomboid Tiling (RT) clustering—for geometric graph deep learning. Unlike traditional clustering-based pooling methods that mainly rely on graph connectivity, RT clustering leverages high-order geometric structures derived from concepts such as alpha shapes, higher-order Voronoi tessellations, and Delaunay complexes. Using these ideas, the authors design RTPool, a graph pooling model that constructs hierarchical representations by clustering vertices using the rhomboid tiling structure. The model is validated on seven benchmark datasets (including chemical and molecular graphs), where it outperforms 19 state-of-the-art competitors. The paper also provides theoretical analysis, including necessary and sufficient conditions for cluster membership and a weighting mechanism based on the frequency of shared high-dimensional rhomboids.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thoughtful and constructive comments. Below, we provide detailed responses to each of the points raised.\n\n**1. Hyperparameter sensitivity**\n\nTo address this concern, we have conducted a detailed sensitivity analysis by varying the value of $k_2-k_1$. The results are summarized in **Table 1** below:\n\n**Table: Sensitivity to $k_2-k_1$.**\n\n|Dataset|$k_2-k_1$| Accuracy         |\n|------|---|------|\n| COX2  | 1  | 89.36 ± 2.33     |\n|| 2 | **92.76 ± 1.90** |\n|| 3 | 86.38 ± 1.90     |\n| MUTAG     | 1   | **94.74 ± 3.33** |\n|           | 2             | 89.64 ± 2.36     |\n|           | 3             | 88.42 ± 2.10     |\n| PTC\\_MR   | 1             | 76.57 ± 1.14     |\n|           | 2             | **78.86 ± 1.57** |\n|    | 3             | 69.71 ± 1.56     |\n\nFrom the results above, we observe that RTPool performs robustly when $k_2-k_1=1$ or $2$, and shows degraded performance when $k_2-k_1=3$. This aligns with our theoretical analysis, which suggests that setting $k_2-k_1\\geq 3$ leads to a loss of node feature information during the pooling process, thus hurting performance. Therefore, we recommend choosing $k_2-k_1=1$ or $2$ in practice. While our original model used $k_2-k_1=1$ by default, these experiments suggest that using $k_2-k_1=2$ can yield better results on some datasets.\n\n**2. RTPool for Graph Regression Tasks**\n\n We believe that our model is not only suitable for graph classification tasks, but also for **graph regression**. This is because the RTPool process incorporates **geometric information** into the pooling operation, ensuring that the final graph-level representation captures essential geometric structures. As a result, this learned representation can benefit a variety of downstream tasks—regardless of whether the objective is classification or regression.\n\nTo support this claim, we have conducted additional experiments on regression datasets. The results, in terms of **RMSE**, are reported in the following table:\n\n**Table: RMSE comparison on graph regression datasets**\n\n| Model| Esol | FreeSolv           | Lipo               |\n|------|---------|---------|--------|\n| MinCutPool    | 2.1913 ± 0.0374     | 4.0111 ± 0.0170     | 1.3481 ± 0.0224     |\n| StructPool    | 2.1749 ± 0.0411     | 4.0077 ± 0.0150     | 1.3422 ± 0.1264     |\n| DiffPool      | 3.7699 ± 0.2035     | 5.2877 ± 0.2049     | 2.7431 ± 0.0753     |\n| HaarPool      | 2.1035 ± 0.0340     | 3.8892 ± 0.0098     | 1.3361 ± 0.0627     |\n| Wit-TopoPool  | **1.8783 ± 0.1628** | 4.2159 ± 0.0816     | 1.0916 ± 0.5007     |\n| Hop-Pool      | 2.4831 ± 0.0760     | 4.0030 ± 0.0940     | 1.3725 ± 0.0738     |\n| Mv-Pool       | 2.5691 ± 0.0484     | 4.0627 ± 0.1048     | 1.3746 ± 0.0682     |\n| **RTPool**    | 2.0195 ± 0.5318     | **3.6666 ± 0.2112** | **1.0789 ± 0.0496** |\n\nAs shown in the table, **RTPool achieves the best or near-best performance across all three datasets**, demonstrating its effectiveness in graph regression tasks compared to other pooling baselines.\n\n**3. Computational Complexity of the RT Clustering**\n\nTheoretically, the construction of the Rhomboid Tiling structure has complexity bounds $O\\left(n^{\\left\\lfloor \\frac{d+1}{2} \\right\\rfloor}\\right)$, and the associated pooling operation in RTPool has complexity bounds $O(n^2)$. Here $n$ is the number of nodes, and $d$ is the dimenstion of space in which the graph is embedded. We have also conducted experiments to empirically assess the efficiency of RTPool compared to other pooling baselines.\n\nDue to space constraints, we kindly refer the reviewer to our detailed response to **Reviewer kfVb**, where we provide both the **theoretical proof** and **empirical runtime results**\n\n**4. RTPool for Social Network Graphs**\n\nTo adapt RTPool to non-geometric graphs such as social networks, one key step is to find an appropriate way to embed the graph nodes into $\\mathbb{R}^3$. A feasible approach is to compute the **graph Laplacian** and use the combination of eigenvectors corresponding to the **three smallest non-zero eigenvalues** as coordinates for each node. \n\nBased on this idea, we applied RTPool to social network datasets which contain only graph connectivity. The results are shown below:\n\n**Table: Accuracy (\\%) on social network datasets (mean ± std).**\n\n| Model| IMDB-BINARY | IMDB-MULTI  |\n|--------|------|------|\n| MinCutPool    | 70.77 ± 4.89       | 49.00 ± 2.83        |\n| DiffPool      | 68.60 ± 3.10       | 45.70 ± 3.40        |\n| SAGPool       | 74.87 ± 4.09       | 49.33 ± 4.90        |\n| HaarPool      | 73.29 ± 3.40       | 49.98 ± 5.70        |\n| Wit-TopoPool  | **78.40 ± 1.50**   | **53.33 ± 2.47**    |\n| Hop-Pool      | 68.04 ± 2.04       | 49.33 ± 5.09        |\n| Mv-Pool       | 69.75 ± 3.61       | 51.67 ± 0.74        |\n| **RTPool**     | 73.06 ± 3.84       | **53.33 ± 1.26**    |\n\nAs shown above, RTPool achieves competitive performance despite lacking enough geometric information", "claims_and_evidence": "The main claims—that RT clustering can capture higher-order geometric information and that RTPool yields superior performance—are backed by both rigorous theoretical derivations and extensive empirical evaluations. The experiments compare RTPool against a broad spectrum of baselines using standard benchmarks and include ablation studies to isolate the contribution of individual components. The theoretical claims are supported by proofs (presented in the supplementary material) that derive conditions under which clusters form and justify the weight definition, though these proofs might benefit from further independent validation.", "methods_and_evaluation_criteria": "The proposed method is well-motivated: it addresses the limitations of connectivity-only approaches in graph pooling by incorporating geometric information. The derivation of RT clustering from higher-order Voronoi and Delaunay structures is conceptually sound and aligns with existing computational geometry ideas. In terms of evaluation, the use of established benchmark datasets (e.g., MUTAG, PTC variants) and comparisons with a wide range of baselines (from graph kernel methods to modern GNN pooling techniques) are appropriate for the problem setting.", "theoretical_claims": "The paper includes proofs for its main theoretical results, such as Theorem 3.1 (characterizing when a vertex belongs to a cluster) and Theorem 3.2 (guiding the choice of clustering parameters k₁ and k₂). These proofs appear detailed and correct on inspection, though their full validity would benefit from additional scrutiny by experts in computational geometry. The weighting mechanism based on counting shared depth-(d+1) rhomboids is also justified through a theorem that connects it to geometric proximity.", "experimental_designs_or_analyses": "The experimental design is solid. The authors test their model on multiple datasets with different characteristics (chemical vs. molecular graphs) and conduct an ablation study to assess the impact of replacing RTPool with trivial pooling, varying the choice of GNN architectures for feature updates, and selecting different underlying graph constructions. The consistent performance gains reported and the detailed breakdown of results suggest that the experimental analysis is sound and that the improvements are not merely due to incidental factors.", "relation_to_broader_scientific_literature": "The paper builds on several important threads in the literature. It extends ideas from traditional graph clustering pooling methods (e.g., DiffPool, MinCutPool) by incorporating geometric insights from alpha shapes, Voronoi tessellations, and Delaunay complexes. This connection to classical computational geometry distinguishes it from methods that rely solely on graph connectivity. The work also relates to recent advances in topological and geometric deep learning, positioning its contributions within both the graph neural network and computational geometry communities.", "essential_references_not_discussed": "The paper cites a wide range of relevant works in topological pooling or geometric deep learning have been considered.", "other_strengths_and_weaknesses": "Strengths:\n• Innovative integration of Rhomboid Tiling clustering into GNN pooling.\n• Strong theoretical grounding that clarifies the clustering mechanism.\n• Comprehensive experimental evaluation demonstrating significant performance gains.\n\nWeaknesses:\n• The complexity of the geometric constructions and associated proofs may pose challenges for reproducibility and practical implementation.\n• Sensitivity to hyperparameter choices (e.g., the difference between k₂ and k₁) might require careful tuning in practice.\n• The approach is tailored to geometric graphs; it is less clear how well it generalizes to non-geometric settings.", "other_comments_or_suggestions": "It would be useful for the authors to provide further insights into the computational overhead of the RT clustering process and to discuss potential strategies for scaling to larger graphs. Additionally, clarifying the limits of parameter sensitivity could help practitioners better understand when and how to deploy the method.", "questions_for_authors": "Could you elaborate on the sensitivity of RTPool to the choice of clustering parameters (k₁ and k₂)? In particular, how robust is the performance when these parameters are varied within the recommended range?\n\nHave you considered applying RT clustering to graph tasks beyond classification, such as regression or link prediction? If so, what challenges might arise in those contexts?\n\nCan you provide more details on the computational complexity of the RT clustering procedure, especially in high-dimensional spaces, and how it scales with graph size?\n\nIn cases where the underlying graph is not strictly geometric (e.g., social networks), do you foresee adaptations of RT clustering that could still capture meaningful structure?", "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": "X8z7Qxs8gq", "reviewer": "Reviewer_kfVb", "summary": "The author proposes a new pooling methgod inspired by the the rhomboid tiling structure. The author starts from “High-Order Voronoi Tessellation”, which is a method to partitate space based on points. The Voronoi cell Q indicates that all points blong to Q are clustered together and separated with other points. All the partitions are called order-K Voronoi tessellation. And the high-order Deluanay Complex, which is defined as the nerve of Voronoi Tessellation, encodes the relationship between these clusters. And Rhomboid Tiling can be used to build the relationship between different orders of Deluanay Complex.  \n\nWith these theories as foundation, the author porpose the RT clustering, which basically use spheres to partition points. The partitions can be used to define geometric relationships or further clustering. And the author also provides methods on two important subproblem, how to choose step size between order k and how to assign weights to different points. Furthermore, authors propose RTPool, which applies the mentioned methods as pooling methods. The author also provides extensive experiments to prove the efficiency of the proposed methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback. Below, we provide detailed responses to each of the points raised.\n\n**1. Model Efficiency**\n\nTo address the reviewer’s concern, we provide both the **theoretical time complexity** of RTPool and **empirical evidence** comparing it with other pooling methods.\n\n***Theoretical Time Complexity***\n\nWhen the input geometric graph is embedded in $\\mathbb{R}^3$, both the construction of the rhomboid tiling and the pooling operation based on this structure have theoretical time complexity $O(n^2)$, where $n$ is the number of input nodes.\n\n***Conclusion 1:***\n\nThe total time complexity of computing rhomboid tiling up to order $K$ in $\\mathbb{R}^d$ is:\n\n$$O\\left(n^{\\left\\lfloor \\frac{d+1}{2} \\right\\rfloor} K^{\\left\\lceil \\frac{d+3}{2} \\right\\rceil} \\right),$$\n\nas induced by result in Corbet et al. (2021) and Corbet et al. (2023). And in our practice, dimension $d=3$, and maximun order $K=2$ or $3$, the complexity reduces to $O(n^2)$.\n\n***Conclusion 2:***\n\nThe number of nodes in the $k$-th RT layer (order-$k$ Delaunay complex) is $O(k^2(n - k))$ (Lee, 1982), and with small $k$ and sparse input graphs, this ensures the total time complexity of RTPool remains $O(n^2)$.\n\nEach pooling layer consists of:\n\n- **Step 1:** Matrix multiplication between clustering matrix ($O(n) \\times O(n)$) and node features ($O(n) \\times O(1)$): $O(n^2)$\n- **Step 2:** GIN layer on sparse graph with $O(n)$ nodes: $O(n)$\n\nThus, total per-layer complexity is $O(n^2)$.\n\n***References***\n\n- Corbet et al. (2023), *Computing the Multicover Bifiltration*, Discrete & Computational Geometry.  \n- Corbet et al. (2021), *Computing the Multicover Bifiltration*, arXiv:2103.07823.  \n- Lee (1982), *On k-nearest neighbor Voronoi diagrams in the plane*, IEEE Trans. Computers.\n\n***Empirical Efficiency***\n\nWe also benchmarked RTPool against other pooling methods such as DiffPool, MinCutPool, HaarPool, etc.  \nRTPool demonstrates comparable efficiency. \n\n**Table 1: Accuracy over 5 runs × 100 epochs**\n\n| Model|BZR| COX2  | MUTAG         | PTC_MR        | PTC_MM        | PTC_FM        | PTC_FR        |\n|--------|-----|---------|----------------|----------------|----------------|----------------|----------------|\n| MinCutPool   | 76.47±2.32     | 79.86±2.47     | 69.47±2.11     | 66.86±2.91     | 72.94±1.18     | 56.74±5.63     | 62.86±1.81     |\n| DiffPool     | 78.54±0.98     | 77.93±3.18     | 73.68±3.33     | 69.14±2.80     | 67.06±2.20     | 68.57±3.61     | 68.57±1.81     |\n| HaarPool     | 78.05±0.00     | 80.64±4.58     | 68.42±0.38     | 62.29±4.20     | 64.71±3.72     | 61.14±6.66     | 65.67±2.25     |\n| Wit-TopoPool | 80.98±2.39     | 80.43±1.59     | 85.32±2.58     | 71.84±1.14     | 72.82±4.71     | 68.56±4.84     | **68.57±4.04**     |\n| Hop-Pool     | 78.05±1.39     | 80.00±1.70     | **87.56±4.41**     | 61.71±2.91     | 70.59±0.78     | 58.29±1.40     | 63.43±1.14     |\n| Mv-Pool      | 75.60±1.98     | 79.68±1.27     | 73.68±10.53    | 64.57±4.64     | 68.24±1.18     | 57.14±0.00     | 65.71±1.77     |\n| **RTPool**   | **84.39±1.19** | **85.96±1.04** | 83.16±5.16     | **72.86±3.65** | **72.94±3.43** | **68.86±8.59** | 67.71±7.75 |\n\n**Table 2: Total Runtime (seconds) over 5 runs × 100 epochs**\n\n| Model                | BZR     | COX2    | MUTAG   | PTC_MR | PTC_MM | PTC_FM | PTC_FR |\n|----------------------|---------|---------|---------|--------|--------|--------|--------|\n| MinCutPool           | 2297.74 | 2554.96 | 1999.89 | 2016.22| 2482.84| 2470.79| 2355.13|\n| DiffPool             | 2507.53 | 2813.80 | 2144.75 | 2235.34| 2637.06| 2621.80| 2529.79|\n| HaarPool             | 3238.15 | 2666.93 | 1787.79 | 1412.01| 1407.39| 2075.04| 2022.91|\n| Wit-TopoPool         | 4512.64 | 4904.08 | 7475.70 | 7390.13| 7332.05| 7370.51| 7357.56|\n| Hop-Pool             | 1483.80 | 1420.63 | 1190.00 | 1171.09| 1450.05| 1421.54| 1355.92|\n| Mv-Pool              |11244.74 | 9137.48 | 5828.78 | 8935.74| 8327.48| 8326.58| 8907.54|\n| **RTPool (constructor)** | 1616.06 | 2356.41 | 189.59  | 341.39 | 321.39 | 331.57 | 360.00 |\n| **RTPool (model)**       | 1117.62 | 1053.07 | 1041.59 | 673.77 | 1268.01| 1708.35| 306.10 |\n\nDespite running for only 100 epochs, RTPool achieves strong results with limited training time, even when including the overhead of rhomboid tiling construction.\n\n**2. Relationship between $C_l$ and $C_k$**\n\n$C_k$ denotes the clustering matrix from the order-$k$ Delaunay complex to order-$(k+1)$. When the pooling layer index $l = k$, we use $C_k$ as the clustering matrix $C_l$. So $C_l$ and $C_k$ refer to the same object with different notations. We thank the reviewer for pointing this out and will revise our notation to avoid confusion.\n\nThe maximum value of $k$ is set to 2 or 3 in our experiments, which is equal to **#pooling layers+1**. (The choice of #pooling layers is provided in the appendix). Due to space limits, please refer to our response to **Reviewer z8We** for detail on the choice of $k$.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "1: The paper is clear to read. The authors clearly states the theory and algorithm of their methods. \n\n2: The idea is novel. Pooling based on cluster is interesting. \n\n3: The experiment result is good.", "theoretical_claims": "No", "experimental_designs_or_analyses": "No issues.", "relation_to_broader_scientific_literature": "The approach proposed is potentially benefit other scientific domains.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Question and concerns: \n\n1: It looks like the authors does not talk about the efficiency of their methods. These operations seems introduce extra overheads to the pooling operation. It can also be helpful to provide experiment results to show efficiency, comparing with other pooling methods.  \n\n2: In section 3.3, the author talk about C_l, which is clustering matrix for layer l. But previously, the author only talk about C_k. How does C_l and C_k connect with each other?  And how to choose the value of k, what will the maximum value of k for each pooling? Please provide some explanation.", "other_comments_or_suggestions": "Please see the weakness.", "questions_for_authors": "See weakness.", "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": "zPqSbjTIp4", "reviewer": "Reviewer_z8We", "summary": "This paper introduces Rhomboid Tiling (RT) clustering, a novel hierarchical clustering method for geometric graph deep learning. The RT clustering approach is based on the rhomboid tiling structure, which extends Voronoi tessellation and Delaunay complex theory to efficiently capture high-order geometric relationships within graph-structured data. Based on RT clustering, the authors propose RTPool, a new graph clustering pooling model tailored for graph classification tasks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable and constructive feedback. Below we respond to the key concerns raised.\n\n**1. Readability**\n\nWe have revised our notation and mathematical expressions to improve consistency and clarity—e.g., clarifying the usage of matrices $C_l$ and $C_k$. Additionally, we added an example in the appendix using the molecular graph of Formaldehyde to illustrate the construction of its rhomboid tiling in a step-by-step manner.\n\n**2. Positioning of RTpool**\n\nRTpool is a hierarchical clustering pooling method. Unlike traditional methods such as DiffPool, which learn how to group nodes via a trainable assignment matrix, RTpool performs clustering purely based on the geometric structure of the input graph.\n\nThis geometry-driven approach offers several advantages:\n- It naturally incorporates higher-order geometric information from the graph, which contributes to the superior performance of RTpool.\n- It avoids additional learnable parameters or training overhead, making the training process efficient.\n- The clustering results depend only on the input graph's geometry and are less affected by noise or quality variations across the training dataset.\n\nA known limitation is that RTpool does not support adaptive pooling to a target size. However, we can mitigate this by leveraging the \"birthtime\" of each cluster, which is naturally generated during the RT clustering process and reflects its importance. By removing clusters with low importance after pooling, we can control the final graph size if needed.\n\n**3. Choice of Underlying Graph**\n\nThank you for pointing this out. We clarify our reasoning as follows:\n\n- RT clustering already relies on the geometric structure of the input graph. Since Delaunay-connected nodes are often clustered together, reusing Delaunay graphs after pooling adds limited new information.\n\n- RT clustering depends solely on geometric positions and does not fully capture edge-level connectivity of the initial graph. However, in domains like molecular graphs, edge connections (e.g., chemical bonds) carry crucial information. To compensate, we use the original molecular graph to construct **generated graphs** after pooling, allowing the model to retain important high-order connectivity information of initial graph.\n\nTherefore, we adopt **generated graphs** as the underlying graph after each pooling layer to enhance representation learning.\n\n**4. Choice of $k$**\n\nIn RTpool, the choices of order $k$ is determined by two parameters: the difference $k_2 - k_1$ and the number of pooling layers.\n\n- $k_2 - k_1$ can be viewed as the \"step size\": at each pooling layer, features are aggregated from order $k$ to order $(k + (k_2 - k_1))$.\n- The number of pooling layers determines how many such \"steps\" we perform in total.\n\nWe conducted a sensitivity analysis for both parameters. The results are shown below:\n\n**Table: Sensitivity to $k_2 - k_1$**\n\n| Dataset  | $k_2 - k_1$ | Accuracy         |\n|----------|-------------|------------------|\n| COX2     | 1           | 89.36 ± 2.33     |\n|          | 2           | **92.76 ± 1.90** |\n|          | 3           | 86.38 ± 1.90     |\n| MUTAG    | 1           | **94.74 ± 3.33** |\n|          | 2           | 89.64 ± 2.36     |\n|          | 3           | 88.42 ± 2.10     |\n| PTC\\_MR  | 1           | 76.57 ± 1.14     |\n|          | 2           | **78.86 ± 1.57** |\n|          | 3           | 69.71 ± 1.56     |\n\n**Table: Sensitivity to the number of pooling layers**\n\n| Dataset  | #Pooling Layers | Accuracy         |\n|----------|------------------|------------------|\n| COX2     | 1                | **89.36 ± 2.33** |\n|          | 2                | 88.50 ± 1.17     |\n| MUTAG    | 1                | **94.74 ± 3.33** |\n|          | 2                | 90.52 ± 2.35     |\n| PTC\\_MR  | 1                | **76.57 ± 1.14** |\n|          | 2                | 72.57 ± 2.56     |\n\nWe observe that RTPool performs robustly when $k_2 - k_1 = 1$ or $2$, and shows degraded performance when $k_2 - k_1 = 3$. This aligns with our theoretical analysis, which suggests that setting $k_2 - k_1 \\geq 3$ may result in a loss of node feature information during the pooling process, thus hurting performance. Therefore, we recommend choosing $k_2 - k_1 = 1$ or $2$ in practice. While our original model used $k_2 - k_1 = 1$ by default, these experiments suggest that using $k_2 - k_1 = 2$ can yield better results on some datasets.\n\nThe number of pooling layers functions similarly to the number of layers in an MLP—deeper models can increase capacity, but may also introduce overfitting or unnecessary compression on small datasets. For most of the small-to-medium-sized benchmarks in our experiments, we find that a single pooling layer is sufficient and often preferable in practice.", "claims_and_evidence": "While the paper presents some experimental results, some claims require additional clarification and justification:\n\n1. The geometric advantage of RT clustering over existing pooling methods is not extensively analyzed. \n\n2. The computational complexity of RTPool is not explicitly compared against existing graph pooling models, making it unclear whether the method is scalable.", "methods_and_evaluation_criteria": "Yes, I think the choice of graph classification datasets is reasonable, as they involve molecular graphs where geometric properties are crucial.", "theoretical_claims": "The paper presents several theoretical formulations related to high-order Voronoi tessellation, Delaunay complexes, and Rhomboid Tiling clustering. The main theorems (Theorems 3.1, 3.2, 3.3) are well-structured, but there is no empirical validation that confirms these theoretical claims in real-world datasets. Also, the weighting mechanism for RT clustering (Theorem 3.3) is introduced without much intuition on its impact on pooling quality.", "experimental_designs_or_analyses": "The experimental setup is well-defined, following the same train-test split strategies as previous works.", "relation_to_broader_scientific_literature": "I am not clear about this work's relationship to existing hierarchical clustering techniques, spectral pooling, and adaptive pooling. Authors may consider providing a more comprehensive review of related work and explicitly highlight how this method differs from classical pooling techniques.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "S1: The paper presents a novel geometric clustering approach based on rhomboid tiling, which has not been extensively explored in the context of graph pooling.\n\nS2: The proposed RTPool method consistently outperforms existing state-of-the-art graph pooling approaches across seven benchmark datasets, including molecular and biochemical graphs.\n\nW1: For readability, I feel that some mathematical notations and derivations are quite dense, making it challenging for readers unfamiliar with computational geometry.\n\nW2: The paper does not clearly position its key contributions within the broader graph learning and pooling literature. While rhomboid tiling is novel, its relationship to existing hierarchical clustering techniques, spectral pooling, and adaptive pooling is not sufficiently discussed.", "other_comments_or_suggestions": "1. The choice of underlying graph representations (Delaunay graphs vs. generated graphs) is not fully justified.\n\n2. A deeper analysis of how different choices of k-values impact clustering performance is needed.\n\n>updated after reading the rebuttal and responses\n\n>All my concerns have been clarified. Therefore, I am happy to increase my score to '4: Accept'.", "questions_for_authors": "see the above", "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": "NWLhEJUD8C", "reviewer": "Reviewer_DiJs", "summary": "This paper proposes a geometry-aware graph clustering algorithm for enhancing geometric graph classification performance across diverse datasets. The method captures high-order structural information of geometric graphs through high-order Voronoi tessellation and Delaunay complexes. Building on this foundation, this paper introduces a hierarchical graph pooling operation that constructs a normalized clustering matrix via Rhomboid incidence matrices. This operation aggregates lower-order cluster features into higher-order representations and updates node features using highly expressive GNNs. The underlying graph structure can be flexibly configured as either Delaunay graphs or generated graphs expanded from chemical bonds to incorporate structural priors. Extensive experiments on multiple benchmark datasets demonstrate comparable or competitive results against state-of-the-art methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's positive recognition of our rhomboid tiling clustering framework and its potential for broader applications.\n\n**1.Question about geometric conflicts**\n\nThank you for the insightful question.\n\nOur method adopts a **layer-wise hierarchical clustering** strategy. Given a set of clusters corresponding to nodes in the layer of order-$k_1$ Delaunay complex, we apply RT clustering to map these clusters onto a higher-order structure—specifically, the new layer of order-$k_2$ Delaunay complex—where $k_2 > k_1$. During this process, we do not incrementally modify or extend the existing lower-order clusters. Instead, we directly construct an entirely new layer of clusters at order-$k_2$.\n\nAs you pointed out, a possible concern is whether clusters in the new layer (order-$k_2$) may geometrically conflict—e.g., a point being assigned to multiple clusters, or clusters overlapping in space. This can indeed occur at the point level; a point may belong to multiple higher-order clusters. However, this is not problematic.\n\nIn particular, if $X_1$ and $X_2$ are point sets forming two distinct clusters from the new layer at order-$k_2$, then even if they share some points (i.e., $X_1 \\cap X_2 \\neq \\emptyset$), their corresponding convex hulls $\\mathrm{conv}(X_1)$ and $\\mathrm{conv}(X_2)$ only intersect at their **boundaries**. Their interiors remain disjoint. This structural property ensures that the rhomboid tiling construction preserves **geometric consistency**, and does not introduce significant geometric conflicts during hierarchical clustering.", "claims_and_evidence": "The motivation of this paper is clearly articulated. Traditional connectivity-based graph clustering methods lack effective geometric information and fail to adequately capture the inherent spatial geometric features in geometric graphs. Furthermore, topology-driven clustering approaches struggle to identify geometric substructures in dense regions and cannot effectively characterize spatial proximity relationships between atoms or molecules, thereby limiting the model's ability to learn complex geometric patterns. Through rigorous analysis and theoretical proofs, this work confirms that the proposed Rhomboid Tiling-based clustering method effectively addresses these limitations.", "methods_and_evaluation_criteria": "This paper proposes a geometric-aware hierarchical clustering method based on the rhomboid tiling structure and a corresponding graph pooling model. The method constructs high-order geometric clusters through spherical partitioning of the spatial domain, where atomic nodes in geometric graphs are hierarchically aggregated based on spatial proximity. Lower-order clusters are formed by small-scale atomic groups, while higher-order clusters emerge by merging geometrically adjacent lower-order clusters. A rhomboid cell depth-based weighting mechanism is introduced to quantify the importance of subclusters. The model incorporates molecular chemical bonds to construct hierarchical graph structures, leverages GNNs to hierarchically extract geometric features across layers, and ultimately obtains global representations through multi-layer geometric pooling. This approach preserves 3D spatial relationships while enabling efficient hierarchical information abstraction. The method's design is well-founded and should enable efficient clustering of data with complex geometric structures.", "theoretical_claims": "I have reviewed the proofs and reasoning in the main text, which  are clear and comprehensible, and the relevant formulas are consistent with the descriptions in the methodology section of the paper.", "experimental_designs_or_analyses": "The proposed method is validated on datasets including molecular property prediction and protein-protein interactions, with experimental results demonstrating that the proposed approach achieves SOTA performance. Ablation studies further confirm the critical impact of the proposed modules on performance enhancement. The experiments in this work are comprehensive, and the method exhibits promising predictive capabilities even on more challenging data scenarios.", "relation_to_broader_scientific_literature": "The efficient clustering algorithm proposed in this paper holds significant implications for adaptive research in point cloud testing. The experiments conducted on complex data such as proteins have validated its feasibility, suggesting that it may also be beneficial for the clustering and construction of neighborhood relationships in point clouds, as discussed in [1].\n\n\n[1]. Yang S, Wang Y, Van de Weijer J, et al. Trust your good friends: Source-free domain adaptation by reciprocal neighborhood clustering[J]. IEEE Transactions on pattern analysis and machine intelligence, 2023, 45(12): 15883-15895.", "essential_references_not_discussed": "I believe the methodologies referenced and the literature discussed in this paper demonstrate relatively comprehensive coverage.", "other_strengths_and_weaknesses": "This paper proposes a highly intriguing graph clustering algorithm. By introducing a novel Rhomboid Tiling clustering method, it effectively handles diverse types of data with complex geometric information, achieving highly accurate classification. I believe this work will provide significant inspiration for research in point cloud feature extraction, unsupervised adaptation.", "other_comments_or_suggestions": "None.", "questions_for_authors": "How does the incremental construction mechanism of rhomboid tiling mentioned in the paper handle geometric conflicts between newly added clusters and existing clusters?", "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": "AJsscj0Z11", "reviewer": "Reviewer_Ci9s", "summary": "This paper proposes Rhomboid Tiling (RT) clustering, a hierarchical clustering method designed for geometric graph deep learning. The method leverages higher-order Voronoi structures to improve graph pooling and demonstrates competitive performance across multiple benchmark datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the thoughtful and constructive feedback. Below we address each concern raised.\n\n**1. Dataset Description**\n\nTo address the reviewer’s concern, we provide a summary of the datasets used in our classification experiments:\n\n**Table: Description of classification datasets**\n\n|Dataset|BZR|COX2|MUTAG|PTC_MR|PTC_MM|PTC_FM|PTC_FR|\n|---|---|--|--|--|---|---|--|\n|No. graphs|405|467 |188|344|336|349|351|\n|Avg. nodes|35.75|41.22|17.93|25.56|24.25|25.00|24.96|\n\nWe also include additional experiments on regression tasks and social network datasets. Their statistics are summarized below. Please refer to our response to **Reviewer FBWn** for performance results.\n\n**Table: Description of regression and social datasets**\n\n| Dataset| Esol | FreeSolv | Lipo | IMDB-BINARY | IMDB-MULTI |\n|--|--|--|--|--|---|\n|No. graphs|1128|642|4200|1000 |1500|\n|Avg. nodes|26.00|18.00|49.00|19.77|13.00|\n\n**2. Comparison with Recent Studies**\n\nWe thank the reviewer for this suggestion. To address it, we included two pooling methods published in 2024:\n\n- **Hop-Pool** (Zhang et al. (2024), *Multi-hop graph pooling adversarial network for cross-domain remaining useful life prediction*, Reliability Engineering & System Safety, 244, 109950.)\n- **Mv-Pool** (Ma et al. (2024), *GraphADT: empowering interpretable predictions of acute dermal toxicity with multi-view graph pooling and structure remapping*, Bioinformatics, 40(7), btae438.)\n\nWe followed the default settings from their original papers and conducted a grid search around those values to fairly tune the hyperparameters. The results of these methods compared to ours are summarized below:\n\n**Table: Performance of different models on benchmark datasets (mean ± std). Best results are in bold.**\n\n| Model| BZR|COX2|MUTAG|PTC_MR|PTC_MM|PTC_FM|PTC_FR|\n|---|---|---|---|---|---|--|---|\n|Hop-Pool|85.37±4.36|85.11±3.74| **94.74±4.76**|65.71±2.85|73.59±5.27|64.15±4.62|65.71±3.71|\n|Mv-Pool|78.05±3.38|82.98±5.24|89.64±2.43|68.58±2.61|70.65±4.83|62.86±3.37|65.72±2.14|\n|**RTPool**|**88.29±0.98**|**89.36±2.33**|**94.74±3.33**|**76.57±1.14**|**82.94±2.20**|**77.72±1.14**|**82.29±2.80**|\n\nThese results show that RTPool consistently outperforms or matches state-of-the-art methods from 2024 on all benchmark datasets.\n\n**3. Computational Complexity**\n\nDue to space constraints, please refer to our detailed theoretical and empirical complexity analysis provided in our response to **Reviewer kfVb**. In short, our RT pooling model have overall complexity of $O(n^2)$ in $\\mathbb{R}^3$, and our runtime comparisons confirm the model’s efficiency.\n\n**4. Additional Visualization**\n\nWe appreciate the suggestion. We have added a visualization example using the molecular graph of **Formaldehyde** to illustrate how RTpool performs hierarchical clustering pooling. The visualization is available at the anonymous link:\n[RTPool_Visual](https://anonymous.4open.science/r/RTpool_rebuttal_images-B017/RTPool_Visualization.png)\n\n**5. Clarity of Notations**\n\nWe have revised our notation and mathematical expressions to improve consistency and clarity—e.g., clarifying the usage of matrices $C_l$ and $C_k$. Additionally, we added an example in the appendix using the molecular graph of Formaldehyde to illustrate the construction of its rhomboid tiling in a step-by-step manner to improve the readability.\n\n**6. Baseline Comparisons**\n\nThe baseline results are taken from the ***Wit-TopoPool*** paper, which also serves as a strong recent benchmark. According to the authors, all baselines in that work, including Wit-TopoPool itself, were tuned using grid search over a fixed set of hyperparameter choices, and evaluated under the same cross-validation protocol. Our model uses the same setting, and this ensures a fair and consistent comparison.\n\n**7. Hyperparameter Sensitivity**\n\nWe thank the reviewer for pointing this out. We have already included a sensitivity analysis of the key structural hyperparameters $k_2 - k_1$ and the number of pooling layers in our response to **Reviewer z8We**.\n\nIn addition, we performed sensitivity experiments on the learning rate and the final dropout rate. The results are summarized below.\n\n**Table: Sensitivity to learning rate (LR)**\n\n|Dataset|LR| Accuracy|\n|--|--|--|\n|COX2|0.0002|87.23±1.50|\n|| 0.0005 | 87.66±0.95|\n||0.001|**89.36±2.33**|\n||0.002|88.93±1.78|\n|MUTAG|0.0002|89.47±0.00|\n||0.0005|91.57±2.88|\n||0.001|**94.74±3.33**|\n||0.002|93.68±2.10|\n|PTC_MR|0.0001|73.72 ± 2.39|\n||0.0002|**76.57 ± 1.57**|\n|| 0.0005 |72.57 ± 1.40|\n||0.001|70.29 ± 1.40|\n\n**Table: Sensitivity to final dropout rate**\n\n|Dataset|Dropout|Accuracy|\n|--|--|--|\n|COX2|0.4|88.51 ± 1.91|\n||0.5|**89.36 ± 2.33**|\n||0.6|88.93 ± 1.78|\n|MUTAG| 0.4| 92.63 ± 2.88|\n|| 0.5 | **94.74 ± 3.33** |\n|| 0.6  | 93.69 ± 2.36|\n| PTC_MR|0.2| 74.86 ± 1.27|\n||0.3|**76.57 ± 1.14** |\n||0.4|75.43 ± 1.56|\n\nThese results show that RTPool is relatively robust to variations in learning rate and dropout.", "claims_and_evidence": "The claims in the submission are generally supported by mathematical proofs, theoretical analysis, and empirical results, but the lack of computational complexity discussion weakens the justification of its scalability and key design choices.", "methods_and_evaluation_criteria": "The proposed RT clustering method and RTPool model are well-aligned with the problem of geometric graph learning, and the evaluation criteria, including benchmark datasets from molecular and bioinformatics domains are appropriate; however, broader dataset diversity could further validate generalizability.", "theoretical_claims": "The theoretical proofs, particularly Theorems 3.1, 3.2, and 3.3, appear mathematically sound, but the lack of computational complexity analysis raises concerns about scalability.", "experimental_designs_or_analyses": "The experimental design, including comparisons across 7 benchmark datasets and ablation studies, is generally sound,", "relation_to_broader_scientific_literature": "The paper builds on prior work in graph pooling (e.g., DiffPool, MinCutPool), computational geometry (Voronoi tessellation, Delaunay complexes), and topological data analysis.", "essential_references_not_discussed": "The paper thoroughly discusses related works in graph pooling (DiffPool, MinCutPool), computational geometry (Voronoi tessellation, Delaunay complexes), and topological methods (Wit-TopoPool, SIN), but it lacks citations to recent advances in topological data analysis (e.g., persistent homology for graph learning) and efficient geometric clustering methods, which could provide additional context for its contributions.", "other_strengths_and_weaknesses": "Strengths:\n\n1.The paper provides solid theoretical support for the proposed method.\n\n2.The authors have released the code to ensure reproducibility.\n\n3.Extensive experiments validate the effectiveness of the proposed approach.\n\nWeaknesses:\n\n1.The paper lacks a detailed description of the datasets, making it difficult to determine the data dimensions and raising concerns about the scalability of the proposed method.\n\n2.The comparative analysis does not include recent studies from 2024, making it challenging to demonstrate the effectiveness of the proposed approach against more recent advancements.\n\n3.The paper lacks complexity analysis, both theoretically and experimentally.\n\n4.It would be beneficial to include additional visualization experiments to illustrate how RT clustering performs hierarchical clustering.", "other_comments_or_suggestions": "1. Clarity of Notation and Mathematical Definitions – Some mathematical formulations, particularly in Section 3 (RT Clustering Definition), are complex and may benefit from more intuitive explanations or examples. A clearer breakdown of key notations and geometric interpretations would improve readability, especially for non-experts in computational geometry.  \n\n\n2. Baseline Selection and Fair Comparisons – While the paper compares against 19 methods, it is unclear whether hyperparameters for all baselines were tuned fairly or if default settings were used. A discussion on how baseline models were optimized would ensure a fair evaluation of the proposed method’s advantages.  \n\n\n3. Hyperparameter Sensitivity Analysis – The paper does not explore how sensitive the method is to key hyperparameters, such as the number of pooling layers. A hyperparameter sensitivity study would help assess the robustness of the approach across different datasets.", "questions_for_authors": "Please see weaknesses and comments.", "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:

Meta-review: The paper proposes a hierarchical clustering algorithm for geometric deep learning. The main contribution is RTPool, a pooling model method where nodes are clustered using a rhomboid tiling structure. The paper is also accompanied by a theoretical analysis showing sufficient conditions for cluster membership. 

The paper has been generally well-received by all reviewers (1 Accept, 4 weak accepts). The contribution is considered novel, the theoretical analysis motivates the contribution, and the experiments appear convincing both in width (7 benchmarks, comparison with 19 existing methods) and depth (ablation analyses). 

Some reviewers didn't participate in the discussion after rebuttal, but reviewing the author's responses, I can confirm that their concerns have been mostly resolved. In all likelihood, had these reviewers participated in the rebuttal discussion, the scores could have been even higher.

I recommend weak acceptance (subject to ICML's quota on acceptable papers).
Decision: Accept (poster)