Attention-based Graph Neural Network for
Semi-supervised Learning
Kiran K. Thekumparampil∗, Chong Wang†, Sewoong Oh‡, and Li-Jia Li§,

arXiv:1803.03735v1 [stat.ML] 10 Mar 2018

March 13, 2018

Abstract
Recently popularized graph neural networks achieve the state-of-the-art accuracy on a number of standard benchmark datasets for graph-based semi-supervised learning, improving significantly over existing approaches. These
architectures alternate between a propagation layer that aggregates the hidden states of the local neighborhood and
a fully-connected layer. Perhaps surprisingly, we show that a linear model, that removes all the intermediate fullyconnected layers, is still able to achieve a performance comparable to the state-of-the-art models. This significantly
reduces the number of parameters, which is critical for semi-supervised learning where number of labeled examples
are small. This in turn allows a room for designing more innovative propagation layers. Based on this insight, we
propose a novel graph neural network that removes all the intermediate fully-connected layers, and replaces the propagation layers with attention mechanisms that respect the structure of the graph. The attention mechanism allows us to
learn a dynamic and adaptive local summary of the neighborhood to achieve more accurate predictions. In a number
of experiments on benchmark citation networks datasets, we demonstrate that our approach outperforms competing
methods. By examining the attention weights among neighbors, we show that our model provides some interesting
insights on how neighbors influence each other.

1

Introduction

One of the major bottlenecks in applying machine learning in practice is collecting sizable and reliable labeled data,
essential for accurate predictions. One way to overcome the problem of limited labeled data is semi-supervised learning, using additional unlabeled data that might be freely available. In this paper, we are interested in a scenario when
this additional unlabeled data is available in a form of a graph. The graph provides underlying pairwise relations
among the data points, both labeled and unlabeled.
Of particular interest are those applications where the presence or absence of an edge between two data points is
determined by nature, for instance as a result of human activities or natural relations. As a concrete example, consider
a citation network. Each node in the graph is a published research paper, associated with a bag-of-words feature vector.
An (directed) edge indicates a citation link. Presence of an edge indicates that the authors of a paper have consciously
determined to refer to the other paper, and hence captures some underlying relation that might not be inferred from
the bag-of-words feature vectors alone. Such external graph data are available in several applications of interest, such
as classifying users connected via a social network, items and customers connected by purchase history, users and
movies connected by viewing history, and entities in a knowledge graph connected by relationships. In this paper, we
are interested in the setting where the graph is explicitly given and represents additional information not present in the
feature vectors.
The goal of such graph-based semi-supervised learning problems is to classify the nodes in a graph using a small
subset of labeled nodes and all the node features. There is a long line of literature on this topic since [7] which seeks
graph cuts that preserve the known labels and [50] which uses graph Laplacian to regularize the nearby nodes to have
similar labels. However, [27] recently demonstrated that the existing approaches can be significantly improved upon
∗ Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, thekump2@illinois.edu. Work done
as an intern at Google Inc.
† Google Inc., Kirkland, chongw@google.com
‡ Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana-Champaign, swoh@illinois.edu
§ Google Inc., Sunnyvale, lijiali@cs.stanford.edu

1

on a number of standard benchmark datasets, using an innovative neural network architecture on graph-based data
known collectively as graph neural networks.
Inspired by this success, we seek to understand the reason behind the power of graph neural networks, to guide our
design of a novel architecture for semi-supervised learning on graphs. To this end, we first found that a linear classifier
of multinomial logistic regression achieves the accuracy comparable to the best known graph neural network. This
linear classifier removes all intermediate non-linear activation layers, and only keeps the linear propagation function
from neighbors in graph neural networks. This suggests the importance of aggregation information form the neighbors
in the graph. This further motivates us to design a new way of aggregating neighborhood information through attention
mechanism since, intuitively, neighbors might not be equally important. This proposed attention-based graph neural
network captures this intuition and (a) greatly reduces the model complexity, with only a single scalar parameter at
each intermediate layer; (b) discovers dynamically and adaptively which nodes are relevant to the target node for
classification; and (c) improves upon state-of-the-art methods in terms of accuracy on standard benchmark datasets.
Further, the learned attention strengths provide some form of interpretability. They provide insights on why a particular
prediction is made on a target node and which neighbors are more relevant in making that decision.

2

Related Work

Given a graph G(V, E) with a set of n nodes V and a set of edges E, we let Xi ∈ Rdx denote the feature vector at
node i and let Yi denote the true label. We use YL to denote the labels that are revealed to us for a subset L ⊂ V . We
let X = [X1 , . . . , Xn ] denote all features, labeled and unlabeled.
Traditionally, semi-supervised learning using both labeled and un-labled data has been solved using two different
approaches - Graph Laplacian based algorithms solving for locally consistent solutions [47] and Expectation Maximization based algorithms [33] where true-labels of the unlabeled data points are considered as the latent variables of
a generative model.
Graph Laplacian regularization. Based on the assumption that nearby nodes in a graph are more likely to have the
same labels, the graph information has been used as explicit regularization:
L(X, YL )

=

Llabel (XL , YL ) + λ LG (X) ,

P

