# Network Representation Learning: From Preprocessing, Feature Extraction to
Node Embedding

JINGYA ZHOU<EMAIL_ADDRESS>0000-0003-0721-7424 Soochow University1 Shizi
streetSuzhouJiangsu215006ChinaGeorgia Institute of Technologyduring May 2019 -
June 2020AtlantaGeorgiaUSAState Key Laboratory of Mathematical Engineering and
Advanced ComputingWuxiJiangsu214125China ,  LING LIU  Georgia Institute of
Technology801 Atlantic DriveAtlantaGeorgia30332USA<EMAIL_ADDRESS>,
WENQI WEI  Georgia Institute of Technology801 Atlantic
DriveAtlantaGeorgia30332USA<EMAIL_ADDRESS>and  JIANXI FAN  Soochow
University1 Shizi streetSuzhouJiangsuChina215006<EMAIL_ADDRESS>
###### Abstract.

Network representation learning (NRL) advances the conventional graph mining
of social networks, knowledge graphs, and complex biomedical and physics
information networks. Over dozens of network representation learning
algorithms have been reported in the literature. Most of them focus on
learning node embeddings for homogeneous networks, but they differ in the
specific encoding schemes and specific types of node semantics captured and
used for learning node embedding. This survey paper reviews the design
principles and the different node embedding techniques for network
representation learning over homogeneous networks. To facilitate the
comparison of different node embedding algorithms, we introduce a unified
reference framework to divide and generalize the node embedding learning
process on a given network into preprocessing steps, node feature extraction
steps and node embedding model training for a NRL task such as link prediction
and node clustering. With this unifying reference framework, we highlight the
representative methods, models, and techniques used at different stages of the
node embedding model learning process. This survey not only helps researchers
and practitioners to gain an in-depth understanding of different network
representation learning techniques but also provides practical guidelines for
designing and developing the next generation of network representation
learning algorithms and systems.

Network representation learning, data preprocessing, feature extraction, node
embedding

††ccs: Computing methodologies††ccs: Computing methodologies Machine
learning††ccs: Information systems Data mining

##  1\. Introduction

Recent advances in deep learning and convolutional neural network (CNN)
(Krizhevsky et al., 2012) have made remarkable breakthroughs to many fields,
such as machine translation (Wu et al., 2016) and reading comprehension in
natural language processing (NLP) (Yu et al., 2018), object detection (Szegedy
et al., 2013) and image classification (Marino et al., 2017) in computer
vision (CV). In addition to text, audio, image and video data, information
networks (or graphs) represent another type of natural and complex data
structure representing a set of entities and their relationships. A wide
variety of real-world data in business, science and engineering domains are
best captured as information networks, such as protein interaction networks,
citation networks, and social media networks like Facebook, LinkedIn, to name
a few.

Network representation learning (NRL), also known as network embedding, is to
train a neural network to represent an information network as a collection of
node-embedding vectors in a latent space such that the desired network
features are preserved, which enables the well-trained NRL model to perform
network analytics, such as link prediction or node cluster, as shown in Fig.
1. The goal of NRL is to employ deep learning algorithms to encode useful
network information into the latent semantic representations, which can be
deployed for performing popular network analytics, such as node
classification, link prediction, community detection, and domain-specific
network mining, such as social recommendation (Fan et al., 2019; Wang et al.,
2019), protein to protein interaction prediction (Fout et al., 2017), disease-
gene association identification (Han et al., 2019), automatic molecule
optimization (Fu et al., 2020) and Bitcoin transaction forecasting (Wei et
al., 2020).

Figure 1. An illustration of NRL and its deployment in example applications
(Fan et al., 2019; Wang et al., 2019; Fout et al., 2017; Han et al., 2019; Fu
et al., 2020; Wei et al., 2020).

NRL introduction

Different from traditional feature engineering that relies heavily on
handcrafted statistics to extract structural information, NRL introduces a new
data-driven deep learning paradigm to capture, encode and embed structural
features along with non-structural features into a latent space represented by
dense and continuous vectors. By embedding edge semantics into node vectors, a
variety of network operations can be carried out efficiently, e.g., computing
the similarity between a pair of nodes, visualizing a network in a
2-dimensional space. Moreover, parallel processing on large scale networks can
be naturally supported with the node embedding learned from NRL.

Most of the existing network representation learning efforts are targeted on
learning node embeddings of a homogeneous network, in which all nodes are
homogeneous and all edges belong to a single type of node relationships, e.g.,
a social network is considered homogeneous when we only consider users and
their friendship relationships (Perozzi et al., 2014). A heterogeneous
information network consists of nodes and edges of heterogeneous types,
corresponding to different types of entities and different kinds of relations
respectively. Knowledge graph (Guo et al., 2018; Ji et al., 2020) and RDF
graphs (Yuan et al., 2013) are known examples of heterogeneous information
networks.

DeepWalk (Perozzi et al., 2014) is the first node embedding algorithm that
learns to encode the neighborhood features of each node in a homogeneous graph
through learning the encoding of its scoped random walk properties using the
autoencoder algorithms in conjunction with node2vec (Grover and Leskovec,
2016). Inspired by DeepWalk design, dozens of node embedding algorithms have
been proposed (Grover and Leskovec, 2016; Ribeiro et al., 2017; Donnat et al.,
2018; Rozemberczki et al., 2019; Zhang et al., 2018c; Epasto and Perozzi,
2019; Liu et al., 2019; Tang et al., 2015b; Wang et al., 2018; Cao et al.,
2015; Yang et al., 2015; Wang et al., 2016; Cao et al., 2016; Qu et al., 2017;
Tsitsulin et al., 2018; Hamilton et al., 2017b; Bojchevski and Günnemann,
2018; Guo et al., 2019; Rossi et al., 2018; Sun et al., 2019c; Deng et al.,
2020; Kipf and Welling, 2017; Wu et al., 2019a; Zhang and Chen, 2018; Cen et
al., 2019; Liao et al., 2018; Perozzi et al., 2017). Although most of them
focus on learning node embeddings for homogeneous networks, they differ in
terms of the specific encoding schemes and the specific types of node
semantics captured and used for learning node embedding. This survey paper
mainly reviews the design principles and the different node embedding
techniques developed for network representation learning over homogeneous
networks. To facilitate the comparison of different node embedding algorithms,
we introduce a unified reference framework to divide and generalize the node
embedding learning process on a given network into preprocessing steps, node
feature extraction steps and node embedding model that can be used for link
prediction and node clustering. With this unifying reference framework, we
highlight the most representative methods, models, and techniques used at
different stages of the node embedding model learning process.

We argue that an in-depth understanding of different node embedding
methods/models/techniques is also essential for other types of network
representation learning approaches that are built on top of node embedding
techniques, such as edge embedding (Abu-El-Haija et al., 2017; Gao et al.,
2019), subgraph embedding (Bordes et al., 2014; Cao et al., 2018) and entire-
graph embedding (Bai et al., 2019; Narayanan et al., 2017). For example, an
edge can be represented by a Hadamard product of its two adjacent nodes’
vectors. Similarly, graph coarsening mechanisms (Chen et al., 2018b; Yu et
al., 2019) may create a hierarchy by successively clustering the nodes in the
input graph into smaller graphs connected in a hierarchical manner, which can
be used to generate representations for subgraphs and even for the entire
graph.

We conjecture that this survey paper not only helps researchers and
practitioners to gain an in-depth understanding of different network
representation learning techniques, but also provides practical guidelines for
designing and developing the next generation of network representation
learning algorithms and systems.

Current surveys (Cai et al., 2018; Hamilton et al., 2017a; Cui et al., 2019)
primarily focus on presenting a taxonomy to review the existing work on
network representation learning. Concretely, (Cai et al., 2018) proposes two
taxonomies of graph embedding based on problem settings and techniques
respectively and it first appeared in 2017 on ArXiv and published in 2018.
(Cui et al., 2019) proposes a taxonomy of network embedding according to the
types of information preserved. (Hamilton et al., 2017a) appeared in 2017 in
the IEEE Data Eng. Bulletin. It describes a set of conventional node embedding
methods with the focus on pairwise proximity methods and neighborhood
aggregation based methods. In contrast, our unified reference framework
provides a broader and more comprehensive comparative review of the state of
the art in network representation learning. In our three-stage reference
framework, each stage serves as a categorization of the set of technical
solutions dedicated to the tasks respective to this stage. For example, we not
only provide a review of node embedding models using the unified framework,
but also describe a set of optimization techniques that are commonly used in
different node embedding methods, and also an overview of recent advances in
NRL.

We list the mathematical notations used throughout the paper in Table 1 for
reference convenience.

The remainder of this survey is structured as follows. In Section 2, we
describe the basic steps of network representation learning to generate node
embeddings using the autoencoder approach. In Section 3, we present an
overview of the unifying three-stage reference framework for NRL, and discuss
representative methods, models, and optimization techniques used at each
stage. In Section 4, we review recent advances in conventional NRL,
distributed NRL, multi-NRL, dynamic NRL and knowledge graph representation
learning by using the proposed reference framework and discuss several open
challenges. In Section 5, we conclude our survey.

Table 1. The list of notations and symbols used in the paper and their meaning Notation/Symbol | Meaning | Notation/Symbol | Meaning
---|---|---|---
W, U, M | bold capital letters represent matrices |  h, ${\bf{u}}_{k}$, ${\bf{v}_{I}}$ | bold lowercase letters represent vectors
${\rm{u}}_{k}$, ${\rm{v}_{I}}$, ${\rm{v}}_{i}$, ${\bf{v}}_{j}$ | lowercase letters represent nodes |  $v_{i}$, $h_{i}$, $y_{i}$ | italic lowercase letters represent vector elements
$\Phi({\cdot}{\rm{)}}$, $f_{\theta_{1}}(\cdot)$ | mapping function, i.e., encoder |  $\Psi(\cdot)$, $g_{\theta_{2}}(\cdot)$ | decoder
$\bf A$ | adjacency matrix | $\bf L$ | Laplacian matrix
$N_{\rm u}$ |  node $\rm u$’s neighborhood | $G_{p}$ | persona graph
$G[N_{\rm u}]$ |  ego-network of node $\rm u$ |  $\bf P^{k}$, $\bf{\Gamma}^{k}$ |  $k$-step transition matrix
$\bf X$ | additional information matrix | ${{\hat{\Psi}}}({{\bf{v}}_{\bf{i}}},{{\bf{v}}_{\bf{j}}})$ | empirical probability
$\bf{g}_{\theta}$ | filter of a convolution operation | $T_{k}(\bf x)$ | Chebyshev polynomials
${\bf{\Theta}}$ | matrix of filter parameters | $AGG_{k}$ |  aggregation function in the $k$th layer
${\rm V}_{neg}$ | set of negative samples | $\eta$ | learning rate
$L_{1st}$, $L_{2nd}$, $L$ | first loss, second loss, loss | $\bf b$ | biase vector
${\bf x}^{(i)}$, ${\bf{\tilde{x}}}^{(i)}$ |  $i$th instance and its corrupted form | $\bf(H^{(i)})_{l}$ |  matrix of representations in the $l$th layer of network $i$
$\bf S^{RPR}$ | rooted PageRank matrix | $\bar{t}_{p}$ | timestamp before the current event
$\bf h$, $\bf r$, $\bf t$ | representations of head, translation and tail | $d_{r}(\bf h,t)$ | distance function of a triple

##  2\. Network Representation Learning: What and How

To establish a common ground for introducing design principles of NRL methods
and techniques, we first provide a walkthrough example to illustrate how
network representation learning works from the autoencoder perspective. We
first briefly describe DeepWalk (Perozzi et al., 2014) as it will be used as
the reference NRL model in this section.

DeepWalk (Perozzi et al., 2014) is generalized from the advancements in
language modeling, e.g., word2vec (Mikolov et al., 2013b). In a language
model, the corpus is built by collecting sentences from many documents. If we
regard node traveling paths as sentences, we can build corpus for network
representation learning. Given an input network, we use the random walk method
with parameters $\gamma$, $t$ and $\alpha$ to generate multiple node traveling
paths, where $\gamma$ decides how many times to issue random walks from a
node, $t$ is the path length, and $\alpha$ is the probability of stopping walk
and restarting from the initial node.

Figure 2. An example of a three-layer neural network used to realize network
representation learning. (1) build corpus based on random walk ($\gamma=4$,
$t=8$, $\alpha=0$); (2) build training set based on sliding window ($s=1$);
(3) build vocabulary to store the set of nodes and their frequency in corpus,
and build a Huffman tree. Note that this step is optional and only necessary
for hierarchical softmax; (4) feed training instance to input layer; (5)
encode input vector into hidden vector; (6) decode hidden vector into
conditional probabilities of context nodes based on softmax or hierarchical
softmax; (7) update matrices W and M or U based on back-propagation method
($\eta=0.025$); (8) output hidden vectors as the learned representations.

NRL example

In the language processing field, skip-gram and continuous bag-of-word (CBOW)
(Mikolov et al., 2013b) are two commonly used models for estimating the
likelihood of co-occurrence among words in training set. For network
representation learning, training instances are extracted from node traveling
paths based on a sliding window. An instance consists of a target node and its
context located within a fixed window size, e.g., (3, (1,7)). In the meantime,
we also need to build a vocabulary to index and sort all nodes by their
frequency in the corpus, and then build a Huffman tree based on the frequency
for hierarchical softmax.

The learning model shown in Fig. 2 contains three layers and it belongs to a
typical autoencoder paradigm. The input vectors are encoded into latent
representation vectors by means of a matrix W, which is known as encoding, and
then the latent representation vectors are reconstructed into output vectors
by means of a matrix U, which is known as decoding. Given a training instance,
skip-gram model is mainly used to forecast the context given a target node,
while on the contrary CBOW model predicts the target node given its context.
Skip-gram model is widely adopted in network representation learning, since
the conditional probability can be decomposed into multiple simple conditional
probabilities under independence assumption,

(1)
$\Pr(context({{\rm{v}}_{\rm{I}}})|\Phi({{\rm{v}}_{\rm{I}}}{\rm{)}})=\prod\limits_{{{\rm{v}}_{j}}\in
contex({{\rm{v}}_{\rm{I}}})}{\Pr({{\rm{v}}_{j}}|\Phi({{\rm{v}}_{\rm{I}}}{\rm{)}})},$

where $\Phi({\cdot}{\rm{)}}$ is a mapping function that embeds nodes into the
low-dimensional vector space, i.e., $\Phi({{\rm{v}}_{\rm{I}}}{\rm{)}}$ refers
to the target node $\rm{v_{I}}$’s learned representation. Here
$\Phi({\cdot}{\rm{)}}$ acts as the encoder from the autoencoder perspective.
Given the embedding of the target node, the conditional probability acts as
the decoder that captures the reconstruction of the target node and its
context nodes in the original network. A loss function is defined accordingly
to measure the reconstruction error and the learning model is trained by
minimizing the loss. To be specific, for each training instance, the target
node $\rm{v_{I}}$ is initially encoded to be a one-hot vector $\bf{v_{I}}$ and
its dimension equals vocabulary size $n$, and W is a $n\times m$ matrix
initialized by letting its entries randomly falling in a range $[-1/2n,1/2n]$.
One-hot encoding implies that $\bf{h}$ is a $m$-dimensional vector simply
copying a row of W associated with the target node $\rm{v_{I}}$. A $m\times n$
matrix $\bf{M}$ is set to decode the encoded vector $\bf{v_{I}}$, where the
conditional probability is obtained by doing softmax, i.e.,
${y_{i}}=\frac{{\exp({{\bf{h}}^{\rm{T}}}{{\bf{m}}_{i}})}}{{\sum\nolimits_{i=1}^{n}{\exp({{\bf{h}}^{\rm{T}}}{{\bf{m}}_{i}})}}}$.
But softmax is not scalable, because for each training instance, softmax
requires to repeat vector multiplication for $n$ times to obtain the
denominator.

