Dynamic Graph Representation Learning with Neural Networks: A Survey
In recent years, Dynamic Graph (DG) representations have been increasingly
used for modeling dynamic systems due to their ability to integrate both
topological and temporal information in a compact representation. Dynamic
graphs allow to efficiently handle applications such as social network
prediction, recommender systems, traffic forecasting or electroencephalography
analysis, that can not be adressed using standard numeric representations. As a
direct consequence of the emergence of dynamic graph representations, dynamic
graph learning has emerged as a new machine learning problem, combining
challenges from both sequential/temporal data processing and static graph
learning. In this research area, Dynamic Graph Neural Network (DGNN) has became
the state of the art approach and plethora of models have been proposed in the
very recent years. This paper aims at providing a review of problems and models
related to dynamic graph learning. The various dynamic graph supervised
learning settings are analysed and discussed. We identify the similarities and
differences between existing models with respect to the way time information is
modeled. Finally, general guidelines for a DGNN designer when faced with a
dynamic graph learning problem are provided.
Leshanshui Yang, Sébastien Adam, Clément Chatelain
# Dynamic Graph Representation Learning with Neural Networks: A Survey

###### Abstract

In recent years, Dynamic Graph (DG) representations have been increasingly used for modeling dynamic systems due to their ability to integrate both topological and temporal information in a compact representation. Dynamic graphs allow to efficiently handle applications such as social network prediction, recommender systems, traffic forecasting or electroencephalography analysis, that can not be adressed using standard numeric representations. As a direct consequence of the emergence of dynamic graph representations, dynamic graph learning has emerged as a new machine learning problem, combining challenges from both sequential/temporal data processing and static graph learning. In this research area, Dynamic Graph Neural Network (DGNN) has became the state of the art approach and plethora of models have been proposed in the very recent years. This paper aims at providing a review of problems and models related to dynamic graph learning. The various dynamic graph supervised learning settings are analysed and discussed. We identify the similarities and differences between existing models with respect to the way time information is modeled. Finally, general guidelines for a DGNN designer when faced with a dynamic graph learning problem are provided.

## 1 Introduction

Graphs are data structures used for representing both attributed entities (the vertices of the graph) and relational information between them (the edges of the graph) in a single and compact formalism. They are powerful and versatile, capable of modelling irregular structures such as skeletons, molecules, transport systems, knowledge graphs or social networks, across different application domains such as chemistry, biology or finance. This expressive power of graphs explains why graphs have been used extensively to tackle Pattern Recognition (PR) tasks, as demonstrated by the current special issue.

In the PR community, most of the existing contributions focus on static graphs where the node set, the edge set and the nodes/edge attributes do not evolve with time. Yet, for some real-world applications such as traffic flow forecasting, rumour detection or link prediction in a recommender system, graphs are asked to handle time-varying topology and/or attributes, in order to model dynamic systems. Several terms are used in the literature to refer to graphs in which the structure and the attributes of nodes/edges evolve. Dynamic graphs
[108, 103], temporal graphs [96, 162, 109], (time-/temporally) evolving graphs [153, 107, 46, 100], time-varying graphs [156, 157], time-dependent graphs [158, 159], or temporal networks [8, 15, 113, 124] are examples of such terms which refer to conceptual variants describing the same principles. This multiplicity of terms can be explained by the diversity of the scientific communities interested by this kind of models but also by the youth of the field. It illustrates the need for precise definitions and clear taxonomies of problems and models, which is one of the contributions of this paper. In the following, we choose to use the more general term Dynamic Graph (DG).

As a direct consequence of the emergence of dynamic graph representations, dynamic graph learning emerged as a new machine learning problem, combining challenges from both sequential/temporal data processing and static graph learning.

When learning on sequential data, the fundamental challenge is to capture the dependencies between the different entities of a sequence. In this domain, the original concept of recurrence, mainly instantiated by LSTM [29], has been gradually replaced in recent years by fully convolutional architectures, which offer better parallelization capabilities during learning. More recently, sequence-to-sequence models based on the encoder/decoder framework have been proposed [173], allowing to deal with desynchronised input and output signals. These models, such as the famous transformer [36], rely on the intensive use of the attention mechanism [35, 174, 175].

When learning on static graphs, the main challenge is to overcome the permutation invariance/equivariance constraint inherent to the absence of node ordering in graph representations. To solve this problem, node-based message-passing mechanisms based on graph structure have led to the first generation of Graph Neural Networks (GNNs), called Message Passing Neural Networks (MPNNs) [163]. As convolutions on images, these models propagate the features of each node to neighbouring nodes using trainable weights that can be shared with respect to the distance between nodes (Chebnet) [164], to the connected nodes features (GAT) [165] and/or to edge features (k-GNN) [166]. Given the maturity of such models and their applicability for large sparse graphs, they have been applied with success on many downstream tasks. This maturity also explains the existence of some exhaustive reviews and comparative studies, such as in [125, 168, 167, 172] to cite a few. One can note that, despite these successes, it has been shown that MPNNs are not powerful enough [167]. That is why machine learning on graphs is still a very active field, trying to improve the expressive power of GNNs [169, 171, 170]. However, these models are still too computationally demanding to be applicable to real-world problems.

Compared to neural networks applied for learning on sequences and on static graphs, Dynamic Graph Neural Network (DGNN) is a much more recent field. To the best of our knowledge, the founding DGNN models are from 2018 [79] and 2019 [106] for respectively the discrete and the continuous cases. These papers have been at the root of a "zoo" of methods proposed by various scientific
communities, with various terminologies, various learning settings and various application domains.

In order to structure the domain, some state-of-the-art papers have been published recently [12, 6, 13]. Without focusing on DGNN, these papers give a good overview of many machine learning issues linked to dynamic graphs and describe many existing models. However, they do not compare models according to the different possible DG inputs and supervised learning settings that can be encountered when applying machine learning to DG. As an example, [12, 6] do not consider in their study the spatial-temporal case. They also do not compare the ability of existing models to consider inductive or transductive tasks.

The main objective of this review is to extend the existing studies mentioned above, focusing on **dynamic graph supervised learning using neural networks**. It is addressed to the audience with fundamental knowledge of neural networks and static graph learning. Three main contributions can be highlighted. The first one consists in **clarifying and categorizing the different dynamic graph learning contexts** that are encountered in the literature. These contexts are distinguished according to the type of input DGs (discrete vs. continuous, edge-evolving vs. node-evolving vs attributes-evolving, homogeneous vs. heterogeneous) but also according to the learning setting (transductive vs. inductive). The second contribution is an **exhaustive review of existing DGNN models**, including the most recent ones. For this review, we choose to categorize models into five groups, according to the strategy used to incorporate time information in the model, which is the main challenge for the application of neural networks on DGs. Based on this categorisation, and using the taxonomy of contexts mentioned above, the third contribution is to provide some **general guidelines for a DGNN designer when faced with a dynamic graph learning problem** and to describe different methods for optimising the DGNN performance.

The remainder of this paper is structured as follows. Section 2 relates to the first contribution, by considering the inputs, the outputs and the learning settings that can be encountered when learning on dynamic graphs. Section 3 reviews existing Dynamic Graph Neural Networks (DGNNs) and compares them according to their temporal information processing. Finally, section 4 brings forward the guidelines for designing DGNNs and discusses some optimisation methods.

## 2 Dynamic Graph Representation Learning

Regardless of the data representation, the goal of supervised learning methods is to build a parameterized statistical model or predictor \(g_{\Theta}\) that maps between an input space \(\mathcal{X}\) and an output space \(\mathcal{Y}\) (see Fig. 1). During the _learning_ phase, the training of the predictor \(g_{\Theta}\) consists in updating its parameters \(\Theta\) using a dataset of couples \((x,y)\). The update is computed by a minimization of the loss between the prediction \(\hat{\mathbf{Y}}\) and the ground truth \(\mathbf{Y}\).
Many recent models follow the encoder/decoder principle, where a variable-length input signal is encoded into a latent representation, which is then used by a decoder to compute the output signal for the downstream task (see Fig. 2). The fixed-size latent representation allows alignment between variable-size input and output signals that are not necessarily synchronised, i.e. the units of the input and output sequences may have a different order. It is of great interest in many sequence-to-sequence problems involving text, images or speech. The learning latent representation (also known as _embedding_) is called _representation learning_.

