Expressivity of Representation Learning on Continuous-Time Dynamic Graphs: An Information-Flow Centric Review
Authors: Sofiane ENNADIR
Gabriela Zarzar Gandler
Filip Cornell
Lele Cao
Oleg Smirnov
Tianze Wang
Levente Zólyomi
Björn Brinne
Sahar Asadi
Venue: Accepted by TMLR ()

Abstract: Graphs are ubiquitous in real-world applications, ranging from social networks to biological systems, and have inspired the development of Graph Neural Networks (GNNs) for learning expressive representations. While most research has centered on static graphs, many real-world scenarios involve dynamic, temporally evolving graphs, motivating the need for Continuous-Time Dynamic Graph (CTDG) models. This paper provides a comprehensive review of Graph Representation Learning (GRL) on CTDGs with a focus on Self-Supervised Representation Learning (SSRL). We introduce a novel theoretical framework that analyzes the expressivity of CTDG models through an Information-Flow (IF) lens, quantifying their ability to propagate and encode temporal and structural information. Leveraging this framework, we categorize existing CTDG methods based on their suitability for different graph types and application scenarios. Within the same scope, we examine the design of SSRL methods tailored to CTDGs, such as predictive and contrastive approaches, highlighting their potential to mitigate the reliance on labeled data. Empirical evaluations on synthetic and real-world datasets validate our theoretical insights, demonstrating the strengths and limitations of various methods across long-range, bi-partite and community-based graphs. This work offers both a theoretical foundation and practical guidance for selecting and developing CTDG models, advancing the understanding of GRL in dynamic settings.