To improve computation efficiency of decoder, DeepWalk uses hierarchical
softmax (Mikolov et al., 2013a; Morin and Bengio, 2005) instead of softmax to
implement the conditional probability factorization. Hierarchical softmax
model builds a binary tree and places all network nodes on the leaf layer.
Then there will be $n-1$ branch nodes and each of them has an associated
$m$-dimensional vector. For the output node $\rm{v}_{j}$ in a training
instance, it corresponds to a leaf node $y_{j}$ in the tree representing the
probability of $\rm{v}_{j}$ in the output layer given target node
$\rm{v_{I}}$. It is easy to identify a unique path from the root node to node
$y_{i}$, and the conditional probability can be computed based on the path,
i.e.,

(2)
${y_{j}}=\Pr({{\rm{v}}_{j}}|\Phi({{\rm{v}}_{\rm{I}}}{\rm{)}})=\prod\limits_{k=1}^{{l_{j}}-1}{\Pr({{\bf{u}}_{k}}|\Phi({{\rm{v}}_{\rm{I}}}{\rm{)}})},$

where $l_{j}$ is the length of the path toward $y_{j}$. DeepWalk uses Huffman
tree to implement hierarchical softmax due to its optimal property on average
path length. On the path toward leaf node $y_{j}$, a binary classifier is used
to compute the probability of going left or right at each branch node, i.e.,

(3)
$\Pr({{\bf{u}}_{k}}|\Phi({{\rm{v}}_{\rm{I}}}{\rm{)}})=\left\\{\begin{array}[]{l}\sigma({{\bf{u}}_{k}}^{\rm{T}}\cdot{\bf{h}}),{\rm{go\,left}}\\\
{{\color[rgb]{0,0,0}1-}}\sigma({{\bf{u}}_{k}}^{\rm{T}}\cdot{\bf{h}}),{\rm{go\,right}}\\\
\end{array}\right.,{\,\rm{where}}\,\sigma({{\bf{u}}_{k}}^{\rm{T}}\cdot{\bf{h}})=\frac{1}{{1+\exp(-{{\bf{u}}_{k}}^{\rm{T}}\cdot{\bf{h}})}}.$

The model’s goal is to obtain the maximized conditional probability, which is
equivalent to minimize the following loss function

(4)
$L=-\log\Pr(context({{\rm{v}}_{\rm{I}}})|\Phi({{\rm{v}}_{\rm{I}}}{\rm{)}})=\sum\limits_{{{\rm{v}}_{j}}\in
context({{\rm{v}}_{\rm{I}}})}{-\log{y_{j}}}.$

To this end, back-propagation method is used to update two weight matrices W
and U with gradient descent. Firstly, we take the derivative of loss with
regard to each $\bf{u_{k}}$ on the path toward the context node and obtain

(5) $\frac{{\partial L}}{{\partial{{\bf{u}}_{k}}}}=\frac{{\partial
L}}{{\partial{{\bf{u}}_{k}}^{\rm{T}}\cdot{\bf{h}}}}\cdot\frac{{\partial{{\bf{u}}_{k}}^{\rm{T}}\cdot{\bf{h}}}}{{\partial{{\bf{u}}_{k}}}}=\sum\limits_{{{\rm{v}}_{j}}\in
context({{\rm{v}}_{\rm{I}}})}{\left({\sigma({{\bf{u}}_{k}}^{\rm{T}}\cdot{\bf{h}})-{\pi_{k}}}\right)}\cdot{\bf{h}},$

where $\pi_{k}=1$ if go left and $\pi_{k}=0$ otherwise. The corresponding
vectors in matrix U is updated by

(6) ${{\bf{u}}_{k}}\leftarrow{{\bf{u}}_{k}}-\eta\sum\limits_{{{\rm{v}}_{j}}\in
context({{\rm{v}}_{\rm{I}}})}{\left({\sigma({{\bf{u}}_{k}}^{\rm{T}}\cdot{\bf{h}})-{\pi_{k}}}\right)}\cdot{\bf{h}},\,{\rm{where}}\,\eta\,{\rm{is\,the\,learning\,rate}}{\rm{.}}$

Then for each context node in an instance, we take the derivative of loss with
regard to the hidden vector $\bf{h}$ and obtain

(7) $\frac{{\partial L}}{{\partial{\bf{h}}}}=\sum\limits_{{{\rm{v}}_{j}}\in
context({{\rm{v}}_{\rm{I}}})}{\sum\limits_{k=1}^{{l_{j}}-1}{\frac{{\partial
L}}{{\partial{{\bf{u}}_{k}}^{\rm{T}}\cdot{\bf{h}}}}\cdot\frac{{\partial{{\bf{u}}_{k}}^{\rm{T}}\cdot{\bf{h}}}}{{\partial{\bf{h}}}}}}=\sum\limits_{{{\rm{v}}_{j}}\in
context({{\rm{v}}_{\rm{I}}})}{\sum\limits_{k=1}^{{l_{j}}-1}{\left({\sigma({{\bf{u}}_{k}}^{\rm{T}}\cdot{\bf{h}})-{\pi_{k}}}\right)\cdot}{{\bf{u}}_{k}}}.$

The vector $\bf{w_{I}}$ in matrix W is updated accordingly by

(8)
${{\bf{w}}_{\rm{I}}}\leftarrow{{\bf{w}}_{\rm{I}}}-\eta\sum\limits_{{{\rm{v}}_{j}}\in
context({{\rm{v}}_{\rm{I}}})}{\sum\limits_{k=1}^{{l_{j}}-1}{\left({\sigma({{\bf{u}}_{k}}^{\rm{T}}\cdot{\bf{h}})-{\pi_{k}}}\right)\cdot}{{\bf{u}}_{k}}}.$

The model will learn the latent representation for every node by updating
matrices iteratively and eventually stabilize. The hidden vectors are the node
representations learned from the network.

Fig. 2 shows a simple network with 8 nodes, we build a corpus by running
random walk 4 times for each node and obtain 32 node sequences. We also
generate multiple instances for training by means of a sliding window with
$s=1$, which means a target node may have 2 context nodes at most. Instance
(3, (1,7)) is the first one used for the following training, and the target
node’s input vector is $\rm{v_{3}}$’s one-hot vector (0,0,1,0,0,0,0,0). After
encoded by weight matrix W, we obtain $\rm{v_{3}}$’s hidden vector that is
$\bf{w_{3}}$ here. In order to obtain the conditional probability, we build a
Huffman tree in the output layer. The weight matrix U is a collection of all
branch nodes’ vectors, and they are initialized to be zero vectors so as to
make sure that the probabilities of going left and going right at each branch
are initially identical, i.e., $1/2$. Paths ($\bf{u_{1}}$, $\bf{u_{2}}$,
$\bf{u_{4}}$) and ($\bf{u_{1}}$, $\bf{u_{3}}$, $\bf{u_{7}}$) are two unique
paths toward leaf nodes $y_{1}$ and $y_{7}$ respectively, and then we have
$y_{1}=y_{7}=1/8$ based on Eq. (2). In the following process, we need to
update the correlated vectors in weight matrices reversely to minimize the
loss, so we obtain $\bf{u_{1}}=\bf{0}$, $\bf{u_{2}}=\bf{u_{7}}=\eta\bf{h}/2$,
$\bf{u_{4}}=\bf{u_{3}}=-\eta\bf{h}/2$ based on Eq. (6), and then
$\bf{w_{3}}=\bf{w_{3}}^{(old)}-\eta^{2}\bf{h}/2$ based on Eq. (8). After we
finish the training against all instances, the representation learned from the
model is the hidden vector. Since the input layer uses one-hot encoding, the
network representation is weight matrix W. We plot these representations in a
two-dimensional coordinate system for visualization, where community structure
can be observed.

##  3\. The Reference Framework for Network Representation Learning

We present a unified reference framework illustrated in Fig. 3 to capture the
workflow of network representation learning and it contains three consecutive
stages. The first stage is the network data preprocessing, and it is
responsible for obtaining the desired network structure information from the
original input network. During this stage, the prime aim is to employ a
learning-task suitable network preprocessing method to transform the input
network into a set of internal data structures, which is more suitable for
structural feature extraction in the next stage. Node state and edge state
provide additional context information other than network topological
structure, which are useful and can be leveraged for learning network
representations. Different NRL algorithms tend to have different design
choices on which additional information will be utilized to augment the node
context information in addition to network topological structure. The second
stage is the network feature extraction and it is responsible for sampling
training instances from the input network structure. Prior to sampling, it
should choose the source of raw features that helps preserve the expected
network properties. These properties may optionally be inferred from a
specific learning task. The source of raw features can be classified into
local structure (e.g., node degree, node neighbors, etc.) and global structure
(multi-hop neighborhoods, node rank, etc. ) with respect to every node in the
raw input graph. Different sampling methods are used for extracting features
from different structures. The third stage is the learning node embeddings
over the training set. Different embedding models can be leveraged to learn
hidden features for node embedding, such as matrix factorization,
probabilistic model, graph neural networks. These representative embedding
models are often coupled with optimization techniques, such as hierarchical
softmax, negative sampling, and attention mechanism, for better embedding
effects.

###  3.1. Network Data Preprocessing

The network processing method is the data preparation stage for network
representation learning. When end-users have different applications in mind
for deploying NRL models, different data preprocessing methods should be
employed. Hence, specific learning tasks should be discussed in the section on
network data preprocessing. For example, when NRL trained models are used for
node classification, if the node classification or node clustering aims to
categorize new nodes based on their node state information and node edge
neighbor information, then the preprocessing stage should employ techniques
that can preprocess the raw graph input to obtain those required node state
properties and node linkage properties for deep feature extraction (the second
stage) before entering the NRL model training, the third stage of the network
representation learning workflow. However, if the end-users prefer to perform
node clustering or classification based on only network topology and traversal
patterns over the network structure rather than node state information, then
the pairwise node relationships over the entire network and their hop counts
are critical in the preprocessing stage in order to learn the node distance
features in terms of graph traversal semantics in the stage 2. These two steps
will ensure that the NRL model training in stage 3 will deliver a high quality
NRL model for end-users to perform their task specific node classification or
node clustering, which are network data and domain specific in real world
applications.

Figure 3. A unified reference framework for NRL.

NRL framework

####  3.1.1. Network Preprocessing Methods

To effectively capture useful features, the network structure is usually
preprocessed before feature extraction. We categorize current preprocessing
methods into two types:

Matrix-based Processing In most cases, we are using an adjacency matrix A to
represent a network $G$, where its entries could directly describe the
connection between arbitrary two nodes and the connection is also the basic
unit of network structure. According to the hypothesis in DeepWalk that nodes
with similar contexts are similar, a node’s contexts are defined as the set of
nodes arrived. In order to reflect transitions between nodes, a transition
matrix $\bf{P}=\bf{D^{-1}A}$ is proposed in (Cao et al., 2015), where D is the
diagonal matrix such that $\bf{D_{ii}}=\sum\nolimits_{j}{{A_{ij}}}$, and
$\bf{P}_{ij}$ refers to the one-step transition probability from $\rm{v_{i}}$
to $\rm{v_{j}}$. Accordingly, the transition matrix can be generalized to high
steps, and the transition matrix within $k$ steps (Qiu et al., 2018) is
obtained by $\bf{P^{*}}=\frac{1}{k}\sum\limits_{m=1}^{k}{\bf{P^{m}}}$. Yang et
al. (Yang and Yang, 2018) defined two proximity matrices: the first-order
proximity matrix $\bf{X}^{(1)}$ is the adjacency matrix, and the second-order
proximity matrix $\bf{X}^{(2)}$ consists of
$\bf{X}_{ij}^{(2)}=\cos(\bf{X}_{i}^{(1)},\bf{X}_{j}^{(1)})$, where
$\bf{X}_{i}^{(1)}$, $\bf{X}_{j}^{(1)}$ are the corresponding rows of
$\bf{X}^{(1)}$. As an important branch of embedding, spectral methods require
to convert adjacency matrix A into Laplacian matrix L before the Laplacian
Eigenmaps (Belkin and Niyogi, 2001), where $\bf{L}=\bf{D-A}$.

Graph Decomposition Graph decomposition is another important type of methods
for data preprocessing, by which the original network is decomposed into
multiple graphs and each of them consists of a subset of nodes and a group of
edges that correspond to connections in the original network or are connected
based on certain rules. These graphs may be connected together to form a new
network in order to extract features for a specific network property.

To capture the structural proximity, the context graph (Ribeiro et al., 2017)
is proposed by leveraging the decomposition idea. The context graph is a
multi-layer weighted graph $G_{c}$ and each layer is a complete graph of all
nodes. In particular, the edges in layer $k$ are linked by nodes that are
$k$-hop away from each other, and the edge weight in the layer is defined as
${w_{k}}(i,j)={e^{-{f_{k}}(i,j)}}$, where ${{f_{k}}(i,j)}$ represents the
$k$-structural distance between node $\rm{v_{i}}$ and $\rm{v_{j}}$ calculated
based on their $k$-hop neighborhoods. For adjacent layers, the corresponding
nodes are connected by directed edges, and the edge weights in both directions
are defined as ${w_{k,k+1}}(\rm{v})=\log({\Gamma_{k}}(\rm{v})+e)$ and
${w_{k,k-1}}(\rm{v})=1$, respectively, where ${\Gamma_{k}}(\rm{v})$ denotes
the number of edges incident to node $\rm v$ such that their weights are
higher than the layer $k$’s average weight.

In social networks, ego-network $G[N_{\rm u}]$ induced on user $\rm u$’s
neighborhood $N_{\rm u}$ is often used to denote her/his social circle. If the
interactions of every node in the original network $G$ are divided into
couples of semantic subgroups, these subgroups will capture different
components of user’s network behavior. Based on the idea, Epasto et al.
(Epasto and Perozzi, 2019) propose a method to convert $G$ into its persona
graph $G_{p}$, where each original node corresponds to multiple personas.
Formally, given the original network $G=\\{V,E\\}$ and a clustering algorithm
$\mathbb{A}$, the method consists of three steps: 1) For each node $\rm{u}\in
V$, its ego-network $G[N_{\rm u}]$ is partitioned into $t_{\rm u}$ disjoint
components $N_{\rm u}^{k}$ via $\mathbb{A}$, denoted by $\mathbb{A}(G([{N_{\rm
u}}]))=\\{N_{\rm u}^{k}|k\in[1,{t_{\rm u}}]\\}$; 2) Collect a set $V_{p}$ of
personas, where each original node ${\rm u}$ induces $t_{\rm u}$ personas; 3)
Add connections between personas if and only if $(\rm u,v)$ $\in E$, $\rm
u\in$ $N_{\rm v}^{i}$ and $\rm v$ $\in N_{\rm u}^{j}$. Social users often
participate in different communities, the persona graph obtained via the above
procedure presents a much better community structure for further embeddings.

For very large graphs whose scales exceed the capability of single machine,
they must be decomposed into multiple partitions before further execution.
Adam et al. (Lerer et al., 2019) propose a block decomposition method that
first splits entity nodes into $P$ parts and then divides edges into buckets
based on their source and destination entity nodes’ partitions. For example,
for an edge (u, v), if source u and destination v are in partitions $p_{1}$
and $p_{2}$, respectively, then it should be placed into bucket
$(p_{1},p_{2})$. For each bucket $(p_{i},p_{j})$, source and destination
partitions are swapped from disk, respectively, and the edges are loaded
accordingly for training. To ensure that embeddings in all partitions are
aligned in the same latent space, an ’inside-out’ ordering is adopted to
require that each bucket has at least one previously trained embedding
partition.

####  3.1.2. Learning task

Node classification aims to assign each node to a suitable group such that
nodes in a group have some similar features. Link prediction aims to find out
pairs of nodes that are most likely to be connected. Node classification and
link prediction are two most basic fundamental tasks for network analytics.
Both tasks could be further instantiated into many practical applications such
as social recommendation (Fan et al., 2019), knowledge completion (Lin et al.,
2015), disease-gene association identification (Han et al., 2019), etc.
Therefore, we mainly focus on the two basic tasks. For both tasks, node’s
topological structure is the important basis for classification and
prediction. For example, nodes with more common neighbors often have higher
probability to be assigned to the same group or to be connected. This type of
structure can be generalized to multi-hop neighborhoods (Zhang and Chen,
2018), which requires to compute the transition matrix of the network.