Sequences are signals in which information varies according to one or more dimensions, that generally define a position in a structure. This structure may have one or multiple dimensions: time for speech, 1D position for text, 2D position for images, etc. In the case of dynamic graphics, the information varies according to the position too, but the structure can also evolve along time. In this section, we propose the concept of _degree of dynamism_ that defines the nature of the variability. Given that the degree of dynamism of DG is higher than for sequences, the encoder/decoder framework therefore provides a very suitable framework for learning DG representations.

In this section, we define important concepts specific to dynamic graphs, giving the necessary material for understanding the review of the dynamic graph embedding problem presented in section 3. The section is structured as follows (see Fig. 2): after giving useful definition about static graphs in subsection 2.1, we present the representation of dynamic graphs in subsection 2.2. We then present

Figure 1: Left: inference phase for making predictions \(\hat{\mathbf{Y}}\) on given data \(\mathbf{X}\). Right: learning phase for updating the parameters \(\Theta\) of the predictor \(g\).

Figure 2: Encoder/decoder model applied on dynamic graphs: the encoding consists in computing \(\mathbf{Z}=f(\text{DG})\), where DG is a dynamic graph (including both topology and attributes), \(f(\cdot)\) is a parameterized statistical model (typically a neural networks with learnable parameters), and \(\mathbf{Z}\) is the encoded tensor representation of DG. The decoder \(f_{dec}(\cdot)\) takes as input the representations \(\mathbf{Z}\) to get the predictions \(\hat{\mathbf{Y}}\).
the output shape and the transductive/inductive nature of learning tasks in subsections 2.3 and 2.4. Finally, we introduce the related applications in each learning setting in subsection 2.5.

### Static Graph Modeling

A static graph \(G\) can be represented topologically by a tuple \((V,E)\) where \(V\) is the node set of \(G\) and \(E\) is the edge set of \(G\). The connectivity information is usually represented by an adjacency matrix \(\mathbf{A}\in\mathbb{R}^{|V|\times|V|}\). In this matrix, \(A(u,v)=1\) if there is an edge between node \(u\) and \(v\), \(A(u,v)=0\) otherwise. \(\mathbf{A}\) is symmetric in an undirected graph, while in the case of directed graphs \(\mathbf{A}\) is not necessarily symmetric.

Nodes usually have attributes represented by a feature matrix \(\mathbf{X}_{V}\in\mathbb{R}^{|V|\times d_{V}}\), where \(d_{V}\) is the length of the attribute vector of a single node. Similarly, edges may have attributes (such as weights, directions, etc.) which can also be represented by a matrix \(\mathbf{X}_{E}\in\mathbb{R}^{|E|\times d_{E}}\).

In the case of weighted graphs, the values in the matrix \(\mathbf{A}\) are the weights of each edge instead of \(1\) which is denoted as:

