Year: 2019

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.

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

heading: 1 INTRODUCTION
text: 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., 2015). 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. In 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 a nodes assignment matrix. These methods suffer from the over-fitting problem and need auxiliary link prediction tasks to stabilize the training (Ying et al., 2018). The primary nodes sampling methods like top-k pooling (Gao & Ji, 2019) rank the nodes in a graph and sample top-k nodes to form the sampled graph. It uses a small number of additional trainable parameters and is shown to be more powerful (Gao & Ji, 2019). However, the top-k pooling layer does not explicitly incorporate the topology information in a 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 a node is used as its ranking score in the selection process. To avoid isolated nodes problem in our TAP layer, we further propose a graph connectivity term for computing the ranking scores of nodes. The graph connectivity term uses degree information as a 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.

heading: 2 BACKGROUND AND RELATED WORK
text: In this section, we describe graph pooling operations and attention operators.

heading: 2.1 GRAPH POOLING OPERATIONS
text: 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 an 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 of the original graph. The node sampling methods mainly select a fixed number k of the most important nodes to form a new graph. In SortPool (Zhang et al., 2018), the same feature of each node is used for ranking and k 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. k 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.

heading: 2.2 ATTENTION OPERATORS
text: Attention operator has shown to be effective in challenging tasks in various fields such as computer vision (Xu et al., 2015b; Lu et al., 2016; Li et al., 2018) and natural language processing (Malinowski et al., 2018; Bahdanau et 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 ∈ Rd×m, a key matrix K ∈ Rd×n, and a value matrix V ∈ Rp×n. The attention operator computes the response of each query vector in Q by attending it to all key vectors in K. It uses the resulting coefficient vector to take a weighted sum over value vectors in V . The layer-wise operation of an attention operation is defined as O = V softmax(KTQ). When the attention operator is applied to graph, each node only attends to its neighboring nodes (Veličković et al., 2017). Self-attention can also produce an attention mask to control information flow on selected nodes in pooling operation (Lee et al., 2019). In our proposed pooling operation, we employ an attention operator to compute ranking scores that explicitly encode topology information.

heading: 3 TOPOLOGY-AWARE POOLING LAYERS AND NETWORKS
text: In this work, we propose the topology-aware pooling (TAP) layer that uses attention operators to encode topology information in ranking scores for node selection. We also propose a graph connectivity term in the computation of ranking scores, which encourages better graph connectivity in the coarsened graph. Based on our TAP layer, we propose the topology-aware pooling networks for network representation learning.

heading: 3.1 TOPOLOGY-AWARE POOLING LAYER
text: Pooling layers have shown to be important on grid-like data with regard to reducing feature map sizes and enlarging receptive fields (Yu & Koltun, 2016; Carreira et al., 2012). On graph data, two kinds of pooling layers have been proposed; those are node clustering (Ying et al., 2018) and primary nodes sampling (Gao & Ji, 2019; Zhang et al., 2018). A primary nodes sampling method, known as top-k pooling (Gao & Ji, 2019), uses a projection vector to generate ranking scores for each node in the
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 a 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 a node has a high ranking score, it can highly represent a local graph that consists of it and its neighboring nodes. By choosing nodes with the highest ranking scores, we can retain the maximum information in the sampled graph.
Suppose there are N nodes in a graph G, each of which contains C features. In layer `, we use two matrices to represent the graph; those are the adjacency matrix A(`) ∈ RN×N and the feature matrix X(`) ∈ RN×C . The non-zero entries in A(`) represent edges in the graph. The ith row in X(`) denotes the feature vector of node i. The layer-wise forward propagation rule of TAP in layer ` is defined as
K = X(`)W (`), ∈RN×C (1) E = X(`)KT , ∈RN×N (2) Ẽ = E ◦A(`), ∈RN×N (3)
d = N∑ j=1 A (`) :j , ∈R N (4)
s = sigmoid
(∑N j=1 Ẽ:j
d
) , ∈RN (5)
idx = Rankingk(s), ∈Rk (6) A(`+1) = A(`)(idx, idx), ∈Rk×k (7) X(`+1) = X(`)(idx, :)diag(s(idx)), ∈Rk×C (8)
where W (`) ∈ RC×C is a trainable weight matrix, A(`):j is the jth column of matrix A (`), ◦ denotes
the element-wise matrix multiplication, Ẽ:j is the jth column of matrix Ẽ, k is the number of nodes selected in the sampled graph, and diag(·) constructs a diagonal matrix using input vector as diagonal elements. Rankingk operator ranks the scores and return the indices of k-largest values in s.
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
score matrix E is obtained by the matrix multiplication between X(`) and K in Eq. (2). Each value eij 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 a 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 a node is computed in Eq. (5) 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 s = [s1, s2, . . . , sN ]T where si represents the ranking score of node i. Rankingk is an operator that selects k-largest values and returns the corresponding indices. In Eq. (6), we use Rankingk to select the k-most important nodes with indices in idx. Using idx, we extract new adjacency matrix A(`+1) in Eq. (7) and new feature matrix X(`+1) in Eq. (8). Here, we use the ranking scores s(idx) 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 as a local-voting, global-ranking process. In our TAP layer, the 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 a 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 1 provides an 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 a better coarsened graph.

heading: 3.2 GRAPH CONNECTIVITY TERM
text: 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 or even only themselves. Suppose node i only connects to itself. The ranking score of node i 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 to 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 densely-connected nodes are preferred during nodes selection. By using the node degree as the graph connectivity term, the ranking score of node i is computed as
si = sigmoid
(∑N j=1 Ẽij
di
) + λ
di N , (9)
where di 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 can overcome the limitation of the TAP layer. The computation of ranking scores now considers nodes degrees and gives rise to better connectivity in the resulting graph.

heading: 3.3 TOPOLOGY-AWARE POOLING NETWORKS
text: 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 a graph embedding layer to produce low-dimensional representations of nodes in the graph, which helps to deal with some datasets with very high-dimensional input feature vectors. Here, we use a 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 a hyperparameter k(i) to 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 h feature maps. Given an input graph with the adjacency matrix A ∈ RN×N and the feature matrix X ∈ RN×C , our TAPNet outputs a list of feature matrices [Y 0,Y 1, . . . ,Y m]. Here, Y 0 ∈ RN×h is the output of the graph embedding layer and Y i ∈ Rk (i)×h is the output of TAP layer in the ith block.
In TAPNets, we use a multi-layer perceptron as the classifier. We first transform network outputs to a one-dimensional vector. Specificity, the resulting vector z = [yT0 ,y T 1 , . . . ,y T m]
T where yi is transformed from Yi. Global max and average pooling operations are two popular ways for the transformation, which reduce the spatial size of feature matrices to 1 using max and average functions, respectively. Recently, Xu et al. (2018) proposed to use the summation function that results in promising performances. In TAPNets, we 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 2 illustrates a sample TAPNet with two blocks.

heading: 3.4 AUXILIARY LINK PREDICTION OBJECTIVE
text: Multi-task learning has shown to be effective across various machine learning tasks (Ruder, 2017). It can leverage useful information in multiple related tasks, thereby leading to better generalization and performance. In this section, we propose to add an auxiliary link prediction objective during training by using a 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-wise sigmoid(·) on E, we can obtain a link probability matrix Ê (`) ∈ RN×N with each element êij 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
lossaux = 1
N2 N∑ i=1 N∑ j=1 f ( Ê (`) ij ,A (`) ij ) , (10)
where f(·, ·) 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 a 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., 2018) that uses the learned adjacency matrix as objective, our method uses the original links, thereby providing more accurate information.