In addition to pure structural information, there are other useful information
available for learning tasks, e.g., node state information and edge state
information. In many real-world networks, node itself may contain some state
information such as node attribute, node label, etc., and this information may
be essential for some tasks. For example, in social networks, besides
embedding social connections, we can also encode user attributes to obtain
more comprehensive representations for individuals (Zhang et al., 2018b; Liao
et al., 2018). Node attributes are still an important source of features to be
aggregated for inductive embeddings (Hamilton et al., 2017b; Bojchevski and
Günnemann, 2018). Nodes with similar attributes and/or structures are more
likely to be connected or classified together. Meanwhile, some node labels are
usually fed into supervised models to boost the task of node classification
(Kipf and Welling, 2017; Zhang et al., 2019). As the most common edge state
information, edge weights can be integrated with topological structure to
achieve more accurate classification and prediction. Besides, edges in some
networks may have signs. Take Epinions and Slashdot as examples, users in
these two social network sites are allowed to connect to other users with
either positive or negative edges, where positive edges represent trust and
like while negative edges convey distrust and dislike. For link prediction on
such a signed network, we have to predict not only possible edges but also
signs of those edges (Wang et al., 2017b; Kim et al., 2018).

###  3.2. Network Feature Extraction

The main task of NRL is to find out the hidden network features and encode
such features as node embedding vectors in a low-dimensional space. Network
properties are used to analyze and compare different network models. For a NRL
task, the learned hidden features should preserve network properties so that
advanced network analytics can be performed accurately and at the same time
the original network properties can be preserved. For example, nodes that are
closer in the original network should also be closer in the latent
representation space in which the node embedding vectors are defined. Most of
the NRL methods focus on preserving topological structures of nodes, such as
in-degree or out-degree neighbors (degree proximity), first order proximity,
random walk distance, and so forth. We categorize the node structural
properties into local structure and global structure.

Embeddings from local structure focus on the preservation of local network
properties such as degree proximity, first-order proximity, etc. In
comparison, global structure provides rich choices of sources of raw features
to be extracted so as to preserve even more network properties. The
classification of source of raw features as well as network properties and
sampling methods are summarized in Table 2.

####  3.2.1. Local Structure Extraction

Local structure reflects a node’s local view about the network, which includes
node degree (in-degree and out-degree), neighbors (in-degree neighbors and
out-degree neighbors), node state and adjacent edge (in-edge and out-edge)
state. To preserve degree proximity, Leonardo et al. (Ribeiro et al., 2017)
define a proximity function ${{f_{k}}(i,j)}$ between two nodes where each
node’s neighbors are sorted based on their degrees and the proximity is
measured by the distance between the sorted degree sequences. The first-order
proximity (Tang et al., 2015b) assumes nodes that are neighbors to each other
(i.e., connected via an edge) are similar in vector space, while the degree of
similarity may depend on the edge state. For example, in a signed social
network, neighbors with positive and negative edges are often called friends
and foes, respectively. From the perspective of social psychology (Wang et
al., 2017b; Kim et al., 2018), when we take edge sign into account, nodes
should be more similar to its friends than its foes in the representation
space. William et al. (Hamilton et al., 2017b) present an inductive
representation learning by aggregating features extracted from neighboring
node states.

Sampling Methods For source of raw features like degree and neighbors,
training instances can be calculated or fetched directly from adjacency
matrix. For adjacent edges, training instances can be generated by edge
sampling. The simple edge sampling is also to fetch entries from adjacency
matrix. When applied to weighted networks where the pairwise proximity has
close relationship with edge weights, if edge weights have a high variance,
the learning model will suffer from gradient explosion or disappearance. To
address the problem, LINE (Tang et al., 2015b) designs an optimized edge
sampling method that fetches edges with the probabilities proportional to
their weights. For node state like node attribute, its features can be
extracted by leveraging existing embedding techniques, e.g., Word2vec (Mikolov
et al., 2013b). If node state is given as a node label, it usually works as
the supervised item to train the embedding model.

####  3.2.2. Global Structure Extraction

Structures that transcend local views can be considered global such as multi-
hop neighborhoods, community, connectivity pattern, etc. Considering that the
first-order proximity matrix may not be dense enough to model the pairwise
proximity between nodes, as an global view (Cao et al., 2015), the pairwise
proximity is generalized to high-order form by using $k$-step transition
matrix, i.e., $\bf{P}^{k}$. Instead of preserving a fixed high-order
proximity, Zhang et al. (Zhang et al., 2018a) define the arbitrary-order
proximity by calculating the weighted sum of all $k$-order proximities.
Community structure is an important network property with dense intra-
community connections and sparse inter-community connections, and it has been
observed in many domain-specific networks, e.g., social networks, co-authoring
networks, language networks, etc. Wang et al. (Wang et al., 2017a) introduce a
community representation matrix by means of the modularity-driven community
detection method, and use it to enable each node’s representation similar to
the representation of its community. Considering that a node may belong to
multiple communities, Sun et al. (Sun et al., 2017) define a $n\times m$ basis
matrix $\bf{W}$ to reveal nodes’ community memberships, where $n$ is the node
set size, $m$ is the total number of communities and $\bf{W}_{ij}$ indicates
the propensity of node $\rm{v_{i}}$ to community $C_{j}$. The basis matrix is
learned and preserved during the representation learning process.

Network nodes usually act as various structural roles (Grover and Leskovec,
2016; Ahmed et al., 2018) and appear different connectivity patterns such as
hubs, star-edge nodes, bridges connecting different clusters, etc. Node role
proximity assumes nodes with similar roles have similar vector representations
and it is a global structural property that is different from community
structure, since it primarily focuses on the connection patterns between nodes
and their neighbors.

As a global structural property, node rank is always used to denote a node’s
importance in the network. PageRank (Page et al., 1998) is a well-known
approach to evaluate the rank of a node by means of its connections to others.
Specifically, the ranking score of a node is measured by the probability of
visiting it, while the probability is obtained from the ranking score
accumulated from its direct predecessors weighted by the reciprocal of its
out-degree. Lai et al. (Lai et al., 2017) demonstrate that node
representations with global ranking preserved can potentially improve both
results of ranking-oriented tasks and classification tasks. Node degree
distribution is also a global inherent network property. For example, scale-
free property refers to a fact that node degrees follow a heavy-tailed
distribution, and it has proven to be ubiquitous across many real networks,
e.g., Internet, social networks, etc. The representation learning for scale-
free is explored in (Feng et al., 2018).

Another global structural property is proposed in Struc2vec (Ribeiro et al.,
2017) that considers structural similarity from network equivalence
perspective without requiring two nodes being nearby, i.e., independent of
nodes’ network positions. To reflect this property, Struc2vec presents a
notion of node structural identity that refers to a node’s global sense.
Struc2vec uses the multi-layer graph output from data preprocessing stage to
measure node similarity at different scales. In the bottom layer, the
similarity exclusively depends on node degrees. In the top layer, the
similarity lies in the entire network. Tu et al. (Tu et al., 2018) propose a
similar concept, i.e., regular equivalence, to describe the similarity between
nodes that may not be directly connected or not having common neighbors.
According to its recursive definition, neighbors of regularly equivalent nodes
are also regularly equivalent. To ensure the property of regular equivalence,
each node’s embedding is approximated by aggregating its neighbors’
embeddings. After updating the learned representations iteratively, the final
node embedding is capable of preserving the property in a global sense.

Different types of global structure are used to reflect different network
properties where multi-hop neighborhoods, node connectivity pattern and node
identity are used to preserve pairwise proximity, which reflects a pairwise
relationship between nodes, including high-order proximity, node role
proximity, and node identity proximity. For example, the node community
membership reflects a relationship between a node and a group of nodes, which
share some common network properties. Furthermore, node rank and node degree
distribution are used to preserve a kind of distribution-based network
property, including node importance ranking, or a relationship between a node
and the entire network, such as the scale free network whose degree
distribution follows a power law.

Sampling Methods For source of raw features like multi-hop neighborhoods, they
can be obtained by matrix power operation, i.e., $\bf{A}^{k}$, but the
computation suffers from high complexity. Random walk and its variants are
widely explored to capture the desirable network properties with high
confidence. For example, DeepWalk (Perozzi et al., 2014) presents a truncated
random walk to generate node traveling paths. It uses co-occurrence
frequencies between node and its multi-hop neighborhoods along these paths to
reflect their similarity and capture the high-order proximity accordingly.

From the perspective of community structure, due the dense intra-community
connections, nodes within the same community have higher probability to co-
occur on the traveling paths than nodes in different communities. Hence random
walk can also be used to capture the community structure. When we consider the
hierarchy of communities, different communities may have different scales. The
regular random walk makes the training set having more entries from
$\bf{A}^{i}$ than from $\bf{A}^{j}$ ($1\leq i<j$), and then it is biased
towards preserving small-scale community structure. Walklets (Perozzi et al.,
2017) presents a skipped random walk to sample multi-scale node pairs by
skipping over steps in each traveling path.

Another drawback of random walk is that it requires too many steps or restarts
to cover a node’s neighborhoods. To improve its coverage, Diff2Vec
(Rozemberczki and Sarkar, 2020) present a diffusion-based node sequence
generating method that consists of two steps: 1) Diffusion graph generation,
which is in charge of generating a diffusion graph $DG_{i}$ for each node
$\rm{v_{i}}$. $DG_{i}$ is initialized with $\rm{v_{i}}$, and then randomly
fetch node $\rm{v_{j}}$ from $DG_{i}$ and node $\rm{v_{k}}$ from
$\rm{v_{j}}$’s neighborhoods in the original graph, append two nodes and the
edge $e_{jk}$ to $DG_{i}$. The above process is repeated until $DG_{i}$ grows
to the predefined size. 2) Node sequence sampling, which generates Euler walk
from $DG_{i}$ as the node sequence. To make sure $DG_{i}$ is Eulerian,
$DG_{i}$ is converted to a multi-graph by doubling every edge into two edges.

Real-world networks often exhibit a mixture of multiple network properties. In
order to capture both community structure and node role proximity, node2vec
(Grover and Leskovec, 2016) designs a flexible biased random walk that
generates traveling paths in an integrated fashion of BF (breadth-first)
sampling and DF (depth-first) sampling. To this end, two parameters $p$ and
$q$ are introduced to smoothly interpolate between two sampling methods, where
$p$ decides the probability of re-fetching a node in the path while $q$ allows
the sampling to discriminate between inward and outward nodes.

In scale-free networks, a tiny fraction of ”big hubs” usually attracts most
edges. Considering that connecting to ”big hubs” does not imply proximity as
strong as connecting to nodes with mediocre degrees, a degree penalty based
random walk (Feng et al., 2018) is proposed. For a pair of connected nodes
($\rm v_{i}$, $\rm v_{j}$), its principle is to reduce the likelihood of $\rm
v_{j}$ being sampled as $\rm v_{i}$’s context when $\rm v_{i}$ has a high
degree and they do not share many common neighbors. To this end, the jumping
probability from $\rm v_{i}$ to $\rm v_{j}$ is defined as
$\frac{{{C_{ij}}}}{{{{({D_{ii}}{D_{jj}})}^{\beta}}}}$, where $C_{ij}$ denotes
the first and second order of proximity between two nodes, $D_{ii}$ and
$D_{jj}$ are their degrees, and $\beta$ is a parameter.

As an anonymous version of random walk, anonymous walk (Ivanov and Burnaev,
2018) provides a flexible way to reconstruct a network. For a random walk $\rm
rw=(v_{1},v_{2},...,v_{k})$, its corresponding anonymous walk is the sequence
of node’s first occurrence positions, i.e., $\rm
aw=(f(v_{1}),f(v_{2}),...,f(v_{k}))$, where $\rm
f({v_{i}})=\mathop{\min}\limits_{{p_{j}}\in pos(rw,v_{i})}pos(rw,v_{i})$. For
an arbitrary node $\rm v\in G$, a known distribution ${\rm D}_{l}$ over
anonymous walks of length $l$ is sufficient to reconstruct a subgraph of $\rm
G$ that is induced by all nodes located within $r$ hops away from $\rm v$.
Therefore, anonymous walk can be used to preserve global network properties
like high-order proximity and community structure by approximating the
distributions.

One of the baseline approaches to extracting global structure is to use random
walk as the sampling method. For complex types of global structure, e.g.,
multi-hop neighborhoods and node community membership, an integrated sampling
method is often recommended, which combines random walk with other types of
graph traversal methods, such as anonymous walk. An advantage of using
anonymous walk as the sampling approach is that it is sufficient to
reconstruct the topology around a node by utilizing distribution of anonymous
walks of a single node, because anonymous walk captures richer semantics than
random walk.

Table 2. Classification of source of raw features, network property and sampling method Categority | Source of raw features | Network property | Sampling method
---|---|---|---
Local structure |  Degree/in-degree/out-degree (Ribeiro et al., 2017) | Degree proximity | Directly from adjacency matrix
Neighbors/in-degree neighbors/out-degree neighbors (Tang et al., 2015b) | First-order proximity | Directly from adjacency matrix
Node state (Hamilton et al., 2017b) | Node state proximity | Directly from node state information
Adjacent edge state (Wang et al., 2017b; Kim et al., 2018) | First-order proximity | Weighted edge sampling
Global structure |  Multi-hop neighborhoods (Zhang et al., 2018a) | High-order proximity | Random/Anonymous walk
Node community membership (Wang et al., 2017a; Sun et al., 2017) | Community structure | Random/Anonymous walk
Node connectivity pattern (Grover and Leskovec, 2016; Ahmed et al., 2018) | Node role proximity | Random walk
Node degree distribution (Feng et al., 2018) | Scale-free | Degree penalty based random walk
Node rank (Lai et al., 2017) | Node importance ranking | Random walk
Node identity (Ribeiro et al., 2017; Tu et al., 2018) | Node identity proximity | Random walk

###  3.3. Node Embedding

Recent years many efforts have been devoted to the design of node embedding
model. We are trying to review those work from a universal perspective of
autoencoder. In general, node embedding is equivalent to an optimization
problem that encodes network nodes into latent vectors by means of an encoding
function $\Phi:V\to{\mathbb{R}^{d}}$. Meanwhile the objective is to ensure
that the results decoded from vectors preserve the network properties we
intend to incorporate, where the decoder is represented by a function of
encoding results, i.e., $\Psi:{[{\mathbb{R}^{d}}]^{t}}\to\mathbb{R}$, where
$t$ denotes the number of input arguments. The output vectors are the latent
representations of hidden features learned by $\Phi$, and they are also the
expected node representations.

####  3.3.1. Embedding Models

We classify the current embedding models into the following three types.

Matrix Factorization Given the matrix of input network, matrix factorization
embedding factorizes the matrix to get a low-dimensional matrix as the output
collection of node representations. Its basic idea can be traced back to the
matrix dimensionality reduction techniques (Chen et al., 2018a). According to
the matrix type, we categorize the current work into relational matrix
factorization and spectral model.

_(1) Relational Matrix Factorization_ Matrix analysis often requires figuring
out the inherent structure of a matrix by a fraction of its entries, and it is
always based on an assumption that a matrix $\bf{M}_{n\times n}$ admits an
approximation of low rank $d\ll n$. Under this assumption, the objective of
matrix factorization corresponds to finding a matrix $\bf{W}_{d\times n}$ such
that $\bf{W}^{T}\bf{W}$ approximates $\bf{M}$ with the lowest loss $L$, where
$L:{[\mathbb{R}]^{2}}\to\mathbb{R}$ is a user-defined loss function. In the
autoencoder paradigm, the encoder is defined by the matrix $\bf{W}_{d\times
n}$, e.g., $\Phi(\rm{v_{i}})=\bf{w}_{i}$, each column $\bf{w}_{i}$ represents
a vector. The decoder is defined by the inner product of two node vectors,
e.g., $\Psi(\bf{w}_{i},\bf{w}_{j})=\bf{w}_{i}^{T}\bf{w}_{j}$, so as to infer
the reconstruction of the proximity between node $\rm{v_{i}}$ and
$\rm{v_{j}}$. When we focus on preserving the first-order proximity $\mu$,
i.e., $\mu(\rm{v_{i}},\rm{v_{j}})=\bf{A}_{ij}$, and let $\Omega$ be the
training set sampled from $\bf{A}$, then the objective is to find $\bf{W}$ to
minimize the reconstruction loss, i.e.,

