# Deep learning for dynamic graphs: models and benchmarks

Alessio Gravina∗ and Davide Bacciu ∗ Corresponding AuthorD. Bacciu and A.
Gravina are with the Department of Computer Science, University of Pisa,
Italy. (e-mail<EMAIL_ADDRESS>and<EMAIL_ADDRESS>
Preprint. Under review

###### Abstract

Recent progress in research on Deep Graph Networks (DGNs) has led to a
maturation of the domain of learning on graphs. Despite the growth of this
research field, there are still important challenges that are yet unsolved.
Specifically, there is an urge of making DGNs suitable for predictive tasks on
real-world systems of interconnected entities, which evolve over time.

With the aim of fostering research in the domain of dynamic graphs, at first,
we survey recent advantages in learning both temporal and spatial information,
providing a comprehensive overview of the current state-of-the-art in the
domain of representation learning for dynamic graphs. Secondly, we conduct a
fair performance comparison among the most popular proposed approaches,
leveraging rigorous model selection and assessment for all the methods, thus
establishing a sound baseline for evaluating new architectures and approaches.

###### Index Terms:

deep graph networks, graph neural networks, temporal graphs, dynamic graphs,
survey, benchmark

##  I Introduction

Graph representation learning has been gaining increasing attention over the
recent years promoted by the ubiquitousness and expressiveness of structured
relational information. Graphs are powerful tools to represent systems of
relations and interactions, across several application fields where deep
learning for graphs has found successful application, such as biology, social
science and human mobility [1, 2, 3, 4, 5, 6].

The key challenge when learning from graph data is how to numerically
represent the combinatorial structures for effective processing and prediction
by the model. A classical predictive task of molecule solubility prediction,
for instance, requires the model to encode both topological information and
chemical properties of atoms and bonds. Graph representation learning solves
the problem in a data-driven fashion, by learning a mapping function that
compresses the complex relational information of a graph into an information-
rich feature vector that reflects both structural and label information in the
original graph.

Despite the progress made in recent years in the field, which is mainly
related to the family of Deep Graph Networks (DGNs) [7, 8], a majority of the
literature works focuses on networks that are textitstatic snapshots of a
phenomenon. Indeed, this is often a limitation when considering real-world
processes, both natural and synthetic, where interactions evolve over time,
i.e., they are dynamic in nature. Examples of such time-evolving systems can
be found in social networks, where users can develop new friendships, citation
networks, which are constantly updated with new publications, and in an
e-commerce, where user behaviors change over time as well as their
interactions with items.

Representing a time-varying process through a static graph can be a reasonable
choice in those scenarios in which the temporal dynamic is extremely slow,
such as in a protein-protein interaction network. In general, however,
ignoring the temporal information can harm the final performance of the
predictor [9, 10, 11, 12]. Therefore, the community has begun to look into
dynamic graphs and into models that can process the temporal dimension of a
graph, as well as its spatial aspects. As a result, the last few years have
witnessed a surge of works on dynamic graphs, leading to a fragmented and
scattered literature with respect to model formalization, empirical setups and
performance benchmarks. This aspect very much motivated us to look into a
systematization of the literature which does not only look at surveying the
existing works, but also actively promotes the identification of shared
benchmarks and empirical protocols for the fair evaluation of dynamic graph
models.

The present survey has a three-fold contribution. First, we propose a coherent
formalization of the domain of representation learning for dynamic graphs,
unifying different definitions and formalism gathered from the literature.
Secondly, we provide a survey on representation learning for dynamic graphs
under our unified formalism. Finally, we provide the graph learning community
with a fair performance comparison among the most popular DGNs for dynamic
graphs, using a standardized and reproducible experimental environment111We
release openly the code at
https://github.com/gravins/dynamic_graph_benchmark.. Specifically, we
performed experiments with a rigorous model selection and assessment
framework, in which all models were compared using the same features, same
datasets and the same data splits. As a by-product of our work, we also
provide the community with a selection of datasets which we put forward as
good candidates for the benchmarking of future works produced by the
community.

Existing surveys on the topic of deep graph learning are [13, 14]. Our novel
contributions with respect to such works are: (i) a broader and more up-to-
date coverage of literature; (ii) a benchmark and an empirical comparison
between a broad range of methods; and (iii) a statistical overview of a
selected list of datasets in both discrete and continuous time setting.

The remainder of the paper is organized as follows: Section II briefly surveys
representation learning for static graphs, providing general definitions and
methods useful to define dynamic graph problems222The interested reader is
referred to [7, 8] for an in-depth analysis of the methods developed within
the scope of representation learning for static graphs.. Section III
formalizes representation learning for dynamic graphs, while Section IV and V
survey the related literature. Section VI describes our empirical evaluation
setting and provides an experimental comparison of most popular DGNs for
dynamic graphs.Section VII concludes the paper.

##  II Representation learning for static graphs

###  II-A Definitions and notations

A (static) graph is a tuple
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X},\mathbf{E})$ defined by the
nonempty set $\mathcal{V}$ of nodes (also referred to as vertices), and by the
set $\mathcal{E}$ of edges (also called links or arcs) [15]. Nodes represent
interacting entities, whereas edges denote connections between pairs of nodes.
Depending on edge type, a graph is undirected, when node pairs are unordered,
i.e., $\mathcal{E}\subseteq\\{\\{u,v\\}\,|\,u,v\in\mathcal{V}\\}$, or
directed, when the pairs are ordered, i.e.,
$\mathcal{E}\subseteq\\{(u,v)\,|\,u,v\in\mathcal{V}\\}$. The structural
information expressed by $\mathcal{E}$ can also be encoded into an adjacency
matrix $\mathbf{A}$, which is a square $|\mathcal{V}|\times|\mathcal{V}|$
matrix where each element $\mathbf{A}_{uv}\in\\{0,1\\}$ is $1$ if an edge
connects the nodes $u$ and $v$, and it is $0$ otherwise.

In many practical scenarios, nodes and edges are often enriched with
additional attributes. We represent node features (also known as node
representation or node embedding) as a matrix
$\mathbf{X}\in\mathbb{R}^{|\mathcal{V}|\times d_{n}}$, where $d_{n}$ is the
number of available features. The $u$-th row of $\mathbf{X}$ is denoted as
$\mathbf{x}_{v}$ and represents a single node’s features. Similarly, we
represent edge features as a matrix
$\mathbf{E}\in\mathbb{R}^{|\mathcal{E}|\times d_{e}}$, where $d_{e}$ is the
number of edge features, and we indicate edge features vectors as
$\mathbf{e}_{uv}$. Finally, we denote the neighborhood (or adjacency set) of a
node $u\in\mathcal{V}$ as the set
$\mathcal{N}_{u}=\\{v\in\mathcal{V}\mid\\{u,v\\}\in\mathcal{E}\\}$. A visual
representation of a directed and undirected graph and the neighborhood of a
node is shown in Figure 1.

(a)

(b)

(c)

Figure 1: (a) A directed graph. (b) An undirected graph. (c) The neighborhood
of node $u$.

###  II-B Overview of representation learning for static graphs

Representation learning for graphs has been pioneered by Graph Neural Network
(GNN) [16] and Neural Network for Graphs (NN4G) [17], which were the first to
provide learning models amenable also for cyclic and undirected graphs. The
GNN leverages a recursive approach, in which the state transition function
updates the node representation through a diffusion mechanism that takes into
consideration the current node and its neighborhood defined by the input
graph. This procedure continues until it reaches a stable equilibrium. On the
other hand, the NN4G leverages a feed-forward approach where node
representations are updated by composing representations from previous layers
in the architecture.

The original approaches by NN4G and GNN have been later extended and improved
throughout a variety of approaches which can be cast under the umbrella term
of (static) Deep Graph Networks (DGNs), for which there exist dedicated
surveys [7, 8]. Briefly, DGNs denote a family of approaches capable of
learning the functional dependencies in a graph through a layered approach,
where the single layers are often referred to as Graph Convolutional Layers
(GCLs). Each of these computes a transformation of node representations by
combining the previous node representations and their neighborhoods. We
visually represent this procedure in Figure 2. The transformations are often
referred to as graph convolutions, and they are realized either in the
spectral or spatial domain.

Figure 2: Visual representation of a DGN. Given the input graph, each GCL
$(\ell+1)$ computes the new representation of a node $u$ as a transformation
of $u$ and its neighbors representations at the previous layer, $\ell$.

####  II-B1 Spectral convolution

In this setting, graphs are processed and learned through a parameterization
in the spectral domain of their Laplacian matrices. Specifically, given a
filter $\mathbf{g}_{\theta}=diag(\theta)$ parametrized by
$\theta\in\mathbb{R}^{|\mathcal{V}|}$ and the graph signal
$\mathbf{x}\in\mathbb{R}^{|\mathcal{V}|}$ for a graph $\mathcal{G}$, we can
define the spectral graph convolution as a multiplication in the Fourier
domain:

$\mathbf{g}_{\theta}*\mathbf{x}=\mathbf{U}\mathbf{g}_{\theta}\mathbf{U}^{T}\mathbf{x}$
(1)

where $\mathbf{U}^{T}\mathbf{x}$ is the graph Fourier transform, and
$\mathbf{U}$ is the matrix of eigenvectors of the normalized graph Laplacian
$\mathbf{L}=\mathbf{I}-\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}=\mathbf{U}\Lambda\mathbf{U}^{T}$,
with $\Lambda$ the diagonal matrix of the eigenvalue of $\mathbf{L}$. In the
graph Laplacian, $\mathbf{I}$ indicates the identity matrix, $\mathbf{D}$ is
the diagonal node degree matrix, and $\mathbf{A}$ is the adjacency matrix of
$\mathcal{G}$. The approach in Equation 1 is severely limited by the
computational requirements associated the Laplacian decomposition and by the
spectral parameterization costs, which have motivated a whole body of followup
works [18, 19]. Among these, the Graph Convolutional Network (GCN) [19] is
certainly the most successful one. GCN leverages the degree-normalized
Laplacian introduced in [18], hence, the output of the GCN’s $(\ell+1)$-th
layer for a node $u$ is computed as

$\mathbf{x}^{\ell+1}_{u}=\mathbf{\Theta}_{0}\mathbf{x}_{u}^{\ell}+\mathbf{\Theta}_{1}\sum_{v\in\mathcal{N}_{u}}\frac{1}{\sqrt{\mathbf{deg}(v)\,\mathbf{deg}(u)}}\mathbf{x}^{\ell}_{v},$
(2)

where $\sigma$ is the activation function, while $\mathbf{deg}(v)$ and
$\mathbf{deg}(u)$ are, respectively, the degrees of nodes $v$ and $u$. With
such formulation, GCN requires $\mathcal{O}(|\mathcal{E}|)$ time.

####  II-B2 Spatial convolution

Spatial convolutions are typically framed in the Message Passing Neural
Network (MPNN) [1] framework, where the representation for a node $u$ at a
layer $\ell+1$ is computed as

$\mathbf{x}_{u}^{\ell+1}=\phi_{U}(\mathbf{x}_{u}^{\ell},\bigoplus_{v\in\mathcal{N}_{u}}\phi_{M}(\mathbf{x}_{u}^{\ell},\mathbf{x}_{v}^{\ell},\mathbf{e}_{uv}))$
(3)

where $\bigoplus$ is an aggregation invariant function, and $\phi_{U}$ and
$\phi_{M}$ are respectively the update and message functions. The message
function computes the message for each node, and then dispatches it among the
neighbors. The update function collects incoming messages and updates the node
state. A typical implementation of the MPNN use sum as $\bigoplus$ and
$\phi_{U}$ functions, and
$\phi_{M}(\mathbf{x}_{u}^{\ell},\mathbf{x}_{v}^{\ell},\mathbf{e}_{uv})=\mathrm{MLP}(e_{uv})\mathbf{x}_{v}^{\ell}$.

Depending on the definition of the update and message functions, it is
possible to derive a variety of DGNs. The Graph Attention Network (GAT) [20]
introduces an attention mechanism to learn neighbors’ influences computing
node representation as

