Topology-Aware Pooling via Graph Attention
Authors: Hongyang Gao
Shuiwang Ji
Venue:  (2020)

Abstract: Pooling operations have shown to be effective on various tasks in computer vision and natural language processing. One challenge of performing pooling operations on graph data is the lack of locality that is not well-defined on graphs. Previous studies used global ranking methods to sample some of the important nodes, but most of them are not able to incorporate graph topology information in computing ranking scores. In this work, we propose the topology-aware pooling (TAP) layer that uses attention operators to generate ranking scores for each node by attending each node to its neighboring nodes. The ranking scores are generated locally while the selection is performed globally, which enables the pooling operation to consider topology information. To encourage better graph connectivity in the sampled graph, we propose to add a graph connectivity term to the computation of ranking scores in the TAP layer. Based on our TAP layer, we develop a network on graph data, known as the topology-aware pooling network. Experimental results on graph classification tasks demonstrate that our methods achieve consistently better performance than previous models.

Under review as a conference paper at ICLR 2020
TOPOLOGY-AWARD POOLING VIA GRAPH ATTENTION
Anonymous authors Paper under double-blind review
ABSTRACT
Pooling operations have shown to be effective on various tasks in computer vision and natural language processing. One challenge of performing pooling operations graph data is the lack of locality that is not well-defined on graphs. Previous studies used global ranking methods to sample some of the important nodes, but most of them are not able incorporate graph topology information in computing ranking scores. In this work, we propose the topology-awar pooling (TAP) layer that uses attention operators to generate ranking scores for each node by attending each node to its neighboring nodes. The ranking scores are generated locally while the selection is performed globally, which enables the pooling operation to consider topology information. To encourage better graph connectivity in the sampled graph, we propose to add a graph connectivity term to the computation ranking scores in the TAP layer. Based our TAP layer, we develop network on graph data, known as the topology-ave aware pooling network. Experimental results graph classification tasks demonstrate that methods achieve consistently better performance than previous models.
INTRODUCTION
Pooling operations have been widely applied in various fields such as computer vision (He et al. 2016; Huang et al. 2017). and natural language processing (Zhang et al. (015]) Pooling operations can effectively reduce dimensional sizes (Simonyan & Zisserman 2015) and enlarge receptive fields (Chen et al. 2016). The application of regular pooling operations depends on the well-defined spatial locality in grid-like data such as images and texts. However, it is still challenging to perform pooling operations on graph data. particular, there is no spatial locality or order information among nodes (Gao et al.] 2018). Some works try to overcome this limitation with two kinds of methods; those are node clustering (Ying et al. 2018) and primary nodes sampling (Gao Ji 2019) Zhang et al.] 2018). The node clustering methods create graphs with super-nodes by learning nodes assigmment matrix. These methods suffer from the over-fitting problem and need auxiliary link prediction tasks to stabilize the training (Ying al. 2018). The primary nodes sampling methods like top-k pooling (Gio & Ji 2019) rank the nodes in a graph and sample top-k nodes to form the sampled graph. uses small number of additional trainable parameters and is shown be more powerful (Gao & Jil 2019). However, the top-k pooling layer does not explicitly incorporate the topology information
graph when computing ranking scores, which may cause performance loss.
In this work, we propose a novel topology-aware pooling (TAP) layer that explicitly encodes the topology information when computing ranking scores. We use an attention operator to compute similarity scores between each node and its neighboring nodes. The average similarity score of node used as its ranking score in the selection process. To avoid isolated nodes problem in our TAP layer, we further propose graph connectivity term for computing the ranking scores of nodes. The graph connectivity term uses degree information as bias term to encourage the layer to select highly connected nodes to form the sampled graph. Based on the TAP layer, we develop topology-aware pooling networks for network embedding learning. Experimental results on graph classification tasks demonstrate that our proposed networks with TAP layer consistently outperform previous models. The comparison results between our TAP layer and other pooling layers based on the same network architecture demonstrate the effectiveness of our method compared to other pooling methods.

---