where Llabel = i∈L l(Yi , f (Xi )) P
is the standard supervised loss for some loss functions l and LG is the graph-based
regularization, for example LG = (i,j)∈E kf (Xi ) − f (Xj )k2 , which is called the graph Laplacian regularization.
Earlier approaches are non-parametric and searches over all f considering it as a look-up table. Most popular one
is the Label Propagation [49] that forces the estimated labels to agree in the labeled instances and uses weighted
graph Laplacian. This innovative formulation admits a closed form solution which makes it practically attractive with
very low computationally cost. ManiReg [5] replaces supervised loss with that of a support vector machine. ICA
[30] generalizes LP by allowing more general local updates. A more thorough survey on using non-neural network
methods for semi-supervised learning can be found in [12].
More recent approaches are parametric, using deep neural networks. SemiEmb [42] was the first to use a deep
neural network to model f (x) and minimize the above loss. Planetoid [46] significantly improves upon the existing
graph regularization approaches by replacing the regularization by another loss based on skip-grams (defined below).
In a slightly different context, Buchnik and Cohen [11] show that the accuracy of these approaches can be further
improved by bootstrapping these models sequentially.
Unsupervised node embedding for semi-supervised learning. Several approaches have been proposed to embed the
nodes in some latent Euclidean space using only the connectivity in graph G. Once the embedding is learned, standard
supervised learning is applied on those embedded features to train a model. Inspired by the success of word2vec [28],
several approaches define “skip-grams” on graphs as the neighborhood (context) of a node on the graph and tries to
maximize the posterior probability of observing those skip-grams. DeepWalk [35] and node2vec [22] use random
walks as skip-grams, LINE [40] uses local proximities, LASAGNE [18] uses the Personalized PageRank random
walk. Graph2Gauss [1] represents a node as a Gaussian distribution, and minimizes the divergence between connected
pairs. Yang et al. [45] provide a post-processing scheme that takes any node embedding and attempts to improve it
by by taking the weighted sum of the given embeddings with Personalized PageRank weights. The strength of these
approaches is universality, as the node embedding does not depend on the particular task at hand (and in particular the
features or the labels). However, as they do not use the node features and the training only happens after embedding,
they cannot meet the performance of the state-of-the-art approaches (see DeepWalk in Table 2).
2

Graph Neural Network (GNN). Graph neural networks are extensions of neural networks to structured data encoded
as a graph. Originally introduced as extensions of recurrent neural networks, GNNs apply recurrent layers to each
node with additional local averaging layer [20, 36]. However, as the weights are shared across all nodes, GNNs
can also be interpreted as extensions of convolutional neural networks on a 2D grid to general graphs. Typically, a
message aggregation step followed by some neural network architecture is iteratively applied. The model parameters
are trained on (semi-)supervised examples with labels. We give a typical example of a GNN in Section 3, but several
diverse variations have been proposed in [10, 17, 29, 24, 39, 8, 15, 13, 3, 32, 38, 23, 37, 38]. GNNs have been
successfully applied in diverse applications such as molecular activation prediction [19], community detection [9],
matrix completion [6], combinatorial optimization [14, 34], and detecting similar binary codes [44].
In particular, for the benchmark datasets that we consider in this paper, Kipf and Welling [27] proposed a simple
but powerful architecture called Graph Convolutional Network (GCN) that achieves the state-of-the-art accuracy. In
the following section, (a) we show that the performance of GCN can be met by a linear classifier; and (b) use this
insight to introduce novel graph neural networks that compare favourably against the state-of-the-art approaches on
benchmark datasets.

3

Dissection of Graph Neural Network

In this section, we propose a novel Graph Neural Network (GNN) model which we call Attention-based Graph Neural
Network (AGNN), and compare its performance to state-of-the-art models on benchmark citation networks in Section
5. We seek a model Z = f (X, A) ∈ Rn×dy that predicts at each node one of the dy classes. Zic is the estimated
probability that the label at node i ∈ [n] is c ∈ [dy ] given the features X and the graph A. The data features X ∈ Rn×dx
has at each row dx features for each node, and A ∈ {0, 1}n×n is the adjacency matrix of G.
The forward pass in a typical GNN alternates between a propagation layer and a single layer perceptron. Let t
(t)
be the layer index. We use H (t) ∈ Rn×dh to denote the current (hidden) states, with the i-th row Hi as the dh
dimensional hidden state of node i. A propagation layer with respect to a propagation matrix P ∈ Rn×n is defined as
H̃ (t) = P H (t) .
P
(t)
(t)
For example, the natural random walk1 P = D−1 A gives H̃i = (1/|N (i)|) j∈N (i) Hj . The neighborhood of
node i is denoted by N (i), and D = diag(A1). This is a simple local averaging common in consensus or random
walk based approaches. Typical propagation layer respects the adjacency pattern in A, performing a variation of such
local averaging. GNNs encode the graph structure of A into the model via this propagation layer, which can be also
interpreted as performing a graph convolution operation as discussed in [27]. Next, a single layer perceptron is applied
on each node separately and the weights W (t) are shared across all the nodes:
H (t+1) = σ(H̃ (t) W (t) ) ,
where W (t) ∈ Rdht+1 ×dht is the weight matrix and σ(·) is an entry-wise activation function. This weight sharing
reduces significantly the number of parameters to be trained, and encodes the invariance property of graph data,
i.e. two nodes that are far apart but have the similar neighboring features and structures should be classified similarly.
There are several extensions to this model as discussed in the previous section, but this standard graph neural network
has proved powerful in several problems over graphs, e.g. [9, 6, 14].
Graph Convolutional Network (GCN). Kipf and Welling [27] introduced a simple but powerful architecture, and
achieved the state-of-the-art performance in benchmark citation networks (see Table 2). GCN is a special case of GNN
which stacks two layers of specific propagation and perceptron:

H (1) = ReLU (P X) W (0) ,

Z = f (X, A) = softmax ( P H (1) ) W (1) ,
(1)
with a choice of P = D̃−1/2 ÃD̃−1/2 , where Ã = A + I, I is the identity matrix, D̃ = diag(Ã1) and 1 is the all-ones
vector. ReLU(a) = max{0, a} is an entry-wise rectified linear activation function, and softmax([a1 , . . . , ak ]) =
1 Random

walk which moves from a node to one of its neighbors selected uniformly at random.

3

P
(1/Z)[exp(a1 ), . . . , exp(ak )] with Z = i exp(ai ) is applied row-wise. Hence, the output is the predicted likelihoods on the dy dimensional probability simplex. The weights W (0) and W (1) are trained to minimize the crossentropy loss over all labeled examples L:
L

=

−

dy
XX

Yic ln Zic .

(2)

i∈L c=1

Graph Linear Network (GLN). To better understand GCN, we remove the intermediate nonlinear activation units
from GCN, which gives Graph Linear Network defined as