\[\mathbf{A}_{u,v}=\left\{\begin{array}{rl}w_{u,v}&\text{if }(u,v)\in E\\ 0&\text{otherwise.}\end{array}\right.\]

For some specific applications, both nodes and edges can be of different types. For example, in recommender systems, nodes can usually be mapped into two types, item and user, and have feature matrices of different sizes and contents. In such cases, we extend the notation of the graph \(G=(V,E)\) with the type mapping functions \(\phi:V\to O\) and \(\psi:E\to R\), where \(|O|\) denotes the possible types of nodes and \(|R|\) denotes the possible types of edges [1]. When \(|O|=1\) and \(|R|=1\), nodes and edges are of a single type, this graph is called homogeneous. In contrast, in a heterogeneous graph, \(|O|+|R|>2\) and each type of node or edge could have its own number of feature dimensions [1, 2].

Figure 3 illustrated the difference between homogeneous and heterogeneous graphs.

### Dynamic Graph Modeling

Definition 1 (Dynamic Graph): A dynamic graph is a graph whose topology and/or attributes change over time.

According to this definition, both structure and attributes may change over time in a dynamic graph. Edges and/or nodes may be added or deleted and their attributes may change. Thus, this definition covers different configurations. In order to distinguish between them, we propose the concept of _degree of dynamism defined as follows:
Definition 2 (Degree of Dynamism (Node-Cintroduceentric)): The _degree of dynamism_ of a DG describes whether the topology, i.e. the edge set \(E\) and the node set \(V\), are invariant. Theoretically, there are 4 possible situations: (1) Both \(V\) and \(E\) are invariant, denoted as \(fix_{V,E}\). This situation corresponds to DG called "Spatial-Temporal Graphs" or "Spatio-Temporal Graphs (STGs) in the literature(2) \(V\) is invariant but the edge set is changing, denoted as \(fix_{V}\). (3) The node set and the edge set are both changing, denoted as \(vary\). (4) The set of edges is constant but the set of nodes changes. Since an edge exists based on a tuple of nodes, this situation is meaningless.

The Table 1 illustrates these different configurations which will be discussed throughout the paper.

\begin{table}
\begin{tabular}{l c c c} \hline \hline  & & \multicolumn{2}{c}{Node Set} \\ \cline{3-4}  & & Constant & Variant \\ \hline \multirow{2}{*}{Edge Set} & Constant & \(fix_{V,E}\) & N/A \\ \cline{2-4}  & Variant & \(fix_{V}\) & \(vary\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Degree of Dynamism discussed in the article.

Figure 3: Left: Common static graph representations. The edges in a directed weighted graph have directions and weights, which are frequently used when modelling email networks, citation networks, etc. The nodes and edges in a heterogeneous graph can have multiple possible types i.e., recommendation systems and knowledge graphs. Middle: Discrete Time Dynamic Graph (DTDG) represented by snapshots, and Continuous Time Dynamic Graph (CTDG) represented by events, the example in the figure is the ”Contact Sequence” case. Right: Equivalent Static Graphs (ESGs) represented by edges and nodes.
In the following, we provide the main existing dynamic graph representations for DG, synthesizing previous studies that focus on subparts of these representations [158, 8, 9, 6, 94, 154]. We also introduce in this part a representation called Equivalent-Static-Graph which consists in modeling a DG using a static graph. The different models are compared in Fig. 3.

#### 2.0.1 Continuous Time Dynamic Graphs

To preserve accurate time information, Continuous Time Dynamic Graphs (CTDGs) use a set of events to represent dynamic graphs. Existing work [6] mainly focuses on the dynamics of edges and outlines three typical representation methods that represent events with index \(i=1,2,\ldots\) by giving a pair of nodes \((u_{i},v_{i})\) and time \(t_{i}\):

_Contact-Sequence_[8, 6] is used to represent the instantaneous interaction between two nodes \((u,v)\) at time \(t\).

\[\textit{Contact-Sequence}=\{(u_{i},v_{i},t_{i})\} \tag{1}\]

_Event-Based_[6, 16] dynamic graphs represent edges with a time \(t_{i}\) and duration \(\Delta_{i}\). They are similar to the _Interval-Graph_ defined in [8]. The difference is that _Interval-Graph_ uses a set \(T_{e}\) of start and end times \((t_{i},t_{i}^{\prime})\) to represent all active times of the edge, rather than the duration of each interaction in _Event-Based_.

\[\textit{Event-Based}=\{(u_{i},v_{i},t_{i},\Delta_{i})\} \tag{2}\]

\[\textit{Interval-Graph}=\{(u_{i},v_{i},T_{e});T_{e}=((t_{1},t_{1}^{\prime}),(t_ {2},t_{2}^{\prime}),...)\} \tag{3}\]

_Graph Stream_[6] is often used on massive graphs [11, 10]. It focuses on edges' addition (\(\delta_{i}=1\)) or deletion (\(\delta_{i}=-1\)).

\[\textit{Graph Stream}=\{(u_{i},v_{i},t_{i},\delta_{i})\} \tag{4}\]

#### 2.0.2 Discrete Time Dynamic Graphs

Discrete-time dynamic graphs (DTDGs) can be viewed as a sequence of \(T\) static graphs as shown in Eqn. 5. They are snapshots of the dynamic graph at different moments or time-windows. DTDGs can be obtained by periodically taking snapshots of CTDGs on the time axis [9, 6].

\[\textit{DTDG}=(G^{1},G^{2},...,G^{T}) \tag{5}\]

#### 2.0.3 Equivalent Static Graphs

Representations of this category consist in constructing a single static graph, called Equivalent Static Graph (_ESG_), for representing a dynamic graph. Several methods for constructing _ESG_ have been proposed in recent years. We divide them into two categories: _edge-oriented_ and _node-oriented ESG_.

_Edge-oriented ESG_ aggregates graph sequences into a static graph with time information encoded as sequences of attributes [162, 8, 15] as shown in Fig. 3
(right top). Such representation is also called _time-then-graph_ representation [154].

_Node-oriented ESG_ builds copies of vertices at each moment of their occurrence and defines how the nodes are connected between timestamps/occurrences [162, 161, 160, 23]. A simple example is shown in Fig. 3 (right bottom), further details are discussed in subsection 3.1.

A major interest of ESG representations is that they make static graph algorithms available for learning on dynamic graph.

### Dynamic Graph Output Granularity

As said before, supervised learning aims to learn a mapping function between an input space \(\mathcal{X}\) and an output space \(\mathcal{Y}\). The previous subsection introduces the space in which a DG \(x\in\mathcal{X}\) can be represented. This subsection now discusses the space \(\mathcal{Y}\).

Since a dynamic graph involves concepts from both graph and temporal/sequential data, both aspects must be considered to define the space \(\mathcal{Y}\).

When learning a statistical model on sequential data, the input \(\mathbf{X}\) can be represented by the \(d\)-dimensional features at \(T\) time steps, denoted as \(\mathbf{X}\in\mathbb{R}^{T\times d}\). The granularity of the outputs \(\mathbf{Y}\) can be either timestep-level (one output per time step, as in _Part of speech_ tagging or more generally sequence labelling), or aggregated (one output for many inputs, as in sentiment classification or more generally sequence classification).

In static graph learning, the inputs have topological information in addition to the features \(\mathbf{X}_{V}\) and \(\mathbf{X}_{E}\). As for sequences, the outputs \(\mathbf{Y}\) can be local (one label per node or per edge) or global (one label per subgraphs or for the entire graph).

As a consequence, the output granularity when considering DG can be temporally timestep-level or aggregated, and topologically local or global.

### Transductive/Inductive on Dynamic Graphs

When learning on static graphs, transductive and inductive tasks are frequently distinguished. Transductive tasks consist in taking decision for a set \(V_{inference}\) of unlabeled nodes, the model being learnt on a set of labeled nodes \(V_{learning}\) of the same graph. In such a situation, the features and the neighborhood of nodes in \(V_{inference}\) can be exploited by the learning algorithm in an unsupervised way. That is why this situation is also called a semi-supervised learning on graphs [155]. In contrast, an inductive task is the case when there exist nodes in the \(V_{inference}\) that have not been seen during the learning phase [46]. This situation typically occurs when learning and inference are performed on different static graphs.

In the case of dynamic graphs, the evolving nature of both \(V\) and \(E\) brings more possible scenarios when considering the transductive/inductive nature of the tasks. Various configurations should be defined, considering the "degree of
dynamism" defined in section 2. We use the term "case" to distinguish between different transductive/inductive natures of dynamic graph learning taking into account the degree of dynamism.

Specifically, we divide learning on dynamic graphs into five cases:

* _Trans-fix\({}_{V,E}\)_ (1) : in this case, the topology of the DG is fixed, \(V\) and \(E\) are therefore the same on the learning and inference sets.
* _Trans-fix\({}_{V}\)_ (2) : in this case, the learning and inference node sets are fixed and equal but the edge set evolves, which requires taking into account the evolving connectivity between nodes on the graph.
* _Trans-vary_ (3) : in this case, \(V_{learning}^{t}\) and \(V_{inference}^{t}\) may evolve over time, but the presence of each node to be predicted in the test set are already determined in the learning phase : \(\forall v\in V_{inference},v\in DG_{learning}\).
* _Ind\({}_{V}\)_ (4) : this case refers to node-level inductive tasks, where the learning and inference are on the same DG, but \(\exists v\in V_{inference},v\notin DG_{learning}\). Although the label and historical attributes from the learning phase can be reused on the inference set, a major challenge is to handle the unseen nodes and the uncertain number of nodes.
* _Ind\({}_{DG}\)_ (5) : this case refers to DG-level inductive learning, where learning and inference are performed on different DGs. The statistical model needs to handle the complete unseen dynamic graphs.

These 5 cases are illustrated in Fig. 4.

Figure 4: The transductive and inductive cases in dynamic graph learning under discrete time: (1) denotes the case where both the node set and edge set are fixed in learning and inference. (2) denotes the case where only the node set is fixed for learning and inference. (3) denotes the case where the node set changes but no unseen node appears for inference. (4) denotes the inductive case where the train and test are on the same DG but there are new nodes for inference. (5) denotes the inductive case where there are new DGs for inference.
### Dynamic Graph Predictive Tasks

In the previous subsections, we have investigated dynamic graph learning specificities related to the representations of the input (discrete vs. continous time), the granularity of the output (local vs. global, timestep-based vs. aggregated), and different learning _cases_. In this section, we categorize existing contributions in the literature according to these four criteria.

Table 2 gives a synthetic view of this categorization with an emphasis on the targeted applications and on the metrics used for assessing models performance.

As one can see in this table, in **Discrete Time Transductive Tasks**, related applications usually concern relatively stationary topologies, i.e. _Transfix\({}_{V,E}\)_, such as human body structure or geographic connectivity. Some typical node-level/local tasks predict attributes for the next time step(s) based on past time step(s), such as traffic flow [94, 80, 83, 84, 73], number of infectious disease cases [69, 77, 67], number of crimes [70] and crop yields [91]. Graph-level/global tasks either retrieve the class of each snapshot like sleep stage classification [95] or output a prediction for the entire DG such as the emotion of a skeletal STG [71]. When the DG has a fixed set of nodes with evolving edges, i.e. _Trans-fix\({}_{V}\)_, such _cases_ can be employed for modelling the connectivity in the telecommunication network [100] or contact of individuals in a conference [124].

In **Discrete Time Inductive Tasks**, i.e. when unseen nodes need to be predicted in discrete time i.e. _Ind\({}_{V}\)_, some typical tasks concerns node classification [96] or link prediction [96, 124, 97] for future snapshots in social networks. An example of _Ind\({}_{DG}\)_ with graph-level output is classifying real and fake news based on the snapshots of its propagation tree on the social network [86, 76, 68].

Dynamic graphs in **Continuous Time** are widely used to model massive dynamic graphs that frequently have new events, such as recommendation systems [85, 82, 92] or social networks in the transductive _cases_[110, 121] or inductive _cases_[108, 96, 109, 113, 106]. Local tasks predict the properties and interactions of seen or unseen nodes, under transductive and inductive _cases_, respectively. Since CTDGs have no access to global/entire graph information under their minimum time unit, the global timestep level label is meaningless under continuous time. However, global aggregated tasks can be implemented by aggregating nodes of different time steps, such as rumour detection in continuous time [107]. Since CTDG can be transformed to DTDG by periodically taking snapshots [9, 6], the above tasks can also be considered as tasks under dynamic time with a lower time resolution.

To evaluate the performance of a statistical model on a given task, traditional machine learning metrics are employed as shown in table 2. When the output predictions are discrete values, i.e. for **classification** task [108, 96, 109, 107, 106], common metrics include accuracy, precision, recall, F1, and area under the receiver operating characteristic (AUROC). When the output values are continuous values, i.e. for **regression** task [94, 80, 83], common metrics are mean absolute (percentage) error, root mean square (log) error, correlation, and R squared. **Node ranking** tasks [82, 92] predict a score for each node and then sort them. These tasks can be evaluated by the reciprocal rank, recall@N, cumulative gain
and their variants. Note that dynamic tasks are generally evaluated using static metrics computed along the time axis.

## 3 Dynamic Graph Embedding with Neural Networks

In the previous section, we have introduced various DG predictive tasks settings and we have categorized literature contributions according to these settings. In this section, we now take the model point of view, by describing how DGNN embed dynamic graphs into informative vectors for subsequent predictions.

We first introduce the general idea of dynamic graph embedding in the context of the different learning tasks mentioned in subsection 2.5. We then dive into different embedding approaches, by categorizing them according to the strategy used for handling both temporal and structural information. Finally, we present the methods for handling heterogeneous dynamic graphs.

From an encoder-decoder perspective, a deep learning statistical model first maps the original input into embeddings denoted as \(\mathbf{Z}\), and then exploits \(\mathbf{Z}\) to predict an output [12, 4]. Graphs can be embedded either at node/edge-level or at (sub)graph-level [13, 5]. Node-level embedding benefits a wide range of node-related tasks and allows more complete input information to be retained for later computation [5]. In the same way, time-step level embedding retains more information than time-aggregated embedding Similarly when learning on sequential data [7].

As a consequence, embedding a dynamic graph at its finest granularity consists in computing a \(d\)-dimensional vector representation \(\mathbf{z}_{v}^{t}\in\mathbb{R}^{d}\) for each node \(v\in V\), at all time steps \(t\in T\). In this case, the embedding of the dynamic graph is given by \(\mathbf{Z}\in\mathbb{R}^{|V|\times|T|\times d}\), as shown in Fig. 5.

However, the different input time granularity and learning settings mentioned in the previous section do not always enable such an "ideal" embedding \(\mathbf{Z}\). In this subsection, we generalise the practicable embeddings under these different settings as shown in Fig. 6 and Tab. 3.

For discrete time transductive settings, when the node set is constant, (i.e. for _cases_ (1) [80, 83, 71] and (2) [96, 97, 88]), the input nodes can be encoded at the

Figure 5: The most fine-grained node embedding \(\mathbf{Z}\in\mathbb{R}^{|V|\times|T|\times d}\), where \(|V|\) is the number of nodes, \(|T|\) is the number of timesteps, and \(d\) is the dimension of embedding \(z_{v}^{t}\) of a single node \(v\) at a single timestep \(t\).
finest granularity \(\mathbf{Z}\in\mathbf{R}^{|V|\times|T|\times d}\) since all the nodes are known during learning, as shown in Fig. 5. When the DTDG node set changes across snapshots in a transductive task (i.e. for _case_ (3) [93; 78; 102]), the nodes can still be encoded in the shape of \(|V|\times|T|\times d\), where \(|V|\) denotes the cardinal of the universal node set [78], by filling the missing values. An example of filling the missing values with \(\mathbf{0}\) vectors [93] is shown in Fig. 6 (A) for node C at \(t_{1}\) and node A at \(t_{3}\).

For discrete time inductive settings (i.e. for _cases_ (4) \(Ind_{v}\)[103; 105] and (5) \(Ind_{DG}\)[86; 76; 68]) the predictor cannot determine the existence of a node until it appears. This case is illustrated on Fig. 6 (B) where the predictor cannot determine the existence of node C until it appears at \(t_{4}\). Hence, \(|V^{t}|\) can vary at each timestep \(t\). Therefore, the embedding of nodes in the inference set cannot be represented in the shape of \(|V|\times|T|\times d\). In this situation, one can use a list to store the representations of all accessible time steps for each node seen [105], e.g. \(\mathbf{Z}=\left\{\mathbf{Z}^{1},\mathbf{Z}^{2},\ldots,\mathbf{Z}^{T}\right\}\) with \(\mathbf{Z}^{t}\in\mathbb{R}^{|V|_{t}\times d}\) for \(t\in\{1,\ldots,T\}\).

In continuous time, there is no longer a time grid, as shown in Fig. 6 (C & D). Therefore, there are no longer embedding updates for all nodes at each time step. Instead, when an event occurs on the CTDG, either the embeddings of the associated nodes are updated or the embedding(s) of the unseen node(s) are added [108; 109].

Figure 6: The available most fine-grained embedding under different dynamic graph learning settings.
To informatively encode dynamic graphs into tensors or a list of vectors, a DGNN must capture both the structure information and their evolution over time. Therefore, to handle topology and time respectively, DGs are often decomposed or transformed into components like equivalent static (sub)graphs [74, 89, 75], random walks [113, 124, 123, 121, 122], or sequences of matrices [95, 86, 93]. In the literature, numerous approaches have emerged by combining different encoders \(f_{G}(\cdot)\) for static graphs with \(f_{T}(\cdot)\) for temporal data. A plethora of graph and temporal data encoders have been at the root of the DG encoders reviewed in the section. These encoders are described in appendices B and C.

In the following subsections, we present a taxonomy of DGNN models which relies on five categories. Our categorization, illustrated in Figure 7, is based on the strategy for handling both temporal and structural information.

1. Modelling temporal edges and encoding _ESG via topology_, denoted as \(TE\) (Section 3.1).
2. Sequentially encoding the hidden states, denoted as \(enc(\mathbf{H})\) (Section 3.2).
3. Sequentially encoding the DGNN parameters, denoted as \(enc(\Theta)\) (Section 3.3).
4. Embedding occurrence time \(t\) as edge feature of _ESG via attributes_, denoted as \(emb(t)\) (Section 3.4).
5. Sampling causal walks, denoted as \(CausalRW\) (Section 3.5).

Note that these five approaches are not exclusive, i.e. they can be combined and used on the same DG.

### Temporal Edge Modeling

Since applying convolution on a static graph is generally easier than encoding across multiple snapshots, the DG encoding problem is frequently transformed into encoding a static graph where each node is connected to itself in the adjacent snapshot [74, 89]. This approach can also be interpreted as constructing a _time-expanded graph_[162, 161, 160] or _node-oriented ESG_ (see section 2.2.4) and is widely used to encode _Trans-fix\({}_{V,E}\)_ cases, i.e. STGs. In more complex configurations, nodes are also connected with their k-hop neighbours in the adjacent snapshot(s) [69].

A simple example of such a strategy is shown in fig. 8. An equivalent static graph \(G^{\prime}=\{V^{\prime},E^{\prime}_{S},E^{\prime}_{T}\}\) is obtained by modelling temporal edges [74]. \(G^{\prime}\) has

\begin{table}
\begin{tabular}{|c|c|c|} \hline DG Learning Case[(1)] (Trans-\(fix_{V,E}\))[(2)] (Trans-\(fix_{V}\))[(3)] (Trans-\(\mathit{vary}\)) & (4) Ind\({}_{V}\)[(5)] Ind\({}_{DG}\) \\ \hline Discrete Time & (A) & (B) \\ \hline Continuous Time & (C) & (D) \\ \hline \hline \end{tabular}
\end{table}
Table 3: The available finest embedding granularity under various dynamic graph learning cases.
\(|V^{\prime}|=|V|\times T\) nodes and \(|E^{\prime}_{S}|=|E|\times T\) spatial edges. Depending on the modelling approach, the number of temporal edges \(|E^{\prime}_{T}|=|V|\times(T-1)\) can be greater.

Once defined the connection rule for temporal edges, the traditional convolution for static graphs is applicable on ESGs. A state-of-the-art example is the **ST-GCN** module [89]. To update the hidden states \(h\) to \(h^{\prime}\) in an ST-GCN layer (see Eqn. 6), a typical spatial GNN structure aggregates the neighbour features with the \(\text{msg}(\cdot)\) function, computes their weights by the \(\text{w}(\cdot)\) function, and then sums them after normalisation with the \(\text{norm}(\cdot)\) function. Note that, unlike the neighbourhood definition in static graphs, the neighbourhood set \(\mathbf{N}\) of \(v^{t}_{i}\) is defined by: (1) spatially, the shortest path distance with neighbour \(v_{j}\) obeys \(d(v_{j},v_{i})\leq K\) and (2) temporally, the time difference between timestamps \(q\) and \(t\), i.e. \(|q-t|\) is not greater than \(\lfloor\Gamma/2\rfloor\).

Figure 8: Comparing snapshot representation (left) and STG with temporal edges (middle) [74]. The edges in blue indicate temporal edges. In ST-GCN module (right) [89], temporal edges also connect nodes with their K-hop neighbours in the adjacent \(\Gamma/2\) snapshot(s), thus the light green area shows the neighbourhood of the orange node while applying spatial-temporal graph convolution with K=1 and \(\Gamma\)=3.

Figure 7: Dynamic graph neural network taxonomy on temporal information processing: 1. **Temporal Edge Modeling** models temporal edges to transform STGs into static graphs. 2. **Sequentially Encoding Hidden States H** encodes the hidden states of each snapshot across time with a temporal encoder \(f_{T}(\cdot)\). 3. **Sequentially Encoding Parameters \(\Theta\)** encodes the parameters \(\Theta\) of the graph encoder \(f_{G}(\cdot)\) across time with a temporal encoder \(f_{T}(\cdot)\). 4. **Embedding Time \(t\)** converts time values to vectors and concatenates or adds them to the attribute vectors when encoding node B. 5. **Causal Walks** restricts the random walks on dynamic graphs by causality.
\[h_{i}^{{}^{\prime}t} = \sum_{v_{j}^{t}\in\mathbf{N}_{v_{i}^{t}}}\mathbf{norm}\left(\mathbf{ msg}(h_{i}^{t},h_{j}^{t})\cdot\mathbf{w}(h_{i}^{t},h_{j}^{t})\right)\] \[\mathbf{N}_{v_{i}^{t}} = \left\{v_{j}^{q}|d(v_{j}^{t},v_{i}^{t})\leq K,|q-t|\leq\left\lfloor \Gamma/2\right\rfloor\right\} \tag{6}\]

### Sequentially Encoding Hidden States H

In DTDGs, there are usually additions/deletions of edges or nodes [96, 100, 124, 97]. To deal with these topological changes, this category denoted as \(enc(\mathbf{H})\) uses \(f_{G}(\cdot)\) and \(f_{T}(\cdot)\) to encode the graph and time domains alternatively. \(Enc(\mathbf{H})\) is widely applied to the Trans-\(fix_{V,E}\)_case_, i.e. STGs [71, 94, 80, 83, 84, 73, 91] and the Trans-\(fix_{V}\)_cases_ on DTDGs [96, 100, 124, 97]. \(f_{T}(\cdot)\) either encodes each snapshot across time after \(f_{G}(\cdot)\) encodes each snapshot [93, 78, 79], i.e., in a stacked way [6], or incorporates graph convolution when encoding each snapshot across time [79, 88, 83], i.e., in an integrated way [6].

When the input is an STG, rather than processing them as static graphs, this approach factorises space and time and processes them differently [80, 94, 98, 99, 91, 77, 81, 95, 83]. **RSTG**[98] and **DyReG**[99] first encode each snapshot at node-level with weighted message passing as \(f_{G}(\cdot)\), and then encode each node over time using LSTM or GRU as \(f_{T}(\cdot)\). Both approaches are of the stacked fashion.

If the node set \(V_{t}\) of a DTDG is constant, then this DTDG is equivalent to an STG only with an additional change in the edge set \(E_{t}\), i.e. Trans-\(fix_{V}\)_case_. Therefore, the stacked architecture mentioned in the previous paragraph is equally practicable. A typical example is **CD-GCN**[93] that concatenates the attributes and the adjacency matrix for each snapshot \(t\) to form input \(X^{t}||A^{t}\). Each snapshot is first encoded by GCN to obtain the node-level topological hidden states \(\mathbf{z}_{i,\textit{GCN}}^{t}\), and then encoded by LSTM in the time dimension to obtain \(\mathbf{z}_{i,\textit{LSTM}}^{t}\). Finally, an MLP maps the concatenation of the hidden states and raw features to the final node-level hidden states \(\mathbf{z}_{i}^{t}\) for each time step. Similar structures which stack temporal encoder \(f_{T}(\cdot)\) after graph encoder \(f_{G}(\cdot)\) are **STGCN**[80], **GraphSleepNet**[95], **E-LSTM-D**[90], **Graph WaveNet**[94], **GRNN**[84]. A simple example is shown in Eqn. 7, as a matter of fact, they can be stacked in more complex ways, see tab 4 for more details.

\[\mathbf{Z}^{t}=f_{T}\left(f_{G}(\mathbf{X}^{t})\right)\text{, or }f_{T}(\mathbf{X}^{t})\oplus f_{G}(\mathbf{X}^{t}) \tag{7}\]

Another strategy for sequentially encoding the hidden states incorporates \(f_{G}(\cdot)\) into \(f_{T}(\cdot)\) rather than stacking them. Since there are usually projection or convolution modules in \(f_{T}(\cdot)\) to handle the features of nodes, this "integrated mode" turns these modules into \(f_{G}(\cdot)\) to aggregate neighbouring features. **GVRN-M2**[79] replaces the 2D convolution in convLSTM with graph convolution. Similar examples are **GC-LSTM**[88] and **DCRNN**[83] which replace the linear layer in LSTM and GRU with respectively GCN[41] and diffusion convolution [25].
To deal with the addition/deletion of nodes in a transductive nature, i.e. \(Trans_{vary}\)_case_, one needs to handle \(|V_{t}|\) which may change across snapshots. **TNDCN**[78] proposes to set a universal node set \(V=\cup V_{t}\) to ensure that \(|V|\) is the same for each snapshot, which transforms the transductive _case_ into a node set-invariant _case_ on DTDG.

In the inductive case, one cannot presume \(|V|\) to set the universal node set, which brings about an inconsistent number of nodes in each snapshot making \(f_{T}(\cdot)\) impossible to encode at the node level. Therefore, this method in inductive tasks is only applicable for encoding graph-level representations across time, e.g. fake news detection based on its propagation tree. **Dyn-GCN**[86] applies Bi-GCN [87] to encode the hidden states \(\mathbf{z}_{G_{t}}\) for each snapshot \(t\) by aggregating the hidden states of its nodes and edges, and passes \((\mathbf{z}_{G_{1}},\mathbf{z}_{G_{2}},\ldots,\mathbf{z}_{G_{T}})\) into an attention layer to compute the final hidden states of the entire DG.

### Sequentially Encoding Parameters \(\boldsymbol{\Theta}\)

Although \(enc(\mathbf{H})\) is relatively intuitive and simple in terms of model structure, the problem is that they can neither handle the frequent changes of the node set, especially in the inductive tasks, nor pass learned parameters of \(f_{G}(\cdot)\) across time

\begin{table}
\begin{tabular}{l r r r r r} \hline \hline Model & Task case & Structure & Graph & Temporal & Embedded & Ref. \\  & & & Encoding & Encoding & Object & \\ \hline DyReg & Trans-fix\({}_{V,E}\) & stacked & GNN & GRU & Node & [99] \\ RSTG & Trans-fix\({}_{V,E}\) & stacked & GNN & LSTM & Node & [98] \\ STAGIN & Trans-fix\({}_{V,E}\) & stacked & GIN & Transformer & Graph & [81] \\ GraphSleepNet & Trans-fix\({}_{V,E}\) & stacked & GNN & TCN & Graph & [95] \\ GNN-RNN & Trans-fix\({}_{V,E}\) & stacked & GNN & LSTM & Node & [91] \\ Graph WaveNet & Trans-fix\({}_{V,E}\) & stacked & GNN & TCN & Node & [94] \\ STGCN & Trans-fix\({}_{V,E}\) & stacked & GNN & TCN & Node & [80] \\ DCRNN, GCRNN & Trans-fix\({}_{V,E}\) & integrated & GNN & GRU & Node & [83] \\ USSTN & Trans-fix\({}_{V,E}\) & stacked & GNN & MLP & Node & [77] \\ GRNN & Trans-fix\({}_{V,E}\) & stacked & GNN & Gated RNN & Node & [84] \\ GCRN-M1 & Trans-fix\({}_{V,E}\) & stacked & GNN & LSTM & Node & [79] \\ GCRN-M2 & Trans-fix\({}_{V,E}\) & integrated & GNN & LSTM & Node & [79] \\ \hline tNodeEmbed & Trans-fix\({}_{V}\) & stacked & RW OP \& LSTM & Node & [96] \\ DynSEM & Trans-fix\({}_{V}\) & stacked & RW & OP & Node & [97] \\ GC-LSTM & Trans-fix\({}_{V}\) & integrated & GNN & LSTM & Node & [88] \\ LRGCN & Trans-fix\({}_{V}\) & stacked & GNN & LSTM & Path & [100] \\  & & & & & (set of edges) & \\ E-LSTM-D & Trans-fix\({}_{V}\) & stacked & AE & LSTM & Node & [90] \\ WD-GCN, CD-GCN & Trans-vary & stacked & GNN & LSTM & Node & [93] \\ TNDCN & Trans-vary & stacked & GNN & TCN & Node & [78] \\ ANOMULY & Trans-vary & stacked & GNN & GRU & Node & [102] \\ \hline Dyn-GCN & Ind\({}_{DG}\) & stacked & GNN & Attention & Graph & [86] \\ DDGCN & Ind\({}_{DG}\) & stacked & GNN & Temporal & Graph & [76] \\  & & & & Fusion & & \\ \hline \hline \end{tabular}
\end{table}
Table 4: Main components of selected (DT)DGNNs which sequentially encode hidden states. Without specification, GNN refers to graph convolution or message passing, OP refers to Orthogonal Procrustes [26], TCN refers to temporal convolution and its variants, Attention refers to the attention mechanism [35], AE refers Autoencoder and its variants, and RW refers to Random Walk-based approaches [55, 53, 54].
steps [103]. To encode DTDGs more flexibly, some other approaches constraint or encode the parameters of \(f_{G}(\cdot)\) across time steps [104, 105, 103].

In order to encode the parameters \(\Theta\) of GCN, **EvolveGCN**[103] proposes to use LSTM or GRU to update the parameters of the GCN model at each time step as shown in eqn. 8 and eqn. 9:

\[\Theta_{f_{G}}^{t}=\text{LSTM}(\Theta_{f_{G}}^{t-1}) \tag{8}\]

\[\Theta_{f_{G}}^{t}=\text{GRU}(\mathbf{H}^{t},\Theta_{f_{G}}^{t-1}) \tag{9}\]

Otherwise, by constraining the GNN parameters, **DynGEM**[104] incorporates autoencoder (AE) to encode and reconstruct the adjacency matrix of each snapshot. Its parameters \(\Theta_{t}\) are initialized with \(\Theta_{t-1}\) to accelerate and stabilize the model training. Similarly, in **VGRNN**[105] the authors combine GRNN and a variational graph AE in order to reuse learned hidden states of \(t^{-}\) to compute the prior distribution parameters of the AE.

### Embedding Time \(t\)

When the scale of the dynamic graph is large, as in social networks and recommendation systems, aggregation to snapshots is neither precise nor efficient [6, 9]. Its evolution is thus represented by a set of timestamped events. Therefore, when encoding a CTDG, one should consider not only how to asynchronously update the node representations over time, but also to define the neighbours of nodes.

The DGNNs presented in this subsection update the representation of a node \(v\) when it changes, i.e. when it participates in a new edge or when its attributes change. Its neighbours at moment \(t\), also called _temporal neighbourhood_, are usually defined as the nodes that have common edges with \(v\) (before \(t\)) [109]. Thus, such models consider \(v\)-centric equivalent static subgraph as shown in Fig. 9. In such cases, the occurrence time of each edge can be considered as part of the edge attributes or used as weight for graph convolution.

**TDGNN**[110] proposes a weighted graph convolution by assuming that the earlier an edge is created, the more weight this edge will have in aggregation, as

Figure 9: To aggregate information of neighbours on a dynamic graph, for example, to encode the pink node, the nodes with which it has an edge, i.e. its _temporal neighbours [75]_ (yellow, orange, purple nodes) and the temporal information (in blue) are embedded as vectors. This can also be interpreted as constructing a _equivalent static graph_ via attributes.
shown in Equ. 10. In more detail, the weight \(\alpha_{u,v}^{t}\) of an edge \((u,v)\) at moment \(t\) is calculated by the softmax of the existence time \(t-t_{u,v}\) of the edge.

\[\alpha_{u,v}^{t}=\frac{e^{t-t_{u,v}}}{\sum_{u\in N_{t}(v)\cup v}e^{t-t_{u,v}}} \tag{10}\]

On the other hand, **TGAT**[109] embeds the value of the existence time \(t-t_{(u,v)}\) of edge \((u,v)\) as a vector of \(d_{T}\) dimensions and then concatenates it to the node \(v\)'s hidden states \(\mathbf{z}_{v}^{t}\). When aggregating neighbour information for a node \(v\), the weight of each neighbour is computed by multi-head attention (Eqn. 11). Similar methods has also been applied for time embedding in Dynamic Graph Transformers [111, 112].

\[\mathrm{q(t)} =[\mathrm{Z(t)}]_{0}\mathrm{W_{Q}}\] \[\mathrm{K(t)} =[\mathrm{Z(t)}]_{1:\mathrm{N}}\mathrm{W_{K}}\] \[\alpha_{u,v}^{t} =\frac{\exp\left(q_{v}^{T}k_{u}\right)}{\sum_{u\in N_{t}(v)}\exp \left(q_{v}^{T}k_{u}\right)} \tag{11}\]

To better reuse the messages aggregated for each node by TGAT, **TGN**[108] adds a memory mechanism which memorizes the historical information for each node \(v\) with a memory vector \(\mathbf{s}_{v}\). This memory is updated after each time \(t\) a node \(v\) aggregates its neighbours' information \(\mathbf{m}_{v}^{t}\).

\[\mathbf{s}_{v}^{t}=\mathrm{MLP}(\mathbf{m}_{v}^{t},\mathbf{s}_{v}^{t-}) \tag{12}\]

Similar to TGN, **TGNF**[107] embeds nodes and time information via TGAT[109], and then updates the node's memory \(\mathbf{S}\) via the temporal memory module (TMM). In order to learn variational information better, it calculates the similarity \((\mathbf{S}_{t},\mathbf{S}_{t^{-}})\) of the memory \(\mathbf{S}\) at \(t\) and \(t^{-}\) during training as part of the loss, called Time Difference Network (TDN).

Some other approaches consider the interaction predictions on the graph as a Temporal Point Problem (TPP [24]) and simulate the conditional intensity function that describes the probability of the event. **DyRep**[106] encodes a strength matrix \(\mathbf{S}\in R^{|V|\times|V|}\) to simulate the intensity function of the interactions between each node pair and uses \(\mathbf{S}\) as the weights for graph convolution. \(\mathbf{S}\) is initialized by the adjacency matrix \(\mathbf{A}\) and updated when an interaction \((u,v)\) occurs at time \(t\). In this case, the embedding of each node involved is updated. For example, the update of \(v\) is the sum of the three embedding components given by Eqn. 13: the latest embedding of \(v\), the aggregation of embeddings of \(u\)'s neighbor nodes, and the time gap between \(v\)'s last update and this update.

\[\mathbf{z}_{v}^{t}=\sigma\left(\mathbf{W}_{1}\mathbf{h}_{\mathrm{N}(u)}^{t^{ -}}+\mathbf{W}_{2}\mathbf{z}_{v}^{t^{-}}+\mathbf{W}_{3}(t-t^{-})\right) \tag{13}\]

All of the models mentioned above embed timestamps or time-gaps as part of the features. However, models such as TGAT are unable to capture accurate
changes in structure without node features [113]. As discussed above, DyREP [106] solves this problem but is unable to perform the inductive task as it relies on the intensity matrix \(\mathbf{S}\). This raises another challenge: How to learn in an inductive task based only on the topology when the nodes have no features.

### Causal Random Walks

Random walk-based approaches do not aggregate the neighbourhood information of nodes, but sample node sequences to capture the local structure. To incorporate time information to the random walks, different ways of defining "causal walks" on dynamic graphs are derived.

To sample random walks with temporal information in discrete time, an intuitive way is to convert the DTDG into a directed static graph. Huang et al. [115] construct a _ESG via topology_, and allow random walks to sample inside the current layer (/timestep) to get the structural information or walk into the previous layer to obtain historical evolving information. Following the supra-adjacency representation (see fig. 10), **DyAne**[124] applies the random walk approach of static graphs (DeepWalk [53] and LINE [55]) to DTDGs. Otherwise, without using these representations, **LSTM-node2vec**[123] directly samples one neighbouring node of a target node \(v\) per snapshot as a walk.

Similar to the method based on supra-adjacency, the walks obey causality under continuous-time, i.e. after walking from node B to node C via an edge occurring at \(t2\), node C can only walk to the next node via an edge having occurring time \(t>t2\) (Fig. 11).

Some early methods are **CTDNE**[121] and **T-Edge**[122]. To encode a node \(v\), they both sample the causal walks starting from \(v\), each walk \(W\) being a sequence of (node, time) pairs. Then they embed each (node, time) pair and encode the sequence \(W\) by \(f_{T}(\cdot)\) like RNNs. Combined with anonymous walk embedding, Causal Anonymous Walks (**CAW**[113]) anonymise nodes and their attributes in order to focus more on graph motifs, which solve the problem at the end of Sec. 3.5.

Figure 10: Supra-adjacency representation: treating discrete time dynamic graphs as directed static graphs for sampling random walks.
### Encoding Heterogeneous Graphs

Since heterogeneous graphs can maintain more informative representations in tasks like link prediction in recommendation systems, a key challenge is to have a dedicated module for handling different types of nodes and edges on dynamic graphs. We introduce in the following paragraphs two main approaches as illustrated in Fig. 12.

GNN-based models keep the same dimension \(d\) of embedding for different node types (e.g. for user nodes and item nodes) to facilitate computations. For example, to update the node embeddings when user \(u\) and item \(i\) have a connection \(e_{u,i}^{t}\) at time \(t\), **JODIE**[92] embeds the user attributes \(\mathbf{x}_{u}\), the item attributes \(\mathbf{x}_{i}\), the edge attributes \(\mathbf{x}_{e}\) and the time difference since the last update \(\Delta\) to the same dimension \(d\) and then adds them together :

\[\mathbf{h}_{u}^{t}=\sigma\left(\mathbf{W}_{1}^{u}\mathbf{h}_{u}^{ t^{-}}+\mathbf{W}_{2}^{u}\mathbf{h}_{i}^{t^{-}}+\mathbf{W}_{3}^{u}\mathbf{h}_{e}^ {t}+\mathbf{W}_{4}^{u}\Delta_{u}\right)\] \[\mathbf{h}_{i}^{t}=\sigma\left(\mathbf{W}_{1}^{i}\mathbf{h}_{i}^ {t^{-}}+\mathbf{W}_{2}^{i}\mathbf{h}_{u}^{t^{-}}+\mathbf{W}_{3}^{i}\mathbf{h}_ {e}^{t}+\mathbf{W}_{4}^{i}\Delta_{i}\right) \tag{14}\]

where \(t^{-}\) refers to the timestamp of the last update thus \(\Delta=t-t^{-}\), and \(h_{i}^{t}=x_{i}^{t}\) for the first layer of model. **DMGCF**[85] and **DGCF**[82] also use similar approaches for same dimensional embedding.

RW-based methods deal with heterogeneous graphs by defining metapaths [57] which specifies the type of each node in the walk, such as (user, item, user), so that each random walk sampled (also called "instance") with the same metapath can be projected to the same vector space. Examples on the dynamic graph are **THINE**[114] and **HDGNN**[119] which sample instances and encode them through the attention layer and bidirectional RNN layers, respectively.

So far we have presented a wide variety of approaches to capture time and graph dependencies within dynamic graphs. In the next section, we discuss their global success and limitations, as well as present guidelines for the design of DGNN architectures.

Figure 11: Schematic diagram on sampling casual walks on a CTDG, the right part shows graph pattern extracted by anonymizing nodes.
## 4 Guidelines for Designing DGNNs

In the previous sections, we have highlighted the diversity of contexts which can be encountered when considering machine learning on dynamic graphs, as well as the diversity of existing models to tackle these problems. In this section, we present some guidelines for designing DGNNs on the basis of the taxonomies presented in section 2 and 3. We also discuss the latest trends for optimizing DGNNs. To the best of our knowledge, while such guidelines have already been proposed for static graphs [125], they do not exist for DGNNs.

### General Design Workflow of DGNNs

For static graphs, Zhou et _al._[125] described the GNN design pipeline as: _i)_ determine the input graph structure and scale, _ii)_ determine the output representation according to the downstream task, and _iii)_ add computational modules.