$\mathbf{x}_{u}^{\ell+1}=\sigma\left(\sum_{v\in\mathcal{N}_{u}}\alpha_{uv}\mathbf{\Theta}\mathbf{x}_{v}^{\ell}\right)$
(4)

where $\alpha_{uv}$ is the classical softmax attention score between node $u$
and its neighbor $v$.

When graphs are large and dense, i.e., $|\mathcal{E}|=|\mathcal{V}|^{2}$, it
can be impractical to perform the convolution over the node’s neighborhood.
Neighborhood sampling has been proposed as a possible strategy to overcome
this limitation, i.e. by using only a random subset of neighbors to update
node representation. GraphSAGE [21] exploits this strategy to improve
efficiency and scale to large graphs. GraphSAGE updates the representation of
a node $u$ by fixing the subset of nodes treated as neighbors, and by
leveraging aggregation and concatenation operations:

$\mathbf{x}_{u}^{\ell+1}=\sigma(\mathbf{\Theta}\cdot[\mathbf{x}_{u}^{\ell}\,||\,\square(\\{\mathbf{x}_{v}^{\ell}\\}_{v\in\mathcal{N}_{S}(u)}])$
(5)

where $\mathcal{N}_{S}:\mathcal{V}\rightarrow\mathcal{V}$ is the function that
computes the fixed subset of neighbors for a node $u$, and $\square$ is am
aggregation function. Differently, ClusterGCN [22] samples a block of nodes
identified by a graph clustering algorithm to restrict the neighborhood
dimension.

The way models aggregate neighbors representations to compute node embeddings
affects the discriminative power of DGNs. Xu et al. [23] showed that most DGNs
are at most as powerful as 1-Weisfeiler-Lehman test [24]. In particular, Graph
Isomorphism Network (GIN) [23] has been proven to be as powerful as
1-Weisfeiler-Lehman test by computing node representations as

$\mathbf{x}_{u}^{\ell+1}=\mathrm{MLP}\left((1+\gamma)\mathbf{x}_{u}^{\ell}+\sum_{v\in\mathcal{N}_{u}}\mathbf{x}_{v}^{\ell}\right)$
(6)

with $\gamma$ as a learnable parameter or a fixed scalar.

More recently, advancements in the field of representation learning for graphs
have introduced new architectures that establish a connection between the
domains of DGNs and Ordinary Differential Equations (ODEs), with the primary
objective of optimizing various aspects of message passing. These new methods
exploit the intrinsic properties of ODEs to enhance the efficiency and
effectiveness of message passing within DGNs. By formulating the propagation
of information in graphs as an ODE system, these architectures effectively
tackle multiple challenges, such as preserving long-range dependencies [25],
reducing the computational complexity of message passing [26, 27], and
mitigating the over-smoothing phenomena [28, 29].

####  II-B3 Random walks

A different strategy to learn node embeddings including local and global
properties of the graph relies on random walks. A random walk is a random
sequence of edges which joins a sequence of nodes. Perozzi et al. [30]
proposed DeepWalk, a method that learns continuous node embedding by modeling
random walks as the equivalent of sentences. Specifically, the approach
samples multiple walks of a specified length for each node in the graph, and
then it leverages the SkipGram model [31] to update node representations based
on the walks, treating the walks as sentences and the node representations as
words within them.

Node2Vec [32] improves DeepWalk by exploiting biased random walks, i.e., we
can control the likelihood of revisiting a node in the walk (allowing the walk
to be more or less explorative) and bias the exploration of new nodes towards
a breath first or a depth first strategy.

##  III Representation learning for dynamic Graphs: Notation and Taxonomy

A dynamic graph is a tuple
$\mathcal{G}(t)=(\mathcal{V}(t),\mathcal{E}(t),\mathbf{X}(t),\mathbf{E}(t))$,
defined for $t\geq 0$. Differently from static graphs, all elements in the
tuple are functions of time $t$. Thus, $\mathcal{V}(t)$ provides the set of
nodes which are present in the graph at time $t$, and
$\mathcal{E}(t)\subseteq\\{\\{u,v\\}\,|\,u,v\in\mathcal{V}(t)\\}$ defines the
links between them. Analogously, $\mathbf{X}(t)$ and $\mathbf{E}(t)$ define
node states and edge attributes at time $t$. Although, $\mathcal{V}(t)$ can
theoretically change over time, in practice it is often considered fixed for
the ease of computation, which means that all the nodes that will appear in
the dynamic graph are known in advance. Hence, $\mathcal{V}(t)=\mathcal{V}$
for $t\geq 0$.

The way we observe a system of interacting entities plays a crucial role in
the definition of the corresponding dynamic graph. We can distinguish between
two distinct types: discrete-time dynamic graphs and continuous-time dynamic
graphs. Each of these representations gives rise to diverse architectures and
learning approaches.

A discrete-time dynamic graph (D-TDG) models an evolving system that is fully
observed at different timestamps. For such a reason, a D-TDG,
$\mathcal{G}=\\{\mathcal{G}_{t}\,|\,t\in[t_{0},t_{n}]\\}$, consists in a
sequence of static graphs (known as snapshots). Each snapshot,
$\mathcal{G}_{t}=(\mathcal{V}_{t},\mathcal{E}_{t},\mathbf{X}_{t},\mathbf{E}_{t})$,
provides a picture of the graph’s state at a particular time $t$. Each
snapshot maintains the notations and definitions outlined for static graphs
(see Section II-A). We note that if the set of nodes and edges are fixed over
time (i.e.,
$\mathcal{G}_{t}=(\mathcal{V},\mathcal{E},\mathbf{X}_{t},\mathbf{E}_{t})$),
then the dynamic graph is often referred to as spatio-temporal graph.

Commonly, D-TDG are captured at periodic intervals (e.g., hours, days, etc.)
Hence, considering $\Delta t>0$ the interval between observations and $t_{i}$
the current timestamp, the next observation is captured at
$t_{i+1}=t_{i}+\Delta t$. We present in Figure 3 a visual exemplification of a
D-TDG.

(a)

(b)

Figure 3: (a) A Discrete-Time Dynamic Graph defined over five timestamps and a
set of five interacting entities. (b) The evolution of a Continuous-Time
Dynamic Graph through the stream of events until the timestamp $t_{3}$.

A continuous-time dynamic graph (C-TDG) is a more general formulation of a
dynamic graph. Indeed, it models systems that are not fully observed over
time. In facts, only new events in the system are observed. Therefore, a C-TDG
is a stream of events (also known as observations)
$\mathcal{G}=\\{o_{t}\,|\,t\in[t_{0},t_{n}]\\}$. An event,
$o_{t}=(t,\,EventType,\,\\{u\\}_{u\in\mathcal{V}(t)})$, is a tuple containing
the timestamp, the event type, and the nodes involved. Since C-TDGs are
captured with fine-grain observations, they typically have irregular
timestamps. Without loss of generality, we can identify three types of event:

  * •

node-wise, i.e., a node is created or its features are updated;

  * •

interaction, i.e., a temporal edge is created;

  * •

deletion, i.e., a node or an edge is deleted.

Generally, the temporal neighborhood of a node $u$ at time $t$, consists of
all the historical neighbors of $u$, prior to current time $t$, i.e.,
$\mathcal{N}^{t}_{u}=\\{v\in\mathcal{V}(t)\,|\,(t_{i},\,interaction,\,u,v)\in\mathcal{G}\wedge
t_{i}<t\\}$.

We observe that at any time point $t$, we can obtain a snapshot of the C-TDG
by sequentially aggregating the events up to time $t$. Figure 3 shows visually
the temporal evolution of a C-TDG.

We now proceed by providing a survey of state-of-the-art approaches in the
domain of representation learning for dynamic graphs by means of the taxonomy
and definition introduced in this section.

##  IV Learning with Discrete-Time Dynamic Graphs

Given the sequential structure of D-TDGs, a natural choice for many methods
has been to extend Recurrent Neural Networks [33] to graph data. Indeed, most
of the models presented in the literature can be summarized as a combination
of static DGNs and RNNs. In particular, some approaches adopt a stacked
architecture, where DGNs and RNNs are used sequentially, enabling to
separately model spatial and temporal dynamics. Other approaches integrate the
DGN inside the RNN, allowing to jointly capture the temporal evolution and the
spatial dependencies in the graph. In the following, we review state-of-the-
art approaches for both spatio-temporal graphs and more general D-TDGs.

###  IV-A Spatio-temporal graphs

When dealing with spatio-temporal graphs, new methods are designed to solve
the problem of predicting the node states at the next step,
$\mathbf{X}_{t+1}$, given the history of states, $\mathbf{X}_{t}$. To do so,
different types of architectures have been proposed to effectively solve this
task.

####  IV-A1 Stacked architectures

Seo et al. [34] proposed Graph Convolutional Recurrent Network (GCRN), one of
the earliest deep learning models able to learn sequences of spatio-temporal
graphs. The authors proposed to stack a Chebyshev spectral convolution [18]
(Equation 2 shows the first-order approximation of this convolution) for graph
embedding computation and a Peephole-LSTM [35, 36] for sequence learning:

$\begin{split}\mathbf{X}^{\prime}_{t}&=\text{Cheb}(\mathbf{X}_{t},\mathcal{E},k,\mathbf{\Theta})\\\
\mathbf{H}_{t}&=\text{peephole-{lstm}}(\mathbf{X}^{\prime}_{t})\end{split}$
(7)

where $\text{Cheb}(\mathbf{X}_{t},\mathcal{E},k,\mathbf{\Theta})$ represents
Chebyshev spectral convolution (leveraging a polynomial of order $k$) computed
on the snapshot $\mathcal{G}_{t}$ parametrized by
$\mathbf{\Theta}\in\mathbb{R}^{k\times d_{h}\times d_{n}}$. Here, $d_{h}$ is
the new latent dimension of node states, and $\mathbf{H}_{t}$ is the hidden
state vector, which is equivalent to the node states at time $t+1$ (i.e.,
$\mathbf{X}_{t+1}$). To ease readability, in the following, we drop from the
equation the edge set, $\mathcal{E}$, and the polynomial degree, $k$, since
they are fixed for the whole snapshot sequence.

Equation 7 can be reformulated to define a more abstract definition of a
stacked architecture between a DGN and an RNN, i.e.,

$\begin{split}\mathbf{X}^{\prime}_{t}&=\text{{dgn}}(\mathbf{X}_{t},\mathbf{\Theta})\\\
\mathbf{H}_{t}&=\text{{rnn}}(\mathbf{X}^{\prime}_{t})\end{split}$ (8)

Li et al. [37] implement Equation 8 by leveraging the same spectral
convolution as GCRN and a Gated Recurrent Unit (GRU) [38] as RNN. Differently,
Zhao et al. [9] employed the first-order approximation of the Chebyshev
polynomials, which lead to the usage of a GCN to learn spatial features, and a
GRU [38] to extract temporal features. This results in:

$\begin{split}\mathbf{X}^{\prime}_{t}&=\text{{gcn}}(\mathbf{X}_{t})\\\
\mathbf{H}_{t}&=\text{{gru}}(\mathbf{X}^{\prime}_{t}).\end{split}$ (9)

A3TGCN [39] extends the implementation of Zhao et al. [9] with an attention
mechanism to re-weight the influence of historical node states, with the aim
of capturing more global information about the system.

####  IV-A2 Integrated architectures

In contrast to the aforementioned approaches, an alternative type of
architecture is the one of an integrated architecture, where the DGN is
incorporated into the RNN to simultaneously capture and integrate temporal
evolution and spatial dependencies within the graph. Seo et al. [34] proposed
a second version of GCRN that exploit this type of architecture, by embedding
the Chebyshev spectral convolution in the Peephole-LSTM. In this case, input,
forget, and output gates can be reformulated as

$\hat{h}=\sigma(\text{Cheb}(\mathbf{X}_{t},\mathbf{\Theta}_{x})+\text{Cheb}(\mathbf{H}_{t-1},\mathbf{\Theta}_{h})+\theta_{c}\odot
c_{t-1}),$ (10)

the rest of the LSTM is defined as usual. We note that $\odot$ denotes the
Hadamard product, $\sigma$ is the activation function, and $\hat{h}$ if the
output of a generic gate. The weights
$\mathbf{\Theta}_{h}\in\mathbb{R}^{k\times d_{h}\times d_{h}}$,
$\mathbf{\Theta}_{x}\in\mathbb{R}^{k\times d_{h}\times d_{n}}$,
$\theta_{c}\in\mathbb{R}^{d_{h}}$ are the parameters of the model. We observe
that (here and in the following) the bias term is omitted for the easy of
readability.

The Spatio-Temporal Graph Convolutional Network [40] composes several spatio-
temporal blocks to learn topological and dynamical features. Each block
consists of two sequential convolution layers and one graph convolution in
between. The temporal convolution layer contains a 1-D causal convolution
followed by a Gated Linear Unit [41], while the graph convolution is in the
spectral domain. Let’s consider $\mathrm{Conv}^{\mathcal{G}}$ the spectral
graph convolution, and $\mathrm{Conv}^{\mathcal{T}}_{1}$ and
$\mathrm{Conv}^{\mathcal{T}}_{2}$ the first and second temporal convolutions,
respectively. Thus, each spatio-temporal block can be formulated as

$\mathbf{H}_{t}=\mathrm{Conv}^{\mathcal{T}}_{2}\left(\,\mathrm{ReLU}(\,\mathrm{Conv}^{\mathcal{G}}(\,\mathrm{Conv}^{\mathcal{T}}_{1}(\mathbf{X}_{t})\,))\right).$
(11)

###  IV-B General D-TDGs

Different from spatio-temporal graphs, the topology of a general D-TDG can
evolve over time. In this case, the mere exploitation of the sole node states
can lead to poor performance, since the new topology leads to different
dynamics in the graph. In fact, the evolving topology is responsible for
different information flows in the graph over time. Thus, excluding the
evolution of the graph structure becomes a major limit of the method, leading
to inaccurate predictions.

Even in this case, we can categorize approaches for general D-TDGs depending
on the architectural design.

####  IV-B1 Integrated architectures

Chen et al. [42] proposed GC-LSTM an encoder-decoder model for link
prediction, assuming fixed the node set $\mathcal{V}(t)$. The encoder consists
of a GCN embedded in a standard LSTM. The GCN learns topological features of
the cell state $c$ and of the hidden state $h$, which are used to save long-
term relations and extract input information, respectively. The encoder takes
as input the sequence of adjacency matrices and returns an embedding that
encodes both temporal and spatial information. Thus, a generic gate in the
LSTM can be expressed as:

$\hat{h}_{t}=\sigma(\mathbf{\Theta}_{h}\mathbf{A}_{t}+\text{{gcn}}_{h}(\mathbf{H}_{t-1},\mathcal{E}_{t-1}))$
(12)

where $\mathbf{\Theta}_{h}\in\mathbb{R}^{|\mathcal{V}|\times d_{h}}$ is the
weight matrix, and $\mathbf{A}_{t}$ is the adjacency matrix at time $t$, as
usual. The decoder part of the model is a MLP that leverages the embedding
generated from the encoder to predict the probability of each edge in future
adjacency matrix $\mathbf{A}_{t+1}$.

A similar strategy, which integrates topological changes into the computation,
has also been employed by Li et al. [43]. Indeed, the authors proposed the so-
called LRGCN that embed a Relational-GCN [44] into a LSTM model. Different
from GC-LSTM, LRGCN exploits the directionality of the edges in accordance
with node features rather than the only stream of adjacency matrices, with the
aim of effective modeling of the temporal dynamics. In LRGCN the input,
forget, and output gates are computed as the result of the R-GCN model over
the input node representations and the node embeddings computed at the
previous step. The authors distinguish between four edge types to produce more
informed latent representation: intra-incoming, intra-outgoing, inter-
incoming, inter-outgoing. An inter-time relation corresponds to an arc
$\\{u,v\\}$ present at time $t-1$, while an intra-time relation is an arc
$\\{u,v\\}$ present at time $t$. To employ LRGCN in a path classification
task, the authors extend their model with a self-attentive path embedding
(SAPE). Given a path $P\in\mathbb{R}^{m\times d_{o}}$, where $m$ is the path
length and $d_{o}$ is the output dimension, SAPE first applies LSTM to capture
node dependency along the path sequence, i.e.,
$\Gamma=\mathrm{LSTM}(P)\,\in\mathbb{R}^{m\times d_{new}}$. Then, SAPE uses
the self-attentive mechanism to learn node importance and generate size-
invariant representation of the path, i.e.,

$S=\mathrm{softmax}(\mathrm{MLP}(\mathrm{tanh}(\mathrm{MLP}(\Gamma))))\,\in\mathbb{R}^{r\times
m}$ (13)

with $r$ an hyper-parameter. Lastly, the final path representation is obtained
by multiplying $S$ with $\Gamma$, i.e., $e=S\Gamma\,\in\mathbb{R}^{r\times
d_{new}}$.

####  IV-B2 Stacked architectures

Instead of integrating the DGN into the RNN, Panagopoulos et al. [45] stack an
LSTM on top of a MPNN, as previously proposed for spatio-temporal graphs.
Differently from those approaches, the authors leverage as input the new node
features as well as the new topology. Thus, the MPNN updates node
representations by exploiting the temporal neighborhoods in each snapshot. You
et al. [46] extend the MPNN-LSTM method by proposing the exploitation of
hierarchical node states. Thus, the authors propose to stack multiple DGN’s
layers and interleave them with the sequence encoder, e.g., the RNN, to better
exploit the temporal dynamic at each degree of computation. Thus, the node
state at each layer depends on both the node state from the previous layer and
the historical node state. More formally, the $\ell$-th layer of roland’s
framework is

$\begin{split}\tilde{\mathbf{H}}^{\ell}_{t}&=\text{{dgn}}^{\ell}(\tilde{\mathbf{H}}_{t}^{\ell-1})\\\
\mathbf{H}_{t}^{\ell}&=\text{{update}}(\tilde{\mathbf{H}}^{\ell}_{t},\mathbf{H}_{t}^{\ell-1}).\end{split}$
(14)

where update is the sequence encoder.

Contrarily from previous works, Cini et al. [47] propose to first embed the
history of the node time series into latent representations that encode the
temporal dynamic of the system. Such representations are then processed
leveraging multiple powers of a graph shift operator (e.g., graph laplacian or
adjacency matrix) to encode the spatial dynamic of the system. Specifically,
the authors propose to encode the temporal dynamic by means of an Echo State
Networks (ESNs) [48, 49], a randomized recurrent neural networks, to
efficiently compute node embedding and improve the scalability of DGNs for
D-TDGs.

With the same aim of speeding up the dynamic graph processing, Micheli and
Tortorella [50] propose DynGESN, an extension of the Graph Echo State Network
[51] to the temporal domain. Specifically, DynGESN updates the embedding for a
node $u$ at time $t$ as

$\mathbf{h}_{t}^{u}=(1-\gamma)\mathbf{h}_{t-1}^{u}+\gamma\text{tanh}\left(\mathbf{\Theta}_{i}\mathbf{h}^{u}_{t}+\sum_{v\in\mathcal{N}^{t}_{u}}\mathbf{\Theta}_{r}\mathbf{x}^{v}_{t-1}\right),$
(15)

with $0<\gamma\leq 1$ being a leakage constant, $\mathbf{\Theta}_{i}$ the
input weights, and $\mathbf{\Theta}_{r}$ the recurrent weights. Both input and
recurrent weights are randomly initialized.

####  IV-B3 Meta architectures

We refer to meta architectures as those methods that learn a function that
maps the evolution of the graph into the evolution of the parameters of the
employed DGN. This kind of architecture has been proposed by Pareja et al.
[52] to deal with those scenarios where nodes may frequently appear and
disappear. As observed by the authors, such dynamics can be challenging to
model with RNN-based models, since they have difficulties in learning these
irregular behaviors. In such situation, the authors proposed Evolving GCN
(E-GCN) to capture the dynamism of such graphs by using an RNN to evolve the
parameters of a GCN. Thus, only the RNN parameters are trained. The authors
considered two versions of their model, depending on whether graph structure
or node features play the more important role. The first treats the GCN
weights as the hidden state of a GRU to assign more significance to node
representations. The second computes the weights as the output of the LSTM
model, and it is more effective when the graph structure is important for the
task. Let’s consider $\mathrm{GRU}(\mathbf{X}_{t},\mathbf{\Theta}_{t-1})$ as
an extended version of a standard GRU model that exploits both the weight
matrix at time $t-1$, $\mathbf{\Theta}_{t-1}$, and the previous node
embedding, $\mathbf{H}_{t}$. The first E-GCN architecture can be formulated as

$\begin{split}\mathbf{\Theta}_{t}&=\mathrm{GRU}(\mathbf{X}_{t},\mathbf{\Theta}_{t-1})\\\
\mathbf{H}_{t}&=\mathrm{GCN}(\mathbf{X}_{t},\mathcal{E}_{t},\mathbf{\Theta}_{t})\end{split}$
(16)

while the second substitutes the GRU with an LSTM that takes as input only the
weight matrix at time $t-1$.

####  IV-B4 Autoencoder architectures

Taheri and Berger-Wolf [53] introduced DyGrAE, an autoencoder for D-TDGs.
Specifically, DyGrAE leverages the Gated Graph Neural Network (GGNN) [54] to
capture spatial information, and LSTM encoder-decoder architecture to capture
the dynamics of the network. GGNN is a DGN similar to the GNN introduced by
Scarselli et al., but with a fixed number of iterations. DyGrAE consists of
four components: a GGNN to learn the spatial dynamic; an RNN to propagate
temporal information; an encoder to project the graph evolution into a fixed-
size representation; and a decoder to reconstruct the structure of the dynamic
graph. At each time step, at first, DynGrAE computes the snapshot embedding as
the result of the average pooling on node embeddings at time $t$, i.e.,
$emb(\mathcal{G}_{t})=\mathrm{pool}_{avg}(\mathrm{GGNN}(\mathbf{X}_{t}))$.
Then, the LSTM encoder-decoder uses the graph embeddings to encode and
reconstruct the input graph sequence:

$\begin{split}\mathrm{encoder}:\,\mathbf{h}^{enc}_{t}&=\mathrm{LSTM}_{enc}(emb(\mathcal{G}_{t}),\mathbf{h}^{enc}_{t-1})\\\
\mathrm{decoder}:\,\mathbf{h}^{dec}_{t}&=\mathrm{LSTM}_{dec}(\bar{\mathbf{A}}_{t-1},\mathbf{h}^{dec}_{t-1})\end{split}$
(17)

where
$\bar{\mathbf{A}}_{t-1}=\mathrm{sigmoid}(\mathrm{MLP}(\mathbf{h}^{dec}_{t-1}))$
is the reconstructed adjacency matrix at time $t-1$. The decoder uses
$h^{enc}_{w}$ to initialize its first hidden state, if $w$ is window size. To
improve the performance, the authors introduced a temporal attention
mechanism, which forces the model to focus on the time steps with significant
impact. That mechanism causes the reformulation of the decoder as

$\mathbf{h}^{dec}_{t}=\mathrm{LSTM}_{dec}([\mathbf{h}_{t}^{*}||\bar{\mathbf{A}}_{t-1}],\mathbf{h}^{dec}_{t-1})$
(18)

where
$\mathbf{h}_{t}^{*}=\sum_{i=t-w}^{t-1}\bar{\alpha}_{t}^{i}\mathbf{h}_{i}^{enc}$
is the attention distribution, the attention weights
$\bar{\alpha}_{t}^{i}=\mathrm{softmax}(f(\mathbf{h}^{dec}_{t-1},\mathbf{h}^{enc}_{i}))$,
and $f$ is a function, e.g., dot product or MLP.

A different strategy has been proposed by Goyal et al. [55] that developed
DynGEM. Such method handles D-TDGs by varying the size of the autoencoder
network depending on a heuristic, which determines the number of hidden units
required for each snapshot. Such heuristic, named PropSize, ensures that each
pair of consecutive layers, $\ell$ and $\ell+1$, satisfy the condition:

$size(\ell+1)\geq\rho\cdot size(\ell)$ (19)

where $0<\rho<1$ is a hyper-parameter. This heuristic is applied to both
encoder and decoder separately. If the condition in Equation 19 is not
satisfied for each pair of layers, then the number of $(\ell+1)$’s hidden
units are increased. If PropSize is still unsatisfied between the penultimate
and ultimate layers, a new layer is added in between. At each time step $t$
and before any application of PropSize, DynGEM initializes model parameters
with those of the previous step $\mathbf{\Theta}_{t}=\mathbf{\Theta}_{t-1}$.
This results in a direct transfer of knowledge between adjacent time steps,
which guarantees a higher affinity between consecutive embeddings.

####  IV-B5 Random walk based architectures

Inspired by DeepWalk and Node2Vec, Bastas et al. [56] propose a random walk
approach for D-TDGs named Evolve2Vec. Given a sequence of graph snapshot,
Bastas et al. consider old interactions to contribute only in the propagation
of topological information, while they use more recent interactions to encode
the temporal dynamic. Thus, they proceed by aggregating old snapshots as a
unique static graph. Evolve2Vec starts random walks from all nodes with at
least one outgoing edge in the static graph, as discussed in Section II. Then,
in the temporal part, each walker move to a new neighbor if there is at least
an outgoing edge in the current snapshot, otherwise it remains in the current
node until an outgoing edge is added. Depending on how threshold between old
and new is set, we can interpolate between a fully static or fully dynamic
approach. After the computation of the random walks, node embeddings are
computed by feeding the walks into a skip-gram model, as usual.

##  V Learning with Continuous-Time Dynamic Graphs

In a scenario where the dynamic graph is observed only as new incoming events
in the system, the methods defined in Section IV are unsuitable. In fact,
approximating a C-TDG through a sequence of graph snapshots can introduce
noise and loss of temporal information, since snapshots are captured at a more
coarse level, with consequent performance deterioration. Moreover, the
previously discussed methods usually do not allow including the time elapsed
since the previous event. The majority of such methods update the embeddings
only when new events occur. However, depending on how long it passed since the
last event involving a node may result in the staleness of the embedding.
Intuitively, the embedding may change depending on the time elapsed since the
previous event. For such reasons, new techniques have been introduced to
handle C-TDGs. We classify literature approaches into four categories
depending on the architectural choices.

####  V-1 Integrated architectures

Kumar et al. [57] proposed JODIE, a method that learns embedding trajectories
to overcome the staleness problem. JODIE computes the projection of a node $u$
in a future timestamp $t$ as an element-wise Hadamard product of the temporal
attention vector with the previous node embedding,

$\hat{\mathbf{x}}_{u}(t)=(1+\mathbf{w})\odot\mathbf{x}_{u}(t^{-}_{u})$ (20)

where $(1+\mathbf{w})$ is the temporal attention vector,
$\mathbf{w}=\mathbf{\Theta}_{p}\Delta t$ is the context vector, and $\Delta
t=t-t^{-}_{u}$ is the time since the last event involving $u$. Thanks to the
projection, JODIE can predict more accurately future embeddings, thus new
events. Similar to other models, when an interaction event occurs between
nodes $u$ and $v$, JODIE computes the embeddings $\mathbf{x}_{u}$ and
$\mathbf{x}_{v}$ by leveraging two RNNs.

Trivedi et al. [11] proposed DyRep, a framework that update the representation
of a node as it appear in an event in the C-TDG. DyRep captures the
continuous-time dynamics leveraging a temporal point process approach. A
temporal point process is characterized by the conditional intensity function
that models the likelihood of an event to happen given the previous events.
DyRep considers only two event types: topological evolution (i.e., node/edge
creation/deletion), and node interaction (i.e., related to activity between
two nodes in the graphs). DyRep’s conditional intensity function, computed for
an event between nodes $u$ and $v$ at time $t$, is:

$\lambda_{uv}^{k}(t)=f_{k}(g^{k}_{uv}(t^{-}))$ (21)

where $k$ is the event type, $t^{-}$ is the previous timestamp in which an
event occur, and

$f_{k}(z)=\psi_{k}\log\left(1+\exp\left(\frac{z}{\psi_{k}}\right)\right)$ (22)

with $\psi_{k}$ a parameter to be learned. The inner function

$g^{k}_{uv}(t^{-})=\omega_{k}^{T}\cdot[\mathbf{x}_{u}(t^{-})||\mathbf{x}_{v}(t^{-})]$
(23)

is a function of node representations learned through a DGN, with
$\omega_{k}\in\mathbb{R}^{2|F|}$ the model parameters that learn time-scale
specific compatibility. Node embeddings computed by the DGN are updated as

$\mathbf{h}_{u}(t)=\sigma(\mathbf{\Theta}_{i}\mathbf{h}_{u}^{loc}(t^{-})+\mathbf{\Theta}_{r}\mathbf{h}_{u}(t^{-}_{u})+\mathbf{\Theta}_{e}(t-t^{-}_{u}))$
(24)

where $h_{u}^{loc}(t^{-})\in\mathbb{R}^{d_{h}}$ is the representation of the
aggregation of $u$’s direct neighbors, $t^{-}_{u}$ is the previous event
involving node $u$, and
$\mathbf{\Theta}_{i},\mathbf{\Theta}_{r}\in\mathbb{R}^{d_{h}\times d_{h}}$ and
$\mathbf{\Theta}_{e}\in\mathbb{R}^{d_{h}}$ are learnable parameters. In
Equation 24 the first addend propagates neighborhood information, the second
self-information, while the third considers the exogenous force that may
smoothly update node features during the interval time. To learn
$\mathbf{h}_{u}^{loc}(t^{-})$, DyRep uses an attention mechanism similar to
the one proposed in the GAT model by Veličković et al. [20]. In this case, the
attention coefficient is parametrized by
$\mathcal{S}\in\mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|}$, which is a
stochastic matrix denoting the likelihood of communication between each pair
of nodes. $\mathcal{S}$ is updated according to the conditional intensity
function. The aggregated neighborhood representation is

