TempGraph: An Efficient Chain-driven Temporal Graph Computing Framework on the GPU

A temporal graph has timestamps on its edges, and a valid path must follow them in time order — so finding temporal paths means walking vertices one after another along chains of time dependencies, a stubbornly sequential process that wastes a GPU's thousands of parallel threads; this paper (Huazhong University of Science and Technology, with Warwick and NUS — Jin Zhao, Yu Zhang, Hai Jin, and colleagues) presents TempGraph, which slices the graph into disjoint time-ordered chains that a GPU can race along, then uses shortcuts and a Generate-Activate-Compute model to let many chains run at once — beating the best GPU systems by 3.0 to 16.2 times and a 128-core CPU system by up to 368.9 times.

The argument in one glance

Problem

Time order makes temporal paths stubbornly sequential, and that starves a GPU

A temporal graph is a graph whose edges carry timestamps — a message sent at 9am, a transaction at noon, a contact at 3pm. Many important questions about such graphs are temporal path problems: what is the earliest you can reach one vertex from another, respecting time? Which vertices can a piece of information reach if it can only travel forward in time? The defining rule is that a valid temporal path must follow edges in non-decreasing time order — you cannot take a 9am edge after a noon edge, because you were not there yet. This time constraint is what makes the problem hard to parallelize. To build a temporal path, the vertices must be handled in the order their timestamps allow: you cannot know when you can leave a vertex until you know when you arrived, and that arrival depends on the earlier edges. This creates chains of temporal dependencies between vertices that must be resolved in sequence. GPUs, by contrast, are built for the opposite: thousands of threads doing independent work in parallel, fed by very high memory bandwidth. A workload that insists on processing one dependent step after another exposes almost no parallelism, converges slowly, and leaves the GPU's enormous throughput mostly idle. So the very structure that defines temporal paths fights the hardware best suited to graph analytics.
What people did

Run temporal path algorithms by following the temporal dependencies in order

The established way to solve temporal path problems is to respect the time constraint directly: propagate along the graph following the time-dependent chains, updating each vertex only once the vertices it temporally depends on have been settled, much as classic shortest-path algorithms relax edges in a dependency-respecting order. Whether on a CPU or ported to a GPU, these solutions walk the temporal dependencies sequentially, because that is what the correctness of a temporal path demands.
Why it fell short

Following dependencies in order leaves the GPU idle and convergence slow

Handling the temporal dependencies sequentially is correct but a poor match for the GPU. Because each vertex on a temporal chain must wait for its predecessors along that chain to be resolved before it can be processed, the work available at any instant is small — a long chain is essentially a sequence of dependent steps, not a batch of independent ones. That is exactly the shape of computation GPUs handle worst: their strength is launching thousands of threads on independent data, and a strict dependency order gives them little to launch. The consequence is twofold. Parallelism is poor, so most of the GPU's thousands of cores and its high internal bandwidth sit unused while a few threads inch along a chain. And convergence is slow, because the result cannot settle faster than the longest chain of dependencies can be walked end to end. Naively porting sequential temporal-path methods to the GPU therefore captures little of its power. What was missing was a way to expose the temporal dependencies in a form the GPU can chew through in parallel — to keep the correctness the time order requires while breaking the artificial serialization it seems to impose.
This paper's idea

Cut the graph into disjoint time-ordered chains, and decouple them with shortcuts

TempGraph is a chain-driven, GPU-based temporal graph computing framework that reshapes the problem to fit the hardware. Its first move is to transform the temporal graph into a set of disjoint time-dependent chains: sequences that make the temporal dependency between vertices explicit and, crucially, that a GPU can walk along quickly, because a chain is a regular, predictable structure well-suited to fast path exploration by many threads. This turns the tangled temporal dependencies into clean chains. But the chains still depend on one another — a temporal path can cross from one chain to another — which would reintroduce sequential coupling. So TempGraph's second move is a novel Generate-Activate-Compute (GAC) execution model that decouples the temporal dependency between different chains by maintaining a set of shortcuts for them. The shortcuts let one chain use another chain's progress without waiting for it step by step, so many chains can be processed at the same time by the GPU's massive thread count rather than in a strict sequence. The result is both high parallelism (many chains active at once) and fast convergence (shortcuts let information skip ahead rather than crawl). On an NVIDIA A100 GPU, the paper reports that TempGraph outperforms state-of-the-art GPU-based solutions by 3.0 to 16.2 times, and beats the cutting-edge CPU-based system TeGraph on a 128-core machine by 33.9 to 368.9 times.

