StructPool: Structured Graph Pooling via Conditional Random Fields
Authors: Hao Yuan
Shuiwang Ji
Venue:  (2020)
Keywords: Graph Pooling
Representation Learning
Graph Analysis

Abstract: Learning high-level representations for graphs is of great importance for graph analysis tasks. In addition to graph convolution, graph pooling is an important but less explored research area. In particular, most of existing graph pooling techniques do not consider the graph structural information explicitly. We argue that such information is important and develop a novel graph pooling technique, know as the StructPool, in this work. We consider the graph pooling as a node clustering problem, which requires the learning of a cluster assignment matrix. We propose to formulate it as a structured prediction problem and employ conditional random fields to capture the relationships among assignments of different nodes.  We also generalize our method to incorporate graph topological information in designing the Gibbs energy function.  Experimental results on multiple datasets demonstrate the effectiveness of our proposed StructPool.

Published as a conference paper at ICLR 2020
STRUCTPOOL: STRUCTURED GRAPH POOLING VIA CONDITIONAL RANDOM FIELDS
Hao Yuan
Shuiwang Ji
Department of Computer Science & Engineering Texas A&M University
Department of Computer Science & Engineering Texas A&M University College Station, TX 77843, USA s jji aatatamu.ee edu
College Station, TX 77843, USA hao. yuang taattaam.... edu
ABSTRACT
Learning high-level representations for graphs is of great importance for graph analysis tasks. In addition to graph convolution, graph pooling is an important but less explored research area. In particular, most of existing graph pooling techniques do not consider the graph structural information explicitly. We argue that such information is important and develop novel graph pooling technique, know as the STRUCTPOOL, in this work. We consider the graph pooling as a node clustering problem, which requires the learning of cluster assignment trix. We propose to formulate it as a structured prediction problem and employ conditional random fields capture the relationships among the assignments of different nodes. We also generalize our method to incorporate graph topologi- cal information in designing the Gibbs energy function. Experimental results on multiple datasets demonstrate the effectiveness of our proposed STRUCTPOOL.
INTRODUCTION
Graph neural networks have achieved the state-of-the-ae results for multiple graph tasks, such as node classification (Veličković et al. 2018 Gao & Jil 2019b Gao et al., 2018) and link predic-
tion (Zhang & Chen. 2018 Cai & Ji 2020). These results demonstrate the effectiveness of graph neural networks to learn node representations. However, graph classification tasks also require learn- ing good graph-level representations. Since pooling operations are shown to be effective in many image and NLP tasks, is natural investigate pooling techniques for graph data (Yu Koltun, 2016 Springenberg et al., 2014). Recent work extends the global sum/average pooling operations to graph models by simply summing or averaging all node features (Atwood & Towsley 2016)] Simonovsky & Komodakis (017). However, these trivial global pooling operations may lose im- portant features and ignore structural information. Furthermore, global pooling are not hierarchical so that cannot apply them where multiple pooling operations are required, such Graph U- Net
Gao & Jil (0199). Several advanced graph pooling methods, such as SORTPOOL (Zhang 2018), TOPKPOOL (Gao & Ji 2019a). DIFFPOOL (Ying al. 2018), and SAGPOOL (Lee 2019). are recently proposed and achieve promising performance on graph classification tasks. However, none of them explicitly models the relationships among different nodes and thus may ig- nore important structural information. We argue that such information is important and should be explicitly captured in graph pooling.
al.
et al.
In this work, we propose a novel graph pooling technique, known as the STRUCTPOOL, that formu- lates graph pooling as a structured prediction problem. Following DIFFPOOL (Ying et al. 2018). we consider graph pooling as a node clustering problem, and each cluster corresponds to node in the new graph after pooling. Intuitively, two nodes with similar features should have higher probability of being assigned to the same cluster. Hence, the assignment of given node should depend on both the input node features and the assignments of other nodes. We formulate this as a structured prediction problem and employ conditional random fields (CRFs) (Lafferty et al.) 2001) to capture such high-order structural relationships among the assignments of different nodes. In addition, generalize method by incorporating the graph topological information so that method can control the clique set in our CRFs. We employ the mean field approximation to compute the assignments and describe how incorporate it in graph networks. Then the networks can be

---

