Rhomboid Tiling for Geometric Graph Deep Learning

We sincerely thank the reviewer for the thoughtful and constructive feedback. Below we address each concern raised.

1. Dataset Description

To address the reviewer’s concern, we provide a summary of the datasets used in our classification experiments:

Table: Description of classification datasets

We 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.

Table: Description of regression and social datasets

2. Comparison with Recent Studies

We thank the reviewer for this suggestion. To address it, we included two pooling methods published in 2024:

• 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.)
• 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.)

We 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:

Table: Performance of different models on benchmark datasets (mean ± std). Best results are in bold.

These results show that RTPool consistently outperforms or matches state-of-the-art methods from 2024 on all benchmark datasets.

3. Computational Complexity

Due 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.

4. Additional Visualization

We 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: RTPool_Visual

5. Clarity of Notations

We 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.

6. Baseline Comparisons

The 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.

7. Hyperparameter Sensitivity

We 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.

In addition, we performed sensitivity experiments on the learning rate and the final dropout rate. The results are summarized below.

Table: Sensitivity to learning rate (LR)

Table: Sensitivity to final dropout rate

These results show that RTPool is relatively robust to variations in learning rate and dropout.

We appreciate the reviewer's positive recognition of our rhomboid tiling clustering framework and its potential for broader applications.

1.Question about geometric conflicts

Thank you for the insightful question.

Our 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$.

As 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.

In 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.

We thank the reviewer for their valuable and constructive feedback. Below we respond to the key concerns raised.

1. Readability

We 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.

2. Positioning of RTpool

RTpool 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.

This geometry-driven approach offers several advantages:

• It naturally incorporates higher-order geometric information from the graph, which contributes to the superior performance of RTpool.
• It avoids additional learnable parameters or training overhead, making the training process efficient.
• The clustering results depend only on the input graph's geometry and are less affected by noise or quality variations across the training dataset.

A 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.

3. Choice of Underlying Graph

Thank you for pointing this out. We clarify our reasoning as follows:

• 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.

• 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.

Therefore, we adopt generated graphs as the underlying graph after each pooling layer to enhance representation learning.

4. Choice of $k$

In RTpool, the choices of order $k$ is determined by two parameters: the difference $k_2 - k_1$ and the number of pooling layers.

• $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))$.
• The number of pooling layers determines how many such "steps" we perform in total.

We conducted a sensitivity analysis for both parameters. The results are shown below:

Table: Sensitivity to $k_2 - k_1$

Table: Sensitivity to the number of pooling layers

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$ 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.

The 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.

We thank the reviewer for their helpful feedback. Below, we provide detailed responses to each of the points raised.

1. Model Efficiency

To address the reviewer’s concern, we provide both the theoretical time complexity of RTPool and empirical evidence comparing it with other pooling methods.

Theoretical Time Complexity

When 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.

Conclusion 1:

The total time complexity of computing rhomboid tiling up to order $K$ in $\mathbb{R}^d$ is:

$O\left(n^{\left\lfloor \frac{d+1}{2} \right\rfloor} K^{\left\lceil \frac{d+3}{2} \right\rceil} \right),$

as 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)$.

Conclusion 2:

The 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)$.

Each pooling layer consists of:

• Step 1: Matrix multiplication between clustering matrix ($O(n) \times O(n)$) and node features ($O(n) \times O(1)$): $O(n^2)$
• Step 2: GIN layer on sparse graph with $O(n)$ nodes: $O(n)$

Thus, total per-layer complexity is $O(n^2)$.

References

• Corbet et al. (2023), Computing the Multicover Bifiltration, Discrete & Computational Geometry.
• Corbet et al. (2021), Computing the Multicover Bifiltration, arXiv:2103.07823.
• Lee (1982), On k-nearest neighbor Voronoi diagrams in the plane, IEEE Trans. Computers.

Empirical Efficiency

We also benchmarked RTPool against other pooling methods such as DiffPool, MinCutPool, HaarPool, etc.
RTPool demonstrates comparable efficiency.

Table 1: Accuracy over 5 runs × 100 epochs

Table 2: Total Runtime (seconds) over 5 runs × 100 epochs

Despite running for only 100 epochs, RTPool achieves strong results with limited training time, even when including the overhead of rhomboid tiling construction.

2. Relationship between $C_l$ and $C_k$

$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.

The 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$.

We sincerely thank the reviewer for their thoughtful and constructive comments. Below, we provide detailed responses to each of the points raised.

1. Hyperparameter sensitivity

To 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:

Table: Sensitivity to $k_2-k_1$.

From 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.

2. RTPool for Graph Regression Tasks

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.

To support this claim, we have conducted additional experiments on regression datasets. The results, in terms of RMSE, are reported in the following table:

Table: RMSE comparison on graph regression datasets

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.

3. Computational Complexity of the RT Clustering

Theoretically, 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.

Due 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

4. RTPool for Social Network Graphs

To 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.

Based on this idea, we applied RTPool to social network datasets which contain only graph connectivity. The results are shown below:

Table: Accuracy (%) on social network datasets (mean ± std).

As shown above, RTPool achieves competitive performance despite lacking enough geometric information