$\mathbf{h}_{u}^{loc}(t^{-})=\max(\\{\sigma(\alpha_{uv}(t)\cdot\mathbf{h}_{v}(t^{-}))\,|\,v\in\mathcal{N}_{u}^{t})\\}),$
(25)

with $\sigma$ the activation function and $\alpha_{uv}(t)$ the attention
factor, as usual.

####  V-2 Stacked architectures

In the case of sequential encoding of spatial and temporal information, Xu et
al. [12] introduce TGAT [12], a model that learns the parameters of a
continuous function that characterize the continuous-time stream. Similar to
GraphSAGE and GAT models, TGAT employs a local aggregator that takes as input
the temporal neighborhood and the timestamp and computes a time-aware
embedding of the target node by exploiting an attention mechanism. The
$\ell$-th layer of TGAT computes the temporal embedding of node $u$ at time
$t$ as

$\mathbf{h}^{\ell}_{u}(t)=\text{{mlp}}^{\ell}_{2}(\mathrm{ReLU}(\text{{mlp}}^{\ell}_{1}([\hat{\mathbf{h}}(t)||\mathbf{x}_{u}])))$
(26)

where $\hat{\mathbf{h}}(t)$ is the hidden neighborhood representation obtained
as

$\begin{split}\mathbf{q}(t)&=\left[\mathbf{Z}(t)\right]_{0}\mathbf{\Theta}_{q}\\\
\mathbf{K}(t)&=\left[\mathbf{Z}(t)\right]_{1:n}\mathbf{\Theta}_{K}\\\
\mathbf{V}(t)&=\left[\mathbf{Z}(t)\right]_{1:n}\mathbf{\Theta}_{V}\\\
\hat{\mathbf{h}}(t)&=\mathrm{attn}(\mathbf{q}(t),\mathbf{K}(t),\mathbf{V}(t))\end{split}$
(27)