Published as a conference paper at ICLR 2020
trained in end-to-end fashion. Experiments show that our proposed STRUCTPOOL outperforms existing methods significantly and consistently. We also show that STRUCTPOOL incurs acceptable computational cost given its superior performance.
BACKGROUND AND RELATED WORK
2.1 GRAPH CONVOLUTIONAL NETWORKS
graph can be represented by its adjacency matrix and node features. Formally, for a graph G consisting of n nodes, its topology information can be represented by an adjacency matrix A E {0, 10 and the node features can be represented as X E Ra assurning each node has c-dimensional feature vector. Deep graph neural networks (GNNs) learn feature representa- tions for different nodes using these matrices (Gilmer et al.] (017). Several approaches are pro- posed to investigate deep GNNs, and they generally follow a neighborhood information aggregation scheme (Gilmer et al. 2017 Xu et al. 2019 Hamilton et al. 2017 Kipf & Welling 2017 Veličkovid jet al. 2018). In each step, the representation a node is updated by aggregating the representations of its neighbors. Graph Convolutional Networks (GCNs) are popular variants of GNNs and inspired by the first order graph Laplacian methods (Kipl & Welling 2017). The graph convolution operation formally defined as:
X = f(D fDD==((D-A---- A
where A= = A + I is used to add self-loops to the adjacency matrix, D denotes the diagonal node degree matrix to normalize Å, X; m=xe; are the node features after jth graph convolution layer, P. E [ is trainable matrix to perform feature transformation, and f(-) denotes a non-linear activation function. Then X; Raxe, is transformed to Xi+1 E Rnxa++ where the number of
nodes remains the same. A similar form of GCNs proposed (Zhang et al. 2018) can expressed
X = f(D=-(D-AX,P))
(2)
differs from the GCNs in Equation (T) by performing different normalization and a theoretically closer approximation to the Weisfeiler- Leemman Lehman algorithm (Weisfeiler & Lehman 1968). Hence, in our models, we use the latter version of GCNs in Equation (2)
2.2 GRAPH POOLING
Several advanced pooling techniques are proposed recently for graph models, such as SORTPOOL, TOPKPOOL, DIFFPOOL, and SAGPOOL, and achieve great performance on multiple benchmark datasets. All of SORTPOOL (Zhang et al. 2018). TOPKPOOL (Gao & Jil 2019a), and SAG- POOL (Lee et al. 2019) learn to select important nodes from the original graph and use these nodes to build a new graph. They share the similar idea to learn a sorting vector based on node representa- tions using GCNs, which indicates the importance of different nodes. Then only the top i important nodes are selected to form a new graph while the other nodes are ignored. However, the ignored nodes may contain important features and this information is lost during pooling. DIFFPOOL (Ying) itt al. 2018) treats the graph pooling as a node clustering problem. A cluster of nodes from the orig- inal graph are merged to form a new node in the new graph. DIFFPOOL proposes to perform GCNs on node features to obtain node clustering assignment matrix. Intuitively, the cluster assignment of a given node should depend the cluster assignments of other nodes. However, DIFFPOOL does not explicitly consider such high-order structural relationships, which we believe are important for graph pooling. In this work, we propose novel structured graph pooling technique, known as the STRUCTPOOL, for effectively learning high-level graph representations. Different from exist- ing methods, our method explicitly captures high-order structural relationships between different nodes via conditional random fields. In addition, our method is generalized by incorporating graph topological information A to control which node pairs are included in our CRFs.
2.3 INTEGRATING CRFs WITH GNNS
Recent work Gao et al. with GNNs. The CGNF (a et al. 2019) is a GNN architecture for graph node classification which explicitly models a joint probability of the entire set of node labels via CRFs and performs inference
2019 Qu et al. 2019 Ma et al. 2019) investigates how to combine CRFs
2

---

Published as a conference paper at ICLR 2020
via dynamic programming. In addition, the GMNN (Qu et al., 2019) focuses semi-supervisee object classification tasks and models the joint distribution of object labels conditioned on object attributes using CRFs. It proposes pseudolikelihook variational EM framework for model learning and inference. Recent work (Gao et al. 2019) integrates CRRs with GNNs by proposing a CRF layer to encourage similar nodes to have similar hidden features that similarity information can be preserved explicitly, All these methods are proposed for node classification tasks and the CRFs are incorporated in different ways. Different from existing work, our STRUCTPOOL is proposed for graph pooling operation and the energy is optimized via mean field approximation. All operations our STRUCTPOOL can be realized by GNN operations so that our STRUCTPOOL can be easily used in any GNNs and trained in an end-to-end fashion.
3 STRUCTURED GRAPH POOLING
3.1 GRAPH POOLING VIA NODE CLUSTERING
Even though pooling techniques are shown to facilitate the training of deep models and improve their performance significantly in many image and NLP tasks (Yu & Koltun 2016 (Springebberg ict al. 2014), local pooling operations cannot be directly applied to graph tasks. The reason is there no spatial locality information among graph nodes. Global max/average pooling operations can be employed for graph tasks but they may lead to information loss, due to largely reducing the size of representations trivially. A graph G with nodes be represented by feature matrix X E R'xe and an adjacent matrix E {0, 1)===_ Graph pooling operations aim at reducing the number of graph nodes and learning new representations. Suppose that graph pooling generates a new graph G' with l nodes. The representation matrices of G are denoted X E R and Ā E {0, 1 j
The goal of graph pooling is learn relationships between X, and X, Å. In this work, we consider graph pooling via node clustering. In particular, the nodes of the original graph G' are assigned to i different clusters. Then each cluster is transformed to a new node in the new graph G. The clustering assignments can be represented as an assignment matrix M E Baxk For hard assignments, mijj E {0, 1) denotes if node i in graph G' belongs to cluster j. For soft assignments, ma, [o, 1] denotes the probability that node i in graph G' belongs to cluster j and E, maj 1.
Then the new graph & can be computed as
x= ==M"X, x, À MMM AM).
(3)
where g(-) is a function that g(ā,,)) = 1 if شz > and g = otherwise.
3.2 LEARNING CLUSTERING ASSIGNMENTS VIA CONDITIONAL RANDOM FIELDS
Intuitively, node features describe the properties of different nodes. Then nodes with similar features should have higher chance to be assigned to the same cluster. That is, for any node in the original graph G, its cluster assignment should not only depend on node feature matrix X but also condition on the cluster assignments of the other nodes. We believe such high-order structural information is useful for graph pooling and should be explicitly captured while learning clustering assignments. To this end, propose novel structured graph pooling technique, known STRUCTPOOL. which generates the assignment matrix by considering the feature matrix X and the relationships between the assignments of different nodes. We propose to formulate this a conditional random field (CRF) problem. The CRFs model a set of random variables with a Markov Random Field (MRF), conditioned on global observation (Lafferty et al. 2001). We formally define Y {Yi..... Y.} as a random field where Y; E {1..... fij is a random variable. Each Y, indicates to which cluster the node i is assigned. Here the feature representation X is treated as global observation. We build a graphical model on Y. which is defined as G". Then the pair (Y, X) can be defined as a CRF, characterized by the Gibbs distribution
X(
((X) exp
1
Σ cEC,
(4)
where e denotes a clique, Cor is a set of cliques in G², (X) is the partition function, and (. is a
potential function induced by e (Krähenbühi & Koltun 2011 Lafferty al. 2001). Then the Gibbs
3

---

Published as a conference paper at ICLR 2020
Usary Enengy
Assignment Matrix
Softmax
Original Graph
GCNs
New Graph
Pairwise Energy
Itenativelyy Update
Figure 1: Illustrations of our proposed STRUCTPOOL. Given graph with 6 nodes, the color of each node represents its features. We perform graph pooling to obtain new graph with = nodes. The unary energy matrix be obtained by multiple GCN layers using X and A. The pairwise energy is measured by attention matrix using node feature and topology information A. Then by performing iterative updating, the mean field approximation yields the most probable assignment matrix. Finally, we obtain the new graph with 4 nodes, represented by X and A.
energy function for an assignment y = {y1, ... ,9 for all variables can be written as F( = Σ
(yel)))
(5)
cEC
Finding the optimal assignment is equivalent to maximizing P(Y X), which can also be interpreted minimizing the Gibbs energy.
3.3 GIBBS ENERGY WITH TOPOLOGY INFORMATION
Now we define the clique set Co in G'. Similar to the existing CRF model (Krähenbühl & Koltun 2011], include all unary cliques in Cg since need measure the energy for assigning each node. For pairwise cliques, we generalize our method to control the pairwise clique set by incorporating the graph topological information A. We consider g-hop connectivity based on A to define the pairwise cliques, which builds pairwise relationships between different nodes. Let A {0, 1|"x* represent the ε-hop connectivity of graph G where af,, = indicates node and node are reachable in G within é hops. Then we include all pairwise cliques (i.j) in Co " = 1. Altogether, the Gibbs energy for cluster assignment y can be written as
Fly) Σ (wr) + Σ Epplynn 13)., (gf
(6)
where (v:) represents the unary energy for node i to be assigned to cluster yt- In addition, 4p Yj) is the pairwise energy, which indicates the energy of assigning node i, to cluster yis yj respectively. Note that we drop the condition information in Equation (6) for simplicity. If is large enough, our CRF is equivalent to the dense CRFs. If equal to 1, we have A A so that only 1-hop information in the adjacent matrix is considered. These two types of energy can be obtained directly by neural networks (Zheng et al. 2015). Given the global observations X and the topology information A, employ multiple graph convolution lavers to obtain the unary energy V. E R Existing work on image tasks (Krähenbühh & Koltun| (201)) proposes to employ Gaus- sian kernels measure the pairwise energy. However, due computational inefficiency, we cannot directly apply it to our CRF model. The pairwise energy proposed in (Krähenbühl & Koltun 201T can be written as
K
Sp Uy) = p(y. U3)
Σ (m) ((m) 2;)), m=1
where (((m) represents the th Gaussian kernel, I; is the feature vector for node i in X, w((m) denotes learnable weights, and p(y;, Uj) is compatibility function that models the compatibility
4

---

Published as a conference paper at ICLR 2020
Algorithm 1 STRUCTPOOL
1: Given a graph G' with n nodes represented by X E Ruxe and A E {0, 1] the goal is to obtain G with & nodes that X E R and Á E {0, 1) The Ehhop connectivity matrix A can be easily obtained from A.
2: Perform GCNs to obtain unary energy matrix Vu E Raxk
3: Initialize that (i: = % exp (i.))) for all 0 S i I n and 0 j k.
4: while not converged do
5: Calculate attention map W that Wi,j Emgi
of for all i + and 0 S i,j S n.
#f 2m
6: Message passing that (t.. )) = Empf Ws.m Q(m. Compatibility transform that (ii,j) Em ()m..))(i,,
7:
8: Local update that ji. = v (i. - ().
9: Perform normalization that ((i,5) - exp (Q( for and j.
10: end while
11: For soft assignments, the assignment matrix is M softmax(Q))
12: For hard assignments, the assignment matrix is M = argmax (Q) for each row.
13: Obtain new graph Q that X = M X,'X,A, A g AM).
between different assignment pairs. However, it is computationally inefficient to accurately com- pute the outputs of Gaussian kernels, especially for graph data when the feature vectors are high- dimensional. Hence, in this work, we propose to employ the attention matrix as the measurement of pairwise energy. Intuitively, Gaussian kernels indicate how strongly different feature vectors are connected with each other. Similarly, the attention matrix reflects similarities between different fea- ture vectors but with a significantly less computational cost. Specifically, each feature vector 2; is attended to any other feature vector I, if the pair (i,j) is existing in clique set Co.. Hence, the pairwise energy can obtained by
x
Up U3) = (((.. Uj)
(8)
Exeps . Fb
It can be efficiently computed by matrix multiplication and normalization. Minimizing the Gibbs en- engy in Equation (6) results the most probable cluster assignments for given graph G. However, such minimization is intractable, and hence mean field approximation is proposed (Krähenbühl & Koltun, 2011). which is an iterative updating algorithm. We follow the mean-field approximation obtain the most probable cluster assignments. Altogether, the steps of our proposed STRUCT- POOL are shown in Algorithm[] All operations in our proposed STRUCTPOOL can be implemented as GNN operations, and hence the STRUCTPOOL can be employed in any deep graph model and trained in an end-to-end fashion. The unary energy matrix can be obtained by stacking several GCN layers, and the normalization operations (step 3&9 in Algorithm TT are equivalent to softmax operations. All other steps can be computed by matrix computations. It is noteworthy that the com- patibility function u(y: y;) ) can be implemented as a trainable matrix A E R and automatically learned during training. Hence, no prior domain knowledge is required for designing the compatibil- ity function. We illustrate our proposed STRUCTPOOL. in Figure where we perform STRUCTPOOL on a graph G with nodes, and obtain a new graph G with nodes.
3.4 COMPUTATIONAL COMPLEXITY ANALYSIS
We theoretically analyze the computational efficiency of our proposed STRUCTPOOL. Since computational efficiency is especially important for large-scale graph datasets, we assume that > k c, The computational complexity of one GCN layer is O(n + n²c ncē) x (n Assuming we employ layers of GCNs to obtain the unary energy, its computational cost (in²). Assuming there are m iterations in updating algorithm, the computational com- Ommr²). The final step for computing Á and X takes Onkec + n²k + nk?) zs (n²)) computational complexity. Altogether, the complexity STRUCT- POOL is ((m + )) which is close to the complexity of stacking m i layers of GCNs.
plexity is O(m(n2c + n² k + n)33)
5

---

Published as a conference paper at ICLR 2020
Table 1: Classification results for six benchmark datasets. Note that of these deep methods can outperform the traditional method WL on COLLAB. We believe the reason is the graphs in COLLAB only have single-layer structures while deep models are complex capture them.
Method
Dataset
ENZYMES
D&D
COLLAB
PROTEINS
IMDB-B
IMDB-M
GRAPHLET
41.03
74.85
64.66
72.91
SHORTEST-PATH
42.32
78.86
59.10
76.43
WL
53,43
78.34
78.61
74.68
PATCHYSAN
76.27
72.60
75.00
71.00
45.23
DCNN
58.09
52.11
61.29
49.06
33,49
DGK
73.09
71.68
66.96
44.55
ECC
53.50
72.54
67.79
72.65
GRAPHSAGE
54.25
75.42
68.25
70.48
SET2SET
60.15
78.12
71.75
74.29
DGCNN
57.12
79.37
73.76
75.54
70.03
47.83
DIFFPOOL
62.53
80.64
75.48
76.25
STRUCTPOOL
63.83
84.19
74.22
80.36
74.70
52.47
3.5
DEEP GRAPH NETWORKS FOR GRAPH CLASSIFICATION
In this section, we investigate graph classification tasks which require both good node-level and graph-level representations. For most state-of-the-art deep graph classification models, they share similar pipeline that first produces node representations using GNNs, then performs pooling op- erations obtain high-level representations, and finally employs fully-connected layers to perform classification. Note that the high-level representations can be either vector or group of k vectors. For set of graphs with different node numbers, with a pre-defined k, our proposed STRUCT produce & vectors for each graphs. Hence, our method can be casily generalized and coupled to any deep graph classification model. Specially, our model for graph classification is developed based DGCNN (Zhang al. 2018). Given any input graph, our model first employs several layers GCNs (Equation (2) to aggregate features from neighbors and learn representations for nodes. Next, perform STRUCTPOOL layer obtain vectors for each graph. Finally, 1D convolutional layers and fully-connected layers are used to classify the graph.
4 EXPERIMENTAL STUDIES
4.1 DATASETS AND EXPERIMENTAL. SETTINGS
We evaluate our proposed STRUCTPOOL on eight benchmark datasets, including five bioinformatics protein datasets: ENZYMES PTC, MUTAG, PROTHINS (Borgwardt et al.) 2005), D&D (Dobson & Doig. 2003), and three social network datasets: COLLAB (Yanardag & Vishwanathan 2015b), IMDB-B. IMDB-M (Yanardag & Vishwanathan, 2015a). Most of them are relatively large-scale and hence suitable for evaluating deep graph models. We report the statistics and properties of them in Supplementary Table Please see the Supplementary Section A for experimental settings.
We compare our method with several state-of-tth-arr deep GNN methods. PATCHYSAN (Niepert 2016) learns node representations and a canonical node ordering to perform classification. DCNN (Awoood & Towsley 2016) learns multi-scale substructure features by diffusion graph con- volutions and performs global sum pooling. DGK (Yanardag & Vishwanathan 2015a) models latent representations for sub-structures in graphs, which is similar to learn word embeddings. ECC (Si-) monovsky & Komodakis 2017) performs GCNs conditioning on both node features and edge in- formation and uses global sum pooling before the final classifier. GRAPHSAGE (Hamilton et al. 2017) is an inductive framework which generates node embeddings by sampling and aggregating features from local neighbors, and it employs global mean pooling. SET2SET /Vinyals et al.) 2015) proposes an aggregation method to replace the global pooling operations in deep graph networks. DGCNN (Zhang et al. 2018) proposes pooling strategy named SORTPOOL which sorts all nodes

---

Published as a conference paper at ICLR 2020
Table 2: Comparisons between different pooling techniques under the same framework.
Method
Dataset
ENZYMES
D&D
COLLAB
PROTEINS
IMDB-B
IMDB-M
SUM POOL
47.33
78.72
69.45
76.26
51.69
42.76
SORTPOOL
52.83
80.60
73.92
76.83
70.00
46.26
TOPK Pool
53.67
81.71
73.34
77.47
72.80
49.00
DIFFPOOL
60,33
80.94
71.78
77.74
72.40
50.13
SAGPOOL 64.17
81.03
73.28
78.82
73.40
51.13
STRUCTPOOL
63.83
84.19
74.22
80.36
74.70
52.47
by learning and selects the first k nodes to form graph. DIFFPOOL (Ying al. 2018) is
built based on GRAPHSAGE architecture but with their proposed differentiable pooling. Note that for of these methods, pooling operations are employed to obtain graph-level representations before the final classifier. In addition, we compare our STRUCTPOOL with three graph kernels: Graphlet (Shervashidze et al., 2009). Shortest-path (Borgwardt & Kriegel 2005), and Weisfeiler- Lehman subtree kernel (WL) Weisfeiler & Lehman 1968).
4.2 CLASSIFICATION RESULTS
We evaluate our proposed method on six benchmark datasets and compare with several state-of-the- art approaches. The results are reported in Table where the best results are shown in bold and the second best results are shown with underlines. For our STRUCTPOOL, we perform 10-fold cross validations and report the average accuracy for each dataset. The 10-fold splitting is the same as DGCNN. For all comparing methods, the results are taken from existing work (Ying et al.) 2018) Zhang et al. 2018).
can observe that our STRUCTPOOL obtains the best performance on out of 6 benchmark datasets. For these datasets, the classification results of our method are significantly better than all comparing methods, including advanced models DGCNN and DIFFPOOL. Notably, model outperforms the second-best performance by average of 3.58% these 5 datasets. In addition, the graph kernel method WL obtains the best performance on COLLAB dataset and none of these deep models performance compared with the second best model. This because many graphs in COLLAB only have simple structures and deep models may be too complex capture them.
achieve similar performance. Our model obtain competitive
4.3 COMPARISONS OF DIFFERENT POOLING METHODS
To demonstrate the effectiveness of proposed pooling technique, we compare different pooling techniques under the same network framework. Specifically, we compare our STRUCTPOOL with the global sum pool, SORTPOOL, TOPKPOOL, DIFFPOOL, and SAGPOOL. All pooling methods are employed in the network framework introduced in Section 3.5 In addition, the same 10-fold cross validations from DGCNN are used for all pooling methods. We report the results in Table and the best results are shown in bold. Obviously, our method achieves the best performance on five of six datasets, and significantly outperforms all comparing pooling techniques. For the dataset EN- ZYMES, our obtained result is competitive since SAGPOOL. only slightly outperforms our proposed method by 0.34%. Such observations demonstrate the structural information in graphs is useful for graph pooling and the relationships between different nodes should be explicitly modeled.
4.4 STUDY COMPUTATIONAL COMPLEXITY
As mentioned in Section 3.4 our pro- posed STRUCTPOOL yields O(m
Table 3: The prediction accuracy with different iteration
number m.
i)re²) computational complexity. The complexity of DIFFPOOL is Ojjn') ) if assume it employs layers of GCNs to obtain the assignment matrix. In our ex- periments, is usually
Dataset
m m =
3
m
5
10
ENZYMES D&D
62.67
63.00
63.83
63.50
82.82
83.08
83.59
84.19
2 or which
PROTEINS
80.09
80.00
80.18
80.18
7

---

Published as a conference paper at ICLR 2020
much smaller than We conduct experiments to show how different iteration number affects the prediction accuracy and the results are reported in Table 3 Note that we employ the dense CRF form for all different m. We can observe that the performance generally increases with increasing, especially for large-scale dataset D&D. We also observe m = 5 is good trade-off between time complexity and prediction performance. Notably,
method can even outperform other approaches when m = 1. Furthermore, we evaluate the running time of our STRUCTPOOL and compare it with DIFFPOOL. For 500 graphs from large-scale dataset D&D, we set i j 3 and show the aver- aging time cost to perform pooling for each graph. The time cost for DIFFPOOL is 0.042 second, while our STRUCTPOOL takes 0.049 second, 0.053 second and 0.058 second for m 1, m 5 respectively. Even though our STRUCTPOOL has relatively higher computational cost, it is still reasonable and acceptable given its superior performance.
3,
4.5 EFFECTS OF TOPOLOGY INFORMATION
Next, we conduct experiments to show how the topology in-
Table 4:
The prediction accuracy using different A in
STRUCTPOOL.
formation A affects the predic- tion performance. We evaluate our STRUCTPOOL with different & values and report the results in Ta- ble 4 Note that when E is large enough, our STRUCTPOOL considers all pairwise relationships between all nodes, and it is equiva- lent to the dense CRF. For the datasets IMDB-M and PROTEINS, we can observe that the prediction accuracies are generally increasing with the increasing of É. With the increasing of l, more pairwise relationships are considered by the model, and hence it is reasonable to obtain better performance. In addition, for the dataset IMDB-B, the results remain similar with different f, and even é yields competitive performance with dense CRF It is possible that 1-hop pairwise relationships are enough to learn good embeddings for such graph types. Overall, dense CRF consistently produces promising results and is proper choice in practice.
Dataset
t=1
f= 5
t= 10
DENSE
IMDB-B
74.60
74.40
74.30
74.70
74.70
IMDB-M
51.53
51.67
52.00
51.96
52.47
PROTEINS
79.73
79.61
79.83
80.36
80.18
4.6 GRAPHI ISOMORPIISM NETWORKS WITH STRUCTPOOL
Recently, Graph Isomor- phism Networks (GINs)
Table 5: Comparisons with Graph Isomorphism Networks.
proposed and shown to be more powerful than traditional GNNs (Xu et al.] 2019). To demonstrate the effectiveness of our STRUCTPOOL. and show its generalizability, we build models based on GINs and evaluate their performance. Specifically, we employ GINs to learn node representations and perform one layer of the dense form of our STRUCTPOOL, followed by ID convolutional layers and fully-connected layers as the classifier. The results are reported in the Table 5 where we employ the same 10-fold splitting as GINs (Xu al., 2019) and the GIN results are taken from its released results. These five datasets include both bioinformatic data and social media data, and both small-scale data and large-scale data. Obviously, incorporating our proposed STRUCTPoOL. in GINs consistently and significantly improves the prediction performance. It leads to an average of 4.52% prediction accuracy improvement, which is promising.
Dataset
PTC
IMDB-B
MUTAG
COLLAB
IMDB-M
GINs
64.60
75.10
89.40
80.20
52.30
OURS
73.46
78.50
93.59
84.06
54.60
CONCLUSIONS
Graph pooling is an appealing way to learn good graph-level representations, and several advaned pooling techiques are proposed. However, none of existing graph pooling techniques explicitly considers the relationship between different nodes. We propose a novel graph pooling technique, known as STRUCTPOOL, which is developed based on the conditional random fields. We consider the graph pooling node clustering problem and employ the CRF to build relationships between the assignments of different nodes. In addition, we generalize our method by incorporating the graph topologiaal information so that our method can control the pairwise clique set in our CRFs. Finally,
8

