Graph Neural Networks for temporal graphs: State of the art, open
  challenges, and opportunities
Graph Neural Networks (GNNs) have become the leading paradigm for learning on
(static) graph-structured data. However, many real-world systems are dynamic in
nature, since the graph and node/edge attributes change over time. In recent
years, GNN-based models for temporal graphs have emerged as a promising area of
research to extend the capabilities of GNNs. In this work, we provide the first
comprehensive overview of the current state-of-the-art of temporal GNN,
introducing a rigorous formalization of learning settings and tasks and a novel
taxonomy categorizing existing approaches in terms of how the temporal aspect
is represented and processed. We conclude the survey with a discussion of the
most relevant open challenges for the field, from both research and application
perspectives.
Antonio Longa, Veronica Lachi, Gabriele Santin, Monica Bianchini, Bruno Lepri, Pietro Lio, Franco Scarselli, Andrea Passerini
# Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunities

###### Abstract

Graph Neural Networks (GNNs) have become the leading paradigm for learning on (static) graph-structured data. However, many real-world systems are dynamic in nature, since the graph and node/edge attributes change over time. In recent years, GNN-based models for temporal graphs have emerged as a promising area of research to extend the capabilities of GNNs. In this work, we provide the first comprehensive overview of the current state-of-the-art of temporal GNN, introducing a rigorous formalization of learning settings and tasks and a novel taxonomy categorizing existing approaches in terms of how the temporal aspect is represented and processed. We conclude the survey with a discussion of the most relevant open challenges for the field, from both research and application perspectives.

## 1 Introduction

The ability to process temporal graphs is becoming increasingly important in a variety of fields such as recommendation systems [48], social network analysis [8], transportation systems [56], face-to-face interactions [25], epidemic modeling and contact tracing [5], and many others. Traditional graph-based models are not well suited for analyzing temporal graphs as they assume a fixed structure and are unable to capture its temporal evolution. Therefore, in the last few years, several models able to directly encode temporal graphs have been developed, such as random walk-based methods [46], temporal motif-based methods [24], matrix factorization-based approaches [1] and deep learning models [30].

In the realm of static graph processing, Graph Neural Networks (GNNs) [40] have progressively emerged as the leading paradigm, thanks to their ability to efficiently propagate information along the graph and learn rich node and graph representations. GNNs have achieved state-of-the-art performance on various tasks such as node classification [17], link prediction [57], and graph classification [51], making them the go-to method. Overall, the success of GNNs highlights the importance of developing deep learning techniques to handle non-Euclidean data, and in particular the potential of these architectures to revolutionize the way we analyze and understand complex graph-structured systems.

Recently, GNNs have been successfully applied also
to temporal graphs, achieving state-of-the-art results on tasks such as temporal link prediction [38], node classification [36] and edge classification [45], with approaches ranging from attention-based methods [50] to Variational Graph-Autoencoder (VGAE) [16]. However, despite the potential of GNN-based models for temporal graph processing and the variety of different approaches that emerged, a systematization of the literature is still missing. Existing surveys either discuss general techniques for learning over temporal graphs, only briefly mentioning temporal extensions of GNNs [20, 2, 52, 49], or focus on specific topics, like temporal link prediction [33, 41] or temporal graph generation [15].

This work aims to fill this gap by providing a systematization of existing GNN-based methods for temporal graphs, or Temporal GNNs (TGNNs), and a formalization of the tasks being addressed.

Our main contributions are the following:

* We propose a coherent formalization of the different learning settings and of the tasks that can be performed on temporal graphs, unifying existing formalism and informal definitions that are scattered in the literature, and highlighting substantial gaps in what is currently being tackled;
* We organize existing TGNN works into a comprehensive taxonomy that groups methods according to the way in which time is represented and the mechanism with which it is taken into account;
* We highlight the limitations of current TGNN methods, discuss open challenges that deserve further investigation and present critical real-world applications where TGNNs could provide substantial gains.

## 2 Temporal Graphs

We provide a formal definition of the different types of graphs analyzed in this work and we structure different existing notions in a common framework.

**Definition 1** (Static Graph - SG): A Static Graph is a tuple \(G=(V,E,X^{V},X^{E})\), where \(V\) is the set of nodes, \(E\subseteq V\times V\) is the set of edges, and \(X^{V},X^{E}\) are \(d_{V}\)-dimensional node features and \(d_{E}\)-dimensional edge features.

Node and edge features may be empty. Moreover, in the following, we assume that all graphs are directed, i.e., \((u,v)\in E\) does not imply that \((v,u)\in E\).

