GRAPH ANALYSIS AND GRAPH POOLING IN THE SPATIAL DOMAIN
Authors: Mostafa Rahmani
Ping Li
Venue:  (2020)
Keywords: Graph Neural Network
Graph Classification
Graph Pooling
Graph Embedding

Abstract: The spatial convolution layer which is widely used  in the Graph Neural Networks (GNNs) aggregates the feature vector of each node with the feature vectors of its neighboring nodes. The GNN is not aware of  the locations of the nodes in the global structure of the graph  and when the local structures corresponding to different nodes are similar to each other, the convolution layer maps all those nodes to similar or same feature vectors in the continuous feature space. Therefore, the GNN cannot distinguish two graphs if their difference is not in their local structures. In addition, when the nodes are not labeled/attributed the convolution layers can fail to  distinguish even  different local structures. In this paper, we propose an effective solution to address this problem of the GNNs. The proposed approach leverages a spatial representation of the graph which makes the neural network aware of the differences between the nodes and also their locations in the graph. The spatial representation which is equivalent to a point-cloud representation of the graph is obtained by a graph embedding method. Using the proposed approach, the local feature extractor of the GNN distinguishes similar local structures in different locations of the graph and the GNN infers the topological structure of the graph from the spatial distribution of the locally extracted feature vectors. Moreover,  the spatial representation is utilized to simplify the graph down-sampling problem. A new graph pooling method is proposed and it is shown that the proposed pooling method achieves competitive or better results in comparison with the state-of-the-art methods. 


Under review as a conference paper at ICLR 2020
GRAPH ANALYSIS AND GRAPH POOLING IN THE SPA- TIAL DOMAIN
Anonymous authors Paper under double-blind review
ABSTRACT
The spatial convolution layer which is widely used in the Graph Neural Networks (GNNs) aggregates the feature vector of each node with the feature vectors of its neighboring nodes. The GNN is not aware of the locations of the nodes in the global structure of the graph and when the local structures corresponding to dif- ferent nodes are similar to each other, the convolution layer maps all those nodes to similar or same feature vectors in the continuous feature space. Therefore, the GNN cannot distinguish two graphs their difference is not in their local structures. In addition, when the nodes not labeled/atrribteed the convolution layers can fail to distinguish even different local structures. In this paper, we pro- pose effective solution to address this problem of the GNNs. The proposed approach leverages spatial representation of the graph which makes the neural network aware of the differences between the nodes and also their locations in the graph. The spatial representation which is equivalent to a point-cloud rep- resentation of the graph is obtained by graph embedding method. Using the proposed approach, the local feature extractor of the GNN distinguishes similar local structures in different locations of the graph and the GNN infers the topo- logical structure of the graph from the spatial distribution of the locally extracted feature vectors. Moreover, the spatial representation is utilized to simplify the graph down-sampling problem. A new graph pooling method is proposed and it is shown that the proposed pooling method achieves competitive or better results in comparison with the state-of the-aar methods.
INTRODUCTION
Many of the modern data are naturally represented by graphs (Bronstein et al. 2017 Cook & Holder
2006 Dadaneh Qian| 2016) Qi al., (017b) and is an important research problem to design neural network architectures which can work with graphs. The adjacency matrix of graph exhibits the local connectivity of the nodes. Thus, is straightforward to extend the local feature aggregation used in the Convolutional Neural Networks (CNNs) to the Graph Neural Networks (GNNs) (Awwod & Towsley| [0166] Bruna et al.| 2014: Fey et al. 2018 Gilmer et al.) 2017 Niepert et al., [016] Simonovsky & Komodakis 2017] Zhhnn al. 2018). However, when the nodes of the graphs are not labeled/atributeed or the labels/atrribute of the nodes do not carry information about the differences between the nodes or any information about their locations in the graph, the GNN can fail to extract discriminative features. The GNN maps nodes whose corresponding local structures are similar same/close feature vectors in the continuous feature space. Although mapping nodes with similar local structures to similar feature vectors might be desirable in some applications (Henderson al. 2012). this feature can make the GNN unable to distinguish graphs whose difference is not in their local structures. In addition, when the nodes are not labeled/atrributed, the spatial graph convolution only propagates information about the degree of the nodes which might not lead to extracting informative features about the topological structure of the graph. Another limitation of the current GNN architectures that they are mostly unable to do the hicrarchical feature learning employed in the CNNs (He al. 2016 Krizhevsky et al. 2012). The main reason is that graphs lack the tensor representation and is difficult to measure how accurate a subset of nodes represent the topological structure of the given graph.
Summary of Contributions. this paper, we focus on the graph classification problem. The main contributions of this paper can be summarized as follows.

---

