Title: SUBGRAPH ATTENTION FOR NODE CLASSIFICATION AND HIERARCHICAL GRAPH POOLING Anonymous

Abstract: Graph neural networks have gained significant interest from the research community for both node classification within a graph and graph classification within a set of graphs. Attention mechanism applied on the neighborhood of a node improves the performance of graph neural networks. Typically, it helps to identify a neighbor node which plays more important role to determine the label of the node under consideration. But in real world scenarios, a particular subset of nodes together, but not the individual nodes in the subset, may be important to determine the label of a node. To address this problem, we introduce the concept of subgraph attention for graphs. To show the efficiency of this, we use subgraph attention with graph convolution for node classification. We further use subgraph attention for the entire graph classification by proposing a novel hierarchical neural graph pooling architecture. Along with attention over the subgraphs, our pooling architecture also uses attention to determine the important nodes within a level graph and attention to determine the important levels in the whole hierarchy. Competitive performance over the state-of-the-arts for both node and graph classification shows the efficiency of the algorithms proposed in this paper.

1. INTRODUCTION:

Graphs are the most suitable way to represent different types of relational data such as social networks, protein interactions and molecular structures. Typically, A graph is represented by G = (V, E), where V is the set of nodes and E is the set of edges. Further, each node v i ∈ V is also associated with an attribute (or feature) vector x i ∈ R D . Recent advent of deep representation learning has heavily influenced the field of graphs. Graph neural networks are developed to use the underlying graph as a computational graph and aggregate node attributes from the neighbors of a node to generate the node embeddings (Kipf & Welling, 2017; Niepert et al., 2016) . Different types of attribute aggregation approaches are proposed in the literature (Hamilton et al., 2017) . Attention mechanisms on graphs show promising results for both node classification (Veličković et al., 2018) and graph classification (Lee et al., 2019; 2018) tasks. There are different ways to compute attention mechanisms on graph. Veličković et al. (2018) compute attention between a pair of nodes in the immediate neighborhood to capture the importance of a node on the embedding of the other node by learning an attention vector. Lee et al. (2018) compute attention between a pair of nodes in the neighborhood to guide the direction of a random walk in the graph for graph classification. Lee et al. (2019) propose self attention pooling of the nodes which is then used to capture the importance of the node to generate the label of the entire graph.

Most of the attention mechanisms developed in graph literature use attention to derive the importance of a node or a pair of node for different tasks. But in real world situation, calculating importance up to a pair of nodes is not adequate. Often due to the presence of a substructure in the vicinity of a node v determines its role (or label) in the graph, or determines the label of the entire graph. But the influence of each node individually from that substructure to the node v may not be significant. In Figure 1 , each node (indexed from a to g) in the small synthetic graph can be considered as an agent whose attributes determine its opinion (1:positive, 0: neutral, -1: negative) about 4 products. Suppose the graph can be labelled +1 only if there is a subset of connected (by edges) agents who jointly have positive opinion about all the product. In this case, the blue shaded connected subgraph (a, b, c) is important to determine the label of the graph. Please note, attention over the pairs (Veličković et al., 2018) is not enough as (a, b) cannot make the label of the graph +1 by itself. Also multiple layers of such attention may not work as the aggregated features of a node get corrupted after the feature aggregation by the first attention layer. With this motivation, we develop a novel attention mechanism in the graph which operates in the subgraph level in the vicinity of a node. We call it subgraph attention mechanism and use it for both node classification and graph classification tasks, which we define formally next.

Node classification: Given a graph G = (V, E) with each node v i associated with an attribute vector x i ∈ R D , and a subset of nodes V s ⊆ V with each node v i ∈ V s labelled with y i ∈ L n (set of discrete labels for the nodes of the graph), the task is to predict the label of a node v j ∈ V u = V \ V s using the structure and the node attributes of the entire graph and the node labels from V s . Essentially, this leads to learning a function f n : V → L n for the given graph G.

Graph Classification: Given a set of M graphs G = {G 1 , G 2 , • • • , G M },

