MxPool: Multiplex Pooling for Hierarchical Graph Representation Learning
Authors: Yanyan Liang
Yanfeng Zhang
Fangjing Wang
Qian Xu
Venue:  (2020)
Keywords: GNN
graph pooling
graph representation learning

Abstract: Graphs are known to have complicated structures and have myriad applications. How to utilize deep learning methods for graph classification tasks has attracted considerable research attention in the past few years. Two properties of graph data have imposed significant challenges on existing graph learning techniques. (1) Diversity: each graph has a variable size of unordered nodes and diverse node/edge types. (2) Complexity: graphs have not only node/edge features but also complex topological features. These two properties motivate us to use multiplex structure to learn graph features in a diverse way. In this paper, we propose a simple but effective approach, MxPool, which concurrently uses multiple graph convolution networks and graph pooling networks to build hierarchical learning structure for graph representation learning tasks. Our experiments on numerous graph classification benchmarks show that our MxPool has marked superiority over other state-of-the-art graph representation learning methods. For example, MxPool achieves 92.1% accuracy on the D&D dataset while the second best method DiffPool only achieves 80.64% accuracy.

Under review as a conference paper at ICLR 2020
MXPOOL: MULTIPLEX POOLING FOR HIERARCHICAL GRAPH REPRESENTATION LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Graphs are known to have complicated structures and have myriad applications. How utilize deep learning methods for graph classification tasks has attracted considerable research attention in the past few years. Two properties of graph data have imposed significant challenges on existing graph learning techniques. (1) Di- versity: each graph has variable size of unordered nodes and diverse node/edge types. (2) Complexity: graphs have not only node/edge features but also complex topological features. These two properties motivate us to use a multiplex structure to learn graph features in a diverse way. In this paper, we propose a simple but effective approach, MxPool, which concurrently uses multiple graph convolution networks and graph pooling networks to build hierarchical learning structure for graph representation learning tasks. Our experiments on numerous graph classifi- cation benchmarks show that our MxPool has marked superiority over other state- of-the-art graph representation learning methods. For example, MxPool achieves 92.1 % accuracy on the D&D dataset while the second best method DiftPool only achieves 80.64 60.64% accuracy.
INTRODUCTION
Graphs are known have complicated structures and have myriad of real world applications. Re- cently, great efforts have been put on utilizing deep learning methods for graph data analysis. Many newly proposed graph learning approaches are inspired by Convolutional Neural Networks (CNNs) (LeCun & Bengio, 1998), which have been greatly successful in learning two-dimensional image data (grid structure). The convolution and pooling layers in CNNs have been redefined to process graph data. Multitude of different Graph Convolutional Networks (GCNs) (Shuman et al., 2013) have been proposed, which can learn node level representations by aggregating feature information from neighbors (spatial-based -ased approaches) (Hamilton et al., 2017) or by introducing filters from the perspective of graph signal processing (spectral-based approaches) (Bengio & LeCun, 2014). On the other hand, similar to the original pooling layer which comes with CNNs, graph pooling module (Defferrard et al., 2016; Zhang et al., 2018) could easily reduce the variance and computation com- plexity by down-sampling from original feature data, which is of vital importance, particularly for graph level classification tasks. Recently, hierarchical pooling methods that can learn hierarchical representations of graphs have been proposed (Ying et al., 2018; Gao & Ji, 2019; Lee et al., 2019) and shows state-of-the performance for graph classification tasks.
However, two properties of graph data have imposed significant challenges on existing graph learn- ing techniques. 1) Diversity: each graph has a variable size of unordered nodes and has diverse node/edge types. 2) Complexity: graphs have not only node/edge features but also complex topo- logical features. These two properties can bring troubles in both of the graph convolution operation and the graph pooling operation.
For example, when performing node-representation learning tasks (by graph convolution operation), it is enough to use small output embedding size for simple and small graphs, as shown in Figure I(a), since large embedding size could result in overfitting problem. By contrast, it is necessary to set large output embedding sizes for complex and large graphs to learn complex graph structure properties, shown Figure in 1(b). This creates contradiction when processing set of irregular graphs For another example, when coarsening graphs (by graph pooling operation), if more attention is put the graph structure, we may obtain a coarsened graph shown in Figure 1(c). If more

---