Why this problem is worth solving

Temporal path queries answer questions that only make sense with time in them, and they are the backbone of many time-sensitive systems, so making them fast matters broadly.

Ordinary graph paths ignore time, but a great many real questions cannot. When can a disease reach a person through a chain of contacts, given when each contact happened? How quickly can information, or money, flow from one account to another through a sequence of transactions in the order they occurred? What is the fastest route through a transport network whose connections are only available at certain times? Each of these is a temporal path problem, where the timestamps are not decoration but the essence of the answer — a path that ignores the order of events is simply wrong. These queries underpin epidemic analysis, fraud and information-flow tracing, and time-dependent routing, all of which are time-sensitive in a second sense: the answers are often needed quickly, on large and growing graphs. So the value of solving temporal path problems fast is not academic; it is what lets these applications operate at the scale and speed the real world demands. And because the hardware most capable of accelerating graph analytics is the GPU, unlocking the GPU for temporal paths specifically — despite their sequential nature fighting it — is where a large speedup, and thus a real practical difference, is available.

The deeper insight is that the sequential feel of temporal paths is partly real and partly an artifact of how they are computed, and separating the two is what makes GPU acceleration possible.

There is genuine sequentiality in a temporal path: you truly cannot leave a vertex before you arrive. But there is also artificial serialization in the way naive algorithms enforce that constraint, processing everything in one global dependency order and thereby serializing work that need not be serialized. TempGraph’s reframing separates these. By decomposing the graph into disjoint chains, it makes the real temporal dependency explicit and local — within a chain, order matters and is respected — while turning the chain itself into a regular structure the GPU can traverse efficiently. That alone exposes parallelism across chains that a global ordering hid. Then the shortcuts attack the residual coupling: instead of one chain waiting for another to advance one careful step at a time, a shortcut summarizes a stretch of a chain so another chain can jump across it, both decoupling the chains for concurrency and letting results propagate in fewer, bigger steps for faster convergence. This is a general pattern in parallelizing dependency-bound computation: represent the dependencies explicitly, isolate the parts that are truly ordered, and add precomputed shortcuts so the ordered parts can be leapt over rather than crawled through. Applying it to temporal graphs is what converts a workload that looked hostile to the GPU into one that harnesses its thousands of threads.

What people did before, and where it broke

Sequential temporal path propagation. Follow the time-dependent chains, settling each vertex only after the vertices it temporally depends on. Where it broke. The strict dependency order exposes little independent work at any instant, so it is inherently serial and slow.
Porting sequential methods to the GPU. Take these dependency-ordered algorithms and run them on a GPU. Where it broke. The GPU’s thousands of threads have nothing to do while a few crawl along a chain, so its parallelism and bandwidth go mostly unused.
Treating the whole graph under one global order. Enforce the time constraint with a single global dependency ordering. Where it broke. This serializes work that need not be serialized, hiding the parallelism available across independent parts of the graph.
CPU-based temporal graph systems. Solve temporal path problems on multi-core CPUs (such as the state-of-the-art TeGraph). Where it broke. Even a 128-core CPU cannot match the throughput a GPU offers when the workload is reshaped to expose parallelism, leaving large speedups on the table.
The gap. No framework exposed the temporal dependencies in a GPU-friendly form — regular chains plus shortcuts that decouple them — so temporal path problems could not exploit the GPU’s massive parallelism and high bandwidth.

How TempGraph works

