ETC: Efficient Training of Temporal Graph Neural Networks over

Large-scale Dynamic Graphs

Shihong Gao Yiming Li Yanyan Shen∗
The Hong Kong University of Science The Hong Kong University of Science Shanghai Jiao Tong University
and Technology and Technology shenyy@[Link]
sgaoar@[Link] yliix@[Link]

Yingxia Shao∗ Lei Chen

Beijing University of Posts and The Hong Kong University of Science
Telecommunications and Technology (GZ)
shaoyx@[Link] leichen@[Link]

ABSTRACT 1 INTRODUCTION
Dynamic graphs play a crucial role in various real-world appli- Dynamic graphs, which are constantly updated with new nodes
cations, such as link prediction and node classification on social and edges, play a crucial role in many real-world applications. For
media and e-commerce platforms. Temporal Graph Neural Net- instance, users on social platforms engage with each other over
works (T-GNNs) have emerged as a leading approach for handling time by commenting on posts or sending messages. Likewise, on e-
dynamic graphs, using temporal message passing to compute tem- commerce platforms, users buy a diverse range of items at different
poral node embeddings. However, training existing T-GNNs on time. To support various downstream tasks such as node classifi-
large-scale dynamic graphs is prohibitively expensive due to the cation and link prediction, it is necessary to learn representations
ill-suited batching scheme and significant data access overhead. In of nodes based on new interactions. Temporal Graph Neural Net-
this paper, we introduce ETC, a generic framework designed specifi- works (T-GNNs) [15, 27, 31ś33] are at the forefront of this endeavor,
cally for efficient T-GNN training at scale. ETC incorporates a novel having achieved state-of-the-art performance in learning represen-
data batching scheme that enables large training batches improving tations on dynamic graphs. T-GNNs employ recursive temporal
model computation efficiency, while preserving model effectiveness message passing to compute the temporal embedding of a target
by restricting information loss in each training batch. To reduce node at a specific timestamp. This process involves time-dependent
data access overhead, ETC employs a three-step data access policy neighbor sampling and time-encoded neighborhood aggregation,
that leverages the data access pattern in T-GNN training, signifi- which enables T-GNNs to capture the propagation process on evolv-
cantly reducing redundant data access volume. Additionally, ETC ing graphs more effectively. Recent studies have demonstrated that
utilizes an inter-batch pipeline mechanism, decoupling data access T-GNNs can significantly outperform static GNNs [11, 14, 29] and
from model computation and further reducing data access costs. snapshot-based GNNs [8, 10, 23] by a considerable margin in terms
Extensive experimental results demonstrate the effectiveness of of predictive performance.
ETC, showcasing its ability to achieve significant training speedups Generally, the training of T-GNNs is in an offline and chronolog-
compared to state-of-the-art training frameworks for T-GNNs on ical fashion [27, 33]. Figure 1 provides an illustration of the general
real-world dynamic graphs with millions of interactions. ETC pro- T-GNN training workflow. Given an input dynamic graph stored on
vides a training speedup ranging from 1.6× to 62.4×, highlighting CPU, it is split into multiple training batches in the preprocessing
its potential for efficient training on large-scale dynamic graphs. stage. Each training batch contains a number of interactions, of
which the timestamps are contiguous in an increasing order. After
PVLDB Reference Format: the preprocessing step, the T-GNN starts to process the generated
Shihong Gao, Yiming Li, Yanyan Shen, Yingxia Shao, and Lei Chen. ETC: batches on GPU in a sequential fashion to preserve the intrinsic
Efficient Training of Temporal Graph Neural Networks over Large-scale temporal dependency of the input dynamic graphs. The process-
Dynamic Graphs. PVLDB, 17(5): 1060 - 1072, 2024.
ing of a batch consists of temporal neighbor sampling, input data
doi:10.14778/3641204.3641215
access, and model computation. Given the target interactions in a
PVLDB Artifact Availability: batch, it is firstly required to conduct temporal neighbor sampling
The source code, data, and/or other artifacts have been made available at for the nodes included in the target interactions. Then based on
[Link] the computation graph generated in the sampling phase, the cor-
responding data such as node state vectors, which summarize the
∗ Yanyan Shen and Yingxia Shao are the corresponding authors. past interactive information of nodes, are accessed and fed to the
This work is licensed under the Creative Commons BY-NC-ND 4.0 International T-GNN model for computation.
License. Visit [Link] to view a copy of
this license. For any use beyond those covered by this license, obtain permission by Apart from the outstanding performance of T-GNNs, researchers
emailing info@[Link]. Copyright is held by the owner/author(s). Publication rights in DB community [18, 19, 39] recently have discovered that the
licensed to the VLDB Endowment. training of T-GNNs is prohibitively expensive on large-scale dy-
Proceedings of the VLDB Endowment, Vol. 17, No. 5 ISSN 2150-8097.
doi:10.14778/3641204.3641215 namic graphs, such that merely one training epoch for existing

1060
 Preprocessing Training
Input Dynamic Graph (B): Temporal Neighbor Sampling
𝑡 Batch 3 𝑡 𝑡 𝑡 𝑡
4 5
𝑡 𝑡 𝑡 4 4 2 4 4 5
2 3 𝑡 𝑡 𝑡 𝑡 𝑡 𝑡
𝑡
𝑡 2 5 3 3 3 3
1 (C): Input Data Access (D): Model Computation
State Vectors 𝑡 𝑡 𝑡 𝑡
(A): Batch Split 𝑠" 𝑠# 𝑠! 𝑠$ 𝑠% 2 4 4 5
Batch 1 Batch 2 Batch 3

1 2 3 3 4 4 T-GNN
𝑡 𝑡 𝑡 𝑡 𝑡 𝑡 𝑠! 𝑠! 𝑠! 𝑠! 𝑠! 𝑠! 𝑠! 𝑠!
2 3 5 4 2 5 3 3 3 3 3 3 3 3
𝑡 𝑡 𝑡 𝑡 𝑡 𝑡 𝑡 𝑡

Figure 1: A toy example of T-GNN training. The input dy- Figure 2: Comparison of the normalized time among the
namic graph contains 6 interactions with different times- input data access (Access.), model computation (Comp.), and
tamps. The batch size is 2 (2 target interactions), the number the other data preparation operations (Others) when training
of sampled neighbor is 1. different T-GNN models on GDELT using TGL.

T-GNNs over large-scale dynamic graphs would take hours to com- Bottleneck II: High Input Data Access Costs Dominate the
plete [19]. To tackle the overwhelming T-GNN training costs, Orca Training Process. When tackling the large-scale dynamic graphs,
[18] and Zebra [19] focus on improving the model computation we find that the input data access is de facto the dominant part
efficiency of T-GNNs. Orca utilizes historical embeddings to avoid of the overall training process. As shown in Figure 2, the input
certain computational workload. Zebra proposes to modify the ag- data access phase generally takes up over 60% of the total training
gregation operation in T-GNN by a temporal personalized PageRank time, which vastly overshadows the costs of model computation
mechanism, which only aggregates the most influential neighbors and the other data preparation operations. Such overwhelming
for target nodes to reduce computation costs. However, their tech- cost originates from frequent data transfer between CPU and GPU.
niques can only be generalized to synchronous T-GNNs [15, 27, 33]. Since the input data such as node features are stored on the CPU
By contrast, TGL [39] is a generic training framework that supports side, the required input data for each batch are constantly selected
various types of T-GNNs [15, 27, 28, 31, 33]. Nonetheless, it only on CPU and transferred to GPU in the entire training loop.
focuses on accelerating the sampling stage but overlooks the other In this paper, we propose a generic framework ETC, which en-
stages in the general T-GNN training workflow. In this paper, we ables efficient training over large-scale dynamic graphs for different
identify that: (1) the typical small batch size setting in the prepro- variants of T-GNNs. It comprises several systematic designs to re-
cessing stage can heavily hinder the model computation efficiency, solve the common efficiency bottlenecks concerning the general
and (2) the input data access stage occupies a large proportion of T-GNN training workflow.
total training time. These two bottlenecks limit the scalability of To address Bottleneck I, we take a fundamentally different
training T-GNNs on large-scale dynamic graphs. batching approach in the preprocessing stage. We first introduce
Bottleneck I: Small Batch Size Hinders the Efficiency of a novel score function to quantify the impact of information loss.
Model Computation. In the preprocessing stage, existing works Then, we formulate a batch split problem that aims to minimize the
[15, 18, 19, 27, 31ś33] usually employ a small batch size to mitigate number of batches used in training while controlling the extent of
the intra-batch information loss issue [15, 27, 31]. In T-GNN train- information loss of each batch. By reducing the number of batches,
ing, in order to process the interactions in a given batch in parallel we can enlarge the batch size on average. To solve the batch split
by GPU, the intra-batch dependencies among target nodes in the problem, we propose an efficient single-pass algorithm, which scans
same batch have to be deserted causing information loss [27]. The the input dynamic graph only once in the preprocessing stage and
larger batch size is, the more intra-batch dependencies can be lost, generates the corresponding batching scheme. We also provide a
which will degrade model performance [27, 31]. However, when rigorous theoretical analysis to demonstrate that our algorithm can
training over large-scale dynamic graphs with over millions of in- provide an optimal solution to the batch split problem.
teractions, utilizing a small batch size to alleviate information loss To address Bottleneck II, our key observation is that: there
results in unsatisfactory training efficiency. Since a small batch size exists plenty of redundant data access in each batch due to the
setting not only produces numerous training batches for T-GNNs temporal characteristic. For instance, the same data in the CPU
to process the whole graph, but also results in limited exploitation storage, e.g., node state vectors that summarizes the past interac-
of GPU parallelism [15], which largely impedes the model compu- tive information of nodes, can be repeatedly accessed by the nodes
tation efficiency of T-GNNs over large-scale dynamic graphs. As with the same ID but different timestamps. In practice, redundant
shown in [18, 19], with batch size set as 200, it takes over 12 hours data access can take up over 80% of the total data access volume.
for existing T-GNNs to finish just one epoch of model computation Based on the crucial observation, We propose a novel three-step
on the large-scale Wiki-Talk [3] dataset. data access policy Supra. Unlike the conventional input data access

