Source-linked AI summary
Breaking Predictions Is Not Enough: Specified-Foil Counterfactuals for Temporal Graphs
Minwoo Yu, Young-guk Ha
TL;DR
Temporal graph counterfactual explanations often change or invalidate a prediction without specifying its replacement. This paper searches for low-cost past-event interventions that make a fixed foil top-ranked, using executable traces and exact replay; it retains most black-box CTDG successes with substantially fewer evaluations and reaches the foil in 74.8% of TKG comparisons.
Problem
Existing temporal counterfactual explanations primarily invalidate the original prediction while leaving the replacement unspecified, despite multiple competing future outcomes.
Method
Trace-guided intervention search contrasts completed and reconstructed executions, maps their differences to temporal edits, and verifies the specified foil through exact replay.
Results
85.7–93.6% of black-box greedy CTDG successes were retained with 75–80% fewer predictor evaluations, while the foil was reached in 74.8% of 600 TKG comparisons.
Takeaways & Limitations
Executable traces can function as computational structures for constructing conditions of alternatives rather than only explaining completed predictions.
Takeaways & Limitations
The model-level interventions and minimality guarantees are limited to the stated candidate space and two-edit budget, without establishing real-world causal prescriptions.
Abstract
from arXiv · showhide
Temporal graph counterfactual explanations typically change past events to change or invalidate an original prediction, while leaving its replacement unspecified. Yet a user facing a predicted outcome often asks which past conditions would make a particular alternative occur instead. We formulate this destination-specific question as the Specified-Foil Counterfactual: given an original prediction A and a foil B fixed before search, find a low-cost past-event intervention under which the same predictor selects B as top-ranked. Our trace-guided intervention search contrasts the completed execution of A with a reconstructed incomplete execution of B, maps their difference to DELETE, INSERT, REWIRE, RELABEL, and SHIFT operations, and verifies B through exact replay. We instantiate this principle with LiFTER on continuous-time dynamic graphs and TLogic on temporal knowledge graphs. On CTDGs, the method retains 85.7-93.6% of black-box greedy successes while reducing predictor evaluations by 75.0-80.0%; on TKGs, it reaches the specified foil in 74.8% of 600 comparisons. Executable traces thereby become computational structures for constructing conditions of unselected alternatives, rather than records used only to explain predictions already made.
1 INTRODUCTION
The paper distinguishes changing or invalidating a predicted outcome from making a specified alternative top-ranked. It formulates this destination-specific task and uses executable traces to construct and verify low-cost temporal interventions across CTDGs and TKGs.
- Motivation: Specified-Foil Counterfactuals require past-event changes that make a prespecified foil B top-ranked, whereas invalidation only removes A without controlling the replacement.Every specified-foil success also invalidates A, but invalidating A does not generally select B.
- Motivation: 4,008 CTDG invalidations reached Rank-5 and Rank-10 foils in only 3.6% and 1.4% of cases, while none of 122 TKG invalidations reached either foil.These results show that changing the original prediction does not generally navigate to a specified alternative.
- Method: Trace-guided search contrasts a completed execution of A with an incomplete reconstruction of B, maps their differences to five temporal edit types, and verifies B by exact replay.The operations are DELETE, INSERT, REWIRE, RELABEL, and SHIFT.
- Contribution: The study connects TKG and CTDG counterfactual research by treating executable traces as structures for synthesizing conditions of an unselected alternative.The same principle is instantiated with LiFTER-based CTDGs and TLogic-based TKGs.
- Results: 85.7–93.6% of black-box greedy successes were retained on CTDGs while predictor evaluations fell 75–80%; on TKGs, the foil was reached in 74.8% of 600 comparisons.Within bounded spaces, the method also recovered 74.9–91.4% of CTDG solutions and 97.9–100% of TKG exhaustive solutions using approximately 9% and 16.6% of evaluations, respectively.
- Results: DELETE alone reached only a subset of CTDG alternatives, while INSERT, REWIRE, SHIFT, and two-edit compositions opened additional solutions.Representative cases include changing a CTDG prediction by deleting one interaction and changing a TKG foil by shifting a negotiation-intent fact three days.
2 RELATED WORK
Prior temporal graph explanation methods mainly recover evidence for an original prediction or interventions that invalidate it. This paper instead supplies the alternative future as input and requires that exact foil to become top-ranked.
- Knowledge-graph foundations: Temporal knowledge-graph work studies fact interventions, hypothetical premises, abductive hypotheses, and executable temporal rules.TKGs represent time-stamped relational quadruples, making relations, entity bindings, and time explicit reasoning variables.
- Existing temporal explainers: Temporal graph explanation has largely focused on factual evidence for an original prediction or removals that invalidate it.T-GNNExplainer and TempME recover relevant factual events, while CoDy and TemGX search for counterfactual removals.
- This paper’s distinction: Specified-Foil Counterfactuals take the alternative future link as input and require that exact foil to become top-ranked under the same predictor.The paper evaluates this objective against black-box output feedback and executable traces.
3 PROBLEM FORMULATION
Specified-Foil Counterfactuals fix an alternative outcome before search and seek past-event changes that make the same temporal predictor select it. The formulation defines executable temporal predictions, admissible edit operators, validity constraints, and bounded reachability.
- 3 PROBLEM FORMULATION: Prediction invalidation only demotes the original outcome, whereas a Specified-Foil Counterfactual requires a prespecified alternative to become top-ranked.With multiple candidate futures, changing the original prediction leaves its replacement unspecified.
- 3.1 Executable Temporal Prediction: The predictor selects the highest-scoring candidate from temporal facts available before query time, covering interaction sequences in CTDGs and time-stamped relational facts in TKGs.The predictor is frozen while scoring candidate outcomes.
- 3.2 Foil Specification and Benchmark Construction: The foil is supplied before intervention search, and benchmark rank constructions control difficulty without replacing user preference or changing the fixed destination.Success requires that the same foil become top-ranked over the full candidate catalog.
- Intervention Space: A CTDG event exposes existence, endpoints, and time, yielding DELETE, INSERT, REWIRE, and SHIFT; TKG relation changes add RELABEL.REWIRE, RELABEL, and SHIFT preserve event correspondence and charge for only the changed coordinate.
- Intervention Space: Interventions modify only admissible history before query time, cannot insert the future query fact, and must satisfy temporal validity, nonleakage, domain, and consistency constraints.Inserted events may support the foil only through past premises.
- Intervention Space: The global objective minimizes intervention cost subject to successful foil selection, while the solver approximates it within a finite candidate space and edit budget.Experimental minimality is therefore local, with a maximum of two edits in the prespecified atomic candidate space.
- Intervention Space: Syntactic admissibility does not guarantee real-world plausibility, so returned interventions are interpreted as model-level counterfactuals rather than causal claims.Domain constraints and expert knowledge may enter candidate filtering without changing exact-replay success.
- 3.4 Operator Coverage Protocol: Operator coverage measures which foils are reachable under a given operator subset and edit budget, distinguishing single-edit reachability from additional compositional reachability.A one-edit REWIRE can be cost-faithful compared with a two-edit deletion–insertion representation.
4 METHOD
Trace-guided intervention search contrasts completed original executions with incomplete foil executions to construct low-cost edits, then verifies the specified foil by exact replay. The method uses executable predictor traces and supports both LiFTER and TLogic through an adapter-style interface.
- 4 METHOD: The method reads the original proof and blocked foil conditions before proposing edits, replacing output-only trial-and-error with execution-guided intervention selection.This reverses black-box search by locating candidate changes from the model’s decision process.
- 4 METHOD: LiFTER supplies grounded interaction executions and TLogic supplies time-consistent rule groundings, while the method adds foil targeting, inverse edit mapping, composition, and exact replay.The quantitative evaluation is limited to LiFTER and TLogic, although the framework is presented as architecture-independent with an adapter.
- 4 METHOD: Trace-guided search constructs candidates from executed original groundings and incomplete foil executions, prioritizing edits expected to reduce the contrastive execution gap.Completed original traces generate disruption candidates, while foil-directed grounding exposes missing premises and endpoint alternatives.
- 4 METHOD: The algorithm uses EXECUTE and REPLAY to obtain the original trace, reconstruct foil-directed candidates, test compositions, and return either a verified intervention or NO LOCAL COUNTERFACTUAL.The procedure evaluates candidates under the specified edit budget and cap.
- 4 METHOD: The solver ranks valid atomic candidates, extends promising ones to bounded nonconflicting compositions, applies them to past facts, and replays the predictor.Success requires the foil to be top-ranked over the full catalog, not merely to gain score or demote the original.
- 4 METHOD: A compatible predictor must expose faithful executions, addressable groundings, foil-queryable execution, and intervention-closed replay.These capabilities connect symbolic proof conditions to concrete past-event edits and recompute scores after intervention.
5 EXPERIMENTS
Experiments evaluate specified-foil reachability, efficiency, exhaustive recovery, stability, ablations, and qualitative transitions across CTDGs and TKGs. Trace-guided search reaches specified alternatives while reducing predictor evaluations, with execution contrast and multiple edit operators contributing to performance.
- 5.2 Specified-Foil Counterfactuals Across Temporal Graphs: CTDG diagnostic reachability averaged 49.9%, 18.7%, and 9.2% for Rank-2, Rank-5, and Rank-10 foils, respectively.As foil rank increased, contributing foil groundings decreased and the positive-support deficit relative to the original increased.
- 5.2 Specified-Foil Counterfactuals Across Temporal Graphs: Adding all four single-edit operators raised CTDG reachability to 43.5%, 12.6%, and 5.9% for Rank-2, Rank-5, and Rank-10 foils.Average coverage increased from 20.6% at budget one to 25.9% at budget two, with 5.3% of comparisons requiring composition.
- 5.4 Search Efficiency: 85.7–93.6% of black-box greedy successes were retained in CTDGs while predictor evaluations fell 75.0–80.0%.In TKGs, trace-guided search retained 95.0–99.2% of successes while reducing evaluations by 59.4–60.0%.
- 5.4 Search Efficiency: Trace-guided search recovered 74.9–91.4% of CTDG exhaustive solutions while reducing evaluations by 91.2–91.6% in fixed candidate spaces.It recovered 46 of 47 ICEWS14 solutions and all 64 ICEWS18 solutions at the same minimum edit count, but these claims do not establish global optimality.
- 5.6 Ablation Study: Complete contrast between original and foil executions raised CTDG target success to 44.8%, compared with 10.0–13.6% using either execution side alone.In TKGs, adding the completed original execution increased success from 56.3% to 64.0% on ICEWS14 and from 82.0% to 85.7% on ICEWS18.
6 CONCLUSION
Specified-Foil Counterfactuals identify low-cost past-event interventions that make a prespecified foil top-ranked, extending temporal counterfactuals beyond merely changing the original answer. Trace-guided search contrasts original and foil executions, verifies the transition by exact replay, and retains most black-box solutions while evaluating fewer candidates.
- Contribution: Specified-Foil Counterfactuals identify a low-cost past-event intervention that makes a prespecified foil B top-ranked instead of the original prediction A.This strengthens prediction invalidation by fixing the desired destination before search.
- Method: Trace-guided search contrasts completed original and reconstructed foil executions, maps their differences to five intervention operators, and verifies the transition through exact replay.The operators are DELETE, INSERT, REWIRE, RELABEL, and SHIFT.
- Results: The method retained most black-box greedy and bounded-exhaustive solutions while evaluating only a fraction of candidates across CTDGs and TKGs.The experiments support both the task’s need and the computational value of execution-based intervention search.
- Scope: These interventions are model-level counterfactuals verified within a frozen predictor, with minimality limited to the stated candidate space and two-edit budget.Domain constraints, event likelihoods, expert knowledge, and causal assumptions can further refine real-world admissibility.
APPENDIX A IMPLEMENTATION AND STATISTICAL DETAILS
The appendix documents dataset sourcing, frozen-model training and evaluation procedures, initialization checks, and foil-construction choices. Rank-controlled foils provide fixed comparison positions across queries, while alternative constructions vary in availability and difficulty.
- Implementation: LiFTER is trained independently of counterfactual search and frozen during intervention experiments, using AdamW for 10 epochs with batch size 512.The reported configuration also specifies learning rate 4 × 10^-3, weight decay 10^-5, dropout 0.1, and maximum history length 128.
- Statistical Details: The main CTDG results use a frozen seed-7 checkpoint, with stability evaluated across seeds 7, 17, and 37 using paired bootstrap and McNemar tests.The paired bootstrap resamples queries while keeping their foils and training seeds together.
- Foil Construction: The appendix compares ground-truth, historical-best, and historical-recent foil constructions by foil distinctness and median pre-intervention rank.These construction statistics are reported in Table 10.
- Foil Construction: Ground truth can coincide with the original prediction and therefore provide no foil, whereas Rank-2/5/10 foils are defined for every query.Among errors, ground-truth foil median rank ranges from 3 to 159 across datasets; historical constructions require sufficient source history.
APPENDIX C SEARCH-WIDTH AND OPERATOR ABLATIONS
Search width improves reachability but eventually saturates, with larger beams sometimes imposing substantial evaluation costs. Ablations show that operator contributions are complementary rather than uniformly important across datasets.
- Search Width: Expanding the TKG beam from 8 to 16 adds only 0.3 percentage points on both datasets while approximately tripling evaluations.In CTDG, the same expansion adds 3.8 points and raises average evaluations from 44.1 to 113.9.
- Operator Ablations: The operator ablation fixes the full candidate set without refilling removed positions, so each value measures solutions uniquely supplied by the removed component.This design isolates component-specific contributions under a common candidate set.
- Operator Ablations: INSERT, REWIRE, and composition contribute unique solutions in both formalisms, while DELETE and SHIFT contribute selectively by dataset.RELABEL adds unique solutions when relations are explicit in TKGs.
D.1 Two-Edit Composition in a CTDG
A CTDG example shows that a specified foil may require composing distinct edits rather than applying one change. Inserting one interaction and rewiring another jointly makes the fifth-ranked item top-ranked.
- Two-Edit Composition: Inserting interaction (1574, 1221) and rewiring an older interaction from item 1172 to 707 makes item 478 top-ranked after no single edit succeeds.LiFTER originally predicts item 1176, while item 478 is ranked fifth.
D.2 Temporal Boundary in a TKG
The TKG counterfactuals identify temporal interventions that make a specified alternative top-ranked. Examples show both insertion of a missing premise and shifting an event across a learned temporal boundary.
- Shifting the relevant fact to September 27 moves Benjamin Netanyahu from ninth to first place.The replay locates this learned temporal boundary beside the observed timeline, without treating the records as causal evidence.
- Inserting one fact one day before the query makes Nigeria top-ranked for Dambazau’s prediction.The inserted Sexually assault relation completes a missing premise in a learned cross-relation rule, making the dependency auditable.
- The replay links each intervention to the predictor’s changed ranking through an auditable execution trace.For the insertion example, the trace explicitly connects the fact, its grounding, and the resulting prediction.
DATA AVAILABILITY
All six study datasets are publicly available, with repository support for obtaining and materializing the experimental inputs.
- All six datasets used in the study are publicly available.The datasets are Wikipedia, Reddit, MOOC, LastFM, ICEWS14, and ICEWS18.
- The repository provides scripts to download source files and materialize processed experimental inputs.
- Dataset URLs are reported in Supplementary Table 7.