Realistic Counterfactual Explanations via Denial Constraints
Open Access
- 8 August 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 33-44
Abstract
In the realm of Explainable AI, classification results are often explained via counterfactuals (CFs for short), which are (ideally small) perturbations to an instance that lead to a change of classification label. Such CFs may serve as explanations for the prediction, pinpointing the features that were important. Existing explainability solutions typically aim at minimizing the distance of CFs from the original instance so that they are specific to it; and/or maximizing the diversity of CFs to cover multiple facets of the reasons underlying the prediction. In this paper, we note that in pursuing these aims, state-of-the-art explainability solutions may (and often do) yield counterfactual explanations that do not correspond to realistic instances. This limits their applicability and usefulness in practice. To remedy this, we combine ideas from Explainable AI with ideas from data management. Specifically, we capture realism of CFs via logical constraints that hold with respect to a dataset of examples (e.g. training set); the class of such constraints that we focus on is that of denial constraints, extensively studied in the context of relational databases. Algorithmically, we then combine explainable AI solutions to yield CFs, with ideas from data cleaning that we adapt to this unique setting, to transform CFs into realistic ones. Extensive experiments across four datasets validate that our solutions achieve realism with relatively minor compromise in terms of distance and diversity. They further validate that the dedicated optimizations that we have developed to speed up the search for CFs are indeed highly effective.Keywords
All Related Versions
Funding Information
- European Research Council (804302)
- Israel Science Foundation (1476\/24)
- Israel Science Foundation (1702\/24)
This publication has 23 references indexed in Scilit:
- CaFA: Cost-aware, Feasible Attacks With Database Constraints Against Neural Tabular Classifiers2024
- NICE: an algorithm for nearest instance counterfactual explanationsData Mining and Knowledge Discovery, 2023
- Counterfactual explanations and how to find them: literature review and benchmarkingData Mining and Knowledge Discovery, 2022
- Multi-Objective Counterfactual Explanations2020
- Constraints-Based Explanations of Classifications2019
- Constraint-Variance Tolerant Data Repairing2016
- Detecting outliers: Do not use standard deviation around the mean, use absolute deviation around the medianJournal of Experimental Social Psychology, 2013
- NADEEF2013
- Holistic data cleaning: Putting violations into context2013
- Z3: An Efficient SMT Solver2008