(9)
$\mathop{\arg\min}\limits_{\bf{W}}L=\sum\limits_{({\rm{v_{i}}},{\rm{v_{j}}})\in\Omega}{\left\|{\Psi(\bf{w}_{i},\bf{w}_{j})-\mu({v_{i}},{v_{j}})}\right\|_{F}^{2}}=\left\|{\bf{W}^{T}\bf{W}-A}\right\|_{F}^{2},$

where Frobenius norm $\left\|\cdot\right\|_{F}^{2}$ is often used to define
the loss function. Singular value decomposition (SVD) (Golub and Reinsch,
1970) is a well-known matrix factorization approach that can find the optimal
rank $d$ approximation of proximity matrix $\bf{A}$. If the network property
focuses on high-order proximity, the proximity matrix can be replaced by power
matrix, e.g., $\bf{A}^{k}$, $\bf{P}^{k}$, $k>1$. For example, GraRep (Cao et
al., 2015) implements node embedding by factorizing $\bf{P}^{k}$ into two
matrices $\bf{W}$ and $\bf{M}$,

(10)
$\mathop{\arg\min}\limits_{\bf{W}}\left\|{\bf{W^{T}}\bf{M}-{P^{k}}}\right\|_{F}^{2},$

where $\bf{W}$ denotes the representation matrix and $\bf{M}$ denotes the
parameter matrix in decoder, e.g., the unary decoder
$\Psi(\bf{w_{i}})=\bf{w}_{i}^{T}M$ computes the reconstructed proximities
between $\rm{v_{i}}$ and other nodes.

In the autoencoder paradigm, the equivalence between DeepWalk and matrix
factorization can be proved by making the following analogies: 1) Define the
pairwise proximity $\mu(\rm{v_{i}},\rm{v_{j}})$ as the co-occurrence
probability inferred from the training set. 2) Let $\bf{W}$ and $\bf{M}$
corresponds to $\bf{W}^{T}$ and $\bf{M^{T}}$ in DeepWalk, where each column
$\bf{w}_{i}$, $\bf{m}_{i}$ of them refers to the representation of node
$\rm{v_{i}}$ acting as target node and context node, respectively.

In addition, matrix factorization can also incorporate additional information
into node embeddings. For example, given a text feature matrix
$\bf{T}_{x\times n}$ where $n$ denotes the node set size and $x$ denotes the
feature vector dimension, TADW (Yang et al., 2015) applies inductive matrix
completion to the node embedding and defines the following matrix
factorization problem:

(11)
$\mathop{\arg\min}\limits_{{\bf{W}},{\bf{M}}}\left\|{{{\bf{P}}^{\bf{*}}}-{{\bf{W}}^{\rm{T}}}{\bf{MT}}}\right\|_{F}^{2}+\frac{\lambda}{2}\left({\left\|{\bf{W}}\right\|_{F}^{2}+\left\|{\bf{M}}\right\|_{F}^{2}}\right),$

where $\lambda$ is a harmonic factor. The output matrices $\bf{W}$ and
$\bf{MT}$ factorized from the transition matrix $\bf{P}^{*}$ can be regarded
as the collection of node embeddings and concatenated as a $n\times 2d$
representation matrix.

_(2) Spectral Model_ In spectral model, a network is mathematically
represented by a Laplacian matrix, i.e., $\bf{L}=D-A$, where adjacency matrix
$\bf{A}$ acts as the proximity matrix, and the entry $\bf{D}_{ii}$ of diagonal
matrix $\bf{D}$ describes the importance of node $\rm{v}_{i}$. $\bf{L}$ is a
symmetric positive semidefinite matrix that can be thought of as an operator
on functions defined on the original network. Let $\bf{W}_{n\times d}$ be the
representation matrix, it also acts as the encoder that maps the network to a
$d$-dimensional space. The representations should assure neighboring nodes
stay as close as possible. As a result, the decoder can be defined as
$\bf{w}_{i}^{T}Lw_{i}$ according to Laplacian Eigenmaps (Belkin and Niyogi,
2003), where $\bf{w}_{i}$ is the $i$th column of $\bf{W}$. Then the node
embedding problem is defined as follows:

(12)
$\mathop{\arg\min}\limits_{{{\bf{W}}^{\rm{T}}}{\bf{DW}}={\bf{I}}}{{\bf{W}}^{\rm{T}}}{\bf{LW}},$

where ${{{\bf{W}}^{\rm{T}}}{\bf{DW}}={\bf{I}}}$ is imposed as a constraint to
prevent collapse onto a subspace of dimension less than $d-1$. The solution
$\bf{W}$ consists of the eigenvectors $\bf{w_{i}}$ corresponding to the lowest
$d$ eigenvalues of the generalized eigenvalue problem $\bf{L}w=\lambda Dw$.
Furthermore, given an additional information matrix $\bf{X}$ describing node
attribute features, the node embedding can be derived by following the idea of
locality preserving projection (LPP) (He and Niyogi, 2003) that introduces a
transformation matrix $\bf{M}$ to realize the mapping $\bf{w}_{i}=M^{T}x_{i}$,
where $\bf{w}_{i}$ and $\bf{x}_{i}$ are the $i$th column of $\bf{W}$ and
$\bf{X}$. Similarly, the solution $\bf{M}$ is obtained by computing the
mapping vectors $\bf{m}$ corresponding to $d$ lowest eigenvalues of the
problem $\bf{XLX^{T}}m=\lambda XDX^{T}m$, and the node embedding incorporates
additional information by $\bf{W}=M^{T}X$.

Probabilistic Model Probabilistic model is specifically designed for node
embedding via preserving the pairwise proximity measured by a flexible
probabilistic manner.

_(1) Skip-gram Model_ Skip-gram is the classic embedding model that converts
pairwise proximity to the conditional probability between node and its
context. For example, DeepWalk (Perozzi et al., 2014) relies on the co-
occurrence probability derived from random traveling paths to preserve the
second-order proximity during node embedding.

_(2) Edge Probabilistic Model_ Edge probabilistic model enforces node
embeddings designed primarily for network reconstruction. For example, LINE
(Tang et al., 2015b) relies on the idea of edge probability reconstruction
without assistance of random walk sampling. It focuses on preserving both
first-order and second-order proximities by defining two decoders, i.e.,

(13)
${\Psi_{1}}({{\bf{v}}_{\bf{i}}},{{\bf{v}}_{\bf{j}}})=\Pr(\rm{v_{i}},\rm{v_{j}})=\frac{1}{{1+\exp(-{{\bf{v}}_{\bf{i}}}^{\rm{T}}{{\bf{v}}_{\bf{j}}})}},\,{\Psi_{2}}({{\bf{v}}_{\bf{i}}},{{\bf{m}}_{\bf{j}}})=\Pr({v_{j}}|{v_{i}})=\frac{{\exp({{\bf{m}}_{\bf{j}}}^{\rm{T}}{{\bf{v}}_{\bf{i}}})}}{{\sum\nolimits_{k=1}^{n}{\exp({{\bf{m}}_{\bf{k}}}^{\rm{T}}{{\bf{v}}_{\bf{i}}})}}},$

where $\bf m_{k}$ refers to the representation of $\rm v_{k}$ acting as a
context node. The objectives to be optimized are based on the loss functions
derived from the distance $Dis(\cdot,\cdot)$ between two distributions, i.e.,

(14)
$\mathop{\arg\min}\limits_{{{\bf{v}}_{\bf{i}}}}\sum\limits_{i=1}^{n}{{\lambda_{i}}Dis({\Psi_{1}}({{\bf{v}}_{\bf{i}}},\cdot),{{\hat{\Psi}}_{1}}({{\bf{v}}_{\bf{i}}},\cdot))},\,\mathop{\arg\min}\limits_{{{\bf{v}}_{\bf{i}}}}\sum\limits_{i=1}^{n}{{\lambda_{i}}Dis({\Psi_{2}}({{\bf{v}}_{\bf{i}}},\cdot),{{\hat{\Psi}}_{2}}({{\bf{v}}_{\bf{i}}},\cdot))}$

where
${{\hat{\Psi}}_{1}}({{\bf{v}}_{\bf{i}}},{{\bf{v}}_{\bf{j}}})=\frac{{{s_{ij}}}}{{\sum\nolimits_{{e_{xy}}\in
E}{{w_{xy}}}}},{{\hat{\Psi}}_{2}}({{\bf{v}}_{\bf{i}}},{{\bf{v}}_{\bf{j}}})=\frac{{{s_{ij}}}}{{\sum\nolimits_{{e_{ik}}\in
E}{{s_{ik}}}}}$ are the empirical probabilities and $s_{ij}$ is the weight of
edge $e_{ij}$.

Graph Neural Networks It is not difficult to find that each node’s embedding
via the above models requires the participation of its neighboring nodes,
e.g., building $k$-order proximity matrix with nodes and their $k$-step
neighborhoods in matrix factorization model, and counting node’s co-occurrence
frequency with its context nodes in skip-gram model. The common idea can be
intuitively generalized to a more general model, graph neural networks (GNNs)
that follow a recursive neighborhood aggregation or message passing scheme.
Graph convolutional network (GCN) (Bruna et al., 2014) is a very popular
variant of GNNs, where each node’s representation is generated by a
convolution operation that aggregates its own features and its neighboring
nodes’ features. Graph isomorphism network (GIN) (Xu et al., 2019) is another
recently proposed variant with a relatively strong expressive power.

_(1) Graph Convolutional Network_ In terms of the definition of convolution
operation (Wu et al., 2019b), GCNs are often grouped into two categories:
Spectral GCNs and Spatial GCNs. Spectral GCNs (Defferrard et al., 2016; Bruna
et al., 2014) define the convolution as conducting the eigendecomposition of
the normalized Laplacian matrix ${\bf{L}}={{\bf
I}_{\rm{n}}}-{{\bf{D}}^{{\rm{-}}\frac{{\rm{1}}}{{\rm{2}}}}}{\bf{A}}{{\bf{D}}^{{\rm{-}}\frac{{\rm{1}}}{{\rm{2}}}}}$
in Fourier domain. An intuitive way to explain spectral convolution is to
regard it as an operation that uses a filter $\bf{g}$ to remove noise from a
graph signal $\bf{x}\in\mathbb{R}^{n}$. The graph signal denotes a feature
vector of the graph with entry $\bf{x}_{i}$ representing node $\rm{v}_{i}$’s
value. Let $\bf{U}$ be the matrix of eigenvectors of $\bf{L}$, graph Fourier
transform is defined as a function that projects input signal $\bf{x}$ to the
orthonormal space formed by $\bf{U}$, i.e., $\mathcal{F}(\bf{x})=\bf{U}^{T}x$.
Let $\bf{\hat{x}}$ be the transformed signal, entries of $\bf{\hat{x}}$
correspond to the coordinates of the input signal in the new generated space,
and the inverse Fourier transform is defined as
$\mathcal{F}^{-1}(\bf{\hat{x}})=\bf{U}\hat{x}$. When the filter $\bf{g}$ is
parameterized by $\bf\theta\in\mathbb{R}^{n}$ and defined as
${{\bf{g}}_{\bf{\theta}}}=diag({{\bf{U}}^{\rm{T}}}{\bf{g}})$, then the
convolution operation against signal $\bf{x}$ with filter $\bf{g}_{\theta}$ is
represented by

(15)
${{\bf{g}}_{\bf{\theta}}}\star{\bf{x}}={{\mathcal{F}}^{{\bf{-1}}}}(\mathcal{F}({\bf{g}})\circ\mathcal{F}({\bf{x}}))={\bf{U}}({{\bf{U}}^{\rm{T}}}{\bf{g}}\circ{{\bf{U}}^{\rm{T}}}{\bf{x}})={\bf{U}}{{\bf{g}}_{\bf{\theta}}}{{\bf{U}}^{\rm{T}}}{\bf{x}},$

where $\circ$ represents the Hadamard product. Nevertheless, The
eigendecomposition of Laplacian matrix $\bf{L}$ is expensive for large graphs,
and the complexity of multiplication with $\bf{U}$ is $O(n^{2})$. To address
the complexity problem, Hammond et al. (Hammond et al., 2011) suggests that
the filter $\bf{g}_{\theta}$ can be approximated by an abridged expansion
based on Chebyshev polynomials $T_{k}(\bf{x})$ up to $K$th order. The
convolution is redefined as

(16)
${{\bf{g}}_{{\bf{\theta}}^{\prime}}}\star{\bf{x}}\approx\sum\limits_{k=0}^{K}{{\bf{\theta}}{{}^{\prime}_{k}}{T_{k}}({\bf{\tilde{L}}}){\bf{x}}},$

where
${\bf{\tilde{L}}}=\frac{2}{{{\lambda_{\max}}}}{\bf{L}}-{{\bf{I}}_{\rm{n}}}$
and $T_{k}(\bf{x})=2\bf{x}T_{k-1}(\bf{x})-T_{k-2}(\bf{x})$ with
$T_{1}(\bf{x})=x$ and $T_{0}(\bf{x})=\rm 1$. The above convolution operation
is $K$-localized since it requires the participation of the neighboring nodes
within $K$-hop away from the central node. Spectral GCNs model consists of
multiple convolution layers of the form Eq. 16 where each layer is followed by
a point-wise non-linearity. From the perspective of autoencoder, each node’s
feature embedding is encoded by the convolution operation, so that the graph
convolution actually acts as the encoder and we call it spectral convolution
encoder or filter encoder here. In order to deal with multi-dimensional input
graph signals, the spectral convolution encoder is generalized to account for
the signal matrix $\bf{X}\in\mathbb{R}^{n\times c}$ with $c$ input channels
and $d$ filters, i.e.,

(17)
$\Phi({\bf{X}},{\bf{A}})={{{\bf{\tilde{D}}}}^{-\frac{1}{2}}}{\bf{\tilde{A}}}{{{\bf{\tilde{D}}}}^{-\frac{1}{2}}}{\bf{X\Theta}},$

where $\bf{\tilde{A}}=A+I_{n}$,
$\bf{\tilde{D}}_{ii}={\sum\nolimits_{j}{{\bf{\tilde{A}}}}_{ij}}$ and
${\bf{\Theta}}\in{\mathbb{R}^{c\times d}}$ is matrix of filter parameters. The
signal matrix is often initialized by the input graph information such as node
attributes. It is noted that the filter parameters ${\bf{\Theta}}$ can be
shared over the whole graph, which significantly decreases the amount of
parameters as well as improves the efficiency of filter encoder.

Similar to convolution neural networks on images, spatial GCNs (Hamilton et
al., 2017b) consider graph nodes as image pixels and directly define
convolution operation in the graph domain as the feature aggregation from
neighboring nodes. To be specific, the convolution acts as the encoder to take
the aggregation of the central node representation and its neighbors’
representations to generate an updated representation, and here we call it
spatial convolution encoder or aggregation encoder. In order to explore the
depth and breadth of a node’s receptive field, spatial GCNs usually stack
multiple convolution layers. For a $K$-layer spatial GCN, its aggregation
encoder ${\Phi}$ is defined as follows:

