Generating Likely Counterfactuals Using Sum-Product Networks
Authors: Jiří Němeček
Tomáš Pevný
Jakub Marecek
Venue: ICLR 2025 Poster (2025)
Keywords: counterfactual explanations
mixed-integer optimization
sum-product networks
Primary area: interpretability and explainable AI
TL;DR: We propose a method for finding Counterfactual Explanations with high-likelihood using Mixed-Integer Optimization (MIO). For the likelihood estimation, we propose an MIO formulation of Sum-Product Networks.

Abstract: The need to explain decisions made by AI systems is driven by both recent regulation and user demand. The decisions are often explainable only post hoc. In counterfactual explanations, one may ask what constitutes the best counterfactual explanation. Clearly, multiple criteria must be taken into account, although "distance from the sample" is a key criterion. Recent methods that consider the plausibility of a counterfactual seem to sacrifice this original objective. Here, we present a system that provides high-likelihood explanations that are, at the same time, close and sparse. We show that the search for the most likely explanations satisfying many common desiderata for counterfactual explanations can be modeled using Mixed-Integer Optimization (MIO). We use a Sum-Product Network (SPN) to estimate the likelihood of a counterfactual. To achieve that, we propose an MIO formulation of an SPN, which can be of independent interest. The source code with examples is available at https://github.com/Epanemu/LiCE.

Published as a conference paper at ICLR 2025
GENERATING LIKELY COUNTERFACTUALS USING SUM-PRODUCT NETWORKS
Jiří Němeček, Tomáš Pevný & Jakub Mareček
Department of Computer Science
Faculty of Electrical Engineering, Czech Technical University
Karlovo náměstí 13, Praha 2, 121 35
{nemecek. jiri, pevnytom, jakub.marecckkee......... wakabbmarecckfffll..rttt.
ABSTRACT
The need to explain decisions made by Al systems is driven by both recent reg- ulation and user demand. The decisions often explainable only post hoc. In counterfactual explanations, one may ask what constitutes the best counterfac- tual explanation. Clearly, multiple criteria must be taken into account, although "distance from the sample" is a key criterion. Recent methods that consider the plausibilitty of counterfactual seem to sacrifice this original objective. Here, we present a system that provides high-likelihood explanations that are, at the same time, close and sparse. We show that the search for the most likely explanations satisfying many common desiderata for counterfactual explanations can be mod- eled using InxeeeInteger Optimization (MIO). We use (SPN) to estimate the likelihood of a counterfactual. To achieve that, we propose MIO formulation of an SPN, which can be of independent interest. The source code with examples is available at https: /gitttb.t..gggggggg com coom//paanem/LiCC.
Network
INTRODUCTION
A better understanding of deployed AI models is needed, especially in high-risk scenarios (Dwivedi al.. 2023). Trustworthy and explainable AI (XAI) is concerned with techniques that help peo- ple understand, manage, and improve trust in Al models (Gunning et al., 2021; Burkart & Huber, 2021; Bodria al., 2023). Explanations also serve an important role debugging models to ensure that they do not rely spurious correlations and traces of processing correlated with labels, such as timestamps. In a post-hoc explanation, a vendor of an AI system provides an individual user with a personalized explanation of individual decision made by the AI system, improving the model's trustworthiness (Karimi et al., 2022; et al., 2023). this context, personalized explana- tions often called local explanations because they explain the model's decision locally, around given sample, such as one person's 's input. Thus, local explanations provide information relevant to the user without revealing global information about the model, regardless of whether the model is interpretable a priori.
Consider, for example, credit decision-making in financial services. The models utilized need be interpretable a priori, ef. the Equal Credit Opportunity Act in the US (ECOA) and related regulation (European Commission, 2016a;b) in the European Union, but an individual who is denied credit may still be interested in personalizee, local explanation. A well-known example of local explanations the counterfactual explanation (CE). CE answers the question "How should sample be changed to obtain a different result?" (Wachter et al., 2017). In the example of credit decision- denied client might ask what they should do to obtain the loan. The answer would take the form of a CE. For example, "Had you asked for half of the loan amount, your application would have been accepted"' As illustrated, CE can be easily understood (Byrne, 2005; Guidotti, 2022). How- ever, their usefulness is influenced by many factors (Guidotti, 2022), including validity, similarity, sparsity, actionability, and plausibility.
This work focuses the plausibility of counterfactual explanations. Unfortunately, plausibility does not have a clear definition. The definition of Guidotti (2022) suggests that CE should not be an outlier and measures it as the mean distance to the data. A Local Outlier Factor is often used

---

Published as a conference paper at ICLR 2025
Table 1: Method comparison. A check mark indicates that given method claims possess the given fea- ture. The star symbol (*) means that method modellaggnsstc as long as the classifier can expressed using MIO. Complex data means data with continuous, categorical, ordinal, and discrete contiguous values. Exogenous property means that a method can generate unseen data samples as CEs. Regarding actionability, C-CHVAE disregards the monotonicity of features, and DiCE claims to achieve actionability through diversity without any data- specific constraints in place. All methods require validity and optimize some notion of simi- larity.
Method
Plausibility
Sparsity
Actionability
Complex data Model-ngnostic
Exogenous
PROPLACE
Jiang al., 2024)
C- C-CHAAE
(Pawelezyk el al., 2020)
only immuut
FACE
(Poyiadzi et al., 2020)
DICE
(Mothilal et al., 2020)
PlaCE
(Artelt & Hammer, 2020)
DACE
(Kanamori al., 2020)
LICE
Proposed here (Section 5)
4
(e.g.. Kanamori et al., 2020), but this method is not invariant of the data size. Alternatively, Jiang et al. (2024) define "plausible region" as convex hull of ls nearest neighbors of the factual. How- ever, this region can still contain outliers. One can also use generative models, such as Adversarial Random Forests (Dandl et al., 2024) that incorporate plausibility in the generation process. This approach relies on multi-objective heuristic optimization.
Many other methods consider estimating the likelihood of CEs as a proxy for plausibility. This ap- proach aligns with the definition of CE not being an outlier since outliers will have a low likelihood. One such approach uses (Conditional) Variational Auto-Encoders (Jordan et al., 1998; Pawelezyk et al., 2020; Stevens et al., 2024) in likelihood estimation. This approach does not provide good way to handle categorical inputs and does not provide an efficient way to compute the exact likeli- hood of a CE. Plausible CE (PlaCE) proposed in (Artelt & Hammer, 2020) uses Gaussian mixture models in the framework of convex optimization maximize likelihood in CE generation. lim- itations are the inability to handle categorical features and non-linear classifiers. Another common way to estimate likelihood is Kernel Density Estimation (KDE), which shares the inability to handle categorical features well. KDE is utilized by, e.g., FACE (Poyiadzi et al., 2020), which can also return CEs only from the training set.
Our Contribution We propose Likely Counterfactual Explanations (LiCE) method, which op- timizes plausibility in combination with other desiderata (see Table 1). LiCE uses Sum-Product Networks (SPNs) of Poon & Domingos (2011), which are state-of-the-ar tractable models es- timate likelihood. They naturally handle categorical features. This work combines the tradition of tractable probabilistic models with mixed-inie integer formulations by formulating the former in the latter.
In particular, we propose:
Network estimating log- likeliioiiood Sum- Product Network as measure of plausibility of CE, which allows the integration of plausibility directly into the MIO formulation.
A mixed-integer formulation of a trained
LiCE method for the generation of CEs. An MIO model that can be constrained by or optimized with respect to common desiderata regarding CE generation.
The advantage of our approach can be illustrated with an example from the German Credit dataset (Hofmann, 1994). See Figure 1, where CEs produced by several methods considering the diversity or plausibility of CE are compared against the factual (white cross) in the plane, where the horizontal axis represents the amount of credit and where the vertical axis is the duration.
For example, C-CHVAE (Pawelezyk et al., 2020), VAE and FACE (Poyiadzi et al., 2020) suggest reducing the duration by one year more. The most plausible explanation produced by DiCE (Mothilal et al., 2020) counter-intutively suggests doubling the credit amount to obtain it. PRO- PLACE (Jiang et al., 2024) suggests decreasing the credit amount below a third of the original amount. All of these counterfactuals are quite distant from the factual. In contrast, MIO finds a counterfactual with the sought credit amount and suggests decreasing the loan duration by single
2

---

Published as a conference paper at ICLR 2025
Log-likelihood of counterfactuals Credit dataset
LICE (ours)
MIO (ours)
Duration [months]
PROPLACE
(knn)
20
C-CHVAE
VAE (+SPN)
DICE (+SPN)
Factual
10
5
2000
4000
6000
8000
Credit amount
Figure 1: The heatmap shows the marginalized log-likelihood distribution of the German Credit dataset into a 2-dimensional space of Credit amount and Duration features, with extremely low values clipped to - 1225 for visual clarity. The factual (white cross) and CEs are also projected the dimensions. The factual classified as being denied. Most CE methods choose distant points, sometimes with poor likelihood. The proposed method (LiCE) strikes a balance between likelihood and proximity.
month. Because the visualization is 2-dimensional projection, some changes are not visualized. LICE changes only one "hidden" feature. All other methods change at least five features (except MIO, which changes three), showing poor sparsity.
This example illustrates the issue of considering plausibility exclusively, High plausibility should ensure that the counterfactual is not outlier, i.e., it is "realizable" by the client. However, this can lead to non-sparse, distant CEs, which are nonetheless difficult to realize.
Notation used Throughout the paper, we consider classification problem in which the dataset D is a set of 2-tuples (x, y) E 'D. Each input vector x E X C RP consists P features and is taken from the input space that can smaller than P-dimensional real space (e.g., can contain categorical values). Iÿ is the value of the j-th feature of the sample x. We have C' classes and describe the set of classes [C] {1.....Cu C}. y E [C] is the true class of the sample x. Finally, we have classifier h(x) = ÿ E [C]] that predicts the class ÿ for the sample x. More details on the notation are given Section A.
PREREQUISITES
2.1 COUNTERFACTUAL EXPLANATIONS
We define counterfactual explanation in accordance with previous works as x' E X such that hxx) * h(x') and the distance between x' and et al., 2017). We refer to x as factual and x' as counterfactual or CE. As mentioned above, there are many desiderata regarding the properties of CEs. Following Guidotti (2022), the common desiderata in which are interested are:
some sense minimal (Guidotti, 2022; Wachter
Validity. x' should be classified differently than X
Similarity, x' should be similar (close) to x
Sparsity. x' should change only few features compared to i.c., minimize ||x x|/o Actionability. A counterfactual should not change features that cannot be changed (im- mutability). This includes the monotonicity of some features, e.g., age can only increase.
Plaustbilliyy CEs should have high likelihood (be plausible) with respect the distri- bution that has generated the dataset D. This is sometimes interpreted as not being an outlier.

---

Published as a conference paper at ICLR 2025
Guidotti (2022) describes also other desiderata, which we discuss in Section B.1
2.2 MIXED-INTEGER OPTIMIZATION
Mixed-Integer Optimization (MIO, (Wolsey, 2020)) is a powerful framework for modeling and solv- ing optimization problems, where some decision variables take values from a discrete set while others are continuously valued. Non-trivially, the problem is in NP (Papadimitrion, 1981) and is NP-Hard, in general. There has been fascinating progress in the field in the past half-century (Bixby, 2012). State-of-the-arr solvers based on the aaneehh-and-uuud-adddd find global, certified optima for instances with millions of binary variables within hours, while there are pathological instances on under a thousand variables whose global optima are still unknown. Naturally, MIO is widely used in those areas of machine learning where both discrete and contin- uous decision variables need to be optimized jointly (e.g.. Huchette et al., 2023). We use the more general abbreviation MIO, though we consider only mixed-integs linear formulations.
approach can often
A crucial advance has been the mixed polytope formulation of Russell (2019), which neatly com- bines categorical and continuous values. A feature j takes continuous value from the range [T.j, Uj] or one of the K distinct categorical values. This is useful for modeling data with missing values, especially when there is a description of why the value is missing (Russell, 2019). To model the mixed polytope (Russell, 2019) of counterfactual for the feature j. we create a one-hot encoding for K2 discrete values into binary variables dj and continuous variable ey with binary indicator variable d goomt equal to I when the feature takes continuous value. In summary:
K2 Σ
dg d coot 1
Cj F,d cont 11 + Uj
(2)
0 1, < (F₃ - )dj cont
(3)
0 < (U, - Fj Fj)d cont
(4)
d nn d2, (0.1)
Wk. [Ky],
(5)
where F, either the original value z, or the median value of continuous data of the mixed feature j if the factual zj has one of the categorical values instead. Constraint (2) fixes the value of ej using two non-negative variables, ln and uj representing the decrease and increase in the continuous value, respectively. This construction facilitates the computation of the absolute difference from the factual. Since we minimize their (weighted) sum, at least one of them will always equal (Russell, 2019).
2.3 SUM-PRODUCT NETWORKS
Probabilistic circuits (PCs) (Choi et al., 2020) tractable probabilistic models (or rather, computa- tional graphs) that support exact probabilistic inference and marginalization in time linear w.r.t. their representation size. Probabilistic circuits defined by tuple (9, (),,,, where rected Acyelic Graph (DAG) defining the computation model, scope function & V + 2 detines a subset of features over which the node defines its distribution, and set of parameters 0. The root node root (a node without parents) has the scope function equal all features, i.e., root) = [P]. To simplify the notation, we define a function pred(n), giving a set of children (predecessors) of an inner node n and denote Tw(n)) the features of x within the scope of n.
(V, is Di-
An important subclass of PCs is Sum Pun-Product Networks (SPNs), which restrict PCs such that the inner (non-leaf) nodes are either sum nodes ()²²) or product nodes ()!l).
Leaf node n E VL- = {n pr)d(n)) 9} within SPNs takes value O,,. from a (tractable) distribution over its scope ((n") parametrized by 0₂2..
Product node n E y!I performs a product of probability distributions defined by its children
(I)(())))== = II
Oa(Emaa))
(6)
aE))od(nn)
4