Extending [33], we define Temporal Graphs as follows.

**Definition 2** (Temporal Graph - TG): A Temporal Graph is a tuple \(G_{T}=(V,E,V_{T},E_{T})\), where \(V\) and \(E\) are, respectively, the set of all possible nodes and edges appearing in a graph at any time, while

\[V_{T} :=\{(v,x^{v},t_{s},t_{e}):v\in V,x^{v}\in\mathbb{R}^{d_{V}},t_{s} \leq t_{e}\},\] \[E_{T} :=\{(e,x^{e},t_{s},t_{e}):e\in E,x^{e}\in\mathbb{R}^{d_{E}},t_{s} \leq t_{e}\},\]

are the temporal nodes and edges, with time-dependent features and initial and final timestamps. A set of temporal graphs is denoted as \(\mathcal{G_{T}}\).

Observe that we implicitly assume that the existence of a temporal edge in \(E_{T}\) requires the simultaneous existence of the corresponding temporal nodes in \(V_{T}\). Moreover, the definition implies that node and edge features are constant inside each interval \([t_{s},t_{e}]\), but may otherwise change over time. Since the same node or edge may be listed multiple times, with different timestamps, we denote as \(\bar{t}_{s}(v)=\min\{t_{s}:(v,x^{v},t_{s},t_{e})\in V_{T}\}\) and \(\bar{t}_{e}(v)=\max\{t_{e}:(v,x^{v},t_{s},t_{e})\in V_{T}\}\) the time of first and last appearance of a node, and similarly for \(\bar{t}_{s}(e)\), \(\bar{t}_{e}(e)\), \(e\in E\). Moreover, we set \(T_{s}(G_{T}):=\min\{\bar{t}_{s}(v):v\in V\}\), \(T_{e}(G_{T}):=\max\{\bar{t}_{e}(v):v\in V\}\) as the initial and final timestamps in a TG \(G_{T}\). For two TGs \(G_{T}^{i}:=(V^{i},E^{i},V_{T}^{i},E_{T}^{i})\), \(i=1,2\), we write \(G_{T}^{1}\subseteq_{V}G_{T}^{2}\) to indicate the topological inclusion \(V^{1}\subseteq V^{2}\), while no relation between the corresponding timestamps is required.

General TGs have no restriction on their timestamps, which can take any value (for simplicity, we just assume that they are non-negative). However, in some applications, it makes sense to force these values to be multiples of a fixed timestep. This leads to the notion of Discrete Time Temporal Graphs, which are defined as follows.
**Definition 3** (Discrete Time Temporal Graph - DTTG): Let \(\Delta t>0\) be a fixed timestep and let \(t_{1}<t_{2}<\cdots<t_{n}\) be timestamps with \(t_{k+1}=t_{k}+\Delta t\). A Discrete Time Temporal Graph \(G_{DT}\) is a TG where for each \((v,x^{v},t_{s},t_{e})\in V_{T}\) or \((e,x^{e},t_{s},t_{e})\in E_{T}\), the \(t_{s},t_{e}\) are taken from the set of fixed timestamps (i.e., \(t_{s},t_{e}\in\{t_{1},t_{2},\ldots,t_{n}\}\), with \(t_{s}<t_{e}\)).

### Representation of temporal graphs

Two main strategies can be found in the literature for the description of time-varying graphs, based on snapshots or on events. These different representations lead to different algorithmic approaches. Extending [15] we give a formal definition of these representation strategies.

The snapshot-based strategy focuses on the temporal evolution of the whole graph. Snapshot-based Temporal Graphs can be defined as follows.

**Definition 4** (Snapshot-based Temporal Graph - STG): Let \(t_{1}<t_{2}<\cdots<t_{n}\) be the ordered set of all timestamps \(t_{s},t_{e}\) occurring in a TG \(G_{T}\). Set

\[V_{i} :=\{(v,x^{v}):(v,x^{v},t_{s},t_{e})\in V_{T},t_{s}\leq t_{i}\leq t _{e}\},\] \[E_{i} :=\{(e,x^{e}):(e,x^{e},t_{s},t_{e})\in E_{T},t_{s}\leq t_{i}\leq t _{e}\},\]

and define the snapshots \(G_{i}:=(V_{i},E_{i})\), \(i=1,\ldots,n\). Then a Snapshot-based Temporal Graph representation of \(G_{T}\) is the sequence

\[G_{T}^{S}:=\{(G_{i},t_{i}):i=1,\ldots,n\}\]

of time-stamped static graphs.

This representation is mostly used to describe DTTGs, where the snapshots represent the TG captured at periodic intervals (e.g., hours, days, etc.).

