Practical do-Shapley Explanations with Estimand-Agnostic Causal Inference
Authors: Álvaro Parafita
Tomas Garriga
Axel Brando
Francisco J. Cazorla
Venue: NeurIPS 2025 spotlight ()
Keywords: Shapley
Explainability
Causality
Attribution
SCM
Modeling
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: do-SHAP explanations made practical with Structural Causal Models and a novel algorithm to accelerate do-SHAP

Abstract: Among explainability techniques, SHAP stands out as one of the most popular, but often overlooks the causal structure of the problem. In response, do-SHAP employs interventional queries, but its reliance on estimands hinders its practical application. To address this problem, we propose the use of estimand-agnostic approaches, which allow for the estimation of any identifiable query from a single model, making do-SHAP feasible on complex graphs. We also develop a novel algorithm to significantly accelerate its computation at a negligible cost, as well as a method to explain inaccessible Data Generating Processes. We demonstrate the estimation and computational performance of our approach, and validate it on two real-world datasets, highlighting its potential in obtaining reliable explanations.

Practical do-Shapley Explanations with Estimand-Agnostic Causal Inference
Álvaro Parafita'
Tomas Garriga Axel Brando' Francisco J. Cazorla'
Barcelona Supercomputing Center Novartis
(alvaro. (alvaro.parafita. axel. brando, francisco. cazorla) aabooraaabbb..... @bscbbbc.ooo. es
tomas, garriga_diiiuui cuw.onooorroo.....cc...cooo com
Abstract
Among explainability techniques, SHAP stands out as one of the most popular, but often overlooks the causal structure of the problem. In response, do-SHAP employs interventional queries, but its reliance on estimands hinders its practical application. To address this problem, propose the use of estimand-agnostcc approaches, which allow for the estimation of any identifiable query from single model, making do-SHAP feasible on complex graphs. We also develop a novel algorithm to significantly accelerate its computation at a negligible cost, as well as method to explain inaccessible Data Generating Processes. We demonstrate the estimation and computational performance of our approach, and validate on two real-world datasets, highlighting its potential in obtaining reliable explanations.
Introduction
The widespread adoption of Machine Learning (ML) systems has raised concerns about their limitations: models can replicate hu- man biases [ base their outcomes on spurious correlations [2) be vulnerable to malicious adversarial attacks (3]. Since most of these systems are black-boxes, there an ever-increasing need for explainability techniques to make sense of the model. This is espe- cially relevant w.r.t. fairness, the right to explanation 4. debugging, auditing, and fostering user trust in the system.
E
A
S
Y
Figure 1: Salary causal graph: Age (A), Education (E), Se-
In response this pressing need, the field of explainability has steadily gained traction, resulting in several approaches (5) to explain model predictions. Among them, the Shapley value (SV, SHAP)
niority (S) and Salary (Y).
[6] is one of the most popular, being the unique attribution strategy fulfilling a set of axioms aligned with human intuition (see appendix AA. SVs are derived from a value function measuring the effect of subset (coalition) S of features X on the model's prediction; each results a different kind SV, the most common being marginal and conditional SHAP 77.
However, both of these options ignore the causal structure underlying the data; for instance, fig. represents the salary of an employee of age A with certain education level E and seniority level S. Let f be a ML model f(X) Re E [Y X], learning Y given inputs X = {A, E, S}. Consider v((E)). In marginal SHAP, v assigns values {E e} and marginalizes the complementary set (a. s) ~ ((A, 5) regardless of how the coalition's 's values causally affect them (E - S). Conditional SHAP does consider these effects, but conditionally. (a. P(A, S E e). producing anti- causal effects to A (i.e., we cannot change age by granting them a degree). Thus, we cannot ignore problem's is causal structure. Please refer to appendix[G]on an extended discussion on this example.
Several works 8
discussed the limitations of non-causal SHAP and proposed limited approaches with a causal interpretation. Jung et al. [12 proposed do-SHAP, defining as causal,
10
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

interventional query estimated with Causal Inference: first transforming the query into a probabilistic formula (the estimand) only containing terms from the observational distribution P(X), training ML models on these terms to estimate them and bringing it back into the formula for the final estimation. The main drawback of Estimand-based (EB) estimation is that do-SVs require computing up to 2 causal queries, one for each coalition S S X, with different estimands and ML models to estimate their terms. As a result, the process becomes too manual and impractical for complex graphs. In fact, do- So--SAPP's authors stated they "are not aware of any general causal effect estimators suitable for estimating the expression".
Here lies our first contribution: by employing the estimand-agnosse (EA) approach [3] based on Structural Causal Models (SCMs), any causal effect required by do-SHAP can be estimated from a single model following general procedure instead of query-specifie estimands, thereby enabling the computation of do-SVs in a general, practical way (sections 3.2 and 4.J). Secondly, we propose the Trontier-Reducibbie Algorithm (FRA), which substantially reduces the number of coalitions that need to be evaluated. Although FRA retains the exponential complexity of exact do-SHAP, it delivers significant speed-ups ups at virtually no additional cost (section 4.2). Thirdly, we devise a do-SHAP explainability strategy, not only for accessible ML systems, but also for natural, inaccessible Data Generating Processes (section 4.3). We validate the estimation capabilities of the EA approach on do-SVs, demonstrate the speedup of FRA, and showcase these techniques on two real-world datasets to illustrate the power of do-SHAP explanations (section S and appendix [.. Finally, we address the limitations of our approach in section 6 and finish with our conclusions in section 7
2 Related work
Among many explainability techniques (see the survey in ( ) we are particularly interested in feature attributions, particularly Shapley values [14]. There is vast literature on SHAP, discussing the choice of the value function v and estimation strategies for the SV (c.g.. permutation sampling, adaptive sampling model-specific strategies); refer to (7] for extensive survey the topic. Our
main focus is in SHAP approaches that leverage the underlying causal structure of the data, operating from Pearl's ' Structural Causal Models perspective [15] Asymmetric Shapley values [8] employ topological order of the graph to restrict which permutations are considered in the computation of conditional-SHH SHAP, thereby granting more attribution to ancestors of other features. Causal Shapley values (9) properly considers the impact of causal interventions on Shapley attributions, but assumes partial causal ordering of the graph in order to avoid dealing with latent confounders. do-SHAP [12] does require a full causal graph, but provides a full method to compute attribution on all variables, as long as an estimand can be found for every causal query. Finally, in a different direction, Shapley flow [16] studies causal attributions on the causal graph's 's edges instead of its nodes/variables
In order to avoid do-SHAPss limitations, we propose EA methods [33, which train SCM modelling the data distribution to estimate causal queries from it. This approach is explored in the Neural Causal Models framework [17]. In this line, recent contributions employ Deep Learning for SCM modeling: CausalGAN 18] uses Generative Adversarial Networks 119 to model images in an SCM containing descriptive factors of the image; Parafita & Vitrià 20 propose the Distributional Causal Node as a way to model mixed-type distributions (i.e., with discrete and continuous random
variables) and expand their framework with Deep Causal Graphs 1
: Pawlowski et al. (21 propose
Normalizing Flows (NFs) (22] and Variational AutoEncoders 223 for SCMs with medical image nodes; and Diffusion- based Causal Models (44] use Diffusion Models (25] train their SCMs on high-dimensional data. A promising alternative models SCMs not node by node as all previous works, but the graph as a whole with a single function of its noise signals, thereby avoiding error propagation when sampling. Two of these approaches are VACA 226), which uses Graph Neural Networks [2]]
and Causal Normalizing Flows (28) with single NF for the whole graph.
3 Preliminaries
This section establishes the concepts and notations needed throughout this work. We start with Struc- tural Causal Models (SCMs), a transparent and concise framework to define the causal assumptions of data distribution, followed by discussion how (identifiable) causal queries can be estimated through SCMs, even the presence of latent confounders. We then define the general Shapley value, from which we can derive do- SHAP.
2

---

Notation Sets are represented by boldface letters (X) and their elements by simple letters (X E X), unless clearly distinguishable. Let the power set of X be denoted by P(X) == {Ø S S x}. [K] := {I...., } an index set, IT(S) the set of permutations of elements of S and <, the order entailed by x (e.g., < in π = (3, 1,2).. Given a graph 9 (V. E) and a subset of vertices X - V. Ax(X) denotes the set of ancestors of X (including X) and De(X) the set of descendants (including X). For a certain node X E V. let Pax denote the set of parents of X (not including X). Random variables (r.v.s) are denoted in uppercase (X) with realizations in lowercase (r). Let
x ~ P(X) denote the generation of a new sample z from the distribution P(X).
3.1 Structural Causal Models
Let M (V, F) be Structural Causal Model (SCM), consisting of set of measured EvS. V = (Vi...., VK), a set of latent r.V.S W, their priors P(W) = Iww P(W) (all mutually independent), and set of functions F == {ffe) for each measured variable. The set of latent variables consists of W := & U,,, with := (E2,...,Ex the exogenous noise signals, Ex corresponding Vk. and Ui set of confounders U (K.1)) affecting distinct V-nodes V₂ and ! Finally, each Sa E F is a deterministic function V = S& (Pax, F&) that returns Vi² '' realizations given its measured parents Pa C V\ {V&J. confounders U(K.) == (USRA) EU | E [K] and the corresponding Ex. Let Pa' == Pas U'(E..)
Let GM EV be the directed graph associated to M, with vertices, nodes or variables V := UUW and edges E = (X + V& VV& E V x E Pak, U (Ex)) If 9m is a Directed Acyclic Graph (DAG), there is topological orden for V. In that case, we can define M's probability distribution (V) from the SCM's sampling procedure: it starts by sampling any latent variable Ex E 3, U E 24 from their priors Ex ~ P(Ex), u ~ P(U); then, following the topological order k == K. it samples every V& V by applying Ux= = fu (pax, E(..).Ex))
We define an intervention do(X = z). also denoted ã, on a variable X E V as the replacement of fx with the assignment X + x. X takes this value independently of its parents, but any descendants may be affected by this change. Note that this transforms the SCM M into an intervened model Mz. graph 92 := GM, (without any edges pointing to X), and distribution P=(V) := PM, (V). We can also define interventions
sets of variables do x) by the replacement of each of the
corresponding functions (/x X E X). The terms Px( P(Ý | do(X = x)) = P(Y | () are used interchangeably, for clarity or economy of notation depending on the case.
3.2 Identifiability and the sstimand-agnostie approach
Given r.v.S V and an i. d. dataset D = (vo() ~ P(V) sampled from an unknown Data
Generating Process (DGP) with a strictly positive probability measure P(V), assume that P()) follows an unknown SCM M, but whose graph 9M is known. For example, in fig. I V
(A, E, S) and U = Ø. Let us estimate the causal query Q == Ey [Y | by transforming it into an observational formula through the rules of do-calculus [S] (see appendix Cp. At the end
of this process, we obtain the final formula, the estimand: in the example, Q = Ey 2 EA [Ey ee If such formula exists, the query is said to be (non non-parametrically) identifiable in 9M- Fortunately, there are algorithms to automatically determine identifiability and obtain the corresponding estimand 29 30). implemented in R [31 and Python [32].
The EB approach employs ML models to approximate each of the probabilistic terms in an estimand; in the example, we can train model for ((E,A) Ey [Y| E, A] and then estimate the formula with Monte Carlo for the final estimation. However, this approach does not scale, since, for each and every query, we need 1) derive the corresponding estimand for that query; 2) train ML models to estimate each term in the formula; and 3) put it all together to arrive at an answer for the query. Even with algorithms to automatically extract the estimand, it is not trivial to compute these formulas, especially if we need to answer exponentially many queries, as will be the case for do-SHAP.
'The case when 24 is empty, i.e., no latent confounders, is known the causal sufficiency assumption. Whhen drawing G.m. we usually omit W: E is implicit, and any confounders U(e. are denoted by V22 ++ Vi. 'we say V = (Vi,..., Vx) is in a topological order of the DAG g if Vk, E [K]. V2 E An(V)) + k 5 L. Let <g represent the particular order defined by G: X <g Y.
3

---

However, if we had access to the original SCM M, we could simply take N i. d. samples from the intervened distribution, (
(Y) using Me's sampling procedure. Regrettably, we rarely have access to the underlying DGP. Instead, let consider a family of proxy SCMs MMe = (V, W. Fe) following the same graph GM = GM and whose Fe depends on set of parameters (e.g., an untrained neural network with parameter space θ). Irrespective of our choice of prior P' and functions Fe. if both are expressive enough, we can train Me to find a value O so that it models the data distribution exactly, PMa (V) = P(V) (in an infinite data setting). Then, by the application of the sampling procedure on the intervened learned model, we could estimate the query through the proxy SCM procedure, without ever using the estimand. If the query was identifiable in G, the result is guaranteed to be the same as if we had used the original SCM M.
It is trivial to see why[ since our identifiable query Q's value is derived from the observational formula of the estimand, it depends exclusively on observational terms resulting from the joint distribution (VV)), which we assume is correctly represented by our trained proxy Mg. Therefore, as long as we derive its value from the distribution entailed by the proxy, we will necessarily arrive at the same result as with M; otherwise, P.M, (V) * (V) In other words, even though its latent priors and functional assignments may be different, we can still compute the causal query through the proxy SCM because there an estimand for Q GM Hence, this results in an alternative approach for causal query estimation, the EA approach 13 define trainable SCM M' with the underlying SCM's graph G, train to learn the observational distribution (V)()), and compute any identifiable queries from that single model using the SCM's procedures, not the specific estimand for each query. This will become essential for the computation of do-Shapley values.
3.3 The Shapley value
:S) Consider a set of K players X and a value function v PX + R. Let = -(()) v()) be the corresponding coalitional (cooperative) game. We define the Shapley value [33] 'Λ. (X) for player X E X, denoted by ou or simply @x unless when leading to ambiguity, as:
Φx =
Σ K
(
K [S]
(u(SU (X)) v(S)
1
(v(Xs,x)-v(x4 v(Xx,))), xEI1())
Σ
KI
X' X and equivalently for Xs, and S.. Both equations are equivalent given that the sum over weighted subsets S results from the average over all permutations of the set of players X. Note that SVs fulfill efficiency: Exex Φx = v(X) - v(Ø)= = (X) (i.e.,
where
SHAP attributions add up to the contributions of the whole set X).
3.4 Shapley value estimation
Even though eq. 2 requires 2- K! computations of v. we can consider each permutation и E [T(()) as sample from the uniform distribution over the set of permutations, ~ (TT((())) resulting in Øx = E -== xx) N i.idd. permutations and averaging their results (34). Quasi-random and adaptive sampling strategies
(Xx..X ). which can be approximated by Monte Carlo, sampling
can also be employed for faster convergence; please refer to ( for more details.
On the other hand, both methods result in significant number of subset collisions, making it worthwhile cache the v(S) values avoid unnecessary computations. We derive the expected number of coalitions sampled after N permutations in appendix which let us define a computational budget (i.e., how many permutations to sample) based on desired coalition coverage.
4 Method
In the following, we present our contributions: we propose EA techniques to make do-SHAP practical on complex graphs; we present the
Algorithm (FRA), an efficient procedure to
'Please refer to [7. Corollary 2, for a formal proof. In their terms, our SCMs are G-constrained, L1- consistent Neural Causal Models that can effectively estimate interventional queries (such as do-SHAP's v(S) coalition values) long they are identifiable by using the mutilation process (see appendix H.4).

---

significantly reduce the number of coalitions to evaluate during do-SHAP (regardless of using EB or EA methods); finally, we present a theorem allowing for do do-Shapley explanations on inaccessible DGPs. Please refer to appendix H for a detailed example illustrating the application of our approach from start to finish.
Please note that throughout this work, we do not claim polynomial sommmmiil-timee tractability of do-SHAP. Any discussion of computational efficiency refers solely to FRA in isolation, and should not be interpreted as implying polynomial-time performance for do-SHAP.
4.1 The do-Shapley value
Consider an SCM M (,, target r.v. Y E V, subset of K variables X CVV {Y} and a certain sample x ~ P(X) we wish to explain. Given a coalition S E PP(X) with realizations (a subset of x), let define the value function (S):
(x(S) == E| do(S s)]
(3)
Then, the do-Shapley value (do-SV) 12 over variables X with realizations x ~ P(X) on a variable
X E X is Øx Qv, (X). For economy of notation, we will simply write v 1x.
Assumption 4.1. Let us assume an unknown SCM M but with known DAG G Further assume its do-SVs are identifiable in 9M (i.e., (S) is identifiable VS X) and that the resulting P(V) is strictly positive. Note that GM may include latent confounders as long as its do-SVs are identifiable.
Jung et al. 12] employed the EB approach, using an estimand for each term (S)). This makes do- SHAP impractical, requiring different ML models for the estimand's terms and an ad-hoc computation following the formula. In response, we propose to use the EA approach: 1) train a single SCM to learn P(V); 2) for each query (S), determine if it is identifiable (as we do in the EB approach); and 3) use general SCM-based procedures, not the estimand, to estimate the query. An illustrative example
of this SCM strategy is provided in appendix H for further details, please refer to [18 13 28
4.2 Efficient estimation of the do-Shapley value
In this section, we derive a novel algorithm to accelerate do-SHAP. We leave all proofs and the more efficient version of the algorithm to appendix D
Proposition 4.2. For any non-ancestor X of Øx = 0.
Consequently, we can restrict & Y's ancestors, since every other do-SV will necessarily be O. Assumption 4.3. Given SCM M (V, W, P. F. and target r.v. Y E V, we assume M to be the projected SCM MY) (see theorem C.8 and simply denote it M.. From now on, V = X U (Y} with X = An(Y) (Y} (Vo..... VK-1) ) in topological order. Let Y == Vk.
Let us introduce the concept of frontiers, with which we will reduce coalitions.
Definition 4.4. Given any node X X, a subset S S a frontier between X and Y if X & S and all directed paths p (X,..., ... Y) from X to Y are blocked by S, i.e., 3Z E S.t.t Z E p. We denote the set of frontiers between X and Y in G as Frg(X,Y)
Proposition 4.5. Given X E X and Y, and a subset S Frg(X,Y) Y), then v(S U (X)) v(S). Remark 4.6. For any parent X E Pay, no subset S C X (X) is a frontier between X and Y.
Finally, using these properties, let us reduce any given coalition S into its irreducible subset S' C S. i..., ((S) v(S') and vX S', S' {X} & Frg (X.Y). While an alternative definition exists (see theorem D.IO), the following form motivates algorithm to efficiently reduce coalitions.
"This is standard assumption in the SCM community. If the graph is not known, Causal Discovery algorithms (35) can derive a potential graph, later refined with domain expertise and/or randomized experiments. 'Running the identifiability algorithms (section 3.2) on all 2|X terms priori is unnecessary. Instead, when using the approximation method discussed in section 3.4. we can test identifiability for each new sampled query, caching results for repeated coalitions. If any coalition found to be non-identifiable during this process, an error state should halt SH-S immediately; otherwise. if no -on-itentieiable coalition is found, our do-SV estimation will be valid. Moreover, certain graph structures (e.g.. no latent confounders) make So-SVs trivially identifiable; general graphical criterion for dV identifiability is left for future work.
5

---

Algorithm 1
Frontier-Reducibbllg Algorithm (FRA) set version
Require: S C X, coalition.
13:
while C C 2 and Y & C
Require: Fr, a map: tuple[int] - bool.
14:
+ P
Require: G, causal graph.
15:
C C UCec \ end while Fr|T] (C Ø)
1: procedure FRA Fr; 9)
16:
2: SS <g)
17:
3: P Ø
18:
end if
4: Z Ø
19:
if Fr[T] then
5: k -t S
20:
Z - Z U (X}
6:
while k: > 0 do
21:
end if
7:
X < Sik]
22:
end if
8:
if X & PYg then
23:
P t P (X)
9:
P' + Pn De)(X) T (P') Z) D
24:
k k k
25:
end while
11:
if Fr then [X}
26:
return S Z
27:
end procedure
Theorem 4.7. Given a topological order <g in 9 and S C X, let 2 == (X E S S20x E Frg(X,Y)), with S>ex (Z E Z >g X}. Then v(S) v(S Z), and S Z is irreducible.
Thanks to this theorem, we can derive the irreducible subset of any coalition. Then, we evaluate its v-value with our SCM and store it in a cache. If, during the do-SHAP calculation, we encounter another subset S' with the same irreducible subset as the previous S, we can employ the cached y-value of that irreducible subset, thereby reducing the number of coalitions evaluate.
From theorem 4.7 we derive the Frontier- Reduuiiiitd Algorithm (FRA) in algorithm [ which determines the irreducible subset of any coalition S efficiently. We start by sorting the coalition in the order defined by 9 (line 2) and then iterate through the nodes descendingly (lines 5-6, 24). Given a step k and the corresponding node X (line 7), P contains the nodes following X in S (line 23). If X is a parent of Y, it trivially has no frontiers, so it cannot be removed (line 8). Otherwise, if P blocks all paths from X to Y (lines 12-17), it is a frontier for X, which means X must be included in Z (line 20), the set of superfluous nodes.
Let us exemplify with fig. 2 where we try to reduce S = (,, For instance, on k = 1, X A, and P {C, E, FF. A is not a parent of Y, so we need to determine if E Frg(A, For that, we move through every path from X Y, and if no path reaches Y without being interrupted by a node in P, then is a frontier between and Y, and X can be removed by adding it to Z. Note that we use the Fr map cache these computations (lines 9-11, 17) using reduced version of P, since P E (A, Y) if (P (X)(X)) Z E Frg Y). Fr stores whether the key T can be reduced by its first (sorted) element X. Please refer to appendix D.2.2 for an in-depth explanation of FRA and for algorithm 3 an alternative, more efficient version using integer-encoded coalitions.
To finish this subsection, let draw parallels Luther et al. 's work (36). in which, for conditional- SHAP, pairs (SS(((()) v(S) were identified to be skipped, since they resulted in null differential in SHAP's formula. We move further by: 1) extending the method to do-SHAP, which requires the use of do-calculus to derive these properties; and 2) by describing and efficiently computing the irreducible subset S' such that v(S) =(S)), instead of only removing a single node.
This results greater speed-up. As an example, consider the chain graph + B - Y. For ΦA. the pairs are v(AA) * v(Ø) and v(A, B) v(B), while for ΦB, v(B) + v()) and v(A, B) # (A).. FRA would only need to compute the irreducible sets Ø, [A]. and (B), since v(A, B) = rBB). while Luther's method needs to evaluate every single coalition eventually, even if v (AA, = could be skipped while computing A.A Now, let us demonstrate this behavior in general:
Proposition 4.8. Under assumption
Y X, 3Z E X s.f. least one of the following is true:
Z $ and S & Fra(Z,Y) Y).
. Z S and S (Z) & Fr)(Z,Y).

---

k=4
A
C
E
F
B
F
A
C
X
A
E
Y
P
k=
A
C
F
Z Z
C
D
k=1
C
F
Figure 2: FRA execution example. Causal Graph with nodes in alphabetical order representing the selected topologiaal order. b) FRA execution steps, with k representing the loop step (lines 5-6, 24), X the current node (line 7), P the potential frontier for X, and Z storing the nodes to be removed from S. The result of this execution is the coalition reduction {A, E, F) + {C,
Consequently, for any pair v(S U (X)) v(S) identified by Luther, we know that 3Z X s.t. somewhere else in the (exact) do-SV computation, S will reappear and cannot be skipped: either Z & S, vSS U {2)) # v(S) or E S, (S) + v(S {2}) nnon-parametrically).. By the same argument, the same can be said about (S U {X})) Therefore, Luther cannot omit these new pairs and will eventually evaluate all v(S). even some were omitted in previous pairs.
Now consider FRA. If we encountered pair (S same irreducible subset, thereby can skipped without evaluating them. However, even we later encounter them in skippaip pair, their irreducible subsets can be evaluated once and cached for subsequent reappearances. In other words, with Luther's strategy, all 2 coalitions will need to be evaluated eventually, regardless if they were omitted previously in another pair. In contrast, by determining the irreducible subsets and storing their values in cache, less evaluations will be necessary. Naturally, in the case of SHAP's approximate method, we may not re-encounter every coalition in an unskippable pair, but even in that case, our method need not compute the skippable pair either. Therefore, FRA can only improve upon Luther's speed-up.
v/(),, both must necessarily result in the
4.3 do-Shapley explanations
So far, we have been talking about do-SHAP values w.r.f. a variable E V in a certain SCM M, but there two use cases to consider in practice: either want to explain ML model that models Y given some inputs X' C V/ {Y} or we want to explain the original variable directly.
If we want to explain a ML model f(X' == E [Y X'), Y is replaced by Y' f(X') (with no Ey. since ff is deterministic): we then work on the projected SCM M[Am(Y') with Pay, X*. Note that this subgraph may contain variables other than those in X', since any X E X X' would be an ancestor to an X' X2, and therefore an ancestor of Y. With this SCM, we can apply EA procedures to estimate do-SHAP. We exemplify this case in the experiment in section 5.1
If, instead, wanted explain Y directly, simply employ do-SHAP on a proxy SCM, but note that for a particular (x. y) ~ P(X, Y). ExEX 6x, (X) IE [Y x - EE [Y] * y [Y] (unless Y is a constant distribution). There is a gap between the contribution of X (A,, (X)) and the actual value of Y, because our particular v/ interventional query, is essentially population estimate, and as such aggregates for the whole distribution. In order to explain a particular outcome, we need some kind of counterfactual value function vs this promising avenue of research, but is left for future work, since it is beyond the scope of this paper. As an alternative approach, the following theorem proves that, under additional assumptions, we can explain this gap through Ey's 's do-SV contribution.
Theorem 4.9. do-Shapley Value for the Noise.
Assume that U(y,)) = Ø and that fy E F follows an additive noise model, i.e., Y f(Pay) + Ey, for certain f. Consider the do Sh-phhll game with players XU (Fx); then, dEy = y E pay]. while ox for X E X can be computed w.r.t. X only. Furthermore, Exex 0x +Øxx y E [Y]
7

---

Consequently, assuming an unconfounded Y with additive noise, we can explain inaccessible DGPs with attribution to the noise and no computational overhead. In practice, we define ML model (p(aa)) E (Y pay] and explain it instead, computing the do-SV for Fy as DEY y (pay).
5 Experiments
This section contains the empirical validation of our approach. We begin with a synthetic DGP, from which we can derive ground truth do-SVs, measure estimation emor on several EA methods. Secondly, we demonstrate the speedup resulting from the FRA-cache with an ablation test. Finally, showcase do-SHAP explanations two real world datasets, left appendix [F] due to space restrictions. Please refer to the Supplementary Material for the code of these experiments.
5.1 Estimation performance
The goal of this experiment is to evaluate if proxy SCM can correctly estimate (identifiable) do-SVs without access to the true underlying DGP. Let us design first synthetic Ma with variables V. following the graph in fig. 3 We train a ML model fpax) = E [Y] pay], and create an SCM M using the same structural equations as Mo for X = V \ {Y} but with Y replaced by Y = f(Pay). This represents our SCM of study. We can consider two cases, both identifiable, by assuming U(x,8) is observed (Markovian) or latent Mark-vaarnv
Z
Figure Semi-Markovian graph. The Markovian graph results from considering U(x,B) as measured.
We replicate the experiment 30 times with different seeds. Let D be a dataset generated from M with N 1000 i. samples. With access to M, we can estimate each query v(S) with M i. d. samples from the intervened SCM, passing them through f and averaging the outputs; we will use the corresponding do-SVs
+ = (oxx )EEM))X)E ground truth. We also train several proxy SCMs (with Y' replacing Y) to learn P(V) and then estimate the do-Shapley values = (Øx )E(N),,EX. finally computing their Px, y2 We will also compare against a marginal-SH.Ne estimator (which should result in different values). We compute the average test log- likelihood (loglk) for each model as way to measure distribution adjustment. Finally, for all X E X,
SHAP estimation loss (2 ④) == N Σ EN
we compute their Feature Importance (FI), defined as Flx := & EiE(N xo ///Exxxx [
We will test do-SHAP with several SCM architectures for further implementation details and justification of our choices please refer to section E.I.I These methods are: 1) a linear SCM with Normal distributions for each variable, used as a baseline; 2) the Distributional Causal Node
20
(DCN), with every node modeled after a pre-defined distribution; and 3) Deep Causal Graph
(DCG) powered with Normalizing Flows. Additionally, in order to test the graph-as-a-whole
approach (see section 2 we opt for Causal Normalizing Flows (CNF) (28].
See fig. 4 for the Markovian case. As expected, better distributional adjustment to P(V) (loglk) correlates with better estimates do-SVs. Linear-SCM cannot properly model P(V), and so its do- SHAP performance suffers; DCN comes close to the best models, probably because of the synthetic nature of the data; DCGs and CNFs exhibit similar performance except for more variance on DCGs, possibly due to CNFs modeling all variables once. Finally, marginal- marginal-SHAP SHAP significantly differs from the do-SHAP ground truth, showing that, evidently, do-SHAP and marginal-SHAr measure different attributions. Fl comparisons w.r.f. ground truth values are also aligned with the previous results. We leave the semi-Markove in presence of a latent confounder; DCGs display the best estimation performance. In the following, we will employ DCGs even if CNFs seem to be more stable variance- wise, because DCGs admit latent confounders and were orders of magnitude faster in our experiments.
experiment for section 1.2 with equivalent conclusions, even
None of these methods are external baselines, as do-SHAP not yet been tested with EA approaches and remains underexplored overall (see (37) for an example), largely due to the ad hoc nature of EB methods. Additionally, EB strategies are excluded from our experiments because they require manual adaptation for each coalition, whereas EA is generalizable and automatable, rendering direct comparison inappropriate.
8

---

Inear DC2
Teat tariog PACK
60 Far
2,000
Pestare
Figure 4: Markovian case. Box-plots computed over 30 realizations of the dataset. (a) Distribution adjustment score, log-likellnn log-likelihood (bigger better). (b) SHAP estimation loss, L (lower is better). (c)
Feature Importance (the closer to ground-truth, the better). Dashed horizontal line represents uniform importance (
See section
E. for a bigger figure.
Bagle comoutee craditbree a8ee 1HL
3.0
nammoaaaa exeuten en
Exeeu on time 0) typose
basding cache FBA
0,8
2.5
108
plogge procil (io
0.6
0.6
2.0
10.8
101
0.4
0.2
0.2
2.0
(Proriatte))
(Chuerisbbec
Figure 5: FRA experiments. (a) Ratio of computed coalitions after FRA. (b) FRA execution time coalition. (c) do-SHAP execution time (logarithmic scale) without cache (baseline), with cache (cache) and with an FRA cache (FRA). Error bars at 2-sigma over replications.
5.2 Frontier-Reducibiie Algorithm
We the computational impact of FRA. Let consider GK the class of graphs with K 1). Y.Y.. =
= VK. where E (0, represents the probability of any possible edge V3 + V,, S j j S appearing in G. and such that G fulfills two conditions: 1) AY(Y) = X U [Y} and Pay S X. We sample uniformly from GK.p using rejection sampling to ensure both conditions. Figure 5 shows the results of our experiments, with error bars for the mean of each metric at 2-sigma over 30 random graphs per configuration.
nodes, defined in topological order, X = (V..
Figure 5 (a) shows the average ratio of coalitions (out of [X) = 2*) that need to be passed through after reduction by FRA. Note that for higher values of K, each p-curve approaches p. i.e., in the case of 0.1, a reduction in u-computations of 90%. Figure (b) shows the average execution time of FRA per coalition. Despite the exponentially-laree number of directed paths in the graph, the computation of FRA appears to grow linearly with K, due the fact that it scales with the size of the coalition S to be evaluated and the depth of the graph, both at most K. For K < 20, the еттог bars do not exceed 3us per FRA call.
Let K (5...., ....,,,00,, 20) and {0.1.... 0.9}.
Finally, we evaluate FRA with ablation test in fig. (c). We design synthetic DGPs for random G E GK,p with VX E V, fx (pax, Ex) == mean (pax Ex, Ex ~ NN 1). We choose a linear SCM for its fast execution; real-world SCMs, with far complex architectures, will require longer to execute, so FRA will have an even stronger impact. We evaluate do-SHAP with a linear DCG and using the approximate method with N permutations such that least half the total number of coalitions are expected to have been processed after N permutations 2) this value for N is computed using eq. (6) in appendix We restrict this experiment K We can now compare the mean execution time when evaluating every coalition (baseline), when employing cache avoid repetitions in v-computations, and when employing an FRA-cache (fra) to reduce and cache coalitions. As result, we can see a consistent pattern: FRA is an order of magnitude faster than the baseline and twice faster than the cache.
that N 30 and set p 0.25.
'Note that when Pay X. FRA has effect (see theorem 4.6): since this is of interest for this experiment, such cases are discarded. discuss limitation the speed-up power of FRA in section 9This particular choice for N results in an exponential time-growtt w.r.f. K, but this is not necessarily the case in the usual setting, where choose N based estimation variance computational limitations.

---

Note that it is not prohibitive to run our method for higher values of K; we repeat the experiment for K 100 without replications to explain a sample with 1000 permutations. The DCG training time amounts to 16s and the do-SHAP executions for no-cache, cache, and FRA-cache lasted for 26m01s, 25m20s and 21 m44, respectively. The average error of estimation 2.71e-4. There still an exponential trend in computation-time (we make no claim of reducing the exponential nature of SHAP) but: 1) it is possible to compute do-SVs on high K with an automatized, single-model approach, in contrast with EB approaches that would require manual specification of procedures based on estimands, rendering them infeasible in practice; and 2) we achieve a considerable improvement time-wise (4m w.r.f. cache) at negligible cost in running FRA (8s in total).
Please refer to section E.2 that FRA's execution time is negligible w.r.f. the computation of vSS), even on linear SCMs. This difference can only increase with more complex SCM architectures; therefore, for virtually no cost, FRA skips computing vS) up to significant factor, resulting in marked speedup for do-SHAP.
(ection[E.2 for the full experimental setup and further tests on FRA. There we show
6 Limitations
We devote this section to discussing the limitations of this work.
Firstly, we assume to know the causal graph 9; while Causal Discovery algorithms and/or domain experts can help to define it, our techniques are sensitive to graph misspecification. Regrettably, there are no doubly-robust guarantees for EA techniques yet, which is definite disadvantage w.r.t. EB alternatives. Nevertheless, the ad-hoc nature of EB methods makes them impractical for do-SHAP, with or without doubly-robust guarantees, while our approach can adapt to complex graphs. In any case, this issue falls out of scope for this paper, which is focused on facilitating and accelerating do-SV estimation. An additional limitation for some EA methods is error propagation: how misalignment in modeling P(V) can propagate to do-SV estimations. However, some works in the literature address this issue by modeling all variables in single-pass F, avoiding compounding errors 26 28
Secondly, our approach requires modeling the data distribution by training an appropriate SCM, which can take some (offline) time. However, once the SCM is trained, any new sample can be explained (online) from that same model. SCMs can typically be trained in the order of minutes (half an hour for the most complex graphs/distributions in this work, figs. 10 and 12 in the appendix), and after that offline training, SHAP execution (online) becomes the most pressing factor time-wise. The FRA algorithm helps in significantly accelerating this step, demonstrated in section [5.2 but this speed-up only results when not all variables are parents of Y: otherwise, no coalition would be reducible. Fortunately, real-world DGPs rarely have all (proper) Y -aancestors as parents, and in ML systems, defining all X as model inputs (Pay') ) is hardly advisable, since they may contain non- ancestors of Y (leading to spurious correlations or anti-causal effects (38) or inputs A C \ Pay that are blocked by Pay, (Y 1 A Pay). in which case their inclusion could lead to overfitting and adversarial vulnerability. Consequently, feature selection strategies should aim at discarding these cases, which paves the way for FRA speed-ups.
7 Conclusion
In this work, we have introduced a practical method to estimate do-SVs on arbitrarily complex graphs by using the estimand-agnostic approach, with which we can estimate any identifiable query using general procedures agnostic to the query's estimand. This flexibility is essential to make these techniques accessible to practitioners, who may not necessarily be experts in Causal Inference. We have tested our approach on multiple SCM architectures, illustrating the relationship between distribution modeling and do-SHAP estimation performance. We have proposed the novel Frontier- Reducibility Algorithm, which speeds up do-SHAP significantly at virtually no cost. Finally, we have tested the capabilities of our method and applied it on two real-world datasets (see appendix F.. explanatoo showcasing LoAS's explanatory power, either for ML models or inaccessible DGPs.
Further work could propose new SCM architectures to better model the data distribution, overcoming some of the identified limitations, along with more efficient estimators, ideally with doubly-robust guarantees. A general graphical criterion for do-SV identifiability is also worthwhile new direction. Finally, do-SVs are based on interventional queries, but these are inherently population measures; counterfactual value functions y could result in promising new kind of causal, local explanations.
10

---

Acknowledgments and Disclosure of Funding
The research leading to these results has received funding from the A14Science fellowship within the "Generacion D" initiative, Red.es, Ministerio para la Transformación Digital de la Función Pública, for talent attraction (C005/24-ED CVT), funded by the European Union NexIGenerationEU funds, through PRTR. It also was funded by the Horizon Europe Programme under the A14DEBUNK Project (htps:/wwww.iiddeunk.cc
grant agreement num. 135757. Additionally, this work has been partially supported by JDC2022-0503 13-I funded by MCIN/AEI/10 10t.//.0..3390011111 100501100111111 1033al by the European Union UoxIGenerationnU/PRRRR We also gratefully acknowledge Novartis for sponsoring Tomås Garriga's industrial PhD, and the Government of Catalonia's Industrial PhDs Plan for funding part of this research.
References
[1] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine Bias. Propublica, May 2016.
[2] Yannic Neuhaus, Maximilian Augustin, Valentyn Boreiko, and Matthias Hein. Spurious features everywhere large-scale detection of harmful spurious features ImageNet. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 20235-20246, 2023.
[3] Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties neural networks. In 2nd International Conference on Learning Representations, ICLR, 2014.
[4] 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/EC (General Data Protection Regulation). 2016.
[5] Yu Zhang, Peter Tiño, Aleš Leonardis, and Ke Tang. A survey on neural network interpretability. IEEE Transactions on Emerging Topics in Computational Intelligence, 5(5):726 2021.
[6] Erik Štrumbelj and Igor Kononenko. Explaining prediction models and individual predictions with feature contributions. Knowledge and information systems, 41:647-665, 2014.
[7] Hugh Chen, Ian C Covert, Scott M Lundberg, and Su-In Lee. Algorithms to estimate Shapley value feature attributions. Nature Machine Intelligence, pages 1-12, 2023.
[8] Christopher Frye, Colin Rowat, and Ilya Feige. Asymmetric Shapley values: incorporat- ing causal knowledge into aggostic explainability. Advances in Neural Information Processing Systems (NeurIPS), 33:1229-111 1239, 2020.
[9] Tom Heskes, Evi Sijben, Ioan Gabriel Bucur, and Tom Claassen. Causal Shapley values: exploiting causal knowledge to explain individual predictions of complex models. Advances in Neural Information Processing Systems (NeurIPS), 33:4778-477 4789, 2020.
[10] Steffen L Lauritzen and Thomas S Richardson. Chain graph models and their causal interpreta- tions. Journal of the Royal Statistical Society Series B: Statistical Methodology, 64(3):321-348, 2002.
[11] Dominik Janzing, Lenon Minorics, and Patrick Blöbaum. Feature relevance quantification in explainable Al: A causal problem. In International Conference on artificial intelligence and statistics, pages 2907-2916. PMLR, 2020.
[12] Yonghan Jung, Shiva Kasiviswanathan, Jin Tian, Dominik Janzing, Patrick Blöbaum, and Elias Bareinboim. On measuring causal contributions via do-interventions. In International Conference on Machine Learning, pages 10476-10501. PMLR, 2022.
[13] Álvaro Parafita and Jordi Vitrià. Estimand-agnostic causal query estimation with Deep Causal Graphs, IEEE Access, 10:71370-71388 2022.

---

[14] Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. Advances neural information processing systems, 30, 2017.
[15] Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, second edition, 2009.
[16] Jiaxuan Wang, Jenna Wiens, and Scott Lundherg. Shapley flow:
A graph-based approach to interpreting model predictions, In International Conference on Artificial Intelligence and Statistics, pages 721-729. PMLR, 2021.
[17] Kevin Xia, Kai-Zhan Lee, Yoshua Bengio, and Elias Bareinboim. The causal-neural connection: expressiveness, learnability, and inference. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 10823-10836, 2021.
[18] Murat Kocaoglu, Christopher Snyder, Alexandros G. Dimakis, and Sriram Vishwanath. Causal- GAN: learning causal implicit generative models with adversarial training. In Proceedings of the 6th International Conference on Learning Representations (ICLR), Vancouver, Canada,
2018.
[19] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative Adversarial Networks. Communications of the ACM, 63(1 1):139-1144, 2020.
[20] Álvaro Parafita and Jordi Vitrià. Explaining visual models by causal attribution. In 2019 IEEE/CVF International Conference on Computer Vision Workshop (ICCVW), pages 4167- 4175, Seoul, Korea, 2019. IEEE
[21] Nick Pawlowski, Daniel Coelho de Castro, and Ben Glocker. Deep Structural Causal Models for tractable counterfactual inference. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
[22] George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshminarayanan. Normalizing Flows for probabilistic modeling and inference. Journal of Machine Learning Research, 22(57), 2021.
[23] Diederik P. Kingma and Max Welling. Auto-encoding variational Bayes. In Proceedings of the 2nd International Conference on Learning Representations (ICLR), Banff, Canada, 2014.
[24] Patrick Chao, Patrick Blöbaum, and Shiva Prasad Kasiviswanathan. Interventional and counter- factual inference with diffusion models. arXiv preprint arXiv:2330. 2023.
[25] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems (NeurIPS), 33:6840-6855 2020.
[26] Pablo Sánchez-Martun, Miriam Rateike, and Isabel Valera. VACA: designing Variational Graph Autoencoders for causal queries. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, volume 36, 2022.
[27] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al open, 1:57-81, 2020.
[28] Adrián Javaloy, Pablo Sánchez-Marte and Isabel Valera. Causal normalizing flows: from theory to practice. Advances in Neural Information Processing Systems, 36, 2024.
[29] Ilya Shpitser and Judea Pearl. Identification of joint interventional distributions in recursive semi-Markovian causal models. In Proceedings of 2 National Conference on Artificial Intelligence (AAAI), pages 1219-1226, Boston, MA, USA, 2006.
[30] Ilya Shpitser and Judea Pearl. Identification of conditional interventional distributions. In Proceedings of the 22th Conference Uncertainty in Artificial Intelligence (UAI), pages 437-444, Cambridge, MA, USA, 2006.
[31] Santtu Tikka and Juha Karvanen. Identifying causal effects with the R package causaleffect. Journal of Statistical Software, 76(12):1-30, 2017.
12

---

[32] Martí Pedemonte, Jordi Vitrià, and Álvaro Parafita. Algorithmic causal effect identification with causaleffect. arXiv preprint arXiv:2107.0463,, 2021.
[33] LS Shapley. value for n-person games. In Contributions to the Theory of Games (AM-28), Volume II, pages 307-317. Princeton University Press, 1953.
[34] Irwin Mann and Lloyd S Shapley. Values of large games, IV: Evaluating the electoral college by Montecarlo techniques. Rand Corporation, 1960.
[35] Peter Spirtes and Kun Zhang. Causal discovery and inference: concepts and recent methodolog- ical advances. In Applied informatics, volume 3. SpringerOpen, 2016.
[36] Christoph Luther, Gunnar König, and Moritz Grosse-Wentrup. Efficient sage estimation via causal structure learning. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1150--16770 PMLR, 2023.
[37] Qi Zhang, Zhenliang Ma, Yuanyuan Wu, Yang Liu, and Xiaobo Qu Quantifying variable contributions to bus operation delays considering causal relationships. Transportation Research Part E: Logistics and Transportation Review, 194:103881, 2025.
[38] Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings the IEEE, 109(5):612-66) 2021.
[39] Sanghack Lee and Elias Bareinboim. Causal effect identifiability under partial-observabiityy. In International Conference on Machine Learning, pages 5692-5700 5701. PMLR, 2020.
[40] Conor Durkan, Artur Bekasov, lain Murray, and George Papamakarios. Neural Spline Flows. In Advances in Neural Information Processing Systems (NeurlPS), volume 32, pages 7511-7511 1-7522, Vancouver, Canada, 2019.
[41] Djork-Aré Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). arXiv preprint arXiv:1511.0728) 2015.
[42] Iya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019.
[43] CDC. CDC Diabetes Health Indicators. UCI Machine Learning Repository, 2015. Preprocessed dataset downloaded from DOI: https///ol.ogg/1104444//333
[44] Hadi Fanaee-T and Joao Gama. Event labeling combining ensemble detectors and background knowledge. Progress in Artificial Intelligence, 2:113-127, 2014.
13

---

A Shapley value axioms
The SV o {ox Xxex is the unique attribution measure fulfilling number of desirable properties:
Σxex v(X) v(Ø) A(X); the sum of SVs adds up to the total contribution of X.
Efficiency:
Missingness: if VS C C [X], U [X)) = v(S), then ox = 0; players with no
contribution any coalition have Shapley value O.
Symmetry: if VS X \ (X,Y), v/S U (x)) vSS U (Y)), then Φx dy: players with identical contribution to any coalition have identical Shapley values.
Linearity: AA C X, vSS) = (S) + 22 (S), then AX E x, 2u (X) = thy (X) + Dag (X), and if VS C X, vSS) coalition game v.
v/ (S), then X- X, & (X) Φe (X); Φ is linear w.r.f. the
B Cache impact on the approximation algorithm
Consider the approximation method (see section 3.4), where we sample permutations of K elements uniformly with replacement, π ~ (((((())) so as to approximate the Shapley value with Monte Carlo estimator. In this section, we want to evaluate how much we can accelerate the computation of new permutations as we fill cache with the values of previously computed coalitions. When use a cache, once we compute coalition for the first time, we save its result in it (assuming no cache limit) and further computations of this coalition will incur in negligible computation time (simply a cache access). therefore speeding up the computation of new permutations. We want to measure exactly how much
speed up the process.
Let us define some notation. Given и E [T((K), let us denote by C(T) the set of K + coalitions S E [(( defined by taking the first elements of æ, = O.. (e.g., for = (3.1.2), 2). C(x) = {2, (3) 1), (3,1 (3, Then, for an arbitrary S e [[[]] and a permutation π (II((()))
P(S C(T)) SSK(KK [S])
K S
K!
since S must appear at the beginning of i in an arbitrary order, so there |S] possibilities, with the remaining (K (S)) elements in an arbitrary order, so (K -SS)),, out of the total K! possible permutations. Since we are taking N i. d. permutations (T7(") )ne[N]. it follows that
K
P(vn (N),SE((TT
1
which is the probability of an arbitrary coalition S not belonging any of the N previously sampled permutations, and therefore, still needs to be computed when it appears in a future permutation. In particular, note that we do not need know the elements of S. only its cardinality [S], which
will denote by s [S]. Given the set of K coalitions ((v()) in permutation x(N), can now compute the expected ratio of its coalitions not found in any of the previous permutations (therefore not cached); in other words, the expected ratio of computations need to perform the N-th permutation, N > 1, is:
N-1
K +1
P(Yn E [N - 11,S & ((+(a))) SEC()(N))
Σ
= K +
K
(6)
s=0
For = 1, the ratio is trivially 1. Morover, for 8 = 0 (S- = 2) and s = K (S = [K]) the term
- (K) - becomes (it impossible not to have seen them in previous permutation, since they in every permutation), so we omit these cases in the following sums.
14

---

Expected ratio of cachod coalitions
1.0
50
Expecied ratio of cached coal itlinss
1.0
20
40
after peruuaatons
0.8
permutation
15
0.6
30
0.6
10
20
0.2
0.2
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Figure 6: Cache evolution plots. Ratio of coalitions in x ((n) already cached. b) Ratio of total coalitions already cached after permutations. Both x-axis represent the number of permutations divided by 2 so to compare between different values of K.
Finally, the expected ratio of cached coalitions (out of the total number of coalitions 2 after N 2 1 permutations
K+1
N
K-1
P(vn' 4
((((m)))
Σ
2K
2K
#=1 (EC(=(m))
n=
K +1
1
Σ
K
1
K
1
K
2K
2K
K+1
1
K-1
Σ
(6)
K
-1
1
K-1
K
1
K
2K
2K
2
8
s=1
#=1
K
N
K
=
1 -
2K
==0
where we first split the sum over n for 1 and
and then swap the sums and apply, for
= (x) the equality Σm= x."h = x 1-z for E (0, 1) (which is the case when 8 * 0, K),
and noting that - = (K)). We then split the sum in two terms, with the first half adding up to with 2k The rest of the transformation is trivial.
We now plot eqs. (6) and
fig. (a) and (b), respectively, for several values of K (represented by color opacity). The x-axis in both cases is 2k. so to show how each curve progresses as + 2 where will have encountered (K + 1)2* coalitions. We can that the likelihood of encountering greviously-compuss computations required per permutation speed up significantly in the early stages. However, if wanted to cover the totality of possible coalitions with the permutation method, this would require many more coalitions given the high likelihood of collision; this is relevant particularly for section 5.2 where we set N to be high enough so that at least half the total number of coalitions are expected to have been processed after N permutations.
coalitions is very high early in the process, which means that the
These plots are merely illustrative; we encourage researchers to make use of the derived equations to adjust for the appropriate number of permutations in terms of computation time budget.
C Causal Inference concepts
We include here some additional notation and concepts for Causal Inference, necessary for the proofs in appendix D
15

---

Notation
Given rvv. & Y and disjoint set of r.v.s (possibly empty), we denote that X is independent of Y conditioned on Z in distribution P by (X T LLY Z)p. Given disjoint sets of r.v.s X, Y, Z, we say that X is independent of Y given Z in a distribution P, denoted by (X 1 Z)p, if and only VX E X, VY E (X 1 Y p. P can be omitted unless it leads ambiguity.
Given X, Y C V, let Gay denote the graph modified such that all edges pointing towards nodes in X removed (overline) and all edges starting from nodes in removed (underline). We may incur in abuse of notation (e.g., 9x = ) unless it leads to ambiguity.
C.1 d-separability and do-caleulus
In the following, we will define the concept of d-separabilityy its connection to independence, and the three rules of do-calculus. Please refer [13 for more details. Definition C.1. d-separability.
Given DAG = (V, E), path is d-separated (blocked) by set Z V (possibly empty) if and only if either is true:
1. contains a chain A + B + C or fork A t B + C' such that B is in Z.
2. p contains a collider + B +- such that no descendant of B (including B) is Z.
Given disjoint sets X, Y, C V, we say that Z d-separates X from Y in G if Z d-separates every path p from node X E X node Y Y. We denote this by (X 1 Y Z)g. Definition C.2. Markov Compatibility.
We say that distribution P(V) set of variables V= -V,,... VK) is (Markov) compatible with a DAG 9 with V as vertices in G if P(V) = [[ke|K] P(V2 Pag(Vz)).
Theorem C.3. Independence and d-separability.
Given SCM M = -V, W, P,, F) compatible with a DAG GM and disjoint sets X,Y.Z C V, if (X L Y Z)au then (X 1 Y Z)p. Conversely, if (X L. Y Z)axo there exists at least one distribution P' compatible with 9m (infact, almost all) such that (X YYY |Z)pr
Remark C.4. The second statement comes from the fact that precise parameter choices 0 of distri- butions Pe might result in independence in otherwise unblocked path in G. Fortunately, such specific tuning θ rarely occurs in practice.
Remark C.S. If we need to determine independence relationships (X SLY 2) (Z possibly empty), simply verify that all paths connecting X and Y are blocked by Z, using d-separability.
Next, we introduce the three rules of do-calculus, with which we can transform causal queries step by step, until we reach the desired estimand.
Theorem C.6. Rules of do-calculus. Given an SCM M (V,WPP. (, compatible with DAG for any disjoint sets Y. W, S V (X and W possibly empty):
1. Insertion/deletion of observations (RI):
(Y Z, W) = PY W) if Z X, W)g,
2. Exchange of interventionslooserrttorr (R2):
(Y W) = PY W) (Y 1 Z X. W)
3. Insertion/deletion of interventions (R3):
(Y W) = PY W) (Y IL Z X, W W where Z(W)- Z Ang,(W), the set of nodes in Z that are not ancestors of W (including
W) in the graph Gx
C.2 Projected Structural Causal Models
Definition C.7. Divergent Path. divergent path between X and consists of two directed paths, from W X and from W Y, such that W W' or W t W'
16

---

Definition C.8. Projected SCM.
Given an SCM M (V. (VW.P..F) compatible with a DAG 9M and a subset V V, we define the projected causal DAG G[V"] defined on vertices V and W == E" U U. with E¹ = [Ex E E | } and U' as defined next, such that:
VV, Vi V", there a directed edge Vi, -> Vi if there exists a directed path from Vx Vi in GM where every internal node in the path is not in V.
VV,, V V., there is bidirected edge Vi ++ V/ (connected by a latent confounder U(,,) E 2(") if there exists divergent path in 9 between them such that every internal node is not in V".
We define the projected SCM M[V by restricting its graph to GM(V"), with distribution PM PM((V).
Remark C.9. The projected SCM respects all conditional independence relationships and the rules of do-calculus in the original graph. [39].
D Proofs
In this section, we will prove the results in the main paper and discuss the Prontier-Reduccbilge Algorithm.
D.1 Non-ancestors
Lemma D.1. Given a DAG = (V, E) and disjoint subsets of vertices X, Y C (possibly empty), if there is path in Gxy then p is path in G.
Proof. 9xy² 's edges are subset of G's edges, since Jxy only removes edges either ending in X or starting from Y. Adding those edges back in G cannot remove any edge from the path; hence, is path in G.
Proposition D.2. Non-Ancestors do not Contribute. Let M be an SCM M (V, W. P, F), Y the target rv., Xa subset X C V (Y) and x a realization x P For any X E X, if X is not ancestor of Y, then Qu, (X) 0.
Proof. We will prove that VX & Ang (X) v(S). If that is the case, then
E =
1
((K-1) -1
Φx
Σ
-x)) - -(()) 0.
K
[S]
SCX((X}
Note that EY 8 B BY if (Y) = P.(Y). which is implied by R3 (Y 1 X S)
Let us prove this independence by contradiction: assume there path p connecting and Y unblocked conditioned on S in GZ The path cannot start with X t.... since all edges pointing towards X are removed in G5x. So p X + ? Y. Since the path is unblocked, if there were any left arrows (+-) in the path, the resulting collider ... - B <- must necessarily fulfill to unblock the path. There are two cases: 1) if
S. then there is an edge B <-.... for a node B S, which cannot be true in O5 2) B E Angax(() \ S, then there a directed path from B to node in S, which again cannot happen in G5 because we have removed all edges pointing towards S. Therefore, the path must necessarily not contain any left arrows, which means that p is directed path from X to Y in G5x, which must also be directed path in G due to theorem D.I therefore X E Ang(Y), contradicting the initial assumption. No unblocked path can exist, which proves (Y 1L X S) and the theorem in turn.
Deggx (B)
17

---

D.2
Fruntier-Reducibilit Algorithm
We begin by defining the concept of frontier and proving several properties related necessary for the definition of the an alternative formulation of the FRA algorithm with integers for faster execution time and lesser memory usage.
Algorithm (FRA), introduced next. We finish with
D.2.1 Frontiers and properties
In the following, consider an SCM = (V, with associated DAG g = (V, E), where (V..... VK) is sorted in an arbitrary topological order of the graph. Let X == {Vo,... ................................ VK-ih. Y := Vx, and assume that X C An(YY. Note that there may be latent confounders (21 + Ø).
Definition D.3. Given any node X E X, subset S C X is frontier between X and Y if X & S and all directed paths p (X,...: Y) from X Y are blocked by S, i... 32 E S.t. Z E p. We denote the set of frontiers between X and Y in 9 as Fro(X,Y)
Proposition D.4. Given nodes X E X and Y, and a subset E Frg(X,Y), frontier from X to Y, then viS (X)) = vS)).
Proof. We will apply R3 by proving that (Y 1 X (S) 0gx in which case
VS = E YY s, T] E [Y s = v(S).
Note that in Ggx. all paths from to Y are front-door paths. Consider any such x X If the path is fully directed, since S is a frontier, 32 E S s.t. Z is in the path, thereby blocking it. it is not directed, there exists a collider ... + Z +- ..., which also blocks the path: & An(S), since S has ancestors other than itself in O5x and Z S because - Z is in p. Therefore, any path p between and must be blocked by S in 95x. which proves R3.
Y.
Remark D.5. For any parent X E Pay, subset S C {X} is frontier between X and Y. Proposition D.6. Given nodes X E X and Y, and a frontier S E Yr)(.,Y).
1. AS CXXXX).S 2 then S' E (Fr((X,)..
2. Sn De(X) E YY)(
Proof.
1. Since S E (X, Y). any directed path p between X and Y is blocked by S; being S' superset of S, it must also block all such paths.
2. Any non-descendant X cannot appear in a directed path from X to Y, which means that it is superfluous in the frontier set. As such, Sn De(X)= e Frg(X, Y).
Corollary D.7. Given X E X and X (X), les X 1xx (2 X).
S Fro(X, Y) S S2pX& E Frg(X, Y) + Sr Deg(X) Frg(X,
(8)
Proof. S E (X, Y), Sn De(X)= E (X, Y), and S S> 2 S De(X), since any Z E
Sn XX) fulfills Z >g X, which proves that S 825X Frg( (Y.). On the other hand, if S 2, x
Frg(X,Y). Y). E Frg(X, Y), since S 2 Spax. The remaining iff is trivial given theorem D.6
L
Definition D.8. A set S C X is Montier-RRduucite (FR) in G if 3X E S S (X) E Frg(X,Y).
In particular, if is FR by X E S. vSS) = ((S((X)).
Theorem D.9. Consider any FRS C X, and let us define == (X E S (X) Fro(X,V)) =
{X E S S>eX E Frg((X,Y) Y)). Then v(S) = v(S Z) and S Z is not FR.
18

---

Proof. Consider Z = [Z Z,,, in the order <g. Firstly, v(S) = v
{Z, }) by construction. and that S Z
Now, note that Syo7, E =Frg(Zi; (Z,, Y) by construction of Z and theorem D.7
S \ (Zi,,.... 25 2 S,. so by Prop. D.6 S
Then, let us assume that A1 j n, v(S) 41S Z.zz,) )- Given that Zzz,, {Zig } Fro(Zigt1 Y), then
ZZ E Fro Zi
u( 2 v/S !5 - vSS), which proves v(S) = (S \ Z) by induction.
Additionally, S Z is not FR since, if E s.t. S Z (x} E Fra(X, Y), then S (X} S Z {X) is also a frontier between X and Y, which implies that X Z.
For clearer characterization of the irreducible set, consider the following proposition.
Proposition D.10. Given a FR C X and its corresponding irreducible subset S' := S Z. with Z = (X e S S Fro((X ()), then S' = n Angz(Y)
Proof. We will show that S Z S Angg (Y), equivalently, that VX E ES, S & Fxr(X,Y) Y) iff X E Angg(Y)) Consider X E S. If > Frg Y). then S \ (X) Frg(X,Y) by theorem D.7 so there is a directed path from X to Y not blocked by S (X). Consequently. X is an ancestor of Y in the graph where we remove any incoming edges to S; in other words, E Ang
Conversely, if X E Angg (Y), there is a directed path from X to not blocked by S {X], therefore S\ (X) & Fx.(X, Y) and S & FX, Y). again by theorem D.7
Finally, let prove the property that explains why the identification of irreducible subsets results in less v-evaluations than Luther el al. 's (36] approach:
Proposition D.11. Under assumption
vS C X, 32 X s.I. at least one of the following is true:
7 g S and & Frg(Z, Y).
2. Z S and S {2} & Y2,
Proof. We will reason by cases:
I X. given that X Ang (Y)
(Y). there must be parent Z of Y in S. A parent Sf Y can never have frontier with Y, hence S [2) & Frg Y).
If S = Ø, AZ E x,0 Ø & Y2)( (otherwise, Z would not be an ancestor of Y, contradicting the assumption).
Let * 2. S X:
If S is irreducible, VZ E S, S,S & Fr(2,Y); otherwise, S would not be irreducible. If S is not irreducible, let S be its irreducible set (as determined by theorem D.9 and proposition D.10). We know that S' ل Ø; otherwise, VZ E S, Ø E meaning that Z Is not an ancestor of Y. contradicting the assumption. Now, ZZ S'. S {2} & Fro Fro(Z,Y) Y);Y); otherwise, by theorem D.9 Z would not belong to the irreducible set of S, which is St.
Under all possible cases, the result is proven.
D.2.2 Algorithm soundness
Theorem D.9 identifies which elements can be removed from the computation of v(S) for any set S. As result, if we compute and cache v(S Z). any other set with the same set can skip the v computation and return the cached value instead. Additionally, we do not need to test identifiability for FR sets, only for the corresponding Frontier- Irreducible sets. We now need to Algorithm (FRA), described in
define an efficient method to compute S \ Z, the algorithm 2 let first demonstrate its soundness.
Given S = (X......, X,,) in <g order, at step n..1, == X., and == (X.,...., X
S S At this stage, we test if P e Frr((X,)) Y), or equivalently, if (X))))))())) Fr)(X,Y).
19

---

Algorithm 2 Reducibr-y Algorithm (FRA) set version (with comments).
Require: S C X. coalition.
Require: Fr, a map: tuple[int] - bool.
Require: G, causal graph.
procedure FRA(S, Fr; 9)
2: SORT(S, <gg)
> Sort S topologically
3: P Ø
Dr Posterior nodes, S
4: Z+ Ø
D Superfluous variables Iterator index. moving backwards
5:
k <-= IS]
6:
while k: >> do
7:
X <- S[k]
>X= X
8:
i & PYg(Y) then
Parents have no frontiers Auxiliary variable for the loop P Cache key for Fr: (node, frontier) > Non-cached key, determine if P E F Y)
9:
P <- Pn (X)
10:
T T [X)
11:
ifT Fr then
12:
C+
> Iterate from X to its descendants While more nodes before Y D Add currently explored nodes to Filter frontier or sevviously-epplore nodes
13:
while C f 2 and Y & do
14:
P' + PUC
15:
C U- Chg(C) \ P
16:
end while
17:
Fr [T C=# Ø
> P Frg(X,Y) + we have not reached Y
18:
end if
19:
if Fr [T then
20:
-- ZU (X}
Add to superflous nodes
21:
end if
22:
end if
23:
P [U
Update S b Continue the global iteration
24:
k k
end while
26:
return S Z
> Remove superfluous nodes
27:
end procedure
in which case we will include it in Z. At the end of the process, Z {X E S> Frg(X, Y)}. which, by theorem D.9 means that v(S) v(S) Z). and S Z is not FR.
We include some optimizations to this algorithm. Firstly, we precompute PY) (Deg (X)) and (Xhg(X)) so that we do not need to traverse the graph every time they are needed. Secondly, employ the Fr cache, containing whether certain coalition (a set of integers) is Frontier- Reducible by its first (sorted) element, which is populated as FRA processes more sets S. On the other hand, when storing the results for P Frg (X, Y) in the Fr cache, store instead = ((P n Deg (X)) \ Z) U (X), which is equivalent: this is so that we can better employ the Fr cache, collapsing different P {X} sets into reduced keys. However, when testing the frontier in lines 12-17, it will be faster with the larger number of nodes in P' ;= P n Deg (X) (including previously removed nodes in Z), since they could cut paths earlier. As result, for any given set S C X, algorithm 2 requires |S] global iterations (one per element of S), some of them skipped because X Pag(Y), some already cached in Fr. Finally, this cache can be reused between explanations of do SHAP for the same graph; only the v cache must be reset every time. This speeds up further explanations with virtually zero cost from the FRA.
The next step is how to determine if the set Pa C X (X) is frontier between X and Y. Naively, could check if all directed paths between X and Y are blocked by (intersect with) Pt; could precompute all paths and store them for faster access, but the number of paths grows exponentially (in the worst case scenario, i.c., complete graph, there are 2 directed paths), which would in turn require an exponential number of iterations per frontier check. Instead, we devise a more efficient method, described in lines 12-17.
We now prove the validity of this procedure. Let us define C. := (X}. C, will never be empty nor contain Y. so always enter the loop. At each while-step 1 > 0, P := Ur Cy U P and C := Ucec.,, CC) \ P All directed paths from X to Y are sequences of parent-child pairs,
20

---

just as any node C' E C is a child of a certain node C" E Ci-1- Additionally. since every node in X an ancestor of Y. by exploring these parent-child sequences we will necessarily result in a directed path from X to Y. Therefore, every directed path is covered by sequence of nodes Ct E Ct unless they are discarded by P',, in which case either P blocked the node in the path, or it was a node already visited in a different path before, which would continue with a subpath C - ..... + Y that is currently being explored or has already been discarded.
Note that since Pt removes any already-visited nodes from C,, and we always move one level deeper in the graph. C,'s nodes are all necessarily at depth / from X. Given that the graph G is finite and acyclic, C will eventually be empty or contain Y (since it is the last node in any path), which guarantees that the loop ends. Let C, denote the last step. Note that if C, * Ø. then Y E Cn2 which means that there was a sequence of nodes, each a child of the previous one. that were never filtered by P'; in other words, there exists directed path from X to Y that is not blocked by P'. Therefore P' & Frg(X X, Y). On the other hand, if C., = 22, then every sequence of nodes (every path) was eventually blocked by P'. Therefore, P' E Fx.(X,Y).
In terms of execution time, since every step results in nodes one depth-level deeper, the number of iterations of this procedure cannot be higher than the maximum depth of the graph, which, in the worst case scenario (e.g., a chain graph) is K d, d being the depth of X, making it much more efficient than the naive strategy.
D.2.3 Integer formulation
We can further optimize FRA by transforming set operations into integer and binary operations,
resulting in algorithm 3 Let us demonstrate that both algorithms are equivalent. Given X =
(Vo..... Vx-1), K == X there is a bijection
P(X) - {o..... 2 1) such that Φ(S) Eves 2t Note that (SS) is K-length binary array with 1s in each position k (starting from the
end) such that V& E S. Consequently, let us define, for any E {1..... 22 1}, (s)s) == [log2 s
then (s)) = max {k| Vi2 E $ (s)]; if we subtract 21((s) from s, we can apply &b again to retrieve
the second-largest element, and so on until s 0 (S- = Ø). The sequence of elements (s)) returns the original set S x- (s).
Thanks to this bijection, we can "ø--nccoe" any node or coalition as unique integer, and we can perform all our operations directly on integers with arithmetic and binary operations, which are less expensive, timing- and memory-wise, than with operations over sequences of integers. Note that, VS, S' X:
1. (SSns) = (S) & (S'), with & the bitwise AND operator.
2. (SSUS) = ((S) (S'), with the bitwise OR operator.
= ((S) & (S"),, with the bitwise NOT operator. 4. SnS' = 0 + d(S (S) = (S) + (S*)
3.
5. S2 = (S S*) = (SS) - -SS))
Let us compare between the set and integer versions of the algorithm. Firstly, we precompute and d-encode PaY, De and Ch, since they will be used repeatedly throughout the algorithm. Note that do not need to sort S beforehand, instead passing it in its s o(S) representation IT We can obtain the elements in descending order, already encoded, by computing == 2 2 (line 5) and subtracting it from (line 28). We can check if an encoded x is a parent of Y with the & operator (line 6). We can restrict P, encoded by integer p. to P P n Deg (X), encoded by integer p', by using the & operator on the precomputed encoded set De [xr] == di Deg( (X)) (line 7). We can set the cache-key T := (P' Z) U (X} by its code (p' & -z) + x (line 8). Finally, in order to determine if P' is frontier between X and Y, we iterate over the elements in C2 by employing the same strategy as before (lines 10-21).
II practice, for larger values of K (e.g., K = 100). we must use bit operations to detect the largest 1-bit in instead of using the logarithm: these faster and not subject to numerical error. However, we denote this operation as [Log2 s] throughout the text and the algorithm for clarity and simplicity. It is more efficient to pass s directly to the procedure, since we can pre-encode all indices (O...., K 1} before generating permutations of them; then, we just need pass the sum of the chosen coalition.
21

---

Algorithm 3 Frrontir- Algorithm (FRA) integer version.
Require: 8:= (SS), S _ X.
Require: Fr, a map
bool.
Require: PaY == < (P))(
Require: De :- o (V.)) VR EX.
Require: Ch(24] - o(Chhg(V)) VV4 E EX.
1: procedure FRA(s, Fr; PaY, De, Ch)
2:
p 0
Posterior nodes, S
3: = 0
Superfluous variables
4: while > 0 do
D Iterating through S pegologicallybbckwaarrr
5:
+- 211022 s]
> = X
6:
if x & PaY
then
Parents have no frontiers Auxiliary variable for the loop Cache key for Fr: (node, frontier) b. Non-cached key, determine if P E Frg Y) Iterate from X to its descendants b While more nodes before Y Add currently explored nodes P' D C + Ucec CC² by iterating
7:
p' + x-p & De[z]
8:
t 4- (p' & -2) +
9:
if t E Fr then
10:
c
11:
while + 0 and y & c= do
D/ pple d fc
13:
14:
while e' > do
15:
x 2002
Get element X' C' > Add Cha (X') to C Remove X' from C' to continue the iteration
16:
C r c Ch(x')
17:
d c' x!
18:
end while
c c c & -p/
Filter frontier or previously-explored nodes
20:
end while
21:
Fr[O] c-=
b P E Frg(X,Y) have not reached Y
22:
end if
Fr[t] then
24:
2 + 2
Add to superflous nodes
end if
26:
end if
- p x 8
Update S
28:
Remove X from S to continue the global iteration
29:
end while
30:
return p
b Remove superfluous nodes
31:
end procedure
of these changes result in an equivalent algorithm, more time-efficient (as demonstrated in section E.2) and memory-efficient (since we operate and cache integers rather than tuples of integers).
D.3 do-Shapley value for the noise
Theorem D.12. do-Shapley Value for the Noise.
Given target r.v. Y V, consider the projected SCM M[An(Y)), with X An(Y) \ (Y) and realizations (x, u) ~ Y). Let (øx = (X)xx be the do-Shapley values associated with K players? X.
Let us assume that there is no latent confounder connected to Y, and that fy E F follows an additive noise model, i.e., Y (PPa Ey) f(Pay) + Ey for an unknown function f. Let o' be the do-Shapley values w.r.t. players = (U(Er) then, for any X X, 6'x = @x and d'y = - Y pay]. Furthermore, Exex Ø'x + dry = E [Y].
Proof. Let define some notation for convenience:
VS C X. Se X
22

---

Note that Pay S S U S" let us denote the selected values pay as the output of a function Pay(s, 5²)) for ease of exposition.
(S) = Es (S( for convenience of notation.
We want to compute do-Shapley values o' for the (K + 1--mmme (including Ey) with realizations (Ey,X, y) ~ P(Ev, P(Ey,X,Y) (with Ey latent, unknown) based on the values & for the K K-game (only including X) with the same realizations (x, y) ~ P(X, Y). Let us first determine the value of the following two quantities for any S C X (Ey S):
v(SU (Ev)) E (Y 8 = B,y Y [E E (S ())] + EY v/(s) +
We can perform the first step by marginalizing over S in Ps.vv. Then, (S 1 Ey S) 9 because any path p connecting Ey must necessarily have collider in Y, since De(Y) = Y. therefore blocking the path. By R3, Ps.yy (S*) = (S)) so we can remove from the expectation over S On the other hand, we know that Y = ((Pay) ) + Ey and by the linearity of expectations, we can remove By from the expectation. Finally, for later clarity, we can denote the first term by /S)).
Next, let us solve the analogous term for S:
w(S) = EY S] = Es Ev BY S,S, Ey] Es-B ([P [Ey] (/(S) BBy))
(10)
We proceed similarly, beginning with marginalization over S and Ey this time. In order to separate Ey from the first term, note that (S 1 Ey gg and (S 1 Ey)g, for the same reason as before: any path connecting Ey must necessarily pass through Y. which acts thereby blocking it. Hence, P(S", Ey $) P(S P(Ey 5) = P(S () P(Ey), with the
unconditioned collider,
former step by the rules of independence and the latter by R3. We can then split the expectation, this time with [Ey] as the second term and using the same notation // (S) again.
With these two computations, we can see that:
vSS U (Ex)) v(S) EY E [Ey],
(11)
and substituting it into the SHAP formula (with K + players):
K (S))
KE
Σ
(ex [(rr))
K
+1
x
Σ
K
(K)
(er R(Fr))
K
K+1
==0
= E [Ey]
(12)
We transform the first second step by realizing that we do not need know what the coalitions are, only their cardinality, so we can transform Escx into E by multiplying by (K)) the number of combinations of elements. This term and its inverse cancel out, and K constant terms summed together cancels with K-1 resulting in EY E [Ey]
Now, note that Ły = y (pay) and:
E [Y pay] E. [f(pay) + Eyl ((pay) [Ey],
(13)
so (pav) = E [Y| pay] - E [E Then,
SEy = E3
E [Ey] y - f(par) - EE [Er] y y-E EY pay].
(14)
This proves the value for d'Ey- Let compute d'x for any X E X. Lets C (XU (X). If Ey S, we can apply eq.
(9) and vsS) = 1'(S (Ey)) EY. Otherwise, eq. 10 gives us
23

---

v(S) = + E [.]] Now, Øx 's computation can use both results:
ox E
1
K
-1 (v(SU (Ex) w
(||++1
K+1
SEX((X)
Σ
1
K
- (x))
K+1
((S)
SEX((X)
E
(
1
((5) + 1)=")))))))) (()- + -15) (MiS (((S)())) v(S))
K
-
K+1
SEX(()
(1s)+ )
-1
+ ( (1)))) (1(S v(S))
E K+1
scx(ix
-E
E S(X(()
K 1 (
(v(SU(X)) - v()) 0x
(15)
We first split the SHAP formula in two: those sets that include Ey and those that do not; note that the combination terms case since the base set is S U {Ey) }). For the first to second step, we can bring together the two sums, and transform the first difference,
altered to reflect the size of the base set applied to ((S) + in the first
v(S X - v(S U (E = VS (SU( //(S) = VSS (X)) v(S), (16)
by applying eq. 9 and eq. (10) and cancelling the sy and E [Ey] terms, respectively. We now sum the two inverse combination terms; let |S], with S K since S _ X (X}:
K -1
K -1
(s+ 1)!(K 1-11 + s!(K -)
8 ++1
K!
(s+ s!(K 1)1 + (K - s) s!(K 1)! (K -1)!
(s 1+ K ss)s!(K - 1)!
K. K.KK -1)!
K ++1
s!(K - 1)! = K (K-1))
+ K K-
(17)
K
Substituting this result back into eq. (15), we can cancel out K + 1. which is exactly the value for SHAP in the K --player game without Ey.
We arrive at the last formula,
Finally, in order to prove the last step, let first prove that E [Y
X
[Y
pay]:
E Y x = E Y jaay
E Y
pay
E Y pay].
(18)
We first split X Pay U Par.. Next, apply R3 with (Y 1 Pay Pay lox since G3 only contain edges leading from Pay to Y and from confounders U(x.)) to Y; therefore, no path can exist from Pay to Y. Then, we apply R2 with (Y 1 Pay )orey since has no descendants and we remove any incoming edges to Y in GPay except for the ones starting from confounders in Ut..) Ø (by assumption), Y must be independent of Pay in GPay proving the expression.
Now we can prove the remaining fact:
Σ o + o
(E [Y - IE + (y E E| p)y
E
(19)
X
E Experiments
These experiments are executed on personal computers (particularly, Macbook with an M3 Pro chip) and do not require an infrastructure of workers for their execution. No experiment lasted longer than 6 hours to exccute in total throughout their multiple replications.
24

---

E.1
Synthetic dataset
We include here further details about the Synthetic experiment in section 5.1 bigger figures for the Markovian case (for better visibility) and discussion on the semi-Markovian case. Please refer to the supplementary code for the actual implementation of these experiments.
E.1.1 Implementation details
We chose several SCM architectures for the experiment; here we justify these choices. Regarding the classic approach of modeling an SCM with each of its functions f& F separately, some of the approaches mentioned in section 2 focus on how to model complex multivariate r.v.s (c.g., images), but the remaining univariate e.v. are modelled by specifying which probability distribution family they belong to. Since our DGP consists exclusively of univariate continuous r.v.s, these proposals are equivalent. Instead, we will employ Deep Causal Graph (DCG) [3], general framework for all sorts of implementations of SCMs. In particular, with DCGs, we can train three different kinds of SCM: 1) a linear SCM with Normal distributions for each variable, used as a baseline; 2) the Distributional Causal Node 20 architecture, where every node is modeled after probability distribution family with a feed-forward network for the computation of its parameters (DCN); and 3) DCGs powered with its most flexible implementation for continuous nodes, based on Normalizing Flows. Finally, in order test the alternative approach of modeling SCMs not node-wise, but the graph as whole, could use Variational Causal Autoencoder (VACA) [26] or Causal Normalizing Flows (CNF) [28]. However, as stated by the authors of CNF based on their experiments, "VACA shows poor performance, and is considerably slower due to the complexity of GNNs". For this reason, we opt for CNFs as a representative of this alternative approach for SCM modeling.
Regarding the definition of the synthetic DGP, we employ set of non-linear functions along with exogenous samples from diverse continuous r.v.s for the generation of new samples. Let x²() be the Chi-squared distribution with & degrees of freedom, B(a,,3) the Beta distribution, N N o)) the Normal distribution, and Exponential(A) the Exponential distribution. We sample from each latent variable first and then apply the functions in F in topological order:
u ~ x2 = 10);
82 ~ B(a = 5);
2 + Ezi
Ex [N 0, 0.1);
I - |=(u - 5) + +exli
84,1 Exponential(A 1);
a t- + +
(20)
EA, 5 NN( =, 0,0 0.1);
b+ 5sin(a) 10 teB
En 6n~ ~N[N = 0, =));
e log(1 + +12++ +
EC ~ (N = 0, = -0.5);
y log = + (1) +c+
EY NNp= 0, 0.5);
Note that we have diverse continuous variables: some non-negative, some restricted to (0, 1), some with unrestricted support. For the DCN implementation, where we need to assume the r.v.'s probability distribution family, we will employ Exponential, Beta and Normal distributions respectively. Each set of parameters Ox can be computed with shared feed-forward network using Graphical Conditioner [3] For the DCG implementation with Normalizing Flows, we will use Normal Distribution as its base noise (Ex) and the following flow structure (from X to Ex):
Affine layer, f(x = or + with learnable parameters.
3 blocks of:
Rational- Qaaarri--Quadratic Spline Flow 40 defined the interval [-5,5]. with K 8 bins. Affine layer.
Additionally, depending on the support of the r.v. to be modelled, we prepend another layer to transform the original domain into I before the application of the first Affine layer. In particular, for flows defined in (0. 1), we use a Logit transformation f(r) := log 1-2 and for non non-negat flows, inverse Softplus layer ((x) == log(e" 1) (using the identity after a certain threshold for numerical stability). All parameters not set as hyperparameters are computed by an external trainable
Conditioner that takes the node's 's parents as input and outputs their value.
25

---

0.150
Test log seep--ikkel irood (1)
-5
SHAP Estimation Loss (4)
0.125
0.100
0.075
-7
0.050
0.025
0.000
CNF
marginal
Estimator
Estimator
marginal
linear
DCN
DCG
CNF
ground-trute
0.5
Feature Im Importance
0.4
0.3
0.2
0.1
Ú
Feature
Figure 7: Markovian case. Box-plots computed over 30 realizations of the dataset. (a) Distribution adjustment score, log-likelihood (bigger better). (b) SHAP estimation loss, L (lower is better). (c) Feature Importance (the closer to ground-truth, the better). Dashed horizontal line represents uniform importance
Regarding the Conditioner network's 's architecture, is a standard feed-forward network with ELU activations [41), 2 hidden layers of dimension 32, and standardizer layer at the beginning defined with the training dataset. This is used for the DCN and DCG SCMs. Regarding the CNF architecture, it uses a Softclip-constrained NSF-based architecture similar to ours, but with 4 stacked Spline layers (the diameter of the graph) and a MADE Conditioner to learn to model all variables at once. this case, the conditioner uses 3 hidden layers with dimension 32 and ELU as its activation.
In terms of training, we the AdamW optimizer [42] with Early Stopping (after 100 epochs with no improvement), using learning rate 10-3 weight decay 10-2 and batch size 100. Regarding SHAP estimation, since we only have 5 variables, samples from each SCM for the Monte Carlo estimators of vS).
the exact permutation method, taking 1,000
Finally, see fig. for bigger representation of the plots in the Markovian case.
E.1.2 Semi-Markovian case
We also test our approach on the Maii-Markovian case, where the latent confounder U(x.8) is not observed. As stated in section 5.1 CNF cannot be applied without the causal sufficiency assumption, so we will proceed with the remaining SCMs.
Figure Souure&shore shows the same three plots as in the Markovian case, with similar results. The linear SCM cannot properly estimate P(V), which results in worse SHAP loss. DCNs achieve similar results to DCGs, but DCGs exhibit the best distribution adjustment and estimation performance. Finally, marginal SHAP results in different estimations than do-SHAP, something that patently clear in the FI plot, where Z and C's contribution are overestimated while A and B are underestimated. Note that we obtain the same explanations in the Markovian case even though we cannot measure the latent confounder nor know its distribution.
E.2 FRA experiments
We will now describe additional tests for FRA.
26

---

SHAP Estimation Loss (L)
Test log -ee--iikkl frood (T)
-4.5-
-5.0
-5.
0.05
0.00
marginal
Estimator
Estimator
marginal
linear
DCN
DCG
ground-truth
0.5
Feature Importance
0.4
0.3
0.2
0.1
0.0
A Feature
Figure 8: Semi-Markovian
Box-plots computed over 30 realizations of the dataset. (a)
Distribution adjustment score, log-likelihool (bigger is better). (b) SHAP estimation loss, & (lower is better). (c) Feature Importance (the closer to ground-truth, the better). Dashed horizontal line represents uniform importance (x))
15
3.5
Eecousan Unne M1.2122
9
2.0
1.5
1.0
10
20
9.0
10
14
(chverbable)
K abres)
K(Avarables)
Figure FRA experiments. (a) shows the errors bars (at 2-sigma over 270 replications) for the average normalized execution times of FR1 (sets) and FR2 (numerical) per number of nodes (K). (b) shows the error bars (at 2-sigma over 30 replications) of the ratio between FRI time and FR2 time, split by edge probability (p), over the number of nodes K. If above 1, FR2 is faster. (c) shows the error bars (at 2-sigma over 30 replications) for the mean of quotients between the total time executing FRA (+permutations) and for estimating all sampled (S))
Figure shows comparisons between both versions of the FRA algorithm: FRI (using sets, algo- rithm 2 and FR2 (using integers, algorithm 3). Note that FR2 is consistently and significantly faster that FRI, and less memory-intensive since the Fr cache needs only store numerical encodings of sets, instead of sets of integers. However, depending edges (p = 0.9), FRI can be faster than FR2, as shown by fig. 9 (b). In any case, FRA negligible time-wise w.r.f. the time needed for the estimation of v(S), we will see next.
graph topology. particularly with many
In the second experiment, as described in section 5.2
we employed synthetic DGP consisting of linear function. We generate 1,000 i. d. samples from this DGP to create training, validation and test sets with ratios 1:1:1. We train a linear DCG with Normal DCN nodes, which fitting for this dataset and deliberately lightweight, so as to show the improvements from the application of FRA even the case where the model particularly fast; FRA can only improve time-gains with more expressive and expensive models. We learning rate of 10 weight decay of 10- batch
27

---

SM
HD
BP
CH
CC
FR
VG
PA
BM
Figure 10: Diabetes Causal Graph, with variables Physical Activity (PA), Fruit (FR), Veggies (VG), Smoker (SM), BMI (BM), High Cholesterol (CH), High Blood Pressure (BP), Heart Disease or Attack (HD), Stroke (ST), Chol. Check (CC). Boldface letters denote Pay, with Y, Diabetes, the target variable, not represented for clarity. We can skip modeling any non non-ancestors Y (theorem 4.2) SM, ST, HD and CC.
size of 100, early stopping with patience of 10 epochs and AdamW 42 as the optimizer. For each estimation, we generate 100 samples from the SCM.
For this experiment, kept track of do-SHAP execution time as well the time for the computation of v(S) specifically; this allows us, by subtraction, to compute the time needed for FRA and generating the permutations π from where the sets S emerge. If we compare these two quantities, dividing the v execution time by the FRA+permutation of magnitude faster than v; this means that, negligible cost, significant ratio, specifically the number of FR coalitions.
time, as shown in fig. [ (c), we see that FRA is orders
speed up do-SHAP by
F Applications
We now showcase do-SHAP explanations two real-worke datasets as illustrative examples.
F1
Diabetes dataset
Here we discuss the Diabetes Health Indicators Dataset lifestyle survey information along with their diagnosis (or not) of diabetes, for the year 2015. Note that the dataset is biased, with 14% of individuals having diabetes. We start with preprocessed version of the original questionnaire dataset, from which 21 features and the target variable are extracted. We select 10 out of 21 features provide a more easily understandable problem for the reader.
43
containing healthcare statistics and
We construct causal graph (see fig. 10 relating these variables and train an SCM model them, with which we finally compute their do-Shapley values. We design the graph using common sense. Note that any causal analysis depends its graph being sound, but once a better graph is found; for this reason, please take this as an illustrative example, since its conclusions regarding healthcare as before, except that every variable other than BMI is binary, so they are modelled with Bernoulli DCNs.
be replicated at any time
necessarily rigorous. We train DCG with the same setup
Our objective here is not to explain ML model, but the data itself; particularly, how each variable affects the likelihood of diabetes. However, the effect of the noise is not as clear in classifier as in regressor, since Φg = E E pay] = y - P(Y pay ); for an application theorem 4.9
please refer to section F2
compute do-SHAP for the first 1,000 test set entries, and measure See fig. ITa) a): HighBP, HighChol and BMI appear to be the most important variables, with Physical Activity, and fruit and vegetable intake having less pronounced role. also important to consider the dependency between feature values and do-SHAL values; the beeswarm plot in fig. II c), which shows
28

---

High
Highthd
m--Shaply Vilue
0.1
314
PrysActivity
0.0
Fruits
-01
Veggies
0.9
0.1
02
0.3
60
Fexture Importance
High
High
Chah
BMI
Fecture
PhysActivity
Fruits
Veggies
LOW
SHAP value (Impact on model outputi
Figure 11: Diabetes Dataset. a) do-SHAP Feature Importance. Dashed vertical line represents uniform importance (x)- b) Scatterplot between BMI value and do-SVs. c) do-SHAP beeswarm plot, relating do-SVs and feature values.
clear-cut effects in do-SV sign and magnitude for HighBP and HighChol, with more nuanced relationship between BMI (continuous) and do-SVs, which we plot in fig. [T);; BMI 30 (typically categorized as obese) seems be the cutting point after which higher BMI values increase the chances of diabetes up to 20%, while lower values decrease that likelihood up to 10%.
F.2 Bike Rental dataset
We now study the Bike Rental Dataset [44] describing the number of rentals in bike sharing service Washington D.C., between 2011 to 2012 (both included), measured on an hourly basis, along with weather data and whether that day the data itself; particularly, how each variable affects the number of rented bikes.
working day. Again, objective in this case is to explain
We design a causal graph, depicted in fig. 12 (a). As stated before, please do not take the conclusions from this experiment as is, but merely as an illustrative example. We train DCG with the same architecture and training parameters as the synthetic experiment, except that hour can be modeled with a uniform distribution on the integer interval [0, 23]. We train our DCG and compute the operating
do-Shapley values for the test set entries. However, since this case, we also want to measure the effect the noise, employing theorem
inaccessible DGP in 4.9 4.9
We measure FI, represented in fig. 12 (b). Hour seems to be the major cause of the target variable, as is to be expected, followed by noise (given by the inherent variance of the target conditioned on its parents) and temperature, which also conditions on the likelihood of users renting bikes. Other variables also have an impact, with only wind speed and weather (categorical, with three levels) having less pronounced effect.
The relationship between feature values and do-SVs is more informative; we use scatter plots in order to study how each value affects the outcome; see fig. [3] Hour presents positive attribution during daytime from 8AM 8PM, with night-time time having negative attribution; temperature effect is mainly negative, with certain temperatures being less inviting for cycling (below 15ºC and above 35%C); in the same way, humidity only affects past 80%, as well wind speed, past 15 km/h.
G Comparison between do-SVs and non-causal approaches
In this appendix, we expand on the discussion about why do-SHAP results in more reliable expla- nations than non-casual alternatives (marginal-SHAPP and conditional-SHAPp, We follow on the example presented in section here replicated in fig. 4 for reader's convenience.

---

WE
WO
humi dity
SE
HU
WI
working day
wind_spen
weather
TE K
HO
Feature importance
Figure 12: Bike Rental Dataset. a) Causal Graph with nodes Season (SE), Weather (WE), Humidity (HU), Temperature (TE), Working day (WO), Wind speed (WT), Hour (HO). Boldface letters denote Pay, with target Y, Rentals, not represented for clarity. b) Feature Importance (FI) for each variable. Dashed vertical line represents uniform importance
20
100
-30
-100
-120
Resperation PCC
Hurddty (5)
Wind speed Omchh)
Figure 13: Bike Rental, continuous features' values against their SHAP values. Errors bars at 2 2-sigma.
Firstly, let us reason about how each method will behave in this particular Data Generating Process (DGP). In magP. consider for example v({ [E)). where we would marginalize A and S regardless of the assigned value E, thereby ignoring the impact that education level may have on the seniority level of the employee (their standing the company), and producing out-of-distribunt configurations (a, e, s). Alternatively, with e).
E
Y
Figure 14: Salary causal graph:
conditional SHAP, we would operate with P(A, S thereby including this dependency between E and S, but also taking whichever value of A would have generated this specific value e, which introduces in turn anti-causal effect (F. ->>))
Age (A), Education (E), Seniority (S) and Salary (Y).
Since both approaches ignore the causal structure, they incorporate non-causal effects that fail to reflect the real DGP, and would therefore lead to unreliable explanations. In contrast, do-SHAP does take into account this causal effect, by using the intervention do e). therefore affecting (E S) while not affecting A (E <- A); not only that, but A's effect de-confounded by blocking back-door path + A + S + Y. See table [ depiction of which coalitions result the same value as do-SHAP's for marginal-Ste -SAA and Annditional-HHAP
Ø
[A]
{E)
(S)
(A
(A
[E.S]
(A,
marg
4
4
conditional-HHAP
Table 1: When does do- SH-SS v equal Barginal-SHAP or conditional-SHH -SAnpss v/?
Secondly, we will illustrate this reasoning with an example SCM corresponding to the same graph; eq. (1). Let consider Bernoulli r.v.S A, E, S, Y with parameters pA, pE,Ps, py, respectively. These parameters are computed following the aforementioned causal graph, with the following structural equations, which generate samples (a, e, s, through Bernoulli sampling.
PA 0.25
PE 0.5a 0.25
(21)
ps 0.25a + 0.5e + 0.1
Py 0.5e 0.3s + 0.1
30

---

method
marg SHAP
Shapley Value
0.2
cond
do-SHAP
-0.2
-0.4
Shapley Value
0.2
-0.2
+
0.4
Shapley Value
0.0
-02
-0.4
+
0.4
Shapley Value
0.0
-044
Figure 15: Salary example, comparison between marginal-SHAP, conditional-SHAP and do-SHAP for each input variable (A, E, S) on every factual combination (title).
We evaluate marginal- conditional-SHAR. and do-SHAP on this DGP. We run the following procedure 30 times to obtain eπrr bars. For each replication, we generate 1, 0,00 background samples (used for marginalization
the first two methods) and test samples (one for every configuration (a,e, e, s)) to explain. We estimate marginal-
on these test set samples by approximating Umarg (S) Ex) [P(Y) Xs. Xs=)] with the i.i.d. background samples. Similarly, we estimate Conditional-SVs by approximating Moond (S) EE xs) [P(Y] Xs, xs=)], averaging over those compute do-SVs by estimating v(S) Ex [P(Y Xs. X)=)]. sampling and intervening on the DGP directly with interventions do(S = Xs). Note that for this particular experiment, we do have access to the true structural equation Y fy(a, s) and employ it in estimations instead of training model to approximate it. We split by each test sample (every factual combination (a, e, s)) and plot the corresponding estimations with boxplots in fig. 15
x' background samples that fulfill X Xs. Finally,
We use the results of this experiment to exemplify how marginal-SHAP and conditional-SIHI fail to address the behavior of the underlying DGP, hence providing explanations whose insights are not reliably applicable to the real world. Meanwhile, do-SHAP does take into account corresponding data structure, and overcomes these weaknesses.
31

---

On the one hand, marginal-SHAP sets ΦΛ = 0 for all possible configurations, since A does not uppear in Y's structural equation; as such, cannot have an effect on within marginal-SHAn interventions on A have no impact on E or S (even if they do in the real DGP). As for Φ5. it disregards
since
the effect of F on S while also not de-confounding the back-door effect t A + S - Y. resulting +) and (a = + -),
in significant differences with do-SHAP, particularly on (a given that the correlation between the two is ignored with marginal -HHPPss intervention. Finally, Øs is closer to an intervention with do-SHAP since S does not propagate its intervention on any other variable before Y; however, it is unable to control for the back-door effects (S + E - or S < A + E + Y), which explains the difference with do-SHAP.
On the other hand, Anditional-SHAA results in more similar attributions to do-SHAP, but still significantly different. This similarity can be explained by the fact that half the coalitions result in the same v-output as do-SHAP in this particular graph, as made explicit in table However, even the conditional may affect descendants of variable as do-intervention does, it can also introduce anti-causal effects and cannot block back-door paths, which explains the differences with do-SHAP.
In summary, both marginal-SHAA SHAP and conditional-SHAP misrepresent the underlying DGP, given that they ignore its underlying causal structure. This is the reason why do-SHAP results in more reliable explanations than the alternatives.
H do-SHAP estimation example
This section is devoted to explaining how to apply EA estima- tion in practice for do-SHAP. This is meant an illustrative written explanation; for a code example, please refer to the experiments code, submitted with the supplementary material.
We will focus on the graph introduced in section 5. here replicated in fig. [6] for reader's convenience. We will employ the semi-Markovian version of this example (meaning, there is a latent confounder U(x.B) (x between X and B). We will assume the (measured) data distribution is composed of unconstrained continuous r.v.,, with an unknown prior distribution for B). but with a known causal graph G.
B
Z
X
Figure 16:
Synthetic
semi-
Markovian graph.
In terms of notation, let Pa'x = Pax Lil(x--) be the concate- nation of the parents of certain node X E X and any latent confounders pointing to it. For example, in our current graph, Pd'g (A,).
H.1 do-SHAP identifiability
Before starting, we need to confirm that do-SVs are indeed identifiable this particular graph; otherwise, two SCMs trained on the same distribution may output different do-SV estimations, rendering them useless.
If there was a graphical criterion that fit the structure of our graph G, it could be used at this step; for instance, if there are no latent confounders in graph, do-SHAP is trivially identifiable. Since this is not the case, we need to test it using the ID algorithm 229 and Python, respectively.
See 31 or 32 for implementations in R
To guarantee SHAP identifiability, we need to test it for every coalition S. In other words, ensure the ID algorithm on
that (S) E [Y] do(S = s)] is identifiable VS C X. Therefore, each of the 25 = 32 queries v(S); if all are identifiable, so are the do-SVs. Note that this test is independent to the data distribution, as it only requires the corresponding graph structure G.
Given that this is a small graph, with only 5 X variables, amounting to 32 coalitions, is feasible to test for identifiability before starting the process. In the general case, with potentially bigger graphs and X| coalitions to test, this becomes infeasible or very expensive, and it is therefore recommended to test for identifiability during do-SV estimation; this lets us skip the identifiability check for any coalitions not appearing during the sampling process, well as leveraging the FRA-cach to skip further identifiability checks on non-irreducible coalitions. In the following, we will indicate where in the do-SHooS SHAP process this check should be performed.
32

---

H.2 SCM implementation
Given that G contains a latent confounder, we choose DCGs 13 as the SCM architecture, and for generality (to adjust to more complex data distributions) employ Normalizing Causal Flows (NCFs) as the node architecture. Refer to section E...I for a possible implementation of NCFs (without domain adjustment, given that our variables are unconstrained real-valued r.v.s). These NCFs provide a general function X = fx (Exx x (P)')) (with Ex the corresponding exogenous noise signal for node X), which is used to sample new values 2: PPX Pa'x) well as to compute the log-likelihood of these values given its parents: log P(x: pppa ). The choice of prior distribution for the exogenous signal Ex and for the latent confounder (XX,B) is irrelevant, as long as the desired queries to estimate are identifiable (which has been previously tested) and the particular choice of prior guarantees enough modeling capacity represent the data distribution P(X). In this particular case, we choose a (0, 1) for both priors.
Regarding the function x (Pax)), it returns the appropriate function parameters 9x for each node's function fx- These parameters define the shape the distribution P(X Pa'x) and as such depend on the values pa'x of Pa'x. After that, fx only depends on the parameters 0x and the exogenous noise Ex- P. This function O (-) could be modeled with a simple Multilayer Perceptron (MLP), one for each node, but this would inevitably result in overfitting for larger graphs. Instead, we employ the Graphical Conditioner presented [13, a single MLP network that takes every node X and latent confounders U as the input and returns all parameters {0x X E X} as the output. By using a particular training and inference strategy, the Graphical Conditioner allows to compute each of these functions Ox independently through a single network, thereby reducing training time and overfitting risk.
H.3
SCM training
DCGs are trained with Maximum Likelihood Estimation, so we will define, for particular sample X P. the Negative Log- -ikeeliiidood (NLL) loss minimize as the training objective. Given the graph structure G of the data distribution to model, we can derive two formulas, one for the Markovian case (no latent confounders).
== log P = Σ log P(x pax),
(22)
XEX
the other for the semi-Markovian case (with latent confounders),
C = log P(x) log 1uu
exp Σ
log P(a po'x)
(23)
XEX
In our example, we need to employ eq. (3 given that u [U * Ø. This latter expectation can be estimated by generating M i. i. samples from P(2) and averaging the results of the expec- tation's 's contents. The terms log P(x pa'x) can be estimated by the predefined node architectures (NCF in our example) using simple function. Finally, the Monte Carlo average can be computed using the log-sum-exp trick for numerical stability.
By running an optimization algorithm (e.g., AdamW (42) on the average of these NLL losses for random maii-e of samples, we can learn the data distribution P(X) with our SCM, from which we can now estimate (identifiable) SV-SVs.
H.4 do-SHAP estimation
Let us describe how estimate do-SVs with our approach.
Firstly, we need to run the SHAP formula. this case, with only variables, we could employ the exact formula directly, using eq. (1). Instead, we exemplify the more general approach, compatible with larger graphs, with the permutations formula in eq. ( which we approximate as described in section 3.4 here re-established for reader's convenience:
(X) Ex--((())) [x(Xx, -x (X,xx))
(24)
where the expectation over permutations и estimated by generating M i.i.d. permutations uniformly, and the internal (x(.) terms are estimated as described in the following. However, before we run the
33

---

es-immmmttion procedure, we employ an FRA-cache to compute the Preeuui- subsets S' of X--x and Xx, x. hence reducing the number of v/ commputationns required.
Let us now discuss FRA. Consider the permutation x = (A, B, 2, C) We need to attempt to reduce sets X x {A, B, Z, } and Xx,x (4, B, 2). By running the FRA algorithm (see algorithm for a simpler definition with sets), we can see that both sets can be reduced by removing A, since B acts as frontier between A and Y. Hence, we compute both values (x 2, )) and (B 2 and store their results in a cache for later look-up. If, on another permutation π we encounter coalitions with irreducible sets that have been computed before, we can retrieve the results from the cache directly, thereby reducing the number of required computations.
Now, if we have not tested identifiability at the beginning of the process, must confirm identi- fiability of all encountered queries v/() before proceeding with their estimation, but only for the corresponding irreducible sets S'. Whether one of such queries is identifiable not is stored in separate cache to avoid running the ID algorithm again once another coalition results in the same irreducible set. Finally, if any such query is deemed unidentifiable, the process must halt with an error, meaning that do-SVs cannot be estimated in this particular graph.
Then, let us describe how to estimate an arbitrary coalition value, (S(,,, which is accomplished with a general sampling procedure. In order to estimate this query, we need to generate M i.i.d d. samples
x(0) P(X do(S = s)). We start by generating values e P(E) and u ~ (24) from their respective prior distributions. Afterwards, we go node by node X E X following any topological
order of the graph, using the corresponding sampling functions xx(() fx(Ex (8) Ox (pa'x ()) unless the variable X is in the intervened coalition S, which case (1()) becomes the corresponding value from the to to-be-explained sample x. After we have sampled from every variable in the graph,
we have joint sample x(6) ~ P(X do(S = s)). We pass each of these samples through our model (-) to compute the corresponding y (1) values, which will finally be averaged for the final estimation of (S).
As note, while smaller coalitions are generally more expensive to evaluate than larger ones, since every node not in S requires to use its sampling mechanism to generate its values, this extra cost is negligible in comparison to evaluating extra coalitions that reduce to the same irreducible subset.
Finally, we can add further optimizations to this procedure. Consider the tuple (x(T)) (x=))) with na the set of variables up to index h: on π (inclusive) (note that 7.00 = Ø). When computing SVs, instead of using the formula directly, we sample permutations compute the corresponding tuples (Tr) and, from there, their diff-tuple Ar, (TT = (vx(T..))
Note that each of these (T)) terms is the difference in the SHAP formula for variable X := Tu. so we can update our do-SV estimations (ox)xex simultancously. which accelerates this computation by reducing the number of FRA-cache accesses and employing tensor operations. Along with this, other estimation approaches, such as antithetic sampling for these permutations, can used to obtain better estimator efficiency, further reducing the number of required permutations.
H.S Final considerations
Putting all of this together amounts seemingly complex method to estimate feature attribution: from finding the assumed Causal Graph G, defining the appropriate SCM architecture, training such a model, estimating the values, running FRA to avoid computations, to finally arriving at the do-SV estimations. However, given training and estimation procedures ready for use. EA do-SHAP made practical. For this reason. we advocate for an open-source library bringing together different SCM architectures for easier switching between approaches, facilitating the general applicability of EA methods, and as result, of do-SHAP explanations.
SCM architectures with appropriate
Impact statement
This work introduces a tool for estimating do-SVs on any black-box system. As an explainability tool, it offers positive societal impact by enabling deeper understanding of complex Al systems, benefiting both scientific progress and business decision-making. Crucially, it addresses ethical concerns about AI trustworthiness by supporting the right explanation in human human-facing facing decision
34

---

systems, facilitating debugging. and enhancing transparency and accountability. Additionally, by enabling audits of opaque systems, the tool promotes responsible AI regulation, protecting human rights against the risks of powerful but opaque Al systems.
One potential negative application of these techniques is in terms of willingly unwillingly obfus- cating harmful behavior in black-box models. Given the complexity of these techniques and the subsequent analysis required derive conclusions from its outputs, explainability techniques could be used to provide a superficial layer of supervision and result in misleading conclusions about the behavior of the system. Great care with respect to the assumptions and outputs of these tools must be taken in their application.
35

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: in the second half of the abstract and the last paragraph of the introduction, we explain the contributions of this paper, which correspond the claims and demonstrations that can be found in the rest of the work. None of the contributions contains a limitation significant enough warrant mention so early in the paper and without the proper context; an extensive discussion on the limitations of our approach can be found in section G
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: all assumptions are highlighted in their respective context with bold-face Assumption paragraph title. All limitations are clearly listed and discussed in section 6
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proof's
36

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: we have paid close attention to the correctness of all the steps of the various proofs that the paper presents for its claims. The assumptions are also clearly stated.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: the main steps to reproduce all the experiments are stated in the experimental section of the paper and the appendices. Additionally, code included in the supplementary material with proper guidelines to execute it.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
37

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: data and code are submitted together with the paper to ensure reproducibility of the results. For synthetic data, we include the generation code and formulas. Any real-world datasets employed in this work are publicly-available and properly referenced.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurIPS code and data submission guidelines (https
//iips.cc/publii. wttpcc/pppppgppu.eeeeeeeeo.opptp /otee/ddeeeeooeeeumiiieeeee sooiiiiiiii for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: every one of these details (within reason) is detailed in the appendix. Addition- ally, we submit the code in the supplementary material for further details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: we have included error bars at 2-sigma, specifyyng the number of replications and the factors of variability.
Guidelines:
The answer NA means that the paper does not include experiments.
38

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: these experiments were carried out in personal computers. Since this is not deterrent for the reproducibility of our results, mention briefly at the beginning of appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported didn't 'tttt make it into the paper).
paper (e.g., preliminary or failed experiments that NeurlPS Code of Ethics stttps://neurre http:ppp.....pp..ccccccccccieaa.
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the
Answer: [Yes]
Justification: we have read the NeurIPS Code of Ethics carefully and can ensure that the research carried out for this paper conforms with the ethical code in every aspect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
39

---

Justification: we have included an Impact Statement in appendix due to space restrictions. Nevertheless, this work does not have any direct negative impact on society, which is why did not feel it necessary to include it in the main paper.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: we believe that our paper does not pose important risks such as those men- tioned.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: any public datasets are properly cited in the text. Every asset has LICENSE. txt file attached to Licenses are respected.
Guidelines:
The answer NA means that the paper does not existing assets.
40

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the datasets..paerssttt paperswi thcode. com/datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: this work does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: paper does not involve studies with subjects.
41

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: no significant usage of LLMs merits mention requested.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our L.LM policy for what should or should not be described.
42


Reviews:
[{"review_id": "NnxD8o0cDn", "reviewer": "Reviewer_Mmbz", "summary": "The authors claim the following contributions:\n1. The work constructs an neural causal model-style approach to estimate do-Shapley-values, assuming identifiability.\n2. The work also limits the exponential number of terms computed requusing their Frontier-Reduction Algorithm (FRA) to generate irreducible subsets.", "questions": "1. Is there a performance or runtime improvement over (Jung et al., 2022)'s estimand based approach when not using FRA?\n2. Is it correct to say that FRA does not yield runtime improvements when all variables X affect Y directly (e.g., when $|Pa_Y| = |\\mathbf X|$ or $p = 1$)?\n3. How significant is the improvement with respect to the proportion of variables that do affect Y directly (e.g., how does the improvement change as $p$ goes to 1, given it is currently set to 0.25)?\n4. Does the FRA algorithm work with semi-Markovian causal diagrams?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Originality: The idea of training a proxy model to estimate do-Shapley values specifically is only marginally novel, given that it comes from the neural causal model framework. The concept of the frontier reducibility algorithm seems logical, stemming from d-separation results, and it primarily seems to be an algorithm for empirically speeding up do-SV estimation.\n\nSignificance & quality: The contribution seems primarily empirical and are claims are the made on the basis of experiments on synthetic data. There does not seem to be a performance or runtime comparison between estimand-based approaches to do-Shapley estimation and the described neural causal model-style approach, so it is challenging to see an improvement from baseline. In cases where not all variables have direct effects on Y, FRA is shown to boost estimation efficiency.\n\nClarity: The work is clearly written.", "was_revised": true, "final_justification": "The authors highlighted the size of the empirical performance gain as proportional to $p$, the proportion of variables which directly cause the outcome.", "rebuttal": "Thank you for your review. We will answer your concerns section by section.\n\n# Strengths and Weaknesses\n\nWhile the neural causal model framework (i.e., the EA framework) is not a novel contribution, its application to the do-SHAP estimation problem is, in our opinion, significant, given that without it, we would need to define and follow separate estimands for each of the $\\nu(S)$ queries, which renders do-SHAP impractical in settings with a moderate number of nodes (2^K queries/estimands in a graph with K nodes). Let us remark that it is in the impracticality of the EB approach for this setting that ours is “faster”, since the process can be automatized through general estimation procedures, as described in [13], only requiring human input once during the DCG definition/training phase.\n\nWhile this contribution may be seen as incremental, we believe it important to be brought forth to the community given that the authors of do-SHAP did not acknowledge the EB approach as a possibility for estimating do-SVs, which limited its applicability: “[we] are not aware of any general causal effect estimators suitable for estimating the expression\" [12]. We do propose such an estimator, and here lies this part of the contribution.\n\nFinally, regarding the request for runtime comparisons between EB and EA approaches, these do not make sense; as stated, EB’s main drawback is in its ad-hoc nature, depending on the causal graph and particular query to estimate, whereas EA approaches are general for any graph and query (provided the given query is identifiable, for which there are also algorithms to automate this check) and therefore can be automatized. Hence, we could not possibly compare their runtime. In other words, it is not in runtime that this contribution lies, but in making it feasible/practical to estimate do-SVs on graphs with larger number of nodes (K).\n\nThe other (and probably more significant) part of our contribution lies on the definition of the FRA algorithm, which significantly speeds up do-SV estimation. Finally, we also derive Theorem 4.8, which lets us measure the do-SV of the target’s exogenous noise at no computational cost under certain assumptions.\n\n# # Questions\n\n- Q1. The FRA contribution is independent to the EB/EA choice; FRA could be used with Jung’s EB approach and would inevitably result in an improvement because it can only reduce the number of coalitions to compute at a negligible cost (see Figure 4b). On the other hand, as stated before, the improvement of the EA approach over the EB approach is not in runtime, but in practicality for larger graphs when using the automatized EA approach.\n- Q2. Yes, this is addressed in Remark 4.6, Footnote 7 and Section 6 (line 352). There we argue that, even though FRA cannot bring any improvement over graphs where *all* proper nodes are parents of the target Y (i.e., no frontiers exist), this kind of graph is unrealistic and, in the case of ML models, unadvisable, since it could lead to spurious correlations, anti-causal effects, overfitting or adversarial vulnerability (see line 358). Hence why we believe this limitation is not of practical importance in general settings.\n- Q3. For the experiment in Figure 4b/c, we set $p=0.25$ instead of replicating it for several values of p due to the costly nature of the experiment. However, we did measure the impact of p indirectly through Figure 4a: there, for several values of p, we can see the proportion of coalitions that need to be evaluated after FRA, which tends towards p. In other words, we can expect a reduction ratio of p thanks to FRA (i.e., 50% total time w.r.t. baseline do-SHAP for p=0.5). I hope this answers your question.\n- Q4. Yes, FRA works irrespective of whether the underlying queries are identifiable or not, because any coalition $S$ that can be reduced to $S’$ entails that their respective queries are equal $\\nu(S) = \\nu(S’)$ on distributions P(V) Markov-compatible to the graph, be it semi-Markovian or not. See the proofs on Appendix D.2.\n\nI hope we have addressed your questions sufficiently; let us know if there are any more concerns. Thank you for your review."}, {"review_id": "dBAPrDlrkb", "reviewer": "Reviewer_oZ6x", "summary": "The Shapley value is a well-known concept from game theory. We are given a set of players X and a valuation function v which assigns each subset S (\"coalition\") of X a value v(S). The Shapley value of a variable P is the average value that adds P to every coalition S, that is, v(S \\cup X) - v(S). \n\nThe Shapley-value is now used to explain the influence of certain observed samples x on a target variable Y. To do so, the valuation function is set to E[Y | do(S = s)] for every subset S of X. Here s is the restriction of x to S. This assumes that there is an underlying SCM whose structure as a graph is known s.t. the expected values are all identifiable (using do-calculus). \n\nTo turn this into a practical scheme, the authors present an estimand-agnostic approach. To compute the Shapley value, one needs to estimate an exponential number of terms. The key is to just learn the distribution of a single SCM, then one can check whether v(S) is identifiable using do-calculus and then estimate v(S) using the learned distribution and SCM-calculation rules.\n\nThe authors present a way to calculate the do-Shapley value faster by the following observation. If X is an ancestor of Y and the coalition we want to estimate contains a blocking set between X and Y, then adding X to the coalition does not change the value of the coalition. This allows one to do a faster than brute-force computation, the authors design a nice frontier reduction algorithm to perform this computation fast.\n\nThe author also provide an implementation and do extensive testing.", "questions": "- Are there any known formal hardness results for computing Shapley values in this setting? Shapley value per se is an exponential sum, but depending on the valuation function, it can be done faster. \n- Can one get estimates in Appendix B when also the underlying SCM is taken into account?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I think this is a nice paper. I combines nice theoretical insights with a practical implementation. The proofs presented in Appendix D are very detailed and well-written.  I am mainly working on ML theory, therefore I found it hard to evaluate the partical part. Therefore, my confidence is only 3. My reservations only stem from the fact that I am not able to confidently evaluate the practical part. \n\n\nComments:\n\n- line 91: The permutation only induces an ordering if S is ordered\n- line 152: SCM G -> graph G (?)\n- line 186: Assumption 4.1 needs to be reworded in my opinion\n- line 205: Should Y also not be in the blocking set\n- line 210: An irreducible frontier would be called minimal cut in graph theory\n- line 219: I find it easier to write that you you encode the set by its characteristic vector stored in an integer. Also the word $\\phi$-encodes is not defined.\n- line 223: That being said, I would present the set-version (in the appendix) of the algorithm as Algorithm 1. While of course the presented version runs faster, the set-version is much easier to understand.", "was_revised": true, "final_justification": "As I said before, I like the theoretical parts of the paper. However, since I working on the theoretical side of causality, I am not very confident in evaluating the practical aspects, even after rebuttal. Therefore, I maintain my score.", "rebuttal": "Thank you for your appreciative review. We will address your questions section by section:\n\n# **Strengths And Weaknesses**\n\nThank you for these Comments (C). We will include your suggested improvements in the camera-ready version.\n\n- C1. Do you mean $\\pi$ only induces an ordering if the elements are *unique*? That is true, we will clarify this part.\n- C2. Noted: “underlying SCM’s graph G”.\n- C3. We acknowledge the wording is quite dense, due to the limited paper size. Thank you for pointing this out, we will extend it briefly to make it more understandable in the camera-ready version.\n- C4. It is not necessary, because $\\mathbf{X}$ does not include Y (line 203), so the frontier $\\mathbf{S} \\subseteq \\mathbf{X}$ cannot include Y.\n- C5. Thank you for pointing this out, we prefer to preserve the frontier terminology in this case to make it more easily understandable.\n- C6. The $\\phi$-encode terminology (i.e., a set $S$ is $\\phi$-encoded by an integer $s$ if $s=\\phi(S)$ with the injective encoding function $\\phi$) was meant for economy of notation in trying to shorten the paper. We will clarify it.\n- C7. That is a good point. We opted for the numerical version to show the final version of FRA in the main text, leaving the preceding version with sets for the appendix along with more detailed explanations about the two.\n\n# Questions\n\n- Q1. Not that we are aware of; the do-SHAP value has not seen much use in the community yet (possibly due to the estimand-based (EB) approach suggested by the authors, which limited its practicality) so there has not been much work on this aspect. Regardless, it is rarely the case where we compute the exact formula for SHAP, instead using the approximate method by sampling permutations. However, further work in this direction would surely be worthwhile for do-SHAP practicality.\n- Q2. We are not sure if we understand your question. The results in Appendix B are general for any kind of SHAP estimation with the cache strategy, to measure the impact of a (non-FRA) cache on the approximation algorithm for an arbitrary number of nodes $K$. This formula is applicable to SHAP as a whole, not specifically do-SHAP. If you meant what the impact of the FRA-cache would be knowing the underlying graph G, this depends on the topology of the graph and it is hard to give conclusive answers in general. However, we did include an experiment related to this point on Figure 4a, where we see the ratio of coalitions left to evaluate after running FRA. Does this answer your question?\n\nThank you again for your insightful review. Let us know if there are any more questions."}, {"review_id": "iAKIBAP5DW", "reviewer": "Reviewer_Da1T", "summary": "The manuscript proposes a practical method for computing do-Shapley values (do-SVs) — causal, interventional variants of Shapley value feature attributions — using an estimand-agnostic (EA) approach. The authors replace the original estimand-based (EB) procedure from prior work with an EA technique, which involves fitting a single structural causal model (SCM) to the data and using this proxy model to estimate any identifiable causal query. The paper introduces a novel Frontier-Reducibility Algorithm (FRA) that exploits graph structure to accelerate do-SV computation by identifying coalitions whose interventional effects can be safely skipped. Experiments on real and simulated data suggest that FRA can lead to major speedups in practice.", "questions": "Full disclosure: I have reviewed a previous version of this manuscript. I think it is much improved, and am generally disposed to recommend acceptance. I have just one major question/comment, and a few minor ones.\n\n**Major comment**\n\n*Clarifying tractability*: As noted above, there is some confusing language around the precise advantages conferred by the FRA approach. Experiments appear to confirm that this often speeds things up in practice, as we would expect. But the word \"efficient\" has a precise meaning in computer science – or maybe I'm just old fashioned :) – and it is clear from the discussion in Sect. 5 that the proposed method is not, in fact, a polytime algorithm. Now it may turn out to be polytime under some graph sparsity assumptions, and it would be very cool to spell this out in a bit more detail. But in lieu of such an analysis, I recommend striking all mention of \"efficient\" algorithms for arbitrary graphs, etc. \n\n\n**Minor comments/questions**\n\n-Since EA methods rely on a known, accurate causal graph, how sensitive are the estimated do-SVs to graph errors?\n\n-Linearity is usually included at a Shapley value axiom (Appx. A).", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n*Problem significance*: Extending Shapley values to causal settings is important for fair, trustworthy, and scientifically grounded explainability in ML. \n\n*Originality*: As far as I'm aware, the proposed EA framework for computing do-SVs is novel, contributing to both the explainability and causal inference literatures.\n\n*Technical contribution*: The FRA algorithm is a well-motivated and technically interesting technique to exploit graph structure for computational gains. Though somewhat similar to prior work (Luther et al., 2023), the similarities and differences are properly acknowledged in the manuscript.\n\n*Empirical validation*: The experiments convincingly demonstrate that the method works on synthetic and real-world data.\n\n*Clear exposition*: The paper is generally well-written, with clear descriptions of causal concepts, algorithm design, and experimental setup. I especially appreciated the thorough appendix.\n\n**Weaknesses**\n\n*Confusing and potentially misleading claims about tractability*: Throughout the paper, the authors repeatedly imply that their method renders do-Shapley value computation practical on arbitrarily complex graphs (e.g., abstract lines 4–7; intro, final paragraph; top of Sect 4; conclusion, first paragraph). However, the method does not in fact circumvent the fundamental #P-hardness of Shapley value computation, as acknowledged in Sect. 5.2. The FRA algorithm accelerates the process in some cases but does not resolve the exponential scaling in the number of features; more generally, the speedups it offers appear to be a function of graph sparsity, although the precise nature of this relationship is never spelled out in detail. This is a missed opportunity, as there has been a number of interesting works on the complexity of Shapley value computation in the last few years (Van den Broeck et al., 2022; Arenas et al., 2023; Marzouk et al., 2025). This tension between claimed practicality and residual intractability needs to be clarified.\n\n*Limited discussion of identifiability limitations*: The method assumes all required causal queries are identifiable from the causal graph, but the paper downplays the practical difficulty of ensuring this in complex or partially observed systems.\n\n*No quantitative comparison to baseline SHAP runtimes*: The paper lacks a direct empirical comparison of total runtime or computational cost between EB do-SHAP, conditional/marginal SHAP, and the proposed EA do-SHAP+FRA method. (Unless I'm misreading Fig. 4c?)\n\n**References**\n\n-https://www.jair.org/index.php/jair/article/view/13283/26815\n\n-https://jmlr.org/papers/v24/21-0389.html\n\n-https://arxiv.org/abs/2502.12295", "was_revised": true, "final_justification": "I said in my initial review that I would revise my score upward if the authors could address my comments. I am satisfied that they have done so (despite some lingering confusion about the appropriate use of the word \"efficient\"). I have therefore upped my score from 4 to 5 and wish the authors the best of luck.", "rebuttal": "Thank you for your review and for your transparency in disclosing having reviewed a previous version of this work before. We will address your concerns section by section.\n\n# Strengths and Weaknesses\n\n- “*Confusing and potentially misleading claims about tractability”:* while we acknowledge the importance of the tractability of Shapley values (be it marginal, conditional, or causal-interventional) we do not address this topic in our work nor do we claim to do so. We were very careful to avoid talking about tractability anywhere in this work so as not to misrepresent our contribution; this was a common concern of previous reviewers and we rectified accordingly.\n\nWhen we talk about practicality, we do not refer to the #P-#NP question, but on the fact that estimand-agnostic (EA) approaches make it possible to automatize do-SHAP estimation once the corresponding SCM is trained (assuming do-SV identifiability). This is in contrast with do-SHAP’s authors proposal with estimand-based (EB) approaches, which required defining separate estimands for each coalition and following those estimands to arrive at the final do-SV estimation. This ad-hoc approach is overcome with the EA approach and its general estimation procedures, which is what makes our approach “practical”, in the sense of being adaptable to general graphs with more nodes than what we can assume with an ad-hoc EB approach. \n\nOn the other hand, the FRA algorithm reduces the number of computations to be carried out throughout do-SV estimation, but this cannot resolve the exponential nature of exact do-SHAP, nor was it meant to. Instead, we propose its application to the approximation method with sampled permutations (section 3.4); here the FRA algorithm can really speed-up computation of do-SV estimation, as shown in the experiments.\n\nTo summarize, the issue of tractability falls out of scope of our contribution, but we agree on its importance and would be a worthwhile future direction. We will include this discussion in the camera-ready version to further clarify this point.\n- *“Limited discussion of identifiability limitations”:* we do acknowledge this topic, and state it as a central limitation of our work (as well as for any other estimation approach without further assumptions): assumption 4.5, footnote 5, and Appendix H.1. Please note that there are algorithms (as pointed out in line 127) to determine whether a certain query is identifiable (no matter how complex the graph is, or if it contains latent variables), which can be used to determine the identifiability of any coalition query $\\nu(S)$. The only remaining point is to develop a general criterion for do-SHAP identifiability based on graph structure, but so far we have not found one; we left it for future work (line 372).\n- “*No quantitative comparison to baseline SHAP runtimes”:* as discussed with reviewer #Mmbz (see the Strengths and Weaknesses section in our rebuttal), it is not possible to compare runtime between the default EB do-SHAP approach and our EA approach. EB’s drawback is in its ad-hoc nature that requires the manual definition of estimators based on estimands for every coalition, in contrast with the EA’s approach that defines a single SCM with automatic general procedures for any coalition query. As such, the improvement lies in the generality of our approach and the possibility to automatize the whole process (as implemented in our code) once the SCM is trained.\n\nAs for the marginal/conditional approaches, we do not believe it makes sense to compare time-wise given that they estimate completely different quantities (see Figure 3 for a comparison between marginal-SVs and do-SVs, and the paragraph on line 27, extended on Appendix G with an actual Data Generating Process).\n\n# Questions\n\n- Major comment: we understand your point. We argued our position in the previous section on tractability and will include a section in the camera-ready version for further clarification. As for the efficiency aspect, we meant efficiency as in reducing the resources needed to run the FRA algorithm: memory-wise, thanks to the integer encoding, and time-wise, as illustrated in Figure 4b and c, where FRA takes negligible time in comparison with the $\\nu(S)$ computation. We do not mean to imply that our do-SHAP estimator runs in polynomial time. After these points and the new planned section discussing this topic, do you believe it necessary to remove any mentions of efficiency?\n- Sensitivity to graph misspecification: this is an important point and we express it as a limitation of our work; see line 338 about the lack of doubly-robust guarantees. This lack is not specific to our approach though, but general for EA approaches, in contrast with EB alternatives; however, the impracticality of EB methods in this setting justifies the necessity for EA on do-SHAP, even without these guarantees. As for sensitivity studies, since our approach is general in the sense that any EA techniques could be applied (as long as they admit semi-Markovian graphs), we believe it would not make sense to run a sensitivity study on a specific class of EA model, as it would not generalize to other models. However, it is an important concern and we will point it out in the camera-ready version to signal novel directions for this work.\n- Linearity: that is true, thank you for pointing out this omission. We will include it in the appendix.\n\nWe hope these arguments will ease your concerns. Let us know if there are any further questions."}, {"review_id": "cDhaTbzgKa", "reviewer": "Reviewer_kUZY", "summary": "Do-Shapley values are expensive to estimate since they require evaluating exponentially many causal queries. The authors propose to make their estimation more feasible by employing two techniques in the context of do-Shapley values:\n1) They propose to employ \"estimand-agnostic (EA)\" causal inference which -- instead of fitting a different model for every query (EB) -- fits a Structural Causal Model (SCM) once (offline) which encodes all possible interventional distributions, and which can then be used to answer the causal queries.\n2) They propose to skip causal queries which are known to evaluate to zero since the intervention is causally independent of the target given the interventions that were already implemented before.\nFurthermore, the authors touch on discussing whether do-Shapley values should be based on counterfactual (rung 3) instead of interventional (rung 2) causal queries, and how they can be defined depending on whether the prediction or the underlying target is explained.\nIn Experiments, the authors evaluate how the choice of SCM (linear vs nonlinear) affects the quality of the effect estimation in a small synthetic setting, demonstrate that do-SHAP is different from marginal SHAP, and show that contribution 2) allows speeding up the estimation of do-SHAP in small synthetic settings.", "questions": "You claim that the approach makes the estimation of do-Shapley feasible for \"arbitrarily complex graphs\". Where do you substantiate this claim?\nYou continue by saying that you achieve this \"by using the estimand-agnostic approach\". Where do you show that EA is responsible for the claimed performance improvements?", "limitations": "Limitations and social impact are discussed appropriately.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n*Significance:* I am convinced that in practice many causal queries can be skipped given knowledge of the causal graph, and that this can lead to a significant speedup in estimation. As such, the main idea of the paper has practical significance.\n\n**Weaknesses**\n\n*Clarity:* The paper touches on several distinct problems, and I found it challenging to understand which of them the authors actually intend to tackle:\n\n- A Accurately estimating (many) causal queries from data. (EB vs EA)\n- B Identifying queries that are redundant. (FWR)\n- C Discussing whether do-SHAP are the \"right\" explanation method. (e.g. section 4.3)\n\nIn my view B is the main contribution, and I would recommend the authors to focus on clearly explaining that. \n\nIn particular, I was confused about the role of EB vs EA for the paper: The EA approach is prominently discussed in the introduction and conclusion, and the EA approach introduced in great length in the background. But in the main paper EA only receives very little attention (a bit at the beginning of 4.1) -- there is no methodological or empirical contribution.\n\nIn the main section of the paper, Section 4, there are three small subsections: 1 \"Do-Shapley value\", 2 \"Efficient estimation of the do-Shapley values\", 3 \"do-Shapley explanations\". 1 could be part of the background, and 3 should be left out or should be discussed together with 1. The really interesting part 2 is very dense and relevant details are missing (for example, what does it mean to $\\Phi$-encode nodes?)\n\n*Originality:* The paper employs existing ideas in a somewhat novel context. Luther et al (2023) already showed that Shapley approximation can be significantly accelerated using knowledge of the causal graph, the difference is that Luther et al make use of statistical independence to speed up conditional SHAP, while the reviewed paper uses causal independence to speed up do-SHAP.\nI don't see relevant contributions in the context of EA vs EB.\n\n*Quality:* The theory is sound. However, the proposed algorithm is quite complex given how simple the solution could be: Shapley values evaluate v(S u j) - v(S) for many sets S. Why not simply check causal independence of j and Y given S for every evaluation (very easy using a causal graph) and skip the evaluation if there is a causal independence in the spirit of Luther et al (2023)? What is the benefit of first identifying all possible irreducible frontiers first?", "was_revised": true, "final_justification": "I raise my score by to acknowledge the bridging fields contribution of suggesting EA in the present context and since questions about the FRA algorithm were resolved during the author discussion period", "rebuttal": "Thank you for your review. We believe there are a number of misconceptions and would like to clarify them in the following.\n\n# Strengths and Weaknesses\n\n- We do tackle all three of the contributions expressed in sections 4.1 to 4.3. While FRA is the most novel contribution, it is not the only one; each is different in importance and nature, but they all contribute to making do-SVs feasible in practice in their own way. Additionally, we believe that the third one has been misunderstood. More details below.\n- “I was confused about the role of [estimand-based] EB vs [estimand-agnostic] EA”. The contribution w.r.t. the EB approach is in bridging the gap between EA general procedures and do-SV estimation (where the original authors “are not aware of any general causal effect estimators suitable for estimating the expression\" [12]). With the base approach (EB), every single query $\\nu(S)$ has its own estimand and estimation procedure one needs to follow; this is an ad-hoc process that renders do-SVs impractical whenever the number of variables is larger. Instead, with the EA approach, we can define a single model from which any (identifiable) query can be computed automatically, following a general estimation procedure that can be implemented as a simple function call. Identifying this connection is the contribution, which makes do-SVs practical and feasible in complex, larger graphs.\n\nThe extensive discussion on the validity of the EA approach is to demonstrate that they are indeed capable of estimating do-SVs even though we do not use the corresponding estimands. This point was contested numerous times before by reviewers in the field, since EB is the dominant approach, which is why we devote a whole section (3.2) to explain why it works, as well as a set of experiments (5.1) to show how an EA method correctly estimates causal queries, and in particular, the true do-SV. (Additionally, we show how more complex architectures better model the data distribution, which in turn improves estimation performance). Section 4.1, where the EA approach is proposed for do-SVs, is much shorter since it does not require further explanation after the extensive previous section. Regardless, we did add Appendix H with a detailed example illustrating the application of our approach from start to finish.\n- About the three parts of section 4: 1 is part of the contribution for the aforementioned reasons. 3 explains how to approach Machine Learning explanations with do-SHAP, and presents Theorem 4.8, which is a novel contribution in itself, explaining the role of the exogenous noise on the do-SHAP game (under certain assumptions). Finally, we agree that section 4.2 (FRA) is quite dense, but this is as a result of space restrictions and the extensive discussion on the EA approach to properly demonstrate its validity, since without it, previous reviewers argued about this point and ignored our other contributions. We include Appendix D with a much more extensive explanation on this topic, together with all requisite proofs.\n\nAbout the “$\\phi$-encode” terminology, it meant that a set $S$ is $\\phi$-encoded by an integer $s$ if $s=\\phi(S)$, with the injective encoding function $\\phi$. This was meant for economy of notation, but we will clarify it in the camera-ready version. Other than that, was there anything else missing in our exposition?\n- Originality: We extend Luther’s approach in that it originally applied to conditional-SHAP (for do-SHAP, we had to derive new properties) and, more importantly, in that it does not only identify cases where $\\nu(S \\cup \\{X}) = \\nu(S)$ but instead returns the irreducible subset $S’$ such that $\\nu(S) = \\nu(S’)$. This is more powerful, as we will discuss in the following related point.\n- Quality: your proposed solution is less powerful than what is offered by the FRA algorithm. Consider an irreducible coalition S, and the maximal set $T \\subseteq \\mathcal{X}$ such that $T \\cap S = \\emptyset$ and $\\forall X \\in T, S \\in Fr(X, Y)$. Then, $\\forall T’ \\subseteq T, \\nu(S \\cup T’) = \\nu(S)$. Now, consider any $X \\in \\mathcal{X} \\setminus S \\setminus T$; there is no guarantee that $\\nu(S \\cup T’ \\cup \\{X\\}) = \\nu(S \\cup T’)$ (because $T$ is maximal) so we must compute the difference according to Luther. However, the FRA algorithm tells us that $\\nu(S \\cup T’) = \\nu(S)$ which can be cached for subsequent evaluations, thereby speeding up cases where Luther cannot offer any advantage. This applies to any irreducible coalition $S$ and superflous subsets $T’$. Hence the power of our proposal.\n\nFinally, note that we do not need to identify all possible irreducible coalitions beforehand. Instead, as we encounter new coalitions during do-SHAP execution, we can check which is the corresponding irreducible coalition and cache its value, so that further collisions can be omitted. We also made sure to make the FRA algorithm efficient, memory- (thanks to the integer formulation) and time-wise (as illustrated in our experiment 5.2; see figure 4b and 4c).\n\n# Questions\n\nWhen we claim that do-SHAP is made feasible on arbitrarily complex graphs due to the EA approach, we do not mean in terms of performance improvements, but on overcoming the ad-hoc nature of the EB approach, as argued above.\n\nNevertheless, we do demonstrate that computational time is not prohibitive for higher values of K, on a graph with $K=100$ nodes. See the paragraph in Section 5.2 starting on line 323, where we compare computation time between baseline do-SHAP, a simple cache, and an FRA-cache.\n\n# Other comments\n\nYour score on clarity is 1 (poor), whereas other reviewers chose 3 (good) or 4 (excellent). Could you please clarify what specific points made it harder to read our work? Was there a section that was misunderstood or confusing?\n\nAs for the fonts in the figures, we apologize for the inconvenience, but given space restrictions it was not possible to increase their size further. We do acknowledge this problem in the text and point towards the appendixes, where the smallest figures are replicated in a larger size for reader convenience.\n\nWe hope to have clarified your concerns, and are open to further questions. \n\nWe would like to kindly ask you to reconsider your review, in light of this rebuttal and the more favorable reviews by other reviewers. Thank you for your time and consideration."}]

Author rebuttal:

Meta-review: Summary: This paper addresses the problem of efficiently computing *do-Shapley values* (do-SVs), which are causal, interventional analogues of Shapley value feature attributions. The authors propose an *estimand-agnostic* (EA) approach: instead of computing each interventional expectation from scratch, they fit a single neural structural causal model (SCM) to the data, which can then be used to estimate any identifiable causal query. The key technical contribution is the *Frontier-Reduction Algorithm* (FRA), which leverages d-separation and graph structure to avoid redundant computations by identifying irreducible coalitions—subsets of variables whose addition to a coalition can affect the outcome. This reduces the number of terms that must be computed, potentially offering significant speedups over brute-force enumeration. The method is evaluated on synthetic and real data, demonstrating empirical gains in runtime and estimation efficiency, particularly when the proportion of variables with direct effects on the outcome is low.

Strength:

1. FRA is a well-motivated and technically interesting algorithm that exploits causal graph structure to accelerate do-SV computation. The theoretical insights are clearly presented, the proofs are detailed.

2. The paper is well-written, with clear explanations of causal concepts, algorithmic design, and experimental setup.

3. The method is implemented and tested on both synthetic and real data, with results showing practical speedups in relevant settings.

Weakness: 

1. The paper sometimes overstates the practical tractability of the approach. While FRA can yield significant speedups, it does not resolve the fundamental exponential complexity of Shapley value computation in the general case. The relationship between graph structure (e.g., sparsity) and computational gains is not fully characterized.
2. There is a lack of direct, quantitative runtime comparisons between the proposed method, prior estimand-based approaches, and standard SHAP baselines. This makes it difficult to assess the practical impact of the method in absolute terms.
3. The method assumes all required interventional queries are identifiable from the causal graph, but the challenges and limitations of this assumption in real-world settings are not sufficiently discussed.
4. The robustness of the approach to errors in the assumed causal graph or SCM is not empirically or theoretically analyzed.
5. The empirical evaluation is still somewhat limited in scope and does not fully explore the method’s behavior in complex, high-dimensional, or partially observed systems.


This is a technically solid and well-presented paper with a meaningful contribution to causal explainability. The paper would benefit from a more nuanced discussion of its limitations and a more thorough empirical evaluation. The reviewers converged on acceptance decisions with 3 borderline accept and 1 accept.
Decision: Accept (spotlight)