(3)
Z = f (X, A) = softmax (P2 X) W(0) W(1) ,
with the same choice of P = D̃−1/2 ÃD̃−1/2 as in GCN. The weights W (0) and W (1) have the same dimensions as
GCN and are trained on a cross entropy loss in (2). The two propagation layers simply take (linear) local average
of the raw features weighted by their degrees, and at the output layer a simple linear classifier (multinomial logistic
regression) is applied. This allows us to separate the gain in the linear propagation layer and the non-linear perceptron
layer.
Comparing the differences in performances in Table 2, we show that, perhaps surprisingly, GLN achieves an
accuracy comparable to the that of the best GNN, and sometimes better. This suggests that, for citation networks,
the strength of the general GNN architectures is in the propagation layer and not in the perceptron layer. On the
other hand, the propagation layers are critical in achieving the desired performance, as is suggested in Table 2. There
are significant gaps in accuracy for those approaches not using the graph, i.e. T-SVM, and also those that use the
graph differently, such as Label Propagation (LP) and Planetoid. Based on this observation, we propose replacing the
propagation layer of GLN with an attention mechanism and test it on the benchmark datasets.

4

Attention-based Graph Neural Network (AGNN).

The original propagation layer in GCN and several other graph neural networks such as [15, 3, 31, 38] use a static
(does not change
p over the layers) and non-adaptive (does not take into account the states of the nodes) propagation,
e.g. Pij = 1/ |N (i)| |N (j)|. Such propagations are not able to capture which neighbor is more relevant to classifying
a target node, which is critical in real data where not all edges imply the same types or strengths of relations.
We need novel dynamic and adaptive propagation layers, capable of capturing the relevance of different edges,
which leads to more complex graph neural networks with more parameters. However, training such complex models
is challenging in the semi-supervised setting, as the typical number of samples we have for each class is small; it is 20
in the standard benchmark dataset. This is evidenced in Table 2 where more complex graph neural network models by
Verma, Boyer, and Verbeek [41], Monti et al. [31], and [38] do not improve upon the simple GCN.
On the other hand, our experiments with GLN suggests that we can remove all the perceptron layers and focus
only on improving the propagation layers. To this end, we introduce a novel Attention-based Graph Neural Network
(AGNN). AGNN is simple; it only has a single scalar parameter β (t) at each intermediate layer. AGNN captures relevance; the proposed attention mechanism over neighbors in (5) learns which neighbors are more relevant and weighs
their contributions accordingly. This builds on the long line of successes of attention mechanisms in summarizing long
sentences or large images, by capturing which word or part-of-image is most relevant [43, 21, 4]. Particularly, we use
the attention formulation similar to the one used in [21].2 It only has one parameter and we found this is important for
successfully training the model when the number of labels is small as in our semi-supervised learning setting.

4.1

AGNN model

We start with a word-embedding layer that maps a bag-of-words representation of a document into an averaged word
embedding, and the word embedding W (0) ∈ Rdx ×dh is to be trained as a part of the model:
H (1)

=

ReLU(XW (0) ) .

(4)

2 We have experimented other types of more complex attention formulations but we found the training becomes much less stable especially when

the number of labeled nodes is small.

4

This is followed by layers of attention-guided propagation layers parameterized by β (t) ∈ R at each layer,
H (t+1)

= P (t) H (t) ,

(5)

where the propagation matrix P (t) ∈ Rn×n is also a function of the input states H (t) and is zero for absent edges such
that the output row-vector of node i is
X
(t+1)
(t) (t)
Hi
=
Pij Hj ,
j∈N (i)∪{i}
(t)

with Pi



(t)
(t)
= softmax [ β (t) cos(Hi , Hj ) ]j∈N (i)∪{i} and cos(x, y) = xT y/kxkkyk with the L2 norm kxk, for

t ∈ {1, . . . , `} and an integer `. Here ` is the number of propagation layers. Note that the new propagation above is
dynamic; propagation changes over the layers with differing β (t) and also the hidden states. It is also adaptive; it learns
to weight more relevant neighbors higher. We add the self-loop in the propagation to ensure that the features and the
hidden states of the node itself are not lost in the propagation process. The output layer has a weight W (1) ∈ Rdh ×dy :

Z = f (X, A) = softmax H (`+1) W (1) .
(6)
The weights W (0) , W (1) , and β (t) ’s are trained on a cross entropy loss in (2). To ease the notations, we have assumed
that the input feature vectors to the first and last layers are augmented with a scalar constant of one, so that the standard
bias term can be included in the parameters W (0) and W (1) .
The softmax function at attention ensures that the propagation layer P (t) row-sums to one. The attention from
node j to node i is
(t)

Pij

=

(1/C)eβ

(t)

(t)

(t)

cos(Hi ,Hj )

,

(7)

(t)
(t)
P
(t)
with C = j∈N (i)∪{i} eβ cos(Hi ,Hj ) which captures how relevant j is to i, as measured by the cosine of the angle
between the corresponding hidden states. We show how we can interpret the attentions in Section 5.2 and show that
the attention selects neighbors with the same class to be more relevant. On the standard benchmark datasets on citation
networks, we show in Section 5 that this architecture achieves the best performance in Table 2.
Here we note that independently from this work attention over sets has been proposed as “neighborhood attention”
[16, 25] for a different application. The main difference of AGNN with respect to these work is the fact that in AGNN
attention is computed over a neighborhood of a node on a graph, whereas in these work attention over set of all entities
is used to construct a “soft neighborhood”.

5

Experiments on Benchmark Citation Networks

On standard benchmark datasets of three citation networks, we test our proposed AGNN model on semi-supervised
learning tasks. We test on a fixed split of labeled/validation/test sets from [46] and compare against baseline methods
in Table 2. We also test it on random splits of the same sizes in Table 3, and random splits with larger number of
labeled nodes in Table 4.
Benchmark Datasets. A citation network dataset consists of documents as nodes and citation links as directed edges.
Each node has a human annotated topic from a finite set of classes and a feature vector. We consider three datasets3 . For
CiteSeer and Cora datasets, the feature vector has binary entries indicating the presence/absence of the corresponding
word from a dictionary. For PubMed dataset, the feature vector has real-values entries indicating Term FrequencyInverse Document Frequency (TF-IDF) of the corresponding word from a dictionary. Although the networks are
directed, we use undirected versions of the graphs for all experiments, as is common in all baseline approaches.
Experimental setup. The accuracy of the baseline methods are all taken from existing literature. If a baseline result
is not reported in the existing literature, we intentionally left those cells empty in the table for fairness, as opposed to
running those experiments ourselves on untuned hyperparameters. We train and test only the two models we propose:
GLN for comparisons and our proposed AGNN model. We do not use the validation set labels in training, but use them
for optimizing hyper-parameters like dropout rate, learning rate, and L2 -regularization factor. For AGNN, we use a
3 https://linqs.soe.ucsc.edu/node/236