where
$\mathbf{Z}(t)=\left[\mathbf{x}^{\ell-1}_{u}(t)||\Phi_{d}(0),...,\mathbf{x}^{\ell-1}_{v}(t)||\Phi_{d}(t-t_{v})],...\right]$
is the temporal feature matrix, with $v\in\mathcal{N}_{u}^{t}$ and $n$ the
size of $u$’s neighborhood; $\mathbf{q}(t)$, $\mathbf{K}(t)$, and
$\mathbf{V}(t)$ are the query, key and value projections of the matrix; and
$\mathrm{attn}$ is an attention mechanism similar to GAT. The dimensional
functional mapping $\Phi_{d}:t\rightarrow\mathbb{R}^{d_{h}}$ is defined as

$\Phi_{d}(t)=[\cos(\omega_{1}t)\sin(\omega_{1}t),...,\cos(\omega_{d}t)\sin(\omega_{d}t)]$
(28)

where $\omega_{i}$ are learnable parameters.

Differently, Ma et al. [58] proposed an approach, named StreamGNN, to learn
the node embedding evolution as new edges appear in the dynamic graph. Thus,
it is design to only deal with interaction events. StreamGNN is composed of
two main components: the update component, which is responsible for updating
the node representations of the source and destination nodes of the new link;
and the propagation component, which propagates the new event across the
direct neighborhood of the involved nodes. When a new event is observed, the
update component computes the representation of the event as the result of an
MLP on the node representation of both source and destination. Then, such
representation is updated by an LSTM to include historical information from
previous interactions. The amount of the past node history used by the LSTM is
inversely proportional to the time difference with the previous node
interaction. Then, the lastly computed node embeddings of source and target
nodes are merged with the output of the LSTM model. After these first steps,
the propagation component diffuse the computed representations across the
1-hop neighborhood by leveraging an attention mechanism and by filtering out
those neighbors which appear in an interaction before a predefined threshold.

Rossi et al. [10] extend previous concepts by proposing a general framework
composed of five core modules: memory, message function, message aggregator,
memory updater, and the embedding module. The memory at time $t$ is a matrix
$\mathbf{s}(t)$ that has the objective of representing the node’s history in a
vectorial format. For this purpose, it is updated after every event. The
message function has the role of encoding the event to update the memory
module. Given an interaction event involving nodes $u$ and $v$ at time $t$,
the message function computes two messages

$\begin{split}m_{u}(t)&=\mathrm{msg}_{src}(\mathbf{s}_{u}(t^{-}),\mathbf{s}_{v}(t^{-}),\Delta
t,\mathbf{e}_{uv}(t))\\\
m_{v}(t)&=\mathrm{msg}_{dst}(\mathbf{s}_{v}(t^{-}),\mathbf{s}_{u}(t^{-}),\Delta
t,\mathbf{e}_{uv}(t)),\end{split}$ (29)

where $\mathrm{msg}$ can be any learnable function, e.g., a MLP. In case of a
node event, it is sent a single message. The message aggregator is a mechanism
to aggregate messages computed at different timestamps. It can be a learnable
function, e.g., RNN, or not, e.g., message average or most recent message.
After every event involving a node $u$, the memory of the node is updated by
the memory updater as

$\mathbf{s}_{u}(t)=\mathrm{mem}(\bar{m}_{u}(t),\mathbf{s}_{u}(t^{-}))$ (30)

where $\bar{m}_{u}(t)$ represents the aggregated messages, and $\mathrm{mem}$
is an RNN. Lastly, the embedding module generates the representation for a
node $u$ at time $t$ by exploiting the information stored in the memory module
of the node itself and its neighborhood up to time $t$

$\mathbf{h}_{u}(t)=\sum_{v\in\mathcal{N}_{u}^{t}}f(\mathbf{s}_{u}(t),\mathbf{s}_{v}(t),\mathbf{x}_{u}(t),\mathbf{x}_{v}(t),\mathbf{e}_{uv})$
(31)

with $f$ a learnable function and $\mathbf{x}_{u}(t)$, $\mathbf{x}_{v}(t)$ the
input node representations of nodes $u$ and $v$.

####  V-3 Random walk based architectures

