A Dependency-Aware Multi-GPU Training Framework for Temporal Graph Neural Networks

arXiv:2610.15730v1 [cs.LG] 11 Oct 2026

A Dependency-Aware Multi-GPU Training Framework for Temporal Graph Neural Networks Yang Zhao∗

Yue Dai∗

Liang Qiao

yang_zhao@mail.ustc.edu.cn University of Science and Technology of China Hefei, Anhui, China

ydai21@illinoistech.edu Illinois Institute of Technology Chicago, Illinois, USA

ql1an9@mail.ustc.edu.cn University of Science and Technology of China Hefei, Anhui, China

Buxin Tu

Bo Liu

Sen Zhang

tubuxin@mail.ustc.edu.cn University of Science and Technology of China Hefei, Anhui, China

liubo22@mail.ustc.edu.cn University of Science and Technology of China Hefei, Anhui, China

sen@mail.ustc.edu.cn University of Science and Technology of China Hefei, Anhui, China

Yi Zhang

Xiaoyu Hao

Jun Shi

yi_zhang@mail.ustc.edu.cn University of Science and Technology of China Hefei, Anhui, China

haoxiaoyu@mail.ustc.edu.cn University of Science and Technology of China Hefei, Anhui, China

shijun18@ustc.edu.cn University of Science and Technology of China Hefei, Anhui, China

Junshi Chen

Hong An

cjuns@ustc.edu.cn University of Science and Technology of China Hefei, Anhui, China

han@ustc.edu.cn University of Science and Technology of China Hefei, Anhui, China

Abstract

(3) critical-path optimization to prioritize urgent memory updates while deferring non-critical work during multi-GPU pipeline execution. Experimental results across representative models and diverse datasets show that DepBloom achieves an average speedup of 2.84× and up to 5.16× over state-of-the-art methods, while maintaining comparable or better model accuracy.

Temporal graph neural networks (TGNNs) achieve superior performance in many dynamic graph learning tasks. These models use node state vectors (i.e., memories) to capture and record graph changes (i.e., events), and then exploit these memories to assist prediction. However, this memorycentric design makes multi-GPU training challenging because predictions for later events often depend on memory updates from earlier events. To maintain model quality, existing multi-GPU TGNN training schemes strictly preserve all event dependencies, which limits parallelism and causes expensive cross-GPU memory synchronization. In this work, we observe that many of these dependencies can be handled more flexibly without harming training quality. Specifically, (a) dependencies in TGNN training have high locality in both time and graph topology, (b) the short-range dependencies missed within a large batch can often be recovered cheaply, and (c) many memory updates are not immediately needed. Based on these observations, we propose DepBloom to accelerate multi-GPU TGNN training with three techniques: (1) temporally bounded spatial partitioning to reduce unnecessary cross-GPU synchronization and improve parallelism; (2) intra-batch memory refinement to recover missing shortrange temporal dependencies inside enlarged batches; and

Keywords: Deep Learning, Dynamic Graph, Temporal Graph Neural Networks, Efficient Multi-GPU Training

1

Introduction

Dynamic graphs are widespread across various applications such as social networks [20], recommendation systems [38], traffic forecasting [24], and financial risk analysis [45]. Compared with static graphs, dynamic graphs involve changing nodes and edges, which makes representation learning substantially more challenging [2, 17, 21, 32]. Temporal Graph Neural Networks (TGNNs) have emerged as an effective approach for learning on dynamic graphs and have achieved state-of-the-art performance on a range of dynamic graph tasks [4, 8, 9, 19, 21, 27, 30, 32, 33, 35, 39, 42, 44, 46, 48, 50, 55]. TGNNs model a dynamic graph as a time-ordered sequence of events, where each event records a graph change, such as adding a node or an edge. A key feature of these models is that each node maintains a time-evolving state vector,

∗ Both authors contributed equally to this research.

1

Trovato et al.

Table 1. Comparison with representative efficient TGNN training systems under √ the two core challenges of scalable multi-GPU training. and ▲ denote explicit and partial support, respectively.

particular, we make three observations: First, dependencies in TGNN training are often local in both time and graph topology. This locality is hard to utilize with only one-dimensional partitioning. Temporal-only partitioning breaks topological dependencies while spatial-only partitioning degrades training quality over long horizons. Second, the short-range temporal dependencies missed inside a large batch can often be recovered cheaply. Specifically, stale node memories in a large batch can be recovered based on earlier events within the same batch, enabling higher parallelism while maintaining training quality. Third, memory updates are not equally urgent for subsequent computation. Only a small subset of updated node memories is immediately required by the next dependent batch. Therefore, uniformly synchronizing all updates places unnecessary work on the critical path and prolongs execution stalls. Together, these observations suggest that scalable TGNN training could preserve only critical dependencies while relaxing or restructuring the rest to improve parallelism and reduce synchronization. Based on these insights, we propose DepBloom, an efficient framework for scalable multi-GPU TGNN training with three key techniques. First, temporally bounded spatial partitioning divides the event stream into serial temporal windows and organizes each window into topology-aware parallel sub-chains, reducing unnecessary cross-GPU synchronization among sub-chains while preserving critical dependencies among windows. Second, intra-batch memory refinement recovers missing short-range temporal information inside enlarged batches, enabling higher parallelism without sacrificing training quality. Third, critical-path optimization for multi-GPU pipeline execution prioritizes urgent memory updates and removes non-critical updates and operations from the critical path, thereby improving pipeline execution efficiency and enhancing system scalability. Experimental results across diverse benchmarks show that DepBloom achieves an average speedup of 2.84× and up to 5.16× over baselines, while maintaining comparable or better model quality. We summarize our contributions as follows:

Quality-Aware Parallelism Memory Sync Overhead Batching Multi-GPU Scaling Reduce Sync Hide Sync √ ETC [13] √ Cascade [10] √ PipeTGL [26] ▲ DistTGL [55] ▲ ▲ √ √ √ √ DepBloom Work

often called node memory [7, 9, 10, 13, 26, 54], which is updated when relevant events occur around it. As dynamic graphs continue to grow in scale to billions or even trillions of events [22, 23, 54], efficient multi-GPU training of TGNNs is crucial for practical deployment. However, TGNN training is fundamentally bottlenecked by its unique memory update mechanism. Ideally, TGNNs follow a strict chronological execution order, updating node memories whenever they become relevant to an event [21, 33, 35, 42]. In TGNN training, however, events are grouped into batches, where each batch reads memories from earlier batches for computing and writes back updated memories for later batches [10, 21, 26, 32, 33, 35, 42, 54, 55]. As a result, unlike conventional deep learning workloads, where batches are largely independent, TGNN batches are linked by strict cross-batch memory dependencies, leading to two major challenges in scaling multi-GPU TGNN training. First, temporal dependency forces a trade-off between parallelism and training quality. Larger batches improve hardware utilization, but they delay memory updates and ignore dependencies among events within the same batch. Existing single-GPU TGNN systems, such as ETC and Cascade [10, 13], improve efficiency by enlarging batches along a chronological event stream while controlling information loss. However, simply enlarging batches remains insufficient to expose scalable parallelism across GPUs, while the resulting irregular workloads can further cause load imbalance and pipeline bubbles in multi-GPU execution. Second, multi-GPU scalability is limited by expensive crossGPU memory synchronization. Existing systems [7, 26] either synchronize updated memory states across GPUs at the end of each batch or ignore such synchronization altogether. As a result, they either incur substantial communication overhead and prolonged pipeline stalls, or suffer noticeable training-quality degradation. Table 1 summarizes how representative prior methods, together with our design, address these two core challenges. As the table shows, prior methods partially improve one challenge or the other, but remain insufficient for scalable multi-GPU TGNN training. Nevertheless, we find that many dependencies can be handled more flexibly without harming training quality. In

• We identify the excessive preservation of event dependencies in existing multi-GPU TGNN training frameworks as a major limitation of parallelism and scalability, and recognize the potential of handling these dependencies more flexibly without harming training quality. • We propose DepBloom, a multi-GPU TGNN training framework that combines temporally bounded spatial partitioning, intra-batch memory refinement, and critical-path optimization to increase parallelism and reduce cross-GPU synchronization costs. • We evaluate DepBloom on representative TGNN models and dynamic graph datasets, and show that it substantially outperforms prior multi-GPU TGNN training systems while maintaining comparable or better accuracy. 2

A Dependency-Aware Multi-GPU Training Framework for Temporal Graph Neural Networks node memory

Batch k-1 Batch k ti: add edge e23

1

events 𝑒23 (𝑡𝑖 )

2

𝑒34 (𝑡𝑖+1 ) 3

node memory 3

𝑠2 (𝑡𝑖− )

4

𝑠3 (𝑡𝑖− ) 𝑠4 (𝑡𝑖− )

4

2 3

ti+1 add edge e34

4 3

prediction & loss 𝑒ǁ23 (𝑡𝑖 )

𝑒23 (𝑡𝑖 )

𝑒ǁ34 (𝑡𝑖+1 )

𝑒34 (𝑡𝑖+1 )

Step 1: Embedding & prediction

message

1 2

Step 2: Message generating

𝑚23 (𝑡𝑖 )

𝑚34 (𝑡𝑖+1 )

𝑚32 (𝑡𝑖 )

𝑚43 (𝑡𝑖+1 )

Batch k+1

and similarly for node 𝑣𝑖 . Here, msg(·) denotes message construction and UPDT(·) denotes the memory update function. For prediction, TGNNs typically compute time-aware node embeddings by feeding the target node memory and its temporal neighborhood memories into a GNN module, e.g.,

node memory

  h𝑢 (𝑡) = GNN s𝑢 (𝑡), {s𝑘 (𝑡) | 𝑘 ∈ N (𝑢, 𝑡)} ,

+ 𝑠2 (𝑡𝑖+1 )

Step 3: Memory updating

+ 𝑠4 (𝑡𝑖+1 )

