Spaces:

SabaPivot
/

repro-exactly-computing-do-shapley-values

Running

App Files Files Community

repro-exactly-computing-do-shapley-values / source /paper.txt

SabaPivot

Add exact algorithm implementation, evidence, source figures, poster, and bundle

c01176e verified 25 days ago

Raw

History Blame Contribute Delete

143 kB

	Exactly Computing do-Shapley Values


	R. Teal Witter * 1 Álvaro Parafita * 2 Tomàs Garriga 2 3 Maximilian Muschalik 4 Fabian Fumagalli 4
	Axel Brando 2 Lucas Rosenblatt 5


	Abstract Structural Causal Model (SCM)

	Structural Causal Models (SCM) are a powerful X1 X3
	framework for describing complicated dynamics closure S = {X1, X2, X3, X4}
	Y basis S = {X3}
	arXiv:2602.07203v1 [cs.LG] 6 Feb 2026




	across the natural sciences. A particularly ele-
	gant way of interpreting SCMs is do-Shapley, a X2 X4
	game-theoretic method of quantifying the average
	effect of d variables across exponentially many 1, 2, 3, 4
	interventions. Like Shapley values, computing
	do-Shapley values generally requires evaluating 1, 2, 4 1, 2, 3 1, 3, 4 2, 3, 4
	exponentially many terms. The foundation of
	our work is a reformulation of do-Shapley val- 1, 4 1, 2 1, 3 2, 3 3, 4 2, 4
	ues in terms of the irreducible sets of the under-
	1 2 3 4
	lying SCM. Leveraging this insight, we can ex-
	actly compute do-Shapley values in time linear Ø
	in the number of irreducible sets r, which itself Lattice of Coalitions
	can range from d to 2d depending on the graph
	structure of the SCM. Since r is unknown a pri- Figure 1. An example Structural Causal Model (SCM) and the
	ori, we complement the exact algorithm with an corresponding lattice of coalitions. Because of the graph structure,
	intervening on some nodes is redundant. For example, setting
	estimator that, like general Shapley value estima- {X1 , X2 , X3 , X4 } has the same effect as setting {X3 } because
	tors, can be run with any query budget. As the X3 blocks all directed paths from the other nodes to Y . For such a
	query budget approaches r, our estimators can class, we refer to its smallest coalition (e.g., {X3 }) as the basis,
	produce more accurate estimates than prior meth- and the largest coalition (e.g., {X1 , X2 , X3 , X4 }) as the closure.
	ods by several orders of magnitude, and, when the
	budget reaches r, return the Shapley values up to
	machine precision. Beyond computational speed, cient due to the fundamental problem of causal inference:
	we also reduce the identification burden: we prove because we cannot observe the counterfactual world where
	that non-parametric identifiability of do-Shapley a specific intervention did not occur, we cannot definitively
	values requires only the identification of interven- state, based on data alone, that one event caused another
	tional effects for the d singleton coalitions, rather (Holland, 1986; Rubin, 1974).
	than all classes.
	Structural Causal Models (SCMs) offer a powerful solu-
	tion by explicitly modeling the underlying mechanisms of a
	system (Pearl, 2009). Whether derived from established do-
	1. Introduction
	main knowledge or learned via causal discovery algorithms
	The question of causality is crucial to scientific inquiry, rang- (Peters et al., 2017), SCMs formalize the data-generating
	ing from policy evaluation in economics to treatment effects process: a directed acyclic graph G representing causal re-
	in healthcare. Yet, observational data alone is often insuffi- lationships, and a set of structural equations that determine
	1
	the value of each node as a function of its parents and ex-
	Mathematical Sciences Department, Claremont McKenna
	College 2 Barcelona Supercomputing Center, Barcelona, Spain
	ogenous noise (Bareinboim & Pearl, 2016). We provide a
	3
	Novartis 4 LMU Munich, MCML 5 Department of Computer more formal introduction to SCMs in Appendix B.
	Science and Engineering, New York University. Correspon-
	With a fully specified SCM, we can rigorously evaluate the
	dence to: R. Teal Witter <rtealwitter@cmc.edu>, Álvaro Parafita
	<parafita.alvaro@gmail.com>. effect of specific actions using the do-operator (Pearl, 2009).
	This operator simulates an intervention where a subset of
	Preprint. February 10, 2026. variables is forced to take specific values, independent of

	1
	Exactly Computing do-Shapley Values

	1.0
	Bid Ask




	Est. (Normalized)
	Close Volume
	Ask 0.5
	High Bid
	Bid Volume
	High 0.0
	Bid
	Open
	Ask 0.5
	Ask Open
	Low RegressionMSR LeverageSHAP
	1.0 doRegressionMSR doLeverageSHAP
	1.0 0.5 0.0 0.5 1.0 1.0 0.5 0.0 0.5 1.0
	True (Normalized)
	Figure 2. Left: A learned SCM from a TALENT dataset. Nodes and edges represent the learned causal graph used to define the
	interventional value function ν(S) = E[Y \| do(S = xS )] for a fixed instance x. Right: Plots of estimated vs true do-Shapley
	values on the learned SCM for randomly sampled x. Compared to the value-function-agnostic state-of-the-art RegressionMSR and
	LeverageSHAP estimators, our doEstimator variants provide substantially more accurate do-Shapley value estimates.


	their natural causes. Consider a specific instance of interest Lee, 2017) or restrictive path-dependent permutations (Frye
	x ∈ Rd . We define the value function ν(S) as the expected et al., 2020), this metric strictly isolates the total causal ef-
	value of the target outcome Y when the subset of features fect of a feature intervention. This rigorous isolation allows
	S ⊆ [d] is intervened upon to match their observed values us to translate abstract model dynamics into concrete causal
	in x: attributions, such as statements like “High family income
	increased acceptance probability by 10%” or “Prescribing
	ν(S) = E[Y \| do(S = xS )]. (1)
	prednisone decreased reported pain by two marks.”
	This formulation enables us to precisely answer hypothetical The challenge in computing the Shapley value, of course,
	queries, such as: “If we explicitly set this student’s income is that there are still 2d terms ν(S). So, without additional
	and tutoring time, how would their probability of admission structure in ν, exactly computing the Shapley value would
	change?” or “If a patient were administered prednisone take exponential time. To address this, the standard ap-
	and made to stop smoking, what would be their expected proach is to approximate the Shapley value using stochas-
	pain level?” However, characterizing the system’s behavior tic estimators that evaluate ν(S) on a limited budget of
	purely through these individual queries is challenging. As sampled coalitions. A diverse array of model-agnostic es-
	the number of features d grows, the number of possible timators has been developed for this purpose, including
	interventional subsets scales as 2d . To extract interpretable direct Monte Carlo estimators (Štrumbelj & Kononenko,
	insights from this combinatorial landscape, we need a uni- 2014), permutation-based sampling (Castro et al., 2009),
	fied framework to attribute the complicated dynamics of the and regression-based formulations such as KernelSHAP
	SCM to individual features. and LeverageSHAP (Lundberg & Lee, 2017; Covert &
	Lee, 2021; Musco & Witter, 2025).
	The Shapley value (Shapley, 1953) provides a rigorous
	framework for such explanations by attributing the changes For do-Shapley values, recent work has exploited the obser-
	in the outcome Y to individual variables based on their vation that the topological structure of SCMs often renders
	marginal contributions. Formally, the ith Shapley value cap- specific interventions redundant (Parafita et al., 2025). For
	tures the weighted average effect of adding variable i to a example, in the causal graph depicted in Figure 1, the inter-
	coalition S: vention on {X3 } results in the same value as the intervention
	X on {X1 , X3 , X4 }, because the paths from X1 and X2 to Y
	ϕi = [ν(S ∪ i) − ν(S)]p\|S\| (2)
	are blocked by X3 . To formalize this, define the basis of a
	S⊆[d]\i
	coalition S as the subset S ⊆ S containing precisely those
	where the weight pℓ = d1 d−1
	−1
	can be interpreted as a variables j ∈ S that possess a directed path to Y that does
	ℓ
	probability distribution. not traverse any other node in S. In effect, any variable in
	S \ S is intercepted by S and yields no additional impact
	When the value function is defined via the interventional do- on the outcome, ensuring ν(S) = ν(S). A set is irreducible
	operator (Equation 1), the result is the do-Shapley value if it is its own basis. This property enables a caching strat-
	(Jung et al., 2022), also referred to as the causal Shap- egy: rather than naively evaluating the SCM for every query
	ley value (Heskes et al., 2020).1 Unlike standard formu- ν(S), the estimator first computes the basis S and checks
	lations that rely on conditional expectations (Lundberg &
	simply as the value function, and the do-Shapley value as the
	1 Shapley value.
	For conciseness, we henceforth refer to the do-value function

	2
	Exactly Computing do-Shapley Values

	if ν(S) has been previously memoized. If so, the cached ···
	1 2 d Y
	value is returned; if not, the SCM is evaluated and the result
	stored. This mechanism avoids redundant evaluations of (a) Since there is a directed path from each node to Y , there
	the underlying model, resulting in significant computational are at least d irreducible sets. The figure depicts a graph with
	speedups (Parafita et al., 2025). d irreducible sets.

	We extend this insight by observing that every basis S is 1 2 ··· d
	associated with a unique closure S̄ ⊇ S—the maximal
	coalition such that intervening on S̄ yields the identical Y
	effect as intervening on S. For example, the closure of
	{X3 } in Figure 1 is {X1 , X2 , X3 , X4 }. Together, these (b) Since there are 2d sets total, there are at most 2d irreducible
	bounds define an equivalence class of coalitions {S ⊆ [d] : sets. The figure depicts a graph with 2d irreducible sets.
	S ⊆ S ⊆ S̄}, all of which map to the same value ν(S).
	Figure 3. The number of irreducible sets ranges between d and 2d .
	Crucially, these classes constitute a partition of the powerset
	of all d features. Letting r denote the total number of such
	classes c1 , . . . , cr , we leverage this structure to compress proaches is sample redundancy. Standard estimators sam-
	the Shapley summation into a linear combination of class ple coalitions without knowledge of the underlying causal
	values: structure, meaning they can (wastefully) query different
	r
	X coalitions that belong to the same large equivalence class.
	ϕi = ν(cj )wi (cj ) (3) Thus, a budget of m queries often produces far fewer than m
	j=1 unique values. We resolve this inefficiency by introducing a
	boundary sampler, a targeted exploration strategy guaran-
	where the class weight wi (cj ) is derived in Equation 5. A teed to identify min(m, r) distinct equivalence classes when
	similar decomposition is known for trees (Zern et al., 2023b; run with m queries. By feeding these distinct values into a
	Witter et al., 2025); but, unlike trees where the structure can simulated estimator, we maximize the information extracted
	be read in a linear pass of the leaves, efficiently finding the from the available budget. We find that this method can
	class structure of an SCM is non-trivial. reduce estimation error by orders of magnitude compared
	This formulation reduces the exact computation of Shapley to the best value-function-agnostic estimators run with the
	values to a sum over r terms. To identify these classes caching scheme of Parafita et al. (2025). Furthermore, the
	efficiently, we propose a lattice exploration algorithm that estimator exhibits seamless convergence: as the budget m
	circumvents the exhaustive enumeration of the powerset. approaches r, the approximation error vanishes, achieving
	Leveraging a structural property of closed sets (Lemma 3.1), exact computation (up to machine precision) once m ≥ r.
	our algorithm enumerates all r classes in O(r(d + e + T )) In practice, SCMs are frequently learned from observational
	time, where e is the number of edges in the causal graph data and a hypothesized graph structure. A critical prerequi-
	and T is the time to query the value function once. site for this process is identifiability: determining whether a
	The efficiency of this approach is strictly governed by the causal query can be uniquely estimated from the observed
	underlying graph topology. As illustrated in Figure 3, the
	number of classes r varies with the graph structure, ranging 105 70
	from a linear d in the best case to 2d in the worst case. Observed (r)
	Exhaustive (2d) 60
	104 Linear Lower Bound (d)
	Number of Classes r




	To quantify how much this compression manifests in prac-
	Number of Edges \|E\|



	50
	tice, we plot the number of irreducible sets r against the
	103 40
	number of variables d across real datasets in Figure 4. The
	observed scaling typically lies below the worst-case 2d , re- 102 30
	flecting the sparsity of learned causal graphs in real-world
	20
	tabular domains. 101
	10
	Although our exact algorithm scales linearly with r, the
	number of classes r is unknown a priori. Since real-world 2 4 6 8 10 12 14 16
	Dimension d (Nodes)
	applications demand strict resource limits, we must often
	operate within a fixed computational budget of m value Figure 4. Complexity Reduction. The number of irreducible sets
	function queries. To address this, we propose a class of r (colored points) versus the dimension d. While the theoretical
	worst-case complexity is 2d (red dashed line), real-world causal
	estimators explicitly tailored to this constrained setting. structures are often sparse, resulting in r scaling in between the
	The fundamental limitation of prior caching-based ap- exponential and the linear lower bound d (black dotted line).


	3
	Exactly Computing do-Shapley Values

	probability distribution given the graph (Pearl, 2009). For 1997), capturing the joint causal impact of coalitions.
	instance, in the presence of unobserved confounding, differ-
	ent structural parameters could yield the exact same obser- 1.1. Additional Related Work
	vational distribution but different interventional outcomes.
	The gold standard for verifying non-parametric identifia- Exactly computing Shapley values is generally feasible only
	bility is the ID algorithm (Shpitser & Pearl, 2006; Tian & when the underlying model possesses exploitable structure
	Pearl, 2002), which determines if a specific query ν(S) is (Rozemberczki et al., 2022). This has led to efficient, model-
	computable from the observational distribution. specific algorithms for decision trees and ensembles, includ-
	ing TreeSHAP (Lundberg et al., 2020; Yu et al., 2022),
	This creates a practical bottleneck for Shapley value es- interventional variants (Zern et al., 2023b), and extensions
	timation. Since the Shapley value aggregates r terms, a like TreeSHAP-IQ (Muschalik et al., 2024c). Similar exact
	practitioner using prior methods would be forced to run methods exist for linear models (Štrumbelj & Kononenko,
	the estimator and iteratively check identifiability for each 2014), product-kernel networks (Mohammadi et al., 2025a),
	irreducible set encountered. If a single coalition proved Gaussian processes (Mohammadi et al., 2025b), graph neu-
	unidentifiable, the entire estimation would be invalidated af- ral networks (Muschalik et al., 2025), and KNN-based data
	ter significant computation (Parafita et al., 2025). In Section valuation (Jia et al., 2019; Wang et al., 2023; 2024). When
	5, we resolve this burden by proving a structural sufficiency black-box access precludes exact methods, practitioners rely
	theorem: to guarantee the identifiability of all 2d coalitions, on model-agnostic estimators (Chen et al., 2023; Muschalik
	it suffices to verify identifiability for only the d singleton et al., 2024b) such as Monte Carlo sampling (Castro et al.,
	interventions {i} ⊂ [d]. This allows practitioners to run a 2009; Kolpaczki et al., 2024b;a; Fumagalli et al., 2023;
	rapid, O(d) sanity check before model training begins, en- Wang & Jia, 2023) or regression-based approaches like
	suring that the resulting Shapley values will be valid without KernelSHAP (Lundberg & Lee, 2017), which has been
	the risk of costly mid-computation failures. enhanced via leverage scores (Musco & Witter, 2025) and
	In summary, our contributions are three-fold: interaction support (Fumagalli et al., 2024; Tsai et al., 2023).
	Finally, exact computation has recently merged with esti-
	1. Exact Computation via Irreducible Sets: We propose mation via surrogate modeling (Butler et al., 2025), where
	an algorithm that computes exact do-Shapley values by auxiliary models are fit to the value function to allow effi-
	exploiting the graph’s equivalence classes. By traversing cient extraction of Shapley values (Witter et al., 2025).
	the lattice of closed sets, the algorithm runs in time linear
	in the number of irreducible sets r (and the graph size e),
	rather than the worst-case exponential complexity of 2d .
	2. Reformulating do-Shapley Values
	2. Structure-Aware Estimation: We introduce a class of In this section, we leverage the underlying structure of an
	boundary sampling estimators designed for fixed-budget SCM to reformulate do-Shapley values in terms of equiva-
	settings. Unlike prior methods that sample blindly, our ap- lence classes.
	proach targets distinct equivalence classes. This yields error Firstly, we will assume that all nodes in [d] are ancestors of
	reductions of several orders of magnitude as m approaches the target node Y , since non-ancestors have null do-Shapley
	r, and seamlessly transitions to exact machine-precision value. We will start with the definition of basis, derived
	computation once the budget satisfies m ≥ r. from the concept of irreducible sets in Parafita et al. (2025).
	3. Efficient Identifiability Check: We prove that non- Definition 2.1 (Basis). The basis of S, denoted S, is the
	parametric identifiability of the full do-Shapley value is subset of nodes j ∈ S such that there exists a directed path
	guaranteed if and only if the d singleton interventions are from j to Y that intersects S only at j.
	non-parametrically identifiable. This result enables a rapid
	O(d) sanity check, allowing practitioners to verify the fea- A set S ⊆ [d] is irreducible if it is its own basis.
	sibility of the explanation task before incurring the cost of Similarly, we will define the closure of S as the superset of
	model training or estimation. nodes that can be blocked from reaching Y by S.
	While we focus on the Shapley value due to its Definition 2.2 (Closure). The closure of S, denoted S̄, is
	widespread adoption, our theoretical insights generalize to the set of all nodes j ∈ [d] such that every directed path
	the broader class of probabilistic values—e.g., Banzhaf val- from j to Y intersects S.
	ues (Banzhaf III, 1964), beta Shapley values (Kwon & Zou,
	2022), and weighted Banzhaf values (Li & Yu, 2024)—by We say a set S ⊆ [d] is closed if it is its own closure.
	simply changing the marginal weights in Equation 4. Fur- Let S and S̄ be the basis and closure of a coalition S, re-
	thermore, in Section 7, we demonstrate how to adapt our spectively. S belongs to an equivalence class with all T
	methods to compute Shapley Interaction Indices (Grabisch, such that S ⊆ T ⊆ S̄. By definition, all nodes in T \ S

	4
	Exactly Computing do-Shapley Values

	are blocked from reaching Y by S, so, by the third rule of Algorithm 1 FindClass
	do-Calculus (Pearl, 2009), Input: Set S ⊆ [d], graph G
	Output: basis S ⊆ S, and closure S̄ ⊇ S
	ν(S) = ν(T ) = ν(S̄).
	G′ ← G with all incoming edges to nodes in S removed
	Nanc ← ancestor nodes i.e., a directed path to Y in G′
	It is easy to see that the classes form a partition of all 2d
	S̄ ← S ∪ ([d] \ Nanc ) ▷ S and nodes not connected to Y
	coalitions.
	S ← S ∩ Nanc ▷ Subset of S still connected to Y
	Let r be the number of irreducible sets, and denote the return S, S̄
	classes by c1 , . . . , cr . In an abuse of notation, we will define
	ν(cj ) = ν(S) where S is any set in class cj . We will use
	this structure to rewrite the Shapley values: there are 2d sets on the lattice, so even constant work per
	set is infeasible. Instead, we can efficiently traverse the
	set lattice by only generating sets which are guaranteed to
	ϕi =
	X
	p\|S\| [ν(S ∪ {i}) − ν(S)] be closed, amortizing the work to each class, rather than
	each subset. The key tool is a structural lemma on alternate
	S⊆[d]\{i}
	definitions of closed sets.
	ν(S) 1[i ∈ S]p\|S\|−1 − 1[i ∈
	X
	= / S]p\|S\| Lemma 3.1. Let S̄ ⊂ [d] be a closed set with basis S. Then
	S⊆[d]
	r
	X 1. For all j ∈ S, S̄ \ {j} is closed.
	= ν(cj ) · wi (cj ) (4)
	j=1 2. If S̄ ̸= [d], there exists j ∈ [d] \ S̄ so that S̄ ∪ {j} is
	closed and j is in the basis of S̄ ∪ {j}.
	where, with S̄ as the closure of class c and S as the basis of
	class c, we define We defer the proof of the lemma to Appendix A.
	1[i ∈ T ]p\|T \|−1 − 1[i ∈/ T ]p\|T \| .
	X
	wi (c) = Algorithm 2 describes our method. We efficiently find each
	T :S⊆T ⊆S̄ class by iterating over closed sets, in decreasing order of
	size. We start with the full set [d]. For each closed set S̄ of
	Even though there could be exponentially many subsets in a size ℓ, we compute its basis S. By Lemma 3.1, S̄ \ {j} is
	class, we can compute wi (c) in O(d) time. In particular, it closed for all j ∈ S. We then add each of these closed sets,
	is easy to show that and further explore them when we reach size ℓ − 1.
	We can see that Algorithm 2 correctly returns all closed sets
	P by an inductive argument. Suppose that we have identified
	\|S̄\|
	pℓ−1 \|S̄\|−\|S\| all closed sets of size ℓ; the base case is trivial since there

	
	 ℓ=\|S\| ℓ−\|S\|
	i∈S
	is only one set, and it must be closed. By Lemma 3.1,
	
	
	
	
	wi (c) = − \|ℓ=\|S\|
	P S̄\|
	pℓ \|S̄\|−\|S\|

	i∈/ S̄ (5) for every closed set S̄ of size ℓ − 1, there is a closed set
	ℓ−\|S\|
	
	
	 S̄ ∪ {j} for some j in the basis of S̄ ∪ {j}. By the inductive
	assumption, we must have identified this set, and also found
	
	
	0 else.
	S̄ by removing j from S̄ ∪ {j}. It follows that every closed
	set of size ℓ − 1 gets generated by some closed set of size ℓ.
	We will use this structure to compute Shapley values. If
	we have O(r(d + e)) time, then we can exactly compute
	Shapley values as described in Section 3. Since r is initially Algorithm 2 AllClasses
	unknown, we may also want to estimate Shapley values Input: Number of elements d, graph G
	given a fixed query budget m. In Section 4, we describe Output: All closed sets C
	estimators that run in O(m(d + e)) time. C0 ← . . . ← Cd ← ∅ ▷ Closed sets of each size
	Cd ← {{1, . . . , d}} ▷ Only closed set of size d
	3. Exactly Computing do-Shapley Values for ℓ = d, . . . , 1 do
	for S̄ ∈ Cℓ do
	By Equation 4, computing all irreducible sets is sufficient S, S̄ ← FindClass(S̄, G)
	to exactly compute the Shapley value. It remains to find all ▷ Use Lemma 3.1
	irreducible sets. for j ∈ S do
	Add S̄ \ {j} to Cℓ−1
	A naive strategy is to traverse the set lattice by subset size,
	return C0 ∪ . . . ∪ Cd
	determining the class of each set via Algorithm 1. Of course,

	5
	Exactly Computing do-Shapley Values

	Algorithm 2 runs in O(r(d + e)) time: for each closure— sample classes proportional to their weights wi (cj ) because
	there is one closure for each of the r classes—the algorithm the classes (and thus their weights) are unknown without
	runs a graph exploration in time d + e, and then adds at most graph exploration. Furthermore, a stratified sampling ap-
	d closed sets of size ℓ − 1 to explore. proach—sampling coalitions without replacement to ensure
	unique classes—proves computationally expensive. As de-
	Simple Class Optimization Sometimes running Algo- tailed in Appendix D, such a stratified sampling method
	rithm 1 as a subroutine in Algorithm 2 can be avoided. For incurs a cost quadratic in m, which defeats the purpose of
	a closed set S̄ that is simple—S̄ is both its own closure and fast approximation.
	basis—all of its subsets are also simple. To see why, observe
	that all nodes j ∈ S̄ have a directed path to Y that does not
	intersect any other node in S̄, and hence any other node in a Boundary Sampling We propose a boundary sampler,
	subset of S̄. It follows that all subsets are irreducible; with a targeted graph exploration strategy that achieves sample
	Lemma 3.1, we have that all such subsets are also closed. efficiency in time linear in m. Instead of sampling blindly
	For a simple set, we add an optimization to Algorithm 2 in from the powerset, we maintain candidate classes adjacent
	our implementation so that all the bases of its candidates are to those we have already visited.
	cached, avoiding the O(d + e) cost of Algorithm 1 for all The algorithm, described in Algorithm 3, proceeds by main-
	subsets of a simple set. taining a priority queue of candidate classes, ordered by
	Together, Equation 4 and Algorithm 2 can compute Shapley their expected weight magnitude Ei [\|wi (c)\|]. In each it-
	values in time linear in r. eration, we sample a class c proportional to the expected
	magnitude of its weight, evaluate ν(c), and add it to our
	Proposition 3.2. Shapley values of the intervention value sampled set. We then expand the candidate by generating
	function can be exactly computed in O(r(d + e + T )) time, the neighbors of c in the lattice. Specifically, for a class
	where T is the time to evaluate the game ν on a given c with basis S and closure S̄, the neighbors are defined as
	coalition, and r is the number of irreducible sets. either lower neighbors {S̄ \{j} \| j ∈ S} or upper neighbors
	{S̄ ∪{j} \| j ∈/ S̄}. For each neighbor, we run FindClass
	4. Approximating do-Shapley Values to determine its canonical representation and weight, adding
	it to the queue if it has not been seen. This ensures that
	While Algorithm 2 allows for exact computation in O(r(d + every query results in a new class. By starting at each level
	e)) time, the number of irreducible sets r is unknown a in the lattice, and adding neighbors above and below, we
	priori. In resource constrained settings where r may be explore the lattice in a balanced way.
	too large, we would like an approximation technique that
	operates within a fixed computational budget of m value We state Algorithm 3, and prove the following upper bound
	function queries. on its runtime, in Appendix A.

	Standard value-function-agnostic estimators sample coali- Proposition 4.1. Algorithm 4 runs in O(m · d(d + e)) time,
	tions from a fixed distribution. While caching can prevent where m is the query budget, d is the number of features,
	re-evaluation of the SCM for known classes, these estima- and e is the number of edges in the graph.
	tors suffer from sample redundancy: they blindly generate
	coalitions that may belong to equivalence classes already
	Estimation via Simulation After running the boundary
	queried. As a result, a budget of m queries often yields far
	sampler, we utilize the set of sampled classes C to compute
	fewer than m distinct class values, wasting computational
	the Shapley values, as shown in Algorithm 3.
	resources on redundant parts of the lattice.
	Case m ≥ r: If the queue empties before the budget is
	To address this, we seek an estimator that guarantees the
	reached, we have identified all irreducible sets. We proceed
	discovery of min(m, r) distinct equivalence classes. If m ≥
	to compute the exact Shapley values using Equation 6.
	r, the method should naturally recover the exact Shapley
	values to machine precision. If m < r, it should prioritize Case m < r: We leverage the fact that we have paid the
	classes with weight to minimize estimation error. cost to evaluate ν(c) for all c ∈ C. We construct a simulated
	estimator, described in Appendix C. This allows us to gener-
	Recall that the Shapley value can be expressed as a weighted
	ate many samples at no additional query cost, reducing the
	sum over equivalence classes:
	variance of the estimator while balancing time complexity.
	r
	ϕi =
	X
	ν(cj ) · wi (cj ). (6) We run Algorithm 3 where the base estimators are the cur-
	j=1
	rent state-of-the-art value-function-agnostic Shapley value
	estimators LeverageSHAP (Musco & Witter, 2025) and
	Directly estimating this sum presents a challenge: we cannot RegressionMSR (Witter et al., 2025).

	6
	Exactly Computing do-Shapley Values

	Algorithm 3 doEstimator key questions: (1) To what extent does the number of irre-
	Input: Budget m, Game v, BaseEstimator, Sam- ducible sets r reduce the complexity compared to the worst-
	pling multiplier k case 2d in real-world dependencies? (2) Do our structure-
	Output: Shapley values estimates ϕ ∈ Rd aware estimators outperform state-of-the-art model-agnostic
	▷ Step 1: Sampling Phase baselines under fixed query budgets? (3) How does the
	C, allSampled ← BoundarySampler(m, G) learned causal structure qualitatively influence feature attri-
	Query ν(c) for all c ∈ C ▷ min(r, m) queries bution error?
	▷ Step 2A: Exact Computation Data. We utilize the TALENT benchmark (Liu et al., 2025),
	if allSampled then a large-scale repository of tabular datasets. To enable reli-
	ϕ←0 able evaluation against exhaustive baselines, we restrict to
	for each class c ∈ C do datasets whose post-pruning dimension (after restricting to
	ϕi ← ϕi + ν(c) · wi (c) for all i the ancestors of the target Y ) permits exact computation of
	return ϕ ν(S) over all coalitions S ⊆ [d] within our computational
	▷ Step 2B: Run BaseEstimator budget. For each dataset, we select a set of test instances x
	D ← SimulatedSampler(C, k · m) ▷ Algorithm 5 and report errors aggregated across instances and datasets.
	return BaseEstimator(D) Additional dataset-level details (including the resulting di-
	mensions after pruning) are provided in the appendix.
	SCM Generation. Since real-world datasets lack ground-
	5. Identifiability
	truth causal graphs, we learn SCMs from data to serve as
	Whenever a causal query PS (T ) is uniquely determined the ground-truth games ν. For each dataset, we employ
	by the graph and dataset, we say the query is (non- the Greedy Relaxed Search Procedure (GRaSP) (Lam et al.,
	parametrically) identifiable. However, this is not always 2022) with a BIC score to learn a Completed Partially Di-
	the case; we include an illustrative example in Appendix E. rected Acyclic Graph (CPDAG), which is converted to a
	DAG greedily. Not all features in a dataset causally influ-
	Computing the do-Shapley value requires verifying the iden-
	ence the target. Following the definition of do-Shapley, we
	tifiability of component queries ν(S) via the ID algorithm
	prune the learned graph to the ancestral set of the target vari-
	(Shpitser & Pearl, 2006). Even with class-based grouping,
	able Y ; nodes with no directed path to Y have a null Shap-
	this necessitates r separate tests. Conducting these checks
	ley value and are removed. We then fit non-linear structural
	sequentially during estimation is risky, as a late discovery of
	equations using Gradient Boosting Regressors (Friedman,
	non-identifiability renders all prior computation wasted. To
	2001) to model the conditional distributions E[Xi \| Pa(Xi )].
	eliminate this overhead, we present a theorem establishing
	This learned SCM acts as our oracle ν(S).
	a linear-time check for global identifiability.
	Methods. We evaluate our framework against two state-
	Theorem 5.1. The do-Shapley value ϕi is identifiable if,
	of-the-art model-agnostic estimators: RegressionMSR
	and only if, ∀j ∈ [d], ν({j}) is identifiable.
	(Witter et al., 2025) and LeverageSHAP (Musco & Wit-
	The necessary background knowledge and proof is left for ter, 2025). These serve as our structure-agnostic base-
	Appendix E. lines, estimating Shapley values by directly sampling and
	querying coalitions from the full powerset. To explic-
	Consequently, we can execute the ID algorithm on the d itly isolate the gains attributable to our graph-theoretic in-
	singleton coalition queries and, if all are identifiable, the sights, our proposed estimators doRegressionMSR and
	do-Shapley value will be identifiable and we can proceed doLeverageSHAP are not fundamentally new regression
	with its estimation. If not, further parametric assumptions, techniques. Rather, they repurpose the same estimation ma-
	or the inclusion of instrumental variables, will be required chinery used in the baselines. The main difference lies in
	to ensure identifiability. Regardless, this result prevents the data generation process: whereas the baselines query
	practitioners from training estimating do-Shapley values random coalitions, our methods train the estimators on the
	only to learn the outcome was not identifiable to begin distinct equivalence classes recovered by the boundary sam-
	with. Additionally, it reduces the number of calls to the ID pler (as described in Algorithm 3). This allows us to com-
	algorithm from r to d. pare “structure-aware” versus “structure-agnostic” sampling
	while holding the estimation logic constant.
	6. Experiments
	We evaluate the performance of our exact algorithm and Lattice Complexity Reduction The efficiency of our ex-
	boundary sampling estimators on a diverse set of real-world act algorithm relies on r ≪ 2d . In Figure 4, we plot the
	datasets. Our experiments are designed to investigate three number of irreducible sets r against the dimension d for 156

	7
	Exactly Computing do-Shapley Values

	Estimator Convergence (Aggregated) do-Shapley values do-Shapley interactions do-Shapley interactions
	(order 1) (order 2) (order 7, Möbius Transform)
	−1
	10
	10 −5
	Relative MSE

	10 −9
	10 −13 Method
	10 −17 doRegressionMSR
	doLeverageSHAP
	10 −21 RegressionMSR
	LeverageSHAP
	10 −25 Budget = r Expressivity
	0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
	Budget Ratio m/r Figure 6. Interactions offer an expressive explanation framework.
	Figure 5. Estimator Convergence (Aggregated). The relative
	MSE of Shapley value estimates versus the budget ratio m/r,
	aggregated across all datasets. Shaded regions indicate 95% confi- b) The framework is not limited to single-feature attribu-
	dence intervals. Our structure-aware estimators consistently out- tions but naturally extends to interaction values, i.e.,
	perform the baseline variants. Notably, as the budget exceeds the changes in the value function with respect to subsets T
	number of classes (m > r, red dotted line), our error vanishes to rather than singletons i, as described in Appendix F.
	machine precision, whereas baselines continue to exhibit variance.
	While the Shapley values provides a principled framework
	for attributing value to individuals, they are limited in expres-
	datasets from the TALENT benchmark. We observe that sivity. For instance, assessing interactions like synergies or
	for real-world data, the number of irreducible sets r often redundancies across multiple features, is not possible based
	remains significantly below 2d . on individual Shapley values. n-Shapley values (Lundberg
	et al., 2018b; Bordt & von Luxburg, 2023) enrich this expla-
	Estimation Efficiency We evaluate estimation error by nation by adding interactions up to order n. These interac-
	query budget m, defined relative to the number of irre- tions are based on the Shapley interaction index (Grabisch
	ducible sets r. Figure 5 presents Relative MSE for all & Roubens, 1999), an axiomatic extension of the Shapley
	estimators. value. Similar to the Shapley value, n-Shapley values satisfy
	In the sparse budget regime where we cannot fully explore an extended efficiency axiom (Muschalik et al., 2024b), and
	the lattice, doRegressionMSR (blue) demonstrates su- provide a more granular and expressive explanation of ν
	perior sample efficiency, consistently achieving the lowest (see Figure 6). Their explicit form is given in Appendix F.
	error. This advantage becomes increasingly pronounced With n = d, n-Shapley values yield the Möbius transform
	as the budget approaches r. By prioritizing the discovery (Rota, 1964), which provides the exact additive decomposi-
	of distinct equivalence classes via boundary sampling, our tion of ν (Bordt & von Luxburg, 2023). Importantly, they
	method minimizes redundant queries that plague the stan- satisfy the linearity axiom and their weights only depend on
	dard samplers. the cardinality of the coalition and the interaction, which al-
	lows a similar decomposition as Equation (4). Consequently,
	A phase transition occurs at m = r (indicated by the red ver- once the irreducible sets are known, we can efficiently com-
	tical line). Once the budget allows for full lattice exploration, pute the Shapley interaction index and n-Shapley values, as
	our boundary sampler identifies that all irreducible sets have shown in Appendix F.
	been found. At this point, the algorithm switches to the exact
	computation described in Section 3. Consequently, the MSE
	Conclusion
	for both doRegressionMSR and doLeverageSHAP
	drops precipitously to machine precision. In contrast, the We address the computational challenges of do-Shapley
	structure-agnostic baselines (green and purple) continue to values by reformulating the estimation via structural equiva-
	sample coalitions with replacement, exhibiting a slow con- lence classes. Our proposed algorithm, based on irreducible
	vergence rate and failing to achieve exactness even with sets, scales with causal complexity (r) rather than dimension
	double the necessary budget (m = 2r). (2d ) and employs boundary sampling to reduce redundancy.
	Additionally, we show that verifying identifiability requires
	7. Generalizations only a linear O(d) check of singletons. By prioritizing
	structure-aware exploration, this framework facilitates attri-
	Our result immediately generalizes in two ways: bution in complex systems, offering a practical step toward
	scalable causal explainability. Future work could extend
	a) The weighting function p is not restricted to Shapley
	these methods to larger graphs, such as in genomics, or
	values and may correspond to alternative probabilistic
	investigate sensitivity to graph misspecification.
	value concepts, such as the Banzhaf index, weighted
	Banzhaf values, or Beta Shapley values.

	8
	Exactly Computing do-Shapley Values

	Impact Statement Behavior, 55(1):72–99, 2006. doi: 10.1016/j.geb.2005.
	03.002.
	This paper presents work whose goal is to advance the field
	of machine learning. There are many potential societal Fumagalli, F., Muschalik, M., Kolpaczki, P., Hüllermeier,
	consequences of our work, none of which we feel must be E., and Hammer, B. SHAP-IQ: Unified Approxima-
	specifically highlighted here. tion of any-order Shapley Interactions. In Proceedings
	of Advances in Neural Information Processing Systems
	References (NeurIPS), 2023.

	Banzhaf III, J. F. Weighted voting doesn’t work: A mathe- Fumagalli, F., Muschalik, M., Kolpaczki, P., Hüllermeier,
	matical analysis. Rutgers Law Review, 19:317, 1964. E., and Hammer, B. KernelSHAP-IQ: Weighted Least
	Square Optimization for Shapley Interactions. In Pro-
	Bareinboim, E. and Pearl, J. Causal inference and the data- ceedings of the International Conference on Machine
	fusion problem. Proceedings of the National Academy of Learning (ICML), pp. 14308–14342, 2024.
	Sciences, 113(27):7345–7352, 2016.
	Grabisch, M. k-order additive discrete fuzzy measures
	Bordt, S. and von Luxburg, U. From Shapley Values to and their representation. Fuzzy Sets and Systems, 92(2):
	Generalized Additive Models and back. In Proceedings 167–189, 1997. doi: 10.1016/S0165-0114(97)00168-1.
	of the International Conference on Artificial Intelligence
	and Statistics (AISTATS), pp. 709–745, 2023. Grabisch, M. and Roubens, M. An axiomatic approach to
	the concept of interaction among players in cooperative
	Butler, L., Agarwal, A., Kang, J. S., Erginbas, Y. E., Yu, games. International Journal of Game Theory, 28(4):
	B., and Ramchandran, K. Proxy-SPEX: Sample-efficient 547–565, 1999. doi: 10.1007/s001820050125.
	interpretability via sparse feature interactions in LLMs.
	In The Thirty-ninth Annual Conference on Neural In- Heskes, T., Sijben, E., Bucur, I. G., and Claassen, T. Causal
	formation Processing Systems, 2025. URL https: Shapley values: exploiting causal knowledge to explain
	//openreview.net/forum?id=KI8qan2EA7. individual predictions of complex models. Advances in
	Neural Information Processing Systems (NeurIPS), 33:
	Castro, J., Gómez, D., and Tejada, J. Polynomial calculation 4778–4789, 2020.
	of the Shapley value based on sampling. Computers
	Holland, P. W. Statistics and causal inference. Journal of
	& Operations Research, 36(5):1726–1730, 2009. doi:
	the American statistical Association, 81(396):945–960,
	10.1016/j.cor.2008.04.004.
	1986.
	Chen, H., Covert, I. C., Lundberg, S. M., and Lee, S.-I.
	Jia, R., Dao, D., Wang, B., Hubis, F. A., Hynes, N., Gürel,
	Algorithms to estimate Shapley value feature attributions.
	N. M., Li, B., Zhang, C., Song, D., and Spanos, C. J.
	Nature Machine Intelligence, pp. 1–12, 2023.
	Towards efficient data valuation based on the shapley
	Covert, I. and Lee, S.-I. Improving kernelshap: Practi- value. In Proceedings of the 22nd International Confer-
	cal shapley value estimation using linear regression. In ence on Artificial Intelligence and Statistics (AIStats), pp.
	International conference on artificial intelligence and 1167–1176. PMLR, 2019.
	statistics, pp. 3457–3465. PMLR, 2021.
	Jung, Y., Kasiviswanathan, S., Tian, J., Janzing, D.,
	Dubey, P., Neyman, A., and Weber, R. J. Value theory Blöbaum, P., and Bareinboim, E. On measuring causal
	without efficiency. Mathematics of Operations Research, contributions via do-interventions. In International Con-
	6(1):122–128, 1981. doi: 10.1287/MOOR.6.1.122. ference on Machine Learning, pp. 10476–10501. PMLR,
	2022.
	Friedman, J. H. Greedy function approximation: A gradient
	boosting machine. The Annals of Statistics, 29(5):1189– Kolpaczki, P., Bengs, V., Muschalik, M., and Hüllermeier,
	1232, 2001. doi: 10.1214/aos/1013203451. E. Approximating the shapley value without marginal
	contributions. In Proceeedings of the AAAI Conference on
	Frye, C., Rowat, C., and Feige, I. Asymmetric Shapley val- Artificial Intelligence (AAAI), pp. 13246–13255, 2024a.
	ues: incorporating causal knowledge into model-agnostic
	explainability. Advances in Neural Information Process- Kolpaczki, P., Muschalik, M., Fumagalli, F., Hammer, B.,
	ing Systems (NeurIPS), 33:1229–1239, 2020. and Hüllermeier, E. SVARM-IQ: efficient approximation
	of any-order shapley interactions through stratification. In
	Fujimoto, K., Kojadinovic, I., and Marichal, J. Ax- Proceedings of the International Conference on Artificial
	iomatic characterizations of probabilistic and cardinal- Intelligence and Statistics (AISTATS), pp. 3520–3528,
	probabilistic interaction indices. Games and Economic 2024b.

	9
	Exactly Computing do-Shapley Values

	Kwon, Y. and Zou, J. Beta shapley: a unified and noise- Muschalik, M., Fumagalli, F., Hammer, B., and Hüllermeier,
	reduced data valuation framework for machine learning. E. Beyond TreeSHAP: Efficient Computation of Any-
	In Proceedings of the International Conference on Artifi- Order Shapley Interactions for Tree Ensembles. In Pro-
	cial Intelligence and Statistics (AISTATS), pp. 8780–8802, ceedings of the 38th AAAI Conference on Artificial Intel-
	2022. ligence, volume 38, pp. 14388–14396, 2024c.
	Lam, W.-Y., Andrews, B., and Ramsey, J. Greedy relax- Muschalik, M., Fumagalli, F., Frazzetto, P., Strotherm, J.,
	ations of the sparsest permutation algorithm. In Uncer- Hermes, L., Sperduti, A., Hüllermeier, E., and Hammer,
	tainty in Artificial Intelligence, pp. 1052–1062. PMLR, B. Exact Computation of Any-Order Shapley Interactions
	2022. for Graph Neural Networks. In The Thirteenth Interna-
	tional Conference on Learning Representations, 2025.
	Li, W. and Yu, Y. Robust data valuation with weighted
	banzhaf values. Advances in Neural Information Process- Musco, C. and Witter, R. T. Provably Accurate Shapley
	ing Systems, 36, 2024. Value Estimation via Leverage Score Sampling. In Proc-
	Liu, S.-Y., Cai, H.-R., Zhou, Q.-L., Yin, H.-H., Zhou, T., cedings of the International Conference on Learning Rep-
	Jiang, J.-P., and Ye, H.-J. Talent: A tabular analytics resentations (ICLR), 2025.
	and learning toolbox. Journal of Machine Learning Parafita, Á. and Vitrià, J. Estimand-agnostic causal query
	Research, 26(226):1–16, 2025. URL http://jmlr. estimation with Deep Causal Graphs. IEEE Access, 10:
	org/papers/v26/25-0512.html. 71370–71386, 2022.
	Lundberg, S. M. and Lee, S.-I. A unified approach to inter- Parafita, Á., Garriga, T., Brando, A., and Cazorla, F. J.
	preting model predictions. Advances in neural informa- Practical do-shapley explanations with estimand-agnostic
	tion processing systems, 30, 2017. causal inference. In The Thirty-ninth Annual Con-
	Lundberg, S. M., Erion, G. G., and Lee, S.-I. Consistent in- ference on Neural Information Processing Systems,
	dividualized feature attribution for tree ensembles. arXiv 2025. URL https://openreview.net/forum?
	preprint arXiv:1802.03888, 2018a. id=Qabko39AS5.

	Lundberg, S. M., Erion, G. G., and Lee, S.-I. Consistent in- Pearl, J. Causality: Models, Reasoning and Inference. Cam-
	dividualized feature attribution for tree ensembles. arXiv bridge University Press, second edition, 2009.
	preprint arXiv:1802.03888, 2018b.
	Peters, J., Janzing, D., and Schölkopf, B. Elements of causal
	Lundberg, S. M., Erion, G. G., Chen, H., DeGrave, A. J., inference: foundations and learning algorithms. The MIT
	Prutkin, J. M., Nair, B., Katz, R., Himmelfarb, J., Bansal, press, 2017.
	N., and Lee, S. From local explanations to global under-
	standing with explainable AI for trees. Nature Machine Rota, G.-C. On the foundations of combinatorial theory: I.
	Intelligence, 2(1):56–67, 2020. theory of möbius functions. In Classic Papers in Combi-
	natorics, pp. 332–360. Springer, 1964.
	Mohammadi, M., Chau, S. L., and Muandet, K. Comput-
	ing exact shapley values in polynomial time for product- Rozemberczki, B., Watson, L., Bayer, P., Yang, H., Kiss,
	kernel methods. arXiv preprint arXiv:2505.16516, 2025a. O., Nilsson, S., and Sarkar, R. The shapley value in
	machine learning. In Proceedings of International Joint
	Mohammadi, M., Muandet, K., Tiddi, I., Teije, A. T., and Conference on Artificial Intelligence (IJCAI), pp. 5572–
	Chau, S. L. Exact shapley attributions in quadratic- 5579, 2022.
	time for fanova gaussian processes. arXiv preprint
	arXiv:2508.14499, 2025b. Rubin, D. B. Estimating causal effects of treatments in
	randomized and nonrandomized studies. Journal of edu-
	Muschalik, M., Baniecki, H., Fumagalli, F., Kolpaczki, P., cational Psychology, 66(5):688, 1974.
	Hammer, B., and Hüllermeier, E. shapiq: Shapley Interac-
	tions for Machine Learning. In Proceedings of Advances Shapley, L. A value for n-person games. In Contributions
	in Neural Information Processing Systems (NeurIPS), pp. to the Theory of Games (AM-28), Volume II, pp. 307–317.
	130324–130357, 2024a. Princeton University Press, 1953.

	Muschalik, M., Baniecki, H., Fumagalli, F., Kolpaczki, P., Shpitser, I. and Pearl, J. Identification of joint interventional
	Hammer, B., and Hüllermeier, E. shapiq: Shapley Inter- distributions in recursive semi-Markovian causal models.
	actions for Machine Learning. In Advances in Neural In Proceedings of 21st National Conference on Artificial
	Information Processing Systems (NeurIPS), volume 37, Intelligence (AAAI), pp. 1219–1226, Boston, MA, USA,
	pp. 130324–130357, 2024b. 2006.

	10
	Exactly Computing do-Shapley Values

	Štrumbelj, E. and Kononenko, I. Explaining prediction mod-
	els and individual predictions with feature contributions.
	Knowledge and information systems, 41:647–665, 2014.
	Tian, J. and Pearl, J. On the testable implications of causal
	models with hidden variables. In Proceedings of the
	18th Conference on Uncertainty in Artificial Intelligence
	(UAI), pp. 519–527, Edmonton, Canada, 2002.

	Tsai, C., Yeh, C., and Ravikumar, P. Faith-Shap: The
	Faithful Shapley Interaction Index. Journal of Machine
	Learning Research, 24(94):1–42, 2023.
	Wang, J. T. and Jia, R. Data banzhaf: A robust data valuation
	framework for machine learning. In Ruiz, F. J. R., Dy,
	J. G., and van de Meent, J. (eds.), Proceedings of the
	International Conference on Artificial Intelligence and
	Statistics (AISTATS), pp. 6388–6421, 2023.
	Wang, J. T., Zhu, Y., Wang, Y.-X., Jia, R., and Mittal, P. A
	privacy-friendly approach to data valuation. In Advances
	in Neural Information Processing Systems (NeurIPS),
	volume 37, 2023.
	Wang, J. T., Mittal, P., and Jia, R. Efficient data shapley for
	weighted nearest neighbor algorithms. In Proceedings
	of the 27th International Conference on Artificial Intel-
	ligence and Statistics (AIStats), pp. 2557–2565. PMLR,
	2024.
	Witter, R. T., Liu, Y., and Musco, C. Regression-adjusted
	monte carlo estimators for shapley values and probabilis-
	tic values. In The Thirty-ninth Annual Conference on Neu-
	ral Information Processing Systems, 2025. URL https:
	//openreview.net/forum?id=Qabko39AS5.
	Yu, P., Bifet, A., Read, J., and Xu, C. Linear tree shap.
	In Advances in Neural Information Processing Systems
	(NeurIPS), volume 35, 2022.

	Zern, A., Broelemann, K., and Kasneci, G. Interventional
	SHAP values and interaction values for piecewise linear
	regression trees. In Proceeedings of the AAAI Confer-
	ence on Artificial Intelligence (AAAI), pp. 11164–11173,
	2023a.

	Zern, A., Broelemann, K., and Kasneci, G. Interventional
	SHAP values and interaction values for piecewise linear
	regression trees. In Proceedings of the 37th AAAI Con-
	ference on Artificial Intelligence, volume 37, pp. 11164–
	11173, 2023b.




	11
	Exactly Computing do-Shapley Values

	A. Delayed Proofs
	Lemma 3.1 Let S̄ ⊂ [d] be a closed set with basis S. Then

	1. For all j ∈ S, S̄ \ {j} is closed.

	2. If S̄ ̸= [d], there exists j ∈ [d] \ S̄ so that S̄ ∪ {j} is closed and j is in the basis of S̄ ∪ {j}.

	Proof of Lemma 3.1. We will first show that S̄ \ {j} is closed for all j ∈ S. To do so, it suffices to show that, for all nodes
	not in S̄ \ {j}, there is a directed path to Y that does not intersect S̄ \ {j}. This is clearly true for all nodes not in S̄ since S̄
	is itself closed. It must also be true for j since j ∈ S, i.e., there is a directed path from j to Y that does not intersect S. The
	first statement follows.
	Next, we will show that for S ̸= [d], there exists j ∈ [d] \ S̄ so that S̄ ∪ {j} is closed. Let T = [d] \ S̄. Since G is a finite
	DAG, there is a topological order on the nodes. Consider a node j ∈ T with no ancestors in T , either because they are all in
	S̄, or it has no ancestors. To prove that S̄ ∪ {j} is closed, it suffices to show that, for all nodes not in S̄ ∪ {j}, there is a
	directed path to Y that does not intersect S̄ ∪ {j}. Since S̄ is closed, all of the nodes in T \ {j} have paths to Y that do
	not intersect S̄. Note that j cannot be in any of these paths, since j has no ancestors in T , hence all nodes in T \ {j} must
	actually have paths that do not intersect S̄ or j. Furthermore, since j ∈ T , it must have a directed path to Y that does not
	intersect S̄. Therefore, j must be in the basis of S̄ ∪ {j}. The second statement follows.

	Proposition 4.1. Algorithm 4 runs in O(m · d(d + e)) time, where m is the query budget, d is the number of features, and e
	is the number of edges in the graph.

	Proof of Proposition 4.1. The algorithm performs exactly m iterations of the main while loop. In each iteration, we
	process one class c. The cost of processing a class is dominated by generating its neighbors and invoking FindClass for
	each. A class with closure S̄ and basis S has \|S\| lower neighbors and d − \|S̄\| upper neighbors; thus, the total number of
	neighbors is bounded by d. For each neighbor, we execute FindClass, which requires a graph traversal taking O(d + e)
	time. Therefore, the work per iteration is O(d(d + e)). Over m iterations, the total time complexity is O(m · d(d + e)).
	This is linear in the budget m, ensuring the method is scalable for anytime estimation.




	12
	Exactly Computing do-Shapley Values




	Algorithm 4 BoundarySampler
	Input: Budget m, Graph G
	Output: Sampled classes C, flag allSampled
	C←∅ ▷ Sampled classes
	Q←∅ ▷ Queue mapping classes to weights
	Cseen ← ∅
	▷ Helper to calculate weight and enqueue
	function Enqueue(S)
	c ← FindClass(S, G) ▷ Get basis and closure
	if c ∈ Cseen then
	return
	Add c to Cseen
	Q[c] ← Ei [\|wi (c)\|] + ϵ ▷ Add ϵ to ensure valid dist.
	▷ Phase 1: Warm-start
	for ℓ = 1 to d do
	Sample random set S ⊂ [d] where \|S\| = ℓ
	Enqueue(S)
	▷ Phase 2: Weighted Graph Traversal
	while \|C\| < m and Q ̸= ∅ do
	Sample c from Q with prob ∝ Q[c]
	Remove c from Q and add to C
	S, S̄ ← basis and closure of c
	Nbelow ← {S̄ \ {j} \| j ∈ S}
	Nabove ← {S̄ ∪ {j} \| j ∈ / S̄}
	for candidate set S ′ ∈ Nbelow ∪ Nabove do
	Enqueue(S ′ )
	return C, Q == ∅




	13
	Exactly Computing do-Shapley Values

	B. Background on Structural Causal Models
	A Causal graph is usually described as a Directed Acyclic Graph (DAG) G, where every node represents a measured
	random variable and every directed edge represents a relationship cause → effect. These graphs often include dashed
	bidirected edges between pairs of nodes (X ↔ Y ) as a shorthand for the existence of an unobserved latent variable U that
	acts as a confounder between them (X ← U → Y ). Additionally, it is assumed that every measured node X has a latent
	exogenous noise variable, denoted EX , with the associated edge EX → X.
	A Structural Causal Model (SCM) is a probabilistic model based on such a causal graph G with a probability distribution for
	all latent nodes (i.e., all confounders and EX ) and, for each measured node X, functions fX such that X := fX (P aG (X)),
	taking the values of all parents of X in G including latent variables. From this model, a probability distribution over
	the measured variables V emerges, P (V ), as well as the intervened model Mdo(S=s) , where the do operator conveys an
	intervention on all nodes X ∈ S replacing their functions fX by the assignment x := sX . This effectively removes all
	incoming edges to the intervened nodes from the graph, and results in a new probability distribution for the intervened
	model, P (V \| do(S = s)), also denoted Ps (V ) or, for arbitrary intervention values, PS (V ).
	Given a dataset and its assumed underlying causal structure, we can train an SCM following that graph to learn the
	distribution of the dataset. Afterwards, one can employ procedures on the SCM to estimate causal queries of the form
	PX (Y ). Additionally, if the causal query is non-parametrically identifiable (more details in Section 5), these estimations
	resulting from the SCM are necessarily equivalent to what the true data generating process would return if we had access
	to it. Therefore, we can employ these trained SCMs to estimate the do-SHAP value functions ν(S) as long as they are
	identifiable. For more details about this approach, please refer to (Parafita & Vitrià, 2022).




	14
	Exactly Computing do-Shapley Values

	C. Simulated Sampling from Irreducible Sets
	In this appendix, we detail the SimulatedSampler, the engine behind Step 2B of the doEstimator. This component
	allows us to sample coalitions efficiently from the specific sub-lattice defined by the discovered equivalence classes.

	C.1. Algorithm and Explanation
	The challenge in simulating samples from the discovered classes is that the union of these classes does not form a simple
	structure (like a full powerset). A naive rejection sampling approach—sampling from the full powerset and keeping only
	those in C—would be inefficient if the volume of C is small relative to 2d .
	Instead, our sampler (Algorithm 5) adopts a constructive approach:

	• Normalization: We first calculate the total “volume” of available coalitions within the known classes. For each class c
	with basis S and closure S̄, the number of subsets of size s contained in c is given by \|S̄\|−\|S\|

	s−\|S\|
	.

	• Scale Calibration: Standard Shapley weights are defined for the entire powerset. To sample validly from our restricted
	support, we solve for a scaling factor γ such that the expected number of samples drawn matches our target budget
	Bsim . This is achieved via binary search (Lines 7-15).

	• Stratified Generation: We iterate through each class c ∈ C and each valid subset size s. For each size, we compute the
	expected number of samples Nc,s . We use probabilistic rounding to convert this expectation into an integer count, and
	then generate that many unique subsets from class c using a combinatorial number system (Lines 22-26).


	Algorithm 5 SimulatedSampler
	1: Input: Discovered classes C, Simulation Budget Bsim , Weights w (per size)
	2: Output: Dataset of coalitions D = {(Sk , ν(ck ), pk )}
	3: D ← ∅
	4: ▷ Step 1: Count available coalitions per size across all classes
	5: Navail [s] ← 0 for s ∈ 0 . . . d
	6: for each class c ∈ C do
	7: Let nfree = \|S̄\| − \|S\|
	8: for j = 0 to nfree do
	Navail [\|S\| + j] ← Navail [\|S\| + j] + njfree

	9:
	10: ▷ Step 2: Calibrate sampling scale γ
	Pd
	11: Define E[samples](γ) = s=0 Navail [s] · minγ wds , 1
	(s)
	12: Find γ ∗ via binary search such that E[samples](γ ∗ ) ≈ Bsim
	13: ▷ Step 3: Constructive Sampling
	14: for each class c ∈ C do
	15: Let Ifree be indices in S̄ \ S
	16: for j = 0 to \|Ifree \| do
	17: Size s ← \|S\| +j
	18: Prob p ← min γ ∗ wds , 1
	()
	\|Ifree \|
	s
	19: Count K ← j
	20: Expected count µ ← K · p
	21: Ndraw ← ⌊µ⌋ + Bernoulli(µ − ⌊µ⌋) ▷ Probabilistic rounding
	22: if Ndraw > 0 then
	23: Generate Ndraw unique combinations Csub ⊆ Ifree of size j
	24: for each combination σ ∈ Csub do
	25: S ←S∪σ
	26: Add (S, ν(c), p) to D
	27: return D


	15
	Exactly Computing do-Shapley Values

	C.2. Runtime Analysis
	Proposition C.1. The SimulatedSampler generates Nsim samples in O(Nsim · d + \|C\| · d) time.

	Proof. The algorithm consists of three main parts:

	1. Counting (O(\|C\| · d)): We iterate over each class once. For each class, we perform a loop over its ”free” size range,
	which is at most d. The binomial coefficient calculations can be done in O(1) with pre-computation.

	2. Calibration (O(d · log(1/ϵ))): The binary search evaluates the expected sample sum a constant number of times. Each
	evaluation sums over d sizes.
	3. Generation (O(Nsim · d)): The outer loops iterate over classes and sizes, but the inner generation logic (Lines 24-28)
	executes exactly Nsim times in total (by definition of the calibrated budget). Generating a combination of size k using
	the combinatorial number system or direct sampling takes O(d). Thus, the generation phase scales linearly with the
	number of output samples.

	Dominating terms yield a total complexity of O(Nsim · d + \|C\| · d), which is highly efficient given that no SCM evaluations
	are performed.




	16
	Exactly Computing do-Shapley Values

	D. Stratified Sampling
	Ideally, to estimate the Shapley value for player i, we would sample each class c proportional to the magnitude of its weight
	wi (c). However, the underlying class structure (the mapping of sets to values) is unknown prior to sampling, making the
	direct computation of wi (c) impossible.
	To address this, we consider an adaptive sampling scheme based on the natural distribution suggested by the Shapley weights.
	We sample a set S containing i with probability pℓ−1 , and a set S excluding i with probability pℓ . Note that while these
	probabilities are derived from the Shapley weights, they do not perfectly correspond to the final importance weights because
	the contribution of i cancels to zero when i is effectively a “null” player (i.e., in the closure but not in the basis).
	The proposed do-Good estimator samples according to these distributions without replacement. Sampling classes without
	replacement is crucial for the estimator to achieve exactness when the sampling budget covers the effective support of the
	game (m ≥ r). To achieve this, we maintain weighted counts of the remaining “mass” of the distributions for each player i.
	We define the remaining mass for sets including i (µ(+) ) and excluding i (µ(−) ) as:
	(+)
	1[S not seen],
	X
	µℓ,i = pℓ−1 (7)
	S:\|S\|=ℓ,i∈S
	(−)
	1[S not seen].
	X
	µℓ,i = pℓ (8)
	S:\|S\|=ℓ,i∈S
	/

	(+) (−)
	Initially, before any classes have been sampled, these initialize to the full binomial sums: µℓ,i = pℓ−1 d−1

	ℓ−1 and µℓ,i =
	pℓ d−1

	ℓ .


	Sampling Procedure
	−
	The sampling process proceeds hierarchically to determine whether to sample proportional to µ+
	ℓ,i or µℓ,i :


	1. We first select an index i uniformly from [d].
	2. We sample an inclusion indicator z ∈ {−, +}, where
	Pd (+)
	ℓ=1 µℓ,i
	Pr(z = +) = Pd (+) Pd−1 (−) .
	ℓ=1 µℓ,i + ℓ=0 µℓ,i

	(z)
	3. We sample a set size ℓ with probability proportional to the remaining mass µℓ,i .

	Once ℓ and z are determined, we must sample a specific set S of size ℓ (containing i if and only if z = +) uniformly from
	the collection of all such sets that belong to currently unseen classes. This step is non-trivial; it depends on the number of
	valid completions available in the unseen space. As detailed in Algorithm 7, computing these counts requires a linear pass
	through the history of previously discovered classes.
	We analyze the computational complexity of the ClassSampler (Algorithm 6). The runtime is dominated by the
	requirement to sample uniformly from unseen sets, which necessitates checking consistency against all previously discovered
	classes.
	Proposition D.1 (Stratified Sampling Complexity). Let m be the sampling budget (number of iterations) and d be the
	number of elements (dimension). Assuming set operations (union, intersection, subset checks) take O(d) time, the total time
	complexity of the ClassSampler is O(m2 d2 ).

	Because the algorithm is quadratic in m, we turn to the boundary sampling method described in Section 4.

	Proof of Proposition D.1. The analysis proceeds by examining the cost of the helper functions from the bottom up.
	1. Cost of CountSeen: This function iterates through the set of seen classes C. In the k-th iteration of the main loop,
	\|C\| ≤ k. Inside the loop, we perform standard set operations (checking S ⊆ S ∪ R, etc.).
	Tcount (k) = O(\|C\| · d) = O(k · d). (9)

	17
	Exactly Computing do-Shapley Values

	Algorithm 6 ClassSampler
	Input: Number of elements d, budget m, value function ν, graph G
	Output: Set of seen classes C
	Initialize seen classesC ← ∅
	(1)
	Set µℓ,i ← pℓ−1 d−1ℓ−1 for all ℓ ∈ {1, . . . , d} and i ∈ [d]
	(0) d−1

	Set µℓ,i ← pℓ ℓ for all ℓ ∈ {0, . . . , d − 1} and i ∈ [d]
	for idx = 1 to m do
	▷ Sample set from unseen classes
	Sample i ∼ Uniform([d])
	Pd (1)
	ℓ=1 µℓ,i
	Sample z ∼ Bernoulli Pd (1) Pd−1 (0)
	ℓ=1 µℓ,i + ℓ=0 µℓ,i
	(z)
	Sample ℓ ∝ µℓ,i
	S ← {i} if z = 1 else ∅
	S ← SampleUnseenBySize(ℓ, S, C)
	S, S̄ ← FindClass(S, G) ▷ Find class c
	(1) (0)
	Update all µℓ,i and µℓ,i ▷ Constant time per ℓ and i
	Add class c to C
	return C


	2. Cost of SampleUnseenBySize: This function constructs a set S of size ℓ element-by-element. The while loop runs
	at most ℓ ≤ d times. In every iteration, it calls CountSeen twice to calculate Nin and Nout .
	ℓ
	X
	Tsample (k) = 2 · Tcount (k)
	j=1

	= O(d · (k · d)) = O(kd2 ). (10)

	3. Total Cost of ClassSampler: The main algorithm runs for m iterations. In iteration k, it calls
	SampleUnseenBySize, performs a graph lookup (FindClass), and updates weights.
	The function FindClass runs in O(d + e) time where e is the number of edges in the graph. Since e ≤ d2 , the dominant
	cost remains the combinatorial counting step. The update of µ values takes O(d2 ) but is repeated only m times.
	Summing over m iterations:
	m
	X
	Tsample (k) + O(d2 )

	Ttotal =
	k=1
	Xm
	= O(kd2 )
	k=1
	m
	X
	= O(d2 ) k ≈ O(d2 m2 ). (11)
	k=1

	Thus, the total complexity is quadratic in both the dimension and the sample budget.




	18
	Exactly Computing do-Shapley Values




	Algorithm 7 SampleUnseenBySize
	Input: Size ℓ, Initial set S (i.e., {i} or ∅), seen classes C
	Output: A set S of size ℓ sampled uniformly from unseen sets
	R ← [d] \ S ▷ Available candidates
	C ′ ← {c : \|S\| ≤ ℓ ≤ \|S̄\|} ▷ Relevant classes
	while \|S\| < ℓ do
	Pick j uniformly from R
	▷ Completions in seen classes with and without j
	Nin , Cin′ ← CountSeen(ℓ, S ∪ {j}, R \ {j}, C ′ )
	′
	Nout , Cout ← CountSeen(ℓ, S, R \ {j}, C ′ )
	▷ Calculate count of unseen completions
	\|R\|−1
	Uin ← ℓ−\|S\|−1 − Nin
	Uout ← \|R\|−1

	ℓ−\|S\|
	− Nout
	▷ Pick j proportional to unseen completions
	Sample b ∼ Bernoulli UinU+U in
	out

	C ′ ← Cout
	′

	if b = 1 then
	C ′ ← Cin′
	S ← S ∪ {j}
	R ← R \ {j}
	return S




	Algorithm 8 CountSeen
	Input: Size ℓ, current set S, remaining set R, seen classes C
	Output: Number of completions N , applicable classes C ′
	N ←0
	C′ ← ∅ ▷ Initialize applicable classes
	for class c ∈ C do
	Let S be the basis and S̄ be the closure of c
	▷ Check if S and R are consistent with class
	if S ̸⊆ (S ∪ R) or S ̸⊆ S̄ then continue
	Add c to C ′ ▷ Applicable class
	▷ Calculate available optional elements in this class
	noptions ← \|R ∩ (S̄ \ S)\|
	▷ Calculate available, optional spaces
	nspaces ← ℓ − \|S\| − \|R ∩ S\|
	N ← N + nnoptions
	spaces
	return N




	19
	Exactly Computing do-Shapley Values

	E. Identifiability Criterion
	In this section, we operate exclusively with non-parametric identifiability, following (Pearl, 2009) (Definition 3.2.4), where
	an interventional causal query Q[M ], defined on a causal model M with DAG G = (V ∪ U, E) with V measured nodes
	and U latent nodes, is (non-parametrically) identifiable from G if the query can be computed uniquely from any positive
	probability of the observed variables Markov-relative2 to the graph. In other words, if two causal models M1 and M2
	with positive probability distributions PM1 and PM2 are both Markov-relative to G and observationally identical to each
	other (PM1 (V ) = PM2 (V )), then both models must have the same value for the given query. Note that this definition
	does not include any assumptions about the functional forms of the causal models nor the probability distributions of the
	unobserved variables. In other words, non-parametric identifiability cannot assume anything other than the shape of the
	graph G (including latent confounders).


	U

	X Y

	Figure 7. Bow-arc graph, with non-identifiable PX (Y ).



	Non-identifiable example. Consider the Directed Acyclic Graph (DAG) G = ({X, Y } ∪ {U }, E) in Figure 7, where U
	is an unmeasured variable acting as a latent confounder between X and Y . In this graph, PX (Y ) is not identifiable. Let us
	demonstrate by creating two equivalent positive distributions P 1 and P 2 Markov-relative to G, with different intervened
	distributions for PX (Y ). We define two latent variables: U , the latent confounder between X and Y , and EY , the exogenous
	noise variable for Y , both with the same distribution in both models, N (0, 1). In terms of their functional assignments,
	1 2
	x := fX (u) = fX (u) = u, while y := fY1 (x, u, ey ) = x − u + ey and y := fY2 (x, u, ey ) = x · 0 + ey . Note that
	all distributions P (X), P 2 (X), P 1 (Y \| X), P 2 (Y \| X) are identical, N (0, 1), and so is P 1 (X, Y ) = P 1 (X)P 1 (Y \|
	1

	X) = P 2 (X)P 2 (Y \| X) = P 2 (X, Y ), and they are positive. However, P 1 (Y \| do(X = 0)) ∼ N (0, 2) while
	P 2 (Y \| do(X = 0)) ∼ N (0, 1). Therefore, PX (Y ) is not identifiable.
	Non-parametric identifiability can be demonstrated if we can find an estimand of the causal query only containing
	observational terms. In particular, the ID algorithm (Shpitser & Pearl, 2006), described in Section E.1 and presented in
	simplified form in Algorithm 9, determines non-parametric identifiability w.r.t. a causal graph G of any non-conditional,
	interventional query PX (Y ), for any disjoint subsets of variables X, Y .
	Note that any coalition value ν(S) = E[Y \| do(S = s)] is non-parametrically identifiable if, and only if, PS (Y ) is
	non-parametrically identifiable. Trivially, identifiability in the probability terms guarantees identifiability in the expectation
	(since the expectation’s summation or integral is an observational estimand only consisting of identifiable terms Ps (y)).
	Conversely, non-identifiability in the terms PS (Y ) must imply non-identifiability for the expectation in the absence of
	further parametrical assumptions (e.g., assuming that Ps (y) = Ps (−y), in which case the terms cancel each other out and
	make the expectation identifiable). For this reason, we will focus on non-parametric identifiability, and only on queries of
	the form PS (Y )—which can be determined thanks to the ID algorithm—as a proxy for identifiability of ν(S).

	E.1. The ID algorithm
	Let us provide the necessary background definitions and properties to understand the ID algorithm and follow the proofs of
	our identifiability criterion.
	Definition E.1. Let G = (V ∪ U, E) be a Directed Acyclic Graph (DAG) with nodes V ∪ U (measured and latent nodes,
	respectively) and edges E. Its latent projection is an Acyclic Directed Mixed Graph (ADMG) G∗ = (V, E ∗ ), which is a
	graph containing directed and bidirected edges and no directed cycles. In particular, G∗ only contains the measured nodes in
	G and: (1) any directed edge in G between measured nodes; (2) an edge between measured nodes if both are connected in G
	by a directed path where all intermediate nodes are in U ; and (3) a bidirected edge Vi ↔ Vj between measured nodes if both
	are connected by a path of the form Vi ← · · · ← · → · · · → Vj where all intermediate nodes are in U .
	2 Q
	A probability distribution is Markov-relative to a DAG G = (V ∪ U, E) if P (V, U ) = X∈V ∪U P (X \| P aG (X)), where P aG (X)
	is the set of parents of X in G.

	20
	Exactly Computing do-Shapley Values

	Algorithm 9 ID(T, S, G)
	Input: Disjoint sets T, S ⊆ V, ADMG G = (V, E).
	Output: Boolean indicating whether PS (T ) is identifiable.
	1: If S = ∅, return TRUE.
	2: If V ̸= AnG (T ), return ID(T, S ∩ AnG (T ), G[AnG (T )]).
	3: Let W := (V \ S) \ AnGS (T ). If W ̸= ∅, return ID(T, S ∪ W, G).
	4: If V \ S ̸∈ C(G[V \ S]), return ∧Ci ∈C(G[V\S]) ID(Ci , V \ Ci , G).
	5: If V ∈ C(G), return FALSE.
	6: If V \ S ∈ C(G), return TRUE.
	7: Let C ∈ C(G) s.t. C ⊃ V \ S, return ID(T, S ∩ C, G[C]).


	In the following, when talking about a graph, we refer to the ADMG latent projection of the DAG under study.

	Notation. Let G be an ADMG. We denote by V (G) the set of nodes of G. We denote by G[S] the induced subgraph of
	G filtering to the nodes S ⊆ V (G) and only preserving those edges connecting preserved nodes. For a node Y ∈ V (G),
	we denote by AnG (Y ) the set of (directed) ancestors of node Y in G including Y , and by DeG (Y ) the set of (directed)
	descendants S of node Y in G including Y . We overload the notation with the ancestors of a set of nodes T ⊆ V (G),
	AnG (T ) := t∈T AnG (t), and equivalently for DeG (T ). We denote the intervened graph GS as the subgraph of G such
	that any incoming edge to the nodes in S is removed. For this reason, in this section, we will avoid denoting the closure of a
	coalition S by S to avoid ambiguity.
	Definition E.2. The root set R of an ADMG G is the set of nodes in G with no proper descendants: R := {X ∈ V (G) \|
	DeG (X) = {X}}.
	Definition E.3. Let G be an ADMG. We say that a set of nodes V is a C-component within an ADMG G if all nodes
	are connected via bidirected arcs. We denote the set of maximal C-components of a graph G by C(G). In particular, C(G)
	constitutes a partition of V (G). We also say G is a C-component when V (G) is a C-component in G.
	Definition E.4. We say an ADMG G is an R-rooted C-forest if R is its root set, G is a C-component, and all its nodes have
	at most one (directed) child.
	Definition E.5. Let G be an ADMG, and S, T disjoint subsets of variables in V (G). We say a pair (F, F ′ ) is an R-
	rooted hedge for PS (T ) if both F and F ′ are R-rooted C-forests such that F ′ ⊆ F ⊆ G, F ∩ S ̸= ∅, F ′ ∩ S = ∅ and
	R ⊆ AnGS (T ).

	Hedges are the reason for non-identifiability of causal effects. See the following theorem from (Shpitser & Pearl, 2006)
	(Theorem 4).
	Theorem E.6. If (F, F ′ ) is a hedge for PS (T ) in an ADMG G, PS (T ) is not identifiable in G.

	We are now ready to study the ID algorithm (Shpitser & Pearl, 2006), with which we can ascertain the identifiability of any
	query PS (T ). We present a simplified version in Algorithm 9.

	E.2. Identifiability criterion
	When evaluating do-SHAP, one must evaluate causal queries ν(S) := E[Y \| do(S = s)] for multiple coalitions S ⊆ [d]. If
	one such query is not identifiable, we cannot continue evaluating do-SHAP and must raise an error. However, this forces
	practitioners to execute do-SHAP without knowing if an estimate can be raised, while also running the ID algorithm for
	every single coalition that must be evaluated.
	Instead, we present the following result, which allows us to determine the identifiability of all 2d coalition values ν(S) just
	by determining the identifiability of the d singleton coalitions {i} ⊆ [d].
	Theorem E.7. Let G be an ADMG over V, with a single Y ∈ V target node. If ∃X ⊆ V \ {Y } such that PX (Y ) is not
	identifiable, then ∃s ∈ X ∪ (V \ AnGX (Y )) such that P{s} (Y ) is not identifiable.

	We will devote the remainder of this section to proving this theorem. Let us first prove a set of lemmas that will progressively
	build towards the proof.

	21
	Exactly Computing do-Shapley Values

	Lemma E.8. Let G be an ADMG over V, with a set Y ⊆ V the target nodes. If ∃X ⊆ V \ Y such that PX (Y ) is not
	identifiable, then the ID algorithm ends at line 5 in a recursive call ID(T, S, G′ ) for S and T non-empty disjoint subsets of
	V ′ ⊆ V, and G′ an induced subgraph G′ = G[V ′ ] ⊆ G. Then, there exists R-rooted C-forests (F, F ′ ), R ⊆ V ′ such that
	they constitute a hedge for PS (T ).

	Proof. Firstly, the ID algorithm (Shpitser & Pearl, 2006) always terminates (Lemma 3 in their paper), it is sound (Theorem 5)
	and complete (Corollary 2). Since we assume that PX (Y ) is not identifiable, it must be that when we evaluate ID(Y, X, G),
	we will eventually return FALSE from line 5 at a certain recursion level ID(T, S, G′ ). Both X and S must be non-empty
	(otherwise line 1 would have returned TRUE). Both S and T must be subsets of V and disjoint (since all recursive
	calls maintain them being disjoint given the initial assumption that Y ∩ X = ∅). Finally, G′ is an induced subgraph
	G′ = G[V ′ ] ⊆ G, since all recursive calls will at most remove nodes from G.
	Let R be the root set of G′ [V ′ \ S]. In particular, R ∩ S = ∅. Let F ′ be an edge subgraph of G′ [V ′ \ S] such that its root set
	remains R but all observable nodes have at most one child, and all confounding arcs in G′ [V ′ \ S] are present. Note that
	G′ [V ′ \ S] is a C-component (otherwise, line 4 would have triggered) and in creating F ′ we did not remove any confounding
	arcs, so F ′ is also a C-component, and therefore an R-rooted C-forest. Now, let us define an edge subgraph F ⊆ G′ by
	starting from F ′ , adding all nodes in S and, for every such node adding only one edge to one of its children in G′ , as well
	as all bidirected edges. Since every new node has a child in V (F ), the root set remains R, and F is an R-rooted C-forest
	by the same reasoning as before because line 5 guarantees C(G′ ) = {V ′ }. Additionally, F ′ ⊆ F , V (F ′ ) ∩ S = ∅ and
	V (F ) ∩ S = S ̸= ∅. All that remains is to prove that R ⊆ AnG′ (T ). First, note that R ⊆ AnG′ (T ) by line 2, so there
	S
	exist paths from nodes r ∈ R to nodes t ∈ T . Let us assume that one such r has all its directed paths blocked by S. Then,
	r ̸∈ AnGS (T ) and r ̸∈ S (because R ∩ S = ∅), which means that W in line 3 would have contained r. By contradiction,
	R ⊆ AnG′ (T ) and, finally, (F, F ′ ) is a hedge for PS (T ) in G′ .
	S



	We now define some notation that will guide the proofs that follow. Let G be an ADMG over V, with a single target node
	Y ∈ V. If ∃X ⊆ V \ {Y } such that PX (Y ) is not identifiable, let us focus on a single call-path returning FALSE, and
	denote the i-deep call ID(T i , S i , Gi ) (with corresponding V i := V (Gi )) along the call-path, starting on ID({Y }, X, G)
	(with {Y } = T 0 , X = S 0 , G = G0 ) and ending at depth d ≥ 0 in line 5 for the found hedge. Whenever line 4 or 7 are
	called at depth i, let us denote by C i the C-component that appears either: in line 4, for the recursive call to ID in the
	particular branch following the call-path, or the one in line 7 that filters S. Let d′ be the first depth level at which line 4 is
	triggered or d + 1 if it never does.
	Lemma E.9. If line 7 triggers at ID(T i , S i , Gi ), then V i \ S i ⊊ C i ⊊ V i . In particular, S i+1 ⊊ S i .

	Proof. V i \ S i ⊂ C i ⊂ V i and it is a maximal C-component in Gi by construction. If C i = V i \ S i , then V i \ S i ∈ C(Gi )
	and line 6 would have triggered. If C i = V i , then V i ∈ C(G) and line 5 would have triggered. Finally, since C i ̸= V i and
	C i ⊋ V i \ S i , then S i ∩ C ⊊ S i .
	Lemma E.10. Some observations that will become relevant throughout the following discussion are:

	• Line 1 never triggers along the failing call-path, and ∀i ≤ d, S i ̸= ∅; otherwise, the call-path would not end at line 5.

	• Line 6 never triggers along the failing call-path; otherwise, the call-path would not end at line 5.

	• Line 5 does not trigger along the failing call-path for depths i < d.

	• G can only have nodes removed: Gi+1 ⊆ Gi , ∀i < d.

	• We can only remove nodes from the local set of intervened variables S on lines 2 and 7, while also removing them from
	the local graph G.

	• We can only add nodes to the local set of intervened variables S on lines 3 and 4, while also removing them from the
	set of unused nodes U := V \ (T ∪ S).

	• The set of unused nodes can never grow: U i+1 ⊆ U i , ∀0 ≤ i < d.

	• T does not change until line 4 is called: ∀i ≤ d′ , T i = {Y }.


	22
	Exactly Computing do-Shapley Values

	Lemma E.11. Under the previous assumptions, line 4 can trigger at most once.

	′
	Proof. Assuming that line 4 triggers at least once, let d′ < d be the depth of its first call, and C d the C-component
	′ ′ ′ ′ ′ ′
	whose recursive call we follow along the call-path. Right after that, T d +1 = C d , S d +1 = V d \ C d , and U d +1 =
	′ ′ ′
	V d +1 \ (T d +1 ∪ S d +1 ) = ∅. Assume there is a minimal d′′ > d′ in which line 4 triggers again. Then, since only line
	′′ ′ ′ ′′ ′′ ′′ ′ ′′
	4 can change T , T d = T d +1 = C d . Note that V d \ S d = T d = C d (otherwise U d would increase). Therefore,
	′′ ′′ ′′ ′′ ′ ′ ′ ′ ′′ ′ ′
	C(Gd [V d \ S d ]) = C(Gd [C d ]) = C(Gd [C d ]) = {C d } since Gd ⊆ Gd and C d is a maximal C-component in
	′ ′ ′ ′ ′ ′
	Gd [V d \ S d ] ⊋ Gd [C d ], which means that line 4 cannot trigger again. In particular, T i = C d , ∀i : d′ < i ≤ d.

	Lemma E.12. Under the previous assumptions, if V = AnG (Y ) and X is closed (i.e., X = X ∪ (V \ AnGX (Y ))), then
	line 3 never triggers.

	Proof. By the fact that the closure of a closed set is itself, line 3 cannot trigger at depth 0. Let us prove the statement by
	induction.
	Firstly, consider a depth i, 0 < i < d′ , in which line 3 is triggered, while assuming it has not been triggered before.
	From Lemma E.10, T i = {Y }. For depth i, it must be that W i := (V i \ S i ) \ AnGi (Y ) ̸= ∅, with nodes w ̸∈ S i and
	Si
	w ̸∈ AnGi (Y ), but w ∈ AnGi (Y ) (since we skip line 2 to trigger 3), so there are directed paths from w to Y , all blocked
	Si
	by S i . Let us now study depth i − 1. Since w ̸∈ S i and S i−1 ⊇ S i , if w ∈ S i−1 it must have been removed by lines
	2 or 7, but that would also remove it from V i , which is not the case, so we know that w ̸∈ S i−1 . Additionally, if we
	assumed that w ̸∈ AnGi−1 (Y ), since w ̸∈ S i , then w ∈ W i−1 but because line 3 did not trigger at depth i − 1, W i−1 = ∅.
	S i−1
	Consequently, w ∈ AnGi−1 (Y ) and w ̸∈ S i−1 , so there are directed paths from w to Y unblocked by S i−1 , going through
	S i−1
	nodes in a set Z ⊆ V i−1 \ S i−1 , which all must have disappeared from Gi to make it so w ̸∈ AnGi (Y ). Since line 2
	Si
	preserves all directed paths to Y , this can only happen if line 7 was triggered at depth i − 1. However, this cannot be the
	case either: the C-component C i−1 ⊋ V i−1 \ S i−1 preserves all non-intervened nodes, which is the case for Z. Therefore,
	it must be that our initial assumption was false, W i is empty, and so line 3 was not triggered at depth i < d′ after all.
	′ ′ ′
	For depth d′ , we naturally skip line 3 to reach line 4. Afterwards, V d +1 = T d +1 ⊔ S d +1 so ∀d′ < i ≤ d, U i :=
	V i \ (T i ∪ S i ) = ∅ (Lemma E.10), so W i = ∅, and line 3 is never called either.

	Lemma E.13. Let G be an ADMG over V, with a single Y ∈ V target node. If ∃X ⊆ V \ {Y } such that PX (Y ) is
	not identifiable, let ID(T d , S d , Gd ) be the last call resulting in the hedge given by Lemma E.8. Then S d ∩ (X ∪ (V \
	AnGX (Y ))) ̸= ∅.

	Proof. Let X ′ be the closure of X, X ′ := X ∪ (V \ AnGX (Y )) (here denoted X ′ instead of X to avoid ambiguity of
	notation), and let us prove that S d ∩ X ′ ̸= ∅. Note that if line 2 or 3 trigger on the first calls, we end up in a recursive call
	ID({Y }, S i , Gi ) where V i = AnG (Y ) and S i = AnG (Y ) ∩ (X ∪ (V \ AnGX (Y ))), so we can assume without loss of
	generality that V = AnG (Y ) and X ′ = X at the start of the call-path. Consequently, S 0 ∩ X ′ = X ′ ̸= ∅ trivially. Let us
	proceed by induction, proving that ∀i < d, S i ∩ X ′ ̸= ∅ implies that S i+1 ∩ X ′ ̸= ∅, and then so will be the case for S d ,
	which will prove the lemma.
	Let us now consider any depth level 0 < i ≤ min(d, d′ ) and assume that S i−1 ⊆ X ′ . Let us study what happens
	at depth i − 1. Lines 1, 3, 4, and 6 cannot trigger (by Lemmas E.10 and E.12 and the fact that i ≤ d′ ). If line 2
	were to remove any nodes, it would still result in a non-empty proper subset S i ⊊ S i−1 ⊆ X ′ . If line 7 triggered,
	S i := S i−1 ∩ C i−1 ⊊ S i−1 ⊆ X ′ and S i ̸= ∅ by Lemma E.9. In all cases, the next recursive S is not empty and only
	contains nodes in X ′ : ∅ ̸= S i+1 ⊊ S i ⊆ X ′ .
	′
	If line 4 never triggers, we have already proved the result. Otherwise, d′ < d, and C d is the C-component whose recursive
	′ ′ ′ ′ ′ ′ ′ ′
	call we follow along the call-path. In particular, V d +1 = V d , T d +1 = C d , S d +1 = V d \ C d ⊋ S d , so it contains
	′ ′
	elements of X ′ and outside X ′ (because the nodes in X ′ \ S d have been removed from Gd as well). Additionally,
	∀i > d′ , U i = ∅, and can never increase.
	′ ′ ′
	For d′ ≤ i ≤ d, let us define S i = Ai ⊔ B i ̸= ∅, with Ai := S i ∩ X ′ and B i := S i \ X ′ . Note that Ad = S d , B d = ∅, and
	′ ′ ′ ′ ′ ′ ′ ′ ′ ′
	Ad +1 = S d , B d +1 = (V d \C d )\Ad ̸= ∅, since S d +1 = V d \C d ⊋ S d ⊆ X ′ . Additionally, ∀i > d′ +1, Ai ⊆ Ai−1

	23
	Exactly Computing do-Shapley Values

	and B i ⊆ B i−1 since we can only remove nodes at this point, given that line 3 and line 4 will not run again (Lemmas E.12
	and E.11). Let us prove that if ∀i : d′ < i < d, Ai ̸= ∅, then Ai+1 ̸= ∅, for which we must check lines 2 and 7.
	If line 2 was triggered at step i and Ai+1 = ∅, the next recursion level would have T i+1 = T i , S i+1 = B i+1 ̸= ∅ and
	Gi+1 = Gi [AnGi (T i )] ⊆ Gi . At level i + 1, line 6 would trigger: neither line 3 nor line 4 can trigger again; if we
	′ ′
	assume that line 5 triggers, then V i+1 ∈ C(Gi+1 ), but B i+1 ⊆ B d +1 and no node in B d +1 belonged in the same maximal
	d′ d′ d′ d′ i+1 d′ ′
	C-component as C in G [V \ A ], then all bidirected paths from B to C were blocked by Ad , and now that
	i+1 i+1 i+1 i+1 d′
	A = ∅, these paths are cut; finally, for line 6, if V \S =T = C were not a maximal C-component of the
	induced subgraph Gi+1 = Gi [AnGi (T i )], it must be that a node b ∈ S i+1 = B i+1 is connected through a bidirected path
	′
	to C d in this graph, which we have just proved to be false, hence proving that the call would return TRUE at line 6. By
	′
	contradiction, this proves that line 2 would have not removed all of Ad +1 ⊆ X ′ .
	′
	Finally, if line 7 was triggered at step i and Ai+1 = ∅, when before it was not, necessarily B i+1 ̸= ∅, and ∀c ∈ T i = C d ,
	′ ′
	∀b ∈ B i+1 = B i ∩ C i , there are bidirected paths connecting c and b in Gi ⊋ Gi+1 , and all are intersected by S d = Ad
	′
	(otherwise b ∈ C d ). Consequently, either these intersecting nodes are in Ai , in which case they would not have been
	removed from Ai+1 , or they are not in Ai , in which case b would have been removed as well for its paths would be cut.
	Both cases contradict the assumption that Ai+1 = ∅.
	Bringing everything together and by induction, ∅ ⊊ Ad ⊆ X ′ , proving the lemma.

	We now have all we need to prove the theorem.

	Proof of Theorem E.7. Finally, let us finish the proof by showing that if (F, F ′ ) is the R-rooted hedge for PS (T ) found at
	the end of the call-stack, ∀s ∈ S ∩ X ′ , with X ′ := X ∪ (V \ AnGX (Y )) the closure of X, then (F, F ′ ) is also a hedge
	for P{s} (Y ). Note that the hedge still fulfills the conditions F ′ ⊆ F, F ∩ {s} ̸= ∅, F ′ ∩ {s} = ∅, both R-rooted, both
	C-forests. So now we only need to check that R ⊆ AnGs (Y ), but if one such r ∈ R were not in AnGs (Y ) ⊇ AnGX ′ (Y ),
	then r would belong in X ′ by definition of the closure of X and the fact that the closure of a closure is itself. Additionally,
	throughout the call-stack, r would have never left the set of intervened nodes without leaving the graph itself, hence r ∈ S,
	contradicting the fact that S ∩ R = ∅ by construction (see Lemma E.8). Therefore, it must be that R ⊆ AnGs (Y ), proving
	that (F, F ′ ) is a hedge for P{s} (Y ). By Theorem 4 in (Shpitser & Pearl, 2006), P{s} (Y ) is not identifiable.
	Corollary E.14. Any do-Shapley value ϕi for i ∈ [d] is (non-parametrically) identifiable if, and only if, all singleton
	coalition probabilities (P{k} (Y ))k∈[d] are (non-parametrically) identifiable.

	Proof. If all singleton coalitions {k} ⊆ [d] have identifiable probability terms P{k} (Y ), there cannot be any coalition
	S ⊆ [d] for which PS (Y ) is not identifiable (otherwise, by Theorem E.7, ∀k ∈ S ∪ (V \ AnGS (Y )), P{k}P (Y ) would not be
	r
	identifiable). Then, all the respective ν(S) = E[Y \| do(S = s)] are identifiable, and consequently, ϕi = j=1 ν(cj )wi (cj )
	is also identifiable. Conversely, if one such P{k} (Y ) were not identifiable, its ν({k}) term cannot be either, nor can ϕk .




	24
	Exactly Computing do-Shapley Values

	F. Extensions of the Shapley value
	The Shapley value was extended in multiple ways. Semivalues (Dubey et al., 1981) , such as the Banzhaf value (Banzhaf III,
	1964), extend the Shapley values to alternative weighting schemes (qs )s=0,...,n−1 ≥ 0 as
	X
	ϕqi = [ν(S ∪ i) − ν(S)]q\|S\| . (12)
	S⊆[d]\i

	If q is a probability distribution over 2[d] , then they are also referred to as cardinal-probabilistic values (Fujimoto et al.,
	2006). By replacing the weights in Equation (4), we can derive an efficient computation for any semivalue.
	Another line of work extends the Shapley value to higher-order interactions, known as the Shapley interaction index
	(Grabisch & Roubens, 1999), and defined by
	\|U \|
	X X
	ϕU = ∆U (S)p\|S\| with ∆U (S) := (−1)\|U \|−\|S\| ν(S ∪ L),
	S⊆[d]\U L⊆U

	1
	and pus := (d−u+1)· . The discrete derivative ∆U (S) thereby measures the interaction of U in the presence of S, and
	(d−u
	s )
	directly extends the marginal contribution. We now utilize a result by Zern et al. (2023b)[Proposition 1] to efficiently
	compute the Shapley interaction index for value functions of the shape 1[S ⊆ S ⊆ S].
	Proposition F.1 (Zern et al. (2023a)). Given subsets S ⊆ S ⊆ [d] and value function ν(S) = 1[S ⊆ S ⊆ S], the Shapley
	1 a+b −1

	interaction index is given by the weights ωa,b := a+b+1 a and

	ϕU = (−1)\|U ∩([d]\S)\| ω\|S\|−\|S∩U \|,\|[d]\(S∪U )\| ,

	if U ⊆ A ∪ ([d] \ B), and ϕU = 0 otherwise.

	Notably, the weights ω can be precomputed. Consequently, we obtain the following result by the linearity of the Shapley
	interaction index (Grabisch & Roubens, 1999).
	Proposition F.2. The do-Shapley interaction index is given by
	r
	X
	ϕU = ν(cj )(−1)\|U ∩([d]\S j )\| ω\|S \|−\|S j ∩U \|,\|[d]\(S j ∪U )\| .
	j
	j=1


	Proof. We define νj (S) := 1[S j ⊆ S ⊆ S j ] for each irreducible set from j = 1, . . . , r. Furthermore, we denote ϕU [ν] as
	the Shapley interaction index with respect to ν. Then, by linearity (Grabisch & Roubens, 1999) of ϕU , we obtain
	r
	X r
	X r
	X
	ϕU [ν] = ϕU [ ν(cj ) · 1[S j ⊆ S ⊆ S j ]] = ν(cj )ϕU [νj ] = ν(cj )(−1)\|U ∩([d]\S j )\| ω\|S \|−\|S j ∩U \|,\|[d]\(S j ∪U )\| .
	j
	j=1 j=1 j=1




	With the efficient computation of the Shapley interaction index (Grabisch & Roubens, 1999), we can directly extract the
	n-Shapley values (Lundberg et al., 2018a; Bordt & von Luxburg, 2023) using the following recursion:

	
	ϕU if \|U \| = n,
	ΦnU := n−1 P
	if \|U \| < n,
	ΦU + Bd−\|U \| K⊆[d]\U ϕU ∪K
	\|K\|+\|S\|=n

	with Φ1i := ϕi for all i ∈ [d]. The n-Shapley values have first been introduced by Lundberg et al. (2018b), and were later
	genearlized to arbitrary order n (Bordt & von Luxburg, 2023). Importantly, they satisfy the generalized efficiency axiom for
	Shapley interactions (Bordt & von Luxburg, 2023), i.e.
	X
	ΦnU = ν([d]),
	U ⊆[d]:\|U \|≤n


	25
	Exactly Computing do-Shapley Values

	where we defined Φ0∅ := ν(∅).
	do-Shapley Interactions for SCMs. Generalizations of the Shapley value to higher-order interactions provide a principled
	framework for explanations with varying degrees of granularity and expressivity. To illustrate this for do-Shapley values and
	their interaction-based extensions, we compute Shapley interactions using shapiq (Muschalik et al., 2024a) for SCMs
	derived from four datasets from the TALENT benchmark (Liu et al., 2025). Following Section 6, the SCMs are learned
	from data using GRaSP (Lam et al., 2022), with the corresponding variables described in Tables 1 to 4. The resulting
	do-Shapley interactions are visualized in Figures 8 to 11. First-order explanations recover the standard do-Shapley values,
	while the highest-order interactions correspond to the Möbius transform of the value function. We present the shapiq
	explanations as overlays on the learned SCMs, where node sizes represent main effects and edge or hyperedge widths encode
	interaction strength. The color indicates the direction of the effects (blue denotes a negative interaction and red a positive
	interaction). While first-order do-Shapley values summarize aggregated causal effects of individual features, increasing
	the interaction order yields progressively finer-grained insights into the causal structure. At the same time, the growing
	number of interaction terms poses interpretability challenges, motivating application-specific post-processing and selection
	of relevant interaction orders.


	X6 X8 X6 X8 X6 X8 X6 X8


	X2 X3 X2 X3 X2 X3 X2 X3


	X5 X7 Y X5 X7 Y X5 X7 Y X5 X7 Y



	X4 X1 X4 X1 X4 X1 X4 X1




	SCM do-Shapley Values do-Shapley Interactions do-Shapley Interactions
	(order 1) (order 2) (order 8)
	Figure 8. do-Shapley values and interactions for B RAZILIAN HOUSES REPRODUCED of increasing order (feature names in Table 1). The
	size of the nodes and edges (hyperedges) denotes the strength of the effect. The color denotes the direction (blue negative, red positive).



	X4 X7 X4 X7 X4 X7 X4 X7



	X3 X3 X3 X3
	X1 Y X1 Y X1 Y X1 Y
	X6 X6 X6 X6

	X5 X5 X5 X5
	X2 X2 X2 X2




	SCM do-Shapley Values do-Shapley Interactions do-Shapley Interactions
	(order 1) (order 2) (order 7)
	Figure 9. do-Shapley values and interactions for FOREX AUDJPY- HOUR -H IGH of increasing order (feature names in Table 4). The size
	of the nodes and edges (hyperedges) denotes the strength of the effect. The color denotes the direction (blue negative, red positive).




	26
	Exactly Computing do-Shapley Values




	X1 X1 X1 X1



	X3 X4 X5 Y X3 X4 X5 Y X3 X4 X5 Y X3 X4 X5 Y



	X2 X2 X2 X2




	SCM do-Shapley Values do-Shapley Interactions do-Shapley Interactions
	(order 1) (order 2) (order 5)
	Figure 10. do-Shapley values and interactions for L APTOP P RICES DATASET of increasing order (feature names in Table 3). The size of
	the nodes and edges (hyperedges) denotes the strength of the effect. The color denotes the direction (blue negative, red positive).




	X2 X4 X2 X4 X2 X4 X2 X4


	X5 Y X5 Y X5 Y X5 Y


	X1 X3 X1 X3 X1 X3 X1 X3




	SCM do-Shapley Values do-Shapley Interactions do-Shapley Interactions
	(order 1) (order 2) (order 5)
	Figure 11. do-Shapley values and interactions for Y EAST of increasing order (feature names in Table 2). The size of the nodes and edges
	(hyperedges) denotes the strength of the effect. The color denotes the direction (blue negative, red positive).

	Node Feature Name
	X1 hoa (BRL)
	X2 fire insurance (BRL)
	X3 parking spaces
	X4 rent amount (BRL)
	X5 rooms
	X6 property tax (BRL)
	X7 target
	X8 bathroom
	Y area
	Table 1. Variables for B RAZILIAN HOUSES REPRODUCED: d = 8 input features and 9 nodes in total (including target Y ).


	Node Feature Name
	X1 alm
	X2 nuc
	X3 vac
	X4 gvh
	X5 mcg
	Y mit
	Table 2. Variables for YEAST: d = 5 input features and 6 nodes in total (including target Y ).



	27
	Exactly Computing do-Shapley Values




	Node Feature Name
	X1 N0
	X2 N1
	X3 N5
	X4 target
	X5 N4
	Y N2
	Table 3. Variables for L APTOP P RICES DATASET: d = 5 input features and 6 nodes in total (including target Y ).




	Node Feature Name
	X1 Ask Low
	X2 Bid Low
	X3 Bid Close
	X4 Ask Open
	X5 Ask Close
	X6 Bid Open
	X7 Ask High
	Y Bid High
	Table 4. Variables for FOREX AUDJPY- HOUR -H IGH: d = 7 input features and 8 nodes in total (including target Y ).




	28
	Exactly Computing do-Shapley Values

	G. Additional Experiments

	10 0
	Estimator Convergence (Aggregated)

	10 −1

	Relative MSE
	10 −2

	10 −3 Method
	doRegressionMSR
	10 −4 doLeverageSHAP
	RegressionMSR
	10 −5 LeverageSHAP
	Budget = r
	10 −6 0.2 0.4 0.6 0.8 1.0
	Budget Ratio m/r
	Figure 12. Estimator Convergence (Aggregated), Clipped View. The Relative Mean Squared Error (MSE) of Shapley value estimates
	versus the budget ratio m/r, aggregated across all datasets. This is the same plot as Figure 5, but where we have adjusted the view to
	more clearly show the distinctions in estimator performance for when m/r ≤ 1.


	Computation Cost vs. Budget
	Method
	doRegressionMSR
	doLeverageSHAP
	10 0
	Computation Time (s)




	RegressionMSR
	LeverageSHAP
	Budget = r


	10 −1




	0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00
	Budget Ratio m/r
	Figure 13. Computational Cost. Average wall-clock time (seconds) versus budget ratio (m/r). The structure-aware estimators (i.e.
	“do”-variants) incur a consistent runtime overhead compared to their structure-agnostic counterparts. This additional cost represents the
	time required for graph traversal and boundary sampling to identify distinct equivalence classes. The more computationally demanding
	structural exploration is the necessary trade-off to achieve the orders-of-magnitude reduction in estimation error seen in e.g. Figure 5.




	29
	Exactly Computing do-Shapley Values




	Table 5. Relative MSE statistics by budget ratio (m/r).

	Metric LeverageSHAP doLeverageSHAP RegressionMSR doRegressionMSR
	Budget Ratio m/r = 0.25
	Mean 1.5e-1 1.2e-1 3.5e-1 6.0e-2
	Median 8.2e-3 9.8e-3 7.9e-3 3.8e-4
	Q1 (25%) 8.5e-4 4.1e-4 1.5e-4 8.1e-8
	Q2 (50%) 8.2e-3 9.8e-3 7.9e-3 3.8e-4
	Q3 (75%) 2.2e-1 5.9e-2 3.0e-1 1.1e-2
	Q4 (Max) 2.5e+00 5.6e+00 2.4e+00 1.2e+00
	Budget Ratio m/r = 0.5
	Mean 5.8e-2 6.8e-2 1.4e-1 2.5e-2
	Median 1.9e-3 4.8e-3 8.8e-4 1.1e-5
	Q1 (25%) 2.0e-4 1.4e-4 1.5e-5 5.9e-9
	Q2 (50%) 1.9e-3 4.8e-3 8.8e-4 1.1e-5
	Q3 (75%) 1.3e-2 1.9e-2 9.7e-3 1.4e-3
	Q4 (Max) 1.2e+00 5.6e+00 2.0e+00 7.0e-1
	Budget Ratio m/r = 0.75
	Mean 1.8e-2 9.1e-3 5.5e-2 6.1e-3
	Median 4.8e-4 9.9e-4 1.4e-4 5.7e-7
	Q1 (25%) 7.7e-5 2.2e-5 2.8e-6 3.8e-10
	Q2 (50%) 4.8e-4 9.9e-4 1.4e-4 5.7e-7
	Q3 (75%) 2.5e-3 6.0e-3 2.3e-3 1.5e-4
	Q4 (Max) 6.6e-1 3.6e-1 2.0e+00 3.3e-1
	Budget Ratio m/r = 1.0
	Mean 6.2e-3 4.2e-6 4.8e-3 2.0e-5
	Median 2.4e-4 4.1e-29 4.4e-6 3.5e-13
	Q1 (25%) 2.8e-5 1.1e-30 2.0e-7 2.6e-14
	Q2 (50%) 2.4e-4 4.1e-29 4.4e-6 3.5e-13
	Q3 (75%) 1.2e-3 6.1e-26 5.1e-4 2.6e-12
	Q4 (Max) 3.3e-1 3.7e-4 3.0e-1 3.7e-3




	30