The event-based strategy is more appropriate when the focus is on the temporal evolution of individual nodes or edges. This leads to the following definition.

**Definition 5** (Event-based Temporal Graph - ETG): Let \(G_{T}\) be a TG, and let \(\varepsilon\) denote one of the following event:

* Node insertion \(\varepsilon_{V}^{+}:=(v,t)\): the node \(v\) is added to \(G_{T}\) at time \(t\), i.e., there exists \((v,x^{v},t_{s},t_{e})\in V_{T}\) with \(t_{s}=t\).
* Node deletion \(\varepsilon_{V}^{-}:=(v,t)\): the node \(v\) is removed from \(G_{T}\) at time \(t\), i.e., there exists \((v,x^{v},t_{s},t_{e})\in V_{T}\) with \(t_{e}=t\).
* Edge insertion \(\varepsilon_{E}^{+}:=(e,t)\): the edge \(e\) is added to \(G_{T}\) at time \(t\), i.e., there exists \((e,x^{e},t_{s},t_{e})\in E_{T}\) with \(t_{s}=t\).
* Edge deletion \(\varepsilon_{E}^{-}:=(e,t)\): the edge \(e\) is removed from \(G_{T}\) at time \(t\), i.e., there exists \((e,x^{e},t_{s},t_{e})\in E_{T}\) with \(t_{e}=t\).

An Event-based Temporal Graph representation of TG is a sequence of events

\[G_{T}^{E}:=\{\varepsilon:\varepsilon\in\{\varepsilon_{V}^{+},\varepsilon_{E}^{ -},\varepsilon_{E}^{+},\varepsilon_{E}^{-}\}\}.\]

Here it is implicitly assumed that node and edge events are consistent (e.g., a node deletion event implies the existence of an edge deletion event for each incident edge). In the case of an ETG, the TG structure can be recovered by coupling an insertion and deletion event for each temporal edge and node. ETGs are better suited than STGs to represent TGs with arbitrary timestamps.

We will use the general notion of TG, which comprises both STG and ETG, in formalizing learning tasks in the next section. On the other hand, we will revert to the STG and ETG notions when introducting the taxonomy of TGNN methods in Section 4, since TGNNs use one or the other representation strategy in their algorithmic approaches.

## 3 Learning tasks on temporal graphs

Thanks to their learning capabilities, TGNNs are extremely flexible and can be adapted to a wide range of tasks on TGs. Some of these tasks are straightforward temporal extensions of their static counterparts. However, the temporal dimension has some non-trivial consequences in the definition of learning settings and tasks, some of which are often only
loosely formalized in the literature. We start by formalizing the notions of transductive and inductive learning for TGNNs, and then describe the different tasks that can be addressed.

### Learning settings

The machine learning literature distinguishes between inductive learning, in which a model is learned on training data and later applied to unseen test instances, and transductive learning, in which the input data of both training and test instances are assumed to be available, and learning is equivalent to leveraging the training inputs and labels to infer the labels of test instances given their inputs. This distinction becomes extremely relevant for graph-structured data, where the topological structure gives rise to a natural connection between nodes, and thus to a way to propagate the information in a transductive fashion. Roughly speaking, transductive learning is used in the graph learning literature when the node to be predicted and its neighborhood are known at training time -- and is typical of node classification tasks --, while inductive learning indicates that this information is not available -- and is most often associated to graph classification tasks.

However, when talking about GNNs with their representation learning capabilities, this distinction is not so sharp. For example, a GNN trained for node classification in transductive mode could still be applied to an unseen graph, thus effectively performing inductive learning. The temporal dimension makes this classification even more elusive, since the graph structure is changing over time and nodes are naturally appearing and disappearing. Defining node membership in a temporal graph is thus a challenging task in itself.

Below, we provide a formal definition of transductive and inductive learning for TGNNs which is purely topological, i.e. linked to knowing or not the instance to be predicted at the training time, and we complete it with a temporal dimension, which distinguishes between past and future prediction tasks.

**Definition 6** (Learning settings): Assume that a model is trained on a set of \(n\geq 1\) temporal graphs \(\mathcal{G}_{\mathcal{T}}\ :=\ \{G_{T}^{i}\ :=\ (V_{i},E_{i},X_{i}^{V},X_{i}^{E}),\ i =1,\ldots,n\}\). Moreover, let

\[T_{e}^{all}:=\max_{i=1,\ldots,n}T_{e}(G_{T}^{i}),\,V^{all}:=\cup_{i=1}^{n}V_{i},\ E^{all}:=\cup_{i=1}^{n}E_{i},\]