followed by an MLP/scoring function to produce edge or node predictions. Batched TGNN Training. In practice, the input event sequence E = {𝑒𝑖 }𝑇𝑖=1 is divided into time-ordered batches 𝐾 and processed sequentially. Using edge prediction {B𝑘 }𝑘=1 as an example, Figure 1 shows that each batch B𝑘 has three stages: (a) First, in the embedding and prediction stage, the model fetches the pre-update memories of nodes involved in B𝑘 , denoted by S𝑘− = {s𝑣 (𝑡 − )}, and uses them to compute embeddings and predictions. Thus, all events in the same batch are predicted from memories updated in previous batches. (b) Next, in the message generation stage, the model generates messages from the current events and their pre-update memories according to Equation (1). (c) Finally, in the memory update stage, these messages are aggregated using a mean or most-recent operator [21, 32], and node memories are updated following Equation (1).

node memory

Figure 1. TGNN computing steps in one batch. In many TGNN training pipelines, the memory update of one batch is deferred and executed as the first step of the next batch.

2

Background

2.1

Temporal GNN Learning on Dynamic Graphs

Dynamic Graphs. Dynamic graphs model systems whose nodes and edges evolve over time. They are commonly represented as either discrete-time dynamic graphs (DTDGs), modeled as a sequence of graph snapshots, or continuoustime dynamic graphs (CTDGs), modeled as a chronologically ordered stream of timestamped events. DTDGs can often be viewed as a coarser discretization of CTDG event streams, where events are grouped into time windows to form snapshots [9, 10, 54]. Recent work [1, 7, 10, 15, 26, 32, 52, 54] increasingly favors CTDGs because they preserve exact interaction timing and better capture fine-grained temporal dynamics. Formally, a CTDG is an ordered event sequence E = 𝑒 (𝑡 1 ), 𝑒 (𝑡 2 ), . . . with 𝑡 1 < 𝑡 2 < · · · , where each event denotes a timestamped graph interaction or update. Prediction at time 𝑡𝑖 is based on the event history before 𝑡𝑖 , which can be denoted as E𝑖− = 𝑒 (𝑡 1 ), . . . , 𝑒 (𝑡𝑖 −1 ). Temporal Graph Neural Networks. Temporal graph neural networks (TGNNs) maintain a time-evolving state vector for each node, commonly referred to as node memory [7, 10, 26, 32, 42, 54], to summarize its historical interactions for prediction. Formally, consider a chronologically ordered input event stream E = {𝑒𝑖 }𝑇𝑖=1 , where each event 𝑒𝑖 = (𝑢𝑖 , 𝑣𝑖 , 𝑡𝑖 , x𝑒𝑖 ) denotes an interaction between nodes 𝑢𝑖 and 𝑣𝑖 at time 𝑡𝑖 , optionally with edge features x𝑒𝑖 . TGNNs update node memories and use them for predictions as follows: When event 𝑒𝑖 arrives, the model first constructs messages using the pre-update memories of the two involved nodes, denoted by s𝑢−𝑖 and s𝑣−𝑖 , together with the time gap Δ𝑡𝑖 and edge features x𝑒𝑖 . It then updates the corresponding node memories. For example, the memory update for node 𝑢𝑖 can be written as m𝑣𝑖 𝑢𝑖 = msg(s𝑣−𝑖 , s𝑢−𝑖 , Δ𝑡𝑖 , x𝑒𝑖 ),

(2)

+ 𝑠3 (𝑡𝑖+1 )

2.2

Multi-GPU Training for TGNNs

To enable multi-GPU TGNN training, prior work has explored four representative paradigms [26, 55], as shown in Figure 2. Batch parallelism [53–55] executes adjacent batches concurrently on different GPUs, which improves throughput but causes stale memories by weakening interbatch dependencies. Epoch parallelism [55] overlaps different training epochs across GPUs, but later epochs may process the same samples before earlier model updates are fully incorporated. Memory parallelism [55] reduces synchronization by keeping multiple copies of node memory across GPUs, but this increases memory overhead and disrupts memory evolution across the entire training event stream. These three paradigms improve hardware utilization by relaxing the original dependency order of TGNN training. In contrast, pipeline parallelism [26] preserves dependency order while still exposing concurrency. It decomposes each batch into dependent stages, such as node memory update and node embedding, and overlaps different batches across GPUs. Once one batch finishes its memory update, the next GPU can start the following batch, while the current GPU continues the later stages of the current batch. Because it improves concurrency without violating the original update order, pipeline parallelism is the most suitable paradigm for TGNN training [26], and we focus on it in this work.

s𝑢+𝑖 = UPDT(s𝑢−𝑖 , m𝑣𝑖 𝑢𝑖 ), (1) 3

Trovato et al.

Timeline

Timeline GPU0

𝐵3i

𝐵0i+1

𝐵3i+1

𝐵0i−1

𝐵0i

𝐵0i+1

𝐵3i−1 RW

𝐵1i

RW

𝐵4i

RW

𝐵1i+1

𝐵4i+1

𝐵1i−1

𝐵1i

𝐵1i+1

𝐵4i−1

𝐵2i

𝐵5i

𝐵2i+1

𝐵5i+1

𝐵2i−1

𝐵2i

𝐵2i+1

𝐵5i−1

RW

GPU1 GPU2

Timeline

𝐵0i

RW

RW

RW

RW RW

RW

RW RW

RW

RW

(a) batch parallelism

RW

RW

Timeline

RW

𝐵1i

RW

𝐵2i+1

𝐵3i+1

𝐵2i

𝐵3i

𝐵4i+1

𝐵5i+1

𝐵4i

𝐵5i

𝐵0i+1

𝐵1i+1

𝐵0i

RW

RW

RW

RW

RW

RW

RW

RW

RW

𝐵0i

RW

𝐵1i

RW

RW

RW

𝐵1i+1

RW

𝐵2i

𝐵3i+1

RW

𝐵4i

RW

(c) memory parallelism

(b) epoch parallelism

𝐵0i+1

𝐵3i

RW

RW

𝐵5i

RW

𝐵2i+1

RW

𝐵4i+1 RW

𝐵5i+1

RW

(d) pipeline parallelism

Figure 2. Comparison of four multi-GPU training paradigms for TGNNs: (a) batch parallelism, (b) epoch parallelism, (c) memory parallelism, and (d) pipeline parallelism. Here, 𝐵𝑖𝑗 denotes the 𝑗-th batch in epoch 𝑖, and different colors distinguish batches from different epochs. RW denotes memory read and write operations, where different colors indicate different memory copies. Green arrows indicate inter-GPU data movement.

3

Motivation and Opportunity

3.1

Bottlenecks in Multi-GPU TGNN Training

batch-centric designs are effective for single-GPU execution, but expose parallelism only along a single global event stream: once a dependency reaches the batch boundary, unrelated graph regions cannot progress independently. Meanwhile, irregular dependency-aware batch sizes can cause workload imbalance and bubbles across GPUs, limiting multiGPU scalability. Consequently, existing multi-GPU TGNN systems still rely on relatively small batches to preserve quality [26, 55], which in turn increases synchronization frequency and leads to frequent stalls on memory updates.

Latency (s)

sample & fetch model train

memory sync total time

40 30 20 10 0

/RVV,QFUHDVH YV%6 

Although recent pipeline-based systems can preserve temporal dependencies [26], they still scale poorly. To quantify this limitation, we profile PipeTGL [26], a state-of-the-art multi-GPU TGNN training system, on WIKI-TALK [22] using 2 to 8 NVIDIA RTX 4090 GPUs. As shown in Figure 3, adding more GPUs does not consistently reduce end-to-end latency. Although total latency decreases from 2 to 6 GPUs, the scaling quickly saturates, and 8 GPUs even underperform 6 GPUs. The overall speedup over 2 GPUs is only 1.77× with 6 GPUs and 1.46× with 8 GPUs. This poor scalability mainly stems from two fundamental challenges: memory update sync ratio 60% 40%

  

7*1 -2',( $3$1

 

  

 



 %DWFK6L]H

   7UDLQLQJ6SHHGXSYV%6 

%6  %6  %6 



20%

Figure 4. Trade-off between training efficiency and model quality under different batch sizes on WIKI-TALK.

0% 2-cards

4-cards

6-cards

8-cards

Figure 3. Latencies of training TGN on WIKI-TALK with different numbers of GPUs. (1) Sample&fetch includes neighbor sampling and input transfer from CPU to GPU; (2) memory_sync denotes the transfer of updated node memories across GPUs; (3) memory_update computes new node-memory states required by subsequent GPUs; and (4) model_train includes forward propagation, backward propagation, and parameter updates.

Challenge 2: Multi-GPU scalability is limited by expensive cross-GPU memory synchronization. The second challenge is that cross-GPU memory synchronization is both expensive and increasingly inefficient at scale. In multi-GPU TGNN training, a batch cannot proceed until the required memory update has been produced by the previous GPU and transferred to the current one. As a result, each synchronization point incurs not only waiting time but also explicit communication overhead. As the number of GPUs increases, this overhead becomes harder to hide and increasingly dominates execution. This effect is clearly reflected in Figure 3. Although the computation stages continue to shrink as more GPUs are added, the synchronization latency rises from 4.70 s on 2 GPUs to 13.85 s on 8 GPUs, and becomes 2.92× higher than that on 4 GPUs. Meanwhile, its share of total runtime increases sharply from 12.3% to 53.1%. These results show that cross-GPU memory synchronization becomes a dominant bottleneck as the system scales.

Challenge 1: Temporal dependency forces a tradeoff between parallelism and training quality. In TGNN training, memory updates generated within a batch are deferred until the batch finishes. As a result, later events in the same batch cannot benefit from updates produced by earlier related events, so larger batches improve parallelism but weaken short-range temporal dependency modeling and often hurt accuracy. As shown in Figure 4, increasing the batch size consistently improves training throughput on WIKI-TALK [22], while causing clear loss degradation. Such 4

A Dependency-Aware Multi-GPU Training Framework for Temporal Graph Neural Networks

5.98%–16.24%. On WIKI_TALK, the ratio drops from 91.83%– 96.23% to 7.86%–30.50%. The results show that temporalonly partitioning incurs substantial dependency breaks. Limits of spatial partitioning. Directly applying spatial partitioning to the full dynamic graph, as is often done for static GNNs [3, 7, 51], is too aggressive for TGNN training because it ignores temporal locality and allows omitted crosschain dependencies to accumulate over long horizons. To evaluate this effect, we use the same setup as in Figure 5(a), vary the temporal window length before partitioning, and train TGN [32] on the resulting partitioned graphs. As shown in Figure 5(b), when we directly partition the whole graph, the cross-chain event ratio increases from 5.98% to 11.19%, and training loss rises by 70.7%. These results show that spatial-only partitioning over the entire input dynamic graph may significantly degrade training quality.

Rethinking Dependencies in Multi-GPU TGNN Training

75% 50% 25% 0%

2

4

8

REDDIT

2

4

8

WIKI TALK

Sub-chain Count

Training Loss Cross Chain Events Ratio Memory Sync Count 20

12

8

10

4

0

0

15

30 60 Full Event Count (×104)

BS=1200 Speedup W refine

BS=4800 W/O refine Speedup W/O refine

Serialized Small Batch …

𝐵𝑖+1

𝐵𝑖

𝐵𝑖+2

…

Fresh Memory Costly Sync

Parallelized Large Batch …

…

𝐵𝑖,𝑖+1,𝑖+2

Fresh Memory Costly Sync

Refined Parallelized Large Batch …

𝐵𝑖

𝐵𝑖+1

𝐵𝑖+2

…

30

BS=4800 W refine

almost equal

20 10

2

38.8%→5.8%

53.2%→27.8%

0

1

0 WIKI

REDDIT

Cheap Sync, Fresh Memory

(a)

Cross-chain Event Ratio (%)

sequential partition topology-aware partition 100%

Training Loss(×104)

Cross-chain Events (%)

By revisiting dependency handling in TGNN training, we find that current execution strategies are often overly conservative, leaving substantial room to improve parallelism and reduce overhead. Specifically, we make three key observations that motivate our design. Our first observation is that dependencies in TGNN training are often local in both time and graph topology, so effective partitioning must jointly consider both. Partitioning is a natural way to reduce cross-GPU communication [12, 36, 47]: If a training sequence can be decomposed into multiple largely independent units, which we call sub-chains, these units can execute in parallel. This preserves sequential dependencies within each sub-chain while reducing synchronization across sub-chains. For TGNN training, however, exploiting this opportunity requires partitioning that respects both temporal locality and graph topology.

Speedup

3.2

Training Loss (×104)

In summary, multi-GPU TGNN training scales poorly because (1) execution on each GPU repeatedly stalls due to memory updates across small batches, and (2) those stalls are too expensive to be effectively hidden by pipelining. This naturally raises the following question: can we reduce (i) the frequency of memory updates and (ii) the cost of each memory synchronization without hurting training quality?

(b)

Figure 6. (a) Execution modes under different parallel strategies. (b) Speedup versus training loss increase under larger batch sizes. Arrows show the percentage loss increase from BS=1200 to BS=4800. Our second observation is that lost temporal dependencies in large batches can often be recovered cheaply. As shown in Figure 6(a), larger batches often hurt model quality because node memories miss short-range temporal dependencies among events within the same batch. However, much of this lost signal can be recovered through memory refinement. Instead of executing several small batches sequentially, we split a large batch into consecutive micro-batches and let later micro-batches refine their input node memories using (i) the node memories carried over from the previous batch along with (ii) the most recent messages from earlier micro-batches. The refinement is performed by a lightweight RNN-based module that is trained jointly with the TGNNs. More details are introduced in Section 4.3. Since these messages can be directly accessed without waiting for intermediate memory updates, this enables parallel micro-batch execution without synchronization. To quantify its potential, we use PipeTGL [26] to train TGN [32] on WIKI and REDDIT [21] with (a) default small batches (Batch_Size=1200), (b) larger batches (Batch_Size =4800) without refinement, and (c) larger batches with memory refinement, which uses events within the same batch to

(a) Cross-chain dependency after partitioning (b) Impact of temporal partition scope

Figure 5. (a) Cross-chain event ratio versus number of sub-chains, comparing naive sequential partitioning against topology-aware partitioning. (b) Cross-chain event ratio and training loss as a function of temporal window size. Limits of temporal partitioning. Existing approaches, such as memory parallelism [55], partition the input sequence only along the temporal dimension and ignore graph topology. As a result, strongly coupled events, which share the same source nodes, are often assigned to different sub-chains, which breaks dependencies across sub-chains. To quantify this effect, we apply (i) sequential partitioning by dividing events chronologically [55] and (ii) topology-aware partitioning using a minimum-cut solver [18] on the first 150,000 events on REDDIT and 300,000 events on WIKI_TALK, and then measure the fraction of dependencies broken across sub-chains. As shown in Figure 5(a), on REDDIT, sequential partitioning yields 99.90%–99.97% broken dependencies, whereas topology-aware partitioning reduces this ratio to 5

Trovato et al.

cross-chain synchronization. Next, Intra-Batch Memory Refinement enables efficient large-batch execution within each sub-chain by compensating for missing short-range temporal dependencies caused by stale updates, thereby increasing parallelism without sacrificing training quality. Finally, Critical-Path Optimization for Multi-GPU Pipeline Execution prioritizes urgent memory updates and removes deferrable operations from the critical path, thereby reducing synchronization cost and shortening execution stalls.

update node memories in parallel (as detailed in Section 4.3). As shown in Figure 6(b), compared with large-batch execution without refinement, memory refinement reduces the loss increase from 53.2% to 27.8% on WIKI and from 38.8% to 5.8% on REDDIT, while still achieving 1.4× and 1.9× speedup, respectively. These results show that much of the lost shortrange temporal signal in large batches can be recovered without exact sequential memory updates. Our third observation is that node memory updates are not equally urgent for subsequent computation, yet existing training schemes still synchronize them as a whole. In practice, only a small subset of updated nodes is immediately needed by the next batch, while most updated nodes are either consumed later or not revisited in the near term. 100% 80% 60% 40% 20% 0%

Cold Node

Hot Node

Cold-related

Hot-related

Temporally Bounded Spatial Partitioning Time-ordered Event Stream

WIKI_TALK

(a) Distribution of updated nodes

REDDIT

WIKI

𝒆𝟑

𝒆𝟓

𝒆𝟒

𝒆𝟔

𝒆𝟕

…

𝑒3 Interaction graph

𝑒𝑐

𝑩𝟐

𝑩𝟏

𝑩𝟐

WIKI_TALK

… …

𝒆𝒎−𝟏

𝒆𝒎

Windows 𝒊 + 𝒏 𝑒𝑒 Topo-Aware Partitioning 𝑒𝑑 𝑒𝑏

Interaction graph Windows 𝒊 + 𝒏

Windows 𝒊 𝑩𝟏

……

𝒆𝟖

𝑒𝑎

Topo-Aware Partitioning

𝑒2

𝑒5

Decompose to sub-chain WIKI

𝑒4

𝑒1

Window Sync exchange mem

REDDIT

𝒆𝟐

Windows 𝒊

Temporally Bounded

Other Operations

𝒆𝟏

𝑩𝒏

𝑩𝟏

𝑩𝟐

𝑩𝒏

𝑩𝟏

𝑩𝟐

… …

𝑩𝒏 𝑩𝒏

Refine the batch within each chain

(b) Critical-path update breakdown

Intra-Batch Memory Refinement

Figure 7. Urgency mismatch in batch-produced memory updates. (a) Distribution of updated nodes immediately required by the next batch (Hot Node) and those that are not (Cold Node). (b) Breakdown of the critical path latency.

Large batch (per sub-chain)

Refinement with intra-batch events Stale Memory

MB1

Updated Memory

Split into micro-batches

Stale Memory

MB2

Refined Memory

MB1

Stale Memory

MB3

Refined Memory

Batch 𝒊 + 𝟏

Batch 𝒊

MB2

Batch 𝒊 + 𝟐

MB3

Memory Aggregate GNN Training

Recover short-range dependencies inside large batches Schedule refined batches

As shown in Figure 7(a), while training TGNN models on WIKI, REDDIT, and WIKI_TALK, only 17.39%, 18.02%, and 11.57% of updated nodes, respectively, are immediately needed by the next batch; most are non-urgent. However, Figure 7(b) shows that these non-urgent updates still consume a substantial portion of stalled update time: 28.93%, 25.87%, and 18.21%, respectively. This unnecessary overhead is comparable to, or even larger than, that of immediately required updates (16.18%, 10.15%, and 17.05%). This indicates that a significant fraction of synchronization-critical time is spent on updates that need not be consumed immediately. These results show that current synchronization policies are overly conservative: they place non-urgent updates on the critical path, although the next batch does not immediately need them. Therefore, prioritizing urgent updates and deferring the rest can shorten stalls and reduce synchronization cost.

4

Design

4.1

Overview

Critical-Path Optimization for Multi-GPU Execution Priority-Aware Node Update Decoupling Updated Memory

Hot nodes urgent

Fast Sync (GPU-GPU)

Cold nodes deferred

Deferred Async

Exec. Pipeline

Critical-Path Precompute & Overlap comp

Reduced Critical Path

sample&fetch pre-comp critical

Host Mem

Load when needed

Critical Path → Bubble!

Precompute metadata

Prioritize updates and critical path optimization with pipeline execution

Figure 8. Design overview of DepBloom.

4.2

Temporally Bounded Spatial Partitioning

Motivated by Observation 1, we propose Temporally Bounded Spatial Partitioning to improve TGNN training efficiency by reducing unnecessary synchronization while preserving critical memory dependencies. The key idea is to organize the execution hierarchically. We first partition the input event stream along the temporal dimension to bound memory synchronization (i.e., enforce necessary memory synchronization between windows), then partition each temporal window along the spatial dimension into sub-chains, and finally execute the resulting sub-chains in parallel with synchronization only at window boundaries. Temporal partitioning for bounded memory synchronization. We first divide the input event stream E = 𝑒𝑖 𝑇𝑖=1 into consecutive temporal windows W1, W2, . . . , W𝑀 , where each W𝑚 contains a contiguous segment of events.