---

Published as a conference paper at ICLR 2025
The scope of product nodes must satisfy decomposability. meaning that the scopes of its children are disjoint, i.., " va(a) = 0, but complete Uaepred(n (b(a) = vnn"))
Sum node n² V has its value defined as
0₂ (Z)(())) =
Σ eEprod(n2)
Wann= Oa(Fip(a))
where weights Wa,n= 2 and Eaepred(n W Wann of distributions defined by its children. The scope of each sum node must satisfy completeness (smoothness), i.e., it must hold that v((a)) = (b2))) Va,, a2 E pred(n").
The value of a sum node is thus a mixture
3 RELATED WORK
Pioneering work on counterfactual explanations (under the name "optimal action extraction")) by Cui et al. (2015) considered classifiers based on additive tree models and extracted an optimal plan to change a given input to desired class at a minimum cost using MIO. In parallel, similar approaches have been developed under the banner of "actionable recourse" (Ustun et al., 2019) or "algorith- mie recourse" (Karimi et al., 2022; 2021). Developing upon this, Karimi et al. (2021) distinguish between contrasting explanations and consequential explanations, where actions are modeled explic- itly in a causal model. Raimundo et al. (2024) coined a broader term "counterfactual antecedents". We use the term counterfactual explanations (CEs), popularized by, c.g., Wachter et al. (2017).
There is a plethora of work on the search for CEs, as recently surveyed (e.g.. Karimi et al., 2022; Burkart & Huber, 2021: Guidotti, 2022; Bodria et al., 2023; Laugel et al., 2023). Below, focus on methods for local CEs, with objectives related to the plausibility of CEs.
DACE (Kanamori et al., 2020) utilizes an MIO formulation, minimizing combination of & -noor based Mahalanobis' distance and I-Local Outlier Factor (1-LOF) for plausibility. The use of 1-LOF requires the of O(ID)) variables and ( constraints. We improve DACE by formulating the SPN as MIO to compute the likelihood. Thus, the number of variables and constraints does not depend on the dataset size but the size of the SPN. Moreover, our flexible formulation allows us to maximize plausibility or constrain the CE not to be an outlier, similar to DACE. PROPLACE (Jiang al., 2024) is also an MIO-baser method for finding robust CEs within a "plausible region". The region is constructed as convex hull of the factual and its (robust) nearest neighbors. The neighbors can, however, be outliers if a factual is not in a dense region of the data. Therefore, this approach not faithful to the plausibility definition we use (Section 2.1) FACE (Poyiadzi et al., 2020) selects a CE from the training set D. rather than generating from X. works by navigating a graph of samples x E D, where edge exists between two samples if they are close or by connecting k- nearest neighbors. It further requires that a sample has density (evaluated by KDE) above a certain threshold. This approach is limited by the inability to generate exogenous CEs, which is not the case for our method. Del Ser et al. (2024) evaluate plausibility using the discriminator from a trained Generative Adversarial Network without estimating the data distribution directly.
However, similarly to LiCE, some works estimate the data distribution via a probabilistic model, such as Variational Auto-Encoder (VAE, Mahajan et al. (2020)). C-CHVAE (Pawelezyk et al., 2020) uses a Conditional VAE to search for plausible (they use the term faithful) CEs without the need of metric in the original space. However, VAE provides only lower bound on likelihood, and the solution lacks any guarantees of optimality. PlaCE (Artelt & Hammer, 2020) uses a Gaussian Mixture Model (GMM) to represent the data distribution. Their formulation approximates a GMM by quadratic term and uses a general convex optimization solver. However, GMMs cannot handle categorical features, which are frequent in datasets of interest. More recently, CeFlow (Duong et al., 2023), PPCEF (Wielopolski et al., 2024) and Dombrowski et al. (2024) use Normalizing Flow Models, which, like GMMs, are non-trivial to formulate using linear constraints.
LiCE uses SPNs, probabilistic models that are tractable, naturally handle categorical features, and can have linear MIO formulation. SPNs are a strict generalization of GMMs (Aden-Ali & Ashtiani, 2020). We refer to Appendix G.3 for further discussion using SPNs. Furthermore, while some research showed users' preference for counterfactual similarity in favor of plausibility (Kuhl et al., 2022), LiCE allows to balance these objectives using a single parameter.
5

---

