Year: 2019

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.

heading: 1 INTRODUCTION
text: 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 vi ∈ V is also associated with an attribute (or feature) vector xi ∈ RD. 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 (Veličković et al., 2018) and graph classification (Lee et al., 2019; 2018) tasks. There are different ways to compute attention mechanisms on graph. Veličković 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 (Veličković 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 vi associated with an attribute vector xi ∈ RD, and a subset of nodes Vs ⊆ V with each node vi ∈ Vs labelled with yi ∈ Ln (set of discrete labels for the nodes of the graph), the task is to predict the label of a node vj ∈ Vu = V \ Vs using the structure and the node attributes of the entire graph and the node labels from Vs. Essentially, this leads to learning a function fn : V 7→ Ln for the given graph G. Graph Classification: Given a set of M graphs G = {G1, G2, · · · , GM}, and a subset of graphs Gs ⊆ G with each graph Gi ∈ Gs are labelled with Yi ∈ Lg (the subscript g stands for ‘graphs’), the task is to predict the label of a graph Gj ∈ Gu = G \ Gs using the structure of the graphs and the node attributes, and the graph labels from Gs. Again, this leads to learning a function fg : G 7→ Lg . Here, Lg is the set of discrete labels for the graphs.
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.

heading: 2 RELATED WORK
text: 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). Veličković 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 (Veličković 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.

heading: 3 SUBGRAPH ATTENTION MECHANISM
text: 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 = {v1, v2, · · · , vN} is the set of N nodes and xi ∈ RD is the attribute vector of the node vi ∈ V . The output of the model is a set of node features (or embeddings) hi ∈ RK , ∀i ∈ [N ] (K is potentially 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 vi as Ni = {vj |(vi, vj) ∈ 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.

heading: 3.1 SUBGRAPH SELECTION AND SAMPLING
text: 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 vi, any tree of the form (vi), or (vi, vj) where (vi, vj) ∈ E, or (vi, vj , vk) where (vi, vj) ∈ E and (vj , vk) ∈ E, and so on will form the set of candidate subgraphs of vi. We restrict that maximum size (i.e., number of nodes) of a subtree is T . Also note that, the node vi is always a part of any candidate subgraph for the node vi according to our design. For example, all possible subgraphs of maximum size 3 for the node a in Figure 1 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).
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 vi is dvi ×∑ vj∈N (vi) (dvj −1)× ∑ vk∈N (vj)\{vi} |N (vk)\{vi, vj}|, where dv 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 beL. 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 Si = {Si1, · · · , SiL} to denote the set (more precisely it is a multiset as subgraphs can repeat) of sampled subgraph for the node vi.

heading: 3.2 SUBGRAPH ATTENTION NETWORK
text: 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 TD) 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 (vi, vj , vk) is [xi||xj ||xk||0] ∈ R4D, where || is the concatenation operation and 0 is the zero vector in RD. Let us denote this derived feature vector of any subgraph Sil as x̂il ∈ RTD, ∀i ∈ [N ] and ∀l ∈ [L]. 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 matrixW ∈ RK×TD, to the feature of all the sampled subgraphs Sil, ∀i ∈ [N ] and ∀l ∈ [L] selected in an epoch. Next we introduce a trainable self attention vector a ∈ RK to compute the attention coefficient αil which captures the importance of the subgraph Sil on the node vi, as follows:
αil = exp(σ(aTWx̂il))∑
l′∈[L] exp(σ(aTWx̂il′))
, hi = σ ( L∑
l=1
αilWx̂il
) ∈ RK , ∀i ∈ [N ] (1)
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 hi of a node vi as shown in Eq. 1. The main difference between our attention mechanism to that described in Veličković 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).

heading: 3.3 LEARNING AND NODE CLASSIFICATION
text: 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 ∈ RK×TD and the attention vector a ∈ RK . 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 dT , 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(NLKTD +NdT ), which is linear with the number of nodes, for a sparse graph. Experimentally, we observe SubGatt to converge fast on all the datasets.

