Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities

1. [Adnan et al., 2020] Mohammed Adnan, et al. Representa- tion learning of histopathology images using graph neural networks. In CVPR Workshop, 2020.
2. [Atwood and Towsley, 2016] James Atwood et al. Diffusion- convolutional neural networks. In NeurIPS, 2016.
3. [Bacciu and Sotto, 2019] Davide Bacciu et al. A non- negative factorization approach to node pooling in graph convolutional neural networks. In AIIA, 2019.
4. [Baek et al., 2021] Jinheon Baek, et al. Accurate learning of graph representations with graph multiset pooling. In ICLR, 2021.
5. [Bai et al., 2019] Yunsheng Bai, et al. Unsupervised induc- tive graph-level representation learning via graph-graph proximity. In IJCAI, 2019. IJCAI
6. [Bai et al., 2021] Lu Bai, et al. Learning graph convolutional networks based on quantum vertex information propaga- tion. IEEE TKDE, 2021.
7. [Bianchi and Lachi, 2023] Filippo Maria Bianchi et al. The expressive power of pooling in graph neural networks. arXiv:2304.01575, 2023.
8. [Bianchi et al., 2020a] Filippo Maria Bianchi, et al. Spectral clustering with graph neural networks for graph pooling. In ICML, 2020.
9. [Bianchi et al., 2020b] Filippo Maria Bianchi, et al. Hier- archical representation learning in graph neural networks with node decimation pooling. IEEE TNNLS, 2020.
10. [Bodnar et al., 2020] Cristian Bodnar, et al. Deep graph mapper: Seeing graphs through the neural lens. In NeurIPS Workshop, 2020.
11. [Cangea et al., 2018] Cȃtȃlina Cangea, et al. Towards sparse hierarchical graph classifiers. arXiv:1811.01287, 2018.
12. [Chang et al., 2021] Jianxin Chang, et al. Sequential recom- mendation with graph neural networks. In SIGIR, 2021.
13. [Chen et al., 2019] Ting Chen, et al. Are powerful graph neural nets necessary? a dissection on graph classification. arXiv:1905.04579, 2019.
14. [Chen et al., 2020a] Chaofan Chen, et al. Hapgn: Hierarchi- cal attentive pooling graph network for point cloud seg- mentation. IEEE TMM, 2020.
15. [Chen et al., 2020b] Zhengdao Chen, et al. Can graph neural networks count substructures? In NeurIPS, 2020.
16. [Chen et al., 2022] Kaixuan Chen, et al. Distribution knowl- edge embedding for graph pooling. IEEE TKDE, 2022.
17. [Demir et al., 2021] Andac Demir, et al. Eeg-gnn: Graph neural networks for classification of electroencephalogram (eeg) signals. arXiv:2106.09135, 2021.
18. [Diehl, 2019] Frederik Diehl. Edge contraction pooling for graph neural networks. arXiv:1905.10990, 2019.
19. [Du et al., 2021] Jinlong Du, et al. Multi-channel pooling graph neural networks. In IJCAI, 2021. IJCAI
20. [Duval and Malliaros, 2022] Alexandre Duval et al. Higher- order clustering and pooling for graph neural networks. In CIKM, 2022.
21. [Duvenaud et al., 2015] David Duvenaud, et al. Convolu- tional networks on graphs for learning molecular finger- prints. In NeurIPS, 2015.
22. [Dwivedi et al., 2020] Vijay Prakash Dwivedi, et al. Bench- marking graph neural networks. arXiv:2003.00982, 2020.
23. [Errica et al., 2020] Federico Errica, et al. A fair comparison of graph neural networks for graph classification. In ICLR, 2020.
24. [Fan et al., 2020] Xiaolong Fan, et al. Structured self- attention architecture for graph-level representation learn- ing. Pattern Recognition, 2020.
25. [Fey et al., 2018] Matthias Fey, et al. Splinecnn: Fast geo- metric deep learning with continuous b-spline kernels. In CVPR, 2018.
26. [Gao and Ji, 2019] Hongyang Gao et al. Graph u-nets. In ICML, 2019.
27. [Gao et al., 2019] Hongyang Gao, et al. Learning graph pooling and hybrid convolutional operations for text rep- resentations. In WWW, 2019.
28. [Gao et al., 2020] Zhangyang Gao, et al. Lookhops: light multi-order convolution and pooling for graph classifica- tion. arXiv:2012.15741, 2020.
29. [Gao et al., 2021a] H. Gao, et al. Topology-aware graph pooling networks. IEEE TPAMI, 2021.
30. [Gao et al., 2021b] Xing Gao, et al. ipool-information- based pooling in hierarchical graph neural networks. IEEE TNNLS, 2021.
31. [Gaudelet et al., 2021] Thomas Gaudelet, et al. Utilizing graph machine learning within drug discovery and devel- opment. Briefings in Bioinformatics, 2021.
32. [Gopinath et al., 2022] Karthik Gopinath, et al. Learnable pooling in graph convolutional networks for brain surface analysis. IEEE TPAMI, 2022.
33. [Grattarola et al., 2021] Daniele Grattarola, et al. Un- derstanding pooling in graph neural networks. arXiv:2110.05292, 2021.
34. [Gu, 2021] Jindong Gu. Interpretable graph capsule net- works for object recognition. AAAI, 2021.
35. [Hermosilla et al., 2021] Pedro Hermosilla, et al. Intrinsic- extrinsic convolution and pooling for learning on 3d pro- tein structures. In ICLR, 2021.
36. [Holtz et al., 2019] Chester Holtz, et al. Multi-task learning on graphs with node and graph level labels. In NeurIPS Workshop, 2019.
37. [Hu et al., 2020] Weihua Hu, et al. Open graph bench- mark: Datasets for machine learning on graphs. arXiv:2005.00687, 2020.
38. [Huang et al., 2019] Jingjia Huang, et al. Attpool: Towards hierarchical feature representation in graph convolutional networks via attention mechanism. In ICCV, 2019.
39. [Isufi and Mazzola, 2021] Elvin Isufi et al. Graph-time con- volutional neural networks. arXiv:2103.01730, 2021.
40. [Itoh et al., 2022] Takeshi D. Itoh, et al. Multi-level atten- tion pooling for graph neural networks: Unifying graph representations with multiple localities. Neural Networks, 2022.
41. [Jo et al., 2021] Jaehyeong Jo, et al. Edge representation learning with hypergraphs. In NeurIPS, 2021.
42. [Khasahmadi et al., 2020] Amir Hosein Khasahmadi, et al. Memory-based graph networks. In ICLR, 2020.
43. [Kim et al., 2021] Byung-Hoon Kim, et al. Learning dy- namic graph representation of brain connectome with spatio-temporal attention. In NeurIPS, 2021.
44. [Kipf and Welling, 2017] Thomas N. Kipf et al. Semi- supervised classification with graph convolutional net- works. In ICLR, 2017.
45. [Knyazev et al., 2019] Boris Knyazev, et al. Understanding attention and generalization in graph neural networks. In NeurIPS, 2019.
46. [Lee et al., 2019] Junhyun Lee, et al. Self-attention graph pooling. In ICML, 2019.
47. [Lee et al., 2021] Dongha Lee, et al. Learnable structural se- mantic readout for graph classification. In ICDM, 2021.
48. [Li et al., 2016] Yujia Li, et al. Gated graph sequence neural networks. In ICLR, 2016.
49. [Li et al., 2020a] Juanhui Li, et al. Graph pooling with rep- resentativeness. In ICDM, 2020.
50. [Li et al., 2020b] Maosen Li, et al. Graph cross networks with vertex infomax pooling. In NeurIPS, 2020.
51. [Li et al., 2020c] Xiaoxiao Li, et al. Pooling regularized graph neural network for fmri biomarker analysis. In MIC- CAI, 2020.
52. [Li et al., 2021a] Jia Li, et al. Deconvolutional networks on graph data. NeurIPS, 2021.
53. [Li et al., 2021b] Shuangli Li, et al. Structure-aware inter- active graph neural networks for the prediction of protein- ligand binding affinity. In KDD, 2021.
54. [Li et al., 2021c] Xiaoxiao Li, et al. Braingnn: Interpretable brain graph neural network for fmri analysis. Medical Im- age Analysis, 2021.
55. [Liang et al., 2020] Yanyan Liang, et al. Mxpool: Multi- plex pooling for hierarchical graph representation learn- ing. arXiv:2004.06846, 2020.
56. [Liu et al., 2020] Fanzhen Liu, et al. Deep learning for com- munity detection: progress, challenges and opportunities. In IJCAI, 2020. IJCAI
57. [Liu et al., 2021a] Ning Liu, et al. Hierarchical adaptive pooling by capturing high-order dependency for graph rep- resentation learning. IEEE TKDE, 2021.
58. [Liu et al., 2021b] Y. Liu, et al. Learning hierarchical review graph representations for recommendation. IEEE TKDE, 2021.
59. [Liu et al., 2022a] Chuang Liu, et al. On exploring node- feature and graph-structure diversities for node drop graph pooling, 2022.
60. [Liu et al., 2022b] Ning Liu, et al. Unsupervised hierarchi- cal graph pooling via substructure-sensitive mutual infor- mation maximization. In CIKM, 2022.
61. [Liu et al., 2023] Chuang Liu, et al. Masked graph auto- encoder constrained graph pooling. In ECML-PKDD, 2023.
62. [Ma et al., 2019] Yao Ma, et al. Graph convolutional net- works with eigenpooling. In KDD, 2019.
63. [Ma et al., 2020] Zheng Ma, et al. Path integral based convo- lution and pooling for graph neural networks. In NeurIPS, 2020.
64. [Ma et al., 2021] Xiaoxiao Ma, et al. A comprehensive sur- vey on graph anomaly detection with deep learning. IEEE TKDE, 2021.
65. [Mai et al., 2020] Sijie Mai, et al. Analyzing unaligned mul- timodal sequence via graph convolution and graph pooling fusion. arXiv:2011.13572, 2020.
66. [Mao et al., 2022] Qianren Mao, et al. Higil: Hierarchical graph inference learning for fact checking. In ICDM, 2022.
67. [Mesquita et al., 2020] Diego Mesquita, et al. Rethinking pooling in graph neural networks. In NeurIPS, 2020.
68. [Morris et al., 2020] Christopher Morris, et al. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv:2007.08663, 2020.
69. [Murphy et al., 2019] Ryan Murphy, et al. Relational pool- ing for graph representations. In ICML, 2019.
70. [Nadgeri et al., 2021] Abhishek Nadgeri, et al. KGPool: Dy- namic knowledge graph context selection for relation ex- traction. In ACL, 2021.
71. [Navarin et al., 2019] Nicolò Navarin, et al. Universal read- out for graph convolutional neural networks. In IJCNN, 2019.
72. [Noutahi et al., 2019] Emmanuel Noutahi, et al. Towards in- terpretable sparse graph representation learning with lapla- cian pooling. arXiv:1905.11577, 2019.
73. [Pan et al., 2021] Li Pan, et al. Identifying autism spectrum disorder based on individual-aware down-sampling and multi-modal learning. arXiv:2109.09129, 2021.
74. [Pang et al., 2021] Yunsheng Pang, et al. Graph pooling via coarsened graph infomax. In SIGIR, 2021.
75. [Papp et al., 2021] Pál András Papp, et al. Dropgnn: Ran- dom dropouts increase the expressiveness of graph neural networks. NeurIPS, 2021.
76. [Qin et al., 2020] Jian Qin, et al. Uniform pooling for graph networks. Appl. Sci., 2020.
77. [Ranjan et al., 2020] Ekagra Ranjan, et al. Asap: Adap- tive structure aware pooling for learning hierarchical graph representations. In AAAI, 2020.
78. [Rhee et al., 2018] Sungmin Rhee, et al. Hybrid approach of relation network and localized graph convolutional fil- tering for breast cancer subtype classification. In IJCAI, 2018. IJCAI
79. [Roy et al., 2021] Kashob Kumar Roy, et al. Structure-aware hierarchical graph pooling using information bottleneck. In IJCNN, 2021.
80. [Shen et al., 2018] Y. Shen, et al. Mining point cloud lo- cal structures by kernel correlation and graph pooling. In CVPR, 2018.
81. [Shirian et al., 2022] Amir Shirian, et al. Dynamic emotion modeling with learnable graphs and graph inception net- work. IEEE TMM, 2022.
82. [Simonovsky and Komodakis, 2017] Martin Simonovsky et al. Dynamic edge-conditioned filters in convolutional neural networks on graphs. In CVPR, 2017.
83. [Su et al., 2021] Zidong Su, et al. Hierarchical graph repre- sentation learning with local capsule pooling. In MMAsia, 2021.
84. [Tak et al., 2021] Hemlata Tak, et al. End-to-end spectro- temporal graph attention networks for speaker veri- fication anti-spoofing and speech deepfake detection. arXiv:2107.12710, 2021.
85. [Tang et al., 2020] Haoteng Tang, et al. Adversarial at- tack on hierarchical graph pooling neural networks. arXiv:2005.11560, 2020.
86. [Tang et al., 2021] Haoteng Tang, et al. Commpool: An interpretable graph pooling framework for hierarchical graph representation learning. Neural Networks, 2021.
87. [Vinyals et al., 2016] Oriol Vinyals, et al. Order matters: Se- quence to sequence for sets. In ICLR, 2016.
88. [Wang and Ji, 2020] Zhengyang Wang et al. Second-order pooling for graph neural networks. IEEE TPAMI, 2020.
89. [Wang et al., 2020] Yu Guang Wang, et al. Haar graph pool- ing. In ICML, 2020.
90. [Wang et al., 2021] Jie Wang, et al. Papooling: Graph-based position adaptive aggregation of local geometry in point clouds. arXiv:2111.14067, 2021.
91. [Wei et al., 2021] Lanning Wei, et al. Pooling architecture search for graph classification. In CIKM, 2021.
92. [Wu and others, 2022] Junran Wu et al. Structural entropy guided graph hierarchical pooling. In ICML, 2022.
93. [Wu et al., 2019] Jun Wu, et al. Demo-net: Degree-specific graph neural networks for node and graph classification. In KDD, 2019.
94. [Wu et al., 2021] Chuhan Wu, et al. User-as-graph: User modeling with heterogeneous graph pooling for news rec- ommendation. In IJCAI, 2021. IJCAI
95. [Xu et al., 2019] Keyulu Xu, et al. How powerful are graph neural networks? In ICLR, 2019.
96. [Xu et al., 2021] Keyulu Xu, et al. How neural networks ex- trapolate: From feedforward to graph neural networks. In ICLR, 2021.
97. [Yang et al., 2021] Jinyu Yang, et al. Hierarchical graph cap- sule network. In AAAI, 2021.
98. [Ying et al., 2018] Zhitao Ying, et al. Hierarchical graph representation learning with differentiable pooling. In NeurIPS, 2018.
99. [Yuan and Ji, 2020] Hao Yuan et al. Structpool: Structured graph pooling via conditional random fields. In ICLR, 2020.
100. [Yuan et al., 2020] Hao Yuan, et al. Explainability in graph neural networks: A taxonomic survey. arXiv:2012.15445, 2020.
101. [Zeng et al., 2021] Hanqing Zeng, et al. Decoupling the depth and scope of graph neural networks. In NeurIPS, 2021.
102. [Zhang et al., 2018] Muhan Zhang, et al. An end-to-end deep learning architecture for graph classification. In AAAI, 2018.
103. [Zhang et al., 2020a] Liang Zhang, et al. Structure-feature based graph self-adaptive pooling. In WWW, 2020.
104. [Zhang et al., 2020b] Zhen Zhang, et al. Hierarchical graph pooling with structure learning. In AAAI, 2020.
105. [Zhang et al., 2021] Zhen Zhang, et al. Hierarchical multi- view graph pooling with structure learning. IEEE TKDE, 2021.
106. [Zhong et al., 2022] Zhiqiang Zhong, et al. Multi-grained semantics-aware graph neural networks. IEEE TKDE, 2022.
107. [Zhou et al., 2020] Kaixiong Zhou, et al. Multi-channel graph neural networks. In IJCAI, 2020. IJCAI