For dynamic graphs, the design of DGNN has to consider more factors. We therefore generalize the workflow of designing DGNN as follows :

1. Clearly define the input, output and nature of the task, according to the taxonomies of section 2 ;
2. Choose the compatible time encoding approach according to the learning setting, using the categorizations of section 3 and more precisely the Table 5 ;

Figure 12: Handling heterogeneous nodes. Above: embedding them into the same vector space (e.g. with \(d=5\)). Below: sampling random walks with defined metapaths.
3. Design NN structure ;
4. Optimise the DGNN model.

The key points in the DGNN compatibility are the input time granularity, the nature, and the object to be encoded. We concluded their known adapted DG types and listed them in table 5 and describe the various cases in this subsection.

Transductive tasks under discrete time, as a relatively simple setting, can be encoded with any approach to incorporate time information. In the setting of inductive DT, no approach using _TE_ is found in the literature, and the method of \(enc(\mathbf{H})\) must also have its output aggregated because of the gap mentioned in sections 3.2, e.g. node-level time-aggregated or graph-level time-step. To handle continuous time, only _emb(t)_ and _Causal RW_ are widely used in the literature.

Once the approach has been selected, the next step is to add the computational components, which are very different for each approach.

For the first three methods mainly used in discrete time, i.e., \(\circled{1}TE\), \(\circled{2}Enc(\mathbf{H})\), and \(\circled{3}Enc(\Theta)\), they can be abstracted to encode graph and time information via \(f_{G}(\cdot)\) and \(f_{T}(\cdot)\), respectively. These neural network components are usually some of the modules introduced in the appendices B, C and Tab. 4. In particular, the encoding of temporal edges in the \(TE\) approach can be performed by \(f_{G}(\cdot)\) without a specific \(f_{T}(\cdot)\). In \(enc(\mathbf{H})\) approach, there are more possible ways to combine \(f_{G}(\cdot)\) and \(f_{T}(\cdot)\) (stacked, integrated, etc.). In \(enc(\Theta)\) approach, the key is how \(f_{T}(\cdot)\) acts on the parameters of \(f_{G}(\cdot)\).

