# A Comprehensive Graph Pooling Benchmark: Effectiveness, Robustness and
Generalizability

Pengyun Wang1, Junyu Luo2, Yanxin Shen3, Siyu Heng4, Xiao Luo5∗
1University of Oxford, 2Peking University, 3Nankai University,
4New York University, 5University of California, Los Angles
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Corresponding authors.

###### Abstract

Graph pooling has gained attention for its ability to obtain effective node
and graph representations for various downstream tasks. Despite the recent
surge in graph pooling approaches, there is a lack of standardized
experimental settings and fair benchmarks to evaluate their performance. To
address this issue, we have constructed a comprehensive benchmark that
includes 15 graph pooling methods and 21 different graph datasets. This
benchmark systematically assesses the performance of graph pooling methods in
three dimensions, i.e., effectiveness, robustness, and generalizability. We
first evaluate the performance of these graph pooling approaches across
different tasks including graph classification, graph regression and node
classification. Then, we investigate their performance under potential noise
attacks and out-of-distribution shifts in real-world scenarios. We also
involve detailed efficiency analysis and parameter analysis. Extensive
experiments validate the strong capability and applicability of graph pooling
approaches in various scenarios, which can provide valuable insights and
guidance for deep geometric learning research. The source code of our
benchmark is available at https://github.com/goose315/Graph_Pooling_Benchmark.

_K_ eywords Graph Pooling; Benchmark; Graph Neural Networks; Graph Machine
Learning

##  1 Introduction

Recently, graph neural networks (GNNs) have garnered significant attention
with extensive benchmarks [1, 2, 3] due to their remarkable ability to process
graph-structured data across various domains including social networks [4, 5,
6, 7], rumor detection [8, 9], biological networks [10, 11], recommender
systems [12] and community detection [13, 14]. Graph pooling approaches play a
crucial role in GNNs by enabling the hierarchical reduction of graph
representations, which is essential for capturing multi-scale structures and
long-range dependencies [15, 16, 17]. They can preserve crucial topological
semantics and relationships, which have shown effective for tasks including
graph classification, node clustering, and graph generation [15, 18, 19, 2].
In addition, by aggregating nodes and edges, graph pooling can also simplify
large-scale graphs, facilitating the application of GNNs in real-world
problems [20, 21, 22, 23, 24]. Therefore, understanding and enhancing graph
pooling approaches is the key to increasing GNN performance, driving the
progress of deep geometric learning.

In literature, existing graph pooling approaches [25, 26, 27, 28, 29, 30, 31,
32, 33, 34, 35, 36, 37, 38, 39] can be roughly divided into two categories
[40, 15], i.e., sparse pooling [25, 26, 27, 28, 29, 30, 31, 32, 33] and dense
pooling approaches [34, 35, 36, 37, 38, 39] based on the number of nodes after
pooling. Sparse pooling approaches generally keep the number of nodes as the
constant cardinality, i.e., $O(1)$ while dense pooling approaches typically
have the number of nodes proportional to the number of total nodes after
pooling [41, 40]. Even though graph pooling research is becoming increasingly
popular, there is still no standardized benchmark that allows for an impartial
and consistent comparison of various graph pooling methods. Furthermore, due
to the diversity and complexity of graph datasets, numerous experimental
settings have been used in previous studies, such as varied proportions of
training data and train/validation/test splits [8, 34, 17, 42]. As a result, a
comprehensive and publicly available benchmark of graph pooling approaches is
highly expected that can facilitate the evaluation and comparison of different
approaches, ensuring the reproducibility of results and further advancing the
area of graph machine learning.

Towards this end, we present a comprehensive graph pooling benchmark, which
includes 15 graph pooling methods and 21 datasets across different graph
machine learning problems. In particular, we extensively investigate graph
pooling approaches across three key perspectives, i.e., effectiveness,
robustness, and generalizability. To begin, we provide a fair and thorough
effectiveness comparison of existing graph pooling approaches across graph
classification, graph regression and node classification. Then, we evaluate
the robustness of graph pooling approaches under both noise attacks on graph
structures and node attributes. In addition, we study the generalizability of
different approaches under out-of-distribution shifts from both size and
density levels. Finally, we include efficiency comparison, parameter analysis
and backbone analysis for completeness.

From extensive experimental results, we have four observations as follows: (1)
Dense pooling approaches generally outperform pooling on graph classification
and graph regression. (2) Different graph pooling approaches have a limited
impact on node classification. (3) Feature masking influences the performance
of graph pooling more seriously compared with structure perturbation and dense
pooling is more robust to noise attack. (4) Most of graph pooling approaches
suffer from serious performance decrement from distribution shifts.

The main contributions of this paper are as follows:

  * •

Comprehensive Benchmark. We present the first comprehensive graph pooling
benchmark, which incorporates 15 state-of-the-art graph pooling approaches and
21 diverse datasets across graph classification, graph regression and node
classification.

  * •

Extensive Analysis. To investigate the pros and cons of graph pooling
approaches, we thoroughly evaluate current approaches from three perspectives,
i.e., effectiveness, robustness, and generalizability, which can serve as
guidance for researchers in different applications.

  * •

Open-source Material. We have made our benchmark of all these graph pooling
approaches publicly available and reproducible, and believe our benchmark can
benefit researchers in both graph machine learning and interdisciplinary
fields.

Figure 1: Overview of our hierarchical backbone for graph classification and
graph regression.

##  2 Preliminaries

Notations. Consider a graph $G$ characterized by a vertex set $V$ and an edge
set $E$. The features associated with each vertex are represented by the
matrix $\bm{X}\in\mathbb{R}^{|V|\times d}$, where $|V|$ denotes the number of
vertices, and $d$ signifies the dimensionality of the attribute vectors. The
adjacency relationships within the graph are encapsulated by the adjacency
matrix $\bm{A}\in\\{0,1\\}^{|V|\times|V|}$, where an entry $\bm{A}[i,j]=1$
indicates the presence of an edge between vertex $v_{i}$ and vertex $v_{j}$;
otherwise, $\bm{A}[i,j]=0$.

Graph Pooling [41, 43, 40]. The aim of graph pooling is to reduce the spatial
size of feature maps while preserving essential semantics, which thereby
decreases computational complexity and memory usage. In this work, we focus on
hierarchical pooling approaches [21]. Let POOL denote a graph pooling function
which maps $G$ to a graph $G^{\prime}=(V^{\prime},E^{\prime})$ with the
reduced size:

${G}^{\prime}=\texttt{POOL}({G}),$ (1)

where $|V^{\prime}|<|V|$. the process has two main principal components, i.e.,
reduction, and connection [43]. In particular, the reduction component aims to
generate pooled nodes and their attributes in ${G}^{\prime}$ while the
connection. The connection component computes the edges $E^{\prime}$ among the
$V^{\prime}$ nodes.

Figure 2: Overview of the graph U-Net framework for node classification.

Graph Classification and Regression [25, 44, 43]. The two primary graph-level
tasks are graph regression and graph classification. Here, a graph dataset
$\mathcal{G}$ is provided as a set of graph-label pairs $(G_{i},y_{i})$, where
$y_{i}$ denotes the label for graph $G_{i}$. The objective is to train a
powerful discriminative model $f$ that predicts the correct label $y_{i}$
given an input graph $G_{i}$. In graph classification, $y_{i}$ are categorical
labels ${1,\cdots,K}$ with $K$ as the number of classes, while in graph
regression, $y_{i}$ are continuous values. A well-trained graph classification
model should output labels that closely match the true labels, and similarly,
a graph regression model should predict values that are nearly identical to
the ground truth values. In these tasks, graph pooling always accompanies
graph convolutional operators. In formulation, the basic updating rule is
written as follows:

$\bm{H}^{(l+1)}=\sigma(\tilde{\bm{D}}^{-\frac{1}{2}}\tilde{\bm{A}}\tilde{D}^{-\frac{1}{2}}\bm{H}^{(l)}\bm{W}^{(l)}),$
(2)

where $\bm{H}^{(l)}$ denotes the node feature matrix at layer $l$,
$\bm{W}^{(l)}$ denotes the weight matrix at the crossponding layer,
$\tilde{\bm{A}}=\bm{A}+\bm{I}$ is the adjacency matrix $\bm{A}$ plus the
identity matrix $\bm{I}$, $\tilde{\bm{D}}$ is the degree matrix of
$\tilde{\bm{A}}$, and $\sigma$ is a nonlinear activation function [45]. The
pooling layers can be formulated as:

$\bm{H}^{(pool)}=\texttt{POOL}(\bm{H}^{(L)}),$ (3)

where $\bm{H}^{(pool)}$ is the node feature matrix after pooling We
iteratively conduct graph convolution and graph pooling operators and adopt a
readout function to output the graph representation for downstream tasks. The
overview of the basic hierarchical backbone can be found in Figure 1.

Node Classification [45, 46, 47]. The aim of node classification is to assign
semantic labels to nodes in a graph according to their attributes and
relationships with different nodes. Each dataset involves a graph $G$,
consisting of nodes $v_{i}$ and their corresponding labels $y_{i}$. $|V|$ is
divided into a labeled set $V^{l}$ and a unlabeled set $V^{u}$. We are
required to train a graph neural network model that can predict the missing
labels of nodes in $V^{u}$ using the attributes of other nodes. As shown in
Figure 2, U-Net framework [48] is widely used to incorporate pooling
operations for node classification. In the encoder part, U-Net progressively
applies pooling and graph convolution to downsample the graphs and extract
multi-scale features. The decoder part of U-Net utilizes upsampling and graph
convolution to gradually upsample the low-resolution feature maps back to the
original graph size. Residual connections are employed to directly transfer
the feature maps from the encoder to the decoder, facilitating the
preservation of fine-grained semantics during upsampling [48, 49, 50].

##  3 Graph Pooling Benchmark

In this section, we present an overview of our graph pooling benchmark, which
includes extensive state-of-the-art approaches, graph datasets, and evaluation
protocols.

###  3.1 Graph Pooling Approaches

Our benchmark contains 15 state-of-the-art graph pooling approaches, which can
be divided into two categories, i.e., sparse pooling and dense pooling based
on the number of nodes after pooling. Table 1 summarizes the experimental
details in their corresponding papers.

Sparse Pooling. Sparse pooling approaches typically maintain the number of
nodes as a constant cardinality $O(1)$ after graph pooling [43, 40]. These
approaches usually utilize a score function to evaluate the importance of each
node and keep the nodes with high scores and are easy to implement using
sparse matrix calculation. Therefore, they require significantly fewer
computational resources, especially when it comes to large-scale graphs. In
our benchmark, we select 9 sparse pooling approaches including TopKPool [25],
SAGPool [26], ASAPool [27], PANPool [28], COPool [29], CGIPool [30], KMISPool
[31], GSAPool [32], and HGPSLPool [33].

Dense Pooling. Dense pooling approaches usually have the number of nodes after
pooling proportional to the original node numbers, i.e., $O(|V|)$. These
approaches typically adopt graph clustering to learn a new coarsened graph,
which can provide a comprehensive semantic view by summarizing similar nodes.
One limitation of these approaches is the potential high complexity. In this
work, we select 6 dense pooling approaches including AsymCheegerCutPool [34],
DiffPool [35], MincutPool [36], DMoNPool [37], HoscPool [38], and
JustBalancePool [39].

###  3.2 Datasets

To systematically evaluate different graph pooling methods, we integrate 21
datasets from different domains for three types of tasks. For graph
classification, we select eight publicly available datasets from TUDataset
[51], including three molecules datasets, i.e., BZR [52], NCI1 [53], and
NCI109 [53], four bioinformatics datasets, i.e., PROTEINS, PROTEINS_full [54],
D&D [55], and ENZYMES [56], one social network dataset, i.e., IMDB-MULTI [57],
and one synthetic dataset, i.e., COLORS-3 [58]. For graph regression, we
choose five datasets from previous works [10] including QM8, BACE, ESOL,
FreeSolv, and Lipophilicity. For node classification, we utilize three
citation network datasets, i.e., Cora, Citeseer, Pubmed [59] and three website
networks, i.e., Cornell, Texas, and Wisconsin [60] and the GitHub dataset
[61]. More information can be found in Appendix.

Table 1: Overview of experimental details of graph pooling research. These
papers utilize different settings, which validates the necessity of building a
comprehensive and fair graph pooling benchmark.

Methods | Datasets | Tasks
---|---|---
Sparse Pooling |
TopKPool | NIPS’19 | MNIST, COLLAB, PROTEINS, D&D |  |  |  |  |  |  | Graph Classification
SAGPool | ICML’19 | D&D, PROTEINS, NCI1, NCI109, FRANKENSTEIN |  |  |  |  |  |  | Graph Classification
ASAPool | AAAI’20 | D&D, PROTEINS, NCI1, NCI109, FRANKENSTEIN |  |  |  |  |  |  | Graph Classification
PANPool | NIPS’20 | PROTEINS, PROTEINS_FULL, NCI1, AIDS, MUTAGENCITY |  |  |  |  |  |  | Graph Classification
COPool | ECMLPKDD’22 | BZR, AIDS, NCI1, NCI109, PROTEINS, QM7, IMDB-M |  |  |  |  |  |  | Graph Classification, Graph Regression
CGIPool | SIGIR’22 | NCI1, NCI109, Mutagenicity, IMDB-B, IMDB-M, COLLAB PROTEINS |  |  |  |  |  |  | Graph Classification
KMISPool | AAAI’23 | D&D, REDDIT-B, REDDIT-5K, REDDIT-12K, Github |  |  |  |  |  |  | Graph Classification, Node Classification
GSAPool | WWW’20 | D&D, NCI1, NCI109, Mutagencity |  |  |  |  |  |  | Graph Classification
HGPSLPool | Arxiv’19 | D&D, PROTEINS, NCI1, NCI109, ENZYMES, Mutagencity |  |  |  |  |  |  | Graph Classification
Dense Pooling |
AsymCheegerCutPool | ICML’23 | Cora, Citeseer, Pubmed, DBLP |  |  |  |  |  |  | Node Classification
DiffPool | NIPS’18 | D&D, PROTEINS, COLLAB, ENZYMES, REDDIT-MULTI |  |  |  |  |  |  | Graph Classification
MincutPool | ICML’20 | D&D, PROTEINS, COLLAB, REDDIT-B, Mutagenicity, QM9 |  |  |  |  |  |  | Graph Classification, Graph Regression
DMoNPool | JMLR’23 | Cora, Citeseer Pubmed, Coauthor |  |  |  |  |  |  | Node Classification
HoscPool | CIKM’22 | Cora, Citeseer Pubmed, Coauthor, DBLP, Email-EU |  |  |  |  |  |  | Node Classification
JustBalancePool | Arxiv’22 | Cora, Citeseer, Pubmed, DBLP |  |  |  |  |  |  | Node Classification

###  3.3 Evaluation Protocols

Our benchmark evaluation encompasses three key aspects, i.e., effectiveness,
robustness, and generalizability. Firstly, we conduct a performance comparison
of graph pooling approaches across three tasks including graph classification,
graph regression, and node classification. For graph and node classification
tasks, we employ accuracy as the evaluation metric. For graph regression, we
use root mean square error (RMSE) for ESOL, FreeSolv, and Lipophilicity [10].
Following previous research [42], we use the area under the receiver operating
characteristic (AUROC) curve to evaluate BACE, and Mean Absolute Error (MAE)
for QM8. Secondly, our benchmark evaluates the robustness of graph pooling
approaches across two views, i.e., structural robustness and feature
robustness [62]. In particular, we add and drop edges of graphs to study
structural robustness and mask node features to investigate feature
robustness. Thirdly, we employ size-based and density-based distribution
shifts to evaluate the generalizability of different pooling methods under
real-world scenarios [63]. In addition to these three views, we conduct a
further analysis of these graph pooling approaches including the comparison of
efficiency, and different backbone parameter choices.

##  4 Experiment

Table 2: Results of graph classification for different graph pooling methods.
$\pm$ denotes standard deviation. OOM denotes out of GPU memory. OOT denotes
cannot be computed within 12 hours.