References were extracted automatically from the PDF and may contain errors.

Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.

1 Introduction

Graph Neural Networks (GNNs) have achieved a substantial improvement over many graph-level tasks such as graph classification [Errica et al., 2020], graph regression [Bianchi et al., 2020a], and graph generation [Baek et al., 2021]. Specifically, GNNs have been successfully applied to graph-level tasks across a broad range of areas such as chemistry and biology [Baek et al., 2021], social network [Ma et al., 2021], computer vision [Fey et al., 2018], natural language processing [Gao et al., 2019], and recommendation [Wu et al., 2021].

∗This work was done when Chuang Liu worked as an intern at JD Explore Academy.

†Corresponding Author

Different from node-level tasks, which mainly use the graph convolutional network (GCN) [Kipf and Welling, 2017] to generate node representations for downstream tasks, graph-level tasks require holistic graph-level representations for graph-structured inputs whose size and topology are varying. Therefore, for graph-level tasks, the pooling mechanism is an essential component, which condenses the input graph with node representations generated by GCN into a smaller sized graph or a single vector, as shown in Figure 1.

In order to obtain an effective and reasonable graph representation, many designs of graph pooling have been proposed, which could be roughly divided into Flat Pooling (Section 3.1) and Hierarchical Pooling (Section 3.2). The former directly generates a graph-level representation in one step, mostly taking the average or sum over all node embeddings as the graph representation [Duvenaud et al., 2015], while the latter coarsens a graph gradually into a smaller sized graph by two main means: Node Clustering Pooling and Node Drop Pooling. Specifically, node clustering pooling [Ying et al., 2018] groups nodes into clusters as a coarsened graph, which is time-and space-consuming [Bianchi et al., 2020a]. In contrast, node drop pooling [Gao and Ji, 2019] selects a subset of nodes from the original graph to construct a coarsened graph, which is more efficient and more suitable for large-scale graphs [Lee et al., 2019] but suffers from inevitable information loss [Gao et al., 2021b].

