Rhomboid Tiling for Geometric Graph Deep Learning

Yipeng Zhang, Longlong Li, Kelin Xia

Introduction

Traditional Graph Neural Networks (GNNs) primarily rely on message-passing across explicit connectivity structures. However, in domains such as cheminformatics and structural biology, the 3D spatial arrangement of atoms—including spatial proximity and geometric voids—often dictates function more than covalent bonds alone. Standard pooling methods, which coarsen graphs to learn global features, frequently fail to capture these higher-order geometric nuances. To address this, researchers have introduced RTPool, a hierarchical pooling method that replaces connectivity-based clustering with a rigorous geometric approach known as Rhomboid Tiling.

Methodology: The RTPool Framework

RTPool leverages computational geometry to define a hierarchy of clusters based on spatial distribution rather than just edge connectivity. The process begins by generalizing Voronoi tessellations to higher orders.

Overview of the RTPool pipeline, from geometric graph to Rhomboid Tiling clustering.

The methodology involves several key steps:

  1. High-Order Voronoi/Delaunay Complexes: Space is partitioned based on subsets of $k$ points, capturing multi-point spatial relationships.
  2. Rhomboid Tiling Bridge: By "lifting" $d$-dimensional data into a $(d+1)$-dimensional space, the relationships between different geometric orders form a continuous polyhedral complex. This provides a mathematically principled hierarchy for pooling.
  3. Geometric Clustering: This structure is converted into a clustering matrix. GNNs use this matrix to aggregate node features into "super-nodes" representing geometrically significant clusters.
  4. Weighting Mechanism: A unique weighting system quantifies the geometric importance of each node based on its membership in "maximal rhomboids."

Experimental Results

The model was evaluated against 21 state-of-the-art competitors on seven major chemical and biological benchmarks, including the BZR, COX2, and MUTAG datasets.

Performance comparison of RTPool against 21 state-of-the-art models across seven benchmarks.

RTPool achieved a "clean sweep," outperforming all baselines across every benchmark. Notably, on the COX2 dataset, RTPool reached 92.76% accuracy, significantly surpassing the next best model, Wit-TopoPool (87.24%). The researchers also established that a "step size" ($\Delta k$) of 1 or 2 between pooling layers is optimal to prevent information loss. Despite its geometric complexity, RTPool maintains a time complexity of $O(n^2)$ for 3D data, ensuring practical efficiency.

Conclusion

RTPool demonstrates that spatial arrangement is a more robust signal for pooling in geometric graphs than bond-graph connectivity alone. By utilizing the "lifting" trick from computational geometry, the framework avoids the "black box" nature of learnable pooling layers. Future work aims to extend this framework into Topological Deep Learning, exploring more complex simplicial and cellular complexes to model even more sophisticated data relationships.

Summary updated

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.
BibTeX
@inproceedings{zhang2025rhomboid,
  author = {Yipeng Zhang and Longlong Li and Kelin Xia},
  title = {{Rhomboid Tiling for Geometric Graph Deep Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=lTZEAqL1R1},
}
Figure