Higher-order Clustering and Pooling for Graph Neural Networks

Graph Neural Networks achieve state-of-the-art performance on a plethora of graph classification tasks, especially due to pooling operators, which aggregate learned node embeddings hierarchically into a final graph representation. However, they ignore completely higher-order connectivity patterns, although essential for GNNs. To tackle this issue, we propose HoscPool, a clustering-based graph pooling operator that captures higher-order information hierarchically, leading to richer graph representations. In fact, we learn a probabilistic cluster assignment matrix end-to-end by minimising a relaxed formulation of motif spectral clustering in our objective function, and then extend it to a pooling operator. We evaluate both HoscPool on graph classification tasks and its clustering component on graph data with ground-truth community structure, achieving increased performance on multiple datasets.