Causal Effect Identification in Uncertain Causal Networks
Authors: Sina Akbari
Fateme Jamshidi
Ehsan Mokhtarian
Matthew James Vowels
Jalal Etesami
Negar Kiyavash
Venue: NeurIPS 2023 poster (2023)
Keywords: Causal effect
identifiability
causal DAGs
probabilistic graphs
TL;DR: We study the problem of causal effect identifiability when the knowledge of the underlying DAG is probabilistic rather than deterministically known.

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 exist with uncertainties which may, for example, represent degree of belief from domain experts. Alternatively, the uncertainty 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 them against both real-world networks and randomly generated graphs.

Causal Effect Identification in Uncertain Causal Networks
Sina Akbari EPFL, Switzerland sina. akbari@epfl.or ch
Fateme Jamshidi EPFL. Switzerland
Ehsan Mokhtarian EPFL, Switzerland
fateme. . jasaamiiiiiio www.dieepll.ooomooo ch
ehsan www...aiaaaiineel...ccmmm
Matthew J. Vowels
Jalal Etesami TUM, Germany
Negar Kiyavash
University of Lausanne, Switzerland matthew. www.wvwwnwl.lloommmm
EPFL, Switzerland negar. Bagaaakkyyavasheepf..oo
j et etesami de
Abstract
Causal identification the core of the causal inference literature, where complete algorithms have been proposed to 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, we study the setting where a probabilistic model of the causal structure is available. Specifically, the edges in causal graph exist with uncertainties which may, for example, represent degree belief from domain experts. Alternatively, the uncertainty 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 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-complete combinatorial optimization problem which call the edge ID problem. We propose efficient algorithms to approximate this problem and evaluate them against both real-world networks and randomly generated graphs.
1 Introduction
large proportion of questions of interest various fields, including but not limited to psychology. social sciences, behavioral sciences, medical research, epidemiology. economy. etc., are causal in nature B3 In order to estimate causal effects, the gold standard is performing controlled be prohibitively expensive,
interventions and experiments. Unfortunately, such experiments unethical, or impractical [10 12] In contrast, non-experimental data are comparatively abundant, and expensive interventions are required to generate such data. This has motivated the development of numerous techniques for understanding whether causal query can be answered using observational data. Specifically, if a particular causal query is identifiable, means it can be expressed of the observational distribution and thus estimated from observational data (at least in principle).
function
A significant body of the causal inference literature is dedicated to the identification problem 23 29 24]. In particular, [13] presented a complete algorithmic approach to decide the identifiability of a specific query and proved that Pearl's 's do caleulus is complete. Furthermore, [26] provided graphical criteria to decide the identifiability based on the hedge criterion. The problem of identifiability
was later generalized deal with interventional data (21 20), selection bias 0. context-specife
independence relations [1 15] and causal bandits [16]. However, all of these results hinge on the full specification of the causal structure, i.c., access correctly specified Acyclic Directed Mixed Graph (ADMG) that models the causal dynamics of the system. This requirement is restrictive in number of ways. (i) The causal identification problem concerned with inference from the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

