Hierarchical Graph Representation Learning with Pooling-Induced Substructures

Luca Sbicego, Xiaowen Dong, Dorina ThanouarXiv 2026 · arXiv

TL;DR

PSA-GNN (Pooled-Substructure-Aware GNN) is a new framework that boosts hierarchical graph learning by explicitly processing the internal structures of clusters uncovered during pooling, rather than discarding them through immediate coarsening. By treating these clusters as meaningful subgraphs, the model achieves higher theoretical expressivity and significantly outperforms standard pooling methods on tasks where hierarchical organization is key to the solution.

What Problem Does This Paper Address?

Standard Graph Neural Networks (GNNs) are great at capturing local patterns, but they often struggle with tasks that require reasoning over larger, hierarchical structures—like communities in a social network or functional modules in a software call graph.

To solve this, researchers typically use graph pooling, which coarsens a graph by grouping nodes into "supernodes." However, this process is often "lossy." Most existing methods immediately collapse these groups into single points, effectively throwing away the rich internal structure of the clusters they just found. Furthermore, the field has lacked principled ways to evaluate these models because standard benchmarks don't always have clear hierarchical signals. This paper tackles both the architectural gap (how to preserve structure) and the empirical gap (how to measure it).

Methods

The authors introduce PSA-GNN, which shifts the perspective of pooling from a simple "coarsening" step to a "substructure discovery" step.

Instead of just shrinking the graph, PSA-GNN treats each pooled cluster as an induced subgraph. The architecture uses a dual-branch approach at each layer:

  1. Subgraph Branch: A shared encoder processes each induced subgraph independently, capturing its internal topology.
  2. Graph Branch: Information is scattered back to the original graph space and processed using standard message passing to allow information to flow between different subgraphs.
PSA-GNN treats clusters as subgraphs rather than collapsing them into single supernodes.

A key innovation is the use of padded subgraph policies. By including "halo" nodes (neighbors just outside the cluster boundary), the model allows local subgraph updates to access boundary context, which the authors prove increases the model's expressive power in the Weisfeiler-Lehman (WL) sense.

Datasets

The paper introduces two new synthetic benchmarks designed to isolate hierarchical reasoning:

  • MACRO-HIERARCHIES: Tests if a model can distinguish between different high-level connectivity patterns (e.g., a ring vs. a bipartite arrangement of communities).
  • GRANULAR-HIERARCHIES: Tests if a model can reason about the size distribution of clusters (e.g., equally sized clusters vs. a mix of small and large ones).
Examples of the new synthetic datasets showing macro-level patterns and cluster size distributions.

For real-world evaluation, they use a diverse set of benchmarks including COLLAB, REDDIT-5K/12K, MalNet-Tiny, NCI1, and ZINC. They also utilize combinatorial optimization tasks (CO-ER and CO-RB) to further validate performance on structured vs. flat graphs.

Key Insights and Ideas

  • Don't Collapse Too Early: The "aha moment" is that the internal edges of a cluster are just as important as the fact that the cluster exists. By keeping these edges active during computation, PSA-GNN preserves information that standard pooling discards.
  • Hierarchy is a Spectrum: Not all graph datasets are hierarchical. The authors used Nested Stochastic Block Models (SBMs) to "probe" datasets, discovering that while MalNet and Reddit are deeply hierarchical, molecular datasets like ZINC are structurally "flat."
  • Expressivity Gains: The authors provide a theoretical hierarchy showing that PSA-GNN is strictly more expressive than standard pooling. This isn't just an empirical trick; it's a fundamental improvement in what the model can distinguish.
  • Predictive Probing: Their SBM-based metric successfully predicts when PSA-GNN will shine. The model shows the most significant gains on datasets that the probe identifies as having rich hierarchical depth.
Structural characterization shows that some datasets are "deeper" than others, correlating with where PSA-GNN performs best.

Key Results

  • Superior Ranking: Across real-world benchmarks, PSA-GNN achieved an average rank of 1.36, significantly better than the within-subgraph baseline (2.33) and standard pooling (2.31).
  • Hierarchical Advantage: On the hierarchical CO-RB dataset, PSA-GNN achieved a +25.14% gain over a flat MPNN baseline, whereas it showed a slight negative gain on the flat CO-ER dataset.
  • Robustness: In synthetic tasks, as the hierarchical signal was obscured by noise, PSA-GNN's performance degraded much more slowly than standard GNNs or Transformers, which struggled to implicitly infer the higher-order organization.
PSA-GNN consistently outperforms baselines as hierarchical tasks become more difficult.

Limitations and Future Work

  • Predictive vs. Structural Hierarchy: The current SBM probe identifies structural hierarchy, but it doesn't yet determine if that hierarchy is actually predictive of the specific task label.
  • Policy Dependence: The performance of PSA-GNN still depends on the choice of the underlying pooling policy (e.g., Leiden vs. CliquePool). There is no "one size fits all" policy that dominates every dataset.
  • Computational Overhead: While more scalable than generic subgraph GNNs (like those using egonets), PSA-GNN still incurs a policy-dependent overhead compared to simple flat MPNNs.

Future work could involve learning the subgraph policies end-to-end while maintaining the substructure-aware processing that makes this framework powerful.

Summary updated

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/.
BibTeX
@misc{sbicego2026hierarchical,
  author = {Luca Sbicego and Xiaowen Dong and Dorina Thanou},
  title = {{Hierarchical Graph Representation Learning with Pooling-Induced Substructures}},
  year = {2026},
  eprint = {2611.14126},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.14126},
}
Figure