1061
approach [18, 19, 39], which directly performs input data access different edge feature vectors. In this work, we focus on Continous-
based on the sampling result, Supra firstly identifies the redundant Time Dynamic Graphs (CTDGs) rather than Discrete Time Dynamic
access workload according to the sampling result, then, it only Graphs (DTDGs), since CTDGs are more general and reflective in
performs data access for the unique data in each batch. Finally, the terms of dynamic evolving patterns.
originally required data for a given batch are reconstructed on GPU Event Types Covered by CTDG. Generally, a CTDG includes
by Supra. As Supra requires constant identification of redundant not only the addition of interaction events, but also the deletion and
access workload throughout the training process, it is important update of interaction events, which can be distinctly reflected in the
to guarantee that the reduced data access costs by Supra are not associated descriptive features [27]. Besides, for node-wise events
outweighed by the cost of Supra itself. To achieve this, we manage (addition/deletion of nodes, update of node features), they can be
the training workflow by proposing an inter-batch pipeline mecha- perceived as self-interacted events, thus can be defined similarly as
nism. It enables concurrent execution of the model computation for described in Definition 1.
the current batch alongside Supra for the subsequent batch. This
simple yet effective pipeline mechanism helps to further improve 2.2 Temporal Graph Neural Networks
the overall efficiency gain. Temporal Graph Neural Networks (T-GNNs) have shown their su-
In summary, we have made the following contributions: periority of representation learning on dynamic graphs. Currently,
• We present ETC, a generic framework tailored for efficient existing state-of-the-art T-GNNs [15, 27, 32] on CTDGs can be
T-GNN training on large-scale dynamic graphs, which com- generalized into a common architecture, which involves two key
prises systematic designs to resolve the efficiency bottle- operations: node state update and temporal message passing.
necks in the general T-GNN training workflow. Node State Update. Since different nodes may have an interac-
• We formulate a batch split problem for T-GNN training tion history of different lengths, merely using neighborhood sam-
over large-scale dynamic graphs with practical constraints pling may not be adequate to provide information for the dynamic
on information loss, and propose an efficient single-pass embedding generation. Therefore, most existing T-GNN models
algorithm for solving this problem, which generates large [15, 19, 27, 31] adopt the node memory module to summarize the
batches for higher model computation efficiency while re- past information of nodes. Specifically, for each node 𝑣𝑖 , T-GNN
stricting information loss for model performance preserva- maintains a state vector 𝑠𝑖 (𝑡) for it, which encodes the historical
tion. Moreover, We provide a rigorous theoretical analysis information of the interactions containing node 𝑣𝑖 . Upon the arrival
demonstrating that the proposed algorithm yields an opti- of an interaction 𝛼 (𝑡) = (𝑣𝑖 , 𝑣 𝑗 , 𝑒𝑖 𝑗 (𝑡), 𝑡), T-GNN firstly updates the
mal solution to the batch split problem. state vectors for the nodes 𝑣𝑖 and 𝑣 𝑗 as follows:
• ETC significantly reduces the input data access costs in
𝑠𝑖 (𝑡) = UPDATE(𝑠𝑖 (𝑡 − ), 𝑠 𝑗 (𝑡 − ), 𝑒𝑖 𝑗 (𝑡), 𝜙 (𝑡 − 𝑡 − )), (1)
training T-GNNs over large-scale graphs by a novel three-
step data access policy Supra, which substantially removes 𝑠 𝑗 (𝑡) = UPDATE(𝑠 𝑗 (𝑡 − ), 𝑠𝑖 (𝑡 − ), 𝑒𝑖 𝑗 (𝑡), 𝜙 (𝑡 − 𝑡 − )), (2)
data access redundancy. Besides, we propose a simple yet where UPDATE is the RNN or GRU memory updater. 𝑠𝑖 (𝑡 − ) and
effective inter-batch pipeline mechanism, which reduces 𝑠 𝑗 (𝑡 − ) are the latest state vectors for node 𝑣𝑖 and 𝑣 𝑗 before the
the cost associated with Supra and helps to further enhance timestamp 𝑡. 𝜙 (·) is a time encoding function, which encodes the
the data preparation efficiency. time interval Δ𝑡 = 𝑡 − 𝑡 − into a vector.
• Extensive experiments are conducted to showcase the ef- Temporal Message Passing. When a new interaction 𝛼 (𝑡) =
fectiveness of the proposed ETC framework. The results (𝑣𝑖 , 𝑣 𝑗 , 𝑒𝑖 𝑗 (𝑡), 𝑡) arrives, T-GNN generates the node embedding ℎ𝑖ℓ (𝑡)
demonstrate that ETC enjoys 1.6× ∼ 62.4× training speedup for node 𝑣𝑖 (and for node 𝑣 𝑗 as well) in the following steps:
compared to state-of-the-art T-GNN training frameworks.
𝑁𝑖ℓ (𝑡) = SAMPLE(G, 𝑣𝑖 , 𝑡), (3)
2 BACKGROUND ℎ𝑖ℓ (𝑡) = AGGREGATE({ℎ ℓ𝑗 −1 (𝑡 − )||𝑒𝑖 𝑗 (𝑡 − )||𝜙 (𝑡 −
− 𝑡 )|
In this section, we introduce the concept of Continuous-time Dy-
namic Graphs (CTDGs) and Temporal Graph Neural Networks (𝑣 𝑗 , 𝑡 − ) ∈ 𝑁𝑖ℓ (𝑡)}), ∀ℓ = 1, ..., 𝐿, (4)
(T-GNNs). ℎ 0𝑗 (𝑡 − ) = 𝑠 𝑗 (𝑡 − ) + MLP(𝑥 𝑗 ). (5)

2.1 Continuous-time Dynamic Graphs Firstly T-GNN conducts temporal neighborhood sampling for 𝑣𝑖
(Eq.3). The sampled neighbor set 𝑁𝑖 (𝑡) consists of nodes, which
Definition 1 (Continuous-time dynamic graph (CTDG)).
interacts with the node 𝑣𝑖 before the timestamp 𝑡. Note that in tem-
A CTDG can be described as a collection of interaction events G =
poral sampling, the timestamp needs to be considered. It means that
{𝛼 (𝑡 1 ), 𝛼 (𝑡 2 ), ...}, which occur over time and are ordered chronolog-
the same nodes may be sampled multiple times but with different
ically. Each event is represented by a tuple 𝛼 (𝑡) = (𝑣𝑖 , 𝑣 𝑗 , 𝑒𝑖 𝑗 (𝑡), 𝑡),
timestamps. As for the sampling strategy, top-𝑘 recent neighbor
which represents a temporal edge in a directed graph. This tuple
sampling is widely adopted in previous literature [19, 27, 31], which
includes the nodes 𝑣𝑖 and 𝑣 𝑗 which are connected by an edge, an asso-
samples the top-k neighboring nodes of the target node 𝑣𝑖 with
ciated feature vector 𝑒𝑖 𝑗 (𝑡) which describes the edge, and a timestamp
the latest timestamps up to 𝑡. Then, T-GNN conducts embedding
𝑡 that indicates when the interaction occurred.
generation at the ℓ-th layer through the neighborhood informa-
A CTDG can also be viewed as a multigraph, in which multiple tion aggregation for node 𝑣𝑖 at the timestamp 𝑡 (Eq.4). Generally,
edges can occur between two nodes in multiple timestamps with AGGREGATE is an attention-based aggregator. Moreover, during

1062
 CPU GPU in CPU main memory throughout the training process. This CPU
