Generating Counterfactual Explanations Under Temporal Constraints

Andrei Buliga, Chiara Di Francescomarino, Chiara Ghidini, Marco Montali, Massimiliano RonzaniAAAI 2025 · DOI

TL;DR

This paper introduces a novel approach to generate counterfactual explanations for temporal data, specifically process traces, that are guaranteed to adhere to predefined temporal rules. By integrating automata-theoretic techniques with genetic algorithms, the authors ensure that the generated explanations are not only valid but also temporally meaningful and interpretable.

What Problem Does This Paper Address?

Explainable AI (XAI) techniques aim to make complex machine learning models more understandable. Counterfactual explanations, a popular XAI method, suggest minimal changes to input data to alter a prediction. However, existing methods struggle with temporal data, such as process mining traces, where the order of events matters and must adhere to temporal constraints (e.g., a patient must be triaged before receiving a diagnosis). Counterfactuals generated without considering these constraints can be inconsistent and nonsensical. This paper addresses the challenge of generating counterfactual explanations for temporal data that are guaranteed to satisfy these temporal background rules.

Methods

The core of the proposed approach is a Genetic Algorithm (GA) enhanced with temporal knowledge. The GA is used to search for counterfactual traces that satisfy a set of objectives, including validity (flipping the prediction), input closeness, sparsity, plausibility, and a new desideratum: compliance with temporal background knowledge expressed in Linear Temporal Logic on process traces (LTLp).

To ensure compliance, the authors integrate automata-theoretic techniques. Specifically, they convert LTLp formulas into Deterministic Finite Automata (DFAs). These DFAs are then used to modify the GA's crossover and mutation operators. The Temporal Knowledge-aware Crossover operator ensures that offspring traces maintain compliance by carefully selecting genetic material. The Temporal Knowledge-aware Mutation operator uses two strategies:

  • aPriori: Mutates genes with activities not present in the LTLp formula's alphabet.
  • Online: Leverages the DFA to determine safe activities that can replace a gene while preserving compliance.

Datasets

The paper evaluates its approach on three datasets:

  • Claim Management: A synthetic dataset for a claim management process.
  • BPIC2012: A real-world dataset related to a loan application process.
  • BPIC2017: Another real-world dataset for a loan application process.

These datasets are standard benchmarks in process mining.

Key Insights and Ideas

  • Temporal Constraints are Crucial: Standard counterfactual generation methods fail in temporal domains because they ignore the inherent order and rules governing event sequences.
  • Automata-Theoretic Integration: Using DFAs derived from LTLp formulas provides a formal and effective way to enforce temporal constraints within a generative process.
  • Modified GA Operators are Key: Simply adding compliance as a fitness objective isn't enough. Modifying the GA's core operators (crossover and mutation) is essential to guarantee compliance by design.
  • Trade-offs Exist: While the proposed methods ensure compliance, they introduce computational overhead compared to standard GAs. The "Online" mutation strategy, while powerful, can be more time-consuming than the "aPriori" strategy.

Key Results

The empirical evaluation demonstrates that the proposed methods (aPriori and Online) significantly outperform a standard GA (Geny) and a baseline "Mutate-And-Retry" (MAR) approach in terms of generating temporally meaningful and interpretable counterfactuals.

  • Quality: aPriori and Online consistently generate counterfactuals with better distance, sparsity, and plausibility compared to Geny. They also show comparable or better quality than MAR, especially on more complex datasets.
  • Runtime: aPriori and Online are generally faster than MAR, particularly at higher coverage levels of temporal constraints. Geny is the fastest but sacrifices compliance.
  • Compliance: The proposed methods guarantee compliance, whereas Geny only achieves it partially (80-99% on average).

Limitations and Future Work

  • Computational Cost: While efficient, the temporal knowledge-aware operators do introduce some overhead compared to standard GAs. The "Online" strategy can be more time-consuming.
  • Future Work: The authors plan to develop more efficient genetic operators and extend the approach to richer temporal logics that can handle numerical data, not just activities. They also suggest that counterfactual desiderata can be redefined for numerical data.

Summary updated

BibTeX
@inproceedings{buliga2025generating,
  author = {Andrei Buliga and Chiara Di Francescomarino and Chiara Ghidini and Marco Montali and Massimiliano Ronzani},
  title = {{Generating Counterfactual Explanations Under Temporal Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i15.33715},
}
Figure