# The expressive power of pooling in Graph Neural Networks

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 50 references that are in the map.
- First posted on arXiv 4 Apr 2023.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [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)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Understanding Attention and Generalization in Graph Neural Networks](https://mlsanity.com/paper/1905.02850/) (2019)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations](https://mlsanity.com/paper/1911.07979/) (2019)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Accurate Learning of Graph Representations with Graph Multiset Pooling](https://mlsanity.com/paper/2102.11533/) (2021)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [Rethinking pooling in graph neural networks](https://mlsanity.com/paper/2010.11418/) (2020)
- [Understanding Pooling in Graph Neural Networks](https://mlsanity.com/paper/2110.05292/) (2021)
- [Global Explainability of GNNs via Logic Combination of Learned Concepts](https://mlsanity.com/paper/2210.07147/) (2022)
- [Memory-Based Graph Networks](https://mlsanity.com/paper/2002.09518/) (2020)
- [Edge Contraction Pooling for Graph Neural Networks](https://mlsanity.com/paper/1905.10990/) (2019)

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

- [Graph Deep Learning for Time Series Forecasting](https://mlsanity.com/paper/2310.15978/) (2023)
- [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)
- [Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNs](https://mlsanity.com/paper/2406.15156/) (2024)
- [Understanding Virtual Nodes: Oversquashing and Node Heterogeneity](https://mlsanity.com/paper/2405.13526/) (2024)
- [Graph Pooling via Ricci Flow](https://mlsanity.com/paper/2407.04236/) (2024)
- [Boosting Graph Pooling with Persistent Homology](https://mlsanity.com/paper/2402.16346/) (2024)
- [Graph Coarsening with Message-Passing Guarantees](https://mlsanity.com/paper/2405.18127/) (2024)
- [A Comprehensive Graph Pooling Benchmark: Effectiveness, Robustness and Generalizability](https://mlsanity.com/paper/2406.09031/) (2024)
- [Over-squashing in Spatiotemporal Graph Neural Networks](https://mlsanity.com/paper/2506.15507/) (2025)
- [Curvature-based Pooling within Graph Neural Networks](https://mlsanity.com/paper/2308.16516/) (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)
- [Feudal Graph Reinforcement Learning](https://mlsanity.com/paper/2304.05099/) (2023)
- [Towards Efficient Training of Graph Neural Networks: A Multiscale Approach](https://mlsanity.com/paper/2503.19666/) (2025)
- [Bridging Theory and Practice in Link Representation with Graph Neural Networks](https://mlsanity.com/paper/2506.24018/) (2025)
- [xAI-Drop: Don't Use What You Cannot Explain](https://mlsanity.com/paper/2407.20067/) (2024)
- [Taxonomy of reduction matrices for Graph Coarsening](https://mlsanity.com/paper/2506.11743/) (2025)
- [The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networks](https://mlsanity.com/paper/2310.01144/) (2023)
- [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)
- [Edge-Based Graph Component Pooling](https://mlsanity.com/paper/2409.11856/) (2024)
- [Towards Systematic Generalization for Power Grid Optimization Problems](https://mlsanity.com/paper/2605.02026/) (2026)
- [The Role of Node Features in Graph Pooling](https://mlsanity.com/paper/2605.06250/) (2026)
- [Analysing the Behaviour of Tree-Based Neural Networks in Regression Tasks](https://mlsanity.com/paper/2406.11437/) (2024)
- [Graph Classification with GNNs: Optimisation, Representation and Inductive Bias](https://mlsanity.com/paper/2408.09266/) (2024)
- [GINTRIP: Interpretable Temporal Graph Regression using Information bottleneck and Prototype-based method](https://mlsanity.com/paper/2409.10996/) (2024)
- [Reducing Smoothness with Expressive Memory Enhanced Hierarchical Graph Neural Networks](https://mlsanity.com/paper/2504.00349/) (2025)
- [Self-Supervised Graph Learning via Spectral Bootstrapping and Laplacian-Based Augmentations](https://mlsanity.com/paper/2506.20362/) (2025)
- [A roadmap for curvature-based geometric data analysis and learning](https://mlsanity.com/paper/2510.22599/) (2025)

## Abstract (arXiv)

In Graph Neural Networks (GNNs), hierarchical pooling operators generate local summaries of the data by coarsening the graph structure and the vertex features. While considerable attention has been devoted to analyzing the expressive power of message-passing (MP) layers in GNNs, a study on how graph pooling affects the expressiveness of a GNN is still lacking. Additionally, despite the recent advances in the design of pooling operators, there is not a principled criterion to compare them. In this work, we derive sufficient conditions for a pooling operator to fully preserve the expressive power of the MP layers before it. These conditions serve as a universal and theoretically grounded criterion for choosing among existing pooling operators or designing new ones. Based on our theoretical findings, we analyze several existing pooling operators and identify those that fail to satisfy the expressiveness conditions. Finally, we introduce an experimental setup to verify empirically the expressive power of a GNN equipped with pooling layers, in terms of its capability to perform a graph isomorphism test.