5

Labeled nodes
Dataset
CiteSeer
Cora
PubMed

Nodes
3,327
2,708
19,717

Edges
4,732
5,429
44,328

Classes
6
7
3

Features
3,703
1,433
500

Table 2
120
140
60

Table 3
120
140
60

Table 4
2,218
2,994
1,805
2,437
13,145 17,745

Table 1: Citation Network Dataset
fixed number of dh = 16 units in the hidden layers and use 4 propagation layers (` = 4) for CiteSeer and Pubmed and
2 propagation layers (` = 2) for Cora as defined in (7). For GLN, we use 2 propagation layers as defined in (1). We
row-normalize the input feature vectors, as is standard in the literature. The tables below show the average accuracy
with the standard error over 100 training instances with random weight initializations. We implement our model on
TensorFlow [2], and the computational complexity of evaluating AGNN is O(`dh |E| + dx dh n). Detailed desription
of the experiments is provided in Appendix C.

5.1

Quantitative results

Fixed data splits. In this first experiment, we use the fixed data splits from [46] as they are the standard benchmark
data splits in literature. All experiments are run on the same fixed split of 20 labeled nodes for each class, 500 nodes
for validation, 1,000 nodes for test, and the rest of nodes as unlabeled data. Perhaps surprisingly, the linear classifier
GLN we proposed in (3) achieves performance comparable to or exceeding the state-of-the-art performance of GCN.
This leads to our novel attention-based model AGNN defined in (6), which achieves the best accuracy on all datasets
with a gap larger than the standard error. The classification accuracy of all the baseline methods are collected from
[46, 27, 38, 31, 11, 41].
Input
YL , XL
YL , X
YL , G

YL , X, G

Method
Singlelayer Perceptron
Multilayer Perceptron
T-SVM [26]
DeepWalk [35]
node2vec [22]
LP [50]
ICA [30]
ManiReg [5]
SemiEmb [42]
DCNN [3]
Planetoid [46]
MoNet [31]
Graph-CNN [38]
DynamicFilter [41]
Bootstrap [11]
GCN [27]
GLN
AGNN (this paper)

CiteSeer
57.2
64.0
64.0
43.2
54.7
45.3
69.1
60.1
59.6
64.7

53.6
70.3
70.9±.05
71.7±.08

Cora
57.4
57.5
57.5
67.2
74.9
68.0
75.1
59.5
59.0
76.8
75.7
81.7
76.3
81.6
78.4
81.5
81.2±.05
83.1±.08

PubMed
69.8
71.4
62.2
65.3
75.3
63.0
73.9
70.7
71.1
73.0
77.2
78.8
79.0
78.8
79.0
78.9±.05
79.9±.07

Table 2: Classification accuracy with a fixed split of data from [46].

In semi-supervised learning on graphs, it is critical to utilize both the structure of the graph and the node features.
Methods not using all the given data achieve performance far from the state-of-the-art. Supervised methods–Single
and Multi-layer Perceptrons–only use the labeled examples (YL , XL ). Semi-supervised methods, e.g. T-SVM, only
use the labeled and unlabeled examples YL , and X. Skip-gram based approaches, such as DeepWalk, ignores the node
features X and only use the labels YL and the graph G.
6

A breakthrough result of Planetoid by Yang, Cohen, and Salakhutdinov [46] significantly improved upon the existing skip-gram based method of DeepWalk and node2vec and the Laplacian regularized methods of ManiReg and
SemiEmb. Kipf and Welling [27] was the first to apply a graph neural network to citation datasets, and achieved the
state-of-the-art performance with GCN. Other variations of graph neural networks immediately followed, achieving
comparable performance with MoNet, Graph-CNN, and DynamicFilter. Bootstrap uses a Laplacian regularized approach of [48] as a sub-routine with bootstrapping to feed high-margin predictions as seeds.
Random splits. Next, following the setting of Buchnik and Cohen [11], we run experiments keeping the same size in
labeled, validation, and test sets as in Table 2, but now selecting those nodes uniformly at random. This, along with
the fact that different topics have different number of nodes in it, means that the labels might not be spread evenly
across the topics. For 20 such randomly drawn dataset splits, average accuracy is shown in Table 3 with the standard
error. As we do not force equal number of labeled data for each class, we observe that the performance degrades for
all methods compared to Table 2, except for DeepWalk. AGNN achieves the best performance consistently. Here, we
note that Kipf and Welling [27] does a similar but different experiment using GCN, where random labeled nodes are
evenly spread across topics so that each topic has exactly 20 labeled examples. As this difference in sampling might
affect the accuracy, we do not report those results in this table.
Method
DeepWalk [35]
node2vec [22]
Bootstrap [11]
GLN
AGNN (this paper)

CiteSeer
47.2
47.3
50.3
68.4±0.45
69.8±0.35

Cora
70.2
72.9
78.2
80.0±0.43
81.0±0.34

PubMed
72.0
72.4
75.6
77.7±0.63
78.0±0.46

Table 3: Classification accuracy with random splits of the data.

Larger training set. Following the setting of [38], we run experiments with larger number of labeled data on Cora
dataset. We perform k-fold cross validation experiments for k = 3 and 10, by uniformly and randomly dividing the
nodes into k equal sized partitions and then performing k runs of training by masking the labels of each of the k partitions followed by validation on the masked nodes. Finally the average validation accuracy across k runs is reported.
We run 10 trials of this experiment and reports the mean and standard error of the average k-fold validation accuracy.
Compared to Table 2, the performance increases with the size of the training set, and AGNN consistently outperforms
the current state-of-the-art architecture for this experiment.
Method
Graph-CNN [38]
GLN
AGNN (this paper)

3-fold Split
87.55±1.38
87.98±0.08
89.07±0.08

10-fold split
89.18±1.96
88.24±0.07
89.60±0.09

Table 4: Classification accuracy with larger sets of labelled nodes.

Performance versus Number of Propagation Layers. In this section we provide experimental results justifying
the choice of number of propagation layers for each dataset. We use the same data split and hyper-parameters (except number of propagation layer) as in the fixed data splits setting in Section 5.1. Similar to other settings the first
propagation layer for Cora dataset is non-trainable with β (t=1) = 0. Tables 5 gives the average (over 10 trials) testing
accuracy respectively for various choices of number of propagation layers. We note that different datasets require
different number of propagation layers for best performance.

5.2

Qualitative analysis

Inter-class relevance score. One useful aspect of incorporating attention into a model is that it provides some form of

7

Propagation
Layers (`)
1
2
3
4
5

