# Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2019.

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

- [Energy Transformer](https://mlsanity.com/paper/2302.07253/) (2023)
- [Understanding Pooling in Graph Neural Networks](https://mlsanity.com/paper/2110.05292/) (2021)
- [Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities](https://mlsanity.com/paper/2204.07321/) (2022)
- [The expressive power of pooling in Graph Neural Networks](https://mlsanity.com/paper/2304.01575/) (2023)
- [Learning Hierarchical Graph Neural Networks for Image Clustering](https://mlsanity.com/paper/2107.01319/) (2021)
- [Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks](https://mlsanity.com/paper/2207.08629/) (2022)
- [Graph-based Time Series Clustering for End-to-End Hierarchical Forecasting](https://mlsanity.com/paper/2305.19183/) (2023)
- [Graph-based Forecasting with Missing Data through Spatiotemporal Downsampling](https://mlsanity.com/paper/2402.10634/) (2024)
- [Graph Neural Networks in Particle Physics: Implementations, Innovations, and Challenges](https://mlsanity.com/paper/2203.12852/) (2022)
- [Attending to Topological Spaces: The Cellular Transformer](https://mlsanity.com/paper/2405.14094/) (2024)
- [Pyramidal Reservoir Graph Neural Network](https://mlsanity.com/paper/2104.04710/) (2021)
- [Graph Pooling via Ricci Flow](https://mlsanity.com/paper/2407.04236/) (2024)
- [GLAN: A Graph-based Linear Assignment Network](https://mlsanity.com/paper/2201.02057/) (2022)
- [Generalizing Downsampling from Regular Data to Graphs](https://mlsanity.com/paper/2208.03523/) (2022)
- [Revisiting Initializing Then Refining: An Incomplete and Missing Graph Imputation Network](https://mlsanity.com/paper/2302.07524/) (2023)
- [Adaptive Hierarchical SpatioTemporal Network for Traffic Forecasting](https://mlsanity.com/paper/2306.09386/) (2023)
- [MaxCutPool: differentiable feature-aware Maxcut for pooling in graph neural networks](https://mlsanity.com/paper/2409.05100/) (2024)
- [Geometry-Aware Edge Pooling for Graph Neural Networks](https://mlsanity.com/paper/2506.11700/) (2025)
- [On Exploring Node-feature and Graph-structure Diversities for Node Drop Graph Pooling](https://mlsanity.com/paper/2306.12726/) (2023)
- [Unsupervised Graph Clustering with Deep Structural Entropy](https://mlsanity.com/paper/2505.14040/) (2025)
- [Supervised Contrastive Learning with Structure Inference for Graph Classification](https://mlsanity.com/paper/2203.07691/) (2022)
- [Maximal Independent Vertex Set applied to Graph Pooling](https://mlsanity.com/paper/2208.01648/) (2022)
- [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)
- [Superpixel perception graph neural network for intelligent defect detection of aero-engine blade](https://mlsanity.com/paper/2210.07539/) (2022)
- [Large Engagement Networks for Classifying Coordinated Campaigns and Organic Twitter Trends](https://mlsanity.com/paper/2503.00599/) (2025)
- [The Role of Node Features in Graph Pooling](https://mlsanity.com/paper/2605.06250/) (2026)
- [Geometric Flow enhanced Graph Coarsening](https://mlsanity.com/paper/2609.14962/) (2026)
- [Maximal Independent Sets for Pooling in Graph Neural Networks](https://mlsanity.com/paper/2307.13011/) (2023)
- [A roadmap for curvature-based geometric data analysis and learning](https://mlsanity.com/paper/2510.22599/) (2025)

## Abstract (arXiv)

In graph neural networks (GNNs), pooling operators compute local summaries of input graphs to capture their global properties, and they are fundamental for building deep GNNs that learn hierarchical representations. In this work, we propose the Node Decimation Pooling (NDP), a pooling operator for GNNs that generates coarser graphs while preserving the overall graph topology. During training, the GNN learns new node representations and fits them to a pyramid of coarsened graphs, which is computed offline in a pre-processing stage. NDP consists of three steps. First, a node decimation procedure selects the nodes belonging to one side of the partition identified by a spectral algorithm that approximates the maxcut solution. Afterwards, the selected nodes are connected with Kron reduction to form the coarsened graph. Finally, since the resulting graph is very dense, we apply a sparsification procedure that prunes the adjacency matrix of the coarsened graph to reduce the computational cost in the GNN. Notably, we show that it is possible to remove many edges without significantly altering the graph structure. Experimental results show that NDP is more efficient compared to state-of-the-art graph pooling operators while reaching, at the same time, competitive performance on a significant variety of graph classification tasks.