# Higher-order Clustering and Pooling for Graph Neural Networks

arXiv: https://arxiv.org/abs/2209.03473 · HTML: https://mlsanity.com/paper/2209.03473/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 56 references that are in the map.
- First posted on arXiv 2 Sep 2022.

## Builds on (most cited first, 30 of 33)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs](https://mlsanity.com/paper/1704.02901/) (2017)
- [Diffusion-Convolutional Neural Networks](https://mlsanity.com/paper/1511.02136/) (2015)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels](https://mlsanity.com/paper/1711.08920/) (2017)
- [ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations](https://mlsanity.com/paper/1911.07979/) (2019)
- [Higher-Order Explanations of Graph Neural Networks via Relevant Walks](https://mlsanity.com/paper/2006.03589/) (2020)
- [Accurate Learning of Graph Representations with Graph Multiset Pooling](https://mlsanity.com/paper/2102.11533/) (2021)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [Graph Convolutional Networks with EigenPooling](https://mlsanity.com/paper/1904.13107/) (2019)
- [Rethinking pooling in graph neural networks](https://mlsanity.com/paper/2010.11418/) (2020)
- [Edge Contraction Pooling for Graph Neural Networks](https://mlsanity.com/paper/1905.10990/) (2019)
- [Higher-Order Attribute-Enhancing Heterogeneous Graph Neural Networks](https://mlsanity.com/paper/2104.07892/) (2021)
- [Scalable motif-aware graph clustering](https://mlsanity.com/paper/1606.06235/) (2016)
- [Hierarchical Adaptive Pooling by Capturing High-order Dependency for Graph Representation Learning](https://mlsanity.com/paper/2104.05960/) (2021)
- [Graph Pooling via Coarsened Graph Infomax](https://mlsanity.com/paper/2105.01275/) (2021)
- [Clique pooling for graph classification](https://mlsanity.com/paper/1904.00374/) (2019)
- [Link Prediction via Higher-Order Motif Features](https://mlsanity.com/paper/1902.06679/) (2019)
- [Higher-Order Label Homogeneity and Spreading in Graphs](https://mlsanity.com/paper/2002.07833/) (2020)
- [Higher-order Graph Convolutional Networks](https://mlsanity.com/paper/1809.07697/) (2018)

## Built on by (most cited first, 26 of 26)

- [Explaining the Explainers in Graph Neural Networks: a Comparative Study](https://mlsanity.com/paper/2210.15304/) (2022)
- [DeepRicci: Self-supervised Graph Structure-Feature Co-Refinement for Alleviating Over-squashing](https://mlsanity.com/paper/2401.12780/) (2024)
- [Contrastive Graph Clustering in Curvature Spaces](https://mlsanity.com/paper/2305.03555/) (2023)
- [Gegenbauer Graph Neural Networks for Time-varying Signal Reconstruction](https://mlsanity.com/paper/2403.19800/) (2024)
- [Bridged-GNN: Knowledge Bridge Learning for Effective Knowledge Transfer](https://mlsanity.com/paper/2308.09499/) (2023)
- [Graph Pooling via Ricci Flow](https://mlsanity.com/paper/2407.04236/) (2024)
- [Transformer-Based Hierarchical Clustering for Brain Network Analysis](https://mlsanity.com/paper/2305.04142/) (2023)
- [Total Variation Graph Neural Networks](https://mlsanity.com/paper/2211.06218/) (2022)
- [A Comprehensive Graph Pooling Benchmark: Effectiveness, Robustness and Generalizability](https://mlsanity.com/paper/2406.09031/) (2024)
- [PhAST: Physics-Aware, Scalable, and Task-specific GNNs for Accelerated Catalyst Design](https://mlsanity.com/paper/2211.12020/) (2022)
- [MaxCutPool: differentiable feature-aware Maxcut for pooling in graph neural networks](https://mlsanity.com/paper/2409.05100/) (2024)
- [Time-varying Signals Recovery via Graph Neural Networks](https://mlsanity.com/paper/2302.11313/) (2023)
- [On Exploring Node-feature and Graph-structure Diversities for Node Drop Graph Pooling](https://mlsanity.com/paper/2306.12726/) (2023)
- [Graph Parsing Networks](https://mlsanity.com/paper/2402.14393/) (2024)
- [From GNNs to Trees: Multi-Granular Interpretability for Graph Neural Networks](https://mlsanity.com/paper/2505.00364/) (2025)
- [Differentiable Cluster Graph Neural Network](https://mlsanity.com/paper/2405.16185/) (2024)
- [Graph Neural Network Generalization with Gaussian Mixture Model Based Augmentation](https://mlsanity.com/paper/2411.08638/) (2024)
- [BN-Pool: Bayesian Nonparametric Pooling for Graphs](https://mlsanity.com/paper/2501.09821/) (2025)
- [Torch Geometric Pool: the PyTorch library for pooling in Graph Neural Networks](https://mlsanity.com/paper/2512.12642/) (2025)
- [Higher-order Sparse Convolutions in Graph Neural Networks](https://mlsanity.com/paper/2302.10505/) (2023)
- [Higher-Order GNNs Meet Efficiency: Sparse Sobolev Graph Neural Networks](https://mlsanity.com/paper/2411.04570/) (2024)
- [Beyond the Academic Monoculture: A Unified Framework and Industrial Perspective for Attributed Graph Clustering](https://mlsanity.com/paper/2603.20829/) (2026)
- [Efficient Knowledge Tracing Leveraging Higher-Order Information in Integrated Graphs](https://mlsanity.com/paper/2507.18668/) (2025)
- [GraphPPD: Posterior Predictive Modelling for Graph-Level Inference](https://mlsanity.com/paper/2508.16995/) (2025)
- [Benchmark-Ready 3D Anatomical Shape Classification](https://mlsanity.com/paper/2511.01613/) (2025)
- [Beyond Convolution: Advancing Hypergraph Neural Networks with Hypergraph U-Nets](https://mlsanity.com/paper/2606.09051/) (2026)

## Abstract (arXiv)

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.