(18)
$\left\\{\begin{array}[]{l}\Phi({\bf{X}},{\bf{A}})=NORM({{\bf{H}}^{\rm{K}}}),{{\bf{H}}^{\rm{K}}}=({\bf{h}}_{\rm{1}}^{\rm{K}},...,{\bf{h}}_{\rm{n}}^{\rm{K}}),\\\
{\bf{h}}_{\rm{v}}^{\rm{k}}=\sigma({{\bf{W}}^{\rm{k}}}\cdot
AG{G_{\rm{k}}}({\bf{h}}_{\rm{v}}^{{\rm{k-1}}},\\{{\bf{h}}_{\rm{u}}^{{\rm{k-1}}}\\})),\forall{\rm{u}}\in{N_{\rm{v}}},\forall{\rm{k}\in[0,\rm{K}]},\\\
\end{array}\right.$

where $\bf{h}_{\rm{v}}^{\rm{k}}$ is node $\rm v$’s representation (also called
hidden state in some other literatures) in the $k$th layer with
$\bf{h}_{\rm{v}}^{\rm{0}}=\bf{x}_{v}$. $AGG_{\rm{k}}$ is an aggregation
function responsible for assembling a node’s neighborhood information in the
$k$th layer, and parameter matrix $\bf{W}^{k}$ specifies how to do aggregation
from neighborhoods, like filters in spectral GCNs, $\bf{W}^{k}$ is shared
across all graph nodes for generating their representations. As the layer
deepens, the node representations will contain more information aggregated
from wider coverage of nodes. The final node representations are output as the
normalized matrix of node representations on layer $\rm K$, i.e.,
$NORM({\bf{H}}^{\rm{K}})$.

Table 3. Classification of node embedding models Category |  Sub-category |  Encoder |  Decoder |  Optimization objective | Publication
---|---|---|---|---|---
Matrix Factorization |  Relational matrix factorization |  $\Phi(\rm{v_{i}})=\bf{w}_{i}$ |  $\Psi(\bf{w}_{i},\bf{w}_{j})=\bf{w}_{i}^{T}\bf{w}_{j}$, $\Psi(\bf{w_{i}})=\bf{w}_{i}^{T}M$, $\Psi(\bf{w_{i}})=\bf{w}_{i}^{T}MT$ |  Eq. 9, Eq. 10, Eq. 11 | (Cao et al., 2015; Yang et al., 2015)
Spectral model |  $\Phi(V)=\bf{W}$, $\Phi(V)=\bf{M}^{T}X$ |  $\bf{w}_{i}^{T}Lw_{i}$, $\bf{x_{i}Lx_{i}^{T}m_{i}}$ |  Eq. 12 | (Belkin and Niyogi, 2003; He and Niyogi, 2003)
Probabilistic Model |  Skip-gram model |  $\Phi(\rm{v_{i}})=\bf{w}_{i}$ |  Eq. 2 |  Eq. 4 | (Perozzi et al., 2014)
Edge probabilistic model |  $\Phi(\rm{v_{i}})=\bf{w}_{i}$ |  Eq. 13 |  Eq. 14 | (Tang et al., 2015b)
Graph Neural Networks |  Spectral Graph Convolutional Network |  Eq. 17 |  $\Psi_{\bf{\theta}}(\Phi(\bf{x}_{i},A))$ |  Eq. 20 | (Hammond et al., 2011; Kipf and Welling, 2017, 2016)
Spatial Graph Convolutional Network |  Eq. 18 |  $\Psi_{\bf{\theta}}(\Phi(\bf{x}_{i},A))$ |  Eq. 20 | (Hamilton et al., 2017b)
Graph Isomorphism Network |  Eqs. 18, 19 |  $\Psi_{\bf{\theta}}(\Phi(\bf{x}_{i},A))$ |  Eq. 20 | (Xu et al., 2019)

_(2) Graph Isomorphism Network_ The representational power of a GNN primarily
depends on whether it maps two multisets to different representations, where
multiset is a generalized concept of a set that allows multiple instances for
its elements. The aggregation operation can be regarded as a class of
functions over multisets that their neural networks can represent. To maximize
the representational power of a GNN, its multiset functions must be injective.
GCN has been proven to be not able to distinguish certain simple structural
features as its aggregation operation is inherently not injective. To model
injective multiset functions for the neighbor aggregation, GIN (Xu et al.,
2019) presents a theory of deep multisets that parameterizes universal
multiset functions with neural networks. With the help of multi-layer
perceptrons (MLPs), GIN updates node representations as follows:

(19)
${\bf{h}}_{\rm{v}}^{\rm{k}}=MLP^{\rm{k}}\left({\left({1+{{\varepsilon}^{\rm{k}}}}\right){\bf{h}}_{\rm{v}}^{\rm{k-1}}+\sum\limits_{{\rm{u}}\in{N_{\rm{v}}}}{{\bf{h}}_{\rm{u}}^{\rm{k-1}}}}\right),$

where $\varepsilon$ is a learnable parameter or a fixed scalar. The
aggregation encoder $\Phi$ can be defined in the same way of Eq. 18.

For both GCN and GIN, the decoder can be designed in any form of the
previously discussed decoders. Recently, many efforts have been devoted to
designing task-driven GCNs, so that the decoder has to incorporate supervision
from a specific task. For instance, assume that each node has a label chosen
from a label set $\bf{y}$. A function like sigmoid,
$y_{i}=\Psi_{\bf{\theta}}(\Phi(\bf{x}_{i},A))$, can be defined as a decoder to
realize the mapping from a node representation $\Phi(\bf{x}_{i},A)$ to its
corresponding label $y_{i}$, where parameters $\theta$ are learnable
throughout the embedding process. We use function
$f(\hat{y_{i}},\Psi_{\bf{\theta}}(\Phi(\bf{x}_{i},A)))$ to measure the loss
between the true label $\hat{y_{i}}$ and the predicted one $y_{i}$, then the
objective is concluded as

(20)
$\mathop{\arg\min}\limits_{\Phi({{\bf{x}}_{\rm{i}}},{\bf{A}})}\sum\limits_{{\rm{i}}=1}^{n}{f({{\hat{y}}_{\rm{i}}},\Psi_{\theta}(\Phi({{\bf{x}}_{\rm{i}}},{\bf{A}})))}.$

We summarize the specific classification of node embedding models outlined in
Table 3 and make comparisons among them as shown in Table 4.

Table 4. Comparison of node embedding models Category | Advantage | Disadvantage
---|---|---
Matrix Factorization |  1) has the solid theoretical foundation available to enhance its interpretability. 2) additional information, e.g., node state and edge state, can be easily incorporated into the matrix factorization model. |  1) high computation cost. 2) hard to be applied to dynamic embedding.
Probabilistic Model |  relatively efficient compared to other models especially when it was designed for network reconstruction. |  hard to be applied to dynamic embedding.
Graph Neural Networks |  1) naturally supports embedding of both structural and additional information. 2) easy to be applied to dynamic embedding. |  high computation cost.

####  3.3.2. Optimization Techniques

Many of the above models have achieved non-trivial embedding results. The
success of these models inevitably relies on some optimization techniques that
have been proposed to assist the node embedding from various aspects such as
the computational complexity reduction, the acceleration of embedding process
and the enhancement of training efficiency and effectiveness. In this section,
we will show several popular optimization techniques with a focus on how they
work at different stages of NRL, and summarize these techniques in Table 5.

Hierarchical Softmax As a variant of softmax, hierarchical softmax (Morin and
Bengio, 2005; Perozzi et al., 2014) has been proposed to speed up the training
process. To this end, hierarchical softmax leverages a well-designed tree
structure with multiple binary classifiers to compute the conditional
probabilities for each training instance (see Sec. 2 for details). Therefore,
it helps decoder reduce the complexity from $O(n)$ to $O(\log n)$.

Negative Sampling As an alternative to hierarchical softmax, noise contrastive
estimation (NCE) (Gutmann and Hyvärinen, 2012) suggests that logistic
regression can be used to help models distinguish data from noise. Negative
sampling (NEG) is a simplified version of NCE that was firstly leveraged by
Word2vec (Mikolov et al., 2013b) to help the skip-gram model to deal with the
difficulty of high computational complexity w.r.t. model training.
Specifically, NEG needs a noise distribution $P_{n}(\rm v)$ to generate $k$
negative samples for every positive one. $P_{n}(\rm v)$ can be arbitrarily
chosen, and more often it is empirically set by raising the frequency to the
$3/4$ power for the best quality of embeddings. The training loss of NEG is
formally defined as

(21)
$L=-\log\sigma({{\bf{v}}_{\rm{O}}}^{\rm{T}}\Phi({{\rm{v}}_{\rm{I}}}))-\sum\limits_{{{\rm{v}}_{\rm{j}}}\in{\rm{V}}_{neg}}{{E_{{{\rm{v}}_{\rm{j}}}\sim{P_{n({\rm{v}})}}}}\left[{\log\sigma(-{{\bf{v}}_{\rm{j}}}^{\rm{T}}\Phi({{\rm{v}}_{\rm{I}}}))}\right]},$

where ${\rm{V}}_{neg}$ is the set of negative samples and $\bf{v}_{O}$ is the
output vector of node $\rm v_{O}$ that corresponds to the column $\rm O$ of
matrix $\bf M$ in the skip-gram model. Then the training objective is
simplified to be able to discriminate the output node $\rm v_{O}$ from nodes
draws from $P_{n}(\rm v)$ using logistic regression. To update node embeddings
under NEG, the derivative of loss $L$ with regard to the input of output $\rm
v_{j}$ is given by

(22) $\frac{{\partial
L}}{{\partial{{\bf{v}}_{\rm{j}}}^{\rm{T}}\Phi({{\rm{v}}_{\rm{I}}})}}=\sigma({{\bf{v}}_{\rm{j}}}^{\rm{T}}\Phi({{\rm{v}}_{\rm{I}}}))-{s_{j}},$

where $s_{j}$ is a binary indicator of samples, i.e., $s_{j}=0$ if $\rm v_{j}$
is a negative sample, otherwise $s_{j}=1$. The output vector is updated by

(23)
${{\bf{v}}_{\rm{j}}}\leftarrow{{\bf{v}}_{\rm{j}}}-\eta\left({\sigma({{\bf{v}}_{\rm{j}}}^{\rm{T}}\Phi({{\rm{v}}_{\rm{I}}}))-{s_{j}}}\right)\Phi({{\rm{v}}_{\rm{I}}})$

By using NEG, we just need to update the output vectors of nodes from
${\\{{{\rm{v}}_{\rm{O}}}\\}\cup{\rm{V}}_{neg}}$ instead of the entire node set
$V$. The computational effort is therefore saved significantly. Finally, the
node vector is updated accordingly by the error backpropagation to the hidden
layer, i.e.,

(24)
$\Phi({{\rm{v}}_{\rm{I}}})\leftarrow\Phi({{\rm{v}}_{\rm{I}}})-\eta\sum\limits_{{{\rm{v}}_{\rm{O}}}\in
context({{\rm{v}}_{\rm{I}}})}{\sum\limits_{{{\rm{v}}_{\rm{j}}}\in\\{{{\rm{v}}_{\rm{O}}}\\}\cup{\rm{V}}neg}{\left({\sigma({{\bf{v}}_{\rm{j}}}^{\rm{T}}\Phi({{\rm{v}}_{\rm{I}}}))-{s_{j}}}\right){{\bf{v}}_{\rm{j}}}}}$

Table 5. Summary of optimization techniques Technique |  Working stage |  Technical principle |  Optimization goal | Publication
---|---|---|---|---
Hierarchical Softmax |  Node embedding |  Leverage a tree structure to minimize the computation of conditional probabilities |  Computational complexity reduction, acceleration of embedding process | (Morin and Bengio, 2005; Perozzi et al., 2014)
Negative Sampling |  Feature extraction |  Reduce the number of output vectors that need to be updated |  Computational complexity reduction, acceleration of embedding process | (Gutmann and Hyvärinen, 2012; Mikolov et al., 2013b)
Attention Mechanism |  (1) Feature extraction; (2) Node embedding |  (1) Replace previously fixed hyperparameters with trainable ones; (2) Distinguish neighborhood’s importance via trainable weights |  Enhancement of training efficiency and effectiveness | (Abu-El-Haija et al., 2018; Velickovic et al., 2018)

Attention Mechanism Ever since attention mechanism was proposed, it has become
an effective way to help models focus on the most important part of data. NRL
also benefits from attention mechanism by conducting attention-guided random
walks in feature extraction stage, and designing attention-based encoder in
node embedding stage.

In the stage of feature extraction, the attention mechanism (Abu-El-Haija et
al., 2018) is borrowed to lead random walk to optimize an upstream objective.
Let ${\bf{\Gamma}}$ be the transition matrix, ${{{\bf{\tilde{P}}}}^{(0)}}$ be
the initial positions matrix with ${{{\bf{\tilde{P}}}}_{\rm vv}^{(0)}}$ set to
the number of walks starting at node $\rm v$, and $C$ be the walk length, the
context distribution can be represented by a $C$-dimensional vector
$\bf{Q}=(Q_{1},Q_{2},...,Q_{C})$. To obtain the expectation on co-occurrence
matrix, $\mathbb{E}[\bf D]$, $\bf{Q}_{k}$ need to be assigned to
$\bf{\Gamma}^{k}$ as a co-efficient. An attention model is proposed to learn
$\bf Q$ automatically, where $\bf{Q}=\rm softmax((q_{1},q_{2},...,q_{C}))$,
and all $\rm{q}_{k}$ can be trained by backpropagation. The attention model
aims to guide the random surfer on ”where to attend to” as a function of
distance. To this end, the model on $\bf{\Gamma}^{\infty}$ is trained
according to the expectation on random walk matrix, i.e.,

(25)
$\mathbb{E}[{{\bf{D}}^{{\rm{softmax[}}\infty]}};{{\rm{q}}_{\rm{1}}},{{\rm{q}}_{\rm{2}}},...,{{\rm{q}}_{\infty}}]={{{\bf{\tilde{P}}}}^{(0)}}\mathop{\lim}\limits_{C\to\infty}\sum\limits_{\rm
k=1}^{C}{{\rm{softmax(}}{{\rm{q}}_{\rm{1}}},{{\rm{q}}_{\rm{2}}},...,{{\rm{q}}_{k}}{\rm{)}}{\bf{\Gamma}^{\rm
k}}}.$

For many random walk based methods like DeepWalk, they are special cases of
the above equation where $C$ is not infinite, $\bf Q$ are fixed apriori, i.e.,
${{\bf{Q}}_{\rm{k}}}=\left[{1-\frac{{{\rm{k}}-1}}{C}}\right]$.

In the stage of node embedding, the graph attention network (GAT) (Velickovic
et al., 2018) proposes to incorporate attention mechanism into a spatial GCN
for providing differentiated weights of neighborhoods. Specifically, GAT
defines a graph attention layer parametrized by a weight vector $\bf a$ and
builds a graph attention network by stacking the layers. The attention
function $\alpha(\cdot)$ is defined to measure the importance of neighbor $\rm
u$ to the central node $\rm v$,

(26)
${\alpha_{{\rm{vu}}}}=\frac{{\exp({\rm{LeakyReLU(}}{{\bf{a}}^{\rm{T}}}{\rm{[}}{\bf{W}}{{\bf{h}}_{\rm{v}}}{\rm{||}}{\bf{W}}{{\bf{h}}_{\rm{u}}}{\rm{])}})}}{{\sum\nolimits_{{\rm{w}}\in{{\rm{N}}_{\rm{v}}}}{\exp({\rm{LeakyReLU(}}{{\bf{a}}^{\rm{T}}}{\rm{[}}{\bf{W}}{{\bf{h}}_{\rm{v}}}{\rm{||}}{\bf{W}}{{\bf{h}}_{\rm{w}}}{\rm{])}})}}},$

where $\bf{h}_{v}$ refers to the feature of input node and $\bf W$ denotes the
weight matrix of a shared linear transformation which is applied to every
node. The convolution operation (aggregation encoder) is defined as

(27)
${\bf{h}}_{\rm{v}}^{\rm{t}}=\sigma\left({\sum\limits_{{\rm{u}}\in{{\rm{N}}_{\rm{v}}}}{\alpha({\bf{h}}_{\rm{v}}^{{\rm{t-1}}},{\bf{h}}_{\rm{u}}^{{\rm{t-1}}}){{\bf{W}}^{{\rm{t-1}}}}{\bf{h}}_{\rm{u}}^{{\rm{t-1}}}}}\right).$

##  4\. Recent Advances in Network Representation Learning

Here we review existing NRL studies with a focus on recent methods that have
achieved significant advances in machine learning and/or data mining. These
studies are classified into four categories and the detailed taxonomy is shown
in Fig. 4 which enables us to classify current NRL methods based on whether
the learning is: 1) performed in centralized or distributed fashion; 2) using
single network or multiple networks; 3) applied to static network or dynamic
evolving network. Besides, we also include some works on knowledge graph as
one of important extensions of NRL. We review these works according to the
proposed reference framework and present a brief summary as shown in Table 6.

Figure 4. A taxonomy of NRLs based on its evolution directions.

NRL category

###  4.1. Conventional NRL Methods