---

Published as a conference paper at ICLR 2020
evaluate proposed STRUCTPOOL several benchmark datasets and our method can achieve new state-of-the-an results on five out six datasets.
ACKNOWLEDGEMENT
This work was supported in part by National Science Foundation grants DBI-1661289 and IIS- 1908198.
REFERENCES
James Atwood and Don Towsley. Diffusion-convolutiona. neural networks. In Advances in Neural Information Processing Systems, pp. 1993-2001, 2016.
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-pand path kernels on graphs. In Fifth IEEE international conference data mining (ICDM"03) pp. 8-pp. IEEE, 2005.
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(supp__1): i47-i56, 2005.
Lei Cai and Shuiwang Ji. A multi-scale approach for graph link prediction. In ThhrttyFFurth AAAI Conference on Artificial Intelligence, 2020.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4))771-783, 2003.
Hongchang Gao, Jian Pei, and Heng Huang. Conditional random field enhanced graph convolu- tional neural networks. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 276-284. ACM, 2019.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In International Conference on Machine Learning, pp. 2083-2092, 2019a.
Hongyang Gao and Shuiwang Ji. Graph representation learning via hard and channel-wise attention networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 2019b.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 1416-1424, 2018
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference Machine Learning-Vain Volume 70, pp. 12722 JMLR. org, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs.
In Advances in Neural Information Processing Systems, pp. 1024 1034,103,,100 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations, 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In Proceedings of the International Conference Learning Representations, 2017.
Philipp Krähenbühl and Vladlen Koltun. Efficient inference in fully connected erfs with gaussian edge potentials. In Advances in neural information processing systems, pp. 109-117, 2011.
John Lafferty, Andrew McCallum, and Fernando CN Percira. Conditional random fields: Probabilis- tic models for segmenting and labeling sequence data. In International conference on machine learning, pp. 282-289, 2001.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International Confer- on Machine Learning, pp. 3734-3743, 2019.