Under review as a conference paper at ICLR 2020
attention is put the node features, may obtain another coarsened graph shown in Figure I(d). This creates another contradiction when processing graphs with not only node features but also topologiaal features.
Simple and graph needs small node embeddings
Complex large graph needs large node embeddingg
[c] Coarsen graph according to graph structure
(d) Coarsen graph according to node features
Multiple graph convolution networks with different output node embedding sizes needed since graph sizes and complexities are not consistent, c.g., (a) and (b). Multiple graph pooling networks needed to coarsen graphs according different graph properties. For example, the original graph can be coarsened according to graph structure as shown in (c) or according to node features as shown (d), where circle vertices have similar node features and triangle vertices have similar node features.
Figure 1:
The diversity property and the complexity property of graph data motivate structure to learn graph features a diverse way. On the other hand, as known, a common solu- tion for augmenting the traditional CNN convolution layers is use multiple convolution kernels in order to learn multiple local features. The success of CNNs on image data also inspires us to concurrently use multiple graph convolution networks and multiple graph pooling networks to learn graph representations.
multiplex GNN
In this paper, we propose MxPool in hierarchical graph representation learning for graph classifica- tion tasks! MxPool comprises multiple graph convolution networks to learn node-level represen- tations and also comprises multiple graph pooling networks to coarsen the graph. The node-level representations resulted from multiple convolution networks and the coarsened graphs resulted from multiple pooling networks are merged in a learnable way, respectively. The merged node represen- coarsened graph, which
tations and the merged coarsened graph are then used to generate used in the next layer. This multiplex structure can adapt to graphs with different sizes and can extract useful information from different perspectives.
We conduct extensive experiments on numerous graph classification benchmarks and show that our MxPool has marked superiority over other state-of-the-ar graph representation learning methods. For example, MxPool achieves 92. 1% accuracy on the D&D dataset while the second best method DiftPool only achieves 80.64% accuracy.
2 RELATED WORK
In this section, we review the recent literature on GNNs, graph convolution variants, and graph pooling variants.
Graph Neural Networks Inspired by Traditional Deep Learning Techniques. GNNs have re- cently drawn considerable attention due to their superiority in wide variety of graph related tasks, including node classification (Kipf & Welling., 2017), link prediction (Schlichtkrull et al., 2018), and graph classification (Dai et al., 2016). Many of these GNN models are inspired by traditional learning techniques. Inspired by the huge success of convolutional networks in the computer vision domain, large number of Graph Convolutional Networks (GCNs) have emerged. Besides convo- lution operation, pooling operation, another key component in CNNs, has also inspired research communities to propose graph pooling operations. There are also GNN optimizations originating from other learning approaches. Inspired by Recurrent Neural Networks (RNNs), You al. (20 8a) apply Graph RNN to the graph generation problem. DGNN (Ma et al., 2018) proposes using LSTM (Hochreiter & Schmidhuber, 1997) learn node representations in dynamic graphs. Inspired by the attention mechanism (Vaswani et al., 2017) Graph Attention Networks (GATs) (Velickovic et al.,
Our code is available http://githu..com//aaal MMPPool/.
2

---

Under review as a conference paper at ICLR 2020
2017) introduce attentions into GCNs by differentiating the influence of neighbors. Graph Au- toEncoders (GAEs) (Wang et al., 2016) origin from the autoencoder mechanism widely used for unsupervised learning and are suitable to learn node representations for graphs. GCPN (You al., 2018b) utilizes Reinforcement Learning (RI.) for goal-directed molecular graph generation.
Graph Convolution. Graph convolution operations fall into two categories, spectral-based ap- proaches and spatial-based approaches. Bengio & LeCun (2014) first introduce convolution for graph data from spectral domain using the graph Laplacian matrix L. Besides, there exist numerous spectral-based graph convolution methods, such as ChebNet (Defferrard et al., 2016), IstChebNet (Kipf & Welling, 2017), and AGCN (Li al., 2018). In contrast, spatial-based convolution meth- ods define graph convolution based on a node's s spatial relations. It takes the aggregation of a node representation and its neighbors' representations order to explore the depth and breadth of a node's ' receptive field, multiple graph convolution lay- er are stacked together. so that the features of two or more hops away neighbors can be learned. For example, GGNNs (Li et al., 2015), MPNN (Gilmer et al.. 2017), GraphSage (Hamilton et al., 2017), PATCHY-SAN (Niepert al., 2016), and DCNN (Atwood & Towsley, 2016) all fall into the spatial-based category.
obtain new representation for this node. In
Graph Pooling. Graph pooling operation is of vital importance for graph classification tasks (Zhang et al., 2018). It coarsens a graph into sub-graphs (Defferrard et al., 2016; Ying et al., 2018) or sum/average over the node representations (Duvenaud al., 2015; Gilmer al., 2017), which can obtain a compact representation on graph level. The graph coarsening approach- es obtain hierarchical graph representations either by using deterministic pooling methods or by using learned pooling methods. The deterministic pooling methods (Defferrard et al., 2016; Simonovsky Komodakis, 2017) utilizes graph clustering algorithms to obtain next level coarsened graph that is going to be processed by GNNs, following two- sto-sttge approach. On the other hand, the learned pooling methods (Ying et al., 2018; Lee et al., 2019; Diehl, 2019; Gao & Ji, 2019) seek to learn the hierarchical structure, which have shown to outperform deterministic pooling methods. DiffPool (Ying et al., 2018) was the first to propose learned graph pooling. It learns a soft cluster as- signment matrix in layer 7 which contains the probability values of nodes being assigned to clusters. A cluster in layer will be reduced to a node in layer / + 1. A GNN with input node features and adjacency matrix is used to generate the soft assignment matrix, based on which we can learn the cluster embeddings (i.e., node features in the next layer) and the coarsened adjacency matrix denot- ing the connectivity strength between each pair of the clusters. Besides DiffPool, numerous graph pooling methods have emerged recently, including gPool (Gao & Ji, 2019), SAGPool (Lee et al., 2019), EigenPooling (Ma et al., 2019), and Relational Pooling (Murphy et al., 2019). This paper will focus on the learned pooling.
3 PROPOSED METHOD
In this section, we propose MxPool to learn graph representations such that graph level classification can be applied. Before going to the details, we first introduce some notations and the problem setting.
Problem Setting A graph can be represented as G = FA, where A E Rax= denotes the adja- cency matrix (n is the number of nodes contained in 9), and F E R denotes the node feature matrix (d is the dimension of features). In the graph classification setting, given a set of graphs and each being associated with label, we aim train a model that takes an unseen graph as input and predicts its corresponding label. To make the prediction, it is important to extract useful information from multiple perspectives including both graph structure and node features.
3.1 OVERVIEW
MxPool is multi-layer hierarchical GNN model. At each layer, MxPool consists of convolution operation and pooling operation. The convolution operation aims to learn node-level representations, while the pooling operation aims to learn coarsened graph. The new coarsened graph can then be used as input to next layer. This process can be repeated several times, generating a multi-layer GNN model to learn hierarchical graph representations. The convolution operation and pooling operation are both important for graph representation learning. To simplify the illustration, we choose GCN (Kipf & Welling., 2017) the convolution layer and DiffPool (Ying et al., 2018) as the pooling
3

