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