---

Published as a conference paper at ICLR 2020
Tengfei Ma, Cao Xiao, Junyuan Shang, and Jimeng Sun. CGNF: Conditional graph neural fields, 2019.
net http://www....eeoo.o..ororyaea/a
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net-
works for graphs. In International conference on machine learning, pp. 2014-2023, 2016.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In Proceedings of the International Conference on Learning Representations, 2017.
Meng Qu, Yoshua Bengio, and Jian Tang. GMNN: Graph Markov neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5241-5250, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Ef- ficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics, pp- 488-495, 2009.
Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters in convolutional neu- ral networks on graphs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3693-37000 3702, 2017.
Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin Riedmiller. Striving for simplicity: The all convolutional net. In Proceedings of the International Conference on Learning Representations, 2014.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. / ott.:///we....teooororooeea111aa
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence sequence for sets. In International Conference on Learning Representations, 2015.
Boris Weisfeiler and Andrei A Lehman. reduction of a graph to a canonical form and an algebra arising during this reduction. Maauhhno-Technicheskken Informatsia, 2(9):12-16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL hetps: //openzeview
Pinar Yanardag and SVN Vishwanathan. Deep graph kemnlss. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374. ACM, 2015a.
Pinar Yanardag and SVN Vishwanathan. A structural smoothing framework for robust graph com- parison. Advances in neural information processing systems, pp. 2134-2142, 2015b.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Advances in Neural Infor- mation Processing Systems, pp. 4800-48101 2018
Fisher Yu and Vladlen Koltun. Multi-scale context aggregation by dilated convolutions. In Proceed- ings of the International Conference on Learning Representations, 2016.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5175, 2018.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI, pp. 1438-4445, 2018.
Shuai Zheng. Sadeep Jayasumana, Bermardino Canner--arrdess, Vibhav Vineet, Zhizhong Su, Da- long Du, Chang Huang, and Philip HS Torr Conditional random fields recurrent neural net- works. In Proceedings of the IEEE international conference on computer vision, pp. 1529-1537, 2015.
10