Under review as a conference paper at ICLR 2020
A shortcoming of the GNNs is discussed and it is shown that the existing GNNs can fail to learn to perform even simple graph analysis tasks. It is shown that the proposed approach which leverages spatial representation of the graph effectively addresses the shorteoming of the GNN. Several new experiments are presented to demonstrate the shorteoming of the GNNs and they show that providing the geometrical representation of the graph to the neural network substantially improves the capability of the GNN in inferring the structure of the graph.
The geometrical representation of the graph is leveraged design novel graph pooling method. The proposed approach simplifies the graph down sampling problem into a column/row sampling problem. The proposed approach samples a subset of the nodes such that they preserve the structure of the graph. It is shown that the proposed approach achieves competitive or better performance in comparison with the existing methods.
Notation. Given vector x, ||x||p denotes its lp Euclidean norm, and x(i) denotes its hth ele- ment. Given matrix X. X, denotes the ith row of X. A graph with nodes is represented by two matrices A E R=x= and E Rxd where A is the adjacency matrix, is the matrix of node labels/attributes, and d is the dimension of the attributes/labels of the nodes. The operation A * B means that the content of A is set equal to the content of B. If I a set of indices, Xx the matrix of the rows of X whose indexes are in I. Vector y = softmax (x) is defined as y(i) Σ. v exp(x(A)) The local structure corresponding to node is the structure of the graph in the close neighbourhood of the node.
exp(xx())
RELATED WORK
This paper mainly focuses on the graph classification problem. In the proposed approach, the geo- metrical representation of the graph provided by a graph embedding algorithm is utilized to make the neural network aware of the topological structure of the graph. In this section, some of the related research works in GNN and graph embedding are briefly reviewed.
Graph Embedding: A graph embedding method aims at finding a continuous embedding vector for each node of the graph such that the topological structure of the graph is encoded in the spatial distribution of the embedding vectors. The nodes which are close on the graph or they share similar structural role are mapped to nearby points the embedding space and vice versa. In general, the graph embedding methods fall into three broad categories: matrix factorization based methods (Ahmed et al.) 2013 Belkin & Niyogi 2002; [Cao et al., 2015 Ou et al. 2016 Roweis Saul, 2000), random-wall based approaches (Grover & Leskovec 2016 Perozzi et al., 2014), and deep learning based methods (Wang et al. 2016). In this paper, we use the Deep Walk graph embedding method (Perozzi et al. 2014) which a random walked based method.
Graph Neural Networks: In recent years, there has been surge of interest in developing deep network architectures which can work with graphs (Bronstein et al., 2017: Bruna et al.] 2014] Du-
venaud et al.) 2015| Fout et al. 2017 Gilmer al., 2017.
et al. 2017 Kipf et al. 2018
Kipf & Welling 2017] | ctt al.) 2019). Local connectivity, weight sharing, and shift invariance of the convolution layer in the CNNs have led to remarkable achievements in computer vision and natural language process- ing (Goodfellow et al., 2016). Accordingly, there are remarkable works focusing on the design of graph convolution layers encoding the traditional properties. Most of the existing graph convolution layers can be loosely divided into two main subsets: the spatial convolution layers and the spec- based on the generalization of spectral filtering in graph signal processing (Bruna et al. 2014, Defferrard et al., 2016 Henaff et al.) 2015 Levic al. 2017). The major drawback of the spectral based methods is the non-generalizability to data residing over multiple graphs which is due to the dependency on the basis of the graph Laplacian. In contrast to spectral graph convolution, the spatial graph convolution performs the convolution di- rectly in the nodal domain and can be generalized across graphs (Nguyen et al.] [0188] Niepert et al.) 2016 Schlichtkrull et al. 2018 Simonovsky & Komodakis) 2017] Veličkovié et al. 2017]] Verma & Zhang 2018 Zhang et al. 2018). If the sum function is used to aggregate the local feature vectors, a simple spatial convolution layer can be written as
et al., 2016 Niepert et al. 2016 Simonovsky & Komodakis 2017 Tixier
tral convolution layers. The spectral methods
X + A (X + (X
where f(-) is the clement-wise non- non-linear function. Some papers use a normalized version of [I) via multiplying (1) with the inverse of the degree matrix (Ying al. 2018). The weight matrix
2

---

Under review as a conference paper at ICLR 2020
22 transforms the feature vector of the given node and 1 transforms the feature vectors of the neighbouring nodes. A drawback of the spatial convolution is that the aggregation function might not be injective function, i.c., two nodes with different local structures can be mapped to the same feature vector by the convolution layer. The authors of (Xu et al.) 2019) showed that with minor modification, the sum aggregation function can become an injective function. However, when the nodes are not labeled/attribted or the labels/attribues do not inform the GNN about the location of the nodes, the GNN is not able to distinguish graphs whose local structures are similar but their global structures are different. The approach proposed in our paper not only addresses the problem raised in (Xu et al. 2019). it also helps the GNN to distinguish the similar local structures in different locations of the graph.
In order to obtain a global representation of the graph, the local feature vectors obtained by the convolution layers should be aggregated into final feature vector. The element-wise max/mean functions are used widely to aggregate all the local feature vectors. Inspired by the hierarchical feature extraction in the CNNs, tools have been developed to perform nonlocal feature aggregation (Duvenaud et al. 2015 Luzhnica et al. 2019). In (Zhang et al. 2018), the nodes are ranked and the ranking used to build sequence of nodes using subset of the nodes. Subsequently, a 1- dimensional CNN is applied to the sequence of the nodes to perform non-local feature aggregation. However, the way that (Zhang et al., 2018) builds the sequence of the nodes is not data driven. In addition, a 1-dimensional array might not have the capacity to preserve the topological structure of the graph. In (Ying et al. 2018), a soft graph pooling method was proposed which learns set of cluster centers that are used to down-sample the extracted local feature vectors. The graph pooling methods proposed in (Gao & Ji 2019; Lee et al. 2019) are similar to the soft graph pooling method presented in (Ying et al.] 20188 but they learn one cluster center which is used to rank the nodes and they sample the nodes which are closer to the learned cluster center. In (Defferrard et al., 2016 Fey et al. 2018), the graph clustering algorithms were used to perform graph down-sizing.
3. THE SHORTCOMING OF THE GNNS
Suppose the nodes of the given graphs are not labeled/atrribtted assume that the labels/attributes do not contain any information about the role/location of the nodes in the global structure of the graph. Therefore, if two different nodes are not labeled or they are labeled similarly, they appear the same to the GNN. Accordingly, if the local structures corresponding to two nodes are similar, the convolution layer of the GNN maps them to the same feature vector in the continuous feature space. This means that if the local structures of two different graphs are similar, the GNN cannot extract discriminative features to distinguish them. In the followings, we study an example to clarify this feature of the GNN.
Illustrative example: Suppose we have a dataset of clustered unlabeled graphs (nodes and edges are not labeled/attiibuted) and assume that the clusters are not topologically different (a common generator created all the clusters). Every node is connected to small a set of the other nodes in its corresponding cluster. One class of the graphs consist of two clusters and the other class of graphs consist of three clusters. Therefore, the task is to infer if a graph is made of two clusters or three clusters. Consider the simplest case in which there is connection between the clusters. Assume that we use a typical GNN which is composed of multiple spatial convolution layers and a global element-wise max/mean pooling layer. Suppose that given graph belongs the first class, i.e., it consists of two clusters. Define V1 and V2 as the aggregation of the local feature vectors corresponding to the first and the second clusters, respectively. The global feature vector of this graph is equal to the element- deeeett-wise mean/max of v and V2. Clearly, va can be indistinguishable from Vi since the clusters are generated using the same generator and the GNN not aware of the location of the nodes. Therefore, the feature vector of the whole graph can also be indistinguishable from V1. The same argument is also true for a graph with three clusters. Accordingly, the representation obtained by the GNN is unable to distinguish this two classes of graphs. If one trains GNN on this task, the test accuracy is around 50 % which is not better than random guess. The main reason is that the local structures corresponding to all the nodes in graph are similar. In addition, the local structures in a graph with two clusters is not different from the local structures in a graph with three clusters. Since the GNN is not aware of the location of the nodes, all the nodes are mapped similar
3

---

Under review as a conference paper at ICLR 2020
& layers of Spatial Graph
Rg blocks giguph pooling followed spatial conv.
E
Globa Apgregatt oeggegttor
Fully Connected
X=E+F
Graph Pooling
layers Spatial Graph Conv.
kg layers of Spatial Graph Conw.
sum
K; layers Spatial Graph Conw.
Global Aggregator
Fully Connected Clazsifier
GNN-ESR
GNN-ESR with pooling layers
Figure 1:
The red box demonstrates GNN Equipped with Spatial Representation (GNN-ESR).
Matrix E is the matrix of node embedding vectors and F is the matrix of node labels/atributes. The large black box depicts GNN which the proposed graph pooling layer utilized. In the presented numerical experiments, we set k 1, k2 2. K3 = 2, and hy 1, i.c., the GNN-ESR composed of three spatial convolution layers and the GNN-ESR with graph pooling includes one graph hownlsnnpling layer and two convolution layers are placed next to the pooling layer.
feature vectors the feature space, Accordingly, the spatial distribution the local feature vectors of the two classes of the graphs are indistinguishable.
Table 1: Classification accuracy while nodes and edges not labeled/attributed Both the GNN and the GNN-ESR are composed of three spatial convolution layers and a global max pooling layer.
PROTEINS
NCII
DD
ENZYM
SYNTHIE
HLLD
CNLC
CNC
GNN
76.87
69.09
75.68
43.30
67.75
54.24
37.33
36.40
14.95
13.47
+3.45
15.27
12.44
14.15
13.78
14.41
GNN-ESR
79.47
73.72
79.77
53.51
71.15
99.10
98.18
99
14.11
+2.36
+2.65
#3.63
+2.54
+0.88
1.05
+0.71
Improvement
3.38 %
6.7%
5.40 %
23.5 %
5.01 %
79.4 %
156.1 %
179.6 %
PROPOSED APPROACH
In section it was shown that the GNN can fail to infer the topological structure of the graph when the local structures in the graph are similar. The GNN is not aware of the location of each node in the global structure of the graph and it maps all the nodes whose corresponding local structures are similar same/close points in the feature space. This was the main reason that the GNN failed to learn to perform the task described in Section Ideally, if the extracted feature vector for each node function of its location in the graph, the nodes are mapped to different points (corresponding to their locations) in the feature space and the GNN can distinguish the graphs via analyzing the spatial distribution of the extracted local feature vectors. Accordingly, we propose an approach using which the extracted feature vectors depend the location/role of the nodes in the global structure of graph. Another motivation for the proposed approach is the remarkable success of the neural networks in analysing point-clod data (Qi al. 2017a). In point-cloud data, each data point is corresponding to point on the surface of the object and the location of each point in the 3D space is included the feature vector which represents each point of the surface. The neural networks which process the point-cloud representation yielded the state-of-the- performance in the 3D vision tasks Qi al. 2017b)
As another example, note the last three columns of Table which are corresponding to three classification tasks described in Section 5 The second row shows the accuracy of GNN these tasks. In all the three tasks, the performance of the GNN comparable random guess.

