# Flexible and Robust Counterfactual Explanations with Minimal Satisfiable Perturbations

arXiv: https://arxiv.org/abs/2309.04676 · HTML: https://mlsanity.com/paper/2309.04676/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 44 references that are in the map.
- First posted on arXiv 9 Sep 2023.

## Builds on (most cited first, 26 of 26)

- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [Actionable Recourse in Linear Classification](https://mlsanity.com/paper/1809.06514/) (2018)
- [Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives](https://mlsanity.com/paper/1802.07623/) (2018)
- [Algorithmic Recourse: from Counterfactual Explanations to Interventions](https://mlsanity.com/paper/2002.06278/) (2020)
- [Interpretable Counterfactual Explanations Guided by Prototypes](https://mlsanity.com/paper/1907.02584/) (2019)
- [Learning Model-Agnostic Counterfactual Explanations for Tabular Data](https://mlsanity.com/paper/1910.09398/) (2019)
- [Algorithmic recourse under imperfect causal knowledge: a probabilistic approach](https://mlsanity.com/paper/2006.06831/) (2020)
- [Towards Realistic Individual Recourse and Actionable Explanations in Black-Box Decision Making Systems](https://mlsanity.com/paper/1907.09615/) (2019)
- [Counterfactual Explanations Can Be Manipulated](https://mlsanity.com/paper/2106.02666/) (2021)
- [Efficient Search for Diverse Coherent Explanations](https://mlsanity.com/paper/1901.04909/) (2019)
- [Towards Robust and Reliable Algorithmic Recourse](https://mlsanity.com/paper/2102.13620/) (2021)
- [Interpretable Predictions of Tree-based Ensembles via Actionable Feature Tweaking](https://mlsanity.com/paper/1706.06691/) (2017)
- [On Counterfactual Explanations under Predictive Multiplicity](https://mlsanity.com/paper/2006.13132/) (2020)
- [On the Fairness of Causal Algorithmic Recourse](https://mlsanity.com/paper/2010.06529/) (2020)
- [The Use and Misuse of Counterfactuals in Ethical Machine Learning](https://mlsanity.com/paper/2102.05085/) (2021)
- [Inverse Classification for Comparison-based Interpretability in Machine Learning](https://mlsanity.com/paper/1712.08443/) (2017)
- [Robust Counterfactual Explanations for Tree-Based Ensembles](https://mlsanity.com/paper/2207.02739/) (2022)
- [Evaluating Robustness of Counterfactual Explanations](https://mlsanity.com/paper/2103.02354/) (2021)
- [DECE: Decision Explorer with Counterfactual Explanations for Machine Learning Models](https://mlsanity.com/paper/2008.08353/) (2020)
- [Consistent Counterfactuals for Deep Models](https://mlsanity.com/paper/2110.03109/) (2021)
- [On the Robustness of Sparse Counterfactual Explanations to Adverse Perturbations](https://mlsanity.com/paper/2201.09051/) (2022)
- [Issues with post-hoc counterfactual explanations: a discussion](https://mlsanity.com/paper/1906.04774/) (2019)
- [Generalized Inverse Classification](https://mlsanity.com/paper/1610.01675/) (2016)
- ["There Is Not Enough Information": On the Effects of Explanations on Perceptions of Informational Fairness and Trustworthiness in Automated Decision-Making](https://mlsanity.com/paper/2205.05758/) (2022)
- [Recursive Online Enumeration of All Minimal Unsatisfiable Subsets](https://mlsanity.com/paper/1708.00400/) (2017)

## Built on by (most cited first, 6 of 6)

- [Robust Counterfactual Explanations in Machine Learning: A Survey](https://mlsanity.com/paper/2402.01928/) (2024)
- [When Graph Neural Network Meets Causality: Opportunities, Methodologies and An Outlook](https://mlsanity.com/paper/2312.12477/) (2023)
- [The Effect of Data Poisoning on Counterfactual Explanations](https://mlsanity.com/paper/2402.08290/) (2024)
- [From Universal to Individualized Actionability: Revisiting Personalization in Algorithmic Recourse](https://mlsanity.com/paper/2604.08030/) (2026)
- [An Intelligent and Privacy-Preserving Digital Twin Model for Aging-in-Place](https://mlsanity.com/paper/2504.03798/) (2025)
- [RecourseBench: A Modular Framework for Reproducible Algorithmic Recourse Evaluation](https://mlsanity.com/paper/2606.16113/) (2026)

## Abstract (arXiv)

Counterfactual explanations (CFEs) exemplify how to minimally modify a feature vector to achieve a different prediction for an instance. CFEs can enhance informational fairness and trustworthiness, and provide suggestions for users who receive adverse predictions. However, recent research has shown that multiple CFEs can be offered for the same instance or instances with slight differences. Multiple CFEs provide flexible choices and cover diverse desiderata for user selection. However, individual fairness and model reliability will be damaged if unstable CFEs with different costs are returned. Existing methods fail to exploit flexibility and address the concerns of non-robustness simultaneously. To address these issues, we propose a conceptually simple yet effective solution named Counterfactual Explanations with Minimal Satisfiable Perturbations (CEMSP). Specifically, CEMSP constrains changing values of abnormal features with the help of their semantically meaningful normal ranges. For efficiency, we model the problem as a Boolean satisfiability problem to modify as few features as possible. Additionally, CEMSP is a general framework and can easily accommodate more practical requirements, e.g., casualty and actionability. Compared to existing methods, we conduct comprehensive experiments on both synthetic and real-world datasets to demonstrate that our method provides more robust explanations while preserving flexibility.