![](https://csdnimg.cn/release/download_crawler_static/10894982/bg3.jpg)
PREPRINT. WORK IN PROGRESS. 3
Deep Learning
on Graphs
Graph Neural Networks
Graph Convolutional Networks
Graph Auto-encoders
Graph Recurrent Neural Networks
Graph Reinforcement Learning
Convolution Operations
Readout Operations
Other Improvements
Auto-encoders
Variational Auto-encoders
Other Improvements
Unsupervised
Fig. 1. The categorization of deep learning methods on graphs. We divide existing methods into three categories: semi-supervised, unsupervised
and recent advancements. The semi-supervised methods can be further divided into Graph Neural Networks and Graph Convolutional Networks
based on their architectures. Recent advancements include Graph Recurrent Neural Networks and Graph Reinforcement Learning methods.
TABLE 1
Some Main Distinctions of Deep Learning Methods on Graphs
Category Type Node Attributes/Labels Counterparts in Traditional Domains
Graph Neural Networks Semi-supervised Yes Recursive Neural Networks
Graph Convolutional Networks Semi-supervised Yes Convolutional Neural Networks
Graph Autoencoders Unsupervised Partial Autoencoders/Variational Autoencoders
Graph Recurrent Neural Networks Various Partial Recurrent Neural Networks
Graph Reinforcement Learning Semi-supervised Yes Reinforcement Learning
TABLE 2
Table of Commonly Used Notations
G = (V, E) A graph
N, M The number of nodes and edges
V = {v
1
, ..., v
N
} The set of nodes
F
V
, F
E
Attributes/features for nodes and edges
A The adjacency matrix
D(i, i) =
P
j6=i
A(i, j) The diagonal degree matrix
L = D − A The Laplacian matrix
QΛQ
T
= L The eigen-decomposition of L
P = D
−1
A The transition matrix
N
k
(i), N (i) k-step and 1-step neighbors of v
i
H
l
The hidden representation of l
th
layer
f
l
The number of dimensions of H
l
ρ(·) Some non-linear activation
X
1
X
2
Element-wise product
Θ Learnable parameters
identical layers to reach a stable state. More discussion will be
given in Section 4.
Though conceptually important, GNN has several drawbacks.
First, to ensure that Eq. (1) has a unique solution, F(·) has to
be a “contraction map” [25], which severely limits the modeling
ability. Second, since many iterations are needed between gradient
descend steps, GNN is computationally expensive. Because of
these drawbacks and perhaps the lack of computational power
(e.g. Graphic Processing Unit, GPU, is not widely used for deep
learning those days) and lack of research interests, GNN was not
widely known to the community.
A notable improvement to GNN is Gated Graph Sequence
Neural Networks (GGS-NNs) [26] with several modifications.
Most importantly, the authors replace the recursive definition of
Eq. (1) with Gated Recurrent Units (GRU) [27], thus remove the
requirement of “contraction map” and support the usage of modern
optimization techniques. Specifically, Eq. (1) is replaced by:
s
(t)
i
= (1 − z
(t)
i
) s
(t−1)
i
+ z
(t)
i
e
s
(t)
i
, (3)
where z are calculated by update gates,
e
s are candidates for
updating and t is the pseudo time. Secondly, the authors propose
using several such networks operating in sequence to produce a
sequence output, which can be applied to applications such as
program verification [28].
GNN and its extensions have many applications. For example,
CommNet [29] applies GNN to learn multi-agent communication
in AI systems by regarding each agent as a node and updating
the states of agents by communication with others for several
time steps before taking an action. Interaction Network (IN) [30]
uses GNN for physical reasoning by representing objects as nodes,
relations as edges and using pseudo-time as a simulation system.
VAIN [31] improves CommNet and IN by introducing attentions
to weigh different interactions. Relation Networks (RNs) [32] pro-
pose using GNN as a relational reasoning module to augment other
neural networks and show promising results in visual question
answering problems.
4 GRAPH CONVOLUTIONAL NETWORKS (GCNS)
Besides GNNs, Graph Convolutional Networks (GCNs) are an-
other class of semi-supervised methods for graphs. Since GCNs
usually can be trained with task-specific loss via back-propagation
like standard CNNs, we focus on the architectures adopted.
We will first discuss the convolution operations, then move to
the readout operations and improvements. We summarize main
characteristics of GCNs surveyed in this paper in Table 3.