E FFECT I DENTIFICATION IN ADMG S

AND

GM S

Causal Effect Identification in Acyclic Directed Mixed Graphs and
Gated Models

arXiv:1612.07512v2 [stat.ML] 28 May 2017

Jose M. Peña
Marcus Bendtsen

JOSE . M . PENA @ LIU . SE
MARCUS . BENDTSEN @ LIU . SE

Department of Computer and Information Science
Linköping University (Sweden)

Abstract
We introduce a new family of graphical models that consists of graphs with possibly directed,
undirected and bidirected edges but without directed cycles. We show that these models are suitable
for representing causal models with additive error terms. We provide a set of sufficient graphical
criteria for the identification of arbitrary causal effects when the new models contain directed and
undirected edges but no bidirected edge. We also provide a necessary and sufficient graphical
criterion for the identification of the causal effect of a single variable on the rest of the variables.
Moreover, we develop an exact algorithm for learning the new models from observational and
interventional data via answer set programming. Finally, we introduce gated models for causal
effect identification, a new family of graphical models that exploits context specific independences
to identify additional causal effects.
Keywords: Acyclic directed mixed graphs; causal models; answer set programming.

1. Introduction
Undirected graphs (UGs), bidirected graphs (BGs), and directed and acyclic graphs (DAGs) have extensively been studied as representations of independence models. DAGs have also been studied as
representation of causal models, because they can model asymmetric relationships between random
variables. DAGs and UGs (respectively BGs) have been extended into chain graphs (CGs), which
are graphs with possibly directed and undirected (respectively bidirected) edges but without semidirected cycles. Therefore, CGs can model both symmetric and asymmetric relationships between random variables. CGs with possibly directed and undirected edges may represent a different independence model depending on whether the Lauritzen-Wermuth-Frydenberg (LWF) or the AnderssonMadigan-Perlman (AMP) interpretation is considered (Lauritzen, 1996; Andersson et al., 2001).
CGs with possibly directed and bidirected edges have a unique interpretation, the so-called multivariate regression (MVR) interpretation (Cox and Wermuth, 1996). MVR CGs have been extended
by (i) relaxing the semidirected acyclity constraint so that only directed cycles are forbidden, and
(ii) allowing up to two edges between any pair of nodes. The resulting models are called original
acyclic directed mixed graphs (oADMGs) (Richardson, 2003). AMP CGs have also been extended
similarly (Peña, 2016). The resulting models are called alternative acyclic directed mixed graphs
(aADMGs).
In this paper, we combine oADMGs and aADMGs into what we simply call ADMGs. These are
graphs with possibly directed, undirected and bidirected edges but without directed cycles. Moreover, there can be up to three edges between any pair of nodes. This work complements the existing
works for the following reasons. To our knowledge, the only mixed graphical models in the literature that subsume AMP CGs are the already mentioned aADMGs and the so-called marginal
1

P E ÑA

DAG
UC
UA

C

A

AND

B ENDTSEN

oADMG

aADMG

C

C

UB
B

A

B

A

B

̂ is identifiable from the aADMG but not from the oADMG.
Figure 1: Example where p(B∣A)
DAG
UC
UA
A

C

oADMG

aADMG

C

C

UB
B

A

B

A

B

̂ is identifiable from the oADMG but not from the aADMG.
Figure 2: Example where p(B∣A)

AMP CGs (Peña, 2014). However, marginal AMP CGs are simple graphs with possibly directed,
undirected and bidirected edges but without semidirected cycles and, moreover, some constellations of edges are forbidden. Therefore, marginal AMP CGs do not subsume ADMGs. Likewise,
no other family of mixed graphical models that we know of (e.g. oADMGs, summary graphs
(Cox and Wermuth, 1996), ancestral graphs (Richardson and Spirtes, 2002), MC graphs (Koster,
2002) or loopless mixed graphs (Sadeghi and Lauritzen, 2014)) subsume AMP CGs and hence ADMGs. To see it, we refer the reader to the works by Richardson and Spirtes (2002, p. 1025) and
Sadeghi and Lauritzen (2014, Section 4.1).
In addition to represent independence models, some of the families of graphical models mentioned above have been used for causal effect identification, i.e. to determine if the causal effect
of an intervention is computable from observed quantities. For instance, Pearl’s approach to causal
effect identification makes use of oADMGs to represent causal models over the observed variables
(Pearl, 2009). The directed edges represent potential causal relationships, whereas the bidirected
edges represent potential confounding, i.e. a latent common cause. A key feature of Pearl’s approach is that no assumption is made about the functional form of the causal relationships. That
is, each variable A is an unconstrained function of its observed causes P a(A) and its unobserved
causes UA , i.e. A = f (P a(A), UA ). In this paper, we study causal effect identification under
the assumption that A = f (P a(A)) + UA , i.e. under the assumption of additive errors. This is
a rather common assumption in causal discovery, e.g. see (Bühlmann et al., 2014; Janzing et al.,
2009; Peters et al., 2014). Specifically, we show that ADMGs are suitable for representing such
causal models: An undirected edge between two nodes represents potential dependence between
their error terms given the rest of the error terms, as opposed to a bidirected edge that represents potential marginal dependence due to confounding. The reason for studying ADMGs for causal effect
identification is that we may identify more causal effects from them than from oADMGs, since the
2

E FFECT I DENTIFICATION IN ADMG S

AND

GM S

former are tailored to the additive error assumption. We illustrate this question with the example
in Figure 1, which is borrowed from Peña (2016). The ADMGs in the figure represent the causal
model over the observed variables represented by the DAG. The oADMG is derived from the DAG
by keeping the directed edges between observed variables, and adding a bidirected edge between
two observed variables if and only if they have a confounder (Tian and Pearl, 2002b, Section 5). The
aADMG is derived from the DAG by keeping the directed edges between observed variables, and
adding an undirected edge between two observed variables if and only if their unobserved causes
are not separated in the DAG given the unobserved causes of the rest of the observed variables.
̂ is not identifiable from the oADMG
Clearly, the effect on B of an intervention on A, i.e. p(B∣A),
(Pearl, 2009, p. 94), but it is identifiable from the aADMG and is given by
̂ = ∑ p(B∣A, c)p(c).
p(B∣A)
c

To see it, recall that we assume additive noise. This implies that C determines UC , which blocks
the path A ← UA → UC → UB → B in the DAG. This can also be seen directly in the aADMG, as
C blocks the path A − C − B. Therefore, we can identify the desired causal effect by just adjusting
for C, since C blocks all non-causal paths from A to B. It is worth mentioning that there are also
cases where the oADMG allows for causal effect identification whereas the aADMG does not. One
such case is shown in Figure 2, where we have just replaced the edge UC → UB in Figure 1 with the
̂ is not identifiable from the aADMG by Theorem 13 in this
edge UC ← UB . Specifically, p(B∣A)
̂ = p(B∣A). Therefore, oADMGs
article, whereas it is identifiable from the oADMG, i.e. p(B∣A)
and aADMGs are more complementary than competing causal models. To further illustrate our
point, we make the example in Figure 1 more concrete by turning it into the following invented
gambling game:
UA ∼ N (0, σ)
UC ∼ N (UA , σ)
UB ∼ N (UC , σ)
A = UA
C = UC
B = A + UB .

(1)