Methods | PROTEINS |  | NCI1 |  | NCI109 |  | ENZYMES |  | BZR |  | IMDB-M |  | COLORS-3 | Avg. | Rank
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Sparse Pooling |  |  |  |  |  |
TopKPool | 72.74$\pm$2.36 |  | 69.08$\pm$2.43 |  | 67.65$\pm$2.11 |  | 38.22$\pm$7.59 |  | 83.23$\pm$2.41 |  | 41.21$\pm$0.34 |  | 43.88$\pm$5.39 | 62.02 | 12.50
SAGPool | 75.71$\pm$1.90 |  | 71.77$\pm$2.31 |  | 71.29$\pm$1.98 |  | 38.89$\pm$5.35 |  | 82.90$\pm$2.19 |  | 45.43$\pm$2.08 |  | 45.27$\pm$2.89 | 64.33 | 8.50
ASAPool | 73.45$\pm$2.18 |  | 74.81$\pm$1.73 |  | 71.97$\pm$0.62 |  | 39.33$\pm$8.68 |  | 86.45$\pm$2.99 |  | 45.72$\pm$1.63 |  | 42.79$\pm$2.02 | 65.29 | 6.83
PANPool | 73.69$\pm$1.38 |  | 74.75$\pm$1.45 |  | 70.03$\pm$1.01 |  | 39.56$\pm$2.86 |  | 85.16$\pm$1.21 |  | 38.29$\pm$0.31 |  | 32.00$\pm$3.68 | 63.58 | 8.83
COPool | 73.69$\pm$4.54 |  | 71.25$\pm$1.24 |  | 69.90$\pm$3.45 |  | 42.89$\pm$3.49 |  | 80.00$\pm$3.47 |  | 48.68$\pm$0.75 |  | 38.44$\pm$3.56 | 64.40 | 8.33
CGIPool | 72.26$\pm$1.79 |  | 76.24$\pm$2.04 |  | 71.81$\pm$1.41 |  | 40.00$\pm$5.26 |  | 84.84$\pm$2.81 |  | 50.36$\pm$0.38 |  | 37.78$\pm$5.35 | 65.92 | 7.50
KMISPool | 72.98$\pm$1.10 |  | 79.06$\pm$0.82 |  | 72.23$\pm$0.67 |  | 20.00$\pm$5.71 |  | 87.10$\pm$3.38 |  | 40.37$\pm$0.38 |  | 20.67$\pm$3.76 | 61.96 | 8.17
GSAPool | 72.50$\pm$1.90 |  | 69.40$\pm$1.55 |  | 68.65$\pm$1.81 |  | 35.78$\pm$3.74 |  | 83.87$\pm$0.00 |  | 41.35$\pm$1.28 |  | 38.44$\pm$4.19 | 61.93 | 12.17
HGPSLPool | 73.45$\pm$2.49 |  | 75.24$\pm$0.89 |  | 68.74$\pm$0.45 |  | 43.56$\pm$2.93 |  | 88.06$\pm$1.64 |  | 39.45$\pm$0.28 |  | 41.33$\pm$1.91 | 64.75 | 7.83
Dense Pooling |  |  |  |  |  |
AsymCheegerCutPool | 76.59$\pm$1.47 |  | 74.75$\pm$0.12 |  | 72.13$\pm$0.69 |  | 43.78$\pm$5.52 |  | 84.52$\pm$2.41 |  | 49.12$\pm$0.43 |  | OOT | 66.82 | 5.00
DiffPool | 73.05$\pm$1.98 |  | 78.35$\pm$0.85 |  | 77.00$\pm$1.81 |  | 46.00$\pm$3.62 |  | 75.16$\pm$1.64 |  | 48.48$\pm$0.33 |  | OOT | 66.34 | 6.00
MincutPool | 73.41$\pm$2.74 |  | 77.60$\pm$1.51 |  | 76.58$\pm$1.45 |  | 42.89$\pm$2.69 |  | 81.61$\pm$3.90 |  | 42.44$\pm$0.20 |  | OOT | 65.76 | 6.50
DMoNPool | 76.71$\pm$1.18 |  | 71.67$\pm$0.58 |  | 72.32$\pm$1.48 |  | 48.89$\pm$3.78 |  | 75.81$\pm$1.77 |  | 41.14$\pm$0.34 |  | OOT | 64.42 | 7.50
HoscPool | 73.17$\pm$2.00 |  | 77.44$\pm$1.79 |  | 73.94$\pm$1.53 |  | 46.67$\pm$3.78 |  | 78.39$\pm$3.16 |  | 42.34$\pm$0.58 |  | OOT | 65.33 | 6.67
JustBalancePool | 73.17$\pm$2.00 |  | 77.63$\pm$1.85 |  | 73.94$\pm$1.53 |  | 43.78$\pm$3.76 |  | 78.39$\pm$3.16 |  | 43.08$\pm$0.42 |  | OOT | 65.00 | 6.33

###  4.1 Experimental Settings

All graph pooling methods in our benchmark are implemented by PyTorch [64].
Graph convolutional networks serve as the default encoders for all algorithms
unless otherwise specified. The experimental setup includes a Linux server
equipped with NVIDIA L4 and NVIDIA A100 GPUs, as well as an Intel Xeon Gold
6354 CPU. The software stack comprises PyTorch version 1.11.0, PyTorch-
geometric version 2.1.0 [65], and Python version 3.9.16.

###  4.2 Effectiveness Analysis

Performance on Graph Classification. To begin, we investigate the performance
of different graph pooling approaches on graph classification. The results of
compared approaches on seven popular datasets are recorded in Table 2. From
the results, we have the following observations. Firstly, in general, dense
pooling methods outperform sparse pooling methods. However, dense pooling
methods encounter memory bottlenecks when processing large datasets with tens
of thousands of graphs, such as COLORS-3. Secondly, two dense pooling
approaches, AsymCheegerCutPool and DiffPool are among the top out of all the
compared methods, achieving optimal or near-optimal results on five datasets.
The potential reasons include that AsymCheegerCutPool minimizes the graph
total variation of the cluster assignments, and DiffPool improves the quality
of membership assignments by using a link prediction auxiliary objective [35,
34]. Thirdly, among the sparse pooling methods, ASAPool, CGIPool, and
HGPSLPool demonstrate the best overall performance. To be specific, CGIPool
achieves the best results on IMDB-M, while HGPSLPool achieves the best results
on BZR.

Table 3: Results of graph regression for different pooling methods.

Methods | QM8 |  | BACE |  | ESOL |  | FreeSolv |  | Lipophilicity | Avg. | Rank
---|---|---|---|---|---|---|---|---|---|---|---
Sparse Pooling |  |  |  |  |  |
TopKPool | 0.026 $\pm$ 0.000 |  | 0.79 $\pm$ 0.01 |  | 1.14 $\pm$ 0.06 |  | 1.91 $\pm$ 0.30 |  | 0.99 $\pm$ 0.09 | 1.35 | 10.67
SAGPool | 0.024 $\pm$ 0.000 |  | 0.78 $\pm$ 0.01 |  | 1.49 $\pm$ 0.28 |  | 1.87 $\pm$ 0.06 |  | 1.00 $\pm$ 0.09 | 1.45 | 12.33
ASAPool | 0.025 $\pm$ 0.002 |  | 0.77 $\pm$ 0.04 |  | 1.06 $\pm$ 0.13 |  | 2.52 $\pm$ 0.38 |  | 0.95 $\pm$ 0.09 | 1.51 | 10.67
PANPool | 0.024 $\pm$ 0.000 |  | 0.75 $\pm$ 0.02 |  | 1.31 $\pm$ 0.05 |  | 3.42 $\pm$ 0.32 |  | 1.11 $\pm$ 0.02 | 1.95 | 14.67
COPool | 0.024 $\pm$ 0.002 |  | 0.81 $\pm$ 1.56 |  | 1.21$\pm$ 0.10 |  | 2.53 $\pm$ 0.26 |  | 0.94 $\pm$ 0.03 | 1.56 | 11.67
CGIPool | 0.020 $\pm$ 0.001 |  | 0.83 $\pm$ 0.01 |  | 1.09 $\pm$ 0.19 |  | 1.78 $\pm$ 0.17 |  | 0.91 $\pm$ 0.05 | 1.26 | 8.00
KMISPool | 0.018 $\pm$ 0.001 |  | 0.81 $\pm$ 0.01 |  | 0.80 $\pm$ 0.03 |  | 1.56 $\pm$ 0.65 |  | 0.77 $\pm$ 0.01 | 1.04 | 5.67
GSAPool | 0.025 $\pm$ 0.001 |  | 0.81 $\pm$ 0.02 |  | 1.22 $\pm$ 0.10 |  | 1.95 $\pm$ 0.32 |  | 0.99 $\pm$ 0.08 | 1.39 | 11.67
HGPSLPool | 0.019 $\pm$ 0.000 |  | 0.81 $\pm$ 0.02 |  | 1.02 $\pm$ 0.14 |  | 2.00 $\pm$ 0.31 |  | 0.93 $\pm$ 0.03 | 1.32 | 9.00
Dense Pooling |  |  |  |  |  |
AsymCheegerCutPool | 0.031 $\pm$ 0.005 |  | 0.84 $\pm$ 0.01 |  | 0.99 $\pm$ 0.12 |  | 2.00 $\pm$ 0.18 |  | 0.95 $\pm$ 0.11 | 1.31 | 9.33
DiffPool | 0.037 $\pm$ 0.010 |  | 0.84 $\pm$ 0.02 |  | 0.81 $\pm$ 0.05 |  | 1.20 $\pm$ 0.09 |  | 0.73 $\pm$ 0.03 | 0.91 | 4.67
MincutPool | 0.020 $\pm$ 0.001 |  | 0.85 $\pm$ 0.02 |  | 0.76 $\pm$ 0.02 |  | 1.19 $\pm$ 0.18 |  | 0.73 $\pm$ 0.02 | 0.89 | 3.33
DMoNPool | 0.021 $\pm$ 0.001 |  | 0.85 $\pm$ 0.02 |  | 0.68 $\pm$ 0.02 |  | 1.16 $\pm$ 0.15 |  | 0.69 $\pm$ 0.02 | 0.84 | 1.33
HoscPool | 0.019 $\pm$ 0.002 |  | 0.84 $\pm$ 0.01 |  | 0.76 $\pm$ 0.02 |  | 1.14 $\pm$ 0.13 |  | 0.72 $\pm$ 0.02 | 0.87 | 2.33
JustBalancePool | 0.022 $\pm$ 0.004 |  | 0.85 $\pm$ 0.02 |  | 0.74 $\pm$ 0.03 |  | 1.26 $\pm$ 0.16 |  | 0.70 $\pm$ 0.01 | 0.90 | 3.00

Performance on Graph Regression. We further explore the performance of
different pooling methods through graph-level regression tasks. As shown in
Table 3, we can observe the following: Firstly, dense pooling methods
significantly outperform sparse pooling methods. DMoNPool, HoscPool, and
JustBalancePool are the best-performing pooling methods, with DMoNPool
achieving optimal or near-optimal results on four datasets, and
JustBalancePool achieving optimal or near-optimal results on three datasets.
Secondly, KMISPool performs well among sparse pooling methods, outperforming
AsymCheegerCutPool in dense pooling methods.

Performance on Node Classification. Table 4 presents the performance of
various sparse pooling methods in node classification tasks. We can observe
that: Firstly, different pooling approaches have consistent performance across
these datasets. The potential reason is that graph convolution is the core of
semantics exploration on the node level. Secondly, TopKPool demonstrates the
best performance among the methods used, potentially because it can adapt to
the irregularity of graph data and extract information from the k most
important nodes [25]. GSAPool achieves the best or second-best accuracy in 5
out of 7 datasets, as previously mentioned studies have indicated. Before
discarding less important nodes, GSAPool aggregates the features of nodes,
ensuring that the pooled nodes contain sufficient effective graph information
[32]. This aggregation strategy ensures that the selected nodes not only
contain their own features but also integrate information from neighboring
nodes. Thirdly, the scalability of ASAPool, PANPool, and HGPSLPool still
requires improvement, as they are unable to complete training on larger
datasets such as GitHub.

Table 4: Results of node classification for different pooling methods.

Methods | Cora |  | Citeseer |  | Pubmed |  | Cornell |  | Texas |  | Wisconsin |  | Github | Avg. | Rank
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
TopKPool | 89.67$\pm$0.18 |  | 77.58$\pm$0.13 |  | 87.90$\pm$0.15 |  | 79.99$\pm$0.83 |  | 82.95$\pm$1.66 |  | 82.23$\pm$1.13 |  | 87.12$\pm$0.05 | 82.48 | 2.80
SAGPool | 89.57$\pm$0.18 |  | 77.37$\pm$0.12 |  | 87.85$\pm$0.16 |  | 80.10$\pm$1.58 |  | 82.41$\pm$1.06 |  | 81.99$\pm$1.07 |  | 86.87$\pm$0.04 | 82.29 | 4.60
ASAPool | 89.70$\pm$0.14 |  | 77.57$\pm$0.24 |  | 87.59$\pm$0.15 |  | 78.89$\pm$1.27 |  | 82.52$\pm$0.58 |  | 82.55$\pm$0.96 |  | OOM | 82.25 | 3.80
PANPool | 89.36$\pm$0.26 |  | 77.45$\pm$0.20 |  | 87.60$\pm$0.09 |  | 79.33$\pm$0.86 |  | 81.63$\pm$0.74 |  | 81.99$\pm$1.51 |  | OOM | 81.95 | 6.00
COPool | 89.29$\pm$0.25 |  | 77.36$\pm$0.23 |  | 87.52$\pm$0.23 |  | 78.25$\pm$0.65 |  | 82.97$\pm$1.26 |  | 82.23$\pm$0.66 |  | 86.25$\pm$0.45 | 82.02 | 5.80
CGIPool | 89.03$\pm$0.43 |  | 77.31$\pm$0.26 |  | 87.76$\pm$0.21 |  | 79.88$\pm$2.14 |  | 81.54$\pm$1.14 |  | 81.19$\pm$1.11 |  | 84.09$\pm$1.31 | 81.79 | 7.80
KMISPool | 89.75$\pm$0.17 |  | 77.69$\pm$0.27 |  | 87.80$\pm$0.06 |  | 79.12$\pm$0.91 |  | 82.08$\pm$0.98 |  | 81.12$\pm$1.19 |  | 87.09$\pm$0.04 | 81.95 | 4.80
GSAPool | 89.61$\pm$0.16 |  | 77.61$\pm$0.22 |  | 87.89$\pm$0.04 |  | 80.01$\pm$0.56 |  | 83.50$\pm$1.23 |  | 81.75$\pm$0.68 |  | 87.19$\pm$0.04 | 82.50 | 3.20
HGPSLPool | 89.63$\pm$0.24 |  | 77.50$\pm$0.18 |  | OOM |  | 79.24$\pm$0.76 |  | 82.08$\pm$0.63 |  | 81.67$\pm$1.14 |  | OOM | 82.02 | 5.60

Table 5: Results of graph classification under random noise attack for
different pooling methods.

Dataset | Ptb Method | TopKPool | SAGPool | ASAPool | CoPool | KMISPool | DiffPool | MincutPool | JustBalancePool
---|---|---|---|---|---|---|---|---|---
PROTEINS | RAW | 72.74$\pm$2.36 | 75.71$\pm$1.90 | 73.45$\pm$2.18 | 73.69$\pm$4.54 | 72.98$\pm$1.10 | 73.05$\pm$1.98 | 73.41$\pm$2.74 | 73.17$\pm$2.00
ADD | 66.71$\pm$1.99 | 70.49$\pm$2.06 | 64.15$\pm$1.41 | 63.54$\pm$1.98 | 59.88$\pm$2.26 | 71.59$\pm$1.42 | 69.63$\pm$1.98 | 70.12$\pm$0.67
DROP | 72.50$\pm$2.21 | 69.09$\pm$1.44 | 68.17$\pm$1.89 | 68.41$\pm$2.45 | 63.72$\pm$4.11 | 70.37$\pm$3.06 | 68.84$\pm$4.58 | 73.05$\pm$1.51
MASK | 65.49$\pm$4.24 | 62.87$\pm$2.89 | 63.35$\pm$2.89 | 64.88$\pm$4.71 | 61.34$\pm$0.56 | 69.63$\pm$3.91 | 68.72$\pm$2.33 | 69.39$\pm$3.39
NCI1 | RAW | 69.08$\pm$2.43 | 71.77$\pm$2.31 | 74.81$\pm$1.73 | 71.25$\pm$1.24 | 79.06$\pm$0.82 | 78.35$\pm$0.85 | 77.60$\pm$1.51 | 77.63$\pm$1.85
ADD | 62.14$\pm$2.19 | 65.71$\pm$1.03 | 63.76$\pm$2.18 | 63.37$\pm$1.11 | 62.85$\pm$0.54 | 70.47$\pm$2.08 | 66.52$\pm$1.94 | 70.11$\pm$1.32
DROP | 72.51$\pm$0.30 | 71.11$\pm$0.79 | 72.99$\pm$0.81 | 72.46$\pm$0.64 | 74.66$\pm$0.27 | 69.66$\pm$0.95 | 72.65$\pm$0.56 | 72.63$\pm$0.50
MASK | 56.40$\pm$3.65 | 64.76$\pm$1.61 | 66.09$\pm$0.76 | 64.08$\pm$1.37 | 65.09$\pm$0.91 | 66.84$\pm$0.95 | 63.82$\pm$3.06 | 67.52$\pm$2.48
NCI109 | RAW | 67.65$\pm$2.11 | 71.29$\pm$1.9 | 71.97$\pm$0.62 | 69.90$\pm$3.45 | 72.23$\pm$0.67 | 77.00$\pm$1.81 | 76.58$\pm$1.45 | 73.94$\pm$1.53
ADD | 66.81$\pm$1.44 | 56.23$\pm$1.63 | 60.32$\pm$2.06 | 63.87$\pm$2.39 | 62.48$\pm$1.14 | 64.32$\pm$1.60 | 65.52$\pm$2.24 | 69.00$\pm$1.84
DROP | 61.00$\pm$1.52 | 64.39$\pm$1.45 | 63.39$\pm$1.55 | 62.06$\pm$1.90 | 61.29$\pm$1.39 | 64.26$\pm$2.58 | 62.42$\pm$1.66 | 67.48$\pm$1.66
MASK | 59.45$\pm$2.88 | 62.81$\pm$1.61 | 65.16$\pm$0.94 | 61.94$\pm$1.27 | 64.35$\pm$0.72 | 64.00$\pm$1.74 | 63.23$\pm$0.95 | 65.77$\pm$1.96
ENZYMES | RAW | 38.22$\pm$7.59 | 38.89$\pm$5.35 | 39.33$\pm$8.68 | 42.89$\pm$3.49 | 20.00$\pm$5.71 | 46.00$\pm$3.62 | 42.89$\pm$2.69 | 43.78$\pm$3.76
ADD | 40.44$\pm$2.29 | 37.56$\pm$0.83 | 20.67$\pm$1.81 | 38.89$\pm$2.22 | 35.56$\pm$4.27 | 35.33$\pm$5.32 | 30.67$\pm$3.11 | 33.33$\pm$3.14
DROP | 44.00$\pm$2.29 | 39.33$\pm$3.11 | 24.44$\pm$0.60 | 42.00$\pm$1.47 | 14.22$\pm$1.78 | 30.22$\pm$3.81 | 24.44$\pm$4.61 | 31.56$\pm$5.56
MASK | 35.78$\pm$4.06 | 33.33$\pm$1.86 | 16.44$\pm$3.47 | 30.67$\pm$3.56 | 16.67$\pm$0.00 | 23.11$\pm$2.57 | 22.00$\pm$6.02 | 23.11$\pm$3.68
BZR | RAW | 83.23$\pm$2.41 | 82.90$\pm$2.19 | 86.45$\pm$2.99 | 80.00$\pm$3.47 | 87.10$\pm$3.38 | 75.16$\pm$1.64 | 81.61$\pm$3.90 | 78.39$\pm$3.16
ADD | 75.81$\pm$1.77 | 80.97$\pm$1.21 | 88.39$\pm$1.88 | 74.52$\pm$4.38 | 69.35$\pm$3.38 | 80.32$\pm$1.58 | 81.94$\pm$2.37 | 82.26$\pm$2.04
DROP | 76.45$\pm$0.79 | 71.61$\pm$3.32 | 74.19$\pm$0.00 | 74.19$\pm$1.44 | 79.35$\pm$0.65 | 72.90$\pm$1.21 | 76.45$\pm$2.99 | 76.77$\pm$2.19
MASK | 70.00$\pm$2.99 | 78.39$\pm$3.16 | 64.52$\pm$8.22 | 78.06$\pm$3.32 | 71.94$\pm$0.79 | 80.32$\pm$2.96 | 78.71$\pm$4.00 | 81.29$\pm$3.62