heading: 4 HIERARCHICAL GRAPH POOLING WITH SUBGRAPH ATTENTION
text: 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
graph. Let us denote these level graphs (i.e., graphs at different levels) by G1, · · · , GR. There is a GNN layer between the level graph Gr (i.e., the graph at level r) and the level graph Gr+1. This GNN layer comprises of an embedding layer which generates the embedding of the nodes ofGr and a pooling layer which maps the nodes of Gr to the nodes of Gr+1. We refer the GNN layer between the level graph Gr and Gr+1 by rth layer of GNN, ∀r = 1, 2, · · · , R − 1. The last level graph GR contains only one node, whose feature summarizes the entire input graph. Pleas note, number of nodes N1 in the first level graph depends on the input graph, but we keep the number of nodes Nr in the consequent level graphs Gr (∀r = 2, · · · , R) fixed for all the input graphs (in a graph classification dataset), which help us to design a shared attention mechanism, as discussed later.
Let us assume that any level graph Gr is defined by its adjacency matrix Ar ∈ RNr×Nr and the feature matrix Xr ∈ RNr×K (except for the level 1 graph, which is the input graph and its feature matrix Xr ∈ RNr×D). Naturally, A1 and X1 are given to the GNN. The rth embedding layer and the pooling layer are defined by:
Zr = { SubGattembed(Ar, Xr) , r = 1 GCNr,embed(Ar, Xr) , r > 1 Pr = { softmax(SubGattpool(Ar, Xr)) , r = 1 softmax(GCNr,pool(Ar, Xr)) , 1 < r ≤ R− 1 (2) Here, Zr ∈ RNr×K is the embedding matrix of the nodes of Gr. The softmax after the pooling is applied row-wise. (i, j)th element of Pr ∈ RNr×Nr+1 gives the probability of assigning node vri in Gr to node vr+1j in G r+1. Based on these, the graph Gr+1 is constructed as follows,
Ar+1 = P T r ArPr ∈ RNr+1×Nr+1 and Xr+1 = PTr Zr ∈ RNr+1×K (3)
The matrix Pr contains information about how nodes in Gr are mapped to the nodes of Gr+1, and the adjacency matrix Ar contains information about the connection of nodes in Gr. Eq. 3 combines them to generate the connections between the nodes (i.e., the adjacency matrix Ar+1) of Gr+1. Node feature matrixXr+1 ofGr+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 graphsGr (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 G2 to GR 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 Gr, ∀r = 2, · · · , R− 1 (since, Gr has only one node, so no feature aggregation is required). More precisely, we use the convolution based self attention within the level graph Gr as:
er = softmax(D̃ − 12 r ÃrD̃ − 12 r Xrθ) ∈ RNr and xr = XTr er ∈ RK (4)
Here, the softmax to compute er is taken so that a component of er becomes the normalized (i.e., probabilistic) importance of the corresponding node in Gr. Ãr = Ar + INr is the adjacency matrix
with added self loops ofGr. D̃ is the diagonal matrix of dimensionNr×Nr with D̃(i, i) = Nr∑ j=1 Ãij . θ ∈ RK is the trainable set of parameters of intra-level attention, which is shared across all the level graphs Gr, ∀r = 2, · · · , R − 1. Intuitively, θ contains the importance of individual attributes and
the components of Nr dimensional Xrθ gives the same for each node. Finally, multiplying that with D̃− 1 2 r ÃrD̃ − 12 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, xr, which is a K dimensional representation of the level graph Gr, 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 xr ∈ RK fromGr, ∀r = 2, · · · , R−1, and the feature vectorZR ∈ RK (from Eq. 2). Let’s set xR = ZR. Here, we aim to get the final representation of the input graph from x2, · · · , xR; in contrast to a hierarchical pooling which just considers ZR to be the final representation. We introduce inter-level attention layer, which takes x2, · · · , xR as input and generates xG ∈ RK as the final graph representation to be fed to a neural classifier. We again use a self-attention as follows:
ẽ = softmax(Xinter θ̃) ∈ RR−1 and xG = XTinter ẽ ∈ RK (5)
Xinter is the R − 1 × K dimensional matrix whose rows correspond to xr (the output of intralevel attention layer for Gr), r = 2, · · · , R. ẽ ∈ RK 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 xG of the input graph is computed as a weighted sum of representations of different level graphsG2, · · · , GR. xG 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 ofO(KTD) 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 θ ∈ RK is shared across the level graphs. Finally the inter-level attention layer hasO(K) parameters. Hence, total number of parameters to train in SubGattPool network isO(KTD+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.

heading: 5 EXPERIMENTAL EVALUATION
text: 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.

heading: 5.1 PERFORMANCE ON NODE CLASSIFICATION
text: Datasets and Baseline Algorithms: We use three popular and publicly available citation networks, where each node has a class label, for node classification. The details of the datasets are given in Table 1a (https://linqs.soe.ucsc.edu/data). We use the following state-of-the-art neural network based algorithms as baselines. node2vec (Grover & Leskovec, 2016) (skip-gram
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.
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.
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.

heading: 5.2 PERFORMANCE ON GRAPH CLASSIFICATION
text: 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 NrNr+1 , ∀r 6= 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.

heading: 5.3 INCREMENTAL EFFECTS OF THE COMPONENTS OF SUBGATTPOOL
text: 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 SubGattPool a mixture of both global and hierarchical pooling strategy. Figure 3 shows the graph
visualization using t-SNE (van der Maaten & Hinton, 2008) on MUTAG dataset. Fig. 3b and 3c explain the incremental improvement of performance by only intra and inter level attentions, and SubGatt layer respectively. Finally, Fig. 3d shows the best performance by SubGattPool, which combines all these components into a single network.

heading: 6 DISCUSSION AND FUTURE WORK
text: In this paper, we introduce subgraph attention mechanism over graph structured data. We also propose a novel graph pooling algorithm which uses subgraph attention, and combines different hierarchical levels of graphs by separate attention layers. Current formulation of subgraph attention is based on heuristic and backed by experimental results. So in future, we would like to theoretically examine its expressiveness power for node and graph representation. Also we would like to conduct experiments in the inductive setting for node classification with SubGatt network.

heading: A APPENDIX
text: A.1 SENSITIVITY ANALYSIS OF SUBGATT NETWORK
SubGatt network has three important hyper parameters. They are: (i) Maximum size of a subgraph (T ), (ii) Number of subgraphs sampled per node in each epoch (L) and (iii) Dimension of the final node representation or embedding (K) (See Eq. 1) and (iv) Number of SubGatt layers used in the network. We conduct node classification experiments on Cora. Figure 4 shows the variation of the performance of SubGatt network for node classification with respect to all these hyper-parameters. We have shown both average node classification accuracy and standard deviation over 10 repetition for each experiment. Interestingly, the variation is less with respect to all the hyper-parameters and hence it shows the robustness of SubGatt. Please note, when we are varying one hyper-parameter of SubGatt, the values of all other hyper-parameters are fixed to the values mentioned in Section 5.1.
A.2 NODE CLASSIFICATION RESULTS ON THE PUBLICLY AVAILABLE SPLITS OF THE DATASETS
Some existing node classification and semi-supervised node representation techniques (Kipf & Welling, 2017; Veličković et al., 2018) use publicly available splits (into training, validation and test sets) of some popularly used datasets such as Cora, Citeseer and Pubmed to show the merit of the proposed algorithms. These splits were introduced in (Yang et al., 2016). However, these splits were created randomly, as mentioned in the cited paper: “We randomly sample 20 instances for each class as labeled data, 1000 instances as test data”. Kipf & Welling (2017) introduces “an additional validation set of 500 labeled examples for hyperparameter optimization”. We use exactly the same splits of the nodes as in (Kipf & Welling, 2017) and report the results in Table 4. It turns out that SubGatt is outperformed by GAT on this publicly available splits of the datasets, whereas the performance is competitive to GCN. This is slightly contradicting to what we observe in Table 2, where the performance of SubGatt is mostly superior to GCN and GAT on the random splits of the dataset into training, validation and test sets. One possible reason can be the larger training size (80% training, in which 10% was used only for validation) of the node classification experiments
conducted in Section 5.1. Compared to that, the publicly available split has much lesser training size and SubGatt being a more complex model than GCN and GAT, needs more training data to effectively train the parameters.

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