Rhomboid Tiling for Geometric Graph Deep Learning

Yipeng Zhang, Longlong Li, Kelin Xia

TL;DR

Traditional Graph Neural Networks (GNNs) often fail to capture rich spatial structures because their pooling mechanisms rely strictly on graph connectivity. This paper introduces Rhomboid Tiling (RT) clustering, a novel geometric pooling method rooted in computational geometry that leverages high-order Delaunay complexes to capture complex 3D spatial features. The resulting architecture, RTPool, consistently outperforms 21 state-of-the-art methods across multiple chemical and molecular graph classification benchmarks.

What Problem Does This Paper Address?

While Graph Neural Networks (GNNs) excel at processing topological data through message passing, they hit a wall when dealing with geometric graphs—graphs where nodes possess explicit spatial coordinates (like atoms in a molecule or proteins in 3D space).

Existing hierarchical graph pooling methods (such as DiffPool or MinCutPool) cluster nodes using learnable assignment matrices based primarily on the graph's adjacency matrix. Consequently, they miss subtle, higher-order geometric variations in densely packed regions. Connectivity alone cannot fully exploit the underlying physical structure of molecular data, creating a clear demand for pooling methods that treat geometry as a first-class citizen.

Methods

The authors bridge this gap by turning to computational geometry, specifically generalizing the concept of Alpha shapes via Rhomboid Tiling.

The pipeline works as follows:

  1. High-Order Voronoi & Delaunay Structures: The spatial coordinates of the graph are used to build order-$k$ Voronoi tessellations and their dual order-$k$ Delaunay complexes. Each vertex in these complexes represents a geometrically tight cluster of $k$ points.
  2. Rhomboid Tiling Construction: By mapping these complexes into a higher-dimensional space ($\mathbb{R}^{d+1}$), the authors construct a polyhedral complex known as a Rhomboid Tiling. This structure naturally links Delaunay complexes of different orders, providing a rigorous framework for hierarchical clustering.
  3. RTPool: Using the incidence matrix of the maximal rhomboids, the authors derive a parameter-free clustering matrix to pool node features from one layer to the next.
  4. Feature Updates: After pooling, node features are updated using standard GNN layers (like GIN). Crucially, the authors found that updating features using a "generated graph" (reconstructing post-pooling edges based on the original graph's connectivity) preserves vital chemical bond semantics better than a purely geometric Delaunay graph.
Figure 1: Flowchart of the Rhomboid Tiling clustering process. A: An example geometric graph and the corresponding point cloud X, obtained by embedding the graph’s vertices into R2. B: 1-, 2-, and 3-order Voronoi tessellations constructed from X. C: 1-, 2-, and 3-order Delaunay complexes obtained as the nerves of the corresponding Voronoi tessellations. D: The Rhomboid Tiling constructed based on X. E: Illustration of 1-layer Rhomboid Tiling clustering, focusing on a single rhomboid.

Datasets

The model was evaluated on seven real-world graph classification benchmarks from the TUDataset:

  • Chemical Compounds: BZR, COX2, and MUTAG.
  • Molecular Compounds (Carcinogenicity): PTC_MR, PTC_MM, PTC_FM, and PTC_FR.

Additionally, to demonstrate versatility, the authors tested RTPool on molecular property regression tasks (Esol, FreeSolv, Lipo) and non-geometric social network datasets (IMDB-BINARY, IMDB-MULTI) by first generating spatial coordinates via Laplacian spectral embeddings.

Key Insights and Ideas

  • Geometry Beats Pure Topology: Entirely data-driven geometric clustering can outperform heavily parameterized, learnable pooling layers. RTPool doesn't rely on a learnable matrix to guess cluster assignments; the geometry dictates the clusters.
  • The Step-Size Constraint ($\Delta k$): The authors prove theoretically (Theorem 2) that the step size between consecutive clustering levels must be small ($\Delta k = 1$ or $2$). If $\Delta k > 4$ in a 3D space, points fail to group into valid clusters, leading to catastrophic information loss.
  • Preserving Edge Semantics: Purely geometric pooling can lose track of graph topology. By using the original graph's connectivity to reconstruct edges after a pooling step, the model successfully marries high-order spatial details with essential chemical bond information.

Key Results

RTPool achieved a clean sweep, outperforming all 21 state-of-the-art competitors on all 7 benchmark datasets.

  • Classification Performance: RTPool achieved an average relative accuracy improvement of 5.94% over the closest runner-up, Wit-TopoPool. For instance, on the COX2 dataset, RTPool reached an accuracy of 92.76%, compared to Wit-TopoPool's 87.24%.
  • Efficiency and Convergence: In early-stage training tests (limited to 100 epochs), RTPool converged rapidly, delivering outstanding accuracy while maintaining a highly competitive runtime compared to computationally heavy baselines like MvPool.
Table 1: Performance of different models on benchmark datasets. The best performance for each dataset is highlighted in bold.

Limitations and Future Work

While the authors demonstrate that the overall time complexity simplifies to a manageable $O(n^2)$ for 3D point clouds when the maximum order $K$ is small, the initial construction of high-order Voronoi diagrams and rhomboid tilings can still be computationally demanding for exceptionally large graphs or higher-dimensional spaces.

As a next step, the authors plan to expand this geometric framework beyond graphs, extending Rhomboid Tiling clustering to the emerging domain of topological deep learning models (such as simplicial or cellular neural networks).

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