Research map / Learning theory and algorithms / Prediction and decision losses
Generating Likely Counterfactuals Using Sum-Product Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LiCE, a mixed-integer optimization method that encodes a fitted sum-product network's log-likelihood as MIO constraints to generate close, sparse, and plausible counterfactual explanations.
Problem
Counterfactual explanations often sacrifice distance and sparsity when optimizing for plausibility, and existing plausibility estimators (VAEs, GMMs, KDE) handle categorical features poorly or lack exact likelihood computation.
Approach
Formulate a trained sum-product network (log-space, with sum nodes approximated by max via big-M binary slacks) as a mixed-integer program, so that CE likelihood can be maximized or thresholded directly alongside validity, MAD-based distance, sparsity, and actionability constraints in one globally optimal MIO.
Key results
- MIO formulation of the SPN approximates the true SPN log-likelihood with mean error around 0.09 to 0.53 nats (about 2.9% at worst), per Table 1.
- LiCE (optimize) and MIO achieve 100% validity and actionability on GMSC and Adult, and the best similarity and sparsity among compared methods (e.g., Credit similarity 4.39 vs 12.9 for C-CHVAE).
- LiCE (median) yields the highest-likelihood CEs on GMSC and Adult among methods, though with lower success rates (60% on GMSC).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Optimize distance jointly with likelihood (α = 0.1) and relax the plausibility constraint rather than use the median likelihood threshold (ablation) | LiCE · GMSC | Similarity (MAD distance): 10.991793505652852 -> 5.871975675449956 | Helped |
| Optimize distance jointly with likelihood (α = 0.1) and relax the plausibility constraint rather than use the median likelihood threshold (ablation) | LiCE · Adult | NLL: 12.863731934272424 -> 18.14528819185729 | Helped |
| Add the SPN likelihood formulation to the MIO optimization rather than use it only for post-hoc selection (ablation) | MIO · GMSC | NLL: 27.866216730694337 -> 25.6180484331279 | Helped |
| Add the SPN likelihood formulation to the MIO optimization rather than use it only for post-hoc selection (ablation) | MIO · Credit | NLL: 43.584538056112685 -> 28.785663175658833 | Helped |
| Add the SPN likelihood formulation to the MIO optimization rather than use it only for post-hoc selection (ablation) | MIO · Adult | NLL: 17.7958828931424 -> 18.14528819185729 | No clear effect |
| Use a median log-likelihood threshold and set α = 0 instead of optimizing the distance-likelihood combination (ablation) | LiCE · GMSC | Similarity (MAD distance): 5.871975675449956 -> 10.991793505652852 | Hurt |
| Use a median log-likelihood threshold and set α = 0 instead of optimizing the distance-likelihood combination (ablation) | LiCE · Adult | Sparsity (changed features): 2.07 -> 2.9955849889624724 | Hurt |
| Use a median log-likelihood threshold and set α = 0 instead of optimizing the distance-likelihood combination (ablation) | LiCE · Credit | Similarity (MAD distance): 4.391437014356211 -> 4.372400589776368 | No clear effect |
Surprising findings
- Adding the SPN as a post-hoc filter to DiCE performs significantly worse than the directly formulated approach.
- LiCE (optimize) beats MIO on Adult in similarity despite MIO directly optimizing distance, attributed to selecting the most likely CE from a set of 10 that includes farther local optima.
Limitations
- Scalability and computational cost inherent to MIO; time concerns once full SPN is formulated.
- Plausibility relies on the SPN's ability to model the true data distribution; the correlation with true probability is only empirically supported.
- Some methods (e.g., LiCE median) fail to produce candidates within the time limit, lowering success rates.
Experimental setup
Datasets: Give Me Some Credit Adult German Credit
Benchmarks: Give Me Some Credit Adult German Credit
Metrics: negative log-likelihood (SPN) MAD-weighted distance number of changed features validity rate actionability rate
Baselines: DiCE VAE C-CHVAE FACE PROPLACE MIO (without SPN)
Builds on: sum-product networks mixed polytope encoding OMLT LearnSPN DACE
Closest papers by meaning
- Promoting Counterfactual Robustness through Diversity (AAAI 2024 · similarity 0.88)
- Robust Stochastic Graph Generator for Counterfactual Explanations (AAAI 2024 · similarity 0.88)
- Counterfactual Explanations for Misclassified Images: How Human and Machine Explanations Differ (Abstract Reprint) (AAAI 2024 · similarity 0.88)
- LeapFactual: Reliable Visual Counterfactual Explanation Using Conditional Flow Matching (NeurIPS 2025 · similarity 0.88)
- Counterfactual Explanations of Time Varying Rankings (Student Abstract) (AAAI 2025 · similarity 0.87)
- Towards Unifying Evaluation of Counterfactual Explanations: Leveraging Large Language Models for Human-Centric Assessments (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.