Causal Identification under Markov equivalence: Calculus, Algorithm, and Completeness
Authors: Amin Jaber
Adele H Ribeiro
Jiji Zhang
Elias Bareinboim
Venue: NeurIPS 2022 Accept (2022)
Keywords: causality
causal inference
Markov equivalence
causal effect identification

Abstract: One common task in many data sciences applications is to answer questions about the effect of new interventions, like: `what would happen to $Y$ if we make $X$ equal to $x$ while observing covariates $Z=z$?'. Formally, this is known as conditional effect identification, where the goal is to determine whether a post-interventional distribution is computable from the combination of an observational distribution and assumptions about the underlying domain represented by a causal diagram. A plethora of methods was developed for solving this problem, including the celebrated do-calculus [Pearl, 1995]. In practice, these results are not always applicable since they require a fully specified causal diagram as input, which is usually not available. In this paper, we assume as the input of the task a less informative structure known as a partial ancestral graph (PAG), which represents a Markov equivalence class of causal diagrams, learnable from observational data. We make the following contributions under this relaxed setting. First, we introduce a new causal calculus, which subsumes the current state-of-the-art, PAG-calculus. Second, we develop an algorithm for conditional effect identification given a PAG and prove it to be both sound and complete. In words, failure of the algorithm to identify a certain effect implies that this effect is not identifiable by any method. Third, we prove the proposed calculus to be complete for the same task.

Causal Identification under Markov equivalence: Calculus, Algorithm, and Completeness
Amin Jaber Purdue University j abberd@uuruue edu
Adèle H. Ribeiro Columbia University adele@cs. waw.eess.columbaa... edu
Jiji Zhang
Elias Bareinboim Columbia University eb#cs. columbia, edu
Hong Kong Baptist University zhangji i8hkbu. edu. hk
Abstract
One common task in many data sciences applications is to answer questions about the effect of new interventions, like: 'what would happen to Y if we make X equal while observing covariates Z 2?'. Formally, this is known as conditional effect identification. where the goal is to determine whether iesevinterventional distribution is computable from the combination an observational distribution and assumptions about the underlying domain represented by a causal diagram. A plethora of methods was developed for solving this problem, including the not always
celebrated do-calculus [Pearl, 1995]. In practice, these results applicable since they require fully specified causal diagram as input, which is usually not available. In this paper, we assume the input of the task a less informative structure known as a partial ancestral graph (PAG), which represents a Markov equivalence class of causal diagrams, learnable from observational data. We make the following contributions under this relaxed setting. First, we introduce new causal calculus, which subsumes the current ofate-of-the-art, PAG-calculus. Second, we develop an algorithm for conditional effect identification given a PAG and prove it be both sound and complete. In words, failure of the algorithm identify a certain effect implies that this effect not identifiable by any method. Third, prove the proposed calculus be complete for the same task.
Introduction
Despite the recent advances in Al and machine learning, the current generation of intelligent systems still lacks the pivotal ability to represent, learn, and reason with cause and effect relationships. The discipline of causal inference aims to 'algorithmitize' causal reasoning capabilities towards producing human-like machine intelligence and rational deaisign-making [Pearl and Mackenzie, 2018, Pearl, 2019, Bareinboim and Pearl, 2016]. One fundamental type of inference in this setting is concerned with the effect of new interventions, e.g., 'what would happen to outcome Y if X were set to x?' More generally,
may be interested in Y's distribution in sub-population picked out by the value of some covariates Z = z². For example, a legislator might be interested in the impact that increasing the minimum wage (X I) has on profits (Y) in small businesses (Z 2). which written in causal language as the interventional distribution (y do(x),,) 2), or Pa (.) One method capable of answering such questions is through controlled experimentation [Fisher, 1951].
In many practical settings found throughout the empirical sciences, AI, and machine learning, not always possible to perform controlled experiment due to ethical, financial, and technical considerations. This motivates the study problem known as causal effect identification [Pearl,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

2
?
W
X
Y
W
X
Y
W 0
X (c)
(a)
(b)
Figure I: Sample causal diagrams (a.b) and the corresponding inferred PAG (c).
2000, Ch. 3]. The idea is to use the observational distribution P(V) along with assumptions about the underlying domain, articulated in the form of causal diagram D, to infer the interventional distribution Px (ylzz when possible. For instance, Fig. la represents a causal diagram in which nodes correspond to measured variables, directed edges represent direct causal relations, and bidirected- dashed edges encode spurious ussociations due to unmeasured confounders. A plethora of methods have been developed to address the identification task including the celebrated causal calculus proposed by Pearl [1995] as well as complete algorithms [Tian,, 2004, Shpitser and Pearl, 2006, Huang and Valtorta, 2006]. For instance, given the causal diagram Fig. 1a and the query P= the calculus sanctions the identity Pa (u]2) = P(ylz, 22. In words, the interventional distribution on the lhh.s. equates to the observational distribution on the right, which is available as input. Despite the power of these results, requiring the diagram the input of the task is an Achilles heel for those methods, since background knowledge is usually not sufficient to pin down the single, true diagram.
To circumvent these challenges, a growing literature develops data-driven methods that attempt to learn the causal diagram from data first, and then perform identification from there. In practice, however, only an equivalence class (EC) of diagrams can be inferred from observational data without making substantial assumptions about the causal mechanisms [Verma, 1993, Spirtes et al., 2001, Pearl, 2000]. A prominent representation of this class is known as partial ancestral graphs (PAGs) [Zhang. 2008b]. Fig. Ic illustrates the PAG learned from observational data consistent with both causal diagrams in Figs. la and lb since they are in the same Markov equivalence class. The directed edges in a PAG encode ancestral relations, not necessarily direct, and the circle marks stand for structural uncertainty. Directed edges labeled with u signify the absence of unmeasured confounders.
Causal effect identification in a PAG usually more challenging than from a single diagram due to the structural uncertainties and the infeasibility of enumerating each member of the EC in most cases. The do-calculus was extended for PAGs account for the inherent structure uncertainties without the need for enumeration [Zhang, 2007]. Still, the calculus falls short of capturing all identifiable effects as we will see in Sec. 3. On the other hand, it computationally hard to decide whether there exists (and, if so, to find) a sequence of derivations in the generalized calculus to identify an effect of interest. a more systematic manner, a complete algorithm has been developed to identify marginal effects (i.e., (y)) given a PAG [Jaber et al., 2019a]. This algorithm can be used to identify conditional effects whenever the joint distribution (y U 2) is identifiable. Still, many conditional effects identifiable even if the corresponding joint effeett is not (Sec. 4.2). Finally, algorithm to identify conditional effects has been proposed in [Jaber et al., 2019b], but not proven to be complete.'
In this paper, we pursue data-driven formulation for the task of identification of any conditional causal effect from a combination of an observational distribution and the corresponding PAG (instead of fully specified causal diagram). Accordingly, we makes the following contributions:
1. We propose causal calculus for PAGs that subsumes the stat-of-the-art calculus introduced in [Zhang, 2007]. We prove the rules are atomic complete, i.e., a rule is not applicable in some causal diagram in the underlying EC whenever it is not applicable given the PAG.
2. Building on these results, we develop an algorithm for the identification of conditional causal effects given PAG. We prove the algorithm is complete, i.e., the effect is not identifiable in some causal diagram in the equivalence class whenever the algorithm fails.
3. Finally, we prove the calculus is complete for the task of identifying conditional effects.
Annohher approach is based on SAT (Boolean constraint satisfaction) solvers [Hyttinen et al., 2015). Given its somewhat distinct nature, closer comparison lies outside the scope of this paper.

---

2 Preliminaries
In this section, we introduce the basic setup and notations. Boldface capital letters denote sets of variables, while boldface lowercase letters stand for value assignments to those variables."
Structural Causal Models. We use Structural Causal Models (SCMs) as our basic semantical framework [Pcarl, 2000]. Formally, an SCM M is a 4-tuple (U, V, P(U), where U is a set of exogenous (unmeasured) variables and V is set of endogenous (measured) variables. F represents collection of functions such that each endogenous variable VÚ E V is determined by a function fi E F. Finally, P(U) encodes the uncertainty over the exogenous variables. Every SCM is associated with one causal diagram where every variable in V U U is a node, and arrows are drawn between nodes in accordance with the functions in F. Following standard practice, we omit the exogenous nodes and add a bidirected dashed are between two endogenous nodes if they share an exogenous parent. We only consider recursive systems, thus the corresponding diagram is acyclic. The marginal distribution induced over the endogenous variables P(V) is called observational. The d-separation criterion captures the conditional independence relations entailed by causal diagram in P(V). For C C V. [[C] denotes the post-intervention distribution of C under an intervention on V C, i.e Prie(c).
Ancestral Graphs. We now introduce a graphical representation of equivalence classes of causal di- agrams. MAGG represents set of causal diagrams with the same set of observed variables that entail the same conditional independence and ancestral relations among the observed variables [Richardson and Spirtes, 2002]. M- M-separation extends d-separation MAGs such that d-separation in a causal diagram corresponds to m-separation in its unique MAG over the observed variables, and vice versa.
Definition 1 (m-separationn. A path between X and Y is active (or m-connecting) relative to Z (X, Y & Z) if every non-collieer on p not in L. and every collider on p is an ancestor of some Z E Z. X and Y are m-separated by Z if there is no active path between X and Y relative to Z.
Different MAGs entail the same independence model and hence are Markov equivalent. A PAG represents equivalence class of MAGs [M] which shares the same adjacencies as every MAG in [M] and displays all and only the invariant edge marks. A circle indicates an edge mark that is not invariant. A PAG is learnable from the independence model over the observed variables, and the FCI algorithm is a standard method to learn such an object [Zhang, 2008b]. In this work, an oracle for conditional independences is assumed to be available, which leads to the true PAG.
Graphical Notions. Given PAG, a path between X and Y is potentially directed (causal) from X to Y if there is no arrowhead on the path pointing towards X. Y is called a possible descendant of X and X possible ancestor of Y if there is potentially directed path from X to Y. For set of nodes X, let An(X) (De(X)) denote the union of X and the set of possible ancestors (descendants) of X. Given two sets of nodes X and Y, path between them is called proper if one of the endpoints is in X and the other is in Y, and no other node on the path is in X or Y. Let (A, B, C*) be any consecutive triple along a path p. B is collider on p if both edges are into B. B is a (definite) non-collider on p if one of the edges is out of B, or both edges have circle marks at B and there is no edge between A and C. A path definite status if every non-endpoint node along it is either collider or non-collider. If the edge marks on a path between X and Y are all circles, we call the path circle path. We refer to the closure of nodes connected with circle paths as bucket.
A directed edge X + Y in a PAG is visible if there exists no causal diagram in the corresponding equivalence class where the relation between X and Y is confounded. Which directed edges visible is easily decidable by a graphical condition [Zhang, 2008a], so we mark visible edges by u.
Manipulations in PAGs. Let P denote a PAG over V and X C V. Px denotes the induced subgraph of P over X. The k-lower-manipulatton of P deletes all those edges that visible in P and are out of variables in X, replaces all those edges that are out of variables in X but are invisible in P with bi-directed edges, and otherwise keeps P as it is. The resulting graph is denoted as Px. The X- supper-manipulatie
of P deletes all those edges in P that are into variables in X, and otherwise keeps P as it is. The resulting graph is denoted as Px
2 A more comprehensive discussion about the background is provided in the full report [Jaber et al., 2022]. 3 'Without loss of generality, we assume the model is semi- mark-vaaav..n. Tian [Tian, 2002, Sec. 5.6] shows that the identification of causal effect in a non non- Markkvvon model is equivalent to the identification of the same effect in derived mai-Markovian model via procedure known as "projection'.
3

---

A
X1
W
Z
Y
X1 0
W
Z
Y
X1
Z Y
X2
X2
X2
(a) PAG P.
(b) Pw
(c) Pvi(w).
Figure 3: Alternative methods to read ancestral relations under interventions from PAGs.
3 Causal Calculus for PAGs
The causal calculus introduced in [Pearl, 1995] is seminal work that has been instrumental for understanding and eventually solving the task of effect identification from causal diagrams. Zhang [2007] generalized this result to the context of ancestral graphs, where a PAG is taken the input of the task, instead of the specific causal diagram. In Sec. 3.1, we discuss Zhang's ' rules and try to understand the reasons they are insufficient solve the identification problem in full generality. Further, in Sec.3.2, we introduce another generalization of the original calculus and prove that it is complete for atomic identification. This result will be further strengthened in subsequent sections.
3.1 Zhang's Calculus
An obvious extension of the m-separation criterion shown in Def. 1 to PAGs blocks all possibly m- en-coneecingg paths, as defined next.
Definition 2 (Possibly m-connecting path). In a PAG, a path p between X and Y a possibly m-- connecting path relative to (possibly empty) set of nodes Z (X,Y & if every definite non-collider on p is not a member of Z. and every collider on p is a possible ancestor of some member of Z. X and Y are ri-separated by Z if there is no possibly m-connecting path between them relative to Z.
Using this notion of separation, Zhang [2007] proposed calculus given a PAG as shown next.
Proposition 1 (Zhang's s Calculus). Let P be the PAG over V, and X, Y, W, Z be disjoint subsets V. V. The following rules are valid, in the sense that if the antecedent of the rule holds, then the consequent holds in every MAG and consequently every causal diagram represented by P.
P(y]do(w). x, z) P(yldo(w),z))
X and Y are i--seaaraeed by W Z in Pw-
2. Ply]do(w) do(x), 2) = P(y]do(w),xx x,
if X and Y are in-separated by W U ZZ in Pw.x
3. P(y]do(w) do(x), z) = P(y]do(w)),2) where X(Z) = X PossAn(Z))n Pw
if X and Y are i--spaarated by WUZ in P P.)
In words, rule generalizes m-separation to interventional settings. Further, rule 2 licenses alternating a subset X between intervention and conditioning. Finally, rule 3 allows the adding/removal of an intervention do(X- = x). The next two examples illustrate the shortcomings of this result, where the first reveals the drawback of using Def. 2 to establish graphical separation and the second inspects evaluating (Z) in rule 3 (where the notion of possible ancestors are evoked).
Example 1. Consider the PAG P shown in Fig. 2. Since X and Y are not adjacent in P. it is easy to show that X and Y are separable given {Z,, Zz} in every causal diagram in the equivalence class. If rule 3 of Pearl's calculus is used each diagram, then Pz 21 22) P(yl 22). Further, applying rule 2 of do-calculus in each diagram, it's also the case that Pz(y) 22, 22) = P(yl 21, 22, 2)) However, due to the possibly m-connecting path (X, Zi. Zz. Y), rules 3 and 2 in Prop. I are not applicable to P. In other words, even though Pearl's 's calculus rules 2 and 3 are applicable to each diagram in the equivalence class, the same results cannot be established by Zhang's 's calculus.
Z1
Z2
Figure 2: Sample PAG

---

Example 2. Consider the PAG in Fig. 3a, and the evaluation on whether the equality P Pw.., 22 (3)2) Po ) holds. In order to apply rule 3 of Prop. 1, we need to evaluate whether {X,, X2) is separated from {Y} given [W, 7 in the manipulated graph in Fig. 3b, which is not true in this case. However, the rule can be improved to be applicable this case, as we will show later on (Sec. 3.2). The critical step will be the evaluation of the set (Z) from Pw
3.2 A New Calculus
Building the analysis of the calculus proposed in [Zhang, 2007], we introduce next set of rules centered around blocking definite n- t--connecting paths, as defined next.
Definition 3 (Definite m-connecting path). In PAG, a path p between X and Y is definite m-connecting path relative to a (possibly empty) set Z (X,Y Y & Z)) if is definite status, every definite non-collider p is not a member of Z. and every collider p is ancestor of some member of Z. X and Y are m-separated by Z if there is no definite m-connecting path between them relative to Z.
is easy to see that every definite m-connecting path is a possibly m m-connecting path, according to Def. 2: however, the converse is not true. For example, given the PAG in Figure 2, we have two definite status paths between X and Y. The first is X о-o Z1 o-o Y and the second is X o-o Zz o-o Y where Zı and Z- are definite non-colliders. Given set Z {7,, 72) paths between X and Y. Alternatively, the path X a-o 21 a-o Ze c-o Y is not definite status since Z1, Z2 are not colliders non-colliders on this path. Hence, the path is a possibly m-connecting path relative to Z by Def. 2 but not a definite m-connecting path by Def. 3.
). Z blocks all definite status
We now ready use this new definition and formulate more powerful calculus.
Theorem 1. Let P be the PAG over V, and X, Y, W be disjoint subsets V... The following rules are valid, in the sense that if the anlecedent of the rule holds, then the consequent holds in every MAG and consequently every causal diagram represented by P.
1. P(y]do(w) x, 2) = Ply]do(w),
if and Y are m-separated by W WUZin Pw-
2. Ply]do(w) do(x), z) = P(y]do(w), x,
if X and Y are m-separated by W U Z in P W.
3. P(y]do(w) do(x), 2) = P(yldo(w),
if X and Y are m-separated by WUZ in P W.X(Z)
where X(Z) = X PossAn( (Z) Pviw
few observations are important at this point. Despite the visual similarity to Prop. 1, there are two pivotal differences between these calculi. First, Thm. I only requires blocking the definite status paths, hence the use of 'm-separation' in Thm. instead of "m-separation". Consider the PAG P in Fig. 2. We want evaluate whether (y(y22 22) P(y x. 21, 22) by applying Rule 2 in Theorem 1. Since all the edges in the PAG are circle edges, then Px = P. As discussed earlier, the set Z Z= [Z,, Z2} } blocks all the definite status path between X and Y. Hence, X and Y are m-separated by Z and Pa (2(221 22) = P(yle jr 21, 22) holds true by Rule 2.
Second, Thm. I defines X as the subset of X that is not in the possible ancestors of Z in Pv.w. as opposed to Pw Prop. 1. We revisit the query in Ex. 2 to clarify this subtle but significant difference. Given the PAG in Fig. 3a, want to evaluate whether Pu,z, 22 (y)2) (y(l2) by applying Rule 3 from Thm. instead of Prop. 1. Fig. 3c shows (v) where X = [X1, X2) are
not possible ancestors of Z. Therefore, X(Z) X, the edges into X₃ are cut in Pw. x(Z) and X and Y are m-separated therein.
Third, the proof of the Theorem 1 is provided in the appendix, but it follows from the relationship between m-connecting path in a manipulated MAG to a definite m-connecting path in the correspond- ing manipulated PAG. It was conjectured in [Zhang. 2008a, Footnote 15] that, for X, Y C V, if there is an m-connecting path in My.x. x then there is a definite m-connecting path in Py x. In this work, we prove that conjecture to be true for the special class of manipulations required in the rules of the calculus. Finally, the next proposition establishes the necessity of the antecedents in Thm. 1 in order to apply the corresponding rule given every diagram in the equivalence class.
'll the proof's be found in the full report [Jaber al., 2022].
5

---

Theorem 2 (Atomic Completeness). The calculus in Theorem 1 is atomically complete; meaning, whenever a rule is not applicable given a PAG, then the corresponding rule in Pearl's 'sss's calculus not applicable given some causal diagram in the Markov equivalence class.
For instance, considering PAG P Fig. Ic, we note that ( P) Px which means rule 2 not applicable. Clearly, the diagram in Fig. la is in the equivalence class of P and the corresponding rule of Pearl's calculus is not applicable due the latent confounder between Z and Y.
4 Effect Identification: A Complete Algorithm
It is challenging to use the calculus rules in Thm. I to identify causal effects since it is computationally hard to decide whether there exists (and, if so, find) a sequence of derivations in the generalized calculus to identify an effect of interest. The goal of this section is to formulate an algorithm to identify conditional causal effects. The next definition formalizes the notion of identifiability from a PAG, generalizing the causal- muusal-diarram--pecifee notion introduced in [Pearl, 2000, Tian, 2004].
Definition (Causal- -ffuet Identifiabilityy. Let X, Y, Z be disjoint sets of endogenous variables, V. The causal effect of X on Y conditioned on Z is said be identifiable from a PAG P if the quantity Px Px(y(z) ( can be computed uniquely from the observational distribution P(V) given every causal diagram D in the Markov equivalence class represented by P.
The remainder of the section is organized as follows. Sec. 4.1 introduces version of the IDP algorithm [Jaber et al., 2019a] to identify marginal causal effects. The attractiveness of this version is that it yields simpler expressions whenever the effect is identifiable while preserving the same expressive power, i.e., completeness for marginal identification. Sec. 4.2 utilizes the new algorithm along with the calculus in Thm. 1 to formulate a complete algorithm for conditional identification.
4.1 Marginal Effect Identification
We introduce the notion of pe-component next, which generalizes the notion of e-component that is instrumental to solve identification problems in a causal diagram (Tian and Pearl, 2002].
Definition 5 (PC-Coomoneett. In a PAG, or any induced subgraph thereof, two nodes are in the same possible e-component (pc-component) if there is path between them such that (1) all non-endpoint nodes along the path are colliders, and (2) none of the edges is visible.
Following Def. 5, e.g., W and Z in Fig. Ic are in the same pe-component due to Wo-+ X <-Z.. By contrast, X, Y are not in the same pc-component since the direct edge between them is visible and Z along (X, Z, Y) is not a collider. Building on pe-components, we define the key notion of regions. Definition 6 (Region R)) Given PAG P over V, and A C C V. The region of A with respect C, denoted R is the union of the buckets that contain nodes in the pe-component of A in Pc-
A region expands a pe-component and will prove to be useful in the identification algorithm. For example, the pc-component of X in Fig. 2 is {X, Zi, Z2} and the region R {X, Zı, Zz, Y). Building further on these definitions and the new calculus, we derive a new identification criterion.
Let P denote a PAG over V, T be a union of a subset of the buckets in P, and X C T be a bucket. Given Pvitt (i.e., an observational expression for QT), QT X] is identifiable by the following expression if, in Pr, C* n PossDe(X)) S X. where C is the pc-component of X.
Proposition 2.
Pvte
Q (X PossDe(X))
(1)
Note the interventions are over buckets which may or may not be single nodes. Since there is little to causal information inside bucket, marginal effects of interventions over subsets of buckets are not identifiable. Also, the input distribution is possibly interventional which licenses recursive applications of the criterion. The next example illustrates the power of the new criterion.
Example 3. Consider PAG P in Fig. 3a and the query P2 z, a). Starting with the observa- tional distribution P(V) input, let T = V and X [X1, WJ. We have CX =X1, A, X2).

---

Algorithm 1 (DP((,x,)) x,,)
Input: PAG P and two disjoint sets X. V
Output: Expression for (y or FAIL
1: Let D = PossAn Y Pvix
2: return Ealy IDENTIFY (D, P)
3: function IDENTIFY T.Q- T-QQQ[T
4: if C 9) then return
5:
if C T then return Q
1 In Pr. let B denote a bucket, and let CB denote the pe-component of */
6:
if 3B C T C such that C n PossDe(B) S B then
7:
Compute Q B) from Q: return IDENTIFY(C,T) B B)
via Prop.
8:
9:
else if JB C C such that RB K C then IDENTIFY T,Q) (R T.Q)
RB is equivalent Rg
10:
return
IDENTIFY (R T.Q)
11: else throw FAIL
PossDe(X) = {X1, W, J,,,, and C* n PossDe(X) X. Hence, the criterion in Prop. 2 is ap- P(v)
plicable and we have Pxly, 2, a 322 P(ri.wla.ns) P(), x =ly, w) after simplification. Next, we consider intervening on X2 given Pa (U, 2, a, 22). Notice X₂ is disconnected from the other nodes in PV)(X1,W) and trivially satisfies the criterion in Prop. 2. Therefore, we get the expression Pa, u (y, 2, a) (=g.u(())))
P(a) Ply, 2 l0, a) after simplification.
more general criterion was introduced in [Jaber et al., 2018, Thm. based on the possible children of the intervention bucket X instead of the possible descendants. However, the corresponding expression is convoluted and usually large, which could be intractable even if the effect is identifiable. Alg. shows the proposed version of IDP, which builds on the new criterion (Prop. 2). Specifically, the key difference between this algorithm and the one proposed in [Jaber et al., 2019at is in Lines 6-7, where the criterion in Prop. 2 is used as opposed to that in [Jaber et al., 2018, Thm. 1]. Interestingly enough, the new criterion "just right," namely, it is also sufficient to obtain complete algorithm for marginal effect identification, as shown in the next result."
Theorem 3 (completeness). Alg. I is complete for identifying marginal effects Px(y). Moreover, the calculus in Thm. 1, together with standard probability manipulations are complete for the same task.
4.2 Conditional Effect Identification
We start by making couple of observations, and then build on those observations to formulate an algorithm to identify conditional causal effects. The proposed algorithm leverages the calculus in Thm. and the IDP algorithm in Alg. 1. Obs. notes that conditional effect Px(y|z) can be and hence is identifiable Px (y, z) identifiable by Alg.
rewritten as Σy Paly', 23 []]
Px(yx)
Observation (Marginal Effect). Consider PAG P1 in Fig. 4a where the goal is to identify the causal effect Ps Po(a, cld). We notice that the effect Po(a, c, d) is identifiable using the IDP algorithm. Let E = (aa, d) P(cb, d) denote the expression for the marginal effect Po(a, c, which can be obtained from IDP. Consequently, the target effect can be computed using the expression E/ Ea E.
Whenever the marginal effect Px z) is not identifiable using Alg. 1, Observations 2 and propose techniques to identify the conditional effect using the calculus in Thm. 1, namely rule 2. Obs. 2 uses rule 2 of Thm. when applicable, to move variables from the conditioning to the intervention set. The marginal effect of the resulting conditional query turns out to be identifiable, and consequently does the conditional effect. We note that the work [Shpitser and Pearl, 2006] uses the same trick to formulate an algorithm for conditional effect identification given a causal diagram.
A more detailed comparison of the two algorithms along with illustrative examples is provided in the full report [Jaber et al., 2022).
7

---

W
W
A
B
X
Z
Y
X
Z
T
(a) PAG Pi.
(h) PAG Ps
(c) Causal Diagram G.
Figure 4: (a,b) Two sample PAGs, and (c) causal diagram in the equivalence class of (b).
Algorithm 2 (P,
Input: PAG P and three disjoint sets X, Y, V
Output: Expression for (y/z)) or FAIL
1: D PossAn Y U P)
1* Ler Bı..... Bm denote the buckets in P */
2:
while BB; s.t. B,DD & A, B, D do
3:
X' < B. B
4:
if (X' IL YI(X) (')
xx x then
5:
4- 1x: zUx
> Apply rule 2 of Thm. 1
6:
D f- PossAn(Y UZ)vvx
7:
else throw FAIL
1 Let Zi...., Zm partition Z such that Z. = Z,
8: while 3Z, s.t. (Z, 11 Y U (Z Zi)) do
9: x x x 23:2 (
> Apply rule 2 of Thm. 1
10: E t IDP U.P. UU) return E/ Ey E
Observation 2 (Flip Observations to Interventions). Consider PAG Pi in Fig. 4a and the causal query Pa d). Unlike the case in Obs the marginal effect Palb, c, d) is not identifiable by the IDP algorithmm. Using rule 2 of Thm. 1, we have (B 1L D)D) and move B from conditioning to intervention, iee. Pa (c)b, d) = Pa.(cld) The marginal effect Pa,b(c, d) is identifiable by IDP and we get the expression E = ((d) x P(c|b, d). Hence, we have Pa(c d) Pa,((cld)
Ee E.
Finally, Obs comes as a surprise since it requires flipping interventions to observations, contrary to Obs. 2. A key graphical structure in the PAG that requires such treatment is the presence of proper possibly directed path from X to Y U Z that starts with a circle edge.
Observation 3 (Flip Interventions to Observations). We revisit the query in Example. 1. First, the marginal effect Ps (y, Z1, 22) is not identifiable by the IDP algorithm. Also, we cannot rule 2 in Thm. to flip Z1 or Zz into interventions since they are both adjacent to with circle edge (o-o). However, can use rule flip X to the conditioning set since there are definite n-connecting paths between and given { Z1, Za} in the PAG. Hence, we obtain (y 21, 22) P(yle 22, x). Alternatively, consider PAG P2 in Fig. 4b with the causal query Pz(y)z). We cannot use rule 2 to ) is active given in P22x- In fact, the causal diagram G in Fig. 4e is in the equivalence class of P2 and such that Pz(y) provably not identifiable |Shpitser and Pearl, 2006, Corol. 2]. Hence, the effect is not identifiable given P2 according to Def. 4.
flip X to an observation since (X, W, W.Y
Putting these observations together, we formulate the CIDP algorithm (Alg. 2) for identifying conditional causal effects given PAG. The algorithm is divided into three phases. In Phase I (lines 1-7), Obs. is used to check for proper possibly directed paths from X Y Z that start with a circle edge. This is checked algorithmically by computing D PossAn Y U Z)p iteratively. and checking if some bucket B, P intersects with, but not subset of, D. If such a bucket exists, CIDP flips B; 0 X from interventions to observations using rule 2, when applicable, else the algorithm throws fail and the effect not computable. In Phase II (lines 8-9), Obs used to flip the subset of observations in each bucket into interventions by applying rule 2 of Thm. 1.

---

A
A
0 B
Ao
0
B
Ge
C
G
0
G
Y (b) PAA
F
(a) PAG P. Figure 5: Illustrating example for Alg. 2.
(c) Pr.E
whenever applicable. Finally, in Phase III (line 10), the marginal effect Py Uzz is computed from the modified sets X and Z, using the IDP algorithm in Alg. 1. If the call is successful, expression for the conditional effect is returned at line 11. The example below illustrates CIDP in action. An empirical evaluation of CIDP is provided in the full report [Jaber al., 2022].
Example 4. Consider PAG P in Fig. 5a and the conditional query Px(y(z) = Pa.s(ulb, e). In Phase we have D possAn( Y U P = [Y, E, , C, G}, and the bucket {A, B} satisfies the conditions at line since A & D. In PF.A (as shown in Fig. 5b), X'= {A} is m-separated fromm Y given {B, E, F} which satisfies the if condition at line 4. Hence, we we.flip A to the conditioning set Z via rule 2 of Thm. to obtain the updated query (x(y(z) Py(yla, b, e). In Phase II (lines 8-9), let Z1 = }E} and Z2 {A, B). In PF.g (see Fig. 5c), we have E m-separated from Y given {F) U Z2 which satisfies the if condition at line 8. Hence,
flip E to the intervention set using rule 2 of Thm. and we get the updated query (y ()) = Pe.. (y a. b). Next, we check if Z = Zn is m-separated from Y given X in Px,z which does not hold due a bidirected edge between B and Y. Hence, rule is not applicable and Z remains in the conditioning set. Finally, call IDP to compute the marginal effect Pe.s(1- (y, a, b), if possible. The effect is identifiale with the simplified expression Ptylb.e. (o P(a.) Plylb, f) P(a, b). Hence, Pa.r e) Pers(yyla, - -E, Plgg
P(ylb, s).
The soundness of Alg. 2 follows from that of Alg. 1 and Thm. 1. Next, we turn to its completeness. According Def. 4, whenever CIDP fails, we need to establish one of two conditions for complete- ness. Either there exist two causal diagrams in the equivalence class with different identifications, or the effect is not identifiable some causal diagram according to the criterion [Shpitser and Pearl, 2006, Corol. 2]. Thm. 4 establishes completeness by proving that the latter is always the case. This result along with the completeness of the calculus rules for the identification of marginal effects (see Thm. 3) implies that the rules complete for conditional effects as well.
Theorem 4 (completeness). Alg. 2 is complete for identifying conditional effects Px z)). Also, the calculus in Thm. together with standard probability manipulations are complete for the same task.
Discussion
In this work, an oracle for conditional independences is assumed to be available, which leads to the true PAG. Assuming the presence of an oracle for conditional independence encapsulates the challenge of dealing with finite data and of testing for conditional independence thereof. Another challenge lies in the computational complexity of learning the PAG in the first place [Colombo et al., 2012], and estimating the expression when the effect is identifiable [Pearl and Robins, 1995, Jung et al., 2021]. I]. In light of this, is important to make the distinction between the task of causal effect identification and that of causal effect estimation.
This set results is concerned with the first task (causal identification), which asks whether a target conditional effect is uniquely computable from P(V), the observational distribution, and given PAG learnable from P(V). The objective of CIDP Algorithm 2 is to decide whether the effect is identifiable and provide an expression for it when the answer is yes, while being agnostic to whether P(V) can be accurately estimated from the available samples.
As for the second task, the estimation of the conditional causal effect using the identification formula provided by Algorithm 2 poses several challenges under finite data. The number of samples sufficient to identify a given effect would depend on the size of the expression, among other factors, and
CCode is available https:: //te:////tttttt hattu//cccccmmaaaaAAAA/AAAA11

---

naive methods for estimation exacerbate this problem. Recent work such as [Jung et al., 2021] proposes double machine learning estimator for marginal effects that are identifiable given PAG. An interesting direction of work is to generalize this approach to conditional causal effects that are identifiable by CTDP.
Conclusions
In this work, investigate the problem of identifying conditional interventional distributions given a Markov equivalence class of causal diagrams represented by a PAG. We introduce new generalization of the do-caleulus for identification of interventional distributions in PAGs (Thm. 1) and show it to be atomically complete (Thm. 2). Building on these results, we develop the CIDP algorithm (Alg. 2). which is both sound and complete, i.e., it identifies any conditional effects of the form (x 2) that is identifiable (Thm. 4). Finally, we show that the new calculus rules, along with standard probability manipulations. are complete for the same task. These results close the problem of effect identification under Markov equivalence in that they completely delineate the theoretical boundaries of what is, in principle, computable from a certain data collection. We expect the newly introduced machinery to help data scientists to identify novel effects in real world settings.
Acknowledgments and Disclosure of Funding
Bareinboim and Ribeiro's research was supported in part by the NSF, ONR, AFOSR, DoE, Amazon, JP Morgan, and The Alfred P. Sloan Foundation. Zhang's research was supported by the RGC of Hong Kong under GRF13602720.
References
E. Bareinboim and J. Pearl. Causal inference and the data-fusion problem. In R. M. Shiffrin, editor, Proceedings of the National Academy of Sciences, volume 1 113, pages 7345-7352. National Academy of Sciences, 2016.
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.
R.A. Fisher. The Design of Experiments. Oliver and Boyd, Edinburgh. 6th edition, 1951.
Yimin Huang and Marco Valtorta. Pearl's calculus of intervention is complete. In Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence, pages 217-224. AUAI Press, 2006.
Antti Hyttinen, Frederick Eberhardt, and Matti Järvisalo. Do-calculus when the true graph is unknown. In UAL, pages 395 404, 2015.
Amin Jaber, Jiji Zhang, and Elias Bareinboim. Causal identification under markov equivalence. In Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, 2018.
Amin Jaber, Jiji Zhang, and Elias Bareinboim. Causal identification under markov equivalence: Completeness results. In International Conference on Machine Learning, pages 2981-2989, PMLR, 2019a.
Amin Jaber, Jiji Zhang, and Elias Barcinboim. Identification of conditional causal effeets under markov equivalence. In 33rd Annual Conference Neural Information Processing Systems, NeurIPS 2019. Neural Information Processing Systems Foundation, 2019b.
Amin Jaber, Adèle H. Ribeiro, Jiji Zhang, and Hlias Bareinboim. Causal identification under Markov equivalence: Calculus, algorithm, and completeness. Technical report, R-86, CausalAI Lab, Columbia University, 2022.
Yonghan Jung, Jin Tian, and Elias Bareinboim. Estimating identifiable causal effects on Markov equivalence class through double machine learning. In International Conference on Machine Learning, pages 5168-5 5179. PMLR, 2021.
10

---

Judea Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669- 688, 1995.
Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, 2000. 2nd edition, 2009.
Judea Pearl. The seven tools of causal inference, with reflections on machine learning. Communica- tions of the ACM, 62(3):54-60 2019.
Judea Pearl and Dana Mackenzie. The Book of Why: The New Science of Cause and Effect. Basic Books, Inc., New York, NY, USA, 1st edition, 2018. ISBN 046509760X, 9780465097609.
Judea Pearl and James M Robins. Probabilistic evaluation of sequential plans from causal models with hidden variables. In UAI, volume 95, pages 444-453, Citeseer, 1995.
Thomas Richardson and Peter Spirtes. Ancestral graph markov models. The Annals of Statistics, 30 (4):962-1030, 2002.
llya Shpitser and Judea Pearl. Identification of conditional interventional distributions. In Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence, pages 437-444, 2006.
Peter Spirtes, Clark N Glymour, and Richard Scheines. Causation, prediction, and search, volume 81. MIT press, 2001.
Jin Tian. Studies in causal reasoning and learning. PhD thesis, University of California, Los Angeles, 2002.
Jin Tian. Identifying conditional causal effects. In Proceedings of the 20th conference on Uncertainty in artificial intelligence, pages 561-568, 2004.
Jin Tian and Judea Pearl. A general identification condition for causal effects. In AAAI/IAAL pages 567-573, 2002.
TS Verma. Graphical aspects of causal models. Technical Report R-191, UCLA, 1993.
Jiji Zhang. Generalized do-calculus with testable causal assumptions. International Conference on Artificial Intelligence and Statistics, pages 667-674, 2007.
Jiji Zhang. Causal reasoning with ancestral graphs. Journal of Machine Learning Research, 1437-1474, 2008a.
Jiji Zhang. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16-17) 2008b.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes]. [No], or [N/A]. You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license the code and datasets? [N/]]
Please do not modify the questions and only use the provided macros for your answers. Note that the
Checklist section does not count towards the page limit. your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...

---

(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The three contributions claimed in the abstract and reiterated at the end of the introduction are reflected in Section 3 for contribution 1, and in Section for contributions 2 and
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The assumption in lines 103-104 leads to the true PAG which what the theoretical results are based
(b) Did you include complete proofs of all theoretical results? [Yes] The proofs can be found in the full report [Jaber et al., 2022].
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as a URL)? [Yes] The code is available at https: / //gtthttt..///g//////// cow Caaa/aaaaaaLaaa/PAGG
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "rCfjAIGKucN", "reviewer": "Reviewer_dzjw", "summary": "This paper studies the problem of conditional causal effect identification, which asks to recover P(y|do(x), z) from the observational distribution. There is a sequence of works that propose an algorithm for this problem under the assumption that the underlining causal graph is known. This paper relaxes this assumption by assuming that only the Markov equivalence class of the underlining causal graph is known. More specifically, the paper assumes that the so-called partial ancestral graph (PAG) is known. The paper proposes new calculus, which is a modified version of Zhang's [2007] Calculus. For the new calculus, the authors prove that it is complete and atomic complete. Moreover, they propose an algorithm for the identification of conditional causal effects given a PAG and show that the algorithms is complete, that is if some causal cannot be identified by this algorithm then it is not identifiable in some causal graph in the equivalence class of a given PAG.", "questions": "1) What is the main difference between the algorithm proposed in by Jaber et al. 2019a and your algorithm? If the difference is insignificant, I believe the algorithm of Jaber et al. 2019a deserves more credit in the discussion, in particular, it should be acknowledged that your algorithm is a minor modification. Alternatively, if the difference is significant, I would kindly suggest including a more detailed discussion of the distinction between these algorithms. \n\n2)  Are there any runtime or space complexity guarantees for your algorithm? Is it polynomial time?\n\n3) Is anything known about the approximate version of the problem: how many samples are sufficient to identify the causal effect?\n\n4) Are there any open problems left related to conditional effect identification (that authors consider interesting)? \n\n4) I would kindly suggest renaming Proposition 1 (by Zhang 2007) into a Theorem, as calling it a proposition appears to be a bit judgemental. \n\n5) typo in line 213: X, Y, Y\n\n6) I believe the notation in line 265 is poorly chosen, y serves the role of both a fixed variable and a summation index (which makes no mathematical sense). I kindly suggest renaming the summation index. The same notation problem occurs in other places.  ", "limitations": "I believe the authors should comment on the runtime and sample complexity guarantees of the proposed algorithm. If the problem of establishing such guarantees is not resolved I kindly suggest that the authors acknowledge this. Alternatively, if such guarantees (lower or upper bounds) follow from the prior work it will be useful if they are included in the paper.  ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Significance:* The problem of identifiability of interventional causal effects is an important and long-studied problem. This paper improves over the state-of-the-art result by relaxing the assumption that the ground truth causal graph is known. Instead, the paper assumes that only the partial ancestral graph is known. This is a significant relaxation of the assumption as the true underlining causal graph is frequently not known, while PAG can be recovered from conditional independencies of variables. Zhang [2007] proposed a calculus to solve the problem considered in this paper which relies on the notion of ``possibly m-connected paths\". However, Zhang's calculus is not complete, i.e., it is possible to contract a PAG in which the effect is identifiable but is not deducible from Zhang's calculus. \n\nThe key observation of this paper is that if one relies on the notion \"definite m-connected paths\" instead of \"possibly m-connected paths\", then the minor modification of Zhang's calculus becomes a complete calculus. Moreover, the paper proposes an algorithm that uses the rules of the newly introduced calculus to recover causal effect and shows that this algorithm is complete.\n\n*Clarity:* Despite the fact the paper is reasonably well-written it is extremely technical, and as a result quite hard to read. I was not able to verify the correctness of the proofs in the appendix within a reasonable time.  \n\n*Originality:* The paper relies mostly on ideas that are well-known in the field. The proposed algorithm appears to be a minor modification of the prior algorithm by Jaber et al. 2019a. However, the proposed calculus and its completeness seem to be novel.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "X_gxr0T_n9U", "reviewer": "Reviewer_Hoya", "summary": "This work studies the question of identification of conditional causal effects given a PAG. Authors propose sound and complete algorithm for the identification of the causal effects of the form P(y|do(x), z). \n", "questions": "It is important to provide high-level intuition about the difference between the algorithm for identifying conditional causal effects proposed in “Identification of Conditional Causal Effects under Markov Equivalence” by A. Jaber and the algorithm proposed in this work.\n\n\nIt will improve the readability to  add more details of what has been already done (like Algorithm 1) and what is newly proposed in the paper.\n\nPapers on identifiability commonly have an assumption that the underlying DAG is semi-Markovian. \nI would like to ask whether it is also needed here and whether this has any effect (limitation) on the set of PAGs which are considered in this work? Will the proofs still hold if the underlying DAG of the corresponding PAG was not semi-Markovian?\n", "limitations": "Please see above comments.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "It studies an important and quite interesting problem in causality which is causal effect identification in PAGs. \n \nAuthors propose new set of do-calculus rules for PAGs and prove their soundness and completeness in terms of identifiability of conditional causal effects. Also they propose sound and complete algorithm for the identification of causal effects P(y|do(x), z) given PAG. \n\n\nThere are statements that require more references. For example, the IDP algorithm is similar (except slight changes in one line)  to the algorithm in “Causal Identification under Markov Equivalence: Completeness Results” by A. Jaber. This needs to be clarified in the main text. \n\nResults resemble the ones presented by Shpitser for identification of the conditional causal effects in DAGs. Moreover, the problem of identification of causal effects in PAGs has been addressed before. Therefore, the natural question is the contribution of this work. It is very important to clearly mention what is the main difference between the proposed method and the other work and what is the significant of this work compared to the others, e.g., proofs are different and more involved, assumptions have been relaxed, ...\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PBQrtl8m59h", "reviewer": "Reviewer_CdvZ", "summary": "This is a paper about the identification of causal queries in structural causal models. If most of the existing works assume the availability of the causal graph, here only the PAG (partial ancestral graph) structure (corresponding to a collection of CGs) is assumed to be available. The authors derive an analogous of do-calculus for such setup. This is an extension of Zhang's calculus, but here completeness guarantees are provided. Algorithms for the identification of causal effects are provided.", "questions": "- It is not perfectly clear to me whether or not these results can be also applied to counterfactual queries (I think so but this point might be made explicit).\n- The considered approach allows to address identifiability when the causal graph is not known and only the PAG is available. As I understand, PAG identifiability corresponds to identifiability on all the CGs compatible with the PAG and the fact that the query would give the same result on each CG. What I don't understand is whether non-identifiability in PAGs, means that there is at least a non-identifiable CG compatible with the PAG or it might be the case that all the CGs are identifiable but leading to different values. A clarification on these points would be helpful, at least from my point of view. ", "limitations": "I don't see critical issues in terms of societal impact.", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n- Although representing an evolution of existing results (Zhang's results and calculus for DAGs and Jaber's algorithms and completeness result) the results in this paper are clearly novel and authors' final claim about their paper \"clos[ing] the problem of effect identification under Markov equivalence\" is hard to question. This makes the contribution highly significant.\n\n- The paper is very technical, but the results and the proofs seem to be correct (I only partially checked to long proofs in the supplementary material). The the derivations and the notation is quite accessible to people working with SCMs. I also appreciate the insights provided by the different examples reported in the paper.\n\nWeaknesses\n\n- While the statements of the theorems and the examples are generally very clear, the presentation of the algorithms can be probably improved.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7Ijg-5tAFU", "reviewer": "Reviewer_9ZqV", "summary": "The manuscript provides a sound and complete calculus and algorithm for identifying conditional causal effects of the form $p(\\bf{y} | do(\\bf{x}), \\bf{z})$ in partial ancestral graphs (PAGs), i.e. a Markov equivalence class of maximal ancestral graphs (MAGs). This generalizes prior work on causal effect identification in different kinds of graphs and equivalence classes thereof.", "questions": "See above.", "limitations": "I am not convinced that the brief reference to an independence oracle constitutes a thorough discussion of the method’s limitations. Some elaboration would be welcome here, as well as further comments on if/how the method can be used for counterfactual effect identification, computational efficiency, etc.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Completeness results for conditional effect identification in PAGs are notably lacking, despite strong progress in this area by Zhang (2007) and Jaber et al. (2019a, 2019b). Providing such a result – not just for an abstract set of rules but in an efficient algorithm – constitutes a major contribution. Since the FCI algorithm outputs a PAG, CIPD could plausibly be incorporated into a causal discovery pipeline for effect estimation over a learned Markov equivalence class. This could be of great use to practitioners in a variety of fields. The manuscript is well-researched and well-written, quite clear and easy to follow despite considerable technicalities. I commend the authors for their strong and original work.\n\nIf anything, I wonder if a conference submission is really the right venue for this, given how many follow up questions I have! I fully appreciate that space constraints prevent the authors from tackling all the problems that arise in causal reasoning with PAGs, but I strongly encourage them to consider a journal length follow up article, along the lines of Zhang (2007) or Shpitser & Pearl (2008). Short of that, some revisions to the present manuscript at least addressing these concerns would be welcome: \n\n-The do-calculus is famously complete for effect identification across all three levels of the causal hierarchy (Shpitser & Pearl, 2008). How, if at all, could the methods proposed here be leveraged for counterfactual inference in PAGs? While a complete answer may lie beyond the scope of this manuscript, some discussion of the problem would be interesting, if only as a direction for future work. \n\n-There is some discussion in the manuscript of an R implementation. Mentioning this without providing any empirical results or supplemental code is a bit frustrating, as it’s unclear how reviewers are meant to evaluate the performance or usability of the CIDP algorithm. I would either include this material as part of the submission or cut the reference altogether. \n\n-There has been considerable work in recent years on CATE estimation. Could methods like inverse propensity weights or double machine learning be used to estimate conditional causal effects in PAGs, at least under certain conditions? Again, perhaps beyond scope to go too deep into this, but a natural follow up that will likely occur to many readers.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept