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
Figure 1: Motivation and overview. Hierarchical tasks are challenging to solve for node-based MPNNs and GTs. We introduce PSA-GNN, a framework to process meaningful substructures exposed by graph pooling that is more expressive and improves performance on hierarchical graph-level tasks.
Figure 2: Computational flow of PSA-GNN. We pre-compute the subgraph policy and initialize node features in subgraph space. Each layer then updates these representations by combining message passing on the original graph with message passing inside each induced subgraph. Finally, node representations are aggregated within each subgraph and passed to a DeepSets-style readout.
Figure 3: Examples from two synthetic datasets. Left: Macro-Hierarchies , where the class distinction is given by ring versus bipartite higher-level structure. Right: Granular-Hierarchies , where the class distinction is given by even versus uneven cluster sizes.
Figure 4: Structural characterization of real-world benchmarks using nested SBM fits. For each graph, we fit a degree-corrected nested SBM and record the number of detected substructures at the finest inferred level (left axis) and the detected substructure depth (right axis).
Figure 5: Results on the synthetic hierarchical benchmarks. We compare Pool-GNN, IP-GNN, and PSA-GNN against flat MPNN and GT baselines across representative structure-based schemes.
Hierarchical Structure
Flat Structure
Model
Subgraph Policy
Avg. Rank ( ↓ )
COLLAB Acc. [%] ( ↑ )
REDDIT-5K Acc. [%] ( ↑ )
REDDIT-12K Acc. [%] ( ↑ )
MalNet Acc. [%] ( ↑ )
NCI1 Acc. [%] ( ↑ )
ZINC MAE ( ↓ )
PSA-GNN
CliquePool
78.1 ± 1.3 ⋆
55.0 ± 0.8
47.8 ± 1.4
90.6 ± 2.4
81.5 ± 2.5
0.182 ± 0.008
CurvPool
1.36
76.8 ± 1.5 ⋆
54.9 ± 1.7
50.1 ± 1.7 ⋆
92.0 ± 1.9
81.2 ± 1.6
0.177 ± 0.005
Leiden
76.4 ± 2.2
55.3 ± 2.1 ⋆
50.0 ± 1.3 ⋆
91.1 ± 1.4 ⋆
80.0 ± 2.5
0.213 ± 0.007 ⋆
IP-GNN
CliquePool
75.0 ± 2.3
53.3 ± 3.4
45.1 ± 2.1
91.7 ± 1.7
80.6 ± 2.1
0.183 ± 0.004
CurvPool
2.33
77.4 ± 0.9
52.6 ± 3.3
42.0 ± 2.5
89.3 ± 2.0
80.3 ± 1.9
0.184 ± 0.005
Table 1: Results on real-world benchmarks. Best overall result per dataset is highlighted in brown , second best in purple . Among PSA-GNN , IP-GNN, and Pool-GNN, the best method for a given subgraph policy π is shown bolded . A ⋆ indicates that PSA-GNN significantly outperforms the matched Pool-GNN under a two-sided Welch test ( p<0.05 , unadjusted). The Avg. Rank reports the average rank of each architecture level across matched dataset–policy comparisons among PSA-GNN , IP-GNN, and Pool-GNN. Dense pooling schemes do not scale and ASAPool cannot use edge features by default.
Figure 6: Relative gain over MPNN. Bars show group means; points show individual datasets. Positive values indicate improvement over MPNN.
Model
Subgraph Policy
Flat CO-ER MAE ( ↓ )
Hierarchical CO-RB MAE ( ↓ )
PSA-GNN
CliquePool
0.5722 ± 0.0085
1.0108 ± 0.0145
CurvPool
0.5917 ± 0.0177
0.9345 ± 0.0649
Leiden
0.6015 ± 0.0145
1.2551 ± 0.0598
Baseline
MPNN (GIN)
0.5844 ± 0.0347
1.4251 ± 0.0180
Avg. Gain vs. MPNN
-0.70%
+25.14%
Table 2: Test MAE on GraphBench CO benchmarks. We compare CO-ER (flat graphs) and CO-RB (with hierarchical structure) on 10K-graph subsets.
Figure 7: Scalability of subgraph policies. We compare the total number of subgraph-node occurrences ∑i∣Vi∣ induced by different policies. Observations are grouped into 20 bins and averaged for readability; very large REDDIT graphs are omitted from the plot.
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 8: Additional example for Proposition 3. The Shrikhande graph and the 4×4 Rook graph are not distinguished by immediate coarsening under this Leiden partition, but their pooling-induced subgraphs exhibit different internal degree signatures that can be exploited by IP-GNN or PSA-GNN .
Figure 9: Strict-separation example for padded pooled-substructure processing. The two original graphs G and H are both 4 -regular and use the same hard partition into two diamond subgraphs. Under the unpadded policy π , both graphs yield the same subgraphs and coarsened graph with six crossing edges, so IP-GNN cannot distinguish them. Under the padded policy π^ , however, the A -subgraphs expose different crossing-edge incidence patterns. In G , the core nodes 1 and 3 see different halo-neighbor types and split after two 1 -WL refinement steps; while they remain symmetric in H .
Figure 10: Number of BREC pairs distinguished by each architecture-policy combination, out of 400 total. Following the official BREC protocol, we report the best score achieved over three seeds.
Figure 11: Results on the synthetic hierarchical benchmarks for learned pooling operators. We compare a range of popular learned pooling operators as well as their randomized implementations.
Granular-Hierarchies
Macro-Hierarchies
Feature Level
PSA-GNN (Leiden)
MPNN (GIN)
Gap
PSA-GNN (Leiden)
MPNN (GIN)
Gap
Featureless
95.70 ± 0.56
53.73 ± 1.84
+41.97
99.06 ± 0.36
52.50 ± 0.64
+46.56
μ=1
95.10 ± 0.36
49.63 ± 2.15
+45.47
99.37 ± 0.31
49.47 ± 1.00
+49.90
μ=5
95.33 ± 0.47
57.07 ± 2.74
+38.26
99.23 ± 0.25
51.40 ± 2.49
+47.83
μ=10
95.97 ± 0.47
66.20 ± 1.32
+29.77
99.53 ± 0.06
49.60 ± 2.55
+49.93
μ=50
97.40 ± 0.90
92.67 ± 0.60
+4.73
99.40 ± 0.26
50.30 ± 2.95
+49.10
Appendix
Table 3: Impact of contextual node features on synthetic hierarchy benchmarks. Test accuracy (mean ± standard deviation) on the medium-difficulty Granular-Hierarchies and Macro-Hierarchies datasets with F=16 contextual node features. The gap denotes the accuracy difference in percentage points between PSA-GNN and the GIN baseline.
Dataset
Task
# Graphs
# Labels
Node feat. dim
Edge feat. dim
Avg. # Nodes
Avg. # Edges
Avg. Degree
Hierarchical Structure
COLLAB
Classification
5,000
3
0
0
74$\pm$62
2,457$\pm$6,439
37.4$\pm$44.0
REDDIT-5K
Classification
5,000
5
0
0
509$\pm$453
595$\pm$567
2.3$\pm$0.2
REDDIT-12K
Classification
11,929
11
0
0
391$\pm$429
457$\pm$518
2.3$\pm$0.2
MalNet
Classification
5,000
5
0
0
1,522$\pm$1,650
2,859$\pm$3,205
3.0$\pm$1.2
CO-RB
Regression
10,000
1
0
0
241$\pm$28
4,497$\pm$1,504
36.8$\pm$9.9
Appendix
Table 4: Summary statistics of the benchmark datasets. Dataset-level statistics are reported as mean ± standard deviation over graphs where applicable.
Total Depth
IP-GNN
Pool-GNN
Hierarchical
Dataset
pre
within
post
pre
within
post
pre
between
post
Hierarchical Structure
COLLAB
6
2
2
2
3
0
3
2
2x2
0
REDDIT-12K
6
2
2
2
3
0
3
2
2x2
0
REDDIT-5K
6
2
2
2
3
0
3
2
2x2
0
MalNet
6
2
2
2
3
0
3
2
2x2
0
Appendix
Table 5: Layer allocations across datasets and model families. For IP-GNN and Pool-GNN, layers are split into pre , within , and post ; for Hierarchical , they are split into pre , between , and post . PSA-GNN and any MPNN baselines always use the full stack, i.e., total depth. between layers are multiplied by the number of pooling steps.
Dataset
# Layers
Max Epochs
Batch Size
Learning Rate
Weight Decay
Layers Dropout
Head Dropout
Early stop Patience
# Seeds
Hierarchical Structure
COLLAB
6
300
32
10−3
0
0.05
0.10
50
5
REDDIT-12K
6
300
16
10−3
0
0.05
0.10
50
5
REDDIT-5K
6
300
16
10−3
0
0.05
0.10
50
5
MalNet
6
300
16
10−3
0
0.05
0.10
50
5
CO-RB
6
300
32
10−3
10−5
0.00
0.10
50
3
Appendix
Table 6: Dataset-specific training and architecture hyperparameters. Key hyperparameters used for each benchmark dataset. For BREC, no patience-based early stopping is used; instead, training stops once the loss falls below 0.2 or after 40 epochs.
Hierarchical Structure
Flat Structure
Model
Subgraph Policy
COLLAB Acc. [%] ( ↑ )
REDDIT-12K Acc. [%] ( ↑ )
MalNet Acc. [%] ( ↑ )
NCI1 Acc. [%] ( ↑ )
ZINC MAE ( ↓ )
PSA-GNN
CliquePool
78.1 ± 1.3
47.0 ± 3.8
90.6 ± 2.4
81.5 ± 2.0
0.181 ± 0.005
- padding
-4.4
+0.8
+1.0
-0.6
-0.002
- node markings
-2.3
+0.8
+1.0
+0.0
+0.010
CurvPool
76.8 ± 1.5
49.3 ± 1.7
92.0 ± 1.9
81.2 ± 1.6
0.175 ± 0.005
- padding
-0.5
-0.3
-1.2
-0.8
+0.003
Appendix
Table 7: Padding and node-marking impact for PSA-GNN on real-world datasets. The base row is the mean-aggregation configuration with node markings enabled and default padding. Italic rows report the change relative to the base. For accuracy metrics, positive values indicate improvement; for ZINC, negative values indicate improvement because lower MAE is better. Models without padding also contain no node markings, as there is no core vs. halo distinction. Empty cells indicate that a configuration was not tested due to computational limitations.
Model
Subgraph Policy
NCI1
REDDIT-12K
PSA-GNN
CliquePool
2.47 ± 0.12
16.11 ± 0.89
CurvPool
2.75 ± 0.18
18.95 ± 2.88
Leiden
2.45 ± 0.09
17.11 ± 0.75
IP-GNN
CliquePool
2.15 ± 0.17
15.04 ± 2.62
CurvPool
2.08 ± 0.10
15.05 ± 1.30
Leiden
2.04 ± 0.04
13.79 ± 1.49
Appendix
Table 8: Training time per epoch on NCI1 and REDDIT-12K. Mean training time in seconds per epoch ( ± standard deviation) for the datasets considered in Figure 7.
Figure 12: Number of BREC graph pairs (out of 400) distinguished by each architecture-policy combination. We report the best score achieved over three seeds.
Figure 13: Results on the synthetic hierarchical benchmarks for additional subgraph policies. We compare immediate coarsening (Pool-GNN), the within-subgraph baseline (IP-GNN), and the full pooled-subgraph model ( PSA-GNN ) across three additional subgraph policies.
Hierarchical Structure
Flat Structure
Model
Subgraph Policy
Avg. Rank ( ↓ )
COLLAB Acc. [%] ( ↑ )
REDDIT-12K Acc. [%] ( ↑ )
MalNet-T Acc. [%] ( ↑ )
NCI1 Acc. [%] ( ↑ )
ZINC MAE ( ↓ )
PSA-GNN
CliquePool
1.34
78.1 ± 1.3
47.8 ± 1.4
90.6 ± 2.4
81.5 ± 2.5
0.182 ± 0.008
CliquePool-max
78.9 ± 0.7
51.2 ± 0.0
92.3 ± 1.6
80.9 ± 1.6
0.179 ± 0.003
CurvPool
76.8 ± 1.5
50.1 ± 1.7
92.0 ± 1.9
81.2 ± 1.6
0.177 ± 0.005
Leiden
76.4 ± 2.2
50.0 ± 1.3
91.1 ± 1.4
80.0 ± 2.5
0.213 ± 0.007
ACL
–
–
92.1 ± 0.9
80.9 ± 2.8
0.189 ± 0.002
Appendix
Table 9: Results on real-world benchmark datasets. The best overall result per dataset is shown in brown , second best in purple . Among PSA-GNN , IP-GNN, and Pool-GNN, the best method for a given subgraph policy π is shown in bold . The Avg. Rank column reports the average rank of these three architecture levels across all available policy–dataset comparisons.
Institute Multiscale Matter and Systems, Ewha Womans University, Seoul, Republic of Korea · Division of AI Data Convergence, Hankuk University of Foreign Studies, Yongin-si, Gyeonggi-do, Republic of Korea