and a subset of graphs G s ⊆ G with each graph G i ∈ G s are labelled with Y i ∈ L g (the subscript g stands for 'graphs'), the task is to predict the label of a graph G j ∈ G u = G \ G s using the structure of the graphs and the node attributes, and the graph labels from G s . Again, this leads to learning a function f g : G → L g . Here, L g is the set of discrete labels for the graphs. 

2. RELATED WORK:

A survey on network representation learning and graph neural networks can be found in Wu et al. (2019) . Here we briefly discuss some more prominent approaches for node classification and graph classification. Kipf & Welling (2017) propose a version of graph convolution network (GCN) which learns a weighted mean of neighbor node attributes to find the embedding of a node by minimizing the cross entropy loss for node classification. Different extensions of GCN are available in literature for inductive learning (Hamilton et al., 2017) and link prediction (Zhang & Chen, 2018) . Veličković et al. (2018) propose GAT which uses attention mechanism to learn the importance of a node to determine the label of another node in the neighborhood of it in the graph convolution framework. Recently, a GCN based unsupervised approach (DGI) is proposed (Veličković et al., 2019) by maximizing mutual information between patch representations and corresponding high-level summaries of a graph.

On the other hand, graph classification is a classical problem in machine learning. Graph kernel (Vishwanathan et al., 2010) based approaches remain to be the state-of-the-art for graph classification for long time. Yanardag & Vishwanathan (2015) propose Deep Graph Kernels which learns hidden representations of sub-structures used in graph kernels. But most of the existing graph kernels use hand-crafted features. Graph2vec (Narayanan et al., 2017) is another graph embedding technique which maximizes the likelihood of the set of subgraphs which belong to a graph. Recently, different types of graph neural networks (GNN) are proposed for graph classification. To go from node embeddings to a single representation for the whole graph, simple aggregation technique such as taking the average of node embeddings in the final layer of a GCN (Duvenaud et al., 2015) and more advanced deep learning architectures that operate over the sets (Gilmer et al., 2017; Zhang et al., 2018) have been used. Attention based graph classification technique GAM (Lee et al., 2018) is proposed, which processes only a portion of the graph by adaptively selecting a sequence of informative nodes. DIFFPOOL (Ying et al., 2018) is a recently proposed hierarchical GNN which uses a GCN based pooling to create a set of hierarchical graphs in each level. Lee et al. (2019) propose a self attention based pooling strategy which determines the importance of a node to find the label of the graph. Inspired by CapsNet (Sabour et al., 2017) , Capsule GNN (CapsGNN) is proposed (Xinyi & Chen, 2019) . Different extensions of GNNs, such as Ego-CNN (Tzeng & Wu, 2019) and ChebyGIN (Knyazev et al., 2019) are proposed for graph classification. A theoretical framework to analyze the representational power of GNNs is developed by Xu et al. (2019) , and a neural architecture GIN is proposed. As discussed in Section 1, attention mechanisms used in the existing GNN literature only consider self-attention or the pair-wise attention between two nodes. Recently, attention over an area for a grid structure data (for e.g., images) is proposed by Li et al. (2019) and show promising results for tasks like image captioning and machine translation. With this motivation, and to fill the research gap, we propose subgraph attention which generalizes attention to a subgraph level and show its efficiency for node and graph classification in this paper.

3. SUBGRAPH ATTENTION MECHANISM:

In this section, we describe the building blocks for subgraph attention layer for any arbitrary graph. A Sub-Graph attention network (referred as SubGatt) can be built by stacking multiple layers of subgraph attention. The input to the model is an attributed graph G = (V, E), where

V = {v 1 , v 2 , • • • , v N } is the set of N nodes and x i ∈ R D is the attribute vector of the node v i ∈ V .

The output of the model is a set of node features (or embeddings)

h i ∈ R K , ∀i ∈ [N ] (K is poten- tially different from D). We use [N ] to denote the set {1, 2, • • • , N } for any positive integer N . We define the immediate (or first order) neighborhood of a node v i as N i = {v j |(v i , v j ) ∈ E}.