be the final timestamp and the set of all nodes and edges in the training set. Then, we have the following settings:

* Transductive learning: inference can only be performed on \(v\in V^{all}\), \(e\in E^{all}\), or \(G_{T}\subseteq_{V}G_{T}^{i}\) with \(G_{T}^{i}\in\mathcal{G}_{\mathcal{T}}\).
* Inductive learning: inference can be performed also on \(v\notin V^{all}\), \(e\notin E^{all}\), or \(G_{T}\not\subseteq_{V}G_{T}^{i}\), for all \(i=1,\ldots,n\).
* Past prediction: inference is performed for \(t\leq T_{e}^{all}\).
* Future prediction: inference is performed for \(t>T_{e}^{all}\).

We remark that all combinations of topological and temporal settings are meaningful, except for the case of inductive graph-based tasks. Indeed, the measure of time used in TGs is relative to each single graph. Moving to an unobserved graph would thus make the distinction between past and future pointless. Moreover, let us observe that, in all other cases, the two temporal settings are defined based on the final time of the entire training set, and not of the specific instances (nodes or edges), since their embedding may change also as an effect of the change of their neighbors in the training set.

We will use this categorization to describe supervised and unsupervised learning tasks in Section 3.2-3.3, and to present existing models in Section 4.

### Supervised learning tasks

Supervised learning tasks are based on a dataset where each object is annotated with its label (or class), from a finite set of possible choices \(\mathcal{C}:=\{C_{1},C_{2},\ldots,C_{k}\}\).
#### 3.2.1 Classification

**Definition 7** (Temporal Node Classification): Given a TG \(G_{T}=(V,E,V_{T},E_{T})\), the node classification task consists in learning the function

\[f_{\text{NC}}:V\times\mathbb{R}^{+}\rightarrow\mathcal{C}\]

which maps each node to a class \(C\in\mathcal{C}\), at a time \(t\in\mathbb{R}^{+}\).

This is one of the most common tasks in the TGNN literature. For instance, [31, 50, 45, 58, 36] focus on a future-transductive (FT) setting, i.e., predicting the label of a node in future timestamps. TGAT [50] performs future-inductive (FI) learning, i.e. it predicts the label of an unseen node in the future. Finally, DGNN [27] is the only method that has been tested on a past-inductive (PI) setting, i.e., predicting labels of past nodes that are unavailable (or masked) during training, while no approach has been applied to the past-transductive (PT) one. A significant application may be in epidemic surveillance, where contact tracing is used to produce a TG of past human interactions, and sample testing reveals the labels (infection status) of a set of individuals. Identifying the past infection status of the untested nodes is a PT task.

**Definition 8** (Temporal Edge Classification): Given a TG \(G_{T}=(V,E,V_{T},E_{T})\), the temporal edge classification task consists in learning a function

\[f_{\text{EC}}:E\times\mathbb{R}^{+}\rightarrow\mathcal{C}\]

which assigns each edge to a class at a given time \(t\in\mathbb{R}^{+}\).

Temporal edge classification has been less explored in the literature. Existing methods have focused on FT learning [31, 45], while FI, PI and PT have not been tackled so far. An example of PT learning consists in predicting the unknown past relationship between two acquaintances in a social network given their subsequent behaviour. For FI, one may predict if a future transaction between new users is a fraud or not.

In the next definition we use the set of real and positive intervals \(I^{+}:=\{[t_{s},t_{e}]\subset\mathbb{R}^{+}\}\).

**Definition 9** (Temporal Graph Classification): Let \(\mathcal{G}_{\mathcal{T}}\) be a domain of TGs. The graph classification task requires to learn a function

\[f_{\text{GC}}:\mathcal{G}_{\mathcal{T}}\times I^{+}\rightarrow\mathcal{C}\]

that maps a temporal graph, restricted to a time interval \([t_{s},t_{e}]\in I^{+}\), into a class.

The definition includes the classification of a single snapshot (i.e., \(t_{s}=t_{e}\)). As mentioned above, in the inductive setting the distinction between past and future predictions is pointless. In the transductive setting, instead, a graph \(G_{T}\in\mathcal{G}_{\mathcal{T}}\) may be classified in a past mode if \([T_{s}(G_{T}),T_{e}(G_{T})]\subseteq[t_{s},t_{e}]\), or in the future mode, otherwise.

