STRUCTPOOL: STRUCTURED GRAPH POOLING VIA CONDITIONAL RANDOM FIELDS
Year: 2020

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 the 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.

heading: 1 INTRODUCTION
text: Graph neural networks have achieved the state-of-the-art results for multiple graph tasks, such as node classification (Veličković et al., 2018; Gao & Ji, 2019b; Gao et al., 2018) and link prediction (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 learning good graph-level representations. Since pooling operations are shown to be effective in many image and NLP tasks, it is natural to 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, 2017). However, these trivial global pooling operations may lose important features and ignore structural information. Furthermore, global pooling are not hierarchical so that we cannot apply them where multiple pooling operations are required, such as Graph UNet (Gao & Ji, 2019a). Several advanced graph pooling methods, such as SORTPOOL (Zhang et al., 2018), TOPKPOOL (Gao & Ji, 2019a), DIFFPOOL (Ying et al., 2018), and SAGPOOL (Lee et al., 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 ignore important structural information. We argue that such information is important and should be explicitly captured in graph pooling.
In this work, we propose a novel graph pooling technique, known as the STRUCTPOOL, that formulates 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 a node in the new graph after pooling. Intuitively, two nodes with similar features should have a higher probability of being assigned to the same cluster. Hence, the assignment of a 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, we generalize our method by incorporating the graph topological information so that our method can control the clique set in our CRFs. We employ the mean field approximation to compute the assignments and describe how to incorporate it in graph networks. Then the networks can be
trained in an 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.

heading: 2 BACKGROUND AND RELATED WORK

heading: 2.1 GRAPH CONVOLUTIONAL NETWORKS
text: A 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 ∈ {0, 1}n×n, and the node features can be represented as X ∈ Rn×c assuming each node has a c-dimensional feature vector. Deep graph neural networks (GNNs) learn feature representations for different nodes using these matrices (Gilmer et al., 2017). Several approaches are proposed 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; Veličković et al., 2018). In each step, the representation of 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 (Kipf & Welling, 2017). The graph convolution operation is formally defined as:
Xi+1 = f(D − 12 ÂD− 1 2XiPi), (1)
where Â = A + I is used to add self-loops to the adjacency matrix, D denotes the diagonal node degree matrix to normalize Â, Xi ∈ Rn×ci are the node features after ith graph convolution layer, Pi ∈ Rci×ci+1 is a trainable matrix to perform feature transformation, and f(·) denotes a non-linear activation function. Then Xi ∈ Rn×ci is transformed to Xi+1 ∈ Rn×ci+1 where the number of nodes remains the same. A similar form of GCNs proposed in (Zhang et al., 2018) can be expressed as:
Xi+1 = f(D −1ÂXiPi). (2)
It differs from the GCNs in Equation (1) by performing different normalization and is a theoretically closer approximation to the Weisfeiler-Lehman algorithm (Weisfeiler & Lehman, 1968). Hence, in our models, we use the latter version of GCNs in Equation (2).

heading: 2.2 GRAPH POOLING
text: 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 & Ji, 2019a), and SAGPOOL (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 representations using GCNs, which indicates the importance of different nodes. Then only the top k 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 et al., 2018) treats the graph pooling as a node clustering problem. A cluster of nodes from the original 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 on 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 a novel structured graph pooling technique, known as the STRUCTPOOL, for effectively learning high-level graph representations. Different from existing 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.

heading: 2.3 INTEGRATING CRFS WITH GNNS
text: Recent work (Gao et al., 2019; Qu et al., 2019; Ma et al., 2019) investigates how to combine CRFs with GNNs. The CGNF (Ma 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
via dynamic programming. In addition, the GMNN (Qu et al., 2019) focuses on semi-supervised object classification tasks and models the joint distribution of object labels conditioned on object attributes using CRFs. It proposes a pseudolikelihood variational EM framework for model learning and inference. Recent work (Gao et al., 2019) integrates CRFs with GNNs by proposing a CRF layer to encourage similar nodes to have similar hidden features so 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 in 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.

heading: 3 STRUCTURED GRAPH POOLING

heading: 3.1 GRAPH POOLING VIA NODE CLUSTERING
text: 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; Springenberg et al., 2014), local pooling operations cannot be directly applied to graph tasks. The reason is there is 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 n nodes can be represented by a feature matrix X ∈ Rn×c and an adjacent matrix A ∈ {0, 1}n×n. 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 k nodes. The representation matrices of G̃ are denoted as X̃ ∈ Rk×c̃ and Ã ∈ {0, 1}k×k. The goal of graph pooling is to learn relationships between X , A and X̃ , Ã. In this work, we consider graph pooling via node clustering. In particular, the nodes of the original graph G are assigned to k 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 ∈ Rn×k. For hard assignments, mi,j ∈ {0, 1} denotes if node i in graph G belongs to cluster j. For soft assignments, mi,j ∈ [0, 1] denotes the probability that node i in graph G belongs to cluster j and ∑ j mi,j = 1.
Then the new graph G̃ can be computed as
X̃ = MTX, Ã = g(MTAM), (3)
where g(·) is a function that g(ãi,j) = 1 if ãi,j > 0 and g(ãi,j) = 0 otherwise.