Dynamic graph main memory storage scheme is also the mainstream choice in sys-
𝑡! 1 𝑡" 1
𝑡"
Aggregate tems for static GNN training [20, 34, 37]. On the other hand, GPU
③ ④
𝑡% ① is responsible for conducting model computation of the T-GNN.
2 4 4
𝑡$ 3 𝑡# 3
𝑡# Preprocessing. Before the training, it is required to preprocess
Node features the given dynamic graph and split it into multiple batches with a
②
temporal order constraint as shown in Figure 1. The temporal order
constraint preserves the intrinsic temporal characteristic of the
Edge features ⑤ Update
dynamic graph. It ensures that the order of the timestamps cannot
be violated. For example, in Figure 1, it is not allowed to exchange
the interaction (𝑣 2 , 𝑣 3 , 𝑒 23 (𝑡 2 ), 𝑡 2 ) in Batch 1 with the interaction
Node state vectors ⑥ (𝑣 3 , 𝑣 5 , 𝑒 35 (𝑡 3 ), 𝑡 3 ) in Batch 2. Since the T-GNN would process the
batches in a sequential fashion, no prediction would be made by
leveraging the future information. Otherwise, the prediction result
is unfair.
Figure 3: An illustration of hybrid CPU-GPU data layout Main Training Stages. Model training on each batch mainly
for T-GNN training over large-scale dynamic graphs. The consists of three stages: temporal neighbor sampling, input data
input dynamic graph, associated node features, edge features access, and model computation. For each target node in a given
and the node state vectors are held in CPU main memory batch, the temporal neighbor sampling is conducted as shown in
during training. For every training batch, ① neighborhood Eq. 3. Different from the sampling in static graphs, in which all the
sampling is performed on CPU. ② Based on the sampling neighbors of the target node are sampling candidates, the temporal
result, the corresponding input data are accessed on CPU. ③ neighbor sampling only considers the neighbors with past times-
The sampled subgraph together with accessed data is trans- tamps so that no future neighbors would be included. To enhance
ferred from CPU to GPU for ④ T-GNN model computation. ⑤ the efficiency of such a sampling process, TGL [39] proposes a
The updater on GPU updates the state vectors for the target parallel sampler, such that the temporal neighbor sampling pro-
nodes in the current batch. ⑥ The updated state vectors for cess for different nodes can be conducted simultaneously. Then the
target nodes are transferred back from GPU to CPU. corresponding node state vectors, node features, and edge features
required for model computation are accessed based on the sam-
pling result. Finally, these accessed input data are fed to the T-GNN
the temporal message passing, the input node features at the first model for computation. To accelerate the model computation stage
layer are comprised of initial node features and the state vectors of of T-GNN training, Orca [18] utilizes the historical embeddings to
nodes (Eq.5). If the CTDG does not provide the initial node features, reduce the frequency of aggregation, while Zebra [19] changes the
the input features would be solely the node state vectors. aggregation rule of general T-GNN [27], which only aggregates
most influential temporal neighbors.
2.3 Training of T-GNNs
Generally, T-GNN offline training is conducted in a chronological 3 BOTTLENECKS OF T-GNN TRAINING ON
fashion. We illustrate the data layout, the preprocessing, and main LARGE-SCALE DYNAMIC GRAPHS
training stages for T-GNN training over large-scale dynamic graphs
as follows. In this section, we provide more detailed analysis for the two pivotal
Data Layout. In previous works [15, 19, 27, 31ś33], most T- efficiency bottlenecks discussed in Section 1, which prevent scaling
GNNs are trained in an all-on-GPU fashion, such that the storage of existing T-GNNs to large-scale dynamic graphs.
the necessary input data for training and the training process itself
solely rely on GPU. However, when tackling large-scale dynamic 3.1 Ill-suited Batching Scheme in Preprocessing
graphs, GPU alone is not adequate to take over both the storage As illustrated in Section 1, the traditional batching scheme for
and training process. For example, for GDELT [16], a real-world T-GNN training in previous literature [18, 19, 27, 31, 39] usually
dynamic knowledge graph with near-billion interactions, just the adopts a small batch size, which leads to few interactions being
storage of all the input data would already consume over 130GB processed in parallel by T-GNN models on GPU. As a result, the
memory. This vastly exceeds the memory capacity of a single GPU, efficiency of T-GNN computation is dragged down [15]. Naively
which is generally equipped with 11GB ∼ 40GB memory. To accom- setting a large batch size under the traditional batching scheme
modate the memory requirement of large-scale dynamic graphs, can exaggerate the intra-batch information loss issue. Example 1
TGL [39] points out the necessity of a hybrid CPU-GPU data layout provides an explanation for the intra-batch information loss issue.
as shown in Figure 3, which leverages large CPU main memory for Typically, with the increase in batch size under the traditional batch-
input data preservation during the training process. Specifically, all ing scheme, the model computation efficiency is boosted while the
the input data are loaded from the secondary storage to the CPU predictive accuracy can be significantly degraded. Corresponding
main memory in an one-shot manner right before the starting of the results can be seen in Section 5.4 later. This calls for an approach
training. Then, the input data including the input dynamic graph, to quantify the information loss of batches, and a new design of
node state vectors, node features, and edge features are maintained the batching scheme, which can mitigate the information loss issue,

1063
 𝑡! 𝑡" 𝑡#
1 1 1
Embeddings

𝑥! 𝑠! 𝑥! 𝑠! 𝑥! 𝑠!

Initial features State vectors

𝑥! 𝑠!
𝑥" 𝑠" (a) (b)
𝑥# 𝑠#
𝑥$ 𝑠$
Figure 5: The sampling results (batch_size=600; 𝑘=10) on (a)
Wikipedia and (b) Reddit datasets [15]. The X-axis denotes
Figure 4: An illustration of data access pattern in T-GNN.
the number of batches in an epoch, and the Y-axis denotes
the number of data IDs. łoriginalž indicates the total data
while using possibly large batches for offline T-GNN training to IDs based on the sampling result, while łuniquež represents
achieve higher model computation efficiency. the unique data IDs in the sampling result.

Example 1. consider the two interactions (𝑣 4 , 𝑣 2 , 𝑒 42 (𝑡 5 ), 𝑡 5 ) and

(𝑣 4 , 𝑣 5 , 𝑒 45 (𝑡 6 ), 𝑡 6 ) of Batch 3 in Figure 1. As they are included in the
are selected three times on CPU and transferred altogether to GPU.
same batch and processed simultaneously, they can be perceived to
But actually, 𝑥 1 and 𝑠 1 can be only transferred once, since the same
be arriving at the same time. Note that 𝑣 4 occurs in both of these
input data are required to generate different embeddings.
interactions. Ideally, T-GNN would update the state vector of 𝑣 4 twice
on 𝑡 5 and 𝑡 6 . However, when performing the state vector update for 𝑣 4
in these two interactions within the same batch, the same past state 4 THE ETC FRAMEWORK
vector of 𝑣 4 is utilized. Therefore, when performing the state vector
updates for 𝑣 4 on 𝑡 6 , it does not leverage the updated state vector of In this section, we present ETC, a generic framework tailored for
𝑣 4 by the interaction (𝑣 4 , 𝑣 2 , 𝑒 42 (𝑡 5 ), 𝑡 5 ), which indicates that such efficient T-GNN training over large-scale dynamic graphs, which
interaction is cast away from the viewpoint of node 𝑣 4 on 𝑡 6 . resolves the two efficiency bottlenecks discussed in Section 3. The
optimizations in ETC reside in the batch split preprocessing stage
3.2 High Input Data Access and the input data access stage, which are orthogonal to existing
T-GNN training frameworks [18, 19, 39]. In the preprocessing stage
As shown in Figure 1, input data access is the major efficiency bot-
of T-GNN training (Section 4.1), we present an information-loss-
tleneck (around 60% of the overall training time) of T-GNN training
bounded batching scheme, which forms sizeable training batches to
on large-scale dynamic graphs. When conducting input data ac-
enhance model computation efficiency while restricting the possible
cess, the conventional procedure [18, 19, 39] involves selecting and
information loss to preserve the effectiveness of the underlying
pulling all the required input data directly based on the sampling
T-GNN models. To address the tremendous input data access costs
result. It begins by creating an access list that is identical to the
(Section 4.2), we present a novel three-step data access policy to
sampled data IDs by the temporal neighbor sampler. Subsequently,
cut down the redundant data access volume. Also, we incorporate
the corresponding data are transferred from the CPU main memory
an inter-batch pipeline mechanism in ETC, which parallelizes the
to the GPU based on this access list. Despite the straightforward-
input data access and the model computation to further hide the
ness of the conventional data access approach, it overlooks the data
input data access costs.
access pattern in T-GNN training, which can lead to redundant
data transfer. A crucial observation of the data access pattern in
T-GNN training is that: within a given batch, the same nodes can
4.1 Information-loss-bounded Batching Scheme
occur in various interactions with different timestamps. Even though In contrast to the traditional batching scheme as discussed in Sec-
the T-GNN model would create distinct state vectors and embeddings tion 3.1, ETC’s batching scheme successfully increases the batch size
for these same nodes with different timestamps, they all require ac- while effectively limiting the impact of information loss. As a result,
cessing the same input node features and past state vectors. Example our approach significantly improves the efficiency of model compu-
2 provides an illustration for such a data access pattern. In practice, tation without compromising model performance, surpassing the
such redundancy can be overwhelming as shown in Figure 5. The limitation of the conventional batching scheme.
same nodes are repeatedly accessed, which can lead to redundant Information Loss Qunatification. To quantify the information
data transfer taking up over 80% of the total data transfer volume. loss of each batch, we define a novel information loss score 𝛽 (𝐵𝑖 )
for a given batch 𝐵𝑖 as follows:
Example 2. In Figure 4, node 𝑣 1 occurs at timestamp 𝑡𝑎 , 𝑡𝑏 , and ∑︂
𝑡𝑐 respectively in a given batch. Though they would have different 𝛽 (𝐵𝑖 ) = 𝛽 (𝑣, 𝐵𝑖 ), (6)
embeddings generated by T-GNN due to different timestamps, the 𝑣 ∈𝑁𝑖
same initial feature 𝑥 1 and the same past state vector 𝑠 1 are accessed
|︁ |︁ (︁|︁
𝛽 (𝑣, 𝐵𝑖 ) = |︁{𝛼 (𝑡)|𝛼 (𝑡) ∈ 𝐵𝑖 , 𝑣 ∈ 𝛼 (𝑡)}|︁ − 1 |︁{𝛼 (𝑡)|𝛼 (𝑡) ∈ 𝐵𝑖 ,
and fed to T-GNN for computation. Under the conventional data |︁ )︁
access policy, there exists redundant data access such that 𝑥 1 and 𝑠 1 𝑣 ∈ 𝛼 (𝑡)}|︁ > 0 . (7)