Even in the scenario of C-TDGs, it is possible to compute node embeddings
relying on random walks. Differently from a standard random walk, in the
continuous-time domain a valid walk is a sequence of interaction events with a
non-decreasing timestamp. Nguyen et al. [59] extended the Node2Vec framework
to exploit temporal random walks. Once decided the starting timestamp $t_{0}$,
which is used to temporally bias the walk, the framework samples new nodes for
the walk by considering the temporal neighborhood. Differently from the
general formulation of temporal neighborhood, Nguyen et al. apply a threshold
to discriminate and filter old neighbors. The distribution to sample nodes in
the walk can be either uniform, i.e., $\mathbb{P}(v)=1/|\mathcal{N}^{t}_{u}|$,
or biased. Specifically, the authors proposed two ways to obtain a temporally
weighted distribution. Let consider that the random walk is currently at the
node $u$. In the first case, a node $v$ is sampled with the probability

$\mathbb{P}(v)=\frac{\exp(\mathcal{T}(v)-\mathcal{T}(u))}{\sum_{v^{\prime}\in\mathcal{N}^{t}_{u}}\exp(\mathcal{T}(v^{\prime})-\mathcal{T}(u))},$
(32)

where $\mathcal{T}:\mathcal{V}\rightarrow\mathbb{R}^{+}$ is the function that
given a node return the corresponding timestamp of the event in which the node
was involved; while in the second

$\mathbb{P}(v)=\frac{\delta(v,\mathcal{T}(v))}{\sum_{v^{\prime}\in\mathcal{N}^{t}_{u}}\delta(v^{\prime},\mathcal{T}(v^{\prime}))},$
(33)

where $\delta:\mathcal{V}\times\mathbb{R}^{+}\rightarrow\mathbb{Z}^{+}$ is a
function that sorts temporal neighbors in descending order.

Instead of temporal random walks, Wang et al. [60] exploited Causal Anonymous
Walks (CAW) to model C-TDGs. A CAW encodes the causality of network dynamics
by starting from an edge of interest and backtracking adjacent edges over
time. Moreover, a CAW is anonymous because it replaces node identities in a
walk with relative identities based on the appearance order. The causality
extraction helps the identification of temporal network motif, while node
anonymization guarantees inductive learning. Given an edge $\\{u,v\\}$, the
model extracts $M$ walks of length $m$ starting from both $u$ and $v$, and
then performs the anonymization step. Afterward, an RNN encodes each walks
leveraging two functions. The first consists of two MLPs ingested with the
encoding of the correlation between the node $w$ and the sampled walks

$f_{1}(w)=\mathrm{MLP}(g(w,S_{u}))+\mathrm{MLP}(g(w,S_{v}))$ (34)

where $S_{u}$ is the set of sampled walks started from $u$, and $g$ is the
function that counts the times a node $w$ appears at certain positions in
$S_{u}$. The second function encodes time as Equation 28. All the encoded
walks are aggregated through mean-pooling or the combination of self-attention
and mean-pooling to obtain the final edge representation.

####  V-4 Hybrid architectures

Souza et al. [61] propose to improve the expressive power of methods designed
for C-TDGs by leveraging the strengths of both CAW and TGN-based
architectures. Thus, by providing a hybrid architecture. Specifically, the
authors observe that for TGN-based architectures, most expressive power is
achieved by employing injective embedding module, message aggregator and
memory updater functions. On the other hand, the main advantage of CAW is its
ability to leverage node identities to compute representative embeddings and
capture correlation between walks. However, such approach imposes that walks
have timestamps in decreasing order, which can limit its ability to
distinguish events. Under such circumstances, the authors propose PINT, an
architecture that leverages injective temporal message passing and relative
positional features to improve the expressive power of the method.
Specifically, the embedding module computes the representation of node $u$ at
time $t$ and layer $\ell$ as

$\begin{split}\hat{\mathbf{h}}^{\ell}_{u}(t)&=\sum_{v\in\mathcal{N}_{u}^{t}}\text{{mlp}}^{\ell}_{agg}(\mathbf{h}^{\ell-1}_{v}(t)||\mathbf{e}_{uv})\alpha^{-\beta(t-t^{-})}\\\
\mathbf{h}^{\ell}_{u}(t)&=\text{{mlp}}^{\ell}_{upd}(\mathbf{h}^{\ell-1}_{u}(t)||\hat{\mathbf{h}}^{\ell}_{u}(t))\end{split}$
(35)

where $\alpha$ and $\beta$ are scalar hyper-parameters the node state is
initialized with its memory representation, i.e.,
$\mathbf{h}^{0}_{u}(t)=\mathbf{s}_{u}(t)$. To boost the power of PINT, the
authors augment memory states with relative positional features, which include
information about the number of existing temporal walks of a given length
between two nodes.

##  VI The benchmark problem

In this section, we provide the graph learning community with a performance
comparison among the most popular DGNs for dynamic graphs. The aim is to
support the tracking of the progress of the state-of-the-art and to provide
robust baseline performance for future works. To the best of our knowledge, in
fact, there are no widely agreed standard benchmarks in the domain of dynamic
graphs. For such a reason, nowadays, it is not easy to fairly compare models
presented in different works, because they typically use different data and
empirical settings. The latter plays a crucial role in the definition of a
fair and rigorous comparison, e.g., including multiple random weights
initialization and hyper-parameter search and similar data splits.

With this in mind, we designed three benchmarks to assess models that deal
with spatio-temopral graphs, general D-TDGs, and C-TDGs. To do so, we extended
the library PyDGN333https://github.com/diningphil/PyDGN to the D-TDG learning
setting to foster reproducibility and robustness of results. With the same
aim, we developed a Pytorch Geometric [62] based framework to allow
reproducible results in the continuous scenario. Lastly, in Table I we provide
the community with a selection of datasets useful for benchmarking future
works. An interest reader is referred to SNAP [63], TSL [64], and Network
Repository [65] for a broader data collections.

TABLE I: A selected list of datasets used in dynamic graphs representation learning field. The “$\mathcal{C}$” in the type column means C-TDG, “$\mathcal{D}$” corresponds to D-TDG, and “$\mathcal{ST}$” to spatio-temporal graph. Name | #Nodes | #Edges | Seq. len. |  Snapshot sizes (nodes/edges) | Granularity | Type | Link
---|---|---|---|---|---|---|---
Autonomous systems | 7,716 | 13,895 | 733 | 103-6,474 / 243-13,233 | daily | $\mathcal{D}$ | http://snap.stanford.edu/data/as-733.html
Bitcoin-$\alpha$ | 3,783 | 24,186 | 24,186 | $-$ | seconds | $\mathcal{C}$ | http://snap.stanford.edu/data/soc-sign-bitcoin-alpha.html
Bitcoin-OTC | 5,881 | 35,592 | 35,592 | $-$ | seconds | $\mathcal{C}$ | http://snap.stanford.edu/data/soc-sign-bitcoin-otc.html
CONTACT | 274 | 2,712 | 28,244 | $-$ | $-$ | $\mathcal{C}$ | https://networkrepository.com/ia-contact.php
ENRON | 151 | 2,227 | 50,572 | $-$ | unix timestamp | $\mathcal{C}$ | https://networkrepository.com/ia-enron-employees.php
Elliptic | 203,769 | 234,355 | 49 | 1,552-12,856 / 1,168-9,164 | 49 steps | $\mathcal{D}$ | https://www.kaggle.com/ellipticco/elliptic-data-set
FB-Forum | 899 | 7,089 | 33,700 | $-$ | $-$ | $\mathcal{C}$ | https://networkrepository.com/fb-forum.php
FB-Covid19 |  152(ENG) 104(ITA) 95(FRA) 53(ESP) |  2,347(ENG) 771(ITA) 864(FRA) 145(ESP) |  61(ENG) 105(ITA) 78(FRA) 122(ESP) |  152 / 2,347(ENG) 104 / 771(ITA) 95 / 864(FRA) 53 / 145(ESP) | daily | $\mathcal{D}$ | https://github.com/geopanag/pandemic_tgnn
Github | 284 | 1,420 | 20,726 | $-$ | $-$ | $\mathcal{C}$ | https://github.com/uoguelph-mlrg/LDG
HEP-TH | 27,770 | 352,807 | 3487 | 1-650 / 0-688 | montly | $\mathcal{D}$ | https://snap.stanford.edu/data/cit-HepTh.html
HYPERTEXT09 | 113 | 2,498 | 20,819 | $-$ | seconds | $\mathcal{C}$ | https://networkrepository.com/ia-contacts-hypertext2009.php
IA-Email-EU | 986 | 24,929 | 332,334 | $-$ | seconds | $\mathcal{C}$ | https://snap.stanford.edu/data/email-Eu-core-temporal.html
LastFM | 2,000 | 154,993 | 1,293,103 | $-$ | unix timestamp | $\mathcal{C}$ | http://snap.stanford.edu/jodie/lastfm.csv
Los-loop | 207 | 2,833 | 2,017 | 207 / 2,833 | 5 mins | $\mathcal{ST}$ | https://github.com/lehaifeng/T-GCN/tree/master/data
METR-LA | 207 | 1,515 | 34,272 | 207 / 1515 | 5 mins | $\mathcal{ST}$ | https://github.com/liyaguang/DCRNN
Montevideo | 675 | 690 | 740 | 675 / 690 | hourly | $\mathcal{ST}$ | https://pytorch-geometric-temporal.readthedocs.io/en/latest/modules/dataset.html
MOOC | 7,144 | 411,749 | 178,443 | $-$ | unix timestamp | $\mathcal{C}$ | http://snap.stanford.edu/data/act-mooc.html
PeMS03 | 358 | 442 | 26208 | 358 / 442 | 5 mins | $\mathcal{ST}$ | https://torch-spatiotemporal.readthedocs.io/en/latest/modules/datasets.html
PeMS04 | 307 | 209 | 16992 | 307 / 209 | 5 mins | $\mathcal{ST}$ | https://torch-spatiotemporal.readthedocs.io/en/latest/modules/datasets.html
PeMS07 | 883 | 790 | 28225 | 883 / 790 | 5 mins | $\mathcal{ST}$ | https://torch-spatiotemporal.readthedocs.io/en/latest/modules/datasets.html
PeMS08 | 170 | 137 | 17856 | 170 / 137 | 5 mins | $\mathcal{ST}$ | https://torch-spatiotemporal.readthedocs.io/en/latest/modules/datasets.html
PeMSBay | 325 | 2,369 | 52,116 | 325 / 2,369 | 5 mins | $\mathcal{ST}$ | https://github.com/liyaguang/DCRNN
PeMSD7 | 228 | 19,118 | 1,989 | 228 / 19,118 | 5 mins | $\mathcal{ST}$ | https://github.com/hazdzz/STGCN/tree/main/data/pemsd7-m
RADOSLAW | 167 | 5,509 | 82,927 | $-$ | seconds | $\mathcal{C}$ | https://networkrepository.com/ia-radoslaw-email.php
Reddit | 11,000 | 78,516 | 672,447 | $-$ | unix timestamp | $\mathcal{C}$ | http://snap.stanford.edu/jodie/reddit.csv
Reddit Hyperlink Network | 55,863 | 339,643 | 858,490 | $-$ | seconds | $\mathcal{C}$ | http://snap.stanford.edu/data/soc-RedditHyperlinks.html
SBM-synthetic | 1,000 | 130,415 | 50 | 1000 / 93,835-105,358 | 50 steps | $\mathcal{D}$ | https://github.com/IBM/EvolveGCN/tree/master/data
SOC-Wiki-Elec | 7,118 | 103,673 | 107,071 | $-$ | $-$ | $\mathcal{C}$ | https://networkrepository.com/soc-wiki-elec.php
SZ-taxi | 156 | 532 | 2,977 | 156 / 532 | 15 mins | $\mathcal{ST}$ | https://github.com/lehaifeng/T-GCN/tree/master/data
Traffic | 4,438 | 8,996 | 2,160 | 4,438 / 8,996 | hourly | $\mathcal{ST}$ | https://github.com/chocolates/Predicting-Path-Failure-In-Time-Evolving-Graphs
Twitter-Tennis | 1000 | 40,839 | 120 | 1000 / 41-936 | hourly | $\mathcal{D}$ | https://pytorch-geometric-temporal.readthedocs.io/en/latest/modules/dataset.html
UCI messages | 1,899 | 20,296 | 59,835 | $-$ | unix timestamp | $\mathcal{C}$ | https://snap.stanford.edu/data/CollegeMsg.html
Wikipedia | 9,227 | 18,257 | 157,474 | $-$ | unix timestamp | $\mathcal{C}$ | http://snap.stanford.edu/jodie/wikipedia.csv