Although such state-of-the-art graph pooling methods have been proposed, only a few recent works have attempted to comprehensively evaluate the effects of graph pooling [Mesquita et al., 2020; Grattarola et al., 2021], and a systematic review of the progress of and challenges facing this emerging area is still lacking. To fill the gaps, we comprehensively survey graph pooling in this paper, including proposing a taxonomy and formulating relevant frameworks (Section 3), overviewing libraries (Section 4), outlining applications (Section 5), and discussing future research directions (Section 6). To the best of our knowledge, our paper is the first attempt to present a systematic and comprehensive review of recent progress on graph pooling. The purpose of this paper is to provide new practitioners with a comprehensive understanding of graph pooling and to keep researchers informed about the latest advancements in this field.

2 ProblemFormulation

Notions. Let G = (V, E) denote a graph with node set V and edge set E. Node features are denoted as X ∈ Rn×d , where n is the number of nodes, and d is the dimension of node features. The adjacency matrix is defined as A ∈ {0, 1}n×n . A[i, j] = 1 if there exists an edge between node vi and node vj , otherwise, A[i, j] = 0.

Graph Pooling. Let a graph pooling operator be defined as any function POOL that maps a graph G to a new pooled graph G ′ = (V ′ , E ′ ) :

Formula not decoded

where |V ′ | < |V| 1 . The primary goal of graph pooling is to reduce the number of nodes in a graph while preserving the semantic information of the graph.

3 Approaches for Graph Pooling

Graph pooling can be roughly divided into flat pooling and hierarchical pooling according to its role in graph-level representation learning. The former directly generates graphlevel representations in a single step (|V ′ | = 1), while the latter coarsens the graph gradually into a smaller sized graph (|V ′ | > 1).

3.1 Flat Pooling

Flat pooling, also known as graph readout operation, directly generates a graph-level representation hG in one step. Thus, Eq. 1 in the case of flat pooling can be denoted as:

Formula not decoded

