Rhomboid Tiling for Geometric Graph Deep Learning

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.

Graphs are everywhere — from social networks and molecules to 3D shapes. Computers can learn useful patterns from graph data using tools called Graph Neural Networks (GNNs), which let each node gather information from its neighbors. However, for a special class of graphs known as geometric graphs — where nodes have spatial positions — these tools often ignore the rich geometric structure and focus only on connections.To address this, we introduce a new clustering method called Rhomboid Tiling (RT) clustering, inspired by a novel concept in computational geometry known as rhomboid tiling. It groups nodes by analyzing the underlying geometric layout of the graph, allowing the model to capture more complex spatial relationships.Building on this, we designed RTPool, a new graph pooling technique that leverages RT clustering to improve graph classification tasks. Our model outperforms 21 leading methods on 7 widely used datasets, showing that geometry-aware graph learning can lead to significantly better results in understanding geomatric graph data.