---

Under review as a conference paper at ICLR 2020
Next hierarchical layer
Multiplexing
hode amboddingg
Multiplex Pooling
Nods
Multiplex Convolution
Multiplexing
Merge
Figure 2: An illustrative example of MxPool. At each hierarchical layer, we first run multiple GCNs with different hyperparameters on the original graph, we will have multiple diverse sets of node embeddings, which form the multiplex convolution step. Next, we use a learnable approach to merge these embeddings for each node into one. We also run multiple differentiable pooling operations on the original graph and cluster nodes together in diverse ways, which forms the multiplex pooling step. These coarsened graphs are then merged into one in learnable approach. The merged node embeddings and the merged coarsened graph are used to generate new coarsened graph with new set of node features, which is going to be processed in the next hicrarchical layer.
layer (which is a differentiable pooling method), but it can be extended to use other convolution variant and pooling variant as well.
Different from other hierarchical GNNs, MxPool launches multiple GCNs to learn node-level rep- resentations and also launches multiple pooling networks coarsen the graph. The node-Ievel representations resulted from multiple GCNs are then merged in learnable way, and the coarsened graphs resulted from multiple pooling networks are also merged. The merged node embeddings and the merged coarsened graph are used to generate tures. This multiplex structure can help extract useful information from different perspectives (c.g., graph structure perspective and node feature perspective) and can adapt to graphs with different sizes. We provide an illustrative example as shown in Figure 3.
coarsened graph with a new set of node fea-
The procedure of the GCN (Kipf & Welling., 2017) is "horizontally" learn node representations, as it can only "pass message" between nodes through edges. The procedure of differentiable pool- ing (Ying et al., 2018) is "vertically" summarize the node features into the higher level graph representation. The procedure of multiplexing is to "diversely" learn node representations or graph representations from different perspectives. The procedure of merging is to "synthetically" learn the diverse results and put more attention to one or more perspectives. Since the convolution, pool- ing, and merging operations are all differentiable, we can define an end-to-end differentiable graph representation learning framework in hierarchical manner.
3.2 MULTIPLEX CONVOLUTION
In our model, we use GCN for the convolution operation. The original GCN (Kipf & Welling 2017) is stacked by several convolutional layers, and single convolutional layer be written
H (++1) ReLU (D- AD 11 (4)),
where H Ig are the node embeddings computed after & steps, A= A+1,D= Adj and (Kk) Rdxd a trainable weighted matrix2. Equation (1) can be understood as message passing process. The node embeddings (k) are the "messages" transferred along edges, which are going to be used to generate new node embeddings in next round. A total number of K convolutional layers
"The number of dimensions of W can be different from d, i.c., W E Rddxe where denotes the output emhedding's size.

---

