Breaking Predictions Is Not Enough: Specified-Foil Counterfactuals for Temporal Graphs

# Breaking Predictions Is Not Enough: Specified-Foil Counterfactuals for Temporal Graphs
Source: [https://arxiv.org/html/2609.11170](https://arxiv.org/html/2609.11170)
Young\-guk Ha††thanks:M\. Yu and Y\.\-g\. Ha are with the Smart Computing Laboratory, Department of Computer Science & Engineering, Konkuk University, Seoul 05029, Republic of Korea\. E\-mail: \{snowypainter, ygha\}@konkuk\.ac\.kr\. Y\.\-g\. Ha is the corresponding author\.

###### Abstract

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 theSpecified\-Foil Counterfactual: given an original predictionAAand a foilBBfixed before search, find a low\-cost past\-event intervention under which the same predictor selectsBBas top\-ranked\. Our trace\-guided intervention search contrasts the completed execution ofAAwith a reconstructed incomplete execution ofBB, maps their difference to DELETE, INSERT, REWIRE, RELABEL, and SHIFT operations, and verifiesBBthrough 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\.

###### Index Terms:

Temporal graph learning, counterfactual explanation, contrastive explanation, neuro\-symbolic reasoning, temporal knowledge graph\.

## IIntroduction

Predictions over evolving graphs select one outcome from multiple possible futures\. Temporal graph learning studies this problem through two major formalisms\. Temporal knowledge graphs \(TKGs\) represent time\-stamped relational facts and logical rules, whereas continuous\-time dynamic graphs \(CTDGs\) model streams of interactions and predict future links\. Yet how past events would need to differ for a particular alternativeBB, rather than the predicted futureAA, has not been directly addressed\.

Counterfactual explanations seek small input changes under which the same predictor selects an alternative outcome\. Human explanation requests are often contrastive: they compare a fact with a foil\[[1](https://arxiv.org/html/2609.11170#bib.bib2),[2](https://arxiv.org/html/2609.11170#bib.bib1)\]\. In temporal link prediction, where many outcomes compete, changing the original prediction and selecting a desired alternative are distinct objectives\. We study model\-level counterfactuals verified within the temporal world learned by a frozen predictor\. Extending such answers to real\-world causal counterfactuals requires an explicit causal model and corresponding identification assumptions\[[3](https://arxiv.org/html/2609.11170#bib.bib3)\]\.

Existing temporal counterfactual explainers primarily implement*prediction invalidation*\. CoDy defines success as changing the original future\-link prediction through past\-event removal\[[4](https://arxiv.org/html/2609.11170#bib.bib15)\]; TemGX similarly identifies a temporal subgraph whose removal changes the original prediction\[[5](https://arxiv.org/html/2609.11170#bib.bib16)\]\. The quantitative evaluation of CTM\-Explainer also centers on deletion\-based event selection and changes in the original score\[[6](https://arxiv.org/html/2609.11170#bib.bib17)\]\. We use prediction invalidation to denote this class of objectives, which identifies events on which the original prediction depends while leaving its replacement unspecified\. OnceAAloses the top rank, the selection ofBB,CC, or any other outcome satisfies the same criterion\.

Consider a temporal event graph that predicts the next state of a soldier on a battlefield\. If the model predictsdeath, prediction invalidation identifies past events whose removal eliminates that prediction\. The replacement, however, could becritical injury,missing, or another state\. Specifyingsurvivalas the foil asks a sharper question:*what would have had to differ for the model to predict survival rather than death?*Suppose the completed death execution followsenemy exposure→\\rightarrowgunshot→\\rightarrowdelayed evacuation→\\rightarrowdeath, while an incomplete survival execution lackstimely evacuation\. A corresponding answer may remove the gunshot event, shift the evacuation time, or change the binding of medical support\. The result is a counterfactual explanation verified within the predictor, rather than a causal prescription that guarantees survival in the real world\.

We formulate this question as theSpecified\-Foil Counterfactualproblem for temporal graph learning across TKGs and CTDGs\. Given an original predictionAAand a foilBBfixed before search, the task identifies past\-event changes that make the same predictor selectBBinstead ofAA\. Every successful specified\-foil intervention also invalidatesAA, whereas an intervention that invalidatesAAneed not selectBB\. The explicit destination therefore strengthens temporal counterfactual explanation from changing the current answer to constructing the conditions for a particular alternative\.

This distinction matters because future\-link prediction is inherently multi\-alternative\. In our controlled invalidation study, interventions that ignored the foil changedAAin 4,008 CTDG cases, yet reached the prespecified Rank\-5 and Rank\-10 foils in only 3\.6% and 1\.4% of those cases, respectively\. In TKGs, none of the 122 successful invalidations reached the Rank\-5 or Rank\-10 foil\. ChangingAAcan promote a nearby runner\-up, but it does not generally navigate to a specified alternative\. An explicit foil makes it possible to measure which past\-event changes separateAAfromBB, whetherBBis locally reachable, and how much that transition costs\. The task thus characterizes the reachability and boundary of an alternative future represented by the model\.

The stronger objective substantially enlarges black\-box search\. Without access to internal execution, an explainer must propose an edit, rerun the predictor, observe the output, and repeat\. Even prediction invalidation has required locality constraints, temporal influence and event\-impact heuristics, and Monte Carlo Tree Search to identify removal sets\. A specified foil further introduces insertions and alternative endpoints and timestamps\. A black\-box method can verify a solution through sufficient computation, but it must discover that solution by exploring the input space from output feedback alone\.

Executable neuro\-symbolic predictors provide a different route\. Their traces expose the grounded facts, entity bindings, and temporal conditions that establish the original prediction\. Re\-grounding rules toward the foil can also reconstruct partial executions and reveal their missing conditions\. Ourtrace\-guided intervention searchcontrasts the completed execution of the original with the reconstructed incomplete execution of the foil, maps their difference to DELETE, INSERT, REWIRE, RELABEL, and SHIFT operations, and then exactly replays the predictor on the edited event set to verify that the foil becomes top\-ranked\.

As reviewed in Section[II](https://arxiv.org/html/2609.11170#S2), prior work has separately developed fact intervention and abduction in KGs, executable temporal reasoning in TKGs, and factual explanation and prediction invalidation in CTDGs\. We connect these lines through temporal interventions between an original prediction and a specified foil\. Our contributions are as follows:

- •We formulate theSpecified\-Foil Counterfactualproblem uniformly for TKGs and CTDGs, combining an original predictionAA, a specified foilBB, admissible past\-event interventions, and exact\-replay success in a single objective\.
- •We derive DELETE, INSERT, REWIRE, RELABEL, and SHIFT from the existence, endpoint, relation, and time coordinates of temporal events, and define intervention cost and bounded minimality\.
- •We introducetrace\-guided intervention search, which maps the difference between a completed original execution and a reconstructed incomplete foil execution into temporal edits\. Grounded traces thereby become a computational interface for synthesizing the conditions of an alternative\.
- •We instantiate the same principle independently in LiFTER\-based CTDGs and TLogic\-based TKGs, and evaluate reachability, target specification, search efficiency, exhaustive recovery, stability, and execution\-level case studies\.

A symbolic trace is not merely a by\-product used to explain a prediction; it is an executable structure from which interventions otherwise guessed by post\-hoc search can be constructed directly\.

Across 12,000 CTDG comparisons, DELETE alone reached only a subset of the specified alternatives; INSERT, REWIRE, SHIFT, and two\-edit compositions opened additional solutions\. Trace\-guided intervention search retained 85\.7–93\.6% of the successes obtained by black\-box greedy search while reducing predictor evaluations by 75–80%\. Within bounded spaces that permitted exhaustive enumeration, it recovered 74\.9–91\.4% of the discovered solutions using approximately 9% of the evaluations\. Across 600 TKG comparisons on ICEWS14 and ICEWS18, the method reached the specified foil in 74\.8% of cases and recovered 97\.9–100% of the exhaustive solutions using approximately 16\.6% of the evaluations\. The shared behavior of CTDG interaction traces and TKG relational proof paths supports execution inversion as a general principle of executable temporal reasoning rather than a mechanism specific to LiFTER’s scoring function\.

Section[V\-G](https://arxiv.org/html/2609.11170#S5.SS7)traces representative solutions through their executions\. One CTDG case changes the predicted learning content after deleting a single past interaction; one TKG case changes the predicted consultation partner from Moon Jae\-in to Benjamin Netanyahu after shifting the time of a negotiation\-intent fact by three days\.

## IIRelated Work

### II\-ACounterfactual and Contrastive Explanations

Counterfactual explanations identify small input changes that lead a predictor to an alternative outcome\[[1](https://arxiv.org/html/2609.11170#bib.bib2),[2](https://arxiv.org/html/2609.11170#bib.bib1)\]\. Reversing a binary decision determines its alternative automatically\. In multiclass and structured prediction, however, a foil must be specified because several replacements are possible\. We bring this distinction to temporal graph prediction, where multiple future links compete\. Our explanations are model\-level interventions verified by a frozen predictor; causal claims about the real world additionally require a causal model and identification assumptions\[[3](https://arxiv.org/html/2609.11170#bib.bib3)\]\.

### II\-BCounterfactual Reasoning over Knowledge Graphs

Knowledge\-graph research has studied explicit interventions on facts\. Pezeshkpour et al\. search for single\-fact additions and deletions that alter link predictions\[[7](https://arxiv.org/html/2609.11170#bib.bib4)\]\. Imagine generates plausible triples that change the rank of a target triple\[[8](https://arxiv.org/html/2609.11170#bib.bib5)\]\. CFKGR inserts hypothetical premises and evaluates facts derived from them through logical rules\[[9](https://arxiv.org/html/2609.11170#bib.bib6)\]\. Abductive reasoning instead infers logical hypotheses capable of explaining observed conclusions\[[10](https://arxiv.org/html/2609.11170#bib.bib7)\]\. These lines provide foundations for fact intervention, target\-directed modification, and inverse reasoning\. We combine them with an original–foil contrast to identify past\-event interventions that establish a specified future link\.

### II\-CExecutable Reasoning in Temporal Knowledge Graphs

TKGs represent facts as quadruples\(s,r,o,t\)\(s,r,o,t\), making relations, entity bindings, and time explicit reasoning variables\. TLogic extracts rules from temporal random walks and predicts future facts through time\-consistent grounding\[[11](https://arxiv.org/html/2609.11170#bib.bib8)\]\. TILP learns recurrence, temporal order, intervals, and duration within differentiable temporal rules\[[12](https://arxiv.org/html/2609.11170#bib.bib9)\]\. TFLEX combines logical operators over entities with temporal operators\[[13](https://arxiv.org/html/2609.11170#bib.bib10)\]; TEILP predicts event times from rule\-satisfying events and time intervals\[[14](https://arxiv.org/html/2609.11170#bib.bib11)\]; and INFER incorporates temporal validity and frequency into neural\-symbolic rule application\[[15](https://arxiv.org/html/2609.11170#bib.bib12)\]\. These models explicitly execute the facts, bindings, and temporal conditions underlying a prediction\. We use that execution structure to construct edits from a completed original grounding and an incomplete foil grounding\.

### II\-DExplanations for Continuous\-Time Dynamic Graphs

CTDG explainability has focused on identifying past events relevant to a future\-link prediction\. T\-GNNExplainer searches for factual event subsets that preserve the original prediction\[[16](https://arxiv.org/html/2609.11170#bib.bib13)\], while TempME explains predictions through temporal motifs\[[17](https://arxiv.org/html/2609.11170#bib.bib14)\]\. Among counterfactual methods, CoDy restricts candidate events through spatio\-temporal vicinity and heuristic policies, then applies MCTS to find a removal set that changes the original prediction\[[4](https://arxiv.org/html/2609.11170#bib.bib15)\]\. TemGX ranks removable temporal subgraphs using structural influence and time decay before verifying the prediction change\[[5](https://arxiv.org/html/2609.11170#bib.bib16)\]\. CTM\-Explainer conceptualizes both removal and synthetic addition, while its quantitative evaluation centers on deletion\-based selection and changes in the original score\[[6](https://arxiv.org/html/2609.11170#bib.bib17)\]\.

T\-GNNExplainer and TempME recover factual evidence for an original prediction; CoDy and TemGX recover counterfactual removals that invalidate it\. Specified\-Foil Counterfactuals instead receive the alternative future link as input and require that exact foil to become top\-ranked\. We therefore evaluate the empirical distinction between invalidation and specified\-foil success, and compare black\-box output feedback with executable traces under the same specified\-foil objective\.

## IIIProblem Formulation

Temporal prediction scores multiple possible futures and selects one\. Changing the original prediction therefore does not determine the destination of a counterfactual\. Suppose a model predicts deteriorationAAas a patient’s next state\. Removing a past event may demoteAA, but the replacement may be stable stateBBor another complicationCC\. Prediction invalidation accepts either outcome, whereas a question about stability is answered only by an intervention that selectsBB\.

The distinction resembles breaking a route versus constructing one to a specified destination\. Prediction invalidation succeeds by disrupting any path toAA\. A Specified\-Foil Counterfactual first fixes destinationBBand seeks the closest change that connects the current temporal facts to it\. This may require DELETE to remove support forAA, INSERT to supply a fact missing fromBB, REWIRE to alter an entity binding, or SHIFT to satisfy a temporal condition\. The foil is therefore an input that determines the counterfactual question, rather than an auxiliary evaluation label\.

### III\-AExecutable Temporal Prediction

LetF<TqF\_\{<T\_\{q\}\}denote the temporal facts available before query timeTqT\_\{q\}, and letY∈𝒴qY\\in\\mathcal\{Y\}\_\{q\}denote a candidate outcome for queryqq\. In a CTDG,F<TqF\_\{<T\_\{q\}\}is a continuous interaction sequence andYYis a future destination\. In a TKG, they correspond to time\-stamped relational quadruples and a candidate object for\(s,r,?,Tq\)\(s,r,?,T\_\{q\}\)\. A frozen predictor assigns scores⁡\(q,Y,F<Tq\)s\(q,Y;F\_\{<T\_\{q\}\}\)and returns

Y^=arg⁡maxY∈𝒴q⁡s⁡\(q,Y,F<Tq\)\.\\hat\{Y\}=\\arg\\max\_\{Y\\in\\mathcal\{Y\}\_\{q\}\}s\(q,Y;F\_\{<T\_\{q\}\}\)\.\(1\)
LiFTER additionally exposes grounded rule executions and signed contributions, whereas TLogic exposes time\-consistent rule groundings and temporal rule scores\. Given predictionY^Δ\\hat\{Y\}^\{\\Delta\}after interventionΔ\\Delta, the two success conditions are

Prediction invalidation:Y^Δ≠Y^,\\displaystyle\\hat\{Y\}^\{\\Delta\}\\neq\\hat\{Y\},\(2\)Specified\-Foil:Y^Δ=Yfoil\.\\displaystyle\\hat\{Y\}^\{\\Delta\}=Y^\{\\mathrm\{foil\}\}\.\(3\)
The conditions coincide in a binary problem\. With multiple candidate links, however,Y^Δ≠Y^\\hat\{Y\}^\{\\Delta\}\\neq\\hat\{Y\}leaves the replacement unspecified, whereas the specified\-foil condition identifies it exactly\.

### III\-BFoil Specification and Benchmark Construction

A foilYfoil∈𝒴q∖\{Y^\}Y^\{\\mathrm\{foil\}\}\\in\\mathcal\{Y\}\_\{q\}\\setminus\\\{\\hat\{Y\}\\\}is supplied with the query rather than selected by the solver during search\. In applications, a downstream user, domain expert, or decision process specifies the alternative of interest\. Existing temporal graph benchmarks provide no such user\-intent annotation\. We therefore compared ground\-truth destinations, each source’s historical\-best and historical\-recent destinations, and prediction\-rank constructions\. Ground\-truth and historical constructions were available only for subsets of queries and induced inconsistent difficulty across datasets\. Rank\-based construction applies to every query and controls difficulty at a common model\-relative position\. We consequently use Rank\-2, Rank\-5, and Rank\-10 as near, intermediate, and distant benchmark foils\. Supplementary Section[B](https://arxiv.org/html/2609.11170#A2)reports the complete comparison\.

Ykfoil=Rankk⁡\{s⁡\(q,Y,F<Tq\)∣Y∈𝒴q\},k∈\{2,5,10\}\.Y\_\{k\}^\{\\mathrm\{foil\}\}=\\operatorname\{Rank\}\_\{k\}\\\{s\(q,Y;F\_\{<T\_\{q\}\}\)\\mid Y\\in\\mathcal\{Y\}\_\{q\}\\\},\\qquad k\\in\\\{2,5,10\\\}\.\(4\)
Rank in Eq\. \([4](https://arxiv.org/html/2609.11170#S3.E4)\) controls model\-induced benchmark difficulty; it does not substitute for user preference\. The solver accepts any user\-specified destination in the candidate catalog, irrespective of rank\. Each benchmark foil is fixed before intervention, and success requires that same foil to become top\-ranked over the full catalog after intervention\.

### III\-CContrastive Counterfactual Reasoning

Letefoil=Link⁡\(X,Yfoil,Tq\)e^\{\\mathrm\{foil\}\}=\\operatorname\{Link\}\(X,Y^\{\\mathrm\{foil\}\},T\_\{q\}\)denote the future link associated with the specified destination\. The task asks which small changes to the past would make the model predictefoile^\{\\mathrm\{foil\}\}instead ofe^\\hat\{e\}\.

#### Intervention Space

We derive intervention operators from the coordinates used by each temporal formalism\. A CTDG interactionε=\(u,v,t\)\\varepsilon=\(u,v,t\)exposes event existence, endpoint, and timestamp\. DELETE removes an existing event, INSERT adds one, REWIRE changes an endpoint while preserving event identity, and SHIFT changes its timestamp\. Thus,

𝒪CTDG=\{DELETE,INSERT,REWIRE,SHIFT\}\.\\mathcal\{O\}\_\{\\mathrm\{CTDG\}\}=\\\{\\mathrm\{DELETE\},\\mathrm\{INSERT\},\\mathrm\{REWIRE\},\\mathrm\{SHIFT\}\\\}\.
A TKG eventε=\(s,r,o,t\)\\varepsilon=\(s,r,o,t\)adds relationrras an independent semantic coordinate\. RELABEL changes this coordinate while preserving subject, object, and timestamp:

𝒪TKG=𝒪CTDG∪\{RELABEL\}\.\\mathcal\{O\}\_\{\\mathrm\{TKG\}\}=\\mathcal\{O\}\_\{\\mathrm\{CTDG\}\}\\cup\\\{\\mathrm\{RELABEL\}\\\}\.
For example,\(A,Consult,B,t\)→\(A,Threaten,B,t\)\(A,\\mathrm\{Consult\},B,t\)\\rightarrow\(A,\\mathrm\{Threaten\},B,t\)is naturally one RELABEL rather than an unrelated deletion–insertion pair\. DELETE and INSERT can express any finite event\-set transformation, but decomposing\(u,v,t\)→\(u,v′,t\)\(u,v,t\)\\rightarrow\(u,v^\{\\prime\},t\)into both operations charges two edits and discards the semantics of changing one endpoint\. REWIRE, RELABEL, and SHIFT preserve event correspondence and charge only for the coordinate that changes\. SWAP is represented as two SHIFTs when timestamps determine event order\. The resulting operators cover the observable event coordinates of both formalisms at faithful atomic costs\.

Every intervention uses only history available at query time\. DELETE, REWIRE, RELABEL, and SHIFT modify facts inF<TqF\_\{<T\_\{q\}\}; INSERT and SHIFT assign timestamps strictly beforeTqT\_\{q\}\. Endpoints and relations belong to the predictor’s admissible domains, and conflicting edits to the same fact are excluded\. The future query fact\(X,r,Yfoil,Tq\)\(X,r,Y^\{\\mathrm\{foil\}\},T\_\{q\}\)cannot be inserted into history\. An insertion may supply a past premise supporting the foil, but never copy the target future fact itself\.

LetΔ\\Deltabe a composition of atomic operations,F<TqΔ=Δ⁡\(F<Tq\)F\_\{<T\_\{q\}\}^\{\\Delta\}=\\Delta\(F\_\{<T\_\{q\}\}\)the edited event set, andC⁡\(Δ\)C\(\\Delta\)its cost\. PredicateVVenforces temporal validity, target nonleakage, domain admissibility, and edit consistency\. The global objective is

Δ∗\\displaystyle\\Delta^\{\*\}=arg⁡minΔ⁡C⁡\(Δ\)\\displaystyle=\\arg\\min\_\{\\Delta\}C\(\\Delta\)\(5\)s\.t\.V⁡\(Δ,F<Tq\)\\displaystyle\\text\{s\.t\.\}\\quad V\(\\Delta,F\_\{<T\_\{q\}\}\)=1,\\displaystyle=1,\(6\)arg⁡maxY∈𝒴q⁡s⁡\(qY,F<TqΔ\)\\displaystyle\\arg\\max\_\{Y\\in\\mathcal\{Y\}\_\{q\}\}s\(q\_\{Y\};F\_\{<T\_\{q\}\}^\{\\Delta\}\)=Yfoil\.\\displaystyle=Y^\{\\mathrm\{foil\}\}\.\(7\)
Equation \([7](https://arxiv.org/html/2609.11170#S3.E7)\) defines the global problem; our solver approximates it within a finite local candidate set and edit budgetτ\\tau\. Experimental minimality therefore holds within the prespecified atomic candidate space and a maximum of two edits\. A foil reached within this space has a*local counterfactual*; otherwise the solver returnsNo Local Counterfactual Within the Searched Space\. Exact execution onF<TqΔF\_\{<T\_\{q\}\}^\{\\Delta\}reveals which original\-supporting groundings disappear and which foil\-supporting groundings emerge\.

Syntactic admissibility does not alone establish real\-world plausibility\. An INSERT or REWIRE over valid entities and relations may remain rare or infeasible in a particular domain\. We therefore interpret returned interventions as model\-level counterfactuals and allow domain constraints, event likelihoods, and expert knowledge to enter throughVVduring candidate filtering\. Exact\-replay success remains unchanged\.

A CTDG case illustrates the targeted condition\. LiFTER predicted content59935993as student348348’s next interaction, and content66596659, initially ranked fifth, was fixed as the foil\. Deleting the earlier interaction\(348,5981\)\(348,5981\)reduced the original logit from4\.464\.46to3\.123\.12and increased the foil logit from2\.132\.13to3\.573\.57, making66596659top\-ranked\. The removed event participated in a two\-event transition contributing\+1\.39\+1\.39to the original and−1\.39\-1\.39to the foil\. Its deletion simultaneously removed support for the original and suppression of the foil\. The example shows why targeted reasoning must compare the signed executions of both candidates rather than merely remove influential evidence for the original\.

### III\-DOperator Coverage Protocol

For operator subsetA⊆𝒪A\\subseteq\\mathcal\{O\}and budgetτ\\tau, define the reachable queries as

ℛ\(A,τ\)=\{q\|∃Δ∈⟨A⟩,C\(Δ\)≤τ,Y^Δ=Yfoil\}\.\\mathcal\{R\}\(A,\\tau\)=\\left\\\{q\\;\\middle\|\\;\\exists\\Delta\\in\\langle A\\rangle,\\ C\(\\Delta\)\\leq\\tau,\\ \\hat\{Y\}^\{\\Delta\}=Y^\{\\mathrm\{foil\}\}\\right\\\}\.
Atτ=1\\tau=1, this set measures single\-edit coverage;τ≥2\\tau\\geq 2captures additional reachability from composition\. Operator\-specific solutions are

𝒰o​\(τ\)=ℛ⁡\(𝒪,τ\)∖ℛ⁡\(𝒪∖\{o\},τ\)\.\\mathcal\{U\}\_\{o\}\(\\tau\)=\\mathcal\{R\}\(\\mathcal\{O\},\\tau\)\\setminus\\mathcal\{R\}\(\\mathcal\{O\}\\setminus\\\{o\\\},\\tau\)\.
This difference measures the budget\-relative necessity of operatoroowithin a finite admissible space\. Although DELETE and INSERT are representationally complete, a foil reachable by one REWIRE but only by a two\-edit deletion–insertion pair demonstrates the cost\-faithful value of REWIRE\. We estimate coverage in the diagnostic study and verify operator contributions through fixed\-candidate ablations and bounded exhaustive search\.

## IVMethod

Section[V\-B](https://arxiv.org/html/2609.11170#S5.SS2)shows that Specified\-Foil Counterfactuals require more than DELETE and often require compositions of edits\. Enumerating all edits produces a search space over past events, candidate endpoints, relations, and timestamps\. We instead proposetrace\-guided intervention search, which maps the execution difference between the original and the foil back to event interventions\.

The method changes the direction of computation\. Black\-box search first proposes an edit and then reruns the predictor to test whether it produces the foil\. Our method first reads the rule execution that produced the original and the unsatisfied conditions that blocked the foil, then constructs edits that close this execution gap\. It identifies where to intervene from the model’s decision process rather than discovering that location solely through repeated output feedback\.

LiFTER and the present contribution play distinct roles\. LiFTER\[[18](https://arxiv.org/html/2609.11170#bib.bib20)\]is a forward predictor that returns future\-link scores, grounded rule executions, and signed contributions\. It neither defines a user\-specified foil nor returns an intervention for reaching one\. We introduce the original–foil input, the inverse mapping from grounded execution differences to edits, low\-cost composition, and foil\-targeted exact replay\. LiFTER serves as an executable backbone on which this inverse computation can be implemented and verified\.

This construction strengthens the question addressed by XAI\. Prediction invalidation succeeds whenever the original ceases to be selected\. A Specified\-Foil Counterfactual requires the same intervention to make a prespecified foil exactly top\-ranked\. The former leaves the destination open; the latter asks for the conditions under which one particular alternative is established\. A grounded trace consequently becomes a computational interface for synthesis: the completed original proof identifies conditions to break, and the reconstructed incomplete foil proof identifies conditions to complete\.

The task remains definable for a black\-box predictor: edit past events and replay the model until the foil becomes top\-ranked\. The available signal, however, is limited to the output of each trial\. Even for deletion\-only invalidation, CoDy restricts candidates through spatio\-temporal vicinity and uses heuristic policies with Monte Carlo Tree Search\[[4](https://arxiv.org/html/2609.11170#bib.bib15)\], while TemGX combines temporal reachability, structural influence, and time decay before verification\[[5](https://arxiv.org/html/2609.11170#bib.bib16)\]\. Specifying a foil expands the candidate space to insertions and alternative endpoints, relations, and timestamps\.

Figure[1](https://arxiv.org/html/2609.11170#S4.F1)summarizes our alternative\. The original trace identifies the events and bindings responsible for its score\. Rules grounded toward the foil reveal near\-complete executions and their missing conditions\. The solver maps this contrast directly to candidate edits and verifies each selected composition by exact replay\.

Fig\. 1:Trace\-guided intervention search reads the completed original execution and the incomplete foil execution, constructs edits from their difference, and verifies the specified foil through exact replay\.For an executable predictor, write the score of candidateYYas the sum of signed contributionsαz\\alpha\_\{z\}from grounded executionszz:

s⁡\(qY,F\)\\displaystyle s\(q\_\{Y\};F\)=bY\+∑z∈𝒵⁡\(Y,F\)αz,\\displaystyle=b\_\{Y\}\+\\sum\_\{z\\in\\mathcal\{Z\}\(Y;F\)\}\\alpha\_\{z\},\(8\)D⁡\(F\)\\displaystyle D\(F\)=s⁡\(qY^,F\)−s⁡\(qYfoil,F\)\.\\displaystyle=s\(q\_\{\\hat\{Y\}\};F\)\-s\(q\_\{Y^\{\\mathrm\{foil\}\}\};F\)\.\(9\)
The contrastive execution gapD⁡\(F\)D\(F\)in Eq\. \([9](https://arxiv.org/html/2609.11170#S4.E9)\) is initially positive\. For atomic interventionδ\\delta, define its gain by

R⁡\(δ\)=D⁡\(F\)−D⁡\(Fδ\)\.R\(\\delta\)=D\(F\)\-D\(F^\{\\delta\}\)\.\(10\)
EvaluatingR⁡\(δ\)R\(\\delta\)for every possibleδ\\deltarecovers exhaustive search\. Instead, we construct a candidate setΓ⁡\(𝒯orig,𝒯~foil\)\\Gamma\(\\mathcal\{T\}\_\{\\mathrm\{orig\}\},\\widetilde\{\\mathcal\{T\}\}\_\{\\mathrm\{foil\}\}\)from the executed original groundings𝒯orig\\mathcal\{T\}\_\{\\mathrm\{orig\}\}and the incomplete foil executions𝒯~foil\\widetilde\{\\mathcal\{T\}\}\_\{\\mathrm\{foil\}\}\. These traces identify edits expected to yield large gap reductions before replay\.

The intuition is route planning with a specified destination\. Invalidation can succeed by breaking the current route anywhere\. A specified\-foil intervention must reach a particular destination\. Overlaying the route that reached the original with a route that stops immediately before the foil exposes the junctions that should change\. Grounded executions are routes, past events are the conditions that open them, and interventions modify the junctions separating them\.

From completed original executions, we generate DELETE and SHIFT candidates targeting events on which active support depends\. From foil\-directed rule grounding, we reconstruct executions missing one fact or entity binding and generate INSERT and REWIRE candidates\. RELABEL plays the analogous role for the relation coordinate in TKGs\. For ordered transitions, endpoint alternatives are inferred from their expected effect on the foil–original margin\. All operators instantiate one principle: they are atomic edits that reduce the difference between a completed original proof and an incomplete foil proof\.

Candidates are ranked by their estimated reduction of Eq\. \([10](https://arxiv.org/html/2609.11170#S4.E10)\), and the topKKare retained\. Let⟨TopK⁡\(Γ\)⟩\\langle\\operatorname\{TopK\}\(\\Gamma\)\\rangledenote their valid compositions within the budget\. The bounded solver computes

Δ∗\\displaystyle\\Delta^\{\*\}=arg⁡minΔ∈⟨TopK⁡\(Γ\)⟩⁡C⁡\(Δ\)\\displaystyle=\\arg\\min\_\{\\Delta\\in\\langle\\operatorname\{TopK\}\(\\Gamma\)\\rangle\}C\(\\Delta\)\(11\)s\.t\.arg⁡maxY∈𝒴q⁡s⁡\(qY,FΔ\)\\displaystyle\\text\{s\.t\.\}\\quad\\arg\\max\_\{Y\\in\\mathcal\{Y\}\_\{q\}\}s\(q\_\{Y\};F^\{\\Delta\}\)=Yfoil\.\\displaystyle=Y^\{\\mathrm\{foil\}\}\.\(12\)
The solver evaluates atomic interventions before extending promising candidates to low\-cost compositions\. Duringexact replay, it appliesΔ\\Deltato the past facts and recomputes temporal order, bindings, groundings, contributions, and all candidate scores\. An increased foil score or a demoted original is insufficient; success requiresYfoilY^\{\\mathrm\{foil\}\}to be top\-ranked over the full catalog\. The method therefore consists of execution contrast, candidate generation, cost\-aware composition, and exact replay\.

### IV\-AAlgorithm and Model Requirements

Algorithm[1](https://arxiv.org/html/2609.11170#alg1)presents the complete procedure\.ExecuteandReplayform the interface between an executable predictor and the intervention solver\. Candidate priority approximates Eq\. \([10](https://arxiv.org/html/2609.11170#S4.E10)\), and replay evaluates the exact condition in Eq\. \([12](https://arxiv.org/html/2609.11170#S4.E12)\)\.

Algorithm 1Trace\-guided intervention search1:facts

FF, query

qq, foil

BB, operators

𝒪\\mathcal\{O\}, cap

KK, budget

τ\\tau
2:

S←Replay​\(F,q\)S\\leftarrow\\textsc\{Replay\}\(F,q\);

A←arg⁡maxY⁡S⁡\(Y\)A\\leftarrow\\arg\\max\_\{Y\}S\(Y\)
3:

𝒯A←Execute​\(F,q,A\)\\mathcal\{T\}\_\{A\}\\leftarrow\\textsc\{Execute\}\(F,q,A\)
4:

𝒯~B←NearMisses​\(F,q,B\)\\widetilde\{\\mathcal\{T\}\}\_\{B\}\\leftarrow\\textsc\{NearMisses\}\(F,q,B\)
5:

Γ←BreakOrRelease​\(𝒯A,𝒪\)\\Gamma\\leftarrow\\textsc\{BreakOrRelease\}\(\\mathcal\{T\}\_\{A\},\\mathcal\{O\}\)
6:

Γ←Γ∪Complete​\(𝒯~B,𝒪\)\\Gamma\\leftarrow\\Gamma\\cup\\textsc\{Complete\}\(\\widetilde\{\\mathcal\{T\}\}\_\{B\},\\mathcal\{O\}\)
7:

Γ←TopKValid​\(Γ,K\)\\Gamma\\leftarrow\\textsc\{TopKValid\}\(\\Gamma,K\)
8:for

Δ\\Deltain nonconflicting compositions of

Γ\\Gammawith

C⁡\(Δ\)≤τC\(\\Delta\)\\leq\\taudo

9:

FΔ←Apply​\(F,Δ\)F\_\{\\Delta\}\\leftarrow\\textsc\{Apply\}\(F,\\Delta\)
10:

SΔ,𝒯Δ←Replay​\(FΔ,q\)S\_\{\\Delta\},\\mathcal\{T\}\_\{\\Delta\}\\leftarrow\\textsc\{Replay\}\(F\_\{\\Delta\},q\)
11:if

arg⁡maxY​SΔ​\(Y\)=B\\arg\\max\_\{Y\}S\_\{\\Delta\}\(Y\)=Bthen

12:return

Δ,𝒯Δ\\Delta,\\mathcal\{T\}\_\{\\Delta\}
13:endif

14:endfor

15:returnNoLocalCounterfactual

The method requires no dedicated architecture\. A compatible predictor must expose or reconstruct four capabilities:

1. 1\.Faithful execution:traces represent rules, programs, or grounded computations that actually determine candidate scores rather than post\-hoc attributions\.
2. 2\.Addressable grounding:each execution identifies its supporting past facts, entity bindings, and temporal conditions, allowing symbolic conditions to map back to concrete edits\.
3. 3\.Foil\-queryable execution:inference can be run for an arbitrary foil to recover completed support and partial executions with identifiable missing conditions\.
4. 4\.Intervention\-closed replay:the same inference engine accepts edited events and recomputes temporal order, bindings, groundings, and full\-catalog scores\.

LiFTER provides grounded interaction executions directly\. TLogic\[[11](https://arxiv.org/html/2609.11170#bib.bib8)\]permits completed executions and foil near\-misses to be reconstructed from time\-consistent groundings and rule\-body prefixes\. We implement the algorithm in both\. TILP\[[12](https://arxiv.org/html/2609.11170#bib.bib9)\]also explicitly represents learned temporal rules, variable groundings, and temporal constraints, suggesting structural compatibility; our quantitative evaluation is limited to LiFTER and TLogic\.

Future models need not implement four new modules\. An adapter suffices if it locates facts used by existing proof paths, executes rule bodies toward a foil to identify blocked premises, and reapplies inference to edited facts\. Models exposing only original support can generate disruption candidates; models exposing partial foil executions support the complete method\. The problem and exact\-replay criterion apply to any temporal predictor, while executable traces replace output\-driven proposal with execution inversion\.

## VExperiments

The experiments test a single chain of claims\. We first establish specified\-foil reachability with LiFTER and TLogic, then quantify why target specification and a multi\-operator intervention space are necessary\. Efficiency and exhaustive comparisons test whether traces concentrate valid edits, ablations isolate the execution signals and search components responsible for performance, and case studies reconstruct complete prediction transitions\.

### V\-AExperimental Setup

CTDG experiments use LiFTER with the public Wikipedia, Reddit, MOOC, and LastFM interaction datasets\[[19](https://arxiv.org/html/2609.11170#bib.bib18)\]\. For each dataset, we use the most recent 70,000 events, training on the first 85% and evaluating on the final 15%\. Each query receives only preceding events, and its candidate catalog contains every destination in the same window\. TKG experiments use the official TLogic implementation\[[11](https://arxiv.org/html/2609.11170#bib.bib8)\]with ICEWS14 and ICEWS18\[[20](https://arxiv.org/html/2609.11170#bib.bib19)\]\. In both formalisms, foil selection and replay success are evaluated over the full candidate catalog rather than sampled negatives\.

##### Frozen predictor\.

LiFTER is trained independently of counterfactual search and frozen for every intervention\. Main results use seed 7; stability is evaluated with independently trained checkpoints for seeds 7, 17, and 37\. Hyperparameters and statistical procedures appear in Supplementary Section[A](https://arxiv.org/html/2609.11170#A1)and Tables[VIII](https://arxiv.org/html/2609.11170#A1.T8)–[IX](https://arxiv.org/html/2609.11170#A1.T9)\.

##### Queries and foils\.

The main CTDG diagnostic and efficiency experiments select 1,000 rows evenly across each 10,500\-event evaluation stream\. Rank\-1 is the original prediction, and Rank\-2, Rank\-5, and Rank\-10 are fixed as foils before search, yielding 3,000 comparisons per dataset and 12,000 overall\. Bounded exhaustive comparisons and ablations use 100 queries per dataset fixed before observing outcomes\. TKG experiments likewise combine 100 queries per dataset with three rank\-controlled foils, producing 300 comparisons each\.

Before adopting rank control, we evaluated the ground\-truth destination and two historical constructions\. Their definitions, availability, and median ranks are reported in Supplementary Section[B](https://arxiv.org/html/2609.11170#A2)and Table[X](https://arxiv.org/html/2609.11170#A2.T10)\.

Fig\. 2:Ground\-truth and historical foils are available only for subsets of queries and induce dataset\-dependent difficulty\. Rank\-controlled foils cover every query at fixed model\-relative positions\.Figure[2](https://arxiv.org/html/2609.11170#S5.F2)shows that rank control provides complete availability and comparable model\-relative difficulty\. This construction is a benchmark device, not a restriction on application\-time foils; the solver accepts any destination in the catalog\.

### V\-BSpecified\-Foil Counterfactuals Across Temporal Graphs

We first measure whether specified foils are reachable through at most two small fact edits\. The CTDG diagnostic uses coordinate\-based candidates to isolate operator and budget effects; the subsequent efficiency experiment uses foil\-specific candidates generated from execution contrast\. The two experiments share queries, foils, budget, and seed, while answering different questions with different candidate generators\.

##### Continuous\-time dynamic graphs\.

The diagnostic constructs DELETE, INSERT, REWIRE, and SHIFT candidates from the 24 most recent query\-relevant events, up to 16 endpoints, and eight timestamp alternatives, then tests two\-edit compositions of the top four candidates per operator\. Table[I](https://arxiv.org/html/2609.11170#S5.T1)reports average reachability of 49\.9%, 18\.7%, and 9\.2% for Rank\-2, Rank\-5, and Rank\-10 foils\.

TABLE I:Bounded diagnostic reachability on continuous\-time dynamic graphs\.DatasetRank\-2Rank\-5Rank\-10OverallWikipedia21\.2%6\.3%2\.4%10\.0%Reddit20\.2%5\.2%1\.1%8\.8%MOOC82\.5%28\.4%12\.5%41\.1%LastFM75\.8%34\.9%20\.6%43\.8%Average49\.9%18\.7%9\.2%25\.9%

As the foil moves from Rank\-2 to Rank\-10, the number of contributing foil groundings decreases in every dataset and the positive\-support deficit relative to the original increases\. The overlap between past\-event rows used by the two executions remains nearly constant\. Distant foils are therefore associated with weaker executable support within similar event pools, making the three ranks meaningful difficulty strata\.

DELETE alone reaches 19\.3%, 2\.6%, and 1\.1% of Rank\-2, Rank\-5, and Rank\-10 foils\. The single\-edit union of all four operators raises these values to 43\.5%, 12\.6%, and 5\.9%\. Average coverage increases from 20\.6% at budget one to 25\.9% at budget two; 5\.3% of all comparisons require composition\. Structural and temporal edits thus open alternatives unavailable to deletion alone\.

The overall rates 10\.0/8\.8/41\.1/43\.8% in Table[I](https://arxiv.org/html/2609.11170#S5.T1)measure bounded reachability under coordinate\-based candidates\. The later efficiency rates 30\.8/37\.1/77\.2/57\.0% measure target success after trace\-guided generation adds foil\-specific facts and bindings and retains up to 32 candidates\. The first experiment identifies which edits are needed; the second evaluates how efficiently execution contrast finds them\.

##### Temporal knowledge graphs\.

For TLogic, we construct DELETE, INSERT, REWIRE, RELABEL, and SHIFT over timestamped facts and replay temporal rules on the edited graph\.

TABLE II:Specified\-foil success on temporal knowledge graphs\.DatasetRank\-2Rank\-5Rank\-10OverallOne editTwo editsICEWS1473\.0%62\.0%57\.0%64\.0%16824ICEWS1890\.0%83\.0%84\.0%85\.7%21740Combined81\.5%72\.5%70\.5%74\.8%38564

Table[II](https://arxiv.org/html/2609.11170#S5.T2)shows that TLogic reaches the specified object in 449 of 600 comparisons \(74\.8%\)\. Of these, 385 require one fact edit and 64 require a two\-edit composition\. The shared result across continuous interactions and relational temporal facts is that original and foil executions can be mapped back to observable edits and verified through exact replay\.

### V\-CWhy the Foil Must Be Specified

We compare the two success criteria with a controlled, foil\-agnostic invalidation procedure\. CTDG removes events supportingAA; TKG generates DELETE and SHIFT from the original trace\. Among interventions that demoteAA, we measure how often the replacement coincides with a Rank\-2, Rank\-5, or Rank\-10 foil fixed beforehand\.

TABLE III:Where untargeted prediction changes arrive\.FormalismSuccessful invalidationsRank\-2 arrivalRank\-5 arrivalRank\-10 arrivalCTDG4,00844\.3%3\.6%1\.4%TKG12291\.8%0\.0%0\.0%

Table[III](https://arxiv.org/html/2609.11170#S5.T3)reflects a local ranking effect at Rank\-2: once the original is removed, its runner\-up often inherits first place\. Arrival at Rank\-5 and Rank\-10 falls sharply in CTDG and never occurs in TKG\. Invalidation selects the complement ofAA; a specified\-foil objective selectsBB\. Foil direction is therefore part of the problem input rather than an additional metric attached to invalidation\.

### V\-DSearch Efficiency

We compare trace\-guided intervention search with random selection, recency\-based locality selection, and black\-box greedy search, which executes every atomic candidate and ranks it by foil\-margin improvement\. All methods share the same edits, foil, budget, and exact\-replay criterion\.

TABLE IV:Target success and predictor\-evaluation reduction of trace\-guided intervention search\.Formalism / datasetOursBlack\-box greedyGreedy success retainedEvaluation reductionCTDG / Wikipedia30\.8%33\.4%92\.3%76\.3%CTDG / Reddit37\.1%39\.7%93\.5%80\.0%CTDG / MOOC77\.2%82\.4%93\.6%77\.2%CTDG / LastFM57\.0%66\.6%85\.7%75\.0%TKG / ICEWS1464\.0%67\.3%95\.0%60\.0%TKG / ICEWS1885\.7%86\.3%99\.2%59\.4%

Table[IV](https://arxiv.org/html/2609.11170#S5.T4)shows that the proposed method retains 85\.7–93\.6% of black\-box greedy successes in CTDG while reducing predictor evaluations by 75\.0–80\.0%\. In TKG, it retains 95\.0–99\.2% while reducing evaluations by 59\.4–60\.0%\.

Fig\. 3:Execution traces concentrate successful interventions into a substantially smaller evaluated candidate set\.As visualized in Fig\.[3](https://arxiv.org/html/2609.11170#S5.F3), the gain follows from a different proposal mechanism\. Black\-box greedy must execute candidates to learn their effects; our method constructs candidates from execution differences before replay\. On ICEWS14 and ICEWS18, trace guidance reaches 64\.0% and 85\.7%, compared with 54\.3% and 69\.7% for random selection and 55\.7% and 63\.0% for locality under equal candidate counts\.

##### Statistical stability\.

Across three independently trained LiFTER checkpoints, target\-success standard deviations range from 0\.45 to 2\.38 percentage points, and method ordering remains unchanged\. Paired cluster\-bootstrap 95% confidence intervals against random and locality exclude zero for every dataset\. Supplementary Table[IX](https://arxiv.org/html/2609.11170#A1.T9)reports complete results\.

### V\-EComparison with Exhaustive Search

Within small bounded spaces, we execute every atomic intervention and every nonconflicting two\-edit pair\. The space contains at most 32 CTDG or 16 TKG atomic candidates\. A solution succeeds only when exact replay makes the foil top\-ranked, and the fewest\-edit successful solution is minimal within this fixed space\.

TABLE V:Comparison with exhaustive search in the fixed bounded candidate space\.Formalism / datasetExhaustive successOursSolution recallMinimum\-cost recoverySearch reductionCTDG / Wikipedia25\.3%22\.7%88\.2%88\.2%91\.5%CTDG / Reddit38\.7%35\.3%91\.4%91\.4%91\.5%CTDG / MOOC79\.3%68\.3%86\.1%85\.7%91\.6%CTDG / LastFM66\.3%50\.3%74\.9%71\.4%91\.2%TKG / ICEWS1471\.2%69\.7%97\.9%97\.9%83\.1%TKG / ICEWS1885\.3%85\.3%100\.0%100\.0%83\.5%

Table[V](https://arxiv.org/html/2609.11170#S5.T5)shows that the proposed method recovers 74\.9–91\.4% of CTDG exhaustive solutions while reducing evaluations by 91\.2–91\.6%\. It recovers 46 of 47 ICEWS14 solutions and all 64 ICEWS18 solutions, always at the same minimum edit count, with 83\.1% and 83\.5% fewer evaluations\. These claims concern the fixed candidate spaces and two\-edit budget rather than global optimality over all possible event values\.

### V\-FAblation Study

We ablate execution information, intervention priority, search width, operators, and composition using shared queries and exact\-replay criteria across both formalisms\.

TABLE VI:Ablation of execution information and intervention priority\.Information or priorityWikipediaRedditMOOCLastFMCTDG avg\.ICEWS14ICEWS18TKG avg\.Original execution only4\.3%8\.7%24\.7%16\.7%13\.6%4\.7%1\.7%3\.2%Foil execution only3\.3%6\.3%21\.7%8\.7%10\.0%56\.3%82\.0%69\.2%Complete execution contrast26\.3%32\.3%72\.0%48\.3%44\.8%64\.0%85\.7%74\.8%Original\-score decrease12\.0%18\.0%42\.3%17\.7%22\.5%64\.7%84\.3%74\.5%Foil\-score increase29\.7%41\.3%78\.7%57\.7%51\.8%66\.7%86\.0%76\.3%Contrastive\-gap reduction27\.0%39\.0%71\.7%53\.0%47\.7%67\.3%86\.3%76\.8%

Table[VI](https://arxiv.org/html/2609.11170#S5.T6)shows that CTDG target success rises from 10\.0–13\.6% with either execution side alone to 44\.8% with their complete contrast\. In TKG, adding the completed original execution to reconstructed foil execution raises success from 56\.3% to 64\.0% on ICEWS14 and from 82\.0% to 85\.7% on ICEWS18\. The original identifies support to disrupt; the foil identifies missing facts and bindings to complete\. Foil\-score increase and gap reduction also outperform original\-score decrease, confirming the need for foil\-directed priority\.

Success increases and then saturates as candidate cap and composition beam expand\. Moving the TKG beam from 8 to 16 adds only 0\.3 percentage points while roughly tripling evaluations\. Full sensitivity grids appear in Supplementary Section[C](https://arxiv.org/html/2609.11170#A3)and Table[XI](https://arxiv.org/html/2609.11170#A3.T11)\.

INSERT and REWIRE provide unique solutions across CTDG and both TKG datasets\. DELETE and SHIFT contribute selectively by formalism, while RELABEL adds unique TKG solutions\. Two\-edit composition accounts for 12\.5–15\.6% of full\-method solutions\. Dataset\-level results appear in Supplementary Table[XII](https://arxiv.org/html/2609.11170#A3.T12)\.

![Refer to caption](https://arxiv.org/html/2609.11170v1/mechanism_ablation.png)Fig\. 4:Complete execution contrast yields the highest reachability; distinct operators and composition open complementary solutions\.Figure[4](https://arxiv.org/html/2609.11170#S5.F4), together with exhaustive recovery, supports the central mechanism: the difference between the executed original proof and the reconstructed incomplete foil proof concentrates edits that reach the specified alternative\.

### V\-GQualitative Analysis

We reconstruct representative CTDG and TKG prediction transitions using foils fixed before intervention\. In MOOC, LiFTER predicts content 5993 for student 348 and ranks content 6659 fifth\. Deleting the earlier interaction\(348,5981\)\(348,5981\)lowers the original logit from 4\.46 to 3\.12 and raises the foil logit from 2\.13 to 3\.57, making the foil top\-ranked without inserting it into history\.

For an ICEWS18 query on September 28, 2018, TLogic predicts Moon Jae\-in as Abdel Fattah Al\-Sisi’s nextConsultcounterpart, while the recorded answer Benjamin Netanyahu ranks ninth\. Shifting\(Benjamin Netanyahu, Express intent to meet or negotiate, Abdel Fattah Al\-Sisi\)from September 24 to September 27 raises Netanyahu’s score from 0\.286 to 0\.738 and moves it to first place\. Date\-wise replay keeps Netanyahu ninth on September 25 and 26 and changes it to first only on September 27\. This boundary is a verified dependency of the frozen predictor, not a real\-world causal effect\. Supplementary Section[D](https://arxiv.org/html/2609.11170#A4)provides additional cases\.

## VIConclusion

We introduced Specified\-Foil Counterfactuals for temporal graphs\. Given an original predictionAA, the task identifies a low\-cost past\-event intervention that makes a prespecified foilBBtop\-ranked\. Prediction invalidation locates conditions that changeAA; our formulation locates conditions that produceBBinstead ofAA\. This explicit destination extends temporal counterfactual explanation from changing an open\-ended outcome to constructing a particular alternative\.

Trace\-guided intervention search solves this stronger problem by contrasting a completed proof of the original with a reconstructed incomplete proof of the foil\. DELETE and SHIFT alter conditions supporting the original, whereas INSERT, REWIRE, and RELABEL complete missing facts, bindings, relations, or temporal conditions for the foil\. Exact replay then verifies the full prediction transition\. LiFTER supplies grounded CTDG executions and TLogic supplies time\-consistent TKG rule groundings; our contribution turns these forward traces into an inverse computation over temporal events\.

The experiments establish both the need for the task and the value of this computation\. Foil\-agnostic invalidation rarely reached distant prespecified alternatives\. Multiple atomic operators and two\-edit compositions opened distinct solutions, and the complete original–foil execution contrast outperformed either side alone\. The proposed method retained most black\-box greedy and bounded exhaustive solutions while evaluating only a fraction of their candidates across both temporal formalisms\.

Returned interventions are model\-level counterfactuals verified within a frozen predictor\. Experimental minimality holds within the stated candidate space and two\-edit budget\. Domain constraints, event likelihoods, expert knowledge, and causal assumptions can further refine admissibility for real\-world analysis\. The broader implication is direct: an executable trace can serve not only as an explanation of a completed prediction, but also as a program for constructing the conditions of an alternative that the model has not yet selected\.

## Appendix AImplementation and Statistical Details

Table[VII](https://arxiv.org/html/2609.11170#A1.T7)lists the public source of every dataset\.

TABLE VII:Public dataset sources used in this study\.DomainDatasetSourceCTDGWikipedia[https://snap\.stanford\.edu/jodie/wikipedia\.csv](https://snap.stanford.edu/jodie/wikipedia.csv)CTDGReddit[https://snap\.stanford\.edu/jodie/reddit\.csv](https://snap.stanford.edu/jodie/reddit.csv)CTDGMOOC[https://snap\.stanford\.edu/jodie/mooc\.csv](https://snap.stanford.edu/jodie/mooc.csv)CTDGLastFM[https://snap\.stanford\.edu/jodie/lastfm\.csv](https://snap.stanford.edu/jodie/lastfm.csv)TKGICEWS14TLogic repository:[https://github\.com/liu\-yushan/TLogic](https://github.com/liu-yushan/TLogic)TKGICEWS18TLogic repository:[https://github\.com/liu\-yushan/TLogic](https://github.com/liu-yushan/TLogic)LiFTER is trained independently of counterfactual search and frozen throughout all intervention experiments\. We use AdamW for 10 epochs with batch size 512, learning rate4×10−34\\times 10^\{\-3\}, weight decay10−510^\{\-5\}, dropout 0\.1, and maximum history length 128\. Table[VIII](https://arxiv.org/html/2609.11170#A1.T8)reports the remaining architecture settings\.

TABLE VIII:LiFTER frozen\-backbone configuration\.ComponentValueTraining events / epochs59,500 / 10Batch size / learning rate512 / 0\.004Weight decay / dropout10−510^\{\-5\}/ 0\.1History / fact\-context length128 / 8Hidden / transition dimension64 / 32Maximum grounding facts / rule length10 / 2Maximum three\-hop paths32

Main results use the frozen seed\-7 checkpoint\. We evaluate initialization stability with independently trained checkpoints for seeds 7, 17, and 37 while holding the temporal split, 1,000 query rows, Rank\-2/5/10 foils, and search seed fixed\. A paired cluster bootstrap resamples queries 20,000 times while keeping their three foils and three training seeds together\. We additionally apply exact McNemar tests to paired binary outcomes\. Table[IX](https://arxiv.org/html/2609.11170#A1.T9)reports the complete results\.

TABLE IX:Statistical stability over independently trained LiFTER checkpoints\.DatasetOurs: target successOurs−\-random, 95% CIOurs−\-locality, 95% CIOurs−\-greedy, 95% CIEvaluation reduction, 95% CIWikipedia30\.38±\\pm0\.45%\+12\.40 \[11\.34, 13\.47\]\+13\.47 \[12\.17, 14\.79\]−\-2\.36 \[−\-2\.83,−\-1\.88\]75\.54 \[75\.22, 75\.84\]%Reddit36\.56±\\pm1\.71%\+12\.82 \[11\.84, 13\.81\]\+27\.69 \[25\.88, 29\.51\]−\-2\.37 \[−\-2\.83,−\-1\.91\]79\.80 \[79\.55, 80\.06\]%MOOC77\.16±\\pm2\.38%\+25\.23 \[24\.08, 26\.38\]\+32\.98 \[31\.11, 34\.92\]−\-4\.84 \[−\-5\.46,−\-4\.24\]77\.23 \[77\.08, 77\.38\]%LastFM56\.26±\\pm0\.74%\+18\.99 \[17\.84, 20\.13\]\+20\.43 \[19\.23, 21\.62\]−\-9\.72 \[−\-10\.47,−\-8\.99\]74\.87 \[74\.69, 75\.05\]%

## Appendix BFoil Construction Details

Before selecting rank\-controlled foils, we compare the ground\-truth destination, the highest\-ranked destination previously selected by the source \(historical best\), and its most recently selected destination \(historical recent\)\. Table[X](https://arxiv.org/html/2609.11170#A2.T10)reports the fraction of queries for which each construction yields a foil distinct from the original and the foil’s median pre\-intervention rank\.

TABLE X:Availability and pre\-intervention rank of benchmark foil constructions\. Each cell reports availability / median rank\.Foil constructionWikipediaRedditMOOCLastFMRank\-2 / 5 / 10100% / 2, 5, 10100% / 2, 5, 10100% / 2, 5, 10100% / 2, 5, 10Ground truth30% / 1239% / 662% / 379% / 159Historical best57% / 359% / 2100% / 2100% / 2Historical recent57% / 359% / 3100% / 3100% / 19\.5

Ground truth coincides with the original whenever the model predicts correctly and therefore supplies no foil for those queries\. Among errors, its median rank ranges from 3 to 159 across datasets\. Historical constructions require sufficient source history and mix substantially different difficulty levels\. Rank\-2/5/10 foils are defined for every query and fix the comparison positions\.

## Appendix CSearch\-Width and Operator Ablations

Table[XI](https://arxiv.org/html/2609.11170#A3.T11)reports the complete sensitivity grid for atomic\-candidate cap and composition beam\. Reachability increases and then saturates as either width grows\. 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 while increasing average evaluations from 44\.1 to 113\.9\.

TABLE XI:Sensitivity to atomic\-candidate cap and composition beam\.Search settingWikipediaRedditMOOCLastFMCTDG avg\.ICEWS14ICEWS18TKG avg\.Candidate cap 45\.0%14\.0%32\.7%8\.0%14\.9%38\.7%48\.3%43\.5%Candidate cap 813\.7%23\.7%56\.0%32\.3%31\.4%49\.0%63\.3%56\.2%Candidate cap 1626\.3%32\.3%72\.0%48\.3%44\.8%64\.0%85\.7%74\.8%Candidate cap 3228\.3%39\.0%74\.7%56\.3%49\.6%73\.0%90\.7%81\.8%Composition beam 222\.0%30\.7%58\.7%34\.7%36\.5%62\.7%80\.3%71\.5%Composition beam 424\.3%31\.7%62\.7%38\.7%39\.3%64\.0%85\.7%74\.8%Composition beam 826\.3%32\.3%72\.0%48\.3%44\.8%65\.7%87\.0%76\.3%Composition beam 1627\.3%34\.0%76\.7%56\.3%48\.6%66\.0%87\.3%76\.7%

Table[XII](https://arxiv.org/html/2609.11170#A3.T12)reports the fraction of full\-method successes lost after removing each operator or composition\. We first fix the full candidate set and do not refill removed positions, so each value measures solutions uniquely supplied by that component\.

TABLE XII:Unique contribution of intervention operators and composition\.Removed componentWikipediaRedditMOOCLastFMCTDG avg\.ICEWS14ICEWS18TKG avg\.DELETE2\.4%0\.8%2\.3%1\.2%1\.7%0\.0%0\.0%0\.0%INSERT26\.5%16\.1%23\.4%43\.7%28\.1%15\.6%20\.2%18\.3%REWIRE28\.9%19\.5%9\.5%13\.8%15\.4%20\.8%38\.9%31\.2%RELABEL–––––1\.6%7\.4%4\.9%SHIFT0\.0%0\.0%5\.0%3\.0%2\.7%1\.6%0\.0%0\.7%Composition19\.3%7\.6%13\.1%18\.0%14\.2%12\.5%15\.6%14\.3%

INSERT, REWIRE, and composition contribute unique solutions in both formalisms\. DELETE and SHIFT contribute selectively by dataset, and RELABEL adds unique solutions when relations are explicit in TKGs\. The result reflects complementary changes to event existence, endpoint, relation, and time rather than equal importance of every operator in every dataset\.

## Appendix DAdditional Qualitative Cases

### D\-ATwo\-Edit Composition in a CTDG

For LastFM listener 1574, LiFTER predicts item 1176 and ranks item 478 fifth\. No single edit reaches the foil\. Inserting the recent interaction\(1574,1221\)\(1574,1221\)and rewiring an older interaction from item 1172 to 707 makes item 478 top\-ranked\. The edits complete distinct missing conditions and jointly open an alternative unavailable to either edit alone\.

### D\-BTemporal Boundary in a TKG

In the ICEWS18 case, shifting the relevant fact one day at a time leaves Benjamin Netanyahu ranked ninth on September 25 and 26, but moves him to first on September 27\. Moon Jae\-in and Abdel Fattah Al\-Sisi held a summit in New York on September 26, and reports place a Netanyahu–Al\-Sisi meeting later that night\. We use these records only to place the learned temporal boundary beside the observed timeline, not as causal evidence\. The replay identifies how SHIFT changes TLogic’s time\-consistent grounding\.

### D\-CA Non\-Intuitive Cross\-Relation Dependency

TLogic predictsCitizen \(Nigeria\)as the target of Abdulrahman Dambazau’sMake an appeal or request, withNigeriaranked second\. Inserting\(Abdulrahman Dambazau, Sexually assault, Nigeria\)one day before the query makes Nigeria top\-ranked\. The inserted fact completes a missing premise of a learned cross\-relation rule\. Its explicit chain from fact to grounding to prediction makes the non\-intuitive dependency directly auditable\.

## Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper\.

## Acknowledgements

The authors have no acknowledgements to declare\.

## Data availability

All six datasets used in this study—Wikipedia, Reddit, MOOC, LastFM, ICEWS14, and ICEWS18—are publicly available\. The repository provides scripts to download the source files and materialize the processed experimental inputs\. Dataset URLs are reported in Supplementary Table[VII](https://arxiv.org/html/2609.11170#A1.T7)\.

## Code availability

The implementation, experiment configurations, aggregation scripts, and plotting scripts used in this study are available at[https://github\.com/SnowyPainter/cf\-public](https://github.com/SnowyPainter/cf-public)\.

## References

- \[1\]S\. Wachter, B\. Mittelstadt, and C\. Russell\(2018\)Counterfactual explanations without opening the black box: automated decisions and the GDPR\.Harvard Journal of Law & Technology31\(2\),pp\. 841–887\.Cited by:[§I](https://arxiv.org/html/2609.11170#S1.p2.1),[§II\-A](https://arxiv.org/html/2609.11170#S2.SS1.p1.1)\.
- \[2\]T\. Miller\(2019\)Explanation in artificial intelligence: insights from the social sciences\.Artificial Intelligence267,pp\. 1–38\.External Links:[Document](https://dx.doi.org/10.1016/j.artint.2018.07.007)Cited by:[§I](https://arxiv.org/html/2609.11170#S1.p2.1),[§II\-A](https://arxiv.org/html/2609.11170#S2.SS1.p1.1)\.
- \[3\]J\. Pearl\(2009\)Causality: models, reasoning, and inference\.2 edition,Cambridge University Press\.Cited by:[§I](https://arxiv.org/html/2609.11170#S1.p2.1),[§II\-A](https://arxiv.org/html/2609.11170#S2.SS1.p1.1)\.
- \[4\]Z\. Qu, D\. Gomm, and M\. Färber\(2025\)CoDy: counterfactual explainers for dynamic graphs\.InProc\. ICML,PMLR, Vol\.267,pp\. 50762–50785\.Cited by:[§I](https://arxiv.org/html/2609.11170#S1.p3.1),[§II\-D](https://arxiv.org/html/2609.11170#S2.SS4.p1.1),[§IV](https://arxiv.org/html/2609.11170#S4.p5.1)\.
- \[5\]M\. Lu, H\. Che, Y\. Fan, Q\. Liu, F\. Shao, T\. Ge, X\. Xiao, and Y\. Wu\(2026\)Training\-free counterfactual explanation for temporal graph model inference\.InProc\. ICLR,Cited by:[§I](https://arxiv.org/html/2609.11170#S1.p3.1),[§II\-D](https://arxiv.org/html/2609.11170#S2.SS4.p1.1),[§IV](https://arxiv.org/html/2609.11170#S4.p5.1)\.
- \[6\]Y\. Zhao, Y\. Xu, N\. Liu, L\. Cui, and Q\. Li\(2026\)Generating counterfactual temporal motifs: unraveling the mysteries of temporal graph neural networks\.Data Science and Engineering11,pp\. 199–212\.External Links:[Document](https://dx.doi.org/10.1007/s41019-025-00321-x)Cited by:[§I](https://arxiv.org/html/2609.11170#S1.p3.1),[§II\-D](https://arxiv.org/html/2609.11170#S2.SS4.p1.1)\.
- \[7\]P\. Pezeshkpour, Y\. Tian, and S\. Singh\(2019\)Investigating robustness and interpretability of link prediction via adversarial modifications\.InProc\. NAACL\-HLT,pp\. 3336–3347\.External Links:[Document](https://dx.doi.org/10.18653/v1/N19-1337)Cited by:[§II\-B](https://arxiv.org/html/2609.11170#S2.SS2.p1.1)\.
- \[8\]R\. Barile, C\. d’Amato, and N\. Fanizzi\(2024\)Additive counterfactuals for explaining link predictions on knowledge graphs\.InProc\. Int\. Conf\. Knowledge Engineering and Knowledge Management,LNCS, Vol\.15370,pp\. 346–363\.Cited by:[§II\-B](https://arxiv.org/html/2609.11170#S2.SS2.p1.1)\.
- \[9\]L\. Zellinger, A\. Stephan, and B\. Roth\(2024\)Counterfactual reasoning with knowledge graph embeddings\.InProc\. EACL,pp\. 2753–2772\.External Links:[Document](https://dx.doi.org/10.18653/v1/2024.eacl-long.168)Cited by:[§II\-B](https://arxiv.org/html/2609.11170#S2.SS2.p1.1)\.
- \[10\]J\. Bai, Y\. Wang, T\. Zheng, Y\. Guo, X\. Liu, and Y\. Song\(2024\)Advancing abductive reasoning in knowledge graphs through complex logical hypothesis generation\.InProc\. ACL,pp\. 1312–1329\.External Links:[Document](https://dx.doi.org/10.18653/v1/2024.acl-long.72)Cited by:[§II\-B](https://arxiv.org/html/2609.11170#S2.SS2.p1.1)\.
- \[11\]Y\. Liu, Y\. Ma, M\. Hildebrandt, M\. Joblin, and V\. Tresp\(2022\)TLogic: temporal logical rules for explainable link forecasting on temporal knowledge graphs\.InProc\. AAAI,Vol\.36,pp\. 4120–4127\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v36i4.20330)Cited by:[§II\-C](https://arxiv.org/html/2609.11170#S2.SS3.p1.1),[§IV\-A](https://arxiv.org/html/2609.11170#S4.SS1.p4.1),[§V\-A](https://arxiv.org/html/2609.11170#S5.SS1.p1.1)\.
- \[12\]S\. Xiong, Y\. Yang, F\. Fekri, and J\. C\. Kerce\(2023\)TILP: differentiable learning of temporal logical rules on knowledge graphs\.InProc\. ICLR,Cited by:[§II\-C](https://arxiv.org/html/2609.11170#S2.SS3.p1.1),[§IV\-A](https://arxiv.org/html/2609.11170#S4.SS1.p4.1)\.
- \[13\]X\. Lin, H\. E, C\. Xu, G\. Zhou, H\. Luo, T\. Hu, F\. Su, N\. Li, and M\. Sun\(2023\)TFLEX: temporal feature\-logic embedding framework for complex reasoning over temporal knowledge graph\.InAdvances in Neural Information Processing Systems,Vol\.36\.External Links:[Document](https://dx.doi.org/10.52202/075280-3194)Cited by:[§II\-C](https://arxiv.org/html/2609.11170#S2.SS3.p1.1)\.
- \[14\]S\. Xiong, Y\. Yang, A\. Payani, J\. C\. Kerce, and F\. Fekri\(2024\)TEILP: time prediction over knowledge graphs via logical reasoning\.InProc\. AAAI,Cited by:[§II\-C](https://arxiv.org/html/2609.11170#S2.SS3.p1.1)\.
- \[15\]N\. Li, H\. E, T\. Yao, T\. Hu, Y\. Li, H\. Luo, M\. Song, and Y\. Zhu\(2025\)INFER: a neural\-symbolic model for extrapolation reasoning on temporal knowledge graph\.InProc\. ICLR,Cited by:[§II\-C](https://arxiv.org/html/2609.11170#S2.SS3.p1.1)\.
- \[16\]W\. Xia, M\. Lai, C\. Shan, Y\. Zhang, X\. Dai, X\. Li, and D\. Li\(2023\)Explaining temporal graph models through an explorer–navigator framework\.InProc\. ICLR,Cited by:[§II\-D](https://arxiv.org/html/2609.11170#S2.SS4.p1.1)\.
- \[17\]J\. Chen and R\. Ying\(2023\)TempME: towards the explainability of temporal graph neural networks via motif discovery\.InAdvances in Neural Information Processing Systems,Vol\.36\.Cited by:[§II\-D](https://arxiv.org/html/2609.11170#S2.SS4.p1.1)\.
- \[18\]M\. Yu and Y\. Ha\(2026\)LiFTER: a grounded neuro\-symbolic microscope for continuous\-time dynamic graph forecasting\.arXiv preprint arXiv:2608\.06765\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2608.06765)Cited by:[§IV](https://arxiv.org/html/2609.11170#S4.p3.1)\.
- \[19\]S\. Kumar, X\. Zhang, and J\. Leskovec\(2019\)Predicting dynamic embedding trajectory in temporal interaction networks\.InProc\. ACM SIGKDD,pp\. 1269–1278\.External Links:[Document](https://dx.doi.org/10.1145/3292500.3330895)Cited by:[§V\-A](https://arxiv.org/html/2609.11170#S5.SS1.p1.1)\.
- \[20\]E\. Boschee, J\. Lautenschlager, S\. O’Brien, S\. Shellman, J\. Starz, and M\. Ward\(2015\)ICEWS coded event data\.Harvard Dataverse\.External Links:[Document](https://dx.doi.org/10.7910/DVN/28075)Cited by:[§V\-A](https://arxiv.org/html/2609.11170#S5.SS1.p1.1)\.