Testing Edges by Truncations

1 Introduction

Causal discovery, that is the problem of learning causal theories from observations, is central to empirical science. In graphical models, which is a popular formalism for representing causal assumptions in the presence of uncertainty, there is a large literature on this problem [Cooper and Dietterich, 1992], [Spirtes et al., 1993], [Suzuki, 1993]. In such models, causal assumptions are represented by means of a directed acyclic graph (dag) called a causal diagram, where nodes are variables of interest, and arrows represent, informally, direct causal influences.

In this setting, causal discovery amounts to learning aspects of the causal diagram from observations summarized as an observable joint probability distribution P (v). The simplest causal discovery problem assumes causal sufficiency,

James M. Robins

Department of Epidemiology Harvard School of Public Health robins@hsph.harvard.edu

e.g. it assumes whenever two observed variables share a common cause, that cause is itself observed. There are two approaches to causal discovery in this setting. The score-based approach [Suzuki, 1993], assigns to each possible graph a score consisting of two terms - the likelihood term which measures how well the graph fits the data, and the model complexity term, which penalizes large graphs. A search is then performed for high scoring graphs. The second, so called constraint-based approach [Spirtes et al., 1993] rules out graphs which are not compatible with constraints observed in the data. Both approaches to causal discovery in the presence of causal sufficiency rely on faithfulness, which is a property stating that a notion of path-separation known as d-separation [Pearl, 1988] in the graph precisely characterizes conditional independence inherent in the distribution which the graph represents.

In the absence of causal sufficiency, the causal discovery problem is significantly harder, especially if, as in this paper, no parametric assumptions are made. One problem is that in this setting graphs may entail constraints which cannot be expressed as conditional independence constraints.

