Higher-order Clustering and Pooling for Graph Neural Networks
This addresses a specific limitation in GNNs for graph classification, offering an incremental improvement over existing pooling methods.
The paper tackles the problem that Graph Neural Networks (GNNs) for graph classification rely on pooling operators that ignore higher-order connectivity patterns, by proposing HoscPool, a clustering-based pooling operator that captures higher-order information hierarchically, achieving best performance on graph classification tasks and clustering evaluation.
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 are not only questioned by recent work showing on par performance with random pooling, but also ignore completely higher-order connectivity patterns. 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 relaxed formulations of motif spectral clustering in our objective function, and we then extend it to a pooling operator. We evaluate HoscPool on graph classification tasks and its clustering component on graphs with ground-truth community structure, achieving best performance. Lastly, we provide a deep empirical analysis of pooling operators' inner functioning.