Achieving Efficient Temporal Graph Transformation on the GPU

Temporal graphs, which associate time information with their edges, are fundamental to various time-sensitive applications. To efficiently handle temporal graphs, existing solutions typically apply a transformation-based execution model. This model first transforms the temporal graph into its equivalent Directed Acyclic Graph (DAG) with embedded timing information and then computes this transformed graph using a single-scan strategy. However, due to the intricate vertex expansion based on the timestamps, the temporal graph transformation suffers from high runtime overhead and graph redundancy problem. To overcome these challenges, this paper proposes a redundant-aware temporal graph transformation method on the GPU, called FASTGT. In detail, it detects and merges virtual edges that do not affect the correctness of temporal path problems via temporal path analysis, thereby eliminating graph redundancy. Then, by decoupling the data dependencies among redundancy detection among different virtual edges, it enhances the parallelism of the temporal graph transformation on the GPU. Experiments on an A100 GPU show that FASTGT reduces temporal graph transformation time by up to \(3.2\times \) and \(9.7\times \), while achieving 10% and 50% reductions in GPU global memory usage, compared to TeGraph and OTBC, respectively. Besides, FASTGT achieves up to \(2.0\times \) and \(5.5\times \) improvements in end-to-end performance (i.e., including both temporal graph transformation and computation) over TeGraph and OTBC, respectively.