Figure 3: Performance of different approaches w.r.t. different rates of random
noise.

###  4.3 Robustness Analysis

The compared performance for three types of random noise on eight graph
pooling methods on the PROTEINS, NCI1, NCI109, ENZYMES, and BZR datasets are
shown in Table LABEL:noise. With a probability of 50%, edges of the graph are
randomly removed or added, and node features are randomly masked with the same
likelihood. From the results, we have the following observations. Firstly,
masking node features would degrade the performance the most, which
demonstrates that node attributes are still the most crucial for graph
representation learning. Secondly, the performance ranking of different
methods is consistent under different noise attacks but not consistent across
different datasets. This indicates that we can choose the optimal graph
pooling approaches by validating the performance under any type of noise
attack in practice. Thirdly, overall, dense pooling methods exhibit stronger
resistance to random noise attacks compared to sparse pooling methods. For
instance, JustBalancePool achieves optimal or near-optimal results on three
datasets, and DiffPool also performs exceptionally well on most datasets. In
addition, sparse pooling methods significantly outperform dense pooling
methods on the multi-classification dataset ENZYMES, as evidenced by the
performance of TopKPool and COPool. This indicate that the choice of pooling
method can be tailored based on different classification tasks.

As depicted in Figure 3, the model’s performance generally declines as the
noise intensity increases. It is observed that at the same level of noise, the
accuracy decrease is more evident on NCI109, while it is relatively minor on
ENZYMES. The accuracy degradation due to edge addition noise is less than that
caused by node masking noise and edge deletion noise. Among the three types of
noise, although the accuracy of nearly all methods decreases with
fluctuations, JustbalancePool and DiffPool exhibit the strongest robustness.
For the NCI1 dataset, MincutPool shows significant variance in terms of
accuracy.

Table 6: Results of graph classification under distribution shifts. Size and
density denote two popular types of shifts across training and test datasets.

Method | D&D | PROTEINS | NCI1 | NCI109
---|---|---|---|---
Size | Density | Size | Density | Size | Density | Size | Density
Sparse Pooling
TopKPool | 56.27$\pm$8.82 | 51.36$\pm$4.27 | 49.29$\pm$6.74 | 43.69$\pm$6.26 | 28.59$\pm$7.73 | 45.88$\pm$5.69 | 24.18$\pm$2.05 | 53.00$\pm$5.00
SAGPool | 50.51$\pm$9.52 | 52.97$\pm$2.67 | 39.11$\pm$6.90 | 49.19$\pm$6.30 | 27.86$\pm$4.15 | 52.95$\pm$3.06 | 25.89$\pm$2.91 | 56.91$\pm$2.59
ASAPool | 62.88$\pm$6.87 | 52.88$\pm$5.99 | 56.07$\pm$11.66 | 47.39$\pm$7.12 | 23.93$\pm$2.22 | 67.02$\pm$2.25 | 23.47$\pm$1.48 | 63.54$\pm$1.70
PANPool | 56.1$\pm$5.73 | 51.86$\pm$5.88 | 43.39$\pm$14.91 | 33.69$\pm$15.52 | 20.24$\pm$0.57 | 55.46$\pm$2.18 | 23.56$\pm$2.64 | 55.18$\pm$2.77
COPool | 55.93$\pm$9.94 | 49.49$\pm$4.88 | 49.29$\pm$8.21 | 52.34$\pm$6.70 | 24.47$\pm$1.34 | 53.63$\pm$3.40 | 26.98$\pm$2.92 | 52.98$\pm$2.62
CGIPool | 63.56$\pm$3.83 | 52.37$\pm$3.81 | 49.29$\pm$17.31 | 44.95$\pm$11.85 | 28.83$\pm$5.88 | 58.61$\pm$0.88 | 27.55$\pm$2.45 | 55.78$\pm$3.12
KMISPool | 75.08$\pm$4.37 | 57.37$\pm$3.68 | 84.11$\pm$4.70 | 61.35$\pm$10.65 | 69.61$\pm$3.09 | 61.75$\pm$2.76 | 65.37$\pm$9.00 | 62.62$\pm$1.67
GSAPool | 53.56$\pm$9.34 | 50.00$\pm$4.30 | 42.68$\pm$7.54 | 44.32$\pm$9.66 | 28.5$\pm$2.51 | 53.03$\pm$3.76 | 26.46$\pm$6.55 | 54.68$\pm$1.57
HGPSLPool | 54.41$\pm$5.71 | 52.97$\pm$2.31 | 50.71$\pm$6.32 | 53.42$\pm$3.22 | 28.01$\pm$0 | 56.44$\pm$2.16 | 23.94$\pm$2.18 | 58.24$\pm$1.39
Dense Pooling
AsymCheegerCutPool | OOM | OOM | 75.71$\pm$3.85 | 67.21$\pm$6.76 | 23.83$\pm$5.14 | 72.18$\pm$0.90 | 55.25$\pm$24.14 | 70.35$\pm$0.46
DiffPool | 59.83$\pm$7.63 | 48.77$\pm$14.98 | 70.00$\pm$5.43 | 76.04$\pm$5.21 | 30.73$\pm$6.32 | 71.35$\pm$1.51 | 35.82$\pm$21.10 | 71.43$\pm$1.54
MincutPool | 63.39$\pm$10.32 | 60.17$\pm$22.57 | 65.00$\pm$9.01 | 63.15$\pm$8.51 | 21.21$\pm$2.50 | 66.12$\pm$4.96 | 24.70$\pm$3.32 | 70.04$\pm$1.58
DMoNPool | 60.17$\pm$4.12 | 39.72$\pm$31.15 | 66.79$\pm$2.22 | 64.59$\pm$6.78 | 22.67$\pm$3.09 | 69.65$\pm$1.72 | 41.05$\pm$21.66 | 68.83$\pm$1.49
HoscPool | 59.83$\pm$5.53 | 71.23$\pm$11.4 | 67.86$\pm$6.63 | 70.99$\pm$4.19 | 33.64$\pm$11.34 | 69.60$\pm$1.77 | 29.88$\pm$6.60 | 69.96$\pm$1.75
JustBalancePool | 59.83$\pm$5.53 | 71.23$\pm$11.4 | 69.64$\pm$3.04 | 69.10$\pm$3.22 | 25.39$\pm$3.27 | 69.60$\pm$1.77 | 38.48$\pm$19.09 | 68.63$\pm$1.69

Figure 4: Performance vs Training time and space of different approaches.

###  4.4 Generalizability Analysis

Table 6 presents the performance of all 15 graph pooling methods under out-of-
distribution shifts. For the datasets D&D, PROTEINS, NCI1, and NCI109, two
types of distribution shifts are implemented. The first type is based on the
number of nodes, where the smallest 50% of graphs by node count are used as
the training set, and the largest 20% as the test set, with the remaining
graphs serving as the validation set [66, 67]. Following the same criteria,
the second type of out-of-distribution shifts are generated based on graph
density [67]. For further details, please refer to the Appendix.

From Table 6, we have the following observations. Firstly, the majority of
graph pooling approaches suffer from serious performance decreases when it
comes to out-of-distribution shifts. For example, most of the approaches have
the accuracy below 35% when it comes to size-level distribution shifts.
Secondly, for the size-based out-of-distribution shift, KMISPool exhibits
superior performance compared with the other approaches in all cases. The
underlying reason is its ability to preserve key topological features in the
coarsened graph [31]. Thirdly, for the density-based out-of-distribution
shift, DiffPool demonstrates optimal performance. The potential reason is that
it adopts a learnable graph clustering process to adaptively explore
hierarchical semantics [35, 43].

###  4.5 Further Analysis

Efficiency Comparison. In this part, we conduct an efficiency analysis of
graph pooling methods on the ENZYMES and NCI1 datasets. We calculate the time
of different algorithms needed to complete 200 epochs of training with the 256
batch size. For space efficiency, we compute the GPU memory utilization during
the training process. The compared results are shown in Figure 4. From the
results, dense pooling methods such as DiffPool, MincutPool, and
JustBalancePool have significantly higher time and space costs. Notably,
although KMISPool performs poorly on the multi-classification dataset ENZYMES,
it has one of the lowest time and space costs across all three datasets.
Conversely, COPool has the highest GPU memory usage among the eight compared
methods.

Backbone Analysis. Figure 5 presents the performance of four pooling methods
based on GCNConv [68], TAGConv [69], SAGEConv [70], and GraphConv [71] on four
datasets, NCI1, NCI109, PROTEINS, and PROTEINS_full. We observe that TAGConv
achieves the best results across all datasets and all four methods except for
PROTEINS, while SAGEConv consistently performs the worst on NCI1, NCI109, and
PROTEINS_full datasets.

Figure 5: Performance w.r.t. graph convolution backbones for different pooling
methods. Figure 6: Performance w.r.t. different pooling ratios for four
pooling methods.

Parameter Analysis. Figure 6 shows the performance of four pooling methods on
different datasets. From the results, we observe that as the pooling rate
increases from 0.1 to 0.9, the performance would increase before saturation in
most datasets. The performance is relatively stable when the ratio is around
$0.7$. However, the performance on PROTEINS is limited and keeps declining
when the ratio is over $0.3$. The potential reason is the lack of node
attributes in PROTEINS, which validates the significance of node attributes in
graph classification.

##  5 Conclusion

In this paper, we construct the first graph pooling benchmark that includes 15
state-of-the-art approaches and 21 different graph datasets across graph
classification, graph regression and node classification. This benchmark
systematically analyzes the effectiveness, robustness, and generalizability of
graph pooling methods. We also make our benchmark publically available to
advance the fields of graph machine learning and applications. One limitation
of our benchmark is the lack of more complicated settings under label
scarcity. In future works, we would extend our graph pooling benchmark to more
realistic settings such as semi-supervised learning and few-shot learning.