For the time embedding approach \(\circled{4}\)_emb(t)_, in addition to the method of aggregating information of neighbours i.e. \(f_{G}(\cdot)\), one also needs to consider the function for time embedding (e.g. by a set of sine or cosine functions [109] or a learnable linear layer [106]) and how to combine them to the hidden states of edges or nodes (e.g. by addition or concatenation). In the situation where the past representation of a node is stored [107; 108; 106], one also needs to determine the module used to update the node representation, i.e. \(f_{T}(\cdot)\).

\begin{table}
\begin{tabular}{l l l l} \hline \hline Approach & DT & Trans. & DT & Ind. & CT \\ \hline \(\circled{1}\) & TE & ✓ & & \\ \(\circled{2}\) & Enc(H) & ✓ & \(*\) & \\ \(\circled{3}\) & Enc(\(\Theta\)) & ✓ & ✓ & \\ \(\circled{4}\) & Emb(t) & ✓ & ✓ & ✓ \\ \(\circled{5}\) & Causal RW & ✓ & ✓ & ✓ \\ \hline \hline \end{tabular}
\end{table}
Table 5: Adapted dynamic graph types of each method:

**TE** stands for ”Temporal Edge Modeling”, **Enc(H)** for ”Sequentially Encoding Hidden States”, **Enc(\(\Theta\))** for ”Sequentially Encoding Model Parameters”, **Emb(t)** for ”Embedding time”, **Causal RW** for ”Causal Random Walks”. \(\checkmark\) means ”applicable”, \(*\) means ”applicable with output restrictions”, and no symbol indicates that it is not yet used in the literature.
For random walk-based method (c) _Causal RW_, one needs to determine the random walk sampling strategy as well as the method for encoding the sampled walks, typical walk-encoding strategies are [54, 53, 55, 56].

