# Provably Robust and Plausible Counterfactual Explanations for Neural Networks via Robust Optimisation

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 56 references that are in the map.
- First posted on arXiv 22 Sep 2023.

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

- [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)
- [Towards Robust Interpretability with Self-Explaining Neural Networks](https://mlsanity.com/paper/1806.07538/) (2018)
- [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)
- [FACE: Feasible and Actionable Counterfactual Explanations](https://mlsanity.com/paper/1909.09369/) (2019)
- [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)
- [Towards Robust and Reliable Algorithmic Recourse](https://mlsanity.com/paper/2102.13620/) (2021)
- [CARLA: A Python Library to Benchmark Algorithmic Recourse and Counterfactual Explanation Algorithms](https://mlsanity.com/paper/2108.00783/) (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)
- [Robust Counterfactual Explanations on Graph Neural Networks](https://mlsanity.com/paper/2107.04086/) (2021)
- [On the Adversarial Robustness of Causal Algorithmic Recourse](https://mlsanity.com/paper/2112.11313/) (2021)
- [Robust Counterfactual Explanations for Tree-Based Ensembles](https://mlsanity.com/paper/2207.02739/) (2022)
- [Robust Counterfactual Explanations for Neural Networks With Probabilistic Guarantees](https://mlsanity.com/paper/2305.11997/) (2023)
- [Probabilistically Robust Recourse: Navigating the Trade-offs between Costs and Robustness in Algorithmic Recourse](https://mlsanity.com/paper/2203.06768/) (2022)
- [Consistent Counterfactuals for Deep Models](https://mlsanity.com/paper/2110.03109/) (2021)
- [Algorithmic Recourse in the Wild: Understanding the Impact of Data and Model Shifts](https://mlsanity.com/paper/2012.11788/) (2020)
- [Abstraction based Output Range Analysis for Neural Networks](https://mlsanity.com/paper/2007.09527/) (2020)
- [Amortized Generation of Sequential Algorithmic Recourses for Black-box Models](https://mlsanity.com/paper/2106.03962/) (2021)
- [Formalising the Robustness of Counterfactual Explanations for Neural Networks](https://mlsanity.com/paper/2208.14878/) (2022)
- [Scaling Guarantees for Nearest Counterfactual Explanations](https://mlsanity.com/paper/2010.04965/) (2020)
- [Counterfactual Plans under Distributional Ambiguity](https://mlsanity.com/paper/2201.12487/) (2022)
- [Finding Regions of Counterfactual Explanations via Robust Optimization](https://mlsanity.com/paper/2301.11113/) (2023)
- [Robust Bayesian Recourse](https://mlsanity.com/paper/2206.10833/) (2022)
- [Feature-based Learning for Diverse and Privacy-Preserving Counterfactual Explanations](https://mlsanity.com/paper/2209.13446/) (2022)

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

- [Robust Counterfactual Explanations in Machine Learning: A Survey](https://mlsanity.com/paper/2402.01928/) (2024)
- [Recourse under Model Multiplicity via Argumentative Ensembling (Technical Report)](https://mlsanity.com/paper/2312.15097/) (2023)
- [Probabilistically Plausible Counterfactual Explanations with Normalizing Flows](https://mlsanity.com/paper/2405.17640/) (2024)
- [Performative Validity of Recourse Explanations](https://mlsanity.com/paper/2506.15366/) (2025)
- [Interval Abstractions for Robust Counterfactual Explanations](https://mlsanity.com/paper/2404.13736/) (2024)
- [Generating Likely Counterfactuals Using Sum-Product Networks](https://mlsanity.com/paper/2401.14086/) (2024)
- [RobustX: Robust Counterfactual Explanations Made Easy](https://mlsanity.com/paper/2502.13751/) (2025)
- [Counterfactual Explanations for Model Ensembles Using Entropic Risk Measures](https://mlsanity.com/paper/2503.07934/) (2025)
- [Faster Verified Explanations for Neural Networks](https://mlsanity.com/paper/2512.00164/) (2025)
- [CE-QArg: Counterfactual Explanations for Quantitative Bipolar Argumentation Frameworks (Technical Report)](https://mlsanity.com/paper/2407.08497/) (2024)
- [Optimal Robust Recourse with Lp-Bounded Model Change](https://mlsanity.com/paper/2509.21293/) (2025)
- [PAR: Plausibility-aware Amortized Recourse Generation](https://mlsanity.com/paper/2601.17309/) (2026)
- [ElliCE: Efficient and Provably Robust Algorithmic Recourse via the Rashomon Sets](https://mlsanity.com/paper/2602.07674/) (2026)
- [T-COL: Generating Counterfactual Explanations for General User Preferences on Variable Machine Learning Systems](https://mlsanity.com/paper/2309.16146/) (2023)
- [Argumentative Ensembling for Robust Recourse under Model Multiplicity](https://mlsanity.com/paper/2506.20260/) (2025)
- [Evaluating Counterfactual Explanation Methods on Incomplete Inputs](https://mlsanity.com/paper/2604.08004/) (2026)
- [A Probabilistic Consensus-Driven Approach for Robust Counterfactual Explanations](https://mlsanity.com/paper/2604.17494/) (2026)
- [RecourseBench: A Modular Framework for Reproducible Algorithmic Recourse Evaluation](https://mlsanity.com/paper/2606.16113/) (2026)
- [Beyond Tracking or Shortcut: Composition-Bounded Predictive States in Poker Autoregressive Models](https://mlsanity.com/paper/2607.19369/) (2026)
- [Class-Aware Reinforcement Learning for Counterfactual Explanation Generation](https://mlsanity.com/paper/2607.27905/) (2026)

## Abstract (arXiv)

Counterfactual Explanations (CEs) have received increasing interest as a major methodology for explaining neural network classifiers. Usually, CEs for an input-output pair are defined as data points with minimum distance to the input that are classified with a different label than the output. To tackle the established problem that CEs are easily invalidated when model parameters are updated (e.g. retrained), studies have proposed ways to certify the robustness of CEs under model parameter changes bounded by a norm ball. However, existing methods targeting this form of robustness are not sound or complete, and they may generate implausible CEs, i.e., outliers wrt the training dataset. In fact, no existing method simultaneously optimises for closeness and plausibility while preserving robustness guarantees. In this work, we propose Provably RObust and PLAusible Counterfactual Explanations (PROPLACE), a method leveraging on robust optimisation techniques to address the aforementioned limitations in the literature. We formulate an iterative algorithm to compute provably robust CEs and prove its convergence, soundness and completeness. Through a comparative experiment involving six baselines, five of which target robustness, we show that PROPLACE achieves state-of-the-art performances against metrics on three evaluation aspects.