Source-linked AI summary
Realistic Counterfactual Explanations via Denial Constraints
Avia Asael, Nave Frost, Amir Gilad, Daniel Deutch
TL;DR
Existing counterfactual methods can produce unrealistic instances while optimizing proximity and diversity. The paper uses Denial Constraints within a perturb-and-project framework to generate realistic counterfactuals, achieving full realism with modest quality costs and faster optimized search. The approach is evaluated on four benchmarks and remains scoped to tabular data.
Problem
Existing counterfactual methods may produce unrealistic instances while optimizing proximity and diversity, limiting their practical usefulness.
Method
The paper captures realism with Denial Constraints and combines counterfactual generation with perturbation, projection, and solver optimizations.
Results
Across four benchmarks, the approach achieves 100% realism with proximity and diversity comparable to unconstrained counterfactuals, while optimizations improve scalability.
Takeaways & Limitations
Realistic counterfactuals can be generated with relatively minor compromises in distance and diversity, while dedicated optimizations make the constrained search scalable.
Takeaways & Limitations
The constraint-based realism notion is specific to relational data, and extending it to unstructured domains is left to future work.
Abstract
from arXiv · showhide
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.
1 Introduction
Counterfactual explanations should be close, diverse, and realistic, but existing methods often produce unrealistic instances. This paper enforces realism with Denial Constraints and develops an optimized perturb-and-project framework that preserves counterfactual quality.
- Counterfactuals explain model predictions by perturbing an instance until its assigned label changes, thereby identifying significant features.
- Useful counterfactuals should combine proximity to the original instance, diversity across explanations, and realism.
- Existing approaches capture proximity and diversity extensively, whereas realism remains substantially more subtle and is addressed through varied strategies.
- Denial Constraints represent realism through logical conditions learned or inferred from datasets, including unary constraints on individual tuples and binary constraints over tuple pairs.
- The paper combines counterfactual optimization with DC adherence for the first time, while proving that realistic-tuple projection is NP-hard and that realism can conflict with label flipping and diversity.
- The perturb-and-project framework uses constraint caching, suspect-set filtering, and diversity-aware projection while treating the classifier as a black-box labeling oracle.
- Across Adult, NY Housing, Tax, and Census, DiCE produces 55.9–100% constraint-violating CFs, whereas the proposed solutions achieve zero violations.
- Proximity degrades by under 10% and diversity by ∼3% on most datasets versus DiCE, while optimizations reduce Census projection time by up to 63×.
2 Model
The paper formalizes counterfactual explanations using proximity, diversity, immutable attributes, and realism constraints expressed as denial constraints over relational data.
- Databases and Denial Constraints: Denial constraints are universally quantified first-order formulas that forbid specified predicate combinations over tuples in a relation.
- Databases and Denial Constraints: Binary denial constraints relate tuple pairs, whereas unary denial constraints restrict individual tuples; relations satisfy constraints when all applicable tuples or pairs do.
- Counterfactuals: A counterfactual is a tuple whose classifier label differs from the original tuple’s label.
- Counterfactuals: Proximity favors small changes, while diversity seeks multiple counterfactuals covering different reasons for classification.
- Problem Formulation: Realistic counterfactuals must preserve immutable attributes and remain consistent with the database and its denial constraints.
- Problem Formulation: The objective is to find k counterfactuals for an input tuple that satisfy the classifier, immutability, denial-constraint, proximity, and diversity requirements.
3 Generating Realistic Counterfactuals
The generation framework repeatedly perturbs an input to obtain diverse, nearby counterfactuals and projects them toward tuples satisfying realism constraints.
- Framework: Algorithm 1 maintains discovered counterfactuals and a candidate queue, iteratively perturbing candidates and projecting the resulting tuples.
- Projection Phase: PROJECT seeks a nearby tuple satisfying the denial constraints and immutable attributes, but the projection may change the classifier label.
- Framework: When a projected tuple is not a counterfactual, the algorithm queues it for another perturb-and-project iteration.
- Perturbation Phase: PERTURB generates k diverse counterfactuals near a tuple while respecting immutable attributes but ignoring denial constraints.
- Perturbation Phase: PERTURB builds on prior counterfactual-generation methods such as DiCE, which jointly optimizes classification confidence, distance, and diversity.
14 end
Projection is the framework’s main novelty: it maps perturbed counterfactuals into the space of realistic tuples, potentially requiring further iterations before label-changing valid candidates emerge.
- Projection Phase: Projection finds a nearby tuple satisfying the realism constraints, using implementation details described in Section 4.
- Projection Phase: A perturbed candidate can project to a realistic tuple that no longer changes the label, triggering another perturb-and-project iteration.
- Greedy Selection: Greedy selection chooses a size-k subset by maximizing the aggregate proximity and diversity score.
- Complete Pipeline: The complete pipeline repeatedly projects queued candidates and retains projections accepted by the model as realistic counterfactuals.
3 end
The algorithm includes implementation steps for fixing immutable-attribute violations and solving the projection objective.
- The implementation fixes immutable attributes before completing the projection procedure.
- The projection procedure sets its objective and invokes a solver.
4 Projecting over Denial Constraints
The projection problem seeks the nearest realistic tuple that preserves immutable attributes and satisfies denial constraints. Because DEC-PROJ is NP-hard, the paper uses SMT-based projection rather than seeking an exact polynomial-time solution.
- The projection algorithm combines perturbation, projection, and greedy selection to generate diverse realistic counterfactuals.
- DEC-PROJ minimizes distance subject to denial-constraint satisfaction and equality on all immutable attributes.
- DEC-PROJ is NP-hard even when the denial-constraint set contains only unary denial constraints.
- The paper therefore focuses on solver-based methods that perform well without guaranteeing polynomial-time convergence.
- The SMT baseline encodes forbidden regions from instantiated denial constraints, fixes immutable attributes, minimizes distance, and returns a solution or ⊥.
9 end
The projection implementation reduces repeated solver work by reusing constraint constructions and filtering constraints to tuples relevant to immutable values. A complementary diversity constraint prevents newly generated projections from being too similar to earlier ones.
- Projection: For each denial constraint and database tuple, the baseline instantiates forbidden regions that the projected tuple must avoid.
- Projection: Immutable-attribute constraints and distance minimization are added before the solver returns a feasible projected tuple or ⊥.
- Optimizer caching: Pre-processing caches O(|R| · |Σ|) constraint instantiations, so later projections add only immutable constraints and the distance objective.
- Suspect-set filtering: Suspect-set filtering builds constraints on demand using only tuples whose immutable values satisfy the relevant predicates.
- Combined optimization: Caching suspect-filtered constraints by immutable values enables reuse when those values remain unchanged across projections.
- Diversity constraints: Diversity constraints require each new projection to differ from every previous projection by more than one MAD unit in at least γ mutable attributes.
5 Experiments
Across four datasets, the proposed methods produce realistic counterfactuals while largely preserving proximity and diversity, and their projection optimizations substantially reduce runtime. The main cost is additional execution time relative to DiCE.
- Realism: Realism is guaranteed by the proposed solutions, whereas 55.9–100% of DiCE counterfactuals violate at least one constraint.
- Distance and Diversity: Under 10% proximity and ∼3% diversity differences occur on most datasets while the proposed methods maintain realism.
- Execution Time: Projection optimizations are up to 63× faster than vanilla solver use, including 301s and 334s versus 18,871s on Census.
- Execution Time: Compared with DiCE, the proposed methods incur 1.1–10.5× execution-time overhead as the cost of realism.
- Proximity: The proposed methods achieve comparable proximity to DiCE, with d istagg increases under 10% on Adult and Tax and up to ∼31% on Census.
- Proximity: On NY, the proposed method achieves 36–45% lower distagg than DiCE because DiCE overshoots into invalid regions.
- Diversity: DPP diversity scores are within 1.7% on Adult and 0.6% on Tax, identical or near identical on Census, and 7% higher for DiCE on NY.
- Diversity optimization: The diversity optimization raises NY’s DPP score from 0.714 to 0.913 while keeping proximity within 4% and adding negligible runtime overhead.
6 Related Work
Prior CF methods often omit explicit realism guarantees, while statistical and causal approaches capture only selected aspects or require unavailable knowledge. This paper uses expressive Denial Constraints to guarantee validity while jointly optimizing proximity and diversity.
- Many CF methods, including DiCE, do not directly address realism, and experiments show DiCE realism is unlikely to arise spuriously.
- Statistical approaches model realism as closeness to a learned distribution, whereas causal approaches require structural models or causal graphs that are rarely available and demand domain knowledge.
- Statistical plausibility does not guarantee validity because an instance can remain consistent with the learned distribution while violating data integrity rules.
- Unlike prior constrained CF methods, this work supports binary Denial Constraints and diversity, while modifying one tuple rather than the entire database.
- Denial Constraints provide explicit, exactly checkable rules and are expressive enough to guarantee that generated tuples satisfy realism requirements.
7 Conclusions
The paper formulates realistic CF generation as optimizing proximity and diversity under database-level Denial Constraints. Experiments show perfect realism with comparable CF quality and scalability enabled by dedicated optimizations.
- The paper studies CFs constrained to be realistic under Denial Constraints with respect to a given database.
- The method optimizes proximity and diversity within the space of constraint-satisfying counterfactuals.
- 100% realism is achieved with comparable proximity and diversity, whereas state-of-the-art solutions often produce non-realistic CFs.
- Dedicated optimizations recover scalability because the vanilla constraint-solver-based solution is not scalable.
- Future work includes additional optimizations and implementations in application domains such as adversarial robustness.
B Additional Experimental Details
The experiments span four datasets with domain-specific prediction tasks, immutable attributes, and mined or manually specified Denial Constraints. Runtime scales linearly with dataset size and constraint count, while diversity remains generally comparable to DiCE.
- The evaluation uses Adult, NY-Housing, Tax, and Census-Income datasets covering income, property-price, tax-rate, and related income classification tasks.
- Immutable attributes restrict which features CFs may modify, with representative fixed attributes chosen for Adult, Census, and NY-Housing, but none for Tax.
- Constraints combine FastADC-mined rules with domain-crafted unary constraints; Census uses 200 sampled constraints from 2,566 to preserve tractability and diversity.
- Runtime vs Dataset Size: Runtime scales linearly with dataset size: on Adult, PreProc takes 0.35s and Suspect 2.18s at 30K tuples, while Suspect uses less memory.
- Runtime vs Number of Constraints: With 1 to 8 Tax constraints, PreProc grows from 0.42s to 0.58s, whereas Suspect grows from 0.99s to 5.41s because it rebuilds the optimizer per projection.
- Diversity: Pairwise diversity is comparable to DiCE on most datasets, with the largest gap on NY because constraints create a tight feasible region.
- Diversity: The framework currently optimizes DPP diversity rather than directly optimizing pairwise or minimum-distance diversity.
C.3 Suspect-Set Optimization Evaluation
Suspect-set filtering substantially reduces projection overhead, while HoloClean leaves most violations unresolved. The solver-based projection supports multiple distance functions, with runtime tracking encoding complexity.
- Suspect-Set Filtering: Suspect reduces bounds-building time by 6–35× compared with PreProc, with the largest Census gain being 6,168s versus 176.8s.
- Suspect-Set Filtering: Suspect reduces optimizer instantiations by up to 96.5% on Census, from 7.19M to 246K, and by 85% on Adult and NY.
- HoloClean Comparison: HoloClean leaves 89% of Adult violations and 100% of NY violations unresolved, making general-purpose cleaning unsuitable for targeted tuple projection.
- Distance Functions: The projection solver supports L0, distagg, and custom domain-specific distance functions, including semantic transition costs and impossible transitions.
- Distance Functions: Runtime follows distance-function complexity: L0 takes 0.17s, distagg 0.35s, and the custom function 1.13s on Adult.