heading: 4 EXPERIMENTAL STUDIES
text: In this section, we evaluate our methods and networks on graph classification tasks using bioinformatics 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.

heading: 4.1 GRAPH CLASSIFICATION RESULTS ON SOCIAL NETWORK DATASETS
text: We conduct experiments on graph classification tasks to evaluate our proposed methods and TAPNets. We use 6 social network datasets; those are COLLAB, IMDB-BINARY (IMDB-B), IMDBMULTI (IMDB-M), REDDIT-BINARY (RDT-B), REDDIT-MULTI5K (RDT-M5K) and REDDITMULTI12K (RDT-M12K) (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 et al., 2018; Xu et al., 2018). Since there is no feature for nodes in social networks,
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-art models in terms of graph classification accuracy. The comparison results are summarized in Table 1. 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, IMDB-BINARY, IMDB-MULTI, REDDIT-BINARY, and REDDIT-MULTI12K datasets, respectively. The promising performances, especially on large datasets such as REDDIT, demonstrate the effectiveness of our methods. Note that the superior performances over g-U-Net (Gao & Ji, 2019) show that our TAP layer can produce better-coarsened graph than that using the top-k pooling layer.

heading: 4.2 GRAPH CLASSIFICATION RESULTS ON BIOINFORMATICS DATASETS
text: 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-ofthe-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 on these small datasets demonstrate that our
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 a mask to control the information flow. Here, our method employs an attention operator to compute ranking scores that better encodes the topology information in the graph. The superior performances over SAGPool on DD and PROTEINS datasets demonstrate that our methods can better capture the topology information, thereby leading to better performances.

