A temporal knowledge graph stores facts that hold at particular times, such as "(Country A, threatens, Country B, 2014-03-02)". Models that learn from these graphs spread information along edges within each time slice and then carry each entity's state forward through time. When such a model is trained across many GPUs, the entities are split among the machines. Every round of spreading information along edges then requires each machine to send the current vectors of its boundary entities to nearly every other machine. This all-to-all exchange is what stops brain simulators and distributed graph networks from scaling. Yet consecutive time slices of real evolving graphs are nearly identical. Consecutive snapshots often share over 99% of their edges (Ren et al.), and most entities in sparse event graphs sit idle for long stretches (TeMP). Most of the bytes sent in each round therefore describe vectors the receiver could have predicted on its own.
We propose co-designing the temporal encoder and its communication protocol so that a machine sends an entity's vector only when something the receiver cannot reconstruct has happened. An idle entity costs zero bytes, because its state evolves by a fixed decay rule that the receiver applies locally and exactly. An active entity whose state barely moves, as happens under the heavy fact repetition in news-event graphs, is sent as a thresholded difference from what the receiver already holds, with the leftover error carried into the next send. The claim is that communication volume should then scale with the number of genuinely new boundary events rather than with the number of boundary entities. We also claim this can be done without hurting link-prediction accuracy on benchmarks built to require real temporal reasoning.
Core Claim and What Is New
The existing bridges between these directions each miss one piece. Efficient Scaling of Dynamic Graph Neural Networks exploits snapshot overlap by sending only edge additions and deletions over the CPU-to-GPU bus, cutting transfer time by up to 4.1x. It compresses topology, handles only single-relation graphs, and removes cross-GPU edge aggregation by splitting along time instead of across entities. DistTGL avoids synchronizing node memory by giving each group of trainers its own full copy for a segment of the timeline. That removes communication by paying memory that grows linearly with the number of groups, and it does not model multi-relational facts. Sparsity-Aware Communication sends only the boundary rows a remote GPU actually needs, but only on static graphs, so it resends the same rows at every step. On the knowledge-graph side, TeMP and TARGCN supply the model family we build on, and both are single-machine methods. TARGCN in particular hits training timeouts on large graphs because of its multi-hop temporal neighbor sampling.
What we add is temporal differencing of learned activations across machines under entity partitioning, made exact for idle entities by choosing an encoder whose idle-state update is a closed-form function. TeMP's imputation already carries forward a decayed copy of an entity's last active representation. We turn that modeling choice into a communication contract. Formally, let $h_v^t$ be entity $v$'s representation at slice $t$ on its owner machine. Let $\hat h_v$ be the copy the receiver last got, at time $t_0$, and let $D(\hat h_v, t - t_0)$ be the shared decay rule. The owner transmits at slice $t$ only if
$$ v \text{ had an event in } (t_0, t] \quad\text{and}\quad \lVert h_v^t + e_v - D(\hat h_v, t-t_0)\rVert > \tau, $$
where $e_v$ is the accumulated unsent residual (error feedback) and $\tau$ is a per-layer threshold. If $v$ had no event, the receiver's reconstruction is exact by construction and no check is needed. Deciding what to skip is therefore driven by structure: the sender knows from its event log that nothing happened, without computing anything. This event-driven logic mirrors the turnover logging of Sun et al., which records state changes instead of polling. The routing of what does get sent borrows the presynaptic routing tables of the NEST 5g kernel (Jordan et al.). Each owner keeps, for each boundary entity, the set of ranks hosting its neighbors, so messages go only to those ranks. Unlike NEST's tables, which are precomputed and break under changing connectivity, ours are updated incrementally from the same event log that drives skipping.
Research Program
The first component is the encoder. We use a relational graph convolution within each slice, followed by a gated recurrent update across slices, in the TeMP style. We constrain the idle-entity path to an exponential decay toward a learned static embedding per entity, echoing DistTGL's hybrid static-dynamic memory. We will verify on a single GPU that this constraint costs little accuracy relative to unconstrained TeMP and TARGCN before any distribution. If it costs a lot, the exact tier fails and the proposal reduces to approximate compression.
The second component is the runtime. Entities are partitioned across machines with a partitioner that balances both total and maximum per-rank volume, as in the Graph-VB design of Sparsity-Aware Communication. Each rank maintains three things: an event log per boundary entity, receiver-side caches of remote representations, and residual buffers. The per-slice exchange becomes a directed all-to-all of variable-size, event-filtered messages. Backpropagation is the subtle part, because gradients for a skipped entity flow into a reconstructed value. For idle entities the reconstruction is an exact function of $\hat h_v$, so gradients are routed back through $D$ to the last sent value. For the thresholded tier we use the straight-through treatment standard in error-feedback compression, and we measure the resulting gradient bias directly against full exchange on small graphs.
The third component is analysis. We will measure how communicated bytes split between the exact tier and the approximate tier, as a function of each dataset's activity rate. The file characterizes GDELT as a graph where almost all entities stay active across consecutive timestamps with strong repetition. That regime is exactly where the exact tier gives little, so any savings there must come from the approximate tier. The ICEWS political-event graphs show TeMP's "quiet periods", so savings there should come mostly from exact skipping. Seeing this split is itself a test of the mechanism.
Baselines
The naive reference point is full boundary exchange. It uses the same encoder and the same entity partition, and every slice sends every needed boundary row, using the sparsity-aware all-to-all of Mukhopadhyay et al.. That paper reports up to 14x speedup on 256 GPUs over sparsity-oblivious exchange, on static graphs only. This baseline is the correct denominator because it already removes the obvious waste, leaving only temporal redundancy for us to exploit. It will be run with identical data, partitions, GPU counts, hyperparameters and number of epochs. Beating it means reaching the same filtered mean reciprocal rank (MRR) within 0.5 points with substantially fewer bytes and lower wall-clock time per epoch; our target is a 3x byte reduction on ICEWS-style data.
The strongest systems competitor is time partitioning with difference-based transfer from Efficient Scaling of Dynamic Graph Neural Networks. We port it to relational graphs by assigning slices to GPUs and shuffling recurrent states, with the graph-difference loading its authors describe. They report 4.1x lower transfer time, a 40% cut in execution time, and 30x speedup from one node to 128 GPUs, on homogeneous graphs. The second strongest is DistTGL's memory parallelism, which reports a 10.17x throughput gain over TGL and a 14.5% accuracy improvement on the 191-million-edge GDELT graph with 32 GPUs (DistTGL). We will run it on the same GDELT data at the same GPU count and report time-to-target-MRR and peak aggregate memory. We will not compare its native accuracy metric against our MRR, since its task is not relational link prediction. For distributed temporal knowledge graph completion itself, there is no reported result found on Lacuna for throughput or scaling, so every distributed number here will be new.
For accuracy we anchor against single-GPU TeMP and TARGCN, and against rule baselines. TeMP reports 8.0% to 10.7% relative Hits@10 gains on ICEWS but loses to the Temporal Exponential Decay rule on GDELT. TARGCN reports over 46% relative MRR improvement on GDELT. No absolute GDELT MRR for either appears in the file, so we will reproduce both under our protocol.
The ablations isolate the key ingredient. The first uses generic top-k activation compression at the same byte budget, with no temporal reference, so the receiver gets the largest coordinates of the current vector rather than a difference against a cache. The second uses random skipping at the same skip rate. The third keeps the exact tier only, and the fourth keeps the thresholded tier only. If the random-skip ablation matches our accuracy, the structural trigger is not doing the work.
Why not just…?
Why not just partition along time, as Chakaravarthy et al. do? This is a real threat for encoders that look only at the current slice plus a recurrent state, because then edge aggregation is local and only recurrent states cross machines. Two things work against it for knowledge graphs. First, TARGCN-style encoders aggregate over neighbors drawn from a window of past slices, so time partitioning must replicate history on every GPU. Second, knowledge graph slices can be small enough that the fixed per-slice recurrent-state shuffle dominates. Our head-to-head at matched GPU counts settles this. We will also report the history-window length at which time partitioning overtakes entity partitioning, and concede that regime if it is where practical models live.
Why not just replicate the whole graph on every GPU and train data-parallel? On ICEWS14 this works, and we treat that dataset as a correctness check rather than a scaling target. It stops working when the entity table and per-slice activations exceed one device, which is where DistTGL already needed 32 GPUs for GDELT. It also stops working when all-reducing gradients for a large entity table becomes the bottleneck. We include a data-parallel baseline and report where it runs out of memory or loses on time-to-accuracy.
Why not just use lower precision or generic gradient and activation compression? Precision reduction is a real lever. Zenke and Gerstner show switching from 64- to 32-bit arithmetic helped simulation speed without changing macroscopic dynamics. It is orthogonal to our method, so we apply it to all baselines alike. Generic top-k compression is the sharper objection. The matched-budget ablation tests whether sending differences against a receiver-side cache beats compressing each vector afresh. We expect it does because the temporal reference absorbs repetition, but that is exactly what the experiment is for.
Why not just use a rule heuristic, since TED and persistence baselines beat deep models on repetitive data? Pan et al. show a trivial rule model matching the best models on leaky ICEWS splits. The Temporal Graph Benchmark reports deep models losing to persistence and moving averages in repetitive streams. If that held everywhere, scaling neural training would be pointless. We therefore evaluate accuracy on leak-free splits. There, Pan et al. report T(NT)ComplEx falling from 60.7 to 48.2 MRR once shortcuts are removed, so real learned structure is still required. We report the rule baseline on every split as a floor.
Proposed Experiments
The datasets are ICEWS14 and ICEWS05-15 (small, sparse, with quiet periods), their leak-free variants ICEWS14RR and ICEWS05-15RR, and GDELT at the 191-million-edge scale used by DistTGL. Metrics are time-aware filtered MRR and Hits@10, bytes sent per epoch broken down by tier, wall-clock time per epoch, time-to-target-MRR, and peak per-GPU and aggregate memory. We scale from 1 to 64 GPUs.
The first decisive check is on the leak-free splits. The approximate tier trades freshness for bytes, and a stale cache could quietly push the model toward the repetition shortcuts Pan et al. warn about. If our MRR drops by more than about a point on the leak-free splits while holding steady on leaky ones, the savings come at the cost of genuine temporal reasoning. We would then report that and narrow the method to the exact tier.
The second check is the regime split. Exact skipping should supply most savings on ICEWS and thresholded differences most savings on GDELT. If GDELT shows no savings at all, the method only helps sparse graphs, which are the ones small enough not to need it, and the proposal fails its purpose.
The third check is the random-skip and top-k ablations at matched budgets. If either matches our accuracy-bytes curve, the temporal and structural reference is not the operative ingredient.
References
- On Querying Historical Evolving Graph Sequences
- TeMP: Temporal Message Passing for Temporal Knowledge Graph Completion
- Efficient scaling of dynamic graph neural networks
- DistTGL: Distributed Memory-Based Temporal Graph Neural Network Training
- Sparsity-Aware Communication for Distributed Graph Neural Network Training
- A Simple But Powerful Graph Encoder for Temporal Knowledge Graph Completion
- Beyond Prediction: On-Street Parking Recommendation Using Heterogeneous Graph-Based List-Wise Ranking
- Extremely Scalable Spiking Neuronal Network Simulation Code: From Laptops to Exascale Computers
- Limits to high-speed simulations of spiking neural networks using general-purpose computers
- Do Temporal Knowledge Graph Embedding Models Learn or Memorize Shortcuts?
- Temporal Graph Benchmark for Machine Learning on Temporal Graphs