Published in Transactions on Machine Learning Research (04/2025)
Expressivity of Representation Learning on Continuous-Time Dynamic Graphs: An Information-Flow Centric Review
Sofiane Ennadir
Gabriela Zarzar Gandler Filip Cornell Lele Cao't, Oleg Smirnov',
Tianze Wang', Levente Zólyomi', Björn Brinne', Sahar Asadi!
'AI Labs, King/Micross Microsoft
KTH Royal Institute of Technology
Reviewed on OpenReview:
https: // openreview. net/ forun? id- N7Lhr2anjg
Abstract
Graphs are ubiquitous in real-world applications, ranging from social networks to biological systems, and have inspired the development Graph Neural Networks (GNNs) for learn- ing expressive representations. While most research has centered on static graphs, many real-world scenarios involve dynamic, temporally evolving graphs, motivating the need for Continuous- Time Dynamic Graph (CTDG) models. This paper provides a comprehensive review of Graph Representation Learning (GRL.) on CTDGs with a focus Self-Supervisel Representation Learning (SSRL). We introduce novel theoretical framework that analyzes the expressivity of CTDG models through an Information-Fll ability propagate and encode temporal and structural information. Leveraging this frame- work, we categorize existing CTDG methods based on their suitability for different graph types and application scenarios. Within the same scope, we examine the design of SSRL methods tailored to CTDGs, such predictive and contrastive approaches, highlighting their potential to mitigate the reliance on labeled data. Empirical evaluations on synthetic and real-world datasets validate our theoretical insights, demonstrating the strengths and limitations of various methods across long-range, bi-partite and community-bawee graphs. This work offers both a theoretical foundation and practical guidance for selecting and developing CTDG models, advancing the understanding of GRL dynamic settings.
(IF) lens, quantifying their
1 Introduction
Graph-structured data prevalent across various domains such as chemoinformatics, bioinformatics, and social network analysis. Those domains often require sophisticated machine lcarning approaches, driving the development of Graph Representation Learning (GRL). At its core, GRL aims to embed graph structures into low-dimensional vector spaces, preserving essential structural and semantic features. This embedding facilitates tasks such as node classification (c.g., music genre prediction (Kumar et al. 2019b)) link prediction (e.g., product recommendation (w et al.j 2019)) ) and graph classification (e.g., drug discovery (Kearnes 2016 A cornerstone of this field is the Possage-Passiigg (MP) paradigm (Gilmer et al. 2017), where nodes iteratively exchange and aggregate information from their neighbors to learn representations.
et al.
While much of the research has focused on static graphs Kipp & Welling 2017 Veličković al., 2018 Xu
et al. 2019), many real-world applications involve evolving graph structures. Such graphs, termed Dynamic Graphs (DGs), undergo changes over time through mode/edge addition/deletion deletion node feature updates collectively referred to as events (Seo et al.) 2018 Bai et al. 2021). DGs can be categorized as Discrete-Tinme Time DGs (DTDGs) or Continuous- Time DGs (C (CTDGs), distinguished by their treatment of temporal granularity. While DTDGs aggregate events into fixed time intervals, CTDGs accommodate temporally irregular events,
"Equal contribution. Source code: htttps://gitaei hon//ing/cttdginnffeee
i "Correpponding author. Email: lele. www.king.ccoooooo con or telecao@nicrrooof..comm

---

Published in Transactions on Machine Learning Research (04/2025)
offering more flexible and widely adopted representation for DGs. Learning on CTDGs presents unique challenges, such capturing temporal dependencies and handling sparse, irregular event data.
Many methods have been proposed to address these challenges, often extending the MP framework to incor- porate temporal dynamics or novel architectures. However, these methods typically require large amounts of training data to achieve satisfactory performance. This poses a significant limitation in domains like recommender systems, where the graph is often sparse, and observed interactions (e.g., purchasing events) represent small fraction of possible connections. Under such conditions, models risk overfitting and struggle to generalize effectively.
To address these limitations, Self-Supervised Representation Learning (SSRL) has emerged as a promising paradigm, leveraging unlabeled data to construct auxiliary pretext lasks for model training. In the context of CTDGs, SSRL tasks often derive supervision from the temporal sequence of events, such as predicting the next link or interaction. This approach mitigates the reliance on labeled data and enables models learn robust representations. Despite its potential, SSRL for CTDGs remains underexplored compared to its adoption in other areas like Computer Vision (CV) and Natural Language Processing (NLP).
This paper presents review of methods for learning representations of CTDGs with an emphasis on SSRL approaches. While previous surveys have examined DG representation learning (Gravina & Bacciu 2024 Kazemi et al. 2020), they often focus on general methods without diving deeply into the unique challenges and opportunities associated with applying SSRL to CTDGs. Our work fills this gap by offering a catego- rization framework based on their theoretical capability represent specific families of graphs, particularly those commonly encountered in specialized domains. For instance, in recommender systems, the user-item interaction graph is typically sparse bipartite graph exhibiting power-law degree distribution (Li ct al., 2012), whereas social networks often form denser small-world networks characterized by high clustering coefficients and short average path lengths (Watts & Strogatz 1998).
We begin by introducing a general formulation for CTDG and the associated learning methods. Building upon the concept of Information Flow (IF) in MP Neural Networks (MPNNs) (Gutteridge et al. 2023 we derive a theoretical framework that quantify their expressivity the ability to capture and propagate information across temporal events. Focusing on approachos that leverage inherent graph dynamics, we exclude methods relying solely on sequence modeling techniques such (Du et al., 2016 Sun et al., 2019). The theoretical analysis of expressivity enables us to categorize existing approaches based on their architectural components and the structural properties of the graphs they are best suited for. We then provide a comprehensive review of these methods, structured according to this catcgorization, with a particular emphasis on SSRL approaches for CTDGs. Finally, we validate our theoret insights through experiments, offering empirical results on representative subset of the reviewed methods. Our contributions are as follows:
Theoretical expressivity framework: We propose framework for analyzing the expressivity of CTDG methods, with a focus on the upper bounds of IF in temporal MP schemes.
Method categorization and review: We review and categorize existing methods based on their performance with specific families of graphs from our theoretical insights.
Empirical validation: We empirically demonstrate the validity of the derived bounds and illustrate key insights through evaluations of several representative methods.
2 Theoretical Expressivity Framework
A static graph is defined as G (V, E), where V is the set of vertices and E the set of edges. Let n [ and m = |E] denote the number of vertices and edges, respectively, and Nww) = {u: (v,u) E E} the set of neighbors of a node u E V. The degree of a node u is [W(u]]. A graph is often represented by its adjacency matrix A E R where the (i, entry denotes the weight of the odge between the i-th and j-th nodes, or if no edge exists. Node features are represented by X R"xD, where D is the feature dimensionality, and the i-th row of X corresponds to the features of the i-th node.
2

---

Published in Transactions on Machine Learning Research (04/2025)
For DGs, the graph at time is represented as G. Ev, where E, is the set of edges at time t. Events at time 1+1 1 can alter the topology by adding or removing edges or nodes, resulting in Ge+1 = (V, 1.+1). To maintain consistency, we treat the node set V as constant over time by assuming nodes with zero degree exist at the start and can transition to active participation as events unfold.
The upcoming formulation will focus on scenarios where the temporal evolution of the graph is primarily driven by the irreversible addition of new edges, as on e-commerce platforms where purchasing events become permanent part of the system's knowledge. In reversible scenario like social networks, edge-removal events such "unfriending" can be modeled adding an edge with negative or reverse signal, this action, combined with the carlier "friending" behavior, conveys information distinct from simply deleting the edge. This perspective ensures that both positive (edge additions) and negative (edge removals) interactions are captured in this work as key mechanisms underlying real-world data- eetta-geeraatng processes.
2.1 Key Components of CTDG Representation Learning
To address the dynamic nature of CTDGs and their inherent temporal aspects, several recent works, such as TGN (Rossi et al.] 2020a). TGAT (Xu et al.; 2020). and CTAN (Gravina al. 2024), have proposed adapted MP mechanisms. They allow nodes communicate and update their states based on both current events and historical interactions. Specifically, for each node u, its temporal neighborhood (u,,t at time is defined to include all nodes that have interacted with within specified time window (also referred to as the context window) leading up to t. This temporal neighborhood captures the temporal aspect of interactions, ensuring that node updates consider both recent and relevant historical information.
We intend to propose a general framework that encompasses the various approaches relying on temporal MP to facilitate learning on CTDGs. This framework built on two essential components:
(i) Node representation: At any given time t, each node u has a representation ht()) in the embed- ding space. This representation is used for various pretraining tasks or downstream applications.
(ii) Node memory: Each node u maintains memory state, denoted as st),), which evolves over time to track the node's historical interactions. While some methods leverage this memory explicitly, others rely solely on the node's current representation.
When an event E (u, u. c.,)) occurs time between nodes and v, where c captures the event's features, updates are performed in two stages:
(i) The nodes directly involved in the event (i.c., u and v) are updated to reflect the new inter- action. The generated message directly updates their corresponding memory based on the event's features e',,, and also their previous memories in time t This can be written as:
(t) MEMUPD((ssa())) st eu,,)) sl) MCMUPD((ss.(T))) (t),,, cl,o)) (1)
where function MEMUPD varies across methods; some use GRUs or LSTMs (umaar et al. 2019a
while others opt. for a simple identity function (Rossi et al. 2020a
(ii) All other nodes are updated through a MP mechanism designed to propagate the newly intro- duced information across the graph. This ensures that the entire network incorporates the updated information, extending beyond the immediately affected nodes. We begin by defining the concept of temporal neighborhood of each node u at time t as:
N(u,t) = {(V, eh,,, t') u(u, E G.).
(2)
where NV,,,) t) captures all nodes v that have interacted with u over time, along with the corre- sponding interaction fcatures et',, and timestamps t' Based on this temporal noighborhood, the representation of node u is updated as follows:
((() (E(N ((),)())))))))))))))))) -f,e) (u.e,t) (eetteeeel (v)
(3)
(()((t) (t) (PDATE(") (A (t),
(4)
3

---

Published in Transactions on Machine Learning Research (04/2025)
where AGG is a permutation-inwan invariann function, such as summation attention, that maps node u's neighbors to an aggregated vector, which is passed to the UPDATE function, producing the updated representation for u. Different variants of these functions have been studied in the literature, such as graph convolution (GCN) (Kipf & Welling) 2017), or an attention- mechanism (Veličković et al. 2018 where each considered neighbor is aggregated based on learned attention value.
In addition to MP components, a temporal projection framework is introduced to account for phases of inactivity when node is not involved in any event. This ensures the representation of inactive nodes continue to evolve over time, capturing the temporal dependencies critical for downstream tasks. The temporal projection can take various forms, such as a simple Multi-Layer Perceptron (MLP) (Kumar et al. 2019a), an attention-based module (Rossi et al. 2020b), or other temporal modeling schemes. For simplicity in our thcoretical analysis, an MLP-based projection is often assumed, where the time difference and the current representation are used to update the node's representation.
2.2 Expressivity Framework Based on Information Flow (IF)
The aforementioned update scheme illustrates that node's representation in DGs evolves temporally, with its trajectory heavily influenced by the composition and activity level of its local neighborhood. Nodes that are consistently involved in events or positioned within close proximity to evolving nodes demonstrale partic- ular dynamic representations over time, highlighting the interdependent interplay between network structure and temporal dynamics in shaping node embeddings. In this study, we aim to extend our understanding clucidate the precise mechanisms by
from rigorous theoretical perspective. Our primary objective which individual components of the update scheme influence node representations. By decomposing the update process and analyzing its components, we seek to develop a comprehensive mathematical framework that captures the essence of temporal node embedding evolution. This theoretical framework serves mul- tiple purposes. Firstly, it provides insights into how different methods for CTDG representation learning generate distinct node embeddings. By identifying the key factors that drive these differences, we can better understand the strengths and limitations of these methods. Secondly, the framework enables us to predict and explain the performance of different methods across various graph types (e.g., sparse, homogeneous) and applications (e-g., recommendation systems, social networks).
The traditional Weisfeiler-Lehman (WL) framework, which was originally built on ideas from the Weisfeiler- Lehman isomorphism test, and further generalized to higher order variants (Morris et al. 2017). has attracted a lot of attention to modelize graph classifier's capabilities Morris et al. (2019). This approach was recently extended to temporal graphs as temporal-Wi WL (Souza et al. 2022), which iteratively refines node color using node/edge features and limestamps to distinguish non-isomorphic graphs. While effective in some scenarios, the temporal- WL struggles to capture the progression of information over time, particularly the differential impact and propagation of events across snapshots. Its reliance on specific node/odge features further limits its generalization in high-dimensional, real-world settings. This limitation renders the approach not adapted for our aim to understand the effect of each model's components on a node's evolving representation In contrast, the IF view focuses on how events propagate through consecutive graph snapshots, modeling their influence on node/edge representations over time. By examining embedding changes, this view provides a more nuanced understanding of temporal dependencies and the evolution of graph structure, offering practical insights into the applicability of different techniques in dynamic, event-driven contexts.
Specifically, our goal is to examine the change in node embeddings between consecutive time points to un- derstand how events impact the node representations. Naturally and intuitively, the nodes directly involved in the events are expected to undergo the most significant changes in their embeddings, while the representa- tions of other nodes are less alfected. This analysis provides valuable insights into how the graph's 's structure evolves in response to events, offering a detailed view of how different parts of the graph react. By studying the evolution of node embeddings, we can also assess how various methods handle information propagation across the graph. This sheds light on the strengths and limitations of different tochniques, offering guidance their applicability to specific use cases where certain types of event-driven changes are more prevalent.
4

---

Published in Transactions on Machine Learning Research (04/2025)
Given graph-based function f (A. - )/ which produces embeddings from dynamic graph snapshots, assess the quantitative differences (f. fu(G)) using distance metric dy in the embedding space. Based on the graph node distribution Dv, we define the flow quantity as:
Fulfl = EENDY (dy(fa(G()))
This flow quantity influenced by both the graph function f and the node distribution of the t-th DG snapshot. While the exact computation of Fulf] is challenging due to the dynamic nature of the graph, we can approach it from upper-bound perspective efficiently. Notably, this analysis assumes the degree distribution of nodes remains relatively stable between consecutive time snapshots, as changes in degree distribution primarily occur over longer intervals. This stability assumption simplifies the derivation, allowing us to focus on localized structural changes in CTDGs.
Definition 2.1 (Continuous IF). Lel's 's consider the CTDG-lased function f (A, - y, we say that node u is y-flowing if F.lff S.
We consider ||-I| as a suitable p-norm that induces a distance metric dy(:;) the output embodding space y. Using this definition, we aim to compute an upper bound, denoted as 7 which quantifies the potential variation in node's representation following an event. This upper bound serves node's embedding may be affected by modifications in the graph's structure, providing measure of the sensitivity of the representation to such events. Since all p-norms in finite-dimensional spaces are equivalent up to a multiplicative constant, the choice of a specific norm II- affects the upper bound only by such a constant. Throughout our analysis, ||-I| denotes the Euclidean (resp., spectral) norm.
indicator of how much
Theorem 2.2 (GCN-based aggregation). Let's consider a CTTD-bbased function f (A, + y based on L GCN-like layers. After an event between node and another node, the following properties hold for any node not involved in the event:
When L < d(u, i), we have u is 7-flowing with
(u(fa(Gea)) & W |ww||
When L d(u, i), we have a is y-flowing with
(())) & II I Well + tw (rtt) (s)4
where va is the sum of temporal normalized walks of length (L 1) starting from u; the term tu, denotes the normalized shortest path between and the terms W, and W(l are weight matrices involved in the propagation, with W₁ capturing temporal updates; (ss+1(ss) is the difference in memory state for node i, as introduced by the event.
In a nutshell, Theorem 2.2 provides an upper bound with respect to Definition 2.1 for two distinct cases. The first occurs when the node u is outside the L-hop neighborhood of the node involved in the event, and the second occurs when is within the neighborhood. This distinction has practical implications: some instances, such as gene mutation, the next event is likely occur within the same neighborhood, while in others, like recommender systems, it may happen in completely different part of the graph. Consequently, understanding how each component affects the evolving node representation is essential for evaluating its applicability to specific scenarios. While Theorem 2.2 focuses on the GCN-based aggregation schemne, these results can also be adapted to more general attention-
aggregation model described in Section 2.1
Theorem 2.3 (Attention-based aggregation). Let's consider a CTDG function f (A, + y based on L attention- based layers. After an event between node and another node, the following properties hold for any node u not involved in the event:
When L < d(u, f), we have u is 7-llowigg with
(a s deg(u) [[W|I+++ Bl]W.|1]]
5

---

Published in Transactions on Machine Learning Research (04/2025)
Memoryy-Bae Baadd
DyRep Trivedi et all
2019
TGN Rosel et all 2020b SPEDGNN Zhou et al.
2022
Meneagr-Phssiing
SS on C0llo
Based Mothods
Non- Vieorr
Based
TGAT Xu
2020
Random Walks
CTDNE Nguyen et al.
2018
NeurTWs Jin et al. 2022
Non-Message Passing Methods
Update-Based
JODIE Kumaz
2019
DeepCoevolve
Dal
Hybrid Methods
Gripe Cong et
2025 SimpleDyG
Wa
2024
PRES
2024
Figure 1: Categorization and Laxonomy of GRL methods on CTDGs.
When L 2 d(u, i), we have u is y-flowing with
dy(fu(Gr+)) fu(G)) s deg(u) [IW + (s:+1(s:),
where deg(u) denotes the degrec of node u; and is an upper-bound of hidden representation space.
Based on Theorem 2.3 the propagation of information to indirectly involved nodes appears to be influenced by three key factors. The first is the node's connectivity, typically reflected by its degroe. This result is intuitive, as highly connected nodes are more likely to fall within the necessary temporal neighborhood and thus receive frequently occurring updates. The second factor the inclusion of memory component, which can enhance the flow of information by retaining past interactions that relevant for future updates. The third factor is the temporal projection mechanism, which updates node representations over time to reflect changes in the graph's 's structure.
The expressivity upper bounds (cf. Appendix B and C for derivation details) allow us to categorize exist- ing methods in the literature based on whether they incorporate one or more of these components. This calegorization provides insights into how node representations evolve and offers guidance on the suitabil- ity of different methods for various scenarios, depending on the used aggregation framework (in terms of connectivity); memory, and temporal dynamics.
3 Method Categorization and Review
This section reviews GRL methods for CTDGs, categorizing them based on our expressivity framework and exploring how SSRL approaches align with this framework to leverage unlabeled data effectively.
3.1 Method Categorization Inspired by Theoretical Framework
The proposed expressivity framework in Section 2.2 provides a systematic basis for evaluating the strengths and limitations of each method across different graph types. Typically, we can see that model's expressivity depends on the messago-passee passing framework and the usage of memory where relying only on one singlo-hop up- date with minimal memory might have small upper-bound on its TF for distance node, limiting therefore its capacity to melodize the event occurrence, Based these insights, introduce categorization (Figure I to distinguish between the different choices. An additional visual summary is provided in Appendix F
3.1.1 Non-message-passing (Non-MP) methods
One of the carliest approaches to address CTDG is JODIE (uuaar et al. 2019a). The proposed approach captures interaction dynamics between users and items by learning two lypes of embeddings: static embed- dings for long-term characteristics and dynamic embeddings that evolve over time based on interactions. JODIE employs two RNNs (for users and items respectively). whose outputs are interdependent and update upon each arrival of event. To manage inactivity periods, the model incorporates projection step that adjusts embeddings using attention-like mechanism. While the items and users can be seen nodes
6

---

Published in Transactions on Machine Learning Research (04/2025)
within graph, the method doesn't rely on MP mechanism and only leverages temporal projection to up- date representations, allowing node embeddings to evolve over time, even in the absence of interactions. Based on Theorem 2.2 we consider that this temporal evolution is useful for predicting recurring events, such as scasonal product demand in recommendation systems. However, we argue that JODIE struggles with stochastic events, especially in multi-community graphs, where sudden, unpredictable changes are more prevalent. Similarly, DeepCoevolve (Dai et al., 2016) also employs two mutually-reccusivv RNNs to generate embedding trajectories. The key difference is that, unlike JODIE, DeepCoevolve does not use temporal projection and consequently doesn't update node representations based temporal dynamics; instead, it maintains node's embedding consistently between events or interactions.
Another category of None-MP methods rely on Random Walks (RW) to generate node embeddings. Nguyen et al. (018)) proposed a pioneering approach in this area, introducing the concept of temporal RW. In static graphs, RW can be freely generated; but in CTDG, these walks must adhere to the temporal dimension, ensuring that steps occur at non-dccreasing time. This approach proposes to select nodes and generate walks within a node's temporal neighborhood, incorporating probability and threshold-cut stralegies to ensure the generated walks are representative. These walks are then processed using a variant of the Nede2Vec algorithm Grover & Leskovee 2016) to produce node representations for various downstream tasks. Further exploration in this field has refined the sampling strategy, such as considering the graph's 's topology (Jin et al. 2022 While these methods are promising, they fall outside the specific scope of our theoretical analysis, which focuses on methods leveraging MP and temporal dynamics.
3.1.2 Message-passing (MP) based methods
Alongside the Non-MP category, methods propagating information across the graph structure were proposed. One such approach is DyRep (Trivedi et al. 2019). which models both the topological evolution of the graph and the temporal dynamics of node interactions. DyRep updates node's representation by considering its direct neighbors, its previous representation, and a temporal projection technique based on temporal point process, which treats cach incoming interaction event as an observation of a stochastic process. While this method checks many important boxes from our theoretical analysis, there is a notable limitation in its reliance on direct neighborhoods. Nodes beyond one-hop distance (i.c., two or more hops from the event) are updated solely through the temporal projection and non-updated neighbors, without direct MP from further nodes. This can lead over-smoothing when events are concentrated within the same neighborhood, as the aggregation pulls in redundant information and dilutes useful features over time. As result, while DyRep performs well in scenarios where onc-hop interactions are crucial (such as recommender systems and bi-partite graphs), it is less effective in extracting information from longer-range interactions in larger, sparser graphs. These insights and limitations are also applicable to the similar approach DyGNN Ma et al. (2020), which consists of two main components: an update mechanism that adjusts the representation of nodes involved in events using two LSTMs and a propagation unit that disseminates information within the 1-hop neighborhood of the event nodes.
Xu ct al. (2020) extended DyRep and DyGNN by proposing TGAT. They incorporate Functional Time Encoding to map temporal data into high-dimensional space. They also introduce Temporal Graph Atten- tion Layer to aggregate information from a node's temporal neighbors using self-attentio mechanism that accounts for both structural and temporal aspects of the neighborhood. TGAT does not necessarily employ a memory component, as described in Section 2.1 but instead uses the node features directly as the initial representation h.. Therefore, as highlighted by Theorem 2.3 selecting an appropriate number of layers I., and thus defining the I-hop neighborhood, crucial for ensuring effective information propagation.
In similar perspective to TGAT, TGN (Rsssi et al. 2020b) offers a general formalization of CTDG func- tions, akin to the framework we presented in Section 2.1 TGN incorporates both temporal projection and information propagation through attention-baser aggregation. Theorem 2.3 is dircctly applicable to this method, emphasizing the need to adjust the number of layers based on the specific use case. For exam- ple, in recommender systems, setting L = 2 may suffice, while in social networks or molecular graphs, the appropriate value of L should be determined by the graph's structural propertics, such as its diamcter or betweenness centrality, which is captured by the degree term in our provided upper- bound. This approach further explored by Souza et al. (002)), who examined the expressive power of the TGN architecture.
7

---

Published in Transactions on Machine Learning Research (04/2025)
Their work highlighted the importance of the memory component and the advantages of using injective MP functions. Building on these insights, they introduced PINT, which enhances the expressivity of the TGN model by incorporating injective aggregation and update functions, along with augmenting memory states with relative positional features.
The temporal dimension has been further explored in recent work, such as FreeDyG (Tian et al. 2024), which approaches the temporal perspective through the frequency domain. FreeDyG's update mechanism utilizes two LSTMs (for source and target node respectively), along with a merge unit that incorporates information from the direct neighborhood and propagates it to adjacent nodes. Its key innovation lies in the use of the Fast Fourier Transform (FFT) to convert time-domain data into the froquency domain, allowing the model to identify key interaction patterns. The process is then reversed using the inverse FFT to project the data back into the time domain. This approach enables the model to capture temporal patterns in node interac- tions more effectively. However, the method remains limited by its reliance on the direct neighbors of the nodes involved in an event. Consoquently, while FreeDyG can better track various temporal trends in some frequency-structured cases, it still falls short, in fully considering the structural aspects of the graph, as dis- cussed earlier. In the same line, SPEDGNN (Zhou et al. 2022) introduces adaptive spectral Transforms and global Framelet graph convolutions to enable efficient ter- dependency modeling and multi-scale graph feature extraction. Unlike TGAT, it avoids discrete time snapshots by encoding temporal and structural information directly in the spectral domain, ensuring scalable and well-conditineed representations.
A common limitation among many existing methods is their sensitivity to the number of layers, which, if not rell-matched to the graph's topology, can hinder performance in capturing long-range dependencies. Our theoretical analysis highlights this, showing how the upper bound depends on the topology, either through normalized walks or node degrees. Increasing the number of layers, L, does not necessarily enhance long- range dependency modeling and can lead to issues like over-smoothing or wver-squashing This limitation inspired the development of CTAN (Gravina et al. 2024), which addresses information propagation following an event by learning a diffusion function, modcled as a dynamical system governed by a learnable ordinary differential equation. This approach particularly beneficial for CTDGs, where learning temporal patterns from irregularly sampled timestamps essential. Similarly, Petrović al. (2024) proposed Temporal Graph Rewiring, method designed to facilitate message passing between distant nodes in temporal graphs. By employing expander graph propagation, technique with proven success in static graphs, this approach enables more efficient long-range interactions in dynamic settings.
3.1.3 Hybrid methods
Another category of methods in the literature falls outside of our proposed calegorization, adopting a hybrid approach that aims to propagate information within DG without strictly adhering to classical MP schemes.
One primary focus of hybrid methods is addressing the complexity challenges associated with existing CTDG methods. Complexity has two main aspects: computational (lime or operation) complexity and storage (space or memory) complexity. From the computational perspective, Cong et al. (2023) analyzed the impact Coug
of incorporating RNNs and self-attention mechanisms into MP on model accuracy and performance. While these components can enhance performance, the study revealed that they are not strictly necessary to achieve strong results. So, the authors introduced GraphMixer, a simpler yet highly effective architecture composed of a "link-encoder" based on MLPs, a "node-encoder" employing neighborhood mean pooling, and an MLP-based "lass-classfffer.. This design significantly reduces both computational complexity, as MLPs are considerably more time-efficient than attention-based models and RNNss Similarly, SimpleDyG (Wul ct al.) 2024) leverages the Transformer's self-attention mechanism by modeling the dynamic graph as a sequence that captures temporal evolution patterns through an aligmment technique. By transforming the graph into sequence and applying an unmodified Transformer architecture, SimpleDyG demonstrate lower operational complexity, resulting in sparser and more efficient design.
Another focus of hybrid methods addresses batching strategies, emphasizing the need to preserve time depen- dencies, particularly when handling larger batch sizes. One notable approach is PRES (Su et al. 2024), which introduces an itcrative prediction-correctin scheme to mitigate temporal discontinuitics, complemented by a memory-smoothne objective to maintain memory coherence. This method achieves comparable wwwtaaaaaleeefffrrreee performance to previous works while significantly improving speed, enabling the use of larger batch sizes.
8

---

Published in Transactions on Machine Learning Research (04/2025)
3.2 Relevance of Sulf-suue Representation Learning (SSRL) Methods for CTDG
While the methods reviewed in the above categories are capable of extracting meaningful node and graph representations for a varioty of tasks, they typically roquire large volumes of labeled data for effective training. However, the exponential growth of CTDG data across diverse fields in domains such as social networks, recommender systems and biological interaction networks, has rendered manual labeling both labor-intensive and prohibitively costly, As result, SSRL has become increasingly popular approach to address the scarcity of labeled data. SSRL tackles this challenge by creating alternative, auxiliary tasks from unlabeled data to help models learn useful representations. These auxiliary tasks, often referred to as pretraining or pretert tasks, allow models to leverage the inherent data structure as a lcarning signal. By defining these pretext tasks carefully, SSRL enables the model to capture essential features and patterns in the data without needing explicit labels. SSRL has achieved considerable success in fields like CV (YM. et al., 2020 He al,, 2022) and NLP (Radford et al., 2018), forming the backbone of foundational models that underpin today's s AI systems (Bommasani et al. 2021
We would like to highlight that the theoretical analysis provided in Section 2.2 grounded in IF, does not consider the presence of labels. Instead, it focuses on examining how an event influences a node's representation, thereby evaluating the method's expressive power in modeling the CTDG at time t. While this analysis has been instrumental in categorizing various methods as Section 3 it is also highly relevant in the context of SSRL. A method's expressive power is essential for designing effective pretext tasks; for instance, if method has limitations in propagating information over long ranges, contrastive augmentations that depend on capturing longrrange dependencies may fail to deliver robust pretraining outcomes.
In the context of CTDGs, SSRL has significant potential for tasks such as link prediction, anomaly detection, and temporal pattern recognition, where labels are often unavailable or costly to obtain. Additionally, another learning paradigm, semi-supervised learning, has also been explored within the DG context. This approach is particularly useful for node classification tasks where only a subset of nodes is labeled, and the objective is to propagate these labels to the remaining unlabeled nodes. Semi-supervised learning has been widely applied in static graph settings, leveraging known labels to guide the representation learning process for all nodes within the graph. In this work, we focus on SSRL approaches in the context of CTDG. The next section will therefore focus on reviewing various SSRL-based methods within the CTDG context, exploring different approaches for designing pretext tasks that harness the temporal and structural aspects of evolving graphs to learn robust representations.
3.2.1 Pretext tasks for pretraining on CTDG
The commonly adopted pretext tasks for pretraining SSRL model on CTDG can be largely divided into two main categorics: predictive and contrastive pretraining tasks.
Predictive pretraining often relies on auto-regressive modeling paradigms, leveraging the sequential nature of temporal data. This task particularly valuable in domains where data naturally follows temporal or ordered structure, such as NLP timo-scries analysis. In NLP, for example, predicting the next word based on the context of preceding words has been shown to help models learn robust and generalizable representations of language (Kenton & Toutanoval 2019). These learned representations capture semantic and syntactic patterns that enhance performance on a range of downstream tasks. For CTDGs, where the temporal aspect of interactions between nodes is a key feature, predictive pretext tasks are equally relevant. By taking advantage of the temporal ordering of events, an intuitive auxiliary pretext task emerges: predicting the occurrence of the next event. This task involves, at any given time step 1, forecasting the subsequent event at the following time step 1+1, underpinning the majority of SSRL approaches for CTDG.
In the context of link prediction within CTDGs, this task often translates to predicting which two nodes will interact in the next event, such as anticipating user's next purchase or interaction in recommender systems (Kumar et al.) 2019b). Such predictions provide critical insights into temporal dynamics and user preferences, enhancing the model's ability to generalize to unseen events. Specifically, it uses observed events to optimize the negative log-likelihoon of event prediction (Xu et al. 2020 Rossi et al.) 2020b Trivedi et al. 2019). Observed events are treated as positive instances, while non-occurrig events are designated negative instances, which facilitates form of binary classification. However, since evaluating all possible
9

---

Published in Transactions on Machine Learning Research (04/2025)
non-occurring events is computationally infeasible in large-scale graphs, negative sampling is commonly employed. Negative sampling draws a manageable set of negative samples from the potential edges based on a predefined sampling distribution, thereby reducing complexity while still providing informative gradients for learning.
Contrastive pretraining seeks to learn an embedding space by positioning semantically similar pairs, such as augmented versions of the same input or closely related elements closer together, while pushing apart pairs that are deemed dissimilar, referred to as negative pairs. This process helps the model to learn discriminative features that are useful for differentiating between various inputs in downstream tasks. By optimizing this contrastive objective, the model gains an enhanced ability to capture meaningful feature distinctions and similarities within the data. This task has achieved notable success in domains like CV, where it has significantly advanced performance by leveraging image augmentations to create so-called positive pairs.
However, contrastive pretraining has been less explored in CTDGs. Only a few studies (Chen ct al. 2023: Sun al. 2022) have extended this technique to DG. In particular, DySubC (Chen al. 2023) introduced contrastive learning framework designed to maximize the mutual information between each node's embed- ding and the representation of its associated temporal subgraph. DySubC consists of generating time-aware subgraphs for each node by capturing both structural information from the node's neighborhood and tem- poral information from edge timestamps, thereby encoding the dynamics of interactions over time. It then constructs positive and negative samples: positive pairs consist of the central node and its time- weighted sub- graph representation, while negative samples are created by applying structural and temporal perturbations, such as shuffling the subgraph structure or removing temporal weight edges. In the same line, CLDG (Xul et al. 2023) approaches contrastive learning by leveraging temporal translation invariance through sam- pling layer that extracts persistent signals across snapshots. The aim is to maintain node's local and global representations while mitigating semantic shifts introduced by temporal augmentations. Additionally, IDOL makes use of a specialized Personalized PageRank mechanism to capture topological changes, and integrates a ropologymmonitorabl sampling stratogy yielding better reprosentations.
3.2.2 Downstream tasks
Pretraining the model with SSRL pretext tasks aims to learn a robust graph function that provides useful representations for a range of predictive tasks, commonly referred as downstream tasks in the literature. In the context of CTDGs, the literature has focused on three primary downstream tasks:
Link prediction task is the most studied one that involves predicting future links for CTDG. That is to predict the next interaction, identifying both the source and target nodes. Link prediction is particularly relevant in recommender systems, where the goal is to anticipate the next item a user may be interested in. By accurately predicting those links, we can enhance recommendation quality and incrcase the likelihood of user engagement or sales. In the same perspective related to edge, a less explored task in the literature is the one related to edge classification, regression and clustering, the main goal of which is to assign each edge class/valns value/clusterr at future time.
Node-level prediction mainly refers to node classification oariffraaaiionrreresssoonooo in CTDGs, which essentially extends the static node-level prediction tasks by incorporating both the temporal dynamics and topologies. For exam- ple, in social networks, node classification may be used to detect spammers or malicious actors by analyzing patterns in their evolving connections and activities. As networks evolve, so do the relationships between nodes, meaning that a node's classification needs to be updated dynamically basod on new interactions.
Graph-level prediction tasks aim to classify or regress entire graphs rather than individual nodes, making them especially relevant in domains like bioinformatics. For instance, in molecular graph analysis, each graph represents a molecular structure, and the task involves predicting graph propertics such as toxicity or stability based on the configuration of the structure. When graphs evolve over time, the objective shifts to assessing whether the graph remains valid under specific criteria. For example, the addition of certain bonds in a molecular graph may result in a chemically viable or unstable structure.
Our theoretical analysis introduced in Section 2.2 primarily focuses on the impact of events on a node's representation, making it particularly well-suited for link prediction tasks. However, it remains applicable to
10

---

Published in Transactions on Machine Learning Research (04/2025)
other tasks well, these tasks are also fundamentally based on node representations, typically aggregated using pooling or ReadOut functions.
4 Empirical Validation
This section presents an empirical study to validate the theoretical insights and categorization proposed carlier. Specifically; we evaluate the effectiveness of reviewed methods and identify the types of graphs where they perform best. We first outline the experimental setup, followed by discussion of the empirical findings, Additionally, an analysis of the tightness of the proposed upper bounds is provided in Appendix D
4.1 Experimental Setup
Our experimental focus on the popular link prediction task, chosen as a representative challenge within the broader scope of CTDGs. We examine a diverse selection of models from those reviewed in Section 3 focusing models that caplure different facets of CTDG methodologies: (I) JODIE (Kumar et al. 90,,a,, which models evolving embeddings over time; (II) DyRep (Trivedi et al. 2019). designed for capturing dynamic (III) TGN (Rossi et al. 2020b), i.c., Temporal Graph Networks for inductive learning; (IV) TGAT (Xu et al. 2020 known for its allention-based approach for handling lemporal information; (V)
node interactions;
CTAN (Gravina et al. 2024). focused on modeling long-range dependencies within graphs. Experimental
details and hyper-parameterr used to train/test the model are provided in Appendix G.2
In alignment with the selected methods, we choose a set of both synthetic and real-world DG datasets which are representative to the main application areas and unique characteristies of CTDGs. Additional details on each dataset, including design considerations and properties, are provided in Appendix G.1
Long-range graphs are those requiring long-range reasoning to achieve strong performance, as distant nodes or graph regions can influence each other. To capture these interactions, specific information prop- agation mechanisms are necessary, as conventional MP often fails to bridge these long-range dependencies effectively. Evaluating performance on these graphs is crucial to assess a method's ability to transfer infor- mation across distant parts of the graph. For this setting, we use an approach similar to the one proposed by Gravina et al. (2024) where we consider temporal version of the PascalVOC-SPP graph (Dwivedi et al. 2022 Additional information about the generation is provided in Appendix G.1
Bi-partite graphs play a crucial role in applications like recommender systems, a prominent use case for CTDGs. To evaluate how different methods handle interactions between disjoint node sets, which are critical for recommendation quality, we use the TGBL-Wiki dataset from the TGB benchmarks (Huang el al. 2024). This dataset represents a bi-partite network where nodes are editors and Wiki pages, with edges added when an editor modifies page at specific timestamp. Edges carry text features derived from the page edits. Dataset statistics can be found in Table 6 in Appendix G.1
Community-basod graphs consist of nodes grouped into distinct clusters, with relatively few inter- community links compared to intra-community connections. A Barbell graph is a representative example of this structure, where communiyy links act as bottlenecks (Alon & Yahav 2021). making these graphs challenging for temporal MP schemes due to limited information propagation between communities. To evaluate how well a benchmark captures intra-community links, we generate a synthetic datasot using the Stochastic Block Model (SBM) with the NetworkX (Hagberg et al., (208)) package. This involves creating B normalized density over time horizon.
dense communities with connections randomly sampled based As time progresscs, the graph evolves, becoming incrcasingly connected across clusters. For evaluation, we leverage the connection sampling densities between clusters to rank nodes across active communities, mea- suring performance using Normalized Discounted Cumulative Gain (NDCG) (Järvelin & Kekäläinen 2002) More details on the parameters, generation and evaluation process are provided in Table 5 in Appendix G.I
4.2 Results Analysis
Table I presents the average AUC scores along with their corresponding standard deviations. As antici- pated and discussed in Section 3 since the graph structure and topology are important for the downstream classification task, MP based models significantly outperform non-MP approaches like JODIE. This specific
11

---

Published in Transactions on Machine Learning Research (04/2025)
use-case showeases the limitation of this latter family of models, which rather focus on updating the evolved nodes in each event. We additionally see that CTAN is outperforming all the other MP based methods, confirming therefore its ability to track long-range dependencies within the graph.
Table 2 summarizes the average test and validation MRR (Mean Reciprocal Rank) scores, along with standard deviations, for various methods on the real-world bi-partite dataset TGBL-Wiki. The re- sults show that JODIE performs similarly to the MP based methods RyRep and TGAT. While JODIE might theoretically be expected to excel on bi- partite graphs, the dataset's low "surprise factor" measure of how predictable the interactions be- tween nodes are limits its advantages. In this set- ting, capluring long-range temporal and structural dependencies becomes more critical for the down- stream task. Consequently, methods like CTAN and TGN, which are better equipped to model such dependencies, achieve superior performance.
Table 1: Average test AUC (+ denotes standard de- viation) of the different. methods long-range Pas- calVOC 10 and 30 datasets. Best performance per dataset in bold.
Long-Range Graph
Model
PascalVOC 10
PascalVOC 30
JODIE
0.67 + 0.03
0.65 1 0.07
DyRep
0.69 + 0.02
0.70 + 0.02
TGN
0.78 + 0.10
0.71 + 0.04
TGAT
0.77 = 0.02
0.76 = 0.03
CTAN
0.80 + 0.01
0.78 + 0.01
Similarly, p the average test and validation NDCG scores, along with their standard deviations, for the evaluated benchmarks on the SBM community-based synthetic datasets. The results indicate that CTAN achieves superior performance compared to the other methods, as expected, given its ability effectively model long-range dependencies, which is critical to facilitate information to flow within the cluster and to capture community structures. Additionally, TGN demonstrates strong performance, surpassing most methods. These findings align with expectations, as the community- conmunity-based nature of the dataset benefits from the self-attention mechanisms utilized by TGN.
5 Conclusion
In this paper, we presented a comprehensive review of Graph Representation Learning (GRL) on Continuous- Time Dynamic Graphs (CTDGs), emphasizing the critical role of expressivily in capturing temporal and structural dynamics. We introduced an Information-Flon (IF) centric theoretical framework to quantify the expressivity of CTDG models, providing a structured analysis of their performance across graph types and application scenarios. Leveraging this framework, we categorized existing methods, highlighting their strengths and limitations in addressing key challenges such as long-range dependency modeling, temporal irregularity, and sparse data. Additionally, examined the growing relevance of Self self-Supervised Representa- tion Learning (SSRL) for CTDGs, offering insights into predictive and contrastive pretraining tasks and their applicability to real-world datasets. Empirical validation supported our theoretical insights, demonstrating the nuanced trade-offs between different methods across synthetic and real-world datasets. By bridging theoretical foundations with practical evaluations, this work provides a robust roadmap for advancing GRL in dynamic settings, enabling more expressive and adaptable models for a broad spectrum of applications.
Table 2: Average Test and Validation MRR. (+ de- notes standard deviation) of the different approaches on the real-world Bi-Partite dataset TGBL-Wiki. Best performance in bold.
Table 3: Average Test and Validation NDCG scores (+ denotes standard deviation), on the considered benchmarks on the SBM Community- syn- thetic dataset. Best performance in bold.
Bi- Partite Graph
Community- Graph
Model
Model
Test
Val
Test
Val
JODIE
0.261
0.123
0.325 + 0.149
JODIE
0.8491
0.003
0.863 + 0.002
DyRep
0.263 0.005
0.317 + 0.008
DyRep
0.811
0.005
0.819 +'t 0.006
TGN
0.577 = 0.015
0.617 = 0.009
TGN
0.8559 + 0.0264
0.8572 = 0.0273
TGAT
0.282 = 0.022
0.323 = 0.008
TGAT
0.8459 + 0.0001
0.8564 = 0.0002
CTAN
0.611 + 0.011
0.647 + 0.012
CTAN
0.868 + 0.002
0.872 + 0.003
12

---

Published in Transactions on Machine Learning Research (04/2025)
Acknowledgments
We would like to thank the entire ACE (AI Center of Excellence) at King (a part of Microsoft) for their continuous support, insightful discussions, and collaborative spirit throughout this project.
We express our sincere gratitude to King's OSC (Open Source Council) for their invaluable support through- out the open source release process. Special thanks go to Colin Cashin, Nate Cleveland, Hugo Cura, Paul Jordaan, David Lorenzo, and Raul Pareja for their dedicated efforts in facilitating the publication and code release process. We are also deeply appreciative of King's CTO, Eric Bowman, for his careful review and approval of our code huttps://githun com www.ccoo..ii/ee.e.eeeeeeee...eee wttp://nn//ggiioooottl
Additionally, we are grateful for the diligent review of our manuscript from legal and commuicatiins per- spectives. Special thanks to Alexandra Stark and Tim Elgar for their essential contributions in ensuring alignment with legal and communications standards.
This work was partially funded by the Wallenberg AI, Autonomous Systems and Software Program (WASP). We also acknowledge the collaboration between King/Microns Mierosoft and KTH Royal Institute of Technology, which made this research possible.
References
Uri Alon and Eran Yahav. On the bottlencck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021. URL http:/::///pprrrriis..eeee////// 1800Ph0CVH2
Jiandong Bai, Jiawei Zhu, Yujiao Song, Ling Zhao, Zhixiang Hou, Ronghua Du, and Haifeng Li. A3t-gen: Attention temporal graph convolutional network for traffic forecasting. ISPRS International Journal of Geo-Information, 10(7):485, 2021.
Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, et al. On the opportunities and risks of foundation models, 2021.
Ke-Jia Chen, Linsong Liu, Linpu Jiang, and Jingqiang Chen. Self-supervised dynamic graph representation learning via temporal subgraph contrast. ACM Transactions on Knowledge Discovery from Data, 18(1): 1-20, 2023.
Weilin Cong, Si Zhang, Jian Kang, Baichuan Yuan, Hao Wu, Xin Zhou, Hanghang Tong, and Mehrdad Mahdavi. Do we really need complicated model architectures for temporal networks? In The Eleventh International Conference on Learning Representations, 2023. URL https::/openrevier: wwt./eeuun/rriiii ayPPc0SyLv1
Hanjun Dai, Yichen Wang, Rakshit Trivedi, and Le Song. Deep coevolutionary network: Embedding user and item features for vecommendation. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016.
Nan Du Hanjun Dai, Rakshit Trivedi, Utkarsh Upadhyay, Manuel Gomez-Rodrigucz, and Le Song. Recur- rent marked temporal point processes: Embedding event history to vector. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and dala mining, pp. 1555-1564 2016.
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Aduances in Neural Information Processing Systems, 35:22326 22340, 2022.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantun chemistry. In International Conference Machine Learning, pp. 1263 1272. PMLR, 2017.
Alessio Gravina and Davide Bacciu. Deep learning for dynamic graphs: models and benchmarks. JEEE Transactions on Neural Networks and Learning Systems, 2024.
13

---

Published in Transactions on Machine Learning Research (04/2025)
Alessio Gravina, Giulio Lovisotto, Claudio Gallicchio, Davide Bacciu, and Claas Grohnfeldt. Long range propagation continuous-time dynamic graphs. Tn Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 16206 16225. PMLR, 21 27 Jul 2024. URL https://proceddin/g mlr. www..prees/veeeee /235// /at////rainnaaaa html
Aditya Grover and Jure Leskovec. Node2Vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 255-864, 2016.
Benjamin Gutteridge, Xiaowen Dong, Michael M Bronstein, and Francesco Di Giovanni. Drew: Dynamically rewired message passing with delay. In International Conference on Machine Learning, pp. 12252-12267. PMLR, 2023.
Aric Hagberg, Pieter Swart, and Daniel A Schult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States). 2008.
Kaiming Hc, Xinlci Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders are scalable vision learners. In Proceedings of the IEEE/CVE conference on computer vision and pallern recognition, pp. 10000-1609, 2022.
Shenyang Huang, Farimah Poursafaei, Jacob Danovitch, Matthias Fey, Weihua Hu, Emanuele Rossi, Jure Leskovec, Michael Bronstein, Guillaume Rabusscau, and Reihanch Rabbany. Temporal graph benchmark for machine learning on temporal graphs. Advances in Neural Information Processing Systems, 36, 2024.
Kalervo Järvelin and Jaana Kekäläinen. Cumulated gain- evaluation of ir techniques. ACM Transac- tions on Information Systems (TOIS), 20(4):422-4466 2002.
Ming Jin, Yuan-Fang Li, and Shirui Pan. Neural temporal walks: Motif-aware representation learning on continuous-time dynamic graphs. Advances in Neural Information Processing Systems, 35:19874-19886, 2022.
Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: A survey. Journal of Machine Learning Research, 21(70):1-73, 2020.
Steven Kearnes, Kevin McCloskey, Marc Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolu- tions: moving beyond fingerprints. Journal of Compuler-Aide Aided Molecular Design, 30(8):595-660 608, 2016.
Jacob Devlin Ming- Wei Chang Kenton and Lee Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of na..I-HHLT, volume 1, pp. Minneapolis, Minncsota, 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Confer- ence on Learning Representations, 2015.
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Leurning Representations (ICLR), 2017.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '19. ACM, July 2019a. doi: 10.1145/3299250033330 URL http:
//dx. doi. ooo/ooorg/10.. 1 3338033399200033388555 3330895
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & dala mining, pp. 1269- 1278, 2019b.
14

---

Published in Transactions on Machine Learning Research (04/2025)
Linyuan Lü, Matúš Medo, Chi Ho Yeung. Yi-Cheng Zhang, Zi-Ke Zhang, and Tao Zhou. Recommender systems. Playice reports, 519(1):1-48) 49, 2012.
Yao Ma, Ziyi Guo, Zhaocun Ren, Jiliang Tang, and Dawei Yin. Streaming graph neural networks. In Proceedings of the 43rd international ACM SIGIR conference on research and development in information retrieval, pp. 719-721 -28, 2020.
Christopher Morris, Kristian Kersting, and Petra Mutzel. Glocalized weisfeiler-lehman graph kernels: Global- local feature maps of graphs. In 2017 IEEE International Conference on Data Mining (ICDM), pp. 327-336. IEEE, 2017.
Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 4602-4609, 2019.
Giang Hoang Nguyen, John Boaz Lee, Ryan A Rossi, Nesreen K Ahmed, Eunyee Koh, and Sungchul Kim. Continuous-tine dynamic network embeddings. In Componion proceedings of the the web conference 2018, pp. 969 976, 2018.
Katarina Petrović, Shenyang Huang, Farimah Poursafaei, and Petar Veličković. Temporal graph rewiring with expander graphs. In ICML 2024 Workshop on Geomelry--graanded Represenlation Learning and Generative Modeling, 2024. URL
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding with unsupervisod learning. 2018.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. In ICML 2020 Workshop on Graph Representation Learning, 2020a.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning dynamic graphs In ICML 2020 Workshop on Graph Representation Learning, 2020b.
Youngjoo Sco, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence model- ing with graph convolutional recurrent networks. In Neural Information Processing: 25th International Conference, ICONIP 2018, Siem Reap, Cambodia, December 13-16, 2018, Proceedings, Port I 25, pp. 362-373. Springer, 2018.
Amauri Souza, Diego Mesquita, Samuel Kaski, and Vikas Garg. Provably expressive temporal graph net- works. Advonces in neural information processing systems, 0182257-32269) 2022.
Junwei Su, Difan Zou, and Chuan Wu. PRES: Toward scalable memory- based dynamic graph neu-
ral networks. In The Twelfth International Conference Learning Representations, 2024. URL
Fei Sun, Jun Liu, Jian Wu, Changhua Pei, Xiao Lin, Wenwu Ou, and Peng Jiang. Bert4rec: Sequential recommendation with bidirectional encoder representations from transformer. In Proceedings of the 28th ACM international conference on information and knowledge management, pp. 1441 1450, 2019.
Li Sun, Junda Ye, Hao Peng, and Philip S Yu. A self-supervised riemannian gnn with time varying curvature for temporal graph learning. In Proceedings of the 31st ACM international conference on information & knowledge management, pp. 1827-1836, 2022.
Yuxing Tian, Yiyan Qi, and Fan Guo. Freedyg: Frequency enhanced continuous-time dynamic graph model for link prediction. In The Twelfth International Conference on Learning Representations, 2024. URL
15

---

Published in Transactions on Machine Learning Research (04/2025)
Rakshit Trivedi, Mehrdad Farajtabar, Prasenject Biswal, and Hongyuan Zha. Dyrep: Learning represen- tations over dynamic graphs. In International Conference on Learning Represenlations, 2019. URL
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.
Graph Attention Networks. In ICLR, 2018.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity deep neural networks: analysis and efficient estimation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianche and R. Garneut (eds.), Advances in Neural Informalion Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: http://rooedddi...uuu..........e http://r...le//pppp///////////1 18b-Peaprr
6B44999666607044$$666666632282 PBp pdf
Duncan J Watts and Steven Strogatz. Collective dynamics of horall-worldnettoorro nature, 393(6684): 440 442, 1998.
Shu Wu, Yuyuan Tang, Yanqiao Zhu, Liang Wang, Xing Xie, and Tieniu Tan. Session-based Recommendation with Graph Neural Networks. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pp. 346-353, 2019.
Yuxia Wu, Yuan Fang, and Lizi Liao. On the feasibility of simple transformer for dynamic graph modeling. In Proceedings of the ACM on Web Conference 2024, pp. 870 880, 2024.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive representation learning temporal graphs. In International Conference on Learning Representations, 2020. URL
https://openrevier httppp/rrrrrioooooooooooooo//aaa
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How Powerful are Graph Neural Networks? In 7th International Conference Learning Representations, 2019.
Yiming Xu, Bin Shi, Teng Ma, Bo Dong, Haoyi Zhou, and Qinghua Zheng. Cldg: Contrastive learning on dynamic graphs. In 2023 IEFE 39th International Conference on Data Engineering (ICDE), pp. 696-707. IEEE, 2023.
Asano YM., Rupprecht C., and Vedaldi A. Self-labelling via simultaneous clustering and representation learning. In International Conference on Learning Representations, 2020. URL https::/openrevies: net/forum?id-Hie jyBFPr
Bingxin Zhou, Xinliang Liu, Yuehua Liu, Yunying Huang, Pietro Lio, and Yu Guang Wang. Well-conditioned spectral transforms for dynamic graph representation. In Learning on Graphs Conference, pp. 12 1. PMLR, 2022.
16

---

Published in Transactions on Machine Learning Research (04/2025)
The Appendix of
Expressivity of Representation Learning on Continuuu--Time Dynamic Graphs: An Information-Flow Centric Review
A Preliminaries
Notations For our theoretical analysis, we consider the following notations:
d(u, u): is the shortest path distance between node u and node
deg(u): denotes node u's degree, i.e (.(())
dy is the distance within our output manifold V.
The node involved in the event. denoted as
denotes the number of layers used in the considered model.
Problem Sct-up. As our goal is to understand the effect of each component on the model's evolving dynamics, we consider the most general use-case a CTDG function. Typically, we consider that our model follows the proposed components Section 2.1 Specifically, we consider the model based on the described temporal message-passing (either through a GCN-like aggregation attention-based). We also consider that it makes use of the memory state and not only the node's individual representation. We additionally consider that the model encompasses Linear temporal projection function to take into account temporal inactivity.
Theoretical Assumptions. For our theoretical analysis, we assume that all models use 1-Lipschitz continuous activation functions, which covers the majority of commonly used functions, including ReL.U, LeakyReLU, and TanH (Virmaux & Scaman 2018). We also focus on the effect of a single event, in contrast to the more practical setting where a batch of events is considered. Under this single-event assumption, the node distribution this assumption may not strictly hold when processing batches, consider that deriving the specific bounds will yield the same theoretical insights on the considered method's ability to propagate information.
be treated static between two relevant time shot of the graph at t and t ++1. 1. While
B Proof of Theorem 2.2
Theorem (GCN-based aggregation). Let's consider a CTDG-based function f (A, + y based on L GCN-like layers. After an everd betweeen node and another node, we have the following:
For any node u not involved in the event and for which d(u,i) have is 7 flowing with:
I dy dyL(I(Ge)))) @.l| [0
FFor any node u not involved in the event and for which d(u,i) have is 7 flowing with:
L II 1=1
(y( & [ t. WWll A (si)l.
2,411
with th being the sum of temporal normalized walks of length (L (L-1) starting from node and tust is the normalized shortest path between and i.
17

---

Published in Transactions on Machine Learning Research (04/2025)
Proof. We consider the case in which the propagation is done using GCN-like aggregation. Specifically, we recall that GCN update at layer & for a node within neighborhood can be written as:
w (f-))-1) v(I (eg u)) (eg(v))
h (0))
E
(5)
UEN)
where W(O E Ree--xer is the learnable weight matrix with being the embedding dimension of layer é and ((6) is the activation function of f-th layer.
Proof's Intuition. In our proof, we want to see the effect of an event on the node representation node u within our graph. Typically, the set of nodes can be divided into two main categories. One first set which is within reachable distance of where the event happened in respect to the number of pressae-passsing layers. A second set, which is not reached based the chosen number of message- pastaggg---asng.g... We approached the proof therefore by considered each set independently, where upper- upper-bound bound the expected change in each set. This latter division gives intuition on how the considered model interacts with the different sets and consequently reflects its ability to propagate information within the graph after an event occurrence.
B.1 For nodes involved in the event and for which d(u,i)
In this part, we consider the nodes that are not directly connected in the events and that are distant from the nodes involved the events. Specifically, we consider that the number of propagation < d(u, i) with u being the node and i being the node included in the event and In this proof, we consider that we are dealing with a GCN-like propagation, we can therefore right the following:
d)([(G"') = 11 -12.111
w(0) (e-1) p,1+1
= (1)
Σ
((1 + deg(u) (1)((1 + deg(v)
110
(1)
Σ
( + dog(u)) + deg(v))
veN(a))
W(0)
((-1)
Σ
b,1+1
Σ
wEN(() (11 + deg(u))(1 deg(v))
vEN(w))(u) V(1 + deg(u)) (1) deg(v))
[ h (8-1))
=| Σ
((1 +1+ +eg(u) (egg(u))(( deg(v))
(EN((w)
18

---

Published in Transactions on Machine Learning Research (04/2025)
We that the right term on the resulting inequality is related to the one are considering. Therefore, by iteratively doing the same process, we get the following:
dy(f(G ).((')) = |1 u
|M 1
E =EN(UU()
((1 + deg(u))) + deg(w))(1 + deg(i)) ... (1 deg(y)) deg(z))
1=1
Will
11
Σ
V(1+ + (1+deg()))(( + deg(w))(1 + deg(i)) ... (1 + deg(y)) + deg(z))
1=1
=EV(Ui
$ i.
||
with i. being the sum of temporal normalized walks of length (L 1) starting from node u.
B.2 For nodes not involved in the event and for which L 2 d(u, i)
Similar to the previous part, we have the result:
dy(f(G+t)) = |1 1
[/ (0)
- IIlwnn Σ
((1 + deg(u))(1 deg(w))(1 + deg(i)) ... (1 + deg(y)) / deg(z))
sEA(H) 1=1
In the specific case that L 2 d(u, i), we know that a part of the neighborhood contains one of the nodes that are subject the event Therefore we have the following:
1/ |1 2..+1 h
dy(((G()), S In
Σ
d ueV( ((1 + +oggww))
deg(w)) + deg(i)) ... (1 + deg(y)) deg(z))
1 - 2
Σ
((1 + (eg(())(( deg deg(i)) (1 + deg(y)) deg(z))
1=1
[| - h
deg deg(())(11 (1)
deg(w)) deg(i)) ... (l deg(y)) (1 deg(i))
The first term like the previous approach only dependent on temporal projection aspect, while the second is rather dependent on the difference terms of memory of the updated node involved in the event. We therefore find the following:
19

---

Published in Transactions on Machine Learning Research (04/2025)
|1 11 h 1 ZeN(s) (1 (eg(u))) deg(w)) deg(i)) ... (1 deg(y)) (1 + deg(z))
dylf(GH)):((G..) -
E
[[ A (s:)
with U. being the sum temporal normalized walks of length (L 1) starting from node and th the normalized shortest path between and
C Proof of Theorem 2.3
Theorem (Autention-based aggregation). Lel's consider a CTDG function f (A, - y based on L attention-based layers. After an event between node and another node, we have the following:
For any node u not involved in the event and for which d(u, have is 7 flowing with:
(y([u(Ce))) S [[e]
For any node not involved in the event and for which I. d(u, have is y flowing with:
dy dy(fu(Gr=)),a((G)) S [W | A(s),,
with deg(u) being the degree of node and B an upper-bound of hidden reprosentation space.
Proof. Proof's Intuition. Similar to the previous proof, we consider in this case that the model is rather based on an attention framework to aggregate the information within the neighborhood. We start therefore by analyzing the effect of this addition. We afterwards, and in the same way as the GCN-case, derived the upper-bound for each set of nodes based on the distance to the event.
In this part rather focus attention-basel aggregation within our temporal neighborhood, which formulated the following:
(
((++)) - (00)
E (EV((N
(0,1))
(6)
Let's consider a node u at time t, we have the following:
(e+1)) 1001 -
Σ
Oz
((-1) (t-1)
11g
Σ ai (1 (t)
kEN,(++1)
kEN
Σ
1
(1+1) ((+1)
+ a
(++1) (5) (t+1)
/1 0 1/
-a ftg
(1) (1)
(t+1(
Σ
la
(++0
(1) + h la a 1']
(t+1)
(E+1
From the previous inequality, we see two main effects. A first effect which dependent on the attention mechanism and second effect which is dependent the neighbor's representations.
20

---

Published in Transactions on Machine Learning Research (04/2025)
We recall that the attention mechanism is formalized as follows:
( exp Sj
aij
(1)
(7)
EKEN(s) exp (ik
(1)
with:
LeakyReLU (w [o] (1) (0))
(8)
where 8/ (2) the "memory' of node i at time i, w is a learnable weight vector, and [0/0 0 denotes the concatenation of o and 40 In this perspective, and since Leaky-ReL.U 1-Lipschitz continuous Virmaux & Scamaa 2018), we have the following:
|a lt+1)
(1) s [[ (++1) (((
- (s(
(9)
(10)
C.1 For any node u not involved in the event and for which d(u,i)
Let's consider node that is involved in the event and for which < d(u,i). The elements within the neighborhood of this specific node are not subject to memory update. Additionally, for the node u, the difference in memory is only dependent on the time projection. Hence, if we assume that this is linear, we have the following:
(t+1) [a ag S | W, 2A.
(2)
Without loss of generality, we additionally assume that the representation space is bounded; specifically for each node E W at any timestamp 1, there exists a finite constant Bi()) 2 0 such that:
|| [ < B where B max (() = | || s B for all and t
wEN,
From these two clements, we find the following:
[ (++1)
h SS
A(sa) + BBW, PA?
AEN(u)
C.2 For any node u not involved in the event and for which 2 d(u,i)
Let's consider node that is not involved in the event and for which L 2 d(u,t). For the considered node u, one of the nodes i included in the event is within the neighborhood, then its memory will be updated as well. From the previously derived inequality, we can directly write:
[1((+1] - 1
Σ kEA(T)
A(sx) + w/ll
Σ
A(sx) + Bl + A(s:) + BI|
kEA(
Σ
[W.[+BB[WWlJ++ACC + BI
REA(W))(
s deg(u)
+ +*x))
21

---

Published in Transactions on Machine Learning Research (04/2025)
D On the Tightness of the Provided Upper-Bound
In Theorem 2.3 we derive upper bound on the expected norm difference in node's representation belween two conseculive time steps. To evaluate the lightness of this theoretical bound, we analyze the TGN model (Rosii et al. 2020bb since it is the closest model to align out with our proposed theoretical framework that is adapted on the general framework of a CTDG function presented in Section 2.1
We note that. in our theoretical proof, we don't consider event features (which are related to the added edges). Consequently, in order to align with our desire to study the tightness of the bounds, we make an adaptation of our derivations to take into account a TGN.
We adapt the Equation equation to take into account edge features as it is the case in the TGN model, we have the following:
exp (ij
(1) ag
(11)
(t) Σ KEE exp
(ikk
with:
= Lea (w (s s fa te'..)).
(12)
with Wy being the learned weight matrix used with the edge features and e' = le,, A.} is the concatenated
vector of the edge features and the limestamp as explained Rossi el al. (2020b). By following this
formulation and using the triangular inequality, we can adapt the upper- upper-bound bound provided in 9 follows:
(1+1) a 11 < (lll((s.)0(s) + [ اللر ||
[wll(ss.))(ss)) + | +
It is important to note that our theoretical analysis assumes the effect a single event on the graph, meaning we consider one event per batch, therefore treating t and t+ as consecutive time steps and only one event coming in per time step. However, in real-world datasets, time is tracked in an absolute timeline, and events may not occur at evenly spaced intervals. To align with our theoretical framework, normalize the time intervals in these datasets, effectively mapping the absolute timestamps to relative scale that satisfies our assumptions.
Based on our previous adaptation, in Theorem 2.3 we derive an upper bound on the expected norm difference in a node's representation between two consecutive time steps. Specifically, we compute the difference in node representations using both our theoretical estimates and empirical values obtained from a trained model. Following the structure of the theorem, we examine two primary cases: (1) nodes within the neighborhood of nodes involved in events and (2) nodes outside this neighborhood with d(u, i) > L. Figure 2 illustrates the results in Log-Scale, highlighting the difference between the analytical upper bound and the empirical values observed when an event occurs.
We observe that the bounds are notably tighter in cases where L 2 d(u, i), as the representation differences are primarily influenced by the temporal projection component, in line with our theoretical analysis. However, for nodes within the neighborhood of the event, the proposed upper bound is somewhat looser, likely due to simplifying assumptions made in the theoretical derivation.
E Empirical Insights of the Information-Flow
As discussed in Section 2.2, the concept of Information-Floww serves as a metric for assessing the influence of an event on the graph's node embeddings. In particular, when new edge added (i.c., an event occurs), it is expected that the node embeddings will be updated accordingly. If no update observed, for example, in edge prediction scenario, the corresponding probabilities remain unchanged, indicating that the event
22

---

Published in Transactions on Machine Learning Research (04/2025)
Tightness of the Theoretical Upper-Bound on tgbl-wiki
d(u,
1.0
L d(u,
0.8
Density
0.6
0.4
0.2
0.0
-6
-2
4
Difference between Theoretical and Empirical Bounds (Log-Scale)
Figure 2: Difference between the theoretical upper-bound and the empirical values of the difference in norms for node u's representation.
Information Flow and Test MRR with Layers- TGBL-Wiki
0.14
0.38
Change in Information-Finn Flow
0.13
0.36
0.12
0.34
Test MRR
0.32
0.10
0.30
0.09
0.28
3
Layers
Figure 3: Information Flow change after an event occurring and the Average Test MRR on the TGBL-Wiki dataset for different number of layers.
provides no additional information. Ideally, the embeddings of all nodes in the graph should be updated in response to the event.
From the thcorctical results, one key determinant of improved Information-Flor is the mumber of message- passing layers. To illustrate this, the normalized average norm difference of node embeddings is evaluated following an event in the TiBL-Wiki dataset, while varying the number message- paassaggpassing layers. Specifi- cally, the TGAT model is considered with different configurations (I. 1, 1,2,3) during inference. As depicted in Figure (left axis), models with a larger number of layers exhibit a greater degree of information propa- gation across the graph.
23

---

Published in Transactions on Machine Learning Research (04/2025)
However, it should be noted that although increased information flow is generally destrable, it does not necessarily lead to superior downstream performance. This discrepancy is often attributed to over-smoothing, a phenomenon well-documented in the literature. In certain graph topologies, such as bipartite structures, a model with smaller number of layers can outperform deeper models. Figure 3 (right axis) further reports the Average Test MRR for the same TGAT models, highlighting this effect.
F Visual Summary of the Theoretical Insights
Our work position itself as a review of the available methods the context of CTDGs. Specifically, our primary goal is to offer unifying perspective on CTDG methods, especially in self-supervised settings, so that given a graph structure and constraints, the user can choose the right method be usod to maximize the performance. In this perspective, our provided "Information-Flow" in Section 2.2 studies how method's components can affect its ability to propagate and update information after event occurrence. This is relevant to understand how different methods shall interact with different topologies. In this perspective, Table provides a visual summary of the different insights that were derived from our theoretical analysis and the computed upper bounds. Specifically, it highlights the key components influencing the "expressivity" of a temporal graph function, detailing their functional roles, associated mathematical constraints, and practical implications. The table summarize how factors such as memory usage, projection mechanisms, neighborhood depth, event features, and attention mechanisms contribute to the propagation of information over time, while also delineating the trade-offs in computational complexity and model stability.
Component
Description
Bound Terms
Practical Effect
Memory Usage
Tracks historical interactions for each node.
(ss)): Change in memory state for nodes involved in events.
Improves temporal dependency modeling: sensitive to memory size and update mechanism.
Temporal Projection
Projucts node representations forward during inactivity.
WW):: Temporal projection weight matrix norm.
Caplures time-varying node states but adds sensitivity to temporal sparsity.
Aggrogator Type
Mechanism combining ueigh- borhond information (e-g., sum- mation, attention).
Aggrogstor-dependeet: 2.
Influences expressivity and com- putational rost; enables fine- grained updates.
[W for GCN, degree-based terms for attention.
Neighborhood Depth (L) Number layers the message- passing scheme, affecting the propagation range.
Wa, dyy: Normalized walks or shortest paths.
Coutrols the range of infor- mation flow but risks over- smoothing or over-squashing.
Event Features
Includes edge-related attributes (e.g., interaction type, times- tamps).
[W] B: Interaction with edge features through pro- jection and event-related adjustments..
Enhances representation with context-specific interactions but may increase model complexity.
Attention Mechanism
Dynamically weighs neighbor contributions using learnable pa- rameters.
Degroe-based (deg(u)) and learned weights (W).
terms
Enables selective information propagation, particularly useful for graphs with heterogeneous links.
Graph Topology
Structural characteristies such sparsity, degree distribution, and community structures.
vie myy; Impact of topol- ogy wask- terms.
Affecls long-range dependency modeling and suitability for spe- graph types (e.g., bipartite).
Table 4: Visual Representation of the theoretical insights from the computer upper- bouud- in Theorem 2.3
and 2.2
24

---

Published in Transactions on Machine Learning Research (04/2025)
Table Parameters for generating the stochastic block model dataset.
B
N
NB
Pij
Pi,i
Egen,ke
100
1000
30
0.025
0.25
[6, 20)
G Datasets and Implementation Details
G.1 Synthetic Datasets
To perform further experimentation and to validate our theoretical insights, we evaluated our considered benchmarks on a number of graph types. Since finding accessible real datasets has been a challenge, we have opted rather use synthetic and generated datasets in which we can control the different settings and confirm our hypothesis. In the following section, we describe in details our data generation process and we give additional information to easily reproduce this process.
Long-Range Benchmark Long-range graphs require long-rann rangr reasoning to achieve high performance, as interactions between distant nodes or graph regions can significantly influence outcomes. To effectively caplure these relationships, specific information propagation strategies are necessary, standard message- passing techniques often fall short in handling these long-range dependencies.
Our objective is to evaluate the performance of the reviewed benchmarks in handling this category of graphs. Following the methodology from prior work (Gravina et al. 2024), we introduce a temporal component to the static PascalVOC-SP graph from the Long-range benchmark dataset (Dwivedi et al. 2022 This dataset comprises graphs generated from images, where each node represents a region within the image that belongs to a particular class. The temporal dimension is introduced by assuming an ordered sequence in node appearance, progressing from the top-left to the bottom-right of the image. For further details, refer readers to the original work (Gravina et al. 2024
Community-based Graphs. One part of our experimental evaluation consists of considering a graph which is based on communities so as to assess the method's ability to propagate information within different clusters. In this perspective, we first generate B blocks of dense communities with NB nodes in each community, resulting in N nodes in separate disconnected components with connection density of Pi, At each timestep we select k. = 4 pairs of communities that we (pairwise) connect over random number tgen.ke E [6, 20). Specifically, this selection follows normalized density of fo 0.025, normalized over a sampled time horizon fyen.k, over which we connect the pair of clusters. Naturally, as time progresses, the graph becomes progressively more connected, and its topology evolves accordingly. The used parameters are reported in Table 3. For the evaluation, we leverage the normalized sampling densities between cluster pairs, derived from the data generation procedure, to identify which communities are most likely to be connected. Based on this, we formulate the task of ranking nodes within the active clusters and evaluate the results using Normalized Discounted Cumulative Gain (NDCG) (Järvelin & Kekäläinen, 2002). We choose the NDCG here, as we know which communities should be more and less likely to be connected during that specific timestep and their true relevance score as they are directly derived from the sampling of stochastic block model used.
Bi-Partitc Datascts. For this category of graphs, we have focused on using the real world graph TGBL- Wiki dataset, which is part of the TGB benchmark datasets (Huang et al., (2024). The dataset is a bi-partite network where Wiki pages and editors are nodes, while an edge is added when user edits page specific timestamp.
Homogeneous Graphs. We additionally experimented with homogeneous graphs, i.e. graphs where nodes and edges belong to the same type. This type of graph encompasses wide range of applications, including social networks, transportation systems, and other domains where graph structures are uniform. For this evaluation, we used an adaptation of the real world TGBL-Coin dataset which part of the TGB benchmarks (Huang et al. 2024) too. This dataset contains crypfocurrency transactions, where each node
25

---

Published in Transactions on Machine Learning Research (04/2025)
is address and each edge denotes the transfer of funds from one address to another at certain time. The results are reported in Table 7
For both the real and synthetic datasets, characteristics and information about the graphs utilized in the experimental results of the study are presented in Table
Table 6: Statistics of the graph datasets used in our experiments.
DATASET
# #NoDES
# EEGeS
# EDGE FEATURES
# SURPHISE INDEX
VOPASCALVOC 10
2,671,704
2,660,352
14
1.0
VOC 30
2,990,466
2,906,113
14
1.0
TGBL- WIKI
9,227
157,474
172
0.108
SBM GRAPH
3,000
172,570
0
1.0
Table 7: Average Test and Validation MRR (+ denotes standard deviation) of the different approaches on an adaptation of the real-world dataset TGBL-Coin. Best performance in bold.
Homogeneous Graph
Model
Test
Val
JODIE
0.713 + 0.028
0.552 + 0.131
DyRep
0.688 = 0.007
0.697 0.007
TGN
0.738 0.007
0.731
0.006
TGAT
0.748
0.025
0.765 + 0.023
CTAN
0.709 0.003
0.754 + 0.006
G.2 Experimental Details
For our experimental setting the long-range datasets, we used the Adam optimizer (Kingma & Bag 2015) with 1c-04 lcarning rate and a batch size of 256 for training, validation and testing, We set the palience to 20 and we optimize the F1-Score, and the learning consisted of 20 epochs. All the experiments were run 5 times to reduce the effect of initialization and other randomization parameters. For the model's parameters, we directly used the best paramcters reported previous work (Dwivedi et al. 2022).
used the Adam optimizer with 1e-04 learning rate and batch size of 200 for training, validation and testing. We set the patience to 20 and we optimize the Mean Reciprocal Rank (MRR) score, and the learning consisted of 50 epochs. All the experiments were run times to reduce the effect of initialization and other randomization parameters. The number GNN layers L -= 1, while the number of heads (for multi-head attention) (for CTANN or 2 (for TGAT and TGN). For CTAN, epsilon 1.0 and gammaa is 0.1, as reported in Gravina et al. (2024). The rest of the configuration is taken from the TGB codebase: the weight decay penalty 0, the embedding/ time/ time/memory memory dimension is 100, the neighborhood sampler size is 10, and evaluation is done with the TGB evaluator.
For experimental setting the real-world bi-partite dataset TGBL-Wiik
Finally, for our experiments on the community-based SBM dataset and homogeneous adapted TGBL- Coin dataset, we have set the number of layers to L = and unique attention head. Similarly to the previous experiment, we have used the Adam optimizer (Kinmma & Ba 2015) with a 1c-04 learning rate and a batch size of 200. All the models were trained for 30 epochs with the palience set to 5, and we have used hidden dimension of 100. All the experiments were run times to reduce the effect of initialization and other randomization parameters. For CTAN, epsilon is 1.0 and gamma is 0.1, reported in Gravina et al.
h
The source code necessary to reproduce our experiments is publicly available at: https://g c
king/ lonn/ctdg-inng ctdg-info-
26


Reviews:
[{"review_id": "3kM6NEU7li", "reviewer": "Reviewer_8yma", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1 - the paper seems to be typo-free and has good English. It is generally well-written.\n\n2 - the survey is thorough in the list of methods\n\n3 - the Information Flow point of view is interesting in its principles\n\nWeaknesses:\n\n1 - I think I've missed the point of the paper: on the one hand, this paper is a survey that categorizes many methods, but on the other, it also introduces some theoretical concepts like IF. Although this can work in principle, as IF is used to address the expressivity of methods, it is also restricted to a limited number of methods, namely those with Message-Passing layers (like Graph Conv. Networks and Attention-based).\n\n2 - I did not understand the relation between the flow quantity (and its upper bound) and the expressivity of a model. Also, I think the application of theorems 2.1 and 2.2 is not discussed in depth enough for each surveyed method. A visual explanation might also help, for example, a plot #layers L vs. upper bound in an example network.\n\n3 - the introduction of Self Supervised Learning seems out of place in the context of the paper, as there is no mention of linking it with the theory developed in Section 2.2 nor in the Experiment section.\n\n4 - I think the experimental section fails in its premise, that is, to prove the theoretical insights of the paper. The results show that CTAN, a state-of-the-art method, surpasses all other methods. This, in my view, is stating the obvious, as it is, in fact, a very recent state-of-the-art method. This does not validate the theoretical results, and no clear correlation is shown.\n\n5 - Although the paper is generally well-written, it misses clarity in some of its statements, for example: \"However, we argue that JODIE struggles with stochastic events, especially in multi-community graphs, where sudden, unpredictable changes are more\nprevalent.\". Do you have proof for this claim?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors offer a survey of the field of Continuous-Time Dynamic Graphs (CTDG), organized in a taxonomy of Message Passing (MP), non-MP, and hybrid methods. To illustrate the expressiveness of the methods, the authors study a general framework incorporating many (but not all) of the listed models, from the point of view of Information Flow (IF). In particular, the authors's study focuses on upper bounding the flow quantity, defined as the distance between embeddings before and after an event in the graph. Finally, a section examines the use of Self Supervised Learning for CTDG downstream tasks. The authors also include an experimental section for benchmarking some of the surveyed methods.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical changes:\n\n1 - more in-depth discussion of theoretical results, with better motivations in claims over how the flow quantity relates to expressivity.\n\n2 - more in-depth application of the theory on the surveyed methods.\n\n3 - clearer empirical proofs regarding how the theory drives better results, for example, pinpointing how the upper bound correlates with performance, depending on the architecture.\n\n4 - explaining clearly the role of the paper, and how self-supervised learning is useful to the narrative.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2naljoQxeo", "reviewer": "Reviewer_TCWK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The information flow centric theoretical framework is a new ground in understanding the expressivity of CTDG models. It focuses on quantifying the ability of models to encode and propagate temporal and structural information.\n\n2. The categorization of existing methods according to their compatibility with different graph structures and temporal dynamics is informative. It provides another view of the complex landscape of CTDG methods, potentially making it easier for practitioners to select or adapt approaches for their specific needs. \n\n3. The paper is generally written well, with a visible effort of connecting its theoretical contributions with practical insights. The empirical validation on long-range, bi-partite and community-based graphs provides an initial insight in understanding the relative capabilities of the tested methods .\n\nWeaknesses:\n\nSome aspects in the paper could benefit from additional elaboration or a broader perspective. One area that stood out is the analysis of the difference between the theoretical upper-bound and the empirical values of node representation norms, which only present thinly in the appendix. I believe this kind of analysis is not only important but also essential for appreciating the practical utility of the theoretical framework. \n\nMinor: lack of information on the availability of datasets and code.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work delivers a review of representation learning on dynamic graphs (specifically CTDGs), with a focus on SSRL. The authors derived a theoretical framework to analyze the expressivity upper-bound of different existing models, categorizes them according to a taxonomy related to the framework. They also conducted empirical validations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The analysis of the theoretical upper-bound versus empirical results should be moved from the appendix to the main paper. This segment deserves more prominence, as I mentioned already. Expanding this analysis with results from additional datasets would further strengthen the paper’s empirical contributions.\n\nCan authors give out their judgement in a promising category of methods (or component of methods) using the expressivity framework? \nPlease make clear of the availability plan of the (synthetic) datasets and code. \n\nLastly, I noticed the way Theorem 2.2 and 2.3 are expressed is different in format, I think it is the best to make them identical and please try to make the proof in Appendix easier to read for general audiences – probably add a bit more explanation?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "w6k6YXdUSc", "reviewer": "Reviewer_s8Qu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- The paper is well-organized, with a clear progression from theoretical foundations to practical evaluations, making it easy to read.\n\n- The proposed IF-centric framework introduces a new way to analyze expressivity in CTDGs, potentially enhancing understanding of temporal and structural dynamics.\n\n- By highlighting SSRL, the paper addresses existing CTDG literature gaps and underscores the potential for learning robust representations without labeled data.\n\n- The experimental evaluations support the theoretical claims and offer insights into method selection for specific tasks.\n\n**Weakness**\n\n- The theoretical framework assumes specific properties (e.g., 1-Lipschitz functions, stable degree distributions) that may not always hold in real-world scenarios. The authors may provide more justification on this. \n\n- The discussion on contrastive pretraining is valuable but lacks references to works such as [1] and [2].\n\n- The synthetic datasets are diverse, but there's limited experimentation with real-world datasets. However, as a survey paper, this might not be necessary.\n\n[1] Xu, Yiming, et al. \"CLDG: Contrastive learning on dynamic graphs.\" 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 2023.\n\n[2] Zhu, Zulun, et al. \"Topology-monitorable Contrastive Learning on Dynamic Graphs.\" Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper reviews Graph Representation Learning (GRL) on Continuous-Time Dynamic Graphs (CTDGs) with a focus on Self-Supervised Representation Learning (SSRL). It presents an innovative Information-Flow (IF) centric theoretical framework to assess expressivity in CTDG models, categorizes existing methods based on their applicability to various graph types, and supports theoretical findings with empirical evaluations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The review around contrastive pretraining needs a further polish to include more recent work and how those methods relate to the proposed framework.\n\n2. Please discuss the limitations of key assumptions in the theoretical framework and their implications for practical applications.\n\n3. Minor Corrections:\n - In a few places “None-MP” should be “Non-MP”.\n - The title of 3.2 should be “Self-Supervised Representation Learning (SSRL)”", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a novel theoretical framework for analyzing continuous-time dynamic graphs (CTDGs) and provides empirical validation on diverse datasets. The claims are well-supported by evidence, and the work is relevant to TMLR’s audience. The paper offers valuable insights into graph representation learning in dynamic settings and highlights the potential of self-supervised learning approaches. Overall, the work is sound and makes a meaningful contribution to the field.
Decision: Accept (poster)