cs.LGNov 10, 2026

Hierarchical Graph Representation Learning with Pooling-Induced Substructures

Authors: Luca Sbicego, Xiaowen Dong, Dorina Thanou

Organizations: EPFL · University of Oxford

Abstract

Hierarchical graph-level tasks that require reasoning over substructures that extend beyond local neighborhoods are posing challenges for standard Graph Neural Networks (GNNs). While graph pooling aims to address this by coarsening graphs into hierarchical representations, existing methods often fail to explicitly preserve the substructures they induce, leading to inconsistent empirical performance. Moreover, evaluating such approaches remains challenging due to the lack of benchmarks with explicit hierarchical structure. We propose Pooled-Substructure-Aware GNNs, an approach to graph pooling that explicitly preserves and processes substructures uncovered by structure-based pooling schemes. We show that this design enhances the expressive power of pooling-based GNNs in the sense of the Weisfeiler-Lehman (WL) test. To enable principled evaluation, we introduce two new synthetic datasets with controllable hierarchical structure and propose a metric to characterize the prevalence of hierarchical patterns in real-world graph-level benchmarks. On tasks with relevant hierarchical structure, our approach outperforms matched pooling baselines, while remaining competitive on structurally simpler benchmarks. Code and datasets are publicly available at https://github.com/lsbicego/PSA-GNN/.

Figures & tables

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Graph-dependent pooling: adaptive granularity in hierarchical graph neural networks

    Oct 24, 2026Bohan Yoon, Hyejin JangMetal-Organic FrameworksGraph Pooling

  2. Hierarchical Pooling for Sheaf Neural Networks

    Jun 18, 2026Dionisia Naddeo, Carlo Abate, Pietro Liò +2Graph Neural NetworksGraph Coarsening

  3. Estimating Subgraph Importance with Structural Prior Domain Knowledge

    May 12, 2026Changhyun Kim, Seunghwan An, Jong-June JeonGraph Neural NetworksGNN Explainability