## References

  * [1] Cheng Tan, Siyuan Li, Zhangyang Gao, Wenfei Guan, Zedong Wang, Zicheng Liu, Lirong Wu, and Stan Z Li.  Openstl: A comprehensive benchmark of spatio-temporal predictive learning.  Advances in Neural Information Processing Systems, 36:69819–69831, 2023.
  * [2] Zhixun Li, Xin Sun, Yifan Luo, Yanqiao Zhu, Dingshuo Chen, Yingtao Luo, Xiangxin Zhou, Qiang Liu, Shu Wu, Liang Wang, et al.  Gslb: The graph structure learning benchmark.  Advances in Neural Information Processing Systems, 36, 2024.
  * [3] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec.  Open graph benchmark: Datasets for machine learning on graphs.  Advances in neural information processing systems, 33:22118–22133, 2020.
  * [4] Wei Ju, Zheng Fang, Yiyang Gu, Zequn Liu, Qingqing Long, Ziyue Qiao, Yifang Qin, Jianhao Shen, Fang Sun, Zhiping Xiao, et al.  A comprehensive survey on deep graph representation learning.  Neural Networks, page 106207, 2024.
  * [5] Yongji Wu, Defu Lian, Yiheng Xu, Le Wu, and Enhong Chen.  Graph convolutional networks with markov random field reasoning for social spammer detection.  In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 1054–1061, 2020.
  * [6] Liangwei Yang, Zhiwei Liu, Yingtong Dou, Jing Ma, and Philip S Yu.  Consisrec: Enhancing gnn for social recommendation via consistent neighbor aggregation.  In Proceedings of the 44th international ACM SIGIR conference on Research and development in information retrieval, pages 2141–2145, 2021.
  * [7] Yanfu Zhang, Hongchang Gao, Jian Pei, and Heng Huang.  Robust self-supervised structural graph neural network for social network prediction.  In Proceedings of the ACM Web Conference 2022, pages 1352–1361, 2022.
  * [8] Tian Bian, Xi Xiao, Tingyang Xu, Peilin Zhao, Wenbing Huang, Yu Rong, and Junzhou Huang.  Rumor detection on social media with bi-directional graph convolutional networks.  In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 549–556, 2020.
  * [9] Kaiwei Zhang, Junchi Yu, Haichao Shi, Jian Liang, and Xiao-Yu Zhang.  Rumor detection with diverse counterfactual evidence.  In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 3321–3331, 2023.
  * [10] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande.  Moleculenet: a benchmark for molecular machine learning.  Chemical science, 9(2):513–530, 2018.
  * [11] Edward Choi, Zhen Xu, Yujia Li, Michael Dusenberry, Gerardo Flores, Emily Xue, and Andrew Dai.  Learning the graphical structure of electronic health records with graph convolutional transformer.  In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 606–613, 2020.
  * [12] Chen Ma, Liheng Ma, Yingxue Zhang, Jianing Sun, Xue Liu, and Mark Coates.  Memory augmented graph neural networks for sequential recommendation.  In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 5045–5052, 2020.
  * [13] Emily Alsentzer, Samuel Finlayson, Michelle Li, and Marinka Zitnik.  Subgraph neural networks.  Advances in Neural Information Processing Systems, 33:8017–8029, 2020.
  * [14] Mengzhu Sun, Xi Zhang, Jiaqi Zheng, and Guixiang Ma.  Ddgcn: Dual dynamic graph convolutional networks for rumor detection on social media.  In Proceedings of the AAAI conference on artificial intelligence, volume 36, pages 4611–4619, 2022.
  * [15] Chuang Liu, Yibing Zhan, Jia Wu, Chang Li, Bo Du, Wenbin Hu, Tongliang Liu, and Dacheng Tao.  Graph pooling for graph neural networks: Progress, challenges, and opportunities.  arXiv preprint arXiv:2204.07321, 2022.
  * [16] Lingfei Wu, Peng Cui, Jian Pei, Liang Zhao, and Xiaojie Guo.  Graph neural networks: foundation, frontiers and applications.  In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4840–4841, 2022.
  * [17] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson.  Benchmarking graph neural networks.  Journal of Machine Learning Research, 24(43):1–48, 2023.
  * [18] Meng Liu, Hongyang Gao, and Shuiwang Ji.  Towards deeper graph neural networks.  In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 338–348, 2020.
  * [19] Daniele Grattarola, Daniele Zambon, Filippo Maria Bianchi, and Cesare Alippi.  Understanding pooling in graph neural networks.  IEEE transactions on neural networks and learning systems, 2022.
  * [20] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  Advances in neural information processing systems, 29, 2016.
  * [21] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec.  Hierarchical graph representation learning with differentiable pooling.  Advances in neural information processing systems, 31, 2018.
  * [22] Diego Mesquita, Amauri Souza, and Samuel Kaski.  Rethinking pooling in graph neural networks.  Advances in Neural Information Processing Systems, 33:2220–2231, 2020.
  * [23] Zhen Zhang, Fan Wu, and Wee Sun Lee.  Factor graph neural networks.  Advances in Neural Information Processing Systems, 33:8577–8587, 2020.
  * [24] Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller.  Graph clustering with graph neural networks.  Journal of Machine Learning Research, 24(127):1–21, 2023.
  * [25] Boris Knyazev, Graham W Taylor, and Mohamed Amer.  Understanding attention and generalization in graph neural networks.  Advances in neural information processing systems, 32, 2019.
  * [26] Junhyun Lee, Inyeop Lee, and Jaewoo Kang.  Self-attention graph pooling.  In International conference on machine learning, pages 3734–3743. PMLR, 2019.
  * [27] Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar.  Asap: Adaptive structure aware pooling for learning hierarchical graph representations.  In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 5470–5477, 2020.
  * [28] Zheng Ma, Junyu Xuan, Yu Guang Wang, Ming Li, and Pietro Liò.  Path integral based convolution and pooling for graph neural networks.  Advances in Neural Information Processing Systems, 33:16421–16433, 2020.
  * [29] Xiaowei Zhou, Jie Yin, and Ivor W Tsang.  Edge but not least: Cross-view graph pooling.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 344–359. Springer, 2022.
  * [30] Yunsheng Pang, Yunxiang Zhao, and Dongsheng Li.  Graph pooling via coarsened graph infomax.  In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2177–2181, 2021.
  * [31] Davide Bacciu, Alessio Conte, and Francesco Landolfi.  Generalizing downsampling from regular data to graphs.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 6718–6727, 2023.
  * [32] Liang Zhang, Xudong Wang, Hongsheng Li, Guangming Zhu, Peiyi Shen, Ping Li, Xiaoyuan Lu, Syed Afaq Ali Shah, and Mohammed Bennamoun.  Structure-feature based graph self-adaptive pooling.  In Proceedings of The Web Conference 2020, pages 3098–3104, 2020.
  * [33] Zhen Zhang, Jiajun Bu, Martin Ester, Jianfeng Zhang, Chengwei Yao, Zhi Yu, and Can Wang.  Hierarchical graph pooling with structure learning.  arXiv preprint arXiv:1911.05954, 2019.
  * [34] Jonas Berg Hansen and Filippo Maria Bianchi.  Total variation graph neural networks.  In International Conference on Machine Learning, pages 12445–12468. PMLR, 2023.
  * [35] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec.  Hierarchical graph representation learning with differentiable pooling.  Advances in neural information processing systems, 31, 2018.
  * [36] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi.  Spectral clustering with graph neural networks for graph pooling.  In International conference on machine learning, pages 874–883. PMLR, 2020.
  * [37] Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller.  Graph clustering with graph neural networks.  Journal of Machine Learning Research, 24(127):1–21, 2023.
  * [38] Alexandre Duval and Fragkiskos Malliaros.  Higher-order clustering and pooling for graph neural networks.  In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pages 426–435, 2022.
  * [39] Filippo Maria Bianchi.  Simplifying clustering with graph neural networks.  arXiv preprint arXiv:2207.08779, 2022.
  * [40] Filippo Maria Bianchi and Veronica Lachi.  The expressive power of pooling in graph neural networks.  Advances in Neural Information Processing Systems, 36, 2024.
  * [41] Chuang Liu, Yibing Zhan, Jia Wu, Chang Li, Bo Du, Wenbin Hu, Tongliang Liu, and Dacheng Tao.  Graph pooling for graph neural networks: Progress, challenges, and opportunities.  arXiv preprint arXiv:2204.07321, 2022.
  * [42] Fanding Xu, Zhiwei Yang, Lizhuo Wang, Deyu Meng, and Jiangang Long.  Mespool: Molecular edge shrinkage pooling for hierarchical molecular representation learning and property prediction.  Briefings in Bioinformatics, 25(1):bbad423, 2024.
  * [43] Daniele Grattarola, Daniele Zambon, Filippo Maria Bianchi, and Cesare Alippi.  Understanding pooling in graph neural networks.  IEEE transactions on neural networks and learning systems, 2022.
  * [44] Ting Chen, Song Bian, and Yizhou Sun.  Are powerful graph neural nets necessary? a dissection on graph classification.  arXiv preprint arXiv:1905.04579, 2019.
  * [45] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [46] Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm.  Deep graph infomax.  arXiv preprint arXiv:1809.10341, 2018.
  * [47] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.  Deepwalk: Online learning of social representations.  In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701–710, 2014.
  * [48] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In Medical image computing and computer-assisted intervention–MICCAI 2015: 18th international conference, Munich, Germany, October 5-9, 2015, proceedings, part III 18, pages 234–241. Springer, 2015.
  * [49] Nabil Ibtehaz and M Sohel Rahman.  Multiresunet: Rethinking the u-net architecture for multimodal biomedical image segmentation.  Neural networks, 121:74–87, 2020.
  * [50] Jiaxu Leng, Ying Liu, Tianlin Zhang, Pei Quan, and Zhenyu Cui.  Context-aware u-net for biomedical image segmentation.  In 2018 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pages 2535–2538. IEEE, 2018.
  * [51] Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann.  Tudataset: A collection of benchmark datasets for learning with graphs.  arXiv preprint arXiv:2007.08663, 2020.
  * [52] Jeffrey J Sutherland, Lee A O’brien, and Donald F Weaver.  Spline-fitting with a genetic algorithm: A method for developing classification structure- activity relationships.  Journal of chemical information and computer sciences, 43(6):1906–1915, 2003.
  * [53] Nikil Wale, Ian A Watson, and George Karypis.  Comparison of descriptor spaces for chemical compound retrieval and classification.  Knowledge and Information Systems, 14:347–375, 2008.
  * [54] Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex J Smola, and Hans-Peter Kriegel.  Protein function prediction via graph kernels.  Bioinformatics, 21(suppl_1):i47–i56, 2005.
  * [55] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt.  Weisfeiler-lehman graph kernels.  Journal of Machine Learning Research, 12(9), 2011.
  * [56] Ida Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg.  Brenda, the enzyme database: updates and major new developments.  Nucleic acids research, 32(suppl_1):D431–D433, 2004.
  * [57] Chen Cai and Yusu Wang.  A simple yet effective baseline for non-attributed graph classification.  arXiv preprint arXiv:1811.03508, 2018.
  * [58] Boris Knyazev, Graham W Taylor, and Mohamed Amer.  Understanding attention and generalization in graph neural networks.  Advances in neural information processing systems, 32, 2019.
  * [59] Zhilin Yang, William Cohen, and Ruslan Salakhudinov.  Revisiting semi-supervised learning with graph embeddings.  In International conference on machine learning, pages 40–48. PMLR, 2016.
  * [60] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang.  Geom-gcn: Geometric graph convolutional networks.  arXiv preprint arXiv:2002.05287, 2020.
  * [61] Benedek Rozemberczki, Carl Allen, and Rik Sarkar.  Multi-scale attributed node embedding.  Journal of Complex Networks, 9(2):cnab014, 2021.
  * [62] Tao Li and Jiexiang Wang.  Distributed averaging with random network graphs and noises.  IEEE Transactions on Information Theory, 64(11):7063–7080, 2018.
  * [63] Shurui Gui, Xiner Li, Limei Wang, and Shuiwang Ji.  Good: A graph out-of-distribution benchmark.  Advances in Neural Information Processing Systems, 35:2059–2073, 2022.
  * [64] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  Advances in neural information processing systems, 32, 2019.
  * [65] Matthias Fey and Jan E. Lenssen.  Fast graph representation learning with PyTorch Geometric.  In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
  * [66] Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro.  Size-invariant graph representations for graph classification extrapolations.  In International Conference on Machine Learning, pages 837–851. PMLR, 2021.
  * [67] Yongqiang Chen, Yonggang Zhang, Yatao Bian, Han Yang, MA Kaili, Binghui Xie, Tongliang Liu, Bo Han, and James Cheng.  Learning causally invariant representations for out-of-distribution generalization on graphs.  Advances in Neural Information Processing Systems, 35:22131–22148, 2022.
  * [68] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [69] Jian Du, Shanghang Zhang, Guanhang Wu, José MF Moura, and Soummya Kar.  Topology adaptive graph convolutional networks.  arXiv preprint arXiv:1710.10370, 2017.
  * [70] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  Advances in neural information processing systems, 30, 2017.
  * [71] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602–4609, 2019.
  * [72] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip.  A comprehensive survey on graph neural networks.  IEEE transactions on neural networks and learning systems, 32(1):4–24, 2020.
  * [73] Jinheon Baek, Minki Kang, and Sung Ju Hwang.  Accurate learning of graph representations with graph multiset pooling.  arXiv preprint arXiv:2102.11533, 2021.
  * [74] Oliver Wieder, Stefan Kohlbacher, Mélaine Kuenemann, Arthur Garon, Pierre Ducrot, Thomas Seidel, and Thierry Langer.  A compact review of molecular property prediction with graph neural networks.  Drug Discovery Today: Technologies, 37:1–12, 2020.
  * [75] Caitlyn L Mills, Rohan Garg, Joslynn S Lee, Liang Tian, Alexandru Suciu, Gene D Cooperman, Penny J Beuning, and Mary Jo Ondrechen.  Functional classification of protein structures by local structure matching in graph representation.  Protein Science, 27(6):1125–1135, 2018.
  * [76] Lianke Qin, Zhao Song, and Baocheng Sun.  Is solving graph neural tangent kernel equivalent to training graph neural network?  arXiv preprint arXiv:2309.07452, 2023.
  * [77] Ghaith Mqawass and Petr Popov.  graphlambda: Fusion graph neural networks for binding affinity prediction.  Journal of Chemical Information and Modeling, 2024.
  * [78] Shunxin Xiao, Shiping Wang, Yuanfei Dai, and Wenzhong Guo.  Graph neural networks in node classification: survey and evaluation.  Machine Vision and Applications, 33(1):4, 2022.
  * [79] Wei Ju, Siyu Yi, Yifan Wang, Qingqing Long, Junyu Luo, Zhiping Xiao, and Ming Zhang.  A survey of data-efficient graph learning, 2024.
  * [80] David Camacho, Angel Panizo-LLedot, Gema Bello-Orgaz, Antonio Gonzalez-Pardo, and Erik Cambria.  The four dimensions of social network analysis: An overview of research methods, applications, and software tools.  Information Fusion, 63:88–120, 2020.
  * [81] Zi Ye, Yogan Jaya Kumar, Goh Ong Sing, Fengyan Song, and Junsong Wang.  A comprehensive survey of graph neural networks for knowledge graphs.  IEEE Access, 10:75729–75741, 2022.
  * [82] Smriti Bhagat, Graham Cormode, and S Muthukrishnan.  Node classification in social networks.  Social network data analytics, pages 115–148, 2011.
  * [83] Jianke Yu, Hanchen Wang, Xiaoyang Wang, Zhao Li, Lu Qin, Wenjie Zhang, Jian Liao, and Ying Zhang.  Group-based fraud detection network on e-commerce platforms.  In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 5463–5475, 2023.
  * [84] Hongyang Gao and Shuiwang Ji.  Graph u-nets.  In international conference on machine learning, pages 2083–2092. PMLR, 2019.
  * [85] Fanding Xu, Zhiwei Yang, Lizhuo Wang, Deyu Meng, and Jiangang Long.  Mespool: Molecular edge shrinkage pooling for hierarchical molecular representation learning and property prediction.  Briefings in Bioinformatics, 25(1):bbad423, 2024.
  * [86] Nahian Siddique, Sidike Paheding, Colin P Elkin, and Vijay Devabhaktuni.  U-net and its variants for medical image segmentation: A review of theory and applications.  Ieee Access, 9:82031–82057, 2021.
  * [87] Grégoire Montavon, Matthias Rupp, Vivekanand Gobre, Alvaro Vazquez-Mayagoitia, Katja Hansen, Alexandre Tkatchenko, Klaus-Robert Müller, and O Anatole Von Lilienfeld.  Machine learning of molecular electronic properties in chemical compound space.  New Journal of Physics, 15(9):095003, 2013.
  * [88] Myriam Ciordia, Laura Pérez-Benito, Francisca Delgado, Andrés A Trabanco, and Gary Tresadern.  Application of free energy perturbation for the design of bace1 inhibitors.  Journal of Chemical information and modeling, 56(9):1856–1871, 2016.
  * [89] John S Delaney.  Esol: estimating aqueous solubility directly from molecular structure.  Journal of chemical information and computer sciences, 44(3):1000–1005, 2004.
  * [90] David L Mobley and J Peter Guthrie.  Freesolv: a database of experimental and calculated hydration free energies, with input files.  Journal of computer-aided molecular design, 28:711–720, 2014.
  * [91] Nina Lukashina, Alisa Alenicheva, Elizaveta Vlasova, Artem Kondiukov, Aigul Khakimova, Emil Magerramov, Nikita Churikov, and Aleksei Shpilman.  Lipophilicity prediction with multitask learning and molecular substructures representation.  arXiv preprint arXiv:2011.12117, 2020.

##  Appendix A Related Work

###  A.1 Graph Classification and Graph Regression

Graphs provide an effective tool to represent interaction among different
objects [72]. Graph classification [73] is a fundamental graph machine
learning problem, which aims to classify each graph into its corresponding
category. The majority of current works adopt message passing mechanisms [72],
where each node receives information from its neighbors in a recursive manner.
Then, a graph readout function is adopted to summarize all node
representations into a graph-level representation for downstream
classification. Graph classification has extensive applications in various
domains such as molecular property prediction [74] and protein function
analysis [75]. Graph regression [76] is close to graph classification which
maps graph-level data into continuous vectors. Researchers usually utilize
graph regression to formulate molecular property predictions [77]. Graph
pooling has been an important topic in graph-level tasks [25, 26, 27, 28, 29,
30, 31, 32, 33, 34, 35, 36, 37, 38, 39], which generally utilize a
hierarchical way to refine the graph structures [40, 41]. In this work, we
generally study the performance of graph pooling on graph-level tasks and
validate the effectiveness of graph pooling approaches in most cases.

###  A.2 Node Classification

Node classification aims to classify each node in a graph based on its
attributes and relationship with the other nodes [78, 79]. Node classification
has various applications in the real world, including social network analysis
[80], knowledge graphs [81], bioinformatics [82] and online commerce services
[83]. Graph neural networks have been widely utilized to solve the problem by
learning semantics information across nodes by neighborhood propagation. Since
graph pooling would reduce the number of nodes, recent works utilize a U-Net
architecture [84], which involves down-sampling and up-sampling with residue
connections. In this work, we systematically evaluate the performance of graph
pooling on node classification and observe that graph pooling has limited
improvement compared with basic graph neural network architectures.

##  Appendix B Details of Selected Pooling Methods

TopKPool [25]. TopKPool utilizes the attention mechanism to learn the scores
of different nodes and then selects the nodes with top scores, which can learn
important local portions from original graphs.

SAGPool [26]. SAGPool utilizes a different graph neural network to learn
importance scores, which can guide the pooling process effectively.

ASAPool [27]. ASAPool considers the neighboring subgraphs to represent nodes
and then adopts the attention mechanism to generate subgraph representations.
The importance nodes are selected by a graph neural networks with local
extremum information.

PANPool [28]. PANPool constructs the maximal entropy transition (MET) matrix
based on graph Laplacian, which can generate importance scores for different
nodes.

COPool [29]. COPool learns pooled representations from the complimentary edge
and node views. The edge view comes from high-order semantics information
while the node view stems from importance scores from the cut proximity
matrix.

CGIPool [30]. CGIPool incorporates the mutual information optimization into
graph pooling, which can enhance the graph-level relationships between the
original graph and the pooled graph.

KMISPool [31]. KMISPool incorporates the Maximal k-Independent Sets (k-MIS)
into graph pooling, which can detect the importance nodes in the graph with
topological preserved.

GSAPool [32]. GSAPool integrates both structural and attribute information in
different components. These scores from different components are then fused to
guide the graph pooling process.

HGPSLPool [33]. HGPSLPool not only utilizes graph pooling to determine
important nodes from the original graph, but also leverages graph structure
learning to explore the topological information in the pooled graph.

AsymCheegerCutPool [34]. AsymCheegerCutPool conducts graph clustering to
generate the assignment of each node according to graph total variation (GTV).
Each cluster is aggregated during graph pooling in a hierarchical manner.

DiffPool [35]. DiffPool introduces a learnable soft assignment of each node
during graph clustering, and then maps each cluster into the coarsened nodes
in the pooling graph.

MincutPool [36]. MincutPool relaxes the classic normalized mincut problem into
a continuous fashion, and then optimizes a graph neural network to achieve
this. The graph clustering results are adopted to guide the graph pooling
process.

DMoNPool [37]. DMoNPool introduces an objective based on modularity for graph
clustering and then adds a regularization term to avoid trivial solutions
during optimization. Similarly, graph clustering results are leveraged for
graph pooling.

HoscPool [38]. HoscPool combines higher-order relationships in the graph with
graph pooling based on motif conductance. It minimizes a relaxed motif
spectral clustering objective and involves multiple motifs to learn
hierarchical semantics.

JustBalancePool [39]. JustBalancePool consists of two components. On the one
hand, it aims to reduces the local quadratic variation during graph
clustering. On the other hand, it involves a balanced term to reduce the risk
of degenerate solutions.

##  Appendix C Additional Experimental Details

###  C.1 Graph Classification