For the simplicity of notations, we assume an input graph G to be undirected for the rest of the paper, but extending it for directed graph is straightforward.

3.1. SUBGRAPH SELECTION AND SAMPLING:

For each node in the graph, we aim to find the importance of the nearby subgraphs to that node. In general, subgraphs can be of any shape or size. Motivated by the prior works on graph kernels Shervashidze et al. (2011) , we choose to consider only a set of rooted subtrees as the set of candidate subgraphs. So for a node v i , any tree of the form

(v i ), or (v i , v j ) where (v i , v j ) ∈ E, or (v i , v j , v k ) where (v i , v j ) ∈ E and (v j , v k ) ∈ E,

and so on will form the set of candidate subgraphs of v i . We restrict that maximum size (i.e., number of nodes) of a subtree is T . Also note that, the node v i is always a part of any candidate subgraph for the node v i according to our design. For example, all possible subgraphs of maximum size 3 for the node a in Figure 1 Depending on the maximum size (T ) of a rooted subtree, the number of candidate subgraphs for a node can be very large. For example, the number of rooted subgraphs for the node

v i is d vi × vj ∈N (vi) (d vj -1) × v k ∈N (vj )\{vi} |N (v k ) \ {v i , v j }|,

where d v is the degree of a node v and T = 4.

Clearly, computing attention over these many subgraphs for each node is computationally difficult. So we employ a subgraph subsampling technique, inspired by the node subsampling techniques for network embedding (Hamilton et al., 2017) . First, we fix the number of subgraphs to sample for each node. Let the number be L. For each node in the input graph, if the total number of rooted subtrees of size T is more than (or equal to) L, we randomly sample L number of subtrees without replacement. If the total number of rooted subtrees of size T is less than L, we use round robin sampling (i.e., permute all the subtrees, picking up samples from the beginning of the list; after consuming all the trees, again start from the beginning till we complete picking L subtrees). For each node, sample of subtrees remains same for one epoch of the algorithm (explained in Section 3.2) and new samples are taken in each epoch. In any epoch, let us use the notation S i = {S i1 , • • • , S iL } to denote the set (more precisely it is a multiset as subgraphs can repeat) of sampled subgraph for the node v i .

3.2. SUBGRAPH ATTENTION NETWORK:

This subsection describes the attention mechanism on the set of rooted subtrees selected for each epoch of the algorithm. As mentioned, the node of interest is always positioned as the root of each subgraph generated for that node. Next step is to generate a feature for the subgraph. We tried different simple feature aggregations (for e.g., mean) of the nodes that belong to the subgraph as the feature of the subgraph. It turns out that concatenation of the features of nodes gives better performance. But for the attention to work, we need equal length feature vectors (the length is T D) for all the subgraphs. So if a subgraph has less than T nodes, we append zeros at the end to assign equal length feature vector for all the subgraphs. For example, if the maximum size of a subgraph is T = 4, then the feature of the subgraph Next, we use self-attention on the features for the sampled subgraphs for each node as described here. As the first step, we use a shared linear transformation, parameterized by a trainable weight matrix W ∈ R K×T D , to the feature of all the sampled subgraphs S il , ∀i ∈ [N ] and ∀l ∈ [L] selected in an epoch. Next we introduce a trainable self attention vector a ∈ R K to compute the attention coefficient α il which captures the importance of the subgraph S il on the node v i , as follows:

(v i , v j , v k ) is [x i ||x j ||x k ||0] ∈ R 4D ,

EQUATION

Here σ() is a non-linear activation function. We have used Leaky ReLU as the activation function for all the experiments. α il gives normalized attention scores over the set of sampled subgraphs for each node. We use them to compute the representation h i of a node v i as shown in Eq. 1. The main difference between our attention mechanism to that described in Veličković et al. ( 2018) is that we propose attention over the subgraphs, whereas they propose attention over the immediate neighboring nodes. Needless to say, one can easily extend the above subgraph attention by multihead attention by employing few independent attention mechanisms of Eq. 1 and concatenate the resulting representations (Vaswani et al., 2017) . This completes one full subgraph attention layer.