None of the existing methods tackles temporal graph classification tasks, possibly for the lack of suitable datasets (see also Section 5). The task has however numerous relevant applications. An example of inductive temporal graph classification is predicting mental disorders from the analysis of the brain connectome [18]. On the other hand, detecting critical stages during disease progression from gene expression profiles [13] can be framed as a past transductive graph classification task.

#### 3.2.2 Regression

The tasks introduced for classification can all be turned into corresponding regression tasks, simply by replacing the categorical target \(\mathcal{C}\) with the set \(\mathbb{R}\). We omit the formal definitions for the sake of brevity. To the best of our knowledge, no existing TGNN work addresses this kind of problem, even if the application of static GNNs alone has already shown outstanding results in this setting, e.g. in weather forecasting [21] and earthquake location and estimation [28].

#### 3.2.3 Link prediction

Link prediction requires the model to predict the relation between two given nodes, and can be formulated by taking as input any possible pair of nodes. Thus, we consider the setting to be transductive when both node instances are known at training time, and inductive otherwise. Instead, [33] adopt a different approach and identify _Level-1_ (the set of nodes is fixed)
and _Level-2_ (nodes may be added and removed over time) temporal link prediction tasks.

**Definition 10** (Temporal Link Prediction): Let \(G_{T}=(V,E,V_{T},E_{T})\) be a TG. The temporal link prediction task consists in learning a function

\[f_{\text{LP}}:V\times V\times\mathbb{R}^{+}\rightarrow[0,1]\]

which predicts the probability that, at a certain time, there exists an edge between two given nodes.

The domain of the function \(f_{\text{LP}}\) is the set of all feasible pairs of nodes, since it is possible to predict the probability of future interactions between nodes that have been connected in the past or not, as well as the probability of missing edges in a past time. Most TGNN approaches for temporal link prediction focus on future predictions, forecasting the existence of an edge in a future timestamp between existing nodes (FT is the most common setting) [31, 38, 16, 55, 50, 26, 45, 27, 36, 58], or unseen nodes (FI) [16, 50, 36]. The only model that investigates past temporal link prediction is [26], which devises a PI setting by masking some nodes and predicting the existence of a past edge between them. Note that predicting past temporal links can be extremely useful for predicting, e.g., missing interactions in contact tracing for epidemiological studies.

**Definition 11** (Event Time Prediction): Let \(G_{T}=(V,E,V_{T},E_{T})\) be a TG. The aim of the event time prediction task is to learn a function

\[f_{\text{EP}}:V\times V\rightarrow\mathbb{R}^{+}\]

that predicts the time of the first appearance of an edge.

None of the existing methods address this task. Potential FT applications of event time prediction include predicting when a customer will pay an invoice to its supplier, or how long it takes to connect two similar users in a social network.

### Unsupervised learning tasks

In this section, we formalize unsupervised learning tasks on temporal graphs, an area that has received little to no attention in the TGNN literature so far.

#### 3.3.1 Clustering

Temporal graphs can be clustered at the node or graph level, with edge-level clustering being a minor variation of the node-level one. Some relevant applications can be defined in terms of temporal clustering.

**Definition 12** (Temporal Node Clustering): Given a TG \(G_{T}=(V,E,V_{T},E_{T})\), the temporal node clustering task consists in learning a time-dependent cluster assignment map

\[f_{\text{NCl}}:V\times\mathbb{R}^{+}\rightarrow\mathcal{P}(V),\]

where \(\mathcal{P}(V):=\{p_{1},p_{2},\ldots,p_{k}\}\) is a partition of the node set \(V\), i.e., \(p_{i}\subset V_{T}\), \(p_{i}\cap p_{j}=\emptyset\), if \(i\neq j\), \(\cup_{i=1}^{N}p_{i}=V_{T}\).

While node clustering in SGs is a very common task, its temporal counterpart has not been explored yet for TGNNs, despite its potential relevance in application domains like epidemic modelling (identifying groups of exposed individuals, in both inductive and transductive settings), or trend detection in customer profiling (mostly transductive).

**Definition 13** (Temporal Graph Clustering): Given a set of temporal graphs \(\mathcal{G_{T}}\), the temporal graph clustering task consists in learning a cluster-assignment function

\[f_{\text{GCl}}:\mathcal{G_{T}}\times I^{+}\rightarrow\mathcal{P}(\mathcal{G_{T }}),\]

where \(\mathcal{P}(\mathcal{G_{T}}):=\{p_{1},\ldots,p_{k}\}\) is a partition of the set of temporal graphs in the given time interval.

Relevant examples of tasks of inductive temporal graph clustering are grouping social interaction networks (e.g., hospitals, workplaces, schools) according to their interaction patterns, or grouping diseases in terms of similarity between their spreading processes [10].