Last but not least, in the case of heterogeneous graphs, an additional vector projection or setting of metapaths has to be considered.

### Trends in Optimising DGNNs

With the development of artificial neural networks and the continuous emergence of new structures over the last five years, questions have been raised about the optimisation of DGNNs. Apart from general neural network training issues (overfitting, lack of data, vanishing gradient, etc.), a main issue for GNN is over-smoothing [133, 132, 134]: if the number of layers and iterations of a GNN is too large, the hidden states of each node will converge to the same value. The second main challenge is over-squashing [135, 136, 137]: if a node has a very large number of K-hop neighbours, then the information passed from a distant node will be compressed and distorted.

To overcome the above problems, numerous methods have been proposed. According to us, general trends to improve DGNN can be categorised as (1) Input oriented, (2) DGNN component oriented, and (3) DGNN structure oriented.

#### 4.2.1 Input Oriented Optimisation

To avoid overfitting when learning graph representations, two main issues related to the DG need to be considered: the noise in topology (e.g. missing or incorrect links) and the noise in the attributes (e.g. incorrect input attributes or output labels) [128, 129].

Since there may be pairs of similar nodes in the graph that should be connected but are not (due to geographical constraints, missing data, etc.), some approaches aim to exploit more informative graph structure or to augment attribute data.