We can stack such multiple layers to design a full subgraph attention network (SubGatt).

3.3. LEARNING AND NODE CLASSIFICATION:

To use subgraph attention network for node classification, we use a softmax (or logistic sigmoid, depending on the number of classes to predict) as the final layer on top of the node representations. We use standard back propagation algorithm with ADAM optimization to learn the parameters of SubGatt by minimizing the cross entropy loss. For one subgraph attention layer, we just need to learn the linear transformation matrix W ∈ R K×T D and the attention vector a ∈ R K . Hence the number of parameters to learn is limited for a smaller value of T (maximum size of a subgraph).

Runtime Complexity of a subgraph attention layer: First we need to compute the set of possible subgraphs (i.e., rooted subtrees of maximum size T ) and their respective features for each node, once for the whole dataset. Computing set of all subgraphs and their features for a node takes d T , where d is the average degree of the nodes in the graph. We set T = 4 for our experiments and average degree of the nodes in real life graphs are small as the networks are highly sparse in nature. Next, in each epoch of SubGatt, we sample L subgraphs for each node and compute Eq. 1. Hence, total runtime for each epoch of subGatt takes O(N LKT D + N d T ), which is linear with the number of nodes, for a sparse graph. Experimentally, we observe SubGatt to converge fast on all the datasets.

4. HIERARCHICAL GRAPH POOLING WITH SUBGRAPH ATTENTION:

As discussed in Section 2, GNN architectures combined with different pooling mechanisms got promising results for graph classification. The main challenge here is to obtain a single representation of the entire graph which can be used as the features for graph classification in an end-to-end fashion. Global pooling mechanisms, where the node representation are averaged or summed to obtain a graph representation for classification is proposed early in the literature (Duvenaud et al., 2015) . Recently, hierarchical graph pooling becomes popular among the researchers, where a graph is converted to a graph of sub-communities in the next level, and then further to a graph of communities and till it becomes only a single node (Ying et al., 2018; Lee et al., 2019) . Our approach, though inspired from the hierarchical pooling proposed by Ying et al. (2018) , combines both global and hierarchical pooling by attention in different levels in the graph. We refer the proposed graph classification architecture by SubGattPool (Sub-Graph and sublevel attention based Pooling mechanism), which is described below.

As shown in Figure 2 , there are R = 4 different levels of the graph in the architecture. The first level is the input graph and the last level is a single node whose features represent the whole input Let us assume that any level graph G r is defined by its adjacency matrix A r ∈ R Nr×Nr and the feature matrix X r ∈ R Nr×K (except for the level 1 graph, which is the input graph and its feature matrix X r ∈ R Nr×D ). Naturally, A 1 and X 1 are given to the GNN. The rth embedding layer and the pooling layer are defined by:

Z r = SubGatt embed (A r , X r ) , r = 1 GCN r,embed (A r , X r ) , r > 1 P r = softmax(SubGatt pool (A r , X r )) , r = 1 softmax(GCN r,pool (A r , X r )) , 1 < r ≤ R -1

(2) Here, Z r ∈ R Nr×K is the embedding matrix of the nodes of G r . The softmax after the pooling is applied row-wise. (i, j)th element of P r ∈ R Nr×Nr+1 gives the probability of assigning node v r i in G r to node v r+1 j in G r+1 . Based on these, the graph G r+1 is constructed as follows,

EQUATION

The matrix P r contains information about how nodes in G r are mapped to the nodes of G r+1 , and the adjacency matrix A r contains information about the connection of nodes in G r . Eq. 3 combines them to generate the connections between the nodes (i.e., the adjacency matrix A r+1 ) of G r+1 . Node feature matrix X r+1 of G r+1 is also generated similarly. Please note that we use SubGatt only after the input graph (i.e., level graph 1) as the presence of some critical structures are high there. In contrast, other level graphs G r (r > 1) have probabilities as edge weights and nodes are connected to many other nodes with weights. Hence, finding subgraphs there would be computational expensive.