Under review as a conference paper at ICLR 2020
stacked to learn node representations and the output matrix Z H can be viewed as the final node representations learned by the GCN model.
In multi-layer GNN, suppose there totally L layers. At each layer I, with the input node feature matrix X R xa' and the adjacency matrix A' E R xn' generated from previous layer, we learn an embedding matrix z E TR' xd'+ Here, we use d'+1 to denote the output embeddings' dimension since will determine the input node embeddings X ((+1) at next layer + that will be introduced later. For simplicity's 's sake, we will use Z GCN, X') to denote the GCN process (containing K iterations of message passing). Initially, A A E R the original graph's 's adjacency matrix, and X()) F E Raxd is the original graph's node features.
In MxPool, we use multiple GCNs to learn multiple sets of node embeddings. These GCNs can be trained with different sets of hyperparameters such as weight matrix W"s dimension. Suppose there are GCNs running concurrently at each layer I, we will have sets of node embeddings (Z(") 22 z!0)) J. Let 8 be the hyperparameters of the ith GCN. Then layer 1, we have node embeddings T resulted from the ith GCN as follows:
(1) GCN((A ,x
Then, the multiple sets of node embeddings embeddings (t) using neural network:
1 _ ..... 2 are merged into one set of node
2 = So( 11 |1.. 112
(3)
where "Il" denotes row-wise concatenation operation and fe() is trainable neural network. One important hyperparameter of fc() the output embeddings' dimension d'+1, i.e., z(0) RRn xx'xd'+= We set d' by averaging the dimensions of the multiple weight matrices (W1, W2..., W..)-
Suppose W; E R. xdt, we can set d -E di/no.
3.3 MULTIPLEX POOLING
We follow DiffPool (Ying et al., 2018) to construct our multiplex pooling layer. We learn to assign nodes to clusters each layer 1 using node embeddings and adjacency matrix generated from previ- ous layer. Specifically, at each layer I, we learn пp cluster assignment matrices [S1. S2...., Sn,.
and each cluster assignment matrix S; is generated as follows:
= softmar (GCN,(A0) x. (:))
(4)
It is noticeable that GCN, is a GCN different from the GCN, used in the convolution layer, though these two GNNs consume the same input data. Each row of s(!) corresponds to one of the n' nodes at layer I, and each column of 5!0) corresponds to of the eę clusters, that we have s( g= xe] (4; < 1 denotes the hyperparameters set the ith GCN, One important hyperparameter could be the compression ratio that determines the number of clusters to be assigned, i.e., cf. Different pooling networks can use different number of clusters.
Similar to the merging process in the convolution operation, these generated assignment matrices o())
(5()) ((() ,..,, S...,,,spp) are merged into a single assignment matrix s()) using a neural network:
5 = 1|.9)
(5)
where "I|" denotes row-wise concatenation operation and fz() is trainable neural network. Given the number of nodes at the next layer / In we should configure fa() to output an assignment matrix with n1+1 columns, i.e., (() T /u''
Following the pooling approach proposed in (Ying et al., 2018), we then use the merged node em- beddings z as shown in Equation (3) and the merged assignment matrix (()) as shown in Equation (5) generate embeddings for each of the n111 clusters. We also take the adjacency matrix A())
5

---

Under review as a conference paper at ICLR 2020
and the merged assignment matrix 5() to generate coarsened adjacency matrix denoting the edge weights between each pair of cluster:
x = 50) z
(6)
A = 50) A()
Here, since 500) p='xx'"1 and z E qgn'xd**1 we have the cluster embeddings X Rn'-'xd++ xxd=1 Similarly, have the coarsened adjacency matrix A(+1) B'' xn'+1
e
Note that, the coarsened graph a fully connected weighted graph, so that the coarsened adjacency matrix A is real matrix and each entry A denotes the edge weight between two clusters. The cluster embeddings X (1+1) and the coarsened adjacency matrix A will then be used input to the next layer, where one cluster at layer I corresponds to one node at layer + 1.
4 EXPERIMENTS
In this section, we compare MxPool with the tfte-offthee-e graph representation learning methods in the context of graph classification task.
Datasets. In our experiments, we use four graph data sets chosen from benchmarks commonly used in graph classification. These include D&D (Dobson Doig. 2003), ENZYMES (Borgwardt al., 2005), PROTEINS (Dobson & Doig, 2003; Borgwardt et al., 2005), NC1109 (Wale et al., 2008), and COLLAB (Yanardag & Vishwanathan, 2015). Each of these datasets include hundreds to thousands graphs. The details of these datasets are provided in Table 1.
Table 1: Statistics of data sets.
Dataset
of graphs
of classes max of nodes
avg of nodes
avg of edges
D&D
1178
5748
284.32
715.66
ENZYMES
600
126
32.63
62.14
PROTEINS
1113
2
620
39.06
72.82
NCI109
4127
2
111
29.68
32.13
COLLAB
5000
492
74.49
2457.78
Model Configurations. We implement MxPool by modifying DiffPool. The convolution GNN model used is the "mean" variant of GraphSAGE (Hamilton al., 2017) architecture, which is sim- ilar to the GCN and provides various aggregation methods. The pooling GNN model used is the DiffPool model. The model configurations for convolution GNN and pooling GNN is the same as DiffPool. Besides, our MxPool comprises multiple graph convolution networks and multiple graph pooling networks with different sets of hyperparameters to learn graph features from different per- spectives. Besides the hyperparameters used in each convolutional/poolng GNN, the number of graph convolution networks and the number of graph pooling networks are two hyperparameter- We concurrently run 3 graph convolution networks and also concurrently run 3 graph pooling networks. The learning rate is set as 0.001. Regarding the ENZYMES dataset, since there exist classes, we cross entropy to compute the loss.
4.1 BASELINES AND EXPERIMENTAL SETTINGS
We consider the following state-of-the-art art methods for graph classification task as basclines:
GraphSAGE (Hamilton et al., 2017) is a graph convolution framework proposed for semi- supervised node classification. GraphSAGE with global mean-pooling on the learned node rep- resentations can realize graph representation learning so that it can be used for graph classification task. Other graph convolution variants are omitted as empirically GraphSAGH AGE obtained higher per- formance in the task (Hamilton et al., 2017).
SortPool (Zhang al., 2018) is global pooling method which uses sorting for pooling. It is built upon the GCN layer, where the features of nodes are sorted before feeding them into traditional ID convolutional and dense layers.

