--- title: "A Graphical Criterion for Effect Identification in Equivalence Classes of Causal Diagrams" authors: - "Amin Jaber" - "Jiji Zhang" - "Elias Bareinboim" doi: "10.24963/ijcai.2018/697" url: "https://ijcai.org/proceedings/2018/697" pdf: "https://ijcai.org/proceedings/2018/0697.pdf" venue: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence" year: 2018 pages: "5024-5030" track: "Main track" keywords: - "Uncertainty in AI: Graphical Models" - "Uncertainty in AI: Bayesian Networks" - "Knowledge Representation and Reasoning: Action, Change and Causality" --- # A Graphical Criterion for Effect Identification in Equivalence Classes of Causal Diagrams Amin Jaber, Jiji Zhang, Elias Bareinboim *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence*, pages 5024-5030. DOI: [10.24963/ijcai.2018/697](https://doi.org/10.24963/ijcai.2018/697) ## Abstract Computing the effects of interventions from observational data is an important task encountered in many data-driven sciences. The problem is addressed by identifying the post-interventional distribution with an expression that involves only quantities estimable from the pre-interventional distribution over observed variables, given some knowledge about the causal structure. In this work, we relax the requirement of having a fully specified causal structure and study the identifiability of effects with a singleton intervention (X), supposing that the structure is known only up to an equivalence class of causal diagrams, which is the output of standard structural learning algorithms (e.g., FCI). We derive a necessary and sufficient graphical criterion for the identifiability of the effect of X on all observed variables. We further establish a sufficient graphical criterion to identify the effect of X on a subset of the observed variables, and prove that it is strictly more powerful than the current state-of-the-art result on this problem. ## Full text ## 1 Introduction Establishing cause-and-effect relations is one prominent task throughout data-intensive sciences and engineering. In medicine, for example, one commonly needs to evaluate the effectiveness of a new drug, trying to disentangle its healing effect from that due to other factors (perhaps diet and hygiene) that may somehow correlate with the administration of the drug. In Artificial Intelligence, one may need to learn the effect of a robot's actions, while not having control over what may motivate that robot to act in the way it is behaving. These are a few applications of causal inference. There is a growing number of methods and techniques that allow researchers to reason with cause-and-effect relationships in a principled and efficient manner [Pearl, 2000; Spirtes et al., 2001; Bareinboim and Pearl, 2016]. One classical method to infer causal effects is to perform randomized experiments [Fisher, 1951], where the action variables are randomized (e.g., the drug is randomly assigned to patients) and the outcomes observed (e.g., recovery of the patients). In many situations, however, it is not feasible to carry out an experiment of this sort for ethical, technological, financial, or other reasons. An alternative strategy proposed to estimate the effect of interest is to combine non-experimental (observational) data with some information about the underlying causal model [Pearl, 1993]. The primary challenge here is the existence of unobserved (latent) variables, which generates spurious association between action and outcome. The difference between the association between X and Y and the effect of X on Y is known as confounding bias. For example, despite the strong correlation observed between ice-cream consumption and drowning on the beach, no one really believes that eating ice-cream causes drowning during the holiday season. Formally, deciding whether a causal distribution is computable from a combination of the observational distribution and a causal model is known as the problem of identification of causal effects (identification, for short) [Pearl, 2000]. The problem of identification has been extensively studied in the literature, and a number of criteria have been proposed [Pearl, 1993; Pearl and Robins, 1995; Galles and Pearl, 1995; Kuroki and Miyakawa, 1999; Halpern, 2000], including the celebrated back-door criterion and the do-calculus [Pearl, 1995]. In a series of results, a novel graphical decomposition strategy was developed to solve the problem of identification given a causal diagram, along with completeness results for both observational and interventional identification [Tian and Pearl, 2002; Huang and Valtorta, 2006; Shpitser and Pearl, 2006; Bareinboim and Pearl, 2012]. Despite the generality of such results, their applicability is contingent upon the explicit articulation of a causal model, which is, unfortunately, not always available in many practical, large-scale settings. In fact, if one attempts to learn the causal structure from observational data, allowing for the possibility of latent confounders, in general only an equivalence class of causal diagrams (with latent variables) can be consistently inferred. A useful graphical representation of such an equivalence class is known as a partial ancestral graph (PAG). Identification from an equivalence class of causal diagrams represented by a PAG is considerably more challenging than from a single causal diagram due to the structural uncertainty of both the direct causal relations among the variables and the presence of latent variables that confounds causal relations between observed variables. Still, there is a growing interest in identifiability results in the context of equivalence classes. [Zhang, 2008a] extended the do-calculus to PAGs, but, in practice, it is computationally hard to decide whether there exists (and, if so, find) a sequence of applications of the rules of the generalized calculus to identify the causal distribution. Another line of work [van der Zander et al., 2014; Maathuis and Colombo, 2015; Perkovi´c et al., 2015] established a generalized back-door criterion for PAGs, and provided a sound and complete algorithm to find a back-door adjustment set, should such a set exist. However, the back-door criterion is not nearly as powerful as the do-calculus, since no adjustment set exists for many identifiable causal effects. 1 In this paper, we generalize to PAGs the powerful identification strategy for singleton interventions developed in DAGs [Tian and Pearl, 2002]. This new approach is computationally more attractive than do-calculus as it provides an algorithm to identify a causal effect, if identifiable. It is also more powerful than the generalized back-door criterion, as we show later. Specifically, we make the following contributions: 1. We derive a complete (necessary and sufficient) graphical criterion to identify the effect of a single variable X on the set of all observed variables V (or, Px(v)). 2. We derive a graphical criterion to identify the effect of X on a subset of observed variables S (i.e. Px(s)) and show that it subsumes the state-of-the-art adjustment criterion. ## 2 Preliminaries In this paper, bold capital letters denote sets of variables, while bold lowercase letters stand for particular assignments to those variables. Whenever it is clear from the context, we write P (V = v) as P (v). ## 2.1 Structural Causal Models We use the language of Structural Causal Models (SCM) ([Pearl, 2000], pp. 204-207) as our basic framework. Formally, an SCM M is a 4-tuple 〈U, V, F, P (u)〉, where U is a set of exogenous (latent) variables and V is a set of endogenous (measured) variables. F represents a collection of functions F = {fi} such that each endogenous variable Vi ∈ V is determined by a function fi ∈ F, where fi is a mapping from the respective domain of Ui ∪ Pai to Vi, Ui ⊆ U, Pai ⊆ V \ Vi, and the entire set F forms a mapping from U to V. The uncertainty is encoded through a probability distribution over the exogenous variables, P(u), which induces a probability distribution over the measured (observed) variables, P(v). A causal diagram associated with an SCM encodes the structural relations among V ∪ U, in which an arrow is drawn from each member of Ui ∪ Pai to Vi, where Pai denotes the endogenous parents of Vi in the causal diagram. We assume the underlying structural system is acyclic. The observational distribution, P(V), is a marginal over V of the joint distribution of V∪U, and it factorizes according to the causal diagram. 1 Another promising approach is based on SAT solvers [Hyttinen et al., 2015]. Given its somewhat distinct nature, a closer comparison lies outside the scope of this paper. Within the structural semantics, performing an action X=x is represented through the do-operator, do(X=x), which encodes the operation of replacing the original equation for X by the constant x and induces a submodel Mx. The resulting distribution is denoted by Px, which is the main target for identification in this paper. For a more detailed discussion of structural causal models, we refer readers to [Pearl, 2000; Spirtes et al., 2001; Bareinboim and Pearl, 2016]. ## 2.2 Identification Given a Causal DAG We will build on the notion of c-components and the graphical condition for the identification of Px(v) developed in [Tian and Pearl, 2002]. Definition 1 (C-Component). In a causal DAG, two observed variables are said to be in the same confounded component (c-component) if and only if they are connected by a bidirected path, i.e. a path composed solely of such bi-directed treks as Vi ← Uij → Vj , where Uij is an exogenous variable. For convenience we will often refer to a bi-directed trek like Vi ← Uij → Vj as a bi-directed edge between Vi and Vj . Proposition 1 (Tian and Pearl). Given a causal diagram G, let V1 < V2 < · · · < Vn be a topological order over V, and let V (i) = {V1, . . . , Vi} with i = 1, . . . , n and V (0) = φ. Px(v) is identifiable given G if and only if X is not in the same c-component with any of its children. If identifiable, the effect is given by where SX is the c-component that X belongs to and x′ ranges over all the values of X. ## 2.3 Ancestral Graphs We now introduce a graphical representation of equivalence classes of causal diagrams. A mixed graph can contain directed (→) and bi-directed edges (↔). A is a spouse of B if A ↔ B is present. An almost directed cycle happens when A is both a spouse and an ancestor of B. An inducing path relative to L is a path on which every node V /∈ L (except for the endpoints) is a collider on the path (i.e., both edges incident to V are into V ) and every collider is an ancestor of an endpoint of the path. A mixed graph is ancestral if it doesn't contain a directed or almost directed cycle. It is maximal if there is no inducing path (relative to the empty set) between any two non-adjacent nodes. A Maximal Ancestral Graph (MAG) is a graph that is both ancestral and maximal. A MAG entails a conditional independence model by a generalization of dseparation called m-separation, and MAG models are closed under marginalization [Richardson and Spirtes, 2002]. Algorithm 1 is a procedure for marginalization of MAGs. Given a causal DAG G(V, L) where V and L are observed and latent variables, respectively, we can marginalize out L and obtain a MAG MG over V by Alg. 1. This MAG retains ## Algorithm 1: MAG Marginalization Input : MAG G over V∪L Output: MAGMG over V 1- for pair X, Y ∈ V: X and Y adjacent inMG iff there exist an inducing path between them relative to L in G. - 2- for each pair of adjacent nodes X, Y ∈MG: 1. X → Y if X is ancestor of Y in G. 2. X ← Y if Y is ancestor of X in G. 3. X ↔ Y otherwise. both the independence and the ancestral relations among variables in V that are entailed by the original DAG. In general, a causal MAG represents a set of causal DAGs with the same set of observed variables that entail the same independence and ancestral relations among the observed variables. Different MAGs may be Markov equivalent in that they entail the exact same independence model. A partial ancestral graph (PAG) represents an equivalence class of MAGs [M], which shares the same adjacencies as every MAG in [M] and displays all and only the invariant edge marks. Definition 2 (PAG). Let [M] be the Markov equivalence class of an arbitrary MAG M. The PAG for [M], P, is a partial mixed graph such that: - i. P has the same adjacencies as M (and hence any member of [M]) does. - ii. An arrowhead is in P iff it is shared by all MAGs in [M]. - iii. A tail is in P iff it is shared by all MAGs in [M]. - iv. A mark that is neither an arrowhead nor a tail is recorded as a circle. A PAG is learnable from the conditional independence and dependence relations among the observed variables [Zhang, 2008b], and represents an equivalence class of DAG models with the same observed variables. Given a 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 a possible ancestor of Y if X = Y or there is a potentially directed path from X to Y . We write An(Y) to denote the set of possible ancestors of set Y. A set A is ancestral if An(A) = A. Y is called a possible child of X and X a possible parent of Y if they are adjacent and the edge is not into X. A directed edge X → Y in a MAG or PAG is visible if there exists no DAG G(V,L) in the corresponding equivalence class where there is an inducing path between X and Y that is into X relative to L. This implies that a visible edge is not confounded (i.e. X ← Ui → Y doesn't exist, for any Ui ∈ L). Which directed edges are visible is easily decidable by a graphical condition [Zhang, 2008a], so we will simply mark visible edges by v. For brevity, we refer to any edge that is not a visible directed edge as invisible. If the edge marks on a path between X and Y are all circles, we call the path a circle path. For convenience, We use an asterisk (*) to denote any of the possible marks of a PAG (◦, >, -) or a MAG (>, -). Figure 1: Causal query Px(v) over PAG P. ![Image](https://ijcai.org/proceedings/2018/fulltext/697/image_000000_bedd592a5b06741e3e13b1a9ae88031a8ffee2673510cd0d8a54230cbd0bcd5c.png) ## 3 Identification of Px(v) We first define the notion of identification in PAGs, which generalizes the model-specific notion [Pearl, 2000, pp. 70]. Definition 3. Given a PAG P over V and a query Pt(s) where T, S ⊂ V. Pt(s) is identifiable in PAG P if and only if Pt(s) is identifiable in all the Markov equivalent DAGs with the same expression. Let V denote the set of all nodes in a given PAG P. In this section, we generalize Proposition 1 to PAGs and derive an identification criterion for the effect of X on all variables in V \ X, denoted by Px(v). The following challenges are immediate when considering this more general setting: 1. Structural uncertainty regarding c-components. 2. Lack of a topological order over the variables with respect to a PAG. To address the first challenge, we generalize the notion of c-component for MAGs and PAGs. Definition 4 (PC-Component). Given a MAG or a PAG, two nodes X and Y are in the same possible c-component (pccomponent) if there is a path between the two variables such that (1) all non-endpoint nodes along the path are definite colliders, and (2) none of the edges, if directed, are visible. Given that all the non-endpoint nodes along the path, if any, are colliders by the first condition of Def. 4, the second condition is only concerned about the first and the last edges on the path, as all the other edges must be bi-directed. For instance, V1 and V4 in Fig. 1 are in the same pc-component due to the path 〈V1, X, V5, V6, V4〉. The following proposition shows that being in the same pc-component in a MAG or PAG is necessary for being in the same c-component in some DAG in the corresponding equivalence class. Proposition 2. Let X and Y be two nodes in a MAG or PAG P. If X and Y are not in the same pc-component in P, then X and Y are not in the same c-component in any DAG in the equivalence class. 2 For example, X and V3 in Figure 1 are not in the same pc-component, and consequently they are not in the same ccomponent in any DAG in the equivalence class. The converse of Proposition 2 does not hold for PAGs (though it does for MAGs). However, the following weaker proposition holds and is sufficient for our purpose: Proposition 3. Let X and Y be two nodes in a MAG or PAG P. If X and Y are in the same pc-component in P, and either X and Y are adjacent or there is no circle path between them, then X and Y are in the same c-component in some DAG in the equivalence class. 2 See [Jaber et al., 2018] for all the proofs. ## Algorithm 2: PTO Algorithm Input : PAG G over V Output: PTO over G - 1- Create singleton buckets Bi each containing Vi ∈ V. - 2- Merge buckets Bi and Bj if there is a circle edge between them (Bi ∋ X ◦-◦ Y ∈ Bj ). - 3- while set of buckets (B) is not empty do (i) Extract Bi with only arrowheads incident on it. (ii) Remove edges between Bi and other buckets. end - 4- The partial order is B1 < · · · < Bm in reverse order of bucket extraction, i.e. B1 is the last extracted bucket. For example, the condition in Proposition 3 is satisfied for X and V4 in Figure 1. Hence, there exists a DAG in the equiv- alence class where X and V4 are in the same c-component. A special case of pc-component is the following: Definition 5 (DC-Component). In a MAG or PAG, two variables are in the same definite c-component, dc-component, if and only if they are connected with a bi-directed path, i.e. a path composed solely of bi-directed edges. For instance, nodes X and V6 in Figure 1 are in the same dc-component, which implies that they are in the same ccomponent in every DAG in the equivalence class. It is important to consider when nodes are in the same c-component in some or all the DAGs in the equivalence class. In the sequel, we address the second challenge by showing how to construct a partial topological order over a PAG that is valid for all DAGs in the equivalence class. It is easy to see that we can't always find a complete topological order over the nodes in a PAG that is valid for all DAGs (consider e.g., X ◦-◦Y ). Instead, Algorithm 2, called PTO, constructs a partial topological order. We refer to the output of the algorithm as Bucketed PAG (BPAG). Note that each BPAG's bucket is called in the literature as a circle component. Consider the PAG in Fig. 1 where we intend to construct a topological order. All the buckets are singleton sets since there are no circle edges. Hence, a possible extraction order is V1 < V5 < X < V3 < V4 < V6, which is valid for all DAGs in the equivalence class. Lemma 1. The PTO algorithm is sound, i.e. the partial order is valid for all the DAGs in the equivalence class. We are now ready to state the main theorem for the identification of Px(v). Theorem 1. Let a partial topological order over PAG P be B1 < B2 < · · · < Bm, and let B(i) = ⋃{B1, . . . ,Bi}, i = 1 . . .m, and B(0) = ∅. Px(v) is identifiable if and only if X is not in the same pc-component with any of its possible children. When identifiable, the effect is given by where SX is the dc-component of X. Figure 2: Sample PAG for the special cases. ![Image](https://ijcai.org/proceedings/2018/fulltext/697/image_000001_b4019222e3d64f1becc938232bc1521d2800b18d4d6b5a56f0a84616f2b0fade.png) Proof Sketch. Proposition 3 is sufficient to guarantee that if X is in the same pc-component with a possible child in P, then there is a DAG in the equivalence class in which X is in the same c-component with a child, and so Px(v) is not identifiable. Conversely, Proposition 2 entails that if X is not in the same pc-component with any of its possible children in P, then X satisfies the condition of Proposition 1 in every DAG in the equivalence class. We can then show that in every DAG, the identification expression is equivalent to the expression above. See Appendix for details. Consider the PAG in Figure 1. Since X is not in the same pc-component with any of its possible children, namely V3, Px(v) is identifiable by Theorem 1. The dc-component of X is SX = {X, V5, V6} , and we use the topological order derived earlier (i.e. V1 < V5 < X < V3 < V4 < V6). Hence, the expression for the causal effect is given by This example also illustrates why the expression in Thm. 1 discards nodes that are in the pc-component but not in the dccomponent of X. V4 is in the pc-component of X (i.e. X ↔ V5 ↔ V6 ←◦V4) and satisfies the condition in Prop. 3, hence it is in the c-component of X in some DAG in the equivalence class. However, the fact that V4 ⊥⊥ X|(V1, V3, V5) can be used to simplify the expression to that in Thm. 1. ## 3.1 Special Cases In two special cases, analogous to those considered in the context of DAGs [Tian and Pearl, 2002], the expression in Theorem 1 can be considerably simplified. These simpler results are worth mentioning because the more compact identification expressions in these special cases entail a lower sample and computational complexity when evaluating them from data, and because the simpler graphical conditions allow the causal analyst to decide identifiability (yes/no) almost immediately by inspection. Let Pax and Chx denote the sets of possible parents and possible children of X, respectively. Corollary 1. If all the edges incident on X are visible, then Px(v) is identifiable and is given by Proof. The condition implies that X is not in the same pccomponent with any node, including its possible children, and that SX = {X}. Hence, the condition of Th. 1 is satisfied and the identification expression becomes P(v)/P(x|x(i-1) ). Figure 3: Example of Definition 7. ![Image](https://ijcai.org/proceedings/2018/fulltext/697/image_000002_3676e301171f82292d68a441a581628ed18d9e44af75a62a3ec98ee02efd5d29.png) Note that X ⊥⊥ X(i-1) \ Pax| Pax since every path p between X and X(i-1) \ Pax includes either (1) an edge out of X, in which case there is a collider along p in V\X(i) that blocks p, or (2) a directed edge into X which is a definite noncollider along p (pax ∋ Vi → X) and so blocks p. Hence, P(x|x(i-1) ) simplifies to P(x|pax). For example, consider the PAG in Figure 2 and the distribution Pd(v). The effect is identifiable by Corollary 1 as The second case relaxes the previous condition on X but imposes a condition on the possible children of X. Corollary 2. If all the edges incident on the possible children of X are visible, then Px(v) is identifiable and is given by Proof Sketch. The identification criterion of Theorem 1 is satisfied as the nodes in Chx are not in the same pccomponent with any other node, including X. The identification expression can be rewritten as We then simplify the expression using the independence relations among the variables to obtain the expression above. The detailed proof can be found in the Appendix. Consider, for example, the distribution Pc(v) over the PAG in Figure 2. The effect is identifiable and given by ## 4 Identification of Px(s) So far, we have derived a complete criterion to identify Px(v) in a given PAG. Now, suppose that we are interested in estimating the effect of X on a subset of observed variables (S ⊆ V \ X). One may be tempted to surmise that Theorem 1 should be enough for this problem - namely, first identify Px(v), and then marginalize out unintended variables (V \ S ∪ X). For instance, for the query Px(v4) in Fig. 1, Px(v) can be computed first (i.e. Eq. 2), and then V \ {X, V4} can be marginalized out. While this solution is certainly sound when the conditions of the theorem are met, the strategy is not necessary. To see this, consider the query Px(y) over the PAG in Fig. 3a. As we will show later, Px(y) is identifiable despite the non-identifiability of Px(v). The aim of this section is to explain these subtleties and derive a stronger graphical criterion to identify Px(s) where S ⊆ V \ {X} is the outcome set. We start by introducing a new construction called marginal PAG which allows us to systematically eliminate nodes that need not be considered. ## 4.1 Marginal PAG Definition 6 (Marginal PAG). Let [M] be a Markov equivalence class of MAGs over V. For A ⊆ V, let [M]A = {M′A|M′ ∈ [M]} where M′A denotes the MAG over A that results from marginalizing out V \ A in M ′ (Algorithm 1). A marginal PAG for [M] relative to A is the partial mixed graph that has the same adjacencies as every graph in [M]A and displays all and only the shared edge marks in [M]A. Note that in this definition, [M]A is in general not a full equivalence class of MAGs over A, but a subset of an equivalence class. For example, let [M] be the equivalence class represented by the PAG in Fig. 3a. Let A = {V1,X, Y }. Then, every MAG in [M]A, according to the above definition, contains an edge V1∗→ X and an edge X → Y . Consequently, the marginal PAG relative to A is the graph in Fig. 3c. In this case, [M]A is not a full equivalence class because, for example, V1 ← X ← Y is also Markov equivalent to graphs in [M]A but not contained therein. If we consider the full equivalence class of which [M]A is a subset, the corresponding PAG is V1 ◦-◦ X ◦-◦ Y . Therefore, a marginal PAG according to our definition is not an ordinary PAG, and is in general more informative. The following two lemmas describe two cases of constructing a marginal PAG that are relevant to our purpose. Lemma 2. Let A be an ancestral set in a PAG P. The marginal PAG for the equivalence class represented by P relative to A is simply PA, the induced subgraph of P over A. Furthermore, a visible edge in P remains visible in the marginal PAG. Lemma 3. Let P be a PAG over V and let B be a circle component in P that is partitioned into two nonempty sets T and C, i.e. T ∪ C = B and T ∩ C = ∅. If every possible child of C is in B, then the marginal PAG relative to V \ C can be constructed from P as follows: 1. Remove C and all the incident edges, and; 2. Add a circle edge between two non-adjacent nodes in T if there exists a circle path between them where every node along the path is in C. Moreover, all the visible edges in P remain visible in the marginal PAG. Although a marginal PAG is not necessarily an ordinary PAG, for the marginal PAGs constructed according to Lemmas 2 and 3, we can show that they retain a crucial graphical property of ordinary PAGs, namely: Lemma 4. The following property holds in a marginal PAG constructed according to Lemmas 2 and 3: for any three nodes A, B, C, if A∗→ B ◦-∗ C, then there is an edge between A and C with an arrowhead at C, namely, A∗→ C. Furthermore, if the edge between A and B is A → B, then the edge between A and C is either A → C or A◦→ C (i.e., it is not A↔C). Proof. The proof is trivial for the marginal PAG in Lemma 2, for a violation of it in the marginal PAG obviously implies its violation in the original PAG, which is not possible. As for the marginal PAG in Lemma 3, it can only introduce new adjacencies between nodes in the form of circle edges within a circle component (bucket). Hence, a violation of the property in the marginal PAG also implies its violation in the original PAG which is not possible. It follows from Lemma 4 that a marginal PAG constructed by Lemmas 2 and 3 preserves the main properties established for a PAG, and specifically all the properties needed for the derivation in Section 3. We can then define a simplified PAG: Definition 7 (P X Y ). Given a PAG P over V. P X Y , referred to as simplified PAG with respect to X and Y, is the result of applying the marginalization in Lemma 2 relative to An(Y), and then Lemma 3, if applicable, with respect to T = X, where X = {X} ∩ An(Y) and C ∩ Y = ∅. For example, the simplified PAG P X Y for the PAG in Fig. 3a is constructed as follows. The set An(Y ) = {Y,X, V1, V2} is ancestral in P, hence Lemma 2 can be applied, and the marginal PAG over An(Y ), P ′ , is given in Fig. 3b. In P ′ , nodes X and V2 correspond to the sets T and C in Lemma 3, respectively. X is the only possible child of V2 and is contained in the corresponding circle component. So, Lemma 3 is applicable, which yields the simplified PAG in Fig. 3c. ## 4.2 A Sufficient Criterion The relevance of marginal PAGs is due to the following result: Lemma 5. Given a PAG P, Px(s) is identifiable in P if PX (s) is identifiable in P X S where X = {X} ∩ An(S). In other words, we can focus our attention on the component of X that persists in the simplified graph, and ignore all the variables that are marginalized out. For instance, given the query Px(y1) over the PAG Y1◦→ X ←◦Y2, Lemma 5 suggests that we drop X along with Y2 from the simplified PAG and the corresponding marginal distribution, i.e. P(y1). Hence, the interventional distribution for this trivial query is P(y1). We use this observation to prove the main result of this section, an identification criterion for Px(s). Figure 4: Px(y) is not identifiable using the adjustment criterion. ![Image](https://ijcai.org/proceedings/2018/fulltext/697/image_000003_7f516070d968028c770ced6f3b7c76bc2d9345db1f0acfc8d6fe7df4200d6238.png) Theorem 2. Given a PAG P, Px(s) is identifiable if X = {X}∩An(S) is not in the same pc-component with any of its possible children in P X S . Proof. Let V′ be the set of variables in P X S . By Lemma 5, it is sufficient to consider the query PX(s) over P X S . As stated in Subsection 4.1, all the properties required for the correctness of the PTO algorithm and Theorem 1 remain valid in P X S . Since the condition here is just the condition of Thm. 1 over P X S , PX(v′ ) is identifiable using Theorem 1. We then marginalize out V′ \ S ∪ {X} to get PX (s). Given a query Px(s), Thm. 2 provides a sufficient condition over the simplified PAG P X S such that the causal distribution can be computed through the formula in Thm. 1. For non-trivial queries of the form Px(v), note that the simplified PAG remains P and Thm. 2 reduces to Thm. 1. Consider the example in Fig. 3a and the causal query Px(y). The corresponding simplified PAG P X Y is shown in Fig. 3c. We compute Px(y, v1) by applying Thm. 1 over P X Y , then we marginalize out variable V1, obtaining ## 4.3 Criterion Strength The identification criterion for Px(s) in Theorem 2 is strictly more powerful than the generalized adjustment criterion proposed in [Perkovi´c et al., 2016], which is proven to be complete for adjustment. For example, the causal query Px(y1, y2) over the PAG in Figure 4 is identifiable using the criterion in Theorem 2 while it is not identifiable using the adjustment method. On the other hand, the following theorem shows that there is no singleton intervention effect that can be identified using the adjustment method but not identifiable using Theorem 2. Theorem 3. Let P be a PAG over a set of nodes V and let Px(s) be a causal query where X ∈ V, S ⊆ V\X. If Px(s) is not identifiable using Theorem 2, then there exist no set Z that satisfies the generalized adjustment criterion. ## 5 Conclusion In this paper, we investigated the problem of identification of causal distributions with singleton interventions in a Markov equivalence class represented by a PAG. We proved three graphical criteria for the identification of Px(v), where V is the set of all variables, including a general criterion that is necessary and sufficient for the identifiability of Px(v). These results can already be used to identify causal queries in challenging settings that backdoor-like methods cannot solve (e.g., given the PAG in Fig. 4, Px(y1, y2) is identifiable using Corollary 2, but not by adjustment). In addition, we introduced a new construction called marginal PAGs, with which we derived a sufficient graphical condition for the identification of Px(s), where S is a subset of the variables. Our criterion was shown to be strictly stronger than the state-of-the-art adjustment method found in the literature. We expect that our results will be helpful to causal analysts when studying complex, high-dimensional settings where learning the full causal model is often infeasible. ## Acknowledgments We thank the reviewers for all the feedback provided. Bareinboim's research was supported in parts by grants from NSF IIS-1704352 and IIS-1750807 (CAREER). Zhang's research was supported in part by the Research Grants Council of Hong Kong under the General Research Fund LU13600715. ## References 1. [Bareinboim and Pearl, 2012] Elias Bareinboim and Judea Pearl. Causal inference by surrogate experiments: z- identifiability. In Proceedings of the Twenty-Eighth Con- ference on Uncertainty in Artificial Intelligence, 2012. 2. [Bareinboim and Pearl, 2016] Elias Bareinboim and Judea Pearl. Causal inference and the data-fusion problem. Pro- ceedings of the National Academy of Sciences, 113:7345- 7352, 2016. 3. [Fisher, 1951] R.A. Fisher. The Design of Experiments. Oliver and Boyd, Edinburgh, 6th edition, 1951. 4. [Galles and Pearl, 1995] David Galles and Judea Pearl. Test- ing identifiability of causal effects. In Proceedings of the Eleventh conference on Uncertainty in artificial intelli- gence, UAI'95, pages 185-195, 1995. 5. [Halpern, 2000] Joseph Y. Halpern. Axiomatizing causal reasoning. Journal of Artificial Intelligence Research, 12(1):317-337, May 2000. 6. [Huang and Valtorta, 2006] Y. Huang and M. Valtorta. Pearl's calculus of intervention is complete. In Proceed- ings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence, UAI'06, pages 217-224, 2006. 7. [Hyttinen et al., 2015] A. Hyttinen, F. Eberhardt, and M. Järvisalo. Do-calculus when the true graph is unknown. In Proceedings of the Thirty-First Conference on Uncer- tainty in Artificial Intelligence, pages 395-404, 2015. 8. [Jaber et al., 2018] Amin Jaber, Jiji Zhang, and Elias Barein- boim. A graphical criterion for effect identification in equivalence classes of causal diagrams. Technical report, R-32, Purdue AI Lab, Department of Computer Science, Purdue University, 2018. 9. [Kuroki and Miyakawa, 1999] Manabu Kuroki and Masami Miyakawa. Identifiability criteria for causal effects of joint interventions. Journal of the Japan Statistical Society, 29(2):105-117, 1999. 10. Marloes H Maathuis and Diego Colombo. A generalized back-door criterion. The Annals of Statistics, 43(3):1060-1088, 2015. 11. [Pearl and Robins, 1995] Judea Pearl and James Robins. Probabilistic evaluation of sequential plans from causal models with hidden variables. In Proceedings of the Eleventh conference on Uncertainty in artificial intelli- gence, UAI'95, pages 444-453, 1995. 12. [Pearl, 1993] Judea Pearl. Aspects of graphical models con- nected with causality. In Proceedings of the 49th Session of the International Statistical Institute, pages 391-401, 1993. 13. [Pearl, 1995] Judea Pearl. Causal diagrams for empirical re- search. Biometrika, 82(4):669-688, 1995. 14. [Pearl, 2000] Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, 2000. 2nd edition, 2009. 15. [Perković et al., 2015] Emilija Perković, Johannes Textor, Markus Kalisch, and Marloes H Maathuis. A complete generalized adjustment criterion. In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intel- ligence, pages 682-691, 2015. 16. [Perković et al., 2016] Emilija Perković, Johannes Textor, Markus Kalisch, and Marloes H Maathuis. Complete graphical characterization and construction of adjustment sets in markov equivalence classes of ancestral graphs. arXiv preprint arXiv:1606.06903, 2016. 17. [Richardson and Spirtes, 2002] Thomas Richardson and Pe- ter Spirtes. Ancestral graph markov models. Annals of Statistics, pages 962-1030, 2002. 18. [Shpitser and Pearl, 2006] Ilya Shpitser and Judea Pearl. Identification of joint interventional distributions in recur- sive semi-markovian causal models. In Proceedings of the Twenty-First Conference on Artificial Intelligence, 2006. 19. [Spirtes et al., 2001] Peter Spirtes, Clark N Glymour, and Richard Scheines. Causation, prediction, and search, vol- ume 81. MIT press, 2001. 20. [Tian and Pearl, 2002] Jin Tian and Judea Pearl. A general identification condition for causal effects. In Proceedings of the Eighteenth Conference on Artificial Intelligence, AAAI'02, pages 567-573, 2002. 21. [van der Zander et al., 2014] Benito van der Zander, Maciej Liskiewicz, and Johannes Textor. Constructing separators and adjustment sets in ancestral graphs. In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intel- ligence, pages 11-24, 2014. 22. [Zhang, 2008a] Jiji Zhang. Causal reasoning with ances- tral graphs. Journal of Machine Learning Research, 9(Jul):1437-1474, 2008. 23. [Zhang, 2008b] Jiji Zhang. On the completeness of orien- tation rules for causal discovery in the presence of la- tent confounders and selection bias. Artificial Intelligence, 172(16):1873-1896, 2008.