1064
𝑁𝑖 is the node set derived from 𝐵𝑖 . Eq.7 quantifies the gap between Algorithm 1 Single-pass Batch Split Algorithm.
the actual update times and the ideal update times (single interac- Input: Dynamic graph G; information loss threshold 𝜀.
tion per batch) for a given node 𝑣. Then Eq.6 shows the information Output: Batches 𝐵 1 , 𝐵 2 , ..., 𝐵𝐾 .
loss score of a given batch, which sums up the information loss 1: Initialize an update counter: 𝐶𝑢 ← 0;
score of each node appearing in 𝐵𝑖 . Based on Eq.6 and Eq.7, we can 2: Initialize batch ID: 𝑖 ← 0;
also derive the following equivalent formulation for the information 3: Initialize an empty node set: 𝑁 ← { };
loss score of a target batch 𝐵𝑖 : 4: Initialize an empty batch: 𝐵𝑖 ← { };
|︁ |︁ |︁ |︁
𝛽 (𝐵𝑖 ) = 2|︁𝐵𝑖 |︁ − |︁𝑁𝑖 |︁. (8) 5: for 𝛼 (𝑡) ∈ G do ⊲ Iterate over the interactions sequentially.
6: 𝐶𝑢 ← 𝐶𝑢 + 2
Problem Formulation. Generally, given an input dynamic
7: for 𝑣 ∈ 𝛼 (𝑡) do
graph, we would like to split it into multiple batches for T-GNN
8: 𝑁 ← 𝑁 ∪ {𝑣 }
training. The optimization goal is about minimizing the total num-
9: end for
ber of batches required for the training process. Since the total
10: 𝛽 (𝐵𝑖 ) ← 𝐶𝑢 − |𝑁 |
number of interactions in an input dynamic graph is fixed, mini-
11: if 𝛽 (𝐵𝑖 ) ≤ 𝜀 then ⊲ Stick to the current batch.
mizing the total number of batches is equivalent to enlarging the
12: 𝐵𝑖 ← 𝐵𝑖 ∪ {𝛼 (𝑡)}
sizes of batches. Also, an information loss constraint is required for
13: else ⊲ State a new batch.
each batch, such that no batch would incur excessive information
14: 𝑖 ←𝑖 +1
loss. We formally define the batch split problem as follows.
15: 𝐶𝑢 ← 0
Definition 2 (Batch Split Problem for T-GNN Training). 16: 𝐵𝑖 ← {𝛼 (𝑡)}
Given all the interactions G = {𝛼 (𝑡 1 ), 𝛼 (𝑡 2 ), ..., 𝛼 (𝑡𝑒 )}, split them 17: 𝑁 ← {𝑣 ∈ 𝛼 (𝑡)}
into K batches 𝐵 1, 𝐵 2, ..., 𝐵𝐾 . Each batch contains a set of continuous 18: end if
𝑞−1
interactions such that 𝐵𝑖 = ∪𝑙=𝑝 {𝛼 (𝑡𝑙 )}, 𝑝 < 𝑞, ∀𝑖. Each batch is 19: end for
associated with an information loss score 𝛽 (·). We aim to find a batch
split 𝑓 (G) = {𝐵 1, 𝐵 2, ..., 𝐵𝐾 }, such that:
should be placed in the current batch or a new batch, its time
𝑚𝑖𝑛 𝐾 complexity is O (|𝐸|), where |𝐸| represents the total number of
𝑓
interactions in the given dynamic graph.
𝑠.𝑡 . 𝛽 (𝐵𝑖 ) ≤ 𝜀, ∀𝑖, (9)
Theoretical Analysis. We present a theoretical analysis of the
𝐵𝑖 ∩ 𝐵 𝑗 = ∅, 𝑖 ≠ 𝑗, ∀(𝑖, 𝑗), (10) proposed single-pass batch split algorithm. Despite the simplicity
𝐾
∪𝑖=1 𝐵𝑖 = G, (11) of Algorithm 1, we can prove that its output is an optimal solution
to the batch split problem. To establish this claim, we begin by
𝑡𝑚 < 𝑡𝑛 , ∀𝛼 (𝑡𝑚 ) ∈ 𝐵𝑖 , ∀𝛼 (𝑡𝑛 ) ∈ 𝐵 𝑗 , 𝑖 < 𝑗 (12)
proving the following two useful lemmas.
Eq. 9 indicates that the information loss score of each batch
Lemma 1. Given a batch 𝐵(𝑝, 𝑞), which starts at the p-th interac-
cannot be larger than a threshold 𝜀. Eq. 10 is a disjoint constraint,
tion and ends right before the q-th interaction, we have:
which requires that there is no overlap among all the batches. Eq.
11 is a union constraint, which means that the union of all the 𝛽 (𝐵(𝑝, 𝑞)) ≤ 𝛽 (𝐵(𝑝, 𝑞 + 𝑐)), (13)
batches is the given input dynamic graph G. As for Eq. 12, it is 𝛽 (𝐵(𝑝 − 𝑐, 𝑞)) ≤ 𝛽 (𝐵(𝑝, 𝑞)), (14)
a temporal order constraint, which ensures that the batch split
generated would not break the intrinsic order of interactions in the where c is a constant integer.
given dynamic graph. Proof. For the batches 𝐵(𝑝, 𝑞) and 𝐵(𝑝, 𝑞 + 𝑐), denote the node
Single-pass Batching Algorithm. The batch split problem sets in them as 𝑁 (𝑝, 𝑞) and 𝑁 (𝑝, 𝑞 + 𝑐) respectively. Based on the
is a variant of the known bin packing problem [4] with an addi- definition of the information loss score as described in Eq.8, we
tional temporal order constraint. To solve the batch split problem, know that:
we develop Algorithm 1, which is an efficient single-pass batch
split algorithm. We further theoretically prove that the proposed 𝛽 (𝐵(𝑝, 𝑞)) = 2(𝑞 − 𝑝) − |𝑁 (𝑝, 𝑞)|,
algorithm is an optimal solution to the batch split problem. 𝛽 (𝐵(𝑝, 𝑞 + 𝑐)) = 2(𝑞 + 𝑐 − 𝑝) − |𝑁 (𝑝, 𝑞 + 𝑐)|.
Algorithm 1 begins by initializing an empty first batch, an empty Then we can derive:
node set, and a counter for update times (Lines 1-4). It then proceeds
with a sequential scan of all the interactions (Line 5). During the 𝛽 (𝐵(𝑝, 𝑞 + 𝑐)) − 𝛽 (𝐵(𝑝, 𝑞)) = 2𝑐 − (|𝑁 (𝑝, 𝑞 + 𝑐)| − |𝑁 (𝑝, 𝑞)|).
scan, each target interaction is added to the current batch, followed We know that 𝑁 (𝑝, 𝑞) ⊆ 𝑁 (𝑝, 𝑞 + 𝑐). Also, 𝐵(𝑝, 𝑞 + 𝑐) can be seen
by the calculation of the information loss score for that batch (Lines as 𝐵(𝑝, 𝑞) adding 𝑐 more interactions right after the last interaction
6-10). If adding the interaction to the current batch does not violate it contains. In this way, 𝑐 more interactions bring at most 2𝑐 more
the information loss constraint, it is retained in the current batch new nodes to 𝑁 (𝑝, 𝑞). Therefore, we know that:
(Lines 11-12). However, if adding the interaction would violate the
information loss constraint, a new batch is created that includes the |𝑁 (𝑝, 𝑞 + 𝑐)| − |𝑁 (𝑝, 𝑞)| ≤ 2𝑐,
interaction (Lines 13-17). Since Algorithm 1 performs a single scan which ends the proof for Eq.13. The proof for Eq.14 can be done in
of all the interactions and decides whether each scanned interaction a similar fashion. □

1065
 Lemma 1 shows the non-decreasing characteristic of the infor- CPU
mation loss function. For a given batch 𝐵, if adding new interactions ②
IDs Data
into it, its information loss score 𝛽 (𝐵) would only either increase 1
or remain the same. 2
Sampled Data IDs ① Access List
1
[1,1,1,5,5] [1, 5]
Lemma 2. An optimal solution (𝑂𝑃𝑇 ) to the batch split problem 3
Mapping 5
generates 𝐾 ∗ batches, and the output of Algorithm 1 (𝐴𝐿𝐺1) generates 4
[0,0,0,1,1]
𝐾 batches. Denote the index of the last interaction in a batch as 𝑒 (·). 5

Then for all 0 < 𝑖 ≤ 𝐾 ∗ , we have 𝑒 (𝑖, 𝑂𝑃𝑇 ) ≤ 𝑒 (𝑖, 𝐴𝐿𝐺1). ② ②

Proof. We can prove the lemma above by induction. The base GPU
Data for Training
case is when 𝑖 = 1, and the first batch produced by both 𝑂𝑃𝑇 and 1
𝐴𝐿𝐺1 starts at the first interaction of the input dynamic graph. We ③
1 1
know that 𝐴𝐿𝐺1 would not stop adding the subsequent interactions
5
to the first batch until the information loss constraint is violated. If 5
5
the first batch produced by 𝑂𝑃𝑇 has more interactions than those
5
in the first batch produced by 𝐴𝐿𝐺1, the information loss constraint
would be violated. Therefore, we have 𝑒 (1, 𝑂𝑃𝑇 ) ≤ 𝑒 (1, 𝐴𝐿𝐺1).
Assume for the 𝑖 − 𝑡ℎ batch, 𝑒 (𝑖, 𝑂𝑃𝑇 ) ≤ 𝑒 (𝑖, 𝐴𝐿𝐺1). Then we Figure 6: An illustration of the three-step data access policy.
need to prove that for the 𝑖 + 1 − 𝑡ℎ batch, 𝑒 (𝑖 + 1, 𝑂𝑃𝑇 ) ≤ 𝑒 (𝑖 +
1, 𝐴𝐿𝐺1) still holds.
Case1: 𝑒 (𝑖 +1, 𝑂𝑃𝑇 ) ≤ 𝑒 (𝑖, 𝐴𝐿𝐺1). Based on 𝐴𝐿𝐺1, we can know the data access volume, which significantly cuts down the cost
that 𝑒 (𝑖, 𝐴𝐿𝐺1) ≤ 𝑒 (𝑖 + 1, 𝐴𝐿𝐺1). Then based on the assumption, of input data access. Besides, to reduce the additional overhead
we get 𝑒 (𝑖 + 1, 𝑂𝑃𝑇 ) ≤ 𝑒 (𝑖 + 1, 𝐴𝐿𝐺1). incurred by the three-step data access policy, ETC adopts an inter-
Case2: 𝑒 (𝑖 + 1, 𝑂𝑃𝑇 ) > 𝑒 (𝑖, 𝐴𝐿𝐺1). By the information loss con- batch pipeline mechanism, which decouples the input data access
straint, we know that the 𝑖 + 1 − 𝑡ℎ batch produced by 𝑂𝑃𝑇 would from the model computation. It assists in further reducing the cost
not violate the information loss constraint, such that: of input data access and improving the overall training efficiency.