---

Under review as a conference paper at ICLR 2020
Table 2: Performance comparison graph classification.
Baselines
D&D
ENZYMES
PROTEINS
NCI109
COLLAB
Gra (Hamilton et al., 2017)
75.42
54.25
70.48
76.50
68.25
SortPool (Zhang et al., 2018)
79.37
57.12
75.54
70.80
73.76
gPool (Gao & Ji, 2019)
75.01
48.33
73.63
66.12
71.12
SAGPool (Lee et al., 2019)
76.45
71.86
67.86
DifiPool (Ying et al., 2018)
80.64
62.53
76.25
78.86
75.48
MxPool (Ours)
92.10
66.90
77.21
82.21
73.44
gPool (Gao & Ji, 2019) recently proposed graph pooling method. It achieves pooling operation by adaptively selecting some nodes to form smaller graph based on their scalar projection values on a trainable projection vector.
SAGPool (Lee et al., 2019) is a Celf-Attention Graph Pooling method for GNNs in the context of hierarchical graph pooling. The self-attention mechanism exploited to distinguish between the nodes that should be dropped and the nodes that should be retained.
DiffPool (Ying et al., 2018) is the first end-to-end trainable graph pooling method that learns hierar- chical representations of graphs. By setting compression ratio parameter r, graph with n nodes coarsened into a graph with n nodes at each layer. We also implement our method based on DiffPool.
Experimental Setup order to remove unwanted bias towards the training data, we use 10-fold cross validation for all the baselines and our approach. Since GraphSAGE. and DiffPool are the two key components in our MxPool approach (GraphSAGE as the graph convolution layer and DiflPool as the graph pooling layer), we use the base implementation and hyperparameter sweeps in our MxPool approach. Regarding the hyperparameters of SortPool, gPool, and SAGPool, we follow the same experimental setups described in their original papers. In addition, we adopt the widely used evaluation metric, i.e., accuracy, for graph classification to evaluate the performance.
4.2 PERFORMANCE ON GRAPH CLASSIFICATION
The graph classification performance in ter90o8ims of accuracy is reported in Table 2. For all the baselines, we use 10-fold cross validation numbers reported by the original authors if we can obtain the numbers close to the reported ones. Regarding the gPool bascline (Gao & Ji, 2019), we cannot obtain the necessary published numbers, so we use the numbers on the ENZYMES dataset and PRO- TEINS dataset reported by the third-party" and the number on D&D dataset reported by Lee al. (2019). For the other datasets, we use the numbers tested by ourselves. Regarding the SAGPool baseline (Lee et al., 2019), meet RuntimeError when processing the ENZYMES dataset and COLLAB dataset, and we denote this case by '-'
From the table, observe that MxPool approach shows remarkable performance improvement over the other state-of-the-ar baselines on the first four datasets. Especially on the D&D dataset, MxPool improves the performance the second-best approach DifiPool over I 11% However, Diff- Pool performs slightly better than MxPool on the COLLAB dataset. We tested DiftPool by ourselves and could only obtain 71.78% accuracy, which is lower than the number 75.4 75.48% reported in the o- riginal paper. This may be due to the unoptimized parameter settings, but we still use the reported number 75.48% for the DiffPool baseline. In addition, GraphSAGE and DifiPool are the two basic components in our multiplex model, working as the convolution layer and the pooling layer, re- spectively. MxPool improves upon the base convolution GNN (i.e., GraphSAGE) by an average of 9.39% and improves upon the base pooling GNN (i.c., DifiPool) by average of 3.62%.
4.3 ANALYSIS OF MULTIPLEX CONVOLUTION/POOLNNG
Our motivation for this work is to utilize multiplex hierarchical structure to deal with the diversity and complexity challenges in graph representation learning. Multiple graph convolutional networks
hhans//gitthh.ccm//haaaaggggg

