Research map / Graph learning / GNN architectures
Rhomboid Tiling for Geometric Graph Deep Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Rhomboid Tiling (RT) clustering, a geometry-driven hierarchical clustering based on high-order Delaunay complexes, and RTPool, a graph pooling model that outperforms 21 baselines on 7 TUDataset molecular/chemical graph classification benchmarks.
Problem
Clustering-based graph pooling methods rely mainly on graph connectivity and learned assignments, so they under-use the geometric information of geometric (e.g., molecular) graphs.
Approach
Cluster the point cloud of atom positions via rhomboid tiling, which relates order-k Delaunay complexes across orders using spheres, giving a hierarchical geometric clustering with a weight N(Q,Q') counting shared maximal rhomboids; pooled features are then updated with GNNs on a generated graph.
Key results
- RTPool reaches 92.76% on COX2 and 94.74% on MUTAG, versus 93.16% best prior baseline (Wit-TopoPool) on MUTAG and 87.24% on COX2 for Wit-TopoPool.
- RTPool achieves 78.86% on PTC_MR and 82.94% on PTC_MM, ahead of Wit-TopoPool (70.57% and 79.12%).
- Replacing RTPool with mean pooling drops COX2 accuracy from 92.76% to 78.72%; using Delaunay graphs instead of generated graphs drops MUTAG from 94.74% to 86.32%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use RTPool instead of Wit-TopoPool | graph classification · BZR, COX2, PTC_MR, PTC_MM, PTC_FM, PTC_FR | accuracy: BZR: 87.80±2.44 -> 88.29±0.98; COX2: 87.24±3.15 -> 92.76±1.90; PTC_MR: 70.57±4.43 -> 78.86±1.57; PTC_MM: 79.12±4.45 -> 8 | Helped |
| use RTPool instead of HopPool | MUTAG · MUTAG | accuracy: 94.74±4.76 -> 94.74±3.33 | No clear effect |
| add RT clustering pooling instead of mean pooling (ablation) | RTPool · COX2, MUTAG, PTC_MR | accuracy: COX2: 78.72±0.85 -> 92.76±1.90; MUTAG: 84.21±1.37 -> 94.74±3.33; PTC_MR: 65.71±0.00 -> 78.86±1.57 | Helped |
| add RT clustering pooling instead of max pooling (ablation) | RTPool · COX2, MUTAG, PTC_MR | accuracy: COX2: 78.31±0.81 -> 92.76±1.90; MUTAG: 75.53±2.26 -> 94.74±3.33; PTC_MR: 67.43±1.40 -> 78.86±1.57 | Helped |
| use GIN instead of GCN for feature updates (ablation) | RTPool · COX2, MUTAG, PTC_MR | accuracy: COX2: 88.93±0.84 -> 92.76±1.90; MUTAG: 89.47±2.33 -> 94.74±3.33; PTC_MR: 74.28±0.86 -> 78.86±1.57 | Helped |
| use GIN instead of GAT for feature updates (ablation) | RTPool · COX2, MUTAG, PTC_MR | accuracy: COX2: 87.23±1.15 -> 92.76±1.90; MUTAG: 88.73±1.48 -> 94.74±3.33; PTC_MR: 71.43±1.40 -> 78.86±1.57 | Helped |
| use generated graphs instead of Delaunay graphs for feature updates (ablation) | RTPool · COX2, MUTAG, PTC_MR | accuracy: COX2: 88.94±0.85 -> 92.76±1.90; MUTAG: 86.32±2.58 -> 94.74±3.33; PTC_MR: 71.43±0.00 -> 78.86±1.57 | Helped |
| set Δk to 3 rather than 2 on COX2 and PTC_MR, and rather than 1 on MUTAG (ablation) | RTPool · COX2, MUTAG, PTC_MR | accuracy: COX2: 92.76±1.90 -> 86.38±1.90; MUTAG: 94.74±3.33 -> 88.42±2.10; PTC_MR: 78.86±1.57 -> 69.71±1.56 | Hurt |
| set Δk to 1 rather than 2 (ablation) | RTPool · COX2, PTC_MR | accuracy: COX2: 92.76±1.90 -> 89.36±2.33; PTC_MR: 78.86±1.57 -> 76.57±1.14 | Mixed |
| set Δk to 2 rather than 1 (ablation) | RTPool · MUTAG | accuracy: 94.74±3.33 -> 89.64±2.36 | Hurt |
Surprising findings
- Delaunay-graph underlying structures performed worse than graph-generated structures, which the authors attribute to RT clustering already capturing geometric adjacency.
- Step size Δk=3 causes consistent performance drops, as some nodes fail to be assigned to any cluster.
Limitations
- Relies on the point-cloud embedding of molecular graphs; the geometric clustering itself ignores edge semantics (chemical bond information), as acknowledged by the authors.
- Theoretical guarantees for step size assume general position in R^3 and the Δk=3,4 case lacks a proof.
- Hyperparameters tuned on the test-time benchmarks via grid search, with per-dataset choices of pooling layers and learning rate.
Experimental setup
Datasets: COX2 BZR MUTAG PTC_MR PTC_MM PTC_FM PTC_FR
Benchmarks: BZR COX2 MUTAG PTC_MR PTC_MM PTC_FM PTC_FR
Metrics: accuracy
Baselines: Wit-TopoPool HopPool MvPool HaarPool DiffPool MinCutPool SAGPool GIN WL PersLay
Builds on: DiffPool MinCutPool Alpha shapes GIN
Closest papers by meaning
- Geometry-Aware Edge Pooling for Graph Neural Networks (NeurIPS 2025 · similarity 0.87)
- SSHPool: The Separated Subgraph-based Hierarchical Pooling (AAAI 2026 · similarity 0.86)
- Structural Entropy Guided Graph Hierarchical Pooling (ICML 2022 · similarity 0.86)
- Geometry Awakening: Cross-Geometry Learning Exhibits Superiority over Individual Structures (NeurIPS 2024 · similarity 0.85)
- LSEnet: Lorentz Structural Entropy Neural Network for Deep Graph Clustering (ICML 2024 · similarity 0.85)
- What Is Missing For Graph Homophily? Disentangling Graph Homophily For Graph Neural Networks (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.