Intra-level attention layer: As observed in Lee et al. (2019) , hierarchical GNNs often suffer because of the loss of information in various embedding and pooling layers, from the input graph to the one node summarizing the entire graph. To alleviate this problem, we propose to use attention mechanisms again, to combine features from different level graphs of our hierarchical architecture. We consider level graphs G 2 to G R for this, as their respective numbers of nodes are same across all the graphs in a dataset. We introduce intra-level attention layer to obtain a global feature for each level graphs G r , ∀r = 2, • • • , R -1 (since, G r has only one node, so no feature aggregation is required). More precisely, we use the convolution based self attention within the level graph G r as:

e r = softmax( D -1 2 r A r D -1 2 r X r θ) ∈ R Nr and x r = X T r e r ∈ R K (4)

Here, the softmax to compute e r is taken so that a component of e r becomes the normalized (i.e., probabilistic) importance of the corresponding node in G r . A r = A r + I Nr is the adjacency matrix with added self loops of G r . D is the diagonal matrix of dimension N r ×N r with D(i, i)

= Nr j=1 A ij .

θ ∈ R K is the trainable set of parameters of intra-level attention, which is shared across all the level graphs G r , ∀r = 2, the components of N r dimensional X r θ gives the same for each node. Finally, multiplying that with D

-1 2 r A r D -1 2 r

produces the (normalized) importance of a node based on its own features and the features of immediate neighbors (for one layer of intra-level attention). Hence, x r , which is a K dimensional representation of the level graph G r , is a sum of the features of the nodes weighted by the respective normalized node importance. Please note, the impact from the first few level graphs becomes noisy due to too many subsequent operations in a hierarchical pooling method like in Ying et al. (2018) . But representing level graphs separately by the proposed intra-level attention make their impact more prominent.

Inter-level attention layer: After the application of intra-level attention layer, we have one vector representation x r ∈ R K from G r , ∀r = 2, • • • , R-1, and the feature vector Z R ∈ R K (from Eq. 2). Let's set x R = Z R . Here, we aim to get the final representation of the input graph from x 2 , • • • , x R ; in contrast to a hierarchical pooling which just considers Z R to be the final representation. We introduce inter-level attention layer, which takes x 2 , • • • , x R as input and generates x G ∈ R K as the final graph representation to be fed to a neural classifier. We again use a self-attention as follows:

EQUATION

X inter is the R -1 × K dimensional matrix whose rows correspond to x r (the output of intralevel attention layer for G r ), r = 2, • • • , R. e ∈ R K is a trainable self attention vector. Similar to Eq. 4, softmax is taken to convert e to a probability distribution of importance of different graph levels. Finally, the vector representation x G of the input graph is computed as a weighted sum of representations of different level graphs

G 2 , • • • , G R .

x G is fed to a classification layer of the GNN, which is a dense layer followed by a softmax to classify the entire input graph in an end-to-end fashion. This completes the construction of SubGattPool architecture.

First layer of SubGattPool consists of an embedding SubGatt network and a pooling SubGatt network, which have a total of O(KT D) trainable parameters. Consequent layers of SubGattPool have GCN as embedding and pooling layers, which have a total of O(RKD) parameters. Total number of parameters for R -2 intra-level attention layers is O(K), as θ ∈ R K is shared across the level graphs. Finally the inter-level attention layer has O(K) parameters. Hence, total number of parameters to train in SubGattPool network is O(KT D + RKD), which is independent of both the average number of nodes and the number of graphs in the dataset. We use ADAM on the cross-entropy loss of graph classification to train these parameters.

5. EXPERIMENTAL EVALUATION:

