Time-Travel Counterfactuals: Explaining Temporal Graph Models Beyond the Window

Temporal graph networks are neural models that predict future interactions, such as who will edit which page or which account will transact next. They do this by keeping a running memory vector for every node, and that vector is updated each time the node takes part in an event. A prediction made today can therefore depend on an interaction from months ago, passed along through a chain of memory updates. The tools that explain these predictions all look backward only a short distance. They ask "which past events, if deleted, would change this prediction?" but consider only events inside a fixed recent window, or they unroll the memory only a few steps. So they cannot even pose the question for old events.

We propose to make old events explainable by exact replay. We save the model's node memories at regular intervals, the way database versioning systems save a snapshot plus a log of changes. To test a deleted event, we restore the nearest saved state and recompute only the nodes that event could have reached. Most candidate events cannot matter, so a cheap score decides which ones are worth replaying. The score combines how much the event changed its own endpoints' memories (local) with how widely that change could have travelled through later time-ordered paths to the node being explained (global). The first question the work must answer is empirical and could kill the idea: how much of a memory-based model's counterfactual dependence actually lies outside the window that current explainers use?

Core Claim

For memory-based temporal graph models, a meaningful share of the events whose deletion flips or strongly shifts a prediction lie outside the standard explanation window. Exact counterfactual replay can be made affordable for events of any age by two ingredients. The first is checkpointed model state with cone-restricted recomputation. The second is a local-to-global influence score that orders candidate events before replay. The result is explanations with higher fidelity at equal sparsity than window-bounded explainers, at comparable wall-clock cost.

This differs from the closest work in specific ways. TemGX scores events with Independent Cascade probabilities, a temporal effective resistance distance, and time decay, then selects greedily. It is restricted to a fixed sliding window, and it treats the graph as an in-memory event list. We keep the idea of a structural influence score but use it only as a filter, and we verify every selected event by exact replay with no age limit. MemExplainer reaches into history by propagating relevance scores back through the memory update function. That is a gradient-style approximation whose tree branches exponentially, and the authors cap it at depth 10. Our replay is an actual counterfactual forward pass and scales with the number of affected nodes, not with tree depth. CoDy runs a tree search over deletions guided by local proximity and recency heuristics, so its candidate set is small by construction. Versioning systems such as CAVE and GLENDA show that "snapshot plus deltas" reconstruction of any historical graph state is practical at scale. They never connect it to a model's internal state or to explanation. We borrow their storage pattern and apply it to the model's memory rather than to raw data.

Research Program

The central quantity is the counterfactual effect of an old event $e$ on a prediction $f_i(t)$ for target node $i$ at time $t$. It is $\Delta_i(e) = f_i(t) - f_i^{\setminus e}(t)$, where $f_i^{\setminus e}$ is the model's output after deleting $e$ and replaying all later memory updates. Deleting $e = (u, v, t_e)$ perturbs only the memories of $u$ and $v$ at time $t_e$. That perturbation can spread only along time-respecting paths, meaning sequences of later events, each after the previous one, starting from $u$ or $v$. The set of events that must be recomputed is therefore the forward temporal cone of $e$. We restore the saved memory checkpoint preceding $t_e$ and replay only events inside the cone. The cost is proportional to the cone's size, not to the history length. Checkpoints are spaced by a tunable number of events, which bounds the replay-start overhead exactly as periodic snapshots bound delta-chain length in GLENDA.

Replaying every old event is still too expensive, so candidates are ranked by a score that fuses a local and a global term:

$$ s_i(e) = \big(\lVert m_u - m_u^{\setminus e} \rVert + \lVert m_v - m_v^{\setminus e} \rVert\big) \cdot R_\gamma(e \to i, t) $$

Here $m_u$ and $m_u^{\setminus e}$ are node $u$'s memory immediately after $t_e$ with and without the event, which takes one memory-update step from the checkpoint. $R_\gamma(e \to i, t)$ counts time-respecting paths from $u$ or $v$ to $i$ within $(t_e, t]$. Each path is discounted by $\gamma$ per intervening memory overwrite, because each later update partially replaces what the memory held. $R_\gamma$ can be computed for all candidates at once with one reverse-chronological sweep from $i$. This is the temporal analogue of the hybrid centralities in network science. Those scores exist because purely local measures such as degree are blind to reach, while coarse global measures such as $K$-shell collapse thousands of nodes into ties (KPDN–INCC, NIRM). Our score is target-specific and time-ordered, which static centralities are not.