Based on the above observations, we propose DepBloom, an efficient framework for multi-GPU TGNN training. DepBloom integrates three complementary techniques to improve scalability and efficiency. As illustrated in Figure 8, DepBloom improves multi-GPU TGNN training from top to bottom. First, Temporally Bounded Spatial Partitioning divides the training event sequence into serial temporal windows and further partitions each window into topologyaware sub-chains, exposing parallelism while minimizing 6

A Dependency-Aware Multi-GPU Training Framework for Temporal Graph Neural Networks

Origin Event Sequence strict sync preserves memory fidelity batch size = 2 𝒆𝟎𝟐 𝒆𝟒𝟓 𝒆𝒂𝒅 𝒆𝟐𝟓 𝒆𝒅𝒆 𝒆𝟏𝟒 𝒆𝒅𝒄 𝒆𝟐𝒂 𝒆𝟒𝟓 𝒆𝟎𝟐 𝒆𝒃𝒅 𝒆𝒂𝒆 𝒆𝒃𝒄 𝒆𝟎𝟏 𝒆𝟎𝟑 𝒆𝒅𝒇

Temporally Bounded

5

4 (𝑖 − 1)

b a

3 2

1

GPU0

……

a

2

1 4

5

e

d

S&F

MU

E&B

S&F

MU

E&B

S&F

MU

Single Chain

MU

E&B

S&F

MU

E&B

S&F

MU

E&B

S&F

MU

E&B

E&B

In-chain Pipeline Parallelism

Topology-Aware Spatial Partitioning

GPU0

Subchain 0

schedule

c

Subchain 1

f

𝒆𝒂𝒅 𝒆𝒅𝒆 𝒆𝒅𝒄 𝒆𝟐𝒂 𝒆𝒃𝒅 𝒆𝒂𝒆 𝒆𝒃𝒄 𝒆𝒅𝒇

S&F

GPU1

𝒆𝟎𝟐 𝒆𝟒𝟓 𝒆𝟐𝟓 𝒆𝟏𝟒 𝒆𝟒𝟓 𝒆𝟎𝟐 𝒆𝟎𝟏 𝒆𝟎𝟑

b

S&F

Hierarchical Multi-Chain Parallelism

(𝑖 + 1)

Subchain Splitting

3

E&B

GPU3

f

Local Interaction Window (𝑖)

0

MU

GPU2

c d

e

Focus on Local Interaction Window (𝑖)

S&F

GPU1

Bounded Selected

0 ……

Pipeline Parallelism

schedule

E&B

S&F

MU

E&B

S&F

MU

E&B

S&F

MU

E&B

Subchain 0

E&B

Subchain 1

In-chain Pipeline Parallelism GPU2 GPU3

Reordered & split event sequence: parallel chains with minimal loss

MU

S&F

MU

E&B

S&F

MU

E&B

S&F

MU

E&B

S&F

MU