###  VI-A Spatio-temopral graph benchmark

In the spatio-temporal setting, we consider three graph datasets for traffic
forecasting, i.e., Metr-LA [37], Montevideo [66], and PeMSBay [37].
Specifically,

  * •

Metr-LA consists of four months of traffic readings collected from 207 loop
detectors in the highway of Los Angeles County every five minutes;

  * •

Montevideo comprises one month of hourly passenger inflow at stop level for
eleven bus lines from the city of Montevideo;

  * •

PeMSBay contains six months of traffic readings collected by California
Transportation Agencies (CalTrans) Performance Measurement System (PeMS) every
five minutes by 325 traffic sensors in San Francisco Bay Area.

For all the three datasets, the objective is to perform temporal node
regression, thus, to predict the future node values, $\mathbf{X}_{t+1}$, given
the past graph history, $[\mathcal{G}_{i}]_{i=1}^{t}$.

The baseline performance for this type of predictive problems on graphs is
based on five spatio-temporal DGNs (i.e., A3TGCN [39], DCRNN [37], GCRN-GRU
[34], GCRNN-LSTM [34], TGCN [9]), within the aim of assessing both stacked and
integrated architectures, and the influence of an attention mechanism.

We designed each model as a combination of three main components. The first is
the encoder which maps the node input features into a latent hidden space; the
second is the DGN which computes the spatio-temporal convolution; and the
third is a readout that maps the output of the convolution into the output
space. The encoder and the readout are MLPs that share the same architecture
among all models in the experiments. We performed hyper-parameter tuning via
grid search, optimizing the Mean Absolute Error (MAE). We perform a time-based
split of the dataset which reserves the first 70% of the data as training set,
15% of the following data as validation set, and the last 15% as test set. We
trained the models using Adam optimizer for a maximum of 1000 epochs and early
stopping with patience of 50 epochs on the validation error. For each model
configuration, we performed 5 training runs with different weight
initialization and report the average of the results. We report in Table II
the grid of hyper-parameters exploited for this experiment.

TABLE II: The grid of hyper-parameters employed during model selection for the spatio-temporal tasks.  | Configs
---|---
learning rate |  $10^{-2}$, $10^{-3}$, $10^{-4}$
weight decay |  $10^{-3}$, $10^{-4}$
embedding dim | 1, 2, 4, 8
$\sigma$ | ReLU
Chebishev poly. filter size | 1, 2, 3
normalization scheme for $\mathbf{L}$ |  $\mathbf{L}=\mathbf{D}-\mathbf{A}$, $\mathbf{L}=\mathbf{I}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$, $\mathbf{L}=\mathbf{I}-\mathbf{D}^{-1}\mathbf{A}$

##### Results

In Table III we report the results on the spatio-temporal-based experiments.

TABLE III: Mean test scores of the spatio-temporal models and std averaged over 5 random weight initializations. MAE is the optimized metric. The lower, the better. | Montevideo | Metr-LA | PeMSBay
---|---|---|---
Model | MAE | MSE | MAE | MSE | MAE | MSE
A3TGCN | $0.3962_{\pm 0.0021}$ | $1.0416_{\pm 0.0047}$ | $0.3401_{\pm 0.0008}$ | $0.3893_{\pm 0.0039}$ | $0.2203_{\pm 0.0105}$ | $0.2540_{\pm 0.0039}$
DRCNN | $0.3499_{\pm 0.0006}$ | $1.0686_{\pm 0.0012}$ | 0.1218±0.0013 | $0.0960_{\pm 0.0017}$ | 0.0569±0.0004 | $0.0398_{\pm 0.0002}$
GCRN-GRU | 0.3481±0.0008 | $1.0534_{\pm 0.0062}$ | $0.1219_{\pm 0.0007}$ | $0.0973_{\pm 0.0009}$ | $0.0571_{\pm 0.0005}$ | $0.0404_{\pm 0.0007}$
GCRN-LSTM | $0.3486_{\pm 0.0026}$ | $1.0451_{\pm 0.0099}$ | $0.1235_{\pm 0.0009}$ | $0.0985_{\pm 0.0004}$ | $0.0593_{\pm 0.0004}$ | $0.0436_{\pm 0.0001}$
TGCN | $0.4024_{\pm 0.0022}$ | $1.0678_{\pm 0.0049}$ | $0.3422_{\pm 0.0046}$ | $0.3891_{\pm 0.0058}$ | $0.2109_{\pm 0.0039}$ | $0.2466_{\pm 0.0033}$

Overall, DCRNN and GCRN-GRU achieve the better performance on the selected
tasks. Interestingly, they both rely on Chebyshev spectral convolution and
GRU, but with different architectural structure. Indeed, DCRNN employs a
stacked architecture, while GCRN-GRU embeds the DGN into the RNN, enabling a
combined modeling of the temporal and spatial information. This result shows
that there is not a superior architectural design, in these tasks. However, it
seems relevant to include a bigger neighborhood in the computation (e.g., by
exploiting a larger Chebishev polynomial filter size). Indeed, even if A3TGCN
employs an attention mechanism to capture more global information, it is not
enough to achieve comparable performance to DCRNN or GCRN-based approaches.

###  VI-B D-TDG benchmark

In the setting of general D-TDGs (i.e., both nodes’ state and topology may
evolve over time), we consider the following datasets:

  * •

Twitter Tennis [67]: a mention graph in which nodes are Twitter accounts and
their labels encode the number of mentions between them;

  * •

Elliptic [68]: a network of bitcoin transactions, wherein a node represents a
transaction and an edge indicate the payment flow. Node are also mapped to
real entities belonging to licit categories (e.g., exchanges, wallet
providers, miners, licit services) versus illicit ones (e.g., scams, malware,
terrorist organizations, ransomware, Ponzi schemes);

  * •

AS-773 [69]: the communication network of who-talks-to-whom defined in a
timespan of almost 26 months from the BGP (Border Gateway Protocol) logs;

  * •

Bitcoin-$\alpha$ [70, 71]: a who-trusts-whom network of bitcoin users trading
on the platform http://www.bitcoin-alpha.com.

We use the first two datasets to run node-level tasks. Specifically, similarly
to the case of spatio-temporal setting, in Twitter tennis we perform temporal
node regression, while in the Elliptic dataset temporal node classification.
Therefore, we predict the class associated to the nodes of the snapshot at
time $t$ given the past graph history, $[\mathcal{G}_{i}]_{i=1}^{t}$. We
employ the last two datasets for link prediction task, i.e., to predict the
future topology of the graph given its past history.

In this benchmark we evaluate three different classes of architectures (i.e.,
stacked, integrated and meta) and we show the potential of randomized networks
in the tradeoff between performance and complexity. Thus, we consider five
DGNs for our experiments: DynGESN [50], EvolveGCN-H [52], EvolveGCN-O [52],
GCLSTM [42], LRGCN [43].

We performed hyper-parameter tuning via grid search, optimizing the Mean
Absolute Error (MAE) in the case of node regression and Area Under the ROC
curve (AUROC) in the case of node classification and link prediction. We
considered the same experimental setting, split strategy, and architectural
choice as for the spatio-temporal graphs. In the case of link prediction, we
perform negative sampling by randomly sampling non-occurring links from the
next future snapshots. We note that in the case of DynGESN, the model employs
fixed and randomized weights and only the final readout is trained. We report
in Table IV the grid of hyper-parameters exploited for this experiment.

TABLE IV: The grid of hyper-parameters employed during model selection for the D-TDG tasks. The “$*$” value refer only to LRGCN model, while “$\diamond$” to DynGESN.  | Configs
---|---
learning rate |  $10^{-2}$, $10^{-3}$, $10^{-4}$
weight decay |  $10^{-3}$, $10^{-4}$
embedding dim | 8, 16, 32
$\sigma$ | ReLU
Chebishev poly. filter size | 1, 2, 3
normalization scheme for $\mathbf{L}$ |  $\mathbf{L}=\mathbf{D}-\mathbf{A}$, $\mathbf{L}=\mathbf{I}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$, $\mathbf{L}=\mathbf{I}-\mathbf{D}^{-1}\mathbf{A}$
n. bases in the basis-decomposition regularization scheme∗ | None, 10, 30
leakage (i.e., $\gamma$)⋄ | 0.1, 0.5, 0.9
random weight init. value⋄ | 0.1, 0.5, 0.9

##### Results

Table V shows the results on general D-TDGs. Differently than the spatio-
temporal setting, different tasks benefit from different architectures.
Indeed, integrating topology’s changes (such as in GCLSTM and LRGCN) is more
effective in link prediction tasks, while evolving the parameters of the DGN
is more beneficial for node-level tasks, since it is more difficult to change
the parameters of a static DGN to predict the topological evolution of the
system. Notably, DynGESN achieves comparable results by exploiting only few
trainable parameters, showing an advantageous tradeoff between performance and
complexity. This makes it an ideal choice when the computational resources are
limited.

TABLE V: Mean test scores and std of DGNs for general D-TDGs averaged over 5 random weight initializations. For MAE and MSE scores, lower values corresponds to better performances, while for AUROC and F1 the higher values are better. MSE and AUROC are the optimized metrics.  | Node-level tasks | Link-level tasks
---|---|---
| Twitter tennis | Elliptic | AS-773 | Bitcoin $\alpha$
Model | MAE | MSE | AUROC | F1 | AUROC | F1 | AUROC | F1
DynGESN | $0.1944_{\pm 0.0056}$ | $0.3708_{\pm 0.0411}$ | $50.57_{\pm 1.34}$ | $77.36_{\pm 20.31}$ | $86.88_{\pm 0.26}$ | $86.02_{\pm 0.35}$ | $90.08_{\pm 3.19}$ | $89.14_{\pm 3.86}$
EvolveGCN-H | $0.1735_{\pm 0.0007}$ | $0.2858_{\pm 0.0074}$ | $97.32_{\pm 0.08}$ | $98.64_{\pm 0.04}$ | $63.87_{\pm 16.99}$ | $46.57_{\pm 38.49}$ | $52.84_{\pm 3.48}$ | $10.15_{\pm 12.43}$
EvolveGCN-O | $0.1749_{\pm 0.0007}$ | $0.3020_{\pm 0.0111}$ | 97.47±0.01 | $98.72_{\pm 0.006}$ | $57.51_{\pm 15.02}$ | $44.22_{\pm 36.92}$ | $51.42_{\pm 2.84}$ | $45.07_{\pm 27.64}$
GCLSTM | 0.1686±0.0015 | $0.2588_{\pm 0.0049}$ | $97.24_{\pm 0.20}$ | $98.60_{\pm 0.10}$ | 91.49±0.09 | $91.62_{\pm 0.11}$ | $91.94_{\pm 0.19}$ | $91.65_{\pm 0.19}$
LRGCN | $0.1693_{\pm 0.0014}$ | $0.2507_{\pm 0.0057}$ | $97.15_{\pm 0.58}$ | $98.55_{\pm 0.30}$ | $88.80_{\pm 1.22}$ | $89.23_{\pm 1.25}$ | 93.14±0.52 | $92.88_{\pm 0.61}$

###  VI-C C-TDG benchmark

In the continuous scenario, we perform our experiment leveraging three
datasets:

  * •

Wikipedia [57]: one month of interactions (i.e., 157,474 interactions) between
user and Wikipedia pages. Specifically, it corresponds to the edits made by
8,227 users on the 1,000 most edited Wikipedia pages;

  * •

Reddit [57]: one month of posts (i.e., interactions) made by 10,000 most
active users on 1,000 most active subreddits, resulting in a total of 672,447
interactions;

  * •

LastFM [57]: one month of who-listens-to-which song information. The dataset
consists of 1000 users and the 1000 most listened songs, resulting in
1,293,103 interactions.

For all the datasets we considered the task of future link prediction, thus,
predicting if a link between two nodes $u$ and $v$ exists at a future time $t$
given the history of past events.

