mlsanityData to 7 Oct 2026

The expressive power of pooling in Graph Neural Networks

arXiv 2304.01575 ↗First posted 4 Apr 2023cs.LGcited by 35

Not on the map. Why?

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.

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

Builds on

38 of 50 references.

References · 38

  1. 2018How Powerful are Graph Neural Networks?cited by 4,355
  2. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  3. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  4. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  5. 2017Deep Setscited by 1,394
  6. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  7. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  8. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 786
  9. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  10. 2020Benchmarking Graph Neural Networkscited by 672
  11. 2019Graph U-Netscited by 489
  12. 2020Parameterized Explainer for Graph Neural Networkcited by 423
26 more
  1. 2019Self-Attention Graph Poolingcited by 421
  2. 2019Provably Powerful Graph Networkscited by 385
  3. 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
  4. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  5. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  6. 2020Random Features Strengthen Graph Neural Networkscited by 184
  7. 2019Understanding Attention and Generalization in Graph Neural Networkscited by 169
  8. 2020Graph Clustering with Graph Neural Networkscited by 163
  9. 2019ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representationscited by 156
  10. 2021Equivariant Subgraph Aggregation Networkscited by 154
  11. 2021Accurate Learning of Graph Representations with Graph Multiset Poolingcited by 120
  12. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  13. 2020Scalable Graph Neural Networks via Bidirectional Propagationcited by 87
  14. 2020Rethinking pooling in graph neural networkscited by 73
  15. 2021Understanding Pooling in Graph Neural Networkscited by 69
  16. 2022Global Explainability of GNNs via Logic Combination of Learned Conceptscited by 64
  17. 2020Memory-Based Graph Networkscited by 56
  18. 2019Edge Contraction Pooling for Graph Neural Networkscited by 53
  19. 2020Path Integral Based Convolution and Pooling for Graph Neural Networkscited by 35
  20. 2022Explaining the Explainers in Graph Neural Networks: a Comparative Studycited by 34
  21. 2019Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Poolingcited by 30
  22. 2015Graph Isomorphism in Quasipolynomial Timecited by 19
  23. 2021Do We Need Anisotropic Graph Neural Networks?cited by 18
  24. 2019A Non-Negative Factorization approach to node pooling in Graph Convolutional Neural Networkscited by 14
  25. 2021Pyramidal Reservoir Graph Neural Networkcited by 10
  26. 2022Explainability in subgraphs-enhanced Graph Neural Networkscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 13; 2025: 11; 2026: 6.

35 papers.

Sort:

  1. 2023Graph Deep Learning for Time Series Forecastingcited by 26
  2. 2023Graph-based Time Series Clustering for End-to-End Hierarchical Forecastingcited by 16
  3. 2024Graph-based Forecasting with Missing Data through Spatiotemporal Downsamplingcited by 15
  4. 2024Understanding Virtual Nodes: Oversquashing and Node Heterogeneitycited by 14
  5. 2024Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNscited by 14
  6. 2024Graph Pooling via Ricci Flowcited by 10
  7. 2024Boosting Graph Pooling with Persistent Homologycited by 9
  8. 2024Graph Coarsening with Message-Passing Guaranteescited by 9
  9. 2024A Comprehensive Graph Pooling Benchmark: Effectiveness, Robustness and Generalizabilitycited by 6
  10. 2025Over-squashing in Spatiotemporal Graph Neural Networkscited by 6
  11. 2023Curvature-based Pooling within Graph Neural Networkscited by 5
  12. 2024MaxCutPool: differentiable feature-aware Maxcut for pooling in graph neural networkscited by 5
23 more
  1. 2025Geometry-Aware Edge Pooling for Graph Neural Networkscited by 5
  2. 2025Towards Efficient Training of Graph Neural Networks: A Multiscale Approachcited by 4
  3. 2025Bridging Theory and Practice in Link Representation with Graph Neural Networkscited by 4
  4. 2023Feudal Graph Reinforcement Learningcited by 3
  5. 2024xAI-Drop: Don't Use What You Cannot Explaincited by 3
  6. 2025Taxonomy of reduction matrices for Graph Coarseningcited by 3
  7. 2023The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networkscited by 2
  8. 2025BN-Pool: Bayesian Nonparametric Pooling for Graphscited by 2
  9. 2025Torch Geometric Pool: the PyTorch library for pooling in Graph Neural Networkscited by 2
  10. 2024Edge-Based Graph Component Poolingcited by 1
  11. 2026Towards Systematic Generalization for Power Grid Optimization Problemscited by 1
  12. 2024Analysing the Behaviour of Tree-Based Neural Networks in Regression Taskscited by 0
  13. 2024Graph Classification with GNNs: Optimisation, Representation and Inductive Biascited by 0
  14. 2024GINTRIP: Interpretable Temporal Graph Regression using Information bottleneck and Prototype-based methodcited by 0
  15. 2025Reducing Smoothness with Expressive Memory Enhanced Hierarchical Graph Neural Networkscited by 0
  16. 2025Self-Supervised Graph Learning via Spectral Bootstrapping and Laplacian-Based Augmentationscited by 0
  17. 2025A roadmap for curvature-based geometric data analysis and learningcited by 0
  18. 2025Multi-Scale Protein Structure Modelling with Geometric Graph U-Netscited by 0
  19. 2026The Role of Node Features in Graph Poolingcited by 0
  20. 2026Graph Hierarchical Recurrence for Long-Range Generalizationcited by 0
  21. 2026Beyond Convolution: Advancing Hypergraph Neural Networks with Hypergraph U-Netscited by 0
  22. 2026Global to Local: Topology-Preserving Adaptive Graph Pooling via Granular-Ballcited by 0
  23. 2026StegGNN: Learning Graphical Representation for Image Steganographycited by 0