Figure 9. Comparison between the original pipeline parallelism and Topology-Aware Hierarchical Multi-Chain Parallelism. Using eight consecutive batches (batch size=2) as an example, the original design executes batches in a single pipeline and incurs frequent unnecessary synchronization. Our design partitions events into multiple topology-aware sub-chains and maps each sub-chain to a GPU group for parallel execution across sub-chains with minimal dependency loss. The purpose of this step is to bound how long memory dependencies can remain unsynchronized. As discussed in Section 3.2, if spatial partitioning is applied over an excessively long event range, omitted cross-partition dependencies accumulate and significantly degrade training quality. By restricting dependency relaxation within bounded temporal windows, DepBloom preserves necessary synchronization across time while preventing long-range dependency loss from growing uncontrollably. In other words, temporal partitioning defines the scope within which dependencies may be relaxed, while still enforcing synchronization between adjacent windows. We empirically set the window size as 80, 000 events by default, and quantitatively evaluate different window sizes in Section 5.5. Spatial partitioning for topology-aware parallelism. Within each temporal window W𝑚 , we build a local inter𝑉 , 𝑤 𝐸 ). A node 𝑣 ∈ 𝑉 apaction graph 𝐺𝑚 = (𝑉𝑚 , 𝐸𝑚 , 𝑤𝑚 𝑚 𝑚 pears if it participates in at least one event in W𝑚 . An edge (𝑢, 𝑣) ∈ 𝐸𝑚 exists if any event occurs between 𝑢 and 𝑣 during 𝐸 (𝑢, 𝑣) equal this window. We assign each edge a weight 𝑤𝑚 to the number of events observed between the two nodes, 𝑉 (𝑣) equal to the number and assign each node a weight 𝑤𝑚 of events involving that node. We then partition 𝐺𝑚 into 𝑃 subgraphs. Let 𝜋𝑚 (𝑣) ∈ {1, . . . , 𝑃 } denote the subgraph assigned to node 𝑣. The goal is to minimize the weighted cut: ∑︁

Cut(𝜋𝑚 ) =

Here, 𝛿 controls the allowed load imbalance. The weighted cut captures the amount of interaction split across different subgraphs, which approximates cross-sub-chain memory dependencies. The balance constraint prevents skewed partitions from creating GPU workload imbalance. In our implementation, we use METIS [18] to solve this weighted graph partitioning problem efficiently. Since a larger edge weight indicates more frequent interaction, this partitioning tends to place strongly coupled nodes in the same subgraph. As a result, most memory dependencies are kept within individual subgraphs. We finally convert the events associated with each subgraph back into a chronological event sequence, which we call a subchain. Events inside each subchain preserve their original temporal order, while different subchains are only weakly coupled. The proposed design is compatible with other lightweight topology-aware strategies, such as greedy assignment or streaming graph partitioning, which can incorporate additional partitioning factors, including node degrees, dependency strength, and event-load balance, to further reduce cross-subchain interactions. Partitioning-based bounded parallelism. After temporal and spatial partitioning, different sub-chains within the same temporal window are assigned to different GPU groups for concurrent execution, as illustrated in Figure 9. Within each sub-chain, the original TGNN training order is preserved, so batches are still executed sequentially. Because spatial partitioning has already minimized cross-chain coupling, synchronization across sub-chains is eliminated. The system synchronizes node memories only after all subchains in the current window complete, before moving to the next temporal window. As a result, DepBloom replaces a single global execution pipeline with multiple local pipelines that progress in parallel, reducing communication overhead and shortening dependency-induced stalls.

𝐸 𝑤𝑚 (𝑢, 𝑣),

(𝑢,𝑣) ∈𝐸𝑚 :𝜋𝑚 (𝑢 )≠𝜋𝑚 (𝑣)

while keeping the total node weight of each subgraph approximately balanced: ∑︁ 𝑣:𝜋𝑚 (𝑣)=𝑝

Í 𝑉 𝑤𝑚 (𝑣) ≤ (1 + 𝛿)

𝑉 𝑣 ∈𝑉𝑚 𝑤𝑚 (𝑣)

,

∀𝑝 ∈ {1, . . . , 𝑃 }.

𝑃 7

Trovato et al. 𝒎𝒔𝒈𝒊

GPU0

S&F

MU

𝒎𝒔𝒈𝒊+𝟑 T&B

S&F

MU

S&F

Stall

T&B

MU

GPU0

S&F

T&B

S&F

MU

…

T&B

𝐵𝑖

𝒎𝒔𝒈𝒊+𝟖

S&F

T&B

Pipelined Small Batches

T&B

MU

T&B

S&F

MU

𝐵𝑖+1

𝐵𝑖+2

𝒎𝒔𝒈𝒊,𝒊+𝟏,𝒊+𝟐

GPU1

S&F

Stall

MU

…

T&B

GPU0

Stall

S&F

S&F

MU

𝒎𝒔𝒈′𝒊,𝒊+𝟏,𝒊+𝟐

GPU1

S&F

GPU2

S&F

T&B

MU

refinement T&B

Stall

𝒎𝒔𝒈′𝒊+𝟒,𝒊+𝟓,𝒊+𝟔 Stall

Execution Path (Serial) Data Trans Path (Parallel)

refinement

MU

…

𝐵𝑖

T&B

𝐵𝑖+1

𝐵𝑖+2

𝐵𝑖+8

𝐵𝑖+6,𝑖+7,𝑖+8

𝑠 𝑖+2 = s 𝑖

𝐵𝑖+4

𝐵𝑖+5

…

…

Updated Memory 𝐵𝑖+3

…

𝑠 𝑖+2 = UPDT(s𝑖+1 , 𝑚𝑠𝑔𝑖+2 ) …

𝐵𝑖+3,𝑖+4,𝑖+5

Pipelined Large Batches (Locally Refinement) T&B

𝐵𝑖+7

𝐵𝑖+6

𝐵𝑖+5

Saved Sync

𝑠 𝑖+1 = s 𝑖

refinement

MU

Saved Sync

Updated Memory

𝐵𝑖,𝑖+1,𝑖+2

𝒎𝒔𝒈𝒊+𝟑,𝒊+𝟒,𝒊+𝟓

GPU2

𝐵𝑖+4

𝐵𝑖+3

𝑠 𝑖+1 = UPDT(s𝑖 , 𝑚𝑠𝑔𝑖+1 )

T&B

Pipelined Large Batches (Locally Parallelism)

T&B

Updated Memory

𝒎𝒔𝒈𝒊+𝟕

𝒎𝒔𝒈𝒊+𝟓 MU

MU

MU

S&F

𝒎𝒔𝒈𝒊+𝟐

GPU2 Sample S&F Stall & Fetch

MU

𝒎𝒔𝒈𝒊+𝟒

𝒎𝒔𝒈𝒊+𝟏

GPU1

𝒎𝒔𝒈𝒊+𝟔 S&F

T&B

Saved Sync 𝐵𝑖+6 <𝑖+1

𝑠ǁ 𝑖+1 = COMB(UPDT s 𝑖 , 𝑚𝑠𝑔𝑖+1 , 𝑅𝐸𝐹𝐼𝑁𝐸(ℇ𝑣

𝐵𝑖+7

𝐵𝑖+8

…

, 𝑡𝑖+1 )) …

Figure 10. Comparison of three multi-GPU pipeline execution strategies for TGNN training. (a) Pipelined Small Batches: each GPU executes one small batch per stage in strict sequential order. (b) Pipelined Large Batches (Local Parallelism): micro-batches within each large batch are scheduled in parallel, each consuming the same stale memory from the previous batch. (c) Pipelined Large Batches (Local Refinement): same scheduling as (b), but a refinement step (green) is inserted between micro-batches to propagate short-range dependencies locally before the next micro-batch executes. : actual scheduling dependencies that enforce serial execution order; : data usage relationships among micro-batches, which allow parallel execution; : sample & fetch; : memory update; : memory refinement; : training & backward. 4.3

cross-device synchronization. Formally, let s𝑣− denote the committed memory of node 𝑣 before batch 𝐵𝑡 , let m𝑣(𝑖 ) denote the message aggregated for 𝑣 in micro-batch M𝑖 , and let E𝑣(<𝑖 ) denote the most recent events involving 𝑣 from preceding micro-batches. The refined memory of 𝑣 in M𝑖 is computed as      s𝑣(𝑖 ) = COMB UPDT s𝑣− , m𝑣(𝑖 ) , REFINE E𝑣(<𝑖 ) , 𝑡𝑖 , (3)

Intra-batch Memory Refinement

Motivated by Observation 2, we propose Intra-Batch Memory Refinement, as illustrated in Figure 10(c). Compared with small-batch execution in Figure 10(a), which preserves frequent memory updates but incurs frequent synchronization and pipeline stalls, and large-batch execution in Figure 10(b), which improves efficiency but uses overly stale node memories, our design combines the strengths of both. It retains the efficiency of large-batch execution while keeping node memories nearly as fresh as if the batch had been processed as several small batches with intermediate memory updates. Micro-batch Split. Instead of treating a large batch as an indivisible unit, we divide it into an ordered sequence of micro-batches, 𝐵𝑡 = {M1, M2, . . . , M𝐾 }, where each microbatch M𝑘 contains the same number of events as the original small-batch baseline, and the micro-batches remain ordered by event timestamp. In this way, the large batch retains the temporal structure of several small batches, while still preserving the lower synchronization frequency of largebatch execution. Parallel Memory Refinement. To avoid sequential updates between micro-batches, which cause frequent stalls and synchronizations, we allow micro-batches to execute in parallel and use a lightweight refinement module to approximate the effect of the omitted intermediate updates. Specifically, when processing micro-batch M𝑖 , we first apply the standard memory update using the available but stale node memories at the beginning of the large batch, and then refine that memory using the most recent events from preceding micro-batches M1, . . . , M𝑖 −1 . This refinement compensates for the skipped intermediate updates without requiring

where UPDT(·) is the standard memory update operator and REFINE(·) is a lightweight refinement module, such as an RNN or a linear projector. The first term captures long-range context from the previous large batch, while the second restores short-range temporal influence missed by skipped intermediate updates. Node-memory aggregation. After all micro-batches in 𝐵𝑡 have been processed, we aggregate the refined node memories to produce the final memory state that will be consumed by subsequent batches. This step is necessary because the same node may appear in multiple micro-batches, leading to multiple refined memory replicas within the same large batch. Following common aggregation operators used in prior TGNN designs [21, 32], we adopt the latest memory strategy, which keeps the replica with the most recent timestamp among all replicas produced within the batch. 4.4

Critical-Path Optimization for Multi-GPU Pipeline Execution

As discussed in Observation 3, a downstream GPU often cannot proceed until the required memory updates from the previous GPU have been both produced and transferred. As the pipeline deepens, these dependency-critical operations 8

A Dependency-Aware Multi-GPU Training Framework for Temporal Graph Neural Networks

become harder to hide and increasingly create pipeline stalls. To address this problem, we optimize multi-GPU pipeline execution from two aspects. First, we remove non-urgent memory updates from the critical path via Priority-aware memory-update decoupling. Second, we move repetitive preprocessing work out of latency-sensitive stages and overlap it with other operations via Critical-path precomputation and overlap. Together, these optimizations shorten the effective critical path and reduce pipeline stalls. GPU0 Sample & Fetch

GPU1 Sample & Fetch GPU2 Sample & Fetch GPU0 Sample & Fetch GPU1 Sample & Fetch GPU2 Sample & Fetch

However, much of this preprocessing depends only on information that is already known before execution begins. In particular, once the event sequence, neighbor sampling results, and partition assignments are determined, the set of accessed nodes and the corresponding memory-access patterns are also fixed. This means that many metadata structures, such as accessed-node lists, index remapping tables, communication offsets, and data movement plans, can be prepared in advance rather than rebuilt repeatedly at runtime and stalled by node memory synchronizations. Therefore, we move this preprocessing work off the critical path by precomputing it before receiving updated node memories from the previous batch, hiding its overhead behind the memory-update critical path. Specifically, while a GPU waits for updated memory from the previous batch or fetches the node features needed by the current batch, DepBloom concurrently prepares the metadata needed for future batches. In our implementation, we also explore Python 3.13’s free-threading mode to implement such thread-level parallelism more easily, allowing I/O data preparation to run concurrently with latency-sensitive training stages.

Origin Node Update Mem Update Embedding & Backward 𝒊+𝟏 𝒊+𝟏 𝒊+𝟏 Unnecessary Sync & Stall 𝒔𝒊+𝟏 𝟏 , 𝒔𝟐 , 𝒔𝟑 , 𝒔𝟒 Mem Update Embedding & Backward Stall 𝒊+𝟐 𝒊+𝟐 𝒊+𝟐 𝒔𝒊+𝟐 = 𝒔𝒊+𝟏 = 𝒔𝒊+𝟏 𝟏 , 𝒔𝟐 , 𝒔𝟑 𝟑 , 𝒔𝟒 𝟒 Mem Update Embedding & Backward Stall Priority-aware Decoupled MU1 MU2 Embedding & Backward Node Update Only Sync & Stall on Critical Subset 𝒔𝟏𝒊+𝟏 , 𝒔𝟐𝒊+𝟏 Stall MU1 MU2 Embedding & Backward 𝒔𝟑𝒊+𝟏 , 𝒔𝟒𝒊+𝟏 Host 𝒊+𝟐 𝒔𝒊+𝟐 𝟏 , 𝒔𝟐 Memory MU1 MU2 Embedding & Backward Stall

Figure 11. Comparisons between unified node update and priority-aware decoupled node update. Priority-aware memory-update decoupling. Recalling Observation 3, only a small subset of memory updates is immediately required by the next dependent batch, while many others are consumed later or not revisited in the near term. To avoid unnecessary waiting cost, we split the updates produced by each batch into two groups: urgent updates and non-urgent updates. Then we handle their execution differently, as illustrated in Figure 11: Urgent updates are those immediately needed by the next dependent batch, so they are updated and transferred first via GPU–GPU communication (e.g., NVLink). This allows the downstream GPU to resume execution as soon as the required memory state becomes available. In contrast, non-urgent updates are removed from the critical path. They are handled separately without blocking the execution of the next batch on remote GPUs, and the resulting memory will first be written back to the CPU and then loaded onto remote GPUs on demand. This design preserves correctness for dependency-critical updates while significantly reducing the amount of communication that lies on the critical path. Critical-path precomputation and overlap. Beyond memory transfer itself, multi-GPU TGNN execution also incurs repeated overhead in preparing memory accesses. Specifically, before a batch can fetch the required node memories, the system often performs preprocessing steps such as node-index deduplication, sorting, remapping, request construction, and buffer packing [55], because the required memories may reside in different locations, such as CPU memory or GPU memory on different devices. Although each step is lightweight in isolation, repeatedly performing them on the critical path adds noticeable delay and further prolongs pipeline stalls.

5

Evaluation

5.1

Methodology

Models. We evaluate DepBloom on five representative TGNN models, including three CTDG-based models: (1) JODIE [21] uses recurrent updates with time-aware projection, (2) TGN [32] combines node memory with temporal graph embedding, and (3) APAN [42] adopts asynchronous mail propagation and attention-based embedding; and DTDG-based models to assess adaptability: (1) DySAT [35], which models temporal evolution across graph snapshots with RNNs, and (2) TGAT [46], which combines temporal encoding with attention-based neighborhood aggregation. We follow Cascade [10] configurations, as shown in Table 2. Table 2. Details of TGNN models, with 𝑑𝑜𝑢𝑡 = 100

JODIE TGN APAN TGAT DySAT

Sample Message most recent (n=1) most recent (n=1) most recent (n=10) uniform (n=10) uniform (n=10)

Memory Update RNN GRU Transformer Identity GAT

Node Embedding Identity GAT Identity 2-layer GAT RNN

Datasets. We evaluate DepBloom on four real-world temporal graph datasets of diverse scales: Wikipedia (WIKI), Reddit (REDDIT) [21], Wikipedia Talk (WIKI-TALK) [22], and GDELT (GDELT) [54]. WIKI and REDDIT are small-scale benchmarks widely used in prior TGNN studies, WIKI-TALK is a large-scale interaction graph with millions of nodes and edges, and GDELT contains nearly 0.2 billion temporal interactions, serving as a stress test for scalability. For datasets without original node or edge features, we generate synthetic 9

Trovato et al. DistTGL1

Speedup

4

DistTGL2

PipeTGL

Ours

A100

2 0 6 4 2 0

4090

DistTGL1

DistTGL2

PipeTGL

Ours

A100

AP

100% 50% 0%

4090

TGAT

DySAT

JODIE

APAN

TGN

TGAT

DySAT

JODIE

WIKI TALK

REDDIT

WIKI

APAN

TGN

TGAT

DySAT

JODIE

APAN

TGN

TGAT

DySAT

JODIE

APAN

TGN

100% 50% 0%

GDELT

Figure 12. Overall performance comparison on NVIDIA A100 and RTX 4090 across four datasets and five TGNN models. The first two rows show end-to-end speedup over DistTGL1 , and the last two rows show average precision (AP). 5.2

features following prior practice [10, 54]. Detailed statistics are in Table 3, where random features are marked by “*”.

We first evaluate the end-to-end performance of our method against three representative baselines, on two hardware platforms (A100 and RTX 4090), four datasets, and five representative TGNN models. As shown in Figure 12, our method consistently delivers the best overall efficiency–accuracy trade-off across all evaluated settings. Training speedup. As shown in Figure 12, DepBloom consistently outperforms all baselines in throughput. Across all 40 evaluated configurations, it achieves the highest speedup, ranging from 1.15× to 5.16×, with an average of 2.84×. On sparse temporal graphs such as WIKI and WIKI-TALK, DepBloom achieves average speedups of 2.90× and 1.96× over DistTGL, and 3.95× and 2.05× over PipeTGL, respectively. On denser and larger-scale datasets such as REDDIT and GDELT, DepBloom achieves 3.17× and 2.03× speedups over DistTGL, while outperforming PipeTGL by 3.91× and 4.02×, respectively. The consistent gains across both CTDG and DTDG models demonstrate the generality of DepBloom across different temporal modeling paradigms. Model quality. DepBloom achieves the highest average precision (AP) of 97.6% across all evaluated configurations, compared with 96.0% for PipeTGL, and obtains the highest AP in 35 of 40 configurations. The advantage is particularly clear on WIKI-TALK, where DepBloom achieves an average AP of 95.3%, compared with 90.7% for PipeTGL. It also improves average AP from 96.1% to 97.0% on WIKI and from 98.4% to 99.4% on GDELT, while remaining comparable on REDDIT (98.7% vs. 98.6%). The quality gains mainly come from DepBloom’s dependency-aware execution: temporally bounded spatial partitioning keeps strongly coupled events within the same sub-chain, while intra-batch memory refinement recovers recent dependencies lost in enlarged batches. Together, these mechanisms expose more parallelism while preserving the memory freshness required for prediction.

Table 3. Dataset statistics. |𝑑 𝑣 | and |𝑑𝑒 | show the dimensions of node features and edge features, respectively. Dataset WIKI REDDIT WIKI-TALK GDELT

|𝑉 | 9,227 11,000 1,140,149 16,682

|𝐸| 157,474 672,447 7,833,140 191,290,882

|𝑑 𝑣 | 172 172 32* 186

Overall Performance

|𝑑𝑒 | 100* 100* 100* 413

Environment. We conduct all experiments on two singlenode 8-GPU platforms: one equipped with eight NVIDIA GeForce RTX 4090 GPUs, and the other with eight NVIDIA A100 GPUs. Both platforms use an Intel Xeon Platinum 8375C CPU and 512 GB of system memory. The system runs Ubuntu 22.04 with CUDA 12.6[29], Python 3.13 (freethreaded), PyTorch 2.9.0[31], and DGL 2.5[41]. For multiGPU execution, we use the distributed package in PyTorch with NCCL as the communication backend. All methods are evaluated under the same hardware and software environment to ensure fair comparison. Compared Methods. Our experiments compare the following representative multi-GPU TGNN training systems: • PipeTGL [26] (baseline) is a pipeline-parallel system that preserves memory continuity across batches and reduces pipeline bubbles through scheduling and communication optimizations. • DistTGL [55] is a distributed training framework that improves scalability via tailored parallel training strategies and system optimizations. In multi-GPU scenarios, we evaluate DistTGL with batch parallelism (denoted as DistTGL1 ) and epoch parallelism (denoted as DistTGL2 ). 10

A Dependency-Aware Multi-GPU Training Framework for Temporal Graph Neural Networks

2 Nodes

3 Nodes

Ours

80%

W TB-SS

JODIE

APAN

TGN

JODIE

APAN

WIKI

TGN

JODIE

WIKI TALK

W/O TB-SS

APAN

1.6 1.2 0.8 0.4 0.0

TGN

JODIE

APAN

TGN

JODIE

APAN

TGN

REDDIT

WIKI

REDDIT WIKI TALK

Figure 14. Effect of temporally bounded spatial partitioning. (a) Average precision (AP). (b) End-to-end speedup. Impact of intra-batch memory refinement. We study intra-batch memory refinement (IMR) under three settings: small batch (SB) with batch size 600, large batch (LB) with batch size 2400, and LB+IMR(4), which splits each large batch into four chunks of size 600. As shown in Figure 15, LB consistently worsens validation loss, while IMR recovers most of the lost accuracy with little overhead. Averaged over all six settings, the normalized loss increases from 1.00 under SB to 1.32 under LB, but drops to 1.03 with LB+IMR(4); meanwhile, the average speedup changes only from 1.24× to 1.21×. These results show that large-batch training mainly loses accuracy due to the omission of short-range dependencies within the batch. IMR recovers the missing information while still avoiding costly sequential updates.

Scalability

Normalized Val Loss

LB+IMR(4)

APAN

LB

JODIE

REDDIT (a)

SB

TGN

JODIE

APAN

TGN

WIKI

1.6 1.2 0.8 0.4 0.0

JODIE

JODIE

LB+IMR(4)

APAN

LB

TGN

SB

APAN

160% 120% 80% 40% 0%

TGN

We evaluate the scalability of DepBloom with APAN on WIKI TALK and GDELT. For multi-node scaling, we combine internode memory parallelism with DepBloom’s intra-node dependency aware execution on up to three RTX 4090 nodes. As shown in Figure 13, DepBloom achieves 87.6%/88.5% parallel efficiency at 8 GPUs on WIKI-TALK/GDELT. When scaling from 1 × 8 to 3 × 8 GPUs, it retains 94.3%/95.1% of the per-node throughput, corresponding to 2.83×/2.85× total-throughput scaling. The results show that DepBloom largely preserves its intra-node efficiency when combined with inter-node memory parallelism. Within each node, DepBloom exposes parallel sub-chains while keeping most temporal dependencies localized, increasing useful execution concurrency without proportionally increasing cross-GPU synchronization. In contrast, PipeTGL remains constrained by cross-GPU memory synchronization as the pipeline scales, while DistTGL improves parallelism by relaxing the original dependency order, which can degrade model quality. Consequently, scaling to more nodes introduces only modest per-node throughput degradation while preserving the benefits of dependencyaware execution. 5.4

JODIE

70%

Figure 13. Scalability on WIKI-TALK and GDELT with APAN, under single- and multi-node GPU configurations. For multinode, inter-node memory parallelism is combined with DepBloom’s intra-node dependency-aware execution.

5.3

W TB-SS

90%

APAN

GDELT

W/O TB-SS

100%

TGN

WIKI TALK

PipeTGL

Ours

PipeTGL

GDELT

Ours

DistTGL

WIKI TALK

PipeTGL

Ours

DistTGL

0

Throughput Per Node (× 105samples/s)

10

Speedup

1 Node

8 GPUs

20

PipeTGL

Train Throughput (×105samples/s)

4 GPUs

AP

2 GPUs

30

Temporally Bounded Spatial Partitioning. We compare with (W) and without (W/O) Temporally Bounded Spatial Partitioning in Figure 14. With our optimization enabled, the average AP increases from 91.24% to 93.02%, together with a 1.19× speedup over the baseline. This result shows that jointly exploiting temporal and topological locality better balances the accuracy-efficiency tradeoff. Temporal bounds limit the accumulation of relaxed-dependency errors, while topology-aware partitioning preserves strongly coupled events within sub-chains, exposing parallelism across sub-chains and reducing cross-chain synchronization.

Speedup

Cross-platform trends. DepBloom delivers consistent gains across both hardware platforms. On A100 and RTX 4090, it achieves average speedups of 2.97× and 2.70× across all baseline comparisons, respectively. The slightly lower gain on RTX 4090 mainly results from its more limited memory capacity, which constrains achievable batch sizes on large-scale datasets. AP improvements remain consistent across platforms, showing that the benefits of our design are not tied to a specific GPU architecture.

REDDIT

WIKI (b)

Figure 15. Effect of intra-batch memory refinement. SB uses batch size 600, LB uses batch size 2400, and LB+IMR(4) splits each large batch into four chunks of size 600. (a) Normalized validation loss. (b) End-to-end speedup.

Optimization Analysis Critical-path optimization for multi-GPU pipeline execution. We evaluate critical-path optimization under the same 8×A100 setup and batch-size configuration as the main experiment. As shown in Figure 16, we decompose epoch

To understand the effectiveness of each optimization in DepBloom, we perform an ablation study to quantify their individual contributions and examine how they improve end-toend training performance. 11

Trovato et al.

loss of 0.86× and a speedup of 1.03×. Overall, these results suggest that a proper temporal bound can preserve useful temporal locality while exposing more parallelism.

W/O W

Other Time Other Time Other Time

Memory MemoryUpdate Update Memory Update

Memory Sync Memory Sync Memory Sync

JODIE

APAN

TGN

REDDIT

JODIE

APAN

TGN

WIKI

JODIE

APAN

TGN

5 4 3 2 1 0

25 20 15 10 5 0

Training Loss Normalization

IMR(2)

Speedup Normalization

IMR(4)

IMR(8)

0.5 0.0

600

1200

2400

4800

6000

600

1200

2400

4800

6000

4800

6000

16

32

REDDIT

Batch Size

1.0 0.5

0.0

600

1200

2400

4800

WIKI 1.6 1.2 0.8 0.4 0.0

6000

600

Training Loss

W/O

4

1200

8

16

2400

REDDIT

Batch Size (a) (a)

Speedup

32

W/O

4

REDDIT

8

WIKI TALK Events (×104)

(b)

Figure 17. Sensitivity of intra-batch refinement and temporal bound. (a) Sensitivity to refinement granularity under different batch sizes on WIKI and REDDIT. Top: Normalized training loss. Bottom: Speedup. (b) Sensitivity to the temporal bound on REDDIT and WIKI-TALK. Normalized training loss. 5.6

Overhead Analysis

DepBloom introduces two additional overhead sources: preprocessing for temporally bounded spatial partitioning and computation for intra-batch memory refinement. As shown in Figure 18, these overheads take only a small fraction of total training time across all evaluated datasets and models. On average, preprocessing accounts for 0.61% of DepBloom’s end-to-end training time, while memory refinement accounts for 3.78%; the remaining 95.61% is spent on normal training execution. Compared with the baseline training time, the added preprocessing and refinement costs are smaller, accounting for only 0.19% and 1.42% on average, respectively. The low preprocessing overhead arises because temporal window construction and topology-aware spatial partitioning run before training and are reused during execution. Refinement overhead is slightly higher because it runs during training. However, refinement enables larger batches while preserving short-range temporal information, amortizing its cost through higher parallelism and fewer synchronizations.

WIKI TALK

Figure 16. Effect of critical-path optimization on multi-GPU pipeline execution. Comparison of pipeline execution with (W) and without (W/O) the optimization.

5.5

W/O

1.0

WIKI

Time per Epoch (WIKI TALK)

Time per Epoch (WIKI & REDDIT)

time into memory synchronization (Memory Sync), criticalpath memory update (Memory Update), and remaining execution time (Other Time). This optimization consistently improves pipeline efficiency, with average speedups of 1.11×, 1.22×, and 1.34× on WIKI, REDDIT, and WIKI-TALK, respectively. The benefit is larger on REDDIT and WIKI-TALK, where memory synchronization causes more severe pipeline bubbles. In particular, critical-path memory-update time drops by 68.8%, 81.3%, and 88.3% on WIKI, REDDIT, and WIKI-TALK, respectively. These results show that removing unnecessary operations from the pipeline critical path directly shortens dependency-induced stalls. The benefit is more pronounced for APAN and JODIE, whose complex memory updaters create a larger pipeline critical path. By decoupling non-urgent memory updates from the critical path and precomputing latency-sensitive metadata, DepBloom allows downstream GPUs to resolve dependencies earlier and resume execution sooner. The increasing gains on larger datasets further indicate that critical path optimization becomes more important as synchronization overhead grows.

Hyperparameter Sensitivity Analysis

Refinement

JODIE

APAN

TGN

REDDIT

Model Training

JODIE

APAN

TGN

WIKI

JODIE

APAN

Latency Breakdown

Preprocessing

100% 75% 50% 25% 0% TGN

Sensitivity to refinement granularity. We vary the number of refinement chunks from IMR(2) to IMR(4) and IMR(8) under different batch sizes on WIKI and REDDIT. As shown in Figure 17, finer-grained refinement consistently reduces training loss, especially at larger batch sizes, but introduces moderate overhead. Averaged across settings, the normalized loss decreases from 1.00 to 0.86, 0.80, and 0.76 with IMR(2), IMR(4), and IMR(8), while speedup becomes 0.93, 0.91, and 0.90, respectively. Overall, IMR(4) offers a good trade-off and is used as the default setting. Sensitivity to temporal bound. We vary the temporal bound in temporally bounded spatial partitioning and report results in Figure 17(b). A moderate bound consistently provides a favorable accuracy-efficiency trade-off. On REDDIT, bound 8 achieves the highest speedup of 1.44× with almost unchanged loss, while bound 16 further reduces loss to 0.86× with a still high speedup of 1.37×. On WIKI-TALK, increasing the bound steadily improves both quality and efficiency in the evaluated range, with bound 32 achieving the best

WIKI TALK

Figure 18. Latency breakdown of DepBloom across datasets and TGNN models, including preprocessing for temporally bounded spatial partitioning and extra computation from intra-batch memory refinement. 12

A Dependency-Aware Multi-GPU Training Framework for Temporal Graph Neural Networks

6

Related Work

[2] Luca Belli, Sofia Ira Ktena, Alykhan Tejani, Alexandre Lung-YutFon, Frank Portman, Xiao Zhu, Yuanpu Xie, Akshay Gupta, Michael Bronstein, Amra Delić, et al. 2020. Privacy-preserving recommender systems challenge on twitter’s home timeline. arXiv preprint arXiv:2004.13715 (2020). [3] Zhenkun Cai, Xiao Yan, Yidi Wu, Kaihao Ma, James Cheng, and Fan Yu. 2021. DGCL: An efficient communication library for distributed GNN training. In Proceedings of the Sixteenth European Conference on Computer Systems. 130–144. [4] Defu Cao, Yujing Wang, Juanyong Duan, Ce Zhang, Xia Zhu, Congrui Huang, Yunhai Tong, Bixiong Xu, Jing Bai, Jie Tong, et al. 2020. Spectral temporal graph neural network for multivariate time-series forecasting. Advances in neural information processing systems 33 (2020), 17766–17778. [5] Venkatesan T Chakaravarthy, Shivmaran S Pandian, Saurabh Raje, Yogish Sabharwal, Toyotaro Suzumura, and Shashanka Ubaru. 2021. Efficient scaling of dynamic graph neural networks. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1–15. [6] Chaoyi Chen, Dechao Gao, Yanfeng Zhang, Qiange Wang, Zhenbo Fu, Xuecang Zhang, Junhua Zhu, Yu Gu, and Ge Yu. 2023. NeutronStream: A dynamic GNN training framework with sliding window for graph streams. arXiv preprint arXiv:2312.02473 (2023). [7] Chao Ma Da Zheng, Minjie Wang, Jinjing Zhou, Qidong Su, Xiang Song, Quan Gan, Zheng Zhang, and George Karypis. 2020. Distdgl: distributed graph neural network training for billion-scale graphs. In 2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3). IEEE, 36–44. [8] Yue Dai. 2025. Towards Efficient and Robust Graph Deep Learning. Ph. D. Dissertation. University of Pittsburgh. [9] Yue Dai, Liang Liu, Xulong Tang, Youtao Zhang, and Jun Yang. 2025. MemFreezing: A Novel Adversarial Attack on Temporal Graph Neural Networks under Limited Future Knowledge. In Forty-second International Conference on Machine Learning. [10] Yue Dai, Xulong Tang, and Youtao Zhang. 2025. Cascade: A dependency-aware efficient training framework for temporal graph neural network. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2. 95–110. [11] Kaihua Fu, Quan Chen, Yuzhuo Yang, Jiuchen Shi, Chao Li, and Minyi Guo. 2023. Blad: Adaptive load balanced scheduling and operator overlap pipeline for accelerating the dynamic gnn training. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1–13. [12] Swapnil Gandhi and Anand Padmanabha Iyer. 2021. P3: Distributed deep graph learning at scale. In 15th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 21). 551–568. [13] Shihong Gao, Yiming Li, Yanyan Shen, Yingxia Shao, and Lei Chen. 2024. ETC: Efficient Training of Temporal Graph Neural Networks over Large-scale Dynamic Graphs. Proceedings of the VLDB Endowment 17, 5 (2024), 1060–1072. [14] Mingyu Guan, Anand Padmanabha Iyer, and Taesoo Kim. 2022. Dynagraph: dynamic graph neural networks at scale. In Proceedings of the 5th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA). 1–10. [15] Ryien Hosseini, Filippo Simini, Venkatram Vishwanath, and Henry Hoffmann. 2025. A deep probabilistic framework for continuous time dynamic graph generation. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39. 17249–17257. [16] Md Ashraful Islam, Hojae Son, Suhaas Kiran Doddagaddavalli Gangadharaiah, and Marco Serafini. 2026. PRISM: A Training System to Unlock the Potential of Temporal Graph Learning Through Staleness Avoidance. Proc. VLDB Endow. 19, 9 (Aug. 2026), 2196–2209.