The classification model comprises three primary components: SAGEConv layers,
pooling methods, and a global average pooling layer. The hidden and output
channels for this model are both set to 64. Initially, the data passes through
three SAGEConv layers with ReLU activation functions, followed by two pooling
layers as well as a global average pooling layer. The embedding output from
this global layer undergoes further processing through a linear layer with
ReLU activation, with dimensions (64, 32), followed by another linear layer
without any activation function but with dimensions (32, number of classes).
The final output can be available after applying softmax to the embedding
output. Hyperparameter tuning is not conducted due to limitations in
computational resources and time. All models use the Adam optimizer with a
learning rate of 0.001 and are trained for 200 epochs by minimizing the
negative log-likelihood loss function. The whole data is divided into
training, validation, and test sets (70%, 15%, and 15% ratios), and each trial
is repeated five times with different random seeds.

###  C.2 Graph Regression

We use a backbone network inspired by MESPool [85] for graph regression. The
model mainly consists of three GINConv layers with ReLU activation functions
and BatchNorm, along with two pooling layers, followed by a global average
pooling layer. All channels (both hidden and output) are set to 64. The
embedding output from the global average pooling layer passes through another
linear layer with ReLU activation, having dimensions (64, 32). Hyperparameter
tuning is not conducted due to limitations in computational resources and
time. All models use the Adam optimizer with a learning rate of 0.001 and are
trained for 200 epochs by minimizing the negative log-likelihood loss
function. The data is split uniformly into training, validation, and test sets
in ratios of 80%, 10%, and 10% respectively. Each experiment is carried out
five times using different random seeds.

###  C.3 Node Classification

For node classification, we utilize a U-net architecture, which we divide into
a downsampling convolutional part and an upsampling convolutional part [86].
The downsampling convolutional section includes two SAGEConv layers with ReLU
activation functions, with pooling applied between these layers. In the
upsampling convolutional section, we use the indices saved during pooling for
upsampling, restoring features to their pre-pooling size. The upsampled
features are then fused with the corresponding residual features from the
downsampling path, either through summation or concatenation. Finally, the
fused features are processed and activated through a SAGEConv layer.

Due to constraints in computational resources and time, we do not perform
hyperparameter tuning. All models employ the Adam optimizer with a learning
rate set to 0.001 and are trained for 200 epochs using cross-entropy loss. All
data are processed using a 5-fold cross-validation and are run on five
different seeds.

##  Appendix D Detailed Description of Datasets

###  D.1 Graph Classification

Table 7 provides descriptive statistics of the selected datasets, which
indicates that our chosen datasets encompass graph data of varying scales and
features. This diversity establishes a robust foundation for our benchmarking
research. The following are detailed descriptions of these datasets:

PROTEINS represents protein structures; nodes denote secondary structure
elements (SSEs) and the edges indicate the relationships between these SSEs
that are in close proximity. The primary goal is to classify each protein into
different classes, i.e., a non-enzyme or an enzyme based on their amino acid
sequences and topological characteristics. The dataset covers diverse protein
structures [54].

PROTEINS_full is an extended version of PROTEINS, which includes the node
attributes as well. The node attribute corresponds to different properties of
SSEs including the polarity and the polarizability [54].

NCI1 is a collection of chemical compound graphs. Originating from the
National Cancer Institute (NCI) database, each graph sample is a compound in
which nodes represent atoms and edges represent the bonds between them. The
dataset is binary-class labeled, indicating biological activity via compounds’
anti-cancer activity against specific cell lines [53].

NCI109 is also a collection of chemical compound graphs derived from the NCI
database. Similarly, each node in the graph denotes an atom and each edge
denotes a bond. The two classes in NCI109 are about compounds’ ability to
inhibit or interact with the specified cancer cell line [53].

ENZYMES is developed to classify each enzyme into one of six EC (Enzyme
Commission) top-level classes. Each graph at hand describes a protein in a way
that nodes represent secondary structure elements (SSEs) while edges show the
relationship between these SSEs either in space or sequence [56].

BZR consists of molecular graphs that represent chemical compounds. Each graph
in this dataset is a chemical compound where nodes are atoms and edges are the
chemical bonds between them. The classification task is focused on classifying
compounds based on their biological activity with respect to binding with
benzodiazepine receptors. In other words, the binary label of each graph can
indicate binding or non-binding status to the benzodiazepine receptor [52].

IMDB-M is a collection of social network graphs derived from the Internet
Movie Database (IMDB). Each graph is about a collaboration network from movies
whereby nodes stand for actors or actresses and edges indicate that the two
actors appeared in the same movie. The dataset comprises three classes
reflecting the movie genres [57].

COLORS-3 is a collection of artificially generated graphs. The dataset’s
primary target is to classify these graphs based on their color distribution
patterns and structural properties [58].

D&D is a dataset of protein graphs. Each graph in this dataset represents a
protein, with nodes corresponding to amino acids and edges corresponding to
the spatial or sequential proximity between these amino acids. The primary
objective of the D&D dataset is to classify proteins into one of two
categories, i.e., enzymes or non-enzymes [55].

Table 7: Summary statistics of datasets for graph classification.

Datasets | Graphs | Classes | Avg. Nodes | Avg. Edges | Node Attr.
---|---|---|---|---|---
PROTEINS | 1,113 | 2 | 39.06 | 72.82 | \+ (1)
PROTEINS_full | 1,113 | 2 | 39.06 | 72.82 | \+ (29)
NCI1 | 4,110 | 2 | 29.87 | 32.30 | -
NCI109 | 4,127 | 2 | 29.68 | 32.13 | -
ENZYMES | 600 | 6 | 32.63 | 62.14 | \+ (18)
BZR | 405 | 2 | 35.75 | 38.36 | \+ (3)
IMDB-M | 1,500 | 3 | 13.00 | 65.94 | -
COLORS-3 | 10,500 | 11 | 61.31 | 91.03 | \+ (4)
D&D | 1,178 | 2 | 284.32 | 715.66 | -

###  D.2 Graph Regression

Table 8 provides an overview of the selected datasets in terms of their task
numbers, compounds and other features, including splits, and metrics. A more
detailed description is provided below.

QM8 is a benchmark dataset in computational chemistry, which is developed to
facilitate the development and evaluation of machine learning approaches for
quantum mechanical property prediction. It contains approximately 21,786
molecular structures, each characterized by their calculated properties using
quantum chemistry methods, specifically focusing on electronic spectra [10,
87].

BACE is a collection of biochemical data used to evaluate computational
methods for drug discovery. The dataset includes a total of 1,522 compounds,
each annotated with their binding affinities, as well as molecular descriptors
and fingerprints to facilitate the development and assessment of machine
learning models [10, 88].

ESOL is a prominent resource in cheminformatics, which is leveraged to
evaluate machine learning models on the prediction of aqueous solubility of
small molecules. The dataset, derived from the work of Delaney, consists of a
diverse range of chemical compounds with experimentally determined solubility
values expressed in logS, where S is the solubility in mols per liter. It
includes 1128 compounds, serving as a benchmark dataset for solubility
prediction tasks [89, 10].

FreeSolv is a dataset containing hydration-free energies for small molecules
in an aqueous solution. It comprises data for a wide range of organic
molecules, providing both experimental values and calculated predictions based
on molecular dynamics simulations [90, 10].

Lipophilicity is primarily utilized for studying and evaluating molecular
lipophilicity. This dataset comprises 4,200 compounds sourced from the ChEMBL
database, with experimentally measured partition coefficient (logD) values
that reflect the distribution behavior of compounds in a water-octanol system
[91, 10].

Table 8: Details of datasets for graph regression.

Datasets | Data type | Tasks | Compounds | Split | Metrics
---|---|---|---|---|---
QM8 | SMILES, 3D coordinates | 12 | 21,786 | Random | MAE
BACE | SMILES | 1 | 1,522 | Scaffold | AUROC
ESOL | SMILES | 1 | 1,128 | Random | RMSE
FreeSolv | SMILES | 1 | 643 | Random | RMSE
Lipophilicity | SMILES | 1 | 4,200 | Random | RMSE

###  D.3 Node Classification

Table 9 presents descriptive statistics of the seven datasets used for node
classification. It is evident that there is a significant variance in the
scale of the selected datasets and each of them show different
characteristics. Further background information and details about these
datasets are provided below.

Cora comprises a collection of 2,708 scientific publications classified into
seven distinct categories. Each publication in the dataset is represented as a
node in a citation network, where edges indicate citation relationships
between papers [59].

CiteSeer is a widely used citation network dataset. It comprises scientific
publications categorized into six classes, with each publication represented
by a 3,327-dimensional binary vector recording the presence or absence of
specific words [59].

PubMed consists of scientific publications from the PubMed database,
categorized into three classes based on their Medical Subject Headings (MeSH)
terms. Each node is represented by a sparse bag-of-words vector derived from
the content of the corresponding publication [59].

Table 9: Summary statistics of datasets for node classification.

Datasets | Number of Nodes | Number of Edges | Number of Features | Number of Classes
---|---|---|---|---
Cora | 2,708 | 10,556 | 1,433 | 7
CiteSeer | 3,327 | 9,104 | 3,703 | 6
PubMed | 19,717 | 88,648 | 500 | 3
Cornell | 183 | 298 | 1,703 | 5
Texas | 183 | 325 | 1,703 | 5
Wisconsin | 251 | 515 | 1,703 | 5
Github | 37,700 | 578,006 | 0 | 2

Cornell, Texas, and Wisconsin consist of nodes that represent web pages and
edges which denote hyperlinks between these pages. Each node has a class label
which typically denotes the topic of the web page; this allows tasks including
node classification and link prediction to be performed. The datasets have
different sizes. In particular, Cornell and Texas have 183 nodes while
Wisconsin has 251 nodes. These networks are relatively small and sparse when
compared to other larger citation datasets [60].

Github includes rich node attributes representing the diverse features of
developers, such as their interests, skills, and contributions to various
repositories. Additionally, the edges within the network capture the
interactions and collaborations among developers, which result in a multi-
faceted graph structure [61].

###  D.4 Out-of-distribution shifts

Size shifts. For the selected datasets including D&D, PROTEINS, NCI1, and
NCI109, we utilize the data provided by the previous work [66]. In this setup,
the graphs with the smallest 50% of nodes are used as the training set, those
with the largest 20% of nodes are used as the test set, and the remaining
graphs are used as the validation set. The data can be downloaded from
https://www.dropbox.com/s/38eg3twe4dd1hbt/data.zip.

Density shifts. For the selected datasets, we divide the datasets based on
graph density. In particular, the 50% of graphs with the lowest density are
used as the training set, the 20% with the highest density are used as the
test set, and the remaining graphs are used as the validation set. After
applying density shifts, the following densities are observed: for D&D, the
training set density is 0.0274, the validation set density is 0.0567, and the
test set density is 0.1245; for PROTEINS, the training set density is 0.1709,
the validation set density is 0.4183, and the test set density is 1.0752; for
NCI1, the training set density is 0.1229, the validation set density is
0.1976, and the test set density is 0.2922; for NCI109, the training set
density is 0.1248, the validation set density is 0.2000, and the test set
density is 0.2916.

##  Appendix E Additional Experiments

Table 10 presents the results of fixing the backbone as GraphConv and setting
the pooling ratios of the sparse pooling method to 0.1, 0.3, 0.5, 0.7, and
0.9, respectively. The pooling ratios for dense pooling remain unchanged. As
shown in Table 10, with the increase in pooling ratio, the accuracy exhibits a
fluctuating upward trend. Among the sparse pooling methods, HGPSLPool and
KMISPool consistently demonstrate superior performance. However, changes in
the pooling ratio also result in varying stability across different methods.
Furthermore, compared to binary classification tasks, the accuracy improvement
with the increasing pooling ratio is more evident in multi-class
classification tasks. This indicate that researchers should consider using
larger pooling ratios when conducting studies on multi-class classification.

Table 11 presents the results of using GCNConv as the backbone model while
varying the pooling ratio. It can be observed that the overall accuracy of
GCNConv is lower than that of GraphConv. Generally, as the pooling ratio
increases, classification accuracy improves and dense pooling methods are more
powerful than sparse pooling methods at the cost of increased computation
time. With the backbone of GCNConv, CGIPool and KMISPool perform best among
the sparse pooling methods. Additionally, the impact of the pooling ratio on
multi-class classification accuracy remains significantly greater than its
impact on binary classification accuracy.

Table 12 presents the results of varying the pooling ratio (0.1, 0.3, 0.5,
0.7, 0.9) in node classification tasks using GraphConv as the backbone model.
Overall, the change in pooling ratio has a minimal impact on the accuracy of
node classification tasks. For most methods, accuracy does not improve with an
increased pooling ratio but rather fluctuates. The two best-performing methods
overall are TopKPool and GSAPool. Additionally, higher pooling ratios result
in increased computational costs for some methods, such as HGPSLPool and
ASAPool. This indicates that when performing node classification, graph
pooling methods should be used more cautiously, and excessive concern over
pooling ratios may be unnecessary.

Table 13 presents the results of node classification with GCNConv as the
backbone model, varying the pooling ratio from 0.1, 0.3, 0.5, 0.7, to 0.9. It
can be observed that, except for HGPSLPool, the performance of most methods
with GCNConv is inferior to that with GraphConv. The performance of different
pooling methods varies across different pooling ratios, making it difficult to
identify a single pooling method that consistently outperforms others at all
pooling ratios. Nevertheless, CGIPool and KMISPool still relatively
demonstrate the best overall performance. Additionally, increasing the pooling
ratio does not consistently improve node classification tasks. Lastly, GCNConv
has higher memory consumption compared to GraphConv, particularly for ASAPool,
PANPool, COPool, and HGPSLPool.

In summary, based on the aforementioned experiments, GraphConv is recommended
as the backbone model over GCNConv for both graph classification and node
classification tasks due to its higher accuracy and lower computational
resource consumption. In terms of graph classification tasks, a larger pooling
ratio generally improves results, especially for multi-class classification
tasks. In contrast, the choice of pooling ratio is not very important for node
classification tasks.

Table 10: Results of graph classification using GraphConv as backbone for
different graph pooling methods and pooling ratios. $\pm$ denotes standard
deviation. OOM denotes out of GPU memory. OOT denotes cannot be computed
within 12 hours.

