Title: TOPOLOGY-AWARE POOLING VIA GRAPH ATTENTION

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.

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

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

2.2. ATTENTION OPERATORS:

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 ∈ R d×m , a key matrix K ∈ R d×n , and a value matrix V ∈ R p×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(K T Q). When the attention operator is applied to graph, each node only attends to 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., 2019) . In our proposed pooling operation, we employ an attention operator to compute ranking scores that explicitly encode topology information.

3. TOPOLOGY-AWARE POOLING LAYERS AND NETWORKS:

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.

3.1. TOPOLOGY-AWARE POOLING LAYER:

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 

(a) (b) (c) (d)

Figure 1 : An illustration of the proposed topology-aware 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), we label each node by its ranking score and bigger node indicates a higher ranking score. By selecting the nodes with the k = 3 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 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 ( ) ∈ R N ×N and the feature matrix X ( ) ∈ R N ×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

EQUATION

where

EQUATION

:j is the jth column of matrix A ( ) , • denotes the element-wise matrix multiplication, Ẽ:j is the jth column of matrix Ẽ, k is the number of nodes selected in the sampled graph, and diag(•) constructs a diagonal matrix using input vector as diagonal elements. Ranking k 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 e ij 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 Ẽ. 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 = [s 1 , s 2 , . . . , s N ] T where s i represents the ranking score of node i. Ranking k is an operator that selects k-largest values and returns the corresponding indices. In Eq. ( 6), we use Ranking k 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.

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

EQUATION

where d i 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.

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 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 ∈ R N ×N and the feature matrix X ∈ R N ×C , our TAPNet outputs a list of feature matrices

[Y 0 , Y 1 , . . . , Y m ].

