Technical Summary: Counterfactual Explanations Under Concept Drift

1. Problem Statement

Counterfactual explanations (CFEs) are actionable recourse mechanisms that answer "what needs to change for the outcome to be different?" While existing literature extensively covers CFE generation for static data and fixed classifiers, this paper identifies a critical gap: CFE maintenance under concept drift.

In evolving data environments (e.g., data streams), classifiers are frequently updated online to adapt to changing data distributions. The authors argue that a CFE valid at the time of generation can silently become invalid as the model evolves, even if the original explanation was robust against bounded, single-step model changes. Unlike prior robustness research, which aims to harden a single explanation against a bounded retraining event, this work addresses the continuous degradation of a population of CFEs as a classifier is repeatedly updated over time. The core challenge is to maintain the validity and local plausibility of existing CFEs without the computational cost of regenerating them from scratch after every model update.

2. Methodology

The authors propose a lightweight, model-agnostic maintenance scheme that repairs existing CFEs using local sampling and a sliding window of recent observations.

2.1 State Representation and Triggering

The system maintains a state $s = (x_0, x', c', a)$ for each query instance $x_0$, where $x'$ is the current CFE, $c'$ is the target class, and $a$ is an active flag.

• Retirement: A state is retired if the current classifier $f_t$ already predicts the target class for $x_0$ (i.e., the drift naturally resolved the recourse need).
• Update Trigger: An update is triggered if the current CFE is invalid ($f_t(x') \neq c'$) or has low confidence in the target class ($p_t(c' | x') < \tau_{low}$).

2.2 The Update Mechanism

The method applies a correction vector to the current CFE $x'$, balancing three objectives:

1. Validity Direction ($v$): Increases the probability of the target class. For non-differentiable models (e.g., Hoeffding trees), this is estimated by sampling local perturbations around $x'$, querying the classifier, and fitting a locally weighted linear surrogate (similar to LIME) to approximate the gradient.
2. Plausibility Direction ($p$): Moves the CFE toward dense regions of the target class in the recent data stream. This is computed using a kernel-weighted mean-shift direction based on the $k$-nearest neighbors of the target class within a sliding buffer $B_t$.
3. Proximity Pull ($r$): A vector pulling $x'$ back toward the original instance $x_0$ to minimize unnecessary deviation.

The update direction $d$ is a normalized linear combination of the selected correction vector ($u \in \{v, p\}$) and the proximity pull:
$$d = \frac{\lambda_u \hat{u} + \lambda_r \hat{r}}{\|\lambda_u \hat{u} + \lambda_r \hat{r}\|}$$
where $\lambda_u$ and $\lambda_r$ control the relative strength of the correction and proximity, respectively.

2.3 Maintenance Variants

The paper evaluates two specific strategies:

• Validity–Plausibility (Ours-VP): Uses the validity direction $v$ when the CFE is invalid or low-confidence. Additionally, it applies the plausibility direction $p$ periodically (every $K$ steps) to keep valid CFEs aligned with recent data distributions.
• Plausibility-Only (Ours-P): Does not estimate the validity direction. Instead, it relies solely on the plausibility direction $p$ to repair invalid or low-confidence CFEs, testing if moving toward dense target regions is sufficient to restore validity under gradual drift.

3. Experimental Setup and Results

Experiments were conducted on synthetic drifting streams (Rotating Hyperplane, Sine, SEA) using online classifiers (Logistic Regression and Adaptive Hoeffding Trees).

3.1 Key Findings

• Degradation of Static CFEs: "Frozen" CFEs (including those generated by robust methods like RobX) rapidly lose validity as concept drift accumulates. For example, on the Rotating Hyperplane stream, validity dropped to ~0.29–0.35 for frozen CFEs.
• Preservation of Validity: Both maintenance variants (Ours-P and Ours-VP) successfully preserved near-perfect validity (often 1.0) throughout the stream, significantly outperforming frozen baselines.
• Improvement in Plausibility: Maintained CFEs achieved substantially higher local plausibility scores (kNN and KDE) compared to regeneration baselines like Nearest Neighbor (NN) and Growing Spheres (GS). This is because the maintenance scheme explicitly incorporates the recent data buffer, whereas regeneration methods often optimize only for validity and proximity.
• Proximity Trade-off: The maintained CFEs exhibited larger $L_2$ distances (proximity) compared to regeneration methods. The authors attribute this to the cost of maintaining local plausibility; the CFEs are moved toward recent target-class regions that may be slightly further from the original instance than the nearest valid point found by regeneration.
• Computational Efficiency: Despite performing 200 maintenance updates, the proposed methods were competitive with or faster than regeneration baselines (e.g., RobX) that run only once at the end of the stream. Ours-P was notably faster than Ours-VP by avoiding the validity direction estimation.

4. Contributions

The paper claims the following contributions:

1. Problem Definition: It introduces CFE maintenance under concept drift as a distinct problem class, differentiating it from static robustness settings. The goal is to keep a population of explanations valid and plausible as the classifier evolves, rather than hardening a single explanation against a single change.
2. Proposed Method: A lightweight, model-agnostic scheme that repairs CFEs using local sampling to estimate validity and plausibility directions while preserving proximity.
3. Empirical Evidence: Demonstration that standard and robust CFEs systematically lose validity under continuous drift, while the proposed scheme preserves validity and local plausibility at a lower computational cost than repeated regeneration.

5. Significance and Limitations

The authors position this work as an initial proof of concept. The significance lies in shifting the paradigm of XAI in streaming environments from treating explanations as static artifacts to viewing them as dynamic objects requiring maintenance. This is particularly relevant when the original CFE generator is computationally expensive, unavailable, or unsuitable for frequent re-execution.

The paper modestly acknowledges its limitations:

• Evaluation is restricted to synthetic, low-dimensional streams with controlled gradual drift.
• It does not yet establish performance in complex real-world scenarios, high-dimensional data, or mixed-type data.
• Future work is suggested to explore real data streams, differentiable classifiers, and extending maintenance from individual CFEs to group-level counterfactuals.

The authors conclude that maintaining explanations over time is a practical alternative to repeated regeneration, offering a balance between validity, plausibility, and computational cost in evolving environments.