where POOLflat denotes the graph pooling function, which must: 1) output fixed-sized graph representations when input graphs are of different sizes; 2) output the same representation when the order of nodes of an input graph changes.

In light of the above discussions, several designs of flat pooling layers have been proposed. The most commonly used method is the sum-pool or mean-pool, which performs averaging or summing operations over all node representations [Duvenaud et al., 2015; Xu et al., 2019]. Some methods [Navarin et al., 2019; Chen et al., 2019; Papp et al., 2021] perform an additional non-linearity transformation to improve the expressive power of pooling methods. Moreover, some methods [Li et al., 2016; Atwood and Towsley, 2016; Bai et al., 2019; Fan et al., 2020; Itoh et al., 2022] introduce the soft attention mechanism to determine the weight of each vertex in the final graph-level representation. Besides, some methods [Zhang et al., 2018; Bai et al., 2021] apply convolutional neural networks to sorted node representations. Different from the above methods, which collect the first-order statistic information of node representations, SOPool, proposed by Wang et al. [2020], considers the important second-order statistics, which refers to functions that utilize the second power of node features. Furthermore, DKEPool [Chen et al., 2022] takes into consideration the entire node distribution of a graph. Due to space limitation, some other flat pooling methods such as Set2set [Vinyals et al., 2016], DEMO-Net [Wu et al., 2019], SSRead [Lee et al., 2021], and GMT [Baek et al., 2021] are not presented here.

1 In some very specific cases, there exits |V ′ | ≥ |V|, causing the graph to be upscaled by pooling.

Most of the above flat pooling methods perform operations on node representations to obtain graph-level representations without consideration of the intrinsic hierarchical structures of graphs, which causes information loss and degrades the performance of graph representations [Knyazev et al., 2019; Bianchi and Lachi, 2023].

3.2 Hierarchical Pooling

Hierarchical pooling methods aim to preserve the hierarchical graph's structural information by iteratively coarsening the graph into a new graph in smaller size. The hierarchical pooling can be roughly classified into node clustering pooling, node drop pooling, and other pooling according to the manner in which it coarsens a graph. The main difference between the first two types of methods is that node clustering pooling generates new nodes for the coarsened graph, whereas node drop pooling retains nodes from the original graph. Note that hierarchical pooling methods still technically employ flat pooling methods (readout in Figure 1) to obtain the graph-level representation of the coarsened graph.

Node Clustering Pooling

Node clustering pooling considers graph pooling as a node clustering problem, which maps the nodes into a set of clusters. After that, the clusters are treated as new nodes of the new coarsened graph. To gain a better insight into node Notations: X′ ∈ Rc×d and A′ ∈ Rc×c are the adjacency matrix and feature matrix for the new graph, respectively; ˜ A ∈ Rn×n is the adjacency matrix with self loop; L ∈ Rn×n is the graph Laplacian; Ik ∈ Rc×c is the identity matrix; k ∈ Rd is a memory key vector; p ∈ R1×2d is a trainable vector; τ is the degree of freedom of the Student's t-distribution, i.e., temperature; c is the number of clusters; |m| is the number of heads; Γ is an [1×1] convolutional operator; ∥ is the concatenation operator; GCont is an auto-learned global graph content; Gumbel-SoftMax achieves soft sampling for neighborhood relationships to decrease the edge density.