Methods in this category share some common features such as performing in a
centralized fashion, applying to only single network representation learning
and only learning from a static network. We introduce recent advances in this
category according to two main types of network properties, i.e., pairwise
proximity and community structure.

####  4.1.1. Pairwise Proximity

MVE (Qu et al., 2017) presents a multi-view embedding framework where pairs of
nodes with different views are sampled as instances. Each view corresponds to
a type of proximity between nodes, for example, the following-followee, reply,
retweet relationships in many social networks. These views are usually
complementary to each other. MVE uses skip-gram model to yield the view-
specific representations that preserve the first-order proximities encoded in
different views. Moreover, an attention-based voting scheme is proposed to
identify important views by learning different weights of views.

SDNE (Wang et al., 2016) presents a semi-supervised learning model to learn
node representations by capturing both local and global structure. The model
architecture is illustrated in Fig. 5 that consists of two components:
unsupervised component and supervised component. The former is designed to
learn node representations by preserving the second-order proximity and the
latter utilizes node connections as the supervised information to exploit the
first-order proximity and refine node representations. Specifically, given the
adjacency matrix ${\bf{A}}$, the first component utilizes a deep autoencoder
to reconstruct the neighborhood structure of each node. The encoder relies on
multiple non-linear functions to encode each node $\rm v_{i}$ into a vector
representation. The hidden representation in the $k$th layer is defined as

(28)
${\bf{y}}_{i}^{(k)}=\sigma({{\bf{W}}^{(k)}}{\bf{y}}_{i}^{(k-1)}+{{\bf{b}}^{(k)}}),$

where $\bf x_{i}$ is the input vector of $\rm v_{i}$,
${\bf{y}}_{i}^{(0)}={{\bf{x}}_{i}}$, $\bf W^{(k)}$ and $\bf b^{(k)}$ are
weights and biases respectively in the $k$th layer. The decoder reconstructs
the input vectors (e.g., ${\bf{\hat{x}}}_{i}$) from the most hidden vectors
(e.g., ${\bf{y}}_{i}^{(k)}$) by means of non-linear functions. Note that the
number of zero elements in ${\bf{A}}$ is far less than that of zero elements.
The autoencoder is prone to reconstruct the zero elements. To avoid this
situation, SDNE imposes more penalty to the reconstruction error of non-zero
elements and the loss function is defined as

(29)
${L_{2nd}}=\sum\limits_{i=1}^{n}{\left\|{({{{\bf{\hat{x}}}}_{i}}-{{\bf{x}}_{i}})\circ{{\bf{b}}_{i}}}\right\|_{2}^{2}},$

where $\circ$ denotes the Hadamard product. The second component enhances the
first-order proximity by borrowing the idea of Laplacian Eigenmaps to incur a
penalty once neighboring nodes are embedded far away. Consequently, the loss
function is defined as

(30)
${L_{1st}}=\sum\limits_{i,j=1}^{n}{{{\bf{A}}_{ij}}\left\|{({\bf{y}}_{i}^{(k)}-{\bf{y}}_{j}^{(k)})\circ{{\bf{b}}_{i}}}\right\|_{2}^{2}}.$

In addition, in order to avoid falling to local optima in the parameter space,
SDNE leverages deep belief network to pretrain the parameters at first.

Figure 5. The semi-supervised model of SDNE (adapted from Fig. 2 (Wang et al.,
2016)).

SDNE

DNGR (Cao et al., 2016) designs a deep denoising autoencoder method to capture
the non-linearities of network features. Its basic idea is to learn node
representations from the positive pointwise mutual information (PPMI) matrix
of nodes and their contexts. As illustrated in Fig. 6, DNGR consists of three
components: random surfing, calculation of PPMI and a stacked denoising
autoencoder (SDAE). In the first component, random surfing is used to generate
the probabilistic co-occurrence (PCO) matrix that corresponds to a transition
matrix by nature. Then the second component calculates the PPMI matrix based
on the PCO matrix by following (Bullinaria and Levy, 2007). After that, SDAE
is presented for highly non-linear abstractions learning. In order to recover
the complete matrix under certain assumptions, SDAE partially corrupt the
training sample $\bf x$ by randomly assigning some of $\bf x$’s entries to
zero with a certain probability. As a result, the objective becomes minimizing
the reconstruction loss, i.e.,

(31)
$\mathop{\min}\limits_{{\theta_{1}},{\theta_{2}}}\sum\limits_{i=1}^{n}{L({{\bf{x}}^{(i)}},{g_{{\theta_{2}}}}({f_{{\theta_{1}}}}({{{\bf{\tilde{x}}}}^{(i)}})))},$

where ${{f_{{\theta_{1}}}}}(\cdot)$ denotes an encoding function,
${{g_{{\theta_{2}}}}}(\cdot)$ denotes a decoding function, the $i$th instance
and its corrupted form are denoted by ${\bf x}^{(i)}$ and
${\bf{\tilde{x}}}^{(i)}$ respectively.

Struc2vec (Ribeiro et al., 2017) insists that node identity similarity should
be independent of network position and neighborhoods’ labels. To well preserve
the property, the input network $G$ is firstly preprocessed into a context
graph $M$ which is a multi-layer weighted graph described in Sec. 3.1.1. Then
a biased random walk process is conducted to produce node traveling sequences.
Each walker chooses its next step on the same layer or across different layers
and the choosing probabilities are proportional to edge weights, so that the
structurally similar nodes are more likely to be visited. After having
samples, Struc2vec uses skip-gram to train the learning model and hierarchical
softmax is leveraged to minimize the complexity.

####  4.1.2. Community Structure

MRF (Jin et al., 2019) proposes a structured pairwise Markov random field
framework. To ensure the global coherent community structure, MRF adopts the
Gibbs distribution to measure the posterior probability $P(C_{p}|\bf A)$ of
community partition $C_{p}$ given network adjacency matrix $\bf A$ and
maximize $P(C_{p}|\bf A)$ by optimizing a well-designed energy function
$E(C_{p};\bf A)$. $E(C_{p};\bf A)$ consists of two parts: a group of unary
potentials that are used to enforce node representations playing a dominant
role and a group of pairwise potentials that are used to fine-tune the
obtained unary potentials based on the connections of nodes. Besides, Gaussian
mixture model is utilized to approximate the probability distributions of all
nodes belonging to various communities.

To capture the overlapping community structure, Epasto et al. (Epasto and
Perozzi, 2019) propose a multi-embedding method, splitter, to learn multiple
vectors for each node, representing each one’s involvement in various
communities. In order to exploit the multi-community participation, splitter
preprocesses the original network into a persona graph $G_{p}$ (see Sec.
3.1.1) having multiple personas for every node. But the persona graph may
consists of many disconnected components that pose challenges for
representation learning. To address the challenge, splitter adds virtual edges
between each persona and its parent node in the original network so as to
enforce that every original node $\rm v_{o}$ can be predicted given its
arbitrary persona $\rm v_{i}$’s representation, i.e.,
$\Pr({{\rm{v}}_{\rm{o}}}|{\Phi_{{G_{p}}}}({{\rm{v}}_{\rm{i}}}))$. Like
DeepWalk, splitter uses skip-gram model coupled with hierarchical softmax to
learn node representations. By introducing a regularization parameter
$\lambda$, the optimization objective is formalized as follows:

(32)
$\mathop{\arg\min}\limits_{{\Phi_{{G_{p}}}}}-\log\Pr(\\{{{\rm{v}}_{{\rm{i-w}}}},...,{{\rm{v}}_{{\rm{i+w}}}}\\}\backslash{{\rm{v}}_{\rm{i}}}|{\Phi_{{G_{p}}}}({{\rm{v}}_{\rm{i}}}))-\lambda\Pr({{\rm{v}}_{\rm{o}}}|{\Phi_{{G_{p}}}}({{\rm{v}}_{\rm{i}}})).$

Figure 6. The framework of DNGR (adapted from Fig. 1 (Cao et al., 2016)).

DNGR

vGraph (Sun et al., 2019b) presents a probabilistic generative model where
each node $\rm v$ is viewed as a mixture of multiple communities and
represented by a multinomial distribution over communities $C$, i.e., $p(C|\rm
v)$, meanwhile each community $C$ can be represented by a distribution over
nodes, i.e., $p(\rm v|$$C)$. vGraph casts the edge generation process as an
inference problem. Specifically, for each node $\rm v$, vGraph first draws a
community assignment $C$ from $p(C|\rm v)$ and then generates an edge $\rm
e_{vu}$ by drawing another node $\rm u$ according to distribution $p(u|\rm
C)$. Both types of distributions are parameterized by the representations of
nodes and communities. Besides, a smoothness regularizer is borrowed by vGraph
to ensure the community memberships of neighborhoods to be similar.

###  4.2. Distributed NRL Methods

Considering the recent advances in GPU-enabled neural network training, Zhu et
al. (Zhu et al., 2019) propose a CPU-GPU hybrid system, GraphVite, which is a
hardware coupling system specifically designed for large-scale network
embedding. To leverage distinct advantages of CPUs and GPUs, GraphVite focuses
on the parallelization of instance sampling inside of feature extraction and
node embedding, and its overview is shown in Fig. 7. The random walk based
sampling procedure involves excessive random access and the random walks
initiated from different starting nodes are independent, so the positive
instance sampling is suitable for parallel execution on multiple CPUs. While
the node embedding procedure involves excessive matrix computation which is
the advantage of GPUs. Due to the limited GPU memory, it is impossible to
place all sampling instances and parameter matrices of node embeddings on a
GPU, GraphVite organizes a grid sample pool. The pool is divided into multiple
blocks and each one corresponds to a subset of the original network. The
training task is also divided into many subtasks and they are assigned with
varied blocks for training. Due to the sparse nature of networks, many block
pairs are gradient exchangeable, which means exchanging the order of gradient
descent steps does not result in a vector difference. As a result, subtasks on
different GPUs are capable of performing gradient updates currently in their
own subsets without any synchronization. At the same time, the sampling pool
is shared between CPUs and GPUs. In order to reduce the synchronization cost,
GraphVite presents a collaboration strategy which maintains two sample pools
in the main memory, so that CPUs fill up a pool and pass it to GPUs and they
always work on different pools in a parallel fashion. GraphVite reports about
50 times faster than the current fastest system and takes around 20 hours to
embed a network as large as 66 million nodes and 1.8 billion edges.

Figure 7. Overview of the CPU-GPU hybrid system (adapted from Fig. 1 (Zhu et
al., 2019)).

Graphvite

Figure 8. A block diagram of the modules used for PBG’s distributed mode
(adapted from Fig. 2 (Lerer et al., 2019)).

PBG

Lerer et al. (Lerer et al., 2019) also present a distributed embedding system,
PyTorch-BigGraph (PBG), which incorporates several modifications to
traditional embedding systems so as to allow it supports scale to multi-
entity, multi-relation graphs with billions of nodes and trillions of edges.
To implement parallelization, PBG partitions the adjacency matrix of original
graph into multiple buckets and feeds the edge samples from buckets
distributively. An example of the training of one bucket upon rank 2 is
illustrated in Fig. 8. The trainer requests a bucket from the lock server
residing on rank 1, where all partitions of that bucket are locked. Then the
trainer saves the no longer used partitions and loads new partitions that it
needs to and from the shared partition servers, at which point it drops its
old partitions left on the lock server. Edge samples are loaded from a shared
filesystem and the training is performed inside multi-thread with no inter-
thread synchronization required. In a single thread, only a small fraction of
shared parameters will be synchronized with a shared parameter server. Note
that checkpoints will be occasionally written back to the filesystem from
trainers. A distributed execution of PBG on 8 machines achieves 4x speedup and
reduces memory consumption by 88%.

###  4.3. Multi-NRL Methods

Compared to single network embedding, multiple networks may contain
complementary information and multi-network embedding can produce better
representations. Similar examples can be observed in many fields like social
networks, bioinformatics, etc. a node in one network may be associated with
multiple nodes in another network which forms a many-to-many mapping
relationship between networks. Ni et al. (Ni et al., 2018) propose a deep
multi-network embedding (DMNE) method, which coordinates different neural
networks with one co-regularized loss to manipulate cross-network
correlations. An example of DMNE for two networks is illustrated in Fig. 9,
where $\bf{A}^{(1)}$ and $\bf{A}^{(2)}$ are network contexts derived from the
two networks, $\bf{S}^{(12)}$ and $\bf{S}^{(21)}$ denote the cross-network
relationship matrix, and $(\bf{H}^{(i)})_{l}$ corresponds to the matrix of
representations for all nodes in the $l$th layer of network $i$. For single
network embedding say network $i$, the neural network consists of $L_{i}+1$
layers built in the autoencoder fashion, where half of hidden layers act as
encoders to learn node representations, while the others are decoders who are
in charge of the reconstruction of input. To achieve the network information
complementarity, DMNE relies on the intuition that a node’s representation
should be similar to the representation of its mapped node in another network,
and introduces the cross-network regularization based on two kinds of loss
functions: embedding disagreement (ED) loss function and proximity
disagreement (PD) loss function. The former is for situation that all networks
have an identical embedding dimension, while the latter is more flexible
without dimension constraint. As a result, the unified objective is
represented by

(33)
$\mathop{\arg\min}\limits_{{{\bf{\theta}}^{(i)}},{{\bf{U}}^{(i)}}}\sum\limits_{i=1}^{g}{L_{ae}^{(i)}}+\alpha\sum\limits_{(i,j)\in
I}^{g}{L_{R}^{(i)}}+\beta\sum\limits_{i=1}^{g}{\left\|{{{\bf{U}}^{(i)}}-{{\bf{H}}^{(i)}}}\right\|_{F}^{2}}$

where $\bf{U}^{(i)}$ denotes network $i$’s representation matrix,
$\bf{\theta}^{(i)}$ denotes the weight matrix, $L_{ae}^{(i)}$ refers to the
loss of network $i$, $L_{R}^{(ij)}$ can be either ED loss or PD loss, and
$\alpha$ and $\beta$ are trade-off factors.

TransLink (Zhou and Fan, 2019) models social network alignment as a link
prediction between different networks and aims to find out all pairs of user
accounts with same identities and connects them via anchor links. TransLink
embeds users and links between uses into a latent space by incorporating both
network structure and user interaction meta-path, and then iteratively predict
the potential anchor links between users who have similar representations over
translative operations. Du et al. (Du et al., 2019) investigate a joint
framework, CENALP that couples link prediction and network alignment together.
The newly predicted links enrich the network structure information, and new
potential nodes with richer features will have a greater chance to be
identified and vice versa. Therefore, link prediction and network alignment
are allowed to work in a mutually beneficial way. CENALP relies on a biased
random walk to generate samples across different networks. For each training
sample ($\rm v_{i},v_{j}$), CENALP adopts a product layer to decode the latent
interaction between two nodes and sets up a logistic regression layer for
prediction.

Figure 9. The DMNE framework for two networks (adapted from Fig. 2 (Ni et al.,
2018)).

DMNE

###  4.4. Dynamic NRL Methods

The methods introduced so far mainly focus on exploring NRL for static
networks. However, real-world networks like social networks and biological
networks are dynamically evolving over time, which means not all nodes are
available during the training. Inductive learning is an effective way to
support the representation learning for unseen nodes. As the first inductive
framework, GraphSage (Hamilton et al., 2017b) derives from the idea of Spatial
GCN where in order to generate node embeddings. It designs an aggregation
function to essentially assemble features from each node’s neighborhood, e.g.,
text attributes, node degrees. The aggregation encoder is defined as follows:

(34) ${\bf{h}}_{\rm{v}}^{\rm{k}}=\sigma({\bf{W}^{k}}\cdot
AGG_{k}({\bf{h}}_{\rm{v}}^{{\rm{k-1}}},\\{{\bf{h}}_{\rm{u}}^{{\rm{k-1}}},\forall{\rm{u}}\in{N_{\rm{v}}}\\})),$