Methods | PROTEINS |  | NCI1 |  | NCI109 |  | ENZYMES |  | BZR |  | IMDB-M |  | COLORS-3
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Sparse Pooling, pooling ratio = 0.1 |  |  |  |
TopKPool | 70.48$\pm$3.99 |  | 73.44$\pm$1.69 |  | 58.26$\pm$2.22 |  | 31.11$\pm$5.26 |  | 81.94$\pm$1.58 |  | 40.71$\pm$3.21 |  | 22.59$\pm$7.61
SAGPool | 71.31$\pm$3.40 |  | 73.00$\pm$1.20 |  | 64.48$\pm$2.16 |  | 26.44$\pm$4.63 |  | 84.52$\pm$3.16 |  | 37.96$\pm$2.98 |  | 29.17$\pm$2.48
ASAPool | 70.36$\pm$4.66 |  | 76.47$\pm$2.13 |  | 68.19$\pm$2.97 |  | 21.11$\pm$6.67 |  | 85.48$\pm$2.70 |  | 41.96$\pm$2.48 |  | 40.23$\pm$1.90
PANPool | 68.33$\pm$1.09 |  | 77.86$\pm$0.92 |  | 65.00$\pm$1.22 |  | 30.89$\pm$4.73 |  | 86.45$\pm$3.32 |  | 39.20$\pm$2.34 |  | 21.57$\pm$0.75
COPool | 70.36$\pm$1.48 |  | 75.59$\pm$0.96 |  | 66.97$\pm$2.26 |  | 39.11$\pm$4.63 |  | 81.61$\pm$1.29 |  | 35.11$\pm$2.55 |  | 28.25$\pm$2.91
CGIPool | 67.86$\pm$3.63 |  | 76.21$\pm$1.71 |  | 64.84$\pm$2.83 |  | 40.00$\pm$5.26 |  | 84.52$\pm$2.99 |  | 44.98$\pm$2.49 |  | 28.27$\pm$7.25
KMISPool | 75.60$\pm$1.13 |  | 76.34$\pm$0.77 |  | 73.29$\pm$1.31 |  | 35.11$\pm$9.34 |  | 85.48$\pm$5.40 |  | 38.76$\pm$1.76 |  | 57.35$\pm$2.29
GSAPool | 71.67$\pm$3.03 |  | 74.42$\pm$2.36 |  | 66.19$\pm$3.58 |  | 27.56$\pm$1.91 |  | 83.87$\pm$1.02 |  | 40.71$\pm$1.72 |  | 28.32$\pm$6.78
HGPSLPool | 75.95$\pm$1.10 |  | 77.21$\pm$0.85 |  | 68.03$\pm$1.82 |  | 32.00$\pm$3.74 |  | 86.77$\pm$2.77 |  | 33.69$\pm$0.81 |  | 34.80$\pm$1.43
Sparse Pooling, pooling ratio = 0.3 |  |  |  |
TopKPool | 70.48$\pm$3.99 |  | 70.99$\pm$0.78 |  | 65.55$\pm$0.80 |  | 28.22$\pm$2.86 |  | 83.23$\pm$1.64 |  | 41.24$\pm$3.95 |  | 28.76$\pm$5.69
SAGPool | 70.83$\pm$3.30 |  | 72.03$\pm$1.95 |  | 70.26$\pm$2.07 |  | 27.33$\pm$4.01 |  | 83.55$\pm$2.14 |  | 41.60$\pm$2.15 |  | 35.58$\pm$3.54
ASAPool | 74.40$\pm$3.43 |  | 76.82$\pm$0.41 |  | 72.52$\pm$1.40 |  | 26.00$\pm$9.10 |  | 82.58$\pm$2.37 |  | 37.96$\pm$4.56 |  | 50.46$\pm$1.99
PANPool | 68.33$\pm$1.52 |  | 77.70$\pm$1.92 |  | 68.23$\pm$1.79 |  | 32.44$\pm$3.25 |  | 82.90$\pm$2.99 |  | 40.89$\pm$2.71 |  | 32.55$\pm$0.99
COPool | 70.71$\pm$0.69 |  | 74.26$\pm$2.05 |  | 71.16$\pm$2.07 |  | 36.22$\pm$8.96 |  | 83.23$\pm$2.62 |  | 39.02$\pm$3.40 |  | 33.16$\pm$2.87
CGIPool | 68.69$\pm$4.27 |  | 76.11$\pm$1.53 |  | 68.55$\pm$2.33 |  | 29.56$\pm$6.31 |  | 80.00$\pm$2.19 |  | 38.04$\pm$3.27 |  | 39.25$\pm$5.92
KMISPool | 77.02$\pm$1.53 |  | 76.95$\pm$0.65 |  | 73.48$\pm$1.42 |  | 32.22$\pm$8.40 |  | 84.84$\pm$4.96 |  | 39.02$\pm$2.49 |  | 57.35$\pm$2.29
GSAPool | 70.71$\pm$2.80 |  | 74.23$\pm$1.61 |  | 70.65$\pm$1.03 |  | 28.22$\pm$7.88 |  | 84.19$\pm$2.58 |  | 38.76$\pm$2.27 |  | 35.18$\pm$4.46
HGPSLPool | 75.36$\pm$1.23 |  | 77.99$\pm$1.32 |  | 71.61$\pm$1.00 |  | 30.00$\pm$7.34 |  | 84.84$\pm$3.62 |  | 38.76$\pm$2.17 |  | 50.32$\pm$1.38
Sparse Pooling, pooling ratio = 0.5 |  |  |  |
TopKPool | 73.10$\pm$1.09 |  | 70.57$\pm$1.56 |  | 69.68$\pm$3.15 |  | 39.33$\pm$5.10 |  | 82.26$\pm$4.45 |  | 39.82$\pm$1.11 |  | 35.06$\pm$5.96
SAGPool | 72.62$\pm$3.22 |  | 71.96$\pm$1.88 |  | 71.94$\pm$2.19 |  | 33.33$\pm$1.99 |  | 83.55$\pm$2.37 |  | 39.64$\pm$2.15 |  | 41.83$\pm$4.26
ASAPool | 71.90$\pm$5.10 |  | 76.11$\pm$1.35 |  | 72.52$\pm$1.40 |  | 22.67$\pm$9.85 |  | 83.55$\pm$3.13 |  | 35.38$\pm$5.10 |  | 59.79$\pm$2.37
PANPool | 73.81$\pm$1.88 |  | 77.83$\pm$1.61 |  | 70.35$\pm$1.82 |  | 41.11$\pm$4.61 |  | 86.13$\pm$2.19 |  | 39.02$\pm$3.57 |  | 41.29$\pm$1.03
COPool | 73.21$\pm$1.92 |  | 74.75$\pm$2.40 |  | 72.87$\pm$2.17 |  | 38.22$\pm$2.06 |  | 82.90$\pm$1.29 |  | 39.29$\pm$2.36 |  | 38.43$\pm$2.52
CGIPool | 74.29$\pm$1.15 |  | 76.73$\pm$2.37 |  | 71.90$\pm$0.89 |  | 28.67$\pm$5.51 |  | 84.84$\pm$5.26 |  | 37.16$\pm$3.33 |  | 41.32$\pm$4.06
KMISPool | 75.95$\pm$0.97 |  | 76.30$\pm$1.06 |  | 74.03$\pm$0.54 |  | 33.11$\pm$8.36 |  | 84.84$\pm$3.47 |  | 38.76$\pm$2.32 |  | 57.37$\pm$1.94
GSAPool | 74.05$\pm$2.98 |  | 74.04$\pm$1.98 |  | 72.16$\pm$2.73 |  | 33.11$\pm$2.57 |  | 82.90$\pm$2.62 |  | 41.33$\pm$0.80 |  | 38.22$\pm$6.40
HGPSLPool | 74.64$\pm$1.58 |  | 77.41$\pm$1.39 |  | 73.61$\pm$1.08 |  | 29.11$\pm$3.94 |  | 85.16$\pm$2.58 |  | 41.60$\pm$1.70 |  | 62.30$\pm$2.55
Sparse Pooling, pooling ratio = 0.7 |  |  |  |
TopKPool | 73.81$\pm$1.25 |  | 74.88$\pm$1.04 |  | 72.94$\pm$1.04 |  | 37.78$\pm$4.61 |  | 81.29$\pm$3.16 |  | 40.44$\pm$2.77 |  | 42.77$\pm$4.11
SAGPool | 72.86$\pm$1.90 |  | 74.55$\pm$1.41 |  | 73.19$\pm$2.33 |  | 41.11$\pm$5.07 |  | 84.84$\pm$3.32 |  | 39.82$\pm$2.97 |  | 41.83$\pm$4.26
ASAPool | 74.05$\pm$2.25 |  | 79.06$\pm$0.68 |  | 74.87$\pm$1.26 |  | 18.00$\pm$1.30 |  | 85.48$\pm$3.68 |  | 34.40$\pm$4.44 |  | 59.79$\pm$2.37
PANPool | 74.64$\pm$1.44 |  | 77.05$\pm$0.39 |  | 74.35$\pm$0.87 |  | 42.00$\pm$6.02 |  | 85.16$\pm$3.13 |  | 41.33$\pm$1.76 |  | 41.29$\pm$1.03
COPool | 74.17$\pm$1.23 |  | 75.20$\pm$0.90 |  | 73.97$\pm$2.58 |  | 39.56$\pm$5.60 |  | 81.29$\pm$2.19 |  | 39.64$\pm$4.14 |  | 38.43$\pm$2.52
CGIPool | 75.83$\pm$2.51 |  | 78.38$\pm$1.70 |  | 74.71$\pm$0.97 |  | 28.67$\pm$5.51 |  | 84.84$\pm$5.26 |  | 37.16$\pm$3.33 |  | 41.32$\pm$4.06
KMISPool | 76.67$\pm$1.02 |  | 76.66$\pm$0.42 |  | 73.06$\pm$1.45 |  | 34.00$\pm$6.76 |  | 85.16$\pm$2.37 |  | 37.78$\pm$5.36 |  | 41.32$\pm$4.06
GSAPool | 72.14$\pm$1.52 |  | 75.49$\pm$1.14 |  | 72.77$\pm$1.39 |  | 38.00$\pm$5.77 |  | 83.55$\pm$2.37 |  | 41.87$\pm$3.17 |  | 38.22$\pm$6.40
HGPSLPool | 75.00$\pm$2.23 |  | 78.28$\pm$1.00 |  | 73.84$\pm$0.55 |  | 24.67$\pm$4.52 |  | 86.45$\pm$1.94 |  | 41.33$\pm$0.97 |  | 62.30$\pm$2.55
Sparse Pooling, pooling ratio = 0.9 |  |  |  |
TopKPool | 73.21$\pm$1.92 |  | 75.82$\pm$1.45 |  | 73.19$\pm$1.73 |  | 39.56$\pm$3.27 |  | 82.58$\pm$3.13 |  | 41.16$\pm$1.58 |  | 47.87$\pm$2.36
SAGPool | 72.74$\pm$0.95 |  | 76.21$\pm$1.96 |  | 74.45$\pm$0.56 |  | 39.33$\pm$2.59 |  | 81.61$\pm$2.19 |  | 41.24$\pm$3.48 |  | 49.66$\pm$2.52
ASAPool | 73.69$\pm$1.48 |  | 79.09$\pm$0.45 |  | 77.16$\pm$1.42 |  | 19.33$\pm$1.51 |  | 86.77$\pm$1.88 |  | 34.84$\pm$4.11 |  | 72.74$\pm$1.21
PANPool | 74.88$\pm$1.02 |  | 77.99$\pm$0.72 |  | 76.06$\pm$1.05 |  | 36.44$\pm$4.73 |  | 83.55$\pm$1.21 |  | 39.11$\pm$1.93 |  | 64.61$\pm$2.22
COPool | 74.52$\pm$1.38 |  | 77.08$\pm$2.42 |  | 75.03$\pm$1.02 |  | 36.44$\pm$2.85 |  | 81.94$\pm$1.21 |  | 35.73$\pm$2.31 |  | 43.67$\pm$1.68
CGIPool | 72.62$\pm$1.92 |  | 79.29$\pm$1.19 |  | 75.29$\pm$0.98 |  | 31.33$\pm$4.89 |  | 82.90$\pm$0.79 |  | 34.84$\pm$3.38 |  | 44.35$\pm$1.25
KMISPool | 74.29$\pm$3.14 |  | 75.85$\pm$0.93 |  | 74.03$\pm$1.30 |  | 31.11$\pm$8.66 |  | 84.84$\pm$4.85 |  | 38.84$\pm$1.91 |  | 57.35$\pm$2.29
GSAPool | 72.38$\pm$1.83 |  | 76.79$\pm$1.70 |  | 73.42$\pm$0.76 |  | 33.33$\pm$2.33 |  | 83.23$\pm$2.99 |  | 40.62$\pm$3.26 |  | 52.43$\pm$2.50
HGPSLPool | 75.60$\pm$1.46 |  | 77.21$\pm$1.53 |  | 74.84$\pm$0.58 |  | 27.11$\pm$5.10 |  | 86.45$\pm$3.62 |  | 38.22$\pm$3.85 |  | 87.12$\pm$1.82
Dense Pooling |  |  |  |
AsymCheegerCutPool | 75.12$\pm$1.05 |  | 73.87$\pm$0.89 |  | 72.74$\pm$1.03 |  | 31.78$\pm$3.19 |  | 83.55$\pm$2.77 |  | 43.02$\pm$3.46 |  | OOT
DiffPool | 75.00$\pm$0.77 |  | 78.38$\pm$0.43 |  | 79.81$\pm$0.96 |  | 35.33$\pm$6.38 |  | 84.19$\pm$1.88 |  | 47.73$\pm$1.72 |  | OOT
MincutPool | 73.54$\pm$5.56 |  | 78.90$\pm$0.99 |  | 77.84$\pm$1.78 |  | 38.00$\pm$2.15 |  | 80.65$\pm$2.70 |  | 39.02$\pm$5.07 |  | OOT
DMoNPool | 75.49$\pm$1.94 |  | 74.46$\pm$0.79 |  | 72.71$\pm$0.55 |  | 41.33$\pm$3.81 |  | 82.58$\pm$1.88 |  | 51.20$\pm$2.44 |  | OOT
HoscPool | 73.05$\pm$2.06 |  | 78.61$\pm$0.69 |  | 77.71$\pm$1.84 |  | 41.11$\pm$4.39 |  | 79.68$\pm$6.00 |  | 52.80$\pm$2.54 |  | OOT
JustBalancePool | 74.51$\pm$2.84 |  | 78.61$\pm$0.69 |  | 77.71$\pm$1.84 |  | 38.00$\pm$4.35 |  | 79.68$\pm$6.00 |  | 52.09$\pm$1.42 |  | OOT

Table 11: Results of graph classification using GCNConv as backbone for
different graph pooling methods and pooling ratios. $\pm$ denotes standard
deviation. OOM denotes out of GPU memory. OOT denotes cannot be computed
within 12 hours.