𝛽 (𝑒 (𝑖, 𝑂𝑃𝑇 ) + 1, 𝑒 (𝑖 + 1, 𝑂𝑃𝑇 )) ≤ 𝜀. 4.2.1 Three-step Data Access Policy. Motivated by the observation
as illustrated in Section 3.2, ETC leverages a novel three-step data
Then based on Lemma 1, we can obtain that: access policy named Supra to efficiently conduct the input data
𝛽 (𝑒 (𝑖, 𝐴𝐿𝐺1) + 1, 𝑒 (𝑖 + 1, 𝑂𝑃𝑇 )) ≤ 𝛽 (𝑒 (𝑖, 𝑂𝑃𝑇 ) + 1, 𝑒 (𝑖 + 1, 𝑂𝑃𝑇 )). access. Figure 6 provides an illustrative example. In the first step,
Supra performs data ID transformation. Starting with the original
In this way, we can know that if the 𝑖 + 1 − 𝑡ℎ batch produced by
data IDs obtained from the sampling result, an access list is cre-
𝐴𝐿𝐺1 ends at 𝑒 (𝑖 + 1, 𝑂𝑃𝑇 ), the information loss constraint would
ated, containing only unique data IDs. Besides, Supra maintains a
not be violated. In other words, the 𝑖 + 1 − 𝑡ℎ batch produced by
mapping between the original data IDs and the unique data IDs.
𝐴𝐿𝐺1 at least ends at 𝑒 (𝑖 +1, 𝑂𝑃𝑇 ). Therefore, we get 𝑒 (𝑖 +1, 𝑂𝑃𝑇 ) ≤
In the second step, utilizing the access list generated in the first
𝑒 (𝑖 + 1, 𝐴𝐿𝐺1). □
step, the corresponding data (node state vectors, node features,
Based on Lemma 1 and Lemma 2, we provide the following and edge features) are selected on CPU and then transferred from
Theorem 1. CPU to GPU. Finally, in the third step, once the unique data has
been transferred to GPU, the originally required input data can be
Theorem 1. The output of Algorithm 1 is an optimal solution to reconstructed using the mapping generated in the first step.
the batch split problem that minimizes the number of batches under Data Transfer Volume Analysis. With the conventional data
the information loss score constraint as described in Definition 2. access policy, the total resultant data transfer volume for a batch
Proof. Denote the number of interactions in the input dynamic is O (𝑄 · 𝑑), where 𝑄 represents the number of data IDs in the
graph as |𝐸|. For the batch split problem, assume the optimal so- batch, and 𝑑 is the dimension of a single data point (e.g., dimension
lution (𝑂𝑃𝑇 ) produces 𝐾 ∗ batches, while Algorithm 1 (𝐴𝐿𝐺1) pro- of a node feature). By contrast, with the utilization of Supra, the
duces 𝐾 batches, such that 𝐾 ∗ ≤ 𝐾. Since 𝑂𝑃𝑇 splits all the in- data transfer volume is reduced to O (𝑅 · 𝑑 + 𝑄), where 𝑅 is the
teractions of the input dynamic graph into 𝐾 ∗ batches, we have number of unique data IDs in the batch. Additionally, an extra term
𝑒 (𝐾 ∗, 𝑂𝑃𝑇 ) = |𝐸|. Then based on Lemma 2, we know 𝑒 (𝐾 ∗, 𝑂𝑃𝑇 ) ≤ of 𝑄 accounts for transferring the ID mapping. Considering the
𝑒 (𝐾 ∗, 𝐴𝐿𝐺1). Since Algorithm 1 performs a single scan over all the data access pattern in T-GNN training, it is observed that 𝑄 can be
interactions of the input dynamic graph, we know that the algo- multiple times greater than 𝑅. Consequently, the implemented data
rithm terminates at the last interaction, which means 𝑒 (𝐾 ∗, 𝐴𝐿𝐺1) = access policy Supra can significantly reduce the total data transfer
|𝐸|. In this way, 𝐾 = 𝐾 ∗ . □ volume, thereby mitigating the heavy data transfer costs.
4.2.2 Inter-batch Pipeline. ETC is also equipped with a lightweight
4.2 Efficient Input Data Access inter-batch pipeline mechanism. While the data access policy Supra
ETC incorporates two key optimizations to efficiently conduct input in ETC boosts the input data access efficiency, the design intro-
data access. Firstly, the three-step data access policy largely shrinks duces some additional overhead. Specifically, the first step of Supra

1066
Table 1: Summary of statistics of the dynamic graphs. |𝑉 | and listener-music interactions. Wiki-Talk [3] and Stack-Overflow [1]
|𝐸| represent the number of nodes and edges. 𝑑 𝑣 and 𝑑𝑒 de- record user-user interactions from the corresponding websites.
note the dimension of node features and edge features. 𝛼 and GDELT [39] is a near billion-scale dynamic temporal knowledge
𝛽 respectively represents the average degree and diameter. graph, which originates from the Event Database in GDELT 2.0 [16].
Θ denotes the average update distance of all nodes. Specifi- As for the data splits, we adopt the same data split on LastFM, Wiki-
cally, for a particular node 𝑣, its average update distance 𝜃 𝑣 is Talk, and Stack-Overflow as used in [19, 27, 33], which chronologi-
defined as the average number of interactions between two cally splits the input graph into the training set (70%), the validation
consecutive updates among all updates of node 𝑣. Then the set (15%), and the test set (15%). On GDELT, we also use the same
∑︁
average update distance for all nodes is Θ = 𝑣 ∈𝑉 𝜃 𝑣 /|𝑉 |. data split in [39], which uses the interactions before 2019, in 2019,
and in 2020 as training set, validation set, and test set, respectively.
Dataset |𝑉 | |𝐸| 𝑑𝑣 𝑑𝑒 𝛼 𝛽 Θ Backbone Models. To verify the effectiveness of ETC frame-
LastFM 2K 1.3M 128 128 1306 1 2873 work, we use three representative T-GNNs as the backbone models.
Wiki-Talk 1.1M 7.8M 172 172 14 11 458149
Stack-Overflow 2.6M 63.4M 172 172 49 13 1354646 • TGAT [33] uses random Fourier features to encode the time
GDELT 17K 191.3M 413 186 22934 7 4876113 information and adopts the attention mechanism, which
imitates the message passing scheme in static GNNs.
• TGN [27] is a general T-GNN framework, which includes
involves searching for unique data IDs and generating mappings several existing T-GNN models [15, 28, 33] as its special
between the unique data IDs and the original data IDs in every train- cases. It dynamically maintains state vectors for nodes in
ing batch. This operation has a time complexity of 𝑂 (𝑄), where the input dynamic graphs to capture the temporal informa-
𝑄 represents the number of data IDs in a batch. However, when tion.
training on a large-scale dynamic graph, a substantial number of • APAN [31] is an asynchronous and attention-based T-GNN
batches are required. The accumulated costs of this operation can model, which decouples model computation and message
become massive in practice, limiting the potential efficiency gains propagation.
offered by Supra. Moreover, in cases where the cost of ID transfor-
mation outweighs the reduction in data transfer costs, the effect of As for the other T-GNN models [13, 15, 32], they can be thought
Supra may be neutralized or even counterproductive. of as extensions on top of the above representative T-GNN models
Under the standard execution order in T-GNN training, CPU with more complex model structure designs [6]. Since the training
and GPU are utilized sequentially. Specifically, CPU is responsible procedures for these T-GNN models are similar to the ones for the
for conducting temporal neighbor sampling and processing input three selected representative T-GNNs, we omit the results for these
data access. When the model computation of a training batch is T-GNN models in the main experiments.
performed by T-GNN on GPU, CPU would remain relatively idle Baseline Frameworks. To verify the efficiency of ETC, we uti-
and underutilized. Recognizing this, we have made a slight adjust- lize three state-of-the-art T-GNN training frameworks as baselines.
ment to the T-GNN training by workload decoupling. While the • TGL [39] is a generic training framework that is applicable
model training is carried out on GPU for a given batch, the tem- to a wide range of T-GNN models. It is equipped with an
poral neighbor sampling and input data access for the subsequent efficient parallel sampler that resolves the high complexity
batch are concurrently performed on CPU. This modification well issue in temporal neighbor sampling.
reduce the additional costs associated with Supra. Although this • Orca [18] focuses on resolving the model computation bot-
pipeline mechanism is lightweight, it effectively facilitates a further tleneck in T-GNN training. It leverages a dynamic caching
reduction on the data access overhead. mechanism and utilizes historical representations to avoid
substantial computation workload. Also, it incorporates a
5 EXPERIMENTS gradient blocking strategy to improve the generalization
5.1 Experiment Setups ability of T-GNN models.
• Zebra [19] also aims at reducing the model computation
Implementations. We implement ETC based on TGL [39] and
costs in T-GNN training. It fundamentally changes the ag-
DGL [30], using Pytorch [24] as the backend deep learning frame-
gregation rule of underlying T-GNN by only aggregating
work for the T-GNN model training phase. We adopt the efficient
the most influential temporal neighbors.
parallel temporal sampler in TGL with a CSR-based data structure
for rapid access to temporal neighbors. We utilize DGL to generate ETC and TGL are generic frameworks, which do not change the
the Message Flow Graph (MFG) for each batch, which contains the functionality of backbone T-GNNs. Their optimizations reside in
sampled dynamic subgraph as well as the associated input data. For managing the data during T-GNN training such as faster sampling
the implementation of the three-step data access policy, we utilize and data access. While Orca and Zebra resort to modifying the
NumPy [12] for a fast search of unique data IDs and the generation model structure design of T-GNN for better model computation
of the ID mapping. For the inter-batch pipeline, we implement it efficiency and model effectiveness. Note that Orca and Zebra can
using Python threading. only be generalized to synchronous T-GNNs [15, 27, 33], and they
Datasets. As summarized in Table 1, we use four real-world only implement the classic TGN [27] model. Therefore, we present
large-scale dynamic graphs with millions of interactions that exhibit their results on their currently supported TGN model in the main
distinct graph characteristics. LastFM [15] consists of one-month experiments.

1067
Table 2: Comparison results of T-GNN training frameworks. Time refers to per-epoch execution time (s). The best average
precision (%) and the fastest execution time are marked in bold. łTLEž indicates the time limit exceed such that the training of
one epoch cannot finish within 12 hours.

Dataset Model Framework AP(%) Time(s) Dataset Model Framework AP(%) Time(s)
Orca 80.11 22.0 (1.6×) Orca 97.64 12428.7 (25.7×)
Zebra 82.44 76.0 (5.4×) Zebra 97.57 30167.4 (62.4×)
TGN TGN
TGL 80.92 29.7 (2.1×) TGL 83.32 1504.4 (3.1×)
ETC 80.79 14.1 ETC 86.10 483.5
LastFM Stack-Overflow
TGL 67.11 8.5 (2.4×) TGL 87.47 339.4 (1.6×)
TGAT TGAT
ETC 67.58 3.6 ETC 87.55 215.9
TGL 70.05 19.1 (1.8×) TGL 63.10 1696.3 (1.8×)
APAN APAN
ETC 69.79 10.8 ETC 66.42 937.4
Orca 96.05 343.3 (5.8×) Orca TLE TLE
Zebra 96.08 1029.5 (17.5×) Zebra TLE TLE
TGN TGN
TGL 92.94 135.5 (2.3×) TGL 98.08 4001.5 (3.3×)
ETC 93.41 58.9 ETC 98.46 1222.4
Wiki-Talk GDELT
TGL 86.10 40.7 (2.0×) TGL 98.08 1338.2 (2.2×)
TGAT TGAT
ETC 86.08 20.1 ETC 98.07 619.9
TGL 86.73 160.4 (2.0×) TGL 96.62 3302.9 (2.5×)
APAN APAN
ETC 88.11 81.8 ETC 96.93 1304.5

Training Configurations. We focus on the link prediction task, 5.2 Main Results
which is widely adopted in previous works [19, 27, 31ś33, 39]. Such We first provide an overall comparison between ETC and baseline
a task aims at predicting whether there exist interactions between frameworks. We apply ETC and the baseline frameworks to train
given pairs of nodes in the future timestamps. Since the original the same T-GNNs on different datasets. The results are summarized
datasets only contain positive interactions between nodes, an equal in Table 2.
number of false links are sampled. As for the evaluation metric, we Efficiency of ETC. We notice that compared to the baseline
utilize average precision (AP) of models on the test set as in previous T-GNN training frameworks, ETC is able to further provide 1.6×
works [19, 27, 31, 39]. For the sampling strategy, we utilize top-𝑘 ∼ 62.4× training speedup for different T-GNN models, and the
recent neighbor sampling [27] for all the underlying T-GNN models achieved speedup is over 2× in most cases. Compared with Zebra,
with k set as 10, since it is shown in previous works [19, 27] that ETC exhibits 5.4× ∼ 62.4× training speedup. Zebra utilizes the con-
the top-𝑘 recent neighbor sampling can provide better predictive ventional data access policy and suffers from prohibitive data access
performance compared to the other sampling strategies. For TGN costs. In contrast, ETC is able to remove a huge amount of redun-
and APAN, we set the base batch size on LastFM, Wiki-Talk, Stack- dant data access thanks to its data access policy Supra. Compared
Overflow, and GDELT as 1000, 1500, 2000, and 2500 respectively. For with Orca, ETC shows 1.6× ∼ 25.7× efficiency gain. Orca leverages
a fair comparison, we first calculate the upper bound of information a dynamic caching mechanism for the intermediate embeddings,
loss score for all batches generated by the conventional batch split, which not only avoids certain computation workload, but also re-
and then use the derived upper bound as the threshold for our duces the data access volume in an indirect way. Nonetheless, it
proposed batch split algorithm. In this way, the two approaches falls short of reducing a large amount of redundant data access.
are bounded by the same extent of information loss. The resultant Compared with the next best T-GNN training framework TGL in
average batch sizes by ETC’s batch split algorithm on four datasets terms of efficiency, ETC is able to provide 1.6× ∼ 3.3× faster training
are 1180, 2180, 2938, and 2635 respectively. For TGAT model without execution. Though the parallel sampler incorporated in TGL is able
the node memory module, the large batch size does not cause the to resolve the high time complexity of sampling, it still overlooks
information loss issue. Therefore, the batch split algorithm in ETC the overwhelming data access costs.
is not adopted for TGAT and we fix the batch size to be 5000 for Effectiveness of ETC. By comparing the predictive results by
TGAT on all the datasets. We train all the models on all the datasets ETC and the other generic T-GNN training framework TGL, we can
for five epochs. For the other training related hyper-parameters, see that ETC is able to well-maintain the effectiveness of different T-
we do not tune and fix them the same as in TGL [39] to verify the GNN models, as there is no prominent accuracy degradation caused
robustness of our framework. All the experiments are done on a by ETC framework. We also notice that the other two frameworks
server with 96 CPU cores and 256 GB main memory. The model Orca and Zebra can present a large accuracy improvement for
training is done on a single RTX 3090 (24GB). All the experiments TGN. This is because these two frameworks modify the model
are repeated three times and the mean results are reported. structure in TGN, which can also improve the effectiveness and
generalization ability of TGN. By contrast, ETC and TGL do not
contain the optimizations in TGN structure design and utilize the

1068
 (a) LastFM (b) Wiki-Talk (a) LastFM (b) Wiki-Talk

(c) Stack-Overflow (d) GDELT

(c) Stack-Overflow (d) GDELT

Figure 9: Per-epoch data preparation time comparison be-

Figure 7: Per-epoch model computation time of TGN and
tween ETC and TGL.
APAN models by ETC and TGL.

Table 3: Per-epoch data access time (s) comparison between

TGL and ETC.

LastFM Wiki-Talk Stack-Overflow GDELT

TGL 14.2 (4.9×) 66.3 (4.2×) 906.1 (3.9×) 2599.6 (6.1×)
ETC 2.9 15.9 233.3 427.5

batch sizes, thus increasing GPU utilization. In this way, the model
computation efficiency can be enhanced. We compare the model
computation time of TGN and APAN under ETC and TGL imple-
mentations in Figure 7. ETC is able to provide 1.3× faster model
Figure 8: Comparison of normalized time between the batch computation on average than TGL for these models, which verifies
split preprocessing and the training. the effectiveness of our batch split algorithm. We also evaluate the
cost of the batch split algorithm on different datasets. As shown
in Figure 8, the batch split algorithm does not incur a heavy pre-
vanilla implementation of TGN. In fact, the techniques incorporated processing cost and it merely accounts for around 2.5% of the total
in ETC are orthogonal to those in Orca and Zebra. ETC as a versatile end-to-end training time.
T-GNN training framework, allows the incorporation of the model- Improved Data Preparation Efficiency. The three-step data
side optimizations to improve the effectiveness of the underlying access policy Supra, as well as the inter-batch pipeline mechanism,
T-GNN. In practice, as we train the Orca’s version of the TGN helps reduce the data preparation costs in training existing T-GNNs
model using ETC, we can achieve prominent enhancement on the over large-scale dynamic graphs. Figure 9 summarizes the data
predictive performance of TGN. Due to the page limit, we put the preparation costs in training existing T-GNN models with TGL and
corresponding results in our technical report [2]. ETC frameworks. ETC can provide up to 5.5× faster data preparation
(3.3× on average) compared with using TGL.
5.3 Analysis of ETC Framework The Effect of Three-step Data Access Policy Supra. We con-
In this section, we conduct one to one comparison between the duct experiments on all the datasets using TGN [27] as an example
proposed ETC and the baseline TGL. Since they are both generic to verify the effectiveness of the proposed three-step data access
frameworks that support a wide range of T-GNN variants, such com- policy Supra. The results with the other T-GNN models are simi-
parison helps to investigate the impact of different optimizations lar. Table 3 shows that Supra largely reduces the data access costs
incorporated in ETC. in data preparation. ETC is able to achieve 4.9×, 4.2×, 3.9×, and
Improved Model Computation Efficiency. The batch split 6.1× faster data access compared with TGL. We notice that for
algorithm in ETC enables training existing T-GNNs with larger denser dynamic graphs, the higher data access efficiency can be

1069
Table 4: Per-epoch time (s) comparison for three steps of the
data access policy Supra.

LastFM Wiki-Talk Stack-Overflow GDELT

Step I 2.1 10.3 137.3 276.2
Step II 2.9 15.9 233.3 427.5
Step III 0.7 2.5 22.2 60.5
(a) Average Precision (b) Per-epoch Computation Time
Table 5: Per-epoch time (s) comparison of ETC with and with-
out the inter-batch pipeline. Figure 10: Comparison of (a) average precision and (b) per-
epoch computation time between the traditional and ETC’s
LastFM Wiki-Talk Stack-Overflow GDELT batching varying the information loss score upper bound on
w/o pipeline 16.9 (1.2×) 75.7 (1.3×) 783.6 (1.6×) 1850.0 (1.5×)
Wiki-Talk dataset.
w pipeline 14.1 58.9 483.5 1222.4

Table 6: Comparison of batch size by the traditional and ETC’s

batching varying information loss score upper bound.

Method Batch Size

Traditional 1000 1500 2000 2500 3000 3500 4000 4500 5000
ETC’s 1442 2118 2771 3399 4033 4631 5243 5860 6480

(a) LastFM (b) Wiki-Talk

enjoyed. Specifically, on much denser datasets LastFM and GDELT,
the extent of data access time reduction is more evident than that Figure 11: The effect of different values of threshold 𝜀. X-axis
on Wiki-Talk and Stack-Overflow. This is reasonable since dense denotes the per-epoch model computation time (s) and Y-axis
dynamic graphs are likely to incur more repeated data IDs in the denotes the average precision (%). Specific threshold values
neighbor sampling results. Table 4 evaluates the cost of each in- are represented by dots with numbers next to them.
dividual step of Supra. It is observed that the second step, which
transfers the unique input data from CPU to GPU, is the most time-
consuming part. Besides the second step, the first step also causes of information loss score by the traditional batching scheme, and
a substantial overhead, which is for the searching of unique data make them the input for ETC’s batching scheme to ensure the same
IDs and generating reverse mapping in each batch. While for the constraint of information loss. Figure 10 shows the comparison
last step, such cost of reconstructing input data on GPU does not results varying the information loss score upper bound on Wiki-
incur much overhead. Talk. We can see that both approaches exhibit similar predictive
The Effect of the Inter-batch Pipeline Mechanism. We also performance when subjected to the same extent of information loss
evaluate the effect of the lightweight inter-batch pipeline mecha- in their respective batches. Nonetheless, ETC’s batching scheme
nism incorporated in ETC. We conduct experiments with TGN as showcased higher model computation efficiency under the same
the backbone model on all the datasets, and compare the training condition. This improvement is resulted from larger (average) batch
efficiency of ETC with or without the pipeline mechanism. The size achieved by ETC’s batching scheme as shown in Table 6.
comparison result is shown in Table 5. We see that the pipeline Impact of Threshold Value & Guidance for Practitioners.
mechanism helps ETC further achieve 1.2× ∼ 1.6× faster training We further perform a case study to investigate the impact of thresh-
speedup compared with ETC without such a pipeline mechanism. old 𝜀 and provide corresponding guidance for practitioners. Specif-
ically, we conduct experiments varying the 𝜀 value from 500 to
5.4 Analysis on the Batching Scheme 8000 with a step size of 500 on LastFM and Wiki-Talk datasets,
In this section, we conduct case studies with TGN [27] as the back- which exhibit quite distinct graph characteristics. We observe the
bone model, which (1) compares ETC’s batching scheme with the following findings: (1) Increasing the threshold value improves the
traditional one varying the information loss score upper bound, model computational efficiency of T-GNNs. However, we notice
and (2) analyzes the impact of different threshold values by ETC. an effect of diminishing marginal utility when the threshold be-
Due to the page limit, we report a few representative results that comes sufficiently large. Further increasing the threshold value
are useful for discussion. Please see our technical report [2] for beyond a certain point only results in minimal improvements in
comprehensive comparison results. model computational efficiency. (2) Interestingly, lower threshold
Varying Information Loss Score Upper Bound. As the input values do not necessarily guarantee better predictive performance.
for the traditional batching scheme is the pre-determined batch size, It is possible that the original dynamic graphs may contain some
we set a batch size range from 1000 to 5000 with the step as 500 noisy interactions, which may result in an overfitted model [26].
for the traditional batching scheme, and calculate the upper bound Therefore, we recommend a reasonably large lower limit for the

1070
threshold value (e.g., over 1000) to mitigate the overfitting issue based GNNs on DTDGs. Chakaravarthy et al. [5] parallelize the
thus improving the generation ability of the underlying T-GNN process of different snapshots of DTDGs to speed up the existing
models on the test set. On the other hand, as the threshold value snapshot-based GNNs. TGL [39] is a generic framework for scaling
increases to a certain point, the model performance can degrade existing T-GNN models on large-scale CTDGs, which is equipped
drastically due to too much information loss. (3) Besides, we can with a parallel temporal sampler to resolve the high sampling over-
see that there exists a broad range of threshold values that can head in previous implementations. Zebra [19] proposes temporal
present satisfactory runtime-accuracy tradeoffs which allow prac- personalized PageRank and performs temporal aggregation only
titioners to fine-tune the specific value based on their individual for top-k influential neighbors to improve model computation effi-
preference. For practitioners who prioritize higher model computa- ciency. Orca [18] incorporates a dynamic caching mechanism and
tion efficiency, choosing a relatively larger value within the range is utilizes historical embedding to reduce certain model computation
advisable. Conversely, those aiming for better model performance and input data access workload.
should consider a relatively smaller threshold value within the For representation learning on static graphs, some works resort
range. (4) Moreover, we also notice the upper limit of the suitable to mini-batch training to scale GNNs to large-scale static graphs
threshold range can significantly vary on two datasets. In order on single machine, which aim at faster execution of sampling
to determine such an upper limit, it is important to consider the [7, 11, 35, 36] and CPU-GPU data transfer [20, 34]. By contrast,
average update distance of the input dynamic graph (as illustrated some others utilize distributed training approach to scale existing
in Table 1). The average update distance can reflect the update graph representation learning models to large-scale static graphs,
frequency of the node state vectors for a given dynamic graph. For and propose different optimizations to reduce heavy inter-device
the input dynamic graph with a small average update distance such communication [21, 22, 25, 38, 40].
as LastFM, a small threshold value upper limit should be considered
(e.g., around 3000). Otherwise, a large threshold value upper limit 7 CONCLUSION
is recommended (e.g., around 5000).
In this paper, we present ETC, a generic framework for efficient
T-GNN training over large-scale dynamic graphs. It incorporates a
6 RELATED WORK novel batching scheme to improve model computation efficiency,
which allows T-GNN training with a large batch size while control-
Representation Learning on Dynamic Graphs. To support the
ling the information loss issue. Moreover, it removes the redundant
dynamic graph related downstream tasks, current approaches can
input data access for temporal neighbors with a novel three-step
be generally divided into two main categories, namely snapshot-
data access policy. It further decouples the input data access and the
based GNNs and T-GNNs. Snapshot-based GNNs focused on discrete-
model computation by T-GNNs using a simple yet effective pipeline
time dynamic graphs (DTDGs), which are represented by graph
mechanism. Extensive experimental results show that ETC can
snapshots captured at different time intervals. While the most recent
achieve 1.6× ∼ 62.4× faster training compared to state-of-the-art
efforts are devoted to continuous-time dynamic graphs (CTDGs). In
training frameworks for various underlying T-GNNs on multiple
real-world applications, where interactions occur at varying time
large-scale dynamic graphs. A promising future direction is to de-
granularities, T-GNNs are more suitable approaches and exhibit
sign a caching mechanism tailored for T-GNN training to further
better performance than snapshot-based GNNs.
reduce data access associated costs, which is capable of capturing
JODIE [15] is the pioneering work of T-GNNs, which updates
the data access dynamics in T-GNN training.
the node representation involved in the edges sequentially using
RNN. Dyrep [28] further takes the 2-hop neighbor information into
consideration to perform node representation update. TGAT [33] ACKNOWLEDGMENTS
follows the message passing scheme in static GNNs but incorporates Yanyan Shen’s work is supported by the National Key Research and
random Fourier features to encode the timestamp in the continuous Development Program of China (2022YFE0200500), Shanghai Mu-
interactions. TGN [27] is a comprehensive T-GNN framework that nicipal Science and Technology Major Project (2021SHZDZX0102),
encompasses previous works [15, 27, 28] as specific instances. To the Tencent Wechat Rhino-Bird Focused Research Program, and
enhance the inductive performance on unseen nodes, CAW [32] SJTU Global Strategic Partnership Fund (2021 SJTU-HKUST). Yingxia
anonymizes node identities with the frequency of node occurrences Shao’s work is supported by the National Natural Science Foun-
based on a set of sampled walks. NeurTWs [13] utilizes temporal dation of China (Nos. 62272054, 62192784), Beijing Nova Program
walks and motif structure to further improve the inductive ability. (No. 20230484319), and Xiaomi Young Talents Program. Lei Chen’s
GraphMixer [6] adopts a simplified MLP-based architecture and work is partially supported by National Science Foundation of
bypasses the temporal neighborhood aggregation. China (NSFC) under Grant No. U22B2060, the Hong Kong RGC
Training Frameworks for Efficient Representation Learn- GRF Project 16209519, CRF Project C6030-18G, C2004-21GF, AOE
ing on Graphs. Besides developing more advanced representation Project AoE/E-603/18, RIF Project R6020-19, Theme-based project
learning models on graphs, researchers in the database and system TRS T41-603/20R, China NSFC No. 61729201, Guangdong Basic
community focus more on the efficient execution of such models. and Applied Basic Research Foundation 2019B151530001, Hong
For representation learning on dynamic graphs, Li et al. [17] propose Kong ITC ITF grants MHX/078/21 and PRP/004/22FX, Microsoft
a cache-based framework to accelerate the training of static GNNs Research Asia Collaborative Research Grant, HKUST-Webank joint
on DTDGs. DynaGraph [9] leverages cached message passing and research lab grant and HKUST Global Strategic Partnership Fund
timestamp fusion mechanisms to efficiently train existing snapshot (2021 SJTU-HKUST).

