Graph Parsing Networks
Authors: Yunchong Song
Siyuan Huang
Xinbing Wang
Chenghu Zhou
Zhouhan Lin
Venue: ICLR 2024 poster (2024)
Keywords: GNN
graph pooling
parsing
Primary area: learning on graphs and other geometries & topologies
TL;DR: In this paper, we propose an efficient parsing algorithm to infer the graph pooling structure and enable the model to learn personalized pooling structure for each individual graph.

Abstract: Graph pooling compresses graph information into a compact representation. State-of-the-art graph pooling methods follow a hierarchical approach, which reduces the graph size step-by-step. These methods must balance memory efficiency with preserving node information, depending on whether they use node dropping or node clustering. Additionally, fixed pooling ratios or numbers of pooling layers are predefined for all graphs, which prevents personalized pooling structures from being captured for each individual graph. In this work, inspired by bottom-up grammar induction, we propose an efficient graph parsing algorithm to infer the pooling structure, which then drives graph pooling. The resulting Graph Parsing Network (GPN) adaptively learns personalized pooling structure for each individual graph. GPN benefits from the discrete assignments generated by the graph parsing algorithm, allowing good memory efficiency while preserving node information intact. Experimental results on standard benchmarks demonstrate that GPN outperforms state-of-the-art graph pooling methods in graph classification tasks while being able to achieve competitive performance in node classification tasks. We also conduct a graph reconstruction task to show GPN's ability to preserve node information and measure both memory and time efficiency through relevant tests.