Models	CAM Generator	Graph Coarsening	Notes
DiffPool [1]	C = softmax(GNNpool(X, A))	{X′ =CT · GNNemb(X,A) A′ = CT AC	Auxiliary Loss 1⃝
NMF [2]	{A ≈ UV C = V T	X′ = CT X;A′ = CT AC	-
LaPool [3]	 si = ∥ ∑ j∈N (vi) Ai,j (xi - xj) ∥2 Vc = {vi ∈ V | ∀vj, si -Aijsj > 0} C = sparsemax (p XXT c ∥X∥ ∥Xc∥ )	{X′ = MLP(CT X) A′ = CT AC	-
MinCut [4]	C = MLP(X)	{X′ =CT X; ̂ A=CT ˜ AC A′ = ̂ A- Idiag( ̂ A)	MinCut Loss 2⃝
StructPool [5]	C : MinimizE(C) 3⃝	X′ = CT X;A′ = CT AC	-
MemPool [6]	 Ci,j = (1 + ∥xi - kj ∥2 /τ )- τ+1 2 ∑j ′ (1+ ∥xi -kj ′∥2 /τ)- τ+1 2 C = softmax (Γ (|m| ∥ t=0Ct))	X′ = MLP(CT X)	Auxiliary Loss 4⃝
HAP [7]	 T = GCont(X) Cij = σ (pT [TRowi ∥TColj ]) C = softmax(C)	{X′ =MLP(CT X), ̂ A = CT AC A′ = Gumbel-SoftMax( ̂ A)	-
SEP [8]	C : MinimizHT (G) 5⃝	X′ = CT X;A′ = CT AC	-

Table 1: Summary of representative node clustering pooling methods in our framework.

clustering pooling, we propose a universal and modularized framework to describe the process of node clustering pooling. Specifically, we deconstruct node clustering pooling into two disjoint modules: 1) Cluster Assignment Matrix (CAM) Generator. Given an input graph, the CAM generator predicts the soft / hard assignment for each node. 2) Graph Coarsening. With the assignment matrix, a new graph coarsened from the original one is obtained by learning a new feature matrix and a adjacency matrix. The process can be formulated as follows:

Formula not decoded

where functions CAM and COARSEN are specially designed by each method, respectively. C(l) ∈ Rnl×nl+1 indicates the learned cluster assignment matrix; nl is the number of nodes (or clusters) at layer l.

Accordingly, we show how existing node clustering pooling methods fit into our proposed framework, and select seven typical methods presented in Table 1. We observe that these methods, with the same coarsening module choice, mainly differ in the way CAM is generated. 1) CAM Generator. Node clustering methods generate CAM from different perspectives. Specifically, DiffPool [Ying et al., 2018] directly employs GNN models, and StructPool [Yuan and Ji, 2020] extends DiffPool by explicitly capturing high-order structural relationships; LaPool [Noutahi et al., 2019] and MinCutPool [Bianchi et al., 2020a] both design the generator from the perspective of spectral clustering; MemPool [Khasahmadi et al., 2020] introduces a clustering-friendly distribution to generate the cluster matrix. 2) Graph Coarsening. Most node clustering methods adopt nearly the same coarsening strategy: the pooled node representations, X(l+1) = C(l) T X(l) ∈ Rnl+1×d , obtained by the sum of representations of the nodes in each cluster and weighted by the cluster assignment scores; the coarsened adjacency matrix, A(l+1) = C(l) T A(l)C(l) ∈ Rnl+1×nl+1 , which indicates the connectivity strength between different clusters, is obtained by the weighted sum of edges between clusters.

Due to space limitation, many other node clustering pooling methods [Ma et al., 2019; Zhou et al., 2020; Bodnar et al., 2020; Khasahmadi et al., 2020; Wang et al., 2020; Roy et al., 2021; Yang et al., 2021; Liang et al., 2020; Su et al., 2021; Liu et al., 2022b] are not presented in Table 1. Despite substantial improvements achieved on several graphlevel tasks (e.g., graph classification), the above methods suffer from the limitation of the time and storage complexity. This is due to the computation of a dense cluster assignment matrix, which typically requires O (n2 ) space complexity, as noted in [Baek et al., 2021]. Besides, as discussed in the recent work [Mesquita et al., 2020], clustering-enforcing regularization usually has little effect.

Models	Score Generator	Node Selector	Graph Coarsening
TopKPool [1]	S = Xp/ ∥p∥2	idx = TOPk(S)	X′ =Xidx ⊙σ(Sidx); A′ = Aidx,idx
SAGPool [2]	S = GNN(X, A)	idx = TOPk(S)	X′ =Xidx ⊙Sidx; A′ = Aidx,idx
AttPool [3]	S = softmax (XW)	idx = TOPk(S)	X′ = Aidx(X⊙S); A′ = AidxAATidx
ASAP [4]	S = LEConv(Xc, A)	idx = TOPk(S)	X′ =Xc idx ⊙Sidx; A′ = AidxAATidx
HGP-SL [5]	S = ∥∥(I - D-1A) X∥∥1	idx = TOPk(S)	{X′ =Xidx ⊙Sidx; ̂ A = Aidx,idx A′ij = max(σ(-→a [X′(i, :)∥X′(j, :)]⊤) + λ · ̂ Aij
VIPool [6]	P = 1t t∑ h=1 ( ˜D- 1 2 ˜A ˜D- 1 2 )h W hMLP(X) S = σ(MLP(MLP(X, P )))	idx = TOPk(S)	{X′ = Xidx ⊙ Sidx A′ = softmax(Aidx)Asoftmax(Aidx)T
RepPool [7]	S = σ (D-1AXp/ ∥p∥2)	idx = SELk(S)	 B = XWb(Xidx)T X′ = (softmax(B ⊙ M))T (X ⊙ S) A′ = (softmax(B ⊙M))T A(softmax(B ⊙M))
GSAPool [8]	S1 = GNN(X, A) S2 = σ(MLP(X)) S = αS1 + (1 - α)S2	idx = TOPk(S)	X′ = (AXW)idx ⊙Sidx; A′ = Aidx,idx
PANPool [9]	 Zi = L∑ n=0 e- E(n) T N∑ j=1 g(i, j; n) M = Z-1 L∑ n=0 e- E(n) T An S = Xp + β diag(M)	idx = TOPk(S)	X′ =Xidx ⊙σ(Sidx); A′ = Aidx,idx
CGIPool [10]	Sr = GNNr(X, A) Sf = GNNf(X,A) S = σ(Sr - Sf )	idx = TOPk(S)	X′ =Xidx ⊙Sidx; A′ = Aidx,idx
TAPool [11]	 Sl = softmax ( 1n ((XXT ) ⊙ ( ˜D-1 ˜ A))1n) Sg = softmax ( ˜D-1 ˜ AXp) S = Sl + Sg	idx = TOPk(S)	X′ =Xidx ⊙Sidx; A′ = Aidx,idx
IPool [12]	S = ∥∥(I - 1t ∑th=1( ¯Dh)-1 ¯Ah) X∥∥2	idx = TOPk(S)	{X′ =Xidx, A′ij = λ (A + I)idx[i],idx[j] + (1 - λ)Oij

Table 2: Summary of representative node drop pooling methods in our framework.

Node Drop Pooling

Node drop pooling exploits learnable scoring functions to delete nodes with comparatively lower significance scores. For a thorough analysis of node drop pooling, we propose a universal and modularized framework, which consists of three disjoint modules: 1) Score Generator. Given an input graph, the score generator calculates significance scores for each node. 2) Node Selector. Node selector selects the nodes with top-k significance scores. 3) Graph Coarsening. With the selected nodes, a new graph coarsened from the original one is obtained by learning a new feature matrix and a adjacency matrix. The process can be formulated as follows:

Formula not decoded

where functions SCORE, TOPk, and COARSEN are specially designed by each method for score generator, node selector, and graph coarsening, respectively. S(l) ∈ Rn×1 indicates the significance scores; TOPk ranks values and returns the indices of the largest k values in S(l) ; idx(l+1) indicates the reserved node indexes for the new graph.

Accordingly, we present how the nine typical node drop pooling methods fit into our proposed framework in Table 2. Intuitively, methods tend to design more sophisticated score generators and more reasonable graph coarsenings to select more representative nodes and retain more important structural information, respectively, thus alleviating the problem of information loss. 1) Score Generator. Different from TopKPool [Gao and Ji, 2019], SAGPool [Lee et al., 2019], and HGP-SL [Zhang et al., 2020b], which predict scores from a single view, GSAPool [Zhang et al., 2020a] and TAPool [Gao

et al., 2021a] generate scores from two different views, i.e.,

local and global views. 2) Node Selector. Most methods sim-

ply adopt TOPk as a selector, and only a few works [Li et al.,

2020a; Qin et al., 2020] design different selectors. 3) Graph

Coarsening. Instead of directly obtaining the coarsened

graph formed by the selected nodes, such as TopKPool [Gao

and Ji, 2019], SAGPool [Lee et al., 2019], and TAPool [Gao

et al., 2021a], RepPool [Li et al., 2020a], GSAPool [Zhang et

al., 2020a], and IPool [Gao et al., 2021b] utilize both the se-

lected nodes and non-selected nodes to maintain more struc-

tural and feature information in a graph.

Due to space limitation, many other node drop pool-

ing methods [Cangea et al., 2018; Knyazev et al., 2019;

Ranjan et al., 2020; Ma et al., 2020; Bianchi et al., 2020b;

Gao et al., 2020; Li et al., 2020b; Zhang et al., 2021;

Tang et al., 2021; Liu et al., 2022a; Liu et al., 2023] are not

presented in Table 2. Though more efficient and more appli-

cable to large-scale graph datasets [Cangea et al., 2018] than

node clustering pooling methods, node drop pooling methods

suffer from inevitable information loss [Gao et al., 2021b;

Baek et al., 2021; Liu et al., 2022a].

Other Pooling

Apart from node drop and node clustering pooling methods,

there also exist some other graph pooling methods. For ex-

ample, EdgePool [Diehl, 2019] and HyperDrop [Jo et al.,

2021] pool the input graph from the edge view, which main-