---

Published as a conference paper at ICLR 2020
A APPENDIX
A.I DATASETS AND EXPERIMENTAL SETTINGS
Table 6: Statisties and properties of eight benchmark datasets.
Dataset
ENZYMES
D&D
COLLAB
PROTEINS
# of Edges (avg)
124.20
1431.3
2457.78
72.82
# of Nodes (avg)
32.63
284.32
74.49
39.06
# of Graphs
600
1178
5000 3
1113
# of Classes
6
2
2
Dataset
IMDB-B
IMDB-M
PTC
MUTAG
of Edges (avg)
96.53
65.94
14.69
19.79
# of Nodes (avg)
19.77
13.00
14.30
17.93
of Graphs
1000
1500
344
188
# of Classes
2
3
2
2
We report the statistics and properties of eight benchmark datasets in Supplementary Table For our STRUCTPOOL, we implement our models using Pytorch (Paszke et al. 2017] and conduct exper- iments one GeForce GTX 1080 Ti GPU. The model trained using Stochastic gradient descent (SGD) with the ADAM optimizer (Kingma & Ba 2014). For the models built on DGCNN (Zhang al. 2018) Section 4.2
4.5 we employ GCNs obtain the node features and the unary energy matrix. All experiments in these sections perform 10-fold cross validations and we report the averaging results. The 10-fold splitting exactly the same as DGCNN (Zhang et al., 2018), For non-linear function, we employ tanh for GCNs and relu for ID convolution layers. For the models built on GINs in Section 4.6 we employ GINs to learn node features and unary energy. Here the 10- fold splitting is exactly the same GINs. We employ relu for all layers the non-linear function. For all models, 1D convolutional layers and fully-connected layers are used after our STRUCTPOOL.. Hard clustering assignments employed in all experiments.
A.2 EFFECTS PAIRWISE ENERGY
Table 7: Comparison with the baseline which excludes pairwise energy.
Dataset
ENZYMES
D&D
COLLAB
PROTEINS
IMDB-B
IMDB-M M
BASELINE 60.83
81.30
70.58
78.18
72.40
50.13
OURS
63.83
84.19
74.22
80.36
74.70
52.47
We conduct experiments to show the importance the pairwise energy. If the pairwise energy is removed, the relations between different node assignments not explicitly considered. Then the method is similar to the DIFFPOOL. We compare our method with such baseline that removes the pairwise energy. Experimental results reported in Table 7 The network framework is the same as introduced in Section 3.3 and the same 10-fold cross validations from DGCNN are used. Obvi- ously, our proposed method consistently and significantly outperforms the baseline which excludes pairwise energy. It indicates the importance and effectiveness of incorporating pairwise energy and considering high-order relationships between different node assignments.
A.3 STUDY OF HIERARCHICAL NETWORK STRUCTURE
To demonstrate how the network depth and multiple pooling layers affects the prediction perfor- mance, we conduct experiments to evaluate different hierarchical network structures. We first define network block contains two GCN layers and one STRUCTPOOL. layer. Then compare three