Published as a conference paper at ICLR 2024
GRAPH PARSING NETWORKS
Yunchong Song', Siyuan Huang', Xinbing Wang', Chenghu Zhou', Zhouhan Lin't "Shanghai Jiao Tong University, Chinese Academy of Sciences (ycsong, xwang8 @du.u. on. 1in. 2mnnzhnhn@@aail com
ABSTRACT
Graph pooling compresses graph information into compact representation. State- of-the-art graph pooling methods follow a hierarchical approach, which reduces the graph size step-by-step. These methods must balance memory efficiency with preserving node information, depending on whether they use node dropping node clustering. Additionally, fixed pooling ratios numbers of pooling layers are predefined for all graphs, which prevents personalized pooling structures from being captured for each individual graph. In this work, inspired by bottom- up grammar induction, we propose an efficient graph parsing algorithm to infer the pooling structure, which then drives graph pooling. The resulting Graph Parsing Network (GPN) adaptively learns personalized pooling structure for each individual graph. GPN benefits from the discrete assignments generated by the graph parsing algorithm, allowing good memory efficiency while preserving node information intact. Experimental results on standard benchmarks demonstrate that GPN outperforms ofte-of-thh-ar graph pooling methods in graph classification tasks while being able to achieve competitive performance in node classification tasks. We also conduct a graph reconstruction task to show GPN's ability preserve node information and measure both memory and time efficiency through relevant tests
INTRODUCTION
Graph neural networks (GNNs) (Saareelli et al. 2008 Bruna et al. 2013 Defterrard et al. 2016
Kipf & Welling 2017 Velicković al. 2018 Hamilton et al. 2017 Gilmer et al.) 2017 17; Xu et al.
2019) have shown remarkable success in processing graph data from various fields (Li & Goldwasser
2019 Yan al. 2019 Suárez- et al. 2021 Kipf al., 2018). Graph pooling built top of GNNs. It aims to capture graph-level information by compressing set nodes and their underlying
structure into a more concise representation. Early graph pooling methods, such as mean or add pool (Atwood & Towsley 2016 Xu et al. (211)). perform permulation-invariinn operations on all nodes in a graph. These flat pooling methods disregard the distinctions between nodes and fail to model the latent hierarchical structure within a graph. Thus, they can only capture information at the graph level in rough manner. To overcome this limitation, researchers drew inspiration from pooling designs in computer vision (Ronneberger et al. 2015 Noh et al.) 2015 Jégou et al., 2017). they turned to perform hierarchical pooling on graph data to capture structural information more accurately. The dominant approaches are node dropping (Gao & Ji, 2019 Lee et al. 2019) and node clustering (Ying) ctt al. 2018 Bianchi et al.) 2020). Each approach has its own advantages and disadvantages: node dropping methods reduce the size of graph by dropping certain proportion of nodes each step. While they are memory- efficient, they irreversibly lose node information and may damage graph connectivity (Baek et al. [222]] Wu al., 2022), leading to sub-optimal performance. On the other hand, node clustering methods perform clustering at each pooling layer, allowing for soft cluster assignments for each node, thus preserving its information. However, this comes the cost of dense cluster assignment matrix with quadratic memory complexity (Back et al. 2021 Liu et al. (023). sacrificing scalability. The comparison of graph pooling methods can refer to Figure I Hierarchical pooling methods need to strike a balance between preserving node information and being memory efficient, while our model excels both aspects.
"Zhouhan Lin is the corresponding author.
Code is available at httppp///eeetteaaao.lll..oooooaa

---

Published as a conference paper at ICLR 2024
x/
x A
x
AP
Node ckoterigs Dome unveg runi, Broak Snce Plord poaling Pre
Graph parving: Space unvipment Foep rolo, oomediiity bearlyy Loorable poaling Pre
Figure I: Comparison of graph pooling methods. The colors of the nodes indicate their pooling levels. The solid/dotted lines with arrows represent hard/soft node assignment matrixes.
Another fundamental problem of existing graph pooling methods is that they are unable to learn personalized pooling structure for each individual graph (Liu et al. 2023), i.e., they predefine fixed pooling ratio number of layers for all graphs. However, some graphs may be more compressible compared to others and imposing a constant pooling ratio may hurt performance on less compressible ones (Gao & Ji. 2019: Ranjan al. 2020 Wu et al. (022), leading to suboptimal performance. We represent the graph pooling structure as a rooted-tree tree to illustrate the problem, which we name the pooling tree (cf. Figure The root node represents the graph-level representation, while the leaf nodes are taken from the input graph. The nodes produced by the k-th pooling layer correspond to the height a of the tree. Ideally, the model should learn a personalized pooling tree for each graph with flexible shape. This means that we should not constrain the total height hmar or the number of nodes ng at height k. There are numerous methods that focus on optimizing graph structure (Gasteiger et al. 2019 Jiang et al. 2019; Chen et al.) 2020b, Jin et al. 2020; Suresh et al. 2021 Topping et al. 2022 Bo et al.] 2023). However, only a few (Diehl) 2019 Wu et al.J 2022) attempt to optimize pooling structure, and even those can only learn a partially flexible shape of the pooling tree and not in an
end-to-end fashion. In Appendix B and Appendix C
we discuss these methods in detail and highlight
the differences. Our model is the first to end-to-end learning of a fully flexible pooling tree.
To overcome these two crucial problems, we propose a graph parsing algorithm inspired by recent advancements in bottom-up grammar induction (Shen et al.) 2018b at 2019). In natural language processing, grammar induction techniques extract latent discrete structures from input text sequences without any guided supervision. We adapted this approach for the graph domain and used it to learn pooling trees. As shown in Figure 2] our model employs a graph parsing algorithm that assigns discrete assignment to each node at layer k, allowing us to infer the number of nodes n& at height k. The parsing process ends when the graph has been fully parsed (i.e., the graph size remains unchanged). enabling us to infer the total height hmaz. Therefore, our model can learn pooling tree with flexible shape for each individual graph in an end-to-end fashion. Our parsing algorithm is based on locality, thus ensures graph connectivity during pooling. We clustering nodes instead of dropping them, which preserves node information intact, and the discrete clustering process guarantees memory efficiency. Jo et al. (202T) also performs edge-centric graph pooling, however, they still need to pre-define the number of pooling layers pooling ratio. A more detailed introduction for related works can be found Appendix
2 PROPOSED METHOD
In this section, we first divide the graph pooling layer into three modules and introduce our design for each. Then, we present the details of our proposed graph parsing algorithm. Finally, we introduce the model architecture that is applied to both graph classification and node classification tasks.
2.1 GRAPH POOLING COMPONENTS
We represent a graph = (V,E), || = n, [|| = m with its feature matrix X E Ra and adjacent matrix A E Roxn, where n, m, d represents the number of nodes, the number of edges and the
2

---

Published as a conference paper at ICLR 2024
dimension of the node feature vector, respectively. Hierarchical graph pooling compress the original graph ((0) = G' into single vector, step-by-step. At each pooling layer, an input graph G( which has (4) nodes, is transformed into a smaller output graph G(++1) with fewer nodes (n (n(++)) < (*))). In this study, we present a unified framework which consists of three modules: graph information encoding, structural transformation, and multiset computation (see Figure
Graph information encoding This module extracts node features and graph structure to generate useful metrics. For instance, it can generate node scores for node dropping methods or cluster assignment vectors for node clustering methods. Considerable effort has been put into improving the quality of these metrics, as evidenced by the advanced designs discussed in Section H To encode structural information, we apply a GNN block and then use an MLP on adjacent nodes to calculate the edge score:
H (k) = GNN A C =a =00==oMM -MLP ! O H
a()) here is a sigmoid function, ((²) is the edge score matrix that satisfy C( = C(K) + A(), In practice, we simply implement the GNN block with multiple GCN layers.
Structural transformation This module consists of two steps: node assignment and output graph construction. In the k-th pooling layer, the first step involves mapping nodes from the input graph to
the output graph, resulting in an assignment matrix ((A) R=(()xn(**) s( ( S(K) fully encode the pooling tree with height K. The primary challenge here is to learn a flexible pooling tree
for each graph, as we described in Section[] We propose graph parsing algorithm A to construct node assignment and perform matrix multiplication for the second step:
S(A) = A (c(#) A (++1)= = (k))* A g+)
Multiset computation This module computes the feature matrix ((++1) for ((++1) As the input node set can be treated as a multiset, this module can be seen as multiset function (Back et al.] (021). Simple implementations include operators such ADD(.), MEAN(-), and MAX(). Recent studies have explored more expressive methods like DeepSets (Zaheer et al. 2017). or attention mechanisms
(Baek et al., 202I). We implement this module using DeepSets:
(k+1) DeepSets (A)), SS()) ML.P2 (S(A) MLP, H (H())
To update the MLP in Equation
| we need to involve edge scores in backpropagation since the graph parsing algorithm A is not differentiable. To achieve this, we compute mask (*) through edge scores. Let us consider a subgraph G; C (+)) induced by cluster in G(++1), We denote edges inside G(()) as E(A²) and a d-dimension ones vector. Through adding the score and then multiplying the features, the cluster can be aware of the number of edges assigned to i
((++1) = (k+1) o ()()1") y (N) ADD ({ {(c% ((
(G.k) E E
(4)
2.2 GRAPH PARSING ALGORITHM
Our graph parsing algorithm A takes edge score matrix (kk) as input and returns an assignment matrix ((k), We do not impose any constraints on the pooling ratio or the number of clusters. Therefore, we infer clusters from nodes in a manner similar to how larger units (e.g., clauses) are inferred from smaller units (e.g., phrases) in grammar induction. In order to make the pooling structure learnable, we rely on both the graph topology and set of continuous values defined on it, namely edge scores. As such, when edge scores are updated through gradients, the pooling structure can also be updated via decoding from it. To elaborate on this decoding process, we first introduce three operators that are utilized within it.
Definition 1. DOM (-) (short for "dominant") ):: this operator selects the dominant edge for each node, which determines its assignment. First performs a row-wise max indexing on the edge score matrix (Kk to obtain seed edges idx, then construct matrix ((() by filtering out other edges:
((k)) (1..) E idæ
idx argmax row- wise C (k))),
(4))
(5)
O, otherwise
Details for Equation and end-to-end training can be found in Appendix F
3

---

Published as a conference paper at ICLR 2024
X
vic
A(-)
200011
BM
Proposed graph parsing networks, driven by the graph parsing algorithm A. The box with three stages indicates the graph pooling layer, which recurrently builds the entire model. The red box shows the details and example of how A works.
Figure 2:
Definition 2. EXP (-) (short for "expand"): ): this operator expands set of seed edges idæ on the filtered graph ((K) through a neighbor lookup. First induce the node set l using idx, then merge neighboring edges idx' that are dominated by them. idx,,, idx, represent the sets of starting and ending node indices for the edge set idæ:
1= =uinon (fidæa); {idry)) idx' = ((i,))((i (lvjjl)) 6 #
(6)
Definition 3. GEN (-) (short for " "generate") ): given an assignment mapping s that maps node to cluster j, this operator generates the assignment matrix ((k) using 8:
[ (i.j)
(k) S.
0, otherwise
Based on these definitions, we present the afore- mentioned decoding process in Algorithm [ To facilitate understanding. we divided into three stages. In Stage we use the DOM (-) operator to identify the dominant edge for each node, which determines its assignment. To ensure memory efficient, we opt for a sparse assign- ment by selecting a single dominant edge for each node. This also protects locality by avoid- ing instances where a single node is assigned to multiple clusters, which could result in uncon-
Algorithm 1 Graph parsing algorithm
Input: edge score matrix ((k) Output: assignment matrix S(k)
I: ( DOM (C(+)
> Stage 1
2: + 0
3: +0
4: while sumn (()) + do
D. Stage
5:
idr <- argmax(((())
6:
do
nected nodes being assigned to the same cluster. During this stage, initialize ping s that associates nodes with clusters. As create clusters and map nodes to them by one, we also set an indicator variable p. which keeps track of the latest cluster's index.
7:
+ lidx
empty map-
I, f,idx'= + EXP (dxx Cik) idr +- union (ida, ida')
8:
9:
10:
while |idx|= =
union (s, ((.p)) E 1})
12:
(())
Cig <- -,,((i,)) E id.
In Stage 2, we use (Ak) to create This is done through a double-loop approach, where new cluster generated in the outer loop and nodes are assigned to it in the inner loop. In the outer loop. we choose the edge with the highest score (k) the seed edge. This edge considered as the first member of new cluster. In the inner loop, we expand this seed edge iteratively using the EXP(.) operator which performs neighborhood lookup and merges. The inner loop terminates when no additional edges can be
2--p 1-p+1
14: end while
15: ((k) = GEN(s)
D SStgee
16: return (k)
covered by expanding from the seed edges, i.e., |idz] q. We then map all the nodes in final node set to the same p-th cluster. After that, clear all the edges covered in this loop (ida) from (A)
4

---

Published as a conference paper at ICLR 2024
and update the indicator p. In Stage 3, we use the GEN(-) operator to create assignment matrix ((k) with If the graph has isolated nodes, generate separate cluster for each isolated node and create a corresponding mapping in s.
(1+1)
Complexity The time complexity for Algorithm I is O Σ d;), d, indicate the diameter of the
subgraph (( C G( induced by node in G Compared to EdgePool, which has a time complexity of (m)()),, our worst case time complexity of (n) is much smaller. In Appendix A.3] we provide further comparison to SEP and demonstrate that our model is more efficient than it.
These results indicate that our model is also time efficient and can handle dense large graphs
Proposition 4. (Proof in Appendix A.7 In k-th graph pooling layer, the time complexity for
2,(k11) 11)
Algorithm I is O Σ di), which upper-bounded by the worst case (n
Permutation invariance Permutation invariance is crucial property in graph representation learning as it ensures the model's ability to generalize on graph data. As the other components (GNN, DeepSets) of our model are already permutation invariant, we only focus on analyzing the permutation invariance of the graph parsing algorithm A.
Given a permutation matrix P, suppose the row-wise non-zero entries in C are distinct, A (C) (PCP!)) thus A is permutation invariant.
Proposition 5. (Proof in Appendix
A.2
Graph connectivity Keep the graph connectivity during pooling is important. Our parsing algorithm keep the connectivity of the input graph unchanged during graph pooling, which guarantees fluent flow of information on the pooled graph.
(k) Proposition (Proof in Appendix A.4) For nodes j.j E G(K), if there is a path oy connect them, (k+11 then a path Sp:P, would exist between the corresponding clusters Pi,Pz E G(++1) after parsing.
2.3 MODEL ARCHITECTURE
Graph-level architecture By utilizing the pooling layer that introduced in previous sections, can directly employ this model for graph classification tasks. The architecture of our model (depicted in Figure 3) comprises solely of one pooling layer which progressively decreases the size of the input graph until it matches the output graph produced by our graph parsing algorithm A. Subsequently, a multiset computation module is utilized to convert the final graph into single node and generate a compressed vector for graph classification.
Node-level architecture We developed an encoder-decoder architecture (refer to Figure 3) for the node classification task, inspired by previous graph pooling methods used in node- level tasks like TopKPool (Gao Ji 2019) and SEP (Wu et al., 2022). Our approach involves compressing the graph into a smaller size using bottom-up pooling in the encoder block, fol- lowed by expanding it in the decoder block. We store the assignment at every pooling layer dur- ing the encoding process and use this informa- tion for un-pooling in the decoding process. We implement k-th un-pooling layer as follows:
Fore
Figure 3: Graph-level and node-level GPN archi- tecture. Each un-pooling layer receives an as- (8) signment matrix and node feature through a skip- connection from its corresponding pooling layer.
A (I+1) s TT( -k) ((--)
x (k+1) = (hh
the variable h represents the height of the pooling tree in the encoder block. The assignment matrix (h) is stored in the (h- k)-th pooling layer and corresponds to the k-th un- pooling layer. Additionally, skip connections are applied between the encoder and decoder, following methods used in Gao & Jil (2019) Wu et al. 2022
5

---

Published as a conference paper at ICLR 2024
Table Graph classification accuracy with mean and standard deviation based on 20 random seeds, we bold the model with best performance.
DD
PROTEINS
NCT1
NCT109
FRANKENSTEIN
Graphs
1,178
1,113
4,110
4,127
4,337
Nodes (Avg.)
284.3 2
39.1 2
29.9
29.7
16.9
Classes
2
2
2
Set2Set (Vinyals et al.
2016
71.60:0.s7
72.16:0.43
66.9710.74
61.04:2.609
61.4620.47
Attention et al. 2010
+1.38
=1.87=0.60
09.00
67.87=a.40
61.31=0.4 41
GCN (KipF Welling 2017
13.333+1.3 1.00
73. 03.3.3
73.92+0.4
72.77=0.57
60.47=00.0
SortPoot [Zhang el al. 2018
71.87+0.00
73.91
788.74
68.59=20.67
63.44420.0
GMT BBack
78.1110.76
70.97
70.3510
69.45
66.7620
TopKPool (Gao
75.01
71.10=0.00
67.02+
66.12=1.60
61.46=0.84
SAGPool [
LLe al.
2019
76.4522..r
71.86200.7
67.45
67.86=1..0
61.7320:70
HIGP-SL Zhing el ml
2019
75. 75.16.0.00
74.09
75.97 07..0.44
74.27
63.80 23.80....50
GSAPool Zhang cl 20:20
76.07.1..81
73. 1..7
70.98 20
7..68.11.44
60.211o.0
ASAP Ramjan et 1020
76.87
0.077
71.48+0.4
70.07=00555
00.26:20.47
SPGP Loc
77.76+0.78
75.20=0.74
78.90
77.27=00.2
08.92s0.71
DiffPool Ying
2018
66.9522241
68 08.20=2.02
62.32+
61.98=1.88
60.60
EdgePool [iih
72.7713.00
71.7322.:1
78.9312
76.79:22.9
69.4222..0
MinCutPooT [Banchh cl. 2020
77.3610.40
75. 15.00
75.8810..57
74.56.1.44
68.301o.40
HoscPool (Duval & Malliaros 2022
76,83 0..90
75.05 05.005
78. 28.60
78.38:9.52
08.37
SEP (Wa et 2022
76.54+0.99
75.28=0.05
78.09
76.48:20.46
67.79+1.64
GPN
77.0920.81
75.62.1.74
80.87.1044
79.20
70.45
An informative node representation is crucial for node-level tasks. To achieve this, we utilize
separate GNN encoder for the multiset computation module. In the node-level architecture, Equation in the pooling layer needs to be rewritten as:
X (k+1)
DeepSets (GNN' (x({), (1)) sS(h)
(10)
EXPERIMENTS
In this section, evaluate model's performance six graph classification and four node classification datasets. We also demonstrate how the node information is well-preserved through graph reconstruction task. To assess the efficiency of our parsing algorithm, we conduct time and memory tests. Additionally, we showcase our model's ability to learn personalized pooling structure for each graph by visualizing the number pooling layers during training across different datasets. Finally. an ablation study is performed on all three graph pooling modules to determine their contributions.
3.1 GRAPH CLASSIFICATION
Graph classification requires a model to classify a graph into a label, which calls for graph-level representation learning.
Experimental setup We evaluate model on five widely-used graph classification benchmarks from TUDatasets (Morris et al. 2020): DD, PROTEINS, NCI1, NCI109, and FRANKENSTEIN Table [ presents the statistics of them. Additionally, evaluate model's performance at scale ogbg-molpeba, one the largest graph classification datasets OGB (Hu et al. 2020), comprising 400,000 graphs. For baselines,
select GCN (Kipf & Welling 2017) (with simple mean pooling), Set2Set (Vinyals et al.] (0166). Global-Attention (Li et 2016). SortPool (Zhang et al. 2018). and GMT (Back al.
(2021) | from the flat-pooling family. For hierarchical pooling methods, we include TopKPool (Gao & Jil 2019), SAGPool (Lee et al.) 2019). HGP-SL (Zhang et al. 2019). GSAPool (Zhang al. (0220). ASAP (Ranjan et al. al.] 2020), and SPGP (Lee et | (022) for node dropping and DiffPool (Ying et al. (018)) EdgePool (Diehl][201) 2019). MinCutPool (Bianchi et al. 2020). HoscPool (Duval& Malliaros 2022), and SEP (Wu et al., 2022) for node clustering"] We adopt 10-fold cross-validation with 20 random seeds for both model initialization and fold generation. This
SEP is special case in node clustering based pooling, since it computes sparse pooling tree before training, while others generate dense assignments for each forward pass.

---

Published as a conference paper at ICLR 2024
Table Node classification accuracy with mean and standard deviation based on 10 splits, we bold the model with best performance.
Cora
CiteSeer
PubMed
Film
# Nodes
2.708
3,327
18.317
7,600
# Edges
5,278
4,676 7
44,327
26.752
# Classes
5
MLP
7..69
74.0221.90
87.1610.77
36.53119770
GCN (Kipf & Welling, 2017
86, 960.88-11177
76.50&1.36
88.4240.00
27.32+1.10
GraphSAGE (Hamilton et al.
2017
86, 9.+4
76.01=1.30
85.15=0.50
31.23
GAT (Velickovic el all 201
76.55
87.30
27.44100.99
MixHop AND- Ei- m
2019
87. 07.6140.55
76, 16.
85,31 #0.01
32.22
PairNorm 7Tha & A Akoglu
20220
45.79..1.01
73.50 1.47
87.53
27.40
Geom-GCN (Pei et 2020
15.35
78.02:+.115
89.95=0047
31.59+1.15
GCNII Chen et M0A00
88.37 +1225
77.33=
90.15++0.0
17.44
H2GCN Zhu el al 20A0
$7.5 1.220
77.11 1
89.49.0.54
35.70
GPRGNN
#021
77.13:107
87.51=0.38
31.63+1222
GGCN Yan et an KUAR)
87. 1.05
77.14
89.15
37.54
NSD Bounal it elm
2022
87 $7.30+11.15
77.14s1as
89.19+0.40
37.81+1.15
TopKPool Gao 2019
79. 2.88
71.97
85.47
SEP (Wu of m. 2072
37.111.
75
87.520035
GPN
88. 07..77
77.02=1.66
89.61 #0.34
38.11#1128
means there are 200 runs in total behind each data point, ensuring fair comparison. This approach
Lee is consistent with Lee et al. (2019), Ranjann et al. (2020), and Lee et al. (2022). More details about
datasets, implementations and model tuning can be found in Appendix|H.] H.1
Classification results shows that our model out- performs SOTA graph pooling methods on four out of five datasets, demonstrating its ability to capture graph-level information precisely. The sub-optimal performance of our model on the DD dataset can be attributed to graph size, as DD has an average node count of 284.3, making it the dataset with large and sparse graphs that pose long- range issues (Alon & Yahav 2020). Resolving such issue requires global information, the complete attention graph in GMT (Baek et al. 202T) provide such information short- cut, thus they perform better. Notably, our method does not include these designs, yet it has achieved considerable re- sults on DD. On the large-scale egbg-molpchee dataset, our model outperforms all SOTA graph pooling models and significantly improves upon GCN's 's performance, demon- strating the superior scalability of our model, and the po- tential to handle complex large scale data.
Table 2: Graph classification accuracy
on large scale dataset ogbg-molge molppba.
ogbg-molpeba
# Graphs
437,929
# Nodes (Avg.)
26.0
# Classes
GCN (Kipl & Welling
2017
20 20.20
HGP-SL Zhing al 2019
18 64
ASAP (Ranjan al. 2020 23 13:44::.4:
Dichl 2019
0OM
GMT Back
70.0.000
SPGP
(126 et al. 20223
23.95 23.95
GPN
26.65.1..0
3.2 NODE CLASSIFICATION
The node classification task focuses on node-level information. Each graph node is assigned label, and the goal is to predict its label.
Experimental setup We conduct node classification experiments under full supervision for four datasets: Cora, CiteSeer, and PubMed from [Sn et al.] (2008), and Film from Pei et al. (2020). Table 3 shows the datasets' statistics. To evaluate our model's performance comprehensively, we compare it with a range of baselines. including classical methods: GCN (Kipf & Welling) (017))
GAT (Veličković et al. (2088). GraphSAGE (Hamilton et al., 2017). PairNorm (Zhao & Akoglu 2020), MixHop (Abu-El-Haijy et al., 2019); and SOTA methods: Geom-GCN (Pei et al. (020). GCNII (Chen et al.) 2020a), GPRGNN (Chien et al., 202I). H2GCN (Zhu et al., (020), GGCN (Yan) et al. 2022), and NSD (Bodnar et al. 2022). We further compare with two graph pooling methods, TopKPool (Gao & Ji 2019) and SEP (Wu et al. 2022). as other pooling models cannot scale to thousands of nodes or lack node-level architecture. We follow the same dataset splitting and settings as Zhu et al. (020)) Yan et al. (2022) and Bodnar et al. (2022) and report the average results of 10 dataset splits. Dataset and cemplmmetationn details can be found in Appendix H.2
7

---

Published as a conference paper at ICLR 2024
Classification results The results in Table demonstrate the competitiveness of model on the selected datasets. Our approach achieves SOTA performance on Film dataset and performs comparably to the SOTA model for node classification, GCNII, on Cora and PubMed datasets. Furthermore, we surpass most baseline models on CiteSeer dataset. Since the compared SOTA methods explicitly designed for node-level tasks and did not extend graph-level, overall performance is satisfactory. Notably, when compared with the leading graph pooling model SEP, we outperform on all datasets. This reveals the superior generality across graph-level and node-level tasks of our proposed method.
3.3 GRAPH RECONSTRUCTION
To demonstrate our model's ability to maintain node information, we conduct graph reconstruction experiment. This can visually illustrate the potential structural damage from graph pooling.
Experimental setup We follow Bianchi et al. (2020) to construct graph autoencoder that includes pool- ing and un-pooling operations on input graph G = (X, A) to recover the original node features. The recov- ered graph G (X", AA") has the same structure as the input graph, but the node features produced solely by the pooling and un-pooling process. The mean square
loss XX- Xr|2 is used to train the autoencoder. We 2-D plane as
(a) Original
(b) TopKPool (c) MinCutPool
(d) GPN
use the coordinates the node features, thus the recovered node features can be visually assessed to evaluate the pooling model's 's ability to preserve node information. We test on the grid and ring graphs. We choose TopKPool and MinCutPool as baselines, which represent the node dropping and node clustering methods, respectively. More baseline results and higher resolution images can be found in Appendix H.
Figure 4: Graph reconstruction task on ring and grid syn- thetic graphs, which tests whether graph pooling model can preserve node information intact.
Reconstruction results Figure shows the graph reconstruction results on a 2D plane. obvious that Pook, which drops nodes, damages node information and performs poorly In contrast, MinCutPool uses clustering and preserves the original coordinates better. Compared to these methods, model recovers clearer ring graph and effectively preserves the central part of the grid graph, demonstrating its ability to preserve node information intact.
graphs
3.4 EFFICIENCY STUDY
In this section, we assess the memory and time efficiency of our proposed model. Since models from the same class will have similar memory and time performance, we choose one model from each class of pooling methods as our baseline. Specifically, we select GMT, TopKPool, MinCutPool, EdgePool for flat pooling, node dropping, node clustering, and edge-scoring based pooling respectively.
Memory efficiency We test memory efficiency as described in Back et al. (2021). Varying numbers of nodes (n) were used to generate Erdos-Renyl graphs, while keeping the number of edges constant at 2n per graph. Applying pooling to each graph once, we compare our model's GPU memory usage with baselines (Figure 5). Our parsing-based model shows much better memory efficiency when compared to MinCutPool. This confirms approach's 's memory-efficient nature.
Time efficiency To test time efficiency, we creat Erdos-Reny. Renyi graphs with m = n22110, and time one forward graph pooling as in Back et al. (2021). Our results, shown in Figure 6 demonstrate that GPN is much more efficient than EdgePool, a model also based on edge-scoring This is because model has upper-bound time complexity of On). making it able to handle large number of edges, whereas EdgePool's 's time complexity of O(m) would result in significant delays when processing too many edges.
8

---

Published as a conference paper at ICLR 2024
GMT
Mecathed 6%
Hiouthe GP4
164
MMerory (MIb)
102
Pooling layors
1.0
(sec)
0.5
L0a
0.0
200
400
6:00
800
1000
0.0
0.5
1.0
2.5
2.0
2.5
Nodes
1ed
Nodds
# Epachs
162
Figure 5: Memory efficiency
Figure 6: Time efficiency test, "x" indicate the out-of out-of-memory error.
Figure 7: Number of pool- ing layers visualization during model training.
test, "x" indicate the out-of- memory error.
3.5 VISUALIZATION
In this section, we verify if our model learns personalized pooling structure for each graph. To achieve this, we have created a visualization in Figure 7 that shows the number of pooling layers learned during training on various datasets. Each data point and its shadow represent the mean and variance of the number of pooling layers for all graphs within dataset. The star indicate the step with best validation loss. model learns distinct pooling layers for each. The fluctuating curve and its shadows during training confirm that our model effectively learns personalized pooling layers for every graph in a dataset.
evident that the heights of star indicators vary across datasets, indicating our
3.6 ABLATION STUDY
In this subsection, we conducted an ablation study to assess the contribution of each module that
Table 4: Ablation study on three components of graph pooling layer, covering both graph dataset and node dataset.
we described in Section [1 We use four datasets, including both graph and node levels. We evalu- ated these variants: for the graph information encoding module, we used GAT or GIN layers in-
Graph-level
Node-tevel
PROTEINS
FRANKENSTEIN
Cora
CiteSeer
Original
75.62
70.4520.3
88.07=0.87
77.02
WAGAT w/GIN
76.41
60.9412.6
87.46.1.15
77.1611
75.02s1.25
70.18
86.62=1.26
76.50a1 67
w/Mean w/Max pool
75.26
69.7519.54
87.40=1.02
76.50
stead of GCN layers; we trans-
72.12s
09.61+0.46
87.08=1.26
76. 26.23++1 20
formed the input graph to com-
Complete graph
74.12st.03
07.003+1.0
74.85=1.47
OOM
plete graph check the necessity
of graph locality and our proposed graph parsing algorithm; we tested two simple aggregators without parameters, mean pool and max pool, instead of DeepSets for multiset computation. SableAsshor that overall superior performance was obtained by these variants, except when we broke the locality with complete graph, the model suffered significant performance drop, highlighting the importance of graph locality and underscoring the crucial role of parsing algorithm. The good performance on other variants indicates that our model is robust regarding the selection of GNN encoder and multiset function. Notably, GPN with GAT backbone get better results CiteSeer, which reveals the potential of our model.
4 CONCLUSION
In this paper, we address two pressing challenges associated with hierarchical graph pooling: the inability preserve node information while simultaneously maintaining high degree of memory efficiency, and the lack of a mechanism for learning graph pooling structures for each individual graph. To address these challenges, we introduce novel graph parsing algorithm. We demonstrate that our model outperforms existing statc-of-the ohftth--artt art graph pooling methods in graph classification, while also delivering competitive performance in node classification. Additionally, graph reconstruction task validates our model's 's ability to preserve node information intact, while an efficiency study confirms the effectiveness of our solution in terms of both time and memory consumption. All the proofs, more detailed introduction to related works, the limitations of our model and broader impacts can be found in Appendix due to the space limit.

---

Published as a conference paper at ICLR 2024
5 ETHICS STATEMENT
In this work, we propose novel graph pooling model. Our model is a general graph pooling model that does make explicit assumptions about data distribution, thus avoiding the occurrence of (social) bias. However, our data-driven pooling mechanism needs to learn from samples with labels, and it possible to be misled by targeting corrupted graph structures or features, which can have negative social impact because both internet data and social networks can be represented as graphs. We can develop corresponding ethical guidelines and constraints for the usage of our model to avoid such problems.
REPRODUCIBILITY STATEMENT
We provide an introduction to our used datasets and model configuration in the experimental section of our paper. The dataset is mentioned first in this section. In our Appendix, report the hardware and software environment used in our experiments, the methods used for aaperrparameter tuning, and the steps for downloading, loading, and pre- proppessssing the datasets. In our released source code, we list the steps required to reproduce the results and provide yaml files that include all the hyper-parameters for the reported performance in this paper.
ACKNOWLEDGEMENT
This work was sponsored by the National Key Research and Development Program of China (No. 2023ZD0121402) and National Natural Science Foundation of China (NSFC) grant 6216133...
REFERENCES
Sami Oou-EE-HHija. Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg. and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning. pp. 21-29. PMLR, 2019.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2020.
James Atwood and Don Towsley. Diffusiin--oonolutionaal neural networks. Advances in neural information processing systems, 29, 2016.
Jinheon Baek, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling. International Conference on Learning Representations, 2021.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International Conference on Machine Learning, pp. 874-883.
PMLR, 2020.
Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. In The Eleventh International Conference on Learning Representations, 2023, URL
https://cpenrevieee net htrr//ormmm//// 1iw.mmmmdddpppttt3333m 3oyJal
Cristian Bodnar, Francesco Di Giovanni, Benjamin Chamberlain, Pietro Lio, and Michael Bronstein. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in gnns. Advances in Neural Information Processing Systems, 35: 1522111711, 2022.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv: 1312.6633..203 2013.
Ming Chen. Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020a.
10

---

Published as a conference paper at ICLR 2024
Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. Advances in neural information processing systems, 33: 19314-19326, 2020b.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. International Conference on Learning Representations, 2021.
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.
Frederik Diehl. Edge contraction pooling for graph neural networks. arXiv preprinl 2019.
Andrew Drozdov, Patrick Verga, Mohit Yadav, Mohit lyyer, and Andrew McCallum. Unsupervised latent tree induction with deep inside-outside recursive auto-encoders. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pp. 1129-1144 144,, 2019.
Alexandre Duval and Fragkiskos Malliaros. Higher-order clustering and pooling for graph neural networks. In Proceedings of the s1 ACM International Conference on Information & Knowledge Management, pp. 426 435, 2022.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 022422, 2019.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In international conference on machine learning, pp. 2083-2092. PMLR, 2019.
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. Advances neural information processing systems, 32, 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1263-1272. PMLR, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems, 33:22 18-22133, 2020.
Simon Jégou, Michal Drozdzal, David Vazquez, Adriana Romero, and Yoshua Bengio. The one hundred layers tiramisu: Fully convolutional densenets for semantic segmentation. Proceedings of the IEEE conference computer vision and pattern recognition workshops, pp. 11-19, 2017.
Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo. Semi-supervised learning with graph reaming--onnvlutiin
networks. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 11313-11324 13300, 2019.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang. Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 66 66-74,7 2020.
Jaehyeong Jo, Jinheon Back, Seul Lee, Dongki Kim, Minki Kang, and Sung Ju Hwang. Edge representation learning with hypergraphs. In Advances in Neural Information Processing Systems, 2021.
Amir Hosein Khasahmadi, Kaveh Hassani, Parsa Moradi, Leo Lee, and Quaid Morris. Memory- based graph networks. In International Conference on Learning Representations, 2020. URL
httpps://ppenreete net http://pareeeeee...eeefooomrr//a ftee:/oorumiiddrrlllll

---

Published as a conference paper at ICLR 2024
Yoon Kim, Chris Dyer, and Alexander M Rush. Compound probabilistic context-free grammars for grammar induction. In Proceedings of the 57th Anmual Meeting of the Association for Computa- fional Linguistics, pp. 2369-2385, 2019a.
Yoon Kim, Alexander M Rush, Lei Yu, Adhiguna Kuncoro, Chris Dyer, and Gábor Melis. Un- supervised recurrent neural network grammars. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume I (Long and Short Papers), pp. 1105-1117, 2019b.
Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang. Max Welling, and Richard Zemel. Neural relational inference for interacting systems. In International Conference on Machine Learning, pp. 2688- 2697. PMLR. 2018.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference Learning Representations, 2017.
Dan Klein and Christopher D Manning. Corpus-based induction of syntactic structure: Models of dependency and constituency. In Proceedings of the 42nd annual meeting of the association for computational linguistics (ACL-04), pp. 478-485, 2004.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International conference on machine learning, pp. 3734-3743, PMLR, 2019.
Sangseon Lee, Dohoon Lee, Yinhua Piao, and Sun Kim. SPGP: Structure prototype guided graph pooling. In NewrIPS 2022 Workshop: New Frontiers in Graph Learning, 2022. URL https
/ copenreview.net/formmme wwt.
Chang Li and Dan Goldwasser. Encoding social information with graph convolutional networks forpolitical perspective detection in news media. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 2594-2604 2019.
Maosen Li, Siheng Chen, Ya Zhang, and Ivor Tsang. Graph networks with vertex infomax pooling. Advances in Neural Information Processing Systems, 14093-14100 2020.
Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. International Conference on Learning Representations, 2016.
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. Proceedings of the Thioty-Second International Joint Conference on Artificial Intelligence, Survey Track, 2023.
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 preprins arXiv:2007.08663 2020.
Hyconwoo Noh, Seunghoon Hong, and Bohyung Han. Learning deconvolution network for semantic segmentation. In Proceedings of the IEEE international conference computer vision, pp. 1520-1528, 2015.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. International Conference Learning Representations, 2020.
Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar. Asap: Adaptive structure aware pooling for
learning hierarchical graph representations. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 5470-5477, 2020.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical
image segmentation. Medical Image Computing and Computer-Assisted Intervention-MICCO 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part IIl 18, pp. 234-241 Springer, 2015.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
12

---

Published as a conference paper at ICLR 2024
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rae -aads Collective classification in network data. Al magazine, 29(3):93 93, 2008.
Yikang Shen, Zhouhan Lin, Chin-wei Huang, and Aaron Courville. Neural language modeling by jointly learning syntax and lexicon. In International Conference on Learning Representations. 2018a.
Yikang Shen, Zhouhan Lin, Athul Paul Jacob, Alessandro Sordoni, Aaron Courville, and Yoshua Bengio. Straight to the tree: Constituency parsing with neural syntactic distance. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1171-1180, 2018b.
Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville. Ordered neurons: Integrating tree structures into recurrent neural networks. In International Conference on Learning Representations. 2019.
net/ forsm//ooum?e d- 6qii557
Yikang Shen, Yi Tay, Che Zheng, Dara Bahri, Donald Metzler, and Aaron Courville. Structformer: Joint unsupervised induction of dependency and constituency structure from masked language modeling. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 1 1th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). pp. 7196-7209, 2021.
José Suárez- Surrez-Varela, Paul Almasan, Miquel Ferriol-Galmés, Krzysztof Rusek, Fabien Geyer, Xiangle Cheng, Xiang Shi, Shihan Xiao, Franco Scarselli, Albert Cabellos-Apane Aparicio,, et al. Graph neural networks for communication networks: Context, use cases and opportunities. arXiv preprint MrXi::2112.14792, 1021.
Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks graphs via curvature. In International Conference on Learning Representations, 2022. URL https::///...... http:///ppneeeeeeeeeeeee hotpo./RLttsss///eeeeeeeeaae
7d=7UmjRGZpp
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. International Conference Learning Representations, 2018.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. International Conference on Learning Representations, 2016.
Yu Guang Wang, Ming Li, Zheng Ma, Guido Montufar, Xiaosheng Zhuang, and Yanan Fan. Haar graph pooling. In International conference on machine learning, pp. 9952-9960 PMLR, 2020.
Junran Wu, Xueyuan Chen, Ke Xu, and Shangzhe Li. Structural entropy guided graph hierarchical pooling. In International Conference on Machine Learning, pp. 24017-24030. PMLR, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Yujun Yan, Jiong Zhu, Marlena Duda, Eric Solarz, Chandra Sripada, and Danai Koutra. Groupinn: Grouping-basee interpretable neural network for classification limited, noisy brain data. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 772-782, 2019.
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing graph convolutional neural networks. In 2022 IEEE International Conference Data Mining (ICDM), pp. 1287-1292. IEFF, 2022.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hier- archical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018.
13

---

Published as a conference paper at ICLR 2024
Hao Yuan and Shuiwang Ji. Structpool: Structured graph pooling via conditional random fields, In Proceedings of the 8th International Conference on Learning Representations, 2020.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
Liang Zhang, Xudong Wang. Hongsheng Li, Guangming Zhu, Peiyi Shen, Ping Li, Xiaoyuan Lu, Syed Afaq Ali Shah, and Mohammed Bennamoun. ferttrre-feattre based graph self-adaptive pooling. In Proceedings of The Web Conference 2020, pp. (098-3104 2020.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
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.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing gnns. International Conference on Learning Representations, 2020.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-7804 2020.
14

---

Published as a conference paper at ICLR 2024
A PROOFS
A.1 PROOFS REGRADING PROPOSITION
Proof. Since in the k-th graph pooling layer, the number of iterations for outer loop in Algorithm
n (k+11
is (k++1), to prove the time complexity O Σ d;), only need to prove the number of iterations
1=1
2 the DOM performs a edges neighborhood lookup graph (*k), and this lookup operation can be effectively parallelized for all edges, thus the number of iterations in inner loop equals to the lookup steps needed to traverse all the nodes that subgraph subgraph corresponding node in the output graph), which equals to the diameter d; of the subgraph.
in i-th inner loop is d,. Notice that in Definition
Since graph (*() has n (k) non-zero entries as we described in Definition the time complexity can never exceed it; then, suppose the input graph C(R) is a pure set of isolated nodes, without any structure, then the number iterations Algorithm equals (k),, which the worst case.
A.2 PROOFS REGRADING PROPOSITION
5
Proof. Since the commonly used operations like sum (-), argmax (-), union (-) in Algorithm I are based set and permutation invariant, only need to prove 3 operators also permutation invariant: for DOM (-) operator, it first doing a row-wise max index, which is permutation invariant, then masking is applied, since the masking based on the idx from last step, thus it is also permutation invariant; for EXP (.) operator, it performs a neighborhood lookup on matrix in a parallel way (has no need specify the order), thus is also permutation invariant; for GEN (.) operator, it's results has no relationship with ordering since it's just matrix filling process, thus is also permutation invariant.
introduced
The above analysis are based set of distinct values in edge score matrix ((k) if there are some duplicate values, the argmax (.) operator cannot guarantee uniqueness. Thus we need to assume the row-wise non-zero entries in C are distinct, when the assumption breaks, it means there least two nodes with common neighbors and their node features are exactly the same.
A.3 PROOFS REGRADING TIME COMPLEXITY COMPARISON WITH SEP
Proof. Suppose we have Amaz pooling layers in total, then the overall time complexity is Amaz Σ diy), diş indicate the diameter for subgraph in j-th pooling layer. The worst case
is that the input graph has edge and get time complexity of (1)())) Thus have overall time
hyan (5)))
Σ Σ da) S 0 Amag
complexity O that also apply heuristic algorithm, our parsing algorithm has a better time efficiency: SEP has overall time complexity (2n + hmaa (m log (0) + (n)) (Wu et al. 2022). which is much larger than ours.
Σ nb-1)) S (1 Compared to SEP Wu et al. 2022)
A.4 PROOFS REGRADING PROPOSITION
Proof. In order to prove the conclusion, we only need to demonstrate that any two nodes in the graph ((k) (V(A), g(k)), if there is a path connect them, then path would exist between the (D(++)),g((++))
corresponding clusters in the graph ((++1) (y(k+1), g(++1)).
Assuming nodes i,j (4)) and there exists path between them: (i Ux U = j), where i E ((A), 0.... ... is Po, (+++), now we examine the relationship between the clusters Poy Pucer If the edge
... Suppose the cluster assigned to node (A)
(u). u141) E (()) is a dominant edge, meaning C( > O. It should be noted that the operator EXP conducts neighborhoodd-lokup operation on (+), regardless of whether the node v or
15

---

Published as a conference paper at ICLR 2024
u1+1 is traversed first in Stage 2 of the parsing algorithm, since these two nodes are adjacent in ((A) they will both be assigned to the same cluster, we have Pe: = P
If the edge (v), ((1) E (() is not a dominating edge, i... Clu C 11 0, then the two nodes
will be assigned to different clusters. According to Equation 2, A (k+1) = S(k) A ( then (K)) L.PMt 1. Popee Noting that Serpe = 1, when 1 V2, 12 i. the corresponding summation term is 1, which means that at least one non-zero term exists among all the summed terms. Since all summation
PopoP = (S(K)) Pop A
(k+1)
(k) (())(() PPu44 = - (E==
(4) (R) ((k) (A)
S0441-Po111 1, A. 01,0
(R)
(k-1) items are non-negative, it follows that A Pop. > O. We have Por1)) E g(K+1),
In conclusion, Pv; and pu1+1 are either the same node or adjacent nodes. Therefore, the node sequence (Pep: .. Puw)) is a path on the graph G(K+1), This completes the proof.
B RELATED WORKS
Graph pooling Researchers have shifted their focus to hierarchical pooling as flat pooling methods (Atwood & Towsley 2016 Xu et al., 2019) face difficulties in capturing comprehensive structural information. Early node dropping methods (Gao & Ji 2019; Lee et al. (019)) only retain nodes with higher computed scores. This explicit dropping risks the irreversible loss of important node
information and can break the graph connectivity (Baek et al. 2021 Wu et al. (022). To better preserve node information, InfoMax-basee based (Li et al.] (2020), memory- based (Khasahmadi et al. 2020)
[ and global prototype-basee (Lee et al.] (022)) techniques have been suggested: ZZhng et al. (2019)
2020p: Ranjan et al. (2020) improves graph connectivity by graph structure learning. These attempts alleviate the problem of node dropping, but at cost of additional computing burden. On the other hand, the node clustering approach calculates a soft assignment vector for each node. This method due to its dense assignment matrix. Some works try to make this matrix sparser using various priors, such as penalty entropy in Ying al.] Haar wavelet transforms in Wang et al.) However, these penalty terms may hurt model training. Another trawback of node clustering methods is that they can easily converge to trivial solutions where each node has uniform soft assignments, due to the ignorance of locality. Several methods inject locality into GNN encoders, such as CRF- based (Yuan & Jil 2020) or MinCut based (Bianchi et al.] 2220)) but they are unable scale to larger graphs Unlike the previous mentioned works, Jo et al. (2021) focuses on edges as the center and emphasizes precise learning of both node and edge information. Finally, none of these approaches can optimize the pooling structure for each individual graph.
effectively retains the node's 's information but can be memory-intensin
Structure Optimization Structure optimization on graphs has gained significant attention in recent
times. The majority of these methods concentrate on the horizonial level, which involves learning
graph structure through techniques such as structure learning (Jiang et al. 2019: Chen et al.) 2020b;
Jin et al. 2020; Suresh et al.) (222I) to determine node adjacency with without a graph prior, or
graph rewiring (Gasteiger et al. 2019) Topping et al., 2022; Bo ct al. 2023) that adds or removes
edges to enhance message passing. Only few focus the vertical level, which is concerned with learning pooling structures. EdgePool (Diehl 2019) is an initial attempt to dynamically learn pooling trees by iteratively contracting edges based on calculated scores, unless one of their nodes has already been part of a contracted edge. Although they achieve end-to-end pooling tree learning through edge scores, their contraction-based strategy limits flexibility as it results in a near-half pooling ratio. On the other hand, SEP (Wu et al. 2022) uses combinatorial optimization to generate pooling trees by defining and optimizing metric with a greedy algorithm. While this optimizes the pooling tree well for each graph, it is only used as pre-processing step before training and cannot benefit from downstream supervision signals. Additionally, SEP relies solely on graph topology and fails to capture node features.
Grammar Induction Grammar induction, which aims at learning the latent structure behind natural language in an unsupervised way, can be dated back to Klein & Manning (2004). It has seen many advances recently, such as by using amortized variational inference on a cunsition-basee parser Kim et al. (2019)), by dynamic programming Drozdov et (2019), or by maximizing the marginal likelihood of a sentence generated by PCFG et al. (2019a), etc. Among all these various approaches, the most related is the works based on syntactic distance Shen et al. (2018b), which
16

---

Published as a conference paper at ICLR 2024
GPN
EdgePool
X
Ag
ha
X A
X
X (
X (
X X"
X A
A
X A
X A
X A
Figure 8: A comparison for SEP, EdgePool and GPN in terms of their pooling mechanisms.
a sequence of continuous scalar values that allows the tree to be inferred from it in a bottom-up fashion. This approach has been successfully shown work for both recurrent models (Shen al. (2018a) 2019) and Transformer- induce latent tree structures byproduct of some self self-supervised training process, our approach let the latent structure drive graph pooling and engage in gradient backpropagation, resulting in a more task-relevant model.
models [Shen et al. (202)). Different from the above works that
C DIFFERENCES COMPARED TO CLOSE METHODS
Our model significantly differs from EdgePool. In EdgePool, each cluster is usually composed of two adjacent nodes, and only when all neighbors of certain node have been assigned, a cluster with single node will be formed. Therefore, the proportion of pooling the EdgePool is always close to 50%, which is not learnable. In contrast, in model, the pooling ratio not constrained and is entirely inferred by the parsing algorithm, allowing for end-to-end learning. Moreover, the number of pooling layers in EdgePool is set hyperparameter, and each pooling layer independent parameters. However, we recursively use single pooling layer to construct our model, the number of which is inferred by the parsing algorithm. This varies continuously during the training process, with all pooling layers sharing the same parameters. Figure g visually illustrates the differences between three methods for optimizing pooling tree, i.e., SEP, EdgePool, and our proposed GPN.
D LIMITATION
model demonstrates good time efficiency when processing batched graphs. However, if batch contains graphs with varying numbers of pooling layers, the model may not be as time-efficient. This because graphs with fewer pooling layers would have wait for those with more iterations to finish before proceeding, potentially leading to inefficiencies when dealing with pretty large batches of graph data. For potential extreme cases that the inferred height of pooling tree is too large, we can set a maximum height limit for the pooling tree in the algorithm. This means the algorithm will stop during the parsing process once this height reached.
In Section 3.4
E DISCUSSION
When running our model on large-scale graph with a significant number of nodes, our graph parsing algorithm may infer high pooling tree. In this case, the model will perform numerous graph convolutions and continuously smooth node features. The model structure for node classification task already includes residual connections from the encoder the decoder, which helps alleviate potential over-smoothing issues by preserving local neighborhood information and original node features through residual connections.
17

---

Published as a conference paper at ICLR 2024
F DETAILS FOR EQUATION 4 AND END-TO-END TRAINING
Here we describe the forward and backward passes of our model to clarify the training process: During the forward pass, we first use GNN and MLP to compute the edge scores (Equation 1). Then we run Algorithm to obtain the assignment matrix (Equation 2) and performs the multiset computation to obtain the coarsened graph (Equation 3). The final step is to compute the edge score mask (Equation 4) ensure the gradients can flow into GNN and MLP. During the backward pass. Algorithm I does not run. Instead, the gradient backpropagation is performed directly. The GNN and MLP can be updated through the gradients of the edge score mask.
We further present the details of Equation 4 to enhance understanding: Induce subgraph G(4)) C G()) from node U; means: each node in graph ((++1) is a cluster generated by the k-th pooling layer, thus it corresponds connected subgraph ((() in (()), In order to allow gradients flow into the MLP used for calculating edge scores, we aggregate the scores of all the edges & in each subgraph G We then obtain a vector y: IR." (++1) represents the score of clusters. This vector is then replicated into a mask matrix y 1 T E In((t-ixdd which matches the shape of the node feature matrix X (k-1), Finally, this mask is element-wise multiplied with the node feature matrix. During the backward pass, Algorithm does not run. Instead, the gradient backpropagation is performed directly. The GNN and MLP can be updated through the gradients of the edge score mask.
G BROADER IMPACTS
In this study, we suggest new graph pooling model that can address issues with current methods. Our model derives the pooling structure from both the topology of the graph and the node features, and is not founded on any assumptions regarding the data, which mitigates the risk of social bias. Nonetheless, since the algorithm used for data parsing is data-driven, it is possible that the pooling structure may be misguided by corrupted graph structure or features, which could lead unfavorable social consequences. Since both internet data and social networks can be presented as graphs, we need to establish ethical guidelines and limit the usage of our model to avert such issues.
H EXPERIMENTAL DETAILS
We use NVIDIA GeForce RTX 3090 and NVIDIA GeForce RTX 4090 as the hardware environment, and use PyTorch and PyTorch Geometric (Fey & Lenssen 2019) as our software environment. The datasets are downloaded from PyTorch Geometric, we also use dataloader provided by Py PyTorch Geometric to load and pre- pre-process datasets. We fix the random seed for reproducibility. We report detailed configurations as follows.
H.1 GRAPH CLASSIFICATION
Dataset details DD and PROTEINS are datasets of protein structures that represent macromolecules. Our task is to distinguish whether they are enzymes non-enzymes based on their structure. The graph size of DD is larger than the other four datasets, resulting in the highest number of graph-pooling layers. NCII and NCI109 two medium-sized datasets of chemical compounds labeled according to whether they are active against lung cancer cells and/or ovarian cancer cells. FRANKENSTEIN is chimeric dataset of Mutagenicity and MNIST. is relatively small and has the lowest average number of nodes among these five datasets, as reflected in its smallest number of learned graph-pooling layers. ogbg-molpeha a chemical compound dataset used to determine molecular properties. is curated dataset from PubChem BioAAssay (PCBA) that provides information on the biological activities of small molecules. The performance of ogbg-molppe dataset is highly biased due to the small number of positive examples. We borrowed the baseline results from Lee et al. 2019). Ranjan et al. (202)), and Lee et al. (2022). Except for MinCutPool, HoscPool, GMT and SEP. we reran their code and report the performance, since they did not have public records under our setting. We followed Py Torch Geometric (Fey & Lenssen 2019) scripts to reimplement EdgePool for testing.
is measured using Average Precision, as this
18

---

Published as a conference paper at ICLR 2024
Table 5: Best hyper-parameters for graph classification
Dataset
Hyper-parameter
DD
LGNN 22 DeeppSets 1, Dropout : 0.2, Ir 0.0001, H 128, B 64
PROTEINS
LGNN : :3, DeepSets 1, Dropout: 0.1, 0.0005, H 128, B 128
NCI1
LGNN 2, DeepSets 3, Dropout 0.4, : 0.0005, H 256, B 256
NC1109
LGNN 3, DeeepSets Dropout 0.2, Ir 0.0005, 128, 64
FRANKENSTEIN
LGNN'T 3, DeeepSetss 1, Dropout: 0.2, Ir 0.001, H 128, B 128
ogbg-molpcba
LGNN 3, DpeppSets
Dropout 0.3, Ir 0.001, H 128, B 128
Table 6: Best hyper-parameters for node classification
Dataset
Hyper-parameters
Cora
LGNN, 1, LONN, 2, L DeepSets 2, LMPP : Dropout 0.5, DropEdge 0.3, Ir 0.005
CiteSeer LGNN 2, LANNs 8, Deeppetts 2, LMPP :3, Dropout 0.6, DropEdge 0.1, Ir 0.005
PubMed
LGNN 2, LGNN,
DeepSets 1, LMPP: 1, Dropout 0.7, DropEdge 0.7, Ir 0.001
Film
LGNN, 22 LGNN, 2, DeepSets LMLP: : Dropout 0.5, DropEdge 0.5, Ir 0.001
Implementation details For each experiment, we repeat the experiment on 20 seeds (from 0 to 19), and we use the 10-fold calss-validation method. So for each dataset we end up reporting the average result of 200 runs on the test set, which allows us to effectively avoid noise in the results and makes the results more credible. For all datasets, we use an early stopping strategy to avoid overfitting. We use validation loss as the criterion the early stopping. Also, the maximum number of epochs is set to 500 for all datasets. The Table 5 gives the best hyperparameters used in the 5 graph classification datasets. For the sake of brevity, we use abbreviations in the table. LGNN represents number of GCN layers inside the GNN block, DeeppSets represents number of MLP layers of DeepSets, LM represents number of layers of the MLP for edge score computation, Dropout represents dropout in the MIP, DropEdge represents the ratio of the edge dropout when perform parsing, Ir represents learning rate, H represents hidden channel, represents batch size.
H.2 NODE CLASSIFICATION
Dataset details CiteSeer, Cora and PubMed are all citation network datasets. They share a common feature in that their node features are 0/1-valued word vectors. CiteSeer consists of 3,312 scientific publications, which contain a total of six categories. has a citation network consisting of 4,732 links. Its word vector has dimension of 3,703. Cora consists of 2,708 scientific publications containing total of seven categories. Its citation network consists of 5,429 links. Its word vector has a dimension of 1,433. PubMed consists of 19,717 scientific publications related diabetes, which are divided into three different categories. Its citation network consists of 44,338 links. Its word vector has a dimension of 500. We obtain all baseline results from Zhu et al. (2020), Yan et al. (2022) and Bodnar et al. (2022). except for TopKPool and SEP, we rerun their code and perform a grid search on Cora, CiteSeer, and PubMed ensure fair comparison.
Implementation details For the node classification task, we used a ten-fold cross-validation method. We keep the same hidden layer for all datasets and limit the maximum number of epochs to 2000. we use an early stopping strategy for all datasets. We also use validation loss as an early stopping criterion. We use the grid search method to find suitable hyperparameters. Table 6 gives the different hyperparameters used for the four node classification datasets. And unlike the first three datasets, Film is a dataset that describes the collaborative relationships between actors.
19

---

Published as a conference paper at ICLR 2024
(a) TopKPool
(b) SAGPool
(c) ASAPPool
(d) DitiPool
(e) minCutPool
(1) GPN
Figure 9: Reconstruction results of ring synthetic graphs, compared to node drop and clustering methods.
H.3 GRAPH RECONSTRUCTION
Implementation details In order keep the same setting with Bianchi al. (2020), we use two message passing layers before the pooling operation and after the unpooling operation. We choose mean squared eиror (MSE) as the loss function. We use an early stopping strategy where patience is set to 1,000 epochs. The maximum number of epochs is set to 10,000. We then optimise the network using the Adam optimiser. In the experiment Bianchi et (2020), they retained 25% of the nodes by adjusting the height of the tree. In contrast, our GPN model automatically retains around 30% of the nodes of the grid and ring during pooling.
More reconstruction results Figure 9 and Figure show the results of graphs reconstructed using various pooling methods. We can visually see that the node-drop method suffers from information loss, resulting in the original graph being basically unrecognisable. Also, we preserves the shape of the ring as well as the coordinates of the interior of the mesh very well.
that GPN
20

---

Published as a conference paper at ICLR 2024
(a) TopKPool
SAGPool
(c) ASAPPool
(d) DifiPool
(c) minCutPool
GPN
Figure 10: Reconstruction results of grid synthetic graphs, compared to node drop and clustering methods.
0.8
0.6
0.7
0.9
Sentence parsing
Graph pooling
Figure 11: Sentence parsing build a syntactic tree based on the scores between tokens; graph parsing build pooling structure based on the scores defined on edges.
21


Reviews:
[{"review_id": "BJzIWValx8", "reviewer": "Reviewer_H5gS", "summary": "This paper deals with graph pooling, i.e., compressing graph information into compact representations. The paper contains a mostly experimental study of various methods. The proposed graph parsing network constitutes a novel contribution, it adaptively learns personalized pooling structures. Experimental results show that the method outperforms state of the art graph pooling methods.", "questions": "none", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The proposed approach does seem novel, and it also seems to perform well compared to existing graph pooling networks.", "weaknesses": "Graph pooling can elegantly be cast into a compression framework and would hence benefit from an analysis of\nits fundamental limits based on information theory. The pooling of a graph structure (potentially with some side information as\nconsidered) here is a classical information-theoretic problem, i.e., how to best store all the information characterizing the graph\nin a vector of finite length or even better a bitstring of finite length. It may well be that the entire field of graph pooling as\ncurrently considered in the ML literature does not take this perspective, but reading this paper makes it clear that many of the questions\nasked here would benefit from such a perspective.\n\nGenerally, this reviewer finds the paper to be quite ad-hoc and also it uses a lot of jargon, not always defined or consistently used. The language is also confusing in many places.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XUJ0GfBwc7", "reviewer": "Reviewer_4RVW", "summary": "This paper presents a novel graph pooling method, namely Graph Parsing Network (GPN), which aims to learn an individual pooling structure for each individual graph in an end-to-end fashion while being memory and time efficient. Specifically, the authors generate the assignment matrix, which is used to transform the larger graph into its compressed smaller graph by mapping nodes of the original graph into certain clusters, per graph. Also, this assignment matrix is generated based on the graph parsing algorithm that infers pooling structures of graphs from their edge scores, i.e., firstly selecting the dominant edges and then expanding them to construct the node assignment matrix for graph pooling. The authors evaluate the performance of the proposed Graph Parsing Network (GPN) on graph classification and node classification tasks as well as the graph reconstruction task, showing its effectiveness and efficiencies.", "questions": "* In Equation (10), it may be better to represent the superscript on GNN' according to its layer index, since GNN' is different across different layers. \n* In Figure 5, the proposed GPN is memory efficient compared to the baseline that uses the cluster assignment matrix for graph pooling. However, the GPN also uses the cluster assignment matrix for graph pooling. In this vein, I am wondering why there exists a significant difference in efficiency while both methods are similar in using the cluster assignment matrix.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The motivation to adaptively condense different graphs based on their differences in graph structures (i.e., edge importances) is sound.\n* The idea of using a graph parsing algorithm to make an individual pooling structure for each graph is interesting and reasonable.\n* The proposed GPN surpasses existing graph pooling methods on both graph-level and node-level tasks.\n* The proposed GPN is efficient in terms of memory usage and computational time, particularly compared to the node-clustering-based (assignment-matrix-based) graph pooling methods.", "weaknesses": "* This work may be similar to the idea of [1] which considers and manipulates edges during graph pooling (i.e., making the cluster assignment matrix with edges), since this work also performs edge-centric graph pooling with the cluster assignment matrix that is generated from edges. \n* Equation (4) lacks details on motivation. I understand that, in order to perform backpropagation with edge scores, edge scores should be added or multiplied with other learnable variables. On the other hand, it is unclear why the edge scores should be multiplied in this way (Equation (4)) and what may be the effect of this multiplication on node features.\n* The authors may further perform the statistical test on the main results (Table 1 and Table 2) since the performance of the proposed GPN is comparable against other performant baselines when considering mean and standard deviations together.\n\n---\n\n[1] Edge Representation Learning with Hypergraphs, NeurIPS 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DF4T857baJ", "reviewer": "Reviewer_xTBe", "summary": "This paper aims to construct a graph pooling method called a graph parsing network (GPN) that can be personalized to every graph and has a good balance of maintaining the node information and high memory efficiency simultaneously. \nThe method is built upon existing GNNs and designs a novel algorithm to construct personalized pooling trees for graphs. The empirical results on graph classification show its effectiveness and efficiency.", "questions": "1. What does a 'different GNN` mean in node classification? $\\mathbf{H}^{(k)}$ in Eq. 3 is the same as '$GNN^\\prime(\\mathbf{X}^{(k)}, \\mathbf{A}^{(k)})$` in eq. 10.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well written, clearly showing its motivation and model structure.\n2. The novel part lies in that it designs a novel algorithm that can adaptively form clusters layer by layer that minimizes loss of information of graph structure and node features, and since it does not have learnable parameters in the graph parsing algorithm. \n3. The empirical results on graph classification and reconstruction demonstrate that the proposed model has a good ability to maintain the graph structure and node feature information.", "weaknesses": "1. It seems that GPN works well on small-sized graphs from the experimental results. Discussion on large-sized graphs is expected to be included in the paper. \n2. If the tree is high for some large-sized graph, the performance might be worse due to over-smoothing.\n3. For the model itself involving GNNs, it is not clear how you train this model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wS976dAG4n", "reviewer": "Reviewer_UKss", "summary": "This work proposes an efficient graph parsing algorithm to infer the pooling structure that drives graph pooling. The pooling structure is trained end-to-end. It achieves competitive real-world performance and good memory and time efficiency.", "questions": "1. The point 1 and 2 in the Weakness section.\n\n2. The argmax operator in DOM is not differentiable. How to train the whole model end-to-end?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. Clear presentation of method.\n\n2. Extensive experiments on both graph and node tasks.", "weaknesses": "1. Time complexity. Though the paragraph above Proposition 4 claims that the time complexity of each pooling layer is $O(n^{(k)})$, the computation of edge score $C$ still takes $O(m^{(k)})$ time.\n\n2. Proposition 5 is doubtful. The argmax operator may not produce unique output when the multiset has several equal maximum elements. \n\n3. The performance gain in ablation study is not significant. In Table 4, the performance difference between the origin model and the model with  Mean pool is smaller than the score deviation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)