Although prior systems accelerate GNN training [7, 28, 43, 47], they do not directly address multi-GPU TGNN training, whose core challenge comes from temporal dependencies across events. Earlier dynamic-graph studies largely focused on discrete-time dynamic graphs (DTDGs), which model graph evolution as snapshots [5, 6, 11, 14, 34, 40]. More recent TGNNs increasingly adopt continuous-time dynamic graphs (CTDGs), which model graph evolution as chronologically ordered event streams and thereby better preserve fine-grained temporal dynamics, but this also introduces event-level training dependencies that make snapshot-based DTDG optimizations difficult to transfer directly [10, 13, 21, 26, 32, 39, 42, 46, 54, 55]. Prior CTDG-focused work improves training efficiency through both algorithmic and systems-level techniques [10, 13, 37, 54]. TGL [54] provides a general framework for CTDG training, while ETC [13] improves efficiency through dynamic batching and Cascade [10] enlarges batches by exploiting spatial and temporal independence. PRISM [16] mitigates intra-batch memory staleness through multi-version memory and refinement. Other studies further reduce overheads by optimizing memory access, data movement, and runtime execution [13, 25, 37, 49]. These methods are designed mainly for single-GPU execution. When extended to multi-GPU training, they do not address how batches should be organized across GPUs to expose parallelism, often leading to workload imbalance and low GPU utilization. In multi-GPU and distributed settings, GNNFlow [53] improves graph storage and data movement, while DistTGL [55] and PipeTGL [26] optimize parallel execution over a fixed chronological batch sequence. Nevertheless, these methods either preserve event dependencies too conservatively or relax them too aggressively, and still struggle to jointly optimize training efficiency and model quality.