tains the connectivity of the input graph through edge con-

tractions based on an adaptive edge scoring design; Much-

Pool [Du et al., 2021] combines node clustering pooling and

node drop pooling to capture different characteristics of a

graph; PAS [Wei et al., 2021] proposes to search for adap-

tive pooling architectures by neural architecture search.

4 Libraries for Graph Pooling

Benchmark Datasets. Table 3 provides the statistics of

commonly used datasets for evaluating graph pooling meth-

ods, which mainly come from two widely used repositories:

TU dataset [Morris et al., 2020], which contains over 130

datasets varying in content domains and dataset sizes, and

Open Graph Benchmark (OGB) dataset [Hu et al., 2020],

which contains many large-scale benchmark datasets. The

above datasets can be classified into four categories: 1) So-

cial Networks. The social networks consider entities as IMDB-MULTI

Datasets	Category	# graphs	# classes [1]	Avg.|V|	Avg.|E|	Task
D&D	Protein	TUDataset 1,178	2	284.32	715.66	Cla.
PROTEINS	Protein	1,113	2	39.06	72.82	Cla.
ENZYMES	Protein	600	6	32.63	124.20	Cla.
NCI1	Molecule	4,110	2	29.87	32.30	Cla.
NCI109	Molecule	4,127	2	29.68	32.13	Cla.
MUTAG	Molecule	188	2	17.93	19.79	Cla.
PTC MR	Molecule	344	2	14.30	14.69	Cla.
MUTAGENICITY	Molecule	4,337	2	30.32	30.77	Cla.
FRANKENSTEIN	Molecule	4,337	2	16.90	17.88	Cla.
REDDIT-BINARY	Social	2,000	2	429.63	497.75	Cla.
REDDIT-M5K	Social	4,999	5	508.52	594.87	Cla.
REDDIT-M12K	Social	11,929	11	391.41	456.89	Cla.
IMDB-BINARY	Social	1,000	2	19.77	96.53	Cla.

Social

1,500

3

13.00

65.94 Cla.

COLLAB

Social

5,000

3

74.49 2457.78 Cla.

QM9

Molecule 133,885

-

18.03

18.63 Reg.

ZINC

Molecule 249,456

-

23.14

24.91 Rec.

Open Graph Benchmark [2]

HIV

Molecule 41,127

2

25.51

27.52 Cla.

TOX21 Molecule 7,831

12

18.57

19.3 Cla.

TOXCAST Molecule 8,576

617

18.78

19.3 Cla.

BBBP

Molecule 2,039

2

24.06

26.0 Cla.

MoleculeNet [3]

QM7

Molecule 7,165

1

61.31

91.03 Reg.

QM8

Molecule 21,786

12

61.31

91.03 Reg.

ESOl Molecule 1,128

1

61.31

91.03 Reg.

FREESOLV Molecule

643

1

20.85

32.74 Reg.

LIPOPHILICITY Molecule 4,200

1

20.85

32.74 Reg.

Synthetic Generation [4]

COLORS-3

Synthetic 5,500

5

61.31

91.03 Cla.

TRIANGLES Synthetic 45,000

10

20.85

32.74 Cla.

Computer Vision [5]

MNIST

Image

60,000

10

70

91.03 Cla.

CIFAR10

Image

70,000

10

117

32.74 Cla.

Cla., Reg., and Rec.

refer to graph classification, graph regression, and

graph reconstruction, respectively.

[1] https://chrsmrrs.github.io/datasets/docs/

datasets/; [2] https://ogb.stanford.edu/docs/graphprop/; [3] https://moleculenet.org/;

[4] https://github.com/bknyaz/graph attention pool/tree/master/data; [5] https://github.

com/graphdeeplearning/benchmarking-gnns

Table 3: A list of commonly used and publicly accessible datasets.

̂

(a): Node Clustering

(b): Graph Regression

̂

(c): Flat Graph Classification

(d): Hierarchical Graph Classification (e): Graph Reconstruction / Node Classification

Figure 2: Illustration of model architectures for different tasks.

nodes, and their social interactions as edges. 2) Protein Networks. The commonly used datasets include PROTEINS and D&D, where nodes correspond to amino acids, and edges

̂

̂

Method	Task	Dataset	Venue	Code Link
Flat Pooling Methods
SortPool [1]♠♣	Graph Classification	D&D, PROTEINS, NCI1, MUTAG, PTC, COLLAB, IMDB-B (M)	AAAI'2018	https://shorturl.at/joAJ9
SOPool [2]	Graph Classification	PROTEINS, NCI1, MUTAG, PTC, IMDB-B (M), COLLAB, RDT-B,RDT-M5K	TPAMI'2020	-
GMT [3]♠	Graph Classification Graph Reconstruction Graph Generation	D&D, PROTEINS, MUTAG, IMDB-B (M), COLLAB, HIV, TOX21, TOXC., BBBP ZINC, Synthetic (Ring and Grid Graphs) QM9	ICLR'2021	https://shorturl.at/iorN3
DKEPool [4]	Graph Classification	PROTEINS, NCI1, MUTAG, PTC, IMDB-B (M), HIV, BBBP	TKDE'2022	https://shorturl.at/drz12
Node Clustering Pooling Methods
DiffPool [5]♠♣	Graph Classification	D&D, PROTEINS, ENZYMES, COLLAB, RDT-M12K	NeurIPS'2018	https://shorturl.at/aflB3
MinCutPool [6]♠♣	Graph Classification Node Clustering Graph Regression	D&D, PROTEINS, ENZYMES, IMDB-B (M), COLLAB Cora, Citeseer, Pubmed QM9	ICML'2020	https://shorturl.at/zIOY9
MemPool [7]	Graph Classification Graph Regression	D&D, PROTEINS, ENZYMES, COLLAB, RDT-B ESOL, Lipophilicity	ICLR'2020	https://shorturl.at/dqxY4
StructPool [8]	Graph Classification	PROTEINS, ENZYMES,MUTAG, PTC, IMDB-B (M),COLLAB	ICLR'2020	https://shorturl.at/fiJ01
HoscPool [9]	Graph Classification Node Clustering	D&D, PROTEINS, NCI1, MUTAGEN., RDT-B, COX2-MD, ER-MD Cora, Pubmed, CS, Photo, PC, Polblogs, Eu-email, Synthetic	CIKM'2022	https://shorturl.at/abR26
SEP [10]	Graph Classification Graph Reconstruction Node Classification	D&D, PROTEINS, MUTAG, NCI1, IMDB-B (M), COLLAB Synthetic (Ring and Grid Graphs) Cora, Citeseer, Pubmed	ICML'2022	https://shorturl.at/ovDLT
Node Drop Pooling Methods
TopKPool [11]♠♣	Graph Classification Node Classification	D&D, PROTEINS, COLLAB Cora, Citeseer, Pubmed	ICML'2019	https://shorturl.at/cjlnr
SAGPool [12]♠♣	Graph Classification	D&D, PROTEINS, NCI1, NCI109, FRANK.	ICML'2019	https://shorturl.at/bEJNQ
ASAP [13]♠	Graph Classification	D&D, PROTEINS, ENZYMES, NCI1, NCI109, MUTAGEN.	AAAI'2020	https://shorturl.at/depuz
VIPool [14]	Graph Classification Node Classification	D&D, PROTEINS, ENZYMES, IMDB-B (M), COLLAB Cora, Citeseer, Pubmed	NeurIPS'2020	https://shorturl.at/luvz1
GSAPool [15]	Graph Classification	D&D, NCI1, NCI109, MUTAGEN.	WWW'2020	https://shorturl.at/ciS02
PANPool [16]♠	Graph Classification	PROTEINS, PROTEINS-FULL, NCI1, MUTAGEN., AIDS	NeurIPS'2020	https://shorturl.at/OP015
TAPool [17]	Graph Classification	D&D, PROTEINS, MUTAG, PTC	TPAMI'2021	-
IPool [18]	Graph Classification	D&D, PROTEINS, ENZYMES, NCI1, NCI109, MNIST, CIFAR10	TNNLS'2021	-
MVPool [19]	Graph Classification Node Classification Node Clustering Graph Clustering	D&D, PROTEINS,ENZYMES, NCI1, NCI109, MUTAGEN. IMDB-B, RDT-M12K Cora, Citeseer, Pubmed, Coauthor-CS, Coauthor-Phy Cora, Citeseer, Pubmed PROTEINS, NCI109, MUTAGEN.	TKDE'2021	https://shorturl.at/fgqX1
AdamGNN [20]	Graph Classification Node Classification Link Prediction	D&D, PROTEINS, MUTAGNCI1, NCI109, MUTAGEN. Cora, Citeseer, Pubmed, DBLP, ACM, Emails, Wiki, Ogbn-arxiv Cora, Citeseer, Pubmed, DBLP, ACM, Emails, Wiki	TKDE'2022	https://shorturl.at/tNQWZ

Table 4: A list of representative graph pooling methods.

are constructed if the distance between two nodes is below 6 Angstroms. 3) Molecule Graphs. The commonly used molecular datasets include NCI1 and MUTAG, in which nodes and edges refer to atoms and bonds, respectively. 4) Others. Besides the above three types of datasets, there are also some less commonly used datasets, such as synthetic datasets introduced by Knyazev et al. [2019], and image datasets [Dwivedi et al., 2020], which are converted into graphs using super-pixels. The former is used to evaluate the generalization capability of pooling methods, and the latter is usually used to visualize the preserved information via graph pooling (usually used in node drop pooling methods), which helps analyze the interpretability of pooling methods.

Model Architectures. The graph pooling methods are generally evaluated by two levels of graph tasks: 1) Node-level tasks include node classification and node clustering tasks, which are generally tested on a single graph in the form of transductive learning; 2) Graph-level tasks include graph classification, graph regression, graph reconstruction, and graph generation tasks, which are usually tested on multiple graphs in the form of inductive learning. Figure 2 summarizes the model architectures commonly used for various tasks. The abbreviations used in the figure are MP for message passing, NC for node clustering, HP for hierarchical pooling, FP for flat pooling, and UP for unpooling. In addition to the above task-oriented evaluations, Daniele et al. [2021] provided another two evaluation criteria, including preserving the information content of the node attributes and preserving the topological structure, which help to comprehensively quantify the ability of graph pooling.

Codes. To facilitate the access to empirical analysis, we summarize the open-source codes of representative graph pooling studies in Table 4. Meanwhile, we list the applied tasks and corresponding benchmark datasets of each method. Due to space limitation, a more complete summary (over 150 papers reviewed) is presented in our GitHub repository 2 . Moreover, we will update the repository in real-time as more methods and their implementations become available.

5 Applications

We briefly review the recent studies that incorporate the idea of graph pooling on a wide range of applications, which can be divided into two classes according to the type of datasets: 1) Structural datasets, where the data have explicit relational structures, such as molecular property prediction [Wang et al., 2020; Khasahmadi et al., 2020], molecular generation [Baek et al., 2021], protein-ligand binding affinity prediction [Li et al., 2021b], 3D protein structure analysis [Hermosilla et al., 2021], drug discovery [Gaudelet et al., 2021], recommendation [Wu et al., 2021; Chang et al., 2021; Liu et al., 2021b], community detection [Liu et al., 2020], and relation extraction of knowledge graph [Nadgeri et al., 2021]. 2) Non-structural datasets, where the relational structures are implicit, and the graphs are built according to domain knowledge, such as cancer diagnosis [Rhee et al., 2018; Adnan et al., 2020], brain data analysis [Li et al., 2020c; Li et al., 2021c; Kim et al., 2021; Pan et al., 2021; Demir et al., 2021; Gopinath et al., 2022], anti-spoofing and speech deepfaked detection [Tak et al., 2021], natural language processing (NLP) [Gao et al., 2019; Mao et al., 2022], computer vision (CV) [Simonovsky and Komodakis, 2017; Fey et al., 2018; Gu, 2021], 3D point clouds [Shen et al., 2018; Chen et al., 2020a; Wang et al., 2021], and multimodal sentiment analysis [Mai et al., 2020].

The aforementioned studies have effectively decreased sample size [Nadgeri et al., 2021] and incorporated hierarchical information [Chen et al., 2020a] by utilizing either pre-existing or newly developed graph pooling techniques. This has resulted in notable enhancements across diverse applications, confirming the efficacy of graph pooling methods as demonstrated through experimental results in these works [Wu et al., 2021; Pan et al., 2021; Shirian et al., 2022; Gopinath et al., 2022]. Thus, the applicability of graph pooling has been established.

2 https://github.com/LiuChuang0059/graph-pooling-papers

6 Challenges and Opportunities

6.1 Different Tasks andMulti-tasks

Challenge. Table 4 demonstrates that most existing graph pooling methods focus on graph-level tasks, with few addressing node-level tasks like node classification. Graph pooling methods show promise in reducing the number of parameters, which can decrease time complexity and increase model resistance to over-fitting. Additionally, these methods have large receptive fields that capture high-order information. However, designing efficient and effective pooling/unpooling operators and integrating them into graph convolution networks for better performance in node-level tasks (e.g., node classification) are still key challenges.