Here, Y 0 ∈ R N ×h is the output of the graph embedding layer and Y i ∈ R k (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 = [y T 0 , y T 1 , . . . , y T m ] T where y i is transformed from Y i . 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.

3.4. AUXILIARY LINK PREDICTION OBJECTIVE:

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 Ê( ) ∈ R N ×N with each element ê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

EQUATION

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.

4. EXPERIMENTAL STUDIES:

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.

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-MULTI5K (RDT-M5K) and REDDIT-MULTI12K (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, Table 1 : Comparisons between TAPNets and other models such as WL (Shervashidze et al., 2011) and PSCN (Niepert et al., 2016) 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.

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-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. 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 Net diff , Net sort , and Net top-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. 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 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 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 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.3. COMPARISON WITH OTHER GRAPH POOLING LAYERS:



4.4. ABLATION STUDIES:

4.5 PARAMETER STUDY OF GAP 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.

5. CONCLUSIONS:

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.

:



Figures and Tables:

Figure2: An illustration of the topology-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 a GCN layer and a TAP layer. A global reduction operation such as max-pooling is applied to the outputs of the first GCN layer and TAP layers. The resulting feature vectors are concatenated and fed into the final multi-layer perceptron for prediction.

Figure 3: Illustrations of coarsened graphs generated by TAP and TAP w/o GCT. Here, GCT denotes the graph connection term. The input graph (a) contains 12 nodes. The pooling layers select 6 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.

Figure Comparison results of TAPNets using different λ values in TAP layers.

in terms of graph classification accuracy (%) on social network datasets including COLLAB, IMDB-BINARY, IMDB-MULTI, REDDIT-BINARY, REDDIT-MULTI5K and REDDIT-MULTI12K datasets.

Table content: <table><tr><td/><td>COLLAB</td><td>IMDB-B</td><td>IMDB-M</td><td>RDT-B</td><td colspan="2">RDT-M5K RDT-M12K</td></tr><tr><td># graphs</td><td>5000</td><td>1000</td><td>1500</td><td>2000</td><td>4999</td><td>11929</td></tr><tr><td># nodes</td><td>74.5</td><td>19.8</td><td>13.0</td><td>429.6</td><td>508.5</td><td>391.4</td></tr><tr><td># classes</td><td>3</td><td>2</td><td>3</td><td>2</td><td>5</td><td>11</td></tr><tr><td>WL</td><td>78.9 ± 1.9</td><td>73.8 ± 3.9</td><td>50.9 ± 3.8</td><td>81.0 ± 3.1</td><td>52.5 ± 2.1</td><td>44.4 ± 2.1</td></tr><tr><td>PSCN</td><td>72.6 ± 2.2</td><td>71.0 ± 2.2</td><td>45.2 ± 2.8</td><td>86.3 ± 1.6</td><td>49.1 ± 0.7</td><td>41.3 ± 0.8</td></tr><tr><td>DGCNN</td><td>73.8</td><td>70.0</td><td>47.8</td><td>-</td><td>-</td><td>41.8</td></tr><tr><td>DIFFPOOL</td><td>75.5</td><td>-</td><td>-</td><td>-</td><td>-</td><td>47.1</td></tr><tr><td>g-U-Net</td><td>77.5 ± 2.1</td><td>75.4 ± 3.0</td><td>51.8 ± 3.7</td><td>85.5 ± 1.3</td><td>48.2 ± 0.8</td><td>44.5 ± 0.6</td></tr><tr><td>GIN</td><td>80.6 ± 1.9</td><td>75.1 ± 5.1</td><td>52.3 ± 2.8</td><td>92.4 ± 2.5</td><td>57.5 ± 1.5</td><td>-</td></tr><tr><td>TAPNet (ours)</td><td>84.6 ± 1.7</td><td>79.5 ± 4.1</td><td>55.6 ± 2.9</td><td>94.1 ± 1.9</td><td>57.1 ± 1.3</td><td>49.2 ± 1.6</td></tr></table>

Comparisons between TAPNets and other models in terms of graph classification accuracy (%) on bioinformatics datasets including DD, PTC, MUTAG, and PROTEINS datasets.

Table content: <table><tr><td/><td>DD</td><td>PTC</td><td>MUTAG</td><td>PROTEINS</td></tr><tr><td># graphs</td><td>1178</td><td>344</td><td>188</td><td>1113</td></tr><tr><td># nodes</td><td>284.3</td><td>25.5</td><td>17.9</td><td>39.1</td></tr><tr><td># classes</td><td>2</td><td>2</td><td>2</td><td>2</td></tr><tr><td>WL</td><td>78.3 ± 0.6</td><td>59.9 ± 4.3</td><td>90.4 ± 5.7</td><td>75.0 ± 3.1</td></tr><tr><td>PSCN</td><td>76.3 ± 2.6</td><td>60.0 ± 4.8</td><td>92.6 ± 4.2</td><td>75.9 ± 2.8</td></tr><tr><td>DGCNN</td><td>79.4 ± 0.9</td><td>58.6 ± 2.4</td><td>85.8 ± 1.7</td><td>75.5 ± 0.9</td></tr><tr><td>SAGPool</td><td>76.5</td><td>-</td><td>-</td><td>71.9</td></tr><tr><td>DIFFPOOL</td><td>80.6</td><td>-</td><td>-</td><td>76.3</td></tr><tr><td>g-U-Net</td><td>82.4 ± 2.9</td><td>64.7 ± 6.8</td><td>87.2 ± 7.8</td><td>77.6 ± 2.6</td></tr><tr><td>GIN</td><td>82.0 ± 2.7</td><td>64.6 ± 7.0</td><td>90.0 ± 8.8</td><td>76.2 ± 2.8</td></tr><tr><td>TAPNet (ours)</td><td>84.2 ± 3.7</td><td>72.7 ± 6.0</td><td>93.0 ± 5.8</td><td>78.9 ± 4.2</td></tr></table>

Comparisons between different pooling operations based on the same TAPNet architecture.

Table content: <table><tr><td>Model</td><td>PTC</td><td>IMDB-M</td><td>RDT-B</td></tr><tr><td>Net diff Net sort</td><td>70.9 70.6</td><td>54.9 54.8</td><td>92.1 92.3</td></tr><tr><td>Net top-k</td><td>71.5</td><td>55.2</td><td>92.8</td></tr><tr><td>TAPNet</td><td>72.7</td><td>55.6</td><td>94.1</td></tr></table>



Table content: <table><tr><td colspan="4">: Comparisons among TAPNets with and</td></tr><tr><td colspan="4">without TAP layers, TAPNet without attention</td></tr><tr><td colspan="4">score term (AST), TAPNet without graph connec-</td></tr><tr><td colspan="4">tion term (GCT), and TAPNet with auxiliary link</td></tr><tr><td colspan="4">prediction objective (AUX) in terms of graph clas-</td></tr><tr><td colspan="4">sification accuracy (%) on PTC, IMDB-MULTI,</td></tr><tr><td colspan="3">and REDDIT-BINARY datasets.</td><td/></tr><tr><td>Model</td><td>PTC</td><td colspan="2">IMDB-M RDT-B</td></tr><tr><td>TAPNet w/o TAP</td><td>70.6</td><td>52.1</td><td>91.0</td></tr><tr><td>TAPNet w/o AST</td><td>71.2</td><td>54.8</td><td>91.5</td></tr><tr><td>TAPNet w/o GCT</td><td>72.0</td><td>55.1</td><td>93.0</td></tr><tr><td>TAPNet</td><td>72.7</td><td>55.6</td><td>94.1</td></tr><tr><td>TAPNet w AUX</td><td>73.0</td><td>55.8</td><td>94.2</td></tr></table>

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.

Table content: <table/>

Comparisons among TAPNets with and without TAP layers, and TAPNet without attention score term (AST) on REDDIT-BINARY dataset. 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 Table5. 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 Table2show that TAP layers will not cause the over-fitting problem.

Table content: <table><tr><td>Model</td><td colspan="2">Accuracy #Params</td><td>Ratio</td></tr><tr><td>TAPNet w/o TAP</td><td>91.0</td><td>323,666</td><td>0.00%</td></tr><tr><td>TAPNet w/o AST</td><td>91.5</td><td>323,666</td><td>0.00%</td></tr><tr><td>TAPNet</td><td>94.1</td><td>330,578</td><td>2.13%</td></tr></table>

Peer review (iclr2020):
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. Although 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: 1) 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. 2) 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? 3) 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. 4) 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. 5) 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. RetGK: Graph Kernels based on Return Probabilities of Random Walks, [Zhang et al, neurIPS*18] 6) 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.