1071
REFERENCES [22] Seung Won Min, Kun Wu, Sitao Huang, Mert Hidayetoğlu, Jinjun Xiong, Eiman
[1] [2023]. Stack-Overflow. [Link] Ebrahimi, Deming Chen, and Wen-mei Hwu. 2021. Large graph convolutional
[2] [2023]. The technical report. [Link] network training with GPU-oriented data communication architecture. Proceed-
[Link] ings of the VLDB Endowment 14, 11 (2021), 2087ś2100.
[3] [2023]. Wiki-Talk. [Link] [23] Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura,
[4] Korte Bernhard and Jens Vygen. 2008. Combinatorial optimization: Theory and Hiroki Kanezashi, Tim Kaler, Tao Schardl, and Charles Leiserson. 2020. Evolvegcn:
algorithms. Springer, Third Edition, 2005. (2008). Evolving graph convolutional networks for dynamic graphs. In Proceedings of
[5] Venkatesan T Chakaravarthy, Shivmaran S Pandian, Saurabh Raje, Yogish Sab- the AAAI conference on artificial intelligence, Vol. 34. 5363ś5370.
harwal, Toyotaro Suzumura, and Shashanka Ubaru. 2021. Efficient scaling of [24] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory
dynamic graph neural networks. In Proceedings of the International Conference Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019.
for High Performance Computing, Networking, Storage and Analysis. 1ś15. Pytorch: An imperative style, high-performance deep learning library. Advances
[6] Weilin Cong, Si Zhang, Jian Kang, Baichuan Yuan, Hao Wu, Xin Zhou, Hanghang in neural information processing systems 32 (2019).
[25] Jingshu Peng, Zhao Chen, Yingxia Shao, Yanyan Shen, Lei Chen, and Jiannong
Tong, and Mehrdad Mahdavi. 2023. Do We Really Need Complicated Model
Cao. 2022. Sancus: Staleness-aware communication-avoiding full-graph decen-
Architectures For Temporal Networks?. In International Conference on Learning
tralized training in large-scale graph neural networks. Proceedings of the VLDB
Representations.
Endowment 15, 9 (2022), 1937ś1950.
[7] Jialin Dong, Da Zheng, Lin F Yang, and George Karypis. 2021. Global neighbor
[26] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. 2020. DropE-
sampling for mixed CPU-GPU training on giant graphs. In Proceedings of the
dge: Towards Deep Graph Convolutional Networks on Node Classification. In
27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 289ś299.
International Conference on Learning Representations.
[8] Palash Goyal, Sujit Rokka Chhetri, and Arquimedes Canedo. 2020. dyngraph2vec:
[27] Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico
Capturing network dynamics using dynamic graph representation learning.
Monti, and Michael Bronstein. 2020. Temporal Graph Networks for Deep Learn-
Knowledge-Based Systems 187 (2020), 104816.
ing on Dynamic Graphs. In ICML 2020 Workshop on Graph Representation Learn-
[9] Mingyu Guan, Anand Padmanabha Iyer, and Taesoo Kim. 2022. DynaGraph:
ing.
dynamic graph neural networks at scale. In Proceedings of the 5th ACM SIGMOD
[28] Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha.
Joint International Workshop on Graph Data Management Experiences & Systems
2019. Dyrep: Learning representations over dynamic graphs. In International
(GRADES) and Network Data Analytics (NDA). 1ś10.
conference on learning representations.
[10] Ehsan Hajiramezanali, Arman Hasanzadeh, Krishna Narayanan, Nick Duffield,
[29] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro
Mingyuan Zhou, and Xiaoning Qian. 2019. Variational graph recurrent neural
Liò, and Yoshua Bengio. 2018. Graph Attention Networks. In International
networks. Advances in neural information processing systems 32 (2019).
Conference on Learning Representations.
[11] Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation
[30] Minjie Yu Wang. 2019. Deep graph library: Towards efficient and scalable deep
learning on large graphs. Advances in neural information processing systems 30
learning on graphs. In ICLR workshop on representation learning on graphs and
(2017).
manifolds.
[12] Charles R Harris, K Jarrod Millman, Stéfan J Van Der Walt, Ralf Gommers,
[31] Xuhong Wang, Ding Lyu, Mengjian Li, Yang Xia, Qi Yang, Xinwen Wang, Xin-
Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg,
guang Wang, Ping Cui, Yupu Yang, Bowen Sun, et al. 2021. Apan: Asynchronous
Nathaniel J Smith, et al. 2020. Array programming with NumPy. Nature 585,
propagation attention network for real-time temporal graph embedding. In Pro-
7825 (2020), 357ś362.
ceedings of the 2021 international conference on management of data. 2628ś2638.
[13] Ming Jin, Yuan-Fang Li, and Shirui Pan. 2022. Neural Temporal Walks: Motif-
[32] Yanbang Wang, Yen-Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. 2021.
Aware Representation Learning on Continuous-Time Dynamic Graphs. In Ad-
Inductive Representation Learning in Temporal Networks via Causal Anonymous
vances in Neural Information Processing Systems.
Walks. In International Conference on Learning Representations.
[14] Thomas N Kipf and Max Welling. 2017. Semi-Supervised Classification with
[33] Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan.
Graph Convolutional Networks. In International Conference on Learning Repre-
2020. Inductive representation learning on temporal graphs. In International
sentations.
Conference on Learning Representations.
[15] Srijan Kumar, Xikun Zhang, and Jure Leskovec. 2019. Predicting dynamic em-
[34] Jianbang Yang, Dahai Tang, Xiaoniu Song, Lei Wang, Qiang Yin, Rong Chen,
bedding trajectory in temporal interaction networks. In Proceedings of the 25th
Wenyuan Yu, and Jingren Zhou. 2022. GNNlab: a factored system for sample-
ACM SIGKDD international conference on knowledge discovery & data mining.
based GNN training over GPUs. In Proceedings of the Seventeenth European
1269ś1278.
Conference on Computer Systems. 417ś434.
[16] Kalev Leetaru and Philip A Schrodt. 2013. Gdelt: Global data on events, location,
[35] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor
and tone, 1979ś2012. In ISA annual convention, Vol. 2. Citeseer, 1ś49.
Prasanna. 2020. GraphSAINT: Graph Sampling Based Inductive Learning Method.
[17] Haoyang Li and Lei Chen. 2021. Cache-based gnn system for dynamic graphs. In
In International Conference on Learning Representations.
Proceedings of the 30th ACM International Conference on Information & Knowledge
[36] Xin Zhang, Yanyan Shen, and Lei Chen. 2022. Feature-Oriented Sampling for
Management. 937ś946.
Fast and Scalable GNN Training. In 2022 IEEE International Conference on Data
[18] Yiming Li, Yanyan Shen, Lei Chen, and Mingxuan Yuan. 2023. Orca: Scalable Tem-
Mining (ICDM). IEEE, 723ś732.
poral Graph Neural Network Training with Theoretical Guarantees. Proceedings
[37] Xin Zhang, Yanyan Shen, Yingxia Shao, and Lei Chen. 2023. DUCATI: A Dual-
of the ACM on Management of Data 1, 1 (2023), 1ś27.
Cache Training System for Graph Neural Networks on Giant Graphs with the
[19] Yiming Li, Yanyan Shen, Lei Chen, and Mingxuan Yuan. 2023. Zebra: When
GPU. Proceedings of the ACM on Management of Data 1, 2 (2023), 1ś24.
Temporal Graph Neural Networks Meet Temporal Personalized PageRank. Pro-
[38] Chenguang Zheng, Hongzhi Chen, Yuxuan Cheng, Zhezheng Song, Yifan Wu,
ceedings of the VLDB Endowment 16, 6 (2023), 1332ś1345.
Changji Li, James Cheng, Hao Yang, and Shuai Zhang. 2022. ByteGNN: efficient
[20] Zhiqi Lin, Cheng Li, Youshan Miao, Yunxin Liu, and Yinlong Xu. 2020. Pa-
graph neural network training at large scale. Proceedings of the VLDB Endowment
graph: Scaling gnn training on large graphs via computation-aware caching. In
15, 6 (2022), 1228ś1242.
Proceedings of the 11th ACM Symposium on Cloud Computing. 401ś415.
[39] Hongkuan Zhou, Da Zheng, Israt Nisa, Vasileios Ioannidis, Xiang Song, and
[21] Xupeng Miao, Yining Shi, Hailin Zhang, Xin Zhang, Xiaonan Nie, Zhi Yang,
George Karypis. 2022. TGL: a general framework for temporal GNN training on
and Bin Cui. 2022. HET-GMP: a graph-based system approach to scaling large
billion-scale graphs. Proceedings of the VLDB Endowment 15, 8 (2022), 1572ś1580.
embedding model training. In Proceedings of the 2022 International Conference on
[40] Rong Zhu, Kun Zhao, Hongxia Yang, Wei Lin, Chang Zhou, Baole Ai, Yong Li,
Management of Data. 470ś480.
and Jingren Zhou. 2019. AliGraph: A Comprehensive Graph Neural Network
Platform. Proceedings of the VLDB Endowment 12, 12 (2019), 2094ś2105.

1072