Opportunity. Some methods attempt to handle the node classification task with an encoder-decoder learning structure as shown in Figure 2 (e), where the unpooling operation is an important component. Several node drop pooling methods [Li et al., 2020b; Zhang et al., 2021] utilize the unpooling operation proposed in the Graph U-net [Gao and Ji, 2019]. Another important component is the convolution of decoder, termed deconvolution. Besides directly adopting the convolution of encoder as deconvolution, we can design a more reasonable deconvolution, inspired by DGN [Li et al., 2021a], which reconstructs graph signals from smoothed node representations from the perspective of spectral domain. Therefore, future research directions include: 1) handling node-level tasks with an encoder-decoder structure by designing efficient unpooling and deconvolutional operators; 2) developing a unified graph pooling approach, through which node-level and graph-level tasks can be simultaneously handled [Holtz et al., 2019; Zeng et al., 2021], which is beneficial since different tasks may benefit from each other.

6.2 Different Types of Graphs

Challenge. The graph pooling methods discussed in Section 3 are primarily intended for plain graphs. However, there are also many other types of graphs in real-world datasets. Obviously, it is not optimal to directly apply the above existing graph pooling methods to these different types of graphs because they possess distinct characteristics. Therefore, there is a significant gap in the literature regarding the development of specific graph pooling operators tailored to handle diverse types of graphs.

Opportunity. Recently, several graph pooling works have attempted to handle the rarely studied but commonly used graphs in real applications, such as heterogenous graphs [Wu et al., 2021], spatio-temporal graphs [Isufi and Mazzola, 2021], and hypergraphs [Jo et al., 2021]. However, specific graph pooling operators for handling other types of graphs are still lacking. Therefore, we suggest two promising research opportunities: 1) extending the existing graph pooling methods or designing new pooling methods to deal with specific graphs in consideration of their properties, such as dynamic graphs, where graph structures and graph nodes dynamically change over time, directed graphs, where the edges have a direction, and signed networks, where signed edges represent positive or negative relationships between nodes; 2) devising a general pooling method, which can efficiently handle different types of graphs in a universal manner.

6.3 Interpretability

Challenge. Although the existing graph pooling methods have achieved excellent results on various graph-based tasks, most of them show little interpretability [Knyazev et al., 2019]. This is particularly problematic for drug or diseaserelated problems where understanding the reasoning behind these methods is crucial. Although there has been some progress in interpreting node representation of GNNs [Yuan et al., 2020], the interpretability of pooling methods remains largely unexplored.

Opportunity. To exactly explain what has been learned from graph pooling operations, some studies [Ying et al., 2018; Khasahmadi et al., 2020; Tang et al., 2021] have attempted to present the visualization of hierarchical clusters or hierarchical community structures captured by pooling operations, but they do not provide quantitative analyses to assess the quality of clustering. Moreover, the interpretability of pooling operations is still not well explored. Therefore, there is a need for further research in this area. A promising direction would be to extend existing studies on interpreting GNNs [Yuan et al., 2020] to include graph pooling.

6.4 Robustness

Challenge. Since many applications of graph pooling methods are risk-sensitive, e.g., drug design and disease diagnosis, the robustness of methods is essential and indispensable for actual usages. However, according to the analysis in recent studies [Tang et al., 2020; Roy et al., 2021; Liu et al., 2022a], most graph pooling methods fail to distinguish the noise information from the input graph, thus dramatically degrading their performance when the input graph is perturbed in terms of features or topology.

Opportunity. Although some initial studies have been conducted on the robustness of graph machine learning, few studies have explored the robustness of graph pooling methods. So far, only an adversarial attack framework has been proposed by Tang et al. [2020] to evaluate the robustness of graph pooling methods. Therefore, there is much work to be done to develop a robust graph pooling method for practical applications, such as: 1) building up a comprehensive adversarial attack framework encompasses various types of attacks; 2) designing adversarial defense graph pooling methods. One potential solution is to extend the techniques used for enhancing the robustness of graph machine learning into improving the robustness of graph pooling methods.

6.5 Large-scale Data

Challenge. Most graph poolingmethods are tested on small benchmark datasets, which may be insufficient for comparisons among different graph pooling models. For example, applying graph pooling methods to small node classification datasets, i.e., Cora, is insufficient to assess their effectiveness in reducing the time and space complexity. Only a few works have attempted to deal with relatively larger graph datasets [Zhong et al., 2022]. Additionally, the efficiency of pooling methods is crucial. The high cost of time or space limits their applicability to large-scale datasets. Node clustering pooling methods, for example, suffer from high storage complexities due to the computation of dense assignment matrices [Grattarola et al., 2021].

Opportunity. Hence, we suggest the following research objectives: 1) performing further verifications on large-scale graph datasets, e.g., on the Open Graph Benchmark [Hu et al., 2020], which is a recently proposed large-scale graph machine learning benchmark; 2) designing more efficient graph pooling methods and making them more practical with constrained resource in real-world scenarios.

6.6 Expressive Power

Challenge. Most existing graph pooling methods are designed by intuition, and their performance gains are evaluated by empirical experiments. The lack of the means by which we can characterize the expressive power of graph pooling operators hinders the creation of more powerful graph pooling models [Xu et al., 2019].

Opportunity. Only a limited number of studies [Murphy et al., 2019; Chen et al., 2020b; Baek et al., 2021] have examined the expressive ability of their models in terms of the 1-Weisfeiler-Lehman (WL) test. Recently, Bianchi et al. [2023] conducted an comprehensive analysis on the expressive power of graph pooling techniques. Therefore, based on their theoretical findings, it is promising and significant to explore more powerful graph pooling methods as future research directions.

6.7 Generalize to Out-of-Distribution Data.

Challenge. Graph Neural Networks are proposed without considering the agnostic distribution shifts between training graphs and testing graphs, causing the degeneration of the generalization ability in out-of-distribution (OOD) settings. Boris et al. [Knyazev et al., 2019] have attempted to improve the generalization ability of GNNs with the help of graph pooling models. Moreover, Xu et al. [Xu et al., 2021] emphasized the significance of selecting appropriate pooling functions for enabling GNNs to generalize over graph data beyond the distribution of training data.

Opportunity. Recently, to improve the OOD generalization ability of GNNs has become an appealing and non-trivial task. According to the above introduction, utilizing graph pooling techniques can be an effective approach to improve the generalization capability of GNNs on OOD graph data.

Acknowledgments

This work was supported in part by the Natural Science Foundation of China (Nos. 61976162, 82174230, 62002090), Artificial Intelligence Innovation Project of Wuhan Science and Technology Bureau (No. 2022010702040070), and Science and Technology Major Project of Hubei Province (Next Generation AI Technologies) (No. 2019AEA170). Dr Wu is partially supported by ARC Projects LP210301259 and DP230100899. Prof Dacheng Tao is partially supported by Australian Research Council Project FL-170100117.

Machine-readable versions of this paper, for tools and AI agents:

• Markdown — metadata, abstract, full text and references
• JSON — metadata and structured references
• BibTeX