For our experimental purposes, we consider the following DGNs: DyRep [11],
JODIE [57], TGAT [12], and TGN [10]. These methods allow us to evaluate the
sequential encoding of spatial and temporal information as well as integrated
architectures. Moreover, they allow assessing the contribution of attention
mechanism, embedding trajectories, and memory components. We consider as
additional baseline EdgeBank [72] with the aim of showing the performance of a
simple heuristic. EdgeBank is a method that merely stores previously observed
interactions (without any learning), and then predicts stored links as
positive.

We performed hyper-parameter tuning via grid search, optimizing the AUROC
score. We considered the same experimental setting and split strategy as
previous experiments. We perform negative sampling by randomly sampling non-
occurring links in the graph, as follows: (1) during training we sample
negative destinations only from nodes that appear in the training set, (2)
during validation we sample them from nodes that appear in training set or
validation set and (3) during testing we sample them from the entire node set.

We report in Table VI the grid of hyper-parameters exploited for this
experiment.

TABLE VI: The grid of hyper-parameters employed during model selection for the C-TDG tasks.  | Configs
---|---
learning rate |  $10^{-3}$,$10^{-4}$
weight decay |  $10^{-4}$,$10^{-5}$
n. DGN layers | 1, 3
embedding dim | 32, 64, 96
$\sigma$ | tanh
Neighborhood sampler size | 5

##### Results

We report the results of the C-TDG experiments in Table VII.

TABLE VII: Mean test scores and std of DGNs for C-TDGs averaged over 5 random weight initializations. The higher, the better. The models are trained to maximize the AUROC score. | Wikipedia | Reddit | LastFM
---|---|---|---
Model | AUROC | F1 | AUROC | F1 | AUROC | F1
EdgeBank | 91.82 | 91.09 | 96.42 | 96.29 | 94.72 | 94.43
DyRep |  89.72±0.59 |  79.02±0.91 |  97.69±0.04 |  92.12±0.13 |  78.41±0.50 |  71.80±0.92
JODIE |  94.94±0.48 |  87.52±0.39 |  96.72±0.21 |  89.97±0.66 |  69.32±1.33 |  63.95±2.64
TGAT |  95.54±0.22 |  88.11±0.45 |  98.41±0.01 |  93.58±0.05 | 81.97±0.08 |  70.96±0.24
TGN | 97.07±0.15 |  90.49±0.24 | 98.66±0.04 |  94.20±0.15 |  79.84±1.58 |  71.09±2.36

Overall, TGN generally outperforms all the other methods, showing consistent
improvements over DyRep and JODIE. This result shows how the spatial
information is fundamental for the effective resolution of the tasks. Indeed,
an advantage of TGAT and TGN is that they can exploit bigger neighborhoods
with respect to DyRep, which uses the information coming from one-hop
distance, and JODIE, which only encode the source and destination information.
Despite these results, we observe that the temporal information is still
extremely relevant to achieve good performance. In fact, the EdgeBank baseline
is able to exceed 91% AUROC score by only looking at the graph’s history. This
is even more evident in the LastFM task, which, as observed in [72], contains
more reoccurring edges with respect to Wikipedia and Reddit. Consequently,
such a task is comparatively easier to solve by solely exploiting these
temporal patterns. Considering that EdgeBank’s performance is directly
correlated to the number of memorized edges, in this task, it is able to
outperform all the other methods.

##  VII Conclusions

Despite the field of representation learning for (static) graphs is now a
consolidated and vibrant research area, there is still a strong demand for
work in the domain of dynamic graphs.

In light of this, in this paper we proposed, at first, a survey that focuses
on recent representation learning techniques for dynamic graphs under a
uniform formalism consolidated from existing literature. Second, we provide
the research community with a fair performance comparison among the most
popular methods of the three families of dynamic graph problems, by leveraging
a reproducible experimental environment. We believe that this work will help
fostering the research in the domain of dynamic graphs by providing a clear
picture of the current development status and a good baseline to test new
architectures and approaches.

In order to further improve the maturity of representation learning for
dynamic graphs, we believe that certain aspects should be deepened. A future
interesting direction, in this sense, is to extend the work that has been done
for heterophilic (static) graphs [73, 74, 75] to the temporal domain. This
will require addressing the problem of generating information-rich node
representations when neighboring nodes tend to belong to different classes. A
similar challenge is the one of heterogeneus dynamic graphs, which contain
different types of nodes and links. In this scenario, new architectures should
learn the semantic-level information coming from node and edge types, in
addition to topological and label information. Although these are interesting
future directions, we observe that there are more challenges to be addressed
in the future, such as the study in the temporal domain of over-smoothing
[76], which is a phenomenon where all node features become almost
indistinguishable after few embedding updates; over-squashing [77, 78], which
prevents DGNs to propagate and preserve long-term dependencies between nodes;
and expressive power of DGNs [23, 79].

## Acknowledgements

This work has been partially supported by EU NextGenerationEU programme under
the funding schemes PNRR-PE-AI FAIR (Future Artificial Intelligence Research)
and by the EU H2020 TAILOR project, GA n. 952215. The authors would like to
thank Federico Errica, NEC Laboratories Europe GmbH, for the insightful
discussions throughout the development of this work.