From globally-ordered sequential propagation to concurrent chains on the GPU

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Harness the GPU’s thousands of threads for graph traversal. TempGraph is fundamentally about making a graph computation run well on the GPU, exposing enough independent traversal work to keep its cores busy. Reshaping graph traversal so that a GPU’s massive parallelism and bandwidth are actually used, rather than stalled by the graph’s irregularity, is the same GPU-graph-processing goal the work on taming misaligned graph traversals in concurrent processing (Glign) covered elsewhere on this site pursues, aligning irregular graph work to the hardware. TempGraph does this for the specifically hostile case of temporal paths, whose time order resists parallelism most.

Transform the graph’s structure so it computes efficiently. TempGraph does not run the temporal path algorithm on the raw graph; it first transforms the graph into disjoint chains, a representation chosen to expose parallelism and enable fast exploration. Restructuring how a graph is represented so that the same computation runs far better on the target hardware is the same graph-transformation strategy the work on memory optimization via coordinated graph transformation and scheduling (MAGIS) covered elsewhere on this site is built on, reshaping the graph to fit what the hardware does well. TempGraph’s transformation into chains is precisely tuned to turn a sequential temporal dependency into GPU-traversable structure.

Recover parallelism hidden inside a dependency-bound computation. TempGraph’s shortcuts and Generate-Activate-Compute model take a computation that looks strictly sequential and expose the concurrency latent in it. Extracting parallel work from a task whose dependencies appear to force a serial order, by making the dependency structure explicit and decoupling what can run independently, is the same dependency-aware parallelization idea the work on accelerating task-parallel workloads by recovering program structure (TaskStream) covered elsewhere on this site is built on, turning apparent serialization into exploitable parallelism. TempGraph applies it to temporal chains, decoupling them with shortcuts so many run at once.

Following a temporal path query through TempGraph

From an earliest-arrival query to a fast, parallel answer on the GPU

An illustration, at the level the paper's abstract describes, of how TempGraph reshapes and solves a temporal path problem. The full paper was not available for this explainer, so internal mechanism details are omitted.

Step 1 of 5

Pose the temporal path query

A user asks, for instance, for the earliest time each vertex can be reached from a source in a timestamped graph, where a path must follow edges in non-decreasing time. This is the kind of query whose time constraint resists parallelism.

The answer depends on the order of events, not just connectivity.

Why it works

Chains turn tangled dependencies into GPU-traversable structure. Raw temporal dependencies are irregular and hard to parallelize → but decomposing into disjoint, regular chains → so GPU threads can race along each chain efficiently.
Disjoint chains expose parallelism a global order hid. One global dependency ordering serializes independent work → but isolating the truly-ordered parts inside separate chains → so work across chains becomes independent and parallelizable.
Shortcuts decouple chains for concurrency. Chains still depend on each other, reintroducing serial coupling → but summarizing chain stretches as shortcuts → so one chain uses another’s progress without waiting step by step.
Shortcuts speed convergence by skipping ahead. Crawling a long chain end to end is slow → but letting information leap across shortcuts → so results settle in fewer, bigger steps rather than many small ones.
The Generate-Activate-Compute model keeps threads busy. A strict order gives the GPU little to launch → but activating and computing many ready chains at once → so the GPU’s thousands of threads and high bandwidth are actually used.

What it costs (trade-offs and scope)

Building chains and shortcuts is extra work. Transforming the graph into disjoint chains and maintaining shortcuts adds computation and memory that a naive traversal does not have; the design bets, and the results suggest, that this pays for itself in parallelism, but it is not free.
Shortcuts consume memory. Maintaining a set of shortcuts for the chains costs storage, a real consideration on a GPU where memory is limited relative to large temporal graphs.
It targets temporal path problems specifically. TempGraph is built for the class of problems defined by time-respecting paths; it is not a general graph framework, and the chain-plus-shortcut design is tuned to that structure.
Gains depend on the graph’s temporal structure. The benefit of chain decomposition and shortcuts depends on how the graph’s temporal dependencies factor into chains; graphs with very different structure could see different speedups.
This explainer is built from the abstract only. The exact chain-decomposition method, the Generate-Activate-Compute model and shortcut mechanism, the algorithms supported, the datasets, and the conditions behind the reported speedups are in the full paper, which was not available here; only the abstract’s stated design and headline numbers are reported.

