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

Summary

Temporal graph counterfactual explanations often change past events to invalidate an original prediction without specifying what should replace it. This paper formulates a specified-foil counterfactual: given an original prediction A and a fixed alternative B, it searches for a low-cost intervention that makes the same predictor rank B first. The trace-guided search compares the completed execution trace for A with a reconstructed incomplete trace for B, converts their differences into DELETE, INSERT, REWIRE, RELABEL, and SHIFT operations, and verifies the result through exact replay. The authors instantiate the approach with LiFTER on continuous-time dynamic graphs and TLogic on temporal knowledge graphs. On continuous-time dynamic graphs, it preserves 85.7% to 93.6% of the successes achieved by a black-box greedy baseline while reducing predictor evaluations by 75.0% to 80.0%. On temporal knowledge graphs, it reaches the specified alternative in 74.8% of 600 comparisons. The paper argues that executable traces can be used to construct conditions for an unselected alternative, rather than only explaining a prediction that has already been made.