---

Under review as a conference paper at ICLR 2020
In order to include the locations of the nodes in the extracted local feature vectors, first have to define a representation for the location of each node. Suppose that vector e; E Rd in the de- dimensional Euclidean space contains the information about the location of the 2th node. Evidently, the 7th node and the jth node are close to each other on the graph, e; and ej should be close to each other in the continuous space and vice versa. Interestingly, graph embedding method can perfectly provide the location representation vectors {= Graph embedding maps each node to a vector the embedding space such that the distance between two points in the embedding space is proportional to the distance of the corresponding nodes on the graph. Accordingly, in order to make the extracted local feature vectors a function of the role of the nodes in the structure of the graph, we propose the approach depicted by the red box in Figure [ The matrix F E Raxdy represents the node labels/attributes and E Randd denotes the matrix of the embedding vectors obtained by graph embedding method (e.g.. DeepWalk). The red box represents GNN Equipped with the Spatial Representation (GNN-ESR). The GNN-ESR leverages both the node labels/attributes and the node embedding vectors extract the local features. Accordingly, the GNN-ESR is aware of the locations of the nodes and the distance between different nodes and it does not map nodes whose corresponding local structures GNN-ESR provides a spatial distribution of the local feature vectors which the next layers use to infer the structure of the graph. For instance, in the example discussed in Section 3 the spatial distribution of the local feature vectors corresponding to two graphs in two different classes were indistinguishable. In sharp contrast, if the local feature vectors are extracted using the GNN-ESR, they can build two/three clusters in the feature space if the graph is composed of two/three clusters. Accordingly, the distribution of the feature vectors makes the two classes distinguishable.
similar to the same feature vector. The convolution layers of the
Algorithm Node Sampling Using the Geometrical Description of the Graph
Input. The matrix of embedding vectors E E Raad, and m as the number of sampled nodes. O. Initialization. Sample index k from set { randomly and initialize set I, {R}
1. Repeat m times: Sample the next embedding vector such that it has the maximum distance to the sampled embedding vectors, i.e., append is to set I, such that
k = arg max (min ((lle, e,1la)jer.))
2. Output: I, contains indexes of the sampled nodes.
4.1 GRAPH POOLING VIA DATA POINT SAMPLING
One of the main challenges of extending the architecture of the CNNs to graphs is to define a pooling function which is applicable to graphs. In this section, the proposed graph pooling method is presented which utilizes the geometrical representation of the graph. The proposed method is composed of two main steps: node sampling and graph down-sampling
Node Sampling: It is not straightforward to measure how accurate a sub-sampled graph represents the topological structure of the given graph. Graph embedding encodes the topological structures of the graph in the spatial distribution of the embedding vectors. Accordingly, the node sampling prob- lem can be simplified into a data point sampling problem. Since the distribution of the embedding vectors represents the topological structure of the graph, we define the primary aim of the proposed pooling function to preserve the spatial distribution of the embedding vectors.
Data point sampling is a well-know problem in big data analysis (Halko et al. 2011 known as col-
umn/row sampling problem. A simple method is to perform random data point sampling. However, if the distribution of the data points is sparse in some region of the space, random sampling might not be able capture the spatial distribution of the data points. Most of the existing sampling methods aim at finding a small set of informative data points whose span is equal to the row-space of the data. However, preserving the row-space of the data is not necessarily equivalent to preserving the spatial distribution of the rows (Rahmani & Atia, 2017). Define (e. (e.)iez, as the set of sampled embedding vectors where Z, is the set of the indexes of the sampled embedding vectors. We define the objective of the sampling method as
min Z
(min ||c - csllphsez.)
subject to
[Zg = m.
(3)
5

---

Under review as a conference paper at ICLR 2020
where [Z,] is the cardinality of I.. The minimization problem samples embedding vectors such that the summation of the distances between the embedding vectors and their nearest sampled embedding vector is minimum. This minimization problem is non-convex and it is hard to solve. We propose Algorithm which uses the farthest data point sampling and provides a greedy method to find the sampled data points. Algorithm 1 samples the first embedding vector randomly. In the subsequent steps, the next embedding vector is sampled such that it has the maximum distance to the previously sampled embedding vectors. Accordingly, in each step the embedding vectors which are not close to sampled ones are targeted and gradually the sampled embedding vectors cover the distribution of all the embedding vectors. The computation complexity of Algorithm 1 O n de).
Although Algorithm 1 starts from randomly chosen embedding vector, this random choice does not cause variance at test time. Algorithm uses farthest data point sampling and the sampled embedding vectors finally cover the spatial distribution of all the embedding vectors (independent from the starting point). Moreover, one can choose the first embedding vector in a deterministic way. For instance, one candidate could be the embedding vector which is the closest vector to the mean of all the embedding vectors.
Graph Down Sampling: Define X E Rexd as the matrix of feature vectors (Figure 1) and define X, and A, as the matrix of feature vectors and the adjacency matrix of the sub-sampled graph. The sub-sam sam-sa adjacency matrix is obtained via sampling the columns and rows of A corresponding to the indexes in I,, We present two methods to obtain X,- Method I: Sample the rows of X corresponding the indexes in Ig. In other word,
X, x,=X,,
(4)
Method 2: In (4), the feature vectors of the unsampled nodes are discarded. Thus, some useful information could be lost during the down-sampling step. In the second method, we utilize the rows of X corresponding to the sampled indexes pivotal feature vectors and all the feature vectors aggregated around them using the attention technique (Xu et al., 2015). Define P e R as the matrix of pivotal feature vectors equal to P XI, which is equivalent the matrix of the sub- sampled feature vectors in Method 1. Using the pivotal feature vectors, we define m assignment vectors {q: E | as follows
q. = softmaaxxx p!')
(5)
where p; is the tth row of P. The vector q, is an attention vector which represents the resemblance between all the feature vectors and the :th pivotal vector. The attention vector qi is used to aggregate the feature vectors of X and obtain the 7th feature vector of the sub-sampled graph as follows
X 9 X,
(6)
where X,; is the 1th row of X..
Remark 1. If the nodes of the given graph are sparsely connected, the down-sampled graph can be disconnected graph. Define A, E A', If the distance between the 5th node and the t node is less than r + 1, Ar(j,) k) is non-zero. Therefore, if we down-sample A, to obtain the adjacency matrix the sub-sampled graph, two sampled nodes are connected if their distance is less than r+1. In the presented experiments, we down-sized A to oblain A.. In most of the graph classification applications, the size of the graphs is not large. However, if in a specific application the size of the graphs is large, the computation of A (for k 2 2) could require large volume of memory. In this scenario, one can simply down sample the adjacency matrix A and find the disconnected nodes and subsequently connect each disconnected node to its nearest sampled node (nearest according to the original graph). In addition, if we use A & to obtain the down sampled adjacency matrix and the obtained adjacency matrix is dense, one can sparsify the matrix by applying proper threshold to the values of the down sampled adjacency matrix. In the presented experiments, we did not face this problem and we used the exact down sampled version of A3.
Remark 2. We presented two methods to obtain X., In the presented experiments, we used both of them to obtain X.. The final X, was obtained as a convex combination of them.
NUMERICAL EXPERIMENTS
First we focus demonstrating the significance of equipping the GNN with the spatial represen- tation. Subsequently, the proposed pooling method (Spatial Pooling) is compared with the existing graph pooling methods.

---

Under review as a conference paper at ICLR 2020
Table 2: Classification accuracy when the node labels included.
PTC
PROTEINS
DD
ENZYM
SYNTHIE
NLC
MDC
GNN
77.44
80.01
82.90
61.66
67.75
90.33
86.44
+6.33
+3.57
=2.70
+4.68
+3.436
#2.17
22.94
GNN-ESR
77.64
80.54
83.33
69.16
71.15
100
97.50
+6.89
+3.17
=3.18
+4.54
#2.54
=0
#1.64
Improvement %
0.25
0.66
0.51
12.17
5.01
10.70
12.80
(a)
(b)
Part (a): This part represents graphs. Each circle represents cluster of nodes. The clusters in the right graph form a loop but in the left graph they do not. Part (b): Each circle represents a cluster of nodes. This graph composed of 11 clusters and the clusters form 3 loops. The task is to count the number of loops made by the clusters.
Figure 2:
Each circle represents cluster and both graphs composed of clusters. A white cluster means that the labels of its corresponding nodes are equal to and black means they are labeled O. In the NLC task, the neural network is trained count the number of white clusters. In the MDC, the neural network is trained to check if the diagonal clusters are labeled similarly. A pair of clusters are called diagonal clusters if they are in the maximum distance from each other. In the left graph, the labels of one pair of diagonal clusters are not equal. In the right graphs, the labels of all the diagonal clusters are equal.
Figure 3:
The structure of the basis neural network: In the presented experiments, GNN-ESR indicates the neural network depicted by the red box in Figure T with k and h 2. The dimensionality of the output of all the convolution layers is equal to 64. The functionality of each convolution layer can be written (1) where f(.) the Relu function followed by Batch- normalization (Ioffe & Szegedy) 2015). The output of all the convolution layers are concatenated (Xu et al.) 2018) to obtain the global representation of the graph and the element- wise max function used the global aggregator. The fully connected classifier is composed of three fully connected layers. The first two layers of the fully connected classifier are equipped with dropout (Srivastava et al. 2014)) ( ddrooot probability equal to 0.5) and batch-normalization. In the presented tables, GNN indicates graph neural network similar to the GNN-ESR while not provided as an input.
The input and the optimizer: The Deep-Walk graph embedding method (Perozzi al. 2014) was used to embed the graphs and the dimension of the embedding vectors is equal to 12. The length of the random walks is determined max (4, min(n/10, 10, 10)) where is the number of the nodes.
All the neural networks were similarly trained using the Adam optimizer (Kingma & Ba (015). initialized 0.005 and was reduced to 0.0005 during the training process. Following the conventional settings, we perform 10-fold cross validation (Zhang et al. 2018). We refer the reader (Kersting al. 2016) for complete description of the used real-world datasets. The size of each synthetic dataset equal to 1000.
The learning

---

Under review as a conference paper at ICLR 2020
5.1 ANALYZING ANLABELED/NON-ATTREE
GRAPHS
In this section, we consider graphs whose nodes are not labelcd/atrriuted. In some of the utilized real datasets, the nodes are labeled/attributed which are discarded in this experiment to examine the ability of the neural networks in inferring the topological features of the graphs in the absence of the labels/attributes. First we describe the designed synthetic graph classification tasks.
High Level Loop Detection (HLLD): In this task, the generated graphs are composed of 3 to 6 clusters (the number of clusters are chosen randomly per graph). Each cluster composed of 20 to 45 nodes (the number of nodes are chosen randomly per cluster). Each node in a cluster is connected to other nodes in the same cluster. In addition, two clusters are connected, 3 nodes of one cluster densely connected to 3 nodes of the other cluster. In the generated graphs, the consecutive clusters are connected. The classifiers are trained to detect if the clusters in a graph form a loop. Obviously, there are many small loops inside each cluster. The task is to detect if the clusters form a high level loop. Accordingly, this task is equivalent to a binary classification problem. Part (a) of Figure 2 shows an example of the HLLD task.
Count Number of Clusters (CNC): In this task, the graphs are similar to the graphs in the HILD task. However, the objective of the CNC task is to count the number of clusters. The generated graphs composed of 3 to 6 clusters. This task is equivalent to a classification task with four classes.
Count the Number of the Loops of Clusters (CNLC): In this task, the generated graphs contain several clusters and the clusters form multiple loops. For instance, the graph depicted in Part (b) of Figure consists of 11 clusters and the clusters form form 3 loops. In this experiment, the clusters can form 2 to 4 loops and each loop is formed with 3 to 5 clusters. The number of clusters in each loop is chosen randomly per loop. The objective of this task is to count the number of the loops. Thus, this task is equivalent to a graph classification task with three classes.
Table 1 shows the classification accuracy of a simple GNN and the GNN-ESR. The last three columns show the performance with the synthetic datasets. One can observe that the GNN failed to learn to perform the synthetic tasks. The main reason is that in the synthetic tasks, the local structure corresponding to all the nodes are similar and the convolution layers map all the nodes to similar vec- tors in the feature space. Thus, the GNN cannot extract discriminative features from the distribution of the local feature vectors. In sharp contrast, the GNN-ESR is aware of the differencess/imilartinn between the nodes and it does not necessarily map them to similar feature vectors when the nodes are not close to each other on the graph. The results show that the GNN-ESR successfully extracts discriminative features from the distribution of the extracted local feature vectors. Moreover, the re- sults with real datasets demonstrate that the proposed approach significantly (up to 23 %) improves the classification accuracy. The spatial representation makes the GNN-ESR aware of the difference between the nodes (although they are not labeled) and it paves the way for the GNN-ESR to extract discriminative features from the distribution of the embedding vectors.
5.2 ANALYZING LABELED GRAPHS
This experiment similar to the previous experiment but the node labels are included. We use the real datasets and the following synthetic tasks.
Number of Labeled Clusters (NLC): The graphs in this task are similar the graphs in the CNC task. Each graph is composed of 6, 7, or 8 clusters. The consecutive clusters are connected and they form loop. The labels of the nodes are binary (0 or 1) and all the nodes in the same cluster are labeled similarly. The task is to count the number of clusters whose nodes are labeled 1. There are classes of graphs, i.e., the number of clusters which are labeled are equal to 2, 3, 4, or 5. Figure 3 shows an example of this task.
Match the Diagonal Clusters MDC: In this task, each graph is composed of 6, 8, or 10 clusters and the clusters form loop. The labels of the nodes are binary and all the nodes in cluster are labeled similarly. The task is to check all the pairs of diagonal clusters are labeled similarly. A pair of clusters are called pair of diagonal clusters if they in the maximum distance from each other. Therefore, the MDC task is equivalent to a binary classification task. Figure 3 shows an example of this graph classification task.
8

---

Under review as a conference paper at ICLR 2020
Table 2 shows classification accuracy with different datasets. One can observe that even when the nodes are labeled, the difference between the performances is significant for most of the datasets. The main reason is that the spatial representation makes the neural network aware of the differences between the nodes and the neural network leverages both the node labels and the node embedding vectors to extract discriminative features.
5.3 GRAPH POOLING
In this experiment, the proposed graph pooling method (Spatial Pooling) is compared with some of the recently published pooling algorithms. In all the neural networks, the described GNN-ESR is used to extract the local feature vectors. Similar to the architecture depicted in Figure| I the pooling layer is placed next to last convolution layer of the GNN-ESR. Since the graphs in the datasets are not large graphs (mostly less than 100 nodes), one down-sampling layer was used.
implemented after the down-sampling step. Define Y E Rax 192 as the concatenation of the outputs of all the convolution layers before the pooling layer (three convolution layers) and define y R 192 as the aggregation of these feature vectors (by the element-wiss max function). Similarly, define Y, E Rmmx128 as the concatenation of the outputs of all the convolution layers after the pooling layer and define Ys R 121 similar to y. The final representation of the graph is defined as the concatenation of y and ys and it is used as the input of the final classifier. We chose m min max(5, n/4)).
Spatial Pooling: Two spatial convolution layers
Diff-Pool (Ying et al. 2018): : This method was implemented according to the instructions in Ying et al., 2018). Two spatial convolution layers were placed after the down-sizing step. The final representation of the graph was obtained similar to the procedure used in Spatial-Pooling.
Rank-Pool. (Gao & Ji. 2019 Lee et al., 2019): Similar to the other pooling methods, one down-sampling layer was used and two spatial convolution layers were implemented after the down-sizing step. The number of sampled nodes was chosen similar to the proposed method.
Sort-Node (Zhang et al. 2018): Similar to the implementation described in (Zhang et al., 2018) and its corresponding code, 30 nodes were sampled to construct the ordered sequence of the nodes.
Table 3: Classification accuracy of the GNN-ESR with different pooling methods.
MDC
PROTEINS
DD
ENZYM
SYNTHIE
Global Max-Poooing
97.50 11.64
80.54 #3.17
83.33 33.18
69.16 #4.54
71.15 #2.54
Spatial-Pooling
98.33 +0.66
80.72 +3442
83.52
2.35
71.33
14.42
72 2.87
Sort-Pooling
70 +5.25
80.54 +4.56
82.39
-2.51
63.16
+3.68
67.75 +3.05
Diff-Pool
97.8 #1.46
80.45 13.36
84.36
2.66
70.33
15.26
71.75 13.36
Rank-PooL
97.66 =123
80.72 +3112
83.67
33.8
67.5 #7.68
71.5 #2.78
Table 3 shows the accuracy of the GNN-ESR with different pooling methods. One can observe that Opatial-Pooling achieves higher or comparable results on all the datasets. On the MDC dataset, Spaatal-PPoling outperforms the other methods and on ENZYM and SYNTHIE datasets, it slightly outperforms Diff-Pool. The Diff-Pool method also achieves notable performance on most of the datasets. The feature vectors which Diff-Pool uses to down-size the graph fixed. In contrast, the way the proposed approach down-sizes the graph depends on the topology of the graph not set of fixed cluster centers. One can observe that the accuracy of Sort-Pool is significantly less than the accuracy of Spatial-Pooling and Diff-Pool with the MDC dataset. The main reason is that Sort- Pool sorts the nodes Iddimensional array. The placement of the nodes in a 1-dimensional array leads to loosing important information about the structure of the graph. An observation one can make by studying the results is that the performance of the GNN-ESR is close to the performance of the GNN-ESR with the pooling layers. In contrast, the performance of simple GNN with the pooling layers can be notably higher than the performance the GNN (Yanardag & Vishwanathan, 2015). For instance, Table 4 shows the performance of the neural networks with and without the pooling layers. One can observe that the performance of the GNN equipped with the pooling layer is notably higher than the performance of the GNN on the MDC and the ENZYM datasets. In contrast, the difference between the performances reported in the third and the forth rows is lower. Another predictable point that Tables 4 makes is that the pooling layer cannot make the GNN able to learn

---

Under review as a conference paper at ICLR 2020
to perform the CNC task or the HLLD task (and also the CNLC task). In these tasks, the neural network should be able to distinguish the nodes to be able to infer the structure of the graph.
Table 4: Classification accuracy of the neural networks with and without the pooling layer.
MDC
CNC
HLLD
ENZYM
SYNTHIE
GNN
86.44
36.40
54.24
61.66
67.75
GNN Diff-PPol
95.55
36.51
56.33
69.49
67
GNN-ESR
97.50
99
99.10
69.
71.15
GNN-ESR + Diff-Pool
97.8
100
100
70.33
71.75
6 CONCLUSION
An important shortcoming of the GNN was discussed. It was shown that if the nodes/edges of the given graph not labeled/attributed the labels/attributes do not make the GNN aware of the role of the nodes in the structure of the graph, the GNN can fail to infer the topological structure of the graph. Motivated by the success of the deep networks in analyzing point-cloud data, we proposed an approach in which a geometrical representation of the graph is provided to the GNN. The geo- computed by a graph embedding method which encodes the topological structure of the graph into the spatial distribution of the embedding vectors. We showed that the proposed approach significantly empowers the GNN via analyzing its performance on a diverse set of real and synthetic datasets. Moreover, the spatial representation was utilized to simplify the graph down-sampling problem and a novel graph pooling method was proposed.
metrical representation
REFERENCES
Amr Ahmed, Nino Shervashidze, Shravan Narayanamurthy, Vanja Josifovski, and Alexander J Smola. Distributed large-scale natural graph factorization. In International Conference on World Wide Web (WWW), pp. 37 48, 2013.
James Atwood and Don Towsley. Diffussion-oonvoluttinaal neural networks. In Advances in Neural Information Processing Systems (NIPS), pp. 9993-2011, 2016.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in Neural Information Processing Systems (NIPS), pp. 585-591, 2002.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pieree Vandergheynst. Geomet- ric deep learning: going beyond Euclidean data. IEEE Signal Processing Magazine, 34:18-42, 2017.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In International Conference on Learning Representations (ICLR), 2014.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. ACM International on Conference on Information and Knowledge Man- agement (CIKM), pp. 891-900, 2015.
Diane Cook and Lawrence B Holder. Mining graph data. John Wiley & Sons, 2006.
Siamak Zamani Dadaneh and Xiaoning Qian. Bayesian module identification from multiple noisy networks. EURASIP Journal Bioinformatics and Systems Biology, 2016:5, 2016.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances Neural Information Processing Systems (NIPS), pp. 3844-3851 2016.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems (NIPS), pp. 2224-222222 2232,, 2015.
10

---

Under review as a conference paper at ICLR 2020
Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. Splinecnn: Fast geometric deep learning with continuous b-spline kernels. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2018..
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Bun-Hur. Protein interface prediction using graph convolutional networks. In Advances in Neural Information Processing Systems (NIPS), pp. 6530-6539, 2017. 2017.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In International conference on machine learning (ICML), pp. 2083-2092, 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neu- ral message passing for quantum chemistry. In International Conference on Machine Learning (ICML), pp. 1263-1277 2017.
lan Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 855- 864, 2016.
Nathan Halko, Per-Gunnar Martinsson, and Joel Tropp. Finding structure with randomness:
Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, 53: 217-288, 2011.
William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 40:52-74, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp- 770-778, 2016.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. CoRR, 506.05666, 2015.
Keith Henderson, Brian Gallagher, Tina Eliassi-Rad, Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra, Christos Faloutsos, and Lei Li. Rolx: structural role extraction & mining in large graphs. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge dis- covery and data mining, pp. 1231-1239 ACM, 2012.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference Machine Learning (ICML), pp- 448-456 2015.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. URL BtR/htttp:///rapkeemee cs tu- dortmund.
de
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel. Neural relational inference for interacting systems. In International Conference on Machine Learning (ICML), pp- 2693-2702, 2018
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep volutional neural networks. In Advances in neural information processing systems (NIPS), pp- 1097-1105, 2012.
11

---

Under review as a conference paper at ICLR 2020
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International confer- ence on machine learning (ICML), pp. 3734-3743, 2019.
Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph con- volutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67:97-109, 2017.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations (ICLR), pp. 2224-2232, 2016.
Enxhell Luzhnica, Ben Day, and Pietro Lio. Clique pooling for graph classification, arXiv preprini 2019.
Dang Nguyen, Wei Luo, Tu Dinh Nguyen, Svetha Venkatesh, and Dinh Phung. Learning graph representation via frequent subgraphs. In SIAM International Conference on Data Mining, pp- 306-314, San Diego, USA, 2018.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In International conference on machine learning (ICML), pp. 2014-2023, 2016.
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserv- ing graph embedding. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 1105-1114, 2016.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social represen- tations. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 701-710, 2014.
Charles Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. sets for 3d classification and segmentation. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 77-85 85, 2017a
Pointnet: Deep learning on point
Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas. Pointnet++: Deep hierarchical feature learning on point sets in a metric space. In Advances in Neural Information Processing Systems (NIPS), pp. 5099-5108, 2017b.
Mostafa Rahmani and George Atia. Spatial random sampling: structure-preserving data sketch- ing tool. IEEE signal processing letters, 24:1398-1402. 2017.
Sam T Roweis and Lawrence Saul. Nonlinear dimensionality reduction by locally linear embed- ding. science, 290:2323 2000.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607, 2018
Martin Simonovsky and Nikos Komodakis. Dynamic edgeconditioned filters in convolutional neural networks on graphs. Conference on Computer Vision and Pattern Recognition (CVPR), pp. 29- 38, 2017.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way prevent neural networks from overfitting. The journal of machine learning research, 15:1929-1958, 2014.
Antoine J-P Tixier, Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. Graph classification with 2d convolutional neural networks. In International Conference on Artificial Neural Networks (ICANN), pp. 578-593, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. CoRR, abs/1710. 10903, 2017.
12

---

Under review as a conference paper at ICLR 2020
Saurabh Verma and Zhi-Li Zhang. Graph capsule convolutional neural networks. (bbs/180500800, 2018.
CoRR,
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 1225-1234, 2016.
Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. In International conference machine learning (ICML), pp. 2048-2057, 2015.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. arXiv preprint arXiv:1806.033536 2018.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 1365-1374, 2015.
Rex Ying. Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, Jure Leskovec, Joseph M Antognini, Jascha Sohl-Dickstein, Nima Roohi, Ramneet Kaur, al. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems (NeurIPS), pp. 4805-4815 2018.
Muhan Zhang. Zhicheng Cui, Marion Neumann, and Yixin Chen. end-to-end deep learning architecture for graph classification. In AAAI Conference on Artificial Inteligence (AAAI), pp. 4438 4445, 2018
13


Reviews:
[{"review_id": "ryxY7TkRtH", "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": "The authors propose in this paper to complement the node attributes in a graph with vectors obtained using a graph embedding algorithm. More precisely, they propose a graph neural network that apply several layers of graph convolution in parallel to the node attributes and to the embedding, then takes an average of the result, which is fed to another series of graph convolution. This is combined with some form of sampling which strongly resembles median based quantization but is solved with some basic heuristics and without acknowledging the resemblance (I might be missing something). \n\nGlobally, I find this paper very unclear. The authors are mixing references to graph convolution for fixed graph structure with references about general graph neural networks. Their goal is not clearly stated from the beginning and in many places the discussion lacks of focus and is difficult to follow. In the experimental evaluation several values are very close one to another and the statistical significativity of the differences is not assessed. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "SylvKD2v9S", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "============ After rebuttal ============\nI thank the authors for carefully discussing the points of my review. I have upgraded the score to marginal acceptance (6).\n\n============ Original review ============\n\nIn this paper, the authors identify a shortcoming of existing GNN architectures for graph classification tasks -- specifically, the fact that, in the featureless regime, the graph convolutional layers rely on propagating very rudimentary structural information, making it hard (or impossible) to distinguish graphs with similar local structure. To fix the problem, the authors propose to augment the input feature space with graph-structural embeddings (computed by an algorithm like DeepWalk), and processing those in parallel with any other input features available.\n\nOn existing real-world datasets, as well as synthetic datasets carefully constructed to illustrate this phenomenon, the proposed pipeline matches or exceeds the version without the structural embedding inputs. Further, the authors note that the structural embeddings could be used to propose a novel graph pooling method -- one which attempts to preserve as diverse structural feature sets as possible. It is shown that this method is competitive to other differentiable pooling methods, like DiffPool and Graph U-Nets. Lastly, the authors demonstrate that the addition of pooling layers does not help baseline GNNs on the synthetically constructed tasks, as the fundamental issue of handling similar local structures is still not addressed.\n\nI believe that the paper clearly exposes and proposes a nice idea which could hold great potential, and which can be useful to graph representation learning practitioners. I am particularly happy with the design of the synthetic experiments. However, I find that, in its current form, the manuscript is narrowly below the bar for a venue like ICLR.\n\nComments:\n* The observation that existing GNN layers may struggle with distinguishing featureless graphs is not particularly novel. It's largely the centerpiece of the (already cited) work of Xu et al. (ICLR 2019), and I believe that its relevance and relation to the authors' work should be better stressed in the related work section.\n\n* The usage of DeepWalk to encode structural information (and even to be used as initial features for a GNN) is, ultimately, also not necessarily a novel idea. At least, it's something that should be clear to any expert GNN practitioner already: if useful features are missing from the graph, a method like DeepWalk (if applicable; see below!) could be a go-to method for obtaining such features. In its current form, I don't see that the authors are proposing anything substantially architecturally novel, and their contribution is primarily on the data/feature engineering side.\n\n* The above point is not necessarily problematic, but if the aim is to stress the importance of the architectural novelties of the proposed GNN-ESR model more, and not just the added features, I would recommend the authors to perform a few ablations: e.g. seeing how well would processing a concatenation of E and F in the same GNN layer perform.\n\n* Many of the standard graph classification datasets are known to be noisy and unreliable (see e.g. Luzhnica, Day and Liò (ICML GraphReasoning Workshop 2019). This means that it is a must to report error bars of the cross-validation experiments. It's hard to say that many of the improvements depicted here are statistically significant otherwise.\n\n* I have concerns about the computational complexity, or even feasibility, of using DeepWalk-like methods in the general case, e.g. for node classification. Namely, if such layers are to be applied in inductive settings (with nodes gradually added to graphs), one would require re-running DeepWalk every time a new node is added. The authors should comment on this adequately, and perhaps discuss the feasibility of other unsupervised embedding techniques for obtaining the e-vectors -- such as VGAE (Kipf and Welling, NIPS BDL 2016), GraphSAGE (Hamilton et al., NIPS 2017), Graph2Gauss (Bojchevski and Günnemann, ICLR 2018) or DGI (Veličković et al., ICLR 2019).\n\n* While I find the proposed pooling method interesting (and more grounded in the graph's structural features than other proposed works), I find that there are many potential limitations to be discussed. For example, the fact that we start from a random first index means that we cannot rely on the obtained pooling to always be the same -- could this cause undesirable variance at test time? Furthermore, the downsampling from A^3 is a sure-fire way to obtain dense graphs after the first pooling -- potentially severely limiting the applicability of the method for large graphs. In my opinion, the authors should appropriately comment on these and perform ablations against pooling with A and A^2 (as was done in Graph U-Nets). It should also be interesting to note that there exist other structurally-informed pooling methods; see e.g. the Clique pooling method from Luzhnica, Day and Liò (ICLR RLGM 2019).\n\nGiven all of the above, I recommend (marginal) rejection, but am open to improving my score if the authors appropriately address the aforementioned comments.\n\nSome minor comments and thoughts:\n* The paper has several typos and grammar issues, and a typo pass is highly encouraged to aid clarity;\n* The \"attention mechanism\" of Equation (5--6) seems to be nonparametric? If so, it might be interesting to compare with a version that features learnable queries, e.g. using the Transformer-style attention.\n* In Equation (3), should the first min actually be a max? As we're maximising the overall minimum distances between topological features.\n* I'm not sure that the paper is anywhere clear on what's the exact GNN layer being used. Could this be clarified and made more explicit? It's critical to reproducibility.\n* I find it curious that the authors needed to resort to using batch normalisation---I usually found it to either have no meaningful effect on the results on the graph classification benchmarks, or it made results worse. Can the authors comment on this decision?\n* The idea to concatenate output of all convolutional layers is heavily resembling Jumping Knowledge networks (Xu et al., ICML 2018), and I believe they should be appropriately cited.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "S1xEfDsJqB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this work the authors point out an issue related to graph neural networks. Specifically, if two nodes, that may be far apart in the graph, may be represented as (almost) the same vector. This is simply because when no features/labels are associated with nodes, and the local structure around those two nodes is very similar then the local aggregation of information will result in a similar representation.  Therefore the authors introduce an embedding first of the graph in the Euclidean space using DeepWalk and then use this embedding in combination with the design of a CNN. The authors propose a pooling method that outperforms several state-of-the-art pooling techniques on real data. Overall, the empirical results are supportive of the fact that the proposed method can help improve the performance of GNNs. \n\nOverall I found the results of this paper to be weak, but nonetheless the paper is well-written and contains some interesting ideas. Hence my rating. Some questions follow. \n\n- While the authors call this as an \"issue\" it is more like a feature of these methods.  For instance, in \"RolX: Structural Role Extraction & Mining in Large Graphs\" by Henderson et al. this \"issue\" could turn out to be an interesting feature of the GNNs in the sense that these nodes may have a similar (structural) role.  It would be nice to have a short discussion related to this line of research in social networks' analysis. \n-  Some components of the CNN (e.g., node sampling) could be done using  well-developed tools for sampling matrices from numerical linear algebra, or by introducing some randomness when sampling a node as in kmeans++. \n- Graph downsampling appears to be an expensive operation. Can you please comment on the running times? The issue of scalability is not discussed, and the reader cannot easily infer to what sizes this method can scale up to. \n- Using other graph tasks, that are classical but also more challenging (e.g., learning 2-connected components of a graph just to mention something that comes up) would be interesting to see in Section 5.2.\n-  It would have been interesting to see the effect of the embedding step on the accuracy on the real data. E.g., using node2vec or standard spectral embeddings. \n\n\n[Edit: The authors have replied to my comments, and the other reviewers' comments in great detail. Therefore I upgrade my score.] ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors identify a limitation of aggregating GNNs, which is that global structure can be mostly lost. They propose a method which combines a graph embedding with the spatial convolution GNN and show that the resulting GNN can better distinguish between similar local structures. 

The reviewers were mixed in their scores. The proposed approach is clearly motivated and justified and may be relelvant for some graphnet researchers, but the approach is only applicable in some circumstances - in other cases it may be desirable to ignore global structure. This, plus the high computational complexity of the proposed approach, mean that the significance is weaker. Overall the reviewers felt that the contribution was not significant enough and that the results were not statistically convincing.  Decision is to reject.
Decision: Reject