---

Published as a conference paper at ICLR 2020
Table 8: Comparison with different hierarchical network structures.
Dataset
1 BLOCK
2 BLOCKS
3 BLOCKS
PROTEINS
79.73
77.42
74.95
D&D
81.87
83.59
81.63
different network settings: block with the final classifier, 2 blocks with the final classifier, and 3 blocks with the final classifier. The results are reported Table [ For the dataset Proteins, we observe that the network with block can obtain better performance than deeper networks. We believe the main reason is dataset Proteins a small-scale dataset with an average number of nodes equal 39.06. A relatively simpler network is powerful enough to learn its data distribution while stacking multiple GCN layers and pooling layers may lead to a serious overfitting problems. For the dataset D&D, the network with 2 blocks performs better than the one with block. Since D&D is relatively large scale, stacking 2 blocks increases the power of network and hence increases the performance. However, going very deep, e,g., stacking blocks, will cause the overfitting problem.
A.4 STUDY OF GRAPH POOLING RATE
Table 9: Comparison with different pooling rates.
0.1
r= 0.3
r= 0.5
r= 0.7
r= 0.9
k
91
160
241
331
503
Acc
80.77
81.53
81.53
81.97
80.68
We follow the DGCNN Zhang et al. 2018) to select the number of clusters Specifically, we use pooling rate E (0, 1) control K. Then & is set to integer so that r 100% of graphs have nodes less than this integer in the current dataset. As suggested in DGCNN, generally, r 0.9 proper choice for bioinformatics datasets and r 0.6 is good for social network datasets. In addition, we conduct experiments to show the performance with the respect to different values. We set r = 0.1, 0.3, 0.5, 0.7, 0.9 to evaluate the performance on large-scale social network dataset D&D. The average number of nodes in dataset D&D is 284.32 and the maximum number of nodes 5748. The results are reported in Table 9 where the first row shows different pooling rates, the second row reports the corresponding k values and the final row shows the results. For simplicity, we employ the network structure with block and a final classifier (as defined in Section AA.3). We can observe that the performance drops when k is relatively large or small. In addition, the model can obtain competitive performance when r is set to a proper range, for example, r E [0.3. 0.7] for dataset D&D.
12