Methods | PROTEINS |  | NCI1 |  | NCI109 |  | ENZYMES |  | BZR |  | IMDB-M |  | COLORS-3
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Sparse Pooling, pooling ratio = 0.1 |  |  |  |
TopKPool | 69.52$\pm$1.09 |  | 58.83$\pm$2.47 |  | 60.52$\pm$4.30 |  | 29.33$\pm$6.46 |  | 83.23$\pm$0.79 |  | 33.60$\pm$3.69 |  | 18.31$\pm$4.39
SAGPool | 70.36$\pm$4.48 |  | 63.66$\pm$3.17 |  | 63.19$\pm$1.34 |  | 26.22$\pm$5.65 |  | 84.19$\pm$1.21 |  | 39.20$\pm$4.52 |  | 32.24$\pm$1.06
ASAPool | 76.90$\pm$2.01 |  | 64.64$\pm$1.96 |  | 65.00$\pm$1.56 |  | 25.56$\pm$8.04 |  | 81.94$\pm$2.77 |  | 32.53$\pm$2.17 |  | 34.76$\pm$0.77
PANPool | 64.88$\pm$3.63 |  | 65.90$\pm$1.09 |  | 66.48$\pm$1.21 |  | 39.56$\pm$3.49 |  | 84.19$\pm$1.21 |  | 31.47$\pm$2.00 |  | 23.34$\pm$1.36
COPool | 67.98$\pm$2.39 |  | 61.33$\pm$1.99 |  | 60.87$\pm$2.57 |  | 36.22$\pm$4.80 |  | 83.23$\pm$0.79 |  | 40.53$\pm$0.76 |  | 31.21$\pm$1.54
CGIPool | 70.83$\pm$3.30 |  | 66.74$\pm$4.68 |  | 66.19$\pm$3.61 |  | 35.11$\pm$3.62 |  | 85.48$\pm$1.44 |  | 40.98$\pm$1.74 |  | 36.62$\pm$2.99
KMISPool | 75.95$\pm$5.36 |  | 74.26$\pm$1.32 |  | 70.81$\pm$1.43 |  | 23.56$\pm$2.15 |  | 86.13$\pm$1.29 |  | 30.84$\pm$1.42 |  | 57.56$\pm$1.53
GSAPool | 68.81$\pm$1.71 |  | 60.68$\pm$1.97 |  | 63.39$\pm$3.30 |  | 30.22$\pm$4.30 |  | 80.32$\pm$2.58 |  | 33.16$\pm$4.49 |  | 23.05$\pm$6.52
HGPSLPool | 71.43$\pm$0.75 |  | 64.21$\pm$1.73 |  | 64.87$\pm$1.65 |  | 31.33$\pm$2.15 |  | 84.19$\pm$2.58 |  | 31.11$\pm$1.35 |  | 22.84$\pm$0.74
Sparse Pooling, pooling ratio = 0.3 |  |  |  |
TopKPool | 69.88$\pm$1.10 |  | 64.89$\pm$1.20 |  | 63.13$\pm$2.24 |  | 35.56$\pm$7.73 |  | 84.19$\pm$1.58 |  | 32.98$\pm$3.38 |  | 30.84$\pm$6.31
SAGPool | 70.95$\pm$1.52 |  | 69.69$\pm$1.66 |  | 67.94$\pm$1.58 |  | 29.78$\pm$6.34 |  | 83.23$\pm$3.76 |  | 40.80$\pm$2.77 |  | 29.59$\pm$4.17
ASAPool | 75.12$\pm$1.90 |  | 69.79$\pm$0.77 |  | 66.87$\pm$0.84 |  | 23.56$\pm$6.02 |  | 82.58$\pm$1.88 |  | 31.82$\pm$1.90 |  | 45.95$\pm$2.82
PANPool | 67.74$\pm$1.15 |  | 69.92$\pm$0.90 |  | 66.16$\pm$1.25 |  | 34.22$\pm$2.37 |  | 81.94$\pm$1.21 |  | 33.51$\pm$1.98 |  | 34.99$\pm$2.01
COPool | 72.38$\pm$3.03 |  | 69.50$\pm$1.27 |  | 65.68$\pm$1.64 |  | 35.56$\pm$4.50 |  | 81.61$\pm$2.62 |  | 38.13$\pm$3.49 |  | 37.35$\pm$2.24
CGIPool | 73.57$\pm$2.28 |  | 73.84$\pm$2.73 |  | 69.32$\pm$2.52 |  | 34.44$\pm$2.98 |  | 85.16$\pm$2.37 |  | 39.29$\pm$3.11 |  | 41.76$\pm$2.47
KMISPool | 76.90$\pm$6.38 |  | 74.94$\pm$0.36 |  | 71.48$\pm$1.18 |  | 20.89$\pm$3.68 |  | 85.16$\pm$2.37 |  | 31.73$\pm$1.48 |  | 57.55$\pm$2.67
GSAPool | 68.33$\pm$2.14 |  | 67.59$\pm$2.22 |  | 67.94$\pm$2.34 |  | 31.56$\pm$5.65 |  | 84.52$\pm$2.19 |  | 30.76$\pm$2.15 |  | 36.50$\pm$4.39
HGPSLPool | 69.40$\pm$1.90 |  | 69.37$\pm$1.08 |  | 67.71$\pm$1.72 |  | 34.22$\pm$2.47 |  | 83.87$\pm$1.44 |  | 32.62$\pm$1.60 |  | 37.51$\pm$1.02
Sparse Pooling, pooling ratio = 0.5 |  |  |  |
TopKPool | 71.19$\pm$2.25 |  | 66.61$\pm$1.40 |  | 67.71$\pm$2.79 |  | 34.67$\pm$7.32 |  | 84.52$\pm$1.29 |  | 34.04$\pm$1.28 |  | 38.33$\pm$5.81
SAGPool | 73.57$\pm$1.39 |  | 70.50$\pm$1.74 |  | 69.19$\pm$2.32 |  | 33.56$\pm$2.57 |  | 84.52$\pm$1.29 |  | 37.24$\pm$1.87 |  | 39.72$\pm$2.19
ASAPool | 75.71$\pm$1.27 |  | 73.29$\pm$1.07 |  | 69.26$\pm$1.18 |  | 22.00$\pm$4.58 |  | 83.23$\pm$2.81 |  | 34.76$\pm$2.07 |  | 52.72$\pm$1.83
PANPool | 70.60$\pm$1.67 |  | 73.78$\pm$1.12 |  | 70.81$\pm$1.33 |  | 31.56$\pm$2.69 |  | 83.23$\pm$3.32 |  | 34.58$\pm$5.16 |  | 43.31$\pm$1.03
COPool | 72.62$\pm$2.41 |  | 70.89$\pm$1.21 |  | 68.61$\pm$1.66 |  | 31.33$\pm$4.41 |  | 82.90$\pm$2.41 |  | 36.44$\pm$1.26 |  | 39.77$\pm$2.49
CGIPool | 73.57$\pm$1.49 |  | 75.72$\pm$1.65 |  | 72.90$\pm$0.64 |  | 34.00$\pm$3.89 |  | 84.19$\pm$2.58 |  | 39.82$\pm$1.28 |  | 43.66$\pm$3.08
KMISPool | 72.26$\pm$5.07 |  | 76.40$\pm$0.73 |  | 71.65$\pm$1.05 |  | 18.44$\pm$3.49 |  | 85.48$\pm$2.70 |  | 31.56$\pm$1.80 |  | 57.88$\pm$1.55
GSAPool | 72.14$\pm$1.09 |  | 68.65$\pm$1.93 |  | 67.84$\pm$1.71 |  | 33.33$\pm$4.04 |  | 83.55$\pm$1.58 |  | 33.33$\pm$2.37 |  | 46.14$\pm$3.13
HGPSLPool | 71.67$\pm$2.08 |  | 71.83$\pm$1.05 |  | 69.26$\pm$1.46 |  | 30.44$\pm$4.53 |  | 83.87$\pm$1.44 |  | 31.20$\pm$0.18 |  | 50.30$\pm$0.55
Sparse Pooling, pooling ratio = 0.7 |  |  |  |
TopKPool | 70.36$\pm$0.69 |  | 68.85$\pm$2.84 |  | 68.45$\pm$2.03 |  | 33.11$\pm$1.91 |  | 84.19$\pm$2.58 |  | 32.00$\pm$1.66 |  | 45.43$\pm$7.52
SAGPool | 68.69$\pm$1.58 |  | 72.84$\pm$1.07 |  | 70.48$\pm$1.28 |  | 34.44$\pm$3.37 |  | 83.87$\pm$2.70 |  | 38.22$\pm$2.12 |  | 45.90$\pm$1.52
ASAPool | 75.00$\pm$1.96 |  | 72.67$\pm$0.94 |  | 70.45$\pm$0.84 |  | 25.56$\pm$6.32 |  | 86.13$\pm$2.41 |  | 31.11$\pm$2.05 |  | 58.02$\pm$2.00
PANPool | 69.52$\pm$1.43 |  | 71.83$\pm$0.87 |  | 69.84$\pm$1.07 |  | 36.22$\pm$4.69 |  | 83.87$\pm$0.00 |  | 32.27$\pm$0.96 |  | 52.69$\pm$2.90
COPool | 73.21$\pm$1.06 |  | 72.61$\pm$0.97 |  | 70.65$\pm$1.25 |  | 40.89$\pm$6.06 |  | 84.19$\pm$2.77 |  | 40.80$\pm$1.42 |  | 41.81$\pm$2.80
CGIPool | 72.26$\pm$1.04 |  | 73.39$\pm$0.84 |  | 71.84$\pm$2.04 |  | 36.00$\pm$4.75 |  | 82.58$\pm$1.58 |  | 40.62$\pm$2.04 |  | 44.51$\pm$3.79
KMISPool | 76.79$\pm$5.66 |  | 74.98$\pm$0.99 |  | 71.16$\pm$1.58 |  | 23.33$\pm$2.98 |  | 85.48$\pm$1.02 |  | 31.56$\pm$0.56 |  | 58.68$\pm$1.55
GSAPool | 71.90$\pm$3.11 |  | 70.53$\pm$1.18 |  | 68.32$\pm$1.04 |  | 36.89$\pm$1.09 |  | 83.87$\pm$0.00 |  | 32.27$\pm$1.90 |  | 49.71$\pm$8.30
HGPSLPool | 72.02$\pm$1.73 |  | 71.64$\pm$0.72 |  | 68.97$\pm$1.43 |  | 33.78$\pm$3.03 |  | 84.52$\pm$1.29 |  | 32.62$\pm$0.92 |  | 57.67$\pm$2.07
Sparse Pooling, pooling ratio = 0.9 |  |  |  |
TopKPool | 70.83$\pm$1.25 |  | 70.34$\pm$1.80 |  | 69.65$\pm$1.61 |  | 38.22$\pm$2.78 |  | 82.90$\pm$1.29 |  | 32.44$\pm$1.32 |  | 54.48$\pm$4.48
SAGPool | 74.64$\pm$1.53 |  | 73.10$\pm$1.21 |  | 71.29$\pm$0.82 |  | 34.67$\pm$4.52 |  | 82.90$\pm$1.29 |  | 40.80$\pm$1.39 |  | 53.18$\pm$1.71
ASAPool | 73.69$\pm$1.48 |  | 73.48$\pm$1.03 |  | 70.06$\pm$1.06 |  | 24.44$\pm$7.44 |  | 85.16$\pm$2.37 |  | 30.93$\pm$0.87 |  | 58.50$\pm$0.68
PANPool | 70.48$\pm$0.81 |  | 72.77$\pm$1.09 |  | 70.84$\pm$1.23 |  | 40.67$\pm$4.48 |  | 82.90$\pm$1.29 |  | 32.98$\pm$1.98 |  | 61.86$\pm$1.15
COPool | 75.24$\pm$2.46 |  | 74.10$\pm$1.06 |  | 71.35$\pm$1.05 |  | 39.56$\pm$4.19 |  | 80.32$\pm$2.14 |  | 39.56$\pm$2.47 |  | 45.03$\pm$1.19
CGIPool | 70.83$\pm$1.46 |  | 75.49$\pm$1.11 |  | 73.81$\pm$0.42 |  | 38.44$\pm$1.51 |  | 83.23$\pm$3.62 |  | 41.07$\pm$2.35 |  | 48.91$\pm$4.14
KMISPool | 76.79$\pm$5.73 |  | 74.46$\pm$0.98 |  | 70.06$\pm$1.66 |  | 21.56$\pm$1.33 |  | 85.48$\pm$2.28 |  | 30.04$\pm$1.81 |  | 58.82$\pm$1.21
GSAPool | 70.95$\pm$0.69 |  | 71.12$\pm$1.33 |  | 70.65$\pm$1.45 |  | 40.89$\pm$5.04 |  | 85.16$\pm$1.88 |  | 32.98$\pm$0.99 |  | 57.77$\pm$7.03
HGPSLPool | 70.95$\pm$1.66 |  | 72.22$\pm$0.42 |  | 70.35$\pm$1.31 |  | 31.11$\pm$3.98 |  | 83.55$\pm$0.65 |  | 33.07$\pm$1.83 |  | 73.46$\pm$1.70
Dense Pooling |  |  |  |
AsymCheegerCutPool | 77.07$\pm$0.91 |  | 73.61$\pm$0.57 |  | 73.42$\pm$0.89 |  | 45.33$\pm$3.25 |  | 73.87$\pm$2.58 |  | 43.02$\pm$3.46 |  | OOT
DiffPool | 75.24$\pm$0.62 |  | 74.98$\pm$1.37 |  | 73.84$\pm$1.99 |  | 43.78$\pm$6.19 |  | 78.06$\pm$4.52 |  | 47.73$\pm$1.72 |  | OOT
MincutPool | 76.22$\pm$1.22 |  | 68.72$\pm$6.67 |  | 73.35$\pm$1.28 |  | 38.89$\pm$8.78 |  | 81.61$\pm$1.29 |  | 39.02$\pm$5.07 |  | OOT
DMoNPool | 76.71$\pm$0.24 |  | 72.32$\pm$0.39 |  | 73.42$\pm$0.48 |  | 42.67$\pm$5.29 |  | 76.77$\pm$4.03 |  | 51.20$\pm$2.44 |  | OOT
HoscPool | 73.90$\pm$0.60 |  | 74.98$\pm$1.34 |  | 73.94$\pm$0.77 |  | 40.89$\pm$3.25 |  | 78.06$\pm$3.62 |  | 52.80$\pm$2.54 |  | OOT
JustBalancePool | 74.39$\pm$1.39 |  | 74.98$\pm$0.85 |  | 74.26$\pm$0.48 |  | 42.44$\pm$2.76 |  | 78.06$\pm$3.62 |  | 52.09$\pm$1.42 |  | OOT

Table 12: Results of node classification using GraphConv as backbone for
different graph pooling methods and pooling ratios. $\pm$ denotes standard
deviation. OOM denotes out of GPU memory. OOT denotes cannot be computed
within 12 hours.

Methods | Cora |  | Citeseer |  | Pubmed |  | Cornell |  | Texas |  | Wisconsin |  | Github
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Sparse Pooling, pooling ratio = 0.1 |  |  |  |
TopKPool | 86.70$\pm$0.90 |  | 74.85$\pm$0.96 |  | 86.52$\pm$0.67 |  | 81.82$\pm$3.45 |  | 74.91$\pm$7.66 |  | 73.68$\pm$5.20 |  | 82.73$\pm$1.10
SAGPool | 87.00$\pm$1.10 |  | 74.89$\pm$0.63 |  | 85.28$\pm$1.02 |  | 79.64$\pm$2.41 |  | 74.91$\pm$6.94 |  | 72.89$\pm$4.13 |  | 83.65$\pm$0.45
ASAPool | 84.70$\pm$1.90 |  | 74.53$\pm$0.99 |  | 70.14$\pm$2.74 |  | 82.18$\pm$3.71 |  | 77.45$\pm$5.22 |  | 73.16$\pm$4.29 |  | OOM
PANPool | 81.90$\pm$1.10 |  | 73.95$\pm$1.13 |  | 72.47$\pm$2.24 |  | 78.18$\pm$3.25 |  | 76.0$\pm$7.66 |  | 73.95$\pm$3.05 |  | OOM
COPool | 85.70$\pm$0.40 |  | 74.71$\pm$0.99 |  | 78.63$\pm$1.81 |  | 78.91$\pm$1.45 |  | 74.18$\pm$7.75 |  | 72.37$\pm$3.22 |  | OOM
CGIPool | 86.50$\pm$0.90 |  | 74.53$\pm$0.80 |  | 81.96$\pm$4.51 |  | 80.00$\pm$4.45 |  | 75.27$\pm$5.22 |  | 72.11$\pm$3.05 |  | 79.85$\pm$4.62
KMISPool | 77.00$\pm$3.00 |  | 74.57$\pm$1.10 |  | 64.21$\pm$4.07 |  | 80.73$\pm$3.17 |  | 75.27$\pm$5.70 |  | 73.16$\pm$4.60 |  | 83.43$\pm$0.39
GSAPool | 87.00$\pm$0.60 |  | 74.33$\pm$1.10 |  | 85.88$\pm$0.67 |  | 80.00$\pm$4.45 |  | 76.0$\pm$8.24 |  | 73.42$\pm$3.47 |  | 83.60$\pm$0.16
HGPSLPool | 29.40$\pm$2.40 |  | 37.12$\pm$3.31 |  | 45.04$\pm$1.56 |  | 77.45$\pm$4.96 |  | 76.00$\pm$7.58 |  | 70.26$\pm$5.30 |  | OOM
Sparse Pooling, pooling ratio = 0.3 |  |  |  |
TopKPool | 86.99$\pm$1.01 |  | 75.28$\pm$1.24 |  | 86.35$\pm$0.94 |  | 80.36$\pm$4.05 |  | 75.27$\pm$8.50 |  | 73.68$\pm$4.32 |  | 82.93$\pm$0.78
SAGPool | 87.23$\pm$0.99 |  | 74.63$\pm$1.32 |  | 85.16$\pm$1.10 |  | 81.09$\pm$3.74 |  | 75.64$\pm$7.68 |  | 72.37$\pm$3.72 |  | 83.24$\pm$0.52
ASAPool | 77.96$\pm$5.96 |  | 74.17$\pm$0.81 |  | 72.09$\pm$1.99 |  | 79.64$\pm$2.91 |  | 71.27$\pm$6.84 |  | 67.37$\pm$5.73 |  | OOM
PANPool | 44.21$\pm$2.12 |  | 64.34$\pm$2.51 |  | 68.23$\pm$1.79 |  | 78.91$\pm$2.47 |  | 74.91$\pm$6.34 |  | 73.42$\pm$2.26 |  | OOM
COPool | 84.45$\pm$0.96 |  | 74.47$\pm$1.08 |  | 77.52$\pm$1.76 |  | 77.82$\pm$3.13 |  | 72.00$\pm$8.65 |  | 70.79$\pm$4.19 |  | OOM
CGIPool | 86.42$\pm$0.82 |  | 74.27$\pm$0.69 |  | 82.96$\pm$5.22 |  | 81.82$\pm$4.30 |  | 76.00$\pm$6.44 |  | 72.11$\pm$2.68 |  | 79.92$\pm$4.70
KMISPool | 77.32$\pm$2.42 |  | 74.55$\pm$1.24 |  | 65.45$\pm$3.46 |  | 81.09$\pm$3.74 |  | 75.64$\pm$5.59 |  | 72.89$\pm$4.53 |  | 83.60$\pm$0.37
GSAPool | 87.06$\pm$0.61 |  | 74.31$\pm$1.11 |  | 85.58$\pm$1.14 |  | 80.36$\pm$3.71 |  | 76.36$\pm$4.74 |  | 72.37$\pm$3.99 |  | 82.39$\pm$1.44
HGPSLPool | 29.47$\pm$1.21 |  | 28.51$\pm$1.59 |  | 44.10$\pm$0.91 |  | 58.55$\pm$3.71 |  | 62.18$\pm$4.66 |  | 51.32$\pm$3.99 |  | OOM
Sparse Pooling, pooling ratio = 0.5 |  |  |  |
TopKPool | 86.74$\pm$0.68 |  | 75.12$\pm$1.23 |  | 86.34$\pm$0.97 |  | 81.45$\pm$5.06 |  | 72.73$\pm$8.76 |  | 76.05$\pm$4.28 |  | 82.14$\pm$2.23
SAGPool | 86.86$\pm$1.27 |  | 74.51$\pm$1.48 |  | 85.44$\pm$1.24 |  | 80.36$\pm$4.36 |  | 73.45$\pm$5.34 |  | 73.42$\pm$2.93 |  | 79.74$\pm$3.23
ASAPool | 70.97$\pm$7.63 |  | 73.11$\pm$1.55 |  | 69.37$\pm$4.84 |  | 72.00$\pm$6.76 |  | 65.82$\pm$4.93 |  | 62.37$\pm$6.64 |  | OOM
PANPool | 47.87$\pm$2.66 |  | 55.4$\pm$2.66 |  | 67.86$\pm$1.86 |  | 78.55$\pm$2.91 |  | 76.00$\pm$8.32 |  | 71.32$\pm$5.22 |  | OOM
COPool | 83.86$\pm$0.94 |  | 74.43$\pm$1.09 |  | 77.86$\pm$1.88 |  | 76.36$\pm$3.45 |  | 69.82$\pm$8.02 |  | 67.89$\pm$3.59 |  | OOM
CGIPool | 86.49$\pm$0.90 |  | 74.05$\pm$0.93 |  | 82.80$\pm$3.99 |  | 82.55$\pm$4.96 |  | 74.91$\pm$7.58 |  | 72.63$\pm$3.85 |  | 81.28$\pm$3.46
KMISPool | 76.92$\pm$2.52 |  | 74.85$\pm$1.32 |  | 64.51$\pm$4.13 |  | 80.73$\pm$2.47 |  | 76.00$\pm$5.06 |  | 73.42$\pm$3.94 |  | 83.46$\pm$0.21
GSAPool | 86.96$\pm$0.83 |  | 74.51$\pm$1.00 |  | 85.90$\pm$1.21 |  | 81.45$\pm$3.88 |  | 78.55$\pm$5.56 |  | 73.95$\pm$2.93 |  | 80.18$\pm$2.73
HGPSLPool | 30.68$\pm$1.26 |  | 27.63$\pm$0.88 |  | OOM |  | 55.27$\pm$5.82 |  | 58.55$\pm$4.80 |  | 50.53$\pm$2.29 |  | OOM
Sparse Pooling, pooling ratio = 0.7 |  |  |  |
TopKPool | 86.86$\pm$0.93 |  | 74.93$\pm$1.34 |  | 86.09$\pm$0.99 |  | 81.09$\pm$4.08 |  | 76.00$\pm$6.65 |  | 76.58$\pm$5.09 |  | 82.71$\pm$1.00
SAGPool | 86.17$\pm$1.50 |  | 74.31$\pm$1.03 |  | 85.16$\pm$1.17 |  | 79.27$\pm$4.54 |  | 76.36$\pm$4.74 |  | 73.42$\pm$3.67 |  | 80.78$\pm$1.57
ASAPool | 69.69$\pm$6.18 |  | 71.51$\pm$3.63 |  | 69.34$\pm$2.61 |  | 64.36$\pm$5.34 |  | 65.82$\pm$3.13 |  | 61.84$\pm$3.90 |  | OOM
PANPool | 51.56$\pm$2.50 |  | 53.45$\pm$0.74 |  | 68.01$\pm$2.01 |  | 85.16$\pm$3.13 |  | 74.55$\pm$6.8 |  | 68.42$\pm$5.71 |  | OOM
COPool | 84.72$\pm$1.68 |  | 74.23$\pm$1.03 |  | 78.84$\pm$1.49 |  | 75.64$\pm$4.69 |  | 68.00$\pm$6.86 |  | 62.89$\pm$3.76 |  | OOM
CGIPool | 85.46$\pm$2.59 |  | 73.97$\pm$1.05 |  | 81.07$\pm$2.62 |  | 80.73$\pm$3.92 |  | 76.36$\pm$5.14 |  | 72.11$\pm$3.85 |  | 80.36$\pm$3.34
KMISPool | 76.09$\pm$3.12 |  | 74.85$\pm$1.45 |  | 64.89$\pm$3.73 |  | 80.73$\pm$4.08 |  | 75.64$\pm$5.47 |  | 73.95$\pm$4.11 |  | 83.41$\pm$0.30
GSAPool | 86.45$\pm$0.82 |  | 74.33$\pm$1.16 |  | 86.10$\pm$1.05 |  | 81.09$\pm$3.37 |  | 77.45$\pm$6.46 |  | 73.95$\pm$2.11 |  | 80.40$\pm$4.29
HGPSLPool | 30.43$\pm$0.99 |  | 27.53$\pm$0.73 |  | OOM |  | 53.82$\pm$2.95 |  | 59.64$\pm$3.71 |  | 45.53$\pm$2.44 |  | OOM
Sparse Pooling, pooling ratio = 0.9 |  |  |  |
TopKPool | 86.69$\pm$0.92 |  | 74.69$\pm$1.03 |  | 85.49$\pm$0.67 |  | 81.09$\pm$3.92 |  | 77.82$\pm$9.01 |  | 75.00$\pm$3.43 |  | 82.97$\pm$0.58
SAGPool | 85.36$\pm$2.02 |  | 74.15$\pm$1.29 |  | 83.60$\pm$0.70 |  | 80.00$\pm$3.25 |  | 77.09$\pm$5.34 |  | 72.37$\pm$4.71 |  | 79.64$\pm$1.98
ASAPool | 63.44$\pm$7.05 |  | 65.63$\pm$2.88 |  | OOM |  | 61.82$\pm$3.45 |  | 62.91$\pm$4.39 |  | 59.47$\pm$5.85 |  | OOM
PANPool | 52.25$\pm$2.38 |  | 52.15$\pm$2.00 |  | 70.64$\pm$3.47 |  | 79.27$\pm$2.95 |  | 71.64$\pm$5.22 |  | 67.37$\pm$5.09 |  | OOM
COPool | 85.29$\pm$1.34 |  | 74.25$\pm$0.75 |  | 79.32$\pm$1.72 |  | 76.73$\pm$2.12 |  | 68.36$\pm$6.57 |  | 65.79$\pm$4.71 |  | OOM
CGIPool | 86.49$\pm$0.87 |  | 73.05$\pm$1.92 |  | 79.63$\pm$1.74 |  | 81.45$\pm$3.71 |  | 75.27$\pm$7.59 |  | 73.95$\pm$3.67 |  | 81.21$\pm$3.57
KMISPool | 76.43$\pm$2.34 |  | 74.73$\pm$1.23 |  | 64.93$\pm$3.64 |  | 80.36$\pm$3.53 |  | 76.36$\pm$4.88 |  | 72.89$\pm$4.75 |  | 83.33$\pm$0.31
GSAPool | 84.94$\pm$1.63 |  | 74.49$\pm$0.95 |  | 83.72$\pm$1.42 |  | 82.18$\pm$3.53 |  | 77.45$\pm$5.09 |  | 73.16$\pm$3.96 |  | 79.66$\pm$2.51
HGPSLPool | 30.60$\pm$1.28 |  | 27.87$\pm$0.52 |  | OOM |  | 57.82$\pm$3.13 |  | 64.0$\pm$3.53 |  | 51.58$\pm$1.53 |  | OOM