CiteSeer

Cora

PubMed

69.08
70.83
71.06
71.70
71.37

80.52
83.07
82.62
82.24
82.07

78.31
79.66
79.56
80.10
80.13

Table 5: Average testing error of AGNN for different number of Propagation Layers.

(t)

interpretation capability [4]. The learned Pij ’s in Eq. (7) represent the attention from node j to node i, and provide
insights on how relevant node j is in classifying node i. In Figure 1, we provide statistics of this attention over all
adjacent pairs of nodes for Cora and CiteSeer datasets. We refer to Figure 3 for similar statistics on PubMed. In Figure
1, we show average attention from a node in topic c2 (column) to a node in topic c1 (row), which we call the relevance
from c2 to c1 and is defined as
X
1
R(j → i) ,
(8)
Relevance(c2 → c1 ) =
|Sc1 ,c2 |
(i,j)∈Sc1 ,c2

for edge-wise relevance score defined as
R(j → i) =

(t)
Pij

1
−
|N (i)| + 1

!,

1
,
|N (i)| + 1

(9)

where |N (i)| is the degree of node i, and Sc1 ,c2 = {(i, j) ∈ E s and Yi = c1 , Yj = c2 } where E s = E ∪ {(i, i) for i ∈
V } is the edge set augmented with self-loops to include all the attentions learned. If we are not using any attention,
then the typical propagation will be uniform Pij = 1/(|N (i)| + 1), in which case the above normalized attention is
zero. We are measuring for each edge the variation of attention Pij from uniform 1/(|N (i)| + 1) as a multiplicative
error, normalized by 1/(|N (i)| + 1). We believe this is the right normalization, as attention should be measure in
relative strength to others in the same neighborhood, and not in absolute additive differences. We are measuring this
multiplicative variation of the attention, averaged over the ordered pairs of classes.
Figure 1 shows the relevance score for CiteSeer and Cora datasets. (PubMed is shown in Appendix A.) For both
datasets, the diagonal entries are dominant indicating that the attention is learning to put more weight to those in the
same class. A higher value of Relevance(c2 → c1 ) indicates that, on average, a node in topic c1 pays more attention to a
neighbor in topic c2 than neighbors from other topics. For CiteSeer dataset (Figure 1 left), we are showing the average
attention at the first propagation layer, P (t=1) , for illustration. In the off-diagonals, the most influential relations
are HCI→Agents, Agents→ML, Agents→HCI, and ML→Agents, and the least influential relations are AI→IR and
DB→ML. Note that these are papers in computer science from late 90s to early 2000s. For Cora dataset (Figure 1
right), we are showing the relevance score of the second propagation layer, P (t=2) , for illustration. In the off-diagonals,
the most influential relations are CB→PM, PM→CB, Rule→PM, and PM→Rule, and the least influential relations
are GA→PM and PM→RL. This dataset has papers in computer science from the 90s. We note that these relations are
estimated solely based on the available datasets for that period of time and might not accurately reflect the relations
for the entire academic fields. We also consider these relations as a static property in this analysis. If we have a larger
corpus over longer period of time, it is possible to learn the influence conditioned on the period and visualize how
these relations change.
Top 100
Bottom 100

CiteSeer
0.69
0.34

Cora
0.64
0.09

PubMed
0.69
0.13

Table 6: Fraction of edges from top 100 most relevant edges and bottom 100 least relevant edges which are connecting
two distinct nodes from the same class.
Attention quality. Next, we analyze the edges with high and low relevance scores. We remove the self-loops and then
sort the edges according to the relevance score defined in Eq. (9). We take the top 100 and bottom 100 edges and with
8

CiteSeer

Center
AI

0.206

-0.261

-0.264

-0.18

-0.215

-0.27

0.18

Cora

Center
Theory

0.061 -0.267 -0.356 -0.26

Reinforcement Learning

-0.319 0.077 -0.271 -0.449 -0.54 -0.426 -0.126

0.08

Genetic Algorithms

-0.48 -0.248 0.028 -0.415 -0.273 -0.279 -0.316

0.16

Neural Networks

-0.252 -0.339 -0.335 0.034 -0.145 -0.083 -0.166

Probabilistic Methods

-0.191 -0.513 -0.619 -0.129 0.026 0.017 -0.047

Case Based

-0.167 -0.428 -0.315 -0.165 -0.011 0.043 -0.116

0.48

Rule Learning

-0.221 -0.524 -0.372 -0.348 -0.077 -0.18

0.56

0.12

ML
IR
DB
Agents
HCI

-0.245

0.095

-0.224

-0.327

-0.149

-0.296

-0.336

-0.296

0.06

-0.227

-0.239

-0.24

0.06
0.00
0.06

-0.193

-0.287

-0.251

0.075

-0.236

-0.224

-0.175

-0.157

-0.262

-0.215

0.041

-0.141

-0.274

-0.321

-0.292

-0.232

-0.154

0.046

0.12

0.30

0.00

0.24
0.32

0.18
0.24

AI

-0.14 -0.101 -0.096