We conduct thorough experimentation in this section. Performance on node classification shows the merit of the subgraph attention (SubGatt) network alone. Whereas, performance on graph classification shows the combined effect of different building blocks of SubGattPool. We also conduct a small experiment with graph visualization to show the merit of individual components of SubGattPool. Experimental Setup: We use 80% of the total node labels for training the algorithms and remaining 20% for testing. Further, 10% of the training set is used as validation. The splits are made randomly. We conduct all the experiments 10 times and reported the mean and standard deviation of classification accuracy on the test sets for all the algorithms. We set all the hyper parameters of SubGatt based on the convergence of loss in the training and the accuracy on the validation set. We use 2 layers of subgraph attention in SubGatt network for all the datasets of node classification. Learning rate is fixed to 0.001 in ADAM. Maximum size (T ) of a subgraph is kept as 4 and the number of subgraphs sampled (L) for each node in an epoch of SubGatt is 32. We use dropout and L2 normalization on the parameters of SubGatt. Embedding dimension (K) is set to 64 for all the datasets. For baselines, we use the best parameterization on the datasets mentioned in their respective papers.

5.1. PERFORMANCE ON NODE CLASSIFICATION:

Performance Analysis: Table 2 shows that the proposed algorithm SubGatt is able to outperform all the baselines on Cora and Pubmed datasets in terms of average classification accuracy, whereas outperformed narrowly by GAT on Citeseer. Interestingly, the standard deviation of SubGatt is always less compared to the baselines on all the datasets which shows the robustness of the algorithm.

5.2. PERFORMANCE ON GRAPH CLASSIFICATION:

Datasets and Baseline Algorithms: We used 4 bioinformatics graph datasets and 2 social network datasets to evaluate the performance of graph classification. Table 1b contains the high-level summary of the datasets (https://bit.ly/2CH22ia). We use a diverse set of baseline algorithms for graph classification. Deep graph kernel (DGK) and graph2vec are unsupervised way to generate a graph kernel and graph embedding respectively. We use SVM on top of them to predict the graph labels. We also use 5 recently proposed state-of-the-art GNN based graph classification techniques: GAM, DIFFPOOL, CapsGNN, GIN and SAGPool. We use publicly available implementation for all the baselines to generate the results.

Experimental Setup: We vary the training size from 15% to 60% for graph classification, and use the remaining for test. All of such splits are done randomly. We use 10% of training as the validation data. Experiments are repeated 10 times and the average classification accuracy and the standard deviation are reported. For SubGattPool, we kept the number (R) of level graphs (including the input graph) to be 3 for all the datasets except PROTEINS. For PROTEINS, we set R to be 4 as the maximum number of nodes in PROTEINS is much higher than the other datasets. The SubGatt layer in SubGattPool samples 12 subgraphs per node for each epoch, with maximum subgraph size as 4. We set the pooling ratio (defined as Nr Nr+1 , ∀r = 1, R -1) to be 0.25 for PROTEINS and 0.1 for the other smaller datasets. We vary the learning rate of ADAM from 0.0001 to 0.001 based on the convergence of cost in the training. Embedding dimension (K) is fixed to 64 for all the datasets. Performance Analysis: Table 3 shows that SubGattPool performs the best on MUTAG dataset for graph classification for all the training sizes. For the other datasets, the best performing algorithm vary over different training sizes. We can see that SubGattPool is always close to the best performing one. For most of the cases, the improvement of performance with increasing training is not very significant. This shows most of these algorithms saturate early with varying training sizes.

5.3. INCREMENTAL EFFECTS OF THE COMPONENTS OF SUBGATTPOOL:

SubGattPool network has two novel components. First, SubGatt layer, which has already performed good for node classification, and second, intra and inter-level attention layers which make Sub-GattPool a mixture of both global and hierarchical pooling strategy. Figure 3 shows the graph

:



Figures and Tables:

Figure 1: Example to motivate subgraph attention Contributions: In this paper, we propose a novel attention mechanism (called subgraph attention) for graph neural networks, which is based on the importance of a subgraph of dynamic size to determine the role of a node in the graph. To validate the efficiency of the mechanism, we propose a node classification algorithm (referred as SubGatt). Further, we propose a graph classification algorithm (referred as SubGattPool) using subgraph attention layer. SubGattPool employs a mixture of hierarchical and global pooling strategies on graph. Thorough experimentation on real world graphs shows the merit of the proposed algorithms over the state-of-the-art.

are: (a), (a,b), (a,d), (a,f), (a,b,c), (a,b,f), (a,b,g), (a,d,e), (a,f,e) and (a,f,b).

where || is the concatenation operation and 0 is the zero vector in R D . Let us denote this derived feature vector of any subgraph S il as xil ∈ R T D , ∀i ∈ [N ] and ∀l ∈ [L].

Figure 2: Architecture of SubGattPool Network for graph classification

based) and DGI (GNN based) are two efficient unsupervised node embedding algorithms. We use SVM to classify the nodes on the embeddings generated by node2vec and DGI. As discussed in Section 2, GCN and GAT are semi supervised GNN based node classification algorithms.

