Fast Proxy Experiment Design for Causal Effect Identification
Authors: Sepehr Elahi
Sina Akbari
Jalal Etesami
Negar Kiyavash
Patrick Thiran
Venue: NeurIPS 2024 poster (2024)
Keywords: Causal Inference
Identifiability
Experiment design
Primary area: causal_inference
TL;DR: We present novel, highly efficient algorithms for designing minimum-cost proxy experiments (interventions) to identify causal effects, significantly outperforming the s.o.t.a.

Abstract: Identifying causal effects is a key problem of interest across many disciplines. The two long-standing approaches to estimate causal effects are observational and experimental (randomized) studies. Observational studies can suffer from unmeasured confounding, which may render the causal effects unidentifiable. On the other hand, direct experiments on the target variable may be too costly or even infeasible to conduct. A middle ground between these two approaches is to estimate the causal effect of interest through proxy experiments, which are  conducted on variables with a lower cost to intervene on compared to the main target. In an earlier work, we studied this setting and demonstrated that the problem of designing the optimal (minimum-cost) experiment for  causal effect identification is NP-complete and provided a naive algorithm that may require solving exponentially many NP-hard problems as a sub-routine in the worst case. In this work, we provide a few reformulations of the problem that allow for designing significantly more efficient algorithms to solve it as witnessed by our extensive simulations. Additionally, we study the closely-related problem of designing experiments that enable us to identify a given effect through valid adjustments sets.

Fast Proxy Experiment Design for Causal Effect Identification
Sepehr Elahi*
Sina Akbari' EPFL, Switzerland sina. www.ri@epalllc..om.. ch
Jalal Etesami TUM, Germany
EPFL, Switzerland
sepehr elahi@epfl.co
J. etesami @tum de
Negar Kiyavash
Patrick Thiran
EPFL, Switzerland
EPFL, Switzerland
negar.kiyavashen www.:kyaaaass@pl...d.
patrick. taaickk.thirannepp..cc.
Abstract
Identifying causal effects is a key problem of interest across many disciplines. The two long-standing approaches estimate causal effects observational and experimental (randomized) studies. Observational studies can suffer from unmeasured confounding, which may render the causal effects unidentifiable. On the other hand, direct experiments on the target variable may be too costly or even estimate
infeasible conduct. A middle ground between these approaches the causal effect of interest through proxy experiments, which are conducted on variables with lower cost to intervene compared the main target. In earlier work, we studied this setting and demonstrated that the problem of designing the optimal (minimum-cose experiment for causal effect identification is NP-complete and provided naive algorithm that may require solving exponentially many NP- hard problems as a sub-routine the worst case. In this work, we provide few reformulations of the problem that allow for designing significantly more efficient algorithms solve as witnessed by our extensive simulations. Additionally, we study the closely-related problem of designing experiments that enable us to identify given effect through valid adjustments sets.
Introduction
Identifying causal effects is central problem of interest across many fields, ranging from epidemi- ology all the way economies and social sciences.
10
8
Ours
Duration
6
S.O.T.A
While conducting randomized (controlled) trials provides framework to analyze and estimate the causal effects of interest, such experiments are of- ten impractical due various limitations, including financial, logistical. and ethical constraints. Even when they are practical, gathering sufficient data to draw statistically significant conclusions is often challenging due to the high costs.
2
00000
20
40
80
100
Number of variables
Figure 1: The average runtime our approach compared with the state-of-the-art (S.O.T.A) from Akbari et al. [2022).
Costs can arise multiple forms: financial costs (e.g., implementing costly interventions), time re- sources (e.g., upgrading infrastructure), and other
Authors contributed equally.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

U1
X
22
U1
S2
W
22
UB
V2
mm
US
Y
(a)
(b)
(c)
(d)
Figure 2: (a): Causal graph of Example 1 (b):
Transformed graph when considering identifiability of Piz.es (V), with S = (w, y). J (c): A causal graph with 2d minimal hedges. (d): Running example.
logistical constraints such human resources. Moreover, certain experiments might be unethical or outright unfeasible, such as exposing patients to harmful treatments, and hence have infinite cost.
Observational data, which is usually more abundant and accessible, offers an alternative avenue. However, observational studies bring a new challenge: the causal effect may not be identifiable due to unmeusured confounding, making it impossible to draw inferences from the observed data [Pearl] 2009 Hernán and Robins 2006). A middle ground between observational and experimental approaches to fuse data from both types of studies [Bareinboim and Pearl 2016 Athey et al.) 2020]. For example, citics might introduce low-emission zones as a proxy experiment before banning diesel vehicles (Dey et al. 2018). or governments might impose regional sugary drink taxes to estimate the effects of nationwide policies Redondo et al. (2018). Several works have studied the achievability of identification from ensembles of observational and experimental data [Bareinboim and Pearl 2012
Lee et al. 2020a Kivva et al., [022] Jamshidi et al., 2024]. Our previous work [Akbari et al.] [022]
was the first to investigate the problem of designing proxy experiments to identify causal effect that is not identifiable from observational data alone.
To illustrate the need for proxy experiments, consider the following drug-drug interaction example, based on the example in Lee et al. [2020a].
Example 1. (Complex Drug Interactions and Cardiovascular Risk) Consider simplified example involving the interaction between a new antihypertensive therapy (V1), anti- diti-diabeicc medications (V2). renal function modulators (V3), and their effects on blood pressure (w) and cardiovascular disease (y). Blood pressure and cardiovascular health are closely linked. The antihypertensive therapy Vi directly influences the need for renal function modulators V2, and v3 in lurn directly affects blood pressure w. Additionally, anti miti-diabelic medicutions v2 reduce the risk of cardiovascular disease y by controlling blood sugar levels, while blood pressure directly impacts y. Unmeasured factors confound these relationships: shared health conditions can inftuence the prescription of both U1 and v3 lifestyle factors affect both V1 and w; and common conditions like metabolic syndrome can impact both 01 and U2. Fig. () illustrates the resulting causal graph, whose directed edges represent direct causal effects, and bidirected edges indicate unmeasured confounders. Suppose we are interested in estimating the intervention effects of 02 and Uy on y, which are not identifiable from observational data alone. Moreover, cannot directly intervene on these variables because 12 and Uy essential for managing immediate, tife-threateing conditions. Instead, we can intervene on Un, which is a feasible and safer approach due to the broader range of trealment options and more manageable risks associated with adjusting antiypertensive therapy. As we shall see, intervention on vn suffices for identifying the effects of 02 and V3 on y.
Selecting the optimal set of proxy experiments is not straightforward in general. In particular, in [Akbari et al., [022) we proved that the problem of finding the minimum-cost intervention set to identify a given causal effect, hereon called the MCID problem, is NP-complete and provided a naive algorithm that requires solving exponentially many instances of the minimum hitting set problem in the worst case. As the minimum hitting set problem is NP-complete itself, our earlier algorithm in [Akbari et al. 2022 can become computationally intractable even for graphs with a modest number of vertices. Moreover, this algorithm was tailored to specific class of causal effects in which the effect of interest is functional of an interventional distribution where the intervention is made on

---

every variable except one district of the causal graph For general causal effect, the complexity of this algorithm includes an additional (super-)exxg jexponenax multiplicative factor, where the exponent is the number of districts.
In this work, we revisit the MCID problem and develop tractable algorithms by reformulating the problem as instances of well-known problems, such as the weighted maximum satisfiability and integer linear programming problems. Furthermore, we analyze the problem of designing minimum cost interventions to obtain a valid adjustment set for a query. This problem not only merits attention in its own right, but also serves as proxy for MCID. Our contributions are as follows:
We formulate the MCID problem in terms of partially weighted maximum satisfiability, integer linear programming, submodular function maximization, and reinforcement learning problem. While our main focus on the former two reformulations, we state the others in Appendix [
We propose new, and in practice, much faster (up to six orders of magnitude) algorithms for solving the problem optimally using our reformulations. Moreover, the computational complexity of our proposed algorithms scales quadratically in the number of districts, a significant improvement over the super-exponential growth exhibited by existing algorithms see Remark 2
We formulate and study the problem of designing minimum-cost experiments for identifying given effect through finding valid adjustments set. Besides the practical advantages of valid adjustment, including ease of interpretability and tractable sample complexity, this approach enables us design a polynomial-ting heuristic algorithm for the MCID problem that outperforms the heuristic algorithms provided in Akbari et al. [2022].
We present new numerical experiments that demonstrate the exceptional speed of our exact algorithms when compared to the current state-of-the-aa along with our heuristic algorithm showcasing superior performance over previous heuristic approaches.
2 Problem formulation
We begin by reviewing relevant graphical definitions. An acyclic directed mixed graph (ADMG) is graph with directed (-+) and bidirected (++) edges such that the directed edges form no cycles Richardsson 2003]. We denote an ADMG ς by a tuple g = (V, É. E), where V, E, and E represent the set of vertices, directed edges, and bidirected edges, respectively. Note that E is set of ordered pairs of vertices in V, whereas E is a set unordered pairs of vertices.
Vertices of G represent variables of the system under consideration, while the edges represent causal relations between them. We use the terms 'variable' and 'vertex' interchangeably. When (y,x) E F,, we say is a parent of x and x is a child of y. The set of parents of X C V denoted by Pa(X)= = {u (1,,x) E for some X) X. We denote by G[W], the induced subgraph of G over vertices W C V. A subset S of V is said to form a district in 9 if S is a maximal set such that any pair of vertices x, y E S are connected through a bidirected path æ ++ words, G[S] is a connected component through its bidirected edges. We say I E V is an ancestor of S C V if there of S in the subgraph G G[W] by Anow (S). Note that S C (SC)(()) When W = V, we drop the subscript for ease of notation.
++ y G[S). In other
directed path x + + for some S. We denote the set of ancestors
Let X,Y C V be two disjoint sets of variables. The probability distribution of Y under a (possibly hypothetical) intervention on X setting its value to x is often represented as either (( using Rubin's 's potential outcomes model (Rubin 1974]. or P(Y do(XX x)) using Pearl's do operator Pearl 2009]. We will adopt the shorthand P. (Y) to denote this interventional distribution
Definition (Identifiability). An interventional distribution Pxx(Y) is identifiable given an ADMG g and the intervention set family I = (II....,IA)) I.), with I, C V. over the variables corresponding to g, xY)) is uniquely computable as a functional of the members of (Pz(-) I I I).
"See Section 2 the definition of district.
"This interventional distribution is often mistakenly referred to as the causal effect of X on Y. However, a causal effect, such as an average treatment effect or quantile treatment effect, is usually a specific functional of this probability distribution for different values of x.
3

---