ML IR DB Agents HCI
Neighbor

0.049

0.40

Theory RL GA NN PM CB Rule
Neighbor

Figure 1: Relevance score in Eq. (8) from a neighbor node with column-class to a center node in row-class. For
example the average normalized attention to Agents from HCI is = −0.141 , largest off-diagonal entry in CiteSeer.
The average attention to Probabilistic Methods (PM) from Case Based (CB) is 0.017, largest off-diagonal entry in
Cora.
respect to their relevance scores, and report the fraction of the edges which are connecting nodes from the same class.
Table 6 shows the result on the benchmark datasets for the relevance scores calculated using the last propagation layer.
This suggests that our architecture learns to put higher attention between nodes of the same class.

PubMed 1580
PubMed 8434

CiteSeer 1512

Figure 2: We show three selected target nodes in the test set that are mistaken by GCN but correctly classified by
AGNN. We denote this target node by the node with a thick outline (node 8434 from PubMed on the left, node 1580
from PubMed in the middle, and node 1512 from CiteSeer on the right). We show the strength of attention from a
node in the 2-hop neighborhood to the target node by the size of the corresponding node. Colors represent the hidden
true classes (nodes with the same color belong to the same topic). None of the nodes in the figure was in the training
set, hence none of the colors were revealed. Still, we observe that AGNN has managed to put more attention to those
nodes in the same (hidden) classes, allowing the trained model to find the correct labels.

Neighborhood attention. Finally, we analyze those nodes in the test sets that were mistaken by GCN but correctly
classified by AGNN, and show how our attention mechanism weighted the contribution of its local neighborhood, and
show three illustrative examples in Figure 2. More examples of this local attention network (including the legends for
the color coding of the topics) are provided in Appendix A. We show a entire 2-hop neighborhood of a target node
(marked by a thick outline) from the test set of the fixed data splits of Citeseer, Cora, or Pubmed. The colors denote the
true classes of the nodes (including the target) in the target’s neighborhood, some of which are unknown to the models
at the training time. The radius of a node j is proportional to the attention to the target node i aggregated over all the
layers, i.e. (P (t=4) P (t=3) P (t=2) P (t=1) )ij for CiteSeer. The size of the target node reflects its self-attention defined in
a similar way. The first example on the left is node 8434 from PubMed. AGNN correctly classifies the target node as
light blue, whereas GCN mistakes it for yellow, possibly because it is connected to more yellow nodes. Not only has
9

the attention mechanism learned to put more weight to its light blue 1-hop neighbor, but put equally heavy weights to
a path of light blue neighbors some of which are not immediately connected to the target node. The second example
in the middle is node 1580 from PubMed. AGNN correctly classifies it as yellow, whereas GCN mistakes it for a red,
possibly because it only has two neighbors. Not only has the attention mechanism learned to put more weight to the
yellow neighbor, but it has weighted the yellow neighbor (who is connected to many yellow nodes and perhaps has
more reliable hidden states representing the true yellow class) even more than itself.
The last example on the right is node 1512 from CiteSeer. AGNN correctly classifies it as light blue, whereas GCN
mistakes it for a white. This is a special example as those two nodes are completely isolated. Due to the static and
non-adaptive propagation of GCN, it ends up giving the same prediction for such isolated pairs. If the pair has two
different true classes, then it always fails on at least on one of them (in this case the light blue node). However, AGNN
is more flexible in adapting to such graph topology and puts more weight to the target node itself, correctly classifying
both.

6

Conclusions

In this paper, we present an attention-based graph neural network model for semi-supervised classification on a graph.
We demonstrate that our method consistently outperforms competing methods on the standard benchmark citation
network datasets. We also show that the learned attention also provides interesting insights on how neighbors influence
each other. In training, we have tried more complex attention models. However, due to the increased model complexity
the training was not stable and does not give higher accuracy. We believe that for semi-supervised setting with such a
limited number of labeled examples, reducing model complexity is important. Note that we are able to train deeper (4layers) models compared to a shallower (2-layers) model of GCN, in part due to the fact that we remove the non-linear
layers and reduce the model complexity significantly. In comparison, deeper GCN models are known to be unstable
and do not give the performance of shallower GCNs [27].

Acknowledgments
We would like to thank Yu Wang and Mason Ng for helping us run the experiments efficiently on the Google servers.
We would also like to thank Fei-Fei Li, Wei Wei, Zhe Li, Xinlei Chen and Achal Dave for insightful discussions.

References
[1]

S. Gunnemann A. Bojchevski. “Deep Gaussian Embedding of Attributed Graphs: Unsupervised Inductive
Learning via Ranking”. In: arXiv preprint arXiv:1707.03815 (2017).

[2]

Martin Abadi et al. “Tensorflow: Large-scale machine learning on heterogeneous distributed systems”. In: arXiv
preprint arXiv:1603.04467 (2016).

[3]

J. Atwood and D. Towsley. “Diffusion-convolutional neural networks”. In: Advances in Neural Information
Processing Systems. 2016, pp. 1993–2001.

[4]

Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. “Neural machine translation by jointly learning to
align and translate”. In: arXiv preprint arXiv:1409.0473 (2014).

[5]

Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. “Manifold regularization: A geometric framework for
learning from labeled and unlabeled examples”. In: Journal of machine learning research 7.Nov (2006), pp. 2399–
2434.

[6]

R. van den Berg, T. N. Kipf, and M. Welling. “Graph Convolutional Matrix Completion”. In: arXiv preprint
arXiv:1706.02263 (2017).

[7]

Avrim Blum and Shuchi Chawla. “Learning from labeled and unlabeled data using graph mincuts”. In: ICML
’01 Proceedings of the Eighteenth International Conference on Machine Learning. 2001.

[8]

Michael M Bronstein et al. “Geometric deep learning: going beyond euclidean data”. In: arXiv preprint arXiv:1611.08097
(2016).

10

[9]

J. Bruna and X. Li. “Community Detection with Graph Neural Networks”. In: arXiv preprint arXiv:1705.08415
(2017).

[10]