For discrete time, an example is **ST-SHN**[70] for crime prediction. Considering each region as a node and its geographical connectivity as an edge, ST-SHN infers the hyper-edges connecting multiple regions by learning the similarity of hidden states between node pairs. These hyper-edges help to learn cross-region relations to handle the global context.

For continuous time, such as heterogeneous graph-based recommendation systems, **DMGCF**[85] constructs two additional homogeneous graphs \(G_{u}\) for users and \(G_{i}\) for items based on the known user-item graph \(G_{ui}\). Then two GCNs are used to aggregate information on \(G_{u}\cup G_{i}\) and \(G_{ui}\) respectively to learn more informative node embeddings.

Noise in attributes can also lead to overfitting DGNNs, therefore adaptive data augmentation is another direction for input-oriented improvement. Wang _et al._ proposed Memory Tower Augmentation (**MeTA**[126]) for continuous time data augmentation by perturbing time, removing edges, and adding edges with perturbed time. Each augmentation has learnable parameters to better adapt to different input data.
#### 5.2.2 DGNN Component Oriented Optimisation

To solve the over-smoothing and over-squashing problems on graphs, the improvement of the DGNN modules focuses on a more versatile message propagation and a more efficient aggregation.

To avoid stacking multiple layers of GCNs, **TNDCN**[78] uses different-step network diffusion which provides a larger receptive field for each layer. Each step \(k\) propagates attributes with a \(k\)-hop neighbourhood and has its independent learnable parameters \(\Gamma_{k}\), as shown in equ. 15, where \(\widetilde{\text{A}}^{\text{k}}\) refers to the parameterised \(k\)-hop connectivity matrix.