#### 3.3.2 Low-dimensional embedding (LDE)

LDEs are especially useful in the temporal setting, e.g. to visually inspect temporal dynamics of individual nodes or entire graphs, and identify relevant
trends and patterns. No GNN-based model has been applied to these tasks, neither at the node nor at the graph level. We formally define the tasks of temporal node and graph LDE as follows.

**Definition 14** (Low-dimensional temporal node embedding): Given a TG \(G_{T}=(V,E,V_{T},E_{T})\), the low-dimensional temporal node embedding task consists in learning a map

\[f_{NEm}:V\times\mathbb{R}^{+}\rightarrow\mathbb{R}^{d}\]

to map a node, at a given time, into a low dimensional space.

**Definition 15** (Low-dimensional temporal graph embedding): Given a domain of TGs \(\mathcal{G_{T}}\), the low-dimensional temporal graph embedding task aims to learn a map

\[f_{GEm}:\mathcal{G_{T}}\times I^{+}\rightarrow\mathbb{R}^{d},\]

which represents each graph as a low dimensional vector in a given time interval.

## 4 A taxonomy of TGNNs

This section describes the taxonomy with which we categorize existing TGNN approaches (see Figure 1). Following the representation strategies outlined in Section 2.1, the first level groups methods into _Snaphost-based_ and _Event-based_. The second level of the taxonomy further divides these two macro-categories based on the techniques used to manage the temporal dependencies. The leaves of the taxonomy in Figure 1 correspond to the individual models, with a colored symbol indicating their main underlying technology.

### Snapshot-based models

_Snaphot-based_ models are specifically tailored for STGs (see Def. 4) and thus, consistently with the definition, they are equipped with a suitable method to process the entire graph at each point in time, and with a mechanism that learns the temporal dependencies across timesteps. Based on the mechanism used, we can further distinguish between _Model Evolution_ and _Embedding Evolution_ methods.

#### 4.1.1 Model Evolution methods

We call _Model Evolution_ the evolution of the parameters of a static GNN model over time. This mechanism is appropriate for modelling STG, as the evolution of the model is performed at the snapshot level.

To the best of our knowledge, the only existing method belonging to this category is **EvolveGCN**[31]. This model utilizes a Recurrent Neural Network (RNN) to update the Graph Convolutional Network (GCN) [23] parameters at each timestep, allowing for model adaptation that is not constrained by the presence or absence of nodes. The method can effectively handle new nodes without prior historical information. A key advantage of this approach is that the GCN parameters are no longer trained directly, but rather they are computed from the trained RNN, resulting in a more manageable model size that does not increase with the number of timesteps.

#### 4.1.2 Embedding Evolution methods

Rather than evolving the parameters of a static GNN model, _Embedding Evolution_ methods focus on evolving the embeddings produced by a static model.

There are several different TGNN models that fall under this category. These networks differ from one another in the techniques used for processing both the structural information and the temporal dynamics of the STGs. **DySAT**[38] introduced a generalization of Graph Attention Network (GAT) [44] for STGs. First, it uses a self-attention mechanism to generate static node embeddings at each timestamp. Then, it uses a second self-attention block to process past temporal embeddings for a node to generate its novel embedding. The **VGRNN** model [16] uses VGAE [22] coupled with Semi-Implicit Variational Inference (SIVI) [54] to handle the variation of the graph over time. The learned latent representation is then evolved through an LSTM conditioned
on the previous time's latent representation, allowing the model to predict the future evolution of the graph. Finally, **ROLAND**[55] is a general framework for extending state-of-the-art GNN techniques to STGs. The key insight is that node embeddings at different GNN layers can be viewed as hierarchical node states. To generalize a static GNN for dynamic settings, hierarchical node states are updated based on newly observed nodes and edges through a Gated Recurrent Unit (GRU) update module [6].

### Event-based models

Models belonging to the _Event-based_ macro category are designed to process ETGs (see Def. 5). These models are able to process streams of events by incorporating techniques that update the representation of a node whenever an event involving that node occurs.

The models that lie in this macro category can be further classified in _Temporal Embedding_ and _Temporal Neighborhood_ methods, based on the technology used to learn the time dependencies. In particular, the _Temporal Embedding_ models use recurrent or self-attention mechanisms to model sequential information from streams of events, while also incorporating a time encoding. This allows for temporal signals to be modeled by the interaction between time embedding, node features and the topology of the graph. _Temporal Neighborhood_ models, instead, use a module that stores functions of events involving a specific node at a given time. These values are then aggregated and used to update the node representation as time progresses.