Joan Bruna et al. “Spectral networks and locally connected networks on graphs”. In: arXiv preprint arXiv:1312.6203
(2013).

[11]

Eliav Buchnik and Edith Cohen. “Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity”. In:
arXiv preprint arXiv:1703.02618 (2017).

[12]

Olivier Chapelle, Bernhard Scholkopf, and Alexander Zien. “Semi-supervised learning (chapelle, o. et al., eds.;
2006)[book reviews]”. In: IEEE Transactions on Neural Networks 20.3 (2009), pp. 542–542.

[13]

H. Dai, B. Dai, and L. Song. “Discriminative embeddings of latent variable models for structured data”. In:
International Conference on Machine Learning. 2016, pp. 2702–2711.

[14]

Hanjun Dai et al. “Learning Combinatorial Optimization Algorithms over Graphs”. In: arXiv preprint arXiv:1704.01665
(2017).

[15]

Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. “Convolutional neural networks on graphs with
fast localized spectral filtering”. In: Advances in Neural Information Processing Systems. 2016, pp. 3837–3845.

[16]

Yan Duan et al. “One-Shot Imitation Learning”. In: arXiv preprint arXiv:1703.07326 (2017).

[17]

David K Duvenaud et al. “Convolutional networks on graphs for learning molecular fingerprints”. In: Advances
in neural information processing systems. 2015, pp. 2224–2232.

[18]

Evgeniy Faerman et al. “LASAGNE: Locality And Structure Aware Graph Node Embedding”. In: arXiv preprint
arXiv:1710.06520 (2017).

[19]

Justin Gilmer et al. “Neural message passing for quantum chemistry”. In: arXiv preprint arXiv:1704.01212
(2017).

[20]

Marco Gori, Gabriele Monfardini, and Franco Scarselli. “A new model for learning in graph domains”. In:
Neural Networks, 2005. IJCNN’05. Proceedings. 2005 IEEE International Joint Conference on. Vol. 2. IEEE.
2005, pp. 729–734.

[21]

Alex Graves, Greg Wayne, and Ivo Danihelka. “Neural turing machines”. In: arXiv preprint arXiv:1410.5401
(2014).

[22]

A. Grover and J. Leskovec. “node2vec: Scalable feature learning for networks”. In: Proceedings of the 22nd
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM. 2016, pp. 855–864.

[23]

W. L. Hamilton, R. Ying, and J. Leskovec. “Inductive Representation Learning on Large Graphs”. In: arXiv
preprint arXiv:1706.02216 (2017).

[24]

Mikael Henaff, Joan Bruna, and Yann LeCun. “Deep convolutional networks on graph-structured data”. In:
arXiv preprint arXiv:1506.05163 (2015).

[25]

Yedid Hoshen. “VAIN: Attentional Multi-agent Predictive Modeling”. In: Advances in Neural Information Processing Systems. 2017, pp. 2698–2708.

[26]

Thorsten Joachims. “Transductive inference for text classification using support vector machines”. In: ICML.
Vol. 99. 1999, pp. 200–209.

[27]

T. N. Kipf and M. Welling. “Semi-supervised classification with graph convolutional networks”. In: arXiv
preprint arXiv:1609.02907 (2016).

[28]

Q. Le and T. Mikolov. “Distributed representations of sentences and documents”. In: Proceedings of the 31st
International Conference on Machine Learning (ICML-14). 2014, pp. 1188–1196.

[29]

Y. Li et al. “Gated graph sequence neural networks”. In: arXiv preprint arXiv:1511.05493 (2015).

[30]

Qing Lu and Lise Getoor. “Link-based classification”. In: Proceedings of the 20th International Conference on
Machine Learning (ICML-03). 2003, pp. 496–503.

[31]

Federico Monti et al. “Geometric deep learning on graphs and manifolds using mixture model CNNs”. In: arXiv
preprint arXiv:1611.08402 (2016).

[32]

M. Niepert, M. Ahmed, and K. Kutzkov. “Learning convolutional neural networks for graphs”. In: Proceedings
of the 33rd annual international conference on machine learning. ACM. 2016.
11

[33]

Kamal Nigam, Andrew McCallum, and Tom Mitchell. “Semi-supervised text classification using EM”. In:
Semi-Supervised Learning (2006), pp. 33–56.

[34]

A. Nowak et al. “A Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks”. In:
arXiv preprint arXiv:1706.07450 (2017).

[35]

B. Perozzi, R. Al-Rfou, and S. Skiena. “Deepwalk: Online learning of social representations”. In: Proceedings
of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM. 2014,
pp. 701–710.

[36]

Franco Scarselli et al. “The graph neural network model”. In: IEEE Transactions on Neural Networks 20.1
(2009), pp. 61–80.

[37]

M. Schlichtkrull et al. “Modeling Relational Data with Graph Convolutional Networks”. In: arXiv preprint
arXiv:1703.06103 (2017).

[38]

Felipe Petroski Such et al. “Robust Spatial Filtering with Graph Convolutional Neural Networks”. In: arXiv
preprint arXiv:1703.00792 (2017).

[39]

Sainbayar Sukhbaatar, arthur szlam arthur, and Rob Fergus. “Learning Multiagent Communication with Backpropagation”. In: Advances in Neural Information Processing Systems 29. 2016, pp. 2244–2252.

[40]

Jian Tang et al. “Line: Large-scale information network embedding”. In: Proceedings of the 24th International
Conference on World Wide Web. ACM. 2015, pp. 1067–1077.

[41]

Nitika Verma, Edmond Boyer, and Jakob Verbeek. “Dynamic Filters in Graph Convolutional Networks”. In:
arXiv preprint arXiv:1706.05206 (2017).

[42]

Jason Weston et al. “Deep learning via semi-supervised embedding”. In: Neural Networks: Tricks of the Trade.
Springer, 2012, pp. 639–655.

[43]

Kelvin Xu et al. “Show, attend and tell: Neural image caption generation with visual attention”. In: International
Conference on Machine Learning. 2015, pp. 2048–2057.

[44]

Xiaojun Xu et al. “Neural Network-based Graph Embedding for Cross-Platform Binary Code Similarity Detection”. In: arXiv preprint arXiv:1708.06525 (2017).

[45]

Cheng Yang et al. “Fast network embedding enhancement via high order proximity approximation”. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI. 2017, pp. 19–
25.

[46]

Z. Yang, W. W. Cohen, and R. Salakhutdinov. “Revisiting semi-supervised learning with graph embeddings”.
In: arXiv preprint arXiv:1603.08861 (2016).

[47]

Denny Zhou et al. “Learning with local and global consistency”. In: Advances in neural information processing
systems. 2004, pp. 321–328.

[48]

Denny Zhou et al. “Learning with local and global consistency”. In: Advances in neural information processing
systems. 2004, pp. 321–328.

[49]

Xiaojin Zhu and Zoubin Ghahramani. “Learning from labeled and unlabeled data with label propagation”. 2002.

[50]

Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. “Semi-supervised learning using gaussian fields and
harmonic functions”. In: Proceedings of the 20th International conference on Machine learning (ICML-03).
2003, pp. 912–919.

12

Appendix
A

Additional experiments on interpretability of attention

PubMed dataset has 3 classes, and the relevance score is shown in the Figure 3. We also show examples of 2-hop local
neighborhood of nodes that are mistaken by GCN but correctly classified by AGNN in Figures 4, 5, 6.
PubMed

Center
Diabetes Mellitus, Exp

0.092

-0.372

-0.191

0.05
0.00
0.05

Diabetes Mellitus, Type 1

-0.341

0.026

-0.112

0.10
0.15
0.20
0.25

Diabetes Mellitus, Type 2

-0.168

-0.109

0.025

0.30
0.35

Experimental

Type1
Neighbor

Type2

Figure 3: Average attention in Eq. (8) from a column class to a row class

AI
ML
IR

*

*

DB

*

Agents
HCI

*

labeled train nodes

*
*
Figure 4: Examples from CiteSeer dataset of attention strength in the local neighborhood of a target node (in thick
outline) from the test set that is mistaken by GCN but correctly classified by AGNN. Colors are true classes and node
sizes are proportional to the attention strength from a neighbor to the target node. Labeled nodes from training set are
marked with ‘*’.

B

Performance of GCN on other dataset splits.

Here we provide the performance of GCN on random splits and larger training set dataset splits from Section 5.1.
We relegate these tables to the appendix since they were not present in [27]. We conducted the experiments with the
13

Theory
Reinforcement Learning
Genetic Algorithms
Neural Networks

*

*

*

Probabilistic Methods
Case Based
Rule Learning

*

labeled train nodes

*

Figure 5: Examples from Cora dataset of attention strength in the local neighborhood of a target node (in thick outline)
from the test set that is mistaken by GCN but correctly classified by AGNN. Colors are true classes and node sizes are
proportional to the attention strength from a neighbor to the target node. Labeled nodes from training set are marked
with ‘*’.
Method
DeepWalk [35]
node2vec [22]
Bootstrap [11]
GCN
GLN
AGNN (this paper)

CiteSeer
47.2
47.3
50.3
66.9±0.50
68.4±0.45
69.8±0.35

Cora
70.2
72.9
78.2
79.2±0.46
80.0±0.43
81.0±0.34

PubMed
72.0
72.4
75.6
77.5±0.61
77.7±0.63
78.0±0.46

Table 7: Classification accuracy with random splits of the data.

same hyper-parameters as chosen by [27] for the fixed split. In Tables 7 and 8 we provide average testing accuracy
and standard error over 20 and 10 runs on random splits and larger training set respectively.

C

Experiment and Architect Details

In this section we will list all the choices made in training and tuning of hyper-parameters. The parameters are chosen
as to maximize the validation. All the models use Adam optimization algorithm with full-batchs, as standard in other
works on GNNs [27, 38]. We also a weight decay term to the objective function for all the learnable weights. We add
dropout to the first and last layers of all models. In Table 9. we show the hyper-parameters used in training the AGNN
models for various settings and datasets. For Cora dataset the architecture consist of ` = 2 propagation layers, but
the first propagation layer P (t=1) is non-trainable and the variable β (t=1) value is fixed at zero. While training these
AGNN models we maintain the validation accuracy for each iteration and finally choose the trained model parameters
from the iteration where average validation accuracy of previous 4 epochs is maximized. For the k-fold cross validation
setting we take the epoch with maximum validation accuracy. For the Graph Linear Network (GLN) as define in (3),
we use the same hyper-parameters as GCN [27] for all the experimental settings: hidden dimension of 16, learning
rate of 0.01, weight decay of 5 × 10−4 , dropout of 0.5, 200 epochs and early stopping criteria with a window size of
10.

14

Experimental
Type 1
Type 2

* labeled train nodes

Figure 6: Examples from Pubmed dataset of attention strength in the local neighborhood of a target node (in thick
outline) from the test set that is mistaken by GCN but correctly classified by AGNN. Colors are true classes and node
sizes are proportional to the attention strength from a neighbor to the target node. None of the nodes are labeled.

Method
Graph-CNN [38]
GCN
GLN
AGNN (this paper)

3-fold Split
87.55±1.38
87.23±0.21
87.98±0.08
89.07±0.08

10-fold split
89.18±1.96
87.78±0.04
88.24±0.07
89.60±0.09

Table 8: Classification accuracy with larger sets of labelled nodes.

Setting

Dataset

Fixed Split
Fixed Split
Fixed Split
Rand. Split
Rand. Split
Rand. Split
Cross Val.

CiteSeer
Cora
PubMed
CiteSeer
Cora
PubMed
Cora

Propagation
layers (`)
4
2
4
4
3
4
3

Hidden state
dimension (dh )
16
16
16
16
16
16
16

Learning
Rate
0.005
0.01
0.008
0.01
0.01
0.008
0.04

Weight
Decay
0.0005
0.0005
0.001
0.0005
0.0005
0.001
0.0005

Table 9: Hyper-parameters for AGNN model

15

Dropout

Epochs

0.5
0.5
0.5
0.5
0.5
0.5
0.25

1000
1000
400
1000
1000
1000
500