In other words, UA , UB and UC represent three unobserved randomly chosen numbers that determine three observed numbers represented by A, B and C. Now, we are told that A has been set
to value a independently of the value of UA . We are asked to bet on the value of B. To make an
̂ = a). However, all we are provided with is p(A, B, C)
informed bet, we would like to know p(B∣A
and the oADMG or the aADMG in Figure 1. As discussed above, p(A, B, C) and the aADMG are
enough for our purpose, whereas p(A, B, C) and the oADMG are not. As also discussed above,
this situation can be reversed if we modify the game as follows:
UC ∼ N (UA + UB , σ)
UB ∼ N (0, σ)

(2)

that is, p(A, B, C) and the oADMG are now enough for our purpose, whereas p(A, B, C) and the
aADMG are not.
3

P E ÑA

B ENDTSEN

̂≤ 0
A

C
A

AND

B

̂> 0
A

C
A

B

̂ > 0, whereas the
Figure 3: Gated model with two contexts. The aADMG is used in the context A
̂
̂
oADMG is used in the context A ≤ 0. This ensures that p(B∣A) is identifiable.

As mentioned, aADGMs were proposed by Peña (2016), who mainly studied them as representation of statistical independence models. In particular, their global, local and pairwise Markov
properties were studied. Their usage to represent causal models was also discussed, but no formal
criteria or calculus for causal effect identification from them were given. This paper is a first step to
fill that gap. In particular, we present a calculus similar to the do-calculus by Pearl (2009), and a decomposition of the distribution over the observed random variables similar to the Q-decomposition
by Tian and Pearl (2002a,b). From this calculus and decomposition, we derive a set of sufficient
graphical criteria for the identification of arbitrary causal effects from aADMGs. We also provide
a necessary and sufficient graphical criterion for the identification of the causal effect of a single
variable on the rest of the variables. Our ambition is to extend these results to ADMGs in the future.
We have seen above that choosing an appropriate causal model is crucial for identifying the
causal effect of interest. However, the domain being modeled may consist of different regimes or
contexts, and the appropriate causal model for one regime may not be quite so for another. For
instance, consider again the gambling games described above. Assume that we are told that the
̂ > 0, whereas the modified one (Equation
original gambling game (Equation 1) applies when A
̂
2) applies when A ≤ 0. Therefore, the aADMG in Figure 1 should be preferred in the context
̂ > 0 since it allows identifying p(B∣A).
̂ For the same reason, the oADMG in Figure 2 should
A
̂
be preferred in the context A ≤ 0. One may hope that combining aADMGs and oADMGs into
ADMGs will help to identify a single model that is appropriate for both contexts. Whether this will
be the case is not clear to us as of today (as mentioned above, we do not know yet how to perform
causal effect identification in ADMGs). In the meantime, we propose to solve this problem with
the help of the gated model in Figure 3. In this model, we have the aADMG and the oADMG
̂ > 0 we shall use the aADMG to the left, and when A
̂≤0
connected with gates such that when A
then we shall use the oADMG to the right. Gated models have previously been used to model
independence models induced by dynamical systems with recurrent regimes (Bendtsen and Peña,
2016a,b; Bendtsen, 2017). However, this is the first work to use them for causal effect identification.
We will moreover show how gated models allow us to represent causal phenomena such as unstable
interventions, non-deterministic outcomes of interventions, and mechanism dependent outcome of
interventions.
The rest of the paper is organized as follows. Section 2 introduces the notation and some preliminary concepts. Section 3 introduces two equivalent separation criteria for ADMGs, which
define their semantics as a formalism to represent independence models. Section 4 provides an
intuitive causal interpretation of ADMGs as systems of structural equations with additive and correlated errors. Section 4 also describes an exact algorithm for learning ADMGs from observational
and interventional data via answer set programming (Gelfond and Lifschitz, 1988; Niemelä, 1999;
4

E FFECT I DENTIFICATION IN ADMG S

A

B

E

A

B

C

E

A

AND

GM S

B

C

D

E

F
Figure 4: Examples of ADMGs.

Simons et al., 2002). Section 5 presents graphical criteria for causal effect identification in aADMGs. Section 6 is devoted to gated models for causal effect identification. Finally, Section 7 closes
the paper with a summary and future lines of research.

2. Preliminaries
In this section, we recall some concepts about graphical models. Unless otherwise stated, all the
graphs and probability distributions in this paper are defined over a finite set V . The elements of V
are not distinguished from singletons. An ADMG G is a graph with possibly directed, undirected
and bidirected edges but without directed cycles, i.e. G cannot have a subgraph A → . . . → A. There
may be up to three edges between any pair of nodes, but the edges must be different. Edges between
a node and itself are not allowed. See Figure 4 for examples of ADMGs. Note that oADMGs are
ADMGs without undirected edges, and aADMGs are ADMGs without bidirected edges.
Given an ADMG G, we represent with A ⊸
← B that A → B or A ↔ B (or both) is in G.
The parents of X ⊆ V in G are P aG (X) = {A∣A → B is in G with B ∈ X}. The children of
X ⊆ V in G are ChG (X) = {B∣A → B is in G with A ∈ X}. The neighbors of X ⊆ V in G are
N eG (X) = {A∣A − B is in G with B ∈ X}. The spouses of X ⊆ V in G are SpG (X) = {A∣A ↔ B
is in G with B ∈ X}. The descendants of X ⊆ V in G are DeG (X) = {B∣A → . . . → B is in
G with A ∈ X or B ∈ X}. The ancestors of X ⊆ V in G are AnG (X) = {A∣A → . . . → B is
in G with B ∈ X or A ∈ X}. Moreover, if AnG (X) = X then we say that X is an ancestral set.
A route between a node V1 and a node Vn on G is a sequence of (not necessarily distinct) nodes
V1 , . . . , Vn such that Vi and Vi+1 are adjacent in G for all 1 ≤ i < n. We do not distinguish between
the sequences V1 , . . . , Vn and Vn , . . . , V1 , i.e. they represent the same route. If the nodes in the route
are all distinct, then the route is called a path. The subgraph of G induced by X ⊆ V , denoted as
GX , is the graph over X that has all and only the edges in G whose both ends are in X. Similarly,
← B is in GX if and only if A ⊸
←B
let GX denote the graph over X ⊆ V constructed as follows: A ⊸
X
is in G, whereas A − B is in G if and only if A − B is in G or A − V1 − . . . − Vn − B is in G with
V1 , . . . , Vn ∉ X.

3. Separation Criteria
In this section, we introduce two equivalent separation criteria for ADMGs that define their semantics as a formalism to represent independence models. Specifically, a node C on a path in an ADMG
←C←
⊸ B or A ⊸
← C − B is a subpath. Moreover, the
G is said to be a collider on the path if A ⊸
path is said to be connecting given Z ⊆ V when
• every collider on the path is in AnG (Z), and
5

P E ÑA

AND

B ENDTSEN

• every non-collider C on the path is outside Z unless A−C −B is a subpath and P aG (C)∖Z ≠
∅ or SpG (C) ≠ ∅.
Let X, Y and Z denote three disjoint subsets of V . When there is no path in G connecting a
node in X and a node in Y given Z, we say that X is separated from Y given Z in G and denote
it as X ⊥ G Y ∣Z. Note that this separation criterion generalizes the existing separation criteria for
UGs, BGs, DAGs, AMP and MVR CGs, oADMGs and aADMGs. In other words, we can use the
criterion above on all these families of graphical models.
Unlike in UGs, BGs, DAGs, and AMP and MVR CGs, two non-adjacent nodes in an ADMG
are not necessarily separated. For example, A ⊥ G E∣Z does not hold for any Z in the ADMGs in Figure 4. This drawback is shared by oADMGs (Evans and Richardson, 2013, p. 752),
summary graphs and MC graphs (Richardson and Spirtes, 2002, p. 1023), and ancestral graphs
(Richardson and Spirtes, 2002, Section 3.7). For ancestral graphs, the problem can be solved by
adding edges to the graph without altering the separations represented until every missing edge corresponds to a separation (Richardson and Spirtes, 2002, Section 5.1). A similar solution does not
exist for ADMGs (we omit the details).
Finally, we present an alternative to the separation criterion introduced above. The alternative
is easier to work with in some cases. The theorem below proves that both criteria are equivalent.
←C←
⊸B
Specifically, a node C on a route in an ADMG G is said to be a collider on the route if A ⊸
or A ⊸
← C − B is a subroute. Note that maybe A = B. Moreover, the route is said to be connecting
given Z ⊆ V when
• every collider on the route is in Z, and
• every non-collider C on the route is outside Z unless A−C −B is a subroute and SpG (C) ≠ ∅.
Let X, Y and Z denote three disjoint subsets of V . When there is no route in G connecting a
node in X and a node in Y given Z, we say that X is separated from Y given Z in G and denote it
as X ⊥ G Y ∣Z.
Theorem 1 Given α, β ∈ V and Z ⊆ V ∖ (α ∪ β), there is a path in an ADMG G connecting α and
β given Z if and only if there is a route in G connecting α and β given Z.
Proof The only if part is trivial. To prove the if part, first replace every edge A ↔ B in G with the
subgraph A ← λAB → B, where λAB is a newly created node. The result is an aADMG G′ over
V ∪ λ, where λ denotes all the newly created nodes. Then, note that the route ̺ in G connecting
α and β given Z can be transformed into a route ̺′ in G′ connecting α and β given Z by simply
replacing every edge A ↔ B in ̺ with the subgraph A ← λAB → B. To see that ̺′ is connecting, it
may be worth noting that if A − C − B is a subroute of ̺ with C ∈ Z and P aG (C) ∖ Z = ∅, then
SpG (C) ≠ ∅ for ̺ to be connecting and, thus, P aG′ (C) ∖ Z ≠ ∅ since λCD ∈ P aG′ (C) for any
D ∈ SpG (C), and λCD ∉ Z since Z ⊆ V . Finally, note that ̺′ can be transformed into a path ρ′ in
G′ connecting α and β given Z (Peña, 2016, Theorem 2), which can be transformed into a path ρ
in G connecting α and β given Z by simply replacing every subpath A ← λAB → B of ρ′ with the
edge A ↔ B. To see that ρ is connecting, it may be worth noting that if A − C − B is a subpath of
ρ′ with C ∈ Z and P aG′ (C) ∖ Z ≠ ∅, then A − C − B is a subpath of ρ with P aG (C) ∖ Z ≠ ∅ or
SpG (C) ≠ ∅.

6

E FFECT I DENTIFICATION IN ADMG S

AND

GM S

Table 1: Magnification of an ADMG.
1
2
3
4
5
6
7
8

Set G′ = G
For each edge A ↔ B in G
Add the node λAB to G′
Replace A ↔ B in G′ with the subgraph A ← λAB → B
For each node A in G
Add the node ǫA and the edge ǫA → A to G′
For each edge A − B in G
Replace A − B in G′ with the edge ǫA − ǫB

4. Causal Interpretation and Learning Algorithm
The contribution of this section is two-fold. First, it provides an intuitive causal interpretation of
ADMGs as systems of structural equations with additive and correlated errors. Second, it describes
an exact algorithm for learning ADMGs from observational and interventional data via answer set
programming (Gelfond and Lifschitz, 1988; Niemelä, 1999; Simons et al., 2002).
4.1 Causal Interpretation
Let us assume that V is normally distributed. In this section, we show that an ADMG G can
be interpreted as a system of structural equations with correlated errors. Specifically, the system
includes an equation for each A ∈ V , which is of the form
A=

∑
B∈P aG (A)

αAB B +

∑

βAB λAB + ǫA

(3)

B∈SpG (A)

where αAB and βAB denote linear coefficients, and λAB and ǫA denote unobserved terms due to
latent causes and errors, respectively. In other words, we divide the unobserved causes of A into
those shared with other observed variables (latent causes or confounders) and those exclusive of A
(errors). The undirected edges in G indicate potential correlation between error terms. The latent
causes and errors are represented implicitly in G. They can be represented explicitly by magnifying
G into the ADMG G′ as shown in Table 1. The magnification basically consists in adding nodes for
the unobserved terms λAB and ǫA to G and, then, connecting them appropriately. Figure 5 shows an
example. Note that Equation 3 implies that every node A ∈ V is determined by P aG′ (A). Likewise,
ǫA is determined by A∪P aG′ (A)∖ǫA , and λAB is determined by A∪P aG′ (A)∖λAB . Let ǫ denote
all the error nodes ǫA in G′ , and let λ denote all the latent causes λAB in G′ . Formally, we say that
A ∈ V ∪ λ ∪ ǫ is determined by Z ⊆ V ∪ λ ∪ ǫ when A ∈ Z or A is a function of Z. We use Dt(Z)
to denote all the nodes that are determined by Z. From the point of view of the separations, that a
node outside the conditioning set of a separation is determined by the conditioning set has the same
effect as if the node were actually in the conditioning set. Bearing this in mind, it is not difficult
to see that, as desired, G and G′ represent the same separations over V . The following theorem
formalizes this result.
Theorem 2 Let G denote an ADMG. Then, X ⊥ G Y ∣Z if and only if X ⊥ G′ Y ∣Z for all X, Y and Z
disjoint subsets of V .
7

P E ÑA

AND

B ENDTSEN

G′

G
A

B

C

D

E

F

ǫA

A

B

ǫB

ǫC

C

D

ǫD

ǫE

E

F

ǫF

λEF
Figure 5: Example of the magnification of an ADMG.
Proof Let G′4 denote the graph G′ in Table 1 immediately after line 4. Note that G′4 is an aADMG
over V ∪λ. We know that X ⊥ G′4 Y ∣Z if and only if X ⊥ G′ Y ∣Z (Peña, 2016, Theorem 9). Therefore,
it suffices to show that every path in G connecting α and β given Z can be transformed into a path
in G′4 connecting α and β given Z and vice versa, with α, β ∈ V and Z ⊆ V ∖ (α ∪ β). This can be
proven in much the same way as Theorem 1. Specifically, a path ρ in G connecting α and β given
Z can be transformed into a path ρ′ in G′4 connecting α and β given Z by simply replacing every
edge A ↔ B in ρ with the subgraph A ← λAB → B. Finally, a path ρ′ in G′4 connecting α and β
given Z can be transformed into a path ρ in G connecting α and β given Z by simply reversing the
previous transformation.
Let λ ∼ N (0, Λ) such that Λ is diagonal, and ǫ ∼ N (0, Σ) such that (Σ−1 )ǫA ,ǫB = 0 if ǫA − ǫB
is not in G′ . Then, G can be interpreted as a system of structural equations of the form of Equation
3 whose errors are correlated as follows
covariance(ǫA , ǫB ) = ΣǫA ,ǫB

(4)

for all A, B ∈ V . The next two theorems confirm that this causal interpretation of ADMGs works as
intended. Let X, Y and Z denote three disjoint subsets of V . Hereinafter, we represent by X ⊥ p Y ∣Z
that X and Y are conditionally independent given Z in a probability distribution p.
Theorem 3 Let G and p denote an ADMG and a probability distribution over V . If p is specified
by Equations 3 and 4, then it is Gaussian.
Proof For each edge A ↔ B in G, add the node λAB to G. Then, replace every edge A ↔ B in
G with the subgraph A ← λAB → B. Note that G is now an aADMG over V ∪ λ. Moreover, recall
that λ ∼ N (0, Λ). Then, add the equation
λAB = ǫ′AB

(5)

and let ǫ′ ∼ N (0, Λ), where ǫ′ denotes all the newly created error terms ǫ′AB . Then, every probability distribution p(V ∪ λ) specified by Equations 3-5 is Gaussian (Peña, 2016, Theorem 10), which
implies the desired result.

8

E FFECT I DENTIFICATION IN ADMG S

AND

GM S

Table 2: Intervention of X on an ADMG.
1
2
3
4

Delete from G all the edges A ⊸
← B with B ∈ X
For each path A − V1 − . . . − Vn − B in G with A, B ∉ X and V1 , . . . , Vn ∈ X
Add the edge A − B to G
Delete from G all the edges A − B with B ∈ X

It is worth mentioning that the opposite of the theorem above is not true. This negative result is
inherited from oADMGs, for which there are Gaussian probability distributions over V that cannot
be specified by Equations 3 and 4 (Richardson and Spirtes, 2002, p. 1019).
Theorem 4 Let G and p denote an ADMG and a probability distribution over V . If p is specified
by Equations 3 and 4, then X ⊥ G Y ∣Z implies that X ⊥ p Y ∣Z for all X, Y and Z disjoint subsets of
V.
Proof Transform G into an aADMG over V ∪ λ as shown in the proof of Theorem 3. Then,
X ⊥ G Y ∣Z implies that X ⊥ p(V ∪λ) Y ∣Z (Peña, 2016, Theorem 11), which implies the desired result.

A more intuitive account of the causal interpretation of ADMGs introduced above is as follows.
We interpret the edge A → B as A being a potential cause of B. We interpret the edge A ↔ B
as A and B being potentially marginally dependent due to an unobserved common cause λAB ,
i.e. a confounder. The unobserved causes of the node A that are not shared with any other node
are grouped into an error term ǫA . We interpret the edge A − B as ǫA and ǫB being potentially
conditionally dependent given the rest of the error terms. This causal interpretation of ADMGs
generalizes that of the oADMGs and aADMGs. Recall however that the noise in the oADMGs is
not necessarily additive normal.
Given the above causal interpretation of an ADMG G and assuming autonomous causal relationships (i.e. external changes to one does not affect the others), intervening on X ⊆ V so that
X is no longer under the influence of its usual causes amounts to replacing the right-hand side of
the equations for the random variables in X with expressions that do not involve their usual causes
(Pearl, 2009, Section 3.2). For simplicity, we only consider interventions that set X to a fixed value
x, which then corresponds to modifying the system of structural equations by replacing the equation for every Xi ∈ X with the equation Xi = xi , where xi is the value of Xi that is consistent
with x. Graphically, it amounts to modifying G as shown in Table 2. Line 1 is shared with an
intervention on an oADMG. Lines 2-4 are best understood in terms of the magnified ADMG G′ :
They correspond to marginalizing the error nodes associated with the nodes in X out of G′ǫ , the
UG that represents the correlation structure of the error nodes. In other words, lines 2-4 replace
G′ǫ with (G′ǫ )ǫ∖ǫX , the marginal graph of G′ǫ over ǫ ∖ ǫX . This makes sense since ǫX is no longer
associated with X due to the intervention and, thus, we may want to marginalize it out because it is
unobserved. This is exactly what lines 2-4 imply. Note that the ADMG after the intervention and
the magnified ADMG after the intervention represent the same separations over V , by Theorem 2.
This treatment of interventions on ADMGs generalizes the treatment for oADMGs and aADMGs
(Pearl, 2009; Peña, 2016).
9

P E ÑA

AND

B ENDTSEN

We can also extend the separation criteria for ADMGs to account for interventions. Specifically, let X ⊥ GW
Y ∣Z, W denote that X is separated from Y given Z in an ADMG G after having
̂
intervened on W , where X, Y , Z and W are disjoint subsets of V . Likewise, let X ⊥ pW
Y ∣Z, W
̂
represent that X and Y are conditionally independent given Z in a probability distribution p after having intervened on W . The corollary below follows from Theorem 4, and provides further
evidence that the causal interpretation of ADMGs introduced above works as intended.
Corollary 5 Let G and p denote an ADMG and a probability distribution over V . If p is specified
by Equations 3 and 4. Then, X ⊥ GW
Y ∣Z, W implies that X ⊥ pW
Y ∣Z, W for all X, Y , Z and W
̂
̂
disjoint subsets of V .
Recall from Section 3 that two non-adjacent nodes in an ADMG G are not necessarily separated.
This is not true when interventions are considered, because A⊥ GW
B∣W with W = V ∖ {A, B} for
̂
all non-adjacent nodes A and B of G. Therefore, some missing edges in G convey information
about the observational regime, and some others about the interventional regime.
Finally, note that Equations 3 and 4 specify each node as a linear function of its parents with
additive normal noise. The equations can be generalized to nonlinear or nonparametric functions as
long as the noise remains additive normal. That is, for any A ∈ V
A = f (P aG′ (A) ∖ ǫA ) + ǫA
with ǫ ∼ N (0, Σ) such that (Σ−1 )ǫA ,ǫB = 0 if ǫA − ǫB is not in G′ . That the noise is additive normal
ensures that ǫA is determined by A ∪ P aG′ (A) ∖ ǫA , which is needed for Theorem 2 to remain valid
which, in turn, is needed for Theorem 4 and Corollary 5 to remain valid.
4.2 Learning Algorithm
In this section, we introduce an exact algorithm for learning ADMGs from observational and interventional data via answer set programming (ASP), which is a declarative constraint satisfaction
paradigm that is well-suited for solving computationally hard combinatorial problems (Gelfond and Lifschitz,
1988; Niemelä, 1999; Simons et al., 2002). ASP represents constraints in terms of first-order logical
rules. Therefore, when using ASP, the first task is to model the problem at hand in terms of rules so
that the set of solutions implicitly represented by the rules corresponds to the solutions of the original problem. One or multiple solutions to the original problem can then be obtained by invoking an
off-the-shelf ASP solver on the constraint declaration. Each rule in the constraint declaration is of
the form head :- body. The head contains an atom, i.e. a fact. The body may contain several
literals, i.e. negated and non-negated atoms. Intuitively, the rule is a justification to derive the head
if the body is true. The body is true if its non-negated atoms can be derived, and its negated atoms
cannot. A rule with only the head is an atom. A rule without the head is a hard-constraint, meaning that satisfying the body results in a contradiction. Soft-constraints are encoded as rules of the
form :˜ body. [W], meaning that satisfying the body results in a penalty of W units. The ASP
solver returns the solutions that meet the hard-constraints and minimize the total penalty due to the
soft-constraints. In this work, we use the ASP solver clingo (Gebser et al., 2011), whose underlying algorithms are based on state-of-the-art Boolean satisfiability solving techniques (Biere et al.,
2009).
Table 3 shows the ASP encoding of our learning algorithm. The predicate node(X) in rule 1
represents that X is a node.
The predicates line(X,Y,I), arrow(X,Y,I) and
10

E FFECT I DENTIFICATION IN ADMG S

AND

GM S

Table 3: ASP encoding of the learning algorithm.
%
%
%
%
%
%

input predicates
nodes(N): N is the number of nodes
set(X): X is the index of a set of nodes
dep(X,Y,C,I,W) (resp. indep(X,Y,C,I,W)): the nodes X and Y are dependent (resp.
independent) given the set of nodes C
after having intervened on the node I

% nodes
node(X) :- nodes(N), X=1..N.

% rule 1

% edges
{ line(X,Y,0) } :- node(X), node(Y), X != Y.
{ arrow(X,Y,0) } :- node(X), node(Y), X != Y.
{ biarrow(X,Y,0) } :- node(X), node(Y), X != Y.
line(X,Y,I) :- line(X,Y,0), node(I), X != I, Y != I, I > 0.
line(X,Y,I) :- line(X,I,0), line(I,Y,0), node(I), X != Y, I > 0.
arrow(X,Y,I) :- arrow(X,Y,0), node(I), Y != I, I > 0.
biarrow(X,Y,I) :- biarrow(X,Y,0), node(I), X != I, Y != I, I > 0.
line(X,Y,I) :- line(Y,X,I).
:- arrow(X,Y,I), arrow(Y,X,I).
biarrow(X,Y,I) :- biarrow(Y,X,I).

%

2

%
%

4
5

%
%

8
9

%

11

%

12

%

14

%
%

15
16

%

17

%

33

%

34

%

37

% satisfy all dependences
:- dep(X,Y,C,I,W), not con(X,Y,C,I).

%

38

% maximize the number of satisfied independences
:˜ indep(X,Y,C,I,W), con(X,Y,C,I). [W,X,Y,C,I]

%

39

%

40

%

42

% directed acyclity
ancestor(X,Y) :- arrow(X,Y,0).
ancestor(X,Y) :- ancestor(X,Z), ancestor(Z,Y).
:- ancestor(X,Y), arrow(Y,X,0).
% set membership
inside_set(X,C) :- node(X), set(C), 2**(X-1) & C != 0.
outside_set(X,C) :- node(X), set(C), 2**(X-1) & C = 0.
% end_line/head/tail(X,Y,C,I) means that there is a connecting route
% from X to Y given C that ends with a line/arrowhead/arrowtail
% single edge route
end_line(X,Y,C,I) :end_head(X,Y,C,I) :end_head(X,Y,C,I) :end_tail(X,Y,C,I) :-

line(X,Y,I), outside_set(X,C).
arrow(X,Y,I), outside_set(X,C).
biarrow(X,Y,I), outside_set(X,C).
arrow(Y,X,I), outside_set(X,C).

% connection through
end_line(X,Y,C,I) :end_line(X,Y,C,I) :end_line(X,Y,C,I) :end_head(X,Y,C,I) :end_head(X,Y,C,I) :end_head(X,Y,C,I) :end_head(X,Y,C,I) :end_tail(X,Y,C,I) :-

non-collider
end_line(X,Z,C,I),
end_line(X,Z,C,I),
end_tail(X,Z,C,I),
end_line(X,Z,C,I),
end_head(X,Z,C,I),
end_tail(X,Z,C,I),
end_tail(X,Z,C,I),
end_tail(X,Z,C,I),

line(Z,Y,I), outside_set(Z,C).
line(Z,Y,I), biarrow(Z,W,I).
line(Z,Y,I), outside_set(Z,C).
arrow(Z,Y,I), outside_set(Z,C).
arrow(Z,Y,I), outside_set(Z,C).
arrow(Z,Y,I), outside_set(Z,C).
biarrow(Z,Y,I), outside_set(Z,C).
arrow(Y,Z,I), outside_set(Z,C).

% connection through
end_line(X,Y,C,I) :end_head(X,Y,C,I) :end_head(X,Y,C,I) :end_tail(X,Y,C,I) :end_tail(X,Y,C,I) :-

collider
end_head(X,Z,C,I),
end_line(X,Z,C,I),
end_head(X,Z,C,I),
end_line(X,Z,C,I),
end_head(X,Z,C,I),

line(Z,Y,I), inside_set(Z,C).
biarrow(Z,Y,I), inside_set(Z,C).
biarrow(Z,Y,I), inside_set(Z,C).
arrow(Y,Z,I), inside_set(Z,C).
arrow(Y,Z,I), inside_set(Z,C).

% derived non-separations
con(X,Y,C,I) :- end_line(X,Y,C,I), X != Y, outside_set(Y,C).
con(X,Y,C,I) :- end_head(X,Y,C,I), X != Y, outside_set(Y,C).
con(X,Y,C,I) :- end_tail(X,Y,C,I), X != Y, outside_set(Y,C).
con(X,Y,C,I) :- con(Y,X,C,I).

% minimize the number of lines/arrows
:˜ line(X,Y,0), X < Y. [1,X,Y,1]
:˜ arrow(X,Y,0). [1,X,Y,2]
:˜ biarrow(X,Y,0), X < Y. [1,X,Y,3]
% show results
#show.
#show line(X,Y) : line(X,Y,0), X < Y.
#show arrow(X,Y) : arrow(X,Y,0).
#show biarrow(X,Y) : biarrow(X,Y,0), X < Y.

11

P E ÑA

AND

B ENDTSEN

Figure 6: ASP encoding of the (in)dependences in the domain.
nodes(3).
set(0..7).

% three nodes
% all subsets of three nodes

% observations
dep(1,2,0,0,1).
dep(1,2,4,0,1).
dep(2,3,0,0,1).
dep(2,3,1,0,1).
dep(1,3,0,0,1).
dep(1,3,2,0,1).
% interventions on the node 1
dep(1,2,0,1,1).
dep(1,2,4,1,1).
dep(2,3,1,1,1).
dep(1,3,0,1,1).
dep(1,3,2,1,1).
% interventions on the node 2
indep(1,2,0,0,2,1).
indep(1,2,4,0,2,1).
dep(2,3,0,2,1).
dep(2,3,1,2,1).
indep(1,3,2,2,1).
% interventions on the node 3
dep(1,2,4,0,3,1).
indep(2,3,0,3,1).
indep(2,3,1,3,1).
indep(1,3,0,3,1).
indep(1,3,2,3,1).

biarrow(X,Y,I) represent that there is an undirected, directed and bidirected edge from the
node X to the node Y after having intervened on the node I. The observational regime corresponds
to I = 0. The rules 2-4 encode a non-deterministic guess of the edges for the observational regime,
which means that the ASP solver will implicitly consider all possible graphs during the search,
hence the exactness of the search. The edges under the observational regime are used in the rules
5-8 to define the edges in the graph after having intervened on I, following the description in Section 4. Therefore, the algorithm assumes continuous random variables and additive normal noise
when the input contains interventions. The random variables do not need to be normally distributed
though, as discussed at the end of Section 4.1. The algorithm makes no such assumption when the
input consists of just observations. The rules 9-11 enforce the fact that bidirected and undirected
edges are symmetric and that there is at most one directed edge between two nodes. The predicate
ancestor(X,Y) represents that the node X is an ancestor of the node Y . The rules 12-14 enforce that the graph has no directed cycles. The predicates in the rules 15-16 represent whether a
node X is or is not in a set of nodes C. The rules 17-33 encode the alternative separation criterion
introduced in Section 3. The predicate con(X,Y,C,I) in rules 34-37 represents that there is a
connecting route between the node X and the node Y given the set of nodes C after having intervened on the node I. The rule 38 enforces that each dependence in the input must correspond to a
connecting route. The rule 39 represents that each independence in the input that is not represented
implies a penalty of W units. The rules 40-42 represent a penalty of 1 unit per edge. Other penalty
rules can be added similarly.
Table 6 illustrates with an example how to encode the (in)dependences in the probability distribution at hand, e.g. as determined from some available data. Specifically, the predicate nodes(3)
represents that there are three nodes in the domain at hand, and the predicate set(0..7) represents that there are eight sets of nodes, indexed from 0 (empty set) to 7 (full set). The predicate
12

E FFECT I DENTIFICATION IN ADMG S

1

2

3

1

2

3

AND

1

GM S

2

3

Figure 7: ADMGs that represent the (in)dependences in the domain.
indep(X,Y,C,I,W) (respectively dep(X,Y,C,I,W)) represents that the nodes X and Y are
conditionally independent (respectively dependent) given the node set index C after having intervened on the node I. Observations correspond to I = 0. The penalty for failing to represent an
(in)dependence is W . The penalty for failing to represent a dependence is actually superfluous in
our algorithm, since rule 38 in Table 3 enforces that all the dependences in the input are represented
by the graph in the output. Note also that it suffices to specify all the (in)dependences between pair
of nodes, because these identify uniquely the rest of the independences in the probability distribution (Studený, 2005, Lemma 2.2). Note also that we do not assume that the probability distribution
at hand is faithful to some ADMG or that it satisfies the composition property, as it is the case in
most heuristic learning algorithms.
By calling the ASP solver with the encodings of the learning algorithm and the (in)dependences in the domain, the solver will essentially perform an exhaustive search over the space of
graphs, and will output the graphs with the smallest penalty. Specifically, when only the observations are used (i.e. the last 15 lines of Table 6 are removed), the learning algorithm finds 104 optimal
models, including one UG, one BG, six DAGs, 13 AMP CGs, 13 MVR CGs, 37 original ADMGs,
and 37 alternative ADMGs. When all the observations and interventions available are used, the
learning algorithm finds two optimal models. These are the models on the left and center of Figure
7. This is the expected result given the last 15 lines in Table 6. The rightmost model in Figure 7 is
not in the output because, although it is indistinguishable from the other two given the observations
and interventions in the input, it has more edges and thus receives a larger penalty, which makes it
suboptimal.
It is worth mentioning that the example above is just illustrative and, thus, we have made use of
an oracle to detect (in)dependencies in the domain at hand. In reality, (in)dependencies are detected
on the basis of a finite sample and, thus, conflicts between them may exist. A solution for conflict
resolution within the ASP framework has been proposed by Hyttinen et al. (2014). This solution has
moreover been included in the ASP algorithm for learning LWF CGs proposed by Sonntag et al.
(2015). Since the latter has been the basis for our learning algorithm in Table 3, we expect that
the conflict resolution of Hyttinen et al. (2014) can also be adapted to our algorithm for enhanced
performance in practice.
Finally, the ASP code in Table 3 can easily be modified to learn some subfamilies of ADMGs
such as
• original ADMGs by adding :- line(X,Y,0).
• alternative ADMGs by adding :- biarrow(X,Y,0).
• AMP CGs by adding :- biarrow(X,Y,0)., :- line(X,Y,0), arrow(X,Y,0).
and ancestor(X,Y) :- line(X,Y,0).
• MVR CGs by adding :- line(X,Y,0)., :- biarrow(X,Y,0), arrow(X,Y,0).
and ancestor(X,Y) :- biarrow(X,Y,0).
• DAGs by adding :- line(X,Y,0). and :- biarrow(X,Y,0).
13

P E ÑA

AND

B ENDTSEN

• UGs by adding :- arrow(X,Y,0). and :- biarrow(X,Y,0).
• BGs by adding :- arrow(X,Y,0). and :- line(X,Y,0).

5. Causal Effect Identification
This section presents graphical criteria for causal effect identification in aADMGs. Some criteria
are based on a calculus similar to the do-calculus by Pearl (2009), and some on a decomposition of
the distribution over V similar to the Q-decomposition by Tian and Pearl (2002a,b).
5.1 Calculus-Based Causal Effect Identification
In this section, we present a new calculus for causal effect identification from aADMGs. The
calculus consists of three rules that may transform a causal effect expression into an expression that
can be computed from observed quantities.
Theorem 6 Let G be an aADMG. Let X, Y , Z and W be disjoint subsets of variables. Then, we
have the following rules.
• Rule 1 (insertion/deletion of observations):
̂ Z, W ) = p(Y ∣X,
̂ W ) if Y ⊥ G Z∣X, W.
p(Y ∣X,
̂
X
• Rule 2 (intervention/observation exchange):
̂ Z,
̂ W ) = p(Y ∣X,
̂ Z, W ) if Y ⊥ G Z∣X, W
p(Y ∣X,
̂Z
X
Ð
→

where GX̂ Z denotes the graph obtained from GX̂ by deleting all directed edges out of Z.
Ð
→

• Rule 3 (insertion/deletion of interventions):
̂ Z,
̂ W ) = p(Y ∣X,
̂ W ) if Y ⊥ G
p(Y ∣X,

ÐÐ→
̂Ð
Z(W )
X

Z∣X, W

where Z(W ) denotes the nodes in Z that are not ancestors of W in GX̂ , and G

ÐÐ→
̂Ð
Z(W )
X

denotes

the graph obtained from GX̂ by deleting all directed and undirected edges into Z(W ).
Proof Rule 1 follows from Corollary 5. The antecedent of rule 2 implies that the only paths between
Y and Z in GX̂ that are not blocked by W ∪X are those that reach Z through its children. Following
Pearl (1995, p. 686), we transform GX̂ into G′X̂ by adding a variable FC and an edge FC → C for all
C ∈ Z. The domain of FC is the same as that of C plus a state labeled idle: FC = c corresponds an
intervention that sets C = c, whereas FC = idle represents that C is observed rather than intervened
upon. Then, the only paths between Y and FZ in G′X̂ that are not blocked by W ∪ X are those that
reach FZ through the children of Z and, thus, they are blocked by Z. Then, observing Z cannot be
distinguished from intervening on Z and, thus, the consequent of rule 2 holds.
The antecedent of rule 3 implies that the only paths between Y and Z in GX̂ that are not blocked
by W ∪ X are those that reach Z through the parents or neighbors of Z(W ). Then, there is no path
between Y and FZ in G′X̂ that is not blocked by W ∪ X. Then, intervening on Z is irrelevant and,
14

E FFECT I DENTIFICATION IN ADMG S

AND

GM S

thus, the consequent of rule 3 holds.
We illustrate the application of the previous theorem with the aADMG in Figure 1. Specifically,
̂ = ∑ p(B∣A,
̂ c)p(c∣A)
̂ = ∑ p(B∣A,
̂ c)p(c) = ∑ p(B∣A, c)p(c)
p(B∣A)
c

c

c

where the first equality is due to marginalization, the second due to rule 3, and the third due to rule
2.
Since producing GX̂ may be a bit involved, the antecedents of the rules can be simplified as
follows.
Theorem 7 Let G be an aADMG. Let X, Y , Z and W be disjoint subsets of variables. Then, we
have the following rules.
• Rule 1 (insertion/deletion of observations):
̂ Z, W ) = p(Y ∣X,
̂ W ) if Y ⊥ GÐ→ Z∣W
p(Y ∣X,
X
Ð
→

→ denotes the graph obtained from G by deleting all directed edges in and out of X.
where GÐ
X
Ð
→

• Rule 2 (intervention/observation exchange):
̂ Z,
̂ W ) = p(Y ∣X,
̂ Z, W ) if Y ⊥ GÐ→ Z∣W
p(Y ∣X,
XZ
Ð
→Ð
→

→ denotes the graph obtained from G by deleting all directed edges in and out of
where GÐ
XZ
Ð
→Ð
→

X and out of Z.
• Rule 3 (insertion/deletion of interventions):
̂ Z,
̂ W ) = p(Y ∣X,
̂ W ) if Y ⊥ G
Z∣W
p(Y ∣X,
Ð
→ÐÐÐ→
X Z(W )
Ð
→

→ , and GÐ
where Z(W ) denotes the nodes in Z that are not ancestors of W in GÐ
→ÐÐÐ→ deX
Ð
→

X Z(W )
Ð
→

→ by deleting all undirected and directed edges into Z(W ).
notes the graph obtained from GÐ
X
Ð
→

Proof We prove that the antecedents of rule 1 in this theorem and in Theorem 6 are equivalent. If
Y⊥
/ GX̂ Z∣X, W then there is a connecting path given W ∪ X that contains no node in X, since the
nodes in X can only have outgoing directed edges in GX̂ and thus the path would be blocked. The
→ by simply undoing lines 2 and 3 in Table 2. The resulting
path can be transformed into a path in GÐ
X
Ð
→

path is clearly connecting given W .
If Y ⊥/ GÐ→ Z∣W then there is a connecting path given W . Note that the nodes in X only parX
Ð
→

→.
ticipate in undirected edges in the path, since they do not participate in any directed edge in GÐ
X
Ð
→

Then, the nodes in X only appear in subpaths of the form A − X1 − . . . − Xi − . . . − Xk − B with
X1 , . . . , Xk ∈ X and A, B ∉ X. Then, the path clearly results in a path in GX̂ that is connecting
given W ∪ X, by lines 2 and 3 in Table 2.
15

P E ÑA

AND

B ENDTSEN

Proving the equivalence of the antecedents for rules 2 and 3 can be done similarly. In rule 3,
→.
note that a node in Z is an ancestor of W in GX̂ if and only if it is an ancestor of W in GÐ
X
Ð
→

We do not currently have a systematic way of deciding whether there exists a sequence of rules
for identifying a given causal effect. The following theorems characterize graphically three cases
where such a sequence exists.
Theorem 8 A set of variables W ∪ Z satisfies the back-door criterion relative to an ordered pair of
variables (X, Y ) in an aADMG G if
1. W ∪ Z contains no descendant of X in G, and
2. W ∪ Z blocks all non-directed paths in G from X to Y .
Moreover,

̂ W ) = ∑ p(Y ∣X, W, z)p(z∣W ).
p(Y ∣X,
z

Proof By condition 2, the only paths between X and Y that are not blocked given W ∪ Z are those
̂ W, z) = p(Y ∣X, W, z) by rule 2. By condition 1,
that reach X through its children. Then, p(Y ∣X,
the only paths between X and Z that are not blocked given W are those that reach X through its
̂ W ) = p(z∣W ) by rule 3. Finally, simply replace the previous
parents or neighbors. Then, p(z∣X,
expressions in
̂ W ) = ∑ p(Y ∣X,
̂ W, z)p(z∣X
̂ , W ).
p(Y ∣X,
z

̂ in the example in Figure 1 can be identified with the help of the previous
Note that p(B∣A)
theorem (X = A, Y = B, W = ∅ and Z = C).
Theorem 9 A set of variables W ∪ Z satisfies the front-door criterion relative to an ordered pair
of variables (X, Y ) in an aADMG G if
1. W contains no descendant of X in G,
2. Z blocks all directed paths in G from X to Y ,
3. W satisfies the back-door criterion in G relative to (X, Z), and
4. W ∪ X satisfies the back-door criterion in G relative to (Z, Y ).
Moreover,

̂ W ) = ∑ p(z∣X, W ) ∑ p(Y ∣z, W, x′ )p(x′ ∣W )
p(Y ∣X,
x′

z

Proof By condition 4, the only paths between Z and Y that are not blocked by W ∪ X are those
̂ W, z) = p(Y ∣X,
̂ W, ẑ) by rule 2. By conditions
that reach Z through its children. Then, p(Y ∣X,
1 and 2, the only paths between X and Y that are not blocked by W ∪ Z are those that reach X
̂ W, ẑ) = p(Y ∣̂
through its parents or neighbors and, thus, p(Y ∣X,
z , W ) by rule 3. To see it, note that
16

E FFECT I DENTIFICATION IN ADMG S

DAG

AND

GM S

oADMG

aADMG

C

C

UA
UC
C

UB

UD

B

D

A

A

B

D

A

B

D

̂ C) is identifiable from the aADMG but not from the oADMG.
Figure 8: Example where p(D∣A,
any path reaching X through its children must be of the form X → . . . → Zi . . . Y where Zi ∈ Z is
a collider on the path. However, the subpath between Zi and Y contradicts condition 4. Moreover,
note that conditions 3 and 4 together with Theorem 8 imply that
̂ W ) = p(Z∣X, W )
p(Z∣X,
and

̂ W ) = ∑ p(Y ∣Z, W, x′ )p(x′ ∣W ).
p(Y ∣Z,
x′

Finally, replace the previous expressions in
̂ W ) = ∑ p(Y ∣X,
̂ W, z)p(z∣X
̂ , W ) = ∑ p(Y ∣X,
̂ W, ẑ)p(z∣X,
̂ W)
p(Y ∣X,
z

z

̂ W ).
= ∑ p(Y ∣̂
z , W )p(z∣X,
z

̂ C) can be identified with
Figure 8 shows a DAG that induces an aADMG from which p(D∣A,
the help of the previous theorem (X = A, Y = D, W = C and Z = B). Note that Theorem 8 is
not applicable to this example. Note also that the DAG induces an oADMG from which the causal
effect is not identifiable (Pearl, 2009, p. 94).
̂ W ) is identifiable from an aADMG G and W contains no descendant of X
Theorem 10 If p(Y ∣X,
in G, then
̂ = ∑ p(Y ∣X,
̂ w)p(w).
p(Y ∣X)
w

Proof The only paths between X and W that are not blocked given the empty set are those that
̂ = p(W ) by rule 3.
reach X through its parents or neighbors. Then, p(W ∣X)
̂ is identifiable in the example in Figure 8 (X = A,
Thanks to the previous theorem, p(D∣A)
Y = D and W = C).
17

P E ÑA

AND

B ENDTSEN

5.2 Decomposition-Based Causal Effect Identification
In this section, we present some new graphical criteria for causal effect identification from aADMGs, which add to the back-door and front-door criteria presented in the previous section. First,
note that the system of structural equations corresponding to the causal model represented by an
aADMG G (recall Equation 3) induces a probability distribution p over V , namely
p(V ) = ∑[∏ p(Vi ∣P aG (Vi ), ui )]p(u)
u

(6)

i

where Ui represents the unobserved causes of Vi , i.e. the error term ǫi since we are just considering
aADMGs, and U represents the set of all Ui . Moreover, the distribution induced by the postinterventional system of structural equations can be obtained from the previous equation by simply
removing the terms for the variables intervened upon, that is
̂ = ∑[ ∏ p(Vi ∣P aG (Vi ), ui )]p(u) = ∑ [ ∏ p(Vi ∣P aG (Vi ), ui )]p(uV ∖X ). (7)
p(V ∖ X∣X)
u Vi ∉X

uV ∖X Vi ∉X

Let W ′ ⊆ V be an ancestral set, and let W = V ∖ W ′. We say that two nodes belong to the same
component if and only if they are connected by an undirected path in GW , i.e. if and only if they
are connected by an undirected path in G that is not blocked by W ′ . Assume that W is partitioned
into k components S1 , . . . , Sk . We define the factor
Q(Sj ∣W ′ ) = ∑ [ ∏ p(Vi ∣P aG (Vi ), ui )]p(uSj ∣UW ′ ).
uSj Vi ∈Sj

Note that
p(W ∣W ′ ) = ∏ Q(Sj ∣W ′ ).

(8)

j

To see it, recall that W ′ is ancestral and, thus, it determines UW ′ . Then, Equation 6 implies that
p(W, w′ ) = [ ∑ [ ∏ p(Vi ∣P aG (Vi ), ui )]p(uW ∣uW ′ )][ ∏ p(vi ∣paG (Vi ), ui )]p(uW ′ )
Vi ∈W ′

uW Vi ∈W

and thus
p(W ∣w′ ) = ∑ [ ∏ p(Vi ∣P aG (Vi ), ui )]p(uW ∣uW ′ ) = ∏ Q(Sj ∣w′ )
uW Vi ∈W

(9)

j

because USj ⊥ G′ USl ∣UW ′ for any j and l, and where G′ denotes the magnification of G. Note also
that Q(Sj ∣W ′ ) is the distribution of Sj given that the variables in W ′ are observed and the rest of
the variables are intervened upon. To see it, recall again that W ′ is ancestral and, thus, it determines
̂
UW ′ . Therefore, given the observation W ′ = w′ and the intervention W
∖ Sj = ̂
t, we have that
Q(Sj ∣w′ ) = ∑ [ ∏ p(Vi ∣P aG (Vi ), ui )]p(uSj ∣uW ′ )
uSj Vi ∈Sj

=

∏Vi ∈W ′ p(vi ∣paG (Vi ), ui )]p(uW ′ )
∏Vi ∈W ′ p(vi ∣paG (Vi ), ui )]p(uW ′ )