Figure 1: **The proposed TGNN taxonomy and an analysis of the surveyed methods.** The top panel shows the new categories introduced in this work with the corresponding model instances (Section 4), where the colored bullets additionally indicate the main technology that they employ. The bottom table maps these methods to the task (Section 3) to which they have been applied in the respective original paper, with an additional indication of their use in the future (F), past (P), inductive (I), or transductive (T) settings (Section 3.1). Notice that no method has been applied yet to clustering and visualization, for neither graphs nor nodes. Moreover, only four out of ten models have been tested in the past mode (three in PT, one in PI).
#### 4.2.1 Temporal Embedding methods

_Temporal embedding_ methods model TGs by combining time embedding, node features, and graph topology. These models use an explicit functional time encoding, i.e., a translation-invariant vectorial embedding of time based on Random Fourier Features (RFF) [34].

**TGAT**[50], for example, introduces a graph-temporal attention mechanism which works on the embeddings of the temporal neighbours of a node, where the positional encoding is replaced by a temporal encoding based on RFFs. On the other hand, **NAT**[26] collects the temporal neighbours of each node into dictionaries, and then it learns the node representation with a recurrent mechanism, using the historical neighbourhood of the current node and a RFF based time embedding.

#### 4.2.2 Temporal Neighborhood methods

The _Temporal Neighborhood_ class includes all TGNN models that make use of a special _mailbox_ module to update node embeddings based on events. When an event occurs, a function is evaluated on the details of the event to compute a _mail_ or a _message_. For example, when a new edge appears between two nodes, a message is produced, taking into account the time of occurrence of the event, the node features, and the features of the new edge. The node representation is then updated at each time by aggregating all the generated messages.

Several existing TGNN methods belong to this category. **APAN**[45] introduces the concept of asynchronous algorithm, which decouples graph query and model inference. An attention-based encoder maps the content of the mailbox to a latent representation of each node, which is decoded by an MLP adapted to the downstream task. After each node update following an event, mails containing the current node embedding are sent to the mailboxes of its neighbors using a propagator. **DGNN**[27] combines an _interact_ module -- which generates an encoding of each event based on the current embedding of the interacting nodes and its history of past interactions -- and a _propagate_ module -- which transmits the updated encoding to each neighbors of the interacting nodes. The aggregation of the current node encoding with those of its temporal neighbors uses a modified LSTM, which permits to work on non-constant timesteps, and implements a discount factor to downweight the importance of remote interactions. **TGN**[36] provides a generic framework for representation learning in ETGs, and it makes an effort to integrate the concepts put forward in earlier techniques. This inductive framework is made up of separate and interchangeable modules. Each node the model has seen so far is characterized by a memory vector, which is a compressed representation of all its past interactions. Given a new event, a mailbox module computes a mail for every node involved. Mails will then be used to update the memory vector. To overcome the so-called staleness problem [20], an embedding module computes, at each timestamp, the node embeddings using their neighbourhood and their memory states. Finally, **TGL**[58] is a general framework for training TGNNs on graphs with billions of nodes and edges by using a distributed training approach. In TGL, a mailbox module is used to store a limited number of the most recent interactions, called mails. When a new event occurs, the node memory of the relevant nodes is updated using the cached messages in the mailbox. The mailbox is then updated after the node embeddings are calculated. This process is also used during inference to ensure consistency in the node memory, even though updating the memory is not required during this phase.

## 5 Open challenges

Building on existing libraries of GNN methods, two major TGNN libraries have been developed, namely PyTorch Geometric Temporal (PyGT) [37], based on PyTorch Geometric1, and DynaGraph [14], based on Deep Graph Library2. While these are substantial contributions to the development and practical application of TGNN models, several open challenges still need to be faced to fully exploit the potential of this technology. We discuss the ones we believe are
the most relevant in the following.

**Evaluation**: The evaluation of GNN models has been greatly enhanced by the Open Graph Benchmark (OGB) [19], which provides a standardized evaluation protocol and a collection of graph datasets enabling a fair and consistent comparison between GNN models. An equally well-founded standardized benchmark for evaluating TGNNs does not currently exist. As a result, each model has been tested on its own selection of datasets, making it challenging to compare and rank different TGNNs on a fair basis. For instance, Zhou _et al._[58] introduced two real-world datasets with 0.2 billion and 1.3 billion temporal edges which allow to evaluate the scalability of TGNNs to large scale real-world scenarios, but they only tested the TGL model [58]. The variety and the complexity of learning settings and tasks described in Section 3 makes a standardization of tasks, datasets and processing pipelines especially crucial to allow a fair assessment of the different approaches and foster innovation in the field.
**Expressiveness**: Driven by the popularity of (static) GNNs, the study of their expressive power has received a lot of attention in the last few years [39]. For instance, appropriate formulations of message-passing GNNs have been shown to be as powerful as the Weisfeiler-Lehman isomorphism test (WL test) in distinguishing graphs or nodes [51], and higher-order generalizations of message-passing GNNs have been proposed that can match the expressivity of the \(k\)-WL test [29]. Finally, it has been proven that GNNs are a sort of universal approximators on graphs modulo the node equivalence induced by the WL test [9].