observational data, but the ADMG cannot be inferred from the observational distribution alone. (ii) which are prone to errors This can in turn result in
Structure learning methods rely heavily on statistical tests 227 3 4
arising from lack of sufficient data and method-specific limitations 25 misspecification of the causal structure.
A notable work to address the second challenge is [22]. where the authors proposed a causal discovery method that assigns a probability the existence of each edge, as opposed making "hard" decisions based on a single or limited number of tests. This is achieved by updating the posterior probability of a direct link between two variables, denoted as and Y, using conditional dependence tests that incorporate independent evidence. The authors demonstrate that the posterior probability denoted as Pi, of a link between X and Y after performing i dependence tests (d,, where j ranges from to is given by the following equation:
14 Pt pi- + (1 - Pi (G + d:)
where G represents a factor ranging from 0 to 1, and it can be interpreted as the measure of "importance" or relevance associated with the truthfulness of each test, denoted as d,. Other closely linked work include (7] and 44. where an optimal transport (OT)-based causal discovery approach is proposed that assigns score to each edge of the graph denoting the strength of that edge.
While previous research, such as [22], has focused on probabilistic learning of causal graphs, the problem of causal effect identification on these graphs remains unexplored. This paper introduces novel approach to address causal effect identification in a scenario where only a probabilistic model of the causal structure is available, as opposed to complete specification of the structure itself. For instance, an ADMG G is given along with probabilities assigned to each edge of G. An example is shown in Figure La These probabilities 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 9 assigned its own plausibility score. Since the causal structure is not deterministic anymore, answering questions such as "is the causal effect P(Y|dol X)) identifiable?" ?" also becomes probabilistic in nature. One can compare the overall plausibility of different subgraphs in which the causal effect is identifiable and then select the graph which maximizes the plausibility.
this work, for 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 (X)) identifiable?" The answer to this question allows us to quantify how confident we are about the causal identification task given the combination of the data at hand and the corresponding probabilistic model.
As the causal identification task is carried out through an identification formula that is based on the causal structure, our second focus on deriving an identification formula for a given causal query that holds with the highest probability. This problem poses a greater challenge compared to the former, as a single identification formula can be valid for various graphs. Consequently, the probability that a particular identification formula is valid for a causal query becomes an aggregate probability across all graphs where this formula holds. We shall illustrate this point in more detail through Example iT Section [ The intricacy of characterizing all valid graphs for given formula makes it an intractable and open problem. To surmount this obstacle, we establish that if an identification formula is valid for a causal graph, it remains valid for all edge-induced subgraphs of that graph. This allows us to form a surrogate problem (see Problem 2 in Section 2.1 that recovers a causal graph with the highest aggregated probability of its subgraphs. The probability of the resulting graph provides lower bound on the highest probable identification formula.
Both problems discussed in this work are aimed at evaluating the plausibility of performing causal identification for a specific query given dataset and -etermeeriiiiticc model describing the causal structure. To sum up, our main contributions are as follows.
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 is 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.

---

o7
ADMG
(b) 91 C g.
(c) C.
Figure I: (a) An example of probabilistic ADMG 9 with corresponding edge probabilities. (b) and (c) are two different subgraphs of G in which Qlyl is identifiable.
2. We show that both aforementioned problems reduce to a special combinatorial optimization problem which we call the edge ID problem. Moreover, we prove that the edge ID problem is NP-complete, and thus, so are both of the problems.
3. We propose several exact and heuristic algorithms for the aforementioned problems and evaluate their performances through different experiments.
2 Preliminaries
We utilize small letters for variables and capital letters for sets of variables. Calligraphic letters are used to denote graphs. An acyclic directed mixed graph (ADMG) G = (VS, Eyg Eg) is defined as an acyclic graph on the vertices VS, where E C V x V and E S (22)) are the set of directed and bidirected edges among the vertices, respectively. With slight abuse of notation, if e E Eg U Eg we write g. We use g' S when g' is an edge-induced subgraph of G, i.e., g' = (V9", Ey ,E''), where V = V0 and F S Fgf for i E {b, d). We denote by G[X] the vertex-inducee subgraph of G over the subset of vertices X C V9, For a set of vertices X. we denote by Ance (X) the set of vertices in G that have a directed path to X. Note that C (A))g(()))) Let Px (Y)) be a shorthand for P(Y do))) and PM (-) denote the distribution of variables described by the causal model M.
Definition 2.1 (Identifiability 24 Given causal ADMG G (V$, "E Egg ) and two disjoint subsets of variables X, Y S. V the causal effect of X on Y, denoted by Px is identifiable in 9 P (Y) = PMMa (Y) for any two models M) and M2 that induce G and PM, (V9) = pasa (V9) > O.
Definition 2.2 (Valid identification formula). For a causal ADMG g over variables V9 and a causal query (Y),,, we say functional FF defined on the probability space over 1 is valid identification formula for Px (Y) in G if ph (Y) = P (Y) = F[PM (V9)) = F(PMa (V9) for any two models Mj and M2 that induce G and MM (V9) = PMppaaaavv >
For any query Px let (I)) denote the set of subgraphs of G which 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\Y on Y, i.e., =
Definition 2.3 (District). For ADMG G = (V8, Fg. Fg) ) let Ge, denote the edge-induced subgraph of G over its bidirected edges. C V a district (aka c-component) in g [ connected.
Definition 2.4 (Hedge (26)). Let & be an ADMG, and &. X be two subsets of its vertices, where Y is a district in G[Y]. Vertices X form hedge for Q[Y] if X is district in G[X] and
Ancgix] (Y) = x[]
Definition 2.5 (Maximal hedge (2). For ADMG G with set vertices Y, let X be the union of all hedges formed for Q[Y]. Graph G[X], denoted by MH Y). is called the maximal hedge for Q[Y].
As example, both sets {t, . and (2, 2) form hedge for Q[1c] in G in Figure la and G12 is the maximal hedge for Q[a].
'ee showed in our previous work (2) that this intuitive definition is equivalent to the standard definition of hedge in (26).
3

---

2.1 Problem setup
Let G (V9, Eg. E be an ADMG, where V is the set of vertices each representing an observed variable of the system, F the set of directed edges, and Fiğ is the set of bidirected edges among V9, We know a priori that the true ADMG describing the system an edge-induced subgraph of e and we are given a probability map that indicates for each subgraph of 9 such G.. with what probability Gg is the true causal ADMG of the system. We denote this probability as P(G.). For instance, if edge probabilities Pe are assumed to be mutually independent, P(G.) takes the form:
P(G.) = II
II (1-Pee).
eEG.
egG,
In what follows, we will refer to P(G.) simply as the probability of the ADMG G.. The first problem of our interest is formally defined as follows.
Problem 1. We consider the problem of finding the most probable edge-induced subgraph of G, in which the causal effect Q is identifiable. That is, the goal is to find the ADMG G defined by
9 : G. e.CC.S.elf)aacov
arg max
P(G.)-
We will prove in Lemma 3 that if Q[Y] is identifiable in G, then it is also identifiable in every edge-induced subgraph of g. In 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.
Example 1. Consider the ADMG in Figure [aa With the given edge probabilities and assuming independence among the edge probabilities, the subgraph of G illustrated in Figure Ibhas has probability 0.7 x 0.7 x 0.1 0.049, whereas the subgraph of Figurelchas probability 0.3 0.3 x 0.9 0.081 (see Eq. (T)) If we were to solve Problem [ we would choose G2 over Gr. as it has a higher probability. Now consider identification formulas in G1 and G2. respectively:
F2: P
Z,T'
Fi is valid identification formula for any edge-induced subgraph of 91 (see Lemma 3 Analogously, Fe is valid for all edge-induce subgraphs of Gz. If we consider the aggregate probability of the subgraphs of 9n and G2, i.e.,
1
- 0.9 0.9 0.1,
VS.
- 0.7) x P()==
0.7) = 0.09,
&CG.
OCS,
then we 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.
Plausibility of certain identification funetional 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, alternatively, we can enumerate all valid formulae for a given graph which changes the problem's ss search space to the space of all graphs. However, this is yet another challenging and, to the best of our knowledge, an open problem. Instead, we proposed a surrogate problem that yields a lower bound for the most plausible identification formula and identifies a causal graph where this formula is valid. To do so, we use the result of Lemma that shows when an identification functional valid in a causal graph, it also valid in all its edge-induces subgraphs.
Problem 2. Consider the problem of finding the edge inguedd subgraph H of G with a maximum aggregate probability of its subgraphs. in which Q[Y) is identifiable. Formally.
H. w.G....elllaaaaa
arg max
Σ P(G)
OCG.
"Note that in case such information is not available, one can simply take G to be a complete graph over both its directed and bidirected edges, as every graph is subgraph of the complete graph. Even when certain G is available but the investigator uncertain about it, the complete graph serve conservative choice eliminate uncertainty.
3 As we shall discuss in Remark 2.1 our results are not limited to causal queries of the form Q[Y]. They are applicable to general causal queries of the form Px PY) as long as the set of ancestors of Y are known.

---

In other words, we are looking for causal graph 7/" with the maximum aggregate probability of its subgraphs among the graphs in ra(Q)))) i.e., the graphs in which Q|Y identifiable. Running an identification algorithm on 7 yields an identification formula for Q[Y), which is valid least with the aggregate probability of the subgraphs of H." Therefore, Problem 2 is surrogate for recovering the identification formula with the highest plausibility. In the sequel. for simplicity, we study Problems 1 and 2 under the following assumption. However, as proved in Appendix [ our results are valid in more general setting where we allow only for perfect negative or positive correlations among the edges. An example of a perfect negative correlation between two edges is that both cannot exist simultaneously. Appendix [. discusses the significance of this generalization.
Assumption 2.1. The edges of G are mutually independent, i.e., the probability of subgraph G, of G is of the form (
Remark 2.1. It is noteworthy that our results are not limited to causal queries of the form Q = P(Y [do(V \ Y)). They can be applied to general causal queries of the form Px (Y) the set Ancgy.x (Y) known. This because the causal query PX(Y) can be expressed as Exmor ( Q[Anceix (Y)), where Anegyx (Y) the set of ancestors of Y in 9 after removing the vertices of X. Furthermore, Px (Y) is identifiable in G if and only if Q[Ancg) (irsxxxxY), (Y)] is identi- fiable in & [30 26 [4]. Note that the assumption that Aneg (Y) is known is not equivalent to precluding uncertainty
the directed edges (as in the case of fixing the edge probabilities 0 or 1), but it rather imposes a perfect correlation type of constraint. Consider for instance the three graphs of Figure 2 where all of them share the same set Anogix (Y) = {z, t). . In fact, knowing this set forces a constraint of the type that if the edge + y does not exist, the path 2 + t + y must.
3 Reduction to edge ID problem and establishing complexity
We begin this section with the following lemma, to which we referred before. Thereafter, we discuss the hardness of the two problems considered in this work. For any causal query Px and ADMG G. if a valid identification formula for Px(Y) in G (Def. 2.2). then J a valid identification formula for Px (Y) in any G' C G. All proofs are presented in Appendix A In what follows, we first formally define the edge ID problem and then show the equivalence of Problems a to the edge ID problem under Assumption 2.1
Definition 3.1 (Edge ID problem). For ADMG G = (VS, Eq Eg), set of non-negative edge weights Wg { wwe 2 Ole E 9), and causal query Q|Y] for Y S V the objective of the edge ID problem is to find the set of edges E C Ey U Eg with minimum aggregated weight (cost), such that Q[Y] is identifiable in the graph resulting from removing E from G. Formally,
E
arg min Σ Wes
s.t. g'= (V9, Fg MAAE E. Eg
E) E (9)
ECEQUE cEE
That is, the cost of removing set of edges from & is the sum of the weights of each individual edge.
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 and with multiplicative objectives into the edge ID problem that has an additive objective.
Lemma 3.2. Under Assumption 2.1 Problem is equivalent to the edge ID problem with the edge weights chosen to be the log propensity ratios, i.e., we max (0, log( Pe }. Ve E G. Moreover, Problem 2 is equivalent the edge ID problem with the choice of weights w. - log(1 11 pe), We E G. That is, an instance of Problems | andd] 2 can be reduced to an instance of the edge ID problem in polynomial time, and vice versa.
As we mentioned earlier, the equivalence of these three problems can be established in more general settings than what is described under Assumption 2.1 We refer the interested reader to Appendix C for a discussion on one such setting. The following result shows no polynomial-time algorithm for solving these three problems exists unless P = NP.
Theorem 3.3. The edge ID problem is NP-complete.
Theorem 3 established through a reduction from another NP-complete problem, namely the minimum-costt intervention problem (MCIP) 2 3), which we shall discuss in Section 4.3 Theorem
5

---

Figure 2: Three different graphs that share the same set Anco (2,
3.3 is key result which shows the hardness of recovering the most plausible graph in which a specified causal effect of interest is identifiable.
Corollary 3.4. Problems) 7 and 2 are NP-complete under Assumption 2.1
is noteworthy that the size of the problem depends on the number of vertices of G, i..., |V9 and the number of edges of 9 with finite weight, i.e., |E = [gg + E. Since the ID algorithm (function ID of (26]) runs in time (( the brute-force algorithm that tests the identifiability of Q[Y] in every edge-induced subgraph of G and chooses the one with the minimum weight of deleted edges runs in time ( (?). In the next Section, we present various algorithmic approaches
for solving or approximating the solutions to these problems.
4 Algorithmic approaches
We first present recursive approach for solving the edge ID problem in Section 4.1 described in Algorithm[] [ Since the problem itself is NP-complete, Algorithm runs in exponential time in the worst case. In Section 4.2, present heuristic approximations of the edge ID problem, which runs in cubic time in the worst case. These heuristics can also be used as pre-process to reduce the runtime of Alg. by providing upper bound that 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-complete problem, namely minimum-cost intervention problem (2], which allows to use the algorithms designed for that problem to solve edge ID. Our simulations in Section 3 evvalate these approaches against each other.
4.1 Recursive exact algorithm
This approach described in Algorithm I The inputs the algorithm are an ADMG & along with edge weights Wg, set of vertices Y corresponding to the causal query Q[Y). an upper bound ub on the aggregate weight (cost) of the optimal solution, and a threshold th an upper bound on the acceptable cost of a solution. The closer "h is the optimal cost, the quicker Algorithm I will find the solution. If no upper bound is known, the algorithm can be initiated with w/ن = co. However, we shall discuss a few approaches to find a good upper bound wh in the following Section. Note that when th = 0, Algorithm I will output the optimal solution. Otherwise, as soon as feasible solution with weight less than With is found, the algorithm terminates (line 13).
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 no hedge formed for Q[Y]] i.c., = G[Y]. there no need to remove any edges from G and the effect is already identified. Otherwise, we remove the edge with the lowest weight (e) from H and recursively call the algorithm to find the solution after removing the edge e, unless the weight of is already higher than the upper bound =h which means no feasible solutions exist for the provided upper bound. Whenever feasible solution found, the upper bound wh is updated to the lowest weight among all the solutions weights discovered so far. This, in turn, helps the algorithm prune the exponential search space during the next iterations to reduce the runtime. As soon as solution with weight less than the acceptable threshold, i.e., th is found, the algorithm returns the solution. Otherwise, We updated to infinity so that it never gets removed (line 14). This is due to the fact that we have already explored all the solutions involving

---

Algorithm Recursive Algorithm for edge ID.
function EDGEID(G, Y, W wb wh)
2:
H. < MH(G.Y)
3: if' H. G[Y] then return (True,
4:
ID, Eimin + False,
5: while True do
6:
4 The edge of H. with minimum weight if we 00 or We > wht then return (ID, Emin)
7:
8:
(id, E) < EDGEID
e, W,Y, \ {we), wib we th we)
9:
if id = True then
WE - we + +E, Ee,en We,
11:
ID < True, wub c- WEE Fimin t F. (e) (c)
wab I th then return (ID, Eminn)
14: Update We f- 00 in Wg
4.2
Heuristic algorithms
In this section, present two heuristic algorithms for approximating the solution to the edge ID problem. These algorithms can also be used to efficiently find the upper bound "h, which could be fed as input to Algorithm
Algorithm 2 Heuristic algorithm for edge ID.
1: function HEID Y, W'))
2:
g' + MHI Y),
Z + {z E V By E Y: {2.8) E E
3:
4:
H induced subgraph of g' on its directed edges.
5:
WH + [we E Wele HH t -V#
[v",2*}
6:
for E Z do E t ER (2" WH t WH (w()))) Ey W(x.))) Wx + Wn U (W())))) = 20)
7:
for y E do E + E
8:
E+ MinCut(H. WH,*",y0
return (E, EeEF We) 9:
Let Z (2 By EY: {2,y) E EYYAY denote the set of vertices that have least one common bidirected edge with a vertex in Y. Any hedge formed for Q contains at least one vertex of Z. As result, to eliminate all the hedges formed for Q[). it suffices ensure that none of the vertices in Z appear in such hedge. To this end, for any E Z, it suffices to either remove all the bidirected edges between z and Y or eliminate all the directed paths from to 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 2n to the graph and draw directed edge from 2 to every z E Z with weight w = Σyey W(2.y), i.c., the sum of the weights of all bidirected edges between z and Y. Note that z can have bidirected edges to multiple vertices Y. We then solve the minimum cut problem for =* and Y. If an edge between x" and E Z is included in the solution to this minimum cut problem, it is mapped to remove all the bidirected edges between and Y in the main problem. Note that Q[]] in G rather than G itself. This heuristic is presented as Algorithm 2
the algorithm the maximal hedge formed for
An analogous approach which goes through solving undirected minimum cut on the edge-induced subgraph of G over its bidirected edges presented in Algorithm I in Appendix [ As mentioned earlier, these algorithms can be used either as standalone algorithms to approximate the solution to the edge ID problem, or as a pre-processing step to find an upper bound ub for Algorithm
Complexity and performance. The aforementioned heuristic algorithms can be broken down into two primary components: constructing an instance of the minimum-cut problem, and solving the latter. Both algorithms follow similar steps for constructing the minimum-cut problem. For reference,
7

---

W 11
31
Waygan
2/2
y1
to 3132
(a) ADMG G, Y
32
(b) ADMG H. ymmcip = (1/1, ./22)
Figure 3: Reduction from edge ID to MCIP
Alg. starts with identifying the maximal hedge formed for Q[Y), which is cubic-time in the worst case 12, followed by forming directed graph H. over the vertices of the maximal hedge. Forming this graph, which inherits its vertices and directed edges from G. is linear in time. Lastly, there exist several minimum-cut cettmumm-cut-maiimntee couutmaximum-ffe fflow algorithms that exhibit cubic-time performance. Therefore, our heuristic algorithms have a cubic runtime in the worst case. On the other hand, given the hardness result provided in the previous section, and in light of the fact that there is a polynomial- time reduction from the minimum hitting set problem to MCIP 33, the edge ID problem is NP-hard to approximate within factor better than logarithmic [I]]. Since our heuristic algorithms run in polynomial time, they are expected to be suboptimal by at least a logarithmic factor in the worst case. However, shall see in simulations, both algorithms achieve near-optimal results random graphs.
4.3 Alternative approach: reduction to MCIP
As alternative approach to the algorithms discussed so far, present reduction of the edge ID problem to another No-complete problem, i.e., the minimum-cost intervention problem (MCIP) introduced in [2]. This reduction allows us exploit algorithms designed for MCIP to solve our problems. The formal definition of MCIP is as follows.
Definition 4.1 (MCIP). Suppose (V9, Fg Fgg is ADMG, C V R is cost function mapping each vertex to non-negative cost, and Y C CV, The objective of the minimum-cost intervention problem for identifying the causal effect Q[Y] is to find the subset A C V with the minimum aggregate cost such that Q[Y] is identifiable after intervening on the set A.
The reduction from edge ID to MCIP based on a transformation from ADMG & another ADMG H, where each edge in G is represented by vertex in H. This transformation is based on the causal query Q[Y), and it maps the identifiability of Q in G to the identifiability of @cymcipp) in H. where is set of vertices in H. This transformation satisfies the following property; removing a set of edges E* in & makes Q[Y) identifiable if and only intervening on the corresponding vertices of E' in H. makes Q| identifiable. More precisely, after this transformation, solving the edge ID problem for Q in G is equivalent to solving MCIP for Q[ymeip] in H. The complete details of this transformation can be found in Appendix A.2. An example of this reduction is shown in Figure 3 where ( 82)1
& (Figure Baa is mapped to Q1f31, V2, y/2 !2) in 7. (Figure (3)). where (vi, 32. 2 is a district, and the set of all vertices of H. forms hedge for it. The vertices of H corresponding to each edge G are indicated with the same color and have the same weight (cost). We assign infinity cost to them to avoid intervening on the remaining vertices in H. It is straightforward to see that the solution to the edge problem in with the query Q = (v1- 3/2]] would be to remove the edge with the lowest weight. This is because after removing any edge in G. no hedge remains for Q.). Similarly, in H. the solution to MCIP with the query Q[Y
@ meip = {311 1/2 y is intervene on the vertex with the lowest cost among Z {2d [2 =f v/222 2b This because The following result establishes
after intervening on any vertex in Z, no hedge remains for the link between the edge ID problem in G and MCIP H.
8

---

000
REID REID2
REI1
REDD2
EDOEI
600
"To replicate our findings, our Python implementations are accessible via https://githut CattaainnCauaal-eee 1194 (802480
DICEP122
KY ah
SOGEID
10GRD
600
000
158
753
No
(a) Runtimes.
Solution costs.
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.
Proposition 4.2. There exists polynomial-time time reduction from edge ID to MCIP and vice versa.
In particular, the time complexity of the transformation from edge ID to MCIP scales linearly in size of G, and is cubic YY] More precisely, the time complexity is [[VV + E | (Y])). For further details, refer to the construction in Appendix A.2
5 Experiments
We evaluate the proposed heuristic algorithms 2 (HEID-1) and (HEID-2), as well as the exact algorithm (EDGEID) where the upper-hound to for EDGEID to be the minimum cost found by HEID-T or -2. Furthermore, given the reduction of the edge ID problem to the MCIP problem described in Section 4.3] we also evaluate the two approximation and exact algorithms from 2 (MCIP-H1, MCIP-H2, and MCIP-exact, respectively). Experimental results are provided for Problem [. and analogous results for Problem 2 are provided in Appendix E.3 All experiments were carried out on an Intel i9-9900K CPU running at 3.6GH
Simulations: The algorithms are evaluated for graphs with between 5 and 250 vertices. For given number of vertices, we uniformly sample 50 ADMG structures from a library of graphs which non-isomorphic to each other. Edges for each of these 100 graphs are sampled with probability of log(n)/n,, where 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 Pe uniformly between 0.51 and 1.0 The problem is then converted into edge ID according to Lemma 3.2 The vertices in the graphs are topologically sorted and the outcome is selected to be the last vertex in the topological ordering. We then check whether solution exists in principle by removing all finite cost edges and checking for identifiability. If not, a new graph sampled to avoid evaluating the algorithms algorithms and record the resulting runtime and the associated cost of the solution. the runtime exceeds 3 minutes, abort and log that the algorithm has failed to find solution.
graphs with no solution. For each of these 50 probabilistic ADMGs,
the
Results are presented in Figure 4 Runtimes and costs are shown for the subset graphs for which all algorithms found solution (to facilitate comparison). Runtimes for each algorithm are shown in Fig. 4a where can 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 to 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 as expected, the lowest cost achieved by the two exact algorithms, EDGEID and MCIP-exact, followed closely by the heuristic algorithms. Figure 4c shows the fraction of evaluations for which the runtime exceeded 3 minutes (applicable to the exact algorithms). In general, and owing to the sparsity
com/ /Stiaatabarri//assaalallllaaaal Effect- www.ndiieenatiii.oo / //github. com wom./mattthewwwwwesll//eeeee
and https:
IPS_ testted__tteeeee
"Note that we do not consider edge probabilities less than 0.5 as from Lemma 3.2 such edges would be mapped to edges with O weight in the equivalent edge ID problem, which can always be removed the beginning.

---

Table 1: Time (seconds), cost, and ratio PPG)) for seven algorithms over four real-world
datasets. dash- indicates the maximum runtime (500 seconds) exceeded.
Psych
Barley Cost
Alarm Cost
Water
Algorithm
Time
Cost
Ratio
Time
Ratio
Time
Ratio
Time
Cost
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
HEID-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
exact
0.0099
0.081
0.92
0.0028
0.0
0.0221
0.42
0.66
EDGEID
0.0005
0.0
1.0
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 MCIP-Exace regardless of the number of vertices and despite the fact that EDGEID is quicker at finding a solution when does so. Overall, HEID-1 was the most consistent in finding a solution, having a short runtime, and achieving close to optimal cost.
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 [8] using data collected as part of the Health and Relationships Project 32. The other three 'Barley' (48 nodes & 84 directed edges), 'Water' (32 nodes & 66 directed edges), and 'Alarm' (37 nodes & 46 directed edges) come from the bnlearn python package (28). For all four graphs, and with the simulations described above, introduce bidirected edges with a sparsity constraint of log(n)/n, and simulate expert domain knowledge by randomly assigning directed and bidirected edge probabilities between 0.51 and 1. The outcome Y is selected be the last vertex in the topological ordering. For these results, we provide the runtime (limited to 500 seconds) and cost, as well as the ratio of graph plausibility before and after selecting a subgraph in which the effect is identifiable P(L*)/ P()). This ratio is 1.0 if the effect is identifiable in the original graph and decreases according to the plausibility of an identified subgraph.
Results are shown in Table DI In cases where MCIP- and/or EDGEID did not exceed the runtime limit, it can be seen that HEID-2 and MCIP-H2 achieved equivalent to optimal cost and ratio. Runtimes for MCIP variants exceeded the HEID variants owing 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 FigureAc).
Concluding remarks
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 a number of algorithms for finding the most probable/plausible probabilistic ADMG in which the target causal effect is identifiable. We provided an analysis of the complexity of the problem, and an experimental comparison of runtimes, solution costs, and failure rates. We noted that our heuristic algorithms, Alg. [ and Alg. performed remarkably well across all metrics. In terms of limitations, we made the assumption that the edges in are mutually independent (Assumption 2.Ip. Future work should explore the case where this assumption does not hold. In this work, we studied the problem of point identification of the target effect. We envision that a similar methodology can be applied to partial identification. Finally, it is 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 using such approaches are encouraged to do so with caution, particularly for research involving human participants.
Acknowledgements
This research was in part supported by the Swiss National Science Foundation under NCCR Automa- /1.
tion, grant agreement 51NF40_ 180545 and Swiss SNF project
10

---

References
[1] Amir Mohammad Abouei, Ehsan Mokhtarian, and Negar Kiyavash. s-id: Causal effect identifi- cation in a coll-poulattin. AAAI, 2024.
[2] Sina Akbari, Jalal Etesami, and Negar Kiyavash. Minimum cost intervention design for causal effect identification. In Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pages 258-289. PMLR, 2022.
[3] Sina Akbari, Jalal Etesami, and Negar Kiyavash. Experimental design for causal effect identifi- cation. arXiv:2205.022.. 02232,, 2023.
[4] Sina Akbari, Luca Ganassali, and Negar Kiyavash. Causal discovery via monotone triangular transport maps. In NeurlPS 2023 Workshop Optimal Transport and Machine Learning, 2023.
[5] Sina Akbari, Ehsan Mokhtarian, AmirEmad Ghassami, and Negar Kiyavash. Recursive causal structure learning in the presence of latent variables and selection bias. Advances in Neural Information Processing Systems, 34: 101 19-100110 2021.
[6] Joshua Angrist and Guido Imbens. Identification and estimation of local average treatment effects. Econometricu, 62(2):467-475, 1994.
[7] Ricardo Baptista, Youssef Marzouk, Rebecca E. Morrison, and Olivier Zahm. Learning non- gaussian graphical models via hessian scores and triangular transport, 2023.
[8] Elias Bareinboim, Juan D. Correa, Duligur lbeling, and Thomas Icard. On Pearl's hierarchy and the foundations of causal inference. ACM Special Reports, 2020.
[9] Diego Colombo, Marloes H. Maathuis, Markus Kalisch, and Thomas S. Richardson. Learning high-dimensional directed acyclic graphs with latent and selection variables. The Annals of Statistics, pages 294-321, 2012.
[10] Angus Deaton and Nancy Cartwright. Understanding and misundertstanding randomized controlled trials. Social Science and Medicine, 210:2-21, 2018.
[11] Uriel Feige. A threshold of In for approximating set cover. Journal of the ACM (JACM), 45(4):634-652, 1998.
[12] Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based on graphical models. Frontiers in Genetics, 10, 2019.
[13] Yimin Huang and Marco Valtorta. Pearl's calculus of intervention is complete. Proceedings of the Twenty-Seoon Conference on Uncertainty in Artificial Intelligence (UAI), 2006.
[14] 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.
[15] Fateme Jamshidi, Sina Akbari, and Negar Kiyavash. Causal imitability under context-specific independence relations. arXiv preprint arXiv:2.306.00 00585, 2023.
[16] Fateme Jamshidi, Jalal Etesami, and Negar Kiyavash. Confounded budgeted causal bandits. 3rd Conference on Causal Learning and Reasoning, 2024.
[17) Fateme Jamshidi, Luca Ganassali, and Negar Kiyavash. On sample complexity of conditional independence testing with von mises estimator with application to causal discovery. arXiv preprint arXiv:2310. 13553, 2023.
[18] Diviyan Kalainathan, Olivier Goudet, Isabelle Guyon, David Lopez-Paz, and Michèle Sehag. Structural agnostic modeling: Adversarial learning of causal graphs. arXiv: 04999933. 2020.
[19] Richard M. Karp. Reducibility among combinatorial problems. Complexity of computer computations, pages 85-103. Springer, 1972.

---

[20] Yaroslav Kivva, Ehsan Mokhtarian, Jalal Etesami, and Negar Kiyavash. Revisiting the general identifiability problem. In Uncertainty Artificial Intelligence. pages 1022-1030. PMLR, 2022.
[21] Sanghack Lee, Juan D Correa, and Elias Bareinboim. General identifiability with arbitrary surrogate experiments. In Uncertainty in artificial intelligence, pages 389-398. PMLR, 2020.
[22] Dimitris Margaritis and Sebastian Thrun. Bayesian network induction via local neighborhoods. Advances in neural information processing systems, 12, 1999.
[23] Judea Pearl. Aspects of graphical models connceted with causality. Proceedings of the 49th Session of the International Statistical Institute, pages 399-401, 1993.
[24] Judea Pearl. Causality. Cambridge University Press, Cambridge. 2009.
[25] Rajen D. Shah and Jonas Peters. The hardness of conditional independence testing and the generalised covariance measure. The Annals of Statistics, 48(3), 2020.
[26] Ilya Shpitser and Judea Pearl. Identification of joint interventional distributions in recursive semi- Markovian causal models. In Proceedings of the National Conference Artificial Intelligence, volume 21, page 1219. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2006.
[27] Peter Spirtes, Clark N. Glymour, and D. Scheines, Richardand Heckerman. Causation, predic- tion, and search. MIT press, 2000.
(28) Erdogan Taskesen. bnlearn Library for Bayesian network learning and inference. Python Library, 2020.
[29] Jin Tian and Judea Pearl. A general identification condition for causal effects. AAAI, 2002.
[30] Jin Tian and Judea Pearl. On the testable implications of causal models with hidden variables. In Proceedings of the Eighteenth conference Uncertainty in artificial intelligence, pages 519-527, 2002.
[31] Santtu Tikka, Antti Hyttinen, and Juha Karvanen. Identifying causal effects via context-specific independence relations. Advances in neural information processing systems, 32, 2019.
[32] Debra Umberson. Health and relationships project. Inter-university consortium for political and social research, 2014-2015.
[33] Mark J. van der Laan and Sherri Rose. Targeted Learning Causal Inference for Observational and Experimental Data. Springer International, New York, 2011.
12

---

Appendix
The appendices are organized as follows. Formal proofs of the results stated in the main text are presented in Section A In Section B we describe the algorithm to recover the maximal hedge formed for a certain query (Def.2.5) which is used as a subroutine of Algorithm
generalization of Assumption 2.1 is discussed in Section [ Section provides further details of the heuristic algorithms discussed in the main text. Further evaluations and experimental conditions for our
proposed algorithms are presented in Section E
Table 2: Table of notations
Symbol
Description
V9
Vertices of G
Eg E A
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 Probability of edge Weight of edge e Causal effect of X on Y
Pe
We PY(
A Formal proofs
We begin with presenting the proof's of Lemma 3 and Lemma 3.2 Proofs of Theorem 3.3 and respectively.
Proposition 4.2 appear at the end of Sections A.I and A.2
For any causal query Px(Y) and ADMG 9, F is valid identification formula for Px in (Def. 2.2b, then F is a valid identification formula for PX( in any G' S G.
Proof. Let H. C G be an arbitrary edge-induced subgraph of G. Let F be an identification formula for Px (Y) in G. i.e. for any model M that induces G,
Px (Y) F(PM (V9)).
By definition, Px is identifiable in G. As result, there exists and identification formula such as F' that can be derived for Px (Y) in 9, using a sequence of do calculus rules and basic probability manipulations. Note that this means for any model M that induces G,
( = (PM (V))).
Note that an immediate corollary of Equations and Giis that for any model M that induces G,
F(PM (V9)) FF' (V9)).
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- graphhindependent. only suffices to show that any applied do calculus rule w.r.t. G 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 is also valid in H. To do so, it suffices to show that if all paths between Z, and Z₂ are blocked in & given W, they are blocked in H too, for arbitrary disjoint sets of vertices Z1, Zz, W C V8, Take an arbitrary path, p. between Zi and Z2 in H. Since H C G. this path exists in G. Since Z1 and Ze are d-separated given W in G, the path p is blocked by W. As result, any path between Z₁ and Zg in H is blocked by W. Therefore, any do-calculus rule applied in G. can also be applied in H. Hence, J' is valid identification formula for Px(X (Y). That is, for any model M that induces H.
(Y) (V) F'(M (V"))))
(
Now note that any model M that induces H. i.e., is compatible with H. is also compatible with g. Also, V = V As a result, from Equations 7 and & we know that for any model M that induces H.
(Y) (V
By definition, FF is a valid identification formula for Px (Y) in H.
13

---

Lemma 3.2. Under Assumption 2.1 Problem D is equivalent to the edge ID problem with the edge weights chosen be the log propensity ratios, i.e., w, max(0, log( "p))), Ve G. Moreover, Problem 2 is equivalent to the edge ID problem with the choice of weights we = - log((1 - pe). We E G. That is, an instance Problems [and can be reduced to an instance of the edge ID problem in polynomial time, and vice versa.
Proof. Problem 1. First consider arbitrary graph 91 (a(eM)))) such that 91 has edge with Pe < 1/2. Let G2 denote the graph G1 after removing e. I Lemma implies that G2 E [(] According Equation we have P(G2) 1- P(G)) > P(G)) (since Pe < 1/2).. As a result, P.
the solution G to Problem (Eq. has no edges with probability less than 1/2. We can therefore rewrite Problem as:
1
G arg max C.CG. 9.6 (.
P(G.)=
arg max G.CG. G. E
P(G.) s.t. Vee G. Pe 2
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
less than 1/2, as otherwise 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.
arg max P(G.) G,Co, (.
arg max log(P(G.)) 9.C9. (.
log( II Pe II (1-Pe))
max 9,C9. C
rEG.
egg.
arg max G,CO, G.E(o))a
log(pe)
+ Σ
log(1 Pe))
eEG
egf,
argmax G,Co. G.E(D))atoiT)
Σ log(p=)+ +
log(1 Pe)) Σ
log(1 pp))
Σ
log(1 Pe))
eES
egg.
cEG.
eEG.
Since Eegg, log(1 - + log(1 Pe)) is constant value that does not depend on Ge. it can be ignored the maximization and we have:
g
arg max CG. E (
Σ eEG.
log(pe) Σ
log(1 (1 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 e E EG we will have an instance of the edge ID) problem. Note that for edges with probability higher than 1/2, log( _=x))) ) 2 O, and this assignment of edge weights satisfies the positivity requirement. 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.
Problem 2. First note that under Assumption 2.1
for any graph G..
Σ P()) = II (1
p.)
Σ
II Pe
II
- pc)
II (1 - (p) egG,
SCG.
egc.
EC
e
é
14

---

This is because the inner summation goes over all the possible subsets of E and the summation adds up Therefore, we can rewrite Problem (Eq.
3ass
H"
arg max C, C.CG. 9, a GCO.
Σ P())
II (1 Pe) eg9.
arg max 9.C9, 0. G
log( II (1 - pe))
arg max G.CG. G.
EEG.
arg max 0.C9, G
log(1 Pe)
egg.
arg arg min G.CG. G.
E-lo((1
-ogg - -Pe).
egc.
With the same reasoning as before, assigning the weights we log(1 (1 Pe) each edge E we end up with an instance of the edge ID problem. Note that again 0 s - -log(1 p.) I co. It is noteworthy that this procedure also reversible with the choice of edge probabilities Pe
1 exp -.)), which reduces the edge ID problem to an instance of Problem 2 Again note that 0 1 exp (-w.) S 1 for any non-negative W..
A.1 Reduction from MCIP to edge
Theorem 3.3. The edge ID problem is NP-complete.
First note that edge ID is in the class of NP problems, since the ID algorithm [26] can verify a solution in polynomial time. To prove Theorem 3.3 we first present polynomial-ting reduction from MCIP to the edge ID problem. It has been shown that the minimum vertex cover problem can be reduced to MCIP in polynomial time (2) Combining the two reductions, we show that there exists polynomial-tine reduction from the minimum vertex cover problem to the edge ID problem. Since the minimum vertex cover problem is known to be NP-complete 19 it follows that the edge ID problem is also No-coeeeeee.
We propose the following reduction from MCIP the edge ID problem. Assume want solve MCIP given ADMG g (Vo, E Eg) query Q.Y,, and the intervention costs C(v) for V We construct graph, denoted by = Ti (g, Y), through the following steps.
For every vertex a E V \ Y. add two vertices x' x,2 V#,
b. For any bidirected edge 2x E Eg where E V Y and z E vo, add the bidirected edge
(a", 2²) to EK
c. For any directed edge (x,z) E Eg where x E V Y and z e v add the directed edge (x ,2²²) to EN.
d. For any bidirected edge (21, ES where v1, U2 Y, add the bidirected edge (v/ y2 to E.H.
c. For evrevery2o 2², x2 E // YY, draw the two edges (-t, } E E and (x2,x²) E E. Furthermore, the weight of {x), 2 is C(z).
f. The costs of the all other edges in H are assigned to be infinite.
With abuse of notation, for any vertex x /e \ Y, we define Ti = (x²,att) E FN where {2 2 } the bidirected edge H that corresponds in G. and inherits the same weight (cost).
'We later showed that there is polynomial timmial--iieeeeee reduction from the minimum hitting set problem to MCIP. resulting in stronger hardness results (3)
15

---

Co
x
Ca
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
Example 2. Consider graph G in Figure 5a Vertices x and z are mapped to x², ,,, and =), =1, =2, respectively, Both directed and a bidirected edge are drawn between these pairs. The bidirected edge (x x²) } is assigned the weight C(x) = C.s and the bidirected edge {2 .²²] is assigned the weight C(z) Cz. Infinite weights are assigned to the rest of the edges in H (Figure 5b).
Proposition A.1. Suppose G' is an ADMG, Y C ' is a set of its verlices such that Y is district in (\ and Ht' (g) Consider X C V Y as arbitrary subset of vertices of G', and define G = g'(ve' \ X]. Let Ey = {e E EN Eu E X, c T(()) and define E = =E \ Ey Let H be the edge-induced subgraph of defined as H (VH H F F. Q[V) is identifiable in 9 if and only if Q[Y) is identifiable in H.
Proof. We prove the contrapositive, i.e., Q is not identifiable in g iff Q is not identifiable in H. Note that by construction, Y is a district in both GDY] and H[Y). That is, it suffices to show that there exists hedge formed for Q[Y] in G iff there exists a hedge formed for Q[Y] in H.
To this end, we first prove the following claim. Let W E V form a hedge for Q[Y]. If W for some & E V then x² E W and vice versa. That is, the two vertices x and x2 corresponding to the same vertex x in V appear only simultaneously in any hedge. To see this, note that by construction, xt is the only child of 2 By definition of hedge, if x² E W, then it has directed path to Y within H[[]. and this path can only go through z². For the other direction, note that x' has only one bidirected edge, which with z² Again, by definition of hedge, if x W. then has a bidirected path to Y within H[W 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 = 2- Z UY, where Z1 { | E Z} and Z (=01z E Z}.
If part. Let W = Z U 2 Y form a hedge for Q[Y] in H. First note that since none of the bidirected edges between Z' and Z are removed H. by construction, all vertices Z are present in G. i.c., Z C Vs. Now we show that Z U forms a hedge for Q[Y] in G. To this end, we prove gIZUY] is a district and Z YY= = Anngizur First note that any vertex in Zt has only one bidirected edge to a vertex in Z That is, we consider the edge-induced subgraph of H[J over its bidirected edges, vertices of Zt are leaf nodes. As a result, Z² U Y must be connected in this graph. That is, 7 UYY is district in H|Z² U YJ. This implies by construction of H that G[Z U Y is single district. With similar reasoning, note that vertices in Z have parents. As result, z U = AnCH[zAuY](X (since the directed paths cannot go through 2²). Again, by construction, the edge-induced subgraph of G[Z UY over its directed edges is a copy of H(Z' UY]. As a result, ZUY = (Yc
Only if part. Let Z UUY Y form hedge for Q in G, where Z S V \ Y. Defin Z = (= Z) and = E Z). We show that z U 7 Y forms a hedge for Q in H. First, by definition of hedge, Ancg|zuy (Y) Z Y.Y. Since the edge-induced subgraph of H(Z U is copy of g U UY by construction, we know (Y) z Y. Further, each vertex z² E 2² is parent of 21 1 As result, Ancgrz
Z u 2 Now it suffices show that z U Z Y is a district in H[Z u UY. By definition of hedge, Z ZUYI is a district in G|Z UY). By construction of H. exactly the same bidirected edges (and therefore bidirected paths) exist in HIZz YY. Therefore, 72 U Y district in H|Z2 U Y). Now note that by construction of H', each vertex 21 Z has a bidirected edge to 22 E Z². And by definition of G and H. since the
16

---

vertices Z exist in G. none of these edges are removed in H. As a result, Z' U Z Y is a district in H|z' U 2 UY. which completes the proof.
Proof of Theorem 3.3 A polynomial-timm time reduction from MCIP to the edge ID problem follows immediately from Proposition A.1 MCIP shown be NP-complete [2]. As a result, the edge ID problem is Np-complete.
A.2 Reduction from edge ID to MCIP
Proposition 4.2. There exists a polynomial-tine reduction from edge ID to MCIP and vice versa.
To prove Proposition 4.2 we begin with presenting transformation T2(9, Y) which is in the core of reduction from edge ID to MCIP.
Suppose we want to solve the edge ID problem given ADMG (VS, _. E.g) ) query Q[Y), and edge weights Wg = {wele g). Let X V Y denote the of vertices of g excluding Y. We define the transformation (H. Ymcii) = (2 Y) where H = (V*, EY E ) is an ADMG and ymcip C VH as follows. Note that VH will consist of two disjoint set of vertices, namely Viz and VH. bot i.e., VR = ViLp U V.H
a. Begin with V top Vot = 0, Ymcsi = 0. For any vertex v E V9, add vertex e to V. with cost C(v) = 0o. If U E Y, add to ymeip.
top
b. For any directed edge (e,, Eg with weight wgJ in G, add a new vertex og to top with cost C(e way where
if Us Uj E X, i E Y or vy EY, if both u. Uj E
Draw directed edges (u,, og)) and (ug), vy). Further, draw bidirected edge between es and vny
c. For any bidirected edge {xx, x2 E Eg with weight w add a new vertex, s/ to Vi with cost Oaziy) = w Add two bidirected edges {a,, aby} and {zz, e/j). Further, draw two directed edges (zly. 2.) and (xl). xz) in H.
d. For any bidirected edge (a,, yÿ} with weight w.y. add new vertex zi to top with cost C(=ly) w Draw bidirected edges (=)) and { vi}. Then draw directed edge from z'j to zi.
For any bidirected edge between (1i, Vj} E F.g with weight w in G, add new vertex, vi to VH, with cost C(v w Draw bidirected edges (vig 34 and (v/ vz}. Further, for any x E X, draw directed edge from vii to
f. Let y1 < ... yk denote a topological ordering among vertices of Y. For every pair (yr, My} of vertices of Y, where < j. add vertices vi .........,, to Vi Add v to ymaii, Draw the directed edges (y), 2 for every k j. Draw the directed edges (vkd yy for every i < < j, and the directed edge (ul² ",,). Draw a bidirected edge between yy and v. Further, for any bidirected edge {Mk, 313 E Eg where i < k, I < j. add new vertex l Voa draw two bidirected edges {ull vi and (y 11. and a directed edge (yl v,,). The costs the all of the vertices in bot are infinite.
With abuse of notation, for any bidirected edge et (vi, vz} E F.g and any directed edge etf (v,, vy) E Eq. we define T2(e?; = o and Ta (e = uh respectively, where ui of E v are the vertices representing their corresponding edges.
We will utilize the following results to prove Proposition used to prove Proposition A.10 which in turn is used to prove Proposition 4.2
More precisely, Lemmas through
17

---

Lemma A.2. Suppose G is an ADMG, Y is a set of its vertices, and (H,Y Y = =TG,YY Y). Each vertex y Ymesp is a district in H.
Proof. It suffices to show that for every pair of v1, U2 Ymcip there is no bidirected edge between them in H. Suppose first that 11 2/2 E Y. Any bidirected edge between and 22 in G (if it exists) removed in step (e) of the transformation, and none of the steps (a) through (f) add a bidirected edge between them. Otherwise, at least one of v1, 12, w.l.o.g. U1, is in Y Y. Suppose w.l.o.g. that y From step (f) of the transformation T, we know that 01 has bidirected edges only to is vertices Vkj where none of them is a member of Ymcip.
Lemma A.3. Suppose G is an ADMG, Y is set of its vertices, and (H.Y m Suppose there is hedge formed for Qlyi 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 V.H. 0.
(2 Y).
Proof. Define V1 = {v bot Vi,j, k. 1), and V/2 = V \ V1. By construction of H. the vertices of V/2 have directed edges only to vertices in V22 Therefore, for each vertex v E V2, we have AnC (y). As result, 1/2 n H = 0, since by definition of hedge, any vertex of H is an ancestor of y in H[H)]. Now, consider an arbitrary vertex E V1. By construction of H. if there exists a bidirected edge { } E E we must have that v' E V2. Therefore, if v E H, there must be at least one vertex v' E V22 D H. Since we proved V2 n H = 0, cannot be in H. Consequently, V1 n 0.
Lemma A.4. Suppose G is an ADMG, Y is set its its vertices, and (H, Y - Suppose there is hedge formed for Q Q'y)²1 in H. where yı. Mj E Y and vJ is the vertex corresponding the pair (yt, yj) added in step (f) of the transform T. Let H denote the set of vertices of this hedge. If u E H.H. n V then v has the superscript ij, that is, v is either one of the vertices u or one of the vertices Ver where i S k S.
j. In the latter case, Vha E H.
Proof. Define V1 = (yKi"
mn E bot: Vm, n, 1) and V/2 = Vi Vi. Suppose V/¹ = (ofl E
VR. Vk, (} and Vi2 = {uk E VR VkJ. Also define V' = V1 \ Vr. V. V/2 Vg. For the first part of the claim, suffices to show that Vi H = 0, V2 n H = 0. By construction of H, the vertices of V2 do not have any child out of V2- Therefore, V/d (ACH[H]] (u))) 6. This implies that
V22 n H 6. Now let of be an arbitrary vertex in Vi. By construction of H. of has bidirected edges only to vertices of Vz. This implies that if of E H, there must be at least one vertex of V in H which is in contradiction with Vi2 n H = 0. Therefore, of & H. Since of is an arbitrary vertex in VL. we conclude Ví 0 H 0.
Now, we prove that if v E H is one of the vertices Vig we have uya H. Since v E H., there exists a directed path from 4 to v2" in H(H). Since s is the only child of ykr the aforementioned path passes through v Therefore, via H.
Lemma A.5. Suppose G = (V8', Ey EES is an ADMG, Y S V is a set of its vertices, and (H', ymcip) = T(g', Y). Let Ea C EG and F C Eğ be arbitrary edges of G, and define Eg Eg" \ Ey E = Eg" EN Define = -V9, E Eg) and H = H' \ V'I, where V = VS' and V = {u E VH E" U E u Tz(e)}. Suppose there is hedge formed for Qlu3'1 in H. for some i.j. Let H denote the set of vertices of this hedge in H. The set of vertices Y= = (yllvg E H} is district in G\Y}. Moreover, Htop AnentHong (Y*), where Heop = H n V
18

---

Proof. First we prove that Y is a district in G Consider an arbitrary vertex yE in H. By definition of hedge, there exists bidirected path, P1, between v/²² and vy in H[H) Let Y denotes the set of vertices in H such that their superscript is ij. Lemma A.4 implies that H S Viop UY Furthermore, by construction of H. there is only one bidirected edge between Y and H \, Y which is {ug, vt }. Therefore, all of the vertices on the path P1 are in Y Now, we define Y = {ux ui E p1) and Y = Iu ij E p1). i.e., the Vi counterparts of the vertices in P1- Since the vertices on P1 are in H, Y/ S Y*. From Lemma A.4 we know that if yid E H. then, 2 H. implies that Y S H. As a result, V and V are both vertices of H. Now if we replace all the vertices in pi with their corresponding counterpart in Y U Y2, we arrive a bidirected path P2 between y/ and yj in M|YY U Y3] (as by construction the same edges exist in V ). By definition of G and H. if vertex u exists in H. the corresponding edge (yk: 31 exists in g. As a result, a bidirected path between yk and y exists in G ([Y]]. Noting that yh 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 y in G[Y"), which completes the proof.
topp).
Next, we prove that Heop - AnCH[Htenp To this end, it suffices to show that there is directed path form an arbitrary vertex v E Htop to Y in H[[Htop). Since H forms a hedge for Q(y in H. there exists directed path from to yy² in H[H)] This path must go through the only parent of v/. which is y 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 to yt. where y Y and it has no ancestors in H \ Hrop- Otherwise, let this parent be / for some i < & < j. Now the last vertex on the path before y must be yks which is the only parent of ij Note that by definition of Y*, yk E Y Therefore, v has directed path to Y in H(ppp)
Lemma A.6. Suppose G = (VS, E2 ET) ) is an ADMG, Y is a set of its vertices, and (H. Ymmip)- = T2(9, Y). Suppose there is hedge formed for Qlyi in H. for some y E Ymcip, Let H denote the set of vertices of this hedge. Then H i X + 0, where X = v9 Y.
Proof. Since H forms hedge for Qly) in H. there exists vertex h E H such that {y, h3 E E.H.
There are two possibilities for E ymesp:
y = yi Y. From Lemma A.4 we have h & V.H. Therefore, by construction of H. h n²y for some j.
y = " path to in H by definition of hedge, which must go through the only child of h, i.e., via.
E VH. By construction of H. 2 for some Vertex h must have a directed bot-
In both cases, we showed that there exists vertex = vlyy H for some j. By definition of hedge, there is a bidirected path, p. from e to y in H because Ancw(y). Since all of the children of u are in X, there at least one vertex in X on path p. Therefore, H includes at least one vertex of X.
Lemma A.7. [Inverse transform preserves hedges.] Suppose G' = =VV"', ,Ey Egy is an ADMG, Y C CV' is a set of its vertices, and (Hl, y = T2(S", .Y). Let End C Eÿ' and E C Egg be arbitrury edges of G, and define FG = E Eyg Eg E.g Eg. Define G = (V9, EG. Eg) and H =H'(V' \ V'',, where v = Vo and V {u E VH' Be E EN, E v Ta(e)). Ler
W C V.H. be set of vertices of H. Let W, C W n 6 be a subset of W such that W. are vertices of G as well. Consider the inverse transform of H[W) in the ADMG G, i.e., for any v = of E W, delete v and all edges incident to it and draw bidirected edge between is and Uj. and for any ofy delete e and all edges incident it and draw directed edge from is to ey. Let the resulting subgraph (which is a subgraph of G) be denoted by GWW-1] with the set of vertices W-1 C VV. If Anchww (W.)- = W. then Ancqw-1 = W-! Moreover, if W is district in H(W), then W-1 is a district in G|W
top
19

---

Proof. First, we show that if Anenww (W.) = W, then Ancow--; = w-1 Let v be an arbitrary vertex in W-1, Vertex is in W because W-1 S W. Since E W and Ane has a directed path v - ... + of V.... .... + w, denoted by I, to vertex w W, in H[W]. For each vertex vit on path I, we have Us, Uj E -[ and since oi E V*, by definition of g and H. there exists Uz) E Ey s.t. i < j. and consequently, (ei, 23) E E-i'''! Therefore, there exists directed path from v to w in G[W- Noting that e is an arbitrary vertex in W-1, we conclude that Ancggw-r((W.)- W-1
Now, prove that if W is district in H[W], then W-1 is district in g[W-']. Consider two vertices U1 2/2 E W- Since U, U/ E W and W is a district, there exists a bidirected path 2n ++ ... ++ uis ++ U/- ... ++ 02 denoted by p. between vi and U2 in H[W). Each vertex vf on path p is in H and U4 By E G[W-']. By definition of g and H. we have {er, 2/y } E Egg. Therefore, {us, my} E E E Then, there is a bidirected path between i1 and 222 in gW- ']. Since in and 222 are two arbitrary vertices in W-1 it implies that W-1 I is a district in g(W
Lemma A.8. [Transform preserves hedges.) Suppose G' (V9", Ey. Eg is an ADMG, Y C V is a set of its vertices, and (H'', Ymcip) = '2(('', Y). Let En S Ey and Ey S Eg be arbitrary edges of g. and define F F F" Fg = Egg En.. Define 9 -VS, Eq, Eg) and H = =H'IV"' \ V"J, where 69 = V and V' = (u E VR'Be E Eg U E.E = Ta(e)). Let W VV be a set of vertices of 9 such that W W\Y # D. Let W. S W be subset W. Let the transformed graph of g[W] under To be denoted by H", where H. S H. Define W VH² If Ancgww (W.) = W, then AncH(--(WW.) = W Moreover, if is a district in G[W], then W* is a district in HW*)
W.
Proof. First, we prove that if Ancg w/ (W&) W, then AncHgw-(WW)) W*. Take an arbitrary vertex e E W*. There are two possibilities for e:
U E W. That is, vertex v is in G[W].
V & W. This implies that v represents an edge between two vertices Us and vj in G[W]. There are three possibilities for e:
- -== Uy). By construction of H. v is parent of ny in H(W)), where uy is a vertex of G[W].
e = {er, }5} and n E x uy E X. In this case, e is parent of at least one of ny and
oy in H[W"), w.l.o.g. Us where iy a vertex of G[W].
{ve, 03} and Uy Y. By construction of H. v is parent of all vertices in V \Y. Since W \ Y o 0, there exists a vertex x in g[W] such that v is a parent of x.
In all three cases above, we proved that there exists a vertex & E W such that is parent x.
Therefore, we showed that any vertex U E W either is itself a vertex in W or is a parent of a vertex in W. As result, it suffices to show that every w W has directed path to W. in H(W*). We know that w has a directed path to W. in g[] such as p. Take an arbitrary pair of consecutive vertices on this path, such on and U2. The directed edge (0), 12) exists in G[W]. As a result, the directed path U1 + ef2 + U2 exists in H H[W'). Starting and repeating this argument for every pair of consecutive vertices on p. we conclude that there exists a directed path from w to Wa, which completes the proof.
Now, we show that if W is a district in G[W], then W is a district in H[W"]. Take an arbitrary vertex v E W*, There are two possibilities for a:
E W. That is, is vertex in G[W].
20

---

V & W. In this case, at least one of the vertices represents an edge e between two vertices 1 and v in G[]]. . By construction of H. is connected to at least one of v; or Uj. w.l.o.g. U/, by a bidirected edge, where Uj E W.
We showed that any vertex E W either is in W. or is connected 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 W1 and W2 in H[W*]. Since W1, W2 E W. there is a bidirected path, p. between wi and w2 in G[W]] Take an arbitrary pair of consecutive vertices on this path, such on and U2 The bidirected edge {u1, 22) exists in g[W]. As result, the bidirected path ++ vîz ++ 02 exists in H ". Starting at and repeating this argument for every pair of consecutive vertices on we conclude that there exists a bidirected path from wi to W2, which completes the proof. O
Lemma A.9. Suppose G is an ADMG, and Y is subset of its vertices. Also let Y be district in G[Y]. If the set of vertices H form a hedge for Q[Y²), then H Y + D.
Proof. Assume by contradiction H HYY Y 0, i... H HCY. By definition of hedge, we know H \ Y * D. Take an arbitrary vertex U E H \.. Furthermore, e E Y Y because H C Y. Since H forms a hedge for Q(Y*), H is district in G[H]. Therefore, there exists bidirected path between v and a vertex y" E Y in Q[Y] which is in contradiction with the assumption that Y is a district in g.).
Proposition A.10. Suppose G' (VS' .Eg') is an ADMG, Y S V is a set of its vertices, and (H'' y T2(g', YY. Let Enj S Eÿ and EY S CE, be arbitrary edges of G, and define Eg = =9 \ E% Eg = Eg" VE Q[Y) identifiable in G- (VS, Eg Egg) and only if q[ymmipj is identifiable in H = H'V"" \V",, where V = =V and V = {o E V Be E En U E 8 T-
Proof. We prove the contrapositive, i.e., Q[Y] is not identifiable in G iff Q[ymcip] is not identifiable in H.
part. Suppose Q[ymcip] is not identifiable in H. That is, there exists a hedge formed for Q[Ymcip)
in H. From Lemma A.2, this hedge is formed for Q[y'] for some y' E ymmip, Denote the set of vertices of this hedge by H. We consider two possibilities separately:
5/ - yi, where y/ E Y. From Lemma A.3 H C V.H. Taking W H in Lemma A.7 W-1 is a set of vertices in 9 such that Aneggw- (v) = W-1, and W-1 is district in G. Now take Y* to be the district of G[Y] that includes y;- By definition of hedge, GlW-lu Y forms hedge for Q[Y*] in G. Note that from Lemma A.6 W-1 \ Y + 0. As a result, Q[Y] is not identifiable in g.
y/ = vJ where Vi, Mj E Y and y' is one of the vertices added H in the last step of the transformation T (step (f)). Define the set Y = {fuelu H). From Lemma A.5 Y is district in G, and therefore a district in G[Y]. As result, it suffices to show that there exists a hedge formed for Q in G. Now define Htop = H n Vi2 By definition of hedge, H is district in H(H). i.e., it is 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
the bidirected edge between Yj and y Therefore, this edge is a cut set that partitions the graph H H(H) into two connected components H H(H2op) and H \ Htop) That is, H(ptop) is connected over its bidirected edges and therefore Hrop is a district in H( Further, Hzop = AnCH H.ool (Y*). Noting that Hoop C top- taking W = HtOP in is a district in G and Ay)" W-1 Note that from Lemma A.6 W Y * 0. Therefore, the set of vertices W-1 form hedge for Q[Y** in G. Hence, Q is not identifiable in G.
from Lemma A.5
Lemma A.7
W
Only is part. Suppose Q[Y] is not identifiable in G. It implies that there exists a district of G such as x such that there is a hedge formed for Q[Y*] G. Let H denote the set vertices of this hedge. From Lemma A.9. H Y * 0. Define W* as in Lemma A.8 that is the transform [G]H),YY)
21

---

without step (f) (only on the vertices of Vinp). Note that Y S W. We consider the following two cases separately:
Y* (v). that is, Y* is single vertex. From Lemma A.8 W is a district in H(W)), and Anchww (v) = W By definition of hedge, the vertices W form hedge for Q in H. Note that y E Ymcip, and from Lemma A.2 it a district of H[Ymeip)) As a result, Q[ymcip) is not identifiable in H.
Y 2 Let yi and Vj be the first and the last vertices of Y in the topological order. Define y = =vv Wv E EY") U luke E YY). y are the vertices in V with superscript ij corresponding to the vertices in Yr. Note that y/ uj E yU** since y/s By Y*. Since " 2) E yymcip and from Lemma A.2 vj is district in H(Ymeip) it suffices to show that there a hedge formed for vj in H. We show that the vertices W = W Y form a -W,, that is, all of the vertices in W are ancestors of Y* in H( and therefore in H[W]. Also, the vertices v in Y have direct edge their corresponding vertex in W i.e., yhe and therefore ancestors of Y in HW] as well. Further, each vertex in Y* such as ya is a parent of / which is in turn a parent of y (or is y," itself if k: = i.) Finally, y has a directed edge to Uy by construction. As result, all of the vertices W have direct path to 2 in H[W]. That is, AncHIw] (u)") = W. It now remains to show that W is district in H[W From Lemma A.8 W is a district in [["' As a result, the vertices W are connected through bidirected edges in H.W] There is bidirected edge between yy and v by construction of H. It suffices to show that for any E Y there exists a bidirected path between v and ij
hedge for v H. From Lemma A.8 AneH[w-)(Y")
8 y/ in H[W]. A vertex Vil E y (with double subscript, which are due to the bidirected edges among Y*) has bidirected edges to v and u²², which are both in y by definition. Now take an arbitrary vertex 3/ E Y (with single subscript, due to vertices in Y*). We i3 know DA E Y as 1/3 E Y by definition of i Y is a district in G[Y That is, there exists bidirected path from yk to y: in g[Y"). From Lemma AemmalA.8) by taking W Y*, there is a bidirected path from to in H|Y* U {M ym E EYH.. By construction of H. if we replace each vertex & on p by vJ, we achieve a bidirected path p' with vertices in y from ye to v." which completes the proof.
Proof of Proposition 4.2
The reduction from the edge ID problem to MCIP shown through the The opposite direction is an immediate corollary of Proposition A. O
proof of Proposition A. 10
Corollary A.11. The edge ID problem and MCIP are equivalent.
B Maximal hedge
Herein, we present the algorithm for recovering the maximal hedge formed for Q[Y] in given ADMG G (see Definition 2.5). Maximal hedge was initially defined in 22 under the name hedge hull. We adopt the same definition, and when G[Y] comprises several districts, we define the maximal hedge the union of the hedge hulls formed for each district of G As result, the complete procedure of recovering the maximal hedge for query Q\Y], summarized in Algorithm finds the maximal hedge formed for each district Y, of G[Y] and returns the union of them. This procedure used as subroutine MH in Algorithm The function HHull is in fact Algorithm borrowed from (] This function is proven to recover the union of all hedges formed for Y,, where Y, one of the districts of G[] (see Lemma 6 of (2).
22

---

Algorithm 3 Maximal Hedge.
1: function MH(G, Y)
2: Initialize M <- 0
3: for Y; in districts of G|Y] do
4: M M (H,
5: return G[M)
1: function HHULL(G,) YD
2: Initialize < V/
3: while True do
4:
C f- connected component (district) of Y, via bidirected edges in H
5:
A ancestors of Y, in G[C]
6:
C * A then
7:
H A
8:
else
9:
break
10:
return !!
Figure 6: An example where the expert is aware that there is no causal path from to y/ e.g., because 2 IL y with high confidence.
C Towards generalizing Assumption 2.1
Lemma 3.2 states the equivalence of Problems and with the edge ID problem under Assumption 2.1 However, as mentioned the main text, this equivalence holds the more general setting where allow for perfect negative correlations among edges. As example, consider the graph of Figure Suppose that the performed statistical independence tests show that the two variables z and y are independent of each other with high confidence. As a result, the expert believes that the edges (=, and (z. y) must not exist simultancously, as otherwise the causal path from 2 to y would make them dependent. In such cases, the belief of the expert can be modeled probabilities and assigned to the existence of the edges (z, z) and (z, y). respectively, as well as perfect negative correlation between them.
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 and 3 We show that with the specification of such negative correlations, Problems Tand caa still be cast an instance of the edge ID problem. Therefore, the results presented in this work are valid this setting as well.
Assumption C.I. The edges in G are assigned probabilities Pe, Ve E G, and perfect negative correlations are defined among subsets edges. More precisely, for any subset E S Eg Eg 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).
Proposition C.1. Under Assumption C.7 there exists reduction from Problems 7 Aand 2 to the edge ID problem and vice versa with the time complexity in the order of O((CI- C' is the set of perfect correlation constraints.
V + E )), where
Proof. First note that proved the equivalence of Problems and with the edge ID problem without the perfect correlation constraints in Lemma 3.2 As result, under assumption C.I i.e., by adding the perfect correlation constraints, Problems and [ are equivalent to a modified edge ID problem with those constraints. But we claim that there exists and instance of the original unconstrained edge ID problem which equivalent these problems. know from Corollary A1 that the edge ID problem is equivalent to MCIP. Therefore, it suffices to show that there exists an instance of MCIP which is equivalent to the constrained edge mentioned above. To this end, consider the transform (g Y) introduced in Section A.2 This transformation
see this, first note that we
23

---

21
2/2
2/3
21
2/2
3/3
9
Figure 7: Integrating the perfect negative correlation constraint into MCIP
maps instance of the edge ID problem an instance of MCIP. Applying this transformation the constrained edge ID problem, we can map the constrained edge ID to an instance of MCIP with extra constraints, with transforming the constraints as well. That is, if for instance, there is a perfect negative correlation among the edges E e2 in G. this constraint is mapped to a negative perfect correlation on the corresponding vertices in H. namely Tæ(e1), (e2)). In words, this constraint would be that at least one of (2()1) and T2(e2) must be intervened upon. We show that such constraints can be integrated into the original definition of MCIP.
Suppose we have an MCIP problem in ADMG 9 with query Q[Y], with the extra constraint that at least of the vertices X C V must be intervened upon. Consider the example of X {21, F2, [33 in Figure 7 We build a new ADMG G' by adding vertices (a' la E X). i.e., a new vertex corresponding to each vertex in X, along with auxiliary vertex ÿ G. We fix random ordering over the vertices of X, and denote the set of vertices of X as æ1, Im. We add the directed edges (Ii, x4) to G', as well as the bidirected edges {ız, a Further, we draw directed edges (a/) x141) for every 1 S i < m. Finally,
draw the directed edge (I'/m 9) and the bidirected edge {#1, 8). Refer to the graph in Figure for an example with X = {I1, I2, I3 ). Note that the set X KUX' U {0} forms hedge for Q(ū), where X' {a/ [ar E X) Now it suffices to set the cost of intervention on vertices of X' to infinity, and consider MCIP for the query Q U {0} in G'. It is straightforward to see that the objective of this problem would be find the minimum cost intervention for identification of Q[Y], 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.ū.. 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 G. The number of vertices (and therefore the time complexity) is at most in the order O(IC) [V')), where C' is the set of constraints
C.1 Further applications
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.
Let us assume we run our algorithm which returns the subgraph with the highest probability, Gi- However, the probability that G1 is the true causal structure describing the system might be too low. In such 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 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 recover such a ranking (of the most probable graphs in which query is identifiable). To see this, note that based on what we proposed in this Appendix, perfect negative correlation constraints can be added to the edge ID problem without additional computational cost. So we begin by solving the original problem, which yields a graph G1. We then solve 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., we force the algorithm to exclude at least one of the edges of G1.) The solution to this problem (let us call it G2) is the highest probability graph among all subgraphs except G1. i.c., it is the second highest
24

---

probability graph in which the query is identifiable. Continuing in this manner, running the algorithm times would give us ranking of the n highest probability graphs.
D Heuristic algorithms
Algorithm 2
was devised considering the fact that every hedge formed for Q[Y] must include a vertex that has bidirected edge to Y. As mentioned in Section 4.2 analogous approach, summarized in Algorithm uses the fact that any hedge formed for Q must include parent of Y.
Let Y S v be set of vertices of G such that G[Y] comprises of only one district. Let 2 := {2 E 3 E Y: (z. E ) Y denote the set of vertices that have at least one directed edge to 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]. suffices to ensure that none of the vertices 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. The problem of eliminating all bidirected paths from 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 z" to the graph and draw bidirected edge between 2' and every Z with weight w Eyey ((zzy)) 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 zt and Y. If an edge between x" and E Z is in the solution this min-cut problem, it translates removing all the directed edges from
vertex Y, i.e., the parents Y excluding
Y can be cast as a minimum cut problem
z to in the original problem. Note that we can run the algorithm on the maximal hedge formed for Q in rather than G itself.
Algorithm 4 Heuristic algorithm 2.
1: function HEID2(G, Y, Wg)
2:
g' < MH(G. (gG Y)
3:
Z x- (= E Fy E Y (z,y) F YY
4:
H < The induced subgraph of G' on its bidirected edges.
5:
WH {we Wolee H}
6:
VH + VH U
7:
for E Z do
8:
E t U {2",2]
9:
WH WH U {W((+))) Ey ((2s)}
10:
for E Y do
11:
E + E U {y,y²} WH WH U (w(v) Fc} E + MinCul WH, ",,,",,"*
12:
13:
return (E, E.Eg We)
E
Experiments
Noting that the synthetic/simulation results in the main paper were for graphs with log(n)/ / sparsity constraint, we begin this section by providing 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 2 formulation in Section
results the simulated graphs without the
E.1
Additional simulation results without sparsity constraint
The simulation results for graphs generated without the sparsity constraint are shown in Figure 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
25

---

16
200
150
Tinee (aamba
HEID-2
HEID-1
MCIP-HI
10
100
MCIP-
MCIP
10
MCTP-312
cuac
-00
EDGUD
30
130
250
lopeligiical
tepelogical
(a) Runtimes.
(b) Solution costs.
MCTP-csact
EDGEID
100
150
200
250
Nambher of vottice betinn Y in 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.
minute runtime limit only 20 nodes, and the MCIP heuristic variants (MCIP-HL 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.
E.2 Psychology graph discovery
The settings for deriving the putative structure used on the psychology real-world graph provided in T
Table 3: Hyperparameter settings for the Structural Agnostic Model used to generate the putative (directed) structure for the 'Psych' real-world dataset.
Parameter
Value
Leariigg Rate
0.01
DAG Penalty
True
DAG Penalty Weight
0.05
Number Runs
50
Train Epochs
3000
Test Epochs
800
Mixed Data
True
hlayers
dhlayers
lambdal
10
lambda2
0.001
dir
0.001
linear
False
nh
20
dah
200
26

---

10240
1201311
HEID-1
0.055
BEID-2
HEID-2
EDGGID
18.15
0.010
20
(a) Runtimes.
(b) Solution costs.
IDGED
2003
12:3
2000
255
(c) 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 in color.
E.3 Simulation results for Problem 2 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 Lemma 3.2 That is, map each probability pe to the weight log(1 - pp)) in the corresponding edge ID problem.
The simulation results are presented in Figure 9 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. Pa 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. The costs for each graph are shown Fig. 96 Figure Pe 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, having a short runtime, and achieving close to optimal cost.
27


Reviews:
[{"review_id": "5cLlYhYjMs", "reviewer": "Reviewer_eheu", "summary": "The authors consider the problem of causal effect identification assuming the given causal graph G is probabilistic where each edge (directed or bi-directed) is associated with a measure of confidence. Under this setting, the objective is to identify a subgraph of G with the highest plausibility such that the target causal effect Q[Y] is identifiable. The authors propose an exact algorithm that is asymptotically exponential, two heuristic approaches, and a reduction to an NP-hard problem that has approximation algorithms. Finally, they evaluate the proposed methods on synthetic and real-world graphs.", "questions": "1- \"when $w^{th} = 0$, Algorithm 1 will output the optimal solution\": Suppose we have G={Z -> X, X -> Y, X <--> Z, Z <--> Y}, $W_G$={$\\infty, \\infty, 10, 1$}, $w^{ub}=\\infty$, and $w^{th}=0$. Running this example does not lead to any solution unless I'm mistaken. It should optimally return the subgraph after removing the bi-directed between Z and Y. Unless you mean that whenever $w^{th} = 0$, then an alternative formulation of Algorithm 1 is run which discards the threshold and simply searchers for the optimal solution.\n\n2- Implication of Remark 2.1: Can you elaborate on the need for this assumption to only consider Q[Y] instead of general causal queries? Is it a necessary assumption for the problem to be defined or are general queries more challenging?\n\n3- Typos:\n  + Line 68: period after \"and open problem\"\n  + Line 224: (Line 12) --> (Line 13)", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The formulated problem of identifying the most plausible subgraph where a target effect is identifiable is algorithmically interesting and the author highlight its complexity by showing it to be NP-hard. Moreover, the paper is well-written, for the most, with examples and discussions to illustrate the problem (i.e., Section 2.1). The experimental evaluation of the heuristic algorithms shows favourable performance.", "weaknesses": "1- Motivation for the problem: Whenever the target causal effect is not identifiable in the full graph G, it is not justifiable why we would drop edges from G just to make the effect identifiable; an alternative to exact identification could be bounding the target effect. The authors can provide more motivation in the introduction to justify their approach.\n\n2- Lack of performance guarantees for the heuristic approaches: There is no theoretical analysis for the heuristic algorithms discussed in Section 4.2 in terms of upper bound on the cost.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the constructive feedback of the reviewer. We will address the concerns raised in the weaknesses and questions section.\n\n-----------------------------------------\n**- Motivation & bounding the effect:** \n\nWe agree that in some cases, relying on partial identification and bounding the target causal effect can be more justifiable than striving for exact identification.\nHowever, we aim at highlighting the importance of taking the uncertainty in the structure into account in the context of causal identification.\nIt is noteworthy that even in the context of partial identification, nontrivial bounds can only be achieved if at least some pairs of variables are assumed to be unconfounded. \nIn particular, if every bidirected edge in our model has a positive probability, even partial identification would become subject to this probabilistic model, which is a nice generalization of our problem. \nWe thank the reviewer for their suggestion and we will mention this direction in the revision as well.\n\n**- Performance guarantees for the heuristic approaches**: \n\nWe acknowledge the lack of theoretical analysis for the heuristic algorithms discussed in Section 4.2. In average-case scenarios, the cost of the heuristic algorithms  can be bound in terms of the optimal cost and the parameter $p$ in a straightforward manner, which we will include in the revision.\nOn the other hand, since both of these algorithms are polynomial-time, it is natural to expect their 'worst-case' performance to be at best log(n) times worse than that of the optimal solution. This can be justified based on [1] below. We will elaborate further in the revision.\n\n[1] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4): 634–652, 1998.\n\n-----------------------------------------\n**Questions**\n\n>1- \"when \n$\\omega^{th}=0$, Algorithm 1 will output the optimal solution\": Suppose we have $G=\\\\{Z -> X, X -> Y, X <--> Z, Z <--> Y\\\\}, W_G=\\\\{\n\\infty,\\infty,10,1\\\\}$, $w^{ub}=\\infty$ and $w^{th}=0$. Running this example does not lead to any solution [...].\n\nRunning Algorithm 1 on the instance with the provided graph G and the given weights will return the optimal solution as follows: \n\nAt the first iteration, the link between $Z$ and $Y$ is removed, which yields the optimal solution with cost 1, and this is stored as E_min. But since there could possibly be solutions with lower cost, the algorithm does not terminate here. Instead, this link is returned to the graph, but with infinite cost this time (see line 14.) The next iteration finds the solution of removing the link between Z and X, but since it is not optimal, it is disregarded and this link is also updated to have infinite cost. Now the graph has 4 edges with infinite cost, and it returns the stored E_min at line 7 of the algorithm.\n\n>2-Implication of Remark 2.1: Can you elaborate on the need for this assumption to only consider Q[Y] instead of general causal queries? Is it a necessary assumption for the problem to be defined or are general queries more challenging?\n\nThe assumption of considering Q[Y] in Remark 2.1 is not a necessary constraint for defining the problem. We appreciate the reviewer's observation, and indeed, the problem can be posed in a more general form without restricting the queries to Q[Y]. The general formulation of the problem would complicate the analysis, potentially invalidating our specific reduction to EdgeID, but the NP-hardness and corollary 3.5 would remain intact. We will clarify this in the revision.\n\n>3- Typos:\n\nWe thank the reviewer for pointing out the typos. We will  correct them in the revised version of the paper.\n"}, {"review_id": "LMnAG2zYhw", "reviewer": "Reviewer_aizw", "summary": "The paper studies the problem of causal identification in a setting which the structure of a causal graph (of interest) is probabilistically uncertain i.e., only known per a certain degree of belief or with a degree of confidence of a particular statistical set, asking the most likely subgraph in which causal effect identifiable. In doing so, paper reduces it the combinatorial optimisation problem i.e., edge ID (as they call it) whose computational complexity is shown to be NP-hard through a reduction from minimum-vertex cover problem. Authors also introduce exact and approximate algorithm and show empirically that the algorithms work good as well. ", "questions": "-how about NP-completeness case?\n-Can the work of Eiter Lukasiewicz 2001 be any useful/connect for further results in your setting?", "limitations": "I did not see any particular limitation. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Deep theoretical paper.\n\n- The theoretical results  are complemented with good empirical evaluation. \n\n - Good exposition. ", "weaknesses": "I did not spot any major weakness. Only very few minor issues:\n\n- causal query better be formally mentioned in *the introduction* (i.e., how does it look like formally)\n-problem To be surmountable (missing dot)\n-In Figure 1 caption, also mention the longer version of Q[y] to help following it. \n-Definition 2.2: explain what you mean when you say functional (again formally). \n- (potential typo): In Example 1, I sense the direction of the subset to be other way around  Gˆ⊆G1\n-Assumption 2.1: form (1) -> Equation 1\n-In the next [s]ection", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and valuable feedback. We also thank the reviewer for pointing out typos and minor issues.\n\n**Questions**\n>how about NP-completeness case? -Can the work of Eiter Lukasiewicz 2001 be any useful/connect for further results in your setting?\n\nThe EdgeID problem is indeed 'NP-complete', since the ID algorithm of [1] can be used to validate an answer to EdgeID within polynomial time. We thank the reviewer for raising this question and we will include it in the revision.\n\n[1] Shpitser, Ilya, and Judea Pearl. \"Identification of joint interventional distributions in recursive semi-Markovian causal models.\" Proceedings of the National Conference on Artificial Intelligence. Vol. 21. No. 2. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2006."}, {"review_id": "z3QSVEn12U", "reviewer": "Reviewer_NvDh", "summary": "The paper considers a setting in which we have a probabililty distribution over causal graphs. This paper considers the problem of finding the most probable subgraph in which a given query is identified, and then that subgraph with the highest sum of probabilities of its own subgraphs in which the query is identified. (The latter problem is significant since the result of the identification must agree among all these subgraphs.) A reduction is given to a known NP-hard problem for which various algorithms are evaluated empirically.", "questions": "- Can the authors point to any other literature besides citation [12] in which probability distributions over ADMGs are considered? Or provide motivating examples perhaps involving statistical tests in structure learning.\n- Line 47: \"to addresses\" -> \"to address\"", "limitations": "Yes, they have (for instance, the assumption of independence between edges).", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and the results are clearly set out, extensive, and correct as far as I can tell.", "weaknesses": "I had a little bit of difficulty understanding the problem initially. I am currently a little dubious about the paper's ultimate significance, but if the authors can make the links to structure learning more explicit then it will represent an interesting synthesis with the other approach in which ADMG encapsulates \"a priori\" facts about the causal structure that are known for certain.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable input. We are delighted that the reviewer has found our results clear, extensive, and sound. We address the main points and questions below.\n\n---\n>Can the authors point to any other literature besides citation [12] in which probability distributions over ADMGs are considered? Or provide motivating examples perhaps involving statistical tests in structure learning.\n\nOne compelling reference to consider is [1], where the authors use concepts of monotone triangular transport maps to define a score for the conditional independence of variables. In particular, these scores are interpreted as indicators of whether an edge is a 'strong' or 'weak' edge\nMoreover, it is noteworthy that a considerable fraction of causal discovery algorithms relies on statistical tests, which inherently introduce uncertainty. These statistical approaches often involve hypothesis testing to assess the conditional independence of variables, which inherently involves probability distributions over graphs.\nWe believe that this fact has been simply overlooked in the literature because it complicates the identification process and analysis.\n\n[1] Learning non-Gaussian graphical models via Hessian scores and triangular transport. R. Baptista, Y. Marzouk, R. E. Morrison, O. Zahm. \n\n---\n>Line 47: \"to addresses\" -> \"to address\"\n\nWe thank the reviewer for pointing out this typo and other minor comments."}, {"review_id": "87tUMukTAv", "reviewer": "Reviewer_DoFR", "summary": "This paper is about causal identification in a setup where the assumption of reliable knowledge of the causal graph is relaxed. The authors assign a probabilistic weight to the possible confounders.  The combinatorial task of finding the most probable causal graph such that a given causal query is identifiable is considered. The same probable with an aggregate probability over the induced subgraph is also considered. Not surprisingly, both these problems are hard. The authors first deliver an exact solution. Two approximate procedures are obtained: (i) a recursion calling min-cut; (ii) a reduction to MCIP. Experiments on real and synthetic data are finally discussed.", "questions": "I understand that min-cut has a poly solution, but what is the overall complexity of the first heuristic algorithm?\nSimilarly, is it possible to implement the polynomial transformation in Proposition 4.2, and if so, which is the overall complexity of reducing the problem to MCIP and solving the corresponding instance?\nThe authors assume that the query should be identifiable, and in this perspective, Problems 1 and 2 are very reasonable ways to face the problem. But why should the query be identifiable? There is a lot of literature on non-identifiable queries. E.g., if the output is identifiable only in a very unlikely graph, how should we proceed?", "limitations": "I don't see relevant issues on this point.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The idea of an uncertain causal network with distributive semantics looks very reasonable.\n\nThe hardness results are not surprising, but they appear important for properly characterising the problem.\n\nThe heuristics presented are non-trivial and effective.\n\n", "weaknesses": "- Both heuristic algorithms lack a worst-case complexity characterisation.\n- In the case of MCIP, it needs to be clarified whether the polynomial reduction considered by Proposition 4.2 can be implemented in practice.\n- Problems 1 and 2 are not necessarily the only/best ways to cope with uncertain causal networks. No robust discussions to advocate such a choice are reported.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's thoughtful and positive feedback. We have carefully considered their comments and concerns and addressed them in the following points:\n\n---\n> is it possible to implement the polynomial transformation in Proposition 4.2, \n\nThis transformation is indeed implemented in the code provided as supplementary material. We have also reported the time required to perform this transformation in Figure 4.c, where even accounting for this overhead, the MCIP-based algorithm is faster on a fraction of instances.\n\n>which is the overall complexity of reducing the problem to MCIP and solving the corresponding instance?\n\nThe time complexity of the transformation is linear in the number of vertices and edges of $\\mathcal{G}$, and cubic in the size of the set $Y$. More precisely, with the notation used in the paper, the time complexity would be $O(\\vert V^\\mathcal{G}\\vert + \\vert E_b^\\mathcal{G}\\vert + \\vert E_d^\\mathcal{G}\\vert + \\vert Y\\vert^3)$. It is straightforward to verify this complexity bound through the construction of Appendix A.2. We thank the reviewer for bringing this up, and we will include this analysis in the revision.\n\n---\n>Both heuristic algorithms lack a worst-case complexity characterisation.\n\n>I understand that min-cut has a poly solution, but what is the overall complexity of the first heuristic algorithm? \n\nThe necessary transformations for the heuristic algorithms, i.e., the transformation from $\\mathcal{G}$ to \\mathcal{H}, requires an inital step of finding the maximal hedge (algorithm 3 in the appendix) which requires running $O(\\vert V^\\mathcal{G}\\vert)$ depth-first-searches in the worst case. After this step, both algorithms are linear-time in the number of edges and vertices of $\\mathcal{G}$. The final step then is to solve the minimum-cut in the graph $\\mathcal{H}$.\nThe real bottleneck of both of these algorithms in terms of computational complexity is therefore the minimum-cut problem, for which there exist cubic-time (and even more efficient) algorithms. \nTherefore, a cubic-time complexity upper bound can be proved for the heuristics, and this bound is tight, for instance for a complete graph. We will include the complexity analysis in the revision.\nAs for the implementation, we relied on the existing min-cut-max-flow algorithms in the scipy package, which use the Ford-Fulkerson algorithm by default. The transformation from $\\mathcal{G}$ to $\\mathcal{H}$ is also included in the code we have provided.\n\n\n---\n> There is a lot of literature on non-identifiable queries. E.g., if the output is identifiable only in a very unlikely graph, how should we proceed?\n\nThis is a valid point, and we agree with the reviewer. As mentioned in our conclusion, it is necessary for the practitioner to evaluate the assumptions they want to make. Assuming identifiability yields point estimates at the expense of the possibility of leaving us with the choice of a very unlikely graph, as the reviewer correctly states. The upside is that the practitioner would at least be aware of the fact that this structure is very unlikely and may choose to disregard the causal conclusions. Also, as pointed out by reviewer 'eheu,' one other possible option would be to consider partial identification of the effect and settle for bounds on the query of interest rather than point estimates, which can be thought of as a generalization of the work we presented here. Our main goal was to advocate for a probabilistic model that takes uncertainties on the structure into account, rather than assuming a certain structure is correct. We will discuss this matter further in the text.\n\n---\n>Problems 1 and 2 are not necessarily the only/best ways to cope with uncertain causal networks. \n\nWe consider this work as a first step towards bringing up the idea of incorporating the uncertainty on the structure into\nuncertainty about inference. While our work may not be the best possible approach, we believe it is\na reasonable step forward.\n\n\n"}, {"review_id": "i8Ya39szFp", "reviewer": "Reviewer_N9rZ", "summary": "This paper considers two problems: 1. Finding the most probable graph that makes a desired causal query identifiable. 2. Finding the graph with the highest aggregate probability over its edge-induced subgraphs makes a desired causal query identifiable. This paper shows that both problems reduce to a special combinatorial optimization problem called the edge ID problem. They prove that the edge ID problem is NP-hard, implying that both of the problems are also NP-hard. The paper presents several exact and heuristic algorithms for these problems and evaluates their performances through different experiments. The experiments note that the heuristic algorithms performed remarkably well across all metrics. The paper also discusses the application of these algorithms to four real-world datasets.\n\n\n\n\n\n", "questions": "Could you elaborate on the assumption of mutual independence of edges in the graph? How might the results change if this assumption does not hold?\n\nThe external validity of the derived subgraph is not guaranteed. Could you discuss potential strategies for validating these subgraphs in real-world scenarios?\n\n- The EDGEID algorithm showed large runtime variance and often timed out on real-world structures. Are there any plans to improve the performance of this algorithm in future work?\n\n- The paper mentions that the heuristic algorithms performed remarkably well across all metrics. Could you provide more details on the specific scenarios or types of data where these heuristic algorithms are most effective?\n\n- The paper suggests that future work should explore cases where the assumption of mutual independence of edges does not hold. Could you provide some insights into how this exploration might be conducted?\n\n- The paper applies the proposed algorithms to four real-world datasets. Are there plans to test these algorithms on a wider variety of datasets, particularly those with different characteristics or from different domains?\n\n- The paper presents a detailed analysis of the problem's complexity. Could you discuss the implications of this complexity for the practical application of the proposed algorithms?", "limitations": "- The authors made the assumption that the edges in the graph are mutually independent. This assumption may not hold in all cases, and the authors themselves acknowledge that future work should explore scenarios where this assumption does not hold.\n\n- The external validity of the derived subgraph is not guaranteed. This means that the subgraph may not be correctly specified with respect to the corresponding real-world process. This could limit the applicability of the results in practical scenarios.\n\n- The EDGEID algorithm, one of the exact algorithms proposed in the paper, had large runtime variance which depended heavily on the specifics of the graph under evaluation, particularly for graphs with fewer vertices. This could limit its utility in certain scenarios.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper addresses a complex causal inference problem, specifically identifying the most probable graph that makes a desired causal query identifiable. This is a significant contribution to the field.\n\n- The authors provide a detailed analysis of the problem's complexity, demonstrating that it reduces to a special combinatorial optimization problem, the edge ID problem, which they prove to be NP-hard. This rigorous theoretical analysis is a strength of the paper.\n\n- The authors propose several exact and heuristic algorithms to solve the problem and evaluate their performance through different experiments. The heuristic algorithms, in particular, performed remarkably well across all metrics, demonstrating the practical applicability of the proposed methods.\n\n- The paper also applies the proposed algorithms to real-world datasets, further demonstrating their practical utility. The authors provide a detailed comparison of runtimes, solution costs, and failure rates, offering valuable insights into the performance of the algorithms in real-world scenarios.", "weaknesses": "- The authors made the assumption that the edges in the graph are mutually independent. This assumption may not be held in all cases.\n\n- The external validity of the derived subgraph is not guaranteed. This means that the subgraph may not be correctly specified with respect to the corresponding real-world process. This could limit the applicability of the results in practical scenarios.\n\n- The EDGEID algorithm, one of the exact algorithms proposed in the paper, had large runtime variance, which depended heavily on the specifics of the graph under evaluation, particularly for graphs with fewer vertices. This could limit its utility in certain scenarios.\n\n- The EDGEID algorithm also timed out on all but one of the real-world structures tested, indicating that it may not be as consistent as other algorithms in terms of runtime.\n\n- The runtimes for the MCIP variants exceeded the HEID variants due to the required transformation. This could be a potential drawback in scenarios where computational efficiency is a priority.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the thoughtful review and for acknowledging the significance of our work. We have addressed the main points and questions below.\n\n---\n>Could you elaborate on the assumption of mutual independence of edges in the graph? How might the results change [...]?\n\nIn the case of violation of this assumption, the NP-hardness result would still be intact, but achieving a proper reduction to the EdgeID problem becomes challenging, unless at least a structure is maintained analogous to our discussion of Appendix C.\nWith the current modelling of the problem, the independence assumption is central for our reduction to hold. \nHowever, this assumption can potentially be relaxed by modelling the EdgeID problem on a hyper-graph rather than a simple graph. \nOn the other hand, it is worth noting that certain instances can be easily analyzed when they violate the independence assumption. For instance, in the extreme case where the independence gets violated is when all of the edges are highly correlated, and only two graphs (one with every edge existing and the other where none exists) are likely. This example illustrates that the more interesting cases to analyze are those in which at least a structure on the dependence of edges is maintained, e.g., our model in Appendix C.\n\n---\n>The EDGEID algorithm showed large runtime variance and often timed out on real-world structures. Are there any plans [...]?\n\nGiven the hardness results proved in this work, we do not see improving the efficiency of this algorithm as the main focus of future work. Instead, we are planning to develop approximation algorithms that would run in polynomial time but guarantee an upper bound on the cost of the recovered solution in terms of the optima.\n\n---\n>The paper mentions that the heuristic algorithms performed remarkably well across all metrics. Could you provide more details on the specific scenarios [...]?\n\nAs indicated in our response to reviewer 'eheu' as well, the result of [1] below suffices to show that it cannot be expected from these heuristic algorithms to exhibit a 'worst-case' performance which is better than a log(n) factor of the optimal. However, our experiments suggest that these algorithms perform quite well in the 'average-case'. We believe that unless the data is generated adversarially, these algorithms would achieve a near-optimal solution. Proving this claim however is left as future work.\nIt is noteworthy that since both of these heuristic algorithms are quite efficient, it would make sense to run both and choose the best solution out of the two. By doing so, the performance would be unsatisfactory only if both heuristic algorithms fail to achieve a near-optimal solution.\nThis indeed would result in a level of robustness, since the performance of HEID1 relies highly on the structure of the directed edges of $\\mathcal{G}$, while the performance of HEID2 depends more on the structure of the bidirected edges of $\\mathcal{G}$.\n\n[1] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4): 634–652, 1998.\n\n---\n>The paper suggests that future work should explore cases where the assumption of mutual independence of edges does not hold. Could you provide some insights [...]?\n\nWe have covered a special case where the independence assumption gets violated in Appendix C. This special case still allows us to reduce the problem to an instance of EdgeID. However, in a more general setting this would not be the case. Of course as mentioned earlier, allowing for the most general cases is not the best course of action  (considering for instance the example above where only two possible configurations exist). One reasonable way to extend our work would be considering the case where each edge is correlated with at most $k$ other edges for some parameter $k$. In such a scenario, classic results such as Lovasz' local lemma might be helpful to tackle the problem.\n\nAnother promising direction might be modelling the EdgeID problem on hypergraphs, assigning each subset of variables a cost. This direction is indeed what we would like to explore next.\n\n---\n>The paper applies the proposed algorithms to four real-world datasets. Are there plans to test these algorithms on a wider variety of datasets [...]?\n\nWe will indeed consider applying these algorithms to a wider range of datasets. We thank the reviewer for their suggestion.\n\n---\n>The paper presents a detailed analysis of the problem's complexity. Could you discuss the implications of this complexity for the practical application [...]?\n\nThere are several implications that can be thought of. \nFirst, as NP-hard problems are known for their high computational complexity, the 'exact' algorithms developed in this paper may face challenges when dealing with large-scale or real-world datasets. In practice, this complexity may result in intractable run times for the exact algorithms on extensive datasets, leaving only the heuristic algorithms on the table.\nSecond, the NP-hard nature of the problem also motivates the development of approximation algorithms that can provide near-optimal solutions in polynomial time. While we have introduced heuristic algorithms that performed well in our experiments, further research in designing more efficient approximation algorithms could enhance the practical applicability of our work.\nLast but not least, understanding the NP-hardness of the problem encourages us to explore scalable techniques, such as parallelization or distributed computing, to tackle larger instances efficiently. These strategies can help mitigate the impact of the problem's complexity on the practical application of the algorithms.\nWhile the NP-hardness of the problem presents challenges in terms of computational complexity, it also motivates further research in developing more efficient algorithms to handle larger datasets.\nWe will discuss these implications in the revision."}]

Author rebuttal:

Meta-review: The paper's main contribution is Theorem 3.4, which shows that the introduced EdgeID problem is NP-hard.

The paper was mostly received well by the reviewers. I have read it as well and would like to remark a few things below.

- It is indeed obvious that if a causal effect is ID on a graph, it will also be ID on its subgraphs. This follows from two basic facts: Any ID alg. can be seen as a sequential application of do-calculus rules, and the predicates of the rules, i.e., graphical d-separation statements that hold in a graph, must also hold in any subgraph. The authors seem to suggest this as part of their key contributions but this two-line proof shows that this is indeed obvious. I would recommend them to reconsider how they position this claim, and accordingly, Proposition 3.1 which currently seems to have quite a lengthy proof in Appendix.

- The assumption that the true graph belongs to a subgraph of a dense graph, and that we have access to this dense graph is quite strong. Despite listing some other limitations, I have not seen this point discussed in depth. Please consider adding a discussion on when one would have access to such a supergraph of the true graph. The current motivation is not very convincing, since if some CI tests are incorrect, suppose during the causal discovery stage, one would get a very different graph than the true graph rather than a strict supergraph.

Despite these weaknesses, I think the paper focuses on an interesting problem. The full solution when we have a prior over different ADMGs would be very interesting to see, and I am hoping this paper will start a more thorough investigation of this interesting problem.
Decision: Accept (poster)