p(Sj , w′ , ̂
t)
= p(Sj ∣w′ , ̂
t)
′
̂
p(w , t)

by Equation 7. Moreover, Q(Sj ∣W ′ ) is identifiable as the next theorem shows.
18

E FFECT I DENTIFICATION IN ADMG S

AND

GM S

Theorem 11 Given an aADMG G, Q(Sj ∣W ′ ) is identifiable and is given by
Q(Sj ∣W ′ ) = ∏ p(Vi ∣V (i−1) , W ′ )
Vi ∈Sj

where V1 < . . . < Vn is topological order of W with respect to G, and V (i) = {V1 , . . . , Vi }.
Proof We prove the theorem by induction over the number of variables in W . Clearly, the theorem holds when W contains a single variable. Assume as induction hypothesis that the theorem
holds for up to n variables. When there are n + 1 variables, these can be divided into components
S1 , . . . , Sk , S ′ with factors Q(S1 ∣W ′ ), . . . , Q(Sk ∣W ′ ), Q(S ′ ∣W ′ ) such that Vn+1 ∈ S ′ . By Equation
8, we have that
p(W ∣W ′ ) = Q(S ′ ∣W ′ ) ∏ Q(Si ∣W ′ )
i

which implies that
p(W ∖ Vn+1 ∣W ′ ) = [ ∑ Q(S ′ ∣W ′ )] ∏ Q(Si ∣W ′ ).
vn+1

Note that p(W ∖Vn+1 ∣W ′ ) factorizes according to (GW )V
(n)
6), and Si is a component of (GW )V . Therefore,

i
(n)

(i.e. it can be expressed as in Equation

Q(Sj ∣W ′ ) = ∏ p(Vi ∣V (i−1) , W ′ )
Vi ∈Sj

by the induction hypothesis and the fact that V1 < . . . < Vn is also a topological order of V (n) with
(n)
respect to (GW )V . Then, Q(S ′ ∣W ′ ) is also identifiable and is given by
Q(S ′ ∣W ′ ) =

p(W ∣W ′ )
∏i p(Vi ∣V (i−1) , W ′ )
=
= ∏ p(Vi ∣V (i−1) , W ′ ).
∏i Q(Si ∣W ′ )
∏i Q(Si ∣W ′ )
Vi ∈S ′

The following theorem gives a necessary and sufficient graphical criterion for the identification
of the causal effect of a single variable on the rest of the variables.
Theorem 12 Given an aADMG G, let X ∈ W belong to the component S X . Then, p(W ∖
̂ W ′ ) is identifiable if and only if there is no undirected path between X and its children
X∣X,
̂ W ′ ) is identifiable, it is given by
in GW . When p(W ∖ X∣X,
̂ W ′ ) = [∑ Q(S X ∣W ′ )] ∏ Q(Si ∣W ′ ).
p(W ∖ X∣X,
x

i

̂ X ∣W ′ ) denote the factor Q(S X ∣W ′ ) with the term
Proof To prove the sufficiency part, let Q(S
p(X∣P aG (X), UX ) removed. Note that
̂ W ′ ) = Q(S
̂ X ∣W ′ ) ∏ Q(Si ∣W ′ ).
p(W ∖ X∣X,
i

19

P E ÑA

AND

B ENDTSEN

̂ W ′ ) is identifiable if and
As shown before, each Q(Si ∣W ′ ) is identifiable. Therefore, p(W ∖ X∣X,
X
′
̂
only if Q(S
∣W ) is so. Moreover, since there is no undirected path between X and its children in
GW , this implies that no child of X is in S X , which implies that
̂ X ∣W ′ ) = ∑ Q(S X ∣W ′ ).
Q(S
x

To prove the necessity part, note that if a causal effect is not identifiable from an aADMG then
it is not identifiable if additional edges are added to the aADMG. To see it, note that the additional
edges can be made ineffective through the parameters of the corresponding system of structural
equations. Therefore, to prove the necessity part of the theorem, it suffices to consider any subgraph
of GW that is of the form of the aADMG in Figure 9. The figure also shows the corresponding
magnified aADMG and a causal DAG that may have induced the aADMG. We define the following
system of structural equations for the DAG:
UX ∼ N (µ, σ)
UZ1 = UX
UZi = UZi−1 for all i > 1
UA = α1 UZm
X = UX
Zi = UZi for all i
A = β1 X + UA .
Let p1 (X, Z1 , . . . , Zm , A, UX , UZ1 , . . . , UZm , UA ) denote the probability distribution induced by
the equations above. We create a second system of structural equations by replacing α1 and β1 with
α2 and β2 such that α1 + β1 = α2 + β2 . Let p2 (X, Z1 , . . . , Zm , A, UX , UZ1 , . . . , UZm , UA ) denote
the probability distribution induced by the second system of equations. Finally, note that
pi (X, Z1 , . . . , Zm , A) = pi (A∣X, Z1 , . . . , Zm )pi (X, Z1 , . . . , Zm )
with i ∈ {1, 2}. Note also that pi (X, Z1 , . . . , Zm ) = 0 unless X = Z1 = . . . = Zm , in which case
pi (X, Z1 , . . . , Zm ) = pi (X) with X ∼ N (µ, σ). Note also that pi (A∣X, Z1 , . . . , Zm ) = 1 if and
only if A = (αi + βi )Zm , because X = Zm . Then, p1 (X, Z1 , . . . , Zm , A) = p2 (X, Z1 , . . . , Zm , A).
However,
̂ = pi (A∣X,
̂ Z1 , . . . , Zm )pi (Z1 , . . . , Zm ∣X)
̂
pi (Z1 , . . . , Zm , A∣X)
̂ Z1 , . . . , Zm )pi (Z1 , . . . , Zm )
= pi (A∣X,
by rule 3 in Section 5.1. Recall that p1 (Z1 , . . . , Zm ) = p2 (Z1 , . . . , Zm ). Moreover, note that
̂ Z1 , . . . , Zm ) = 1 if and only if A = βi X
̂ + αi Zm . Therefore, p1 (Z1 , . . . , Zm , A∣X)
̂ ≠
pi (A∣X,
̂
p2 (Z1 , . . . , Zm , A∣X). In other words, the causal effect in the theorem cannot be computed uniquely
from observed quantities.
̂ is not identifiable by the previous theorem from the aADMG in
For instance, p(B, C, D∣A)
̂ C) is identifiable (X = A,
Figure 8 (X = A, W = {A, B, C, D} and W ′ = ∅). However, p(B, D∣A,
′
W = {A, B, D} and W = C).
The following theorem strengthens the sufficient condition for unidentifiability in the previous
theorem.
20

E FFECT I DENTIFICATION IN ADMG S

aADMG
UX
Z1
X

...

Zm

GM S

Magnified aADMG
UZ1 . . . UZm UA

UX

Zm

Z1
A

AND

X

A

UZ1

DAG
. . . UZ m

Z1

Zm

X

UA

A

Figure 9: Example in the proof of Theorem 12.
̂ W ′ ) is not identifiable
Theorem 13 Given an aADMG G, let X ∈ W ′′ ⊆ W . Then, p(W ′′ ∖ X∣X,
if there is an undirected path between X and its children in GW ′′ .
̂ W ′ ) is not identifiable from the aADMG GW ′ ∪W ′′ by Theorem
Proof Note that p(W ′′ ∖ X∣X,
12. Then, it is not identifiable from G either because the additional edges can be made ineffective
through the parameters of the corresponding system of structural equations.
̂ W ′ ) is identifiable by Theorem 12, so is p(Y ∖ X∣X,
̂ W ′ ) with
Clearly, whenever p(W ∖ X∣X,
Y ⊆ W by marginalization. However, as the following theorem shows, there are cases where the
latter is identifiable despite the fact that the former is not. Let W ′′ = AnG (Y ) ∖ W ′ .
Theorem 14 Given an aADMG G, if there is no undirected path between X ∈ W ′′ and its children
′′
̂ is identifiable and is given by
in (GW )W , then p(W ′′ ∖ X∣W ′ , X)
̂ W ′ ) = [∑ Q(T X ∣W ′ )] ∏ Q(Ti ∣W ′ )
p(W ′′ ∖ X∣X,
x

i
′′

where T1 , . . . , Tk , T X are the components in which W ′′ is partitioned in (GW )W , and T X is the
component that contains X.
Proof By summing over W ∖ W ′′ on both sides of Equation 9, we have that
p(W ′′ ∣W ′ ) = ∑ [ ∏ p(Vi ∣P aG (Vi ), ui )]p(uW ∣uW ′ )
uW Vi ∈W ′′

= ∑ [ ∏ p(Vi ∣P aG (Vi ), ui )]p(uW ′′ ∣uW ′ ).
uW ′′ Vi ∈W ′′

Note that the previous expression is of the same form as Equation 6, when G is replaced with
′′
(GW )W . Then, we can repeat the reasoning in the proof of Theorem 12.

Theorem 15 Given an aADMG G, if there is no undirected path between X ∈ W ′′ and its children
′′
̂ and p(W ′′ ∖ X∣X)
̂ are identifiable and are given by
in (GW )W , then p(W ′′ ∖ X, W ′ ∣X)
̂ = p(W ′ )[∑ Q(T X ∣W ′ )] ∏ Q(Ti ∣W ′ )
p(W ′′ ∖ X, W ′ ∣X)
x

21

i

P E ÑA

DAG
UC
UA
A
UD

C

AND

B ENDTSEN

oADMG

UB

aADMG

C

B

A

D

C
B

A

D

B

D

̂ C) and p(B∣A)
̂ are identifiable from the aADMG but not from
Figure 10: Example where p(B∣A,
the oADMG.
and
̂ = ∑ p(w′ )[∑ Q(T X ∣w′ )] ∏ Q(Ti ∣w′ )
p(W ′′ ∖ X∣X)
w′

where T1 , . . . , Tk , T

X

x

i

are as in Theorem 14.

̂ = p(W ′ ), because W ′ is an
Proof The theorem follows from Theorem 14 by noting that p(W ′ ∣X)
ancestral set.
̂ C) is not identifiable by Theorem 14 from the aADMG in Figure 10
For instance, p(B, D∣A,
′′
̂ C) is identifiable (X = A, W ′′ =
(X = A, W = {A, B, D} and W ′ = C). However, p(B∣A,
̂ and p(B∣A)
̂ are identifiable by Theorem 15 (X = A,
{A, B} and W ′ = C). Moreover, p(B, C∣A)
′′
′
W = {A, B} and W = C). Note that the latter two effects are not identifiable by Theorem 14.
̂ C), p(B, C∣A)
̂ nor p(B∣A)
̂ are identifiable from the oADMG in the
Note also that neither p(B∣A,
figure (Pearl, 2009, p. 94).
Note that X is a singleton in Theorem 14. The algorithm in Table 4 shows how Theorem
14 can be used for causal effect identification when X is a subset of V . For each ordering σ of
the variables in X, the algorithm tries to identify the causal effect of Xσ(1) from the available
′′
information, i.e. p(W ′′ ∣W ′ ) and (GW )W . If the identification succeeds, then the algorithm tries
to identify the causal effect of Xσ(2) from the available information, i.e. the post-interventional
distribution identified in the previous iteration and the corresponding aADMG (G′ )X
where
̂
σ(1)
′′

G′ = (GW )W . The process continues until the causal effects of all variables in X are identified
in which case the last expression constitutes the answer to the original query, or some effect is not
identifiable in which case the algorithm tries a new ordering σ. If all orderings are tried without
success, then the algorithm declares the causal effect unidentifiable. Whether the effect is truly
unidentifiable is still an open problem.
We illustrate the use of the algorithm in Table 4 with an example. In particular, consider again
̂ C)
̂ is identifiable from the aADMG G with the ordering
the example in Figure 1. Then, p(B∣A,
̂
σ = (C, A): First, p(A, B∣C) is identifiable from G by Theorem 14 and is given by a function of
̂ A)
̂ is identifiable from G ̂ = {A → B, C} and is given by a function
p(A, B, C) and, then, p(B∣C,
C
̂ Note that the effect is not identifiable with the ordering σ = (A, C).
of p(A, B∣C).
22

E FFECT I DENTIFICATION IN ADMG S

AND

GM S

Table 4: Causal effect identification for multiple interventions.
1
2
3
4
5
6
7
8
9
10
11
12

V 1 = W ′′
p1 (V 1 ) = p(W ′′ ∣W ′ )
′′
G1 = (GW )W
for each ordering σ of the variables in X do
for i = 1, . . . , ∣X∣ do
i
̂
if pi (V i ∖ Xσ(i) ∣X
σ(i) ) is identifiable from G by Theorem 14 then
i+1
i
V
= V ∖ Xσ(i)
i+1
̂
p (V i+1 ) = pi (V i ∖ Xσ(i) ∣X
σ(i) )
i+1
i
G = (G )X
̂
σ(i)
else go to line 4
return IDENTIFIABLE
return UNIDENTIFIABLE

Note that Theorem 15 can also be generalized to the case where X is a subset of V : If p(W ′′ ∖
̂
̂ and p(W ′′ ∖ X∣X)
̂
X∣X, W ′ ) is identifiable by the algorithm in Table 4, then p(W ′′ ∖ X, W ′ ∣X)
are also identifiable and are given by
̂ = p(W ′ )p(W ′′ ∖ X∣X,
̂ W ′)
p(W ′′ ∖ X, W ′ ∣X)
and
̂ = ∑ p(w′ )p(W ′′ ∖ X∣X,
̂ w′ )
p(W ′′ ∖ X∣X)
w′

̂ = p(W ′ ) since W ′ is an ancestral set. Finally, we have the following result.
because p(W ′ ∣X)
̂ W ′ ) is identifiable if every undirected path between X
Theorem 16 Given an aADMG G, p(Y ∣X,
and those children of X that are ancestor of Y includes some node that is in W ′ or that is neither
a descendant of X nor of Y .
Proof Let T denote the nodes that are neither descendants of X nor of Y . Note that W ′ ∪ T is an
̂ is identifiable by Theorem 15 with W ′ ∪ T instead
ancestral set. Then, p((W ′′ ∖ T ) ∖ X, W ′ , T ∣X)
′
′′
′′
of W , W ∖ T instead of W , and W ∖ T instead of W . Then, the theorem follows by conditioning
and marginalization.

6. Gated Models for Causal Effect Identification
The gambling example in Section 1 showed how the context may decide which of the oADMG or
the aADMG is more appropriate in terms of being able to identify the causal effect of interest. We
used a gated model, i.e. a graphical model which combines multiple graphical models using gates,
to explicitly state the criteria used to decide which model is more appropriate. In this section we
shall generalise this idea, using gated models to accommodate so called context specific independences (CSIs), in such a way that we can exploit these independences to identify more causal effects
23

P E ÑA

X

AND

B ENDTSEN

Z

X

Y

Z
Y

(a)

X >0

X

Z
Y

X ≤0
(b)

L(D∣R2 )/L(D∣R1 ) > θ

X

X

Z

U1

U2

X

Z

Z

R1

R2
Y

Y

Y

L(D∣R1 )/L(D∣R2 ) > θ

(c)

(d)

Figure 11: In (a), a single DAG that does not convey that X → Z can be removed if X > 0, a gated
model representing this extra knowledge is given in (b). When the CSI is dependent on unobserved
variables, U1 and U2 in (c), we cannot discern context based on variables taking specific values. The
gated model in (d) uses threshold gates to decide which DAG is appropriate.

than would be possible using a single model. The gated model can also be used to model certain
causal phenomena that may occur due to CSIs, such as unstable and non-deterministic effects of
interventions. It should be noted that gated models are just a formalism to represent contexts explicitly, so that the do-calculi introduced in the previous sections and in other articles can be fully
deployed. So, gated models can build on any existing family of graphical models, e.g. oADMGs,
aADMGs, ADMGs, etc.
6.1 Context Specific Independence
In a graphical model, an edge between two nodes should be present if there is a potential direct association between the two variables that the nodes represent, even if this association is only present
for a certain range of the values the variables may take. Studying the conditional probability distributions that are associated with the model may however reveal that some edges can be removed
when some variables take on certain values. Exploiting such CSIs within the domain of DAGs has
been done since at least the mid-nineties (Boutilier et al., 1996), where representing discrete distributions which contained such CSIs in form of trees allowed for more efficient representation. CSIs
were studied a few years earlier in the domain of influence diagrams (Smith et al., 1993), and later
within the domain of event trees (Smith and Anderson, 2008). Poole and Zhang (2003) give several
examples of cases where CSIs may materialize, and they extend the variable elimination algorithm
with the ability to utilize CSIs within the DAG, resulting in more efficient inference. Enforcing CSIs
has also been used to facilitate more efficient inference and parameter estimation, for instance in the
form of noisy OR-models (Pearl, 1988; Zagorecki and Druzdzel, 2004). To further illustrate CSIs,
consider the DAG in Figure 11a, and the additional knowledge that the edge X → Z is unnecessary
24

E FFECT I DENTIFICATION IN ADMG S

T

C

A

T

C
W

W

(a)

A

AND

GM S

̂ > 100
W
̂ ≤ 100
W

T

C

A

W

(b)

̂ > 100, p(A, C∣T̂) is
Figure 12: In (a), p(A, C∣T̂) is not identifiable. In (b), in the context where W
identifiable.

when X > 0. This CSI is obviously not revealed by the DAG in the figure. An alternative way of
representing this DAG is to use a gated model, an example of which is depicted in Figure 11b. In
Figure 11b we have two DAGs connected with gates, when X > 0 we shall use the DAG to the
right, where there is no edge between X and Z, and when X ≤ 0 then we shall use the DAG to
the left (where the edge is present). The gated model representation allows us to not only reduce
the number of edges in some circumstances (which in turn may imply less computation), but also
graphically state the CSIs that exist among the variables.
In some cases we may have CSIs that are due to unobserved variables. Consider the DAG
in Figure 11c, where we assume that U1 and U2 are unobserved. If the edge between Z and U1
disappears when U2 > 0, then in a dataset over X, Y and Z there will be data points for which
the edge Z → Y has to be present, and data points for which it is not required, however this may
not be evident from the conditional distributions estimated from the dataset. We can therefore not
create gates which specify for which values of any of the observed variables we can remove Z → Y .
In such cases we use a gate which judges which DAG is more appropriate given some data D. In
our previous work, e.g. (Bendtsen, 2017; Bendtsen and Peña, 2016b), appropriate has been equated
with likelihood, which we shall denote with L. Figure 11d shows an example, where we have
labeled the DAGs R1 and R2 . The model makes it clear that it is necessary to continually assess
whether or not the other DAG is more appropriate (above some threshold θ).
While being able to remove an edge in a graphical model may result in faster computation and
easier estimation of parameters, removing an edge in a causal model may lead to causal effects
being identifiable that previously were not. Consider the aADMG in Figure 12a. Due to Theorem
̂ > 100
13, we cannot identify p(A, C∣T̂). However, if we could identify a CSI, for instance when W
the edge T → C can be removed, then p(A, C∣T̂) would be identifiable in this specific context.
The aADMG in Figure 12a however lacks the ability to tell us that p(A, C∣T̂) is identifiable in the
̂ > 100. A gated model such as the one in Figure 12b solves this problem by making
context of W
the contexts and the context specific causal models explicit.
6.2 Modeling Causal Scenarios Using Gated Models
Gated models are interesting for causal reasoning not only because they make explicit the contexts
where causal effects are identifiable, but also because they allow modeling some causal phenomena
that occur due to CSIs. Without having the possibility to explicitly represent CSIs, these causal phenomena would pass unmodeled. We describe three such causal phenomena below. For simplicity,
we use DAGs in some of the examples below. However, as mentioned above, gated models can
build on any other family of graphical models.
25

P E ÑA

AND

B ENDTSEN

B

Y

U

Z

(a)
B > 60
̂ ≤ 60
B

B
B

Y

R1

B > 60

B

L(D∣R3 )/L(D∣R2 ) > θ

B

Y

R2

B

Z
B > 60

R1
Z

R3

Y

R3

Z

Y

Y
B

Y

R2

Z

Z

Z

L(D∣R2 )/L(D∣R3 ) > θ

̂ ≤ 60
B

̂ ≤ 60
B

L(D∣R3 )/L(D∣R2 ) > θ

L(D∣R2 )/L(D∣R3 ) > θ

(b)

(c)

Figure 13: In (a), a single causal model cannot capture the extra knowledge regarding CSIs. In (b),
intervening to lower the blood pressure implies moving to a physiological stable state, but may lead
to transitions back and forth with a crisis state. In (c), the outcome of the intervention is unknown,
it may either lead to the stable or the crisis state.
6.2.1 U NSTABLE E FFECT

AND

N ON -D ETERMINISTIC O UTCOME

OF I NTERVENTIONS

Assume that our domain of interest consists of the following variables: Blood pressure (B), dosage
of medication (Y ), dizziness (Z), and anxiety (U ). Moreover, B, Y and Z are observed but U is unobserved. Assume that performing an intervention to lower the blood pressure puts the human body
in a context where it goes back and forth between a physiological stable state and an unstable crisis
̂ ≤ 60 and the body enters the physiological
state. After performing the intervention we know that B
stable state, but may then go back and forth between the stable and crisis state. We want to model
these states or contexts separately due to the existence of the CSIs below.
In Figure 13a, a single causal model for this scenario is depicted. This model tells us very little
̂ ≤ 60
about the scenario just narrated. Knowing that the edge B → Y is lost in the context of B
(i.e. the dosage of medication is not a function of the blood pressure when the pressure is low),
̂ ≤ 60 and U > 0 (i.e. dizziness is not a function of the dosage of
and Y → Z is lost when B
medication when the blood pressure is low and the patient experiences an anxiety attack) does not
help in making the model more informative. However, using a gated model we can incorporate
this extra knowledge. The resulting gated model is depicted in Figure 13b. As we can see, once
̂ ≤ 60, we change from R1 to R2 , the physiological stable state under low blood pressure. Since
B
U is unobserved, we cannot use a context gate to describe when we should switch between R2 and
R3 (the crisis state), thus we need to use a threshold gate that can identify which of the two contexts
is most appropriate. The gated model also makes it clear that increasing the blood pressure while
either in the crisis state or the stable state will take the body back to the initial context.
To demonstrate non-deterministic outcomes, we shall change the previous scenario slightly.
This time, assume that we do not know if we will enter the stable state or the crisis state after the
intervention to lower the blood pressure. Furthermore, the stable and crisis states cannot transition
into each other, i.e. once the blood pressure turns low, the body enters a stable or crisis state and
does not change between them. The single causal model stays the same (Figure 13a), and again
26

E FFECT I DENTIFICATION IN ADMG S

AND

GM S

̂ > 30∣bootcamp
W

T

T

C

R1
T

W

W

C

C

R2

W

W ≤ 30

(a)

(b)

Figure 14: In (a), the single causal model does not encode the mechanism dependent context, however in (b) the mechanism used to set the context is part of the context itself, thus different outcomes
are achieved depending on the mechanism used.

tells us very little about the scenario. Using a gated model we can model this causal scenario, but
this time using a combination of threshold and context gates, as depicted in Figure 13c. The gated
model tells us that when the intervention lowers the blood pressure, we must assess which of the
states is most appropriate, and it is the data D that determines the appropriate causal model (recall
that this is due to the CSIs that are created due to the unobserved variable U ).
6.2.2 M ECHANISM D EPENDENT O UTCOME

OF I NTERVENTIONS

Consider the monthly physical activity (W ) measured in hours, and the monthly alcohol consumption (C) of a person in a population. Assume that there exists a leaflet which contains information
about the negative consequences of overconsumption of alcohol, and that the person can read the
leaflet or not (T ). In general, if the leaflet is read it reduces the amount of alcohol consumed.
Assume further that we can intervene on the person to increase her physical activity through two
different mechanisms: Either sending her to a bootcamp or motivating her to increase the physical
activity on her own. In this scenario, a CSI is introduced such that T → C is lost if the person
achieves a high physical activity due to the intervention mechanism of sending her to a bootcamp
(no alcohol available at the bootcamp, thus reading the leaflet has no effect on alcohol consumption).
However, the same is not true for the alternative intervention mechanism (motivating to increase the
physical activity does not reduce access to alcohol, thus reading the leaflet does have some effect).
As before, using a single causal model (Figure 14a) to represent this scenario results in a less
informative model than what we can express with a gated model. In Figure 14b we have depicted a
̂ > 30∣bootcamp to mean
gated model which can represent such a scenario, where we have used W
that the bootcamp mechanism was used.
6.2.3 U SING G ATED M ODELS

TO I DENTIFY

C AUSAL E FFECTS

In this section we shall expand upon the alcohol and physical activity example given in Section 6.2.2.
This time we shall focus on the identification of causal effects within the contexts, and show how
gated models allow us to identify causal effects that cannot be identified using a single causal model
even though, unlike in the scenarios described above, none of the gates refers to an intervention.
Consider the causal scenario depicted in Figure 15, which is now represented using a gated
model with aADMGs. Here, C represent the monthly consumption of alcoholic beverages for an
27

P E ÑA

AND

B ENDTSEN

L(D∣R3 )/L(D∣R2 ) > θ

W > 30

R1
T

C

R2
A

T

W

C

R3
T

A

A

W

W

W ≤ 30

C

L(D∣R2 )/L(D∣R3 ) > θ

Figure 15: A gated model using aADMGs. The causal effect p(A, C∣T̂) cannot be identified in R1 .
However, exploiting certain CSIs the effect is identifiable in the context R2 .

individual, W represents the individual’s monthly level of physical activity measured in number of
hours, A represents the number of alcohol related accidents that the individual has been subjected
to, and T represents whether or not the individual has read a leaflet containing information about
the negative effects of overconsumption of alcoholic beverages, and information about how to avoid
accidents when consuming alcohol. From the initial context R1 , we can tell that there is confounding
between T and C, which implies that we cannot identify p(A, C∣T̂) by Theorem 13.
We further assume that individuals who have a high level of physical activity do not change the
number of alcoholic beverages they consume if they read the leaflet. By exploiting this CSI in R2 ,
p(A, C∣T̂) can in this context be identified by Theorem 12. Thus the investigator can collect observational data in this context, and use the do-calculus presented in Section 5 to calculate p(A, C∣T̂).
If the individual no longer maintains a high level of physical activity, then the gated model expresses
that such effect no longer can be calculated from observational data. However, the gated model also
expresses that the effect of high physical activity is not stable, and that under certain circumstances
(due to unobserved variables, hence the use of threshold gates), the edge T → C might be recovered
even when W > 30. The investigator must therefore be careful, as it may be the case that R3 is more
appropriate than R2 , thus the effect would again not be identifiable. Therefore, as the investigator
collects observations in the context of W > 30 it is necessary to assess which of R2 and R3 is most
appropriate.

7. Conclusions
In this paper, we have introduced ADMGs as a combination of oADMGs and aADMGs. We have
defined the global Markov property for ADMGs by introducing two equivalent separation criteria.
We plan to define local and pairwise Markov properties for ADMGs, and study Markov equivalence
between ADMGs.
We have also shown the suitability of ADMGs to represent causal models with additive error
terms. We have presented sufficient graphical criteria for the identification of arbitrary causal effects
from aADMGs. Some criteria are based on a calculus, while others are based on a decomposition.
We plan to study the equivalence of these two sets of criteria, and extend them to ADMGs. We have
also presented a necessary and sufficient graphical criterion for the identification of the causal effect
of a single variable on the rest of the variables in aADMGs. In the future, we would like to extend
28

E FFECT I DENTIFICATION IN ADMG S

AND

GM S

this criterion to arbitrary causal effects, as it has been done for oADMGs (Huang and Valtorta, 2006;
Shpitser and Pearl, 2006), and generalize it to ADMGs.
It is worth mentioning that several of the graphical criteria presented in this paper aim to iden̂ W ), also called conditional causal effects. Such effects are
tify causal effects of the form p(Y ∣X,
important for the evaluation of conditional and stochastic plans, i.e. plans that intervene on X to
set it to a value that depends on the observed value of W either deterministically or stochastically
(Pearl, 2009, Chapter 4).
Finally, we have presented gated models for causal effect identification, a new family of graphical models that exploits CSIs to identify additional causal effects. Gated models can be combined
with any existing family of graphical models, e.g. oADMGs, aADMGs, ADMGs, etc. We have
illustrated the benefits of gated models with examples of certain causal phenomena that many practitioners may encounter when dealing with real-world systems, for instance uncertainty in the outcome of interventions and unstable effects. A line of research that we are interested in pursuing is
the extension of the exact learning algorithm presented in Section 4.2 to learn gated models from
observations and interventions.

Acknowledgments
We thank the Reviewers for their comments, which helped us to improve our manuscript.

References
S. A. Andersson, D. Madigan, and M. D. Perlman. Alternative Markov Properties for Chain Graphs.
Scandinavian Journal of Statistics, 28:33–85, 2001.
M. Bendtsen. Regimes in Baseball Player’s Career Data. Data Mining and Knowledge Discovery,
2017. To appear.
M. Bendtsen and J. M. Peña. Gated Bayesian Networks for Algorithmic Trading. International
Journal of Approximate Reasoning, 69:58–80, 2016a.
M. Bendtsen and J. M. Peña. Regime Aware Learning. In Proceedings of the 8th International
Conference on Probabilistic Graphical Models, pages 1–12, 2016b.
A. Biere, M. Heule, H. van Maaren, and T. Walsh. Handbook of Satisfiability. IOS Press, 2009.
C. Boutilier, N. Friedman, M. Goldszmidt, and D. Koller. Context-Specific Independence in
Bayesian Networks. In Proceedings of the 12th International Conference on Uncertainty in
Artificial Intelligence, pages 115–123, 1996.
P. Bühlmann, J. Peters, and J. Ernest. CAM: Causal Additive Models, High-Dimensional Order
Search and Penalized Regression. Annals of Statistics, 42:2526–2556, 2014.
D. R. Cox and N. Wermuth. Multivariate Dependencies - Models, Analysis and Interpretation.
Chapman & Hall, 1996.
R. J. Evans and T. S. Richardson. Marginal log-linear Parameters for Graphical Markov Models.
Journal of the Royal Statistical Society B, 75:743–768, 2013.
29

P E ÑA

AND

B ENDTSEN

M. Gebser, B. Kaufmann, R. Kaminski, M. Ostrowski, T. Schaub, and M. Schneider. Potassco: The
Potsdam Answer Set Solving Collection. AI Communications, 24:107–124, 2011.
M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming. In Proceedings
of 5th Logic Programming Symposium, pages 1070–1080, 1988.
Y. Huang and M. Valtorta. Pearl’s Calculus of Intervention is Complete. In Proceedings of the 22nd
Conference on Uncertainty in Artificial Intelligence, pages 217–224, 2006.
A. Hyttinen, F. Eberhardt, and M. Järvisalo. Constraint-based Causal Discovery: Conflict Resolution with Answer Set Programming. In Proceedings of the 30th Conference on Uncertainty in
Artificial Intelligence, pages 340–349, 2014.
D. Janzing, J. Peters, J. Mooij, and B. Schölkopf. Identifying Confounders Using Additive Noise
Models. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, pages
249–257, 2009.
J. T. A. Koster. Marginalizing and Conditioning in Graphical Models. Bernoulli, 8:817–840, 2002.
S. L. Lauritzen. Graphical Models. Oxford University Press, 1996.
I. Niemelä. Logic Programs with Stable Model Semantics as a Constraint Programming Paradigm.
Annals of Mathematics and Artificial Intelligence, 25:241–273, 1999.
J. M. Peña. Marginal AMP Chain Graphs. International Journal of Approximate Reasoning, 55:
1185–1206, 2014.
J. M. Peña. Alternative Markov and Causal Properties for Acyclic Directed Mixed Graphs. In
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, 2016.
J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan
Kaufman Publishers, 1988.
J. Pearl. Causal Diagrams for Empirical Research. Biometrika, 82:669–688, 1995.
J. Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2009.
J. Peters, J. M. Mooij, D. Janzing, and B. Schölkopf. Causal Discovery with Continuous Additive
Noise Models. Journal of Machine Learning Research, 15:2009–2053, 2014.
D. Poole and N. L. Zhang. Exploiting Contextual Independence in Probabilistic Inference. Journal
of Artificial Intelligence Research, 18:263–313, 2003.
T. Richardson. Markov Properties for Acyclic Directed Mixed Graphs. Scandinavian Journal of
Statistics, 30:145–157, 2003.
T. Richardson and P. Spirtes. Ancestral Graph Markov Models. The Annals of Statistics, 30:962–
1030, 2002.
K. Sadeghi and S. L. Lauritzen. Markov Properties for Mixed Graphs. Bernoulli, 20:676–696, 2014.
30

E FFECT I DENTIFICATION IN ADMG S

AND

GM S

I. Shpitser and J. Pearl. Identification of Conditional Interventional Distributions. In Proceedings
of the 22nd Conference on Uncertainty in Artificial Intelligence, pages 437–444, 2006.
P. Simons, I. Niemelä, and T. Soininen. Extending and Implementing the Stable Model Semantics.
Artificial Intelligence, 138:181–234, 2002.
J. E. Smith, S. Holtzman, and J. E. Matheson. Structuring Conditional Relationships in Influence
Diagrams. Operations Research, 41:280–297, 1993.
J. Q. Smith and P. E. Anderson. Conditional Independence and Chain Event Graphs. Artificial
Intelligence, 172:42–68, 2008.
D. Sonntag, M. Järvisalo, J. M. Peña, and A. Hyttinen. Learning Optimal Chain Graphs with
Answer Set Programming. In Proceedings of the 31st Conference on Uncertainty in Artificial
Intelligence, pages 822–831, 2015.
M. Studený. Probabilistic Conditional Independence Structures. Springer, 2005.
J. Tian and J. Pearl. A General Identification Condition for Causal Effects. In Proceedings of the
18th National Conference on Artificial Intelligence, pages 567–573, 2002a.
J. Tian and J. Pearl. On the Identification of Causal Effects. Technical report R-290-L, Department
of Computer Science, University of California, Los Angeles, 2002b.
A. Zagorecki and M. Druzdzel. An Empirical Study of Probability Elicitation under Noisy-OR
Assumption. In Proceedings of the 17th International Florida Artificial Intelligence Research
Society Conference, pages 880–885, 2004.

31