Conversely, the expressive power of TGNNs is still far from being fully explored, and the design of new WL tests, suitable for TGNNs, is a crucial step towards this aim. This is a challenging task since the definition of a node neighbourhood in temporal graphs is not as trivial as for static graphs, due to the appearing/disappearing of nodes and edges. In [3], a new version of the WL test for temporal graphs has been proposed, applicable only to DTTGs. Instead, [42] proposed a novel WL test for ETGs, and the TGN model [36] has been proved to be as powerful as this test. Finally, [3] proved a universal approximation theorem, but the result just holds for a specific TGNN model for STGs, composed of standard GNNs stacked with an RNN.

To the best of our knowledge, these are the only results achieved so far on the expressive power of TGNNs. A complete theory of the WL test for the different TG representations, such as universal approximation theorems for event-based models, is still lacking. Moreover, no efforts have been made to incorporate higher-order graph structures to enhance the expressiveness of TGNNs. This task is particularly demanding, since it requires not only the definition of the temporal counterpart of the \(k\)-WL test but also some techniques to scale to large datasets. Indeed, a drawback of considering higher-order structures is that of high memory consumption, which can only get worse in the case of TGs, as they usually have a greater number of nodes than static graphs.
**Learnability**: Training standard GNNs over large and complex graph data is highly non-trivial, often resulting in problems such as over-smoothing and over-squashing. A theoretical explanation for this difficulty has been given using algebraic topology and Sheaf theory [43, 4]. More intuitively, we yet do not know how to reproduce the breakthrough obtained in training very deep architectures over vector data when training deep GNNs. Such a difficulty is even more challenging with TGNNs, because the typical long-term dependency of TGs poses additional problems to those due to over-smoothing and over-squashing.

Modern static GNN models face the problems arising from the complexity of the data using techniques such as dropout, virtual nodes, neighbor sampling, but a general solution is far from being reached. The extension of the above mentioned techniques to TGNNs, and the corre
sponding theoretical studies, are open challenges and we are aware of only one work towards this goal [53]. On the other hand, the goal of proposing general very deep TGNNs is even more challenging due to the difficulty in designing the graph dynamics in a hierarchical fashion.
**Real-world applications**: The analysis of the tasks in Section 3 revealed several opportunities for the use of TGNNs far beyond their current scope of application. We would like to outline here some promising directions of application.

A challenging and potentially disruptive direction for the application of TGNNs is the learning of dynamical systems through the combination of machine learning and physical knowledge [47]. Physic Informed Neural Networks (PINNs) [35] are already revolutionizing the field of scientific computing [7], and static GNNs have been employed in this framework with great success [32, 12]. Adapting TGNNs to this field may enable to carry over these results to the treatment of time-dependent problems. Climate science [11] is a particularly attractive field of application, both for its critical impact in our societies and for the promising results achieved by GNNs in climate modelling tasks [21]. We believe that TGNNs may rise to be a prominent technology in this field, thanks to their unique capability to capture spatio-temporal correlations at multiple scales. Epidemics studies are another topic of enormous everyday impact that may be explored throw the lens of TGNNs, since a proper modelling of the spreading dynamics needs to be tightly coupled to the underlying TG structure [10]. Both fields requires a better development of TGNNs for regression problem, a task that is still underdeveloped (see Section 3).

## 6 Conclusion

GNN based models for temporal graphs have become a promising research area. However, we believe that the potential of GNNs in this field has only been partially explored. In this work, we propose a systematic formalization of tasks and learning settings for TGNNs, which was lacking in the literature, and a comprehensive taxonomy categorizing existing methods and highlighting unaddressed tasks. Building on this systematization of the current state-of-the-art, we discuss open challenges that need to be addressed to unleash the full potential of TGNNs. We conclude by stressing the fact that the issues open to date are very challenging, since they presuppose considering both the temporal and relational dimension of data, suggesting that forthcoming new computational models must go beyond the GNN framework to provide substantially better solutions.