Different datasets used in our experiments

Table content: <table><tr><td/><td/><td/><td/><td>Dataset</td><td>#Graphs</td><td>#Max Nodes</td><td>#Labels</td><td>#Attributes</td></tr><tr><td>Dataset</td><td>#Nodes</td><td>#Labels</td><td>#Attributes</td><td>MUTAG</td><td>188</td><td>28</td><td>2</td><td>NA</td></tr><tr><td>Cora Citeseer Pubmed</td><td>2708 3312 19717</td><td>7 6 3</td><td>1433 3703 500</td><td>PROTEINS NCI1 NCI109 IMDB-BINARY</td><td>1113 4110 4127 1000</td><td>620 111 111 136</td><td>2 2 2 2</td><td>1 NA NA NA</td></tr><tr><td colspan="4">(a) Datasets for node classification</td><td>IMDB-MULTI</td><td>1500</td><td>89</td><td>3</td><td>NA</td></tr><tr><td/><td/><td/><td/><td colspan="4">(b) Datasets for graph classification</td><td/></tr></table>

Citeseer 55.2±0.7 71.3±1.1 75.6±0.8 68.0±1.3 74.3±0.5 Pubmed 80.1±0.7 82.8±0.5 79.0±0.3 78.8±0.7 87.0±0.2 Classification accuracy (%) of different algorithms for node classification.

Table content: <table><tr><td colspan="2">Dataset node2vec</td><td>GCN</td><td>GAT</td><td>DGI</td><td>SubGatt</td></tr><tr><td>Cora</td><td colspan="5">80.9±1.0 84.3±1.8 81.2±2.3 71.0±1.8 87.3±0.9</td></tr></table>

Peer review (iclr2020):
The paper proposes a novel attention approach to graph neural networks which is applicable to both of node and graph classification. The proposed method gives an attention to a subgraph instead of a node by which importance can be controlled as a set of nodes. Further, the authors also introduce two types of attention in the hierarchical structure of the network called intra- and inter- level attention. Considering subgraph attention would be novel and a reasonable idea. The sampling-based approach is a bit naive though it would be easy to implement. Reliability of some results are not clear for me because of the small training set. The intra- and inter- attention approach would be a reasonable, but the relation with subgraph attention is not mentioned in my understanding. These two are independent approaches? Nothing is related to each other? The MUTAG dataset has only 188 graphs, and so, in the smallest case in Table 3, the training data only contains 188*0.15 = 28.2 graphs. For me, learning an attention neural network with less than 30 sample is difficult to evaluate. Is there any rationale that the proposed method works on such a small dataset? In sensitivity analysis in A.1, the performance on different max subgraph size (T) is shown, and the change of the performance is moderate. One of the main claims of the paper is that considering a subgraph (not a node) increases the performance. This results does not show the increase of the performance with the increase of the subgraph size T. Showing the performance with T = 1 can be informative to verify improvement brought by the subgraph attention. Is Figure 3 training set or test set?