where the function $AGG_{k}(\cdot,\cdot)$ should be symmetric so as to ensure
the framework can be trained and applied to neighborhood feature sets with
arbitrary order. GraphSage examines three types of functions, i.e., mean
aggregator, LSTM aggregator and pooling aggregator. Note that LSTM is not
inherently permutation invariant, so it is applied to a random permutation of
neighborhoods for implementation. The learning procedure of GraphSage is
illustrated by an example in Fig. 10. For each node to be embedded, GraphSage
first samples a fixed number of neighborhoods within $k$ hops, then obtains
the central node’s state by aggregating its neighborhoods’ features, and
finally makes predictions and backpropagate errors based on the node’s state.
In order to learn useful predictive representations, negative sampling is
introduced to enhance performance, and then a graph-based loss function is
given by

(35)
$L({{\bf{z}}_{\rm{u}}})=-\log(\sigma({\bf{z}}_{\rm{u}}^{\rm{T}}{{\bf{z}}_{\rm{v}}}))-Q\cdot{E_{{{\rm{v}}_{\rm{n}}}\sim{P_{n({\rm{v}})}}}}\left[{\log\sigma(-{\bf{z}}_{\rm{u}}^{\rm{T}}{{\bf{z}}_{\rm{n}}})}\right],$

where $\bf z_{u}$ denotes the representation of node $\rm v_{u}$, $Q$ denotes
the amount of negative samples and $P_{n}$ represents the negative sampling
distribution. As an inductive representation learning method, GraphSage
enforces that every representation $\rm v_{u}$ fed into the above function is
generated from the features of node $\rm u$’s neighborhoods rather than a
unique representation trained by an embedding look-up.

Figure 10. An example illustrating the three-step learning procedure of
GraphSage (adapted from Fig. 1 (Hamilton et al., 2017b)).

GraphSage introduction

Graph2Gauss (G2G) (Bojchevski and Günnemann, 2018) proposes a novel
unsupervised inductive learning method that embeds nodes in (un)directed
attributed graphs into Gaussian distributions rather than conventional vector
representations, so that it can capture the uncertainty of each node’s
embedding. G2G first uses a deep encoder to yield the parameters associated
with the node’s embedding distribution from the node attributes. The mean and
diagonal representations for a node are learned as functions of the node
attributes. After that, G2G optimizes a ranking loss function that
incorporates the ranking of nodes derived from the network structure. Given an
anchor node $\rm v$, nodes at distance 1 of $\rm v$ are closer than nodes at
distance 2, etc. Distance between node representations is measured by the
asymmetric KL divergence. The ranking loss is a square-exponential loss
proposed in energy based models. To avoid the situation that low-degree nodes
are less often updated, G2G presents a node-anchored sampling method. For each
node $\rm v$, the method randomly samples one other node from its
neighborhoods and then optimize over all the corresponding pairwise
constraints. To enable the inductive learning for unseen nodes, G2G passes the
attributes of these unseen nodes through the learned deep encoder.

To incorporate global structural information, SPINE (Guo et al., 2019)
proposes a structural identity preserved method. Rooted PageRank matrix
$\bf{S}^{RPR}$ is used as the indicator of pairwise proximity where
$\bf{S}_{i}^{RPR}$ represents $\rm v_{i}$’s global feature. As an inductive
method, the length of a node’s structural description should be independent of
the network size, so that the structural feature $\bf{T}_{i}$ of $\rm v_{i}$
is defined as the top-$k$ values of $\bf{S}_{i}^{RPR}$. Given the content
feature matrix $\bf{F}_{i}^{k}$ of $k$ nodes, node $\rm v_{i}$’s embedding is
generated by aggregating the $k$ vectors w.r.t. the corresponding weights in
$\bf T_{i}$. To encode the similarity in terms of both structural identities
and local proximities simultaneously, a biased positive sampling strategy is
proposed to collaborate with negative sampling.

Zhou et al. (Zhou et al., 2018) proposes a dynamic NRL method, DynamicTriad,
to preserve both structural information and evolution patterns during the
learning process. The evolution of a dynamic network is described by a series
of static network snapshots over discrete time. A triad of three nodes works
as the basic units of networks and its closure process is used to capture the
network dynamics. In specific, the triad closure process reflects how a closed
triad develops from an open triad over time by means of an evolutionary
probability, where a closed triad is a complete graph of three nodes while an
open triad misses a connection between any two nodes. For sampling,
considering the expensive computation on the combination of positive and
negative samples, DynamicTriad adopts an idea of sample corruption to generate
negative samples by replacing nodes in positive triad with varied nodes.
Besides, DynamicTriad enforces the evolutionary smoothness by minimizing the
distance of node representations in adjacent timestamps. In the dynamic
settings, nodes not seen at the current timestamp are regarded as out-of-
sample nodes and their embeddings can be inferred by exploring the idea of
inductive learning. To ensure the inferred embeddings preserve intricate
network properties, DepthLGP (Ma et al., 2018) designs a high-order Laplacian
Gaussian process (hLGP) to encode these properties, and employs a DNN to learn
a nonlinear transformation from the hLGP.

Figure 11. An illustration of evolution for representation learning. (a)
Association events (k=0); (b) Evolving representations; (c) Communication
events (k=1). (adapted from Fig. 1 (Trivedi et al., 2019))

DyRep

The above work assume that network dynamics evolve at a single time scale,
however, the evolution of real-world networks usually exhibit multiple time
scales. DyRep (Trivedi et al., 2019) uses two distinct dynamic processes to
model the dynamic evolution: association process describes dynamics of the
network, which brings structural changes caused by nodes and edges and results
in long-lasting information flow associated with them; and communication
process reflects dynamics on the network, which relates to the activities
between connected or non-connected nodes and results in temporary information
exchange across them. As shown in Fig. 11, the dynamic evolution of a network
is given by a stream of events that involve both processes. To model the
occurrence of event $p=(\rm u,v,t_{p},k)$ between $\rm u$ and $\rm v$ at time
$\rm t_{p}$, a conditional intensity function is defined based on the temporal
point process, i.e.,

(36)
$\lambda_{k}^{{\rm{u,v}}}(t_{p})={f_{k}}(g_{k}^{{\rm{u,v}}}(\bar{t}_{p})),$

where $\bar{t}_{p}$ is the timestamp before the current event, and
$f_{k}(\cdot)$ is a parameterized softplus function designed for capturing the
timescale dependence. Once an event $p$ occurred, the representation of each
involved node will be updated via a deep recurrent neural network (RNN), e.g.,
node $\rm v$’s representation $\bf{z}^{v}(t_{p})$ at current timestamp $t_{p}$
is updated by

(37)
${{\bf{z}}^{\rm{v}}}({t_{p}})=\sigma(\underbrace{{{\bf{W}}^{struct}}{\bf{h}}_{struct}^{\rm{u}}({{\bar{t}}_{p}})}_{{\rm{Localized\,embedding\,propagation}}}+\underbrace{{{\bf{W}}^{rec}}{{\bf{z}}^{\rm{v}}}(\bar{t}_{p}^{\rm{v}})}_{{\rm{Self-
propagation}}}+\underbrace{{{\bf{W}}^{t}}({t_{p}}-\bar{t}_{p}^{\rm{v}})}_{{\rm{Exogenous\,drive}}}),$

where ${\bf{h}}_{struct}^{\rm{u}}$ is the representation aggregated from node
$\rm u$’s neighborhoods, ${{{\bf{z}}^{\rm{v}}}(\bar{t}_{p}^{\rm{v}})}$ is the
recurrent state obtained from $\rm v$’s previous representation, and
${\bar{t}_{p}^{\rm{v}}}$ denotes the timestamp of $\rm v$’s previous event.
Parameter matrices ${{{\bf{W}}^{struct}}}$, ${{{\bf{W}}^{rec}}}$ and
${{{\bf{W}}^{t}}}$ are applied to control the aggregate effect of three
inputs. For a set of observed events, the learning objective is defined as
negative log likelihood. Specifically, DyRep borrows the idea of graph
attention networks (GAT) (Velickovic et al., 2018) that is the attention
mechanism applied to graph data, and uses it to endue neighborhoods with
varied attention coefficients that also evolve over time.

Figure 12. An illustration of SACN (adapted from Fig. 1 (Shang et al., 2019)).

SACN

###  4.5. Knowledge Graph Representation Learning

As a special type of networks, knowledge graph can be viewed a structured
representation of facts, denoted by a set of triples. Each triple consists of
two entities h, t and a relation r between them, e.g., (h, r, t). Knowledge
graph representation learning (KRL) is to map entity nodes and relation edges
into low-dimensional vectors while capturing their semantic meanings (Ji et
al., 2020). The primary goal of KRL is to improve the plausibility of facts
where the plausibility can be viewed as a specialization of network property.
Distance proximity is often used to enhance the plausibility of a fact by
minimizing the distance between entities of the corresponding triple. In the
classic translating embedding model (Bordes et al., [n.d.]), the relation r
corresponds to a translation from head entity to tail entity and their
embeddings $\bf{h+r}\approx t$ hold when (h, r, t) is a fact. RotatE (Sun et
al., 2019a) expands the embedding space from real-valued space to complex
space where entities and relations are mapped to low-dimensional complex
vectors and each relation corresponds to a rotation from head entity to tail
entity, i.e.,

(38) $\bf t\approx h\circ r,$

where $\circ$ denotes the Hadamard product. For each element in the embedding
space, $t_{i}\approx h_{i}\circ r_{i}$ and $|r_{i}|=1$. Element $r_{i}$ is of
the form $e^{i\theta_{r,i}}$, which corresponds to a counterclockwise rotation
by $\theta_{r,i}$ radians about the origin of the complex plane. For each
triple (h, r, t), its distance is defined as

(39) $d_{r}(\bf{h,t})=\left\|{\bf{h\circ r}}-t\right\|.$

The complex space allows RotatE to capture more relation patterns including
symmetry/antisymmetry, inversion and composition. During the training,
traditional negative sampling samples the negative triples in a uniform way,
which suffers the problem of inefficiency since many samples are obviously
false and cannot provide meaningful information. RotatE presents a variant
called self-adversarial negative sampling, which samples negative triples from
the following distribution

(40)
$p({h^{\prime}_{j}},r,{t^{\prime}_{j}}|\\{({h_{i}},{r_{i}},{t_{i}})\\})=\frac{{\exp\alpha{d_{r}}({\bf{h^{\prime}}}_{j},{\bf{t^{\prime}}}_{j})}}{{\sum\limits_{i}{\exp\alpha{d_{r}}({\bf{h^{\prime}}}_{i},{\bf{t^{\prime}}}_{i})}}},$

where $\alpha$ is the temperature of sampling. The above probability work as
the weight of the negative sample. The negative sampling loss is defined as

(41)
$L=-\log\sigma(\gamma-{d_{r}}({\bf{h,t}}))-\sum\limits_{i}{p({h^{\prime}_{i}},r,{t^{\prime}_{i}})\log\sigma({d_{r}}({\bf{h^{\prime}}}_{i},{\bf{t^{\prime}}}_{i})-\gamma)},$

where $\gamma$ is a fixed margin, $\sigma$ is the sigmoid function, and
$({h^{\prime}_{i}},r,{t^{\prime}_{i}})$ is the $i$th negative triple.

SACN (Shang et al., 2019) proposes an end-to-end structure-aware convolutional
network, SACN, to predict new triples for knowledge graph completion. As
illustrated in Fig. 12, SACN presents a weighted GCN as the encoder to learn
entities’s representations by aggregating connected entities as specified by
the relations in the knowledge graph, where the weighted GCN weights the
different types of relations differently by defining the interaction strength,
e.g., $\alpha_{t}$ denotes the strength of relation type $t$, so that the
amount of information from neighboring nodes used in aggregation can be
controlled. Let ${\bf{h}}_{i}^{l}$ be the input vector of node $\rm{v}_{i}$ in
the $l$th layer, its output vector is given by

(42)
${\bf{h}}_{i}^{l+1}=\sigma\left({\sum\limits_{{\rm{v}}_{j}\in{N_{i}}}{\alpha_{t}^{l}g({\bf{h}}_{i}^{l},{\bf{h}}_{j}^{l})}}\right),$

where $N_{i}$ is the neighbor set of node ${\rm{v}}_{i}$ and $g$ is the
aggregation function. With node embeddings as the input, the decoder aims to
represent the relations more accurately by recovering the original triples.
Based on ConvE (Dettmers et al., 2018), SACN develops Conv-TransE as the
decoder where the translation fashion of TransE is incorporated. Conv-TransE
aligns the convolutional outputs of both entity and relation embeddings with
all kernels and yields a matrix $\bf{M}(h,r)$. Both encoder and decoder are
jointly trained by minimizing the cross-entropy between $\bf{h+r}$ and $\bf t$
to preserve the distance proximity and the objective function is defined as

(43) $d_{r}({\bf{h,t}})=f(vec({\bf{M}(h,r)})\bf{W})\bf{t},$

where $f$ is a non-linear function and $W$ is a matrix for the linear
transformation. $vec(\bf M)$ corresponds to a reshaping operation that changes
feature map matrix to a vector.

Table 6. Summary of recent advances in NRL Category | NRL work |  Data preprocessing method, input data | Network feature extraction | Node embedding
---|---|---|---|---
|  Network property |  Sampling method |  Embedding model |  Optimization technique
Conventional NRL |  MVE (Qu et al., 2017) |  -, Adjacency matrix |  Multi-view first- order proximities |  Edge sampling |  Skip-gram model |  Attention mechanism, negative sampling
|  SDNE (Wang et al., 2016) |  Matrix-based processing, Adjacency matrix, Laplacian matrix |  1st, 2nd order proximity |  Fetch from adjacency matrix |  Deep autoencoder, Laplacian Eigenmaps |  Deep belief network
|  DNGR (Cao et al., 2016) |  Random surfing, PCO matrix |  High-order proximity |  Fetch from PPMI matrix |  SDAE |  Negative sampling
|  Struc2vec (Ribeiro et al., 2017) |  Graph decomposition, Context graph |  Node identity proximity |  Biased random walk |  Skip-gram model |  Hierarchical softmax
|  MRF (Jin et al., 2019) |  Matrix-based processing, Transition matrix |  Community structure |  Random pairwise sampling |  Markov random field |  Gaussian mixture model
|  splitter (Epasto and Perozzi, 2019) |  Graph decomposition, Persona graph |  Overlapping community structure |  Random walk |  Skip-gram model |  Hierarchical softmax
|  vGraph (Sun et al., 2019b) |  -, Adjacency matrix |  Community structure |  Edge sampling |  Probabilistic generative model |  Negative sampling
Distributed NRL |  GraphVite (Zhu et al., 2019) |  -, Adjacency matrix |  1st, 2nd order proximity |  Parallel random walk |  Edge probabilistic model |  Parallel negative sampling
|  PBG (Lerer et al., 2019) |  Graph decomposition, Multi-bucket |  1st-order proximity |  Distributed edge sampling |  Edge probabilistic model |  batched negative sampling
Multi-NRL |  DMNE (Ni et al., 2018) |  -, Adjacency matrix, cross-network relationship matrix |  High-order proximity under many-to-many mapping |  Random walk |  Deep autoencoder |  Negative sampling
|  TransLink (Zhou and Fan, 2019) |  Meta-path extraction, Meta-path, node state, edge state |  High-order proximity under translations |  Fetch from adjacency matrix |  Translating embedding |  Negative sampling
|  CENALP (Du et al., 2019) |  -, Adjacency matrix |  High-order proximity |  Biased random walk |  Skip-gram model |  Negative sampling
Dynamic NRL |  GraphSage (Hamilton et al., 2017b) |  Matrix-based processing, Transition matrix, node state |  2nd-order proximity |  Random walk |  Spatial GCN |  Negative sampling
|  Graph2Gauss (Bojchevski and Günnemann, 2018) |  -, Adjacency matrix, node state |  High-order proximity |  Node-anchored sampling |  Deep autoencoder |  Negative sampling
|  SPINE (Guo et al., 2019) |  Matrix-based processing, Rooted PageRank matrix, node state |  Node identity proximity |  Random walk |  Skip-gram model |  Biased positive sampling, Negative sampling
|  DynamicTriad (Zhou et al., 2018) |  -, Adjacency matrix |  1st-order proximity |  Edge sampling |  Edge probabilistic model |  Negative sampling base on corruption
|  DyRep (Trivedi et al., 2019) |  -, Adjacency matrix, node state, edge state |  2nd-order proximity |  Random walk |  GNN |  Graph attention network, negative sampling
KRL |  RotatE (Sun et al., 2019a) |  -, Adjacency matrix |  Distance proximity |  Fetch from adjacency matrix |  Translating embedding |  Self-adversarial negative sampling
|  SACN (Shang et al., 2019) |  -, Adjacency matrix, node state, edge state |  Distance proximity |  Fetch from adjacency matrix |  Weighted GCN |  Negative sampling