Remark 1. It is common in the literature to define identifiability with respect to observational data only (i.e., when I {I,- 0}). Our definition above follows what is known as the 'general identifiability from Lee et al. 2020ay.
We will now formally define hedge, which, as we will see shortly after, is central to deciding the identifiability of an interventional distribution given the data at hand.
Definition 2 (Hedge). Let S C V be district in G[ We say W 2 S forms a hedge for S (i) W a district in G[W), and (ū) every vertex w E W is an ancestor of S in G[W] (i.e, W = Aucw(S)) We denote by Hg(5) the set of hedges formed for S in G.
For example, in Fig. B()) S has two hedges given by Hş(S)= = {s U (03, v1); 1 SU {vz, v1, 22) }. Definition 3 (Hedge hull Akbari et al. 2022). Let S be a district in ADMG G. Also let Hg( be the set of all hedges formed for S in G. The union of all hedges in HS(S), denoted by Ho UWe)o(S) W, is said to be the hedge hull of S in g.
For instance, in Fig. 2 d). the hedge hull of S = {is} is Hc(Si) = {31, 82, U1 U2 U3, U4 8t} and the hedge hull of S { is Hg((2)) = {s2, V3 When set S consists of more than one district, we simply define the hedge hull of S as the union of the hedge hulls of each district of S. The hedge hull of set can be found through series of at most [V| depth-firtt-searche seachhs.... In the latter example, the hedge hull of S = {s1, 82} is My(() = {$1, $2, 21, 02 F3 U1, Us}. For the sake of completeness, we have included the algorithm for finding hedge hull in Appendix B.
The following proposition from Lee et al. [2020a] and Kivva et al. [2022 establishes the graphical criterion for deciding the identifiability of causal effect given set family of interventions.
Proposition 1. Let G be an ADMG over the vertices V. Also let X, S be disjoint sets of variables. Define S = Ancv (Y), and let S = { S be the (unique) set of districts in ([S). The interventional distribution Ix FY( is identifiable given G and the intervention set family I [I, [I,...., I. if and only if for every St E S. there exists an intervention set Iy II such that (i) I S5+ = 9, and (ii) there is no hedge formed for St in GIV Ix].
Note that there is no hedge formed for St in GIV Ix] if and only if I' hits every hedge of Se (i.e.,
for any hedge W E H.t(St). I nw * 0). For ease of presentation, we will use I2 _ Se to denote that Iy n St and Zg hits every hedge formed for Sg. For example, given the graph in Fig. dd and with 5 = {S1, S2}. an intervention set family that hits every hedge is I = {{32), {ca)).
Minimum-cost intervention for causal effect identification (MCID) problem. Let C V R20 U be a known function" indicating the cost of intervening on each vertex U E V. An infinite cost is assigned to variables where an intervention is not feasible. Given & and disjoint sets X,Y C V. our objective is to find a set family I' with minimum cost such that PY is identifiable
given I': that is, for every district Se of S, there exists Ia such that I, id, Se. Since every I E I a subset of V, the space of such set families is the power set of the power set of V.
To formalize the MCID problem, we first write the cost of set family I as C(I) = EIez Evez C(v), where with slight abuse of notation, we denoted the cost of I by C(T). The MCID problem then can be formalized as follows.
I" E argmin C(I) s.t. V (BI E I: IEZ2V
Is id St).
(1)
where S = (S),... ...., S.) is the set of districts of S = A (Y), and 22 represents the power set of the power set of V. In the special case where comprises a single district, the MCID problem can be presented in simpler way.
Proposition 2 (Akbari et al. (022). If Ancv (Y) comprises a single district S = {S} = S}. then the optimization in equivalent to the following optimization:
I E argmin C(I) s.t. VW E Hg(S): I EnW#0.
(2)
IE2V/8
That is, the problem reduces to finding the minimum-com set that 'hits' every hedge formed for S.
'Although it only makes sense to assign non non-negative costs to interventions, adopting non- non-negatvve costs is without loss of generality. If certain intervention costs are negative, one can shift all the costs equally so that the most negative cost becomes zero. This constant shift would not affect the minimization problem in any way.

---

Recall example Example 1 we were interested in finding the least costly proxy experiment to identify the effect of bi and Vy on y. By Proposition 2 this problem equivalent to finding an intervention set with the least cost (i.e., a set of proxy experiments) that hits every hedge of S = {v. w) in the
transformed graph (Fig. 2 b)). If C(u1) < C(r)). then the optimal solution would be T (m))
In the remainder of the paper, we consider the problem of identification of Px (Y) for a given pair (X, Y), and with S defined as S = A (Y), unless otherwise stated. We will first consider the case where S comprises a single district, and then generalize our findings to multiple districts.
3 Reformulations of the min-cost intervention problem
In the previous section, we delineated the MCID problem discrete optimization problem. This problem, cast as Eq. ( necessitates search within a doubly exponential space, which is computationally intractable. Algorithm 2 of (Akbari et al. 2022 is an algorithm that conducts this search and eventually finds the optimal solution. However, even when S comprises a single district, this algorithm requires, in the worst case, exponentially many calls to subroutine which solves the NP-complete minimum hitting set problem on exponentially many input sets, hence resulting in doubly exponential complexity. More specifically, our previous algorithm described in [Akbari eet al. [022] attempts to find a set of minimal hedges, where minimal indicates a hedge that contains no other hedges, and solves the minimum hitting set problem on them. However, there can be exponentially many minimal hedges, as shown for example in Fig. 2 c). Letting m = nn/2. then any set that contains one vertex from each level (i.e., directed distance from S) is a minimal hedge, of which there are ((2n/2).
Furthermore, the computational complexity of Algorithm 2 of AAkarri et al. 2022 grows super- exponentially in the number of districts of S. This is due to the necessity of exhaustively enumerating every possible partitioning of these districts and executing their algorithm once for each partitioning.
In this section, we reformulate the MCID problem as a weighted partially maximum satisfiability IVPMAX-SATI problem (Fu and Malik 2006]. as well as an integer linear programming (ILP) problem. We focus on the WPMAX-SA AAT and ILP reformulations due to their computational efficiency and practical applicability, but we provide alternative reformulations as a submodular maximization problem and reinforcement learning problem in Appendix D for completeness. The advantage of the WPMAX-SAT and ILP formulations is two-fold: (i) compared to Algorithm of [Akbari et al. 2022]. we state the problem exist, and (ii) these formulations allow us to propose algorithms with computational complexity that is quadratic in the number of districts of S. We will see how these advantages translate to drastic performance gains in Section
single instance of another problem for which range of well-studied solvers
3.1 Min-cost intervention as WPMAX-SAT problem
We begin with constructing a 3-SAT formula F that satisfiable if and only if the given query Fx is identifiable. To this end, we define m + variables { 1m+1 for each vertex es E V. where m (S) \ S] is the cardinality of the hedge hull of S. excluding S. Intuitively, æı,j is going to indicate whether or not vertex v; is reachable from S after iterations of alternating depth-first-serrches on directed and bidirected edges. This is in line with the workings of Algorithm for finding the hedge hull of S. In particular, if vertex ;; is reachable after m + 1 iterations, that is, Fim++1 = 1, then v, is a member of the hedge hull of S. The query of interest identifiable if and only if (S) = S, that is, the hedge hull of S contains other vertices. Therefore, we ensure that the formula F is satisfiable if and only if 2i,m+1 = 0 for every U, & S. The formal procedure for constructing this formula is as follows.
SAT Construction Procedure. Suppose a causal ADMG G = (V, E. E and a set S C V are given, where S is a district in G. Suppose (S) = {uI,.... on) the hedge hull of S in G. where without loss of generality, S = -fum+1.... Un }. and {ei.... em nS = 0. We will construct a corresponding boolean expression in conjunctive normal form (CNF) using variables ( for
i E (1,..., ) and j E (0.....
+ 1 For ease of presentation, we also define æijj = for all i E {m + 1,..,, n). E (O....,
.., m + 1). The construction carried out m + 2 steps, where in each step, we conjoin new clauses to the previous formula using 'and'. The procedure is as follows:
5

---

To construct the WPMAX-SAT instance, we simply define all clauses in F hard constraints, and add a soft clause vio with weight C(m)) for every i E (1...., .m]. The former ensures that the assignment corresponds to feasible solution of Fq. (2p, while the latter ensures that the objective in For odd j m--), for each directed edge (e,, ve) E, add (- (=2ea))) to F. we) For even E fl....,. +++1++111 1), for each bidirected edge [e E E," add both clauses (~ Fig V -we,j) and (~wir,j-1 Te,j V - to F.
Finally, step m + 2, add clauses -1, the expression F for every i m.)...,m).
As an example, consider the graph of Figure 3 with = 3 vertices. The hedge hull of S = {va} is {u1, U2, v3), and m = H e = 2. Following the SAT construction pro- cedure outlined above, the construction is carried out in m + = 4 steps. Our SAT expression will consist of 8 variables, Tı.j for E [1.2] - corresponding to i and 022 -ndd j {0. 1, 2, 3} corresponding to the four steps of construction. Below, we explain each step.
UI
U2
U3
At step 1, we add the clauses (-01,0 V F1,1 V - and (~32.0 V #2,1 V V corresponding to the edges d1 + 02 and U2 + V3 respectively. Note that by convention, T3.1 = 1, hence the second clause reduces (-32,0 V Z221)) At step 2, for the edge + U2, we add the clauses (-#1,1 V21,2 -22,2 and (~z2,1 for the edge 11 ++ V3 we add the clauses (-#1,1 V 21,2 V -23,2) and (-r3,1 V 23,2 V -112). Since by convention, F3,1 = 23,2 = 1, the latter two clauses reduce to (-#1,1 V 21,2) and 1, respectively. At step 3, we add the clauses (--r1,2 V F1.3 V -w223) and (-32,2 V #2,3 V -33,3), corresponding to the edges - 122 and + uz. respectively. Again 43.3 = 1, and the latter clause reduces to (~322,2 F2.3). At step 4, the clauses -3,,3 and m22,3 are added.
Figure 3: Example graph for 3SAT construction, where S (va)-
Similarly
Finally, combining all the clauses together, the SAT expression is given by
(~21,0 V F1,1 V -22,1) (5z2,0 V 12,1) A (-21,1 V F1,2 V -2222 (-r2,1 V F2,2 -01,2) A (-01,1 V x122) A (-x1,2 V 11,3 V -2233) A (- V 1223) A -1,3 A -22
Theorem 1. The 3-SAT formula F constructed by the procedure above given 9 and S has a satisfying solution {xi,}} where z,,0 0 i (1..... m) and xi,,- =1 i (1..... m)\I I if and only if I intersects every hedge formed for S in 9; i.e., I is feasible solution to the optimization in Eq. 2
The proofs of all our results appear in Appendix C The first corollary Theorem Dis that the SAT formula is always satisfiable, for instance by setting 2 = 0 for every i (1...., m). The second
(and more important) corollary is that the optimal solution to Eq. 22) corresponds to the satisfying assignment for the SAT formula F that minimizes
m
Σ - 11-1z,))()))).
(3)
This suggests that the problem in Eq. can be reformulated as weighted partial MAX-SAT (WPMAX-SAT) problem. WPMAX-SAT is generalization of the MAX-SAT problem, where the clauses are partitioned into hard and soft clauses, and each soft clause is assigned weight. The goal is to maximize the aggregate weight of the satisfied soft clauses while satisfying all of the hard ones.
Eq. 3 is minimized which, consequently, minimizes the cost of the corresponding intervention.
Multiple districts. The formulation above was presented for the case where S is a single district. In the more general case where S has multiple districts, we can extend our formulation to solve the general problem of Eq. (T) instead. To this end, we will use the following lemma.
Lemma 1. Let S = .S,,..., S.) } be the set of districts of S, where S = Ancy (YY). There exists an intervention set family I' of size |S| = r that is optimal for identifying IPx (Y).
Based on Le we can assume w.l.o.g. that the optimizer of Eq. T contains exactly r intervention sets II....,22 I,.. We will modify the SAT construction procedure described in the previous section

---

