Ancestral graphs (AGs) are graphical causal models that can represent uncertainty about the presence of latent confounders, and can be inferred from data. Here, we present an algorithmic framework for efficiently testing, constructing, and enumerating m-separators in AGs. Moreover, we present a new constructive criterion for covariate adjustment in directed acyclic graphs (DAGs) and maximal ancestral graphs (MAGs) that characterizes adjustment sets as mseparators in a subgraph. Jointly, these results allow to find all adjustment sets that can identify a desired causal effect with multivariate exposures and outcomes in the presence of latent confounding. Our results generalize and improve upon several existing solutions for special cases of these problems.
Graphical causal models endow researchers with a
language to codify assumptions about a data generating
process
In this paper, we aim to efficiently find a definitive
answer for the following question: Given a causal graph G,
which covariates Z do we need to adjust for to estimate the
causal effect of the exposures X on the outcomes Y? To our
knowledge, no efficient algorithm has been shown to
answer this question, not even when G is a directed acyclic
graph (DAG), though constructive solutions do exist for
special cases like singleton X = fXg
1Quoting VanderWeele (2009), “Time will perhaps tell
whether results like Pearl’s front-door path adjustment theorem
and its generalizations are actually useful for epidemiologic
research or whether the results are simply of theoretical interest.”
the Bayes-Ball algorithm for verification of d-separating
sets
We denote sets by bold upper case letters (S), and
sometimes abbreviate singleton sets as fSg = S. Graphs are
written calligraphically (G), and variables in upper-case (X).
Mixed graphs and paths. We consider mixed graphs
G = (V; E) with nodes (vertices, variables) V and directed
(A ! B), undirected (A B), and bidirected (A $ B) edges
E. Nodes linked by an edge are adjacent. A walk of length
n is a node sequence V1; : : : ; Vn+1 such that there exists an
edge sequence E1; E2; : : : ; En for which every edge Ei
connects Vi; Vi+1. Then V1 is called the start node and Vn+1
the end node of the walk. A path is a walk in which no node
occurs more than once. Given a node set X and a node set
Y, a walk from X 2 X to Y 2 Y is called proper if only its
start node is in X. Given a graph G = (V; E) and a node
set V0, the induced subgraph GV0 = (V0; E0) contains the
edges E0 from G that are adjacent only to nodes in V0.
Ancestry. A walk of the form V1 ! : : : ! Vn is
directed, or causal. If there is a directed walk from U to V,
then U is called an ancestor of V and V a descendant of U.
A graph is acyclic if no directed walk from a node to itself
is longer than 0. All directed walks in an acyclic graph are
paths. A walk is anterior if it were directed after replacing
all edges U V by U ! V. If there is an anterior path
from U to V, then U is called an anterior of V. All
ancestors of V are anteriors of V. Every node is its own ancestor,
descendant, and anterior. For a node set X, the set of all of
its ancestors is written as An(X). The descendant and
anterior sets De(X); Ant(X) are analogously defined. Also, we
denote by Pa(X), (Ch(X)), the set of parents (children) of
X.
m-Separation. A node V on a walk w is called a collider
if two arrowheads of w meet at V, e.g. if w contains U $
V Q. There can be no collider if w is shorter than
2. Two nodes U; V are called collider connected if there
is a path between them on which all nodes except U and
V are colliders. Adjacent vertices are collider connected.
Two nodes U; V are called m-connected by a set Z if there
is a path between them on which every node that is a
collider is in An(Z) and every node that is not a collider
is not in Z. Then is called an m-connecting path. The
same definition can be stated simpler using walks: U; V are
called m-connected by Z if there is a walk between them
on which all colliders and only colliders are in Z. If U; V
are m-connected by the empty set, we simply say they are
m-connected. If U; V are not m-connected by Z, we say
that Z m-separates them or blocks all paths between them.
Two node sets X; Y are m-separated by Z if all their nodes
are pairwise m-separated by Z. In DAGs, m-separation is
equivalent to the well-known d-separation criterion
Ancestral graphs and DAGs. A mixed graph G = (V; E)
is called an ancestral graph (AG) if the following two
conditions hold: (1) For each edge A B or A $ B, A is
not an ancestor of B. (2) For each edge A B, there are no
edges A C, A $ C, B C or B $ C. There can be
at most one edge between two nodes in an AG
In this section, we compile an algorithmic framework for
solving a host of problems related to verification,
construction, and enumeration of m-separating sets in AGs.
The problems are defined in Fig. 1, which also shows
the asymptotic runtime of their solutions. Throughout, n
stands for the number of nodes and m for the number of
edges in a graph. All of these problems except LISTSEP
can be solved by rather straightforward modifications of
existing algorithms
An important tool for solving similar problems for
dseparation is moralization, by which d-separation can be
reduced to a vertex cut in an undirected graph. This
reduction allows to solve problems like FINDMINSEP using
standard network flow algorithms
Definition 3.1 (Moralization of AGs
Theorem 3.2 (Reduction of m-Separation to vertex cuts
A direct implementation of Definition 3.1 would lead to a
suboptimal algorithm. Therefore, we first give an
asymptotically optimal (linear time in output size) moralization
algorithm for AGs. We then solve TESTMINSEP,
FINDMINSEP, FINDMINCOSTSEP and LISTMINSEP by
generalizing existing correctness proofs of the moralization
approach for d-separation
Not all our solutions are based on moralization, however. Moralization takes time O(n2), and TESTSEP and FINDSEP can be solved faster, i.e. in asymptotically optimal time O(n + m).
Lemma 3.3 (Efficient AG moralization). Given an AG G, the augmented graph (G)a can be computed in time O(n2). Proof. The algorithm proceeds in four steps. (1) Start by setting (G)a to G replacing all edges by undirected ones. (2) Identify all connected components in G with respect to bidirected edges (two nodes are in the same such component if they are connected by a path consisting only of bidirected edges). Nodes without adjacent bidirected edges form singleton components. (3) For each pair U; V of nodes from the same component, add the edge U V to (G)a if it did not exist already. (4) For each component, identify all its parents (nodes U with an edge U ! V where U is in the component) and link them all by undirected edges in (G)a. Now two nodes are adjacent in (G)a if and only if they are collider connected in G. All four steps can be performed in time O(n2).
Lemma 3.4. Let X; Y; I; R be sets of nodes with I R, R \ (X [ Y) = ;. If there exists an m-separator Z0, with I Z0 R then Z = Ant(X [ Y [ I) \ R is an m-separator. Corollary 3.5 (Ancestry of minimal separators). Given an AG G, and three sets X; Y; I, every minimal set Z over all m-separators containing I is a subset of Ant(X [ Y [ I). Proof. Assume there is a minimal separator Z with Z * Ant(X [ Y [ I). According to Lemma 3.4 we have that Z0 = Ant(X [ Y [ I) \ Z is a separator with I Z0. But Z0 Ant(X [ Y [ I) and Z0 Z, so Z , Z0 and Z is not a minimal separator.
Corollary 3.5 applies to minimum-cost separators as well
because every minimum-cost separator must be minimal.
Now we can solve FINDMINCOSTSEP and
FINDMINSIZESEP by using weighted min-cut, which takes time
O(n3) using practical algorithms, and LISTMINSEP by
using Takata’s algorithm to enumerate minimal vertex cuts
with delay O(n3)
However, for FINDMINSEP and TESTMINSEP, we can do better than using standard vertex cuts.
Proposition 3.6. The task FINDMINSEP can be solved in time O(n2).
Proof. Two algorithms are given in the appendix, one with runtime O(nm) (Algorithm 8) and one with runtime O(n2) (Algorithm 9).
Corollary 3.7. The task TESTMINSEP can be solved in time O(n2).
Proof. First verify whether Z is an m-separator using moralization. If not, return “no”. Otherwise, set S = Z and solve FINDMINSEP. Return “yes” if the output is Z and “no”, otherwise.
Moralization can in the worst case quadratically increase the size of a graph. Therefore, in some cases, it may be preferable to avoid moralization if the task at hand is rather simple, as are the two tasks considered below.
Proposition 3.8. The task FINDSEP can be solved in time O(n + m).
Proof. This follows directly from Lemma 3.4, and the fact that the set Ant(X [ Y [ I) \ R can be found in linear time from the MAG without moralization. Note that unlike in DAGs, two non-adjacent nodes cannot always be m-separated in ancestral graphs.
By modifying the Bayes-Ball algorithm
Proposition 3.9. The task TESTSEP can be solved in time O(n + m).
Lastly, we consider the problem of listing all m-separators. Here is an algorithm to solve that problem with polynomial delay.
Verification: For given X; Y and Z decide if : : :
TESTSEP Z m-separates X; Y
TESTMINSEP Z m-separates X; Y but no Z0 ( Z does Construction: For given X; Y and auxiliary I; R, output : : : FINDSEP an m-separator Z with I Z R FINDMINSEP a minimal m-separator Z with I Z FINDMINCOSTSEP a minimum-cost m-separator Z with I Enumeration: For given X; Y; I; R enumerate all : : : LISTSEP m-separators Z with I Z R LISTMINSEP minimal m-separators Z with I Z R
Z R
R
O(n + m) O(n2) O(n + m) O(n2) O(n3) O(n(n + m)) delay O(n3) delay
Proof. Algorithm LISTSEP performs backtracking to
enumerate all Z with I Z R aborting branches that will not
find a valid separator. Since every leaf will output a
separator, the tree height is at most n and the existence check
needs O(n + m), the delay time is O(n(n + m)). The
algorithm generates every separator exactly once: if initially
I ( R, with V 2 R n I, then the first recursive call returns
all separators Z with V 2 Z and the second call returns all
Z0 with V < Z0. Thus the generated separators are pairwise
disjoint. This is a modification of the enumeration
algorithm for minimal vertex separators
In this section, we leverage the algorithmic framework of the last section together with a new constructive, sound and complete criterion for covariate adjustment in DAGs to solve all problems listed in Table 1 for adjustment sets instead of m-separators in the same asymptotic time. First, however, we need to introduce some more notation pertaining to the causal interpretation DAGs. ables V = fX1; : : : ; Xng as p(v) = Qnj=1 p(xjjpaj), where paj denotes a particular realization of the parent variables of Xj in G. When interpreted causally, an edge Xi ! Xj is taken to represent a direct causal effect of Xi on Xj. For disjoint X; Y V, the (total) causal effect of X on Y is p(yjdo(x)) where do(x) represents an intervention that sets X = x. In a DAG, this intervention corresponds to removing all edges into X, disconnecting X from its parents. We denote the resulting graph as GX. Given DAG G and a joint probability density p for V the post-intervention distribution can be expressed in a truncated factorization formula:
Y p(xjjpaj) for V consistent with x 8 > > p(vjdo(x)) = <>> Xj2VnX >>: 0 otherwise.
Definition 4.1 (Adjustment
Remark 4.3. In
the factorization of joint distribution p for the set of
variProof. First note that if Z satisfies the condition (a) then
Z satisfies (a) with GX instead of G, too. Since
conditions (b) in Definition 4.2 and in
Now assume Z satisfies the condition (a) with GX instead of G and the condition (b). We show that Z then satisfies the condition (a), or there must exist some W 2 V n X, which lies on a proper causal path from X to Y, and a causal path from W to Z which intersects X.
Let W ! : : : ! Y denote the suffix of the path from X to Y starting in W. Note that this path can consist only of the vertex W. Additionally, for the causal path from W to Z, let W ! : : : ! X be its shortest prefix which intersects X. Then, from the condition (a), with GX instead of G, we know that no vertex of W ! : : : ! X belongs to Z. This leads to a contradiction with the condition (b) since X : : : W ! : : : ! Y is a proper non-causal path in G from X to Y that is not blocked by Z.
Analogously to GX, by GX we denote a DAG obtained from G by removing all edges leaving X. 4.1
Definition 4.4 (Proper back-door graph). Let G = (V; E) be a DAG, and X; Y V be pairwise disjoint subsets of variables. The proper back-door graph, denoted as GpXbYd, is obtained from G by removing the first edge of every proper causal path form X to Y.
Note the difference between the back-door graph GX and the proper back-door graph GpXbYd: in GX all edges leaving X are removed while in GpXbYd only those that lie on a proper causal path. However, to construct GpXbYd still only elementary operations are sufficient. Indeed, we remove all edges X ! D in E such that X 2 X and D is in the subset, which we call PCP(X; Y), obtained as follows:
PCP(X; Y) = (DeX(X) n X) \ AnX(Y) (1) where DeX(W) denotes descendants of W in GX. AnX(W) is defined analogously for GX. Hence, the proper back-door graph can be constructed from G in linear time O(m + n). Now we propose the following adjustment criterion. For short, we will denote the set De(PCP(X; Y)) as Dpcp(X; Y). Definition 4.5 (Constructive back-door criterion (CBC)). Let G = (V; E) be a DAG, and let X; Y; Z V be pairwise disjoint subsets of variables. The set Z satisfies the constructive back-door criterion relative to (X; Y) in G if (a) Z
V n Dpcp(X; Y) and (b) Z d-separates X and Y in the proper back-door graph GpXbYd.
Theorem 4.6. The constructive back-door criterion is equivalent to the adjustment criterion.
Proof. First observe that the conditions (a) of both criteria are identical. Assume conditions (a) and (b) of the adjustment criterion hold. We show that (b) of the constructive back-door criterion follows. Let be any proper path from X to Y in GpXbYd. Because GpXbYd does not contain causal paths from X to Y, is not causal and has to be blocked by Z in G by the assumption. Since removing edges cannot open paths, is blocked by Z in GpXbYd as well.
Now we show that (a) and (b) of the constructive back-door criterion together imply (b) of the adjustment criterion. If that were not the case, then there could exist a proper noncausal path
from X to Y that is blocked in GpXbYd but open in G. There can be two reasons why is blocked in GpXbYd: (1) The path starts with an edge X ! D that does not exist in GpXbYd. Then we have D 2 PCP(X; Y). For to be noncausal, it would have to contain a collider C 2 An(Z) \ De(D) An(Z) \ Dpcp(X; Y). But because of (a), An(Z) \ Dpcp(X; Y) is empty. (2) A collider C on is an ancestor pbd of Z in G, but not in GXY . Then there must be a directed path from C to Z via an edge X ! D with D 2 An(Z) \ PCP(X; Y), contradicting (a). 4.2
For a singleton set X = fXg of exposures we know that if
a set of variables Y is disjoint from fXg [ Pa(X) then one
obtains easily an adjustment set with respect to X and Y
as Z = Pa(X)
X2
Z
Y: Using our criterion, we can construct a simple adjustment set explicitly if one exists. For a DAG G = (V; E) we define the set
Adj(X; Y) = An(X [ Y) n (X [ Y [ Dpcp(X; Y)): Theorem 4.7. Let G = (V; E) be a DAG and let X; Y V be distinct node sets. Then the following statements are equivalent: 1. There exists an adjustment in G w.r.t. X and Y.
Z1 Z2
Y1
X1
Y1
X1
Z1
Z2 Y2
X2
Y2
X2
pbd GXY
Z1 Z2
Y1 Y2
3. Adj(X; Y) d-separates X and Y in the proper backdoor graph GpXbYd.
Proof. The implication (3) ) (2) follows directly from the criterion Def. 4.5 and the definition of Adj(X; Y). Since the implication (2) ) (1) is obvious, it remains to prove (1) ) (3).
Assume there exists an adjustment set Z0 w.r.t. X and Y. From Theorem 4.6 we know that Z0 \ Dpcp(X; Y) = ; and pbd that Z0 d-separates X and Y in GXY . Our task is to show pbd that Adj(X; Y) d-separates X and Y in GXY . This follows pbd from Lemma 3.4 used for the proper back-door graph GXY if we take I = ;, R = V n (X [ Y [ Dpcp(X; Y)). From Equation 1 and the definition Dpcp(X; Y) De(PCP(X; Y)) we then obtain immediately: =
can be found in O(n + m) time. V, Adj(X; Y) 4.3
Using our criterion, every algorithm for m-separating sets Z between X and Y can be used for adjustment sets with respect to X and Y, by requiring that Z not contain any node in Dpcp(X; Y). This allows solving all problems listed in Table 1 for adjustment sets in DAGs instead of mseparators. Below, we name those problems analogously as for m-separation, e.g. the problem to decide whether Z is an adjustment set w.r.t. X; Y is named TESTADJ in analogy to TESTSEP.
TESTADJ can be solved by testing if Z \ Dpcp(X; Y) = ; pbd and Z is a d-separator in the proper back-door graph GXY . Since GpXbYd can be constructed from G in linear time, the total time complexity of this algorithm is O(n + m). TESTMINADJ can be solved with an algorithm that iteratively removes nodes from Z and tests if the resulting set remains an adjustment set w.r.t. X and Y. This can be done in time O(n(n + m)). Alternatively, one can construct the proper back-door graph GpXbYd from G and test if Z is a minimal d-separator, with Z V n Dpcp(X; Y) between X and Y. This can be computed in time O(n2). The correctness of these algorithms follows from the proposition below, which is a generalization of the result in Tian et al. (1998). Proposition 4.9. If no single node Z can be removed from an adjustment set Z such that the resulting set Z0 = Z n Z is no longer an adjustment set, then Z is minimal. The remaining problems like FINDADJ, FINDMINADJ etc. can be solved using corresponding algorithms for finding, resp. listing m-separations applied for proper back-door graphs. Since the proper back-door graph can be constructed in linear time the time complexities to solve the problems above are as listed in Table 1. 5
We now generalize the results from the previous section
to MAGs. Two examples may illustrate why this
generalization is not trivial. First, take G = X ! Y. If G is
interpreted as a DAG, then the empty set is valid for
adjustment. If G is however taken as a MAG, then there exists
no adjustment set as G represents among others the DAG
U X Y where U is an unobserved confounder.
Second, take G = A ! X ! Y. In that case, the empty set
is an adjustment set regardless of whether G is interpreted
as a DAG or a MAG. The reasons will become clear as we
move on. First, let us recall the semantics of a MAG. The
following definition can easily be given for AGs in general,
but we do not need this generality for our purpose.
Definition 5.1 (DAG representation by MAGs
V if U 2 An(S [ V) and V 2 An(S [ U); U ! V if U 2 An(S [ V) and V < An(S [ U); U $ V if U < An(S [ V) and V < An(S [ U). We call L latent variables and S selection variables. We say there is selection bias if S , ;.
Hence, every MAG represents an infinite set of underlying
DAGs that all share the same ancestral relationships. For a
given MAG M, we can construct a represented DAG G by
replacing every edge X Y by a path X ! S Y, and
every edge X $ Y by X L ! Y, where S and L are new
nodes; then M = G[SL where S and L are all new nodes. G
is called the canonical DAG of M
Lemma 5.2 (Preservation of separating sets
We now extend the concept of adjustment to MAGs in the
usual way
Definition 5.3 (Adjustment in MAGs). Given a MAG M = (V; E) and two variable sets X; Y V, Z V is an adjustment set for X; Y in M if for every probability distribution p(v0) consistent with a DAG G = (V0; E0) for which G[SL= M for some S; L V0 n V, we have p(y j do(x)) =
X p(y j x; z; s)p(z j s) :
z
(2)
Selection bias (i.e., S , ;) substantially complicates
adjustment, and in fact nonparametric causal inference in
general
In this section we first identify a class of MAGs in which adjustment is impossible because of causal ambiguities – e.g., the simple MAG X ! Y falls into this class, but the larger MAG A ! X ! Y does not.
Definition 5.4 (Visible edge
Intuitively, an invisible directed edge X ! Y means that there may still hidden confounding factors between X and Y, which is guaranteed not to be the case if the edge is visible.
Lemma 5.5 (Graphical conditions for edge visibility
Lemma 5.7. If a MAG M = (V; E) is not adjustment amenable w.r.t. X; Y V then there exists no adjustment set W for X; Y in M.
Proof. If the first edge X ! D on some causal path to Y in M is not visible, then there exists a consistent DAG G where there is a non-causal path between X and Y via V that could only be blocked in M by conditioning on D or some of its descendants. But such conditioning would violate the adjustment criterion in G. 5.2
We now show that DAG adjustment criterion generalizes to adjustment amenable MAGs. The adjustment criterion and the constructive back-door criterion are defined like their DAG counterparts (Definitions 4.2 and 4.4), replacing dwith m-separation for the latter.
Theorem 5.8. Given an adjustment amenable MAG M = (V; E) and three disjoint node sets X; Y; Z V, the following statements are equivalent: (i) Z is an adjustment relative to X; Y in M. (ii) Z fulfills the adjustment criterion (AC) w.r.t. (X; Y) in
M. (iii) Z fulfills the constructive backdoor criterion (CBC) w.r.t. (X; Y) in M.
Proof. The equivalence of (ii) and (iii) is established by observing that the proof of Theorem 4.6 generalizes to mseparation. Below we establish equivalence of (i) and (ii). :(ii) ) :(i): If Z violates the adjustment criterion in M, it does so in the canonical DAG C(M), and thus is not an adjustment in M. :(i) ) :(ii): Let G be a DAG with G[;L= M in which Z violates the AC. We show that (a) if Z \ Dpcp(X; Y) , ; in G then Z \ Dpcp(X; Y) , ; in M as well, or there exists a proper non-causal path in M that cannot be m-separated; and (b) if Z \ Dpcp(X; Y) = ; in G and Z d-connects a proper non-causal path in G, then it m-connects a proper non-causal path in M. (a) Suppose that in G, Z contains a node Z in Dpcp(X; Y), and let W = PCP(X; Y)\An(Z). If M still contains at least one node W1 2 W, then W1 lies on a proper causal path in M and Z is a descendant of W1 in M. Otherwise, M X Z
DAG G
W1
Y W2
X Z MAG M = G[;W1
Y W2 must contain a node W2 2 PCPG(X; Y) n An(Z) (possibly W2 2 Y) such that W2 $ A, X ! W2, and X ! A are edges in M, where A 2 An(Z) (possibly A = Z; see Fig. 3). Then M contains an m-connected proper non-causal path X ! A $ W ! W2 ! : : : ! Y. (b) Suppose that in G, Z \ Dpcp(X; Y) = ;, and there exists an open proper non-causal path from X to Y. Then there must then also be a proper non-causal walk wG from some X 2 X to some Y 2 Y (Lemma A.1), which is d-connected by Z in G. Let wM denote the subsequence of wG formed by nodes in M, which includes all colliders on wG. The sequence wM is a path in M, but is not necessarily mconnected by Z; all colliders on wM are in Z because every non-Z must be a parent of at least one of its neighbours, but there can subsequences U; Z1; : : : ; Zk; V on wM where all Zi 2 Z but some of the Zi are not colliders on wM. However, then we can form from wM an m-connected walk by bypassing some sequences of Z-nodes (Lemma A.9). Let w0 be the resulting walk.
M If w0 is a proper non-causal walk, then there must also exist aMproper non-causal path in M (Lemma A.1), violating the AC. It therefore remains to show that w0 is not a proper causal path. This must be the case if wG dMoes not contain colliders, because then the first edge of wM = w0 cannot be a visible directed edge out of X. Otherwise,Mthe only way for w0 to be proper causal is if all Z-nodes in wM have been Mbypassed in w0 by edges pointing away from X. In that case, one can sMhow by several case distinctions that the first edge X ! D of w0 , where D < Z, cannot be visible (see Figure 4 for an examMple of such a case). For simplicity, assume that M contains a subpath A ! X ! D where A is not adjacent to D; the other cases of edge visibility like A $ X ! D (Lemma 5.5). are treated analogously. In G, there are inducing paths (possibly several) AX from A to X and XD from X to D w.r.t ;; L; AX must have an arrowhead at X. We distinguish several cases on the shape of XD. (1) A path
XD has an arrowhead at X as well. Then A; D are adjacent (Lemma A.13), a contradiction. (2) No inducing path XD has an arrowhead at X. Then wG must start with an L1 X
A DAG G
Z
L2
MAG M = G[f;L1;L2g
Z Y
X
Y A arrow out of X, and must contain a collider Z 2 De(X) because wG is not causal. (a) Z 2 De(D). This contradicts Z \ Dpcp(X; Y) = ;. So (b) Z < De(D). Then by construction of w0 (Lemma A.9), wM must start with
M an inducing Z-trail X ! Z; Z1; : : : ; Zn; D, which is also an inducing path from X to D in G w.r.t. ;; L. Then Z; Z1; : : : ; Zn; D must also be an inducing path in G w.r.t. ;; L because An(X) An(Z). Hence Z and D are adjacent. We distinguish cases on the path X ! Z; D in M. (i) If X ! Z ! D, then Z lies on a proper causal path, contradicting Z \ Dpcp(X; Y) = ;. (ii) If X ! Z $ D, or X ! Z D, then we get an m-connected proper noncausal walk along Z and D. In the previous section, we have already shown that the CBC is equivalent to the AC for MAGs as well; hence, adjustment sets for a given MAG M can be found by forming the proper back-door graph MpXbYd and then applying the algorithms from the previous section. In principle, care must be taken when removing edges from MAGs as the result might not be a MAG; however, this is not the case when removing only directed edges.
Lemma 5.9 (Closure of maximality under removal of
directed edges). Given a MAG M, every graph M0 formed
by removing only directed edges from M is also a MAG.
Proof. Suppose the converse, i.e. M is no longer a MAG
after removal of some edge X ! D. Then X and D cannot
be m-separated even after the edge is removed because X
and D are collider connected via a path whose nodes are all
ancestors of X or D
For MAGs that are not adjustment amenable, the CBC might falsely indicate that an adjustment set exists even though that set may not be valid for some represented graph. Fortunately, adjustment amenability is easily tested using the graphical criteria of Lemma 5.5. For each child D of X in PCP(X; Y), we can test the visibility of all edges X ! D simultaneously using depth first search. This means that we can check all potentially problematic edges in time O(n + m). If all tests pass, we are licensed to apply the CBC, as shown above. Hence, we can solve all algorithmic tasks in Table 1 for MAGs in the same way as for DAGs after an O(k(n + m)) check of adjustment amenability, where k jCh(X)j. 6
We have compiled efficient algorithms for solving several tasks related to m-separators in ancestral graphs, and applied those together with a new, constructive adjustment criterion to provide a complete and informative answer to the question when, and how, a desired causal effect can be estimated by covariate adjustment. Our results fully generalize to MAGs in the absence of selection bias. One may argue that the MAG result is more useful for exploratory applications (inferring a graph from data) than confirmatory ones (drawing a graph based on theory), as researchers will prefer drawing DAGs instead of MAGs due to the easier causal interpretation of the former. Nevertheless, in such settings the results can provide a means to construct more “robust” adjustment sets: If there are several options for covariate adjustment in a DAG, then one can by interpreting the same graph as a MAG possibly generate an adjustment set that is provably valid for a much larger class of DAGs. This might partially address the typical criticism that complete knowledge of the causal structure is unrealistic. Our adjustment criterion generalizes the work of Shpitser et al. (2010) to MAGs and therefore now completely characterizes when causal effects are estimable by covariate adjustment in the presence of unmeasured confounders with multivariate exposures and outcomes. This also generalizes recent work by Maathuis and Colombo (2013) who provide a criterion which, for DAGs and MAGs without selection bias, is stronger than the back-door criterion but weaker than ours. They moreover show their criterion to hold also for CPDAGs and PAGs, which represent equivalence classes of DAGs and MAGs as they are constructed by causal discovery algorithms. It is possible that the constructive back-door criterion could be generalized further to those cases, which we leave for future work. A A.1
In this section, we prove Lemma 3.4 and several auxiliary Lemmas that are necessary for the proof of Theorem 5.8. Proof of Lemma 3.4. Let us consider a proper walk w = X; V1; : : : ; Vn; Y with X 2 X; Y 2 Y. If w does not contain a collider, all nodes Vi are in Ant(X [ Y) and the walk is blocked by Z, unless fV1; : : : ; Vng \ R = ; in which case the walk is not blocked by Z0 either. If the walk contains colliders C, it is blocked, unless C Z R. Then all nodes Vi are in Ant(X [ Y [ I) and the walk is blocked, unless fV1; : : : ; Vng \ R = C. Since C Z is a set of anteriors, there exists a shortest (possible containing 0 edges) path j = Vj ! : : : ! Wj for each Vj 2 C with Wj 2 X [ Y [ I (it cannot contain an undirected edge, since there is an arrow pointing to Vj). Let 0j = Vj ! : : : ! W0 j be the shortest subpath of j that is not blocked by Z0. Let w0 be the walk w after replacing each Vj by the walk Vj ! : : : ! W0j : : : Vj. If any of the Wj is in X [ Y we truncate the walk, such that we get the shortest walk between nodes of X and Y. Since 0j is not blocked, w0 contains no colliders except w0j and all other nodes of w0 are not in R, w0 is not blocked and Z0 is not a separator. Lemma A.1. Given a DAG G and sets X; Y; Z V satisfying Z\Dpcp(X; Y) = ;, Z m-connects a proper non-causal path between X and Y if and only if it m-connects a proper non-causal walk between X and Y.
Proof. (: Let w be the m-connected proper non-causal walk. It can be transformed to an m-connected path by removing loops of nodes that are visited multiple times. Since no nodes have been added, remains proper, and the first edges of and w are the same. So if w does not start with a ! edge, is non-causal. If w starts with an edge X ! D, there exists a collider with a descendant in Z which is in De(D). So has to be non-causal, or it would contradict Z \ Dpcp(X; Y) = ;. ): Let be an m-connected proper non-causal path. It can be changed to an m-connected walk w by inserting Ci ! : : : ! Zi : : : Ci for every collider Ci on and a corresponding Zi 2 Z. Since no edges are removed from , w is non-causal, but not necessarily proper, since the inserted walks might contain nodes of X. However, in that case, w can be truncated to a proper walk w0 starting at the last node of X on w. Then w0 is non-causal, since it contains the subpath X : : : Ci.
In all of the below, G = (V; E) is a DAG, Z; L
L disjoint, and M = G[; .
Definition A.2 (Inducing path
L in G[; .
Proof. This is Theorem 4.2, cases (v) and (vi), in Richardson and Spirtes (2002).
Lemma A.4. Two nodes U; V are adjacent in G[;L if and only if G contains an inducing path between U and V with respect to ;; L. Moreover, the edge between U; V in
L can only have an arrowhead at U (V) if all such hGa[v;e an arrowhead at U (V) in G.
Proof. The first part on adjacency is proved in
ZL1e misma anoAn.-5c.olSluidpepro.sSeuZpp0o;Zse1;aZn2inisduacpinagthpianthG[;L on which 01 from Z0 to Z1 w.r.t. ;; L in G has an arrowhead at Z1, and an inducing path 12 from Z1 to Z2 w.r.t. ;; L has an arrowhead at Z1. Then the walk w012 = 01 12 can be truncated to an inducing path from Z0 to Z2 w.r.t. ;; L in G.
Proof. The walk w012 does not contain more non-colliders than those on 01 or 12, so they must all be in L. It remains to show that the colliders on w012 are in An(Z0 [ Z2). Because Z1 is not a collider on Z0; Z1; Z2, at least one of the edges Z0; Z1 and Z1; Z2 must be a directed edge pointing away from Z1. Assume without loss of generality that Z0 Z1 is that edge. Then all colliders on 01 are in An(Z0 [ Z1) = An(Z0) An(Z0 [ Z2), and all colliders on 12 are in An(Z1 [ Z2) An(Z0 [ Z2). Z1 itself is a collider on w012 and is also in An(Z0). Hence, the walk w012 is d-connected, and can be truncated to an inducing path that starts with the first arrow of 01 and ends with the last arrow of 12.
Definition A.6 (Inducing Z-trail). Let = V1; : : : ; Vn+1 abendafpoartehaicnh Gi[2;L fs1u;c:h: :th;nagt,Vth2e;r:e: :i;sVann 2indZu,cVin1g; Vpan+th1 w<.rZ.t,. ;; L linking Vi; Vi+1 that has an arrowhead at Vi (Vi+1) if Vi 2 Z (Vi+1 2 Z). Then is called an inducing Z-trail. Lemma A.7. Let = V1; : : : ; Vn+1 be an inducing Z-trail, and let 0 be a subsequence of formed by removing one node Vi of such that Vi 2 Z is a non-collider on . Then 0 is an inducing Z-trail.
Proof. According to Lemma A.5, if Vi is a non-collider on , then Vi 1 and Vi+1 are linked by an inducing path that contains an arrowhead at Vi 1 (Vi+1) if Vi 1 2 Z (Vi+1 2 Z). Therefore, Vi 1 and Vi+1 are themselves adjacent, 0 is a path, and is a Z-trail.
has a subpath 0 that is m-connected by Z. = V1; : : : ; Vn+1 Proof. Transform into 0 by replacing non-collider nodes in Z by the direct edge linking their neighbours until no such node exists anymore. By inductively applying Lemma A.7, we see that 0 is also an inducing Z-trail, and every node in Z is a collider because otherwise we would have continued transforming. So 0 must be m-connected by Z. in Z (possibly wM0 = wM).
M Lemma A.9. Let wG be a walk from X to Y in G, X; Y < L, that is d-connected by Z. Let wM = V1; : : : ; Vn+1 be the subsequence of wG consisting only of the nodes in M = sGu[b;Ls.eTqhueenncZe wm0-cofonrnmecetds fXroamnwdMY ibny Mremvoiaviangpsaothmaelnoondgeas Proof. First, truncate from wM all subwalks between nodes in Z that occur more than once. Now consider all subsequences V1; : : : ; Vn+1, n > 1, of wM where V2; : : : ; Vn 2 Z, V1; Vn+1 < Z, which now are all paths in wM. On those subsequences, every Vi must be adjacent in G to Vi+1 via a path containing no colliders, and all nonendpoints on that path must be in L. So there are inducing paths w.r.t. ;; L between all Vi; Vi+1, which have arrowheads at Vi (Vi+1) if Vi 2 Z (Vi+1 2 Z). So V1; : : : ; Vn+1 is an inducing Z-trail, and has a subpath which m-connects V1, Vn+1 given Z. Transform wM to w0 by replacing all inducing Z-trails by their m-connected sMubpaths. According to Lemma A.4, non-colliders on wM cannot be colliders on w0 , as bypassing inducing paths can remove but not createMarrowheads. Moreover, all nodes in Z on w0 are colliders. Hence w0 is m-connected by Z. M M Corollary A.10. Each edge on w0 as defined above corM responds to an inducing path w.r.t ;; L in G along nodes on wG.
Lemma A.11. Suppose there exists an inducing path 01 from Z0 to Z1 w.r.t. S; L with an arrowhead at Z1 and an inducing path from Z1 to Z2 w.r.t. S0; L with an arrowhead at Z1. Then the walk w012 = 01 12 can be truncated to an inducing path from Z0 to Z2 w.r.t. S [ S0 [ fZ1g; L in G. Proof. The walk w012 does not contain more non-colliders than those on 01 or 12, so they must all be in L. All colliders on 0;1 and 1;2 as well as Z1 are in An(Z0; Z1; Z2; S; S0), and therefore also all colliders of w012.
Hence, the walk w012 is d-connected, and can be truncated to an inducing path that starts with the first arrow of 01 and ends with the last arrow of 12.
L Lemma A.12. Suppose Z0; Z1; : : : ; Zk+1 is a path in G[; with an arrowhead at Zk+1 on which all Z1; : : : ; Zk are colliders. Then there exists an inducing path from Z0 to Zk+1 w.r.t. fZ1; : : : ; Zkg; L with an arrowhead at Zk+1. Proof. Because all Zi; Zi+1 are adjacent and all Z1; : : : ; Zk are colliders there exist inducing paths i;i+1 w.r.t. ;; L from Zi to Zi+1 that have arrowheads at Z1; : : : ; Zk (Lemma A.4). The claim follows by repeatedly applying Lemma A.11 to the i;i+1’s.
Lemma A.13. Suppose A ! V1 $ : : : $ Vk $ X ! D or A $ V1 $ : : : $ Vk $ X ! D is a path in eGx[i;Lsts(paonssinibdluyckin=g p0a)t,heach Vi is a parent of D and there
XD from X to D w.r.t ;; L that has arrowheads on both ends. Then A and D cannot be m
L separated in G[; .
Proof. Assume the path is A ! V1 $ : : : $ Vk $ X ! D. The case where the path starts with A $ V1 can be handled identically, since the first arrowhead does not affect m-separation. bAesssuumche aAseapnadraDtorc.aInf bVe1 mis-sneoptairnatZedthinenGth[;Le, paanthd Alet!Z V1 ! D is not blocked, so V1 2 Z. Inductively it follows, if Vi is not in Z, but all 8 j < i : Vj 2 Z then the path A ! V1 $ : : : $ Vi 1 $ Vi ! D is not blocked, so Vi 2 Z for all i.
There exist an inducing path AX from A to X with an arrowhead at X w.r.t. to fV1; : : : ; Vkg; L (Lemma A.12) which can be combined with XD to an inducing path from A to D w.r.t. to fV1; : : : ; Vk; Xg; L (Lemma A.11).
Hence no m-separator of A; D can contain fX; V1; : : : ; Vkg (Lemma A.3). Then there cannot exist an m-separator, because every separator must include V1; : : : ; Vk and the path A ! V1 $ V2 $ : : : $ Vk $ X ! D is open without X 2 Z.
A.2
This section contains algorithm pseudocodes and parts of their correctness proofs that were omitted from the main text for space reasons.
A.2.1
For a given ancestral graph G the problem TESTSEP can be solved with a modified Bayes-Ball algorithm in time O(n+m). In the algorithm every bi-directed edge A $ B is considered as a pair of edges A ! B and an undirected edge A B as a directed edge pointing to the currently visited node.
function TESTSEP(G; X; Y; Z)
Run Bayes-Ball from X
return (Y not reachable)
The problem TESTMINSEP can be solved using Algorithm
6 TESTMINSEP in O(jEAmnj) = O(n2) time. Alternatively,
the problem can be solved with an algorithm that iteratively
removes from Z nodes and tests if the resulting set remains
an m-separator. This can be done in time O(n(n + m)).
The correctness of the algorithms for TESTMINSEP can
be shown by generalizing the results presented in
return false RGx0a fGZaA2ntZ(X[jY9) path X Z in G0a
not intersecting Z n fZgg if Z * Rx then return false Ry fZ 2 Z j 9 path Y Z in G0a
not intersecting Z n fZgg if Z * Ry then return false return true The problem can be solved using Algorithm 7 FINDSEP in O(n + m) time. The correctness follows directly from Lemma 3.4. Algorithm 8 FINDMINSEPNAIVE depends on an implicit moral graph and the fact that in an undirected graph every node that cannot be removed from a separating set has to be in separating subsets, and runs in O(jAnt(X [ Y)jjEAnj). function FINDMINSEPMORAL(G; X; Y; I; R)
G0 GAnt(X[Y[I) G0a GaAnt(X[Y[I) Z0 R \ Ant(X [ Y) Remove from G0a all nodes of I if not TESTSEP(G0; X; Y; Z) then
return ?
Run BFS from X. Whenever a node in Z0 is met, mark it, if it is not already marked and do not continue along the path. When BFS stops, let Z00 be the set of all marked nodes. Remove all markings
Run BFS from Y. Whenever a node in Z00 is met, mark it, if it is not already marked and do not continue along the path. When BFS stops, let Z be the set of all marked nodes.
return Z [ I
Figure 9: FindMinSepMoral Algorithm 9 FINDMINSEPMORAL begins with the separating set R \ Ant(X [ Y) and finds a subset satisfying the conditions tested by algorithm 6 TESTMINSEP, in O(jEAmnj).
The problem MINCOSTSEP can be solved with algorithm 10 FINDMINCOSTSEP in O(n3).
function FINDMINCOSTSEP(G; X; Y; I; R; w)
G0 GAnt(X[Y[I) G0a GaAnt(X[Y[I) Add a node Xm connected to all nodes in X, and a node Ym connected to all nodes in Y.
Assign infinite cost to all nodes in X [ Y [ (V n R) and cost w(Z) to every other node Z.
Remove all nodes of I from G0a.
Change the graph to a flow network as described in Cormen et al. (2001) and return a minimum cutset Z. The correctness without I follows from the fact that a minimum set is a minimal set and the minimal cut found in the ancestor moral graph is therefore the minimal separating set. The handling of I is shown in Acid and de Campos (1996).
A.2.5
The problem LISTMINSEP can be solved with algorithm 11 LISTMINSEP with O(n3) delay between every outputted Z.
function LISTMINSEP(G; X; Y; I; R)
G0 GAnt(X[Y[I) G0a GaAnt(X[Y[I) Add a node Xm connected to all X nodes.
Add a node Ym connected to all Y nodes.
Remove all nodes of I.
Remove all nodes of V n R, but insert additional edges connecting the neighbours. of all removed nodes.
Use the algorithm in Takata (2010) to list all sets separating Xm and Ym. The correctness is shown by Textor and Lis´kiewicz (2011) for adjustment sets and generalizes directly to mseparators, because after moralization, both problems are equivalent to enumerating vertex cuts of an undirected graph. The handling of I is shown by Acid and de Campos (1996).
Let N(V) denote all nodes adjacent to V, and Sp(V) denote all spouses of V, i.e., nodes W such that W $ V 2 E. The adjustment amenability of a graph G w.r.t sets X; Y can be tested with the following algorithm: function TESTADJUSTMENTAMENABILITY(G; X; Y) for all D in Ch(X) \ PCP(X; Y) do
C ; A ; function CHECK(V) if C[V] then return A[V] C[V] true A[V] ((Pa(V) [ Sp(V)) n N(D) , ;) for all W 2 Sp(V) \ Pa(D) do
if CHECK(W) then A[V] true return A[V] for all X in X \ Pa(D) do if :CHECK(X) then
return false The algorithm checks for every edge X ! D on a proper causal path to Y whether it satisfies the amenability conditions of Lemma 5.5 by searching a collider path through the parents of D to a node Z not connected to D; note that condition (1) of Lemma 5.5 is identical to condition (2) with an empty collider path. Since CHECK performs a depth-firstsearch by checking every node only once and then continuing to its neighbors, each iteration of the outer for-loop in the algorithm runs in linear time O(n + m). Therefore, the entire algorithm runs in O(k(n + m)) where k jCh(X)j.