Subgraph Attention for Node Classification and Hierarchical Graph Pooling
Authors: Sambaran Bandyopadhyay
Manasvi Aggarwal
M. N. Murty
Venue:  (2020)
Keywords: Graph Neural Network
Graph Attention
Graph Pooling
Node Classification
Graph Classification
Network Representation Learning

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.

Under review as a conference paper at ICLR 2020
SUBGRAPH ATTENTION FOR NODE CLASSIFICATION AND HIERARCHICAL GRAPH POOLING
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks have gained significant interest from the research commu- nity for both node classification within graph and graph classification within a set of graphs. Attention mechanism applied on the neighborhood of node improves the performance of graph neural networks. Typically, it helps to identify a neigh- bor node which plays more important role to determine the label of the node under consideration. But in real world scenarios, particular subset of nodes together, but not the individual nodes in the subset, may be important to determine the la- bel of node. To address this problem, 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 archi- tecture also uses attention to determine the important nodes within a level graph and attention to determine the important levels in the whole hierarchy. Competi- tive performance over the offte-of-thearr for both node and graph classification shows the efficiency of the algorithms proposed this paper.
INTRODUCTION
Graphs are the most suitable way represent different types of relational data such social networks, protein interactions and molecular structures. Typically, A graph is represented by G = -V, E), where V the set of nodes and E is the set of edges. Further, each node 2/ V is also associated with an attribute (or feature) vector x, E RR Recent advent of deep representa- tion 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 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 different ways 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 node on the embedding of the other node by learning an attention vector. [ee 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 al. 2019) propose self attention pooling of the nodes which is then used to capture the importance of the node 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 substructure in the vicinity of a node e 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 [] 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, O: 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 sub- graph (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

---

Under review as a conference paper at ICLR 2020
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 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 = EV,E) with each node e2 associated with an attribute vector x; R2, and a subset of nodes V. S. V with each node 12 E V, labelled with y E C, (set of discrete labels for the nodes of the graph), the task is to predict the label of a node Uj E Vu V \ Vv using the structure and the node attributes of the entire graph and the node labels from Vg- Essentially, this leads to learning a function fn : V + Ln for the given graph G.
Graph Classification: Given set of M graphs G
Gg. Gmr. and subset of graphs
9, S 9 with each graph G; E 9, are labelled with Y; E Lu (the subscript g stands for 'graphs") ), the task to predict the label of graph G3 E 9v = 9 \ 9, using the structure of the graphs and the node attributes, and the graph labels from Gs. Again, this leads to learning a function fg 9 + bg- Here, Lg is the set of discrete labels for the graphs.
Contributions:
In this paper, we propose a novel attention mecha- nism (called subgraph attention) for graph neural networks, which is based on the importance of subgraph of dynamic size to deter- mine the role of a node in the graph. To validate the efficiency of the mechanism, we propose a node classification algorithm (referred SubGatt). Further, we propose a graph classification algorithm (re- ferred 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,
10001]
[0101]
(0010)
8
100-10)
[1000]
1000 -1]
1010-1)
Figure 1: Example to moti- vate subgraph attention
RELATED WORK
A survey on network representation learning and graph neural net- works can be found in Wu et al. (2019). Here we briefly discuss some more prominent approaches for node classification and graph classification. Kipf' & Welling (017)) 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) pro- pose GAT which uses attention mechanism to learn the importance of 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 graph.
On the other hand, graph classification is a classical problem in machine learning. Graph kernel Vishwanathan et al. (2100) based approaches remain to be the ofate-of-the-art for graph classifica- tion 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 ker- nels 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. Re- cently, 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 GCN (Duvenaud et al. 2015)
and more advanced deep learning architectures that operate over the sets (Gilmer et al. [2] Zhang et al. 2018) have been used. Attention based graph classification technique GAM (Lee et al. 201 8)
is proposed, which processes only portion of the graph by adaptively selecting a sequence of infor- mative nodes. DIFFPOOL (Ying et al.) 2018)) is recently proposed hierarchical GNN which uses a GCN based pooling to create a set of hierarchical graphs in each level. Lee et al. (2119) propose 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., (017]). Capsule GNN (CapsGNN) is proposed Xinyi & Chen 2019). Different extensions of GNNs, such Ego-CNN (T'zeng & Wu 2019) and
2

---

Under review as a conference paper at ICLR 2020
ChebyGIN (Knyazev et al. 2019) are proposed for graph classification. A theoretical framework to analyze the representational power of GNNs is developed (y et al. (2019). and a neural architec- ture GIN is proposed. As discussed in Section | attention mechamisms used in the existing GNN literature only consider self-attention or the pair-wise attention between two nodes. Recently, atten- tion over an area for a grid structure data (for e.g., images) is proposed by[[. 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 the model is an attributed graph G = (V, F),, where == 02, uNv] } is the set of N nodes and T; E TR& is the attribute vector of the node in E V. The output of the model is set of node features (or embeddings) h2 E R.K, Vi [N] (K' is poten- tially different from D). We use [MV] to denote the set {1, 2, ... .N} for any positive integer N. We define the immediate (or first order) neighborhood of node u, as M, = {u,((v, 0ÿ) E 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 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 al. (201T), D) we choose consider only a set of rooted subtrees as the set of candidate subgraphs. So for a node ni any tree of the form (v;), or (M;, where (v,, ) E F, or (vx, ej vx)) where (v;, U2) E E and (ny, 0x) E F,, and so on will form the set of candidate subgraphs of t. We restrict that maximum size (i.e., number of nodes) of a subtree is T. Also note that, the node es is always a part of any candidate subgraph for the node v, according to our design. For example, all possible subgraphs of maximum size 3 for the node in Figure aree: (a), (a,b), (a,d), (a,f), (a,b,c), (f,,,)), (a, (a,d,e), (a,f,e) and (a.f.b).
Depending on the maximum size (T) of rooted subtree, the number of candidate subgraphs for a node can be very large. For example, the number of rooted subgraphs for the node ny is de, x 1) Σ (((w)) \ 2y}l where d, is the degree of a node and T = 4.
Σ
ey (())
Clearly, computing attention over these many subgraphs for each node is computationally difficult. So employ subgraph subsampling technique, inspired by the node subsampling techniques for network embedding (Hamilton et (017). 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, = {S... ... S.t } to denote the set (more precisely it is multiset as subgraphs can repeat) of sampled subgraph for the node U,.
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 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 the end to assign
3

---

Under review as a conference paper at ICLR 2020
equal length feature vector for all the subgraphs. For example, if the maximum size of a subgraph ' = 4, then the feature of the subgraph 2y, Uy) is [=,||r,||a>||0 E R4", where || is the concatenation operation and is the zero vector in RP. Let us denote this derived feature vector of any subgraph Sa žα E ITD,, vi [A] and VI E [L].
Next, we use self-attention on the features for the sampled subgraphs for each node as described here. As the first step. matrix W E RK*TD) to the feature of all the sampled subgraphs Sa, vi E [MV] and A/ E [L] selected in epoch. Next we introduce trainable self attention vector R.K to compute the attention coefficient og which captures the importance of the subgraph Sy on the node Ui as follows:
shared linear transformation, parameterized by trainable weight
explo of Wia))
0y = Σ erplo(a"Waar)) PE[L]
h; =
an ant E ERK, [iE
(I)
Here o() is a non-linear activation function. We have used Leaky ReLU as the activation function for all the experiments. oa gives normalized attention scores over the set of sampled subgraphs for each node. We use them to compute the representation h2 of node v, as shown Eq. [ 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 multi- head attention by employing few independent attention mechanisms of Eq. [ and concatenate the resulting representations (Vaswani 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 softmax (or logistic sigmoid, depending on the number of classes to predict) as the final layer 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 E RXTTD and the attention vector a E R² Hence the number of parameters to learn is limited for smaller value of T' (maximum size of 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 7) 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',, where d is the average degree of the nodes in the graph. We set T 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. T Hence, total runtime for each epoch of subGatt takes O(N LKTD + NNd"). which is linear with the number of nodes, for a sparse graph. Experimentally, we observe SubGatt converge fast on all the datasets.
for our experiments and average
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 representa- tion 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 graph converted to graph of sub-communities in the next level, and then further to graph of communi- ties and till it becomes only a single node (Ying et al. 2018 Lee 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 classi- fication architecture by SubGattPool (Sub- BaabGrrphhoee 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 single node whose features represent the whole input
4

---

Under review as a conference paper at ICLR 2020
Level Graph (Inpu))
Level Graph 2
Gatt
GCN Emb
Level Graph
GON Emb
Level Graph
Classfication
Layer
Emb
GCN Pool
GCN Pool
Gat!
Pool
Inter-laval Attention
Intraiovall Attention
Sub communities in Input graph
Intra-ievel Attertion
Figure 2: Architecture SubGautPool Network for graph classification
graph. Let denote these level graphs (i.e., graphs different levels) by G ,..... G There is GNN layer between the level graph G (i.e., the graph at level r) and the level graph G This GNN layer comprises an embedding layer which generates the embedding of the nodes of G" and a pooling layer which maps the nodes of G" to the nodes of Gr+1, We refer the GNN layer between the level graph G" and G by rth layer of GNN, Vr = 1.2,
1. The last level graph RR 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 N, in the consequent level graphs G" (Vr 2, ..... Rt fixed for all the input graphs (in graph classification dataset), which help us to design shared attention mechanism, as discussed later.
Let us assume that any level graph G" is defined by its adjacency matrix A, E N. and the feature matrix X, E N.NK (except for the level graph, which is the input graph and its feature matrix X, E RD).D). Naturally, A1 and X₃ are given to the GNN. The rth embedding layer and the pooling layer are defined by:
= [SubGattembed Ar, Xr), = Ar. r>>
Softmax(SubGatt, (Art Xx)) r= (A,, 1< --1
Z, -
P. P-=
softmax(GCN
(2)
Here, Z, E RNNKK the embedding matrix of the nodes of G". The softmax after the pooling applied row-wise. (i,j)th element of P, NNN,NN41 gives the probability of assigning node v/ in G" to node of in Gr+1, Based on these, the graph G*+1 is constructed as follows,
Ar+1 = P" A,P, E N and X,+1 = Pf Zr E RNNIIKK
The matrix P. contains information about how nodes in G" are mapped to the nodes of Gr+1, and the adjacency matrix A, contains information about the connection of nodes in G". Eq. combines them to generate the connections between the nodes (i.e., the adjacency matrix A,+1) of G Node feature matrix X,+1 of G*+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 1) have probabilities as edge weights and nodes 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 be- cause of the loss 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 use attention mechanisms again, to combine features from different level graphs of our hierarchical architecture. We consider level graphs G2 H for this, their respective numbers of nodes are same across all the graphs in dataset. We introduce intra-level attention layer to obtain global feature for each level graphs G", Vr 2.... R (since, G" has only one node, so no feature aggregation is required). More precisely, we use the convolution based self attention within the level graph G" as:
= softmax (D, A, x,0) E R.N. and x.' = x e, E R
(4)
Here, the softmax to compute e, is taken so that component of e, becomes the normalized (i.e., probabilistic) importance of the corresponding node in G". A, A, + IN. is the adjacency matrix N.
with added self loops of G". D' is the diagonal matrix of dimension N, x N, with D(i, Σ Ag.
j=1
0 E RRK is the trainable set of parameters of intra-level attention, which is shared across all the level graphs G", Vr 2.... R - 1. Intuitively, contains the importance of individual attributes and
5

---

Under review as a conference paper at ICLR 2020
Dataset
#Graphs
#Max Nodes
#Labels
#Attribures
Dataset
#Nodes
#L.abel
#Attribures
MUTAG
Cora
2708
7
1433
PROTEINS
1113
620
2
Pubmed
Citeseer
19717
3312
6
3703
IMDB-BINARY
NC1109
NCI1
4127
4110
1030
111
136
111
2
2
2
NA
NA
IMDB-MULTI
1500
3
NA
(a) Datasets for node classification
(b) Datasets for graph classification
Table Different datasets used in our experiments
the components of N, dimensional X,0 gives the same for each node. Finally, multiplying that with D, D, produces the (normalized) importance of node based on its own features and the features of immediate neighbors (for one layer of intra-level attention). Hence, x", which is a K dimensional representation of the level graph G", is 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 hierarchical pooling method like in Ying ctt 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 2, IR K from G", Vr 2, R 1, and the feature vector Zn E R& (from Eq. 2 Let's set I = ZR. Here, we aim to get the final representation of the input graph from æ ... .R. in contrast hierarchical pooling which just considers ZR be the final representation. We introduce inter-level attention layer, which takes 22. ZR as input and generates x E RK as the final graph representation be fed a neural classifier. We again use self-attention as follows:
ē = softmax(Xitted) E RR R-1 and x = X RR
(5)
Xinter is the R 1 x K dimensional matrix whose rows correspond to x" (the output of intra- level attention layer for G*), 2.... R. RK is trainable self attention vector. Similar to Eq. 4 softmax is taken to convert to probability distribution of importance of different graph levels. Finally, the vector representation G of the input graph is computed representations of different level graphs G² ....... G x is fed to classification layer of the GNN, which dense layer followed by a softmax classify the entire input graph in an end-to-end fashion. This completes the construction of SubGattPool architecture.
weighted sum of
First layer of SubGattPool consists of an embedding SubGatt network and pooling SubGatt net- work, which have total of O(KTD) trainable parameters. Consequent layers of SubGattPool have GCN as embedding and pooling layers, which have a total of O O(RKD) parameters. Total number of parameters for R 2 intra-level attention layers is O(K), as 0 E IRK is shared across the level graphs. Finally the inter-level attention layer has O(K) parameters. Hence, total number of parame- ters to train in SubGattPool network is O(KT (RDD), which is independent of both the average number nodes and the number of graphs in the dataset. We use ADAM on the cross-entropy loss of graph classification to train these parameters.
EXPERIMENTAL EVALUATION
We conduct thorough experimentation in this section. Performance node classification shows the merit of the subgraph attention (SubGatt) network alone. Whereas, performance on graph classifica- tion 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.
5.1 PERFORMANCE ON NODE CLASSIFICATION
We use three popular and publicly available citation networks, where each node has class label, for node classification. The details of the datasets are given in Table Ia (https::/ /tttps://lings. soe ucsc. edu/ data). We use the following state-of-the-a neural network based algorithms as baselines. node2vec (Grover & Leskoved 2016) (skip-gram
Datasets and Baseline Algorithms:

---

Under review as a conference paper at ICLR 2020
Dataset
node2vee
GCN
GAT
DGI
SubGatt
Cora
80.9=1.0
8..3+1.8
81.2+22.3
71.0+1..
0. 7..3+0.5
Citeseer
5..2=0.7
71.3+1.1
7..6=0.8
68.0 1..0
Pubmed
80.1
82.8.0.55
78.8 79.010.3
87.0.10.2
Table 2: Classification accuracy (%) of different algorithms for node 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.
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 classifica- tion accuracy on the test sets for all the algorithms. We set all the hyper parameters of SubGatt based on the convergence of loss 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 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, use the best parameterization on the datasets mentioned in their respective papers.
Experimental Setup:
Table shows that the proposed algorithm SubGatt is able to outperform all the baselines Cora and Pubmed datasets in terms of average classification accuracy, whereas out- performed 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.
Performance Analysis:
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 Tb contains the high-level sum- 1y mary of the datasets (https: (ittpp:://bit.1L//////aa 2CH22ia), We use a diverse set of baseline algorithms
for graph classification. Deep graph kernel (DGK) and graph2vec are unsupervised way to generate graph kernel and graph embedding respectively. We use SVM on top of them to predict the graph labels. We also use recently proposed state-of-the ofttth-tttattttt GNN based graph classification techniques: GAM, DIFFPOOL, CapsGNN, GIN and SAGPool. We use publicly available implementation for all the baselines to generate the results.
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 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 N. Vr + R 1) 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.
Experimental Setup:
N.,,
Performance Analysis: Table 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 shows the graph
7

---

Under review as a conference paper at ICLR 2020
Algocihm
15
Training Size(%)
Algorithm
30
Training Size(
68
DGiK
1.44:1.3
15.8=1.2
76.22009
1.55e:1.5
DGK
653100
66.31:3
678113
68.1116
graph2ves
64.6-23.6
61.7493.1
67.143311
68.0-55.7
graph2vec
62.91:15
63.6211
664117
67.742.1
64.3-1:5.5
GAM
61.11:20
613118
998114
59.6.1:188
DIFFPOOL
61.2:15.2
71.825.5
78.5
76.94:5.6
DIFFPOOL
67.442.
670122
686114
68.133311
CupsLNNN
52.54:2.6
68.5#55.0
67.5433.6
66.8-55.5
CapstiNN
61.1425
7.110
GIN
70.24:5.4
76.5::3.8
77.5-33.2
76.8:1-4.8
GIN
6222428
63.01:.11
619116
63.1133
+:2.7
SAGPool
68 68.61443
70.74:32
708 1:12
68.0
SubGattPool
80.8 80.8-22.6
8..9:22.6
$1.1-112
80.3-:3.1
SubGattPool
714110
71221-1
72.21:10
72.41:66
(a) MUTAG
(b) PROTEINS
Triining Size(%)
Training Size ())
Algocitim
15
30
45
60
Algorithm
15
30
45
60
DGK
60.52:0.7
6..
62.3
62.1=066
DGK
55021.1
$6.1000
5802008
57.74-033
graph2vee
6..65:100
1..7=1.0
64.--0.
64.7=29
62.14:111
64.3:00.7
65.7408
65022.
51,44:122
51.1-13
DIFFROOL.
61.02209
1.
63.2211
64.--.1
DIFFPOOT
60111:3
62.22:12
62.71:3
61.111
CapsCINN
55.1=28
574=25
624=1.2
628822
CapstENN
519415
605:22
618416
63111:2
59.8:209
65.020.3
GIN
60.712.3
634100
64411:5
66.5-122
65.1218
6522-20
SAGiPool
57.744
66.122.11
669114
66:110
SubGattPool
65.8 -0.7
6.
69
70.4 0.7
SubCartPool
64.6209
67.2:2.06
678106
67.7
(c) NCI1
NCHO9
Trining Size(S)
Training Soo88)
Algocitim
Algoritim
DGK
60.13:233
610E18
62.32:211
63.3211
DGK
401124
420113
419109
21611]
GAM
48.94 0.2
48.3+-0.4
50.2+:2.1
50.9=:177
GAM
52.7 0.2
52.440.6
32.34055
320406
DIFFPOOL
61.0:11.4
6..3
64.3:8233
65.4-:2.1
DIFFPOOL
4233422
44.24:33
45.1422
4564:3
CapsGiNN
48.94-.11
48.02:0.4
47.9-0.2
CapsENN
GIN
66.4::2.2
64.09:299
68.2-115
08.1-:200
GIN
43.74:
468:21
478+12
475426
SAGioool
58.7 8:5.1
59.8 1:7.7
62.5 1:5.6
63.0::3.9
SAGPool
4244::3
43.7:621
44.
45881111
SubGattPool
68.2:0.6
SubGartPoo
44211
462404
#65112
47.1111
(c) IMDB-BINARY
(f) IMDB-MULTT
Table 3: Classification accuracy (%) of graph classification on multiple datasets.
(a) DIFFPOOL
(b) SubGattPool (SubGart
(c) SubGattPool \I-I--A
(d) SubGartPoo
Figure 3: I-SNE visualization of the graphs from MUTAG (different colors show different labels of the graphs) by the representations generated by: (a) DIFFPOOL: (b) SubGattPool, but the SubGatt embedding and pooling layers being replaced by GCN; (c) SubGattPool without intra and inter layer attention; (d) the complete SubGattPool network. Compared to (a). there are improvement of performances for both the SubGatt layer and intra/inter-level attention individually. Finally different classes separated most by SubGattPool which again shows the merit of the proposed algorithm.
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.
DISCUSSION AND FUTURE WORK
In this paper, we introduce subgraph attention mechanism over graph structured data. We also propose novel graph pooling algorithm which uses subgraph attention, and combines different hierarchical levels of graphs by separate attention layers. Current formulation subgraph attention based on heuristic and backed by experimental results. So in future, would like 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.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Gura and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, pp. 2224-2222222222222212222222----2 2232, 2015.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Learning-Volume Volume 70, pp. 1263-1272. JMLR, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pp. 855-864. ACM, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1025-1035, 2017.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Boris Knyazev, Graham W Taylor, and Mohamed R Amer. Understanding attention in graph neural networks. In Advances in Neural Information Processing Systems, 2019.
John Boaz Lee, Ryan Rossi, and Xiangnan Kong. Graph classification using structural attention. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 1666-1674. ACM, 2018.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International Confer- ence on Machine Learning, pp. 3734-3743, 2019. 2019.
Yang Li, Lukasz Kaiser, Samy Bengio, and Si Si. Area attention. In Proceedings of the 36th Inter- national Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, Califor- nia, USA, pp. 3846-3855, 2019. URL http:::/poccceinggsss mlr wwt.pmp..s...///.p...... html
A. Narayanan, M. Chandramohan, R. Venkatesan, L Chen, Y. Liu, and S. Jaiswal. graph2vec: Learning distributed representations of graphs. In 13th International Workshop on Mining and Learning with Graphs (MLGWWrkshhop 2017), 2017.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In International conference on machine learning, pp. 2014-2023, 2016.
Sara Sabour, Nicholas Frosst, and Geoffrey E Hinton. Dynamic routing between capsules. In Advances in neural information processing systems, p 3856-3866, 2017.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisneille-lehman graph kernels. Journal of Machine Learning Research, 12(Sep):2539- 2561, 2011.
Ruo-Chun Tzeng and Shan-Hung Wu. Distributed, egocentric representations of graphs for detecting critical structures. In International Conference on Machine Learning, pp. 6354-6343 6362, 2019.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of Ma-
chine Learning Research, 9:2579- 2605, 2008. URLhttpp:/www. jml org./pppess/v//
vande SaadeermaatenDaa.naa
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Fukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6000 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. URL htt./htttss//openrett net. wtt:/oorrm...erreeeeee... tt

---

Under review as a conference paper at ICLR 2020
Petar Veličkovié, William Fedus, William L Hamilton, Pietro Liö, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations, 2019. URL httpp///..aaaaaaeeeeoees..crr/aa
URUhttps///peeeeeeeeee net Wow.:m2dddd
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, 101112222011122,,, 2010.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey on graph neural networks. arXiv preprint vrXiv:/901.00566 2019.
Zhang Xinyi and Lihui Chen. Capsule graph neural network. International Conference on Learn- ing Representations, 2019. /tL./tttpa////ppeeeeveee net. Fet/ By 18
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural
networks? In International Conference on Learning Representations, 2019. URL https:
//openzeview. wwtp/orommaad-reeeeereeeee ryGs1ii55
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374. ACM, 2015.
Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. arXiv preprint arXiv:1603.00 2016.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Advances in Neural Infor- mation Processing Systems, pp. 4800 4810,4480,.0 2018.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5175, 2018.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018
10

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 SENSITIVITY ANALYSIS OF SUBGATT NETWORK
SubGatt network has three important hyper parameters. They are: (i) Maximum size of subgraph (I', (ii) Number of subgraphs sampled per node in each epoch (L) and (iii) Dimension of the final node representation or embedding (K) (See Eq. I 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 all these syper-parameen We have shown both average node classification accuracy and standard deviation over 10 repetition for each experiment. Interestingly, the variation is less with respect all the hyper-parameterss and hence it shows the robustness of SubGatt. Please note, when are varying one hyper-paramett of SubGatt, the values of all other
are fixed to the values mentioned in Section 5.1
Accuracy (%)
Accuracy (%)
88.5
88.0
88.0
87.5
87.5
87.0
87.0
86.5
86.5
86.0
86.0
85.5
85.5
2
3
4
5
16
32
64
128
Max. Subgraph Size (T)
#Subgraphs Sampled (L)
(a)
(b)
Accuracy (%)
Accuracy (%)
88.5
88.5
88.0
88.0
87.5
87.5
87.0
87.0
86.5
86.0
86.5
85.5
86.0
85.0
32
64
128
256
1
2
3
4
Embedding Dimen. (K)
# SubGatt Layers
Figure 4: Sensitivity analysis of SubGatt network for node classification on Cora with respect to different hyper-parameters
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 Veličković 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 (2077) 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 this publicly available splits of the datasets, whereas the performance 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 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
11

---

Under review as a conference paper at ICLR 2020
Dataset
#Trrin/Validattion/Test
GCN
GAT
SubGatt
Cora Citeseer
140/500/1000
81.5
83.0++0.7
81.4
120/500/1000
70.3
7..5+
70.5
Pubmed
60/500/1000
79.0
79.0.10.3
78.2
Table 4:
Classification accuracy (%) of different algorithms for node classification the publicly available node splits into training. validation and sets.
conducted in Section 5.1 size and SubGatt being a more complex model than GCN and GAT, needs more training data to effectively train the parameters.
Compared to that, the publicly available split has much lesser training
12


Reviews:
[{"review_id": "S1gTvA5g5S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a subgraph attention method for graphs. Recently, many papers have shown that attention is a very important concept. However, there was no attention method for graph input structures, while a particular subset of nodes is very crucial to make the output.  \n\nThis paper first proposes the graph attention mechanism and hierarchical graph pooling idea. The attention basically subsamples subtrees so that each node can have the same number of attention candidates. Then, we can the attention network as many other papers. Experimental results show that the proposed attention based algorithm outperforms other algorithms.\n\nI think this paper attacks a very important issue \"graph attention\" and have a very nice algorithm and results. Overall, my recommendation is \"accept\".\n\nCons.\nIt would better if the authors test some other different attention networks along with the current way.\n\n================================================\nI've read all discussions and changed my score. The novely of this work is not enough as R4 pointed out.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "H1eP1XmtcH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes a subgraph attention mechanism on graphs. Compared to the previous graph attention layer, the node in the graph attends to its subgraph. The subgraph is represented by an aggregated feature representation with a sampled fixed-size subgraph. The methods are evaluated on both node classification and graph classification problems.\n\nI have major concerns about the novelty, and experiments in this work.\n\n1. The motivation is not clear. Using a subgraph or neighborhood to represent a node is reasonable. However, this work samples a subset of nodes from the one-hop neighborhood and aggregates them for attention mechanism. It is very similar to a GCN + GAT. The sampling process even loses some neighborhood information in the graph.\n\n2. The experimental setups are very strange. In Table 2, the methods are compared to GCN and GAT on node classification problems. The performance of GAT is too low and even lower than that reported in GAT. Can authors explain this? It is highly recommended to use the same experimental settings as in GCN and GAT. The same problem exists in Table 3. Can authors provide a performance comparison based on the same settings in GIN?\n\n3. The performance improvements are very unstable and marginal. In Table 3, the proposed methods can not compete with previous methods especially on large datasets like IMDB-MULTI. I wonder how the proposed methods perform on very large datasets such as reddit.\n\n4. Can authors provide comparisons with a simple GCN+GAT? ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "B1eyv-pYYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nConsidering 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.\n\nThe 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?\n\nThe 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?\n\nIn 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.\n\nIs Figure 3 training set or test set?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Initially, two reviewers gave high scores to this paper while they both admitted that they know little about this field. The other review raised significant concerns on novelty while claiming high confidence. During discussions, one of the high-scoring reviewers lowered his/her score. Thus a reject is recommended.
Decision: Reject