Table 13: Results of node classification using GCNConv as the backbone for
different graph pooling methods and pooling ratios. $\pm$ denotes standard
deviation. OOM denotes out of GPU memory. OOT denotes cannot be computed
within 12 hours.

Methods | Cora |  | Citeseer |  | Pubmed |  | Cornell |  | Texas |  | Wisconsin |  | Github
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Sparse Pooling, pooling ratio = 0.1 |  |  |  |
TopKPool | 88.91$\pm$0.93 |  | 77.56$\pm$0.85 |  | 85.73$\pm$0.34 |  | 48.00$\pm$0.89 |  | 54.18$\pm$4.8 |  | 50.79$\pm$3.49 |  | 86.95$\pm$0.20
SAGPool | 89.18$\pm$0.65 |  | 77.56$\pm$0.81 |  | 85.83$\pm$0.23 |  | 48.73$\pm$3.13 |  | 55.64$\pm$2.95 |  | 51.32$\pm$3.53 |  | 86.83$\pm$0.20
ASAPool | 89.03$\pm$0.84 |  | 77.76$\pm$1.01 |  | 85.74$\pm$0.18 |  | 49.82$\pm$1.45 |  | 54.55$\pm$4.74 |  | 50.53$\pm$3.96 |  | OOM
PANPool | 89.05$\pm$0.96 |  | 77.20$\pm$0.98 |  | 85.88$\pm$0.11 |  | 49.82$\pm$2.18 |  | 56.00$\pm$4.80 |  | 50.53$\pm$3.18 |  | OOM
COPool | 89.00$\pm$0.70 |  | 77.24$\pm$0.90 |  | 85.27$\pm$0.27 |  | 47.64$\pm$2.12 |  | 54.91$\pm$5.32 |  | 51.84$\pm$0.64 |  | 86.68$\pm$0.20
CGIPool | 89.15$\pm$0.84 |  | 77.40$\pm$0.81 |  | 85.80$\pm$0.13 |  | 49.45$\pm$1.78 |  | 54.55$\pm$4.15 |  | 50.79$\pm$3.78 |  | 86.88$\pm$0.22
KMISPool | 89.05$\pm$0.93 |  | 77.60$\pm$0.81 |  | 85.92$\pm$0.07 |  | 48.73$\pm$1.36 |  | 54.18$\pm$3.88 |  | 52.89$\pm$2.11 |  | 86.88$\pm$0.24
GSAPool | 89.05$\pm$0.77 |  | 77.16$\pm$0.92 |  | 85.70$\pm$0.19 |  | 49.09$\pm$1.15 |  | 54.18$\pm$3.88 |  | 51.58$\pm$3.85 |  | 87.12$\pm$0.09
HGPSLPool | 89.00$\pm$0.64 |  | 77.84$\pm$0.67 |  | 86.00$\pm$0.16 |  | 48.73$\pm$2.12 |  | 54.91$\pm$4.21 |  | 51.58$\pm$1.75 |  | OOM
Sparse Pooling, pooling ratio = 0.3 |  |  |  |
TopKPool | 88.63$\pm$1.05 |  | 77.12$\pm$1.16 |  | 85.53$\pm$0.35 |  | 49.09$\pm$2.57 |  | 54.18$\pm$4.80 |  | 51.32$\pm$3.00 |  | 86.89$\pm$0.27
SAGPool | 88.81$\pm$0.73 |  | 77.22$\pm$0.94 |  | 85.68$\pm$0.54 |  | 49.82$\pm$2.95 |  | 55.64$\pm$2.95 |  | 51.32$\pm$3.53 |  | 86.85$\pm$0.21
ASAPool | 89.10$\pm$0.86 |  | 77.40$\pm$1.13 |  | OOM |  | 79.64$\pm$2.91 |  | 54.55$\pm$5.14 |  | 50.53$\pm$3.87 |  | OOM
PANPool | 88.98$\pm$0.70 |  | 77.16$\pm$0.99 |  | 85.64$\pm$0.15 |  | 49.82$\pm$2.47 |  | 56.36$\pm$5.14 |  | 50.00$\pm$2.04 |  | OOM
COPool | 88.73$\pm$0.84 |  | 77.26$\pm$0.89 |  | 84.70$\pm$0.24 |  | 48.73$\pm$1.78 |  | 56.00$\pm$5.80 |  | 51.05$\pm$1.93 |  | 86.61$\pm$0.29
CGIPool | 89.15$\pm$0.84 |  | 77.14$\pm$0.80 |  | 85.92$\pm$0.66 |  | 49.82$\pm$1.85 |  | 54.55$\pm$4.15 |  | 51.05$\pm$3.85 |  | 86.84$\pm$0.12
KMISPool | 89.08$\pm$0.86 |  | 77.59$\pm$0.65 |  | 85.93$\pm$0.06 |  | 48.73$\pm$1.36 |  | 54.18$\pm$3.88 |  | 52.89$\pm$2.11 |  | 86.86$\pm$0.25
GSAPool | 88.91$\pm$1.20 |  | 77.12$\pm$1.16 |  | 86.00$\pm$0.42 |  | 49.09$\pm$1.15 |  | 54.18$\pm$3.88 |  | 51.58$\pm$3.85 |  | 86.95$\pm$0.28
HGPSLPool | 89.03$\pm$0.84 |  | 77.80$\pm$0.71 |  | OOM |  | 48.36$\pm$1.85 |  | 55.27$\pm$3.37 |  | 51.58$\pm$2.26 |  | OOM
Sparse Pooling, pooling ratio = 0.5 |  |  |  |
TopKPool | 88.81$\pm$1.07 |  | 77.08$\pm$1.10 |  | 85.60$\pm$0.06 |  | 47.30$\pm$1.80 |  | 54.18$\pm$4.80 |  | 50.53$\pm$3.39 |  | 86.94$\pm$0.31
SAGPool | 88.98$\pm$0.67 |  | 77.10$\pm$0.82 |  | 86.07$\pm$0.70 |  | 81.09$\pm$3.74 |  | 55.64$\pm$2.72 |  | 51.32$\pm$3.53 |  | 86.88$\pm$0.25
ASAPool | 88.86$\pm$0.96 |  | 77.18$\pm$1.02 |  | OOM |  | 72.00$\pm$6.76 |  | 54.18$\pm$3.88 |  | 50.79$\pm$3.49 |  | OOM
PANPool | 88.95$\pm$0.73 |  | 77.02$\pm$0.90 |  | OOM |  | 78.55$\pm$2.91 |  | 56.36$\pm$5.14 |  | 49.74$\pm$1.93 |  | OOM
COPool | 88.56$\pm$1.02 |  | 76.78$\pm$0.98 |  | OOM |  | 76.36$\pm$3.45 |  | 56.36$\pm$5.98 |  | 52.37$\pm$2.68 |  | 86.57$\pm$0.29
CGIPool | 89.15$\pm$0.84 |  | 77.10$\pm$0.83 |  | 85.80$\pm$0.78 |  | 81.82$\pm$4.30 |  | 54.55$\pm$4.15 |  | 50.79$\pm$3.49 |  | 86.86$\pm$0.08
KMISPool | 89.15$\pm$0.93 |  | 77.58$\pm$0.62 |  | 85.88$\pm$0.14 |  | 81.09$\pm$3.74 |  | 54.18$\pm$3.88 |  | 52.89$\pm$2.11 |  | 86.89$\pm$0.29
GSAPool | 88.98$\pm$1.13 |  | 76.96$\pm$0.93 |  | 86.04$\pm$0.53 |  | 80.36$\pm$3.71 |  | 54.18$\pm$3.88 |  | 51.32$\pm$3.81 |  | 86.94$\pm$0.27
HGPSLPool | 89.08$\pm$0.90 |  | 77.80$\pm$0.96 |  | OOM |  | 58.55$\pm$3.71 |  | 55.27$\pm$4.39 |  | 50.53$\pm$1.78 |  | OOM
Sparse Pooling, pooling ratio = 0.7 |  |  |  |
TopKPool | 88.44$\pm$1.09 |  | 77.08$\pm$0.98 |  | 86.04$\pm$0.41 |  | 47.30$\pm$1.80 |  | 49.09$\pm$1.15 |  | 51.05$\pm$3.85 |  | 86.76$\pm$0.33
SAGPool | 88.91$\pm$0.62 |  | 77.08$\pm$0.80 |  | 85.94$\pm$0.76 |  | 81.09$\pm$3.74 |  | 50.55$\pm$1.36 |  | 51.05$\pm$3.47 |  | 86.99$\pm$0.22
ASAPool | 88.76$\pm$0.72 |  | 76.74$\pm$1.05 |  | OOM |  | 79.64$\pm$2.91 |  | 50.55$\pm$1.36 |  | 49.74$\pm$4.11 |  | OOM
PANPool | 88.59$\pm$1.01 |  | 76.98$\pm$1.03 |  | OOM |  | 78.91$\pm$2.47 |  | 50.91$\pm$1.15 |  | 49.74$\pm$1.93 |  | OOM
COPool | 88.27$\pm$1.09 |  | 76.72$\pm$1.07 |  | OOM |  | 77.82$\pm$3.13 |  | 50.18$\pm$3.74 |  | 51.58$\pm$2.93 |  | 86.57$\pm$0.28
CGIPool | 89.15$\pm$0.84 |  | 77.02$\pm$0.65 |  | 85.50$\pm$0.69 |  | 81.82$\pm$4.30 |  | 49.82$\pm$1.45 |  | 50.26$\pm$3.37 |  | 86.77$\pm$0.14
KMISPool | 89.15$\pm$0.91 |  | 77.52$\pm$0.65 |  | 85.86$\pm$0.10 |  | 81.09$\pm$3.74 |  | 50.55$\pm$1.36 |  | 52.89$\pm$2.11 |  | 86.89$\pm$0.26
GSAPool | 88.66$\pm$0.98 |  | 77.1$\pm$0.72 |  | 86.21$\pm$0.73 |  | 80.36$\pm$3.71 |  | 49.82$\pm$2.72 |  | 51.84$\pm$4.29 |  | 86.83$\pm$0.19
HGPSLPool | 89.03$\pm$0.87 |  | 77.74$\pm$0.85 |  | OOM |  | 58.55$\pm$3.71 |  | 49.82$\pm$2.47 |  | 50.26$\pm$2.26 |  | OOM
Sparse Pooling, pooling ratio = 0.9 |  |  |  |
TopKPool | 88.44$\pm$0.91 |  | 77.08$\pm$0.75 |  | 86.13$\pm$0.34 |  | 47.30$\pm$1.80 |  | 48.73$\pm$2.12 |  | 51.58$\pm$3.05 |  | 86.80$\pm$0.25
SAGPool | 88.83$\pm$0.97 |  | 77.08$\pm$0.81 |  | 85.89$\pm$0.63 |  | 81.09$\pm$3.74 |  | 50.55$\pm$1.36 |  | 50.79$\pm$3.49 |  | 86.87$\pm$0.17
ASAPool | 88.98$\pm$0.74 |  | 76.76$\pm$0.87 |  | OOM |  | 79.64$\pm$2.91 |  | 50.55$\pm$1.36 |  | 50.00$\pm$4.32 |  | OOM
PANPool | 88.76$\pm$1.11 |  | 76.70$\pm$0.92 |  | OOM |  | 78.91$\pm$2.47 |  | 51.27$\pm$2.41 |  | 49.47$\pm$1.97 |  | OOM
COPool | 88.54$\pm$1.09 |  | 76.72$\pm$1.41 |  | OOM |  | 77.82$\pm$3.13 |  | 49.45$\pm$3.13 |  | 51.84$\pm$2.58 |  | 86.54$\pm$0.28
CGIPool | 89.15$\pm$0.84 |  | 77.10$\pm$0.54 |  | 84.95$\pm$0.39 |  | 81.82$\pm$4.30 |  | 50.55$\pm$2.12 |  | 50.79$\pm$3.78 |  | 86.65$\pm$0.25
KMISPool | 89.13$\pm$0.90 |  | 77.64$\pm$0.58 |  | 85.87$\pm$0.09 |  | 81.09$\pm$3.74 |  | 50.18$\pm$0.89 |  | 52.89$\pm$2.11 |  | 86.88$\pm$0.28
GSAPool | 88.93$\pm$0.88 |  | 76.94$\pm$0.74 |  | 86.07$\pm$0.62 |  | 80.36$\pm$3.71 |  | 49.82$\pm$2.72 |  | 51.58$\pm$4.19 |  | 86.75$\pm$0.24
HGPSLPool | 89.08$\pm$0.83 |  | 77.70$\pm$1.01 |  | OOM |  | 58.55$\pm$3.71 |  | 49.45$\pm$2.12 |  | 50.53$\pm$2.44 |  | OOM