Previous work showed that certain non-independence constraints, which we refer to as Verma constraints, may be represented by an identified dormant independence (i.e., a conditional independence in an interventional distribution [Robins, 1986], [Spirtes et al., 1993], [Pearl, 2000] that can be used to test for the presence of an edge in the causal diagram [Robins, 1999], [Tian and Pearl, 2002b], [Shpitser and Pearl, 2008]. We show that there exist identified dormant independencies that cannot be used to test for the presence of an edge and thus do not represent a Verma constraint.

Using the notion of edge testing, explored in [Shpitser and Pearl, 2008], we characterize which dormant independences do give rise to Verma constraints. Finally, we prove that every such dormant independence can be obtained from the joint distribution by a sequence of simple operations we call truncations, and construct an algorithmwhich does this. This implies that an algorithm trying to recover correct causal structure from data which uses Verma constraints can restrict itself to searching over possible truncations.

2 An Example of Edge Testing

Consider the causal graph in Fig. 1 (a), where a bidirected arc corresponds to an unobserved cause of W and Y . Any model compatible with this graph imposes certain constraints on its observable distribution P(x, w, z, y), here assumed positive. Some of these constraints are in the form of conditional independences. For instance, in any such model X is independent of Z given W , which means P (x|w) = P (x|w, z).

However, there is an additional constraint implied by this graph which cannot be expressed in terms of conditional independence in the observable distribution. This constraint, noted in [Verma and Pearl, 1990], [Robins, 1999], states that the expression ∑w P (y|z, w, x)P (w|x) is a function of y and z, but not of x. In fact, constraints of this type do emanate from conditional independences, albeit not in the original observable distribution, but in a distribution resulting from an intervention.

An intervention, written do(x) [Pearl, 2000], is an operation which forces variables X to attain values x regardless of their usual behavior in a causal model. The result of applying an intervention do(x) on a model M with a set of observable variables V is a submodel Mx, with stochastic behavior of V described by an interventional distribution written as Px(v) or P(v|do(x)). The graph induced byMx is almost the same as the graph induced by M, except it is missing all arrows incoming to X, to represent the fact that an intervention sets the values of X independently of its usual causal influences, represented by such arrows. We will denote such a graph as Gx. We will also consider the so called stochastic interventions, where values of X are set according to a new distribution P ∗ (x). We denote this intervention as do(x ∼ P ∗ ), and its result by P(v|do(x ∼ P ∗ )) or Px∼P ∗(v). The graphical representation of stochastic interventions is the same as that of ordinary interventions.

A key idea in causal inference is that in certain causal models, some interventional distributions can be identified from the observational distribution. Consider for instance a model M inducing the graph in Fig. 1 (a). If we intervene on Z in M, we obtain the submodel Mz inducing the graph in Fig. 1 (b). The distribution of the unfixed observables in this submodel, Pz(x, w, y), is identifiable from P(x, w, z, y) and equals to P (y|z, w, x)P (w|x)P (x) [Pearl and Robins, 1995], [Tian and Pearl, 2002a]. Moreover, by d-separation [Pearl, 1988], the graph in Fig. 1 (b) implies that X is independent of Y in Pz(x,w, y), or Pz(y|x) = Pz(y). But it's not hard to show that Pz(y|x) is equal to ∑w P(y|z,w, x)P(w|x), which means this expression depends only on z and y. What we have just shown is that independence in Pz(x,w, y), which is an identifiable distribution, leads to a constraint on observational distributions in the original, unmutilated model M. The same reasoning applies to stochastic interventions, since all identification results carry over without change. Conditional independences in interventional distributions are called dormant [Shpitser and Pearl, 2008]. Given an appropriate notion of faithfulness, we can conclude from this constraint that there should be no edge between X and Y in Fig. 1 (a). In the remainder of the paper, we explore this sort of constraint-based testing in more detail.

2.1 AVacuous Dormant Independence

It turns out that not every dormant independence leads to a Verma constraint. Consider the graph in Fig. 2 (a). In this graph, variables Y and Z cannot be d-separated by any conditioning set. However, it's not difficult to see that Y and Z are independent if we fix X and W, in other words Y is independent of Z in P(y, z|do(x, w)). Moreover, P(y, z|do(x,w)) is identifiable in this graph, and equal to P(y|x)P(z|w). In other words, there exists an (identifiable) dormant independence between Y and Z. However, if we translate what this independence asserts about the joint distribution P(x, y, z,w) we get that Y and Z are independent in the distribution P(y|x)P(z|w) where x, w are held constant and y, z are allowed to vary. But this independence trivially holds by construction regardless of what P(v) we choose. In other words, this dormant independence does not constrain P (x, y, z, w) in any way.

Which dormant independences do give rise to Verma constraints? For intuition we consider the easier case of conditional independence. In faithful models the presence of conditional independence between X and Y implies the lack of an edge connecting these variables. Similarly, we would expect (identifiable) dormant independences between two variables which lead to constraints to imply the lack of an edge between those variables. However, unlike the conditional independence case, identifying dormant independences relies on the absence of certain edges (since the process of identifying interventional distributions relies on causal assumptions embodied by missing edges in the causal diagram). The key point is that identifying the dormant independence used to test a particular edge e cannot rely on the absence of that edge in the process of identification!

In particular, the distribution P(y, z|do(x,w)) in Fig. 2 (a) is only identifiable if we assume there is no edge between Y and Z (the very thing we would be trying to test by a dormant independence between Y and Z). In particular, if we add a directed edge from Y to Z as in Fig. 2 (b), P(y, z|do(x,w)) becomes non-identifiable since the graph becomes a Z-rooted C-tree [Shpitser and Pearl, 2006b]. Similarly, P (y, z|do(x, w)) becomes non-identifiable if we add a bidirected edge from Y to Z as in Fig. 2 (c).

3 Preliminaries

One way of formalizing causal inference is with probabilistic causal models (PCMs). Such models consist of two sets of variables, the observable set V representing the domain of interest, and the unobservable set U representing the background to the model that we are ignorant of. Associated with each observable variable Vi in V is a function fi which determines the value of Vi in terms of values of other variables in V ∪ U. Finally, there is a joint probability distribution P(u) over the unobservable variables, signifying our ignorance of the background conditions of the model.

The causal relationships in a PCM are represented by the functions fi, each function causally determines the corresponding Vi in terms of its inputs. Causal relationships entailed by a given PCM have an intuitive visual representation using a graph called a causal diagram. Causal diagrams contain two kinds of edges. Directed edges are drawn from a variable X to a variable Vi if X appears as an input of fi. Directed edges from the same unobservable Ui to two observables Vj , Vk can be replaced by a bidirected edge between Vj to Vk. We will consider models which induce acyclic graphs where P(u) = ∏i P(ui), and each Ui has at most two observable children. A graph obtained in this way from a model is said to be induced by said model.

The importance of causal diagrams stems from the fact that conditional independences between observable variables correspond to graphical features in the diagram. Since the rest of the paper will rely heavily on this correspondence, we introduce probabilistic and graphical notions we will need to make use of it. A set X is independent of Y conditional on Z (written as X ⊥⊥P Y|Z) if P(x|y, z) = P(x|z). We will use the following graph-theoretic notation. An(.)G, De(.)G, P a(.)G stand for the set of ancestors, descendants and parents of a given variable set in G. The sets An(.)G and De(.)G will be inclusive, in other words, for every An(X)G,De(X)G, X ∈ An(X)G and X ∈ De(X)G. The set C(X)G stands for the C-component of X [Tian and Pearl, 2002a], that is the maximal set of nodes containing X where any two nodes are pairwise connected by a bidirected path contained in the set. A graph Gx is the subgraph of G containing only nodes in X and edges between them.

It's possible to show that whenever edges in a causal diagram are drawn according to the above rules, the distribution P(u, v) induced by P(u) and the fi functions factorizes as ∏Xi ∈V∪U P(xi|Pa(xi)). This Markov factorization implies that conditional independences in P(u, v) are mirrored by a well-known graphical notion of "path blocking" known as dseparation [Pearl, 1988], which we will not reproduce here. 1

Two sets X, Y are said to be d-separated given Z (written X ⊥G Y|Z) in G if all paths from X to Y in G are d-separated by Z. Paths or sets which are not d-separated are said to be d-connected. The relationship between d-separation and conditional independence is provided by the following theorem.

Theorem 1 (Pearl) Let G be a causal diagram. Then in any model M inducing G and P , if X ⊥G Y|Z, then X ⊥⊥P Y|Z.

1 In fact d-separation is defined for dags, although a natural generalization exists for mixed graphs with bidirected arcs [Richardson and Spirtes, 2002].

Using d-separation as a guide, we can look for a conditioning set Z which renders given sets X and Y independent by only examining the causal diagram, without having to inspect the probability distribution P (v).

A causal dag with an arbitrary set of hidden variables has a graphical representation called the latent projection [Pearl, 2000], such that the projection only contains nodes corresponding to observable variables, it contains only directed and bidirected arcs, is acyclic, and preserves the set of dseparation statements over observed nodes in the dag. In this sense the mixed graphs we consider include causal models with arbitrary latent variables.

We examine probabilistic independences in distributions resulting from not only conditioning but a second, powerful operation of intervention, defined in the previous section. An intervention is a more powerful operation than conditioning, for the purposes of determining probabilistic independence. This is because conditioning on a variable can d-separate certain paths, but also d-connect certain paths (due to the presence of the so called collider triples). On the other hand, interventions can only block paths, since incoming arrows are cut by interventions, destroying all colliders involving the intervened variable. Some interventions can be computed from P(v) and the graph G, due to a general notion called identifiability, defined as follows.

Definition 1 (identifiability) Consider a class of models M with a description T , and two objects φ and θ computable from each model. We say that φ is θ-identified in T if all models in M which agree on θ also agree on φ.

If φ is θ-identifiable in T , we write T, θ ⊢id φ. Otherwise, we write T, θ ̸⊢id φ. Often, the model class T corresponds to a causal graph, θ is the observational distribution P(v), and φ is the causal effect of interest. For example, in Fig. 1 (a), G, P(v) ⊢id Pz(x,w, y). Conditional independences in interventional distributions are called dormant in [Shpitser and Pearl, 2008].

Definition 2 (dormant independence) A dormant independence exists between variable sets X, Y in P(v) obtained from the causal graph G if there exist variable sets Z,W (with W possibly intersecting X ∪ Y) such that Pw∼P ∗ (y|z) = Pw∼P ∗(y|x, z). If P(v), G ⊢id Pw∼P ∗(y, x|z), the dormant independence is identifiable; we denote this as X ⊥⊥w,G,P Y|Z. 2

A natural graphical analogue of d-separation exists for dormant independence.

Definition 3 (d∗ -separation) Let G be a causal diagram. Variable sets X, Y are d∗ -separated in G given Z, W (written X ⊥w,G Y|Z), if we can find sets Z,W, such that X ⊥Gw Y|Z, and P (v), G ⊢id Pw∼P ∗ (y, x|z).

Note that despite the presence of probability notation in the definition, this is a purely graphical notion, since identification can be determined using only the graph [Shpitser and Pearl, 2006a]. A theorem analogous to Theorem 1 links d∗ - separation and identifiable dormant independence [Shpitser and Pearl, 2008]. 3

2 Earlier work [Shpitser and Pearl, 2008] used ⊥⊥w. We use this modified notation to emphasize the fact that dormant independence unlike conditional independence is both graph and distribution dependent.

Theorem 2 Let G be a causal diagram. Then in any model M inducing G, if X ⊥w,G Y|Z, then X ⊥⊥w,G,P Y|Z. 4

In the next section we consider the question of edge identification, namely determining which dormant independences can test non-adjacency of variable pairs.

4 Edge Identification

Typically, questions of identifiability are posed about distributions obtained from interventions, such as causal effects and counterfactuals. In such cases, a given distribution P is identifiable in a model class M if every model in the class agrees on P . This can be extended to any aspect of the model, such as an edge. An edge e is said to be θ-identifiable in M (written θ ⊢id e) if every model in M which agrees on θ agrees on the presence of e.

For faithful, causally sufficient models, P(v)-identified edges are those edges on which the Markov equivalence class of models [Pearl, 1988] consistent with P(v) agree.

We are interested in exploring which edges can be identified if, in addition to P(v), we assume partial causal knowledge in the form of a graph, where every edge is either correctly specified, or extraneous. We call such graphs valid. As we saw in an earlier example, such problems may be solved using constraints implied by dormant independence, given an appropriate notion of faithfulness. It turns out this notion is identifiable faithfulness. 5 A model is identifiable faithful if the subgraph corresponding to every identifiable Px∼P ∗(y) is faithful to Px∼P ∗(y). 6 We can give a general theorem for testing edges in valid graphs of such models.

Theorem 3 Let M be an identifiable faithful model with observable distribution P(v), G a graph valid for M, and e a (possibly extraneous) edge between X and Y in G. Then G, P(v) ⊢id e if there exist variable sets W, Z, such that G, P(v) ⊢id Pw(x, y|z), X ⊥Gw\{e} Y |Z, and Gw ̸= Gw \ {e}. Gw \{e} is obtained by removing incoming arrows to W, and then removing e from G.

Proof: Assume such sets W, Z exist. If X and Y are independent in Pw∼P ∗(x, y|z), then due to results in [Shpitser and Pearl, 2006a], there exists a set Z′ such that G, P(v) ⊢id Pw,z′(x, y, z \ z′ ) iff G, P(v) ⊢id Pw(x, y|z). By identifiable faithfulness of M, the true graph G′ corresponding to Pw,z′(x, y, z \ z′ ) is faithful to Pw,z′(x, y, z \ z′ ), so it cannot contain e. Since Z cannot intersect {X, Y }, and we assumed Gw ̸= Gw \ {e}, do(w ∪ z′ ) does not cut e. We conclude that e is extraneous in G.

3 The reference did not consider stochastic interventions, although the theorem extends to this setting.

4 This theorem also holds if we drop the requirement of identifiability from both sides of the implication.

5 In fact, it is possible to relax this assumption somewhat by restricting faithfulness only to those identifiable distributions which can lead to edge identification. However, characterizing all such distributions is outside the scope of this paper (though we give one such distribution for each identifiable edge), so we used a slightly stronger assumption that was easier to state.

6 This graph can be obtained by applying graphical rules for marginalization found in [Richardson and Spirtes, 2002] to remove variables in V \ (Y ∪ X), and removing all arrows incoming to X.

If X and Y are dependent in Pw(x, y|z), then by identifiable faithfulness of M, the true graph of M must contain e since, Gw \ {e} d-separates X and Y given Z. Thus the presence of e is a function of G and Pw(x, y|z), and the latter is a function of P (v). ✷

We use existing graphical conditions for identification of conditional causal effects [Shpitser and Pearl, 2006a] to characterize exactly when edges can be identified in a valid graph via Theorem 3, although we make no claims about the existence of other methods by which edges may be identified. In the remainder of the paper we use "identified" and "identified by Theorem 3" as synonyms.

We start by characterizing directed edge testing. First, we define some graphical terminology. A C-forest is a graph consisting of a single C-component where every node has at most one child. A C-forest with a single childless node is called C-tree. The set of childless nodes R of a C-forest is called its root set. The unique maximum set of nodes that forms a Y -rooted C-tree in G is called the maximum ancestral confounding set (MACS) of Y , and is denoted by T G y [Shpitser and Pearl, 2008].

Theorem 4 Let e be a directed edge X → Y in G. Then P(v),G ⊢id e (via Theorem 3) if and only if X ̸∈ T G y , and the only directed edge from X to T G y is e.

Proof: Let G′ = G\{e}. By Theorem 3, Y ̸∈ W for any separating W. Assume X ∈ T G y . This implies there is an inducing path fromX to Y in G, and moreover no element of T G y can be fixed, since G, P(v) ̸⊢id Pt(y), for T ⊆ T G y . If we remove e from T G y , nodes in T G y either form an {X, Y }-rooted Cforest or stay a C-tree in G′ . In both cases the inducing path remains. If there is a directed arrow fromX to T G y other than e, and X ̸∈ T G y then there is an inducing path fromX to Y in G, and no element in it can be (identifiably) fixed. Moreover, fixing X, even if identifiable, does not cut this path. Finally, if we remove e fromG, the inducing path remains.

Assume X ̸∈ T G y , and the only directed edge from X to T G y is e. This implies T G y = T G′ y , and by definition, T G x = T G′ x . Since G is acyclic, there cannot be a directed arc from Y to T G′ x . What remains is to show there is no bidirected arc from T G′ x to T G′ y . But if such an arc does exist, then T G′ x ∪ T G′ y would form a Y -rooted C-tree in G, whichmeans T G′ x ∪ T G′ y ⊆ T G y . But we assumedX ̸∈ T G y . By results in [Shpitser and Pearl, 2008], X, Y are d∗ -separable in G′ by Z, W, where Z = T G′ x ∪ T G′ y \ {X, Y }, W = (Pa(T G′ x ) ∪ Pa(T G′ y )) \ (T G′ x ∪T G′ y ). If G, P(v) ̸⊢id Pw(x, y|z), then there is a hedge [Shpitser and Pearl, 2006b] ancestral to {X, Y } in G for this effect, and it must contain e (or it would exist in G′ which we ruled out). But the existence of this hedge implies T G y ̸= T G′ y , which is a contradiction. ✷

There are simple examples where an edge e between X and Y is not identifiable if it is bidirected, but identifiable if it is directed. For instance, if we add an edge X ↔ Z to Fig. 1 (a), the directed edge fromX to Y is identifiable using the same reasoning as in our example, while the bidirected edge from X to Y is not identifiable (no sets Z,W both separate X and Y and result in an identifiable distribution). The next natural question is the converse, can there be a graph where a bidirected arc can be identified but a directed arc cannot be. It turns out the answer is no. In fact, the same is true if we reverse the direction of a directed arc.

Theorem 5 Let G be a graph where a directed arc e from X to Y is not identified. Let G′ be an acyclic graph obtained from G by replacing e by a bidirected (or directed but reversing direction if this is possible) edge e′ . Then e′ is not identified in G′ .

Proof: If e between X, Y is not identified, then for any sets Z,W either G, P(v) ̸⊢id P(x, y|do(w), z) or X, Y are not d∗ -separated by conditioning on Z, and fixing W in the graph G \ {e}, or do(w) cuts e directly. In particular, if the second case is true, then it is also true in the graph G′ \ {e′}.

If the first case is true, assume without loss of generality G, P (v) ̸⊢id P (x, y, z|do(w)). Results in [Shpitser and Pearl, 2006b] imply there is a hedge for this effect in G. Results in [Shpitser and Pearl, 2008] imply it is sufficient to restrict our attention to Z ∈ An({X, Y }). Since there is a hedge for P(x, y, z|do(w)) (e.g. ancestral to {X, Y } ∪ Z), then there is one ancestral to {X, Y }. If this hedge does not involve the edge e, then it remains in G′ and remains ancestral to {X, Y } in G′ , so our conclusion follows. If the hedge does involve e, then at least one of the X, Y nodes which e connects must be in F (the smaller of the two C-forests of the hedge). Removing e will then preserve the {X, Y }-rooted status of both C-forests in the hedge, and our conclusion follows.

If the third case is true, then if e becomes bidirected, it stays true. If e points the other way, then due to Theorem 4 either X is an ancestor of Y , in which case we cannot reverse e without introducing a cycle into G′ , or reversing e creates T G′ x which contains Y . ✷

Due to Theorem 5, there is no need to give conditions for testing for the absence of bidirected edges, although it is not hard to rephrase Theorem 4 for this purpose (and this may be useful in cases where background knowledge forbids direct effects, but confounding is still desirable to test for).

We also note that, assuming all constraints of the type that appear in Fig. 1 are due to missing edges that are identifiable, Theorem 4 gives a characterization of dense inducing paths, that is inducing paths [Verma and Pearl, 1990] which prevent separation of X and Y not only by conditioning but by identifiable interventions.

5 Sufficiency of Truncations

In the previous section, we characterized identification of edges in valid graphs of identifiable faithful models - a notion of identification which corresponds to observable constraints implied by dormant independence. In this section, we give an algorithm for identifying interventional distributions where such constraints appear, show this algorithm complete for this problem, and use this fact to conclude that a particular operation which we call truncation is sufficient for showing such constraints.

The algorithm, shown in Fig. 3, consists of four functions. The function Test-Edge is a top level function, and determines the candidate sets W, Z to fix and condition respectively in order to d∗ -separate X and Y . In order to do so it uses the notion of a maximum ancestral confounded set (MACS), which was shown to be sufficient for this purpose [Shpitser and Pearl, 2008]. The function Find-MACS finds the MACS (such sets are unique) for a singleton node argument in a given graph. The function Truncate-IDC identifies a conditional interventional distribution by rephrasing the query to be without conditioning, and calling Truncate-ID. It was shown that such rephrasing is without loss of generality for conditional effects [Shpitser and Pearl, 2006a]. Finally, the function Truncate-ID identifies the resulting distribution by means of two operations: marginalization and truncation. The latter operation consists of dividing by a conditional distribution term P(x|nd(x)), where Nd(X) is the set of nondescendants of X.

The key theorem about Test-Edge is that it can succeed on every edge identifiable by Theorem 3. Before proving this result, we prove a utility lemma.

Lemma 1 Px(v \ x) = P(v)/P(x|nd(x)) in G if there is no bidirected path from X to De(X).

Proof: Px(v \ x) = Px(de(x)|nd(x))Px(nd(x)) (by chain rule). Px(nd(x)) = P (nd(x)) by rule 3 of do-calculus [Pearl, 2000]. We claim Px(de(x)|nd(x)) = P(de(x)|nd(x), x) by rule 2 of do-calculus. We must show there are no d-connected back-door paths from X to De(x) conditioned on Nd(x). Such a path must start either with an directed arrow pointing to X or a bidirected arrow. In the former case, such an arrow will have a tail pointing to an element in Nd(X) which is conditioned on, implying no d-connected path. In the latter case, as long as the path consists entirely of bidirected arcs, it must stay within Nd(X) by assumption. However, the first directed arc on the path will render it d-separated by the above reasoning if the arrow points to the path fragment, and by definition if the arrow points away. ✷

Theorem 6 Let e be an edge in a valid graph G of an identifiable faithful model M. Then P(v), G ⊢id e due to Theorem 3 if and only if Test-Edge succeeds. Moreover, the successful output of Test-Edge gives an identifiable distribution witnessing identification of e.

Proof: Soundness of Find-MACS is shown in [Shpitser and Pearl, 2008]. Soundness of Truncate-ID follows by Lemma 1 and the soundness proof of the ID algorithm is found in [Shpitser and Pearl, 2006b]. Soundness of Truncate-IDC follows by soundness of do-calculus, and the fact that the input distribution P ∗ (v) at the point of failure of Truncate-ID was soundly identified from P(v). Soundness of Test-Edge follows from the soundness of other functions, and results in [Shpitser and Pearl, 2008].

To show completeness, we must show that if Test-Edges returns FAIL, the preconditions of Theorem 3 fail. If Test-Edges returns FAIL itself, then by known results X and Y are not d∗ -separable [Shpitser and Pearl, 2008]. If function Test-Edge(P (v), G, e).

INPUT: P(v) a probability distribution, G a causal diagram, e an edge fromX to Y .

OUTPUT: Expression for Pw(x, y|z) that tests e in G or FAIL.

• 1 T G x = Find-MACS(G,X), T G y = Find-MACS(G, Y ).
• 2 If X is a parent of T G y or Y is a parent of T G x or there is a bidirected arc between T G x and T G y , return FAIL.
• 3 Let T = T G x ∪ T G y , Z = T \ {X, Y }, W= Pa(T) \ T.
• 4 return Truncate-IDC(P(v),G, {X, Y },W, Z, e).

function Find-MACS(G, Y )

INPUT: G, a causal diagram, Y a node in G.

OUTPUT: T G y , the maximum ancestral confounded set for Y in G.

• 1 If (∃X ̸∈ An(Y )G), return Find-MACS(GAn(Y ), Y ).
• 2 If (∃X ̸∈ C(Y )G), return Find-MACS(GC(Y ), Y ).
• 3 Otherwise, return G.

function Truncate-IDC(P (v), G, Y, X, Z, e)

INPUT: P(v) a probability distribution, G a causal diagram, X,Y,Z variable sets, e an edge between X and Y .

OUTPUT: Expression for Pw(x, y|z) such that

X ⊥⊥w,G,P Y |Z or FAIL.

• 1 If (∃Z ∈ Z)(Y ⊥⊥P Z|X, Z \ {Z})Gx,z , return Truncate-IDC(P (v), G, y, x ∪ {z}, z \ {z}, e). 2 Let P ′ = Truncate-ID(P (v), G ∪ {e}, y ∪ z, x).
• 4 Otherwise, return P ′/ ∑y P ′ .

function Truncate-ID(P (v), G, Y, X).

INPUT: P(v) a probability distribution, G a causal diagram, X, Y, variable sets.

OUTPUT: An expression for P (y|do(x)) or FAIL.

• 1 If X is empty, return ∑v\y P(v).
• 2 If Na(Y) = V \ An(Y) is not empty, return Truncate-ID(∑na(y) P (v), Gan(y), Y, X \ Na(Y)).
• 3 If W = (V \ X) \ An(Y)Gx is not empty, return Truncate-ID(P (v), G, Y, X ∪ W).
• 4 If there is a node X ∈ X with no bidirected paths to
• De(X) in G, return Truncate-ID( P (v)∗P ∗ (x) P (x|nd(x)) , Gx, P (y|do(x \ {x})).
• 5 If C(X)G ̸= C(Y )G, return Test-Edge( Truncate-ID(P (v), G, C(Y )G, C(X)G), Gc(x)g , e).
• 6 Otherwise, return FAIL.

Figure 4: A causal diagram with a Verma constraint between B and E.

Truncate-ID returns FAIL, then by construction of the algorithm, the only remaining nodes other than X and Y are nodes Z such that Z is an ancestor of X, Y , Z has a bidirected path to a descendant of Z, and Z is being fixed. But this implies (by induction) that every remaining node has a bidirected path to {X, Y }.

Since e can be assumed directed, then all remaining nodes are ancestors of either X or Y , say Y . Then these nodes (including X) either form a Y -rooted C-tree, in which case Theorem 4 applies, or there are two C-components, one containing X and another containing Y . In this case, P(c(y)|do(c(x))) is identifiable by truncations, and line 5 of Truncate-ID uses this fact to continue the recursion. Either failure case after this step implies either Theorem 4 holds, or X and Y are not d∗ -separable - in the original graph.

Finally, though complete identification results in [Shpitser and Pearl, 2006b], [Shpitser and Pearl, 2006a] were for the set of all causal models, it is simple to extend them to also hold in all faithful models. ✷

We illustrate the operation of the algorithm by testing an edge between B and E in Fig. 4. In this graph, T G b = {B}, and T G e = {E}. Thus, the algorithm tries to fix the parents of {B, E}, namely {A, D}. However, both of these nodes have bidirected paths to their descendants (an arc from A to C, and a path D ↔ A ↔ E), so these interventions cannot be identified by truncations. Instead, since the C-component containing B (which is just B itself) and the C-component containing E are disjoint, the algorithm recurses and truncates out B, e.g. it considers P ∗ (b) P (b|a) P (a, b, c, d, e). This distribution is equal to Pb∼P ∗(a, b, c, d, e), and corresponds to the graph where the arrow from A to B is cut. The algorithm then proceeds to marginalize A and truncate D, resulting in an expression P ∗∗ (d) P (d|b,c) ∑a P ∗ (b) P (b|a) P (a, b, c, d, e) which corresponds to Pb∼P ∗ ,d∼P ∗∗(b, c, d, e), where B and E are independent.

Note that in this example in order to find the independence between B and E we had to fix B itself. Since typically interventions hold the variable constant, an intervention do(b) would make B and E trivially independent. By considering stochastic interventions like do(b ∼ P ∗ ), we are able to show that B and E remain independent after appropriate truncations even if B is allowed to vary (although in a way that no longer depends on B's causal ancestors).

The distributions returned by Test-Edges can be thought of as resulting from applying a sequence of nested operations, where some operations are marginalizations and others are truncations. What we are going to show is that all truncations can be applied before every marginalization, in which case marginalizations can be dispensed with as they do not affect conditional independence.

Theorem 7 Let P (v) be a probability distribution, and P ∗ = f1(f2(...fk(P(v))...)), where fi(p) is either ∑xi p, for some Xi ∈ V, or p P(xi|zi) , and such that Xi ̸= Xj for i ̸= j, Zi is some set not containing either Xi or any Xj mentioned in fi+1, ..., fk (Zi and Zj can intersect for j > i). Then there exists an ordering j1, ..., jk of fi such that P ∗ = fj1 (fj2 (...fjk (P(v))...)), and for any fji that is a marginalization, fj1 , ..., fji-1 are also marginalizations.

Proof: By definition of Zi, every truncation fi commutes with every marginalization fj where j > i, while marginalizations commute with each other due to axioms of probability. ✷

Corollary 1 Let M be an identifiable faithful model with a valid graph G and observable distribution P(v). Then if an edge e is identifiable by Theorem 3, there exists a set of truncations f1, ..., fk and a set Z such that X ⊥⊥P Y |Z in f1(...fk(P (v))...).

Proof: This follows from Theorems 6 and 7, the fact that conditional independence X ⊥⊥P Y |Z holds in P(v) if and only if it holds in ∑w P(v) for any W which does not intersect {X, Y } ∪ Z, and the fact that Truncate-ID never mentions nodes it removes on each step in subsequent steps. ✷

Corollary 1 suggests that in order to unearth dormant independence constraints which are due to edge absences in the graph, it is sufficient to consider truncation operations on a probability distribution. For instance, the independence between B and E in the expression P ∗∗ (d) P (d|b,c) ∑a P ∗ (b) P(b|a) P(a, b, c, d, e) obtained by running Test-Edge on Fig. 4, also holds in the expression P ∗∗ (d) P (d|b,c) P ∗ (b) P (b|a) P (a, b, c, d, e).

We hasten to add that since Theorem 7 "pushes truncations inward," and Corollary 1 ignores marginalizations, the independences we observe in the distributions obtained by truncations alone using these two results can lose their causal interpretability as independences in identifiable interventional distributions, since such distributions rely on truncations and marginalizations performed in a certain order. In particular, the expression above with two nested truncations does not correspond in an obvious way to any identifiable interventional distribution. Losing this interpretability is the price we pay for restricting the set of operations we consider.

What remains is to characterize all the constraints between two variables which are discoverable via truncation operations, and show, as we conjecture, that under reasonable faithfulness assumptions such constraints can only arise due to edge absences. The proof of this conjecture would allow the use of dormant independence in causal discovery, although unfortunately it is outside the scope of this paper.

Conclusion

In this paper we consider probabilistic constraints due to dormant independence which can be used to test the presence of edges in a causal diagram. We characterized when these constraints arise, and give an algorithm which finds them, given a graph where every edge is either correct or extraneous, i.e. the graph is a (possibly non-proper) supergraph of the true graph. Furthermore, we showed that applying an operation we call truncation in sequence to an observable probability distribution is sufficient to unearth all constraints of this type.

What remains to show before dormant independence constraints can be used in causal discovery algorithms is that sequences of truncation operations only lead to types of constraints we characterize and no others, given an appropriate notion of faithfulness. Proving this conjecture, and developing a causal discovery algorithm based on these ideas are the next steps in our investigation.