heading: 4.3 COMPARISON WITH OTHER GRAPH POOLING LAYERS
text: It may be argued that our TAPNets achieve promising results by employing superior networks. 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 TAPNet architecture while using these pooling
layers as Netdiff, Netsort, and Nettop-k, respectively. We evaluate them on PTC, IMDB-MULTI, and REDDIT-BINARY datasets and summarize the results in Table 3. 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 contributions of TAP layer and its components in ranking score computation; those are the attention score term (AST) and the graph connectivity term (GCT). We remove TAP layers from TAPNet 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 in TAPNets. We denote the resulting models as TAPNet w/o AST and TAPNet w/o GCT, respectively. In addition, we add the auxiliary link prediction objective as described in Section 3.4 in training. We denote the TAPNet using auxiliary training objective
as TAPNet w AUX. We evaluate these models on three datasets; those are PTC, IMDB-MULTI, and REDDIT-BINARY datasets. The comparison results are 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-MULTI, and REDDIT-BINARY datasets, respectively. The better results of TAPNet over
TAPNet w/o AST and TAPNet w/o GCT show the contributions of ASTs and GCTs to performances. It 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 a 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 to 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 layers 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 5. 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 on REDDIT-BINARY dataset. Also, the promising performances of TAPNets on small datasets like PTC and MUTAG in Table 2 show that TAP layers will not cause the over-fitting problem.
4.6 PERFORMANCE STUDY OF λ
In Section 3.2, we propose to add the graph connectivity term into the computation of ranking scores to improve the graph connectivity in the coarsened graph. It can be seen that λ is an influential hyperparameter in the TAP layer. In this part, we study the performances of different λ values. We select different λ values from the range of 0.01, 0.1, 1.0, 10.0, and 100.0 to cover a reasonable range of values. We evaluate TAPNets using different λ values on PTC, IMDB-MULTI, and REDDIT-BINARY datasets. The results are shown in Figure 4. We can observe 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.

heading: 5 CONCLUSIONS
text: In this work, we propose a 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 a 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 our 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.

heading: 1 EXPERIMENTAL SETUP FOR GRAPH CLASSIFICATION TASKS
text: 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 a slop of 0.01 to activate the outputs of GCN layers. The three TAP layers in 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 of 0.7. We use a two-layer feed-forward network as the network classifier. Dropout with keep rate of 0.8 is applied to input features of two layers. We use ReLU activation function on the output of the first layer on DD, PTC, MUTAG, COLLAB, REDDIT-MULTI5K, and REDDIT-MULTI12K datasets. We use ELU (Clevert et al., 2015) for other datasets. We train our networks using Adam optimizer (Kingma & Ba, 2015) with a 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.

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

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.