---

Under review as a conference paper at ICLR 2020
Table 3: Effect of multiplex convolation/pooling:
Variations
D&D
ENZYMES
PROTEINS
NC1109
COLLAB
C1 P1
80.01
62.17
75.48
80.07
71.31
SCSP
79.33
59.85
74.47
80.10
71.33
C3 P1
78.75
60.32
75.14
78.49
71.14
MCSP
[c [2|c P1
88.60
63.01
75.57
81.43
72.23
80.01
60.30
75.48
80.07
71.31
SCSP
p2
78.64
56.12
75.96
78.47
71.78
78.79
61.22
74.52
78.95
71.02
SCMP
C1 * [P1 P2 Ps)
87.50
61.85
76.01
78.47
72.89
MCMP
[c 02 [ca]
92.10
66.90
77.21
82.21
73.44
(i.e., GraphSAGE) with different sets of hyperparameters used to learn node representations. The node embedding size, as a hyperparameter in GraphSAGE, plays an important role in determining the quality of node representation. We vary the node embedding sizes different GraphSAGE networks. On the other hand, multiple graph pooling networks (i.e., DiffPool) with different sets of hyperparameters are used coarsen graphs. The compression ratio, as hyperparameter in DifiPool, plays an important role in determining the quality of graph representation. We vary the compression ratios in different DiffPool networks.
In order to verify the effectiveness of multiplex convolution and multiplex pooling, we run our MxPool with single convolution network and single pooling network (SCSP), multiple convolution networks and single pooling network (MCSP), single convolution network and multiple pooling networks (SCMP), and multiple convolution networks and multiple pooling networks (MCMP), re- spectively. The accuracy results for graph classification are shown in Table 3. Since the suitable node embedding sizes and compression ratios are not consistent for different datasets, we use C1, C2 C3 to denote three different graph convolution parameters (i.e.. node embedding size) and P1, P2, P3 to de- note three different graph pooling parameters (i.e., compression ratio). Note that, they are different GitHub project page.
for different datasets. We have put the detailed parameter settings
From the table, we observe that the multiplex structure significantly improves performance over the singular structure. By fixing the pooling network with pl. multiplexing three convolution networks with hyperparameters [c1 (22 (ca] performs much better than using single convolution network with either C1, C2, 03- A similar trend can be observed when multiplexing pooling networks. Anyhow, the best choice is to simultaneously multiplex convolution networks and multiplex pooling networks (i.e., MCMP).
4.4 NUMBER OF CONVOLUTTON/POOLING NETWORKS
The number of convolution/pooling networks is a hyperparamter in MxPool. In the previous ex- periments, we use fixed number of convolution/pooling GNNs to show the performance. In this experiment, we vary the number of convolution/pooling networks from mance. Our results listed in Appendix A show that the performance can be improved a lot when the number is set to 3. But as the number is increased larger, the performance reduced. This may be because that too many networks with large amount of parameters result in overfitting problem.
and test the perfor-
CONCLUSION
In this paper, we proposed simple but effective multiplex GNN architecture MxPool for hierar- chical graph representation learning. MxPool comprises multiple graph convolution networks to learn node-level representations and also comprises multiple graph pooling networks to coarsen graph. The diversity challenge and the complexity challenge of graph representation learning can be well addressed our proposed approach. Our results show that MxPool has remarkable perfor- graph representation learning methods. Future work
mance improvement over the state-of-the-ee includes designing unpooling layers to form an encoder-decoder learning structure to deal with node classification tasks and link prediction tasks.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
James Atwood and Don Towsley. crffusion-convllution neural networks. In Proceedings of the 30th International Conference on Neural Information Processing Systems (NIPS 2016), pp. 2001- 2009, 2016.
Yoshua Bengio and Yann LeCun. Spectral networks and locally connected networks graphs. In Proceedings of the 2nd International Conference on Learning Representations (ICLR 2014), 2014.
K. M. Borgwardt, C. S. Ong. S. Schonauer, S. Vishwanathan, A. J. Smola, and P. Kriegel. Protein function prediction via graph kemels.. Bioinformatics, 21(suppL_1):47-56, 2005.
Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for struc- tured data. In Proceedings of the 33rd International Conference on International Conference on Machine Learming (ICML 2016), pp. 2702-2711. 2016.
Michael Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Proceedings of the 30th International Conference on Neural Information Processing Systems (NIPS 2016). pp. 3844-3852, 2016.
Frederik Diehl. Edge contraction pooling for graph neural networks. CoRR, 0bs/1995.1009 2019.
wwwgg//g/////o/.../...o/eeeeeeee URL http: //arxivaivvv..//aa org/ abs /105 10990.
P. D. Dobson and A. J. Doig. Distinguishing enzyme structures from non-enzymes without align- ments. Journal of molecular biology, 330(4):771-783, 2003.
David Duvenaud, Dougal Maclaurin, Jorge othy Hirzel, Alán Aspuru-Guzz and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Proceedings of the 28th International Conference on Neural Information Processing Systems (NIPS 2015), pp. 2224-2232, 2015.
Rafael Gómez-Bombarelli, Tim-
Hongyang Gao and Shuiwang Ji. An end-to-end deep learning architecture for graph classification. In Proceedings of the 36th International Conference on Machine Learning (ICML 2019), 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning (ICML 20/7), pp. 1263-1272, 2017.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference Neural Information Processing Systems (NIPS 20/7), pp. 1025-1035, 2017.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput., 98): 1780, 1997.
T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference Learning Representations (ICLR 2017), 2017.
T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the 7th International Conference on Learning Representations (ICLR 2017), 2017.
Yann LeCun and Yoshua Bengio. The handbook of brain theory and neural networks. chapter Convolutional Networks for Images, Speech, and Time Series, pp. 255-258, 1998.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Proceedings of the 36th International Conference on Machine Learning (ICML 2019), 2019.
R. Li, Wang, Zhu, and Huang. Adaptive graph convolutional neural networks. Proceedings of the AAAI Conference Artificial Intelligence (AAAI 2018), pp. 3546-3553, 2018.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In Proceedings of the 3rd International Conference on Learning Representations (ICLR 2015), 2015.

---

Under review as a conference paper at ICLR 2020
Yao Ma, Ziyi Guo, Zhaochun Ren, Yihong Eric Zhao, Jiliang Tang. and Dawei CoRR, abs/1810.10627, 2018. URL
Yin. Dynamic graph neural networks
http:/ / http://axvvvvvo//i org/ abs 1166.76627.
Yao Ma, Suhang Wang, Charu C. Aggarwal, and Jiliang Tang. Graph convolutional networks with eigenpooling. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery (KDD 2019), pp. 723-731, 2019.
Ryan L. Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pool- ing for graph representations. In Proceedings of the 36th International Conference on Machine Learning (ICML 2019), 2019.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In Proceedings of the 33rd International Conference on International Confer- ence on Machine Learning (ICMI. 2016), pp. 2014-2023, 2016.
M. Schlichtkrull, N. Kipf, P. Bloem, R. van den Berg, I. Titov, and M. Welling. Modeling relational data with graph convolutional networks. In Extended Semantic Web Conference, 2018.
David Shuman, Sunil Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to net- works and other irregular domains. IEEE Signal Processing Magazine, 30(3):83 98, 2013.
Martin Simonovsky and Nikos Komodakis. convolutional neural networks graphs.
Dynamic edge-conditioned filters in CoRR, abs/1704.02901, 2017.
URL
029901.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31st In- ternational Conference on Neural Information Processing Systems (NIPS 2017), pp. 6000-6010, 2017.
P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention net- works. In Proceedings of the 5th International Conference on Learning Representations (ICLR 2017), 2017.
Nikil Wale, Ian A. Watson, and Samy Bengio. Comparison of descriptor spaces for chemical com- pound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008.
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2016), pp. 1225-12222 1234, 2016.
Pinar Yanardag and V.N. Vishwanathan. structural smoothing framework for robust graph com- parison. In Advances in Neural Information Processing Systems, pp. 2142, 2015.
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (NIPS 2018), pp. 4805- 4815, 2018
J. You, R. Ying, X. Ren, W. Hamilton, and J. Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. In Proceedings of the 35th International Conference on Machine Learming (ICML 2018), 2018a.
Jiaxuan You, Bowen Liu, Rex Ying, Vijay Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. In Proceedings of the 32Nd International Conference on Neural Information Processing Systems (NIPS 2018), pp. 6412-6422, 2018b.
Muhan Zhang, Zhicheng Cui. Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI Conference on Artificial Intelli- gence (AAAI 2018), pp. 4438 4445, 2018
10

---

Under review as a conference paper at ICLR 2020
A RESULTS OF THE NUMBER OF CONVOLUTION/PPOOING NETWORKS
In this experiment, we vary the number of convolution/pooling networks from to 6. The number of convolution networks and the number of pooling networks are the same. The graph classification accuracy results on D&D, ENZYMES, and PROTEINS datasets are shown in Table 4.
Table 4: Effect of number of convolution/poolligg GNNs.
2
3
4
5
D&D
80.24
88.57
92.10
89,29
87.86
87.32
ENZYMES
62.02
60.80
66.90
64.89
65.71
62.70
PROTEINS
76.25
77.31
77.21
76.73
75.58
75.19
From the table, But as the number is increased larger than 3, the performance is reduced. This may be because that too many networks with large amount of parameters result in overfitting problem.
that the best performance is achieved when the number is set 2 or 3.


Reviews:
[{"review_id": "rye-2tQptr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper introduces a new hierarchical graph representation learning method for graph classification. It builds upon the diffpool method. Specifically, the authors propose the multiplex convolution and the multiplex pooling operation. The multiplex convolution learns multiple graph convolution operations (potentially with different parameters) and merges them using a neural network. Similarly, the multiplex pooling learns multiple assignment matrices utilizing diffpool and merges them using a neural network. The effectiveness of the proposed model is demonstrated with experiments in several standard benchmark datasets for graph classification. \n\nStrengths\n\nThe overall architecture of the proposed method can be regarded as an extension of diffpool method by using multiple convolution and pooling operations. An analysis on how the number of convolution and pooling operations can affect the performance of the model shows the effectiveness of the proposed multiplex convolution/pooling operations. The effectiveness of the proposed model is further verified by the experimental results on 5 standard benchmark datasets.\n\nWeakness \n\nThe novelty of the paper is limited. The major contribution of this paper is to utilize multiple convolution/pooling operations and merge them with neural networks. \n\nIt is not clear how issues mentioned in the motivational examples shown in Figure 1 can be solved by the proposed model. As discussed in Figure 1(a) and Figure 1(b), small graphs may prefer small embedding while large graphs may prefer large embedding. However, it is unclear how the proposed model achieves this goal as the combination of the embeddings from different convolution operations is through a neural network that is shared by all graphs. Similarly, for Figure 1(c) and Figure 1(d), it is not clear how the proposed model can focus more on one type of information than the other. It would be helpful if there are some empirical results to demonstrate this.\n\nRecommendations\n\nIt would be better if the authors can provide some analysis on time complexity of the proposed model. The major concern of the efficiency is the introducing of fully connected graph after each pooling as mentioned in Section 3.3. \n\nMinor comments\n\nIn section 3.3, “is a GCN different” -> “is a GCN variant”?\nIn Section 3.3, should there be a softmax function after Eq.(5)? \nIn section 4.2, “in ter90o8ims” -> “in terms”?\n\n\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 carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJxlWY32KS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper extends DiffPool for hierarchical graph representation learning (in particular, graph classification). The authors empirically show that for several data sets, the approach outperforms quite a few recently proposed strong competitors.\n\nThe proposed approach is reasonable, but is not much innovative. The prior work DiffPool uses GCNs to parameterize the node embedding matrix Z and the cluster assignment matrix S. This paper computes a number of Zs and Ss, each of which result from a different hyperparameter choice of GCN, and then combines them through concatenation and feed forward transform. Significance of the contribution is a bit marginal.\n\nThe experimental results appear to be exciting, in light of the substantial boost in classification accuracy on the D&D data set. However, the experiment design and the reporting of results are doubtful. A major concern is the copying of results reported by prior work to Table 2. It is unclear whether these numbers were obtained from the same experiment setting. For example, the number for SAGPool + D&D comes from Lee et al., 2019, but the DiffPool number in that paper is 66.95, which is significantly different the one shown here, 80.64, copied from Ying et al., 2018.\n\nAnother concern is the missing numbers for SAGPool. Although the authors explain the difficulty of obtaining these numbers, a lack of them does not complete the empirical evaluation.\n\nMinor comments/questions:\n\n- In the first sentence of 4.2, the word \"ter90o8ims\" is a typo of \"terms\".\n\n- What are the neural networks f_c in (3) and f_p in (5)?\n\n- Texts after (5) read f_g instead of f_p.\n", "extra_scores": {"experience_assessment": "I have published one or two 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 carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1xnZGs3YH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strengths:\n-- The paper is well written and easy to follow\n-- Learning graph representation learning is a very important problem\n-- The performance of the proposed approach are strong on the existing data sets\n\nWeakness\n--  the novelty of the proposed method is marginal\n-- Some real-case study on why the model works are not presented.\n-- The data sets used in the experiments are too small\n\nThis paper studied learning the hierarchical representation of graphs. Comparing to the previous work DiffPool, the author proposed to use multiple node representations and multiple pooling functions. Experimental results on a few data sets prove the effectiveness of the proposed approach.\n\nOverall, the paper is well written and easy to follow. Learning the hierarchical representation of graphs is an important and also interesting problem. However, I feel the novelty of the proposed method is marginal. And besides, though illustrated using artificial example in the introduction, it is not clear why the proposed method work in practice. Specifically, I have the following questions:\n(1) How does multiple convolutional method compared with just concatenating the weight matrix W_i, in other words, we can just use a much larger node embedding size. From equation (2) and (3), I feel these two are identical. The authors should explain this.\n(2) Similar concerns in the multiple pooling case.\n(3) It would be more convincing that the authors presented a few real cases to prove the effectiveness of the proposed approach instead of only using the artificial examples in introduction.", "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 carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers are consistently negative on this paper. Thus a reject is recommended.
Decision: Reject