Causal Discovery in Probabilistic Networks with an Identifiable Causal Effect
Authors: Sina Akbari
Fateme Jamshidi
Ehsan Mokhtarian
Matthew James Vowels
Jalal Etesami
Negar Kiyavash
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Causal Discovery
Causal Identification
ADMG
Causal Inference
Probabilistic Networks
NP-hard

Abstract: Causal identification is at the core of the causal inference literature, where complete algorithms have been proposed to identify causal queries of interest. The validity of these algorithms hinges on the restrictive assumption of having access to a correctly specified causal structure. In this work, we study the setting where a probabilistic model of the causal structure is available. Specifically, the edges in a causal graph are assigned probabilities which may, for example, represent degree of belief from domain experts. Alternatively, the uncertainly about an edge may reflect the confidence of a particular statistical test. The question that naturally arises in this setting is: Given such a probabilistic graph and a specific causal effect of interest, what is the subgraph which has the highest plausibility and for which the causal effect is identifiable? We show that answering this question reduces to solving an NP-hard combinatorial optimization problem which we call the edge ID problem. We propose efficient algorithms to approximate this problem, and evaluate our proposed algorithms against real-world networks and randomly generated graphs. 

24 has motivated the development of numerous techniques for understanding whether causal query Causal Discovery in Probabilistic Networks with an Identifiable Causal Effect
Anonymous Author(s)
Affiliation
Address
email
Abstract
Causal identification at the core the causal inference literature, where complete algorithms have been proposed identify causal queries of interest. The validity these algorithms hinges on the restrictive assumption of having access to a correctly specified causal structure. In this work, study the setting where a probabilistic model of the causal structure is available. Specifically, the edges in a causal graph are assigned probabilities which may, for example, represent degree of belief from domain experts. Alternatively, the uncertainly about an edge may reflect the confidence of particular statistical test. The question that naturally arises in this setting is: Given such a probabilistic graph and specific causal effect of interest, what is the subgraph which has the highest plausibility and for which the causal effect is identifiable? We show that answering this question reduces to solving an NP-hard combinatorial optimization problem which call the edge ID problem. We propose efficient algorithms to approximate this problem, and evaluate our proposed algorithms against real-worke networks and randomly generated graphs.
3
10
11
12
13
14
Introduction
18
A large proportion of questions of interest in various fields including but not limited to psychology. social sciences, behavioural sciences, medical research, epidemiology, economy, etc. are causal in In order to estimate causal effects, the gold standard is performing controlled interventions and experiments. Unfortunately, such experiments can be prohibitively expensive. unethical, or impractical (consider. for example, an experiment in which participants are required smoke in order to understand the links cancer) [3] 5]. In contrast, non-experimental data are 23 comparatively abundant, and no expensive interventions are required to generate such data. This
17
19
nature 21 13
20
21
22
25 can be answered using observational data. Specifically, if particular causal query is identifiable, it
26 means can be expressed as function the observational distribution, and thus estimated from observational data (at least in principle).
significant body of the causal inference literature is dedicated the identification problem 18 13 [6 [2]. . In particular, Huang and Valtora presented a complete algorithmic approach to decide the identifiability of specific query, and proved that Pearl's do calculus is complete, in the sense that if a causal query is identifiable, a sequence of do calculus rules can be applied to derive an identification expression for that query [6]. Furthermore, Shpitser and Pearl provided graphical 33 criteria to decide the identifiability, based on the hedge criterion [16]. However, all of these results
29
30
31
32
34 hinge on full specification of the causal structure, i.e., access to correctly specified Acyelic Directed
35 Mixed Graph (ADMG) that models the causal dynamics of the system. This requirement is restrictive
36 a number of ways. Firstly, the causal identification problem concerned with inference from the observational data, but the ADMG cannot be inferred from the observational distribution alone.
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

38 Secondly, structure learning methods rely heavily on statistical tests, which are prone to errors arising
39 from lack of sufficient data and pethod-speciffe limitations [5] which can result in misspecification of the causal structure.
40
As opposed to full specification of the causal structure, propose the setting in which only have access to probabilistic model of the causal structure. For instance, an ADMG G is given along with probabilities assigned to each edge of G. An example is shown in Figure Ia These probabílities could represent uncertainties arising from statistical tests, or the strength of belief of domain experts concerning the plausibility of the existence of an edge. Under this setting, each ADMG on the set of vertices of G is assigned its own plausibility score. Since the causal structure is not deterministic anymore, answering questions such as "is the causal effect P(Y [d)(X)) identifiable?" also becomes probabilistic in nature. One can compare the overall plausibility of different subgraphs in which the causal effect identifiable, and then select the graph which maximises the plausibility. Indeed, identification is often assumed on the basis of ignorability (i.e., no unobserved confounders exist) 8 thus the use of probabilistic models enables us to quantify the strength of such an assumption.
42
43
44
45
48
47
48
49
50
51
52
In this work, for a specific causal query P(Y|do(X), we first answer the question "which graph has the highest plausibility among those compliant with the probabilistic ADMG model that renders P(Y do(X)) identifiable?" The answer to this question then shows us with what confidence we can
53
54
55
carry out the causal identification task using the combination of the data at hand and the corresponding probabilistic model.
58
Noting that the causal identification task is carried out through identification formula which is based on the causal structure, our second focus is on deriving an identification formula for a given causal query that holds with the highest probability. This problem is different from the former in the sense that a single identification formula can be valid with respect to set of different graphs. Therefore, the probability that given identification formula is valid for causal query would be the aggregate probability of all graphs on which this formula is valid. We shall illustrate this point in more detail through Example Section 2 To identify the most probable identification formula, we first show that if an identification formula is valid w.r.t. a causal graph, it is also valid w.r.t. all its edge-inducee subgraphs. Afterwards, we propose surrogate problem (see Problem 2 in Section 88 2. that recovers a causal graph with highest aggregated probability of its subgraphs. Both problems 67 discussed in this work are aimed at evaluating the plausibility of performing causal identification for a specific query given a dataset and non-deterministic model describing the causal structure.
58
59
60
61
62
63
64
65
68
To sum up, our main contributions
follows.
70
1. We study the problem of causal identifiability in probabilistic causal models, where there are uncertainties about the existence of edges and whether a given causal effect identifiable. More precisely, we consider two problems: 1) finding the most probable graph that renders desired causal query identifiable, and 2) finding the graph with the highest aggregate probability over its edge-induced subgraphs that renders a desired causal query identifiable.
71
72
73
74
75 2. We show that both aforementioned problems reduce to special combinatorial optimization problem which we call the edge ID problem. We prove that the edge ID problem NP-hard, and 77 thus, so are both of the problems we discussed.
78
78
3. We propose several exact and heuristic algorithms for the aforementioned problems.
79 In Section 2, we introduce the terminology and formally define the two problems we are considering 80 in this work. In Section 3 we show that both of these problems are equivalent to the edge ID problem.
81 Furthermore, we show that the edge ID problem NP-hard. We discuss algorithmic approaches (both exact and heuristic) in Section Empirical evaluations of our algorithms are presented in Section
83
5 Proofs and accompanying code are provided in the appendices and in supplementary material, respectively.
84
2
Preliminaries
85
86
We utilize small letters for variables, and capital letters for sets of variables. Calligraphic letters are used to denote graphs. An acyelic directed mixed graph (ADMG) g = (VS,E% Egg Eg) is defined as an
87
88 acyclic graph on the vertices Vo, where Ey S VV x ve and E C (V2) are the set of directed and bidirected edges among the vertices, respectively. With slight abuse of notation, if Ey U Eg
2

---

(a) ADMG G.
(b) 91 C G.
(c) 92 C
Figure 1: (a) An example of a probabilistic ADMG with corresponding edge probabilities. (b) and (c) are two different subgraphs of G in which Qlyl is identifiable.
90 write E G. We use G' C G when G' is an edge-induced subgraph of i.c. g' = (VV5' EE Eg )
91 where V V9 and E E for i E d). We denote by [[X] the vertex-induced subgraph 92 of G over the subset of vertices X C V9. For set of vertices X, we denote by Ancç(X) the set of vertices in & that have a directed path to X. Note that X C AAncg(X) Let Px (Y) ) be a shorthand for P(Y do)).., and pM (-) denote the distribution of variables described by the causal model M.
93
94
Definition 1 (Identifiability (3).. Given a causal ADMG 9 (vØ, Egg ) and two disjoint subsets of variables X, C V9, the causal effect of X on Y, denoted by Px(Y), is identifiable in G if PM (Y) = P (Y) for any two models M1 and M2 that induce G and PMi (VG) - (VS) > O. Definition 2 (Valid identification formula). For causal ADMG G over variables v and causal query Px (Y), we say a functional F defined on the probability space over V is a valid identification formula for Px (X) in G if P (Y) = MMaa (Y) = F(PM (V9) = F(PM (V9)) for any two models Mi and M2 that induce G and PM (V9) = PMa (V9) >
96
97
98
39
100
101
102
For any query (Y), let [9]aa(Pxx)) denote the set of subgraphs of G in which Px Px(Y) is iden- tifiable (note that if G is complete graph, [9] (Y)) is the set of all graphs in which Px (Y) is identifiable.) We denote by Q the causal effect of V V on i.e. Q[y]= = P(Y (VV ()).
103
104
Definition 3 (District 44. For ADMG G = (VS,E%) E,, ). let Gop denote the edge-induced subgraph of G over its bidirected edges. X S V is a district (aka c-component) in G if G is connected.
107
Definition& 4 (Hedge (6)). Let G be an ADMG, and Y S X be two subsets of its vertices, where Y is a district in G[Y). Vertices X form hedge for Q if X is a district in G[X] and xncgix(()) = x[ Definition 5 (Maximal hedge (... For ADMG G and a set of its vertices Y, let X be the union of all
108
hedges formed for Q Graph G[X), denoted by (G Y), is called the maximal hedge for Q
110
As an example, both sets {t,z} and {2, x) form hedge for Q[xc] in G in Figure la and g[x 2, t]] the maximal hedge for Q(a]].
111
112
113
2.1
Problem setup
Let g= = (VV Egg ) be an ADMG, where V is the set of vertices each representing an observed variable of the system, Eÿ is the set of directed edges, and E is the set of bidirected edges among
114
115
V4 We know a priori that the true ADMG describing the system is an edge-induced subgraph of and we are given a probability map that indicates for each subgraph of G such G.. with what 118 probability G. is the true causal ADMG of the system. We denote this probability as P(G.). For
116
119 instance, if edge probabilities pe are assumed to be mutually independent, P(G.) takes the form:
P(G.) = II [1
(1)
eEG.
<gC,
120
In what follows, we will refer to P(G.) simply as the probability of the ADMG Ge. The first problem 121 of our interest is formally defined as follows.
122 Problem 1. We consider the problem of finding the most probable edge-induced subgraph of G. in
which the causal effect Q[Y) identifiable. That is, the goal is to find the ADMG G defined by
123
g"
arg max P(G.).
9,C9.
G. e.
I Akbari et al. 1 showed that this intuitive definition is equivalent to the standard definition of hedge in 16 Note that G can be complete graph over both its directed and bidirected edges.
3

---

Figure 2: Three different graphs that share the same set Ancg((u)) - (2,1).
We will prove in Proposition [ that if Q[Y] is identifiable in G. then it is also identifiable in every edge-induced subgraph of G. Tn other words, if G is a feasible solution to the above optimization problem, so all its edge-induced subgraphs. Furthermore, the same identification functional that is valid w.r.t. G, is also valid w.r.t. every subgraph of G. Let us illustrate this first on an example.
124
125
126
127
128
Example 1. Consider the ADMG in Figure [a independence among the edge probabilities, the subgraph of G illustrated in Figure 1b has probability
With the given edge probabilities and assuming
130
0.7 x 0.7 x 0.1 = 0.049, whereas the subgraph of Figure has probability 0.3 0.3 x 0.9 = 0.081 (see Eq. (1) If we were solve Problem [ we would choose G2 over Gr, it has higher probability. Now consider identification formulas in O1 and G2, respectively:
132
Fi: - F2: Q[ - [ PXXXXXZT))
Z,T
Fi is a valid identification formala for any edge-induced subgraph of 91 (see Proposition 7 Analogously, F2 is valid for all edge-induced subgraphs of Gz. If we consider the aggregate probability of the subgraphs of 91 and G2, ie.,
133
134
135
Σ P())=11- 0.9 0.1,
= (.70 x (1 0.7) 0.09,
versus
GCOL
GCG2
136
then should prefer choosing 91 over G2, as its identification formula Fi is more likely to be valid than F2 considering the fact that for all its subgraphs, the identification functional Fi is still valid.
137
138
Plausibility of a certain identification functional F is the sum of the probabilities of all graphs in which F is valid given the query of interest. Finding the most plausible identification formula for a given query requires computing the plausibility of all formulae. Since the space of all formulae is intractable, an alternative approach to solve this problem is enumerating all valid formulae for given graph. This changes the search space of the problem to the space of all graphs. However, this is yet another challenging and to the best of our knowledge open problem. Therefore, we propose the following problem as a surrogate that maximizes a lower bound of the most plausible identification formula. To do so, we use the result of Proposition D that shows when an identification functional is valid in causal graph, it also valid in all its edge-induced subgraphs.
139
140
142
144
146
147
Problem Consider the problem of finding the edge-induced subgraph H. of G with maximum aggregate probability of its subgraphs. in which Q[Y is identifiabl. Formally.
148
H := arg max
Σ P(G).
(3)
G. G. G(I OCG.
149
In other words, we are looking for graph H. with the maximum aggregate probability of its subgraphs, among the graphs in [[]aa()))) i.c., the graphs in which Q[Y] is identifiable. Running an identification algorithm (such as the ID function of (16) on H2 yields an identification formula for Q which is valid at least with the aggregate probability of the subgraphs of H" Therefore, Problem is surrogate to recovering the identification formula with the highest plausibility.
150
151
152
153
154 In the sequel, for simplicity, we study Problems I aand Junder the following assumption. However, as proved in Appendix C our results are valid in more general setting where we allow only for perfect negative or positive correlations among the edges. An example of perfect negative correlation between two edges that both of them cannot exist simultaneously. Appendix C.I discusses the significance of this generalization.
155
156
157
158
159
Assumption 1. The edges of are mutually independent. That is, the probability of subgraph G, of G is of the form in ①
160
Remark 1. It is noteworthy that our results are not limited to cuusal queries of the form Q = P(Y|do(VS (, Y)). They can be applied to general causal queries of the form Px 182
if the set Ancoux(Y) is known. This is because the causal query Px(Y) can be expressed as

---

184
Am x OY Q[Ancexxx (Y), where Ancgxx(Y) is the set of ancestors of Y in 9 after removing the vertices of X. Furthermore, Px is identifiable in G if and only if Q (Y)) is iden- rifiable in 9 19 16 9. Note that the assumption that Anco, x (Y) known is not equivalent to precluding uncertainty on the directed edges (as in the case of fuxing the edge probabilities to 0 or 1), but it rather imposes perfect correlation rype of constraint. Consider for instance the three graphs of Figure 2 where all of them share the same set Aneg, x x(Y) = {z, t}. In fact, knowing this set forces a constraint of the type that if the edge -+ y does not exist, the path z -> t -> must.
185
186
187
188
189
170
3
Reduction to Edge ID problem and establishing complexity
172 We begin this section with the following proposition, to which we referred before. Thereafter, discuss the hardness of the two problems considered in this work.
173
174
Proposition 1. For any causal query Px (Y) and ADMG g. F is valid identification fortifiiaatonoormlllll for Px (Y) in G 2). then F a valid identification formula for Px (Y) ) in any g' S G.
175
178
All proofs are presented in Appendix A what follows, we first formally define the edge ID problem. and then show the equivalence of Problems ! and too
to the edge ID problem under Assumption] !
177
Definition (Edge ID problem). For ADMG 9 = (VS, Ed F.)). a set of non-negative edge weights Wg = {we 2 Ole E G). and a causal query Q for subset of variables Y S V the objective of the edge ID problem is to find the set of edges E C E. U Eg with minimum aggregated weight in the graph resulting from removing F. from G. Formally,
178
179
180
(cost), such that Q[Y) is identifiable
E = arg min
Σ We
ECEQUET CE s.t. G' C'=(VVEE EAAAEEE
(4)
182 We implicitly assume that the cost of removing a set of edges from G is the sum of the weights of each individual edge.
184
The following result unifies the two problems considered in this work by establishing their equivalence to the edge ID problem. This is done by transforming Problems [ad with multiplicative objectives into the edge ID problem that has an additive objective.
185
186
Lemma 1. Under Assumption 7 Problem 7 is equivalent to the edge ID) problem with the edge weights chosen to be the log propensity ratios, ie., We = max log( )p Ve E G. Moreover, Problem 2 is equivalent to the edge ID problem with the choice of weights We = - llo((1 pe), Ve E G. That is, an instance of Problems 7 fand) [ can be reduced to an instance of the edge ID
188
190
problem in polynomial time, and vice versa.
192
As we mentioned earlier, the equivalence of these three problems can be established in more general settings than what is described under Assumption We refer the interested reader to Appendix [foo discussion on one such setting. The following result shows that no polynomial-tin algorithm for solving any of these three problems exists unless P NP.
193
194
195
196
Theorem 1. The edge ID problem is NP-hard.
197
Theorem
iss established through a reduction from the minimum vertex cover problem, which is known to be NP-hard [II]. Theorem iis key result which shows the hardness of recovering the most plausible graph in which a specified causal effect of interest is identifiable.
199
200
Corollary 1. Problems I and are NP-hard under Assumption
7
is noteworthy that the size of the problem depends on the number of vertices of G. i.e., |V9, and the number of edges of G with finite weight, i.e., | Eg + E Since the ID algorithm (function ID of [6) runs in time ( ), the brute-force algorithm that tests the identifiability of Q in every edge-induced subgraph of G and chooses the one with the minimum weight of deleted
201
202
203
edges runs in time ( E (| In the next Section, we present various algorithmic approaches
205
for solving approximating the solutions to these problems.
5

---

Algorithm 1 Recursive Algorithm for edge ID.
1: function EDGEID(G, Y, We, wbb wh)
2:
H. < MH(G.Y)
3: if H. G[Y] then return (True,
4:
ID t False, Emin +- 0
5:
while True do
6:
- The edge of H. with minimum weight
7:
if e 00 or We > wh then return (ID, Eman)
(id, E) <- EDGEID We \ {wo), w We wh we
8:
9:
if id = True then
ID + True, WE + We -E,EE We,
11:
wab s- WE. Eainn t- EU [e( it' S wtt then return (ID, Emin)
12:
13:
Update we +- 0o in Wg
4
Algorithmic approaches
208
We first present a recursive approach for solving the edge ID problem in Section described in Algorithm [ Since the problem itself is NP-hard, Algorithm [ runs in exponental time in the worst case. In Section 4.2 we present heuristic approximations of the edge ID problem which run in cubic time in the worst case. These heuristics can also be used as pre-process reduce the runtime of Alg. by providing an upper bound which can be fed into Alg. to prune the search space. Finally, in Section [4.3] we present reduction of edge ID to yet another NP-hard problem, namely minimum-cost intervention problem (. which allows us to use the algorithms designed for that problem to solve edge ID. Our simulations in Section 5 evallate these approaches against each other.
210
212
213
214
215
216
4.1
Recursive exact algorithm
This approach is described in Algorithm I The inputs to the algorithm are an ADMG G along with edge weights Wg. set of vertices Y corresponding to the causal query Q[Y]. J. an upper bound we on the aggregate weight (cost) of the optimal solution, and threshold th an upper bound on the acceptable cost of a solution. The closer w is to the optimal cost, the quicker Algorithm I will find the solution. If no upper bound known, the algorithm can be initiated with w/b = co. However,
218
219
220
221
222
we shall discuss a few approaches to find a good upper bound wh in the following Section. Note that when th = O, Algorithm 1 will output the optimal solution. Otherwise, as soon as a feasible solution with weight less than w is found, the algorithm terminates (line 12).
223
225
The algorithm begins with calling subroutine MH in line 2, which constructs the maximal hedge for Q,Y], denoted by H. We discuss this subroutine in detail in Appendix B Throughout the rest of the algorithm, we only consider the edges in H. as the other edges do not alter the identifiability. If there
226
227
228
is no hedge formed for Y i.e., H = G there is no need to remove any edges from G and the effect is already identified. Otherwise, we remove the edge with the lowest weight (c) from and recursively call the algorithm to find the solution after removing the edge unless the weight of is
229
230
already higher than the upper bound ah which means no feasible solutions exist for the provided upper bound (line 7). Whenever feasible solution is found, the upper bound w/b is updated to the lowest weight among all the solutions weights discovered so far (line 11). This in turn helps the algorithm prune the exponential search space during the next iterations to reduce the runtime. As soon as a solution with a weight less than the acceptable threshold, i.c., th, is found, the algorithm returns the solution. Otherwise, we is updated to infinity that it never gets removed (line 13). This is due to the fact that we have already explored all the solutions involving e.
231
233
235
237
238
4.2
Heuristic algorithms
239
In this Section, we present two heuristic algorithms for approximating the solution to the edge ID problem. These algorithms can also be used to find the upper bound uh efficiently, which could be fed as an input to Algorithm []
240
241
242 Let 7 (= E F9 E Y {2,y) E F \ Y denote the set of vertices that have least one common bidirected edge with vertex in Y. Any hedge formed for Q contains at least one vertex

---

Algorithm 2 Heuristic algorithm for Edge ID.
1: function HEIDIG, Y, Wg)
2:
g' < MH( Z < {z E 1 EY: (2,1) E Egg \
3: H - The induced subgraph G' on its directed edges.
4:
WH {w, Wgle HJ. VR + VR Ut ,²,
5:
for E do E t (2*, Wn t WH (w(cr Eg (12.01
6:
for E Y do E* t FE* Wx < WH U (W(()))) = 20)
7: E E MinCut(H, 2n,²",0")
8:
return (E, Eeegwa,
M1
12
00
12
(a) ADMG G. Y = {y1. y2).
(b) ADMG H. Y meip
(11, .22 3)
Figure 3: Reduction from edge ID to MCIP.
of Z. As result, in order to eliminate all the hedges formed for Q[Y), it suffices to make sure that none of the vertices in Z appear in such a hedge. To this end, for any E Z, it suffices to either remove all the bidirected edges between and Y, eliminate all the directed paths from Y. The problem of eliminating all directed paths from Z to Y can be cast as minimum cut problem between Z and Y in the edge-induced subgraph of G over its directed edges. To add the possibility of removing the bidirected edges between Z and Y, we add an auxiliary vertex =" to the graph, and draw directed edge from 2 every Z with weight = Eyer W(s,y}- i.e., the sum of the have bidirected edges multiple vertices in Y. We then solve the minimum cut problem for =" and Y. If an edge between 2" and 7 is included in the solution this minimum cut problem, it is mapped removing all the bidirected edges between z and Y in the main problem. Note that we can run the algorithm on the maximal hedge formed for Q[Y] in G rather than G itself. This heuristic is presented Algorithm 2
245
247
249
250
weights of all bidirected edges between and Y. Note that
252
254
255
296
An analogous approach which goes through solving an undirected minimum cut on the edge induced subgraph of G over its bidirected edges presented in Algorithm in Appendix [D] As mentioned earlier, these algorithms can be used either as standalone algorithms to approximate the solution to the edge ID problem, as a pre-processing step to find upper bound wh for Algorithm | As shall see our simulations, both algorithms achieve near-optimal results on random graphs.
258
280
261
Alternative approach: reduction to MCIP
262
As an alternative approach to the algorithms discussed so far, we present reduction of the edge ID problem to another Na-hard problem, i.e., the minimum-comt intervention problem (MCIP) introduced
263
in M. This reduction allows us to exploit algorithms designed for MCIP to solve our problems. The formal definition of MCIP is as follows.
265
Definition 7 (MCIP). Suppose G (V$, EE, EEg is ADMG, C: V R220 is cost cost function mapping each vertex of to non-negative cost, and Y C VV. The objective of the minimum-cost intervention problem for identifying the causal effect Q is to find the subset S V9 with the minimum aggregate cost such that Q is identifiable after intervening on the set A.
288
270
The reduction from edge ID to MCIP based on a transformation from ADMG G to another ADMG H. where each edge in G is represented by vertex in H. This transformation is based on the causal
7

---

query Q[Y), and it maps the identifiability of Q[Y] in G to identifiability of Q[Y in H. where ymap is set of vertices in H. This transformation satisfies the following property; removing a set of edges F" in 9 makes Q[Y] identifiable if and only if intervening on the corresponding vertices of E" in H makes Q[Ymccip) identifiable. More precisely, after this transformation, solving the edge ID problem for Q[Y) in G is equivalent to solving MCIP for Q[Ymeip] in H. The complete details
272
273
274
275
276
277
of this transformation can be found in Appendix A.2, An example of this reduction is shown in Figure 3 where Q y23] in & (Figure Bap is mapped to QKyi. 12, v12 }] in H. (Figure 3b), where {y y2, V22) is a district, and the set of all vertices of H forms a hedge for it. The vertices of H corresponding to each edge in G are indicated with the same color and have the same weight (cost). To avoid intervening on the remaining vertices in H. we assign infinity cost to them. It is straightforward
279
281
202
to see that the solution to the edge ID problem in G with the query Q {y1. 3/2 H would be to remove the edge with the lowest weight. This is because after removing any edge in g, no hedge
283
remains for Q. Similarly, in H. the solution to MCIP with the query Q(ymcii = {y1: 12, v is
284
to intervene on the vertex with the lowest cost among Z = {x1 121 -42 2/22 z This is because after intervening on any vertex in Z, no hedge remains for Q|Ymep). The following result formally
286
287
establishes the link between the edge ID problem in & and MCIP in H.
288
Proposition 2. There exists a polynomial reduction from edge ID to MCIP and vice versa.
Experiments
289
280
We evaluate the proposed heuristic algorithms 2 (HEID-1) and 4 (HEID-2), as well as the exact algorithm| [ (EDGEID), where the upper-bound w for EDGEID is set to be the minimum cost found by HEID-T or -2. Furthermore, given the reduction of the edge ID problem
281
282
the MCIP problem described in Section 4.3 we also evaluate the two approximation and one exact algorithms from I (MCIP-HI, MCIP-H2, and MCIP-exact, respectively). Experimental results are provided for Problem
293
294
295
I and analogous results for Problem 2 are provided in Appendix E.3 All experiments were carried
298
out on an Intel i9-9900K CPU running at 3.6GHz.
297
The algorithms are evaluated for graphs with between 5 and 250 vertices. For a given number of vertices, uniformly sample 50 ADMG structures from library of graphs which are non-isomorphic to each other. Edges for each of these 100 graphs are sampled with probability of (n)(n)//z /n. where n is the number of (observable) vertices, to impose sparsity (thus pragmatically reducing the search space). For each graph we sample directed and bidirected edge probabilities pa uniformly between 0.51 and 1.0F] The problem is then converted into edge II) according to Lemma
Simulations
298
299
300
301
302
303
The vertices in the graphs are topologically sorted and the outcome Y is selected to be the last vertex in the topological ordering. We then check whether a solution exists in principle by removing all finite cost edges and checking for identifiability. If not, a new graph is sampled to avoid evaluating the algorithms on graphs with no solution. For each of these 50 probabilistic ADMGs, we run the algorithms and record the resulting runtime and the associated cost of the solution. If the runtime exceeds 3 minutes, we abort and log that the algorithm has failed to find a solution.
304
305
306
307
308
309
Results are presented in Figure 4 Runtimes and costs are shown for the subset of graphs for which all algorithms found solution (to facilitate comparison). Runtimes for each algorithm are shown in Fig. 4a where it can be seen that our proposed HEID-1 and HEID-2 heuristic algorithms have negligible runtime, followed by the MCIP variants. Interestingly, the exact algorithm EDGEID outperformed the MCIP algorithms on larger graphs, for which the transformation time from the edge ID problem the MCIP increases with the size of the graph. In contrast, EDGEID had large runtime variance which depended heavily on the specifics of the graph under evaluation, particularly for graphs with fewer vertices. The costs for each graph are shown in Fig. 4b] and here we see, as expected, the lowest cost is achieved by the two exact algorithms, EDGEID and MCIP-exact, the fraction of evaluations for which the runtime exceeded 3 minutes (applicable to the exact algorithms). In general, and owing to the sparsity penalty in our graph generation mechanism, the cost of identified solutions falls with the number of vertices. However, among the exact algorithms, EDGEID, exceeds the 3 minute runtime more often than the AICI--Exac regardless of the number of vertices and despite the fact that EDGEID is quicker at finding solution when it does so. Overall, HEID-1 was both the most consistent in terms of finding a solution, having a short runtime, and achieving a close to optimal cost.
310
311
312
313
314
315
316
317
318
followed closely by the heuristic algorithms. (4gure/4c|shour
320
322
324
NNot that we do not consider edge probabilities less than 0.5 as from Lemma such edges would be mapped edges with 0 weight in the equivalent edge ID problem, which can always be removed at the beginning.
8

---

HED MORUI
MCCHHD
EDCEDD
the of Viatpe
(a) Runtimes.
(b) Solution costs.
(c) Fraction runtime exceeded 3 min.
Figure 4: Experimental results for runtime, solution costs, fraction of graphs for which solution was found, and fraction of graphs for which runtime limit of 3 minutes was exceeded. Error bars for runtime and cost graphs indicate 5th and 95th percentiles. Best viewed in color.
325
Real- World Graphs: We also apply the algorithms to four real-world datasets. The first 'Psych' (22 nodes & 70 directed edges) concerns the putative structure from causal discovery algorithm Structural Agnostic Model [10] using data collected as part of the Health and Relationships Project
327
The other three 'aalle' (48 nodes & 84 directed edges), 'Water' (32 nodes & 66 directed edges), and 'Alarm' (37 nodes & 46 directed edges) come from the bnlearn python package [17]. For
20
329
all four graphs, and as with the simulations described above, we introduce bidirected edges with sparsity constraint of log(n)) /nn and simulate expert domain knowledge by random assigning directed and bidirected edge probabilities between 0.51 and 1. The outcome Y is selected to be the last vertex in the topological ordering. For these results, we provide the runtime (limited to 500 seconds) and cost, well as the ratio of graph plausibility before and after selecting subgraph in which the effect identifiable P(ğ*)/((S) P(G)) This ratio is 1.0 if the effect is identifiable in the original graph, and decreases according to the plausibility of an identified subgraph.
331
333
335
336
Results shown in Table [ In cases where MCIP-exact and/or EDGEID did not exceed the runtime limit, can seen that HEID-2 and MCIP-H2 achieved equivalent to optimal cost and ratio. Runtimes for MCIP variants exceeded the HEID variants owing to the required transformation. EDGEID timed out on all but the Alarm structure, whereas MCIP-exact only timed out on the Psych structure, indicating that the MCIP-exact is more consistent (this also corroborates Figure 4c).
338
340
Table I: Time (seconds), cost, and ratio P(C))/P()) for seven algorithms over four real-world datasets. dash indicates maximum runtime (500 seconds) exceeded.
Psych Cost
Barley Cost
Alarm Cost
Water Cost
Algorithm
Time
Ratio
Time
Ratio
Time
Ratio
Time
Ratio
HEID-1
0.0019
2.648
0.07
0.0026
0.081
0.92
0.0004
0.0
1.0
0.0019
1.02
0.36
HRID-2
0.0019
1.806
0.16
0.0026
0.081
0.92
0.0003
0.0
1.0
0.0017
0.42
0.66
MCIP-HI
0.0136
2.648
0.07
0.0140
0.081
0.92
0.0027
0.0
1.0
0.0124
1.02
0.36
MCIP-H2
0.0133
1.806
0.16
0.0131
0.081
0,92
0.0029
0.0
1.0
0.0113
0.42
0.66
MCIP-exact
0.0099
0.081
0.92
0.0028
0.0
1.0
0.0221
0.42
0.66
EDGEID
0.0005
0.0
1.0
6 Conclusion
343
Researchers in causal inference are often faced with graphs for which the effect of interest is not identifiable. It is common to identify target effect by assuming ignorability. A less drastic and more reasonable approach would be to relax this assumption by identifying the most plausible subgraph, given uncertainty about the structure as we suggested in this work. We presented number of algorithms for finding the most probable/plausible probabilistic ADMG in which the target causal effect identifiable. We provided an analysis of the complexity of the problem, and experimental comparison of runtimes, solution costs, and failure rates. We noted that our heuristic algorithms,
345
346
347
348
350
Alg. 2 and Alg. perfformed remarkably well across all metrics. In terms of limitations, we made the assumption that the edges in G are mutually independent (A (Assumption T). Future work should explore case where this assumption does not hold. Finally, it worth noting that the external validity of the derived subgraph (i.e., whether or not the subgraph is correctly specified with respect to the corresponding real-world process) is not guaranteed. As such, practitioners that use such approaches encouraged to do with caution, in particular for research involving human participants.
351
352
354

---

References
356
357
[1] S. Akbari. J. Etesami, and N. Kiyavash. Minimum cost intervention design for causal effect identification. arXiv preprint, arXiv:2205.0223 2022.
358
359
[2] E. Bareinboim, J.D. Correa, D. Ibeling, and T. Icard. On Pearl's hierarchy and the foundations of causal inference. ACM Special Reports, 2020.
381
[3] A. Deaton and N. Cartwright, Understanding and misundertstanding randomized controlled trials. Social Science and Medicine, 210:2-21, 2018. doi: 10. 10016f..ocxcimmd2201..2222
363
[4] Robin Evans and Thomas S Richardson. Markovian acyclic directed mixed graphs for discrete data. The Annals of Statistics, 42(4):1452-1482 2014.
385
[5] C. Glymour, K. Zhang, and P. Spirtes. Review of causal discovery methods based on graphical models. Frontiers Genetics, 10, 2019.
386
367
[6]
Y. Huang and M. Valtorta. Pearl's calculus of intervention is complete. Proceedings of the Twenty-Second Conference on Uncertainty Artificial Intelligence (UAI), 2006. doi: 02555/3020419.3022444
368
389
370
77] G. Imbens and J.D. Angrist. Identification and estimation of local average treatment effects. Econometrica, 62(2):467-4755 1994. doi: 10.2307/2951620
372
[8] G.W. Imbens and D.B. Rubin. Causal inference for statistics, social, and biomedical sciences.
373
An Introduction. Cambridge University Press, New York, 2015.
374
[9] Amin Jaber, Jiji Zhang, and Elias Bareinboim. Causal identification under Markov equivalence: Completeness results. In International Conference on Machine Learning, pages 2981-2989. PMLR, 2019.
375
376
377
[10] D. Kalainathan, O. Goudet, I. Guyon, D. Lopez-Paz, and M. Sebag. Structural agnostic modeling: Adversarial learning of causal graphs. arXiv: 0499333449933... 2020.
378
379
Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Springer, Sprinee,, 1972.
381
[12] J. Pearl. Aspects of graphical models connceted with causality. Proceedings of the 49th Session of the International Statistical Institute, pages 399-401, 1993.
383
[13] J. Pearl. Causality. Cambridge University Press, Cambridge, 2009.
384
[14] D. B. Rubin. Causal inference using potential outcomes: Design, modeling, decisions. Journal of the American Statistical Association, 100(469):322-331, 2005. doi: 10.1198/ 0162145040000018880
385
386
387
[15] R. D. Shah and J. Peters. The hardness of conditional independence testing and the generalised covariance measure. The Annals of Statistics, 48(3), 2020.
308
[16] llya Shpitser and Judea Pearl. Identification of joint interventional distributions in recursive semi- Markovian causal models. In Proceedings of the National Conference on Artificial Intelligence, volume 21, page 1219. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2006.
380
392
[17] E. Taskesen. baleam - Library for Bayesian network learning and inference. Python Library, 2020. jttt:ttss://rdddooo watpaannttgtttub io/bonnaaa
394
385
[18] J. Tian and J. Pearl. A general identification condition for causal effects. AAAI, 2002.
396
[19] Jin Tian and Judea Pearl. On the testable implications of causal models with hidden variables. In Proceedings of the Eighteenth conference on Uncertainty in artificial intelligence, pages 519-527, 2002.
387
398
399
[20] D. Umberson. Health and relationships project. Inter-universityy consortium for political and social research, 2014-2015. doi: 10.3886/ICPSS::7444..22
400
401
[21] M. J. van der Laan and S. Rose. Targeted Learning Causal Inference for Observational and Experimental Data. Springer International, New York, 2011.
10

---

Checklist
403
404
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
406
contributions and scope? [Yes]
407
(b) Did you descrihe the limitations of your work? [Yes]
408
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
410
411
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
413
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
416
417
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]... ...
419
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes]
420
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
422
423
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
425
(b) Did you mention the license of the assets? [Yes]
426
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
427
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
428
429
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
431
5. If you used crowdsourcing or conducted research with human subjects...
432
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
434
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
435
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
437

---

Appendix
438
439
The appendices are organized as follows. Formal proofs of the results stated in the main text are presented in Section A In Section B formed for a certain query (Def. which is used as a subroutine of Algorithm []] A generalization
440
we describe the algorithm to recover the maximal hedge
441
of Assumption [ is discussed in Section C Section D provides further details of the heuristic algorithms discussed in the main text. Further evaluations and experimental conditions for our
443
proposed algorithms are presented in Section E
Table 2: Table of notations
Symbol
Description
VS
Vertices of g
Eg E Ance (X)
The set of bidirected edges of G The set of directed edges of G Ancestors of X in G
M(G)
The set of the all compatible models with g Probability of edge Weight of edge e Causal effect of X on Y
Pe
We Px(
445
A
Formal Proofs
446
We begin with presenting the proofs of Proposition I and Lemma Proposition Pppositioonaappeeee appear at the end of Sections A. and A.2 respectively.
! Proofs of Theorem and
448
Proposition 1. For any causal query Px (Y) and ADMG g. if is a valid identificatinn feentficationnoommlla for
(Y) in G ( then F is valid identification formula for PY in any g' C G.
450 Proof. Let H. C g be an arbitrary edge-induced subgraph of G. Let F be an identification formula for Px (Y) in 9, i.e., for any model M that induces G,
P (Y) =(PMM((M (V9)..
(5)
452 By definition, Px (Y) is identifiable in G. As result, there exists and identification formula such as F that can be derived for Px PY( in 9, using sequence of do calculus rules and basic probability 454 manipulations. Note that this means for any model M that induces G,
( = F'M (()))(
(6)
Note that immediate corollary of Equations] 5 and 6 is that for any model M that induces G,
F(PM (V9) F' FPM (V9)).
456 Now, we first show that this sequence of actions (combination of do calculus rules and probability manipulations) is valid in H. Note that the basic probability manipulations are graph-independent only suffices to show that any applied do calculus rule w.r.t. can also be applied w.r.t. H. The validity conditions of all three do calculus rules are based on certain d-separations. As a result, it suffices to show that a d-separation relation is valid in G, it also valid in H. To do so, it suffices
458
459
460
to show that if all paths between Z, and Ze are blocked in G given W, they are blocked in H too, for arbitrary disjoint sets of vertices Z1, Zz, W C V Take an arbitrary path, p, between Z, and Zg in H. Since H C G. this path exists in G. Since Z1 and Zz are d-separated given W in G, the path p is blocked by W. As a result, any path between Zı and Z₂ in H is blocked by W. Therefore, any do- do-callulus rule applied in G, can also be applied in H. Hence, J is valid identification formula for (Y). That is, for any model M that induces H.
462
464
486
(8) Now note that any model M that induces H. i.c., is compatible with H. is also compatible with G. 468 Also, V = HH. As a result, from Equations 7 and & we know that for any model M that induces H.
PM (Y)== (V))()
(V*)). By definition, FF is a valid identification formula for Px (Y) in H.
12

---

471
Lemma 1. Under Assumption 7 Problem 7 is equivalent to the edge ID problem with the edge
472
weights chosen be the log propensity ratios, i.e., w, max(0, log( "p) Ve G. Moreover, lo
473
Problem 2 is equivalent to the edge ID problem with the choice of weights we = - logg(1 - pe). 474 Ve E G. That is, an instance Problems [nnd can be reduced to an instance of the edge ID
475
problem in polynomial time, and vice versa.
Proof. Problem 1. First consider arbitrary graph 91 (ateey) such that 91 has edge with Pe < 1/2.. Let G2 denote the graph G1 after removing e. Proposition I implies that G2 E [() According to Equation we have P(22) 1- P(G)) > P(G)) (since Pe < 1//2). As a result,
478
P.
479 the solution G to Problem (Eq. 2
has no edges with probability less than 1/2. We can therefore
rewrite Problem as:
1
G arg max C.CG. 9. (.
P(G.)=
arg max G.CG. G. E
P(G.) s.t. Ve G. Pe 2
481 Or equivalently, we can always assume that we start with graph & that has no edges with probability remove all of those edges and the problem does not change. This 483 indeed is equivalent to choosing weight (cost) 0 for those edges in the equivalent edge ID problem. Now assuming that the edges have probability at least 1/2.
less than 1/2, as otherwise
arg max P(G.) G,Co, 9. I
arg max log(P(G.)) 9.C9. (.E(
log( II Pe II (1-Pe)) rEG.
mrg 9,C9. C
max
egg.
arg max G,Co, G.E(o))
log(pe)
+ Σ
log(1 Pe))
eEG
egf,
argmax G,Co. G.E(D))atoiT)
Σ log(p=)+ +
Σ
log(1 Pe)) E log(1 pp))
Σ
log(1 - Pe))
eES
egg.
cEG.
eEG.
485 Since Eegg, log(1 - +e)) log(1 Pe)) is constant value that does not depend on Ge. it 486 can be ignored the maximization and we have:
g
arg max CG. e (
Σ eEG.
log(pe) Σ
log(1 (1g pe))
cEG.
Σ log( - Pe)
Pe
arg max G.CO. 9. 9laann
eEg.
Σ log(
Pe
arg min mig S.C9. G.E(M)
1 --pe)"
egS.
From the formulation above, it is clear that if we assign the weight w. log( 1 ) to each edge 488 e E EG we will have an instance of the edge ID) problem. Note that for edges with probability higher than 1/2, log( Pe_) 2 O, and this assignment of edge weights satisfies the positivity requirement.
489
480
For the opposite direction, note that the procedure explained above is reversible by the choice of exp (w.).. probabilities Pa- T+exp (w.. which a value between 1/2 and 1.
491
432
Problem 2. First note that under Assumption T
for any graph G..
Σ P()) = II (1
p.)
Σ
Pe II (1 - [1)p II (1 (1-Pe). egG,
OCG.
egc.
EC e
é
13

---

493 This is because the inner summation goes over all the possible subsets of E and the summation 494 adds up Therefore, we can rewrite Problem (Eq.
3as
: arg max C.Co, 9, (
P(()
OCS.
II (1 10-PP Pa)
arg max G.CG, 9, ( ogG.
log( II (1 Pe))
arg max 9,C9, 9
egG.
arg max C.CG, 9, (.
log(1 po)
ogG.
arg min 9.Co, 9. 0.
-loog(1
log(1 - -Pe).
egc.
495
With the same reasoning as before, assigning the weights w. = - log(1 pe) each edge e E we end up with an instance of the edge ID problem. Note that again 0 s - log((1 p.) S cc.
496
437
noteworthy that this procedure also reversible with the choice of edge probabilities Pe
1
exp W,), which reduces the edge ID problem to an instance of Problem 2 Again note that exp we) S 1 for any non-negative W..
499
S
500
A.1
Reduction from MCIP to edge ID
501
Theorem 1. The edge ID problem is NP-hard.
To prove Theorem 1 first present a polynomial-time reduction from MCIP the edge ID problem. It has been shown that the minimum vertex cover problem can be reduced to MCIP in polynomial time M. Combining the two reductions,
503
504
show that there exists a polynomial-tin -imoomial-tmme redcution from the minimum vertex cover problem to the edge ID problem. Since the minimum vertex cover problem known to be NP-hard [1], follows that the edge ID problem is also NP-hard.
505
506
507
We propose the following reduction from MCIP to the edge ID problem. Assume we want to solve MCIP given ADMG g = (V9, Eg Eg), ), query Q.Y., and the intervention costs C(v) for e e V We construct graph, denoted by 7 Ti (G, Y), through the following steps.
508
a. For every vertex æ E VG \ Y. add two vertices x², xx= to VH.
510
For any bidirected edge {æ, Eg where x V \ Y and z E V9, add the bidirected edge =² to E.K.
511
512
For any directed edge 2x, Eg where E V \ and E vs, add the directed edge (x 2² E.
513
514
d. For any bidirected edge (v1, E Eg where vı, U2 E Y. add the bidirected edge {vi, y2 to EN
e. For every _t, x E / y, draw the two edges (xt,a² E E. and (2²,x*) E E. Furthermore, the weight of (x+, ] is C(x).
517
518
519 f. The costs of the all other edges in H are assigned to be infinite.
With abuse of notation, for any vertex x /s Y., we define = (a², E EN,, where (x x' } the bidirected edge H that corresponds to x in G, and inherits the same weight (cost).
520
521
Example 2. Consider graph G in Figure 5a Vertices x and z are mapped to xt,x², and 21 2² respectively, Both directed and a bidirected edge are drawn between these puirs. The bidirected edge (x² x²2 is assigned the weight C(x) = Ca, and the bidirected edge {2-, 222) is assigned the weight C(z) Cz. Infinite weights are assigned to the rest of the edges in H (Figure 5b).
522
524
14

---

Co
x
Ca
00
y1
y2
1/1
1/2
(a) The model 9 with costs each vertex
(b) The model G with costs on each edge
Figure 5: Reduction of MCIP to edge ID
Proposition 3. Suppose G' is an ADMG, Y C V is set of its vertices such that Y is district in (Y and H1' (g', Y). Consider X C V Y as arbitrary subset of vertices of G', and 528 define G = G'IV9' XX) Let E - Ee E, Bu E X, (T(()) and define E =E \ E", Let
529 H. be the edge- edge-induced subgraph of defined as H. = (V EE. E. Q[Y) is identifiable in G if
and only if Q[{] is identifiable in H.
531 Proof. We prove the contrapositive, i.c. Q[Y] is not identifiable in & iff Q[Y] is not identifiable in
532 H. Note that by construction, Y is district in both G and H[Y). That is, suffices to show that there exists hedge formed for Q[Y] in G iff there exists a hedge formed for Q[Y] in H.
533
To this end, we first prove the following claim. Let W V form hedge for Q|Y. If W for some x E V0" then x² E W and vice versa. That is, the two vertices x' and x² corresponding the same vertex x: in 50 appear only simultaneously in any hedge. To see this, note that by construction, x² is the only child of 2²2 By definition of hedge, if x E W, then it has directed path to Y within H.W) and this path can only go through x'. For the other direction, note that x has only one bidirected edge, which is with z². Again, by definition of hedge, if x E W, then it has a bidirected path to within H HW), and this path can only go through x². Hence, in the sequel, when there is a hedge W formed for Q in H. we will without loss of generality assume that there exists a set of variables Z C VG' such that W = Z U 7 UY, where Z (= E Z) and 2 {2212 Z).
535
536
537
538
540
543
If part. Let W = Z Z Y form a hedge for Q|Y] in H. First note that since none of the bidirected edges between Zt and Z are removed in H. by construction, all vertices Z are present in 9. i.e. C V9, Now we show that Z ZUY forms a hedge for Q[Y] in G. To this end, we prove C] is district and Z YUY Y Ancgrzury( (Y). First note that any vertex in Z' has only one bidirected edge vertex in Z That is, if we consider the edge-induced subgraph of H[J over its bidirected edges, vertices of Z are leaf nodes. As a result, Z U Y must be connected in this graph. That is, Z² UY is district in H[Z2 Y.. This implies by construction of H that g Z U Y] is single district. With a similar reasoning, note that vertices in Z² have no parents. As result, z U Y Anch(z-ur (Y) (since the directed paths cannot go through Z²). Again, by construction, the edge-induced subgraph of GIZ UY] over its directed edges is a copy of HIZ UY). As result, Z JUY Y = (Y))
545
548
550
551
552
553
Only if part. Let Z Y form a hedge for Q in G. where Z C V \ Y. Define z²= (= 2} and 2 [22|2 22 E Z}. We show that Z U ZU forms hedge for Q[Y H. First, by definition of hedge, Ancgizur (Y) = Z U.Y. Since the edge-induced subgraph of H(Z UY] is a copy of Z YY by construction, we know (n) = Z UY. Further, each vertex 2² E 2 is 2t u ZY. Now it suffices to show that z U UY is district in H[Z- U 2 UY]. By definition of hedge. Z Y is district in GIZ UY]. By construction of H. exactly the same bidirected edges (and therefore bidirected paths) exist in 2 U.J. Therefore, 2 Y is district in 2 U Y]. Now note that by construction of H', each vertex z' E Z has a bidirected edge to 2² E Z And by definition of G and H. since the vertices Z exist in G, none of these edges removed in H. As result, Zt U Z U Y is district in
554
555
556
557
parent of 21 zt. As result, Ancgiz (uu
560
562
563
H(21 U 2² U UY, which completes the proof.
564
15

---

586
Proof of Theorem 7 A polynomial-tin -ittee reduction from MCIP to the edge ID problem follows
567
immediately from Proposition 3
MCIP is shown be NP-hard [ As a result, the edge ID problem
568
is Np-hard.
589
A.2
Reduction from edge ID to MCIP
570
Proposition 2. There exists a polynomial reduction from edge ID MCIP and vice versa.
To prove Proposition 2 we begin with presenting a transforrattin T2(9, Y) which is in the core of reduction from edge ID to MCIP.
571
572
Suppose we want to solve the edge ID) problem given ADMG G = (V9, F.g P.g. query Q[Y,, and edge weights W = {wele E G}. Let X = V Y denote the set of vertices of g excluding Y. We define the transformation (H, mmiip) = (g Y) where H = (VH, E2 E is an ADMG and ymrip C VH as follows. Note that V will consist of two disjoint set of vertices, namely V and VH. i.., V = Vihp U Vior-
574
575
578
577
bot
Begin with V Vi = 0, Y = 0. For any vertex v E V add vertex v to top with If U E Y, add ymesp.
578
579
cost C(v)
For any directed edge (vi, U2) E Eg with weight ugJ in 9, add a new vertex og to V with cost C(vlt) w where
5e0
581
if uz, Uj E X, if E Y or vy E Y, both us 0j E
Draw directed edges (vs, vgt) and (v)) Further, draw bidirected edge between ey and oiy For any bidirected edge 25} } E Eg with weight w/e, add a new vertex, ziy to Vid, with cost O(al)) = w/z- Add two bidirected edges {a,, aby and {zy, xly). }. Further, draw two directed edges (z/g. 2.) and (z))..;) in H.
582
583
584
585
d. For any bidirected edge {ara, y5} with weight w.j. add vertex =iJ to Vop with cost C(=l)) 586
587 w Draw bidirected edges (z/z, xi and { 3. Then draw a directed edge from z/y to Z,,
For any bidirected edge between Vj} E Fig with weight w in G, add new vertex, vij to Vip with cost C( = wfz. Draw bidirected edges (vig, 31 and (ulj- yz}. Further, for any E X, draw directed edge from v to a.
588
589
590
f. Let y1 < ... Yv denote a topological ordering among vertices of Y. For every pair (Vi, ys} of vertices Y, where < j. add vertices y²¹ w.. to VH. Add uy to ymesp, Draw the directed edges (yk, v for every i < k S j. Draw the directed edges (vl v. ) for every i < < j. and the directed edge (u u,"",)"). Draw a bidirected edge between y, and v/" Further, for any bidirected edge {yk; yt) E F.g. where i S k, s j. add new vertex Vkr to Voat draw two bidirected edges {uM vie } and (ull vi J. and a directed edge (yl vty). The costs the all of the vertices in bot are infinite.
582
594
i5
596
587
With abuse of notation, for any bidirected edge ety (U; Uj} E Eg and any directed edge et (1, vy) Eg. we define Te(y of and Tz (e(),) = u.y. respectively, where u uff E VH are the vertices representing their corresponding edges.
598
599
600
We will utilize the following results to prove Proposition 2 More precisely, Lemmas 2 through 9 are used to prove Proposition 4 which in turn is used to prove Proposition
602
Lemma 2. Suppose G is an ADMG, Y is a set of its vertices, and (H, ymmci)) = T(G,Y), Each
603
604
vertex y E ymms is a district in H.
Proof. It suffices to show that for every pair of w1, 02 E ymcip there is no bidirected edge between them in H. Suppose first that U1, U2 E Y. Any bidirected edge between i1 and U2 in G (if it exists)
605
16

---

607 is removed in step (e) of the transformation. and none of the steps (a) through (f) add a bidirected
608 edge between them. Otherwise, least one of UI U2, w.l.o.g. U1, in Ymeip Y. Suppose w.l.o.g. that 01 = y From step (f) of the transformation T, we know that t1 has bidirected edges only to 609
vertices Viy where none of them member of ymeip.
610
Lemma 3. Suppose G is an ADMG, Y is a set of its vertices, and (H, Ymcip) = (g, Y). Suppose there is a hedge formed for Qlyl in H. where y Y. Let H denote the set of vertices of this hedge. H does not include any of the vertices added in the step (f) of the transformation. That is, H n Voot = D.
611
612
613
Proof. Define V1 = [yll E Voot Vi, k, I]. and V22 = Voot \ V1. By construction of H. the vertices of 1/2 have directed edges only to vertices in V2- Therefore. for each vertex v E V22 we have v & A (v). As a result, 1/2 1 H = 0, since by definition of hedge, any vertex of H is an ancestor of y in H[H.] Now, consider an arbitrary vertex v E V/. By construction of H. if there exists bidirected edge e') E Eg we must have that v' E V2. Therefore, if v E H, there must be at least one vertex v/ E 1/2 n H. Since we proved 1/2 n = 0. v cannot be H. Consequently,
614
616
617
V1 n H = 0. 619
621
Lemma 4, Suppose G is an ADMG, Y is a set of its vertices, and Ymcip)= TG. Y). Suppose there is hedge formed for Q(u]] in H. where ys. Vj E Y and vj² is the vertex corresponding to the puir (yi, Uy) added in step (f) of the transform T. Let H denote the set of vertices of this hedge. If
622
623
624
E H n V.HL then v has the superscript ij, that is, v is either one of the vertices ui or one of the
625
826
vertices yug. where i S k, S. In the latter case, yhu E H.
Proof. Define 1/2 = (ukt E V.H. Vm, n, k. (). and V22 = Vot Vi, Suppose V/² = (uul E 'bot bot: yk. l) and V = {uk E Vit Vk). Also define Vi' = Vi \ Vr. V = V/2 \ Vg. For the first part of the claim, suffices to show that V/ n H = 0, V2 n H = 0. By construction of H. the vertices of V/2 do not have any child out of 22 Therefore, Vi2 (nc = 0. This implies that
627
628
629
630
1/2 H 0. Now let of be an arbitrary vertex in V/ By construction of H. o has bidirected 631
edges only to vertices of Vyz This implies that if u1 E H, there must be at least one vertex of Vi
632
in H which is in contradiction with Vi n = 0. Therefore, of & H. Since of is an arbitrary vertex in Vi, we conclude V1 n 0.
633
634
Now, we prove that if v E H is one of the vertices Vig we have v H. Since v E H, there exists a directed path from 3t to y in H(H). Since s is the only child of v the aforementioned path passes through v Therefore, slaa E H.
635
636
637
638
, Ey EY"FE is an ADMG, Y S V is a set of its vertices, and (H', Y ymrip) T(g', Y). Let E" C Ey and En C Eg be arbitrary edges of G, and define Eg = Ey Ey E = Eg" Ey. Define 9= --VV, -VS,EL Eg) and H. = H'(H' \, V",, where V vo and V" = (u E V E Eg U F TT(e)- Suppose there is hedge formed for Quyi1 in H for some i, Let H denote the set of vertices of this hedge in H. The set of vertices Y (unlv E H} is district in GYY, Moreover, Heop = Anex(H where
Lemma 5. Suppose G' = (VS',
639
640
641
642
643
644
Hoo H n NH
645
646 Proof. First we prove that Y is a district in G[Y]. Consider an arbitrary vertex y in H. By definition
647 of hedge, there exists a bidirected path, P1, between it and y 30 in H[H].. Let Y denotes the set of vertices in H such that their superscript is ij. Lemma 4 implies that H S Vtop U y Furthermore, 649 by construction of H. there is only one bidirected edge between y and H \. Y which is {uy, v. Therefore, all of the vertices the path p1 are in YJ, Now, we define Y {yx w E P1) and
17

---

Y - Eoleluad E pı), i.e., the Vip counterparts of the vertices in P1. Since the vertices on Pr are in H. Yf Y.. From Lemma we know that if yil E H. then, u E H. It implies that Y2 S H. As a result, Y and Y/ are both vertices of H. Now if we replace all the vertices in p1 with their corresponding counterpart in Yf UYY we arrive at a bidirected path p2 between ys and yj in
651
652
653
654
H|Y? U Y2] (as by construction the same edges exist in ViN top).. By definition of g and H. if a vertex 2 exists in H. the corresponding edge {yk ) exists in G. As a result, a bidirected path between yk and yu exists in G G[Y?] Noting that ye is an arbitrary vertex in Y and Y S Y", this implies that all of the vertices of Y are in the same district as yj in G[Y"),, which completes the proof.
655
856
658
659
Next, we prove that Hoop = Ano)( (Y (Y*). To this end, it suffices to show that there is directed path form an arbitrary vertex v E top to Y in Hop Since H forms a hedge for Q(v]] in H. there exists directed path from v/² in H(HH]. This path must go through the only parent of vj. which is v.r Then, the last vertex on the path is one of the parents of y If this parent is yt. we are done as we have a directed path from v to yi. where yi E Y and it has no ancestors in H \ Htop- Otherwise, let this parent be & for some i < & < j. Now the last vertex on the path before v must ij
660
682
663
664
be yu. which is the only parent of ye Note that by definition of Y*, yk Y". Therefore, e has directed path to Y in H(Hoopp..
666
1 EGg EE) is an ADMG, Y is a set of its vertices, and (H, Y Ymcip) = Ta(g, Y). Suppose there is hedge formed for Qlyi in H. for some y E Ymcip, Let H denote the set of verlices of this hedge. Then H I & 0, where X = V \Y
Lemma 6. Suppose G = (VV
667
668
Proof. Since H forms hedge for Qly] in H. there exists vertex h E H such that hy E E.g.
670
There are two possibilities for y Ymap::
y = yı E Y. From Lemma 4 we have h & ViH Therefore, by construction of H. h = yir for some j.
672
673
674
リ y= u E bot- By construction of H, h Dky
5 for some k. Vertex h must have directed
path to y in H by definition of hedge, which must go through the only child of h, i.e., vic-
675
676 In both cases, we showed that there exists a vertex v = v// E H for some j. By definition of hedge,
677 there is a bidirected path, p. from v to y in H. because u E Ancx(y). Since all of the children of v are
678 in X, there is at least one vertex in X on path p. Therefore, H includes at least one vertex of X.
679
Lemma 7. [Inverse transform preserves hedges.] Suppose G' = (VS' ".",E"" is an ADMG,
680
Y V is a set of its vertices, and (HL Y ymcii) (g', .Y) Let En S Eq and E S Eg be arbitrary edges of G, and define Eq = Eg" \ Egg Eg Eg" E.g Define g = (V8, Eg. )
681
682
and H =H'VV'' \, (V", where V 6 and V (u E V E
E FN U En, v= Ta(e)). Let W C V.H. be set of vertices of H. Let W. C W n V be subset of W such that W. are vertices of 9 as well. Consider the inverse transform of H(W in the ADMG G, ie., for any v = of E W, delete v and all edges incident to it and draw bidirected edge between oi and uj. and for any
683
684
685
686
687 v oyy delete v and all edges incident to it and draw directed edge from vs to uj. Let the resulting subgraph (which is a subgraph of G) be denoted by G[W-1] with the set of vertices W-1 C CV9, If An (W.) = W. then Ancgw--)(W.) = W-1 Moreover, if W is a district in H(W), then
688
689
W is a district in G]
680
P Proof. First, we show that if (WCz)w1W..) = W. then Ancow I(W,) = W-1, Let be an 692 arbitrary vertex in W-1 Vertex is in W because W-1 _ W. Since W and AncHww (W.).
693 e has a directed path e -x... 0 + og + Uj ... - w. denoted by I, to vertex w W, in H[W].
684 For each vertex of on path 1, we have us by E G[- and since vgl E VVH by definition of g
and H. there exists (e,, v,) E Eÿ s.t. i x j. and consequently, (v,, v3) E B Therefore,
18

---

there exists directed path from to w in G[W []. Noting that v is an arbitrary vertex in W-1, we conclude that Ancgiw-ij (W W-1
696
697
Now, we prove that if W is a district in H[W]. then W-1 is district in g|W- Consider two vertices U1, U2 E W-1, Since U1,02 E W and W is a district, there exists a bidirected path 2 + ...... 22 ++ Di + 2/- ....... + U2, denoted by p. between i1 and 1/2 in H[W Each vertex ofy on path is in H. and Uss eg E G[ By definition of G and H. we have {er, 2/} E Egg Therefore,
698
699
700
701
{u,, J E Li E Then, there is a bidirected path between es and U2 in G[W- Since vs and 02 are two arbitrary vertices in W-1, it implies that W-1 is a district in G.W-
702
703
Lemma 8. [Transform preserves hedges. Suppose g' = =VV9, Eg" ..g' is an ADMG, Y YC CVV is set of its vertices, and (H', Ymcip) = 'T'(9', (T)) Let E C Ey and En C C be arbitarr edges of G, and define F = F E.. F.g = F.g F.g Define 9 = (V9, Eg Fgg) and H = H'(H' VV", T2(e)). Let W C be a set of vertices of 9 such that W \ Y * 0. Let Wa S W be subset of W. Let the transformed graph of 9[W] under To be denoted by H", where H. S H. Define W = VH If (nogw)(W.). = W, then AncH[w-][Wa, = W" Moreover, if is a district in G[W). then W is a district in HWW...
704
705
706
where V9_ = =V9' and V {w E V E UGUEN, v
708
709
top
710
711
First, we prove that if Ancgw) (W₂) = W, then AncH(w-]WW)) = W. Take an arbitrary vertex e E W*. There are two possibilities for w:
Proof.
712
* E W. That is, vertex v is in G[W].
& W. This implies that u represents an edge between two vertices uy and uj in G[W].
714
715
There are three possibilities for e:
- e= vy). By construction of H. v is parent of u, in H[W",, where vy is a vertex of g[W].
716
718
fer, 23} and os X er E X. In this case, e parent of at least one of of and
719
uy in H[W"), *, w.l.o.g. us where vú is a vertex of G[W).
e= fv;, 13} and n4, E Y. By construction of H. v parent of all vertices in V \V. Since W Y * 0, there exists a vertex x in G[W] such that v is a parent of x.
720
721
722
In all three cases above, we proved that there exists a vertex & E W such that is parent of x.
723
Therefore, we showed that any vertex v E W either is itself vertex in W or is parent of a vertex in W. As a result, it suffices to show that every w E W has a directed path to We in H[W*). We know that w has a directed path to W. in G[] such as p. Take arbitrary pair of consecutive vertices on this path, such as 01 and V2. The directed edge (01, 12) exists in G[W]. As a result, the directed path 2 + 212 + U2 exists in H["".. Starting at w and repeating this argument for every pair of consecutive vertices on p. we conclude that there exists a directed path from w to W., which completes the proof.
725
727
728
730
731
Now, we show that if W is a district in G[W], then W' is a district in H(W).. Take an arbitrary vertex & E W* There are two possibilities for e:
732
733
u E W. That is, v is vertex in GW).
& W. In this case, at least one of the vertices represents an edge between two vertices v; and vy in G[W]. By construction of H. v is connected to at least one of is or Uj. w.l.o.g. U; by a bidirected edge, where U; E W.
735
737 We showed that any vertex U E W either is in W, or is connected to a vertex in W through a bidirected edge. Therefore, it suffices to show that for any two vertices W1, w2 E W there exists a bidirected path between W/ and We in H[W"]. Since W1, W2 E W. there is a bidirected path, p.
739
between Wi and we in GWW Take an arbitrary pair of consecutive vertices on this path, such 01 and uo. The bidirected edge {v1, )2) exists in G[W]. As result, the bidirected path 0 ++ efe + 02
19

---

742
exists in ]. Starting at w and repeating this argument for every pair of consecutive vertices on
743
P. we conclude that there exists bidirected path from w to W2, which completes the proof. t
744
Lemma 9. Suppose G is an ADMG, and is a subset of its vertices. Also let Y* be a district in G., If the set of vertices H form a hedge for Q(Y",, then H \ Y # Ø.
745
748
Proof. Assume by contradiction H Y = 0. ie.. H.Y. By definition of hedge, we know HY Y + W. Take an arbitrary vertex v E H Y Furthermore, v E Y Y because H S Y. Since H forms a hedge for ", H is district in G[H]. Therefore, there exists a bidirected path between and a vertex y" Y in Q[Y] which is in contradiction with the assumption that Y* is a district in G[Y].
747
748
749
750
Proposition 4. Suppose g' (V9' EE Eg is an ADMG, Y S VS' is a set of its vertices, and (H', ymcip) = = Y). Let EyJ I F and Fn S F. be arbitrary edges of 9, and define Fd Fg Egg \ Ely. Q identifiable in 9 (V9, Eg Fg) and only if (fQ identifiale in H = H'IV"' \V", where V9 =V and V {o E V 1e Eg U E }e))
751
752
E E
753
754
758
Proof.
We prove the contrapositive, i.e., Q[Y] is not identifiable in G iff Q|Y is not identifiable in H.
757
!f part. Suppose @[ymcip] is not identifiable in H. That is, there exists a hedge formed for @
758
in H. From Lemma 2 this hedge is formed for Q(v') for some y' ymmcip, Denote the set of vertices
759
780
of this hedge by H. We consider two possibilities separately:
y'= where y, Y. From Lemma H C V Taking W H in Lemma 7 W-1 is top set of vertices in G such that Ancg (y) W-1, and W-1 is a district in G. Now take y to be the district of G that includes y/- By definition of hedge, G[W-1 UY! forms a hedge for Q[Y*] in G. Note that from Lemma W-1 Y + 0. As a result, Q[Y] is not identifiable in G.
782
763
764
765
786
y where ye, VJ E Y and y' is one of the vertices added to H in the last step of the transformation T (step (f)) Define the set Y {yx 1y H). From Lemma 5 Y is a district in G. and therefore a district in G[ As a result, it suffices to show that there exists hedge formed for Q( in G. Now define Heop
787
788
789
H n Vog. By definition of hedge, H is a district in H(H). i.e it connected over its bidirected edges. By construction of H. there is only one bidirected edge between the vertices in Heop and H \ Htop, which is set that partitions the
770
771
the bidirected edge between yj and n Therefore, this edge is graph H(H) into two connected components H. H2op) and H. H \ Htop] That is, H(Htop) is connected over its bidirected edges and therefore Htop is district in H topl- Further, from Lemma 5 Hoop AnCH[H[op) (Y*). Noting that Htop C Viop taking W Htop in Lemma
773
7 W is district in and Anceiw 1I(Y)) W-1 Note that from Lemma * Therefore, the set of vertices W-1 form a hedge for Q[Y*) in G. Hence, Q[Y] is not identifiable in G.
778
777 W
779
Only if part. Suppose Q[Y] is not identifiable in G. It implies that there exists a district of G[Y] such as Y such that there is a hedge formed for 2[ in G. Let H denote the set of vertices of this hedge. From Lemma 9 H Y * O. Deñine W* as in Lemma 8 that the transform T(G(H) Y*) without
780
781
step (f) (only on the vertices of V.H.) Note that y W* We consider the following two cases separately:
782
783
784
Y = {u}. that is, Y is single vertex. From Lemma g AncH[w-1(9) = W* By definition of hedge, the vertices W form hedge for Q Qiyl in H.
W is district in H[W*] and
785
Note that y E ymeip, and from Lemma 2 it is a district of H[ymoipp) As result, Q mccip) is not identifiable in H.
786
20

---

788
Y 2 2. Let and yy be the first and the last vertices of Y in the topological order. Define the vertices in V with superscript ij corresponding to the vertices in Y*. Note that v 33 E V since yi, Uj E Y*. Since 1 is district in H[Y it suffices show that there U
y {vk yyk E EY) fuMlua V E Y y
780
v) E Ymmci and from Lemma 2
is hedge formed for v/ in H. We show that the vertices W W U U form a hedge for u in H. From Lemma 8 Ancx(w--(X**) = W", that is, all the vertices W are ancestors of Y in H(W*), and therefore in H[W]. Also, the vertices y in Y have direct edge to their corresponding vertex in W i... vhi and therefore
792
798
794
795
ancestors of Y in H[] as well. Further, each vertex in Y* such as yk is parent of y which is in turn parent of y (or is v itself if i.) Finally, v/² has a directed edge to vf by construction. As a result, all of the vertices W have a direct path to o in H(W). That is, Anczww (u,²) W. now remains show that W district H[W]. From Lemma W is district in H(["). As a result, the vertices W are connected through bidirected edges in H[W]. There is a bidirected edge between y/ and y/ by construction of H. suffices to show that for any Y there exists bidirected path between v and / in H. A vertex vi E y (with double subscript, which are due to the bidirected edges among Y)) has bidirected edges to / and w/², which are both in y by definition. Now take an arbitrary vertex v22 E y (with single subscript, due to vertices in Y*). We know V/ E Y as vi E Y by definition of y Y is a district in G[Y*). That is, there exists a bidirected path from y/k to y; in G[Y*]. From Lemma 8 by taking W = Y*, there is a bidirected path from y% to Y/ in H[Y U {3 M/ E Y }]. By construction of H. if we replace each vertex u on by 1²) we achieve a bidirected path p' with vertices in y from to y which completes the proof.
796
797
798
799
800
801
802
804
805
807
809
810
812
Proof of Proposition The reduction from the edge ID problem to MCIP was shown through the proof of Proposition
The opposite direction is an immediate corollary of Proposition 3
814
Corollary 2. The edge ID problem and MCIP are equivalent.
B
Maximal Hedge
815
Algorithm Maximal Hedge.
1: function MH(G, Y)
2: Initialize M K
3: for Y, districts of G do
4: M M HHull Y))
5: return 9[M]
1:
function HHULL(G, YD
2: Initialize H V9"
3: while True do
4:
C +- connected component (district) of Y, via bidirected edges in ( A 4- ancestors of Y, in G[C]
5:
6:
if # then
7:
H - A
8:
else
9:
break
10:
return H
Herein, we present the algorithm for recovering the maximal hedge formed for Q[Y] in given
816
ADMG G (see Definition Maximal hedge was initially defined in [ under the name hedge hull.
21

---

y
Figure 6: An example where the expert is aware that there no causal path from a to y, e.g., because 1 y with high confidence.
We adopt the same definition, and when G comprises several districts, we define the maximal hedge as the union of the hedge hulls formed for each district of G.Y.. As result, the complete procedure of recovering the maximal hedge for a query Q[Y], summarized in Algorithm finds the maximal hedge formed for each district Y, of GIY] and returns the union of them. This procedure is
818
819
820
822
used as a subroutine MH in Algorithm(]] [ The function HHull is in fact Algorithm borrowed from
I.
This function is proven to recover the union of all hedges formed for Y,, where Y, is one of the
824
districts of G (see Lemma 6 of (.].
C Generalizing Assumption
825
Lemma S the equivalence of Problems I and 2 with the edge ID problem under Assumption [ However, as mentioned in the main text, this equivalence holds in the more general setting where we
827
allow for perfect negative correlations among edges. As an example, consider the graph of Figure
829
6
Suppose that the performed statistical independence tests show that the two variables 2 and y are independent of each other with high confidence. As result, the expert believes that the edges (2, and (ar, y) must not exist simultaneously, as otherwise the causal path from 2 to y would make them dependent. In such cases, the belief of the expert can be modeled as probabilities p and q assigned to the existence of the edges (z, z) and (z, y), respectively, as well as perfect negative correlation
830
831
832
833
834
between them.
835
Note that the aforementioned constraint, i.e., that the edges do not exist simultaneously. can be specified for any number of edges, not limited to two edges only. For instance, the expert might believe at least one of the edges along a causal path of length n must not exist in the true ADMG describing the system. This belief can be modeled as an extra constraint in the optimization of Equations
837
838
2 and 3 We show that with the specification of such negative correlations, Problems | and can still be cast an instance of the edge IID problem. Therefore, the results presented in this work are valid in this setting as well.
839
840
2
841
842
Assumption 2. The edges G are assigned probabilities Pe, Ve E 9, and perfect negative corre- lations are defined among subsets of edges. More precisely, for any subset E S Ey U Egg there is either 1) no constraint (mutually independent), or 2) the constraint that at least one of the edges in E must not exist in the true ADMG (perfect negative correlation).
843
844
845
846
Proposition 5. Under Assumption 2 there exists reduction from Problems 7 and 2 to the edge ID problem and vice versa with the time complexity in the order of O(CC) |V E U Eg l). where C' is the set of perfect correlation constraints.
847
848
849
Proof. First note that we proved the equivalence of Problems J and with the edge ID problem without the perfect correlation constraints Lemma As a result, under assumption i.e., by adding the perfect correlation constraints, Problems| [ and 2 are equivalent to modified edge ID problem with those constraints. But we claim that there exists and instance of the original unconstrained edge ID problem which is equivalent to these problems. To see this, first note that we know from Corollary that the edge ID problem equivalent to MCIP Therefore, suffices to show that there exists an instance of MCIP which is equivalent to the constrained edge ID mentioned above. To this end, consider the transform (G, Y) introduced in Section A.2 This transformation maps an instance of the edge ID problem to an instance of MCIP. Applying this transformation to the constrained edge ID problem, we can map the constrained edge ID to an instance of MCIP with extra constraints, with transforming the constraints
850
851
852
854
856
858
well. That is, if for instance, there is a perfect negative correlation among the edges e1, 62 in G. this constraint is mapped to a negative perfect correlation on the corresponding vertices in H. namely Te(e1). Tz(ez). In words, this constraint would be that least one of (eee) and Ta (e2) must be intervened upon. We show that such constraints can be integrated into the original definition of MCIP
860
862
863
Suppose we have an MCIP problem in ADMG g with query Q with the extra constraint that at least one of the vertices X S 6 must be intervened upon. Consider the example of X
864
22

---

21
2/2
2/3
21
222
3/3
9
Figure 7: Integrating the perfect negative correlation constraint into MCIP
886
We build a new ADMG g' by adding vertices {z'|zz la E X) i.c., a new vertex corresponding to each vertex in X, along with an auxiliary vertex ÿ to G. We fix random ordering over the vertices of X, and denote the set of vertices of X as 2 Im. We add the directed edges (o,, 2 to G', as well as the bidirected edges a Further, we draw directed edges (a',, x/41) for m. Finally,
{21, I2, T3} y in Figure 7
867
888
869
870
draw the directed edge (5rm v) and the bidirected edge ( ū). Refer to the graph in Figure 7 for an example with X = (21, 22, 233)- )- Note that the set XUX U (ύ} forms hedge for Q[ū), where X' {a/ [a: E X) Now it suffices to set the cost of intervention on vertices of X' to infinity, and consider MCIP for the query Q!Y U H in G'. It is straightforward to see that the objective of this problem would be find the minimum cost intervention for identification of
every 1 S
871
872
873
874
875
QLY], with the constraint that at least one of the vertices in X must be intervened on. Note that as soon as one vertex in X gets intervened upon, there is no hedge left for Qī0.. Also it is noteworthy that adding this structure does not add any new hedges formed for Q[Y], since the structure only includes new descendants for X which have no directed paths to Y. Also note that the vertices X" and ğ are specific to the very constraint corresponding to the set of vertices X. For any constraint, we add such structure to G. The number of vertices (and therefore the time complexity) is at most in the order O([C). IV9)), where C' is the set of constraints.
876
877
878
879
880
882
883
C.1
Further applications
884
The relaxation provided in this Appendix allows the approaches proposed in this work to be applicable to more general set of problems. Herein, we discuss one such application.
885
886 Let us assume we run our algorithm which returns the subgraph with the highest probability, G1- However, the probability that G1 is the true causal structure describing the system might be too low. In such a case, the researcher might be interested in having a ranking of most probable graphs (for instance, the 10 most probable graphs), rather than only one most probable graph. This could be helpful for instance, when a unique identification formula is valid in a few of these graphs, or the researcher is interested in identifying more than one causal query. The methods discussed in this work along with the relaxation proposed in this appendix provide the tools to recover such a ranking (of the most probable graphs in which query is identifiable). To see this, note that based what
888
880
882
883
we proposed in this Appendix, perfect negative correlation constraints can be added to the edge
894
895
ID problem without additional computational cost. So we begin by solving the original problem, which yields a graph G1 We then solve it for a second time (i.e., re-run the algorithm), with the only difference that we add the perfect negative correlation constraint over the set of all edges of G1 (i.e..
896
897
898
we force the algorithm to exclude at least one of the edges of G1.) The solution to this problem (let us call G2) the highest probability graph among all subgraphs except G1. i.e., is the second highest probability graph in which the query is identifiable. Continuing in this manner, running the algorithm n times would give us ranking of the n highest probability graphs.
899
901
D Heuristic Algorithms
902
Algorithm 2 was devised considering the fact that every hedge formed for Q[Y] must include vertex that has a bidirected edge to Y. As mentioned in Section 4.2, an analogous approach, summarized in Algorithm uses the fact that any hedge formed for Q[Y] must include parent of Y.
904
23

---

Let Y S V be set of vertices of G such that G[Y] comprises of only one district. Let Z := {a e By E Y (2, v) E F Y denote the set of vertices that have at least one directed edge to vertex Y. i.e., the parents of Y excluding Y. Any hedge formed for Q contains least one vertex of Z. As a result, in order to eliminate all the hedges formed for Q[Y], it suffices to ensure that none of the vertices in Z appear the final hedge. To this end, for any 2 E Z, it suffices to either remove all the directed edges between and Y, or eliminate all the bidirected paths from to Y. Y can be cast as a minimum cut problem between Z and Y in the edge-induced subgraph of g over its bidirected edges. To add the possibility of removing the directed edges between Z and Y. we add an auxiliary vertex 2" to the graph and draw bidirected edge between 2" and every Z with weight
908
908
909
910
912
The problem of eliminating all bidirected paths from
914
Eyey W(z,y) ie., the sum of the weights of all directed edges between and Y. Note that can have directed edges to multiple vertices in Y. We then solve the minimum cut problem for z" and Y. If an edge between =² and E Z is in the solution to this min-cut problem, it translates to removing all the directed edges from 917
919 2 to Y in the original problem. Note that we can run the algorithm on the maximal hedge formed for
Q in G rather than G itself.
Alg Algorithm 4 Heuristic algorithm 2.
1: function HEID2(G, Y, WG)
2:
g' < MH Y)
3:
Z - {z E V Y (2,3) E Y
4:
H < The induced subgraph of G' on its bidirected edges.
5:
WH (we Wgle H}
6:
VA + V U""
7:
for E Z do
8:
F.H <- [
9:
WH WH U (w(x+.)) Ey m(nn)
10:
for y E Y do
11:
E +- F u [y.y²}
12:
WH WH U (W(n'") oc} E + MinCut(HL "H,2",8"
13:
return (E, EeEg W.)
E
Experiments
922
Noting that the synthetic/simulation results in the main paper were for graphs with log(n)/n sparsity constraint, we begin this section by providing a set results on the simulated graphs without the sparsity penalty for comparison. Then, we provide information about the causal discovery algorithm used derive the psychology 'Psych' real-world graph. We also provide experimental results for Problem foomuultionn in Section E.3
923
925
926
927
E.1
Additional Simulation Results without Sparsity Constraint
928
The simulation results for graphs generated without the sparsity constraint are shown in Figure g These results illustrate monotonic increases in runtime and cost as the number of nodes increases. Our proposed heuristic algorithms (HEID-1 and HEID-2) maintain runtimes less than 0.5 seconds even for 250 nodes. In contrast, the two exact algorithms (MCIP-exact and EDGEID) exceed the three minute runtime limit at only 20 nodes, and the MCIP heuristic variants IMCIP-HI and MCIP-H2) have runtimes which increase exponentially with the number of nodes. These results highlight the efficiency of our proposed heuristic algorithms to find solutions with equivalent cost with significantly faster runtimes.
929
931
933
935
938
E.2
Psychology Graph Discovery
937
The settings for deriving the putative structure used on the psychology real-world graph are provided in Table
24

---

16
200
150
Tinee baamba
HEID-2
HEID-1
MCIP-HI
10
100
MCIP-
MCIP
10
MCTP-312
cuac
-00
EDGUD
300
130
250
lopeligiical
before tepelogical
(a) Runtimes.
(b) Solution costs.
MCTP-csact
EDGEID
100
150
200
250
Namiler of vottice betinn Y inpollgiii undir
(c) Fraction for which runtime of 3 minutes exceeded.
Figure 8: Experimental results (for graphs generated without the sparsity constraint) for runtime, solution costs, fraction of graphs for which solution found, and fraction of graphs for which runtime limit of 3 minutes was exceeded. Error bars for runtime and cost graphs indicate 5th and 95th percentiles. Best viewed in color.
Table 3: Hyperparameter settings for the Structural Agnostic Model used to generate the putative (directed) structure for the 'Psych' real-world dataset.
Parameter
Value
Learning Rate
0.01
DAG Penalty
True
DAG Penalty Weight
0.05
Number of Runs
50
Train Epochs
3000
Test Epochs
800
Mixed Data
True
hlayers
dhlayers
lambdal
10
lambda2
0.001
dlr
0.001
linear
False
nh
20
dnh
200
939
E.3
Simulation Results for Problem Formulation
The experimental setup is exactly in the main text (the results depicted in Figure 4. except that the probabilities are chosen in the range [0.01, 1] instead of [0.51, 1]. and we use the weight mapping corresponding to Problem 2 described in Lemmal That is, we map each probability pe to the weight log(1 - pp)) in the corresponding edge ID problem.
941
943
944
The simulation results are presented in Figure Runtimes and costs are shown for the subset of graphs for which all algorithms found solution (to facilitate comparison). Runtimes for each algorithm are shown in Fig. 9a where it can be seen that our proposed HEID-1 and HEID-2 heuristic algorithms have negligible runtime. contrast, EDGEID had large runtime variance which depended heavily the specifics of the graph under evaluation, particularly for graphs with fewer vertices.
945
947
25

---

11240
1201311
HEID-1
0.055
BEID-2
HEID-2
EDGGID
18.15
0.010
(a) Runtimes.
(b) Solution costs.
IDGED
2003
12:3
2000
255
Fraction runtime exceeded 3 min.
Figure 9: Experimental results for runtime, solution costs, fraction of graphs for which no solution found, and fraction of graphs for which runtime limit of minutes was exceeded. Error bars for runtime and cost graphs indicate 5th and 95th percentiles. Best viewed color.
The costs for each graph are shown in Fig. 9b Figure De shows the fraction of evaluations for which the runtime exceeded 3 minutes (applicable to the exact algorithms). In general, and owing the sparsity penalty in our graph generation mechanism, the cost of identified solutions falls with the number of vertices. Overall, HEID-1 was both the most consistent in terms of finding solution, 953 having a short runtime, and achieving close to optimal cost.
949
951
26


Reviews:
[{"review_id": "ymFNJBTDosW", "reviewer": "Reviewer_s5gw", "summary": "1. Given uncertainties about the existence of edges in a causal diagram, this paper consider two problems:\n\n* finding the most probable graph that renders a desired causal query identifiable.\n\n* finding the graph with the highest aggregate probability over its edge-induced subgraphs that renders a desired causal query identifiable.\n\n2. Then, the authors introduce a combinatorial optimization problem which they call the edge ID problem and show that it is NP-hard. Further, they show that the two problems mentioned above are also NP-hard by reducing them to the edge ID problem. \n\n3. Finally, the authors propose several exact and heuristic algorithms for the aforementioned problems.", "questions": "Questions:\n1. In line 52, the authors say 'selecting the most plausible subgraph in which the assumption holds true'. Could they justify or elaborate on why this is the case? In other words, I fail to see the point being made here.\n\n2. What happens when the uncertainties associated with the edges are such that $p_e = 0$ or $p_e = 1$ instead of $p_e \\in [0,1]$? It is clear that the weights in Lemma 1 are either 0 or $\\infty$. Would the recursive algorithm or the heuristic algorithms simplify? Would the solutions of three problems considered in this work simplify? Would the solutions/algorithms map to some existing work?\n\n3. Could the authors provide more insight regarding Lemma 1? More specifically, is there any intuition behind the weights of the edge ID problem that Problems 1 and 2 map to?\n\n4. Depending on the number of vertices and edges in the underlying causal diagram, the probability in (1) for any subgraph might be very small. For example, the values for Problem 1 for $G_1$ and $G_2$ are 0.049 and 0.081 respectively. Further, it is also likely that the aggregate probabilities in Problem 2 for two graphs are not very different. In that case, instead of a single identification formula, it might be useful to find a bunch of such formulae. In other words, it might be useful to derive interval bounds for the causal effect than a point estimate. Could the uncertainties about the existence of the edges and/or the problems analyzed in this work be useful towards this?\n\n5. As mentioned in lines 148-149, Problem 2 is a surrogate to recovering the identification formula with the highest plausibility. Do the authors have a sense of how far away is this lower bound from the true value?\n\n6. I understand that the Assumption 1 could be expanded to allow edges with perfect negative or positive correlation as mentioned in lines 158-159. But a perfect correlation between two edges basically makes the probability of one of the two edges irrelevant/useless. I don't have any major concern with Assumption 1 but it may be useful to comment on how relevant this assumption is in practice. \n\nSuggestions / typos:\n1. The authors might want to introduce certain notation before using them e.g., $P_X(Y)$ in line 47, $P_X^M(Y)$ in line 97, ...  \n2. The authors introduce the notation $[G]_{Id(P_X(Y))}$ in line 102 as the set of ADMGs in which $P_X(Y)$ is identifiable. Is each element of this set an edge-induced subgraph of $G$? The authors might want to clarify this. \n3. In line 111, the authors mention that the set including $z$ and $t$ forms a hedge for $Q[x]$. Is this correct? Should $x$ not be a part of the hedge for $Q[x]$? \n4. The authors might want to clarify 'the ID algorithm' mentioned on line 192.\n5. Based on lines 268-276, it seems that there exists a hedge for $Q[Y^{mcip}]$ in ADMG $H$ in Figure 2b. Is this true? Does $Y^{mcip}$ form a district in $H[Y^{mcip}]$?\n6. What is $n$ on lines 289 and 320?\n7. It might be useful to provide more details about the real-world datasets used in this work. Why are the outcome variables in these datasets not fixed? Is there a particular reason why these specific datasets were used?", "limitations": "In its current form, this work has some limitations which are not addressed. For example, see the two points made in the weaknesses above. \n\nFurther, I am also concerned about the relevance of the Problems studied here. In Problem 1, the authors are interested in finding the most probable causal diagram in which the causal effect is identifiable. In Problem 2, the authors are interested in finding (a lower bond on) the most probable causal effect. These problems makes sense when there exists no way to find the causal effect (under the assumption that only the uncertainties associated with the edges are known).\n\nWhile most algorithms proposed to identify causal effect assume access to a correctly specified causal diagram, there has been a line of work for identifying causal effect using only an anchor variable when the underlying causal diagram is not known. For example: (1) Entner et al 2013 -- Data-driven covariate selection for nonparametric estimation of causal effects [https://proceedings.mlr.press/v31/entner13a.html], (2) Cheng et al 2020 -- Towards unique and unbiased causal effect estimation from data with hidden variable [https://arxiv.org/pdf/2002.10091.pdf], (3) Shah et al 2021 -- Finding Valid Adjustments under Non-ignorability with Minimal DAG Knowledge [https://arxiv.org/pdf/2106.11560.pdf].\n\nIn light of these works, I am concerned about the relevance of the two problems studied in this work. First, by requiring uncertainty for *every* edge in a causal diagram, this paper require global knowledge of the underlying causal diagram which may be too much to ask for as described in first weakness above. In contrast, the aforementioned works require only local knowledge of the underlying causal diagram concerning the anchor variable. Second, and more importantly, consider a scenario where the aforementioned works are able to find a valid identification formula for a causal effect of interest. In that case, no matter what the rest of the causal diagram looks like, the identification formula remains valid. On the other hand, this may not be true for the two problems studied in this work. Consider the example 1 on page 4. If one were to solve Problem 1, they may choose $F_2$ over $F_1$ and if one were to solve Problem 2, they may choose $F_1$ over $F_2$. However, it is certainly possible that the true underlying causal diagram is $G$ in Figure 1a and neither $F_1$ nor $F_2$ are valid identification formulae. To conclude, what is the validity of the causal effect / identification formula returned by the two problems considered in this work? I understand that this may not be apples to apples comparison with the three works mentioned above, my question in the previous sentence stands. How would the outputs of the Problems considered here be used in a real-world application?", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. This paper introduces three new problems and prove that they are NP-hard:\n* finding the most probable graph that renders a desired causal query identifiable.\n* finding the graph with the highest aggregate probability over its edge-induced subgraphs that renders a desired causal query identifiable.\n* finding the set of edges $E$ with minimum aggregated weight that renders a desired causal query identifiable in the graph resulting from removing $E$ (i.e., the edge ID problem).\n2. As a consequence of their work, the authors also show that if an identification formula is valid w.r.t a causal graph, it is also valid w.r.t all its edge-induced subgraphs. \n3. Further, they also establish a bi-directional link between the edge ID problem and the minimum-cost intervention problem. Therefore, the algorithms proposed here could be useful to solve the minimum-cost intervention problem as well.\n\nOriginality:\n\nThe paper is technically solid and brings a significant originality of ideas. However, I am a little concerned about the importance of the questions considered. See the limitation section below.\n\nClarity:\n\nThe paper is mostly well-written. There are certain places where the writing could be improved/made clear. Please see 'Suggestions / typos' below.\n\nWeakness:\n1. **Relevance of the problem setup:** As mentioned in the paper, most algorithms proposed to identify causal effect assume access to a correctly specified causal diagram. This assumption includes knowing the presence of every edge in a causal diagram with probability 0 or with probability 1 i.e., $p_e = 0$ or $p_e = 1$. While this paper does not need to know a binary $p_e$, it still needs to know a continuous valued $p_e$ i.e., $p_e \\in [0,1]$ for every edge in a causal diagram. In my opinion, such information is difficult to obtain in most real-world applications. The authors sample $p_e$ uniformly between 0.51 and 1.0 in all of their experiments and mention that these uncertainties may reflect the confidence of a particular statistical test. However, how would one obtain such information for bi-directed edges even from statistical tests? I would encourage the authors to think more carefully about this requirement and include real-world scenarios where this requirement would be satisfied. \n\n2. **Type of causal queries studied:**  In Remark 1, the authors mention that their results are not limited to causal queries of the form $Q[Y]$. They can be applied to general queries of the form $P_X(Y)$ when the directed edges of the causal diagram are known. However, in this case, the authors are inherently eliminating any uncertainties associated with the directed edges of the causal diagram which seems against the spirit of the paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "T9-uYrgfIMM", "reviewer": "Reviewer_Yekr", "summary": "The paper considers a setting where one does not have access to a fully specified causal ADMG but a probabilistic causal graph in which the directed/bidirected edges are assigned probabilities. It studies two questions under this setting:  Given a probabilistic graph and a specific causal effect of interest, (1)  which subgraph has the highest plausibility and (2) which subgraph has the highest aggregate probability over its edge-induced subgraphs for which the causal effect is identifiable? The paper shows that both problems reduce to an NP-hard combinatorial optimization problem, provides several exact and heuristic algorithms, and empirically evaluates the proposed algorithms.\n", "questions": "Are the results limited to causal queries of the form Q[Y] or applicable to arbitrary causal effects $P_X(Y)$? Please clarify Remark 1.\n\nIn the experiments, the edge probabilities $p_e$ are sampled uniformly between 0.51 and 1.0. Why making $p_e > 0.5$? I believe this makes the graph samples biased. In fact, I suspect making all edge probabilities larger than 0.5 might make certain optimization problems easy to solve (just a guess), but any reason keeping $p_e > 0.5$?\n\nLine 111, {z, t} should be {z, x}?\n", "limitations": "If the results are indeed limited to causal queries of the form Q[Y] instead of arbitrary causal effects $P_X(Y)$, then this limitation should be made clear in the abstract/introduction, etc.\n", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality\n\nThe paper introduces a new causal inference setting represented by probabilistic causal graphs that capture uncertainties in the existence of edges. The setting relaxes the restrictive requirement that one must have access to a fully specified causal graph in the majority of works on causal effect identification. To the best of my knowledge, this problem setting is novel.\n\nQuality of work\n\nThe technical results look sound. The proposed algorithms look reasonable. The empirical evaluation is largely adequate.\n\nClarity\n\nThe paper is clearly written. The presentation is excellent.\n\nSignificance\n\nThe main weakness of the paper is in its significance. Although the results are of some interest, it looks to me the paper does not really solve the problem it claims to be solving. \n\n-It looks to me that the results are limited to causal queries of the form Q[Y] instead of arbitrary causal effects $P_X(Y)$. Remark 1 appears to address this issue and claims ``They can be applied to general causal queries of the form $P_X(Y )$ if the directed edges of G and therefore the set $Anc_{G\\setminus X}(Y)$ are known.'' It’s not clear what this claim means. Are the results of the paper applicable to general $P_X(Y )$ only if all the directed edges are fixed with probability 1?\n\n-Problem 2 does not solve the problem of deriving an identification formula for a given causal query that holds with the highest probability. Solving Problem 2 finds a lower bound on the plausibility of an identification formula since there may exist other types of graphs with the same identification formula.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JqAd-OU-TZS", "reviewer": "Reviewer_PiUW", "summary": "This paper addresses the problem of causal identification under structural uncertainty. In particular the authors assume that the probability of edge existence is given and provide an algorithm to find the most probable configuration for a given causal query of interest. Empirical results show promise. ", "questions": "In many practical settings I would imagine that there are a large number of dense graphs that appears (i.e., many non-zero probabilities) do the authors have ideas or guidance on how to reduce the size of the search space?", "limitations": "The authors address limitations of the proposed approach well. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* Novel and interesting task. Structural uncertainty and misspecification is commonplace, and addressing this for identification is a very important problem area. \n* Well described problem setup and the authors provide both exact and heuristic solutions. \n\nWeaknesses:\n\n* Approach seems fraught in dense graphs. \n* Experimental evidence could be more compelling, would especially like to see a comparison with more naive approaches. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BTLFQ8vldt3", "reviewer": "Reviewer_2dMf", "summary": "This paper addresses problems of probabilistic reasoning about uncertainty in causal diagrams. In particular, given a simple distribution over ADMGs, and a causal effect query, the authors consider 1) finding the most likely graph that is identifiable; and 2) finding the identifiability formula with the greatest probability of being valid. They show that 1) and a relaxation of 2) are equivalent to the edge-ID problem, which they show to be NP-hard (in particular, equivalent to the minimum-cost intervention problem). In view of this, they provide a number of heuristic algorithms to solve the edge-ID problem, demonstrating their efficacy on both simulated graphs and real-world datasets.", "questions": "1) What practical applications can the authors envisage for their methods?\n2) In all experiments, the probability of an edge is restricted to lie in [0.51, 1]. Is this because an edge with probability <0.5 would always be removed? If so, do the authors consider this a limitation of their formulation of the problem (in that positive correlations between edges are not possible)?", "limitations": "The authors appropriately acknowledge the limitations of their method (independent edges, approximation made by Problem 2).", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, this is a technically strong and interesting paper which introduces a number of new ideas. The authors introduce the novel problem of evaluating (maximal) probabilities of identifiability under graph uncertainty, and provide both clear formal results on hardness as well as practical heuristic algorithms. \n\nForm a theoretical perspective, the reductions to and from MCIP (Thm 1 and Thm 2) are quite non-trivial and provide an interesting computational link between the problems of choosing minimal cost interventions and most likely edge-subgraphs for identifiability. The authors study the problem under the restrictive assumption of independent edges, but also introduce a clever extension to distributions with perfect negative correlations. Algorithmically, the backtracking exact algorithm is simple but sensible, while the heuristic algorithms make clever use of the properties of hedge structures.\n\nThe presentation of the paper has clearly been thought out carefully; in particular, the technical clarity of the main paper and appendix proofs is excellent. However, in terms of telling the story, the paper as written seems to rely on a lot of implicit context to be fully understood, which could perhaps be spelled out more explicitly. To give a few examples, with the aim of providing constructive suggestions for improving readability:\n- Definition 4 of a hedge appears to be non-standard, as a specific case of the full definition where G[Y] forms a c-component and the intervention is on all other nodes V\\Y; while I understand the authors’ desire to set up the intuition, it would be helpful to explicitly state this.\n- Theorem 1 appears before the MCIP problem is defined or even mentioned; in my opinion, given that the relationship between these two problems is so close as shown in the proofs of Thm 1 and 2, it would be useful to explicitly mention this and give some intuition in the main paper.\n- The MCIP problem formulation is not intuitive (“minimum cost set of interventions”) without the context in [1] about why the stated formulation is consistent; this could be stated explicitly.\n\nMy main criticism of the paper is with regards to the motivation of the edge-ID problem, and as a result the degree to which the paper breaks new ground beyond [1]. In particular, it is not clear why one would want to find the most likely identifiable graph. Unless this probability is very high, it would be unreasonable to rely on identification formulae based on that graph. Finding the identification formula that is most likely to be valid is more compelling, but unfortunately (and understandably from a computational perspective) a rather crude relaxation is used, which could have very different solutions. \n\nIn this sense, I would have liked to have seen some experiments demonstrating the utility of the edge-ID problem, by putting it in the context of the original problems. In particular, it might be useful to see the raw probabilities associated with the most likely graph/most likely aggregate graphs; or perhaps, in cases where exact computation is feasible, the gap between the probability of the most likely identification formula and the solution to Problem 2. \n\nNonetheless, this is an extremely solid work overall that provides new understanding of the computational issues regarding probabilistic reasoning about identifiability.\n\n[1] S. Akbari, J. Etesami, and N. Kiyavash. Minimum cost intervention design for causal effect identification.  \t \t \t\t\n\t\t", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject