A GPU Accelerated Temporal Window-Based Random Walk Sampler

Md Ashfaq Salehin, George Parisis, Luc Berthouze · 2026

Read A GPU Accelerated Temporal Window-Based Random Walk Sampler by Md Ashfaq Salehin, George Parisis, Luc Berthouze (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16182.txt.

Introduction

Salehin, Parisis, and Berthouze present Tempest, a GPU engine for streaming temporal random walks over time-stamped interaction graphs. Real graphs arrive as high-volume streams, demanding continuous ingestion, lean memory, and strict temporal order. Tempest pairs a GPU-native dual-index edge store with a hierarchical scheduler that dispatches walks at thread, warp, or block level. It sustains real-time processing of billion-edge streams under sliding windows, beating prior systems on ingestion and walk-generation throughput while preserving causal correctness.

Catalog record

CREATORMd Ashfaq Salehin, George Parisis, Luc Berthouze
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47171
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.16182

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A GPU Accelerated Temporal Window-Based Random Walk Sampler Md Ashfaq Salehin, George Parisis, Luc Berthouze 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 billion-edge 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., u\rightarrow v ), 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 causality-preserving 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 ( 13 ) . 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 ( 23 ; 20 ; 1 ; 38 ; 15 ) . 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 ( 18 ; 19 ; 3 ; 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 ( 36 ; 5 ) and up to 98.8% of execution time in distributed implementations ( 44 ; 26 ) . 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 ( 28 ; 7 ; 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 ( 35 ) , and gSampler ( 5 ) , achieve high throughput on static graphs but do not account for temporality. Dynamic graph engines such as FlowWalker ( 21 ) and Bingo ( 36 ) 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 ( 35 ) , 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 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 streaming-scale execution under bounded memory by efficiently ingesting new edges and evicting outdated ones; this setting is widely studied as sliding window processing ( 6 ; 16 ; 2 ) . 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

Read the complete text