\[\mathbf{H}=\sum_{k\geq 0}\widetilde{\text{A}}^{\text{k}}\mathbf{H}^{k}\Gamma_{k} \tag{15}\]

Inspired from the Bidirectionnal LSTM [176], an easy-to-implement enhancement for propagation is bi-directional message passing **Bi-GCN**[87, 86]. It processes an undirected tree graph as two directed tree graphs: the first one from the root to the leaves, and the second one from leaves to the root. Then two GCNs with different parameters encode each case independently to obtain more informative hidden states.

Besides improving propagation methods, a widely used technique for aggregating information is the (multi-head) attention mechanism, which enables the model to use adaptive weights \(\left(f_{attn}:R^{|N_{v_{i}}|\times d}\to R^{|N_{v_{i}}|\times 1}\right)\) for enhancing vanilla GCNs [127], as well as its variant self-attention mechanism \(\left(f_{self-attn}:R^{|N_{v_{i}}|\times d}\to R^{|N_{v_{i}}|\times d^{ \prime}}\right)\), which is good at capturing the internal correlation among elements in the sequence.

The three component-oriented improvements mentioned above are applicable not only to \(f_{G}(\cdot)\), but also to \(f_{T}(\cdot)\) when encoding along time, such as dilated convolution for expanding the temporal perceptual field [177], Bi-LSTM for bidirectional propagation along the sequence [176], and (self-)attention mechanisms for encoding sequences [36].

#### 5.2.3 DGNN Structure Oriented Optimisation

Another research direction is to optimise the overall structure. For example, residual connection [131] for dealing with the vanishing gradient is widely used in DGNNs, especially for the DGNNs which sequentially encode hidden states [77, 93, 83].

In particular for the time embedding approach under continuous time, how to better store historical information and how to learn variations of information are two major challenges due to the difficulty of encoding over time. Models such as **TGAT**[109] can encode the timestamps of the event but cannot reuse the hidden states already encoded in the past timesteps. **TGN**[108] addresses this problem by incorporating memory modules, **TGNF**[107] adds the similarity between current memory and previous memory in the loss to encourage the model to learn variational information. All these improvements enhance the performance and efficiency of the model. The evolution of the relevant models is shown in Fig. 13.
## 5 Conclusion

Thanks to their ability to integrate both structural and temporal aspects in a compact formalism, dynamic graphs has emerged in the last few years as a state of the art model for describing dynamic systems.

Many scientific communities have investigated this area of research using their own definition, their own vocabulary, their own constraints, and have proposed prediction models dedicated to their downstream tasks. Among these models, Dynamic Graph Neural Networks occupy an important place, taking benefit of the representation learning paradigm.

The first part of this survey provides a clarification and a categorization of the different dynamic graph learning contexts that are encountered in the literature, from the input point of view, the output point of view and the learning setting (inductive/transductive nature of the task). This categorization leads to five different learning _cases_ covering the different contexts encountered in the literature.

Using this categorization, our second contribution was to propose a taxonomy of existing DGNN models. We distinguish five families of DGNN, according to the strategy used to incorporate time information in the model

Finally, we also provide to practitioners some guidelines for designing and improving DGNNs.

Although dynamic graph learning is a recent discipline, it will undoubtedly be a major trend for machine learning researchers for years to come. We hope that this review is a modest contribution in this direction.

## 6 Acknowledgement

This work was financially supported by the ANR Labcom Lisa ANR-20-LCV1-0009

Figure 13: The main differences between the time-embedding methods, with the green color indicating the graph encoding-related methods and the blue color indicating the time encoding-related methods.