The comparison

Solving temporal path problems

Property	Sequential propagation	CPU temporal systems	TempGraph
How temporal dependencies are handled
Parallelism exposed
Convergence speed
Hardware used
Reported speed

A comparison of ways to solve temporal path problems. Sequential propagation follows the temporal dependencies in one global order, exposing little parallelism; CPU-based temporal systems (such as TeGraph) use multiple cores but cannot match GPU throughput. TempGraph decomposes the graph into disjoint time-dependent chains that GPU threads traverse fast, and uses a Generate-Activate-Compute model with shortcuts to decouple the chains so many run concurrently — outperforming state-of-the-art GPU solutions by 3.0 to 16.2 times and TeGraph on a 128-core CPU by 33.9 to 368.9 times on an NVIDIA A100. Exact figures should be read from the paper.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based only on the paper’s abstract and TLDR (obtained via Semantic Scholar); the full text was not available — the paper is behind the ACM Digital Library, its arXiv listing could not be found, and the Warwick institutional-repository copy was access-restricted at the time of writing, so this page is marked a draft. What is reported here is what the abstract states: temporal path problems require handling a temporal graph’s vertices sequentially along time-dependent chains, which gives poor parallelism and slow convergence and prevents existing solutions from exploiting the GPU. TempGraph is a chain-driven, GPU-based temporal graph computing framework that transforms the temporal graph into a set of disjoint time-dependent chains exposing the temporal dependency while facilitating fast path exploration on the GPU, and employs a novel Generate-Activate-Compute execution model that decouples the temporal dependency between different chains by maintaining a set of shortcuts, enabling many chains to be processed concurrently by GPU threads for high parallelism and fast convergence. On an NVIDIA A100 GPU, the abstract reports that TempGraph outperforms state-of-the-art GPU-based solutions by 3.0 to 16.2 times and gains 33.9 to 368.9 times speedups over the cutting-edge CPU-based system TeGraph on a 128-core CPU machine. Everything beyond these claims — the exact chain-decomposition algorithm, the Generate-Activate-Compute model and shortcut design, the specific temporal path problems solved, the datasets, and the detailed results — is not contained in the abstract and should be read in the full paper. Background on temporal graphs, temporal paths, and GPU graph processing is standard context, and the step-by-step walkthrough is an illustration at the abstract’s level, not a verbatim trace of the paper’s mechanism.

Background

Why graph processing keeps wrestling irregular work onto parallel hardware

It helps to see TempGraph within the long effort to run graph analytics fast on modern parallel hardware. Graphs are the awkward case for machines built to love regularity: their connections are irregular, their memory accesses scattered, and their algorithms often carry dependencies that resist being spread across many cores. A great deal of systems research is therefore about reshaping graph computations so that parallel hardware — multi-core CPUs, and especially GPUs with their thousands of threads and high bandwidth — can be fully used. The recurring moves are to transform the graph or its traversal into a more regular form, to expose the independent work hidden by a naive ordering, and to add structure that lets computation skip ahead rather than crawl. Temporal graphs, where edges carry time and paths must respect it, are among the hardest cases, because the time constraint adds a strict ordering on top of the usual irregularity. This drive to make graph analytics on evolving, time-stamped data efficient despite its inherent awkwardness is the same terrain the work on graph analytics on evolving data (CommonGraph) covered elsewhere on this site occupies, coping with graphs that change over time. TempGraph’s particular contribution is to show that even the strongly sequential temporal-path problem can be reshaped — into disjoint chains decoupled by shortcuts — so that a GPU’s massive parallelism finally applies, yielding order-of-magnitude speedups.

If you remember only three things