Published as a conference paper at ICLR 2025
4 MIXED-INTEGER FORMULATION OF SPN
Our contribution is built on a novel formulation of likelihood estimates provided by a Sum-Product Network (SPN) in Mixed- Mixed-Integer Optimization (MIO). Eventually, this makes it possible to utilize the estimate to ensure plausible counterfactuals generated using MIO. Specifically, we propose an MIO formulation for log space variant of a fitted SPN (Poon & Domingos. 2011) with fixed parameters. We perform all computations in log space because it enables formulation of product nodes with linear constraints, while sum nodes can be well upproximated. In addition, it makes optimization less prone to numerical instabilities.
Let us introduce the MIO formulation following the definition SPN Section 2.3:
Leaf nodes In any SPN, the leaves are represented by probability distributions over a single fea- ture. In the case of discrete random variables, we can utilize the indicator dj,8 that feature j has value k in the one-hot encoding. In the case of continuous random variables, we can utilize his- togram approximations, that is, piecewise linear functions, whose mixed-integer formulations have been studied in considerable detail (cf. Huchette & Vielma, 2023). We suggest and utilize alter- native formulation a histogram described in Section C.2.
Product nodes In any SPN, each node n combines the outputs Oas pred(n) of its predeces- sors. Consider now a product node n E V with output defined as a product of predecessor outputs. Since consider all computations in log space, this translates
On
Σ Oa
Vn V
(8)
(Epred(x))
Sum nodes A sum node E 12 is defined as weighted sum of predecessor a outputs. In log space, the sum would translate of log Euspred(n)) Wa,n exp(o.). which we cannot easily for- mulate as a linear expression. Considering wa,n exp(o,) = exp(o, + log Wa,n), we can approximate log Σ cxp(2) (2) by max Specifically, let 2a oa + log Wan and we bound
max Za = log exp( max a aEpred(n)
za)
aEpred(n)
log exp(za) 0%
(Epred(x)
log
[pred(n)) exp( max zn) log([pred(n) aEpred(n)
max Zn. aEpred(n)
In other words, the approximate value on of sum node n can be bound by the true value of as 0f log((pred(n))) I o₂ = max 2a S 0z aEpred(n)
meaning that our approximation is a lower bound of the true of, and the error in the estimate is the most logarithm the number of predecessors. If we wanted an upper bound, we could easily add log( log((pred(r))) to the value on, To formulate the max function, can linearize it by introducing slack binary indicators ma,n E {0, 1} for each predecessor a of sum node n
On S 0n + log Wa,n + Ma,n TTLL Vn E V Va pred(n)
Σ (Eprod(n)
Ma,n [pred(n)) -1 Vn E D
(10)
where TLL is a big enough "big-M" constant (Wolsey, 2020). Constraint (10) ensures that constraint (9) tight (o,, S 2a) for single predecessor for which my Since we maximize the likelihood, the value of will be equal to max, Za.
5 LIKELY COUNTERFACTUAL EXPLANATIONS
As our main contribution, we present a novel formulation for Likely Counterfactual Explanations (LiCE), which finds plausible CEs (with high likelihood) while satisfying common desiderata. Since

---

Published as a conference paper at ICLR 2025
the optimization problem is written MIO, the solution (CE) satisfies all constraints and is globally optimal. Throughout the section, we assume that all continuous values are scaled to the range [0, 1].
We now describe how we formulate the imput encoding, classification model, and various desiderata as MIO constraints. The potential of MIO to formulate similar constraints is well discussed in the literature (e.g., Russell, 2019; Kanamori et al., 2020; Mohammadi et al., 2021; Jiang et al., 2024), although the discussion rarely contains concrete formulations (Parmentier & Vidal, 2021). We dis- cuss MIO formulations of the desiderata specific for the mixed polytope input encoding (Russell, 2019) in Section B.3.
Input encoding To encode the input vector, we utilize the mixed polytope formulation (Russell, 2019), as explained in Eqs. 1-5 on page 4. The mixed polytope encoding works for purely continu- values by setting K; O. For fully categorical features, one must disregard the variable d doo as explained in more detail in Section C.I.
The input to the classification model (and to the SPN) is then of all variables cj and d₃ (but not d, cont) concatenated into a single vector. With some abuse of the notation, we denote this vector x'. When there is no risk of confusion, we denote the space of encoded inputs as X' and the number of features after encoding P.
Model formulation We encode the classification model using the OMLT library (Ceccon et al., 2022), which simplifies the formulation of various ML models, although we foeus Neural Net- works. Linear combinations in layers are modeled directly, while ReL.Us are modeled using big-M formulations, though other formulations are possible (Fischetti & Jo, 2018).
Validity Let hraw : XX + Z be the neural network model h(-) without activation at the output layer. Let hraw (x") be the result obtained from the model implementation. Assuming that have a binary classification task (C = 2), a neural network typically has a single output neuron (Z R). A sample is classified based whether the raw output is above below 0, i.e., h(x) [ [hraa (x) 2 0}. Thus, depending on whether the factual is classified as 0 or 1,, we set
haw (x)) 2 raw (x') S -T,
(11)
respectively, where 2 is margin that be set ensure higher certainty of the decision, improving the reliability of the CE. We present further formulations the validity for C > 2 in Section B.
Similarity and Sparsity To ensure similarity of the counterfactual, we follow Wachter et al. (2017) and Russell (2019) and use the somewhat non-standard ||-]] MAD norm, weighed by inverse Median Absolute Deviation (MAD)
||x 1,MAD
Σ
IJ MAD,
(12)
MAD; = modian (1æ, modian (x)dia)))
This metric also improves sparsity and adds scale invariance that is robust to outliers (Russell, 2019).
Actionability We call CE actionable if it satisfies monotonicity and immutability constraints. For immutability, the constraint is simply I = z/ for each immutable feature j. We can also set the input value as a parameter instead of variable, omitting the feature encoding. Modeling monotonicity, i.e., that a given value cannot decrease/inerease, is done using a single inequality for continuous features, e.g.. 1 for non-decreasing feature. For ordinal values, we fix zero all one-hot dimensions representing smaller ordinal values, for non-decreasing features. Similarly, we can enforce basic causality constraints. Details are provided in Section B.3.3.
Plausibility As explained in Section 4, fixed SPN fitted on the data allows us to estimate likelihood within MIO formulation. Negative likelihood can be added to the minimization objective with some multiplicative coefficient > 0. Alternatively, the likelihood can be used in constraints to force all generated CEs to have likelihood above a certain threshold 8SPN Such constraint is simply
OpTo > SPN
(13)
where 8SPN is hyperparameter of method, and Orroet is the likelihood estimated by the SPN.
7

---

Published as a conference paper at ICLR 2025
Full LiCE model
In summary, method optimizes the following problem:
arg min
(1 u) T cont + (d - d faet) T a Onroon
(14)
lu.d
s.t. mixed polytope conditions (1-5) hold
ML classifier constraints hold
validity constraints (e.g.. 11) hold
SPN constraints (8-10) hold
plausibility constraint (13) holds
data-specific desiderata (e.g., actionability) constraints hold,
where a is parameter of LiCE, weighing the influence of logelikel in the objective, and d represent the vectors obtained by concatenation of the parameters in Eqs. 1-5, The vector fact is the vector of binary variables of the encoded factual yonnt and vin represent weights for continuous and binary variables, respectively. The weights for feature j are 1/MAD, and thus Eq. 14 (when 0) correspond to Eq. 12. Details about data-specific constraints in Section E.1.
6 EXPERIMENTS
We first train a basic feed-forward Neural Network (NN) classifier with 2 hidden layers with ReLU activations. One could easily one of the variety of ML models that be formulated using MIO, including linear models, (gradient-bu boostedd trees, forests, or graph neural networks.
Secondly, train SPN model the likelihood on the same training dataset. We include the class y of a sample x in the training since we have prior knowledge of the counterfactual class. SPNs have variety of training methods (Xia et al., 2023), of which Domingos, 2013) implemented in the SPFlow library (Molina et al., 2019), though newer methods exist (e.g., Trapp et al., 2019).
variant of LearnSPN (Gens &
Data We tested on the Give Me Some Credit (GMSC) dataset (Fusion & Cukierski, 2011), the Adult dataset (Becker & Kohavi, 1996) and the German Credit (referred to Credit) dataset (Hof- mann, 1994). We dropped some outlier data and some less informative features (details Section D) and performed all experiments in a 5-fold cross-validation setting.
LiCE variants The main proposed model directly reflects the formulation (14). We compare two variants, with lower-bound the log-likelihood (8SPN) the median log-likelihood value of training samples, similar to Artelt & Hammer (2020). We also set a 0, to minimize purely the distance to factual. We refer to this LiCE (median). The other variant, LiCE (optimize), is the opposite, i.e., we optimize a combination of distance and likelihood with a 0.1 and relax the plausibility constraint (Eq. 13). MIO represents our method without the SPN model directly formu- lated. We use all constraints described in Section 5, without the plausibility and SPN constraints. We use the SPN post hoc to select the most likely explanation.
MIO and LiCE are implemented using the open-source Pyomo modeling library (Bynum et al., 2021) that allows for the simple use of (almost) any MIO solver. We use the Gurobi solver (Gurobi Optimization, ILC.C 2024). We solve each formulation for up to 2 minutes, after which we recover (up to) 10 best solutions. The entire implementation, together with the data, available at https: //github. com/ Doanemu/LiC.,
Compared methods We compare our methods the C-CHVAE (Pawelezyk al., 2020). FACE (Poyiadzi et al., 2020) and PROPLACE (Jiang et al., 2024) methods described in Section 3. We use the implementations of FACE and C-CHVAE provided in the CARLA library (Pawelezyk al., 2021). We run FACE in two variants, connecting samples within given distance (e) or by nearest neighbors (knn). For PROPLACE, we use the official implementation (Jiang et al., 2024). We omit PlaCE and DACE since their implementation does not support CE generation for Neural Networks.
In addition to those, we also compare to DiCE (Mothilal et al., 2020), a well-known method that focuses generating diverse set of counterfactuals. VAE is method using Variational Auto- Encoder. It is an implementation available version 0.4 of the DiCE library based on the work of Mahajan et al. (2020). For DiCE and VAF, select the most likely CE out of 10 generated CEs.
8

---

Published as a conference paper at ICLR 2025
Table 2: Approximation quality of the SPN. The first row shows the mean likelihood of CEs, evaluated by the SPN. The second row is mean output of MIO formulation same SPN. The third row shows mean difference.
GMSC
Adult
Credit
True SPN output
25.62 1 4.64
-18.15
3.89
-8..79 + 3.28
MIO formulation output (Onroos)
-25.71 + 4.71
-18.67 4.10
-99.01 = 3.34
SPN approximation error
0.09 + 0.57
0.53 + 0.47
0.23 + 0.24
Table 3: The proportion of factual instances for which given method generated valid or actionable counter- factual. Actionable CEs satisfy the immutability and monotonicity of relevant features (see Section 2.1).
GMSC (Fusion Cukierski, 2011)
Adult (Beeker & Kohavi, 1996)
Credit (Hofmann, 1994)
Method
Valid
Actionable
Valid
Actionable
Valid
Actionable
DiCE (+spn)
100.0%
100.0%
99.8%
65.4%
99 29
3.4%
VAE (+spn)
1.2%
0.2%
79.8%
22 6%
28. 2%
0.0%
C-CHVAE
84.8%
21.2%
13.4%
9.0%
11.6%
9.6%
FACE (c)
98.8%
15.8%
63. 2%
31.2%
28 28.0%
10.4%
FACE (kmn)
98.8%
14.8%
79.8%
45.4%
28 28.2%
11.2%
PROPLACE
98.8%
34.2%
79.8%
54.8%
28.2%
9.6%
MIO (+spn)
100.0%
100.0%
100.0%
100.0%
99.4%
99.4 %
LICE (optimize)
100.0%
100.0%
100.0%
100.0%
99.4%
%
LICE (median) 60.0%
60.0%
90.6%
90.6%
99.4%
99.4% %
If a CE method requires any prior training, we use the default hyperparameters (or some reasonable values, details in Section E.2) and train it on the same training set. If a given method can take into account actionability constraints, we enforce them.
Experimental settings For all experiments, we assume that the SPN and NN are fitted and fixed. We generate CEs for 100 factuals using each method for each fold, summing up to 500 factuals per dataset. The factuals are randomly selected from both classes. Methods that can output more CEs (MIO, LiCE, DiCE, VAE) are set to find at most 10 CEs, and we select valid CE with the highest likelihood (cvaluated by the SPN) post hoc. Further details on hyperparameters and experiment configurations provided in Section E.
Results To assess the quality of the MIO approximation of the SPN, we compare the CE likelihood computed by the MIO solver and the true value computed by SPN in Table 2. The worst approxi- mation error at 0.53 on average, which is just 2.92%. We find this surprisingly tight. Moreover, considering the differences between methods (cf. Table 4), this is acceptable.
The comparison of the CE methods is non-trivial since the factuals for which a given method suc- cessfully returned valid counterfactual are not the same for all methods. See Table for details on the success rate of the presented methods. For LiCE (median), the lower rates are caused by a failure to create counterfactual candidate in time. For other methods, it is also failure to follow the validity/actionabiiit criteria, especially for the case where a valid CE exists but an actionable does not. Overall, these results show that MIO-based methods have high success rate unless the constraints are too tight. Methods unconstrained by the likelihood, i.e., MIO and LiCE (optimize), have a 100% success rate, except for credit dataset, where few ill-defined samples had no action- able counterfactual w.r.t. the NN. For our methods, all generated CEs are guaranteed to be both valid and actionable.
We now compare CE methods on plausibility, similarity, and sparsity measured by negative log- likelihood (evaluated by the SPN), M. and by the number of modified features, respectively, see Table 4. The results are difficult to interpret since not every method produced valid CE for each factual. However, MIO and LiCE have success rates among the highest (cf. Table 3) and still perform best not only with regards to likelihood but also in terms of similarity and sparsity. Results on a subset of factuals for which each method generated a valid CE paint a similar picture, see Table 11 1 in Section F.2.

---

Published as a conference paper at ICLR 2025
Table Mean negative log- likelihood (NLL). ||| distance, and the number of changed features, measured on valid generated counterfactuals, by the SPN. The number of valid counterfactuals generated by given method varies (see Table 3), so the direct comparison between methods is non-trivial, The (+spn) means that the given method generates 10 CEs from which we choose the likeliest valid counterfactual using the SPN. For all measures, lower value is better.
information about standard deviation. log- oeeliikli estimated
GMSC (Fasion & Cukianski, 2011)
Adult (Bocker & Kohavi, 1996)
Credit (Hotmann, 1994)
Method
NLL
Similarity
Spunsity
NLL
Similarisy
Spursity
NLL
Similarity
Spansity
DACE (tspp)
29.1
27.3
27.7 4:
8.7 4:
VAR (45pm)
18.0
2.2
17.2 + 3.7
8.0 + 1.2
18.4 + 3.6
37.1 + 13.2
5.4 + 1.5
48.5 + 17.1
28.2 + 7.5
10.8
C-CHVAE
25.6 - 2.4
18.0 4.7
8.3 0.7
18.0 3.4
8.2
288 0.9
32.3 3 3,6
12.9 1.8
6.6 1.5
7.6
8.4
18.4
FACE (knn)
29.0
15.0 +
8.4++1.1
14.3 +
14.3 7.8
3.7
44.2 17.5
18.6
7.1+1..5
PROPLACE
27.9 4.3
12.9 =
6.4
15.4 +
23.2 266 8.6
4.8
384 15.2
24.467
9.0
(+spn)
1.5 6.
0.8
LICE (optim.)
4.66
5.9
2.6 1.1
18.1 1: 3.9
5.6 1: 3.8
2.1 1.0
28.8 1 3.3
4.4 2.88
2.3 2.3
LaCE (median)
2:2
11.0 + 3.4
4.4 1.2
12.9 + 1.0
9.7 + 6.6
3.0 + 1.4
29.9 3.1
4.4.#22 2.9
2.1 1.2
The plausibility of LiCE (median), evaluated by the SPN, seems to be the best across datasets. Except for GMSC, where VAE is comparable (on very few factuals 1.2%). Interestingly, the optimizing variant of LiCE achieves a better mean objective value on Adult and GMSC than the median variant, despite the median version's objective function not accounting for the NLL. This is in part because LiCE (optimize) has a bigger feasible space, allowing it to generate closer CEs with likelihood worse than the median of the training set. The fact that LiCE (optimize) beats MIO Adult in similarity (which MIO directly optimizes) is counterintuitive. is caused by choosing the most likely CE out of set of 10. This set includes local optima that are farther from the factual, but might have a higher likelihood.
Although for some datasets, the plausibility results are comparable between multiple methods, the similarity and sparsity remain dominated by our methods. We must also point out that merely adding the SPN as a post-hoc evaluation to some existing method (e.g.. DiCE) performs significantly worse. Further comparisons and discussion of the results are in Sections F and G.
Limitations Our method shares the limitations of all MIO methods with respect to scalability and computational complexity. The additional SPN formulation leads to some computational overhead, especially when using the likelihood threshold, exemplified in the results the GMSC dataset in Table 3.
Our method relies bility of an SPN to accurately model the data distribution. We empirically show a strong correlation between the SPN likelihood and the true probability in Section G.4. Furthermore, in Appendix F.4, we use synthetic data to show that the true probability of CEs generated by LiCE is comparable to the probability CEs generated by other well-performing methods.
SPN to evaluate likelihood, i.e., plausibility. One may question the capa-
7 DISCUSSION AND CONCLUSIONS
We have presented a comprehensive method for generating counterfactual explanations called LiCE. In Section 5, we show that our method satisfies the most common nasidyl validity, simi- larity, sparsity, actionability and, most importantly, plausibility.
Our method shows promising performance at the intersection of plausibility, similarity, and spar- sity. It also reliably generates high-quality, valid, and actionable CEs. However, time concerns are relevant once the full SPN is formulated within the model.
In future work, the limitations using MIO could be addressed by approximation algorithms. Ad- ditionally, other SPN-based models (e.g., Trapp al., 2020) could be considered to estimate plau- sibility. Last but not least, the MIO formulation of a Sum-Produc Network can be independent interest.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work has received funding from the European Union's Horizon Europe research and innovation programme under grant agreement No. 10107056. The contribution of Tomák Pevný has been funded by the Czech Grant Agency under project 22-32620S. Finally, access to the computational infrastructure of the OP VVV funded project wtt.0....110..000.///// 0t0000//166019/000766666666 001900000655 "Research Center for Informatics" is also gratefully acknowledged.
We thank anonymous reviewers for their insightful comments that led to the strengthening of this work.
REFERENCES
Ishaq Aden-Ali and Hassan Ashtiani. On the sample complexity of learning sum-product networks. In Silvia Chiappa and Roberto Calandra (eds.). Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statisties, volume 108 of Proceedings of Machine Learn- ing Research, pp. 4508-4518. PMLR, 26-28 Aug 2020. URL https: / httpass:/rrceeeii//ee pgo.eeddings.
w.l..pres/vvl 100/////////0 Baeee-/dd----e a 100 html.
André Artelt and Barbara Hammer. Convex Density Constraints for Computing Plausible Counter- factual Explanations. Igor Farkaš, Paolo Masulli, and Stefan Wermter (eds.), Artificial Neural Networky and Machine Learning ICANN 2020, volume 12396, pp. 553-365. Springer Interna- tional Publishing, Cham, 2020. ISBN 7778--0030-6160990 doi: (0.1007/978-3-0363 0030-61609-0-110
Andre Artelt, Valerie Vaquet, Riza Velioglu, Fabian Hinder, Johannes Brinkrolf, Malte Schilling, and Barbara Hammer. Evaluating Robustness of Counterfactual Explanations. In 202/ IEEE Symposium Series Computational Intelligence (SSCI), pp. 01-09, Orlando, FL, USA, Decem- ber 2021. IEEE. ISBN 978-1-72819-048-1
doi: 10. 10.1109/SSI104451.22....88
Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. URL https:
//doi. wowooorg///// 10.
Robert E Bixby. A brief history of linear and mixed-integer programming computation. Documenta Mathematica, 2012:107-121, 2012. doi: 10.4171/dms/6/16. URL https: /doi. /1./ 4171/dms/ 6 16.
Francesco Bodria, Fosca Giannotti, Riccardo Guidotti, Francesca Naretto, Dino Pedreschi, and Sal- vatore Rinzivillo. Benchmarking and survey of explanation methods for black box models. Data Mining and Knowledge Discovery, pp. 1-60, 2023. URL https: //tp:i////cieee/ www...oooo...000000/.000 111618-023-00933--1
Dieter Brughmans, Lissa Melis, and David Martens. Disagreement amongst counterfactual expla- nations: How transparency can be misleading. TOP, May 2024. ISSN 1863-8279, doi: 10. s1 11150-024-0067022. URL https:tp/////....t. http///i..og..////////oo 111111110000011100000000000 00111177000000770---11
Nadia Burkart and Marco F. Huber. A survey the explainability of supervised machine learning. Journal of Artificial Intelligence Research, 70:245-317, May 2021. ISSN 1076-9757. doi: 10. 1613/jair. 1. 12228. URL https: http::::/ooooooooooooo 1o..g//...1111/// (aa/////arrr jair. 1.1228..
Michael L. Bynum, Gabriel A. Hackebeil, William Hart, Carl D. Laird, Bethany L. Nicholson, John D. Sürolla, Jean-Paul Watson, and David L. Woodruff. Pyomo Optimization Modeling in Python, 3rd Edition, volume 67. Springer, 2021. URL https: / //tc///ccii//// (eri..org11.1000 978 3- 030 58
Ruth M. J. Byrne. The Rational Imagination: How People Create Alternatives to Reality. The MIT Press. June 2005. ISBN
doi: 10.755 007755/miippess//56....0000 1.001.
Francesco Ceccon, Jordan Jalving, Joshua Haddad, Alexander Thebelt, Calvin Tsay, Carl Laird, and Ruth Misener. OMLT: Optimization & machine learning toolkit. Journal of Machine Learn ing Research, 23(349):1-8, 2022. URL http:// / jmir. wwwp.orrgaa..t..atm..t......oeee
html.
11

---

Published as a conference paper at ICLR 2025
YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying frame- work for tractable probabilistic models. Technical report, University California, Los Angeles, October 2020. URL http: /tt.aaaaaaaaaaaa//aa
www.ull.aaaa.. http:///pppppppeepprccccc...ooo pdf.
Zhicheng Cui, Wenlin Chen, Yujie He, and Yixin Chen. Optimal Action Extraction for Random Forests and Boosted Trees. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 179-188, Sydney NSW Australia, August 2015. doi: 10.1 10.11457788255827782222
ACM. ISBN 978- 10-1--553-3366--2
Susanne Dandl, Kristin Blesch, Timo Freiesleben, Gunnar König, Jan Kapar, Bernd Bischl, and Mar- vin N. Wright. CountARFactuals generating plausible model-agnostic counterfactual explana- tions with adversarial random forests. In Luca Longo. Sebastian Lapuschkin, and Christin Seifert (eds.), Explainable Artificial Intelligence, pp. 85-107, Cham, 2024. Springer Nature Switzerland. ISBN 7778-30331-63806 URL wttpt::t///........ 1 ink springer. com/ chapter 1eptter/10... 1007/ 118-3-03--6333 63800-888-----
Javier Del Ser, Alejandro Barredo-Arritaa, Natalia Diaz-Rodríguez, Francisco Herrera, Anna Saranti, and Andreas Holzinger. On generating trustworthy counterfactual explana- tions. Information Sciences, 655:119898, 2024. ISSN 0020-0255. doi: 10. 10.1016/j.ins ins.
2023.119898. URL https: /www///wwwww...//////////ww www.wwww...................w.www sciencedi com/ wwaam//scinneeeeeeeeeeeeeeeeeeee wwweeeeceeaaaieeeeeiieeee SSC20025523014854
Janez Demšar. Statistical comparisons of classifiers over multiple data sets. The Journal of Machine learning research, 7:1-30, December 2006. ISSN 1532-4435, URL httph: //dl. acm. org/ doi/10.
1248548.
Ann-Kathrin Dombrowski, Jan E. Gerken, Klaus-Robert Müller, and Pan Kessel. Diffeomorphic counterfactuals with generative models. IEEE Transactions on Pattern Analysis and Machine Intelligence, (155):3257-32744 2024. doi: 10. 109//PAM122223.339990.
Tri Dung Duong, Qian Li, and Guandong Xu. Ceflow: robust and efficient counterfactual ex- planation framework for tabular data using normalizing flows. In Hisashi Kashima, Tsuyoshi Ide, and Wen-Chih Peng (eds.), Advances Knowledge Discovery and Data Mining, pp. 133- 144, Cham, 2023. Springer Nature Switzerland. ISBN 978-3-031-33377-4 URL https: //link. springer. com/ wtt.ccc///c//eeeee wttpp/e/tptet..e// 1007 00077883-03----- 00--033-3377777 4_1.
Rudresh Dwivedi, Devam Dave, Het Naik, Smiti Singhal, Rana Omer, Pankesh Patel, Bin Qian, Zhenyu Wen, Tejal Shah, Graham Morgan, and Rajiv Ranjan. Explainable AI (XAI): Core Ideas, Techniques, and Solutions. ACM Computing Surveys, 55(9):194:1-94:33, January 2023. ISSN 0360-0300. doi: 10.1145/3561048
ECOA.
Equal Credit Opportunity Act (ECOA). https:/ /ww///ww.... law. pernell.edu. soccodeteex/111 http://///////////eeee/aaa /uwsssuuccapttrtrreeeeee 1974. Title 15 of the United States Code, Chapter 41, Subchapter IV, paragraph 1691 and following.
European Commission. Directive 2013/36/EU of the European Parliament and of the Coun- cil 26 june 2013 on access to activity of credit institutions and the prudential supervi- sion of credit institutions and investment firms, amending Directive 2002/87/EC and repealing Directives 2006/48/EC and 2006/49/cc., 2016a. URL https: / /eur -ear-lex..o www.eexeeee mour-lex.europa.co europa. Regalll=oonteem//////////o/oooo
310036. Accessed: 2023-04-30.
European Commission. Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016 the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing Directive 95/46/BC (General Data Protection Regulation).. 2016b. URL https: //err//eureee lex. 679/oj. Accessed: 2023-04-30.
Matteo Fischetti and Jason Jo. Deep neural networks and mixed integer linear optimization. Con- straints, 23(3):296-309) July 2018. ISSN 1572-9354. doi: 10. 10.10077/100011-18--22555
Credit Fusion and Will Cukierski. Give me some credit. https: attpss//kaggle... /wt./aaggll....o. com/
competi ttmpsttiiiisss VeMeSSeeeeeeeeeeeeeeeeeee t, 2011. Kaggle.
12

---

Published as a conference paper at ICLR 2025
Robert Gens and Pedro Domingos. Learning the structure of sum sum-product networks. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference on Ma- chine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 880,880, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. httt::t::: http///pocceddeee ngs.m. ml www.sres//// gens13. 1emm1..html.
Noam Goldberg, Steffen Rebennack, Youngdae Kim, Vitaliy Krasko, and Sven Leyffer. MINLP formulations for continuous piecewise linear function fitting. Computational Optimization and Applications, 79(1):223-233, May 2021. ISSN 1573-2894. doi: 10.10077/100899001-0002253
Riccardo Guidotti. Counterfactual explanations and how to find them: Literature review and benchmarking. Data Mining and Knowledge Discovery, April 2022. ISSN 1573-756X. doi: 00000//s110180022-00888033
David Gunning, Eric Vorm, Jennifer Yunyan Wang, and Matt Turek. Darpa's explainable ai (xai)
program: A retrospective. Applied Al Letters, 2(4))e61, 2021. doi: 10.1002/a12.61. URL
http//onnnnnnibbrrrrr wiwey com/ ht////ii/aaaa absl//as//// aba/aaas..0000 10. 1000//00211222 61.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL httph:tt/////
gurobi com.
Hans Hofmann. Statlog (German Credit Data), 1994. URL https://abiioogg///aaa C5NC77.
Joey Huchette and Juan Pablo Vielma. Nonconvex Piecewise Linear Functions: Advanced Formu- lations and Simple Modeling Tools. Operations Research, 71(5):1835-1883 September 2023.
ISSN 0030-364X. doi: 10. 20.1887/pre.201..1173.
Joey Huchette, Gonzalo Muñoz, Thiago Serra, and Calvin Tsay, When deep learning meets polyhe- dral theory: A survey, arXiv preprini arXiv:2305.0022 00241, 2023.
Junqi Jiang, Jianglin Lan, Francesco Leofante, Antonio Rago, and Francesca Toni. Provably Robust and Plausible Counterfactual Explanations for Neural Networks via Robust Optimisation. In Proceedings of the 15th Asian Conference on Machine Learning, pp. 582-592277 PMLR, February 2024.
Michael Jordan, Zoubin Ghahramani, Tommi S Jaakkola, and Lawrence K Saul. An introduction to variational methods for graphical models. Learning in graphical models, pp. 105-161, 1998. URL https:://///... ///://ddo //w.///.i/////////////...o . org 100. 10. 1023 00016609077777
Kentaro Kanamori, Takuya Takagi, Ken Kobayashi, and Hiroki Arimura. DACE: Diswribution-Aware Counterfactual Explanation by Mixed-Inten Integer Linear Optimization. In Proceedings of the Twenty- Ninth International Joint Conference on Artificial Intelligence, pp. 2855-2862, Yokohama, Japan, July 2020. International Joint Conferences on Artificial Intelligence Organization. ISBN 978-0- 9992411-6-S doi: 10. http:///aaaa..22239999
Karimi, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse: from counter- factual explanations to interventions. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, FAccT '21, pp. 353-362 362, New York, NY, USA, 2021. Associ- ation for Computing Machinery. ISBN 978 9781450383097. doi: (0.1145/3442188.445559) URL
https: //tsi./////ieee// http://oooooog///////// orgg10 1145 34 421 22../44442888.444988 3445899.
Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algo- rithmic recourse: Contrastive explanations and consequential recommendations. ACM Com- put. Surv., 55(5), December 2022. ISSN 0360-0300. doi: 10.1145/3527848. URL https:
//doi. org/ 10. 1100..145550 1145/3527848
Ulrike Kuhl, André Artelt, and Barbara Hammer. Keep your friends close and your counterfac- tuals closer: Improved learning from closest rather than plausible counterfactual explanations in an abstract setting. In Proceedings of the 2022 ACM Conference on Fairness, Account-
ability, and Transparency, FAceT '22. pp. 2137, New York, NY, USA, 2022. Associa- tion for Computing Machinery. ISBN 9781450393522. doi: 10.1145/3531 146.333430. URL https://ddet . .org 104./115/2200 3.. 3534630.
13

---

Published as a conference paper at ICLR 2025
Thibault Laugel, Adulam Jeyasothy, Marie-Jeanne Lesot, Christophe Marsala, and Marcin De- tyniecki. Achieving Diversity in Counterfactual Explanations: Review and Discussion. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, FAccT '23, pp. 1869,1869, New York, NY, USA, June 2023. Association for Computing Machinery. ISBN 979-8-4007-0192-44 doi: 0..1455/399003335941222 URL https: org/
3594122..
Bo Li, Peng Qi, Bo Liu, Shuai Di, Jingen Liu, Jiquan Pei, Jinfeng Yi, and Bowen Zhou. Trustworthy AI: From Principles to Practices. ACM Computing Surveys, 55(9):1771--177:6 January 2023.
ISSN 0360-0300. doi: 10.1145/3555803.
Divyat Mahajan, Chenhao Tan, and Amit Sharma. Preserving causal constraints in counterfac- tual explanations for machine learning classifiers, 2020. URL https://arxvv.org 1912.033 03277.
Donato Maragno, Jannis Kurtz, Tabea E. Röber, Rob Goedhart, Ş. undefinedlker Birbil, and Dick den Hertog. Finding regions of counterfactual explanations via robust optimization, September 2024. ISSN 1526-5528. URL https::////.o /ttp:::/doi.ooo 10. 87 /11/8//jjoo /ijoc./////////////// 2023. 0153.
Kiarash Mohammadi, Amir-Hossein Karimi, Gilles Barthe, and Isabel Valera. Scaling Guarantees for Nearest Counterfactual Explanations. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, AIES '21, pp. 177-187, New York. NY, USA. July 2021. Association for Computing Machinery. ISBN 978- 118-1--503--477-44 doi: 10.1145/3461700.34665511
Alejandro Molina, Antonio Vergari, Karl Stelzner, Robert Peharz, Pranav Subramani, Nicola Di Mauro, Pascal Poupart, and Kristian Kersting. Spflow: An easy and extensible library for deep probabilistic learning using sum-product networks, 2019. URL https://arxxii...t https////xvvvo///eeeeee abs/
Ramaravind Kommiya Mothilal, Amit Sharma, and Chenhao Tan. Explaining Machine Learn- ing Classifiers through Diverse Counterfactual Explanations. In Proceedings of the 2020 Con- ference on Fairness, Accountability, and Transparency, pp. 607-617, January 2020. doi:
10.1145/3351095.337885.
Hien D. Nguyen and Geoffrey McLachlan. On approximations via convolution-defined mix- ture models. Communications in Statistics Theorry and Methods, 48(16):3945-3355, 2019. doi: 10. 88.0080/0661096622188888888 1487069. URL https: /ttp///oii..o./// wttp.//....00/000000000000
2018. 1487069.
Christos H. Papadimitriou. On the complexity of integer programming. J. ACM, 28(4):765-768, October 1981. ISSN 0004-5411. doi: 10.1145/3222763222288 URL htttps://ddi..o. 10. 114.1115/2000 322276.22. 322287.
Axel Parmentier and Thibaut Vidal. Optimal Counterfactual Explanations in Tree Ensembles. In Ma- rina Mcila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8422-8431. PMIR, 18-24 24 Jul 2021. URL https: http://poceeeeeeee/eeeeee ngg mlr. htt..ppreee//113//pmmetttiii.i html.
Martin Pawelezyk, Klaus Broelemann, and Gjergji Kasneci. Learning Model-Agnostic Counterfac- tual Explanations for Tabular Data. In Proceedings of The Web Conference 2020, www '20, pp. 3126-3132. New York, NY, USA, April 2020. Association for Computing Machinery. ISBN 978-1-4503--023-2 doi: 10. 00.1145/33664333338000
Martin Pawelczyk, Sascha Bielawski, Johannes van den Heuvel, Tobias Richter, and Gjergji Kas- neci. CARLA: A python library to benchmark algorithmic recourse and counterfactual explana- tion algorithms, 2021. URL https: /ttp:///aaxivv.ieeeeeeoa abs / 2108. 00783.
Hoifung Poon and Pedro Domingos. Sum-product networks: A new deep architecture. In 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pp. 690,690, November 2011 1. doi: 10.1 1111109/CCCW..21...133333
14

---

Published as a conference paper at ICLR 2025
Rafael Poyiadzi, Kacper Sokol, Raul Mantos-Rdrriuezz Tijl De Bie, and Peter Flach. FACE: Fea- sible and Actionable Counterfactual Explanations. In Proceedings of the AAAI/ACM Conference on Al. Ethics, and Society, pp. 344-350, February 2020. doi: 00.1145/3375627.3377888
Marcos M. Raimundo, Luis Gustavo Nonato, and Jorge Poco. Mining Pareto-optimal coun- terfactual antecedents with a branch-and-bound model-agnostic algorithm. Data Mining and Knowledge Discovery, 2845)2294222974 September 2024. ISSN 1573-756X. doi: 10.1007/
Chris Russell. Efficient Search for Diverse Coherent Explanations. In Proceedings of the Con- ference on Fairness, Accountability, and Transparency, FAT* '19. pp. 20-28, New York, NY, USA, January 2019. Association for Computing Machinery. ISBN 978- 118-1-4503-6125-4 doi: 10.1 10.1145/3287560.32887
Marco Scutari. Learning bayesian networks with the bnlearn R package. Journal of Statistical Software, 35(3):1-22, 2010. doi: 2118867/jss.v033...
Alexander Stevens, Chun Ouyang, Johannes De Smedt, and Catarina Moreira. Generating feasible and plausible counterfactual explanations for outcome prediction of business processes, 2024. URL http::
abs 240ss/2433.00 09232.
Erdogan Taskesen. Learning Bayesian Networks with the balearn Python Package., January 2020. URL
Martin Trapp, Robert Peharz, Hong Ge, Franz Pernkopf, and Zoubin Ghahramani. Bayesian learning of sum-product networks. In Proceedings of the 33rd International Conference on Neural Infor- mation Processing Systems, number 570, pp. 6347-6358. Curran Associates Inc., Red Hook, NY, USA, December 2019.
Martin Trapp, Robert Peharz, Franz Pernkopf, and Carl Edward Rasmussen. Deep Structured Mixtures of Gaussian Processes. In Proceedings of the Twenty Third International Confer- ence on Artificial Intelligence and Statistics, pp. 2251-2261. PMLR, June 2020. URL https: wtt.ggs.ww.....s/...o..me
/ //proceedi ngs mlr wrwsssrssvve http///v1///ttpeeeeeee ttapp html. ISSN: 2640-3498.
Berk Ustun, Alexander Spangher, and Yang Liu. Actionable Recourse in Linear Classification. In Proceedings of the Conference on Fairness, Accountabilityy and Transparency, pp. 10-19, Atlanta GA USA, January 2019. ACM. ISBN 978- 1-5----650----5555 doi: 10.1145//2875603328866.
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual Explanations Without Opening the Black Box: Automated Decisions and the GDPR. SSRN Electronic Journal, 2017. ISSN 1556-5068. doi: 10.2139/ssm.3063888
Patryk Wielopolski, Oleksii Furman, Jerzy Stefanowski, and Maciej Zieba. Probabilistically plausi- ble counterfactual explanations with normalizing flows. In 27th European Conference on Artificial Intelligence, 2024. doi: 10.3233/FAAA240584.
Paul Williams. Model building in mathematical programming. John Wiley Sons, 2013. ISBN 9781 1 18443333.
Laurence A Wolsey, Integer programming. John Wiley & Sons, 2020. ISBN 9781 19606536. doi: 10.1002/9781 119606475
Riting Xia, Yan Zhang, Xueyan Liu, and Bo Yang. A survey of sum-product networks structural learning. Neural Networks, 164(C):645-666, July 2023. ISSN 0893-6080. doi: 10.10166 10166/..nennet.. 2023.05.010. URL /twii/iiiii////////////
neunet. 2023 05. 010.
A NOTATION
Generally, the notation follows these rules:
Capital letters typically refer to amounts of something, as in classes, features, bins, etc. Exceptions are U, T., and F, which taken from the original work (Russell, 2019).
15

---

Published as a conference paper at ICLR 2025
Table 5: General functions used
General function symbols
1-| Absolute value (if scalar) or size of the set
[-]
Set of integers, [N] = [ 21.2..... N
11-)
Equal if input is true, otherwise
la
to norm, number of non-zero elements
(P)
Set all subsets of [P]
Table Symbols used indices
Indices
Index of features, typically j [P]
(m) Index of counterfactuals within set Cx. typically m E [M]
7 A node of the SPN, n
i Index of bins of histogram in leaf node (n), typically E [Bn]
a A predecessor node (of node n) the SPN, usually a E pred(n)
k A class (k (CI) or categorical value (k [Ky] index
6 Index of the feature that is changed as an effect of causal relation R
Caligraphic capital letters denote sets or continuous spaces.
Small Latin letters are used as indices, variables, or parameters of the MIP formulation.
Small Greek letters refer to hyperparameters of the LiCE formulation or parameters of the SPN (scope vi, parameters 0).
Subscript is used to specify the position of a scalar value in a matrix or a vector. When in parentheses, specifies the index of a vector within a set.
Superseript letters refer to specification of symbol with otherwise intuitively similar meaning. Except for IR.", where P has the standard meaning of P-dimensional.
A hat ()) symbol above an element means that the element the output of the Neural Network ((.)).
A prime (') symbol as a superscript of an element means that the element a part of (or the output of) the counterfactual.
In bold font are only vectors. When we work with a scalar value, the symbol is in regular font.
The specific meanings of symbols used in the article are shown in Tables 5 to 9. The symbols divided into groups.
Functions non-specific to our task (Table 5)
Used indices (Table
LiCE (hyper)parameters that can be tuned (Table 7)
Classification task and SPN symbols (Table 8)
MIO formulation parameters and variables (Table 9)
B
CE DESIDERATA
B.1
OTHER DESIDERATA FOR CES
We present more desiderata by Guidotti (2022) that we consider.
Diversity. Each Xmm E Cx should be as different as possible from any other CE in the set, ideally by proposing changes in different features. For example, CE recommends
16

---

Published as a conference paper at ICLR 2025
Table 7: Input parameters into the LiCE formulation
LiCE (hyper)parameters
The minimal difference between counterfactual class (h"* (x')gr) and factual class (hraw (hta((x)))) NN output value. Alternatively, for binary classification, it is the require- ment for minimal absolute value of the NN output before sigmoid activation (A** (x'))
P Limit for the relative difference of values of the objective function within the set of closest counterfactuals Cx
O
Weight negative log- logliielihood in the objective function Minimal change in continuous value Gj of j-th feature. The absolute difference between z'j and łj is either O, or at least Cj.
Cj
8SPN
Lower bound on the estimated value of likelihood of the generated counterfactual.
Table 8: Symbols of the classification task, CE search, and SPNs
Classification task symbols
P
Number of features
C Number of classes
The dataset, set of 2-tuples (x, v) D
X Input space X' S R
X A (factual) sample
X'
T A j-th feature of sample x
y
Ground truth of sample x. E [C]
h(
Classifier we are explaining X' - [C]
caasiffier-rrddictes class h(x) = y E [C]
Faw
NN classifier output without activation w : X +
Output space of the NN classifier, without sigmoid/softmax activation
Counterfactual generation symbols
I1 MAD
Counterfactual distance function (see Eq. 12)
Cx
Set of generated counterfactuals for factual x Number of sought counterfactuals, . > |xx
M
x!
Counterfactual explanation of x. x' Cx
x
Optimal (closest) counterfactual m-th counterfactual explanation of factual x A value of j-th feature of the counterfactual
x
Predicted class of the counterfactual (can be a parameter of LiCE)
Sum Product Network symbols
V
Set of nodes of the SPN
yL
Set of leaf nodes
Set of sum nodes
y
Set of product nodes
(-)
Function returning children (predecessors) of node
(b(-)
Scope function mapping nodes to their input features 10 V + 2(p) Parameters of the SPN
0
On
Output value of node n. E V
Wo.n
Weight of output value of predecessor node a in computing the value sum node n.
n root
Root node, its value the value of the SPN
17

---

Published as a conference paper at ICLR 2025
Table Used variables and parameters MIO formulation
MIO formulation variables
15 Decrease in continuous value of j-th feature.
1 Concatenated vector of all lj.
Uj
Increase in continuous value of j-th feature. Concatenated vector of all Uj. Continuous value of j-th CE feature. iff z'J takes k-th categorical value Kj. All variables dj,x concatenated into vector. iff u', takes continuous value Cj.
Cj
dj.k
d
cont
h bra
(+),
Value of Itww corresponding to class & E [C].
1 iff class
[C] has higher hrww value than the factual class.
85
I iff j-the feature changed, i.e., : + 2'z.
I iff causal relation R is activated, i.c., cause is satisfied and effect is enforced.
ba,s
iff æ' does not belong to the i-th bin (i E [B,]), assuming j-th feature corresponds to node n, i.e., (/n) {j}.
Estimated output value of SPN node n E V.
Mamn
Binary slack indicator for sum node n E V equal to if output of predecessor
constrains output of tightly.
MIO formulation parameters
Lj Lower bound on continuous values of j-th feature. In our implementation, equal to 0.
Uj Upper bound continuous values of j-th feature. In our implementation, equal to 1.
F Default continuous value of j-th feature, equal the value of the factual 2y, if it has continuous value. Otherwise equal to the median.
K Number of categorical values of j-th feature.
f Equal to z.. if has categorical value. If z, is continuous, f, removed, and so are all constraints containing it.
S Maximal number of feature value changes of x' compared to x. Sparsity limit. Example causal relation: if j-th feature increases, e-th feature must decrease. Number of bins the histogram of leaf node n.
R
B.
ta
Threshold between - 1-th and i-th bin in histogram of leaf node n Likelihood value of i-th bin of node n.
In
hin
Vector of respective |-I|1.MAD weights for binary one-hot encodings.
cont
Vector of respective ||||1,, MMAD weights for continuous values.
d fact
One-hot encoded vector of factual categorical values corresponding d.
TLL
A "big-M" constant for sum node used for slack in the computation of max.
18

---

Published as a conference paper at ICLR 2025
increasing the income; another should recommend decreasing the loan amount instead. An important example of a CE library aiming for diversity is DiCE (Mothilal et al., 2020). In MIO, this is usually achieved by adding constraints and resolving the formulation (Rus- sell, 2019; Mohammadi et al., 2021).
Causality. Given that know some causal relationships between the features, the gen- erated CEs should follow them. For example, if x' contains decrease in the total loan amount, the number of payments their amount should also decrease.
B.2 OUR APPROACH TO THESE DESIDERATA
Causality Like actionabilityy causality depends on prior knowledge of the data. In causality, the constraints in the form of implications (Mahajan al., 2020). We describe way to model causal constraints where, if one value changes in a certain direction, then another feature must change accordingly. Details are provided in Section B.3.3.
Diversity and Robustness The diversity of CEs has been recently surveyed by Laugel et al. (2023). Methods for CE diversity in the context of MIO exist (Russell, 2019; Mohammadi al., 2021). While their approach can be applied to our model too, here we simply generate a set of top-M counterfactuals closest the global optimum. We optionally limit the maximal distance relative to the optimal CE; see Section B.3.5. Regarding the robustness of the counterfactuals, Artelt et al. (2021) show that finding plausible CEs indirectly improves the robustness, Thus, we do add any further constraints to the model despite this being viable option (e.g., Maragno et al., 2024; Jiang al., 2024).
B.3 MIO FORMULATIONS DESIDERATA
The following MIO formulations of the desiderata are novel in that we came up with them, and, the best of our knowledge, they not formalized before. They not too complex, but formulate them for completeness.
B.3.1 VALIDITY
For C classes, the raw output has C dimensions (Z RC), and the classifier assigns the class equal to the index of the highest value, i.e., h(x) arg maxke[c] Faw (x)&- Let j' be the desired counterfactual class. The validity constraint, given that we specify the counterfactual class prior, is then
raw (x')g h raw (x')xx) 2T
Wk E (0').
(15)
Note that we can also implement a version where we do not care about the counterfactual class j' in advance by the following
9k 1 now (x')x hrow (x') Z
Vk [C] {0)
Ok 0
ht row (x')x h
(x')
ST
Vk E C (0)
(16)
Σ 1
where can be either indicator constraint equal to if and only if class & has higher value than the factual class ÿ in the raw output. The sum then ensures that at least one other class has higher value.
implication (Williams, 2013), 9k
wide variety of constraints ensuring validity are possible. For example, we can ensure that the factual class has the lowest score by setting Exe Ih C - 1, could enforce custom order of classes.
19

---

Published as a conference paper at ICLR 2025
B.3.2 SPARSITY
To constrain the sparsity further, we can an upper bound S the number of features changed
Σ S
8j 2 1 d3.s
vj E [P]
8j 2 d3
vj [P), Ak E [Kj] \ (G)
(17)
2 1/ + U
vj E [P]
E E 10
Vj [P],
where the binary value 5, that equals if the j-th feature changed, the fy is the categorical value of attribute j of the factual (if applicable).
Neither LiCE nor MIO use this constraint.
B.3.3 CAUSALITY
Consider the following example of causal relation R. If feature increases its value, another feature e must decrease, For continuous ranges, this is formulated as
2 U - l
Le 2 rC.
(18)
Me S
E {0,1}.
where is a minimal change in the value of feature and equals if the relation R is active. In the case when the features are ordinal, we can assume that their values are just variables representing categorical one-hot encoding, ordered by indices and use:
K2
Σ
dj.k
k=
(19)
de
r E (0,1),
where fj is the categorical value of the factual in feature j. Naturally, one can see that we can use any combination of increasin//decreasing values in continuous and categorical feature spaces. With these formulations, we can also model monotone values, such as age or education. We simply replace the variable r by 1.
One can formulate any directed graph composed of these causal relations by decomposing it into pairwise relations, one per edge. This way, we can encode commonly used Structural Causal Models that utilize directed graphs to express causality.
B.3.4 COMPLEX DATA
We use the umbrella term "Complex data" for tabular data with non-real continuous values. This includes categorical (e.g., race), binary (e.g., migrant status), ordinal (e.g., education), and discrete contiguous (e.g., number of children) values.
For binary, we simple 0-1 encoding: categorical data is encoded into one-hot vectors; and discrete features are discretized by fixing their value to an integer variable within the formulation. Since we normalize all values to the [0, 1] range, introduce a proxy integer variable 2y:
(F) - Ly + uz) scale, + shift, 2j
2j E Z
For ordinal variables. we use the same encoding as categorical values, with the addition of the one- hot encoding being sorted by value rank to allow for the causality/monooonicity to be enforced.
20

---

Published as a conference paper at ICLR 2025
B.3.5 DIVERSITY
Instead of a single counterfactual, the solver returns (up to) M counterfactuals closest to the global optimum, optionally within some distance range. This range is defined in terms of the objective function, which is the distance of counterfactual in our case. In other words, we search for a set Cx (xx(1))-->> (x)...... x(rr)) of counterfactuals that have similar distance the factual.
Let x" be the closest CE satisfying all other constraints; we can set a parameter p that represents the relative distance of all CEs to the x" leading to the generation of set
Cx = {x'
x
x |l1MMAD S (1 + p) ||x x [I1.
Nevertheless, we disregard the relative distance parameter and search for the M closest CEs. Later, we sift through the set of top-M counterfactuals, looking for the most likely CEs. Here, one could perform any filtering
C OTHER MIO FORMULATIONS
C.I MIXED POLYTOPE FORMULATION CORRECTION
For purely categorical features, the original mixed polytope (Russell, 2019) implementation contains an issue. The first categorical value (represented by zero) is mapped to the continuous variable. This seems to work fine for the logarithmic regression (Russell, 2019), but it failed on non-monotone neural networks, leading to non-binary outputs. This was corrected by replacing the continuous variable ej with another binary decision variable, making it standard one-hot encoding.
C.2 SPN HISTOGRAM FORMULATION
In practice, the probability distribution of a leaf VL trained on data is a histogram on a single feature j. i.e., (nn) = (j). The interval of possible values of z/J is split into B, bins, delimited by B, +1 breakpoints denoted ln,i, E [B, + 1].
Because modeling that a value of a variable belongs union of intervals simpler than an in- tersection, consider variables 6 that equal if and only if the value x'j does not belong to the interval [n (1) This leads to set of constraints
bns 2 mn - x¹j
Vn 2t, Vi E [Bx] Vn E vL, vi E [Bx]
(20)
bn. 2 x + Ej tniit1
(21)
Bn
Σ
bn,i Bn 1
Vn v4
(22)
Bi
On = > (1 bn.s) log qn,i
Vn VL
(23)
bn E {0
Vn 2L Vi E [Bn],
(24)
where in.i is the likelihood value in a bin i and o, is the output value of the leaf node n. 6j is again the minimal change in the feature and ensures that we consider an open interval on one side. We use the fact that all values I, (thus also in are in the interval [0, 1J. Eq. 20 sets bn = iff < tn, and Eq. 21 sets bn, single bin is chosen and Eq. 23 sets the output value to the log value of the bin that x' belongs to. This implementation bin splitting is inspired by the formulation of interval splitting in piecewise function fitting of Goldberg et al. (2021).
for values the other side of the bin x/S 2 tn, Eq. 22 ensures that
We assume that the bins cover the entire space, which we can ensure by adding at most 2 bins on both sides of the interval.
21

---

Published as a conference paper at ICLR 2025
D DATA MODIFICATIONS
We remove samples with missing values. Optionally, we also remove some outlier data or uninfor- mative features.
GMSC We do remove any feature in GMSC, but keep only data with reasonable values avoid numerical issues within MIO. The thresholds for keeping the sample are follows
MonthlyIncooee < 50000
Rarolyyiigtc.llaaattooottteeeees <
Muubepoofttns33--gggyyssttteeeen 10
DebtRatio <
humbberofoppenteeelltlleeehhaaan <0
Numtberoffiimess90oyyysltttttele
Numberrfeallsccateecoooorrrssse 10
Numbezoffiinee--BBByyyeeeeeeerrr 10
NumberoffDependents 10
this removes around 5.5% of data after data with missing values was removed. We could combat the same issues by taking log of some of the features. In our "pruned" GMSC dataset, there are 11,595 samples and 10 features, none of which are categorical, are discrete contiguous, and the remaining 3 are real continuous. Further details are in the preprocessing code.
Adult
In the Adult dataset, we remove 5 features
fnl which equals the estimated number of people the data sample represents in the census, and is thus not actionable and difficult obtain for new data, making it less useful for predictions,
education-nun because it can be substituted by ordinal feature education
because it is again not actionable, less informative, and also heavily
imbalanced,
capital-gain and capital-los because they contain few non-zero values.
not uncommon to remove the features we did, as some them also have many missing values. We remove only about 2% of the data by removing samples with missing values. We are left with 47,876 samples and features, 5 of which are categorical, is binary, ordinal, and the remaining 2 are discrete contiguous. Further details are in the preprocessing code.
Credit We do not remove any samples or features for the Credit dataset. The dataset contains 1,000 samples and 20 features, 10 of which are categorical, are binary, 1 ordinal, are discrete contiguous, and the remaining 2 are real continuous. Further details are in the preprocessing code.
All code used for the data preprocessing is in the repository attppa:// /tte:////htttt.. com/ /etm///paem//////a LiCE.
EXPERIMENT SETUP
Here, we describe furhter details our experiments.
E. ADDITIONAL DATA CONSTRAINTS
In addition to data type constraints described in Section D, we also constrain some features for immutability and causality.
22

---

Published as a conference paper at ICLR 2025
GMSC
Immutable: o
Monotone: age cannot decrease
Causal: no constraints
Adult
Immutable: race and sex
Monotone: age cannot decrease and educat on cannot decrease
Causal:
education increases = age increases
Credit
Number people being liable to provide ma intenancee for, Personal status and sex, and foreign worker
Immutable:
Monotone:
Age cannot decrease
Present residence since increases Age increases and Present employment since increases = Age increases
Causal:
E.2 HYPERPARAMETER SETUP
The entire configuration be found in the code, but also present (most of) here.
Neural Network We compare methods on a neural network with four layers, first with size equal the length of the encoded input, then 20 and 10 for hidden layers, and single neuron as output. It trained with batch size 64 for 50 epochs. We compare all methods on this neural network architecture, trained separately five times for each training set (from the five folds).
SPN To create fewer nodes in the SPN (i.e., to not overtrain it), we set the min.instances..llee parameter the number of samples divided by 20.
CE methods We used default parameters for most methods. In cases when there were no default values set, used the following:
DiCE: we use the gradient method of searching for CEs.
VAÆ: set the size of the model copy the predictor model. We parametrize the hinge loss with margin of 0.1 and multiply the validity loss by 10 to promote validity. We use learning rate Ie-3 and batch size 64. We use weight decay of le-4 and train for 20 epochs (200 for the Credit data since the dataset is small).
FACE: we only configure the fraction of the dataset used search for the CE, increasing to 0.5 for the Credit dataset due to its size.
C-CHVAE: we set the size of the model to copy the predictor model. For the Credit dataset, we increase the number of training epochs 50.
PROPLACE: We create the retrained NN models to reflect the same architecture and train them for 15 epochs. We set up instance of PROPLACE per class and set its delta by starting at 0.025 and decreasing by 0.005 until we are able to recover enough samples.
LICE + MIO: For our methods, we configure a time limit of 2 minutes for MIO solving. These are high enough for MIO, but constrained LiCE struggles with increasing likelihood requirements. We generate 10 closest CEs, not using the relative distance parameter. We set the decision margin they normalized. In the SPNs, use T.LL 100 safe upper bound though this could be computed more tightly for an individual sum node. We choose 8SPN equal to the median (or lower quartile) of likelihood on the dataset. For LiCE (optimize), used a = 0.1 since features are normalized to [0, 1] and log- likeliiid often takes values the [0100- 100] range.
1 and we use E 10 for all features because
23

---

Published as a conference paper at ICLR 2025
Table 10: Comparison of LiCE variants. (optimize) means that optimize the likelihood together with the distance, with coefficient a 0.1. (quartile) means that we constrain the have the likelihood greater or equal to the lower quartile likelihood of training data. (median) is the same as (quartile), but we take the median instcad of the quartile. Finally, (sample) is a relaxation of the (median) variant. It constrains the CE likelihood be greater or equal to the likelihood of the factual sample or the median value, whichever is lower.
GNSCC
Adult
Credit
Method
NLL
Similarity
Sparsity
NLL
Similarity
Sparsity
NLL
Similarity
Sparsity
MIO (tspe)
27.9
5.9
5.8
43.8
4.4 288
LICE Toptimize)
25.6.1:4.5 4.6
5.9
2.
18.1
3.9
3.8
2.1 1.0
28.8 3.3
4.
2.3 1.2 2.0 2.3
LICE (quartile)
3.7
5.8
18.4 1.7
5.7 3.9
2.1 1.0
39.1 15.0
LÍCE (median)
18.3
12.9
1.0
6.6
20.9
LICE (sumple)
2.25
3.6
1.2
14.3
5.8
27
1.1
4.9
2.0
E.3 COMPUTATIONAL. RESOURCES
Most experiments ran on personal laptop with 32GB of RAM and 16 CPUs AMD Ryzen 7 PRO 6850U, but since the proposed methods had undergone wider experimentation, their experiments were run on an internal cluster with assigned 32GB of RAM and 16 CPUs, some AMD EPYC 7543 and some Intel Xeon Scalable Gold 6146, based on their availability.
Regarding computational time, it is non-trivial to estimate. The time varies greatly for some methods since, for example, VAE retries generating a CE until a valid is found or limit on tries reached. Most methods compared took few hours for the 500 samples, including the method training. The MIO method takes, on average, a few seconds to generate an optimal counterfactual, while LiCE often reaches the 2-minute time limit.
Considering the tests presented in this paper, we estimate 200 hours of real-time was spent gen- erating them, meaning approximately 3,200 CPU hours. If include all preliminary testing, the compute time is estimated at around 20,000 CPU hours, though these are all inaccurate rough esti- mates, given that the hours were not tracked.
F FURTHER COMPARISONS
In this section, we would like to discuss some results that could not fit into the article's main body.
F.1 LICE VARIANTS
We tested multiple versions of using the SPN within LiCE. In Table 10, show results for 2 more configurations.
One, called (sample), is relaxation of the (median) variant. It constrains the CE likelihood to be greater or equal to the likelihood of the factual sample (i.c., the counterfactual should have, at worst, the same likelihood as the factual) or the median value, whichever lower. This increases the proportion of factuals for which the method returns a CE in time, though only by 10 percentage points at most. This suggests that the complexity might not depend on the likelihood of the factual, thus that there might be notable difference in likelihood landscape for the opposite classes.
The LICE (quartile) is weaker variant of LiCE (median), with the bound set to the first quartile instead of the median likelihood. This is enough to obtain CEs for 100% of factuals (and in good time, see Table 12). Its good performance w.r.. similarity and sparsity is possibly caused by the method returning very close CEs with "good enough" log-likelihood.
The results show that selecting the most likely CE out of 10 local optima given by MIO is quite strong. The two-stage setup can be quite performant. The results similarity show that some of the MIO CEs are not globally optimal. This because the SPN in the second phase selects some of the locally optimal (i.e., globally suboptimal) CEs.
24

---

Published as a conference paper at ICLR 2025
Table 11: Results in the same format in Table 4, but consider only valid CEs generated for the intersection factuals for which all methods generated valid CE. These results are more suitable for the comparison of methods between each other. The VAE was omitted from the evaluation on the GMSC dataset because the intersection of factuals would he empty if we included VAE.
GMSC (254 factuals)
Adult (55 (actuals)
Credit (56 factuals)
Method
NLL
Similarity
Spanstt
NLL
Similarity
Sparsity
NLL
Similarity
Sparsity
DICE (tsp))
28.1 5.5
28.5 a 6.5
6.6 1.1
19.8
2.6
22.9 1: 6.1
1 1.4
35.1 4: 3.0
22.1 1 4.6
7.6
1.9
VAE (+spp)
17.9
2.8
5.0 9.7
46.2 = 17.0
27.8
6.2
10.7
1: 1.8
C-CHVAE
25.8
18.2
0.7
17.3
7.5
52.1
12.9
1.5
FACE (e)
6.6
15.2 11
8.5
11.
933665
27
12.0=175
17.7
7.0
FACE (knn)
6..
15.4
84 1.2
13.9
8.
28
42.8
18.6
71+11
PROPLACE
27.8
2..1
39
37.1
22.8
882
MIO (+spn)
2.31
1.2
0.1
15.
31
1.7
311=120
23+13
1.
L-CE (optimize)
24.4
6.3
2.4
16.4+
2.9
1.4
28.8 3.4
2.3+1..
1.7
LICE (median)
18.
11.1333
1.2
1.2
6.1
21
298828
2.3
0.4
F.2 VALID CEs ON COMMON FACTUALS
Table 11 shows the results on the intersection of factuals for which all methods generated valid CE. The proposed methods show similar differences in all metrics, as in Table 4.
Notice the comparability of DiCE results on negative log- likelihood. This suggests that the two- stage setting of generating a diverse set of CEs and then selecting the likeliest could be viable option. On the other hand, compared to LiCE (or MIO), there is major difference in all measures.
F.3 TIME COMPLEXITY
Regarding the complexity of the SPN formulation, the number of variables is linearly dependent on the size the SPN (real-valued variables). Additionally, each leaf node requires one binary variable for each bin of the histogram distribution. Sum nodes require predecessor; the total number is bounded by the number all nodes from above, but is typically less. The number of constraints is linearly dependent on the size of the SPN.
extra binary variable per
This is, however, difficult to translate to the algorithmic complexity of solving the MIO, which is exponential w.r.t. size of the formulation in general.
Table 12 shows the median number of seconds required to generate (or fail to generate) a CE. We that there are stark differences between methods and also between datasets. For our methods (MIO and LiCE), we constrain the maximal optimization time to 120 seconds.
LiCE seems be comparable Adult well Credit datasets. Since MIO seems be faster, we suggest that the main portion of the overhead is caused by solving the SPN formulation. Note that the optimizing variant of LiCE takes a long time partly to prove optimality. A (non-optimal) solution could likely be obtained even with tighter time limit.
There also seems to be some computational overhead in constructing the formulation, which could likely be partly optimized away in the implementation.
F.4 CE GENERATION WITH KNOWLEDGE OF THE TRUE DISTRIBUTION.
In this section, we would like to compare the CE generation methods using the true data distribution. While this distribution is generally unknown, we construct the following experiments to evaluate our method in such scenario by forming 3 synthetic datasets.
We utilize three the Bayesian Networks (BNs) used Section G.4 varying size (asia, alarm, and win9Spts), choose a target variable (dysp, BP, and Problemi, respectively) and sample training dataset of 10,000 samples. On this training dataset, we train an SPN and a Neural Network model. which we then utilize to generate counterfactuals for a set of 100 factuals freshly sampled from the BN. We perform this whole setup for 5 different seeds for each BN and aggregate the results.
25

---

Published as a conference paper at ICLR 2025
Table 12: Median time spent the computation of single CE. The values above 120 in the LiCE computation are caused by computational overhead formulating the SPN. The time limit given solver was 120 seconds.
Method
GMSC
Adult
Credit
DiCE
27.55s
18.40s
145.21s
VAE
0.70s
0.92s
0.67s
C-CHVAE
0.47s
0.66s
0.56s
FACE (e)
9.25s
7.25s
5.08s
FACE (knn)
6.68s
7.12s
5.17s
PROPLACE
0.25s
0.35s
0.29s
MIO
0.80s
1.52s
1.56s
LICE (optimize)
132.72s
34.39s
3.12s
LiCE (quartile)
19.27s
10.64s
2.71s
LiCE (sample)
124.32s
14.34s
2.86s
LiCE (median)
122.50s
17.70s
2.93s
Table 13: Comparison on the asia BN. LL stands for log- log-likellhood. We show the mean probability directly (non-log) because of a few 0 probability counterfactuals.
asia
LL estimate (SPN)
True prohability (BN)
Similarity
Sparsity
Time [s]
% valid
VAE (+spa)
-1.17 + 0.01
2 0.0
3.88 3.37
2.18 1.15
0.02 0.00
46.6
DICE (+spn)
-1.17
29
3.88 3.37
2.18
1.15
11.86
2.98
46.6
C-CHVAE
-252 1.78
16x10-1 10
2.37
1.27 0.65
0
46.6
FACE (knn)
1.44
1.6x10-++9.7x 10
2.34
1.25 0.60
0.18 0.06
46.6 %
FACE
-3.47+2255
2 24.55 10
3.34
2.11 0.74
0.24 0.06
1.8 %
PROPLACE
1.8
x0 1
3.20
1.68 0.84
0.10 0.03
41.8 %
MIO (+spm)
0.55
23 10-1 10
2.89
L.86 0.76
100
LiCE (med)
0.13
2. 10 10
3.09
1.94 0.91
0.71
100
LiCE 1)
0.98
L8 10 1
2.26
1.41 0.76
100
In the tables below (Tables 13, 14, and 15 for asia, alarm, and win95pts, respectively), we evaluate the mean log-likelihood of generated CEs using the fitted SPN, the mean true probability, mean distance (similarity), sparsity, and time spent generating the valid counterfactuals. Finally, we show the percentage of factuals for which a valid counterfactual was found by a given method.
We see that LiCE methods, especially the likelihood likelihood-optimiiiie optimizing variant (a 1), perform compara- bly to other methods even when taking into account the true distribution.
Finally, note that:
performance improvements in terms of distance and sparsity reflect experiments on real data;
only MIO-based methods generate 100% of valid counterfactuals, other methods generate 55,8% CEs best;
the time complexity of LiCE is par with other methods;
while not perfect, SPN likelihood generally correlates with the true probability (see the discussion Section G.4 for additional details).
Statistical significance To evaluate the statistical significance of our results, rank the methods using the true probability of the generated CE. To account for cases where no CE was generated, we rank the methods that did not return valid CE as last. We evaluate each simulated dataset (from each BN) separately. Friedman test rejects the null hypothesis that all methods perform the same with p 0.001.
The average ranks are shown Table 16 and in Figure 2, we show plots inspired by (Demšar, 2006, fig. la), where average ranks and results of the Nemenyi test are shown.
26

---

Published as a conference paper at ICLR 2025
Table 14: Comparison the alarm BN. LL stands for log-likelihood. We show the mean probability directly (non-log) because a few probability counterfactuals. DiCE did not return any valid counterfactuals.
alarm
LL estimate (SPN)
True probability (BN) 1
Similarity
Sparsity
Time [s]
% valid
VAE (+spn)
- 18.32 + 4.49
1.1 10
2.0x 2.0
10
27.15
11.31
8:27 + 2.96
0.02
0.00
53.2 %
DICE (+spn)
C-CHVAR
-9.72
+56xx
10
12.61
0.72
FACE (kun)
-8.59 4.57
10
+50x 10
12:25
3.53 +:
7.69 1.92
54
FACE (e)
-9.28 3.40
1.7 10
4100
10
13.61 8.18
3.92 1: 2.08
7.29 1 1.87
40.2 %
PROPLACE
10.38
1.0 10
#28
10
9..8
1.29 4 2.51
0.56 :: 0.14
54 %
MIO (+spa)
-.2992
2.9 10
3.86 0.861:1 1.37
1.37 + 0.53
1.97
0.18
100
LiCE (med)
-
2.8 10
+.3
10
8.42 7:41
2.52 + 1.98
10.68
13.95
100
LICE (a = 1)
-9.19 = 1.57
3,3 10
5.8
10
4,58 2 2.52
1.51 + 0.76
8.67
2
100 %
Comparison on the win95pts BN. LL stands for log-likelihodd. We show the mean probability directly (non-log) because of few 0 probability counterfactuals. VAE did not return any valid counteffactuals, and DiCE returned the same counterfactuals for all factuals, leading to very poor sparsity and similarity.
Table 15:
Min95pts
estimate (SPN)
probubility (BN)
Similarityy J
Spursity L
valid
VAE (+spn)
0%
DICE (+spn)
-151 40 4.65
0.0 + 0.0
18 x 10 = 3.8 x 10a
63.50
3.99
39.17 + 10.84
44.2 %
C-CHVAE
-7.38
x.0 10
4.7 10-4
7.80
0.55
FACE (knn)
-8.59 3.19
1.5 10
10-3
6.98 5.33
3.44 1.88
8.16
2.54
55.8 %
FACE(()
100.0 1. 3.65
7.2 10
1.6 10-3
10.05 1. 5.96
4.51 4: 1.97
7.21
1.48
28.8 %
PROPLACE
-8.20 2.76
3.2
4.00
7.08 7.05
3.56 4: 2.80
0.49 1: 0.15
55.8 %
(+spu)
-00.8
x. 119x
2.33
0.17
LICE (mod)
-7.77 + 1.22
6.2 10 #21 10-3
7
3.47 + 3.15
5.26 + 0.47
100 %
LiCE (a 1)
-9.33 4.15
133 10
2.49 1.72
1.57 1. 0.83
5.48 1. 0.58
100 %
The thresholding variant of LiCE ranks the highest on all simulated datasets, and the Nemenyi test with confidence level a = 0.05 cannot reject its similarity only from MIO (+spn) on the data sampled from asia and win95pts.
To be more generous towards competing methods, we could consider only factuals for which both methods successfully returned valid CE. This disadvantages LiCE variants and MIO (+SPN) be- cause they are the only methods that always succeed in generating valid CE. The Friedman test also rejects the null hypothesis with p 0.001. The results of Nemenyi test shown in Figure 3, in similar setup to Figure 2.
The thresholding variant of LiCE still achieves the highest rank for alarm and asia BNs. However, its performance is not statistically better than other CE methods. On win95pts, our methods rank poorly, striking contrast to Figure
The plausibility of CEs returned by the proposed methods clearly depends on the quality of the SPN. It is possible that for such big BN, generating 10,000 points with one of 76 possible values is not enough to have high-quality SPN using the LearnSPN algorithm. Some methods are omitted from Figure 3 due to low number of factuals in the intersection.
G FURTHER COMMENTS
Given the limited size of the Credit dataset, it is unsurprising to see many failures of some methods. There is not much data for some methods to support the training. This might be behind the low success rate of computing valid CE.
Table 16: Average ranks of CE methods for each simulated dataset. We rank the methods based on the truc probability, evaluated the BN.
VAB (+sps)
DICE (+spn)
C-CHVAE
FACE
FACE
PROPLACE
MIO (4spn)
LiCE (med)
LiCE (a
asia
1.866
4.866
6.212
6,221
7.603
6.672
2.529
2.350)
3.651
alarm
6.789
7.642
6.263
4.672
5.369
5.427
3.670
2.254
3.014
winS5pps
7.702
6.029
3.136
1.311
6.051
1.916
3.717
3.209
3.886
27

---

Published as a conference paper at ICLR 2025
asia
7
5
2
FACE (c)
LiCE (med)
PROPLACE
MIO (+spn)
C-CHVAE
LICE (a
FACE (knn)
DICE (+spn)
(+spn)
alarm
7
5
2
DICE (+spn)
LiCE (med)
VAE (+Spn)
LiCE (cr
C-CHVAE
MIO (+spn)
PROPLACE
FACE (knn)
FACE (e)
win95pts
7
5
2
VAE (+spn)
LiCE (med)
FACE (E)
MIO (+spn)
DICE (+spn)
LiCE
C-CHVAE
FACE (knn)
PROPLACE
Average ranks and results of Nemenyi test for the true probability of CEs generated for factuals sampled using the Bayesian Networks. When method fails to generate valid CE, give the lowest rank. Groups of methods that are not significantly different (using Nemenyi test with a 0.05) are connected. Critical difference (for a 0.05) is shown on the upper left.
Figure 2:
28

---

Published as a conference paper at ICLR 2025
asia
5
4
3
2
PROPLACE
LICE (med)
CH-CVAE
VAE (+spn)
FACE (knn)
(+spn)
LICE (a= 1)
MIO (+spn)
alarm
5
4
3
2
VAE (+spn)
LÍCE (med)
MIO (+spn)
FACE (E)
PROPLACE
FACE (knn)
LICE (a 1)
CH-CVAE
win95pts
6
4
2
LICE (a= 1)
FACE (knn)
MIO (+spn)
FACE (e)
CH-CVAE
PROPLACE
LiCE (med)
Figure 3: Average ranks and results of Nemenyi test for the probability CEs generated for factuals sampled using Bayesian Networks. Here, we consider only factuals where each CE method was successful. FACE (e) was removed from comparison on asia, because it returned a CE only for 6 factuals. DiCE was removed from alarm because it did not return any CEs, and from win95pts because there were no factuals in the intersection of successful CEs. VAE removed from win95pts because did return any CEs. Groups significantly different (using the Nemenyi test with 0.05) connected. Critical
of methods that difference (for a = 0.05) shown on the upper left.
29

---

Published as a conference paper at ICLR 2025
Regarding the other results, it is possible that the VAE method has been misconfigured for GMSC, returning very few results.
The main disadvantage of LiCE is the time complexity of CE generation. We argue, however, that for some use cases, the user might be willing to wait to obtain a high-quality CE. We leave this decision to the user.
G.1 OMITTED METHODS
It is not feasible to test against all CE methods, looked for selection of methods that consider the plausibility of generated CEs. Two methods were, however, not tested for the following reasons:
PlaCE (Artelt & Hammer, 2020) does not allow for explaining Neural Networks. It also cannot model categorical features well.
DACE (Kanamori et al., 2020) does not have a public implementation that would allow for Neural Networks as models. It might also struggle with the size of datasets used here since they are an order of magnitude larger, and DACE computes the Local Outlier Factor, meaning that the formulation size increases linearly with the increase in the number of samples.
G.2 POTENTIAL NEGATIVE CONSEQUENCES
Given the many CE methods for generating CEs, one must deal with the disagreement problem (Brughmans et al., 2024), where a user could be misled by the owner of an ML model who selects the CEs that align with their interests. We argue that our method does not severely contribute to this problem, since it is deterministic, thus resistant to re-generation attempts to obtain more favorable CE. Our method also outperforms many other methods, making arguing for their use more difficult.
G.3 SUITABILITY OF SPNS FOR ESTIMATING THE PLAUSIBILITY OF CES
We believe that SPNs are well suited for the problem because (i) they naturally model distributions over continuous and discrete random variables; (ii) their simple formulation can be tightly approxi- mated within MIO; (iii) and they are universal approximators (Nguyen & McLachlan, 2019).
Other options
Gaussian Mixture Models (GMMs) are designed only for continuous random variables. SPNs are strict superset to GMMs.
Flow models are very flexible, but they model only distribution on continuous random variables. Since they are parametrized by neural networks, they might be rather difficult to formulate within MIO, especially considering their block nature relying on smooth non- linear functions (exp, softplus).
Neural regr-sigeee models can model discrete and random variables, and they provide exact likelihood. But again, they use relatively large neural networks, which might need non-lincarities that are difficult to use within MIO (sigmoid, softmax).
Auto-encoders have, with respect to MIO similar advantages and disadvantages as neu- ral auto-regressive models. Furthermore, they provide only lower-bound estimates of true likelihood in the form of ELBO.
G.4 SPN AS MODEL OF DATA DISTRIBUTION
Furthermore, we test the ability an SPN to model the true data distribution empirically. We choose 8 Bayesian Networks (BNs) to model the data-generating process. For each of them, generate (sample) training data, then fit an SPN to this data, and finally compare the SPN's likelihood estimates of test samples their true probability, given by the BN.
More specifically, we utilize the bnlearn Python library (Taskesen, 2020) and select 7 Bayesian Networks of varying sizes from the Bayesian Network Repository (Scutari, 2010) (namely asia,
30

---

Published as a conference paper at ICLR 2025
Table 17: Size comparison of BNs used generate the synthetic data.
sprinkler
asia
sachs
child
water
alarm
win95pts
andes
Number of nodes
4
8
11
20
32
37
76
223
Number of edges
4
8
17
25
46
112
338
Number of parameters
9
18
178
230
10083
509
574
1157
Table 18:
Evaluation of the fit by correlation coefficients for all 8 tested BNs. Total Variation was computed only for smaller BNs, where the computation was practical. Numbers are rounded to 3 decimal digits.
sprinkler
asia
sachs
child
water
alarm
win95pts
andes
Pearson coefficient
0.996
0.990
0.964
0.954
0.955
0.959
0.959
0.793
Kendall (7-b) coeff.
1.000
0.992
0.860
0.853
0.828
0.892
0.891
0.600
Spearman coefficient
1.000
1.000
0.972
0.966
0.961
0.978
0.977
0.788
Total variation
0.017
0.073
0.260
sachs, child, water, alarm, win9Spts, and andes). The eighth BN (sprinkler) is another standard BN, available directly in the bnlearn. library. See Table 17 for parameters of the used networks.
To train the SPN, we sample 10,000 points using the BN and train the SPN in the same way as for LiCE, with default parameters. Then we sample 1,000 more samples and evaluate their likelihood using the trained SPN. We also compute their true probability from the BN and compare these pairs of values. We perform the above process times with different seeds for each BN and select the best-performing SPN for comparison.
In Table 18, we show the correlation coefficients of the log-likelihood and log hog-probability computed on the 1,000 test samples. We also show the total variation for the smaller BNs, when the value can be computed in reasonable time. All correlation evaluations reject the null hypothesis that there is no or negative correlation with p < 0.001. In Figure 4, we show scatter plots of the data on which the correlation coefficients were computed. The BNs are sorted in increasing order of the number of nodes.
The SPN performs quite well, with the exception of the biggest BN (andes), where the drop might be explained by 10,000 samples (from 223 possible values) being too few to train the SPN precisely.
31

---

Published as a conference paper at ICLR 2025
sprinkler
asia
Log-likellnn le-lliiklhhoddd from the fittedd SPN
llooo ligllikellhood from the fitted SPN
-2
-2
-6
-8
Log-likelligg
-7
-10.0
-7.5
-5.0
-2.5
Log-prabability from the Bayesian Network
Leg-probability from Bayesian Network
sachs
child
Log- Log-likellnes ne-llkellnood from the fitted 5PN
Log- likelllodd from the fitted 5PN
-6
-10
-8
-15
-12
-14
-20
-18
-15
110
-25
-20
-15
-10
Log-probability from the Bayesian Network
Log-probability from the Bayeslan Network
water
alarm
Log ho-llkellhoodd from the fitted SPN
Log -lllleelhhood from the fitted SPN
-10
-10
-15
-15
-20
-20
-25
-25
-30
-30
-25
-20
-15
-10
-30
-20
-10
Log-probability from the Bayesian Network
Log-probability from the Bayesian Network
win95pts
andes
Log Bog-likellhood from the fitted SPN
Log fil--iieihhodd from the fitted SPN
-10
-90
-15
-100
-110
-25
-120
-30
-130
-35
-30
-20
-10
-120
-100
-80
Log-probability from the Bayesian Network
Log-prabability from the Bayesian Network
Figure 4: Visual comparison of correlation between the true probability of sample and
estimate
given hy SPN. Each plot shows 1,000) points sampled using the given Bayesian Network, their names in titles. For numerical comparison, see Table
32


Reviews:
[{"review_id": "DJbG7sJTC8", "reviewer": "Reviewer_Xi76", "summary": "This paper deals with the task of finding counterfactual explanations (x’) for a multi-class classification model (h(x)). Specifically, the authors aim to find a counterfactual set (C) satisfying desiderata specified in Guidotti (2022). i.e. apart from being a valid counterfactual, each x’ \\in C must be similar to the original example x, involve changing as few features as possible (sparse), comply with domain constraints such as monotonicity of age (actionable), and not be an outlier (plausibility). Additionally, C must be as diverse as possible and follow causal domain knowledge. The authors approach this problem from a mixed integer optimization perspective and use sum-product networks to model the data distribution (P(X)). To this effect, they translate the desiderata into constraints and solve the optimization problem using the OMLT library (Ceccon et al., 2022). While the trained SPN cannot be encoded exactly in log-space, the authors develop an approximate encoding and bound the likelihood. The authors call their proposed counterfactual generation approach Likely Counterfactual Explanations (LiCE) and define two variants of LiCE, one based on likelihood (upper) threshold of train-set median (LiCE (median)) and the other on minimizing a linear combination of distance and likelihood (LiCE (optimize)). They evaluate the two variants by comparing them against a non-SPN variant (MIO) and on prior work including DiCE (Mothilal et al., 2020), C-CHVAE (Pawelczyk et al., 2020), FACE (Poyiadzi et al., 2020) and PROPLACE (Jiang et al., 2024) on 3 financial data sets focusing on plausibility (as measured by log-likelihood), similarity (counterfactual distance), and sparsity (number of modified features). Their experiments show that both LiCE variants outperform the baselines, and while LiCE (median) excels at plausibility of generated counterfactual sets, LiCE (optimize) is the best at similarity even beating MIO.", "questions": "- Would making structural assumptions (e.g., determinism) about SPNs make it easier to encode exactly? \n- Can you elaborate on the setup and significance of the VAE baseline from Mahajan et al. (2020)?\n- The results mention that LICE (median) times out for some of the cases, and the appendix mentions that the time limit for each run was 2 minutes. Are these results sensitive to the time limit duration? Would they change drastically for a small increase in the time limit?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- LiCE is a principled method of inferring *plausible* counterfactual explanations that satisfy several desiderata. The MIO approach is flexible enough to accommodate additional criteria.\n- The MIO formulation for SPN inference is itself a significant contribution. It opens up space for work on SPN inference tasks such as finding the entire Maximum a Posterori (MAP) set possible. Existing work has focused on finding single solutions (e.g., Poon and Domingos, 2011 and Arya et al., 2024).\n\nArya, Shivvrat, Tahrima Rahman, and Vibhav Gogate. \"Neural Network Approximators for Marginal MAP in Probabilistic Circuits.\" AAAI 2024.", "weaknesses": "The Accuracy of likelihood assessment is limited by the expressivity of SPNs. This might be at least partially resolved by using PFCs (Sidheekh et al., 2023) to improve performance on high-dimensional domains,\n\nSidheekh, Sahil, Kristian Kersting, and Sriraam Natarajan. \"Probabilistic flow circuits: towards unified deep models for tractable probabilistic inference.\" UAI 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ruEqzO6Jvb", "reviewer": "Reviewer_RaSc", "summary": "The paper presents a novel method to model counterfactual explanation (CE) search that maximizes likelihood, closeness, and sparseness. The method leverages sum-product networks (SPNs) to estimate point likelihoods (or plausibility) and use mixed integer optimization (MIO) to optimize the different objectives simultaneously. The work includes empirical comparisons with state-of-the-art CE algorithms.", "questions": "Content-related: \n\n- L53: What is the definition of an outlier in your context? Are you suggesting that an epsilon-ball around the factual could contain outliers due to factor interactions and their joint distribution? Please expand on this. \n\n- L80: Table 1 is not explained. Why are the \"other desiderata\" important? \n\n- L97-107: A definition of plausibility is missing in this section. You claim that DiCE is the most plausible—what criteria support this claim? Additionally, LiCE changes installment/disposable income while keeping amount and duration constant, suggesting a change in income. Is this more \"realizable\" than borrowing less? MIO changes two features (duration and income); could you provide more details on how these changes are measured?  \n\n- Later in the paper, it becomes clearer that your definition of plausibility stems from the joint probability distribution extracted from SPNs. However, this raises concerns about whether this plausibility measure should be evaluated independently. In your experiments, you assume that this probability distribution provides the correct measure of plausibility without empirical validation. Could you justify this assumption further, or better yet, provide an evaluation of plausibility as a standalone concept? This is crucial, as your entire method relies on the assumption that SPN-based plausibility is the most accurate or appropriate for counterfactuals. \n\n- L184: Why do you take the median for categorical values? Could you use their actual values instead? Taking the median for categorical variables may cause all of them to start from the same point. \n\n- L188: Why will at least one always be 0? Please provide intuition. Also, the citation is placed after the full stop—should be corrected. \n\n- L237: Outliers are mentioned again without a definition. Also, plausibility is referenced but not defined earlier. An intuition would help the reader follow the motivation more clearly. \n\n- L260: Why do you work in log-space? Is it to simplify handling products? Please provide a rationale for this choice. \n\n- L332: Taking a threshold of 0 on the raw output of a neural network implies a threshold probability of 0.5 after applying a logit. Are there dependencies on this, and can it be changed? \n\n- L461: You select CEs based on SPN output, which establishes plausibility in your results. Does this give your method an advantage over baselines? For example, on L484, you claim \"unparalleled\" plausibility. \n\n- L471: You mention that the failure to terminate worsens the results. How pronounced is this effect? \n\n\nMinor points: \n\n- L82: \"This work combines the tradition ...\"—what tradition are you referring to? Please include a reference to clarify. \n\n- Fig2: The heatmap legend is missing. Are the most likely points represented by the most yellow areas, particularly near 0 amount and 12 months? \n\n- L252: \"SPNs are a strict generalization\"—this statement is missing a reference. \n\n- L293: Typo: \"the it\" \n\n- L376: Why do you need $v^{cont}$ and $v^{bin}$? Could you elaborate on the correspondence between these values and their respective roles in your approach? Does this correspondence offer advantages or properties? \n\n- L468: What do you mean by \"considering the differences between methods\" when referring to finding the error acceptable? \n\n- L497: What do you mean by \"the limitations of all MIO methods\"?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The use of SPNs to model plausibility in counterfactual explanations is a novel and creative approach, addressing limitations in handling mixed data that many existing methods struggle with. \n\n- The integration of SPNs and MIO to optimize multiple constraints simultaneously offers flexibility and the formulation of bounds for the output of SPNs that can be integrated as constraints into a MIO formulation is (as the authors mention) quite interesting on its own.", "weaknesses": "- The key concept of plausibility, derived from the output of SPNs, is assumed to be correct without evaluation. This is a critical assumption, as it underpins the entire method, and its validity should be examined and justified. The lack of empirical evaluation of this concept weakens the overall contribution. \n\n- The experiments appear to be biased in their evaluation of plausibility as the SPN distribution is taken as the true one, giving the proposed method an unfair advantage over the baselines \n\n- The clarity of the paper could be improved, particularly around the explanation of key terms and concepts like plausibility and outliers, which are not sufficiently defined when first introduced. \n\n- The method appears computationally expensive, which could be a practical concern in real-world applications. This issue is not directly addressed in the paper, but the experiments suggest that the optimization process may be time-consuming, particularly for more complex scenarios. The paper would benefit from a discussion of the computational cost and potential ways to mitigate it, such as pruning strategies, approximations, or discussing scalability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "syVi1rv5rL", "reviewer": "Reviewer_kD9A", "summary": "This paper studies the problem of generating counterfactual explanations for a fixed classification function, say $f(x)$. The explanation here refers to different input $x'$ to the classifier $f(x)$ (with a factual baseline $x$) such that they result in different classification outcomes $f(x') \\neq f(x)$. In general, there are many such realizations of input $x'$. This paper studies the problem of finding the most likely counterfactual explanations $x'$ satisfying a set of selection desiderata, including validity, similarity, sparsity, and actionability. The authors evaluate the likelihood of an input $x'$ by fitting a sum-product network (SPN). Using the formalism of SPNs, the selection desiderata could be translated into a series of equivalent polynomial constraints. The explanation generation is then reduced to an equivalent mixed integer optimization (MIO) problem.", "questions": "1. Could the proposed method apply to other generative models measuring the likelihood, e.g., Gaussian processes?\n2. For all variants of the proposed methods, LiCE (optimize) seems to perform the best. However, its implementation is somewhat ambiguous. The authors stated, \"we optimize a combination of distance and likelihood with α = 0.1 and relax the plausibility constraint (Eq. 13).\" Could the authors further elaborate on this statement? For instance, what is the \"combination of distance\" and how to \"relax the plausibility constraint?\" A pseudo-code description would be appreciated.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The writing is generally clear. The paper is well-organized. While no main theorem is presented in the paper, the derivation of the mixed integer program is technically sound.\n- Comprehensive simulations were performed. Simulation results support the proposed MIO formulation.\n- The authors have clearly stated the limitations of the proposed methods, including the computational challenges of solving MIO programs.", "weaknesses": "- The SPN models might be limited. First, it can only account for discrete features, while most prediction tasks in practice involve high-dimensional, continuous feature inputs. Also, SPNs require structural constraints. It could be challenging to learn SPNs that best fit with the observed data.\n- The explanation generation problem is reduced to an MIO program, which is generally NP-hard to solve. This presents challenges in generalizing the proposed methods to more complex domains.\n- The reduction of SPN to MIO programs is not surprising. It has been known that constrained optimization in Bayesian networks is generally equivalent to linear integer programming. This paper would be most improved by proposing an efficient approximation algorithm to solve the MIO program while leveraging the graphical structure of the learned SPN.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xIauiAofV4", "reviewer": "Reviewer_WAgz", "summary": "The paper proposed a method for computing plausible counterfactual explanations by using sum-product networks.", "questions": "See weaknesses.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses an important problem and proposes a novel and interesting approach. Its strength is its ability to handle categorical features (often encountered in real-world data sets).", "weaknesses": "Disclaimer: I have reviewed the paper before (Neurips 2024)—I hope that this does not disqualify me as a reviewer. In my opinion, the paper has improved significantly. In particular, the empirical evaluation is now done fairly, the notation and formalization are clear now, and the structure of the entire paper is now more accessible and more \"scientific\" compared to the previous version that I reviewed.\n\nHowever, I still think that some more information on SPNs could be added: How powerful are SPNs? What types of distribution can they model? What are the assumptions? How to estimate SPN's parameters from data? Given the large number of existing methods (for computing plausible counterfactuals), this information would help practitioners select one of those existing methods. There is information given in the appendix but it might be also good to (briefly) answer some of those questions in the main text.\n\nI understand that there is not enough space to fully introduce SPNs but I still think that it would be important to highlight what they can model and what they can not -- this would help practitioners to select an appropriate method for their particular use case. Currently, different methods exist for computing plausible counterfactuals based on Gaussian Mixture Models, Kernel Density Estimators, Neural Autoencoders, etc., and each of those methods has its advantages and disadvantages. However, I am happy to discuss this and step back if the authors or the other reviewers can convince me that this is not necessary or is somehow already in the paper. Thanks :)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)