7

Conclusion

We present DepBloom, a scalable multi-GPU framework for TGNN training. Instead of synchronizing all dependencies across small batches, DepBloom combines temporally bounded spatial partitioning, intra-batch memory refinement, and critical-path optimization to reduce unnecessary synchronization, recover missing short-range temporal information, and shorten memory-synchronization stalls. Across representative TGNN models and dynamic graph datasets, DepBloom achieves 2.84× average speedup and up to 5.16× speedup over state-of-the-art baselines while maintaining comparable or better model quality.

References [1] Marouane Alilou, Bikram Pratim Bhuyan, Rachida Fissoune, and Amar Ramdane-Cherif. 2026. Temporal motif-based representation learning on continuous-time dynamic graphs. Data Mining and Knowledge Discovery 40, 2 (2026), 22. 13

Trovato et al.

high-performance deep learning library. Advances in neural information processing systems 32 (2019). [32] Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. 2020. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006.10637 (2020). [33] Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. 2020. Temporal Graph Networks for Deep Learning on Dynamic Graphs. In ICML 2020 Workshop on Graph Representation Learning. [34] Benedek Rozemberczki, Paul Scherer, Yixuan He, George Panagopoulos, Alexander Riedel, Maria Astefanoaei, Oliver Kiss, Ferenc Beres, Guzman Lopez, Nicolas Collignon, et al. 2021. Pytorch geometric temporal: Spatiotemporal signal processing with neural machine learning models. In Proceedings of the 30th ACM international conference on information & knowledge management. 4564–4573. [35] Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. 2020. DySAT: Deep Neural Representation Learning on Dynamic Graphs via Self-Attention Networks. In Proceedings of the 13th International Conference on Web Search and Data Mining (Houston, TX, USA) (WSDM ’20). Association for Computing Machinery, New York, NY, USA, 519–527. doi:10.1145/3336191.3371845 [36] Yingxia Shao, Hongzheng Li, Xizhi Gu, Hongbo Yin, Yawen Li, Xupeng Miao, Wentao Zhang, Bin Cui, and Lei Chen. 2024. Distributed graph neural network training: A survey. Comput. Surveys 56, 8 (2024), 1–39. [37] Guangming Sheng, Junwei Su, Chao Huang, and Chuan Wu. 2024. Mspipe: Efficient temporal gnn training via staleness-aware pipeline. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2651–2662. [38] Zixing Song, Yuji Zhang, and Irwin King. 2023. Towards fair financial services for all: A temporal GNN approach for individual fairness on transaction networks. In Proceedings of the 32nd ACM international conference on information and knowledge management. 2331–2341. [39] Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. 2019. Dyrep: Learning representations over dynamic graphs. In International conference on learning representations. [40] Chunyang Wang, Desen Sun, and Yuebin Bai. 2023. PiPAD: Pipelined and parallel dynamic GNN training on GPUs. In Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. 405–418. [41] Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, et al. 2019. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint arXiv:1909.01315 (2019). [42] Xuhong Wang, Ding Lyu, Mengjian Li, Yang Xia, Qi Yang, Xinwen Wang, Xinguang Wang, Ping Cui, Yupu Yang, Bowen Sun, et al. 2021. Apan: Asynchronous propagation attention network for real-time temporal graph embedding. In Proceedings of the 2021 international conference on management of data. 2628–2638. [43] Yuke Wang, Boyuan Feng, Gushu Li, Shuangchen Li, Lei Deng, Yuan Xie, and Yufei Ding. 2021. {GNNAdvisor}: An adaptive and efficient runtime system for {GNN} acceleration on {GPUs}. In 15th USENIX symposium on operating systems design and implementation (OSDI 21). 515–531. [44] Yufeng Wang and Charith Mendis. 2024. Tglite: A lightweight programming framework for continuous-time temporal graph neural networks. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2. 1183–1199. [45] Shu Wu, Yuyuan Tang, Yanqiao Zhu, Liang Wang, Xing Xie, and Tieniu Tan. 2019. Session-based recommendation with graph neural networks. In Proceedings of the Thirty-Third AAAI Conference on