## References

  * Gilmer et al. [2017] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, “Neural Message Passing for Quantum Chemistry,” in _Proceedings of the 34th ICML_ , vol. 70. JMLR, 2017, p. 1263–1272.
  * Zitnik et al. [2018] M. Zitnik, M. Agrawal, and J. Leskovec, “Modeling polypharmacy side effects with graph convolutional networks,” _Bioinformatics_ , vol. 34, no. 13, pp. i457–i466, 06 2018.
  * Gravina et al. [2022] A. Gravina, J. L. Wilson, D. Bacciu, K. J. Grimes, and C. Priami, “Controlling astrocyte-mediated synaptic pruning signals for schizophrenia drug repurposing with deep graph networks,” _PLoS Comput. Biol._ , vol. 18, no. 5, pp. 1–19, 05 2022.
  * Bacciu et al. [2023] D. Bacciu, F. Errica, A. Gravina, L. Madeddu, M. Podda, and G. Stilo, “Deep Graph Networks for Drug Repurposing with Multi-Protein Targets,” _IEEE TETC_ , pp. 1–14, 2023.
  * Monti et al. [2019] F. Monti, F. Frasca, D. Eynard, D. Mannion, and M. M. Bronstein, “Fake News Detection on Social Media using Geometric Deep Learning,” _arXiv preprint arXiv:1902.06673_ , 2019.
  * Derrow-Pinion et al. [2021] A. Derrow-Pinion, J. She, D. Wong, O. Lange, T. Hester, L. Perez, M. Nunkesser, S. Lee, X. Guo, B. Wiltshire, P. W. Battaglia, V. Gupta, A. Li, Z. Xu, A. Sanchez-Gonzalez, Y. Li, and P. Velickovic, “ETA Prediction with Graph Neural Networks in Google Maps,” in _Proceedings of the 30th ACM CIKM_. Association for Computing Machinery, 2021, p. 3767–3776.
  * Bacciu et al. [2020] D. Bacciu, F. Errica, A. Micheli, and M. Podda, “A gentle introduction to deep learning for graphs,” _Neural Networks_ , vol. 129, pp. 203–221, 2020\.
  * Wu et al. [2021] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu, “A Comprehensive Survey on Graph Neural Networks,” _IEEE TNNLS_ , vol. 32, no. 1, pp. 4–24, 2021.
  * Zhao et al. [2020] L. Zhao, Y. Song, C. Zhang, Y. Liu, P. Wang, T. Lin, M. Deng, and H. Li, “T-GCN: A Temporal Graph Convolutional Network for Traffic Prediction,” _IEEE T-ITS_ , vol. 21, no. 9, pp. 3848–3858, 2020.
  * Rossi et al. [2020] E. Rossi, B. Chamberlain, F. Frasca, D. Eynard, F. Monti, and M. Bronstein, “Temporal Graph Networks for Deep Learning on Dynamic Graphs,” in _ICML 2020 Workshop on Graph Representation Learning_ , 2020.
  * Trivedi et al. [2019] R. Trivedi, M. Farajtabar, P. Biswal, and H. Zha, “DyRep: Learning Representations over Dynamic Graphs,” in _ICLR_ , 2019.
  * Xu et al. [2020] D. Xu, C. Ruan, E. Korpeoglu, S. Kumar, and K. Achan, “Inductive representation learning on temporal graphs,” in _ICLR_ , 2020.
  * Kazemi et al. [2020] S. M. Kazemi, R. Goel, K. Jain, I. Kobyzev, A. Sethi, P. Forsyth, and P. Poupart, “Representation Learning for Dynamic Graphs: A Survey,” _J. Mach. Learn. Res._ , vol. 21, no. 1, jan 2020.
  * Jiang and Luo [2022] W. Jiang and J. Luo, “Graph neural network for traffic forecasting: A survey,” _Expert Systems with Applications_ , vol. 207, p. 117921, 2022\.
  * Bondy [1976] J. A. Bondy, _Graph Theory With Applications_. Elsevier Science Ltd., 1976.
  * Scarselli et al. [2009] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The Graph Neural Network Model,” _IEEE Transactions on Neural Networks_ , vol. 20, no. 1, pp. 61–80, 2009.
  * Micheli [2009] A. Micheli, “Neural Network for Graphs: A Contextual Constructive Approach,” _IEEE Transactions on Neural Networks_ , vol. 20, no. 3, pp. 498–511, 2009.
  * Defferrard et al. [2016] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering,” in _Proceedings of the 29th NeurIPS_. Curran Associates Inc., 2016, p. 3844–3852.
  * Kipf and Welling [2017] T. N. Kipf and M. Welling, “Semi-Supervised Classification with Graph Convolutional Networks,” in _ICLR_ , 2017.
  * Veličković et al. [2018] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph Attention Networks,” _ICLR_ , 2018.
  * Hamilton et al. [2017] W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive Representation Learning on Large Graphs,” in _NeurIPS_ , 2017.
  * Chiang et al. [2019] W.-L. Chiang, X. Liu, S. Si, Y. Li, S. Bengio, and C.-J. Hsieh, “Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks,” in _Proceedings of the 25th ACM SIGKDD KDD_. Association for Computing Machinery, 2019, p. 257–266.
  * Xu et al. [2019] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How Powerful are Graph Neural Networks?” in _ICLR_ , 2019.
  * Weisfeiler and Lehman [1968] B. Weisfeiler and A. Lehman, “A Reduction of a Graph to a Canonical Form and an Algebra Arising during This Reduction,” _Nauchno-Technicheskaya Informatsia_ , vol. 2, no. 9, 1968.
  * Gravina et al. [2023] A. Gravina, D. Bacciu, and C. Gallicchio, “Anti-Symmetric DGN: a stable architecture for Deep Graph Networks,” in _ICLR_ , 2023.
  * Wang et al. [2021a] Y. Wang, Y. Wang, J. Yang, and Z. Lin, “Dissecting the Diffusion Process in Linear Graph Convolutional Networks,” in _NeurIPS_ , 2021.
  * Wu et al. [2019] F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger, “Simplifying Graph Convolutional Networks,” in _Proceedings of the 36th ICML_ , vol. 97. PMLR, 09-15 Jun 2019, pp. 6861–6871.
  * Eliasof et al. [2021] M. Eliasof, E. Haber, and E. Treister, “PDE-GCN: Novel Architectures for Graph Neural Networks Motivated by Partial Differential Equations,” in _NeurIPS_ , 2021.
  * Rusch et al. [2022] T. K. Rusch, B. P. Chamberlain, J. Rowbottom, S. Mishra, and M. M. Bronstein, “Graph-Coupled Oscillator Networks,” _arXiv preprint arXiv:2202.02296_ , 2022.
  * Perozzi et al. [2014] B. Perozzi, R. Al-Rfou, and S. Skiena, “DeepWalk: Online Learning of Social Representations,” in _Proceedings of the 20th ACM SIGKDD KDD_. ACM, 2014, pp. 701–710.
  * Mikolov et al. [2013] T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient Estimation of Word Representations in Vector Space,” in _ICLR_ , 2013.
  * Grover and Leskovec [2016] A. Grover and J. Leskovec, “node2vec: Scalable Feature Learning for Networks,” in _Proceedings of the 22nd ACM SIGKDD KDD_ , 2016.
  * Rumelhart et al. [1986] D. E. Rumelhart, G. E. Hinton, and R. J. Williams, “Learning representations by back-propagating errors,” _Nature_ , vol. 323, no. 6088, pp. 533–536, Oct 1986.
  * Seo et al. [2018] Y. Seo, M. Defferrard, P. Vandergheynst, and X. Bresson, “Structured Sequence Modeling with Graph Convolutional Recurrent Networks,” in _NeurIPS_. Springer International Publishing, 2018, pp. 362–373.
  * Gers et al. [2002] F. Gers, N. Schraudolph, and J. Schmidhuber, “Learning Precise Timing with LSTM Recurrent Networks,” _Journal of Machine Learning Research_ , vol. 3, pp. 115–143, 01 2002.
  * Graves [2013] A. Graves, “Generating sequences with recurrent neural networks,” _arXiv preprint arXiv:1308.0850_ , 2013.
  * Li et al. [2018] Y. Li, R. Yu, C. Shahabi, and Y. Liu, “Diffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting,” in _ICLR_ , 2018.
  * Cho et al. [2014] K. Cho, B. van Merrienboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio, “Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation,” _arXiv preprint arXiv:1406.1078_ , 2014.
  * Bai et al. [2021] J. Bai, J. Zhu, Y. Song, L. Zhao, Z. Hou, R. Du, and H. Li, “A3T-GCN: Attention Temporal Graph Convolutional Network for Traffic Forecasting,” _ISPRS International Journal of Geo-Information_ , vol. 10, no. 7, 2021.
  * Yu et al. [2018] B. Yu, H. Yin, and Z. Zhu, “Spatio-temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting,” in _Proceedings of the 27th IJCAI_ , 2018.
  * Dauphin et al. [2017] Y. N. Dauphin, A. Fan, M. Auli, and D. Grangier, “Language Modeling with Gated Convolutional Networks,” in _Proceedings of the 34th ICML_ , vol. 70. JMLR, 2017, p. 933–941.
  * Chen et al. [2018] J. Chen, X. Xu, Y. Wu, and H. Zheng, “GC-LSTM: Graph convolution embedded lstm for dynamic link prediction,” _arXiv preprint arXiv:1812.04206_ , 2018\.
  * Li et al. [2019] J. Li, Z. Han, H. Cheng, J. Su, P. Wang, J. Zhang, and L. Pan, “Predicting Path Failure In Time-Evolving Graphs,” in _Proceedings of the 25th ACM SIGKDD KDD_. Association for Computing Machinery, 2019, p. 1279–1289.
  * Schlichtkrull et al. [2018] M. Schlichtkrull, T. N. Kipf, P. Bloem, R. van den Berg, I. Titov, and M. Welling, “Modeling Relational Data with Graph Convolutional Networks,” in _The Semantic Web_. Springer International Publishing, 2018, pp. 593–607.
  * Panagopoulos et al. [2021] G. Panagopoulos, G. Nikolentzos, and M. Vazirgiannis, “Transfer Graph Neural Networks for Pandemic Forecasting,” in _Proceedings of the 35th AAAI Conference on Artificial Intelligence_ , 2021.
  * You et al. [2022] J. You, T. Du, and J. Leskovec, “ROLAND: graph learning framework for dynamic graphs,” in _Proceedings of the 28th ACM SIGKDD KDD_ , 2022, pp. 2358–2366.
  * Cini et al. [2023] A. Cini, I. Marisca, F. Bianchi, and C. Alippi, “Scalable Spatiotemporal Graph Neural Networks,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2023.
  * Jaeger [2010] H. Jaeger, “The “echo state” approach to analysing and training recurrent neural networks–with an erratum note,” _German National Research Center for Information Technology GMD Technical Report_ , vol. 148, no. 34, 2010\.
  * Jaeger and Haas [2004] H. Jaeger and H. Haas, “Harnessing Nonlinearity: Predicting Chaotic Systems and Saving Energy in Wireless Communication,” _Science_ , vol. 304, no. 5667, pp. 78–80, 2004.
  * Micheli and Tortorella [2022] A. Micheli and D. Tortorella, “Discrete-time dynamic graph echo state networks,” _Neurocomputing_ , vol. 496, pp. 85–95, 2022.
  * Gallicchio and Micheli [2010] C. Gallicchio and A. Micheli, “Graph echo state networks,” in _IJCNN_. IEEE, 2010, pp. 1–8.
  * Pareja et al. [2020] A. Pareja, G. Domeniconi, J. Chen, T. Ma, T. Suzumura, H. Kanezashi, T. Kaler, T. B. Schardl, and C. E. Leiserson, “EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs,” in _Proceedings of the 34th AAAI Conference on Artificial Intelligence_ , 2020.
  * Taheri and Berger-Wolf [2019] A. Taheri and T. Berger-Wolf, “Predictive Temporal Embedding of Dynamic Graphs,” in _Proceedings of the 2019 IEEE/ACM ASONAM_. Association for Computing Machinery, 2019, p. 57–64.
  * Li et al. [2016] Y. Li, R. Zemel, M. Brockschmidt, and D. Tarlow, “Gated Graph Sequence Neural Networks,” in _Proceedings of ICLR’16_ , April 2016.
  * Goyal et al. [2018] P. Goyal, N. Kamra, X. He, and Y. Liu, “DynGEM: Deep Embedding Method for Dynamic Graphs,” _arXiv preprint arXiv:1805.11273_ , 2018.
  * Bastas et al. [2019] N. Bastas, T. Semertzidis, A. Axenopoulos, and P. Daras, “evolve2vec: Learning Network Representations Using Temporal Unfolding,” in _MultiMedia Modeling_. Springer International Publishing, 2019, pp. 447–458.
  * Kumar et al. [2019] S. Kumar, X. Zhang, and J. Leskovec, “Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks,” in _Proceedings of the 25th ACM SIGKDD KDD_. ACM, 2019.
  * Ma et al. [2020] Y. Ma, Z. Guo, Z. Ren, J. Tang, and D. Yin, “Streaming Graph Neural Networks,” in _Proceedings of the 43rd International ACM SIGIR_. Association for Computing Machinery, 2020, p. 719–728.
  * Nguyen et al. [2018] G. Nguyen, J. B. Lee, R. A. Rossi, N. Ahmed, E. Koh, and S. Kim, “Continuous-Time Dynamic Network Embeddings,” _Companion Proceedings of The Web Conference 2018_ , 2018.
  * Wang et al. [2021b] Y. Wang, Y.-Y. Chang, Y. Liu, J. Leskovec, and P. Li, “Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks,” in _ICLR_ , 2021.
  * Souza et al. [2022] A. H. Souza, D. Mesquita, S. Kaski, and V. K. Garg, “Provably expressive temporal graph networks,” in _NeurIPS_ , 2022.
  * Fey and Lenssen [2019] M. Fey and J. E. Lenssen, “Fast graph representation learning with PyTorch Geometric,” in _ICLR Workshop on Representation Learning on Graphs and Manifolds_ , 2019.
  * Leskovec and Krevl [2014] J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/data, Jun. 2014.
  * [64] A. Cini and I. Marisca, “Torch spatiotemporal, 3 2022,” _https://github.com/TorchSpatiotemporal/tsl_ , vol. 10.
  * Rossi and Ahmed [2015] R. A. Rossi and N. K. Ahmed, “The network data repository with interactive graph analytics and visualization,” in _AAAI_ , 2015. [Online]. Available: https://networkrepository.com
  * Rozemberczki et al. [2021] B. Rozemberczki, P. Scherer, Y. He, G. Panagopoulos, A. Riedel, M. Astefanoaei, O. Kiss, F. Beres, G. Lopez, N. Collignon, and R. Sarkar, “PyTorch Geometric Temporal: Spatiotemporal Signal Processing with Neural Machine Learning Models,” in _Proceedings of the 30th ACM CIKM_ , 2021, p. 4564–4573.
  * Béres et al. [2018] F. Béres, R. Pálovics, A. Oláh, and A. A. Benczúr, “Temporal walk based centrality metric for graph streams,” _Applied Network Science_ , vol. 3, no. 1, p. 32, 2018.
  * Weber et al. [2019] M. Weber, G. Domeniconi, J. Chen, D. Weidele, C. Bellei, T. Robinson, and C. Leiserson, “Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics,” _KDD ’19 Workshop on Anomaly Detection in Finance_ , 08 2019.
  * Leskovec et al. [2005] J. Leskovec, J. Kleinberg, and C. Faloutsos, “Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations,” in _Proceedings of the 11th ACM SIGKDD KDD_. Association for Computing Machinery, 2005, p. 177–187.
  * Kumar et al. [2016] S. Kumar, F. Spezzano, V. Subrahmanian, and C. Faloutsos, “Edge weight prediction in weighted signed networks,” in _IEEE ICDM_. IEEE, 2016, pp. 221–230.
  * Kumar et al. [2018] S. Kumar, B. Hooi, D. Makhija, M. Kumar, C. Faloutsos, and V. Subrahmanian, “Rev2: Fraudulent user prediction in rating platforms,” in _Proceedings of the 11th ACM WSDM_. ACM, 2018, pp. 333–341.
  * Poursafaei et al. [2022] F. Poursafaei, S. Huang, K. Pelrine, , and R. Rabbany, “Towards better evaluation for dynamic link prediction,” in _NeurIPS Datasets and Benchmarks_ , 2022.
  * Pei et al. [2020] H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang, “Geom-GCN: Geometric Graph Convolutional Networks,” in _ICLR_ , 2020.
  * Yan et al. [2021] Y. Yan, M. Hashemi, K. Swersky, Y. Yang, and D. Koutra, “Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks,” _arXiv preprint arXiv:2102.06462_ , 2021.
  * Cavallo et al. [2023] A. Cavallo, C. Grohnfeldt, M. Russo, G. Lovisotto, and L. Vassio, “GCNH: A Simple Method For Representation Learning On Heterophilous Graphs,” _arXiv preprint arXiv:2304.10896_ , 2023.
  * Cai and Wang [2020] C. Cai and Y. Wang, “A note on over-smoothing for graph neural networks,” _arXiv preprint arXiv:2006.13318_ , 2020.
  * Alon and Yahav [2021] U. Alon and E. Yahav, “On the Bottleneck of Graph Neural Networks and its Practical Implications,” in _ICLR_ , 2021.
  * Giovanni et al. [2023] F. D. Giovanni, L. Giusti, F. Barbero, G. Luise, P. Lio’, and M. Bronstein, “On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology,” _arXiv preprint arXiv:2302.02941_ , 2023.
  * Li and Leskovec [2022] P. Li and J. Leskovec, “The expressive power of graph neural networks,” in _Graph Neural Networks: Foundations, Frontiers, and Applications_ , L. Wu, P. Cui, J. Pei, and L. Zhao, Eds. Springer Singapore, 2022, pp. 63–98.

|  Alessio Gravina is a Ph.D. Student in Computer Science at University of
Pisa. He received his B.Sc./M.Sc. in Computer Science from University of Pisa
in 2018 and 2020, respectively. He was a visiting researcher at Huawei
Research Center, Munich in 2023 and at Stanford University in 2019, while, in
2018, he won the Fujistu AI-NLP Challenge. He is a member of the Computational
Intelligence and Machine Learning group and Pervasive AI Lab. His interests
are related to the area of machine learning for graphs and deep learning.
---|---
|  Davide Bacciu (S’06–M’09–SM’18) has a Ph.D. in Computer Science and
Engineering from IMT Lucca. He is Associate Professor at the Computer Science
Department, University of Pisa, where he heads the Pervasive AI Lab. His
research interests include machine learning for structured data, Bayesian
learning, deep learning, reservoir computing, distributed and embedded
learning systems. Dr. Bacciu received the 2009 E.R. Caianiello Award for the
best Italian Ph.D. thesis on neural networks. He is the Vice President of the
Italian Association for Artificial Intelligence, Chair of the IEEE Technical
Committee on Neural Networks and the founder of the IEEE CIS Task Force on
Learning for Graphs. He is a Senior Editor of the IEEE TNNLS.
---|---