Under review as a conference paper at ICLR 2020
2
BACKGROUND AND RELATED WORK
In this section, we describe graph pooling operations and attention operators.
2.1 GRAPH POOLING OPERATIONS
The pooling operations on graph data mainly include two categories; those are node clustering and node sampling. DIFFPOOL (Ying et al. 2018) realizes graph pooling operation by clustering nodes into super-nodes. By learning assignment matrix, DIFFPOOL softly assigns each node to different clusters in the new graph with specified probabilities. The pooling operations under this category retain and encode all nodes information into the new graph. One challenge of methods in this category is that they may increase the risk of over-fitting by training another network to learn the assignment matrix. In addition, the new graph is mostly connected where each edge value represents the strength of connectivity between two nodes. The connectivity pattern in the new graph may greatly differ from that the original graph. The node sampling methods mainly select a fixed number & of the most important nodes to form new graph. In SortPool (Zhang et al. 2018), the same feature of each node is used for ranking and & nodes with the largest values in this feature are selected to form the coarsened graph. Top-k pooling (Gao & Ji 2019) generates the ranking scores by using a trainable projection vector that projects feature vectors of nodes into scalar values. nodes with the largest scalar values are selected to form the coarsened graph. These methods involve none or a very small number of extra trainable parameters, thereby avoiding the risk of over-fitting. However, these methods suffer from one limitation that they do not explicitly consider the topology information during pooling. Both SortPool and top-k pooling select nodes based on scalar values that do not explicitly incorporate topology information. In this work, we propose a pooling operation that explicitly encodes topology information in ranking scores, thereby leading to an improved operation.
2.2 ATTENTION OPERATORS
Attention operator has shown to be effective in challenging tasks in various fields such as computer
vision (Xu et al. 201 Lu et al. 2016 [L et al. 2018) and natural language processing (Malinowski
et al. 2018 Bahdanau al. 2015 Vaswani et al. 2017). Attention operator is capable of capturing long-range relationships, thereby leading to better performances (Wang et al. 2018). The inputs to an attention operator consist of three matrices; those are a query matrix Q E æd key matrix K E _Rdx,, and a value matrix V E _2xx". The attention operator computes the response of each query vector in Q by attending take weighted sum over value vectors in V. The layer-wist wise operation of an attention operation is defined as O = "softmax(K" Q). When the attention operator is applied to graph, each node only attends its neighboring nodes /Veličković et al., 2017). Self-attention can also produce an attention mask to control information flow on selected nodes in pooling operation (Lee et al. (201)). In our proposed pooling operation, we employ an attention operator to compute ranking scores that explicitly encode topology information.
all key vectors in K. It uses the resulting coefficient vector to
TOPOLOGY-AWARY POOLING LAYERS AND NETWORKS
In this work. we propose the topology-awar pooling (TAP) layer that uses attention operators encode topology information in ranking scores for node selection. We also propose a graph connectivity term in the computation of ranking scores, which encourages hetter graph connectivity in the coarsened graph. Based on our TAP layer, we propose the topology-aware pooling networks for network representation learning.
3.1 TOPOLOGY-AWARE POOLING LAYER
Pooling layers have shown to be important grid-like data with regard to reducing feature map sizes and enlarging receptive fields YYu & Koltun 2016 Carreira et al. (012). On graph data, two kinds of pooling layers have been proposed; those node clustering (Ying al. 2018) and primary nodes sampling (Gao & Ji. 2219 /Zhang et al. 2018). A primary nodes sampling method, known as top-k pooling (Gao & Jil 2019), uses projection vector generate ranking scores for each node in the
2

---

Under review as a conference paper at ICLR 2020
Similarity Scores
Ranking Scores
Node Sampling
0.37
0.46
0.53
0.29
0.52
0.21
0.51
0.36
(a)
(b)
(c)
(d)
Figure I: An illustration of the proposed topology awarr pooling layer that selects k 3 nodes. This graph contains four nodes, each of which has 2 features. Given the input graph, we firstly use an attention operator to compute similarity scores between every pair of connected nodes. Here, we use self-attention without linear transformation for notation simplicity. In graph (b), we label each edge by the similarity score between its two ends. Then we compute the ranking score of each node by taking the average of the similarity scores between it and its neighboring nodes. In graph (c), label each node by its ranking score and bigger node indicates a higher ranking score. By selecting the nodes with the k largest ranking scores, the selected graph is shown in graph (d).
graph. The graph is created by choosing nodes with k-largest scores. However, the sampling process relies on the projection vector and does not explicitly consider the topology information in the graph.
In this section, we propose the topology-aware pooling (TAP) layer that performs primary nodes sampling by considering the graph topology. In this layer, we generate the ranking scores based on local information. To this end, we employ an attention operator to compute the similarity scores between each node and its neighboring nodes. The ranking score for node i is the mean value of the similarity scores with its neighboring nodes. The resulting ranking score for a node indicates the similarity between this node and its neighboring nodes. If node has high ranking score, it can highly represent a local graph that consists the highest ranking scores, we can retain the maximum information in the sampled graph.
and its neighboring nodes. By choosing nodes with
Suppose there are N nodes graph G, each of which contains C' features. layer E, we use two matrices to represent the graph; those are the adjacency matrix (0) E N and the feature matrix x E RN The non-zero entries in (2) represent edges in the graph. The ith row in (() denotes the feature vector of node i. The layer-wise forward propagation rule of TAP in layer é is defined as
K x(O
ER-xCC
E = ( KT.
ER-
(2)
È E 10)
ERN
(3)
d Σ 10
ER-
(4)
J=1
Σラ= E.
8 sigmoid
ER
(5)
d
id. Ranking, (8);
ER*
(6)
A (f-1) 1) = (1) (idæ, idæ),
ER
(7)
X (f-1) (0 ( (iddx,))dia((Ce :)diag(s(ddx)))
*
(8)
where (00 E RCXC is a trainable weight matrix, A! is the jth column of matrix A (0) o denotes
the clement-wise matrix multiplication, E.y is the jth column of matrix E, A is the number of nodes selected in the sampled graph, and diag(-) constructs diagonal matrix using input vector as diagonal elements. Ranking, operator ranks the scores and return the indices of k-largest values in 8.
To compute attention scores, we perform a linear transformation on feature matrix x in Eq. 1 which results in the key matrix K. We use the input feature matrix as the query matrix. The similarity
3

---

Under review as a conference paper at ICLR 2020
Inputs
GCN
GCN
GCN
MLP
TAP
TAP
An illustration of the topology-awe aware pooling network. denotes the concatenation operation of feature vectors. Each node in the input graph contains three features. We use a GCN layer to transform the feature vectors into low-dimensional representations. We stack two blocks, each of which consists of GCN layer and TAP layer. A global reduction operation such as max-pooling is applied to the outputs the first GCN layer and TAP layers. The resulting feature vectors are concatenated and fed into the final multi-layer perceptron for prediction.
Figure 2:
score matrix is obtained by the matrix multiplication between X (f) and K in Eq. (2). Each value egj in E measures the similarity between node i and node j. Since E contains similarity scores for nodes that are not directly connected, we use the adjacency matrix A as mask to set these entries in E to zeros in Eq. 3 resulting in E. We compute the degree of each node in Eq. (4). The ranking score of node is computed in Eq. ( by taking the average of similarity scores between this node and its neighboring nodes followed by a sigmoid operation. Here, we perform element-wise division between two vectors. The resulting score vector is = [s1, $ sx]" where s; represents the ranking score of node i. Ranking, is an operator that selects k-largest values and returns the corresponding indices. In Eq. (6), use Ranking, select the k-most important nodes with indices in idn. Using idæ. we extract new adjacency matrix A (f+1) in Eq. 7 and new feature matrix x (f+1) in Eq. 8). Here, we use the ranking scores s sidx) as gates to control information flow and enable the gradient back-propagation for trainable transformation matrix w(() (Gao & Ji 2019
This method can be considered ranking scores are derived from the similarity scores of each node with its neighboring nodes, thereby encoding the topology information of each node in its ranking score. This can be considered as local voting process that each node gets its votes from the local neighborhood. When performing global ranking, the nodes that get the highest votes from local neighborhoods are selected such that maximum information in the graph can be retained. Figure [T provides illustration of our proposed TAP layer. Compared to the top-k pooling (Gao & Ji, 2019), our TAP layer considers topology information in the graph, thereby leading to better coarsened graph.
local-voting, global-ranking process. In our TAP layer, the
3.2 GRAPH CONNECTIVITY TERM
Our proposed TAP layer computes the ranking scores by using similarity scores between nodes in the graph, thereby regarding topology information in the graph. However, the coarsened graph generated by the TAP layer may suffer from the problem of isolated nodes. In sparsely connected graphs, some nodes have a very small number of neighboring nodes even only themselves. Suppose node only connects to itself. The ranking score of node is the similarity score to itself, which may result in high ranking scores in the graph. The resulting graph can be very sparsely connected.
To overcome the limitation of TAP layer and encourage better connectivity in the selected graph, we propose to add a graph connectivity term the computation of ranking scores. To this end, we use node degrees as an indicator for graph connectivity and add degree values to their ranking scores such that censely-connected nodes are preferred during nodes selection. By using the node degree as the graph connectivity term, the ranking score of node is computed as
Egg
d
8; sigmoid
d,
N
where de is the degree of node i, and À is a hyperparameter that sets the importance of the graph connectivity term to the computation of ranking scores. The graph connectivity term overcome the limitation of the TAP layer. The computation of ranking scores now considers nodes degrees and gives rise better connectivity in the resulting graph.
4

---

Under review as a conference paper at ICLR 2020
3.3 TOPOLOGY-AWARE POOLING NETWORKS
Based on our proposed TAP layer, we build a family of networks known as topology-aware pooling networks (TAPNets) for graph classification tasks. In TAPNets, we firstly apply graph embedding layer to produce ciw-dimensional representations of nodes in the graph, which helps to deal with some datasets with very high-dimensional input feature vectors. Here, we use GCN layer (Kipf) & Welling 2017) for node embedding. After the embedding layer, we stack several blocks, each of which consists of a GCN layer for high-level feature extraction and a TAP layer for graph coarsening. In the ith TAP layer, we use hyperparameter ((()) control the number nodes in the sampled graph. We feed the output feature matrices of the graph embedding layer and TAP layers to a classifier. Suppose we stack m blocks and all GCN and TAP layers output feature kcps. Given an input graph with the adjacency matrix A E TRN X and the feature matrix X E N our TAPNet outputs list feature matrices [Yo, Y 1,..., m) Here, Yo- E N x is the output of the graph embedding layer and Y; E R xk is the output of TAP layer in the vth block.
In TAPNets, we use multi-layer perceptron as the classifier. We first transform network outputs to one-dimensional vector. Specificity, the resulting vector [yd yf ......... VMl" where y, is transformed from Y,. Global max and average pooling operations are two popular ways for the transformation, which reduce the spatial size of feature matrices to using max and average functions, respectively. Recently, Xu et al. (2018) proposed to use the summation function that results in promising performances. In TAPNets,
concatenate transformation output vectors produced by the global pooling operations using max, averaging, and summation, respectively. The resulting feature vector is fed into the classifier. Figure illustrates sample TAPNet with two blocks.
3.4 AUXILIARY LINK PREDICTION OBJECTIVE
Multi-task learning has shown to be effective across various machine learning tasks (Ruder 2017).
can leverage useful information in multiple related tasks, thereby leading to better generalization and performance. this section, we propose add an auxiliary link prediction objective during training by using by-product of our TAP layer. In Eq. 2 we compute the similarity scores E between every pair of nodes in the graph. By applying an element-wiss wise sigmoid(.) on E, we can obtain a link
probability matrix E E NxN with each element énj measures the likelihood of a link between node i and node j. With the adjacency matrix A(), we compute the auxiliary link prediction loss as
lossauz
Σ
E
!!)
(10)
N2
where (:. -) is a loss function. Note that the adjacency matrix used as the link prediction objective is directly derived from the original graph. Since the TAP layer extracts sub graph from the original one, the connectivity between two nodes in the sampled graph is the same as that in the original graph. Compared to auxiliary link prediction in DiffPool (Ying et al., (0188) that uses the learned adjacency matrix as objective, our method uses the original links, thereby providing more accurate information.
EXPERIMENTAL STUDIES
In this section, we evaluate our methods and networks on graph classification tasks using bioinfor- matics and social network datasets. We conduct ablation experiments to evaluate the contributions of the TAP layer and each term in it to the overall network performance.
4.1 GRAPH CLASSIFICATION RESULTS ON SOCIAL NETWORK DATASETS
We conduct experiments on graph classification tasks to evaluate our proposed methods and TAP- Nets. We use 6 social network datasets; those are COLLAB, IMDB-BINARY (IMDB-B), IMDB- MULTI (IMDB-M), REDDIT-BINARY (RDT-B), REDDIT-MULTHE MULTI12K (RDT-MI2K) (Yanardag& & Vishwanathan 2015) datasets. Note that REDDIT datasets are popular large datasets used for network embedding learning in terms of graph size and number of graphs (Ying al. 2018 Xu al. 2018). Since there is feature for nodes in social networks,
(RDT-M5K) and REDDIT-
5

---

Under review as a conference paper at ICLR 2020
Table 1: Comparisons between TAPNets and other models such WL (Shervashidze al. 2011) and
PSCN (Niepert et al. 2016) in terms of graph classification accuracy (%) on social network datasets
including COLLAB, MMDB-BINAR, IMDB-MULTI, REDDIT-BINARE REDDIT-MULTIS and
datasets.
COLLAB
IMDB-B
IMDB-M
RDT-B
RDT-M5K
RDT-MI2K
# graphs
5000
1000
1500
2000
4999
11929
# nodes
74.5
19.8
13.0
429.6
508.5
391.4
# classes
5
I1
WL
78,9 1.9
73.8 1 3.9
50.9
3.8
81.0 + 3.1
52.5 + 2.1
44,4 + 2.1
PSCN
72.6 + 2.2
71.0
2.2
45.2 + 2.8
86.3 + 1.6
49.1 + 0.7
41.3 + 0.8
DGCNN
73.8
70.0
47.8
41.8
DIFFPOOL
75.5
47.1
g-U-Net
77.5 +
75.4 + 3.0
51.8 + 3.7
85.5 +
48.2 + 0.8
44.5 + 0.6
GIN
80.6
1.9
75.1 +
52.3 4 2.8
92.4
57.5
TAPNet (ours)
84.6 1 1.7
79.5
1
4.1
55.6 1
2.9
94.1 1 1.9
57.1 1 1.3
49.2 1 1.6
Table 2: Comparisons between TAPNets and other models in terms of graph classification accu- racy (%) on bioinformatics datasets including DD, PTC, MUTAG, and PROTEINS datasets.
DD
PTC
MUTAG
PROTEINS
# graphs
1178
344
188
1113
# nodes
284.3
25.5
17.9
39.1
# classes
2
2
2
WL
78.3 + 0.6
59.9 4.3
90.4 + 5.7
75.0 + 3.1
PSCN
76.3 + 2.6
60.0
4.8
92.6 + 4.2
75.9 = 2.8
DGCNN
79.4 1.
58.6 2.4
85.8 1 1.7
75.5
SAGPool
76.5
71.9
DIFFPOOL
80.6
76.3
g-U-Net
82.4 2.9
64.7 6.8
87.2 22 7.8
77.6 =
GIN
82.0 + 2.7
64.6 = 7.0
90.0 + 8.8
76.2 + 2.8
TAPNet (ours)
84.2 1 3.7
72.7 6.0
93.0 1. 5.8
78.9 1 4.2
we create node features by following the practices in (Xu et al. 2018). In particular, we use one-hot encodings of node degrees as feature vectors for nodes in social network datasets. To ensure fair comparisons, we do not use the auxiliary link prediction objective in these experiments. We provide more details about the experimental setups in the appendix.
We compare our TAPNets with other state-of-the-an models in terms of graph classification accuracy. The comparison results are summarized in Table T We can observe from the results that our TAPNets significantly outperform other models on most social network datasets by margins of 4.0%, 4.4%. 3.3%, 1.7%, and 2.1% % on COLLAB, and REDDIT-MULTH 12 datasets, respectively. The promising performances, especially large datasets such as REDDIT, demonstrate the effectiveness of our methods. Note that the superior performances g- U-Net (Gao & Ji 2019) show that our TAP layer can produce better-coarsened graph than that using the top-k pooling layer.
IMDE-MULTI, REDDIT-BINARY.
4.2 GRAPH CLASSIFICATION RESULTS ON BIOINFORMATICS DATASETS
We have shown the promising performances of our TAPNets on social network datasets. To fully evaluate our methods, we conduct experiments on graph classification tasks using 4 bioinformatics datasets; those are DD. PTC, MUTAG, and PROTEINS (Xu et al. 2018) datasets. Notably, nodes in bioinformatics datasets have categorical features. We compare our TAPNets with other state-of- the-art models in terms of graph classification accuracy without using auxiliary link prediction. The comparison results are summarized in Table 2 We can observe from the results that our TAPNets achieve significantly better results than other models by margins of 1.2%, 8.1%, 3.0%, and 2.7% on DD, PTC, MUTAG, and PROTEINS datasets, respectively. Notably, some bioinformatics datasets such as PTC and MUTAG are much smaller than social network datasets in terms of number of graphs and number of nodes in graphs. The promising results these small datasets demonstrate that our

---

Under review as a conference paper at ICLR 2020
(a) Input graph
(b) Graph by TAP w/o GCT
(c) Graph by TAP
Figure 3: Illustrations of coarsened graphs generated by TAP and TAP w/o GCT. Here, GCT denotes the graph connection term. The imput graph (a) contains 12 nodes. The pooling layers select nodes to form new graphs. The nodes that are not selected are colored black. The new graph in (b) generated by TAP w/o GCT is sparsely connected. The new graph generated by TAP is illustrated in (c), which is shown to be much better connected.
methods can achieve good generalization and performances without involving the risk of over-fitting. SAGPool (Lee et al. 2019) uses a GCN layer to compute ranking scores and a self-attention operator to generate mask control the information flow. Here, method employs attention operator to compute ranking scores that better encodes the topology information in the graph. The superior performances over SAGPool on DD and PROTHINS datasets demonstrate that our methods can better capture the topology information, thereby leading to better performances.
4.3 COMPARISON WITH OTHER GRAPH POOLING LAYERS
It may be argued that TAPNets achieve promising results by employing superior net- works. In this section, we conduct experiments on the same TAPNet architecture to compare our TAP layer with other graph pooling layers; those are DIFFPOOL. sort pooling, and top-k pooling layers. We denote the networks with the
Table 3: Comparisons between different pooling operations based on the same TAPNet architecture. Model
PTC
IMDB-M
RDT-B
Netdiff
70.9
54.9
92.1
Netsort
70.6
54.8
92.3
Netrop=
71.5
55.2
92.8
TAPNet 72.7
55.6
94.1
TAPNet architecture while using these pooling layers as Netdiff, Netsort. and Nettop- respectively. We evaluate them on PTC, MMDB-MULTY and REDDIT-BINARY datasets and summarize the results Table Note that these models use the same experimental setups to ensure fair comparisons. The results demonstrate the superior performance of our proposed TAP layer compared with other pooling layers using the same network architecture.
4.4 ABLATION STUDIES
In this section, we investigate the contribu- tions of TAP layer and its components in rank- ing score computation; those are the attention score term (AST) and the graph connectivity term (GCT). We remove TAP layers from TAP- Net which we denote as TAPNet w/o TAP. To explore the contributions of terms in ranking scores computation, we separately remove ASTs and GCTs from all TAP layers TAPNets. We denote the resulting models as TAPNet w/o AST and TAPNet w/o GCT, respectively. In addition,
Table Comparisons among TAPNets with and without TAP layers, TAPNet without attention score term (AST), TAPNet without graph connec- tion term (GCT), and TAPNet with auxiliary link prediction objective (AUX) in terms of graph clas-
sification accuracy (%) PTC, IMDB-M MULTM, and REDDIT-BINARY datasets.
Model
PTC
IMDB-M
RDT-B
TAPNet wo TAP
70.6
52.1
91.0
TAPNet w/o AST
71.2
54.8
91.5
TAPNet w/o GCT
72.0
55.1
93.0
we add the auxiliary link prediction objective as
TAPNet
72.7
55.6
94.1
described in Section in training. We denote
TAPNet AUX
73.0
55.8
94.2
the TAPNet using auxiliary training objective as TAPNet w AUX. We evaluate these models on three datasets; those are PTC, IMDB-MULTI,
and REDDIT-BR BINARYY datasets. The comparison results summarized in Table 4 The results show that TAPNets outperform TAPNets w/o TAP by margins of 2.1%, 3.5%, and 2.4% on PTC, IMDB-MULTT,, and REDDIT-BINARY datasets, respectively. The better results of TAPNet over
7

---

Under review as a conference paper at ICLR 2020
TAPNet w/o AST and TAPNet w/o GCT show the contributions of ASTs and GCTs to performances. can be observed that TAPNet w AUX achieves better performances than TAPNet, which shows the effectiveness of the auxiliary link prediction objective. To fully study the impact of GCT on TAP layer, we visualize the coarsened graphs generated by TAP and TAP without GCT (denoted as TAP w/o GCT). We select graph from PTC dataset and illustrate outcome graphs in Figure 3 We can observe from the figure that TAP produces better-connected graph than that by TAP w/o GCT.
4.5 PARAMETER STUDY OF GAP
Since TAP layer employs an attention operator compute ranking scores, which involves extra trainable parameters, we conduct experiments to study the number of parameters in TAPNet. We remove the extra trainable parameters from TAP layers in two ways: those are removing TAP lay- ers from TAPNet and removing attention score terms (AST) from TAP layers. We denote the resulting two networks as TAPNet w/o TAP and TAPNet w/o AST, respectively. The comparison results on REDDIT-BINARY dataset is summarized in Table We can see from the results that TAP layers only need 2.13% additional trainable parameters. We believe the negligible usage of extra parameters will not increase the risk of over-fitting but can bring 1.9% performance improvement over TAPNet w/o TAP and TAPNet w/o AST performances of TAPNets on small datasets like PTC and MUTAG in Table show that TAP layers will not cause the over-fitting problem.
Table 5: Comparisons among TAPNets with and
without TAP layers, and TAPNet without attention
score term (AST) REDDIT-BINARY dataset. Model
Accuracy
#Params
Ratio
TAPNet w/o TAP
91.0
323,666
0.00%
TAPNet w/o AST
91.5
323,666
0.00%
TAPNet
94.1
330,578
2.13%
BEDDIT-BINARY dataset. Also, the promising
4.6 PERFORMANCE STUDY OF X
In Section 3.2
propose to add the graph con-
100
nectivity term into the computation of ranking scores to improve the graph connectivity in the coarsened graph. It can be seen that is an in- fluential hyperparameter in the TAP layer. In this part, we study the performances of differ- ent À values. We select different À values from the range of 0.01, 0.1, 1.0, 10.0, and 100.0 to cover reasonable range of values. We evalu- ate TAPNets using different À values on PTC, IMDB-MULTI, and REDDIT-BINARY datasets. The results are shown in Figure 4 We can ob- serve that the best performances are achieved with À 0.1. When À becomes larger, the performance of TAPNet models decrease. This indicates that the graph connectivity term is a plus for generating reasonable ranking scores but it should not overwhelm the attention score term that encodes the topology information in ranking scores.
80
Acaurcc
70
XDF-3 THIIIMM
40
0.01
0.1
1.0
10.0
100L
Figure 4: Comparison results of TAPNets using different À values in TAP layers.
CONCLUSIONS
In this work, we propose novel topology-aware pooling (TAP) layer that applies attention mechanism to explicitly encode the topology information in ranking scores. A TAP layer attends each node to its neighboring nodes and uses the average similarity score with its neighboring nodes as its ranking score. The primary nodes sampling based on these ranking scores can incorporate the topology information, thereby leading to better-coarsened graph. Moreover, we propose to add a graph connectivity term to the computation of ranking scores to overcome the isolated problem which a TAP layer may suffer from. Based on the TAP layer, we develop topology-aware pooling networks (TAPNets) for network representation learning. We add an auxiliary link prediction objective to train our networks by employing the similarity score matrix generated in TAP layers. Experimental results on graph classification tasks using both bioinformatics and social network datasets demonstrate that TAPNets achieve performance improvements as compared to previous models. Ablation Studies show the contributions of our TAP layers and terms in ranking score computation to network performances.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. International Conference on Learning Representations, 2015.
Joao Carreira, Rui Caseiro, Jorge Batista, and Cristian Sminchisescu. Semantic segmentation with second-order pooling. In European Conference on Computer Vision, pp. 430-443. Springer, 2012.
Liang-Chieh Chen, George Papandreou, lasonas Kokkinos, Kevin Murphy, and Alan L Yuille. Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected erfs. Transactions on Pattern Analysis and Machine Intelligence, 2016.
Djork-Arné Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). arXiv preprint arXiv:1511.07250 2015.
Hongyang Gao and Shuiwang Ji. Graph U-nets. In Proceedings The 36th International Conference on Machine Learning, 2019.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 1416-1424. ACM, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Gao Huang, Zhuang Liu, Kilian Q Weinberger, and Laurens van der Maaten. Densely connected convolutional networks. IEEE Conference on Computer Vision and Pattern Recognition, 2017.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. The International Conference on Learning Representations, 2015.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference Learning Representations, 2017.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Proceedings of The 36th International Conference on Machine Learning, 2019.
Guanbin Li, Xiang He, Wei Zhang, Huiyou Chang, Le Dong, and Liang Lin. Non-locally enhanced encoder-decoder network for single image de-raining. In 2018 ACM Multimedia Conference on Multimedia Conference, pp. 1056-1060 1064. ACM, 2018.
Jiasen Lu, Jianwei Yang, Dhruv Batra, and Devi Parikh. Hierarchical question-image co-attention for visual question answering. In Advances In Neural Information Processing Systems, pp. 289-297, 2016.
Mateusz Malinowski, Carl Doersch, Adam Santoro, and Peter Battaglia. Learning visual question answering by bootstrapping hard attention. In European Conference on Computer Vision, pp. 3-20. Springer, 2018
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International Conference on Machine Learning, pp. 2014-2023 2016.
Sebastian Ruder. An overview of multi-task learning in deep neural networks. arXiv preprint arXiv: arXiv:1706.05009: 05098, 2017.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(Sep): 2239,2566,,2 2011.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. Proceedings of the International Conference on Learning Representations, 2015.

---

Under review as a conference paper at ICLR 2020
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(1):1929-1988 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pp. 6000-6010, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10900, 2017.
Xiaolong Wang. Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), volume 1, pp. 4, 2018.
Bing Xu, Naiyan Wang, Tianqi Chen, and Mu Li. Empirical evaluation of rectified activations in convolutional network. arXiv preprint arXiv: 150..0055003333 2015a.
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 on machine learning, pp. 2048-2057 2015b.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 2018.
Pinar Yanardag and SVN Vishwanathan. structural smoothing framework for robust graph comparison. In Advances in Neural Information Processing Systems, pp. 2134-2142, 2015.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, pp. 4800-4810, 10, 2018.
Fisher Yu and Vladlen Koltun. Multi-scale context aggregation by dilated convolutions. In Proceed- ings of the International Conference on Learning Representations, 2016
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of AAAI Conference on Artificial Inteligence. 2018.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification, In Advances Neural Information Processing Systems, pp. 649-657, 2015.
10

---

Under review as a conference paper at ICLR 2020
Appendix
EXPERIMENTAL SETUP FOR GRAPH CLASSIFICATION TASKS
We evaluate our methods using social network datasets and bioinformatics datasets. They share the same experimental setups except for minor differences. The node features in social network networks are created using one-hot encodings of node degrees. The nodes in bioinformatics have categorical features. We use the TAPNet proposed in Section 3.3 that consists of one GCN layer and three blocks. The first GCN layer is used to learn low-dimensional representations of nodes in the graph. Each block is composed of one GCN layer and one TAP layer. All GCN and TAP layers output 48 feature maps. We use Leaky ReLU (Xu et al. 2015a) with slop of 0.01 to activate the outputs of GCN layers. The three TAP layers the networks select numbers of nodes that are proportional to the nodes in the graph. We use the rates of 0.8, 0.6, and 0.4 in three TAP layers, respectively. We use 0.1 to control the importance of the graph connectivity term in the computation of ranking scores. Dropout (Srivastava et al., 2014) is applied to the input feature matrices of GCN and TAP layers with keep rate 0.7. We use a two-layer feed-forward network as the network classifier. Dropout with keep rate of 0.8 is applied imput features of two layers. We ReLU activation function on the output of the first layer on DD, PTC, MUTAG, COLLAB, REDDIT-MULTISK, and REDDIT-MULTT12K datasets. We ELU (Clevert al. 2015) for other datasets. We train our networks using Adam optimizer (Kingma & Ba 2015) with learning rate of 0.001. To avoid over-fitting, we use L2 regularization with 0.0008, All models are trained using one NVIDIA GeForce RTX 2080 Ti GPU.
We will release our code in the final version.
REFERENCES
All citations refer the references in the main paper.


Reviews:
[{"review_id": "r1gXgfF6uB", "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 proposed a topology-aware-pooling method to generate ranking scores for each node and so the pooling (or coarsening) of the graph can be achieved by picking those nodes with higher aggregated attention scores. The ranking scores for each node are computed by taking the average of the scores of its neighbors, by doing which the authors claim that the topological information of the graph is taken into direct account in the pooling steps. \n\nThe proposed method indeed shares some common idea with “Hierarchical Graph Representation Learning with differentiable pooling” by Xing et al. There, a differentiable pooling procedure is used to progressively coarsen the graph to achieve global representation, and the assignment matrix is learned in each hierarchies. This is very similar to the proposed method, since those nodes with higher attention scores are those with more neighbors, which can be considered as ``local cluster centers’’ on a graph. In other words, both methods perform some kind of hierarchical clustering to coarsen the graph. The authors claim that an assignment matrix may cause (1) overfitting, and (2) the coarsened graph may have a different structure than the original graph, which I believe are not justified criticisms. In many cases of clustering the assignment matrix  is auxiliary variables; and even if the assignment matrix is learned as a whole matrix variable, as long as the loss terms is properly defined (such as reconstruction loss in k-means), it can be learned very well because it does not need labels as a unsupervised term.  Second, computing the assignment matrix has more flexibility, especially considering that the coarsening step is not just to perform clustering but rather to facilitate the final classification, therefore locating ``important’’ nodes (in terms of fully representing the graph) is not the only goal, but locating both important and discriminative nodes (i.e., those nodes that can lead to informative features for final classification) is. In this sense, learning an assignment matrix obviously has the benefit of receiving back-propagated gradients from class labels, while the proposed method does not have this flexibility in the pooling step since the neighborhood structure of the graph is fixed throughout the iterations. \n\nAnother important observation is that The proposed method seems to connect each hierarchy directly to the final layer, which is similar to skip-connections. Can this be the main reason why the performance shows improvement, as has been validated in extensive studies in the computer vision community? Some ablation studies are needed to verify that the performance gains are mainly due to the key idea of TAP but not due to the skip connections that have been widely used in computer vision tasks.\n\nSome minor comments:\nHow do you implement the ranking_k() function? Is it differentiable?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HkeXw-909H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 presented a new pooling method for learning graph-level embeddings. The key idea is to use the initial node attributes to compute all-pair attention scores for each node pair and then use these attention scores to formulate a new graph adjacency matrix beyond the original raw graph adjacency matrix. As the result, each node can average these attention score edges to compute the overall importance. Based on these scores, the method chooses top-k nodes to perform graph coarsening operation. In addition, a graph connectivity term is proposed to address the problems of isolated nodes. Experiments are performed to validate the effectiveness of the proposed method. \n\nAlthough I found this paper is generally well written and well motivated, there are several concerns about the novelty of paper, computational expenses, and the experimental results as listed below:\n\n1) The idea of using attention score is simple yet seems effective. But using attention score to identify the importance of nodes has been first presented in GAT [Velicˇkovic ́ et al., 2019] and further studied by a lot of subsequent works.  \n\n2) In this paper, authors considered using raw node features to obtain good attention scores between each node pair. However, the effectiveness of this will heavily depend on how informative these original node features are. In the extreme case, the original node features are completely random, then the proposed method will definitely fail since there are no meaningful similarity scores that can be learnt from. Surprisingly, I did not see any discussion or any ablation study on this aspect. Also, why only using initial node attributes? How about the computed node embeddings to compute the similarity scores?\n\n3) The pair-wise similarity scores (similarity or attention matrix) are very expensive to compute and score, which easily renders quadratic complexity in terms of the number of nodes O(N^2) for both computation and memory. This makes it scale to really large graph. In this sense, the proposed scheme is not promising in real applications. \n\n4) The experiments are really problematic. There are no descriptions on how the graph data are split in train/val/test. Following the traditional graph kernel settings, it should be 9/1/1. Also, there are no information about how many runs are performed on each dataset. I noticed that authors basically collected all performance results from published related works except for several baselines. Different data split and number of runs could result quite different performance report, leading to apple-and-orange comparisons. \n\n5) The experimental results are also problematic as well. For example, WL baseline has extremely large variance for all of datasets, which are completely different from the reported number from other literature [Zhang et al, neurIPS'18] and my personal experience. In general, the variance of WL could be 1/10 smaller than what are reported in this paper. Also, there is no clear explanations why the proposed method achieved quite large margin compared to G-UNet and GIN as shown in Table 1. \n\nRetGK: Graph Kernels based on Return Probabilities of Random Walks, [Zhang et al, neurIPS'18]\n\n6) In Table 3, authors tried to show the performance difference between different pooling methods. I was so surprised about the results after I looked back to Table 1. For instance, Net_top-k (G-Unet) achieved 71.5 on PTC while GUnet achieved 64.7 on PTC in Table 2. It is really hard to believe this almost 7 points difference are just due to slight different model choices in other parts beyond the main contribution - new pooling component. I feel the whole experimental results are not convincing or at least no well explanations what's going on here. Of course, based on very large variances shown in table 1 and 2, table 3 and table 4 are meaningless to look without seeing the variances for each ablation study. \n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "H1ghLsy4cB", "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": "This paper proposes a topology-aware pooling method on graph data, which explicitly encodes the topology information when computing ranking scores. More specifically, the proposed method uses an attention operator to compute similarity scores between each node and its neighborhood nodes, and then uses the average similarity score of each node as the ranking score in the node selection process. This topology-aware pooling technique can be applied to graph neural networks on downstream tasks such as graph classification. Experimental results demonstrate the effectiveness of the proposed method, which outperform previous state-of-the-art models consistently.\n\nOverall, this paper is well-organized and the contributions are clear. Although the methodology of adding a graph connectivity term is relatively simple, it is effective to improve the performance on graph classification task and should be straightforward to be applied to other graph learning tasks. Based on the above reasons, I would like to recommend a weak accept for this paper.", "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 assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to incorporate graph topology into pooling operations on graphs, to better define the notion of locality  necessary for pooling.  While the paper tackles an important problems, and seems to be also well-written, the reviewers agree that there are several issues regarding the contribution and empirical results that need to be addressed before this paper is ready for publication.
Decision: Reject