The explainer selects greedily. It takes the top-scored candidates across the entire history, verifies each by exact replay, and keeps the smallest set that flips or maximally shifts the prediction. It is post hoc and needs no training.

We build this as an extension of the TGN codebase used by DyGLib and the ST-TGExplainer repository. The replay engine checks correctness against full recomputation from scratch.

We also note a secondary consequence without making it the core claim. Because checkpoints are indexed by when events were recorded, the same machinery can explain a prediction against the state the model actually saw, rather than a later corrected log. This is the valid-time versus transaction-time distinction stressed in Jensen's letter and in real-time COVID-19 indicators.

Baselines

The naive reference points are a random-event explainer and a recency-only explainer that deletes the most recent events touching the target. The random baseline matters because Probing GNN Explainers found that a random-edge baseline often has lower unfaithfulness than GNNExplainer and GraphMASK. Beating random at matched sparsity is a floor, not a result.

The strongest existing competitor is TemGX, because it is training-free, counterfactual, and already uses a composite structural influence score. On UCIM with a TGN backbone it reports a fidelity of 0.468, stated as 6.5x TGNNExplainer and 113% better than TempME (TemGX). We run it with its published window, and again with the window enlarged until its wall-clock time matches ours. Beating it means higher fidelity at equal explanation size under the same time budget, on UCI and at least two of Wikipedia, Reddit, and USLegis.

CoDy is the strongest search-based competitor. It reports a 16% AUFSC+ gain over its strongest rival (CoDy). We have no absolute AUFSC+ value from Lacuna, so we will report our own reproduction under a matched forward-pass budget.

MemExplainer is the strongest method that already reaches into history. It reports statistically significant Fidelity-KL gains in 77% of cases across nine datasets. We run it at its capped depth of 10 and at a depth matched to our compute.

Two ablations isolate our ingredients, each run with the same number of verification replays. The first swaps our score for alternatives: recency, degree, static $K$-shell, TemGX's score, and the local term or global term alone. The second removes the window constraint from TemGX's own scoring while keeping our replay. That tells us whether gains come from reach or from the score.

Why not just…?

Why not just widen TemGX's window? This is the most direct threat, and the matched-budget run above tests it. Widening the window increases candidates linearly. Without cone-restricted replay, each verification costs a forward pass over the whole window, and TemGX's scores were designed for nearby events. If widened TemGX matches us at equal time, then our contribution reduces to engineering and we will say so.

Why not just backpropagate relevance through memory, as MemExplainer does? Relevance propagation estimates contribution; it does not execute the deletion. The input to the memory update is nonlinear, so relevance and true counterfactual effect can disagree. The depth cap of 10 also means events further back are never scored. We will measure the rank correlation between MemExplainer's relevance and exact replay effects on old events. Low correlation would justify replay.

Why not just rank by recency or degree? Recency is a real threat, because memory overwriting may make old events matter only through a few paths. The score ablation tests this directly. If recency matches the hybrid score, we drop the global term. HIA found that bridge and high-growth nodes were much better attack targets than established hubs. That suggests degree will underperform, but it is attack evidence, not explanation evidence.

Why not just recompute from scratch without checkpoints? It is exact but costs one full-history pass per candidate. On tgbl-comment (over 30 million timestamps, per TGB) that is infeasible. We will report speedup against full replay on the smaller datasets.

Proposed Experiments

The first decisive check measures how much counterfactual dependence lies outside the window. For TGN on Wikipedia, Reddit, UCI-Messages, and USLegis, we sample predictions and compute exact replay effects for all events in each target's full backward cone, which is affordable on the smaller datasets. We report the fraction of total counterfactual effect carried by events outside TemGX's window. TGAT serves as a control: it has no memory and samples recent neighbors, so its outside-window share should be near zero. If TGN's share is also negligible, the premise fails and the project stops.

Second, we build a synthetic benchmark in the spirit of the planted-motif graphs used by CF-GNNExplainer. A trigger event is planted in UCI-like streams, and a later label depends on it by construction, at controlled delays beyond the window. This gives ground truth for whether each explainer recovers the true cause as the delay grows.

Third, we run the main comparison on real data. Metrics are fidelity as defined by TemGX, AUFSC+, explanation size, and wall-clock time per explanation, all against the baselines above. The Wikipedia and Reddit runs also report scaling with history length.

Finally, a stability check responds to the reasoning-overfitting finding in Evaluating Attribution for GNNs. We explain the same prediction from models saved at different training epochs and measure explanation overlap, testing whether full-history explanations drift less than window-bounded ones.