to allow for multiple districts as follows. For any district St, we will construct copies of the SAT expression, one corresponding to each intervention set Ig. h {1, [l.....r} rr). Each copy is built on new sets of variables indexed by (k, f), except the variables with index j = 0. which are common across districts. We introduce variables (=x.e){.t=1. which will serve as indicators for whether I& hits all the hedges formed for Sz. We relax every clause corresponding to the k-th copy by conjoining a E literal with an 'or." Intuitively, this is because it suffices to hit the hedges formed for S; with some Ig. Additionally, we add the clauses (21,4 V.... 2,.e) for any E (1.....r) to ensure that for every district, there is at least one intervention set that hits every hedge. This modified procedure, detailed in Algorithm 3
appears in Appendix B.2 The following result generalizes Theorem ||
Theorem 2. Suppose G, a set of its vertices with districts S = {Si..... .. and an intervention set family 2 I = {II...., } are given. Define my = [Hg(Se) Sel. i.e., the cardinality of the hedge hull of St excluding St itself. The SAT formula F constructed by Algorithm 3 has a satisfying where every E E (1,...,r)), there exists k (1.....r) such (ii) x,,0 for every i E It, and (iii) Fi 1 for every E {1...., In. if and only I is feasible solution optimization of Eq. (
solution (
that (i) =k,t
Constructing the corresponding WPMAX-SAT instance follows the same steps as the case for single district, except that the soft clauses are of the form (Fi.n, V -Zx,e) with weight C(us) for every i E
me} and & E r..
Remark 2. The SAT construction of Algorithm 3 is advantageous because its complexity grows quadratically with the number of districts of S in the worst case, This is because the inner-loop of the SAT construction algorithm (line 8 of Algorithm 3 is executed r2 many times. In contrast, the runtime of the algorithm of Akbari et al. [2022], when consists of multiple districts, is super-expor exproenxpol in the number of districts, because they need execute their single-district algorithm at least as many times as the number of partitions of the set (1,...,T..
Min-cost intervention as an ILP problem. The WPMAX-SAT formulation of Section 3.1 paves the way for straightforward formulation of integer linear program (ILP) for the MCID problem. ILP allows for straightforward integration of various constraints and objectives, enabling flexible modeling of potential extra constraints. Moreover, there exist efficient and scalable solvers for ILP
[Gearbart et al. 2013 Gurobi Optimization. LLC 2023 To construct the ILP instance for the MCID) problem, it suffices to represent every clause the boolean expression of Algorithm as linear
inequality. For example, clauses of the form (-a v b V -e) is rewritten as (1 - a) b
c) 2 1.
The soft constraints may be rewritten as a sum to maximize over, given by Eq. 33
4 Minimum-cost intervention design for adjustment criterion
A special case of identifying interventional distributions is identification through adjusting for confounders. A set Z C V is a valid adjustment set for Px (Y) I is identified as
Px( = [P(Y X, 2)},
where the expectation w.r.t. PZ))). Adjustment sets have received extensive attention in the literature because of the straightforward form of the identification formula (Eq. and the intuitive interpretation: Z is the set of confounders that we need adjust for identify the effect of interest. The simple form of Eq. (4) has the added desirable property that its sample efficiency and asymptotic behavior are easy to analyze [Witte et al. 2020 [Rotnizkky and Smucler 2020 Henckel al., 2022]. A complete graphical criterion for adjustment sets was given by (Shpitser et al. [2010]. As an example, when all parents of X (i.e., Pa (X)) are observable, they form a valid adjustment set. However, in the presence of unmeasured confounding, no valid adjustment sets may exist. Below, we generalize the notion of adjustment sets to the interventional setting.
Definition& 4 (Generalized adjustment). We say C V is generalized adjustment set fer Px (Y) under intervention I xfPx(Y) is identified as Fx (Y) Ez, [P X, Z)), where P-(()) represents the distribution after intervening on CV and the expectation is w.r.t. Pz(Z).
Note that unlike the classic adjustment, the generalized adjustment is always feasible a trivial generalized adjustment can be formed by choosing I = X and Z = 0.
7

---

Equipped with Definition 4
we can define problem closely linked to Eq. Q but with a (possibly)
narrower set of solutions, which can be defined as follows: find the minimum-coum cost intervention I such that generalized adjustment exists for Px (Y) under I:
I
argmin C(I) s.t. 3 V Px(() = Br, | ΣEZY
(5)
Observation.
The existence of valid (generalized) adjustment set ensures the identifiability of Fx As such, any feasible solution to the optimization above is also a feasible solution to Eq. 2 Eq. 5 is not only a problem that deserves attention in its own right, but also serves as proxy for our initial problem (Eq. 2
To proceed, we need the following definitions. Given an ADMG g = (V, F, E), let g (Vd, 7.d, .6) be the ADMG resulting from replacing every bidirected edge e = {a. v) E F. by vertex and two directed edges (e,z), (e, v). In particular, v = Vu E. and _ E U (e) e E E. E e). Note that g is directed acyclic graph (DAG). The moralized graph of g, denoted by 9TT the undirected graph constructed by moralizing G as follows: The set of vertices of 9mh is Vol Each pair of vertices x; y E Vd are connected by an (undirected) edge if either (i) (z. v) E Ed,
or (ii) 72 E Vd such that {1r, =), (u: C a.
Throughout this section, we assume without loss of generality that X is minimal in the following sense: there exists proper subset X ç X such that Px (Y) = xx, (Y) everywhere g Otherwise, we apply the third rule of do calculus [Paal 2009] as many times as possible to make X minimal. other vertices are irrelevant for our purposes (Lee)
We also assume w.l.o.g. that V = Anc
eet al. 2020b). We will utilize the following graphical criterion for generalized adjustment.
Lemma 2. Let X, Y be two disjoint sets of vertices in G such that X is minimal as defined above. Set Z S V is a generalized adjustment set for Fx (Y) under intervention I if (i) Z S Anc((S), and (ii) Z is a vertex cut between S and Pa(S) in (Grra(s))) where S = Ancv (Y)), and GIra()) is
the ADMG resulting from omitling all edges incoming to I and all edges outgoing of Pa()).
Based on the graphical criterion of Lemma we present the following polynomial for finding an intervention set that allows for identification of the query of interest in the form of a (generalized) adjustment. This algorithm will find the intervention set I and the corresponding generalized adjustment set Z simultaneously. We begin by making X minimal in the sense of applicability of rule 3 of do calculus. Then we omit all edges going out of Pa(S), and construct the graph (Gra(s))*= (V', E.d, .0) as defined above - by replacing bidirected edges with vertices representing unobserved confounding. Finally, we construct an (undirected) vertex cut network gee = (Vee, Eve) as follows. Each vertex E V is represented by two connected vertices Uı, 02 in gec. If E V, then vi has cost of zero, and v2 has cost C(v). Otherwise, both V1 and v2 have infinite costs. Intuitively, choosing e1 will correspond to including in the adjustment set, whereas choosing U/ in the cut would imply intervention on v. We connect U2 to all vertices corresponding to Pa(v) with index 1, i.e., {w) (w.,v E Jd. This serves two purposes: (i) if 02 is included in the cut (corresponding to an intervention on v), all connections between v and its parents are broken, and (ii) when 02 is not included in the cut (corresponding to no intervention on v), 12 connects the parents of u to each other, completing the necessary moralization process. We solve for the minimum vertex cut between vertices with index 1 corresponding to S and Pa(S). Algorithm [ summarizes this approach. In the solution set J, the vertices with index represent the vertices where an intervention is required, while those with index represent the generalized adjustment set under this intervention.
algorithm
Theorem 3. Let (I, Z) be the output returned by Algorithm for the query (Y) Then, Z is a generalized adjustment set for Px (Y)) under intervention I. I is the minimumn-ca cost intervention for which there exists a generalized adjustment set based on the graphical criterion of Lemma 2
*This is to say, the third rule of do calculus does not apply to Px (
'This corresponds to Z blocking all the backdoor paths between Pa(S) and S. the modified graph Gz. 'The computational bottleneck of the algorithm is an instance of minimum vertex cut problem, which can be solved using any off- shel- max- flow algorithm.
8

---

Algorithm Intervention design for generalized adjustment
1: procedure MINCOSTGEEAADUSTTMENTTAL Y, (V, E. E (C(u) vVE
2: while ir X s.t. x m-sep from Y given X {x} 9J do
b. Make minimal
3:
X + X {x}
4:
8 A
5:
F. E [1,, :
(Pa(S)
BL D,eect
6:
Construct (Gra(s))* vu + Uveaafe 02), E + (fo, (2 voJ (ffr, 02) (w, v) Ed]
7:
8:
Construct minimum vertex cut instance on the network g = (V E" with costs 0 for any U1 where V. C(v) for any 12 where V. and for any other vertex
9:
J + the minimum vertex cut between {a1 E Pa(S)) and {sl :s S}
I {v: 00:22 J}. Z t (U:01 J}
11:
return (I,
10*
10*
10
10
Duration (s)
10
10²
MHS
10
10
ILP
10
10
SAT
10
10_1
10
10
10-3
10"
20
30
40
50
60
70
80
100
3
9
(a)
(b)
Figure 4: Average time taken by Algorithm 2 of Akbari et al. [2022] (MHS), ILP, and WPMAX-SAT to solve one graph versus (a) the number of vertices in the graph and (b) the number of districts of S.
Remark 3. Algorithm [ enforces identification based on (generalized) adjustment for Fx (Y). As discussed above, this algorithm can be utilized as heuristic approach to solve the MCID problem in (2. In this case, one can run the algoritim on the hedge hull of rather than the whole graph. We prove in Appendix C that the cost of this approach is always at most high heuristic algorithm I of Akbari al.) [2022), and is often in pructice lower, as verified by our experiments.
The worst-case time complexity of Algorithm main computational bottlenecks are (i) the preprocessing in lines 2-3, which involves up to [V] rounds of m-separation tests (performed via depth-first search), resulting in complexity of F (
cubic the number of variables. The two
O ( [
1])- and (ii) the minimum-cut instance in line 9, solved using
flow algorithm with |Vec O(VVI + and E ~ O(IVI E edges, respectively.
E
many vertices and
5 Experiments
In this section, we present numerical experiments that showcase the empirical performance and time efficiency of our proposed exact and heuristic algorithms. A comprehensive set of synthetic and real-world experiments analyzing the impact various problem parameters on the performance of these algorithms, along with the complete implementation details, is provided in Appendix A We first compare the time efficiency of our exact algorithms: WPMAX-SAT and ILP, with the exact algorithm of Akbari et al. 2022 Then, we present results pertaining to performance of our heuristic algorithm. All experiments, coded in Python, were conducted on a machine equipped two Intel Xeon ES-2680 v3 CPUs, 256GB of RAM, and running Ubuntu 20.04.3 LTS.

---

2.00
Normalized cost
1.75
H2
H1
1.50
Algorithm
1.25
SAT
1.00
XXXXXXXXXXXXX
20
40
60
80
100
120
140
160
180
200
Number of vertices
Figure 5: Average normalized cost of the heuristic algorithms H1 and H₂ of Akbari et al. [2022] and Algorithm versus the number of vertices in the graph.
Results on exact algorithms. We compare the performance of the WPMAX-SAT formulation, the ILP formulation, and Algorithm 2 of Akbari et al. [2022), called Minimal Hedge Solver (MHS) from hereon. We used the RC2 algorithm [[gnatiev et al. 2019). and the Gurobi solver [Gurobi Optimization, LLC, 2023). , to solve the WPMAX-SAI problem, and the ILP, respectively. We ran each algorithm for solving the MCID problem on 100 randomly generated Renyi [Erdos and Renyi 1960] ADMG graphs with directed and bidirected edge probabilities ranging from 0.01 to 1.00, in increments of 0.01. We performed two sets of simulations: for single-district and multiple-district settings, respectively. In the single-district case, we varied the number of vertices, from 20 to 100, while the multiple-district case, we fixed n = and varied the number of districts from 1 to 9.
We plot the average time taken to solve each graph versus the number of vertices dingle-districn in Fig. ()) and versus the number of districts (n2 20) in Fig. 4(b). The error bands in our figures represent 99% confidence intervals. Focusing on the Single-isttrie plot, we observe that both of our algorithms are faster than MHS Akbari al. [022 for all graph sizes. More specifically, ILP on average one to two orders of magnitude faster than MHS, while SAT is on average four to five orders of magnitude faster. All three algorithms exhibit exponential growth in time complexity with the number of vertices, which is expected as the problem is NP-hard, but SAT grows at much slower rate than other two algorithms. This is likely due to RC2's ability exploiting the structure of the SAT problem to reduce the search space efficiently. In the multiple-district case, we observe that the time complexity of both SAT and IIP grows polynomially with the number of districts, while the time complexity of MHS grows exponentially. This is consistent with theory, MHS iterates over all partitions of the set districts, which grows exponentially with the number of districts.
Results on inexact algorithms. We compared Algorithm 1 our proposed heuristic, with the two best performing heuristic algorithms in Akbari al. [2022]. ). H1 and H₂. We ran each algorithm on 500 randomly generated Erdos-Rent Renyi ADMG graphs with directed and bidirected edge probabilities {0.1, 0.5). with n ranging from 10 to 200. We randomly sampled the cost of each vertex from discrete uniform distribution on [1, ro). In Fig. 55, we plot the normalized cost of each algorithm, computed by dividing the cost of the algorithm by the cost of the optimal solution, provided by WPMAX-SAT. Observe that Algorithm I consistently outperforms H1 and H2 for all graph sizes.
Conclusion
We introduced novel formulations and efficient algorithms for the MCID problem, demonstrating significant improvements over existing methods. Our extensive experiments showed that the WPMAX- SAT reformulation, particularly when using a high-perffrmmnne solver like RC2, excels in both speed and effectiveness.. In contrast, the ILP reformulation offers a more interpretable approach, especially valuable for incorporating additional constraints such as domain expert knowledge.
Moreover, our work on designing minimum-coss experiments for obtaining valid adjustment sets demonstrates both practical and theoretical advancements. We highlighted the superior performance of our proposed methods through extensive numerical experiments. We envision designing efficient approximation algorithms for MCID future work.
10

---

Acknowledgments
This research was in part supported by the Swiss National Science Foundation under NCCR Automa- tion, grant agreement 51NF40 180545 and Swiss SNF projects 200021 __12407 and 200021 200021_204355 /l.
References
Sina Akbari, Jalal Etesami, and Negar Kiyavash. Minimum cost intervention design for causal effect identification. In Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages
PMLR, 17-23 Jul 2022. URL
mlr ppwps/vv62/ www.riaaaaaaa..a. html html
Judea Pearl. Causality. Cambridge university press, 2009.
Miguel A Hernán and James M Robins. Estimating causal effects from epidemiological data. Journal of Epidemiology & Community Health, 60(7):578- 586, 2006.
Elias Bareinboim and Judea Pearl. Causal inference and the data-fusion problem. Proceedings of the National Academy of Sciences, 113(27)7735--3352 2016.
Susan Athey, Raj Chetty, and Guido Imbens. Combining experimental and observational data to estimate treatment effects on long term outcomes. arXiv preprint arXiv:2006.09677 2020.
Shreya Dey, Brian Caulfield, and Bidisha Ghosh. Potential health and economic benefits of banning diesel traffic in dublin, ireland. Journal of Transport & Health, 10:156-166, 2018. ISSN 2214- 1405. doi: https://doi.orr//1000 1t../////.././....o....... 2018 04.006.. science/ sccincee/atiicleee httpa///arrrrre//////11111111110
fttt::://www.scieneeiiin
com/
Maite Redondo, Ildefonso Hernández-Aguado, and Blanca Lumbreras. The impact of the tax on sweetened beverages: systematic review. The American Journal of Clinical Nutrition, 108 (3):548-563, 2018. ISSN 0002-9165.
doi:
URL https
//www www..scieenedirecttt com/ ott.://www...a.....ooooc.o..oooa
Elias Bareinboim and Judea Pearl. Causal inference by surrogate experiments: z-identifiability. arXiv preprint arXiv: 4842, 2012.
Sanghack Lee, Juan D Correa, and Elias Bareinboim. General identifiability with arbitrary surrogate experiments. In Uncertainty in artificial intelligence, pages 389-398. PMLR, 2020a.
Yaroslav Kivva, Ehsan Mokhtarian, Jalal Etesami, and Negar Kiyavash. Revisiting the general identifiability problem. In Uncertainty in Artificial Intelligence, pages 1022-1030. PMLR, 2022.
Fateme Jamshidi, Sina Akbari, and Negar Kiyavash. Causal imitability under context-specific independence relations. Advances Neural Information Processing Systems, 36, 2024.
Thomas Richardson. Markov properties for acyelic directed mixed graphs. Scandinavian Journal of Statistics, 30(1):145-157, 2003.
Donald B Rubin. Estimating causal effects of treatments in randomized and nonrandomized studies. Journal of educational Psychology. 66(5),688, 1974.
Zhaohui Fu and Sharad Malik. On solving the partial max-sat problem. Armin Biere and Carla P. Gomes, editors, Theory and Applications Satisfiability Testing SAT 2006, page 252-265, Berlin, Heidelberg, 2006. Springer. ISBN 978-3-540-33207-5 doi: 10. 1007/1 181 01814889225
Jared Lee Gearhart, Kristin Lynn Adair, Justin David Durfee, Katherine A Jones, Nathaniel Martin, and Richard Joseph Detry. Comparison of open-source linear programming solvers. Technical report, Sandia National (SNI-NN)) Albuquerque, NM (United States), 2013.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL. https: : //w Furobi.com

---

Janine Witte, Leonard Henckel, Marloes H. Maathuis, and Vanessa Didelez. On efficient adjustment in causal graphs. Journal of Machine Learning Research, 21(246):1-45, 2020.
Andrea Rotnitzky and Ezequiel Smucler. Efficient adjustment sets for population average causal treatment effect estimation in graphical models. Journal of Machine Learning Research, 21(188); 1-86, 2020.
Leonard Henckel, Emilija Perković, and Marloes Maathuis. Graphical criteria for efficient total effect estimation via adjustment in causal linear models. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(2):579-599 2022.
Ilya Shpitser, Tyler VanderWeele, and James M Robins. On the validity of covariate adjustment for estimating causal effects. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, UAI 2010, pages 527-536. AUAI Press, 2010.
Sanghack Lee, Juan D. Correa, and Elias Bareinboim. General identifiability with arbitrary surrogate experiments. In Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, page 389-398. PMLR, August 2020b. URL htttps://proceeddnggg mlr press/v115/lee203 html
Alexey Ignatiev, Antonio Morgado, and Joao Marques-Silva. Rc2: an efficient maxsat solver. Journal Satisfiability, Boolean Modeling and Computation, 11(1):53-64, September 2019. ISSN 15740617. doi: 10.3233/SAT190116
Paul Erdos and Alfred Renyi. On the evolution of random graphs. Publ. Math. Inst. Hungary. Acad. Sci., 5:17-61, 1960.
Antonio Morgado, Carmine Dodaro, and Joao Marques-Silye Core-guided maxsat with soft cardinal- ity constraints. In Barry O'Sullivan, editor, Principles and Practice of Constraint Programming, page 364-573, Cham, 2014. Springer International Publishing. ISBN 978-3-319-10428-7. doi:
IBM Corporation. IBM ILOG CPLEX Optimization Studio CPLEX User's Manual, 2023. URL
https://www. ibm. com/ analytics/ cerriics/plleee. axplex-optimize
J.J.H. Forrest and R. Lougee-Hord Heimer. CBC User Guide. COIN-OR, 2023. URL httppttt:///gthhbb
Steffen L Lauritzen, Philip Dawid, Birgitte N Larsen, and H-G Leimer. Independence properties of directed markov fields. Networks, 20(5):4915505 1990.
G. L. Nemhauser, I. A. Wolsey, and M. I.. Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical Programming, 14(1):265-22) 294, December 1978. ISSN 1436-4646. doi: 10. 10.100///F015889
12

---

Appendix
A Implementation details and further experimental results
A.1 Implementation details
Our codebase is implemented fully in Python. We use the PySAT library for formulating and solving the WPMAX-SAT problem, and the PuLPPlibrary for formulating and solving the ILP problem.
Solving the WPMAX-SAT problem. There are several algorithms to solve the WPMAX-SAT instance to optimality. These algorithms include RC2 [Ignatiev et al., 2019] and OLL [Morgado et al. 2014), both of which are core-based algorithms that utilize unsatisfiable cores to iteratively refine the solution. In this context, a "core" refers to an unsatisfiable subset clauses within the CNF formula that cannot be satisfied simultaneously under any assignment. These algorithms relax the unsatisfiable soft clauses in the core by adding relaxation variables and enforce cardinality constraints on these variables. By strategically increasing the bounds these cardinality constraints modifying the weights of soft clauses based on the cores identified, the algorithms efficiently reduce the search space and converge the maximum weighted of satisfiable clauses, therehy solving the WPMAX-SAT problem optimally.
Solving the ILP problem. Similarly, with the ILP formulation of the MCID problem presented in Section 3] we can utilize exact algorithms designed for solving ILP problems to find an optimal solution. ILP solvers work by formulating the problem with linear inequalities constraints and integer variables that need to be optimized. Popular ILP solvers include CPLEX [IMM Corporation
2023). Gurobi (Gurobi Optimization, LLC [203), and the open-source solver CBC [Forrest and
Lougee-Heimer 2023]. The latter is a branch-and-cut-bass based solver, and cutting plane methods to explore feasible integer solutions systematically while pruning the search space based bounds calculated during the solving process.
We the Gurobi solver in experiments.
13

---

A.2 Experiments on real-world data
We conduct experiments using 17 real-world networks from the Bayesian Network Repository This repository encompasses networks from diverse domains such biology, engineering. medicine, and social science. In our experiments, each network from the repository is utilized as the DAG on the known variables. We assign random cost to each variable, sampled uniformly at random from [L. rt.. We then introduce hidden variables by randomly sampling bidirected edges with probabilities of 0.01, 0.1, and 0.3, resulting in 50 ADMGs per network. For each ADMG, we select singleton consisting of the last node in the causal order. This choice ensures that any other node would not reduce the network's 's size by ignoring some vertices and edges, as outgoing edges from are irrelevant for the MCID problem.
Subsequently, implemented the exact algorithms: minimal hedge solver (Algorithm 2 of Akbari et al. (022 ), IIP,, and WPMAX-SAT. We also tested the heuristic algorithms H1 and H₂ from Akbari 2022]. alongside Algorithm from this work.
In Figure 6 we present semi-log bar chart of the average time taken for each exact algorithm to solve instance of graph for each network. Notably,
approaches, ILP and SAT, consistently outperform MHS by an average factor of over 100, and by more than 1000 times on the largest network, link. Additionally, SAT demonstrates superior performance in all but two networks, andes and diabetes.
In Figure 7 we provide semi-log plot of the normalized cost of the heuristics H1 and H2 from Akbari et aT., 2022, and our Algorithm 1, averaged across each network. evident that Algorithm I significantly outperforms H1, often by one two orders of magnitude. Although H2 performs better due to its focus on performing cuts on nodes over directed edges (which are fewer), its cost remains higher than that of Algorithm 1. Overall, the results align with findings from synthetic simulations the main text. Our WPMAX-SAL and ILP formulations surpass the previous state- of ff-the-an art approach Akbari al. 2022). with WPMAX- being the fastest. Furthermore, polynomial Algorithm consistently outperforms the heuristics of Akbari et al.) [2022].
10
Algorithm
10
MHS
ILP (ours)
10
SAT (ours)
Duration (s)
10
10a
10
10
10
asia (8)
sachs (11)
child (20)
insurance (27)
water (32)
mildew (35)
alarm (37)
barley (48)
hailfinder (56)
hepar2 (70)
win95pis (76)
pathfinder (109)
muninl (186)
andes (223)
diabetes (413)
pigs (441)
link (724)
Network (size)
2022 (MHS), ILP, and WPMAX-SAN solve one instance of the network. Error bars represent 99% confidence interval.
Figure 6: Semi-log plot of the average time taken by Algorithm 2 of Akbari et al.
Dinleam.coo//urreossite
14

---

Algorithm
10
H1
H2
Normalized cost
Algorithm (ours)
10
10
asia (8)
sachs (1I)
child (20)
insurance (27)
water (32)
mildew (35)
alarm (37)
barley (48)
haider (56)
hepar2 (70)
Win9Spts (76)
pathfinder (109)
munin (186)
andes (223)
diabetes (413)
pigs (441)
link (724)
Nctwork (sizc)
Figure 7: Semi-log plot of the average normalized cost of the heuristic algorithms H1 and H₂ of Akbari et al. [022 and Algorithm solve one instance of the network. Normalized cost is the cost of the solution divided by the cost the optimal solution. Error bars represent the 99% confidence interval.
102
WPMAX-SAT
10
Duration
10
10
10"
0
100
200
300
400
500
Number of vertices
Figure 8: Semi-log plot of the average time taken by WPMAX-SAT solve one graph versus the number of vertices in the graph.
A.3 Extended WPMAX-SAT simulations
We extended the simulations in Section 5 for up to n = 500 vertices, and the results are presented in Fig. & We observe that even
500, WPMAX-SAT takes around the same time Algorithm 2 of Akbari et al. [2022] does to solve = 40 (230 for both). Moreover, we can clearly see the exponential growth in time complexity, as expected, especially for 400.
A.4 Investigating the effects of directed and bidirected edge probabilities on the performance of exact algorithms
We run experiments on varying the probabilities of directed and bidirected edges in the graph. We fix the number of vertices at n 20 and vary the probabilities directed and bidirected edges from 0.001 to 1.00 in increments of 0.001. The results are presented in Fig. 9
15

---

F I
-
10
10
10
10
10
1.0
1.0
Bidirected edge probability
0.89
Bidirected edge probability
0.89
0.78
0.78
0.67
0.67
0.56
0.56
0.45
0.45
0.34
0.34
0.23
0.23
0.12
0.12
0.01
0.01
0.01
0.12
0.23
0.34
0.45
0.56
0.67
0.78
0.89
1.0
0.01
0.12
0.23
0.34
0.45
0.56
0.67
0.78
0.89
1.0
Directed edge probability
Directed edge probability
Figure 9: Heatmap of the average time taken by WPMAX-SAT (on the left) and Algorithm 2 of
Akbari et al. [2022] (on the right) to solve one graph versus the probabilities of directed and bidirected edges in the graph.
10
Algorithm
MHS
10
ILP
Duration (s)
SAT
10
10-2
10
20
40
80
100
Poisson mean
Figure 10: Average time taken by Algorithm 2 of Akbari et al. 2022 (MHS), ILP, and WPMAX-SAT to solve one graph versus the mean parameter of the Poisson distribution from which the costs sampled.
A.5 Investigating the effeec of cost on the performance of the algorithms
We run experiments with 20 and costs sampled from Poisson distributions with mean parameter ranging from 100. The results are presented in Fig. 10 Interestingly, there appears be no clear trend in the time complexity of the algorithms with respect to the mean parameter of the Poisson distribution. This suggests that the time complexity the algorithms is not significantly affected by the cost of the vertices.
16

---

H1
-
H2
Algorithm
SAT
p = 0.1 and q = 0.1
p 0.1 and q = 0.5
Normalized cost
Normalized cost
4
1.50
1.25
1.00
100
200
100
200
Number of vertices
Number of vertices
p = 0.5 and = 0.1
p= 0 and q = 0.5
Normalized cost
Normalized cost
4
1.1
1.0
100
200
100
200
Number vertices
Number vertices
Figure 11: Average running time of the heuristic algorithms H1 and H2 of Akbari et al. 2202 and Algorithm versus the number of vertices in the graph for different probabilities of directed and bidirected edges the graph.
A.6 Investigating the effects of directed and bidirected edge probabilities on the performance of the heuristic algorithms
We experiments varying the probabilities of directed and bidirected edges in the graph. We vary n from = 10 to n 200 and the probabilities of directed and bidirected edges in f0.1. 0.5). The results are presented in Fig. [T] We see that our proposed heuristic algorithm consistently outperforms the heuristic algorithms of Akbari et al. 2022 for all graph sizes and edge probabilities.
17

---

B Algorithms
B.1 Pruning algorithm for finding the hedge hull
We include the algorithm for finding the hedge hull for the sake of completeness. This algorithm is adopted from Akbari et al. [2022]
Algorithm Pruning algorithm
1: procedure PRUNE(G = (V, E, S)
2: H. < (S)
3: while True do
4:
H' {u H has bidirected path S in g[H]}
5:
if HL' = H then
6:
return H.
7:
H + AncH. (S)
8:
if Ht' then return H
9:
B.2 SAT construction procedure for multiple districts
The procedure for constructing the SAT formula when S comprises multiple districts was postponed this section due to space limitations. This procedure detailed below.
Algorithm 3 SAT construction
1: procedure CONSTRUCTSSTTXXXYYG (V, (V,
2: S + A
3: S - districts S in G[S]
4:
r S
5:
F
6:
for E E (1,...r do
iterate over districts of S D # iterations iterate over expressions
7:
m + (Sp) \ Sy
8:
for k E (1, ..l..rrr. r do
9:
F + F (Ii,o. V -ākee) for every i s.t. ez E S
F F (Fijhht V -zkee for every s.t. U2 Se and every (l,..., m 1}
11:
for (2;, up) E do
> iteration j = 1
F F (- V Ni,I,A, D.p.I V -22,))
13:
for jE ( + 1} do
if is odd then
15:
for (C,, Up) E E. do
F F F V ZisKkE V -pp.d.. V -zk,e)
17:
else
18:
for
(Ui, Up) E do
19:
F+ F A (- VaiskE TPi.ke V -2k,)) F+ F F Zp.iktt V -Iigike -22,()
21:
F-FA( - for every v; $ St
22:
F 2x.1)
23:
return
18

---

C Missing Proofs
C.1 Results of Section
Theorem 1. The formula F constructed by the procedure above given 9 and S has a satisfying
solution {xī where zi, for i ((....., and x for iE (L....,7h m m if and only if
I intersects every hedgeformed for S in G; i.e., I is feasible solution to the optimization in Eq. 2
Proof. Proof of 'if" Suppose I hits every hedge formed for S. We construct a satisfying solution for the SAT formula as follows. We begin with Ii,o:
00;
i
2,,00
11; O.W.
For every f1..... m 1}, define H, {i Fi.j11 1}. Then æi for j E fl...., m + 13 is chosen recursively as below.
Odd j: oi = if E H, and has directed path to S in [[Hz]. and o = =0 otherwise.
Even j: =i. if E Hj and u; has bidirected path in G[H,), and wi, otherwise.
Next, we prove that { } as defined above satisfies F. We consider the three types of clauses in F separately:
For odd j E (1,..., m + 1). the clause (-Wi.- V Day V -itt.) corresponds to the directed edge 27, = 0, then this clause is trivially satisfied. So suppose
(v,, ue) E E: if either zi hi--1 and =i, 1, which implies by construction that z 1. Therefore, i, f E Hj- Further, since =ī 1, uy has directed path S in G[ll)]. Then v; has directed path to S in G[H because of the edge (v,, ve) E E. By the construction above, # 1,, which satisfies the clause.
For even {l...., + 1}, the clause (-w1,-11 V zij V -ate)) corresponds to the bidirected or =ž, 0, then this clause trivially satisfied. So
edge (1,, E F: either =i,j- suppose -f = and = 1, which implies by construction that zīz-ı i, l Hy. Further, since क,, 1, dy has a bidirected path in G[H,). Then us has bidirected path to in G[H, because of the edge {u,, v2 E. By the construction above, x7, = 1, which satisfies the clause.
Therefore,
The clauses +1 First note that by construction, if for some j E {1...., m 1}, - O. then o = Lii++1
zi,m = O. That is, { is a non non-increasing binary- valued sequence for every i. Therefore, for every E (1, (1...., m), there exists at most one j such that -T,3-1 > - We consider two cases separately:
There are exactly m many E {l...., m + 1} for which there exists at least one i such zi.j. In this case, for every that - {1...., m + 1} such that -i,-1 > xf Then for every i, there exists j such that x;,- = and following the argument above, 2t,+ 0. Hence, the clauses -., are all satisfied.
{I...., mm), there exists exactly one j
There are strictly less than m many j {1....,, m 1} for which there exists at least one i such that -i > zt. Then there exist j.j' E {1...., m 1} such that for every i E (1...., m}. - = =f and -1 "",,". Assume without loss of generality that j' < j and therefore, j > 1. If x 0 for every i, then by similar arguments as the previous case, 2im+1 0 and the clauses -i are satisfied. So suppose for the sake of contradiction that there exists a non-empty set H, = {i: - = 1] * 0. Note that Hj+1 = {i: z 1} = Hy. since x; = = for every i. Moreover, I n Hj = 0 since zin- = for every E I and {xj 1 non-increasing. Assume without loss of generality that j is odd. The proof is identical case is even. By definition, the set of vertices H,+1 = H, G [[H Moreover, the set of vertices H, those vertices in H
have directed path to S in
19

---

that have bidirected path to S in -[H (here we used j > 1 for H3-1 to be well-defined.) That is, H2 is the connected component of S in -1 The latter implies that every vertex in H has a bidirected path to S in G { We proved that Hj is hedge formed for S, and H ni I 0. This contradicts with I intersecting with every hedge formed for
Proof of 'only if:' Suppose {at,)) } is satisfying solution, where x;,0 = 1 for every i $ I. To prove intersects every hedge formed for S. it suffices to show that there is no hedge formed for S in GVV Σ]. Assume, for the sake of contradiction, that this is not the case. That is, there exists hedge H S V' I formed for S' in G. Suppose for some j E {I,...,,m m + 1}, it holds that -i,j-1 = for every 2 E H. We show that 2i,- = 1 for every vs E H. We consider the following two cases separately:
E F. consider the clauses (~ax.s V Jig V -xt,,) and (-xt,-1 V Fij V -xis)) that are in F by construction for even j. Since -i = -2.5-1 = 1, the expression (Ii, V (-22,)
(o2, V (,)) is satisfied; i.e., it evaluates Even j: for arbitrary 02 dh E H such that {or 02) (e)
to 'true.' The latter expression is equivalent to (x.. A x (-x),, A -x],)) which implies that "h = Note that i, E were chosen arbitrarily. This implies that xi is equal for every i, since H is a connected component through bidirected edges by definition of hedge. Finally, since by construction, Ii.j = for every 0 E S C H, that equal value is 1. Therefore, mi, for every i such that U/ E H.
Odd j: the proof is analogous to the case where j is even. For arbitrary vs U2 E H such that (vi, ue) ue)
E E. consider the clause (-wig-1 V æi,j V -are.). Since =i--1 1, the expression (æt, V - is satisfied; i.e., evaluates 'true.' The latter implies that if 0 directed edge to 1j, then .i.; = 1. Using the same argument recursively, if æi, and 8/2 has directed 'path' to 1j in G[H]. then =i.j 1. By construction, =t,, 1 for every v E S, and by definition of hedge, every vertex vn H has directed path to S. As result, x7.1 for every U; E H.
and v2 has
Since for every U, E H, H,,0 = 1, using the arguments above, by induction, Fi,+1 1 for every Vs H. However, this contradicts the fact that { satisfies F, since F includes the clauses mii for every i.
Lemma 1. Let S = (Si,..., Sy) } be the set of districts of S. where S = Anevix(Y), There exists an intervention set family I' of size (S] = that is optimal for identifying Ixx xY).
Proof. Let I be an optimizer of Eq. TT. By Proposition D for every S; E S, there exists I₁ E I that hits every hedge formed for S, The set of such I,s is subset of at most size of I, which implies that [I] S r since I is optimal. If [I] = r, the claim is trivial. If [Z] < r, then simply add (r - [I] empty intervention sets to I to form intervention set family I with the same cost which is an optimal solution to Eq. (T.
Theorem 2. Suppose G, a set of its vertices S with districts S = (St..... Sr,,, and an intervention set family 2 I (II....,II } are given. Define m = (Hg(Se)) Sel. i.e., the cardinality of the hedge hull of Sz excluding St itself. The SAT formula F constructed by Algorithm has a satisfying where for every E [I....,, there exists k (l,.... such that (i) 2 1, (ii) x0,0 for every i In, and (iii) x = 1 for every E {l....,m, Ix. if and only I is feasible solution optimization of Eq. (1.
solution {=;,0,x (.a,
Proof. The proof is identical to that of Theorem D with necessary adaptations.
Proof of 'if:' Suppose I is a solution Eq. (I). From Proposition [ for every Se E S, there exists & such that I, hits every hedge formed for Se. Assign zi,6 = 1 and 2 = 0 for every other k' * k. thereby satisfying every clause that includes 7Ekre, k' A k. So it suffices to assign values to other variables so that clauses including -2k.f. Since zk,e = 1, these clauses reduce to ( (-xri,j-1,R,e V &i.j.K.E V -Kpjjkkee) (see lines 16, 19, or 20.) These clauses are exactly in the form of 3-SAT clauses as in the single-district case procedure. An assignment exactly parallel to the proof of Theorem satisfies these clauses.
20

---

Proof of "only if:' Suppose (, U f s. is a satisfying solution, where for some k, l E (1....,r). it holds that = = and oi = 1 for every i & Ig. We show that Ia hits every hedge formed for Sy. Since such a & exists for every S we will conclude that I is feasible for Eq. ① by Proposition| []] Finally, to show that Z& hits every hedge formed for Se, note that satisfiability of all clauses containing the literal e reduces to the satisfiability of (- V Lij.e, V p...).)) (see lines 16, 19, or 20), and the same arguments as in the proof of Theorem applyy.
C.2 Results of Section
Lemma 2. Let Y,Y be two disjoint sets of vertices in 9 such that X is minimal as defined above. Set Z S V is a generalized adjustment set for PP (Y) under intervention I if (i) Z S Anc(S), and (ii) Z is a vertex cut between S and PS( in (GIra(s)))" )m, where S = Ancy (Y), and 9Ira()) is the ADMG resulting from omitting all edges incoming to I and all edges outgoing of Pa(().
Proof. Define S = Anev (Y). First, we show that Pa(S) S X. Assume the contrary, i... there is a vertex w E (a(S) \ X. Clearly w has directed path to S (a direct edge) that does not go through X. This implies that w E xnev, (S), and since by definition, S Ancy (Y). we E Aney (Y)) S. However, the latter contradicts with w Pa(S). Second, we note that from the third rule of do calculus (Pearl 2009), (w))) (S) for any W 2 Pa(S). Combining the two arguments, we have the following:
Pw(S) = (9); M 2 Pa(S).
To proceed, we will use the following proposition.
Proposition 3 (Lauritzen et al. 1990). Let S, R, and Z be disjoint subsets of vertices in directed acyclic graph G. Then Z d-separates S from R if and only if Z is a vertex cut between S and R in (S[Anc(S U Z))"
Choose R Pa(S) in the proposition above. Since S Anc(S), we have that Anc(S RU Z) Anc(S). From condition (ii) in the lemma, Z is vertex cut between S and R in (Trra(s))) which implies it is also a vertex cut in (Grpa(s) (An((S))) as every path in the latter graph exists in (GIpa(s))". "" Using the proposition above, Z d-separates S and Pa(S) in CIpees) This is to say, Z blocks all non-causal paths from Pa(S) to in Gz. and clearly has no elements that are descendants of PS( Therefore, Z satisfies the adjustment criterion of (Shpitter et al. (2010) w.r.t. (S) in G.. That is, the following holds:
(I)PA(S)(S) = F2, (P Pa(S)) 2)},
where the expectation is w.r.t. (7). Choosing W = UU Pa(S) in Eq. 6 we get Px(S) Ep, [P>(S] Pa(S), Z)}.
Marginalizing S Y out in both sides of the equation above, we have
Px Ep, (P Pa(S),
The last step of the proof is to show that Pa(S) X. We already showed that Pa(S) C X. For the other direction, we will use the minimality of X. Suppose to the contrary that x E X Pa(S). We first show that every causal path from Y goes through X \ {xx.. Suppose not. Then take a causal path 2, $i,..., Sm. y be causal path from x to E Y. Note that s1 has a causal path to Y that does not go through X. By definition, $1 E S. which implies x E Pa(S), which is a contradiction. Therefore, every causal path from x to Y goes through X \ {x). and consequently, there is no causal path from x to Y in Gx. Clearly there is no backdoor path either. Every other path has a collider on it, and therefore is blocked by X \ {x+ note that none of these can be colliders in Gz. Therefore, {z) d-separated from Y given
{m) in G. which contradicts the minimality of X w.r.t. the third rule of do calculus. This shows X C Pa(S), completing the proof.
This corresponds Z blocking all the backdoor paths between Pa(S) and S, in the modified graph Gz.
21

---

Theorem 3. Let (I, 2) be the output returned by Algorithm for the query PX Then, Z is a generalized adjustment set for Fx (Y) under intervention I.
-I is the minimum-cost intervention for which there exists a generalized adjustment set based on the graphical criterion of Lemma 2
Proof. For the first part, using Lemma 2 it suffices show that Z is vertex cut between S and Pa(S) in (STpa(s)))) )"" Suppose not. That is, there exists a path from S to Pa(S) in (GTpa(s))"
that does not pass through any member of Z. Let P = v'....,'', represent this path, where E S and x E Pa(S). We construct a corresponding path p' in g as follows. The first vertex on P' is $1, which corresponds to the first vertex on P. s. We then walk along P and add a path to P' corresponding to each edge we traverse on P as follows. Consider this edge to be {w, w) - for instance, the first edge would be {s, )²). By definition of (GIra(s))) for every pair of adjacent
vertices v, w the path P, one of the following holds: (i) + in (GIra(3)) (ii) v (TTPa(s) 1d, (iii) v and have a common child in (SIPa(S))* )a In case (i), add vn, W2, w0- In case (ii,, add 02 w1- Finally, in case (iii), we add V1, 22, W1 to P'. We continue this procedure until we traverse all edges on P. The last vertex on p' is 22, as x has no children in (Gzra(s))* Finally we add 21 to this path, 22 and xy are always connected by construction. Note that by construction of P', any vertex that appears with index 2 has a parent in v - w in (GIra(s) )² and
in
therefore is not a member Z. Hence, (122 v E I does not intersect with P'. Further, {v1 : E Z) does not intersect with P' either, none of the vertices appearing P' correspond to Z. This is to say that J = (02 u E ] U {2) D E 2}. which is the solution obtained by Algorithm [ does not cut the path P.. This contradicts with J being vertex cut.
in line 10,
For the second part, let (I', Z') be so that Z' is vertex cut between S and Pa(() in (STPA(S)) and
I' induces lower cost than I; that is, C(I') C()). Define J' {12 U E I') {or U E Z'). Clearly, the cost of J' is equal to C(I'), which is lower than the cost of minimum vertex cut found in line 10 of Algorithm [ It suffices to show that is also vertex cut between { : I E Pa(S)} and {s1 8 E 5} in g to arrive at a contradiction. Suppose not; that is, there is path P = $1,....4 21 on Goh that J' = {e2 : v E I'} U {2z : v E Z') does not intersect. None of the vertices with index on P belong to I', and none of the vertices with index 1 belong to Z'. Analogous to the first part, we construct a corresponding path p' this time in (Grre(s))
)T The starting vertex on P s, which
corresponds to 81, the initial vertex on P. Let us imagine cursor on 81. We then sequentially build p' by traversing P as follows. We always look at sequences starting with Vi (where the cursor is located): when the sequence is of the form U1, W2, Wi U1, U2 W1, we add to P', and move the cursor to W1; however, when the sequence is of the form U1 W2, T1, we add T1 to P' and move the cursor to 71- By construction of G between i1 and wi or 222 and W2 where e and w are distinct. Since none of the vertices with index on P belong to I, in the first case, the corresponding edge v w and consequently, the edge (v, w) is present in (S7Pa(s) )": and in the latter case, both edges v w and f- are present in (Grra(s))* and consequently, the edge {2, r is present in (Gyra(s))" )" P' is therefore path between S and Pa( in (Grra(s)))) Notice that by construction, only those vertices appear on P' that their corresponding vertex with index 1 appears on P P- -the cursor always stays on vertices with index 1. As argued above, none of such vertices belong to Z', which means Z' does not intersect with p' which is a path from S to Pa(S) in (GrPPa(s)) This contradicts with Z' being a vertex cut.
other sequence is possible note that there are edges
is present in (STra(s)) )d
C.2.1 Proof of Remark 3
Proof. Since the algorithms are run in the hedge hull of S. assume without loss of generality that V = "HHo(S) i.c., V is the hedge hull of S. From Theorem 3. Algorithm| finds the optimal (minimum-cost) intervention I such that there exists a set Z S that is a vertex cut between S and Pa(S) in (ITpa(s)))) To prove that the cost of the solution returned by Algorithm 1 is always smaller than or equal to that of heuristic algorithm I of Akbarii et al. (2022). suffices to show that the solution of their algorithm is feasible point for the statement above. That is, denoting the output
22

---

of heuristic algorithm Akban et al. [022 by I1, we will show that there exist sets Z1 S V such that it is vertex cut between S and (S( (GTra())))
Heuristic algorithm I: This algorithm returns an intervention set I such that there is no bidirected path from Pa(S) in GT, We claim Z1 VV PP((S) \ satisfies the criterion above. To prove this, consider an arbitrary path P between S and Pa(S) (())) If there is an observed vertex E V on P. this vertex is included in Zi and separates the path. So it suffices to show that there is no path P between S and Pa(S) in ((()) ) where all the intermediate vertices on P correspond to unobserved confounders. Suppose there is. That is, P I, M........ Um 8, where I E Pa( and {u, {u are unobserved. Since u, is not connected to uj in (GTraa()) )" must be the case that any u, and u,+1 have a common child U4,j in (TT)))))) )d This is to say. there is path + Um-1,m +- Um + in (GT))a()))* which corresponds to the bidirected path v, 21..,.... 1m, 8 in 97. This contradicts with the fact that there is no bidirected path between Pa(S) and S in ST.
- 012 < u2
C.3 Results the appendices
Lemma 3. For any district S C V, the function fs 2 7,50 is submodular.
Proof. Take two distinct vertices {x. y) V \ S and an arbitrary set c V VVVSSV S {2,0). It suffices to show that
f (s( S fs(1U(x)) - fs(1).
By definition, the right hand side is the number of hedges H CVV formed for S such that & H. Similarly, the left hand side counts the number of hedges H - V (IU {y}) formed for S such that & H. The inequality holds because the set of hedges counted by the left hand side is a subset of that on the right hand side.
Proposition 4. The combinatorial optimization of Eq. equivalent the the following unconstrained submodular optimization problem.
EVEr C(v) 1+ Evevis C(v)
I argmax ICVIS
[s(I)
Proof. The submodularity of the objective function follows from Lemma 3 To show the equivalence of the two optimization problems, we show that a maximizer I of Eq. (7) (1) hits every hedge formed for S, and (ii) has the optimal cost among such sets.
Proof of '(i):" Note that [T) = if and only there are no hedges formed for G IT), or equivalently, I hits every hedge formed for S. So it suffices to show that fs(I") = 0 for every maximizer I" of Eq. (7). To this end, first note that
Ever's C(v) 1 Eneris C(v)
1
fs(V S)
= 1+
-1,
1 Everis C(u) C(1)
which implies that
EVEr. C(v) -1
fs(I*) 1+ Evevis C(v)
Eorz C(v)
On the other hand, clearly I+E.evis C(uj which combined with the inequality above implies
fI("") > -1 Since fs(I') E 5 is only possible that fs( =
Proof of ((ii:" We showed that fs(I') 0. So I' maximizes E.rz C(v)
I+E.ev's C(ej among all those
such that Js(T) = O. Since the denominator is constant, this is equivalent to minimizing C(T) = Σ C(u) among all those 7 that hit all the hedges formed for S, which matches the optimization of Eq. 2
D
23

---

D Alternative Formulations
D.1 Min-cost intervention submodular function maximization problem
In this Section, we reformulate the minimum-cos intervention design as a submodular optimization problem. Submodular functions exhibit property akin to diminishing returns: the incremental gain from adding an element to a set decreases as the set grows [Nemhauser et al. 1978).
Definition 5. A function f 2 + R is submodular for all A C BCV V and E V B, we have that fAA {u}) f(A) 2 f (BU(t - f(B).
Given an ADMG G = (V, E. E district S in G, and an arbitrary set I S V VVV, we define fs(Z) the negative count of hedges formed for S in g[V I].
Lemma 3. For any district S C V, the function fs V z is submodular.
Note that gs 2 R, where (z( fs( - a Evez C(v), and a is an arbitrary constant, is also submodular as the second component is a modular function (similar definition as in only with equality instead of inequality.).
Proposition 4. The combinatorial optimization of Eq. 22 is equivalent to the following unconstruined submodular optimization problem.
EVErCh C(v)
I' argmax
fs(I)
1+ ++E Dverys C(v)
ICVIS
D.2 Min-cost intervention as an RI. problem
We model the MCID problem given graph (V, E) and S C V, as Markov decision process (MDP), where vertex is removed in each step until there are no hedges left. The goal is to minimize the cost of the removed vertices (i.e., intervention set). Naturally, the action space the of vertices, V and the state space is the set of all subsets of V. More precisely, let 8 and denote the state and the action of the MDP at iteration t, respectively. Then, St is the hedge hull for S from the remaining vertices at time f, and action is the vertex that will be removed from V/ in that iteration. Consequently, the state transition due to action o, is 8t411 = Hhun V. \ {a: The immediate reward of selecting action a state will be the negative of the cost of removing (i.e., intervening on) dg. given by
r(s,, a+)= = -C((a))
The MDP terminates when there hedges left and the hedge hull of the remaining vertices is empty (i.e., 8, = 0). The goal is to find a policy æ that maximizes sum of the rewards until the termination of the MDP. Formally, the goal is to solve
Σ rsse an)
argmax
where 51 V and T' is the time step which the MDP terminates (i.e., ST 0).
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract summarizes the problem and contributions of the paper. The contributions are listed at the end of Section [ after a couple of paragraphs explaining the problem with an illustrative example and positioning the contributions with respect to the state of the art.

---

Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We examined the limitations of our proposed reformulations and algorithms by outlining their complexities and specifying the conditions under which their results hold true.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All the theorems, lemmas, propositions are numbered and cross-referenced. All assumptions are clearly stated or referenced their statements. The proofs are in the supplemental material (Appendix C).
Guidelines:
The answer NA means that the paper does not include theoretical results.
25

---

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

---

We will release our code a toolbox on GitHub, providing access for researchers and practitioners. The link will be available upon publication of the paper.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
public/guides/CDne Soaadddss/ooeeStummsissoooooe
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https "pipsscc/puulic//uuu gwtp://wwiee//eeeeee /ooeee//mmmSeummia wwtpibmmmssioooPPooooioe
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify the experimental details both in the text and also in the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: The plotted results are displayed with 99% CI on each figure reporting experi- mental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
27

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The computing resources used to produce the numerical results are provided at the beginning of Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httph:tt//////t httpriiig..ccpuulleeeettcccceeee
Answer: [Yes]
Justification:
The research conducted in this paper respects the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
28

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cited all the original papers that produced the (code of the) various algorithms and packages used in the paper
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the batasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
29

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The paper does not release assets, other than the code that will be provided, with documentation, upon publication of the paper.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "9hTMIKlTEI", "reviewer": "Reviewer_Jqzf", "summary": "The problem of finding a lower cost intervention to identify causal effects has been shown to be NP-complete.\nThis paper provides many new reformulations to the problem in terms of a partially weighted maximum satisfiability (in the main paper), integer linear programming (in supplementary), submodular function maximization (in supplementary), and reinforcement learning (in supplementary) that allow designing algorithms that are significantly more efficient.\nThe new proposed algorithms were shown to have a superior performance through extensive numerical experiments.", "questions": "* Could you provide a definition of cost? Alternatively, can you offer a concrete example of what the cost might be?\n\n* I believe the paper could be made smoother by consistently using notation. For instance, in almost all definitions, S is used for districts, but in the introduction of notations, S is used as a random set and W as a district. Please consider using S exclusively for districts. This would simplify the reading of the paper.\n\n* lines 133 and 136 and fig 2(d): can you give an intuition of why S2 and X3 hits every hedge for S1 and S2? Maybe consider given the manipulated graph after intervention and discuss how the hedges disappear. Same remark for fig 2(b) the lines  lines 152 and 155.\n\n* Example 1 seems to be not compatible with the text between lines 152 and 155. In the example you consider the effect of X1 and X3 on Y and you say that intervening on X2 suffices for identification; in  lines 152 and 155, you consider the effect of X2 and X3 on Y.\n\n* Perhaps providing a brief overview of the other reformulations introduced in the supplementary material in the main paper could give readers a glimpse into the broader scope of the study. Alternatively, focusing solely on one reformulation in the main paper and leaving the others for future work might streamline the presentation.\n\n* There is a typo in \"causal effects win which the effect of ...\"", "limitations": "Limitations were not clearly addressed in the paper, although some limitations are implicitly pointed out in the complexities and conditions under which the results hold true. It would be beneficial to explicitly discuss these limitations. Additionally, it would be valuable to explore whether there are specific limitations associated with the new reformulations of the problem compared to the initial formulation.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The paper contributes in making the identification of causal effects with lower-cost interventions feasible in practice.\n\n* The paper tackles a significant problem and is quite engaging; I truly enjoyed reading it.\n\n* All proofs are provided\n\n* All pseudo codes are provided", "weaknesses": "* The primary weakness of this paper lies in its presentation and clarity. I believe it would greatly benefit from another round of revision and restructuring by the authors to enhance its clarity and organization (see section questions), making it more accessible to readers who are not familiar with the topic.\n\n* The limitations were not clearly addressed (see section limitations).\n\n* In the introduction, the authors stated their intention to introduce several reformulations; however, only one reformulation was presented in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and positive assessment. Taking your comments into account, we have rewritten and restructured the relevant sections of the paper to improve the presentation and clarity. We respond to your comments and questions below.\n\n## Weaknesses:\n### W1:\nWe acknowledge the need for improvements in how the content is conveyed. We are refining our manuscript to enhance its readability based on the feedback we received. We are undertaking another round of revision and restructuring to enhance the clarity and organization.\n\n### W2:\nPlease see our answer to L1.\n\n### W3:\nThank you for noticing this and bringing it to our attention. Due to space limitations, we chose to present only the two most noteworthy and practical reformulations, namely WPMAX-SAT and ILP, in the main paper. We have revised the introduction to clarify that we present and focus on these two reformulations in the main text, while the other reformulations are provided in Appendix D.\n\n## Questions:\n### Q1:\nCosts are assigned to interventions on variables (i.e., conducting experiments). We consider heterogeneous costs, as certain experiments can be more costly to run than others. 'Cost' in this context can be in terms of:\n- **Financial Costs**: For example, in the healthcare system, different interventions can have varying financial implications. Upgrading medical equipment might be relatively inexpensive compared to implementing a comprehensive telemedicine service or enhancing emergency response systems.\n- **Time Resources**: Time is another critical aspect of cost. For instance, upgrading medical equipment in already existing hospitals may require significantly less time than building a new hospital from scratch.\n- **Other Resources**: This includes human resources and other logistical considerations. For example, implementing a new healthcare protocol might require extensive training for staff, which can vary in cost depending on the complexity and scope of the training required.\n\nAdditionally, some experiments are not possible to perform as they might be unethical or have not yet recieved approval from authorities, and for these experiments, we model the cost as infinite. For example, in medical research, conducting certain experiments might require exposing patients to possibly harmful or unapproved treatments or withholding treatments currently percieved as effective, which is ethically unacceptable.\n\nWe have included these concrete examples in the revised paper to help readers better understand the practical implications of costs.\n\n### Q2:\nThank you for pointing this out. We have adapted the notation in the introduction to be more consistent with the rest of the paper.\n\n### Q3:\nThank you for thoroughly going over our examples! In Fig. 2(d), notice that $\\\\{S_1\\\\}$ and $\\\\{S_2\\\\}$ are the two unique districts of $S=\\\\{S_1,S_2\\\\}$. As they are both singletons, we use $\\\\{S_1\\\\}$ and $S_1$, and $\\\\{S_2\\\\}$ and $S_2$ interchangeably for the sake of conciseness. Note that after intervening on a variable, in the resulting graph, all the incoming edges to that variable disappear, i.e., the intervened variable has no parents.\n\nFocusing first on $S_1$, we observe that after intervening on $S_2$, the resulting graph contains no hedges for $S_1$ by Definition 2. This is because the only sets $W \\supsetneq \\\\{S_1\\\\}$ that are districts (i.e., connected via bidirected edges) and contain $S_1$ are $W= \\\\{S_1, X_2\\\\}$, $W= \\\\{S_1, X_4\\\\}$, or $W = \\\\{S_1, X_2, X_4\\\\}$, and neither of these sets satisfy condition (ii), namely that all $w \\in W$ are ancestors of $S_1$ in $\\mathcal{G}[W]$. Looking now at $S_2$, the only ancestor of $S_2$ is $X_3$, and following an intervention on $X_3$, it is not in the same district with $S_2$. Therefore, by Definition 2, there are no hedges remaining for $S_2$.\n\nWe have added these explanations for both figures 2(b) and 2(d) in the revised version.\n\n### Q4:\nYou are right that there is a discrepancy between Example 1 and what we had written between lines 152 and 155. We have fixed the example to be consistent with what is stated in lines 152-155.\n\n### Q5:\nWe agree with your suggestion that focusing on one reformulation would streamline the presentation, which is why we concentrated on the WPMAX-SAT and ILP formulations. These two formulations are very similar, making it sensible to present both. To clarify this better, we have added an explanation in the main text on why we chose to focus on these reformulations:\n\n>\tBased on our extensive simulations provided in Section 5 and Appendix A, the WPMAX-SAT reformulation, when paired with a high-performance MAX-SAT solver like RC2, consistently outperforms other approaches in terms of speed and effectiveness. Similarly, the ILP formulation aligns very closely with the structure of the WPMAX-SAT approach, thus justifying our focus on these two formulations.\n\n### Q6:\nThe sentence should read \"... a specific class of causal effects in which the effect...\" We apologize for the oversight.\n\n## Limitations:\n### L1:\nWe have added a paragraph addressing the limitations in the main text. We provide the paragraph below:\n\n>\tThe main limitation of our reformulation is that it still involves solving an NP-hard problem, which inherently has a worst-case exponential complexity. However, it should be noted that the MCID problem itself is an NP-hard problem, meaning any reformulation will inevitably have an exponential worst-case complexity. Despite this, our WPMAX-SAT reformulation offers significant advantages over the initial formulation by expressing the problem as a single instance of a WPMAX-SAT problem. This approach allows for the use of well-studied and high-performance solvers, as demonstrated in our simulations. Moreover, our reformulation benefits from a quadratic complexity in the number of districts of $S$, compared to the exponential complexity of the initial formulation by Akbari et al., 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mJRm5ERfNS", "reviewer": "Reviewer_ARx2", "summary": "In this paper, the authors consider how to introduce interventional data based on observational data to make causal effect identifiability with the minimal cost. A high-dependent method is proposed by Akbari et al. [2022], which needs a very large computational cost. In this paper, by converting the problem to weighted partially maximum satisfiability problem, the computational cost is largely reduced. The authors prove that addressing the weighted partially maximum satisfiability problem equals to find to min-cost intervention target by Theorem 1 and Theorem 2. In light of the ease to calculation by adjustment criterion, the authors also establish the relevant results for adjustment criterion.", "questions": "Could the authors provide more clues about the reason that the SAT-based method performs better than the existing method?", "limitations": "No.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors present a detailed and very clear introduction to the related studies in the literature.\n\nThe experiment results show a giant efficiency improvement compared to existing studies. \n\nFor me, it is very novel to converting the problem to a weighted partially maximum satisfiability problem, through which the problem can be addressed efficiently. And the theoretical results seem solid.", "weaknesses": "I do not find evident weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review and positive comments. We respond to your question below.\n\n## Questions:\n### Q1:\nCould the authors provide more clues about the reason that the SAT-based method performs better than the existing method?\n\n**Response:**\n\nAt a high level, the previously existing method requires multiple calls to a subroutine solving an instance of the minimum hitting set problem, which is NP-hard. The number of calls to this subroutine can be exponential in the worst case, leading to solving exponentially many instances of a problem where each instance may require exponential time to solve. In contrast, our reformulation necessitates only a single call to a MAX-SAT solver. Additionally, the complexity of the previous methods grows exponentially with the number of districts of $S$, while the complexity of our method remains quadratic. This is due to the fact that the previous methods require enumerating all possible partitionings of the set of variables, whereas our SAT formulation avoids this unncessary enumeration by directly encoding the constraints into a single optimization problem, significantly reducing the computational burden.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ypN9nTmA3F", "reviewer": "Reviewer_Zgff", "summary": "This paper contributes to connecting the MCID problem—finding the minimum-cost interventions to identify a given causal effect, which has been proven to be NP-Complete—with four well-known problems, such as weighted maximum satisfiability and integer linear programming. These reformulations allow the original MCID problem to be solved by existing advanced solvers associated with the corresponding problems, reducing its computational complexity. The numerical experiments conducted demonstrate the improvements brought by the proposed methods.", "questions": "See weaknesses.", "limitations": "1. More details about the baselines and datasets should be provided in the manuscript. This includes a thorough description of the baseline algorithms used for comparison and the characteristics of the datasets employed in the experiments.\n2. The methodology part of this paper, especially Section 3.1, might hinder readers who are not familiar with SAT from fully understanding this kind of reformulation. It would be helpful to include a more detailed and intuitive explanation of the SAT concepts and their application in this context in the appendix.", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The writing is based on the theoretical analysis, and the notations in the paper are well explained.\n2. The topic this paper focuses on is practical, as practitioners can resort to proxy experiments when both observational studies and RCTs are difficult to collect or conduct.\n3. The numerical experiments indicate the effectiveness of these reformulations and the proposed inexact algorithms.", "weaknesses": "1. This paper provides four types of reformulations of the MCID problem. It would be better to add a discussion section about which reformulation users should choose for their specific problem and the reasoning behind the recommendation.\n2. Can the authors analyze the time complexity of the proposed heuristic algorithm?  Besides, a thorough analysis of the time complexity in experiment part would provide a deeper understanding of the algorithm's performance, particularly in terms of its behavior in worst-case and average-case conditions.\n3. In lines 230-231, The inclusion of $\\neg z_{k,l}$ in the SAT construction seems intuitive, but can the authors provide a more detailed explanation of its rationale? Specifically, it would be beneficial to understand how $\\neg z_{k,l}$ functions within the overall logic of the problem.\n4. The experimental results are solely based on synthetic data. It would be beneficial to evaluate the proposed method using real-world datasets, if possible, which would provide a more comprehensive validation of the method's effectiveness in practical applications.\n5. The writing of this paper mostly focus on the theoretical results, and may be difficult to be understood by the readers, especially for the example 1, a more straightforward example may be helpful for the paper presentation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s comments and feedback. We respond to your individual comments below.\n\n## Weaknesses:\n### W1:\nBased on our extensive simulations given in Section 5 and Appendix A, the WPMAX-SAT reformulation, when paired with a high-performance MAX-SAT solver like RC2, consistently outperforms other approaches in terms of speed and effectiveness. The ILP reformulation, on the other hand, provides a more straightforward and interpretable way for incorporating extra constraints, say domain expert knowledge. We have included a paragraph in Section 6 emphasizing the advantages of using each reformulation. \n\n### W2:\nThank you for pointing this out. Indeed, the time complexity of Algorithm 1 can be analyzed in a rather straightforward way. The short answer is that the worst-case complexity of the algorithm is cubic in the number of variables. In particular, the two bottle-necks are (i) the initial pre-processing of lines 2-3, which can take up to $n$ rounds of d-separation tests (each of which can be carried out using a depth-first search), and (ii) the minimum-cut instance solved at line 9, which is carried out using a min cut - max flow algorithm such as Edmonds-Karps or linear programming, for which the worst-case complexities are known; e.g., push-relabel algorithms or MKM take time at most $O(|V|^2\\sqrt{|E|})$ or $O(|V|^3)$ in the worst case. We will include the rigorous analysis in the final version.\n\nAs a side note, we would like to emphasize that our Algorithm 1 serves the main purpose of solving the minimum cost generalized adjustment set, but it also can be utilized as a very perofrmant heuristic for MCID, as seen in Section 5.\n\n### W3:\nWe have provided a more detailed explanation in the text, given below:\n> We need to ensure that for each district $S_\\ell$, there exists at least one intervention set $\\mathcal{I_k} \\in \\boldsymbol{\\mathcal{I}}$ such that by intervening on $\\mathcal{I_k}$, $S_\\ell$, becomes identifiable. However, as we do not require that *all* intervention sets hit the hedges formed for $S_\\ell$, we introduce the boolean variable $z_{k,\\ell}$, which indicates whether $I_k$ intersects (hits) the hedges formed for $S_\\ell$, and we add the clause $(z_{1,\\ell}\\lor\\cdots\\lor z_{r,\\ell})$ to the SAT expression to ensure *at least one* $z_{k,\\ell}$ is $1$. Then, if $z_{k,\\ell} = 1$, the solution of the $k^\\text{th}$ SAT expression must hit the hedges of $S_\\ell$, whereas if $𝑧_{k,\\ell} = 0$, there is no such obligation. As such, the $\\neg z_{k,\\ell}$ term ensures that if there is no need for $\\mathcal{I_k}$ to hit the hedges of $S_\\ell$ (meaning that another intervention set is already hitting them), we impose no constraints on the $k$-th copy. Note that when $z_{k,\\ell}=0$, or equivalently, $\\neg z_{k,\\ell}=1$, the $k$-th copy is already satisfied, imposing no unnecessary constraints. Note that without $𝑧_{k,\\ell}$, every copy would be forced to give a solution that hits $S_\\ell$, which would be undesirable.\n\n### W4:\nThank you for pointing this out. We have conducted new simulations on real-world networks, which we present and discuss in the general rebuttal.\n\n### W5:\nThank you for your valuable feedback. In response, we are revising parts of the introduction to make the concept of the MCID problem more accessible. Following your advice, we have modified the example (see the comment below) to be less technical and more straightforward.\n\n## Limitations:\n### L1: \nIn the revised version, we are providing more detail on the baseline algorithms that we compared our methods with. Below are the relevant modified paragraphs from the main text:\n\n>\tThe baseline algorithm with which we compare our exact algorithms is Algorithm 2 of Akbari et al., 2022, referred to as Minimal Hedge Solver (MHS). MHS runs as follows. It maintains a growing list of discovered hedges, and at each iteration, solves a minimum hitting set problem for this list of hedges. If the solution to this minimum hitting set problem is sufficient to make the query identifiable, it terminates. Otherwise, it discovers a new hedge and grows the list of its discovered hedges. As there can be exponentially many minimal hedges, as shown in Fig. 2&#40;c&#41;, the runtime of their algorithm is doubly exponential, which is corroborated by the poor performance in our simulations.\n>\t\n>\tWe compare our heuristic algorithm, Algorithm 1, with the two best heuristics of Akbari et al., $H_1$ and $H_2$. Both algorithms solve a weighted minimum cut problem to return a set of interventions. $H_1$ performs a minimum cut between $S$ and the parents of $S$ over the bidirected edges, while $H_2$ performs a minimum cut between $S$ and the bidirected neighbors of $S$ over the directed edges.\n\nAs for the datasets used, we explained them in lines 337-341 for the exact algorithms, and lines 356-359 for the heuristic algorithms. However, we have added more detail, as included below:\n\n>\tFor all simulations, we used the NetworkX library in Python to generate Erdos-Renyi (ER) graphs. ER graphs were generated by creating an upper triangular $n \\times n$ adjacency matrix, where $n$ is the number of vertices. Then, we permuted the rows and columns of the adjacency matrix to ensure that node indices are randomized.\n>\t\n>\tTo ensure reproducibility, we used a fixed random seed for graph generation. The code as well as detailed instructions, including the specific seed values and the script for graph generation, are provided in the supplementary materials.\n\n### L2:\nThank you for the feedback. We will add a detailed and intuitive explanation of the WPMAX-SAT problem, starting from the SAT problem and building up to the weighted partial MAX-SAT problem. Additionally, we will include the encoding of the depth-first traversal of a directed graph as a SAT problem. This example, being similar in spirit to our approach, is easier to follow and understand, and will help readers grasp the underlying intuition behind our reformulation more effectively.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "o4EXrZ2Lkn", "reviewer": "Reviewer_tZFY", "summary": "This paper provide a computationally efficient algorithm for finding the sets of variables $\\mathbf{Z}_1,\\cdots,\\mathbf{Z}_m$ that achieve the minimum intervention cost, allowing for $P(\\mathbf{y} \\mid \\operatorname{do}(\\mathbf{x}))$ to be identifiable from $\\{P(\\mathbf{V} \\mid \\operatorname{do}(\\mathbf{Z}_i)): i=1,\\cdots,m\\}$.", "questions": "1. In line 109, is the condition S \\subsetneq W is necessary?", "limitations": "1. This paper still solves the heuristic solution, instead of the exact solution. The exact solution of the problem still remains NP-hard.", "rating": 4, "confidence": 5, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "1. The research problem is interesting and practical.\n2. Experiments conducted on the large graph provide empirical evidence supporting the proposed method.", "weaknesses": "__1. Misleading and wrong statements__\n\nThis paper contains some statements that could mislead readers. First, there is a sentence that doesn’t acknowledge the previous works properly.\n\n> A middle ground between the two extremes of observational and experimental approaches was introduced by Akbari et al. [2022]\n> \n\nThe middle ground, which uses the fusion of observational and experimental data to identify the causal effect, is introduced by [Bareinboim and Pearl (2012)](https://arxiv.org/pdf/1210.4842), not Akbari et al., 2022. This sentence could mislead readers by ignoring existing works on the middle ground.\n\nSecond, this paper incorrectly defines some existing notions in theories of causal effect identification or gives new names to already existing concepts. \n\n- For example, a “district” is a *maximal* set of vertices connected by bidirected edges [[Richardson et al., 2023](https://arxiv.org/abs/1701.06686) or [Shpitser et al., 2014](https://web.archive.org/web/20181102234555id_/https://www.jstage.jst.go.jp/article/bhmk/41/1/41_3/_pdf)]. Therefore, given a (sub-)graph $\\mathcal{G}(T)$ and a set of vertices $S$, there is only one district containing $S$ in $\\mathcal{G}(T)$. However, this paper wrongly defines “district” without invoking *maximality.*\n- Another example is “hedge hull.” Acknowledging the original definition of the district, the hedge hull is just a hedge defined by [Shpitser et al., 2008](https://jmlr.org/papers/volume9/shpitser08a/shpitser08a.pdf) and [Shpitser al el., 2012](https://arxiv.org/pdf/1202.3763), which is an ancestor of $S$ and a district at the same time. I don’t see why the authors redefine the original “hedge” as “hedge hull.” It only raises confusion in comprehending the paper.\n\nThird, some of statements are not sound. Specifically, the following sentence in line 133-134 seems to be incorrect.\n\n> Note that there is no hedge formed for $S_{\\ell}$ in $\\mathcal{G}[V \\setminus \\mathcal{I}_k]$ if and only if \\mathcal{I}_k hits every hedge of $S_{\\ell}$ (i.e.,for any hedge $W \\in H_{\\mathcal{G}}(S_{\\ell})$,$\\mathcal{I}_k \\cap W \\ neq \\emptyset$).\n>\n\nFor example, \n\n* Consider the case where $S_{\\ell}$ is identifiable in $\\mathcal{G}$. Then, there must be no hedge formed for $S_{\\ell}$ in $\\mathcal{G}$. However, the condition where $\\mathcal{I}_k$ and $W$ is non-overlapped is violated. \n\n* Another case is when $S_{\\ell}$ itself is a hedge. Then, with $\\mathcal{I}_k = \\emptyset$, the sentence doesn't hold. \n\nAlso, The following sentence is false: \n\n> The query of interest is identifiable if and only if HG (S) = S, that is, the hedge hull of S contains no other vertices.\n> \n\nConsider the graph $\\mathcal{G} = ( W → R → X → Z → Y, W ↔ X, W↔Z, X↔Y )$. Here, $S = \\operatorname{Anc}_{V \\setminus X}(Y) = (Z,Y)$, but the hedge hull found from Algorithm 2 is $(X,Z,Y)$. However, the causal effect P(Y | do(X)) is identifiable from $\\mathcal{G}$. \n\n---\n\n__2. Weak presentation__ \n\nFirst, the paper weakly exemplifies the SAT Construction Procedure. Without providing detailed examples of how 3-SAT can be constructed using the graphs in Figure 1, it's hard to understand how the problem is reformulated using 3-SAT.\n\nSecond, many important results are omitted (e.g., a detailed example for 3-SAT construction and IP formulation) and presented in the supplementary document (e.g., Algorithms 2 and 3). Specifically, it's impossible to comprehend this paper without reading Section B. Given that reading the supplementary document is not mandatory for reviewers and readers, I encourage the authors to reorganize the paper to make it more comprehensible.\n\n\n---\n\n__3. Lack of analysis \\& misleading contribution__ \n\nTo my knowledge, the exact solution for integer programming is NP-hard, and only heuristic methods are available for efficiently solving the problem. A natural question is the gap between the exact solution and these approximated solutions.\n\nAlso, the authors need to be more cautious in presenting their contribution. The fast experiment design was achieved by heuristically solving the problem, and the exact solution remains NP-hard. However, the paper is presented as if the NP-hard problem has been solved just by reformulating the problem.\n\n---\n\n__4.Minor comments__\n\n1. The following sentence is not parsable. Is “win” a typo? \n\n> Moreover, Akbari et al. [2022]’s algorithm was tailored to a specific class of causal effects win which the effect of interest is a functional of an interventional distribution where the intervention is made on every variable except one district of the causal graph\n>", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thorough reading of our paper and their detailed feedback. We have addressed each comment and question below.\n## Weaknesses:\n### W1:\nWe acknowledge this comment. We have made our statements more precise to clarify that data fusion for causal identification goes way back (as we ourselves build upon a follow-up to Bareinboim and Pearl, 2012, namely Lee et al., 2020), and we are revising our manuscript to include a comprehensive literature review on this; but that the idea of surrogate experiment design for causal identification was put forward by Akbari et al., 2022.\n### W2:\nWe indeed slightly diverged from the original definitions of hedge and district, particularly by not imposing maximality. This was done solely to simplify the presentation of our work and enhance readability. These adjusted definitions are what make our arguments sound. However, we acknowledge that this can be confusing for certain readers. To address this, we are updating our manuscript to use alternative names or be more explicit about the altered definitions wherever possible. We have additionally included proper citations to the relevant papers by Richardson et al. 2023 and Shpitser et al. 2008, 2012, 2014.\n### W3:\nIf $S_\\ell$ is identifiable in $\\mathcal{G}$, i.e., there is no hedge formed for$S_\\ell$ in $\\mathcal{G}$, then $H_\\mathcal{G}(S_\\ell) = \\emptyset$. Thus, the statement *for any $W$ in $H_\\mathcal{G}(S_\\ell)$, $\\mathcal{I}_k \\cap W \\neq \\emptyset$* is true by the concept of vacuous truth, as the antecedent (i.e., $\\forall W \\in H_\\mathcal{G}(S_\\ell)$) can never be satisfied.\n\nAs for your second example, we are not sure what you mean by \"when $S_\\ell$ is a hedge.\" By our definition of hedge (Def. 2), $S_\\ell$ can never be its own hedge. If you meant that $S_\\ell$ is within a hedge for another district $S_k$, then our statement is still valid. For instance, consider the graph of Fig. 2(d), where $S_2$ is involved in a hedge formed for $S_1$, and our statement is still valid with $I_k=\\\\{S_2\\\\}$.\n### W4:\nOur Def. 3 defines the hedge hull for a (single) district. Right after this definition, we define the hedge hull of an arbitrary set $S$ as the union of the hedge hulls of each of its districts. In your specific example, $S=\\\\{Z,Y\\\\}$ consists of two districts, $S_1=\\\\{Z\\\\}$ and $S_2=\\\\{Y\\\\}$. Following Def. 3, the hedge hull of $S_1$ is $S_1$ itself, and the same goes for $S_2$. Therefore, $\\mathcal{H}_{\\mathcal{G}}(S)=S_1\\cup S_2=S$, which indicates that $P(Y\\mid do(X))$ is identifiable, as expected.\n\nOur paper first covers the case where $S$ comprises a single district, then generalizes the results to the case of arbitrary sets (see lines 157-158,). As such, Alg. 2 is designed for single-district $S$. We have made this clearer in the revised version. In particular, we have explicitly stated that if $S$ comprises more than one district, Alg. 2 is run on each district separately to compute the hedge hull of $S$.\n### W5:\nDue to space constraints, we had to move the details of the SAT construction to Appendix B.2. However, with the extra page allocated for the camera-ready, we are relocating these construction details to the main text. We have also provided a walkthrough of how the SAT expression can be constructed using a toy graph from Figure 2. This will clarify the SAT reformulation. We will also add the DFS encoding of a graph as a SAT problem in the appendix and reference it in the main text, aiding readers, especially those new to SAT constructions.​\n\nWe have condensed Algorithms 2 and 3, and brought them into the main text, with a brief explanation of the rationale behind them to aid the reader in understanding the work more easily.\n### W6: \nIt’s important to clarify that the MCID problem is NP-hard, as shown by Akbari et al. 2022, with the best achievable polynomial-time approximation being within a $\\log(n)$ factor, where $n$ is the number of vertices. Thus, the worst-case time complexity of our reformulations is expected to be exponential in $n$.\n\nOur reformulations not only solve the problem exactly, but also provide a significant speedup of 1,000 to 100,000,000 times for the single-district case. \n\nMoreover, for the multiple-district case, our approach is only quadratic in the number of districts (theoretically guaranteed), unlike the previous method which required iterating over an exponential number of partition sets. This efficiency is demonstrated in Fig. 3b, showing speedups of 50 to 10,000 times for a modest number of districts.\n\nWe believe therefore the term “fast” is justified. Although the exact solution remains exponential in the worst case, our reformulations make solving these problems practically feasible and significantly more efficient, especially for large graphs.\n\nAnother significant contribution is our novel min-cost experiment design for generalized adjustment (Section 4), for which we provide a polynomial-time algorithm.\n\nThese distinctions will be more clearly presented in the revised text to accurately reflect our contributions and their practical implications.\n## Questions (Q1):\nYes, the condition $S \\subsetneq W$ ensures that $S$ cannot form a hedge for itself, in line with Shpitser and Pearl (2006), which impose $F_1\\subsetneq F_2$ for two r-rooted c-forests. Without this, $S$ would always have a trivial hedge, itself, Consequently, many of our statements and proofs would need to be modified to exclude the trivial hedge. complicating many statements and proofs. For example, \"hitting all of the hedges of $S$\" would need to be \"hitting all of the nontrivial hedges of $S$.\"\n\n### Thank you for your time and detailed feedback. We are confident in the correctness of the technical statements in our paper. We appreciate your other comments, most of which are easily fixable, and will be promptly addressed in the manuscript. We kindly request that you acknowledge the soundness of our work and consider increasing your score accordingly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you to all reviewers for your valuable feedback. We have carefully reviewed each comment and addressed all questions and concerns in our individual rebuttals. We welcome further questions or comments and look forward to engaging with you during the discussion period. We have made the following major changes and additions:

1. Streamlined our paper and clarified our focus on the WPMAX-SAT and ILP formulations, addressing concerns raised by Reviewer $\color{darkblue}{\textbf{Jqzf}}$ and Reviewer $\color{darkred}{\textbf{Zgff}}$.
2. Conducted new experiments on real-world data, as requested by Reviewer $\color{darkred}{\textbf{Zgff}}$, with results presented below.
3. Enhanced readability and ease of understanding, particularly for our SAT reformulation, in response to feedback from Reviewer $\color{darkred}{\textbf{Zgff}}$ and Reviewer $\color{darkgreen}{\textbf{tZFY}}$. We provide a walkthrough example of the SAT construction for a toy-example graph below.
4. Implemented other clarity improvements, including providing intuitions about the SAT construction and clarifying our definitions, as suggested by all reviewers.

Thank you again for your feedback. We kindly request that you reevaluate your assessment given our responses and improvements.

## New experiments on real-world data
We have conducted new experiments using 17 real-world networks from the Bayesian Network Repository [1]. This repository encompasses networks from diverse domains such as biology, engineering, medicine, and social science.

In our experiments, each network from the repository is utilized as the DAG on the known variables. We assign a random cost to each variable, sampled uniformly at random from $[1, n]$. We then introduce hidden variables by randomly sampling bidirected edges with probabilities of 0.01, 0.1, and 0.3, resulting in 50 ADMGs per network. For each ADMG, we select $S$ to be a singleton consisting of the last node in the causal order. This choice ensures that any other node would not reduce the network’s size by ignoring some vertices and edges, as outgoing edges from $S$ are irrelevant for the MCID problem.

Subsequently, we implemented the exact algorithms: minimal hedge solver (Algorithm 2 of Akbari et al., 2022), ILP, and WPMAX-SAT. We also tested the heuristic algorithms $H_1$ and $H_2$ from Akbari et al., 2022, alongside Algorithm 1 from our work. 

The results are given in the uploaded PDF document. In Fig. 1, we present a semi-log bar chart of the average time taken for each exact algorithm to solve an instance of a graph for each network. Notably, our approaches, ILP and SAT, consistently outperform MHS by an average factor of over 100, and by more than 1000 times on the largest network, link. Additionally, SAT demonstrates superior performance in all but two networks, _andes_ and _diabetes_.

In Fig. 2, we provide a semi-log plot of the normalized cost of the heuristics $H_1$ and $H_2$ from Akbari et al., 2022, and our Algorithm 1, averaged across each network. It is evident that Algorithm 1 significantly outperforms $H_1$, often by one to two orders of magnitude. Although $H_2$ performs better due to its focus on performing cuts on nodes over directed edges (which are fewer), its cost remains higher than that of Algorithm 1.

Overall, the results align with our findings from synthetic simulations in the main text. Our WPMAX-SAT and ILP formulations surpass the previous state-of-the-art approach by Akbari et al., 2022, with WPMAX-SAT being the fastest. Furthermore, our polynomial-time Algorithm 1 consistently outperforms the heuristics proposed by Akbari et al., 2022.

[1] Scutari M (2010). “Learning Bayesian Networks with the bnlearn R Package.” _Journal of Statistical Software_, **35**(3), 1–22. [doi:10.18637/jss.v035.i03](https://doi.org/10.18637/jss.v035.i03).

## Walkthrough SAT construction example
Consider the graph $v_1\to v_2\to v_3$, $v_1\leftrightarrow v_2 \leftrightarrow v_3$ where $S = \\{v_3\\}$, with $n=3$ vertices. The hedge hull of $S$ is $\\{v_1,v_2, v_3\\}$, and $m=\left|\\{v_1,v_2\\}\right| =2$. Following the SAT construction procedure outlined in lines 193-203, we will carry out the construction in $m+2=4$ steps. Our SAT expression will consist of 8 variables, $x_{i,j}$ for $i\in\\{1,2\\}$ (corresponding to $v_1$ and $v_2$), and $j\in\\{0,1,2,3\\}$, corresponding to the four steps of construction.

### Step 1: 
We add the clauses $(\lnot x_{1,0} \lor x_{1,1} \lor \lnot x_{2,1})$ and $(\lnot x_{2,0} \lor x_{2,1} \lor \lnot x_{3,1})$, corresponding to the edges $v_1\to v_2$ and $v_2\to v_3$, respectively. Note that by convention, $x_{3,1}=1$, and the second clause reduces to $(\lnot x_{2,0} \lor x_{2,1})$.
### Step 2: 
For the edge $v_1\leftrightarrow v_2$, we add the clauses $(\lnot x_{1,1} \lor x_{1,2} \lor \lnot x_{2,2})$ and $(\lnot x_{2,1} \lor x_{2,2} \lor \lnot x_{1,2})$.
Similarly, for the edge $v_1\leftrightarrow v_3$, we add the clauses $(\lnot x_{1,1} \lor x_{1,2} \lor \lnot x_{3,2})$ and $(\lnot x_{3,1} \lor x_{3,2} \lor \lnot x_{1,2})$.
Since by convention, $x_{3,1}=x_{3,2}=1$, the latter two clauses reduce to $(\lnot x_{1,1} \lor x_{1,2})$ and $1$, respectively.
### Step 3: 
We add the clauses $(\lnot x_{1,2} \lor x_{1,3} \lor \lnot x_{2,3})$ and $(\lnot x_{2,2} \lor x_{2,3} \lor \lnot x_{3,3})$, corresponding to the edges $v_1\to v_2$ and $v_2\to v_3$, respectively. Again $x_{3,3}=1$, and the latter clause reduces to $(\lnot x_{2,2} \lor x_{2,3})$.
### Step 4:
The clauses $\lnot x_{1,3}$ and $\lnot x_{2,3}$ are added.

Finally, combining all the clauses together, the SAT expression is given by
$(\lnot x_{1,0} \lor x_{1,1} \lor \lnot x_{2,1}) \land (\lnot x_{2,0} \lor x_{2,1})
\land
(\lnot x_{1,1} \lor x_{1,2} \lor \lnot x_{2,2}) \land (\lnot x_{2,1} \lor x_{2,2} \lor \lnot x_{1,2})
\land
(\lnot x_{1,1} \lor x_{1,2})
\land
(\lnot x_{1,2} \lor x_{1,3} \lor \lnot x_{2,3})
\land
(\lnot x_{2,2} \lor x_{2,3})
\land \lnot x_{1,3} \land \lnot x_{2,3}.$

Meta-review: Reviewer Zgff reduced their score to a 2 from a 4 after rebuttal. Based on the discussion, it is clear they have taken this as a retaliation because the authors posted a comment since the authors answered the questions in great detail. Posting comments before reviewer engagement is not forbidden by the NeurIPS policies. I agree with the authors that this is very unprofessional/policing behavior by the reviewer, rather than evaluating the scientific merit of the work.  

Because of this, I am treating Reviewer Zgff's score as a 4 instead of the updated 2. This brings the average to a 5, making this a borderline paper. 

With this, overall no reviewer has a strong opinion about this paper in its current form. Two reviewers acknowledge the validity of the contributions; although admittedly one with low confidence. The critical reviewer #tZFY, who is also an expert, provided very detailed feedback. There were initial concerns around inconsistent use of some previously well-known concepts, and some around clarity. Most of these seem to have been cleared out by the rebuttal although the reviewer seems to be hesitant to increase their score without seeing a revised version with changes implemented. There seem to be no major concerns by any of the reviewers currently.
Decision: Accept (poster)