Title: STRUCTPOOL: STRUCTURED GRAPH POOLING VIA CONDITIONAL RANDOM FIELDS

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.

1. INTRODUCTION:

Graph neural networks have achieved the state-of-the-art results for multiple graph tasks, such as node classification (Veličković 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 U-Net (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.

2. BACKGROUND AND RELATED WORK:



2.1. GRAPH CONVOLUTIONAL NETWORKS:

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 ∈ R n×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; Veličković 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:

EQUATION

where Â = A + I is used to add self-loops to the adjacency matrix, D denotes the diagonal node degree matrix to normalize Â, X i ∈ R n×ci are the node features after i th graph convolution layer, P i ∈ R ci×ci+1 is a trainable matrix to perform feature transformation, and f (•) denotes a non-linear activation function.

Then X i ∈ R n×ci is transformed to X i+1 ∈ R n×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:

X i+1 = f (D -1 ÂX i P i ).

(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).

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 & Ji, 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 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.

2.3. INTEGRATING CRFS WITH GNNS:

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.

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; 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 ∈ R n×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 ∈ R k×c and Ã ∈ {0, 1} k×k .

The goal of graph pooling is to learn relationships between X, A and X, Ã. 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 ∈ R n×k . For hard assignments, m i,j ∈ {0, 1} denotes if node i in graph G belongs to cluster j. For soft assignments, m i,j ∈ [0, 1] denotes the probability that node i in graph G belongs to cluster j and j m i,j = 1.

Then the new graph G can be computed as

EQUATION

where g(•) is a function that g(ã i,j ) = 1 if ãi,j > 0 and g(ã i,j ) = 0 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 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 = {Y 1 , • • • , Y n } as a random field where Y i ∈ {1, • • • , k} is a random variable.

Each Y i 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

EQUATION

where c denotes a clique, C G is a set of cliques in G , Z(X) is the partition function, and ψ c (•) is a potential function induced by c (Krähenbühl & Koltun, 2011; Lafferty et al., 2001) . Then the Gibbs The unary energy matrix can be obtained by multiple GCN layers using X and A. The pairwise energy is measured by attention matrix using node feature X 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 Ã.

energy function for an assignment y = {y 1 , • • • , y n } for all variables can be written as

EQUATION

Finding the optimal assignment is equivalent to maximizing P (Y |X), which can also be interpreted as minimizing the Gibbs energy.

3.3. GIBBS ENERGY WITH TOPOLOGY INFORMATION:

Now we define the clique set C G in G . Similar to the existing CRF model (Krähenbühl & Koltun, 2011) , we include all unary cliques in C G 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 C G if a i,j = 1. Altogether, the Gibbs energy for a cluster assignment y can be written as

EQUATION

where ψ u (y i ) represents the unary energy for node i to be assigned to cluster y i . In addition, ψ p (y i , y j ) is the pairwise energy, which indicates the energy of assigning node i, j to cluster y i , y j 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 ∈ R n×k . Existing work on image tasks (Krähenbü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 (Krähenbühl & Koltun, 2011) can be written as

EQUATION

where k (m) (•, •) represents the m th Gaussian kernel, x i is the feature vector for node i in X, w (m) denotes learnable weights, and µ(y i , y j ) is a compatibility function that models the compatibility Algorithm 1 STRUCTPOOL 1: Given a graph G with n nodes represented by X ∈ R n×c and A ∈ {0, 1} n×n , the goal is to obtain G with k nodes that X ∈ R k×c and Ã ∈ {0, 1} k×k . The -hop connectivity matrix A can be easily obtained from A. 2: Perform GCNs to obtain unary energy matrix

Ψ u ∈ R n×k . 3: Initialize that Q(i, j) = 1

Zi exp (Ψ u (i, j)) for all 0 ≤ i ≤ n and 0 ≤ j ≤ k. 4: while not converged do 5:

Calculate attention map W that w i,j =

x T i xj m =i x T i xm a i,j for all i = j and 0 ≤ i, j ≤ n.

6: Message passing that Q(i, j) = m =i w i,m Q(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) = 1

Zi 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 = M T X, Ã = g(M T AM ).

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 x i is attended to any other feature vector x j if the pair (i, j) is existing in clique set C G . Hence, the pairwise energy can be obtained by ψ p (y i , y j ) = µ(y i , y j )

EQUATION

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 (Krähenbü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 STRUCT-POOL 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 µ(y i , y j ) can be implemented as a trainable matrix N ∈ R k×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.

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 n > k, c, c. The computational complexity of one GCN layer is O(n 3 + n 2 c + ncc) ≈ O(n 3 ).

Assuming we employ i layers of GCNs to obtain the unary energy, its computational cost is O(in 3 ). Assuming there are m iterations in our updating algorithm, the computational complexity is O(m(n 2 c + n 2 k + nk 2 )) ≈ O(mn 3 ). The final step for computing Ã and X takes O(nkc + n 2 k + nk 2 ) ≈ O(n 3 ) computational complexity. Altogether, the complexity STRUCT-POOL is O((m + i)n 3 ), which is close to the complexity of stacking m + i layers of GCNs. 

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

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, 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 (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 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-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.

4.3. COMPARISONS OF DIFFERENT POOLING METHODS:

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 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. As mentioned in Section 3.4, our proposed STRUCTPOOL yields O((m + i)n 3 ) computational complexity. The complexity of DIFFPOOL is O(jn 3 ) 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 different m. We can observe that the performance generally increases with m 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. 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.

4.4. STUDY OF COMPUTATIONAL COMPLEXITY:



4.5. EFFECTS OF TOPOLOGY INFORMATION:

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

4.6. GRAPH ISOMORPHISM NETWORKS WITH STRUCTPOOL:



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

:



Figures and Tables:

Figure1: Illustrations of our proposed STRUCTPOOL. Given a graph with 6 nodes, the color of each node represents its features. We perform graph pooling to obtain a new graph with k = 4 nodes. The unary energy matrix can be obtained by multiple GCN layers using X and A. The pairwise energy is measured by attention matrix using node feature X 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 Ã.

Classification results for six benchmark datasets. Note that none 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 too complex to capture them.

Table content: <table><tr><td>Method</td><td/><td/><td colspan="2">Dataset</td><td/><td/></tr><tr><td/><td colspan="6">ENZYMES D&amp;D COLLAB PROTEINS IMDB-B IMDB-M</td></tr><tr><td>GRAPHLET</td><td>41.03</td><td>74.85</td><td>64.66</td><td>72.91</td><td>-</td><td>-</td></tr><tr><td>SHORTEST-PATH</td><td>42.32</td><td>78.86</td><td>59.10</td><td>76.43</td><td>-</td><td>-</td></tr><tr><td>WL</td><td>53.43</td><td>78.34</td><td>78.61</td><td>74.68</td><td>-</td><td>-</td></tr><tr><td>PATCHYSAN</td><td>-</td><td>76.27</td><td>72.60</td><td>75.00</td><td>71.00</td><td>45.23</td></tr><tr><td>DCNN</td><td>-</td><td>58.09</td><td>52.11</td><td>61.29</td><td>49.06</td><td>33.49</td></tr><tr><td>DGK</td><td>-</td><td>-</td><td>73.09</td><td>71.68</td><td>66.96</td><td>44.55</td></tr><tr><td>ECC</td><td>53.50</td><td>72.54</td><td>67.79</td><td>72.65</td><td>-</td><td>-</td></tr><tr><td>GRAPHSAGE</td><td>54.25</td><td>75.42</td><td>68.25</td><td>70.48</td><td>-</td><td>-</td></tr><tr><td>SET2SET</td><td>60.15</td><td>78.12</td><td>71.75</td><td>74.29</td><td>-</td><td>-</td></tr><tr><td>DGCNN</td><td>57.12</td><td>79.37</td><td>73.76</td><td>75.54</td><td>70.03</td><td>47.83</td></tr><tr><td>DIFFPOOL</td><td>62.53</td><td>80.64</td><td>75.48</td><td>76.25</td><td>-</td><td>-</td></tr><tr><td>STRUCTPOOL</td><td>63.83</td><td>84.19</td><td>74.22</td><td>80.36</td><td>74.70</td><td>52.47</td></tr></table>

Comparisons between different pooling techniques under the same framework.

Table content: <table><tr><td>Method</td><td/><td/><td colspan="2">Dataset</td><td/><td/></tr><tr><td/><td colspan="6">ENZYMES D&amp;D COLLAB PROTEINS IMDB-B IMDB-M</td></tr><tr><td>SUM POOL</td><td>47.33</td><td>78.72</td><td>69.45</td><td>76.26</td><td>51.69</td><td>42.76</td></tr><tr><td>SORTPOOL</td><td>52.83</td><td>80.60</td><td>73.92</td><td>76.83</td><td>70.00</td><td>46.26</td></tr><tr><td>TOPK POOL</td><td>53.67</td><td>81.71</td><td>73.34</td><td>77.47</td><td>72.80</td><td>49.00</td></tr><tr><td>DIFFPOOL</td><td>60.33</td><td>80.94</td><td>71.78</td><td>77.74</td><td>72.40</td><td>50.13</td></tr><tr><td>SAGPOOL</td><td>64.17</td><td>81.03</td><td>73.28</td><td>78.82</td><td>73.40</td><td>51.13</td></tr><tr><td>STRUCTPOOL</td><td>63.83</td><td>84.19</td><td>74.22</td><td>80.36</td><td>74.70</td><td>52.47</td></tr><tr><td colspan="6">by learning and selects the first k nodes to form a new graph. DIFFPOOL</td><td/></tr></table>

The prediction accuracy with different iteration number m.

Table content: <table><tr><td>Dataset</td><td colspan="4">m = 1 m = 3 m = 5 m = 10</td></tr><tr><td colspan="2">ENZYMES 62.67</td><td>63.00</td><td>63.83</td><td>63.50</td></tr><tr><td>D&amp;D</td><td>82.82</td><td>83.08</td><td>83.59</td><td>84.19</td></tr><tr><td colspan="2">PROTEINS 80.09</td><td>80.00</td><td>80.18</td><td>80.18</td></tr></table>

The prediction accuracy using different A in STRUCTPOOL.

Table content: <table><tr><td>Next, we conduct experiments</td><td/><td/></tr><tr><td>to show how the topology in-</td><td/><td/></tr><tr><td>formation A affects the predic-tion performance. We evaluate our STRUCTPOOL with different values and report the results in Ta-ble</td><td>Dataset IMDB-B IMDB-M PROTEINS 79.73 79.61 79.83 = 1 = 5 = 10 74.60 74.40 74.30 51.53 51.67 52.00</td><td>= 15 DENSE 74.70 74.70 51.96 52.47 80.36 80.18</td></tr></table>

Comparisons with Graph Isomorphism Networks.

Table content: <table><tr><td colspan="6">Dataset PTC IMDB-B MUTAG COLLAB IMDB-M</td></tr><tr><td>GINS</td><td>64.60</td><td>75.10</td><td>89.40</td><td>80.20</td><td>52.30</td></tr><tr><td>OURS</td><td>73.46</td><td>78.50</td><td>93.59</td><td>84.06</td><td>54.60</td></tr></table>

Comparison with different hierarchical network structures. block with the final classifier, 2 blocks with the final classifier, and 3 blocks with the final classifier. The results are reported in Table

Table content: <table><tr><td>Dataset</td><td colspan="3">1 BLOCK 2 BLOCKS 3 BLOCKS</td></tr><tr><td>PROTEINS</td><td>79.73</td><td>77.42</td><td>74.95</td></tr><tr><td>D&amp;D</td><td>81.87</td><td>83.59</td><td>81.63</td></tr><tr><td>different network settings: 1</td><td/><td/><td/></tr></table>

Comparison with different pooling rates. r = 0.1 r = 0.3 r = 0.5 r = 0.7 r = 0.9

Table content: <table><tr><td>k</td><td>91</td><td>160</td><td>241</td><td>331</td><td>503</td></tr><tr><td>ACC</td><td>80.77</td><td>81.53</td><td>81.53</td><td>81.97</td><td>80.68</td></tr></table>

Peer review (iclr2020):
Strength: -- An interesting idea to use CRF idea to cluster the nodes on a graph for pooling purpose -- The paper is well written and easy to follow -- On a few datasets and task, the proposed method works pretty well Weakness: -- The computational complexity of the proposed algorithm is on(n^3), which is too expensive This 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. Although 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: (1) In the experiments, I assume one CRF pooling layer is used. What would be the results if multiple layers are used? (2) How did you select the number of clusters K? How would the performance change w.r.t. different K?