1. A temporal graph has timestamps on its edges, and a temporal path must follow them in non-decreasing time order, which makes temporal path problems (earliest arrival, temporal reachability, and the like) fundamental to time-sensitive applications like epidemic tracing, fraud analysis, and time-dependent routing. But the time constraint forces the vertices to be handled sequentially along chains of temporal dependencies — you cannot know when you can leave a vertex until you know when you arrived — so the work available at any instant is small. This is the worst-case shape for a GPU, whose strength is launching thousands of independent threads: naive temporal-path methods expose little parallelism, converge slowly, and leave the GPU's throughput and high bandwidth mostly idle.
2. TempGraph is a chain-driven, GPU-based framework that reshapes the problem to fit the hardware. First, it transforms the temporal graph into a set of disjoint time-dependent chains that make the temporal dependencies explicit and, being regular ordered structures, let GPU threads race along them for fast path exploration. Second, because chains still depend on one another (a path can cross between them), it uses a novel Generate-Activate-Compute execution model that decouples different chains by maintaining a set of shortcuts — summaries that let one chain use another's progress without stepping through it. This isolates the genuinely-sequential parts inside chains, exposes the parallelism a global ordering hid, and lets many chains run at once across the GPU's massive thread count, while shortcuts let information skip ahead for faster convergence.
3. The key insight is that a temporal path's sequentiality is partly real (you cannot leave before you arrive) and partly an artifact of enforcing the constraint through one global order; decomposing into chains and adding shortcuts separates the two, keeping correctness while breaking the false serialization. On an NVIDIA A100 GPU, the paper reports that TempGraph outperforms state-of-the-art GPU-based solutions by 3.0 to 16.2 times and beats the cutting-edge CPU-based system TeGraph on a 128-core machine by 33.9 to 368.9 times. The trade-offs: building chains and maintaining shortcuts costs extra computation and GPU memory, the design is specialized to temporal path problems, and the gains depend on how the graph's temporal dependencies factor into chains. This explainer is drawn only from the abstract, so the detailed algorithms should be read in the full paper.

Check yourself

Check your understanding

1. Why are temporal path problems hard to parallelize on a GPU?
2. What is TempGraph's first move to make temporal paths GPU-friendly?
3. How does TempGraph let many chains run at once, given that chains still depend on each other?
4. What did TempGraph achieve, and how should this page be read?

Sources

The paper is “TempGraph: An Efficient Chain-driven Temporal Graph Computing Framework on the GPU” by Jin Zhao, Qian Wang, Ligang He, Yu Zhang, Sheng Di, Bingsheng He, Xinlei Wang, Hui Yu, Hao Qi, Longlong Lin, Linchen Yu, Xiaofei Liao, and Hai Jin (Huazhong University of Science and Technology, with the University of Warwick, National University of Singapore, and Argonne National Laboratory among the affiliations), published at ASPLOS 2025, DOI 10.1145/3676642.3736116.

This explainer is written only from the paper’s abstract and TLDR, obtained via the Semantic Scholar API; the full text was not available, because the paper is behind the ACM Digital Library, no arXiv listing could be found, and the Warwick institutional-repository copy was access-restricted at the time of writing. Accordingly this page is marked a draft. The abstract describes TempGraph as a chain-driven, GPU-based temporal graph computing framework that transforms the temporal graph into a set of disjoint time-dependent chains (exposing temporal dependencies while enabling fast GPU path exploration) and employs a novel Generate-Activate-Compute execution model that decouples the temporal dependency between chains by maintaining shortcuts, so many chains run concurrently for high parallelism and fast convergence. On an NVIDIA A100 GPU, the abstract reports outperforming state-of-the-art GPU-based solutions by 3.0 to 16.2 times and gaining 33.9 to 368.9 times speedups over the CPU-based system TeGraph on a 128-core machine. Background on temporal graphs, temporal paths, and GPU graph processing is standard, widely-known context. All quantitative claims are the paper’s own; the internal mechanisms and full evaluation should be confirmed in the paper.