A GPU Accelerated Temporal Window-Based Random Walk Sampler Md Ashfaq Salehin University of Sussex United Kingdom
George Parisis
University of Sussex United Kingdom
arXiv:2605.16182v1 [cs.DC] 15 May 2026
Abstract Temporal random walks, which sample causality-preserving paths, are widely used to analyze time-stamped interactions in domains such as microservices, finance, and online platforms. Generating such walks at scale is challenging because real-world graphs evolve as high-volume streams, making continuous ingestion, efficient memory usage, and strict temporal ordering essential for practical deployment. We present Tempest (TEMPoral nEtwork Streaming Traversals), a GPU-accelerated engine for streaming temporal random walks. Tempest combines a GPU-native dual-index organization over a shared edge store with a hierarchical cooperative scheduler that dispatches walks at thread, warp, or block granularity based on per-step node convergence, enabling efficient start-edge selection, hop-by-hop causality enforcement, and window-based eviction without synchronization. It further provides closed-form constant-time samplers for common temporal bias functions. Our evaluation demonstrates sustained real-time processing of billionedge streams under sliding windows, outperforming prior systems in ingestion and walk generation throughput while preserving causal correctness.
1
Introduction
Temporal networks are graphs in which interactions (edges) between nodes are time-dependent and occur at specific moments [9]. Unlike static networks where edges are assumed to persist, temporal networks explicitly encode the timing and order of interactions, capturing the dynamic nature of evolving systems. These networks can be either directed, where interactions have a defined source and target (e.g., 𝑢 → 𝑣), such as in email exchanges, phone calls, transportation routes, financial transactions, and microservice calls; or undirected, where interactions are mutual and symmetric, as in face-to-face social encounters or co-location events [9]. Because temporal networks encode fine-grained time order, paths must preserve temporal causality. Reasoning over all such causalitypreserving paths quickly becomes infeasible: even counting them is NP-complete, making exact enumeration impractical for large graphs [4, 40]. This intractability motivates the use of temporal random walks, which provide a scalable alternative by sampling representative time-respecting paths without requiring full enumeration. Sampling not only keeps computation feasible by restricting to a fixed number of walks, but also provides diversity in exploration, ensuring that different regions and temporal patterns of the network are covered. These walks can be generated either in an unbiased manner, where all valid temporal edges are chosen uniformly, or with temporal biases that favor more recent interactions. Common examples include linear and exponential weighting [23], while extensions such as temporal node2vec incorporate additional structural return and in-out parameters [12].
Luc Berthouze
University of Sussex United Kingdom
Temporal random walks are not only of theoretical interest but also form the basis of several temporal node embedding methods such as CTDNE and others [1, 15, 20, 23, 38]. These embeddings enable a variety of downstream tasks across different domains. For example, in microservice systems they support incident detection, root-cause localization, and workload forecasting [3, 18, 19, 30], while in finance they have been applied to stock price forecasting [42]. As a result, the efficiency of temporal walk sampling is critical not only for embedding methods themselves but also for the scalability of these downstream applications. Temporal random walks are also expensive to generate. Walk sampling can dominate training pipelines in large-scale graph learning systems, accounting for up to 96.2% of end-to-end runtime [5, 35] and up to 98.8% of execution time in distributed implementations [26, 44]. A recent system reported that random walk computation alone required 3.5 hours, representing 35% of overall processing time on graphs with hundreds of millions of nodes and billions of edges [21]. The severity of this bottleneck has driven some temporal GNNs to bypass explicit walk sampling in favor of edge streaming or message passing [7, 28, 41]. Related work: Several systems accelerate random walk generation but target different problem settings. Static walk engines such as KnightKing [44], GraphWalker [37], FlashMob [43], and ThunderRW [32], and GPU-based systems including CSAW [26], Skywalker [36], and gSampler [5], achieve high throughput on static graphs but do not account for temporality. Dynamic graph engines such as FlowWalker [21] and Bingo [35] support evolving structures but do not take timestamps as input and cannot generate causality-preserving walks. The only published systems supporting causality-preserving temporal random walks at large scale are TEA [11] and TEA+ [10], which share the same engine; both are CPU-based and require loading the full dataset into memory. To enable high-throughput walk generation, most existing walk engines rely on execution models in which the graph is first reorganized into a CSR-style representation to facilitate fast graph traversals during sampling, as is common in systems such as GraphWalker [37], ThunderRW [32], FlashMob [43], Skywalker [36], gSampler [5], and FlowWalker [21]. This preprocessing step allows efficient random access during execution but introduces a global reorganization cost performed ahead of time and typically excluded from reported metrics. As a result, these systems are primarily evaluated in batch settings and are not designed for streaming or real-time scenarios, where edges arrive continuously and walk generation must proceed without costly preprocessing. In addition, the scale of real-world temporal graphs poses significant challenges for existing methods. Alibaba’s 2022 microservice logs record 81 billion interactions over 14 days, representing only 0.5% of total interactions during that period [18]. Similarly, Visa’s
Salehin et al.
payment infrastructure processed 234 billion transactions in 2024, averaging 639 million timestamped interactions per day across a continuously evolving network of credentials and merchant endpoints [34]. Bulk-oriented methods that require loading the entire dataset into memory are not viable at this scale, making streaming ingestion with bounded memory and data eviction necessary. These limitations motivate a practical temporal random walk system. First, it must strictly preserve temporal causality so that every sampled walk respects time order, unlike static walk engines that ignore temporal ordering. Second, it must sustain streamingscale execution under bounded memory by efficiently ingesting new edges and evicting outdated ones; this setting is widely studied as sliding window processing [2, 6, 16]. Finally, leveraging GPU-native designs is desirable for achieving high throughput at large scale, which in turn requires data structures and algorithms specifically tailored for GPUs to ensure that temporal ordering can be handled efficiently without degrading performance [24]. In this paper, we present Tempest (TEMPoral nEtwork Streaming Traversals), a GPU-accelerated system for temporal random walk sampling. Our contributions include: • A GPU-native temporal random walk engine built on a dual-index edge store with two views over a shared edge array. • Hierarchical cooperative scheduling, an execution model that groups walks at the same node and step into a unit of work and dispatches that unit at thread, warp, or block granularity. • A bounded-memory streaming architecture that integrates batch ingestion, window eviction, and walk generation under sliding-window semantics, materializing GPU-efficient index layouts at each window update without fine-grained mutation or coordination overhead. • Comprehensive experimental validation demonstrating scalability to datasets with up to 81 billion temporal edges, more than sixty times larger than those used in prior work, together with detailed ablation study and sensitivity analyses that explain performance trade-offs. • Open-source implementation released as a Python library with a high-performance C++ core and comprehensive APIs.
2
Tempest: System Architecture
This section presents the system architecture of Tempest. We first formalize the execution constraints imposed by causality-preserving temporal random walks on GPUs, then describe the dual-index data structure over which walks operate. We then present the walk scheduler, which dispatches walks across cooperative GPU execution tiers based on per-step node convergence. The remainder of the section covers temporal bias sampling, streaming ingestion under sliding-window semantics, and a complexity analysis of walk execution, index construction, and memory usage.
2.1
Design Constraints of Temporal Walk Execution
We consider a temporal graph 𝐺 = (𝑉 , 𝐸𝑇 ),
𝐸𝑇 ⊆ 𝑉 × 𝑉 × R+,
where each temporal edge 𝑒 = (𝑢, 𝑣, 𝑡) represents an interaction from node 𝑢 to node 𝑣 occurring at time 𝑡.
For a temporal random walk that arrives at node 𝑣 at time 𝑡, causality requires that transitions respect temporal order. The causality-preserving neighborhood in the forward direction is Γ𝑡 (𝑣) = {(𝑣, 𝑤, 𝑡 ′ ) ∈ 𝐸𝑇 | 𝑡 ′ > 𝑡 }, with the backward case defined analogously. Each hop selects its next edge from this node-conditioned and time-filtered neighborhood; ties on timestamps are broken by uniform random sampling. The set Γ𝑡 (𝑣) is hop-dependent: its membership depends on both the current node and the timestamp reached at the previous step. It cannot be precomputed, cached, or reused across hops without violating temporal correctness. On GPUs, enforcing hop-dependent temporal constraints by enumerating valid neighbors or synchronizing threads does not scale. These approaches produce irregular memory access and coordination overhead, which limit throughput on massively parallel hardware [24].
2.2
System Overview
Tempest ingests a temporal edge stream (𝑢, 𝑣, 𝑡) and processes it in GPU-resident batches. Each batch undergoes three stages: GPUparallel ingestion with sliding-window eviction (Section 2.6), reconstruction of a dual-index representation over the active edge set (Section 2.3), and generation of temporal random walks under a hierarchical cooperative scheduler (Section 2.4). The dual index provides both global temporal access (for start-edge selection and window eviction) and node-conditioned temporal access (for walk progression). Once built, the index is reused across many walk sampling operations, amortizing construction (Section 2.7). This design favors bulk reconstruction over fine-grained mutation. Tempest rebuilds its index at batch boundaries, in contrast to dynamic graph systems that incrementally update adjacency structures. Construction and window maintenance run entirely through GPU data-parallel primitives, avoiding synchronization and sequential updates. The resulting layout is compact, predictable, and aligned with sliding-window eviction.
2.3
Dual-Index Organization Shared Edge Store List of active interactions: (u1 , v1 , t1 ), (u2 , v2 , t2 ), . . . Logical Views
Timestamp Grouped View (Global Sorting)
Node+TS Grouped View (Temporal Neighborhoods)
Used for efficient Start Edge Sampling
Used for causal Walk Progression
Figure 1: Dual-index organization. Two logical views over a shared edge store, distinguished by their offset arrays. Tempest organizes active edges as a shared edge store with two logical views, illustrated in Figure 1: a timestamp-grouped view and a node–timestamp-grouped view. Both are offset structures over a single edge array; neither replicates edge data.
A GPU Accelerated Temporal Window-Based Random Walk Sampler
Timestamp-grouped view. The timestamp-grouped view orders edges globally by timestamp, with an offset array marking each timestamp group’s boundary. Start-edge sampling under a temporal bias and bulk window eviction both proceed by binary search over the offset array: the bias selects a timestamp group, and the offset locates the corresponding edge slice in constant time. Window eviction then reduces to discarding the prefix of the edge array up to the temporal cutoff.
which a GPU rewards [8, 24], are absent. We introduce hierarchical cooperative scheduling, an execution model that recovers them by treating walks at the same node and step as a unit of cooperative work and dispatching that unit at thread, warp, or block granularity based on how many walks have converged.
Node-and-timestamp-grouped view. The node-and-timestampgrouped view is a two-level offset structure. Edges are grouped by source node, then ordered by timestamp within each node’s region. Figure 2 shows the layout. A node-group offset array locates each node’s edge region; a node–timestamp-group offset array locates each timestamp sub-group within that region. Both offset arrays are built once per batch and reused across all walks.
start node
thread
step 0
step 1
step 2
step 3
n1
t1
n1
n3
n2
n1
n3
t2
n3
n1
n2
n2
t3
n2
n1
n1
t4
n1
n2
Edge Array:
n1 → n2 t1
n1 → n3 t2
n1 → n4 t2
1
2
n2 → n1 t1
n2 → n4 t2
3
4
5
0
3
6
n1
n2
end
3
3
n1
n2
Node Group Counts:
n3
n1
no valid edge
0 n2 → n3 t1
Node Group Offsets:
Indexes in global memory
Figure 3: Full-walk execution where each thread advances one walk independently.
Figure 2: Node-and-timestamp-grouped view.
2.4.1 The Full-Walk Baseline. The naive GPU baseline is to assign one thread to each walk. We call this the full-walk baseline. At each step, the thread fetches its current node’s edge range from global memory, locates the temporal cutoff Γ𝑡 (𝑣) by binary search, draws an edge, and advances to the next hop. The kernel scales by launching more threads. Figure 3 illustrates one step. Walks that converge on the same node share the index range and the binary-search target, but full-walk threads fetch and search independently. On hub-skewed temporal graphs [9, 18], this redundancy dominates per-step global-memory traffic. Walks also terminate at different steps when Γ𝑡 (𝑣) becomes empty, leaving lanes masked within an otherwise active warp.
A walk thread evaluates Γ𝑡 (𝑣) in two steps. The node-group offset array gives the edge range [𝑎, 𝑏) for node 𝑣 in constant time. A binary search over the node–timestamp-group offset array within [𝑎, 𝑏) then locates the first timestamp strictly greater than 𝑡, returning [𝑐, 𝑏) ⊆ [𝑎, 𝑏) as Γ𝑡 (𝑣). The cost is O (log 𝐺) where 𝐺 is the number of distinct timestamp groups at 𝑣. Selecting an edge from Γ𝑡 (𝑣) is then constant-time pointer arithmetic. This two-stage lookup eliminates per-hop neighborhood scanning.
2.4.2 Cooperation and Its Challenges. Walks that converge on the same node at the same step share work: the temporal binary search, the timestamp-group offsets it consults, and the edge-range arithmetic are identical across the group, while only the random draw and the picked edge differ per walk. NextDoor [14] exploits this on static graphs by caching the transit’s adjacency list in shared memory across co-located walks. The temporal regime introduces five challenges that a static design does not face.
Node-TS Group Offsets:
0
1
3
5
6
(n1 , t1 )(n1 , t2 )(n2 , t1 )(n2 , t2 ) end
Node Color Map: • n1 edges • n2 edges
2.4
Node-TS Group Color Map: • (n1 , t1 ) group • (n1 , t2 ) group • (n2 , t1 ) group • (n2 , t2 ) group
Hierarchical Cooperative Scheduling
Causality-preserving temporal walks expose a tension when executed on a GPU. At each hop, a thread must locate Γ𝑡 (𝑣) inside the node’s edge range, sample under the active bias, and write the result. The work is short, dependent on the previous hop’s timestamp, and concentrated on a single node’s metadata. When tens of thousands of walks advance in parallel, threads in the same warp diverge across nodes, accesses to per-node metadata scatter across global memory, and control flow branches on walk lifetime. Coalesced access, shared-memory reuse, and uniform branching, all of
• Variable walk length. Temporal walks terminate early whenever no future valid edge exists at the current node, producing high per-walk variance in walk length. Under one-thread-perwalk dispatch, terminated lanes sit masked while their warpmates continue, so warp efficiency degrades step by step. • Runtime grouping. The walk-population count 𝑊 at each node changes every step as walks migrate. It can only be obtained by inspecting walk state at the current step, so the grouping must be recomputed on every hop. • Granularity selection. The execution unit that does the computation depends on 𝑊 . A node with tens of walks underutilizes a
Salehin et al.
block but suits a warp; a node with hundreds of walks overflows a warp’s lanes. Suboptimal resource allocation reduces efficiency. • Bounded shared memory. The per-node metadata that makes cooperation profitable is the timestamp-group offset array, whose size 𝐺 varies across nodes and across windows. Only some fit in a warp’s slice of shared memory, fewer fit in a block’s, and the rest must be served from global memory. • Mega-hubs. A single node can hold thousands of walks. A oneblock-per-task dispatch would monopolize an SM with one task while other SMs sit idle, requiring work to be split across blocks. 2.4.3 Cooperative Dispatch. Tempest dispatches each per-node group of co-located walks to one of three execution units, sized to the GPU thread hierarchy: a single thread, a warp, or a thread block. The cooperative tiers (warp and block) preload the node’s adjacency metadata into shared memory (smem) once per task; every thread of the unit reads from smem instead of global memory. With the metadata resident, the temporal binary search and the edge-range arithmetic become smem reads, and the heavy globalmemory access is done once per node rather than once per walk. Walk dispatch at step i block warp
block warp
block
W1 W2 W3 W4
n5 : {W9 ..W36 }
warp
warp
W5 W6 W7 W8
n12 : {W37 ..W64 }
{W65 , ..., W320 }
solo 1 walk / thread
warp-coop 1 node / warp
block-coop 1 hub / block
smem
smem
smem
hub n42
Figure 4: Three cooperative execution units. Solo dispatches one walk to one thread. Warp-coop assigns one node’s walks to one warp, all 32 threads sharing the node’s adjacency metadata in smem. Block-coop assigns one hub’s walks to one block, with a larger smem allocation holding the metadata. Figure 4 shows the three units. Solo handles nodes carrying a handful of walks; the cooperation overhead is unjustified there, so each walk runs as in the full-walk baseline but launched within a step-bounded kernel. Warp-coop and block-coop differ in scale: a warp’s smem allocation holds less metadata than a block’s, so the warp tier serves moderate 𝑊 and the block tier serves the long tail. 2.4.4 The Dispatch Plane. The choice between solo, warp-coop, and block-coop is governed by the walk-population count 𝑊 . The choice between an in-smem metadata copy and a global-memory fallback within each cooperative tier is governed by the node’s timestamp-group count 𝐺. The two together define a dispatch plane shown in Figure 5, partitioned into the five terminal kernels. The 𝑊 thresholds set tier boundaries. The warp/block boundary is 𝑊 = block_dim: a node carrying more walks than a block can hold must use a block-tier kernel. The solo/warp boundary is a tunable hyperparameter that trades cooperation overhead against amortization gain at low 𝑊 , where co-located walks are few. Both are tuned empirically (Section 3.5).
G=1
warp × smem solo
block × smem
multi-block × smem
block × global
multi-block × global
warp × global
W =5
G=340
G=2800
W =257
W =8193
Figure 5: Dispatch plane. The 𝑊 axis selects the execution unit; the 𝐺 axis selects whether the node’s adjacency metadata is preloaded into smem or read from global memory. W thresholds are obtained empirically (Section 3.5). The 𝐺 thresholds set memory-tier boundaries. In the warp tier, the metadata sits in a warp’s slice of the block’s shared-memory allocation. In the block tier, it occupies the full block’s allocation. Each is sized to the maximum that fits, giving the per-tier 𝐺 caps shown in Figure 5: above each cap, the metadata does not fit and the kernel reads from global memory instead. The block tier’s larger budget tolerates roughly 8× the 𝐺 that the warp tier does, reflecting the block hosting 8 warps that share the smem allocation. Mega-hubs occupy the rightmost column. A node with𝑊 > 8192 walks would, under one-block-per-task dispatch, monopolize one streaming multiprocessor while others sit idle. Tempest splits such tasks into ⌈𝑊 /8192⌉ disjoint sub-tasks, each dispatched to its own block. The walks at the node are partitioned into contiguous slices of up to 8192, with each block assigned a slice and performing sampling on it independently. The metadata is loaded once per sub-task because the underlying node is the same. Algorithm 1 Per-step walk scheduling. Require: walk array, step 𝑖, timestamp-group counts 𝐺 [·] Ensure: task lists for the solo, warp-smem, warp-global, blocksmem, block-global tiers 1: flag walks alive at step 𝑖 2: compact alive walks via PartitionFlagged 3: gather each alive walk’s current node 4: SortPairs (current node, walk index) by node 5: RunLengthEncode on sorted nodes; ExScan on run lengths 6: partition runs by 𝑊 into solo, warp, block tiers {Fig. 5} 7: partition warp tier by 𝐺 into warp-smem, warp-global 8: partition block tier by 𝐺 into block-smem, block-global 9: expand block-tier tasks with 𝑊 > 𝑊max into disjoint sub-tasks 2.4.5 Per-Step Pipeline. The scheduler produces the five terminal task lists with a sequence of GPU data-parallel passes, summarized in Algorithm 1. Most stages are CUB primitives [25]; the remaining are custom kernels (alive flagging, current-node gather, the partitions, and the mega-hub expansion). Two host syncs are required
A GPU Accelerated Temporal Window-Based Random Walk Sampler
per step: one to read the alive count after compaction, and one to read the per-tier task counts before launching the terminal kernels.
2.6
2.4.6 Comparison to Prior Dispatch Schemes. Multi-granularity dispatch on GPUs is itself not new. Skywalker [36] and FlowWalker [21] assign work at warp or block granularity, but the dispatch input is the static structural degree of the current vertex and does not depend on the state of the walk population. Tempest’s 𝑊 is a runtime, per-step quantity that requires inspecting walk state at the current step. The same node receives different dispatch granularities at different steps as walks migrate. NextDoor [14] performs the closest analog of Tempest’s per-step regrouping: it inverts the sample-to-transit map and dispatches each transit vertex to a warp, block, or grid of blocks based on the number of samples sharing that transit. Once a kernel choice is made, NextDoor caches the transit’s adjacency slice unconditionally within that choice. Tempest extends the regrouping idea to the temporal regime: the data preloaded is the per-node timestampgroup offset array under sliding-window expiration, the decision to preload at all is governed by 𝐺, and Tempest filters walk state per step to drop completed walks before kernel launches. FlexiWalker [27] is recent work that adapts at runtime per node. The signal and the decision space differ. FlexiWalker selects between rejection and reservoir sampling per node using a runtime cost model, targeting dynamic random walks on static graphs. Tempest selects an execution unit and a memory tier per task based on 𝑊 and 𝐺, on streaming temporal graphs under sliding windows.
Tempest maintains an active temporal window of fixed duration Δ. At time 𝑡, the active edge set is
2.5
Temporal Bias Sampling
Each hop selects the next edge under a temporal bias evaluated within the index range exposed by the dual-index. Tempest’s default sampler is weight-based: it applies inverse transform sampling on the cumulative weight array of Γ𝑡 (𝑣). Edges are assigned weights 𝑤 (𝑒𝑖 ) = exp(𝑡𝑖 − 𝑡 min ) where 𝑡 min = min𝑒 ∈Γ𝑡 (𝑣) 𝑡 (𝑒); the cumulative Í array 𝑊 [𝑘] = 𝑘𝑗=0 𝑤 (𝑒 𝑗 ) is built once per neighborhood, and a draw 𝑢 ∼ U (0, 1) selects the smallest index 𝑘 with 𝑊 [𝑘] ≥ 𝑟 for 𝑟 = 𝑢 · 𝑊 [𝑛 − 1] via binary search, at O (log 𝑛) per hop. When timestamp gaps within a neighborhood are uniform, only ordinal position matters, and the index-based sampler admits closedform inverse CDFs over the index 𝑖 ∈ [0, 𝑛): (1)
Uniform: 𝑖 = ⌊𝑢 · 𝑛⌋. Linear: 𝑖 =
√
−1+ 1+4𝑢𝑛 (𝑛+1) 2
.
Exponential: 𝑖 ≈ ⌊𝑛 + ln(𝑢) − 1⌋.
(2) (3)
These collapse the per-hop cost to O (1) on a single random draw. Derivations and the numerically stable forms are deferred to the supplementary material. Tempest supports Temporal Node2Vec [12], which adds a secondorder bias 𝛽 (𝑢, 𝑤) depending on the previous node. We apply 𝛽 via rejection sampling on the static exponential proposal: each hop accepts with probability 𝛽 (𝑢, 𝑤)/𝛽 max , where 𝛽 max = max(1/𝑝, 1, 1/𝑞), keeping the inner CDF prev-independent so Node2Vec runs through the same cooperative dispatch path as other pickers.
Streaming Ingestion and Window Management
𝑊 (𝑡) = {𝑒 ∈ 𝐸𝑇 | 𝑡 − Δ ≤ 𝑡𝑒 ≤ 𝑡 }, where 𝑡𝑒 is the timestamp of edge 𝑒. Only edges within 𝑊 (𝑡) participate in indexing and walk sampling, bounding memory usage by |𝑊 (𝑡)| regardless of total stream length. Incoming batches advance the window forward in time. Each batch is sorted by timestamp before merge; edges older than 𝑡 − Δ at merge time are dropped. The system assumes monotonic batch boundaries: edges arriving in a later batch with timestamps before the current window are treated as too late and dropped without retraction. This is consistent with the streaming-graph processing model used in prior work on sliding-window analytics [6, 16]. Each batch triggers a bulk reconstruction of the dual-index over the updated edge set rather than incremental mutation. Ingestion and rebuild costs depend on |𝑊 (𝑡)| and do not accumulate across batches; if per-batch processing time stays below the arrival interval, the stream sustains stable throughput without backlog (Section 3.3). The window duration Δ trades temporal context against memory and rebuild cost; we measure this trade-off in Section 3.9.
2.7
Complexity Analysis
Walk execution. Let 𝐿 denote the walk length and let |Γ𝑡 (𝑣)| be the size of the causality-preserving neighborhood at a hop from node 𝑣. The per-hop cost depends on the sampler. The index-based picker performs a constant number of arithmetic operations and one random draw, yielding O (1) per hop and O (𝐿) per walk. The weight-based picker performs a binary search over the cumulative weight array of Γ𝑡 (𝑣), yielding O (log |Γ𝑡 (𝑣)|) per hop and O (𝐿 log |Γ𝑡 (𝑣)|) per walk. Cooperative dispatch (Section 2.4) reduces wall-clock time by amortizing the per-node work across co-located walks but does not change per-walk asymptotic cost. Index construction and window management. Let 𝑚 = |𝑊 (𝑡)| denote the number of edges in the active window. Each batch boundary triggers eviction and reconstruction of the dual-index. The reconstruction performs two GPU radix sorts (one for each view) and a constant number of linear-time prefix-sum and offset-generation passes. CUB’s radix sort is linear in input size [25], so each runs in O (𝑚) work, and the per-batch reconstruction cost is O (𝑚). These costs are amortized across the 𝐾 walks generated from the rebuilt indices, giving a per-walk amortized index cost of O (𝑚/𝐾). Memory usage. Memory is bounded by the active window. Each edge in 𝑊 (𝑡) is stored once in the shared edge store, with auxiliary index arrays of total size linear in 𝑚. No memory is retained for evicted edges, and usage does not grow with input stream length.
3 Evaluation 3.1 Experimental Setup Hardware and configuration. Experiments use compute nodes with 32 CPU cores, 196 GB of RAM, and an NVIDIA A40 GPU (46 GB VRAM, CUDA 12.6). GPU kernels use a block dimension of 256 (Section 3.5). Walk length is 80, walks per node is 10, temporal bias
Salehin et al.
Baselines. We compare against TEA+ [10] and TEA [11], CPU temporal-walk engines using hybrid alias sampling; for temporal walks the two systems are identical, as evidenced by TEA+ reporting the same tables as TEA (TEA: Table 4, TEA+: Table 2). Several random walk engines target static or dynamic-structure graphs, including GraphWalker [37], KnightKing [44], FlashMob [43], ThunderRW [32], FlowWalker [21], and Bingo [35]; these systems do not ingest timestamps and cannot enforce temporal causality. We compare against two representatives in Section 3.10.
3.2
Datasets
Table 1: Datasets used in evaluation. Dataset
Nodes
Edges
TGBL-Review [13] TGBL-Coin [13] Konect-Growth [17] TGBL-Flight [13] Konect-Delicious [17] Alibaba Microservices [18]
352K 638.5K 1.8M 18K 33.7M 68K
4.8M 22.8M 39M 67M 301M 81B
1.0 0.5 0.0
0
25
50
75
Total Edges Added (Billions)
102
Index Weight TN2V
1.7
Tempest GPU Tempest CPU Raphtory
100
1.6 1.5
100K
10M
Number of edges (a) Edge ingestion.
1B
1K
100K
10M
301M
Number of edges (b) Walk sampling (10M walks).
Figure 7: Scaling on Konect-Delicious (1K to 301M edges). We characterize how Tempest scales with active graph size on Konect-Delicious. To our knowledge, no random walk engine supports streaming ingestion as part of its pipeline; we therefore compare against Raphtory [31], an industrial temporal graph engine supporting incremental edge insertion at this scale, and against a CPU backend of Tempest itself. The CPU backend mirrors the GPU data-parallel primitives, pickers, and samplers using OpenMP and TBB; the hierarchical cooperative scheduler is GPU-only. Both backends share the same data structures and source tree, so CPUvs-GPU comparisons isolate the GPU’s parallelism advantage.
0.2 0.1 0
Scaling Behavior
1K
0.3
0.0
3.4
10 2
Streaming-Scale Evaluation Total Time (hours)
Total Time (hours)
3.3
Results. Figure 6 shows cumulative ingestion and walk-sampling time as the 14-day stream is replayed. Tempest sustains real-time processing throughout: per-batch ingest averages 596 ms and walk sampling averages 167 ms, against a 180-second batch arrival interval, leaving over 235× headroom and no backlog. The full 81 billion edges are processed end-to-end in 1.42 hours of wall time (1.11 hours ingestion, 0.31 hours sampling). The ingestion curve is essentially linear, confirming that batch-bounded reconstruction cost (Section 2.6) does not accumulate as the stream advances.
Time (s)
We report streaming-scale results on Alibaba, the largest publicly available temporal interaction dataset (81B edges over 14 days) [18]. Detailed ablation, profiling, and sensitivity studies use TGBL-Coin, TGBL-Flight [13], and Konect-Delicious [17], three of the largest temporal datasets in TGB and Konect. Profiling at Alibaba scale is impractical due to the cost of repeated full-stream replays. Table 1 lists the datasets used in the main paper.
sliding window, holding ≈120M active edges in steady state. After each batch, the system generates 20 temporal random walks of length 100 from every active source node (≈219K walks per batch). High-frequency interaction data of this kind concentrates many events into each millisecond timestamp, making timestamp gaps approximately uniform; we therefore use the index-based sampler with the closed-form O (1) inverse-CDF (Section 2.5), which is exact under uniform-gap conditions.
Time (s)
is exponential, and start bias is uniform unless stated otherwise. The default sampler is weight-based (Section 2.5). Streaming experiments process temporally ordered batches under a sliding window of one-third the dataset’s time span. Results average over five runs.
25
50
75
Total Edges Added (Billions)
(a) Cumulative edge ingestion (b) Cumulative walk sampling time. time.
Figure 6: Cumulative streaming performance on the Alibaba dataset over 81B edges. We evaluate Tempest under sustained streaming on the Alibaba 2022 Microservice Logs [18]: 81 billion interactions among 68,000 microservices over 14 days, partitioned into 6,720 chronological 3-minute batches of ≈12M edges each. Tempest uses a 60-minute
Ingestion. Each point on Figure 7a is a separate run that ingests the indicated number of edges from scratch and rebuilds the dualindex. At 301M edges, Tempest GPU completes ingestion in 0.9 s, 76× faster than Raphtory and 84× faster than the same algorithm on CPU. Tempest CPU and Raphtory are within 10% of each other across the range, which separates the GPU advantage from any algorithmic difference between Tempest and Raphtory. Walk sampling. Each point on Figure 7b is a separate run that ingests the indicated number of edges and then generates 10M walks of length 100 with uniformly sampled start nodes. All three pickers stay essentially flat across edge counts: per-walk time varies by less than 5% from 1K to 301M edges. The rejection-sampling
A GPU Accelerated Temporal Window-Based Random Walk Sampler
Table 2: Cooperative scheduler ablation. Steps/sec averaged over five runs (mean ± std); kernel time and launch count are per walk-generation call.
Variant
M-steps/s
TGBL-Coin ms/call launches
TGBL-Flight M-steps/s ms/call launches
Konect-Delicious M-steps/s ms/call launches
Full-Walk Coop-Global Coop
59.4 ± 0.9 60.6 ± 1.2 63.8 ± 1.2
1496 ± 3.9 1293 ± 1.5 1273 ± 0.7
106.9 ± 1.3 108.1 ± 1.1 112.3 ± 1.5
60.5 ± 0.8 62.5 ± 0.8 66.7 ± 1.2
324 ± 1.2 297 ± 0.04 276 ± 0.02
coin delicious
flight mean
8 2,487 2,646
107 ± 0.2 96 ± 0.04 89 ± 0.04
formulation of Temporal Node2Vec (Section 2.5) lets the secondorder picker run through the same cooperative dispatch path as the first-order pickers, with per-hop cost dominated by walk length rather than neighborhood size. The GPU backend accelerates all three pickers by 2.5–2.9× over the CPU backend (CPU lines are omitted from the figure for brevity).
Parameter Tuning
The cooperative scheduler exposes two tunable parameters: the CUDA block dimension and the solo–warp boundary 𝑊warp . Block dimension. Figure 8 sweeps the block dimension on TGBLCoin. Block dimension is determined by the kernel’s GPU resource footprint, so a single representative dataset suffices. Throughput rises sharply through 128 and then flattens; values from 128 to 512 lie within run-to-run standard deviation of each other. SM occupancy continues to rise past 128 and saturates at 256. Going beyond 256 also requires opting into the architecture’s higher dynamic shared-memory ceiling, which causes portability and occupancy issues. We default to 256, the largest block size that fits the static shared-memory envelope and captures both the throughput plateau and the occupancy saturation point.
Occupancy (%)
M steps / s
80 70 60
32
128
block_dim (a) Walk throughput.
512
50 40 30 20
32
128
512
block_dim (b) SM occupancy.
Figure 8: Block dimension sweep on TGBL-Coin. Solo–warp boundary. Figure 9 sweeps𝑊warp ∈ {1, 2, 4, 8, 16, 32, 64} on TGBL-Coin, TGBL-Flight, and Konect-Delicious. Per-dataset throughput stays within 3% of its maximum on TGBL-Coin and TGBL-Flight across the full range. Konect-Delicious peaks at𝑊warp = 4 and drops by 9% at 𝑊warp ≥ 8. Its heavy-tailed degree distribution produces many medium-𝑊 nodes that benefit from warp-coop amortization. At higher thresholds these nodes fall into solo dispatch, forfeiting the amortization. The cross-dataset mean peaks at 𝑊warp = 4, which we adopt as the default.
8 576 575
1.000
Frac. of max
3.5
8 2,487 2,567
0.975 0.950 0.925 0.900 1
2
4
8
Wwarp
16 32 64
Figure 9: 𝑊warp sweep across three datasets. Per-dataset throughput is normalized to its own maximum; the bold curve is the cross-dataset mean.
3.6
Cooperative Scheduler Ablation
We isolate the two mechanisms of the cooperative scheduler (Section 2.4) by comparing three execution variants on TGBL-Coin, TGBL-Flight, and Konect-Delicious. Variants. Full-Walk is the one-thread-per-walk baseline of Section 2.4.1: each thread carries one walk to completion with no shared state. Coop-Global enables the per-step regrouping and tier dispatch but disables the smem-resident metadata; cooperative tiers read the per-node timestamp-group offsets from global memory on every hop. Coop is the full scheduler: per-step regrouping plus tier dispatch plus the smem panel. Results. Table 2 shows that cooperative dispatch alone (CoopGlobal vs. Full-Walk) lifts throughput by 2–3% across the three datasets, and adding smem-resident metadata (Coop vs. CoopGlobal) lifts it by a further 4–7%. The two mechanisms compose additively for an end-to-end gain of 5–10%. The structural change is visible in the launch and per-call columns. Full-Walk performs each walk-generation call with eight monolithic kernel launches, running for hundreds of milliseconds (1.5 s on coin, 324 ms on delicious). Coop and Coop-Global decompose work into thousands of tier-specific micro-kernels: ∼2,500 launches on coin and flight (300× more), ∼575 on delicious (70× more). Per-kernel time drops to tens or hundreds of microseconds, and wall-clock per call drops by 10–15% despite the larger launch count. Smemresident metadata accounts for the additional gain over Coop-Global by amortizing the per-node temporal-index access across co-located walks, reducing global-memory traffic in the warp- and block-tier
Salehin et al.
kernels. Beyond the throughput gain, the scheduler bounds perlaunch cost regardless of walk-population skew, which enables scaling to mega-hub workloads under sliding windows. Table 3: Per-tier launch distribution (%) on Coop. Tier
Coin
Flight
Delicious
solo warp × smem warp × global block × smem block × global multi-block
14.2 14.4 14.4 14.2 14.2 28.7
16.5 16.7 16.7 16.5 0.0 33.5
20.2 20.5 0.0 16.9 0.0 42.5
Tier distribution. Table 3 shows that the dispatch plane is fully exercised. Mega-hub expansion accounts for 29–43% of launches across all three datasets, validating the W-axis. Coin and Flight exercise the global tier where 𝐺 exceeds the smem cap, validating the G-axis; Delicious never reaches the global fallback because its 𝐺 distribution fits within the smem caps at every step.
3.7
Ingestion Time Breakdown
We profile each batch with NVIDIA’s NVTX to measure four stages: the dual-index sort, cumulative-weight precomputation for the bias sampler, host-to-device transfer, and pipeline overhead. Pipeline overhead captures the per-batch framework costs (GPU memory allocation, kernel-launch queueing, CPU-GPU coordination) that recur every batch but do not accumulate. Table 4: Per-batch ingestion time breakdown (% of total). Stage
Coin
Flight
Delicious
sort weight H2D pipeline overhead
6.3 10.8 26.4 56.5
14.7 0.6 19.5 65.2
8.9 26.4 23.9 40.9
total (ms)
210
219
226
Results. Table 4 shows the breakdown averaged over a full streaming run. Sort accounts for 6–15%, validating the linear-time CUB radix sort claimed in Section 2.7. Weight precomputation scales with node count: Flight (18K nodes) sees 0.6%, Delicious (34M nodes) sees 26%. Host to device transfer (H2D) is roughly proportional to batch size. Pipeline overhead dominates because each batch accumulates many small framework costs (allocation, kernel launch overhead, CPU-GPU coordination) across the ingestion pipeline. Each component is bounded by the active window |𝑊 (𝑡)| and does not accumulate as the stream advances.
3.8
Comparison with TEA+/TEA
TEA+ [10] and its predecessor TEA [11] are CPU-based engines for causality-preserving temporal random walks, the closest comparable baselines to Tempest. We compare architectural design and end-to-end performance on shared workloads.
Architecture. TEA+ operates in bulk mode and requires the full temporal graph in memory before walk generation; it does not support sliding-window eviction. Its sampler relies on hierarchical alias tables and hash-indexed structures; per-vertex alias trunks consume substantial auxiliary memory and require updates across multiple distributed structures when edges are evicted. Tempest stores edges once and exposes two logical orderings (Section 2.3), supporting global start-edge selection and window eviction over the same physical layout, with hop-by-hop progression served from a node-local timestamp ordering. Source code and reproducibility. TEA+’s source code is not publicly available and could not be obtained from the authors. Faithful reimplementation without access to internal design details would be unlikely to yield a fair comparison. Following the standard practice for evaluating closed-source systems [29, 33, 39], we report TEA+’s performance numbers as published. Datasets. TEA+ reports four KONECT [17] datasets. We restrict our comparison to growth and delicious, whose edge counts and temporal attributes match the public KONECT release. The reported edge count for edit differs from the count listed on KONECT, and twitter is listed on KONECT without timestamps. We therefore exclude both from the comparison. Performance. Table 5 reports walk generation runtimes under the configuration TEA+ uses (1 walk per node, walk length 80). Tempest runs in bulk mode for parity, while its primary operating regime is streaming ingestion in smaller batches under bounded memory (Section 3.3). Under exponential bias, the configuration TEA identifies as the most relevant for temporal walks [11], Tempest is 4.6–5.8× faster. Under linear bias the two systems are comparable. For Temporal Node2Vec, Tempest is 6–7× faster on both datasets. Due to differing execution models and hardware, these results are indicative rather than definitive.
3.9
Window Duration Sensitivity
The temporal window duration Δ trades historical context against per-batch cost. We sweep Δ from 1 to 10 batches on TGBL-Coin, TGBL-Review, and TGBL-Flight, with batch duration fixed at 𝑇 /100 where 𝑇 is each dataset’s time span. Walk length, walks per node, and bias are held constant. For downstream evaluation, we split each dataset chronologically into 70/15/15 train/validation/test partitions. Walks generated after each training batch update node embeddings via incremental skipgram [22] training. Link prediction is supervised against negative edges constructed by replacing each positive edge’s target with a non-co-occurring node. We report mean and standard deviation of test AUC across five trials. Results. Figure 10 shows walk-sampling latency rising monotonically with Δ as the active edge set grows. Downstream link prediction peaks at Δ = 1–2 batches; beyond that, AUC plateaus or declines. Larger windows resample stale interactions across batches, diluting the contribution of recent edges. Recent context alone is sufficient for accurate prediction when the underlying model is updated regularly; increasing Δ beyond this regime spends GPU memory and sampling cost without improving prediction quality.
A GPU Accelerated Temporal Window-Based Random Walk Sampler
Table 5: Performance comparison on shared datasets. Runtimes in seconds; best values in bold. Exponential
Linear
Temporal Node2Vec
Dataset
TEA+
Tempest
TEA+
Tempest
TEA+
Tempest
growth delicious
2.93 38.84
0.50 (5.8×) 8.43 (4.6×)
0.56 7.98
0.49 8.36
3.52 59.82
0.51 (6.9×) 9.64 (6.2×)
Table 6: Comparison with non-temporal walk engines. Throughput is mean ± std of 10 runs. Best values in bold. Avg.
Throughput (M steps/s)
Degree
Tempest
Flow.
Thun.
Tempest
Flow.
Thun.
Tempest
Flow.
Thun.
Growth Delicious TGBL-Coin TGBL-Flight
21.4 8.9 35.7 3702.2
30.6 ± 0.6 66.7 ± 1.2 63.8 ± 1.2 112.3 ± 1.5
28.8 ± 0.0 1.3 ± 0.0 10.0 ± 0.0 97.3 ± 0.1
7.3 ± 1.3 11.0 ± 1.2 13.9 ± 0.1 16.6 ± 0.3
100 100 100 100
0.0 0.0 0.0 0.0
1.1 0.1 0.9 1.2
100 100 100 100
0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0
+0.00 -0.01
2.0
-0.04 1 2
5
1
10
(a) Walk sampling.
tgbl-coin
2
3
5
10
Window size (batches)
Window size (batches)
(b) Link prediction ΔAUC.
tgbl-review
tgbl-flight
Figure 10: Window sensitivity on TGB datasets. (b) reports ΔAUC relative to the smallest window (1 batch); baseline AUCs are 0.861 (coin), 0.535 (review), 0.971 (flight). Asterisks mark per-dataset optima.
Comparison with Non-Temporal Baselines
GPU and CPU random walk systems for static graphs operate on time-agnostic abstractions and do not enforce temporal causality. For consistency with prior comparisons in this space [10, 11], we evaluate Tempest against two recent, high-performance static frameworks for which open-source artifacts are available: the GPUbased FlowWalker [21] and the CPU-based ThunderRW [32]. We ran FlowWalker on the same NVIDIA A40 used for Tempest and ThunderRW on a 20-core CPU server with 192 GB of RAM. Setup. We evaluate on four temporal datasets at varying scales. For FlowWalker and ThunderRW, timestamps were discarded to accommodate their static graph abstraction. With each system we generate 10 million walks of length 80. Temporal causality was independently validated by post-processing each walk using a greedy, earliest-feasible timestamp assignment rule. Walks violating strict timestamp monotonicity were marked as invalid. Results. Table 6 reports throughput alongside hop- and walklevel temporal validity. FlowWalker and ThunderRW produce 0%
3.11
Memory Usage Analysis
We evaluate Tempest’s memory footprint under two regimes: bulk mode with varying edge count, and streaming mode with a sliding window where each ingested batch evicts the previous one.
32 24 16 8 0
Memory (GB)
20.0 10.0 5.0
valid walks across every dataset: although a small fraction of individual hops happen to satisfy temporal monotonicity by chance (up to 1.2%), every walk contains at least one violation. This is structural, not a tuning issue: static engines have no notion of temporal causality and cannot preserve it. Once the validity gap is established, the throughput numbers quantify the cost of enforcing causality. Tempest is fastest on every dataset, with the largest margins on Delicious (51× over FlowWalker) and TGBL-Coin (6.4×). Throughput scales with the average static degree across datasets.
Memory (GB)
+0.01
AUC
Time (s)
Valid Walks (%)
Dataset
50.0
3.10
Valid Hops (%)
103 106 Edge Count
109
(a)
Directed (w/ weights) Directed (w/o weights)
0.08 0.07 0.06 0.05 0
25 50 75 100 Batch Number (b)
Undirected (w/ weights) Undirected (w/o weights)
Figure 11: Memory usage. (a) Edge scaling in bulk mode (nodes = 10K, timestamps = 10K). (b) Streaming with a constant window over 100 batches of 10M edges each. Results. Figure 11a shows linear memory growth with edge count, matching Tempest’s flat layout: 1 billion edges fit in approximately 35 GB, well within commodity datacenter GPUs like the
Salehin et al.
NVIDIA A40 (46 GB VRAM). Figure 11b shows memory remaining flat across 100 streaming batches, confirming the bounded-memory claim from Section 2.7: memory does not grow with stream length, only with active-window size. Weight-based sampling consumes slightly more memory than index-based due to the cumulativeweight arrays, and trends hold for directed and undirected modes.
4
Conclusion
Tempest is a GPU-accelerated engine for streaming temporal random walks combining a dual-index edge store with a hierarchical cooperative scheduler that dispatches walks at thread, warp, or block granularity. Sustained processing of 81 billion edges over a 14-day stream demonstrates bounded-memory streaming temporal walks at industrial scale, with 76× ingestion speedup over the closest temporal graph engine and causal correctness against non-temporal engines that produce 0% valid walks. The cooperative scheduler delivers measurable end-to-end gains on hub-skewed temporal graphs by bounding per-launch work cost. Tempest opens a path to walk-native temporal embedding methods that consume causal walks directly, which we are pursuing in ongoing work. Source code and a Python package will be made publicly available upon acceptance.
References
[1] Ferenc Béres, Domokos M. Kelen, Róbert Pálovics, and András A. Benczúr. 2019. Node Embeddings in Dynamic Graphs. Appl. Netw. Sci. 4, 1 (2019), 1–27. [2] 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. Proc. VLDB Endow. 17, 3 (2023), 455–468. [3] Anurag Dutt, Doseok Jang, Joao Nadkarni, Kai Su, and Anshul Gandhi. 2025. GUIDE: GNN-based Unified Incident Detection for Microservices Application Deployments. In Proc. of IEEE ICDCS. [4] Jessica Enright, Kitty Meeks, and Hendrik Molter. 2025. Counting Temporal Paths. Algorithmica 87, 3 (2025), 736–782. [5] Ping Gong, Renjie Liu, Zunyao Mao, Zhenkun Cai, Xiao Yan, Cheng Li, Minjie Wang, and Zhuozhao Li. 2023. gSampler: General and Efficient GPU-based Graph Sampling for Graph Learning. In Proc. of ACM SOSP. [6] Xiangyang Gou and Lei Zou. 2021. Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges. In Proc. of ACM SIGMOD. [7] William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In Proc. of NeurIPS. [8] Mark Harris. 2007. Optimizing Parallel Reduction in CUDA. NVIDIA Developer Technology. [9] Petter Holme and Jari Saramäki. 2012. Temporal networks. Phys. Rep. 519, 3 (2012), 97–125. [10] Chengying Huan, Yongchao Liu, Heng Zhang, Shuaiwen Song, Santosh Pandey, Shiyang Chen, Xiangfei Fang, Yue Jin, Baptiste Lepers, Yanjun Wu, and Hang Liu. 2024. TEA+: A Novel Temporal Graph Random Walk Engine with Hybrid Storage Architecture. ACM TACO 21, 2 (2024). [11] Chengying Huan, Shuaiwen Leon Song, Santosh Pandey, Hang Liu, Yongchao Liu, Baptiste Lepers, Changhua He, Kang Chen, Jinlei Jiang, and Yongwei Wu. 2023. TEA: A General-Purpose Temporal Graph Random Walk Engine. In Proc. of ACM EuroSys. [12] Shixun Huang, Zhifeng Bao, Guoliang Li, Yanghao Zhou, and J. Shane Culpepper. 2020. Temporal Network Representation Learning via Historical Neighborhoods Aggregation. In Proc. of IEEE ICDE. [13] Shenyang Huang, Farimah Poursafaei, Jacob Danovitch, Matthias Fey, Weihua Hu, Emanuele Rossi, Jure Leskovec, Michael Bronstein, Guillaume Rabusseau, and Reihaneh Rabbany. 2023. Temporal Graph Benchmark for Machine Learning on Temporal Graphs. In Proc. of NeurIPS. [14] Abhinav Jangda, Sandeep Polisetty, Arjun Guha, and Marco Serafini. 2021. Accelerating Graph Sampling for Graph Machine Learning Using GPUs. In Proc. of ACM EuroSys. [15] Ming Jin, Yuan-Fang Li, and Shirui Pan. 2022. Neural temporal walks: motifaware representation learning on continuous-time dynamic graphs. In Proc. of NeurIPS.
[16] Nina Klobas, George B. Mertzios, and Paul G. Spirakis. 2023. Sliding into the Future: Investigating Sliding Windows in Temporal Graphs. In Proc. of MFCS. [17] Jérôme Kunegis. 2013. KONECT: The Koblenz Network Collection. In Proc. of ACM WWW Companion. [18] Shutian Luo, Huanle Xu, Kejiang Ye, Guoyao Xu, Liping Zhang, Guodong Yang, and Chengzhong Xu. 2022. The Power of Prediction: Microservice Auto Scaling via Workload Learning. In Proc. of ACM SoCC. [19] Yang Luo, Mohan Gao, Zhemeng Yu, Haoyuan Ge, Xiaofeng Gao, Tengwei Cai, and Guihai Chen. 2024. Integrating System State into Spatio Temporal Graph Neural Network for Microservice Workload Prediction. In Proc. of ACM KDD. [20] Mehrdad Mahdavi, Saeed Khoshraftar, and Aijun An. 2018. dynnode2vec: Scalable Dynamic Network Embedding. In Proc. of IEEE BigData. [21] Junyi Mei, Shixuan Sun, Chao Li, Cheng Xu, Cheng Chen, Yibo Liu, Jing Wang, Cheng Zhao, Xiaofeng Hou, Minyi Guo, Bingsheng He, and Xiaoliang Cong. 2024. FlowWalker: A Memory-Efficient and High-Performance GPU-Based Dynamic Graph Random Walk Framework. Proc. VLDB Endow. 17, 8 (2024), 1788–1801. [22] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S. Corrado, and Jeffrey Dean. 2013. Distributed Representations of Words and Phrases and their Compositionality. In Proc. of NeurIPS. [23] Giang Hoang Nguyen, Jae-Gil Lee, Ryan A. Rossi, Nesreen K. Ahmed, Eunyee Koh, and Sungpack Kim. 2018. Continuous-Time Dynamic Network Embeddings. In Proc. of ACM WWW Companion. [24] NVIDIA Corporation. 2012. CUDA C Best Practices Guide. Technical Report. NVIDIA. [25] NVIDIA Corporation. 2024. CUB: A Flexible Library of Cooperative Threadblock Primitives. https://github.com/NVIDIA/cccl/tree/main/cub. [26] Santosh Pandey, Lingda Li, Adolfy Hoisie, Xiaoye S. Li, and Hang Liu. 2020. C-SAW: A Framework for Graph Sampling and Random Walk on GPUs. In Proc. of SC. [27] Jinhyeon Park, Bumsoo Song, Yongseok Shin, Hyeonseong Kim, Sungpack Hong, and Jinha Lee. 2026. FlexiWalker: Extensible GPU Framework for Efficient Dynamic Random Walks with Runtime Adaptation. In Proc. of ACM EuroSys. [28] Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. 2020. Temporal Graph Networks for Deep Learning on Dynamic Graphs. In Proc. of ICML. [29] Jiaxin Shi, Youyang Yao, Rong Chen, Haibo Chen, and Feifei Li. 2016. Fast and Concurrent RDF Queries with RDMA-based Distributed Graph Exploration. In Proc. of USENIX OSDI. [30] Gagan Somashekar, Anurag Dutt, Mainak Adak, Tania Lorido Botran, and Anshul Gandhi. 2024. GAMMA: Graph Neural Network-Based Multi-Bottleneck Localization for Microservices Applications. In Proc. of ACM WWW. [31] Benjamin A. Steer, Felix Cuadrado, and Richard G. Clegg. 2017. Raphtory: Decentralised Streaming for Temporal Graphs. In Proc. of ACM DEBS. [32] Shixuan Sun, Yuhang Chen, Shengliang Lu, Bingsheng He, and Yuchen Li. 2021. ThunderRW: An In-Memory Graph Random Walk Engine. Proc. VLDB Endow. 14, 11 (2021), 1992–2005. [33] Keita Suzuki, Kenta Ishiguro, and Kenji Kono. 2024. Balancing Analysis Time and Bug Detection: Daily Development-Friendly Bug Detection in Linux. In Proc. of USENIX ATC. [34] Visa Inc. 2024. Visa Annual Report 2024. https://investor.visa.com. [35] Pinhuan Wang, Chengying Huan, Zhibin Wang, Chen Tian, Yuede Ji, and Hang Liu. 2025. Bingo: Radix-based Bias Factorization for Random Walk on Dynamic Graphs. In Proc. of ACM EuroSys. [36] Pengyu Wang, Chao Li, Jing Wang, Taolei Wang, Lu Zhang, Jingwen Leng, Quan Chen, and Minyi Guo. 2021. Skywalker: Efficient Alias-method-based Graph Sampling and Random Walk on GPUs. In Proc. of IEEE PACT. [37] Rui Wang, Yongkun Li, Hong Xie, Yinlong Xu, and John C. S. Lui. 2020. GraphWalker: An I/O-efficient and Resource-friendly Graph Analytic System for Fast and Scalable Random Walks. In Proc. of USENIX ATC. [38] Xinshi Wang, Dingxian Zhang, Da Zheng, Alex Smola, and Le Song. 2021. Inductive Link Prediction on Temporal Graphs via Causal Anonymous Walks. In Proc. of ICLR. [39] Brian Wickman, Hong Hu, Insu Yun, DaeHee Jang, JungWon Lim, Sanidhya Kashyap, and Taesoo Kim. 2021. Preventing Use-After-Free Attacks with Fast Forward Allocation. In Proc. of USENIX Security. [40] Huanhuan Wu, Yuzhen Huang, James Cheng, Jinfeng Li, and Yiping Ke. 2016. Reachability and Time-based Path Queries in Temporal Graphs. In Proc. of IEEE ICDE. [41] Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. 2020. Inductive Representation Learning on Temporal Graphs. In Proc. of ICLR. [42] Wentao Xu, Weiqing Liu, Chang Xu, Jiang Bian, Jian Yin, and Tie-Yan Liu. 2021. REST: Relational Event-driven Stock Trend Forecasting. In Proc. of ACM WWW. [43] Ke Yang, Xiaosong Ma, Saravanan Thirumuruganathan, Kang Chen, and Yongwei Wu. 2021. Random Walks on Huge Graphs at Cache Efficiency. In Proc. of ACM SOSP. [44] Ke Yang, MingXing Zhang, Kang Chen, Xiaosong Ma, Yang Bai, and Yong Jiang. 2019. KnightKing: A Fast Distributed Graph Random Walk Engine. In Proc. of ACM SOSP.