###  4.6. Discussions and Open Challenges

The past half-decade has witness the rapid development of NRL, meanwhile NRL
research also faces multiple challenges, among which we select some promising
challenges with high attention to discuss, hoping to provide useful guidance
for future study.

####  4.6.1. Automated Learning

We have shown that different NRL approaches tend to exhibit different
performances for different scenarios. There is no single method that is the
winner for all scenarios. When one method is considered to be better than
another, it typically depends on which benchmark is used, including tasks and
datasets available for evaluation. According to our framework, proper
combinations of candidate methods, models, and techniques at different stages
of NRL may have greater potential to boost the performance of NRL. For
example, Struc2vec (Ribeiro et al., 2017) preprocesses the input graph into a
context graph, generates samples via a biased random walk method and learns
representations by leveraging skip-gram model as well as negative sampling
technique to reflect features w.r.t. node identities. It ranks the second-best
model for node classification on Wikipedia (str, [n.d.]). Most of existing NRL
approaches follow the data-driven paradigm and is semi-automatic, i.e., given
a benchmark with the specified dataset, we have to decide 1) how the data
should be preprocessed? 2) what features should be preserved? 3) what models
and techniques can be used? 4) how to optimize the chosen model? It is not a
trivial task even for an expert to answer the above questions. Some recent
efforts on meta-learning (Hospedales et al., 2020) hold potential to partially
address these questions. The learning-to-learn mode allows meta-learning being
useful in multi-task scenarios where task-agnostic knowledge is learned from a
family of tasks and used to improve learning of new tasks from the same
family. AutoNE (Tu et al., 2019) presents an automatic hyperparameter
optimization, the principle behind which is transferring the knowledge
regarding optimized hyperparameters from multiple subnetworks to the original
network.

Nevertheless, implementing a fully automated learning of network
representation remains an open problem.

####  4.6.2. Proximity vs. Distinguishability

Observed from Table 6, we find that most of the current studies prefer to put
feature proximity preserving as the guideline to learn node representations,
so as to ensure structurally similar nodes having similar representations. As
a result, application tasks like node classification and social recommendation
benefit from this proximity-driven embedding. On the contrary, enhancing
proximity reduces the distinguishability of nodes at the same time.  Here the
distinguishability refers to that an arbitrary node is significantly different
from others in the representation space even though there is structural
proximity between nodes. The enforced proximity imposes adverse impacts on
some other application tasks. For example, in order to accurately identify
anchor users between different social networks, it is desirable to ensure that
each node’s representation should be explicitly separated from the
representations of its proximities. Otherwise, it would be hard to
discriminate the anchor nodes from their structurally similar neighborhoods.
Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) may provide a
possible way to enhance distinguishability, e.g., dNAME (Zhou et al., 2019)
presents a GAN mechanism to learn the latent space of single network combined
with a graph kernel based regularizer for discriminating anchor nodes from
others. GAN’s function depends on capturing true data distribution. How to
make use of GANs to finely distinguish each node meanwhile preserving
proximity is still open to exploring. GCNs (Bruna et al., 2014) generate node
representations by combining its own features with features aggregated from
its neighborhoods. A well-designed convolution operation can benefit the
trade-off between proximity and distinguishability. Nowadays, many real-world
networks can be classified as scale-free networks such as airline networks and
co-authorship networks. Scale-free networks follow power-law distributions and
the vast majority of network nodes have few neighbors, on the contrary, a tiny
fraction of network nodes have huge number of neighbors.  Can we design a
proper preprocessing method to deal with such extreme imbalance and to keep
the structural features of different nodes at the same time? The receptive
field for convolution largely depends on the adopted sampling method. How to
design a sampling method to collaborate with preprocessing method and
embedding models to handle this challenge still needs to be explored.

####  4.6.3. Interpretability

Compared with handcrafted feature engineering, the superiority of NRL research
has been empirically verified by both visualization and benchmarks, but less
studies on NRL can give theoretically satisfactory answers to the following
fundamental questions: 1) what exactly latent features are learned from the
network? 2) what contributes to good performance on visualization and
benchmarks? The connections between the underlying working mechanism and the
performance results have not been well revealed yet. NetMF (Qiu et al., 2018)
makes a good attempt to create intrinsic connections between four NRL methods
(e.g., DeepWalk (Perozzi et al., 2014), LINE (Tang et al., 2015b), PTE (Tang
et al., 2015a) and node2vec (Grover and Leskovec, 2016)) and graph Laplacian
by unifying them into the matrix factorization model.  Gogoglou et al.
(Gogoglou et al., 2019) try to explore the association of the embedding space
with both external and internal node categorization. Abductive learning (Dai
et al., 2019) provides another beneficial attempt by unifying machine learning
and logic programming, where the former learns to perceive primitive logic
facts from data while the latter is able to exploit symbolic domain knowledge
and correct the wrongly perceived facts for improving learning results
including interpretability. In short, to answer the above questions and ensure
that the learned representations truly reflect the network information, more
efforts need to be devoted to the interpretable learning in the future.

##  5\. Conclusions

We have presented a comprehensive overview of the state-of-the-art NRL
techniques through a unifying reference framework. We describe and compare
different NRL approaches in terms of the network data preprocessing methods,
the network feature learning models and the node embedding and optimization
techniques. We also discuss open challenges of NRL research, including
automated learning, trade-off between proximity and distinguishability and
interpretability. Our unified three phase reference framework offers a number
of unique benefits: (1) This framework presents a new perspective to reviewing
the state of the art NRL methods and technical optimizations employed. (2) The
unified framework promotes reviewing the state of the art NRL methods using
three progressive and complementary phases. This new approach provides an in-
depth understanding of network representation learning from three important
perspectives: (i) raw input preprocessing, (ii) the node feature extraction
task and different methods utilized for improving and optimizing node feature
extraction qualities, and (iii) network representation learning models. (3)
This unified three phase framework by design serves dual purposes: (i) help
beginner readers and practitioners to understand the end to end NRL workflow,
and (ii) help researchers and graduate students who are interested in learning
the state of the art NRL to gain a deeper understanding through reviewing each
of the three phases in the network representation learning workflow.

###### Acknowledgements.

The first author conducted this work during his one year visit at Georgia
Institute of Technology under Jiangsu Overseas Visiting Scholar Program for
University Prominent Young & Middle-aged Teachers and Presidents. The authors
from Soochow University acknowledge the support from National Natural Science
Foundation of China under Grants 61972272, 62172291, 62072321, U1905211 and
Open Project Program of the State Key Laboratory of Mathematical Engineering
and Advanced Computing under Grant 2019A04. The authors from Georgia Institute
of Technology acknowledge the partial support from the National Science
Foundation under Grants 2038029, 1564097 and an IBM faculty award.

## References

  * (1)
  * str ([n.d.]) [n.d.].  _Node Classification on Wikipedia_.  https://paperswithcode.com/sota/node-classification-on-wikipedia
  * Abu-El-Haija et al. (2017) Sami Abu-El-Haija, Bryan Perozzi, and Rami Al-Rfou. 2017\.  Learning Edge Representations via Low-Rank Asymmetric Projections. In _Proceedings of CIKM ’17_. 1787–1796.
  * Abu-El-Haija et al. (2018) Sami Abu-El-Haija, Bryan Perozzi, Rami Al-Rfou, and Alexander A. Alemi. 2018.  Watch Your Step: Learning Node Embeddings via Graph Attention. In _Proceedings of NeurIPS ’18_. 9198–9208.
  * Ahmed et al. (2018) Nesreen K. Ahmed, Ryan A. Rossi, John Boaz Lee, Xiangnan Kong, Theodore L. Willke, Rong Zhou, and Hoda Eldardiry. 2018.  Learning Role-based Graph Embeddings.  _CoRR_ abs/1802.02896 (2018).  arXiv:1802.02896 http://arxiv.org/abs/1802.02896
  * Bai et al. (2019) Yunsheng Bai, Hao Ding, Yang Qiao, Agustin Marinovic, Ken Gu, Ting Chen, Yizhou Sun, and Wei Wang. 2019\.  Unsupervised Inductive Graph-Level Representation Learning via Graph-Graph Proximity. In _Proceedings of IJCAI ’19_. 1988–1994.
  * Belkin and Niyogi (2001) Mikhail Belkin and Partha Niyogi. 2001.  Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering. In _Proceedings of NIPS ’01_. 585–591.
  * Belkin and Niyogi (2003) Mikhail Belkin and Partha Niyogi. 2003.  Laplacian Eigenmaps for Dimensionality Reduction and Data Representation.  _Neural Computation_ 15, 6 (2003), 1373–1396.
  * Bojchevski and Günnemann (2018) Aleksandar Bojchevski and Stephan Günnemann. 2018.  Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking. In _Proceedings of ICLR ’18_.
  * Bordes et al. (2014) Antoine Bordes, Sumit Chopra, and Jason Weston. 2014\.  Question Answering with Subgraph Embeddings. In _Proceedings of EMNLP ’14_. 615–620.
  * Bordes et al. ([n.d.]) Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. [n.d.].  Translating Embeddings for Modeling Multi-relational Data. In _Proceedings of NeurIPS ’13_. 2787–2795.
  * Bruna et al. (2014) Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2014.  Spectral Networks and Locally Connected Networks on Graphs. In _Proceedings of ICLR ’14_.
  * Bullinaria and Levy (2007) John A. Bullinaria and Joseph P. Levy. 2007.  Extracting semantic representations from word co-occurrence statistics.  _Behavior Research Methods_ 39, 3 (2007), 510–526.
  * Cai et al. (2018) HongYun Cai, Vincent W. Zheng, and Kevin Chen-Chuan Chang. 2018\.  A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications.  _IEEE Trans. Knowl. Data Eng._ 30, 9 (2018), 1616–1637.
  * Cao et al. (2015) Shaosheng Cao, Wei Lu, and Qiongkai Xu. 2015.  GraRep: Learning Graph Representations with Global Structural Information. In _Proceedings of CIKM ’15_. 891–900.
  * Cao et al. (2016) Shaosheng Cao, Wei Lu, and Qiongkai Xu. 2016.  Deep Neural Networks for Learning Graph Representations. In _Proceedings of AAAI ’16_. 1145–1152.
  * Cao et al. (2018) Zhu Cao, Linlin Wang, and Gerard de Melo. 2018.  Link Prediction via Subgraph Embedding-Based Convex Matrix Completion. In _Proceedings of AAAI ’18_. 2803–2810.
  * Cen et al. (2019) Yukuo Cen, Xu Zou, Jianwei Zhang, Hongxia Yang, Jingren Zhou, and Jie Tang. 2019\.  Representation Learning for Attributed Multiplex Heterogeneous Network. In _Proceedings of KDD ’19_. 1358–1368.
  * Chen et al. (2018a) Haochen Chen, Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2018a.  A Tutorial on Network Embeddings.  _CoRR_ abs/1808.02590 (2018).  arXiv:1808.02590 http://arxiv.org/abs/1808.02590
  * Chen et al. (2018b) Haochen Chen, Bryan Perozzi, Yifan Hu, and Steven Skiena. 2018b.  HARP: Hierarchical Representation Learning for Networks. In _Proceedings of AAAI ’18_. 2127–2134.
  * Cui et al. (2019) Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu. 2019\.  A Survey on Network Embedding.  _IEEE Trans. Knowl. Data Eng._ 31, 5 (2019), 833–852.
  * Dai et al. (2019) Wang-Zhou Dai, Qiu-Ling Xu, Yang Yu, and Zhi-Hua Zhou. 2019.  Bridging Machine Learning and Logical Reasoning by Abductive Learning. In _Proceedings of NeurIPS ’19_. 2811–2822.
  * Defferrard et al. (2016) Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016.  Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In _Proceedings of NeurIPS ’16_. 3837–3845.
  * Deng et al. (2020) Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang, and Zhuo Feng. 2020.  GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding. In _Proceedings of ICLR ’20_.
  * Dettmers et al. (2018) Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018.  Convolutional 2D Knowledge Graph Embeddings. In _Proceedings of AAAI ’18_. 1811–1818.
  * Donnat et al. (2018) Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovec. 2018.  Learning Structural Node Embeddings via Diffusion Wavelets. In _Proceedings of KDD ’18_. 1320–1329.
  * Du et al. (2019) Xingbo Du, Junchi Yan, and Hongyuan Zha. 2019.  Joint Link Prediction and Network Alignment via Cross-graph Embedding. In _Proceedings of IJCAI ’19_. 2251–2257.
  * Epasto and Perozzi (2019) Alessandro Epasto and Bryan Perozzi. 2019.  Is a Single Embedding Enough? Learning Node Representations that Capture Multiple Social Contexts. In _Proceedings of WWW ’19_. 394–404.
  * Fan et al. (2019) Wenqi Fan, Yao Ma, Qing Li, Yuan He, Yihong Eric Zhao, Jiliang Tang, and Dawei Yin. 2019.  Graph Neural Networks for Social Recommendation. In _Proceedings of WWW ’19_. 417–426.
  * Feng et al. (2018) Rui Feng, Yang Yang, Wenjie Hu, Fei Wu, and Yueting Zhang. 2018.  Representation Learning for Scale-Free Networks. In _Proceedings of AAAI ’18_. 282–289.
  * Fout et al. (2017) Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. 2017\.  Protein Interface Prediction using Graph Convolutional Networks. In _Proceedings of NeurIPS ’17_. 6530–6539.
  * Fu et al. (2020) Tianfan Fu, Cao Xiao, and Jimeng Sun. 2020.  CORE: Automatic Molecule Optimization Using Copy & Refine Strategy. In _Proceedings of AAAI ’20_. 638–645.
  * Gao et al. (2019) Zheng Gao, Gang Fu, Chunping Ouyang, Satoshi Tsutsui, Xiaozhong Liu, Jeremy J. Yang, Christopher Gessner, Brian Foote, David J. Wild, Ying Ding, and Qi Yu. 2019.  edge2vec: Representation learning using edge semantics for biomedical knowledge discovery.  _BMC Bioinform._ 20, 1 (2019), 306:1–306:15.
  * Gogoglou et al. (2019) Antonia Gogoglou, C. Bayan Bruss, and Keegan E. Hines. 2019\.  On the Interpretability and Evaluation of Graph Representation Learning.  _CoRR_ abs/1910.03081 (2019).
  * Golub and Reinsch (1970) G.H. Golub and C. Reinsch. 1970.  Singular value decomposition and least square solutions.  _Numer. Math._ 14, 5 (1970), 403–420.
  * Goodfellow et al. (2014) Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. 2014\.  Generative Adversarial Nets. In _Proceedings of NIPS ’14_. 2672–2680.
  * Grover and Leskovec (2016) Aditya Grover and Jure Leskovec. 2016.  node2vec: Scalable Feature Learning for Networks. In _Proceedings of KDD ’16_. 855–864.
  * Guo et al. (2019) Junliang Guo, Linli Xu, and Jingchang Liu. 2019.  SPINE: Structural Identity Preserved Inductive Network Embedding. In _Proceedings of IJCAI ’19_. 2399–2405.
  * Guo et al. (2018) Shu Guo, Quan Wang, Lihong Wang, Bin Wang, and Li Guo. 2018.  Knowledge Graph Embedding With Iterative Guidance From Soft Rules. In _Proceedings of AAAI ’18_. 4816–4823.
  * Gutmann and Hyvärinen (2012) Michael Gutmann and Aapo Hyvärinen. 2012.  Noise-Contrastive Estimation of Unnormalized Statistical Models, with Applications to Natural Image Statistics.  _J. Mach. Learn. Res._ 13 (2012), 307–361.
  * Hamilton et al. (2017a) William L. Hamilton, Rex Ying, and Jure Leskovec. 2017a.  Representation Learning on Graphs: Methods and Applications.  _IEEE Data Eng. Bull._ 40, 3 (2017), 52–74.