heading: 3.2 LEARNING CLUSTERING ASSIGNMENTS VIA CONDITIONAL RANDOM FIELDS
text: Intuitively, node features describe the properties of different nodes. Then nodes with similar features should have a 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, we propose a novel structured graph pooling technique, known as 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 as a conditional random field (CRF) problem. The CRFs model a set of random variables with a Markov Random Field (MRF), conditioned on a global observation (Lafferty et al., 2001). We formally define Y = {Y1, · · · , Yn} as a random field where Yi ∈ {1, · · · , k} is a random variable. Each Yi 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 as
P (Y |X) = 1 Z(X) exp − ∑ c∈CG′ ψc(Yc|X)  , (4) where c denotes a clique, CG′ is a set of cliques in G′, Z(X) is the partition function, and ψc(·) is a potential function induced by c (Krähenbühl & Koltun, 2011; Lafferty et al., 2001). Then the Gibbs
energy function for an assignment y = {y1, · · · , yn} for all variables can be written as E(y|X) = ∑
c∈CG′
ψc(yc|X). (5)
Finding the optimal assignment is equivalent to maximizing P (Y |X), which can also be interpreted as minimizing the Gibbs energy.

heading: 3.3 GIBBS ENERGY WITH TOPOLOGY INFORMATION
text: Now we define the clique set CG′ in G′. Similar to the existing CRF model (Krähenbühl & Koltun, 2011), we include all unary cliques in CG′ since we need to 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 `-hop connectivity based on A to define the pairwise cliques, which builds pairwise relationships between different nodes. Let A` ∈ {0, 1}n×n represent the `-hop connectivity of graph G where a`i,j = 1 indicates node i and node j are reachable in G within ` hops. Then we include all pairwise cliques (i, j) in CG′ if a`i,j = 1. Altogether, the Gibbs energy for a cluster assignment y can be written as
E(y) = ∑ i ψu(yi) + ∑ i 6=j ψp(yi, yj)a ` i,j , (6)
where ψu(yi) represents the unary energy for node i to be assigned to cluster yi. In addition, ψp(yi, yj) is the pairwise energy, which indicates the energy of assigning node i, j to cluster yi, 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 ` is 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, we employ multiple graph convolution layers to obtain the unary energy Ψu ∈ Rn×k. Existing work on image tasks (Krähenbühl & Koltun, 2011) proposes to employ Gaussian kernels to measure the pairwise energy. However, due to computational inefficiency, we cannot directly apply it to our CRF model. The pairwise energy proposed in (Krähenbühl & Koltun, 2011) can be written as
ψp(yi, yj) = µ(yi, yj) K∑ m=1 w(m)k(m)(xi, xj), (7)
where k(m)(·, ·) represents the mth Gaussian kernel, xi is the feature vector for node i in X , w(m) denotes learnable weights, and µ(yi, yj) is a compatibility function that models the compatibility
Algorithm 1 STRUCTPOOL 1: Given a graph G with n nodes represented by X ∈ Rn×c and A ∈ {0, 1}n×n, the goal is to
obtain G̃ with k nodes that X̃ ∈ Rk×c̃ and Ã ∈ {0, 1}k×k. The `-hop connectivity matrix A` can be easily obtained from A.
2: Perform GCNs to obtain unary energy matrix Ψu ∈ Rn×k. 3: Initialize that Q(i, j) = 1Zi exp (Ψu(i, j)) for all 0 ≤ i ≤ n and 0 ≤ j ≤ k. 4: while not converged do 5: Calculate attention map W that wi,j =
xTi xj∑ m6=i x T i xm a`i,j for all i 6= j and 0 ≤ i, j ≤ n.
6: Message passing that Q̃(i, j) = ∑
m6=i wi,mQ(m, j). 7: Compatibility transform that Q̂(i, j) = ∑ m µ(m, j)Q̃(i,m). 8: Local update that Q̄(i, j) = Ψu(i, j)− Q̂(i, j). 9: Perform normalization that Q(i, j) = 1Zi exp ( Q̄(i, j) ) for all i 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̃ = MTX, Ã = g(MTAM).
between different assignment pairs. However, it is computationally inefficient to accurately compute the outputs of Gaussian kernels, especially for graph data when the feature vectors are highdimensional. 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 feature vectors but with a significantly less computational cost. Specifically, each feature vector xi is attended to any other feature vector xj if the pair (i, j) is existing in clique set CG′ . Hence, the pairwise energy can be obtained by
ψp(yi, yj) = µ(yi, yj) xTi xj∑ k 6=i x T i xk , (8)
It can be efficiently computed by matrix multiplication and normalization. Minimizing the Gibbs energy in Equation (6) results in the most probable cluster assignments for a given graph G. However, such minimization is intractable, and hence a mean field approximation is proposed (Krähenbühl & Koltun, 2011), which is an iterative updating algorithm. We follow the mean-field approximation to obtain the most probable cluster assignments. Altogether, the steps of our proposed STRUCTPOOL are shown in Algorithm 1. 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 1) are equivalent to softmax operations. All other steps can be computed by matrix computations. It is noteworthy that the compatibility function µ(yi, yj) can be implemented as a trainable matrixN ∈ Rk×k, and automatically learned during training. Hence, no prior domain knowledge is required for designing the compatibility function. We illustrate our proposed STRUCTPOOL in Figure 1 where we perform STRUCTPOOL on a graph G with 6 nodes, and obtain a new graph G̃ with 4 nodes.

heading: 3.4 COMPUTATIONAL COMPLEXITY ANALYSIS
text: We theoretically analyze the computational efficiency of our proposed STRUCTPOOL. Since computational efficiency is especially important for large-scale graph datasets, we assume that n > k, c, c̃. The computational complexity of one GCN layer is O(n3 + n2c + ncc̃) ≈ O(n3). Assuming we employ i layers of GCNs to obtain the unary energy, its computational cost is O(in3). Assuming there are m iterations in our updating algorithm, the computational complexity is O(m(n2c + n2k + nk2)) ≈ O(mn3). The final step for computing Ã and X̃ takes O(nkc + n2k + nk2) ≈ O(n3) computational complexity. Altogether, the complexity STRUCTPOOL is O((m+ i)n3), which is close to the complexity of stacking m+ i layers of GCNs.

heading: 3.5 DEEP GRAPH NETWORKS FOR GRAPH CLASSIFICATION
text: 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 a similar pipeline that first produces node representations using GNNs, then performs pooling operations to obtain high-level representations, and finally employs fully-connected layers to perform classification. Note that the high-level representations can be either a vector or a group of k vectors. For a set of graphs with different node numbers, with a pre-defined k, our proposed STRUCTPOOL can produce k vectors for each graphs. Hence, our method can be easily generalized and coupled to any deep graph classification model. Specially, our model for graph classification is developed based on DGCNN (Zhang et al., 2018). Given any input graph, our model first employs several layers of GCNs (Equation (2)) to aggregate features from neighbors and learn representations for nodes. Next, we perform one STRUCTPOOL layer to obtain k vectors for each graph. Finally, 1D convolutional layers and fully-connected layers are used to classify the graph.

heading: 4 EXPERIMENTAL STUDIES

heading: 4.1 DATASETS AND EXPERIMENTAL SETTINGS
text: We evaluate our proposed STRUCTPOOL on eight benchmark datasets, including five bioinformatics protein datasets: ENZYMES, PTC, MUTAG, PROTEINS (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 6. Please see the Supplementary Section A for experimental settings.
We compare our method with several state-of-the-art deep GNN methods. PATCHYSAN (Niepert et al., 2016) learns node representations and a canonical node ordering to perform classification. DCNN (Atwood & Towsley, 2016) learns multi-scale substructure features by diffusion graph convolutions 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 (Simonovsky & Komodakis, 2017) performs GCNs conditioning on both node features and edge information 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 a pooling strategy named SORTPOOL which sorts all nodes
by learning and selects the first k nodes to form a new graph. DIFFPOOL (Ying et al., 2018) is built based on GRAPHSAGE architecture but with their proposed differentiable pooling. Note that for most 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 WeisfeilerLehman subtree kernel (WL) (Weisfeiler & Lehman, 1968).

heading: 4.2 CLASSIFICATION RESULTS
text: We evaluate our proposed method on six benchmark datasets and compare with several state-of-theart approaches. The results are reported in Table 1 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). We can observe that our STRUCTPOOL obtains the best performance on 5 out of 6 benchmark datasets. For these 5 datasets, the classification results of our method are significantly better than all comparing methods, including advanced models DGCNN and DIFFPOOL. Notably, our model outperforms the second-best performance by an average of 3.58% on these 5 datasets. In addition, the graph kernel method WL obtains the best performance on COLLAB dataset and none of these deep models can achieve similar performance. Our model can obtain competitive performance compared with the second best model. This is because many graphs in COLLAB only have simple structures and deep models may be too complex to capture them.

heading: 4.3 COMPARISONS OF DIFFERENT POOLING METHODS
text: To demonstrate the effectiveness of our 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 2 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 ENZYMES, 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.

heading: 4.4 STUDY OF COMPUTATIONAL COMPLEXITY
text: As mentioned in Section 3.4, our proposed STRUCTPOOL yields O((m + i)n3) computational complexity. The complexity of DIFFPOOL is O(jn3) if we assume it employs j layers of GCNs to obtain the assignment matrix. In our experiments, i is usually set to 2 or 3 which
is much smaller than n. We conduct experiments to show how different iteration number m affects the prediction accuracy and the results are reported in Table 3. Note that we employ the dense CRF form for all differentm. We can observe that the performance generally increases withm increasing, especially for large-scale dataset D&D. We also observe m = 5 is a good trade-off between time complexity and prediction performance. Notably, our 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 averaging 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 = 3, m = 5 respectively. Even though our STRUCTPOOL has a relatively higher computational cost, it is still reasonable and acceptable given its superior performance.

heading: 4.5 EFFECTS OF TOPOLOGY INFORMATION
text: Next, we conduct experiments to show how the topology information A` affects the prediction performance. We evaluate our STRUCTPOOL with different ` values and report the results in Table 4. Note that when ` is large
enough, our STRUCTPOOL considers all pairwise relationships between all nodes, and it is equivalent 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 `, 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 `, and even ` = 1 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 a proper choice in practice.

heading: 4.6 GRAPH ISOMORPHISM NETWORKS WITH STRUCTPOOL
text: Recently, Graph Isomorphism Networks (GINs) are 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 1D 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 et 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.

heading: 5 CONCLUSIONS
text: 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 as a 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 topological information so that our method can control the pairwise clique set in our CRFs. Finally,
we evaluate our proposed STRUCTPOOL on several benchmark datasets and our method can achieve new state-of-the-art results on five out of six datasets.

heading: ACKNOWLEDGEMENT
text: This work was supported in part by National Science Foundation grants DBI-1661289 and IIS1908198.

heading: A APPENDIX
text: A.1 DATASETS AND EXPERIMENTAL SETTINGS
We report the statistics and properties of eight benchmark datasets in Supplementary Table 6. For our STRUCTPOOL, we implement our models using Pytorch (Paszke et al., 2017) and conduct experiments on one GeForce GTX 1080 Ti GPU. The model is trained using Stochastic gradient descent (SGD) with the ADAM optimizer (Kingma & Ba, 2014). For the models built on DGCNN (Zhang et al., 2018) in Section 4.2, 4.3, 4.4, 4.5, we employ GCNs to 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 is exactly the same as DGCNN (Zhang et al., 2018). For the non-linear function, we employ tanh for GCNs and relu for 1D 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 as GINs. We employ relu for all layers as the non-linear function. For all models, 1D convolutional layers and fully-connected layers are used after our STRUCTPOOL. Hard clustering assignments are employed in all experiments.
A.2 EFFECTS OF PAIRWISE ENERGY
We conduct experiments to show the importance of the pairwise energy. If the pairwise energy is removed, the relations between different node assignments are not explicitly considered. Then the method is similar to the DIFFPOOL. We compare our method with such a baseline that removes the pairwise energy. Experimental results are reported in Table 7. The network framework is the same as introduced in Section 3.5 and the same 10-fold cross validations from DGCNN are used. Obviously, 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 performance, we conduct experiments to evaluate different hierarchical network structures. We first define a network block contains two GCN layers and one STRUCTPOOL layer. Then we compare three
different network settings: 1 block with the final classifier, 2 blocks with the final classifier, and 3 blocks with the final classifier. The results are reported in Table 8. For the dataset Proteins, we observe that the network with one block can obtain better performance than deeper networks. We believe the main reason is dataset Proteins is a small-scale dataset with an average number of nodes equal to 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 1 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 3 blocks, will cause the overfitting problem.
A.4 STUDY OF GRAPH POOLING RATE
We follow the DGCNN (Zhang et al., 2018) to select the number of clusters k. Specifically, we use a pooling rate r ∈ (0, 1) to control k. Then k is set to an 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 is a 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 r values. We set r = 0.1, 0.3, 0.5, 0.7, 0.9 to evaluate the performance on a 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 is 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 1 block and a final classifier (as defined in Section A.3). We can observe that the performance drops when r, 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 ∈ [0.3, 0.7] for dataset D&D.

Review summaries:
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.