Reviews:
[{"review_id": "SylGq_LxqB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors here introduces a novel  graph pooling technique called StructPool that uses the underlying graph’s structural information to behave as a node clustering algorithm and learns a node clustering matrix.\n\nGraph level classification requires learning good graph level representation, especially for  aggregating low level information for high . Recent work in pooling does not take advantage of important structural information of the relationship between different  nodes. Here, the authors formulate  graph pooling as a structured prediction problem, control clique set in the CRFs and use mean filed approximation to calculate assignments. \n\nA cluster assignment matrix assigns each node in the original graph to a cluster in the new graph. The assignment not only depends on the node features but also on the cluster assignment of the other nodes. The authors therefore draw connection with finding the optimal assignment to minimizing the Gibbs energy. The authors propose to learn clustering assignment via CRF conditioned on the global feature representation of the nodes.\n\nThe unary potentials of the cliques are computed used the GCN to measure energy of each node. The novelty in accommodating topology information is in using l hop connectivity based on adjacency A to define pairwise cliques thus building pairwise relationship between pairs of nodes thus allowing the Gibbs energy formulation of the cluster assignment thereby using GCN to also compute this pairwise energy. \n\nI have  a few questions as below:\nI think the authors can better elucidate the motivation for using  the attention matrix over Gaussian kernels to measure pairwise energy in section 3.3; an  empirical experiment for drawing comparison wrt to the computational time and number of feature dimensions on a toy problem seems important. \nHow is the computation  of the unary potential and pairwise energy influenced by the connectivity of the graph G for the datasets considered? It would be interesting to see how the pairwise energy, unary energy varies over different layers of GCNs. \nFurther, how is the cluster assignment affected by the l-hop connectivity? \nIs there a notion of the minimum value of ‘k’ in the context of convergence?\nWhat happens in case of very different graph features, or structural assumptions where the cliques are not enforced? \nIs there a notion of how the method performs on datasets with a high percentage of isomorphism bias: repeating instances or repeating instances with different labels?\nIt will be interesting to see a discussion on how the performance varies with respect to the depth of the overall architecture,  positioning of the structpool and some results on how effective they are on  hierarchical features and multiple pooling ops as in architectures such as Graph UNet.\nAvoid repetition in 2.2 Related work section and in other sections throughout. Otherwise, the paper is rather well written and has clarity.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJgUtBvZqS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a new graph pooling method by learning the node assignments from a CRF based structure prediction formulation. Different from existing pooling methods, the proposed model explicitly captures high-order structural relationships between nodes via a CRF, and the pairwise energy in the CRF is defined by a $l$-hop connection instead of the original neighborhoods. The paper is written clearly, and the experimental results are good. The sensitivity analysis is also complete.\n\nIntegrating CRFs with GNNs for node classification is not new ([1][2][3]), but this paper extended energy definition to capture high-order connections and use it for a new subsequent task: graph pooling. It is interesting and novel, but maybe not very significant. (BTW, it is better to add the related works which combined CRF and GNNs, considering the close connection to this paper.)\n\nThe sensitivity analysis in the paper is very useful, but it lacks one important ablation study. To justify the usefulness of CRFs instead of other clustering methods for node assignment, I think there should be a baseline which removes the pairwise energy and just use the unary energy for node clustering. Moreover, the paper may also need to compare with a more recent state-of-the-art pooling model SAGPool [4].\n\n\n[1]Gao, H., Pei, J., & Huang, H. (2019). Conditional Random Field Enhanced Graph Convolutional Neural Networks. In KDD2019.\n[2]Ma, T., Xiao, C., Shang, J. and Sun, J., (2018). CGNF: Conditional Graph Neural Fields. https://openreview.net/forum?id=ryxMX2R9YQ\n[3]Qu, M., Bengio, Y., & Tang, J. (2019). GMNN: Graph Markov Neural Networks. In ICML2019.\n[4]Lee, J., Lee, I., & Kang, J. (2019). Self-Attention Graph Pooling. In ICML 2019.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1lHXXRhtH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Strength:\n-- An interesting idea to use CRF idea to cluster the nodes on a graph for pooling purpose\n-- The paper is well written and easy to follow\n--  On a few datasets and task, the proposed method works pretty well\n\nWeakness:\n-- The computational complexity of the proposed algorithm is on(n^3), which is too expensive \n\nThis paper studied to use CRF to define the cluster assignment of the nodes  for graph pooling, which model the dependency of the cluster assignments between the nodes. Experiments on a few data sets and experiments prove the effectiveness of the proposed approach over competitive baselines. \n\nAlthough the proposed approach is interesting and works well on different datasets,  one strong concern I have is the high computational complexity of the algorithm, which is as high as o(n^3) (n is the number of nodes). This limits the applicability of the algorithm to large graphs.  Besides, I also have the following questions:\n(1) In the experiments, I assume one CRF pooling layer is used. What would be the results if multiple layers are used?\n\n(2) How did you select the number of clusters K? How would the performance change w.r.t. different K?\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposed an operation called StructPool for graph-pooling by treating it as node clustering problem (assigning a label from 1..k to each node) and then use a pairwise CRF structure to jointly infer these labels. The reviewers all think that this is a well-written paper, and the experimental results are adequate to back up the claim that StructPool offers advantage over other graph-pooling operations. Even though the idea of the presented method is simple and it does add more (albeit by a constant factor) to the computational burden of graph neural network, I think this would make a valuable addition to the literature.
Decision: Accept (Poster)