doi:10.14778/3819518.3819544 [17] Zhen Jia, Abdalghani Abujabal, Rishiraj Saha Roy, Jannik Strötgen, and Gerhard Weikum. 2018. Tequila: Temporal question answering over knowledge bases. In Proceedings of the 27th ACM international conference on information and knowledge management. 1807–1810. [18] George Karypis and Vipin Kumar. 1997. METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. (1997). [19] Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. 2020. Representation learning for dynamic graphs: A survey. Journal of Machine Learning Research 21, 70 (2020), 1–73. [20] Srijan Kumar, William L. Hamilton, Jure Leskovec, and Dan Jurafsky. 2018. Community Interaction and Conflict on the Web. In Proceedings of the 2018 World Wide Web Conference (Lyon, France) (WWW ’18). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 933–943. doi:10.1145/3178876.3186141 [21] Srijan Kumar, Xikun Zhang, and Jure Leskovec. 2019. Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks. In Proceedings of the 25th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM. [22] Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. 2010. Signed networks in social media. In Proceedings of the SIGCHI conference on human factors in computing systems. 1361–1370. [23] Jure Leskovec and Rok Sosič. 2016. Snap: A general-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technology (TIST) 8, 1 (2016), 1–20. [24] Fuxian Li, Jie Feng, Huan Yan, Guangyin Jin, Fan Yang, Funing Sun, Depeng Jin, and Yong Li. 2023. Dynamic graph convolutional recurrent network for traffic prediction: Benchmark and solution. ACM Transactions on Knowledge Discovery from Data 17, 1 (2023), 1–21. [25] ZhiQiang Liang, Hongyu Gao, Jue Wang, Fang Liu, Xingguo Shi, Junyu Gu, Peng Di, Sian Li, Lei Tang, Chunbao Zhou, Lian Zhao, Yangang Wang, and Xuebin Chi. 2026. TAC: Cache-Based System for Accelerating Billion-Scale GNN Training on Multi-GPU Platform. In Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (Sydney, NSW, Australia) (PPoPP ’26). Association for Computing Machinery, New York, NY, USA, 577–590. doi:10.1145/3774934.3786460 [26] Jun Liu, Bingqian Du, Ziyue Luo, Sitian Lu, Qiankun Zhang, and Hai Jin. 2025. PipeTGL:(Near) Zero Bubble Memory-based Temporal Graph Neural Network Training via Pipeline Optimization. Proceedings of the VLDB Endowment 18, 8 (2025), 2722–2734. [27] Antonio Longa, Veronica Lachi, Gabriele Santin, Monica Bianchini, Bruno Lepri, Pietro Lio, Franco Scarselli, and Andrea Passerini. 2023. Graph neural networks for temporal graphs: State of the art, open challenges, and opportunities. arXiv preprint arXiv:2302.01018 (2023). [28] Vasimuddin Md, Sanchit Misra, Guixiang Ma, Ramanarayan Mohanty, Evangelos Georganas, Alexander Heinecke, Dhiraj Kalamkar, Nesreen K Ahmed, and Sasikanth Avancha. 2021. Distgnn: Scalable distributed training for large-scale graph neural networks. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1–14. [29] John Nickolls, Ian Buck, Michael Garland, and Kevin Skadron. 2008. Scalable parallel programming with cuda: Is cuda the parallel programming model that application developers have been waiting for? Queue 6, 2 (2008), 40–53. [30] Joel Oskarsson, Per Sidén, and Fredrik Lindsten. 2023. Temporal graph neural networks for irregular data. In International Conference on Artificial Intelligence and Statistics. PMLR, 4515–4531. [31] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019. Pytorch: An imperative style,

14

A Dependency-Aware Multi-GPU Training Framework for Temporal Graph Neural Networks

Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence (Honolulu, Hawaii, USA) (AAAI’19/IAAI’19/EAAI’19). AAAI Press, Article 43, 8 pages. doi:10. 1609/aaai.v33i01.3301346 [46] Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. 2020. Inductive representation learning on temporal graphs. arXiv preprint arXiv:2002.07962 (2020). [47] Shuangyan Yang, Minjia Zhang, Wenqian Dong, and Dong Li. 2023. Betty: Enabling large-scale gnn training with batch-level graph partitioning. In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2. 103–117. [48] Jiaxuan You, Tianyu Du, and Jure Leskovec. 2022. Roland: graph learning framework for dynamic graphs. In Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining. 2358–2366. [49] Longjiao Zhang, Rui Wang, Tongya Zheng, Ziqi Huang, Wenjie Huang, Xinyu Wang, Can Wang, Mingli Song, Sai Wu, and Shuibing He. 2025. Effective and Efficient Distributed Temporal Graph Learning through Hotspot Memory Sharing. Proceedings of the VLDB Endowment 18, 9 (2025), 3093–3105. [50] Yao Zhang, Yun Xiong, Yongxiang Liao, Yiheng Sun, Yucheng Jin, Xuehao Zheng, and Yangyong Zhu. 2023. Tiger: Temporal interaction graph embedding with restarts. In Proceedings of the ACM web

conference 2023. 478–488. [51] Da Zheng, Xiang Song, Chengru Yang, Dominique LaSalle, and George Karypis. 2022. Distributed hybrid cpu and gpu training for graph neural networks on billion-scale heterogeneous graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 4582–4591. [52] Ying Zhong and Chenze Huang. 2023. A dynamic graph representation learning based on temporal graph transformer. Alexandria Engineering Journal 63 (2023), 359–369. [53] Yuchen Zhong, Guangming Sheng, Tianzuo Qin, Minjie Wang, Quan Gan, and Chuan Wu. 2023. Gnnflow: A distributed framework for continuous temporal gnn learning on dynamic graphs. arXiv preprint arXiv:2311.17410 (2023). [54] Hongkuan Zhou, Da Zheng, Israt Nisa, Vasileios Ioannidis, Xiang Song, and George Karypis. 2022. Tgl: A general framework for temporal gnn training on billion-scale graphs. arXiv preprint arXiv:2203.14883 (2022). [55] Hongkuan Zhou, Da Zheng, Xiang Song, George Karypis, and Viktor Prasanna. 2023. Disttgl: Distributed memory-based temporal graph neural network training. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1–12.

15

Related documents

• A Dependency-Aware Multi-GPU Training Framework for Temporal Graph Neural Networks#1326980
• Advancing graph neural networks : addressing representation challenges in the vision domain#413324
• DepTGL: A Parallel Framework for Memory-based TGNN Training with Adaptive Temporal Data Dependency Management#620705
• DepTGL: A Parallel Framework for Memory-based TGNN Training with Adaptive Temporal Data Dependency Management#619026
• DepTGL: A Parallel Framework for Memory-based TGNN Training with Adaptive Temporal Data Dependency Management#459613