MARGINALIZATION AND CONDITIONING FOR LWF
CHAIN GRAPHS

arXiv:1405.7129v4 [stat.OT] 28 Aug 2016

By Kayvan Sadeghi
University of Cambridge
In this paper, we deal with the problem of marginalization over
and conditioning on two disjoint subsets of the node set of chain
graphs (CGs) with the LWF Markov property. For this purpose, we
define the class of chain mixed graphs (CMGs) with three types of
edges and, for this class, provide a separation criterion under which
the class of CMGs is stable under marginalization and conditioning
and contains the class of LWF CGs as its subclass. We provide a
method for generating such graphs after marginalization and conditioning for a given CMG or a given LWF CG. We then define and
study the class of anterial graphs, which is also stable under marginalization and conditioning and contains LWF CGs, but has a simpler
structure than CMGs.

1. Introduction. Graphical models use graphs, in which nodes are random variables and edges indicate some types of conditional dependencies.
Mixed graphs, which are graphs with several types of edges, have started
to play an important role in graphical models as they can deal with more
complex independence structures that arise in different statistical studies.
The first example of mixed graphs in the literature appeared in [11].
This was a chain graph (CG) with a specific interpretation of conditional
independence, which is now generally known as the Lauritzen-WermuthFrydenberg or LWF interpretation. A formal interpretation, i.e. a Markov
property, was later provided by [5]. This Markov property, together with
other properties such as the factorization property was extensively discussed
in [9]. By the term LWF CGs, one refers to the class of CGs with a specific
independence structure that comes from the LWF Markov property.
It has become apparent that CGs with the LWF interpretation of independencies are important tools in capturing conditional independence structure
of various probability distributions. For example, Studeny and Bouckaert
[24] showed that for every CG, there exists a strictly positive discrete prob∗
Supported by grant #FA9550-12-1-0392 from the U.S. Air Force Office of Scientific
Research (AFOSR) and the Defense Advanced Research Projects Agency (DARPA)
AMS 2000 subject classifications: Primary 62H99; secondary 62A99
Keywords and phrases: c-separation criterion, chain graph, independence model, LWF
Markov property, m-separation, marginalization and conditioning, mixed graph

1

2

K. SADEGHI

ability distribution that embodies exactly the independence statements displayed by the graph, and Peña [14] proved that almost all the regular Gaussian distributions that factorize with respect to a chain graph are faithful to
it. This means that a Gaussian distribution chosen at random to factorize as
specified by the LWF CG will have the independence structure of the graph
and will satisfy no more independence constraints.
However, in the corresponding models to LWF CGs, when some variables
are unobserved – also called latent or hidden – or when some variables are set
to specific values, the implied independence structure, i.e. the corresponding
independence structure after marginalization and conditioning respectively,
is not well-understood.
The same problem for the well-known class of directed acyclic graphs
(DAGs), which is a subclass of LWF CGs, has been a subject of study, and
several classes of graphs have been defined in order to capture the marginal
and conditional independence structure of DAGs. These include MC graphs
[8], ancestral graphs [18], and summary graphs [26]; see also [19]. There is
also a literature pertaining to this problem for other types of graphs; see, for
example, the class of marginal AMP chain graphs in [15] for marginalization
in AMP chain graphs [1].
For LWF CGs, as it will be shown in this paper, one can capture the
independence structure induced by conditioning on some variables by another LWF CG, but in general cannot capture the independence structure
induced by marginalization over some variables by a CG. In this sense, CGs
are stable under conditioning but not under marginalization.
Indeed models with latent variables do not necessarily possess the desirable statistical properties of graphical models without latent variables, such
as identifiability, existence of a unique MLE, or being curved exponential
families in some cases such as DAGs; see, e.g.,[6].
However, a first step in dealing with this problem is, in the case of
marginalization, to come up with a more complex class of graphs with a certain independence interpretation that captures the marginal independence
structure of CGs; and in both cases of marginalization and conditioning, to
provide methods by which the graphs that capture the marginal and conditional independence structure are generated. These are the main objectives
of the current paper.
In the causal language (see, e.g., [16]) the resulting classes of graphs give
a simultaneous representation to “direct effects”, “confounding”, and “noncausal symmetric dependence structures”.
It is important to note that the classes of graphs introduced here only
deals with the conditional independence constraints, and not other con-

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

3

straints such as so-called Verma constraints [25]. The actual statistical model
is much more complicated even when marginalizing DAGs; see, e.g., [21].
The introduction of these classes of graphs is also justified in the paper
by showing that, for large subclasses of these classes of graphs, there are
probability distributions (in fact both Gaussian and discrete) that are faithful to them. Although finding the explicit parametrizations for the definned
graphs is beyond the scope of this paper, it also seems possible to extend
the existing parametrizations for smaller types of graph in the literature to
these classes in a fairly natural way. We will provide a discussion on this in
the paper.
The structure of the paper is as follows: In the next section, we define
mixed and chain graphs, and, for these classes of graphs, give graph theoretical definitions needed in this paper. In Section 3, we provide two equivalent ways for reading off independencies from a CG based on the LWF
Markov property. In Section 4, we define the class of chain mixed graphs
with certain independence interpretation, and show that they capture the
marginal independence structure of LWF CGs and that they are stable under marginalization, and provide an algorithm for generating such graphs
after marginalization. In Section 5, we show that the class of CMGs is also
stable under conditioning, provide the corresponding algorithm, and combine marginalization and conditioning for CMGs. As a corollary, we see that
LWF CGs are stable under conditioning. In Section 6, we define the class
of anterial graphs as a subclass of CMGs, which also contains LWF CGs,
and show that this class is stable under marginalization and conditioning.
We also provide an algorithm for marginalization and conditioning for this
class. In Section 7, we discuss the implications of the results for probabilistic independence models that are faithful to LWF CGs, and possible ways
to generalize the parametrizations existing in the literature for CMGs and
anterial graphs. In the Appendix in the supplementary material [20], we provide proofs of non-trivial lemmas, propositions, and theorems in the paper
as well as some more technical and yet less informative lemmas that are
used in the proofs.
2. Definitions for mixed graphs and chain graphs.
2.1. Basic graph theoretical definitions. A graph G is a triple consisting
of a node set or vertex set V , an edge set E, and a relation that with each
edge associates two nodes (not necessarily distinct), called its endpoints.
When nodes i and j are the endpoints of an edge, these are adjacent and
we write i ∼ j. We say the edge is between its two endpoints. We usually
refer to a graph as an ordered pair G = (V, E). Graphs G1 = (V1 , E1 ) and

4

K. SADEGHI

G2 = (V2 , E2 ) are called equal if (V1 , E1 ) = (V2 , E2 ). In this case we write
G1 = G2 .
Notice that graphs that we use in this paper (and in general in the context
of graphical models) are so-called labeled graphs, i.e. every node is considered
j
k is not equal to
a different object. Hence, for example, graph i
i
k.
j
Here we introduce some basic graph theoretical definitions. A loop is an
edge whose endpoints are equal. Multiple edges are edges whose endpoints
are the same as each other. A simple graph has neither loops nor multiple
edges. A complete graph is a simple graph with all pairs of nodes adjacent.
A subgraph of a graph G1 is graph G2 such that V (G2 ) ⊆ V (G1 ) and
E(G2 ) ⊆ E(G1 ) and the assignment of endpoints to edges in G2 is the same
as in G1 . An induced subgraph by a subset A of the node set is a subgraph
that contains the node set A and all edges between two nodes in A.
A walk is a list hi0 , e1 , i1 , . . . , en , in i of nodes and edges such that for
1 ≤ m ≤ n, the edge em has endpoints im−1 and im . A path is a walk
with no repeated node or edge. A cycle is a walk with no repeated node
or edge except i0 = in . If the graph is simple then a path or a cycle can
be determined uniquely by an ordered sequence of nodes. Throughout this
paper, however, we use node sequences to describe paths and cycles even in
graphs with multiple edges, but we assume that the edges of the path are
all determined. It is usually apparent from the context or the type of the
path which edge belongs to the path in multiple edges. We say a walk or a
path is between the first and the last nodes of the list in G. We call the first
and the last nodes endpoints of the walk or of the path. All other nodes are
the inner nodes.
For a walk or path π = hi1 , . . . .in i, any subsequence hik , ik+1 , . . . , ik+p i,
1 ≤ k, k + p ≤ n, whose members appear consecutively on π, defines a
subwalk or a subpath of π respectively.
2.2. Some definitions for mixed graphs. A mixed graph is a graph containing three types of edges denoted by arrows, arcs (two-headed arrows),
and lines (solid lines). Mixed graphs may have multiple edges of different
types but do not have multiple edges of the same type. We do not distinguish
j and j
i or i≺ ≻j and j ≺ ≻i, but we do distinguish bebetween i
tween j ≻i and i ≻j. In this paper we are only considering mixed graphs
that do not contain loops of any type. These constitute the class of loopless
mixed graphs.
For mixed graphs, we say that i is a neighbour of j if these are endpoints
of a line, and i is a parent of j and j is a child of i if there is an arrow from

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

5

i to j. We also define that i is a spouse of j if these are endpoints of an arc.
We use the notations ne(j), pa(j), and sp(j) for the set of all neighbours,
parents, and spouses of j respectively.
In the cases of i ≻j or i≺ ≻j we say that there is an arrowhead pointing
to (at) j.
A walk hi = i0 , i1 , . . . , in = ji is directed from i to j if all ik ik+1 edges
are arrows pointing from ik to ik+1 . If there is a directed walk from j to i
then j is an ancestor of i and i is a descendant of j. We denote the set of
ancestors of i by an(i). Notice that, unlike some authors,we do not consider
i to be in the set of ancestors or descendants of i. Moreover, a cycle with
the above property is called a directed cycle.
A walk hi = i0 , i1 , . . . , in = ji from i to j is a semi-directed walk if it
only consists of lines and arrows (it may contain only one type of edge),
and every arrow ik ik+1 is pointing from ik to ik+1 . Thus a directed walk is
a type of semi-directed walk. We shall say that i is anterior of j if there
is a semi-directed walk from i to j. We use the notation ant(i) for the
set of all anteriors of i. Notice again that, similar to ancestors, we do not
consider aS
node i to be an anterior of itself. For a set of nodes A, we define
ant(A) = i∈A ant(i) \ A. Notice also that, since ancestral graphs have no
arrowheads pointing to lines, our definition of anterior extends the notion
of anterior used in [18] for ancestral graphs. Moreover, a cycle with the
properties of semi-directed walks is called a semi-directed cycle.
A section of a walk in a mixed graph is a maximal subwalk that only
consists of lines. Thus, any walk decomposes uniquely into sections (that
are not necessarily edge-disjoint and may also be single nodes). Similar to
nodes, all sections on a walk between i and j are inner sections except those
that contain i or j, which are endpoint sections. As in any walk, we can
also define the endpoints of a section. A section ρ on a walk π is called
a collider section if one of the three following walks is a subwalk of π:
i ≻ρ≺ j, i≺ ≻ρ≺ j, and i≺ ≻ρ≺ ≻ j. All other sections on π are
called non-collider sections. We may speak of collider or non-collider sections
without mentioning the relevant walk when this is apparent from context.
A trislide on a walk π is a subpath hi = i0 , i1 , . . . , in = ji, where ii1 and
in−1 j are arrows or arcs and the subpath ρ′ = hi1 , . . . , in−1 i is a section.
...
◦ ≺ j, i≺ ≻◦
...
◦
Three types of trislides i ≻◦
≺ j, and i≺ ≻ ◦
...
◦ ≺ ≻ j are collider trislides and all other
types of trislides are non-collider on any walk of which the trislide is defined.
A tripath is a trislide where the subpath ρ′ is a single node. Note that
[19] used the term V-configuration for such a path. ([7] and most texts let
a V-configuration be a tripath with non-adjacent endpoints.) Tripaths and

6

K. SADEGHI

their inner nodes can be defined to be colliders or non-colliders as trislides
and their inner sections.
Two walks π1 and π2 (including trislides, tripaths, or edges) between i
and j are called endpoint-identical if there is an arrowhead pointing to the
endpoint section containing i on π1 if and only if there is an arrowhead
pointing to the endpoint section containing i on π2 ; and similarly for j.
k ≻l≺ ≻j, and i ≻k≺ ≻l
j are
For example, the paths i ≻j, i
all endpoint-identical as they have an arrowhead pointing to the section
containing j but no arrowhead pointing to the section containing i on the
k≺ ≻j.
paths, but they are not endpoint-identical to i
2.3. Chain graphs. Chain graphs (CGs) is a graph consisting of lines
and arrows that does not contain any semi-directed cycles with at least one
arrow.
It is implied from the definition that CGs are characterized by having
a node set that can be partitioned into disjoint subsets forming so-called
chain components. These are connected subgraphs consisting only of undirected edges and are obtained by removing all arrows in the graph. All edges
between nodes in the same chain component are lines, and all edges between
different chain components are arrows. In addition, the chain components
can be ordered in such a way that all arrows point from a chain with a higher
number to one with a lower number.
For example, in Fig. 1(a) the graph is a chain graph with chain components τ1 = {l, j, k}, τ2 = {h, q}, and τ3 = {p}, but in Fig. 1(b) the graph
is not a chain graph because of the existence of the hh, k, qi semi-directed
cycle.
l

l
h

h
p

j

p

j

q
k

q
k

(a)

(b)

Fig 1. (a) A CG. (b) A mixed graph that is not a CG.

If one replaces every chain component with a single node, one obtains a
directed acyclic graph (DAG), a graph consisting exclusively of arrows and
without any directed cycles.

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

7

Notice that generally CGs are defined to contain arrows and one symmetric type of edge in their chain component, which can be. e.g., arcs. In this
sense , the type of CG in which we are interested in this paper is a line CG.
can be lines or arcs)
3. LWF Markov property for CGs. An independence model J over
a set V is a set of triples hX, Y | Zi (called independence statements), where
X, Y , and Z are disjoint subsets of V and Z can be empty, and h∅, Y | Zi and
hX, ∅ | Zi are always included in J . The independence statement hX, Y | Zi
is interpreted as “X is independent of Y given Z”. Notice that independence models contain probabilistic independence models as a special case.
For further discussion on independence models, see [23].
A graph G also induces an independence model J (G). One way is by using
a separation criterion, which determines whether for three disjoint subsets
A, B, and C of the node set of G, hA, B | Ci ∈ J (G). Such a criterion verifies
whether A is separated from B by C in the sense that there are no walks
or paths of specific types between A and B given C in the graph. Such a
separation is denoted by A ⊥ B | C. It is clear that J (G) satisfies the global
Markov property, which states that if A ⊥ B | C in G then hA, B | Ci ∈ J .
For CGs, at least four different separation criteria, i.e. four different types
of global Markov property have been discussed in the literature. Drton [3]
has classified them as (1) the LWF or block concentration Markov property,
(2) the AMP or concentration regression Markov property, as defined and
studied by [1], (3) a Markov property that is dual to the AMP Markov
property, and (4) the multivariate regression Markov property, as introduced
by [2] and studied extensively recently; for example see [12; 27].
In this paper, we are interested in the LWF Markov property, and we
introduce two equivalent separation criteria for this in this section. Henceforth, for the sake of brevity, by CGs we refer to CGs with the LWF Markov
property.
The moralization criterion for CGs was defined in [5] and is a generalization of the moralization criterion for DAGs defined in [10]; see also [9]. The
moral graph of a chain graph G, denoted by (G)m is a graph that consists
only of lines and that is generated from G as follows: for every edge ij in
G there is a line ij in (G)m . In addition if nodes i and j are parents of the
same chain component in G then there is the line ij in (G)m .
Now let Gant(A∪B∪C) be the induced subgraph of G generated by ant(A ∪
B ∪C). The moralization criterion states that for A, B, and C, three disjoint
subsets of the node set of G, if there are no paths between A and B in
(Gant(A∪B∪C) )m whose inner nodes are outside C then A ⊥ mor B | C.

8

K. SADEGHI
j

k

l

h

q

r

(a)

p

j

h

k

l

q

r

(b)

Fig 2. (a) A chain graph G. (b) The moral graph (Gant({j,h,l}) )m .

An equivalent criterion, called the c-separation criterion for CGs was
defined in [24]. Here we present a simpler version of that criterion, presented
in [22], with a different notation and wording:
A walk π in a CG is a c-connecting walk given C if every collider section
of π has a node in C and all non-collider sections are outside C. A section on
π is open if either: it is a collider section and one of its nodes is in C; or it is
a non-collider section and all its nodes are outside C. Otherwise it is blocked.
We say that A and B are c-separated given C if there are no c-connecting
walks between A and B given C, and we use the notation A ⊥ c B | C.
Notice that, as mentioned in [24], there is potentially an infinite number
of walks, and therefore, this might not be an appropriate criterion for testing
independencies. Although, in this paper, we only use this criterion in order
to prove our theoretical results regarding marginalization and conditioning,
and an infinite number of walks is not an issue for this purpose, in [22], it
was shown that this criterion can also be implemented with an algorithm.
For example, in the graph of Fig. 2(a), the independence statement j ⊥ h | l
does not hold. This can be seen by looking at the moral graph (Gant({j,h,l}) )m =
(G{j,h,k,q,l,r})m in Fig. 2(b), and observing that the inner nodes of the path
hj, k, q, hi are outside the conditioning set. The same conclusion can be made
by looking at the walk hj, k, l, r, q, hi, where the non-collider sections k and
q are outside the conditioning set, but the inner node l of the collider section
hl, ri is in the conditioning set.
The equivalence of the moralization criterion and the original c-separation
criterion was proven in Consequence 4.1 in [24]. The equivalence with the
mentioned simplified criterion was proven in [22]. We use the notation Jc (G)
for the independence model induced from G by the above criteria.
We first prove the following lemma, which provides an equivalent type of
walk to c-connecting walks:
Lemma 1. There is a c-connecting walk between i and j given C if and
only if there is a walk between i and j whose sections are all paths, and

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

9

on which nodes of every collider section are in C ∪ ant(C), and non-collider
sections are outside C. In addition, these walks can be chosen to be endpointidentical.
Notice that by the same method as the proof of this lemma, one can
always assume that a section on a walk is a path. This is our assumption
throughout the paper unless otherwise stated.
4. Stability of CGs under marginalization and conditioning. For
a subset C of V , the independence model after conditioning on C, denoted
by α(J ; ∅, C), is
α(J ; ∅, C) = {hA, B | Di : hA, B | D ∪ Ci ∈ J and (A ∪ B ∪ D) ∩ C = ∅}.
One can observe that α(J ; ∅, C) is an independence model over V \ C.
We now present the definition of stability under conditioning [19]: Consider a family of graphs T . If, for every graph G = (V, E) ∈ T and every disjoint subsets C of V , there is a graph H ∈ T such that J (H) =
α(J (G); ∅, C) then T is stable under conditioning. Notice that the node set
of H is V \ C.
We will see as a corollary of the results and algorithms in the next section
that CGs are stable under conditioning.
Similar to the conditioning case, for a subset M of V , the independence
model after marginalization over M , denoted by α(J ; M, ∅), is defined by
α(J ; M, ∅) = {hA, B | Di ∈ J : (A ∪ B ∪ D) ∩ M = ∅}.
One can observe that α(J ; M, ∅) is an independence model over V \ M .
The definition of stability under marginalization is defined similarly to
the conditioning case: for a family of graphs T , if, for every graph G =
(V, E) ∈ T and every disjoint subsets C of V , there is a graph H ∈ T such
that J (H) = α(J (G); M, ∅) then T is stable under marginalization. We
see again that the node set of H is N = V \ M .
CGs are not closed under marginalization. For example, it can be shown
that G in Fig. 3 is a CG (in fact a DAG) whose induced marginal independence model cannot be represented by a CG. We leave the details as an
exercise to the reader.
h

i

j

k

l

Fig 3. (a) A chain graph G, by which it can be shown that the class of CGs is not
stable under marginalization. (6 6 ∈ M .)

◦

10

K. SADEGHI

Hence, we define a class of graphs that is stable under marginalization
and contains CGs: the class of chain mixed graphs (CMGs) is the class of
mixed graphs without semi-directed cycles with at least an arrow. Notice
that we allow CMGs to have multiple edges consisting of arcs and arrows
and arcs and lines. This is a generalization of chain graphs since if a CMG
does not contain arcs then it is a chain graph.
For example, in Fig. 4(a) the graph is a CMG, but in Fig. 4(b) the graph
is not a CMG because of the existence of the hh, p, qi semi-directed cycle.
I

I
h

h

j

j
p

p

q
k

q
k

(a)

(b)

Fig 4. (a) A CMG. (b) A mixed graph that is not a CMG.

We provide a c-separation criterion for CMGs, and using this, show that
CMGs are closed under marginalization. For this purpose, we provide in
this section an algorithm that, from a CMG (or a chain graph) G and after
marginalization over M , generates a CMG with the corresponding independence model after marginalization over M .
We define a c-separation criterion for CMGs with exactly the same wordings as that of CGs: a walk π in a CG is a c-connecting walk given C if every
collider section of π has a node in C and all non-collider sections are outside
C. We say that A and B are c-separated given C if there are no c-connecting
walks between A and B given C, and we use the notation A ⊥ c B | C.
However, notice that this is in fact a generalization of the c-separation
criterion for CGs since, for CMGs, bidirected edges on π may make a section
collider.
We now provide an algorithm that, from a chain mixed graph G and after
marginalization over M , generates a CMG with the corresponding independence model after marginalization over M . Notice that this algorithm may
indeed be applied to a CG.
Algorithm 1. αCM G (G; M, ∅):(Generating a CMG from a chain
mixed graph G after marginalization over M )
Start from G.

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

11

1. Generate an ij edge as in Table 1, steps 8 and 9, between i and j on
a collider trislide with an endpoint j and an endpoint in M if the edge
of the same type does not already exist.
2. Generate an appropriate edge as in Table 1, steps 1 to 7, between the
endpoints of every tripath with inner node in M if the edge of the same
type does not already exist. Apply this step until no other edge can be
generated.
3. Remove all nodes in M .
Table 1

Types of edge induced by tripaths with inner node m ∈ M and trislides with
endpoint m ∈ M .
1

i≺

m≺

j

generates

i≺

j

2

i≺

m

j

generates

i≺

j

3

i≺ ≻m

j

generates

i≺ ≻j

4

i≺

m

≻j

generates

i≺ ≻j

5

i≺

m≺ ≻j

generates

i≺ ≻j

6

i

m≺

j

generates

i≺

j

7

i

m

j

generates

i

j
j

8

m

≻i

···

◦≺

j

generates

i≺

9

m

≻i

···

◦ ≺ ≻j

generates

i≺ ≻j

Notice that, here and elsewhere, by removing nodes we mean also removing all the adjacent edges to those nodes. Notice also that all the cases
generate an endpoint-identical edge to the tripath or the trislide. In addition, in cases 8 and 9, the node m is separate from the inner nodes of the
concerned trislide since otherwise there will be a semi-directed cycle in the
graph.
This algorithm is a generalization of the marginalization part of the
summery-graph-generating algorithm [19]. The first seven cases are exactly
the same as the corresponding cases in the summery-graph-generating algorithm, whereas cases 8 and 9 do not appear in the summery-graph-generating
algorithm since in summary graphs there are no arrowheads pointing to lines.
The other reason is that here we deal with connecting walks instead of paths,
and the subwalk hi, m, ii may be present in a connecting walk. In general,
here in this algorithm, and in later algorithms in this paper, the sections

12

K. SADEGHI
j

k

l

j

h

q

r

h

(a)

k

l

q

r

(b)

j

k

l

j

h

q

r

h

(c)

l

q

r

(d)

◦

Fig 5. (a) A chain graph G, 6 6
∈ M . (b) The graph after applying step 1 of
Algorithm 1 (case 8 of Table 1). (c) The graph after applying step 2 of Algorithm
1 (case 4 of Table 1) . (d) The generated CMG after applying step 3.

are treated in the same way as the nodes are treated in the algorithms that
generate summary graphs, acyclic directed mixed graphs (ADMGs) [17],
or ancestral graphs. It is also worth noticing that all these algorithms are
indeed generalizations of the ordinary latent projection operation; see [16].
Fig. 5 illustrates how to apply Algorithm 1 step by step to a CG. We
consider Algorithm 1 a function denoted by αCM G . Notice that for every
chain mixed graph G, it holds that αCM G (G; ∅, ∅) = G. We first show that
αCM G (G; M, ∅) is a CMG:
Proposition 1.

Graphs generated by Algorithm 1 are CMGs.

We first provide lemmas that express the global behavior of step 2 of
Algorithm 1 as well as a generalization and an implication of step 1 (in the
Appendix in [20]):
Lemma 2. Let G be a CMG. There exists an edge between i and j in
αCM G (G; M, ∅) if and only if there exists an endpoint-identical walk between
i and j in the graph generated after applying step 1 of Algorithm 1 to G whose
inner sections are all non-collider and whose inner nodes are all in M .
The following theorem shows that αCM G (·; ·, ∅) is well-defined in the sense
that, instead of directly generating a CMG, we can split the nodes that we
marginalize over into two parts, first generate the CMG related to the first
part, then from the generated CMG, generate the desired CMG related to
the second part.

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

13

Theorem 1. For a chain mixed graph G and disjoint subsets M and
M1 of its node set,
αCM G (αCM G (G; M, ∅); M1 , ∅) = αCM G (G; M ∪ M1 , ∅).
Some CMGs may not be generated after marginalization for CGs. In the
following proposition, we provide the exact set of graphs to which CMGs
are mapped after marginalization. Denote by CG the set of all CGs and by
CMG the set of all CMGs.
Proposition 2.
properties:

Define H to be the subset of CMG with the following

1. There is no collider trislide of form k≺ ≻i
there is an arrow from l to i;
2. there is no collider trislide of form k≺ ≻i
there are kj, il, and ij arcs.

...

j≺

...

j ≺ ≻l unless

l unless

Then αCM G (·; ·, ∅) maps CG and a subset of the node set of its member
surjectively onto H.
Here we prove the main result of this section:
Theorem 2. For a chain mixed graph G and disjoint subsets A, B, M ,
and C1 of its node set,
hA, B | C1 i ∈ Jc (αCM G (G; M, ∅)) ⇐⇒ hA, B | C1 i ∈ Jc (G).
We, therefore, have the following immediate corollary:
Corollary 1. The class of chain mixed graphs, CMG, with c-separation
criterion is stable under marginalization.
5. Stability of CMGs under marginalization and conditioning.
5.1. Stability of CMGs under conditioning. In the previous section, we
showed that the class of CMGs is stable under marginalization. In this section, we first show that the class of CMGs is also stable under conditioning,
and provide an algorithm for conditioning for CMGs:
Algorithm 2. αCM G (G; ∅, C):(Generating a CMG from a chain mixed
graph G after conditioning on C)
Start from G.

14

K. SADEGHI

1. Find all nodes in C ∪ ant(C) and call this set S.
2. For collider trislides illustrated in Table 2, steps 4 and 5, with an
endpoint i and one endpoint in S, generate an ij edge following the
table if the edge does not already exist.
3. For collider trislides (including tripaths) illustrated in Table 2, steps
1-3, with at least one inner node in S, generate an edge following the
table if the edge does not already exist. Apply this step repeatedly until
no other edge can be generated, but do not use generated lines (to
generate new sections).
4. Remove the arrowheads of all arrows and arcs pointing to members of
S (i.e. turn such arrows into lines and such arcs into arrows).
5. Remove all nodes in C.
Table 2

Types of edges induced by trislides with an inner node or endpoint
s ∈ S = C ∪ ant(C).
1

i

≻s

···

s≺

j

generates

i

j

2

i≺ ≻s

···

s≺

j

generates

i≺

j

3

i≺ ≻s

···

s≺ ≻ j

generates

i≺ ≻j

4

s≺ ≻i

···

◦≺

j

generates

i≺

5

s≺ ≻i

···

◦ ≺ ≻j

generates

i≺ ≻j

j

Notice that if a node of a section is in S then all the inner nodes are in S,
thus, we may speak of a section being in S. Notice also that all the steps of
the algorithm generate endpoint-identical edges to the concerned trislides. In
addition, we can assume that the endpoints of trislides are disjoint from the
inner nodes, since (1) j as an endpoint of an arrow cannot be also an inner
node because the graph does not contain semi-directed cycles; and (2) cases
2 and 3 with i an inner node are equivalent to cases 4 and 5 respectively,
and cases 4 and 5 with s an inner node are equivalent to cases 2 and 3
respectively.
Similar to Algorithm 1, this algorithm is a generalization of the conditioning part of the summery-graph-generating algorithm [19]. The first three
cases are the same when one considers sections here to be the nodes in the
summery-graph-generating algorithm. Cases 4 and 5 do not appear in the
summery-graph-generating algorithm for the same reasons explained before.
Fig. 6 illustrates how to apply Algorithm 2 step by step to a CMG.

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS
j

k

j

k

l
h

l
h

q

(a)
j

q

(b)

k

j

k

l
h

l
h

q

(c)
j

q

(d)

k

j

l
h

15

l

q

q

(e)

(f)

◦
✷

Fig 6. (a) A chain mixed graph G,
∈ C. (b) The graph after applying step 1 of
Algorithm 2,
∈ S = C ∪ ant(C). (c) The generated graph after applying step
2 (step 5 of Table 2). (d) The generated graph after applying step 3 (steps 2 and 3
of Table 2). (e) The generated graph after applying step 4. (f ) The generated CMG
from G.

◦
✷

First, let us provide a global interpretation of step 3 of Algorithm 2.
Lemma 3. Let G be a CMG. There exists an edge between i and j in
the graph generated after step 3 of Algorithm 2 if and only if there exists an
endpoint-identical walk to the edge between i and j in the generated graph
after step 2 whose inner sections are all collider and in C ∪ ant(C), and
whose endpoint sections contain a single node (i or j).
We provide two lemmas that explain why the set S can be fixed in the
beginning of the algorithm, and why there is no need to apply step 4 of
Algorithm 2 repeatedly.
Lemma 4. Let G be a CMG. If there is an arrow from j to i or a line
between j and i generated by steps 3 or 4 of Algorithm 2 then j ∈ S =
C ∪ ant(C). In addition, generated lines by Algorithm 2 do not lie on any
collider section in αCM G (G; ∅, C).

16

K. SADEGHI

Lemma 5. Let G be a CMG. A node i is in ant(C) in G if and only if
it is in ant(C) in the graph generated after every step of Algorithm 2 before
step 5.
We now follow the same procedure as in the previous section.
Proposition 3.

Graphs generated by Algorithm 2 are CMGs.

Here, we provide the global interpretation of Algorithm 2.
Lemma 6. Let G be a CMG. There exists an edge between i and j in
αCM G (G; ∅, C) if and only if there exists a walk between i and j in G whose
inner sections are all collider and in S = C ∪ ant(C), and whose endpoint
sections contain a single node (i or j) except when there is an arrowhead at
the section containing i (or j), and i (or j) is a spouse of a member of S.
In addition, the walk and the edge are endpoint-identical except when there
is an arrowhead at the endpoint section containing i (or j), and i ∈ ant(C)
(or j ∈ ant(C)) in G.
Theorem 3.
of its node set,

For a chain mixed graph G and disjoint subsets C and C1

αCM G (αCM G (G; ∅, C); ∅, C1 ) = αCM G (G; ∅, C ∪ C1 ).
Theorem 4. For a chain mixed graph G and disjoint subsets A, B, C,
and C1 of its node set,
hA, B | C1 i ∈ Jc (αCM G (G; ∅, C)) ⇐⇒ hA, B | C ∪ C1 i ∈ Jc (G).
Corollary 2. The class of chain mixed graphs, CMG, with c-separation
criterion is stable under conditioning.
Applying Algorithm 2 to a CG, step 2 becomes inapplicable, and step
3 specializes to generating a line between the endpoints of collider trislides
with at least one inner node in S if the line does not already exist. Denote
this specialization by αCG (G, ∅, C). We first have the following:
Proposition 4.

Algorithm 2 generates CGs from CGs.

Denote now by CG the set of all CGs. We also provide the following trivial
statement:

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

17

Proposition 5. The map αCG (·; ∅, ·) from CG and a subset of the node
set of its members to CG is surjective.
Proof. The result follows from the fact that αCM G (G; ∅, ∅) = G.
We, therefore, have the following immediate corollary:
Corollary 3. The class of chain graphs, CG, with the LWF Markov
property is stable under conditioning.
5.2. Simultaneous marginalization and conditioning for CMGs. Corollaries 4 and 2 imply that CMG with c-separation criterion is stable under
marginalization and conditioning, which formally holds when there is a graph
H ∈ CMG such that Jc (H) = α(Jc (G); M, C), where
α(J ; M, C) = {hA, B | Di : hA, B | D∪Ci ∈ J and (A∪B∪D)∩(M ∪C) = ∅}.
We now deal with the case where there are both marginalization and conditioning subsets in a CMG. We first define maximality in order to simplify
the results. A graph is maximal if to every non-adjacent pairs of nodes, there
is an independence statement associated. CMGs are not maximal since, for
example, the class of ancestral graphs [18] is a subclass of CMGs, and there
exist non-maximal ancestral graphs; see also Fig. 7, for an example of a
CMG that is not ancestral and that induces no independence statement of
form j ⊥ c l | C for any choice of C. There is a method to generate, from a
non-maximal CMG, a maximal CMG that induces the same independence
model, which is beyond the scope of this manuscript. However, here we provide a sufficient condition for non-maximal graphs as a lemma, which will
be used in our proofs.
q
j

k

p

l

Fig 7. A non-maximal AnG.

Lemma 7. If there is a collider trislide between i and j in G such that
there is an arrow from an inner node of the trislide to j (or i) and i 6∼ j
then G is not maximal.
We also provide the following lemma, which deals with the global behavior
of the simultaneous marginalization and conditioning as described later in
this section:

18

K. SADEGHI

Lemma 8. There is an edge between i and j in αCM G (αCM G (G; ∅, C); M, ∅)
if and only if there is a walk between i and j in G on which (i) all nodes
on collider sections are in C ∪ ant(C); (ii) on non-collider sections, (a) all
nodes are in M , or (b) one endpoint is in M and also either a child of a
node in M or a spouse of a node in C ∪ ant(C), and the other endpoint has
an arrowhead at it from the adjacent node on the walk. In addition, the walk
and the edge are endpoint-identical except when there is an arrowhead at the
endpoint section containing i (or j), and i ∈ ant(C) (or j ∈ ant(C)) in G.
We now have the following important result, which illustrates that, for
maximal graphs, in order to both marginalize and condition, it does not
matter whether we marginalize first by using Algorithm 1 and then condition
by using Algorithm 2 or vice versa:
Proposition 6. For a chain mixed graph G and two disjoint subsets M
and C of its node set, it holds that
αCM G (αCM G (G; M, ∅); ∅, C) = αCM G (αCM G (G; ∅, C); M, ∅)
if αCM G (αCM G (G; M, ∅); ∅, C) is maximal.
It is also clear from the proof that if we drop the maximality assumption
then the two concerned graphs in the proposition induce the same independence models. In addition, we show that the corresponding algorithm
(Algorithm 1 followed by Algorithm 2 or vice versa) is well-defined for maximal graphs. We denote the corresponding function by αCM G (G; M, C). In
general, one can first apply Algorithm 2 followed by Algorithm 1, in which
case we showed in the proof that an edge is present between the endpoints
of the walk described in Lemma 7.
Theorem 5. For a chain mixed graph G and disjoint subsets M , M1 ,
C, and C1 of its node set,
αCM G (αCM G (G; M, C); M1 , C1 ) = αCM G (G; M ∪ M1 , C ∪ C1 )
if the two graphs are maximal.
Proof. The result follows from the definition and Proposition 6, Theorem 3, and Theorem 1.
In Proposition 2, we showed that all CGs after marginalization are mapped
onto H, which is a subclass of CMGs. Here we show that CGs after marginalization and conditioning are also mapped onto H.

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

19

Proposition 7. The map αCM G maps CG and two subsets of the node
set of its members surjectively onto H.
We are now ready to provide the main result, which illustrates that by
applying Algorithm 1 followed by Algorithm 2 (or vice versa), we obtain the
marginal and conditional independence model for a CMG (or a CG) after
marginalization and conditioning.
Theorem 6. For a chain mixed graph G and disjoint subsets A, B, M ,
C, and C1 of its node set,
hA, B | C1 i ∈ Jc (αCM G (G; M, C)) ⇐⇒ hA, B | C ∪ C1 i ∈ Jc (G).
Proof. By definition and Proposition 6, Theorem 4, and Theorem 2, it
is implied that
hA, B | C1 i ∈ Jc (αCM G (G; M, C)) = Jc (αCM G (αCM G (G; M, ∅); ∅, C)) ⇐⇒
hA, B | C ∪ C1 i ∈ Jc (αCM G (G; M, ∅)) ⇐⇒ hA, B | C ∪ C1 i ∈ Jc (G).

6. Anterial graphs. The definition of CMGs can be considered a generalization of the definition of summary graphs (SGs) by [26]: CMGs collapse
to SGs when there are no arrowheads pointing to lines. CMGs are also analogous to SGs in the sense that they capture the marginal and conditional
models for CGs, and SGs capture the marginal and conditional models for
DAGs; and CMGs exclude graphs with semi-directed cycles while SGs exclude graphs with directed cycles.
The class of ancestral graphs, defined by [18], captures the same independence models as those of SGs, but has a simpler structure than SGs. In this
section, we define the class of anterial graphs (AnGs), which can be thought
of as a generalization of and analogous to ancestral graphs with the same
relationship to CMGs as that of ancestral graphs to SGs.
An anterial graph is a mixed graph that contains neither semi-directed
cycles that contain at least an arrow; nor does it contain arcs with one
endpoint that is an anterior of the other endpoint. This implies that, unlike
CMGs, AnGs are simple graphs. For example, in Fig. 8(a) the graph is an
AnG, but in Fig. 8(b) the graph is not an AnG because of the existence of
the arc kq, where k ∈ ant(q) via the semi-directed path hk, j, l, h, qi as well
as the arc qp, where q ∈ ant(p).

20

K. SADEGHI
I

I
h

h

j

j
p

p

q
k

q
k

(a)

(b)

Fig 8. (a) An AnG. (b) A CMG that is not an AnG.

Here we show that, from an anterial graph and after marginalization
and conditioning, how to generate an anterial graph with the corresponding
marginal and conditional independence model.
Algorithm 3.
Start from G.

αAnG (G; M, C): (Generating an AnG from an anterial graph G)

1. Apply Algorithm 2.
2. Apply Algorithm 1.
3. Generate respectively arrows from j to i or arcs between i and j for trislides j ≻ ◦
···
i≺ ≻k or j ≺ ≻ ◦
···
i≺ ≻k when
k ∈ ant(i) if the arrow or the arc does not already exist.
4. Generate respectively an arrow from j to i or an arc between i and j for
···
km ≺ ≻i or j ≺ ≻k1
···
km ≺ ≻i
trislides j ≻k1
when there is an 1 ≤ r ≤ m such that kr ∈ ant(i) if the arrow or the
arc does not already exist. Continually apply this step until it is not
possible to apply it further.
5. Remove the arc between j and i in the case that j ∈ ant(i), and replace
it with an arrow from j to i if the arrow does not already exist; and
remove the arc between j and i in the case that j ∈ ant(i) and i ∈
ant(j), and replace it with a line between i and j if the line does not
already exist.
Notice that, as we will see, steps 3, 4, and 5 of Algorithm 3 generate,
from the generated CMG after step 2, an AnG that captures the same
independence model as that of the CMG. In addition, in step 4, one kr
being in ant(i) implies that all kr , 1 ≤ r ≤ m, are in ant(i), and in this sense
we can say that a section is in ant(i).
This Algorithm is a generalization of the related algorithm for ancestral
graphs [18; 19]. Again, one can see that sections here are treated in the same
way as nodes in the ancestral-graph-generating algorithms. The idea here
is that step 4 generates a dependency between j and i (which in fct always

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS
r
s

j

k

j

k

(c)

p

l

(a)

r
s

r

q

l

q

s

q

j

s

l

k

(b)

r
p

21

j

k

p

q
l

p

(d)

Fig 9. (a) A chain mixed graph G. (b) The graph after applying step 3 of Algorithm
3. (c) The graph after applying step 4. (d) The generated AnG after applying step
5.

exists) before step 5 makes the graph anterial, and consequently destroys
the dependency between i and j.
Fig. 9 illustrates how to apply these steps to a CMG. We consider Algorithm 3 a function denoted by αAnG . Notice that for every anterial graph G,
it holds that αAnG (G; ∅, ∅) = G. We again follow a parallel theory as that
in the previous sections:
Proposition 8.

Graphs generated by Algorithm 3 are AnGs.

We first provide two lemmas that deal with the global behavior of the
algorithm.
Lemma 9. Let H be a chain mixed graph. It holds that i ∈ ant(j) in H
if and only if i ∈ ant(j) in the anterial graph generated after applying steps
3, 4, and 5 of Algorithm 3 to H.
Denote by a walk between i and j on which all sections are collider and
every inner section is in ant(i) a subprimitive inducing walk from j to i.
This is a special case of a generalization of primitive inducing paths, defined in [18], where all nodes are anteriors of one of the endpoints, not
either of the endpoints. We also denote the function corresponding to steps
3, 4, and 5 of Algorithm 3 by αCM G.AnG . Notice that αAnG (G; M, C) =
αCM G.AnG (αCM G (G; M, C)).
Lemma 10. Let H be a chain mixed graph. There is an edge between i
and j in αCM G.AnG (H) if and only if there is a subprimitive inducing walk

22

K. SADEGHI

from j to i in H (which might also contain i as an inner node) with singleelement endpoint sections. In addition, the edge and the walk are endpointidentical except when i ∈ ant(j) or j ∈ ant(i) in H, in which case there is
no arrowhead at i or at j, respectively, on the ij edge in αCM G.AnG (H).
We now prove that Algorithm 3 does not need to be applied to an anterial
graph, but it can be applied to a chain mixed graph.
Lemma 11. Let H be a chain mixed graph and M and C be two subsets
of its node set. It holds that αAnG (αCM G.AnG (H); M, C) = αAnG (H; M, C).
Theorem 7. For an anterial graph G and disjoint subsets M , M1 , C,
and C1 of its node set,
αAnG (αAnG (G; M, C); M1 , C1 ) = αAnG (G; M ∪ M1 , C ∪ C1 ),
if the two graphs are maximal.
Proof. Using Theorem 5 and Lemma 11, we have the following:
αAnG (αAnG (G; M, C); M1 , C1 ) = αAnG (αCM G.AnG (αCM G (G; M, C)); M1 , C1 ) =
αAnG (αCM G (G; M, C); M1 , C1 ) = αCM G.AnG (αCM G (αCM G (G; M, C); M1 , C1 )) =
αCM G.AnG (αCM G (G; M ∪ M1 , C ∪ C1 )) = αAnG (G; M ∪ M1 , C ∪ C1 ).

Denote the set of all AnGs by AN G.
Proposition 9.
ties:

Let K be the subset of AN G with the following proper-

1. There is no collider trislide of form k≺ ≻i
there is an arrow from l to i.
2. There is no collider trislide of form k≺ ≻i
there are jk and il arcs and an ij line.

...

j≺

...

j ≺ ≻l unless

l unless

Then αAnG maps CG and two subsets of the node set of its members surjectively onto K.
Theorem 8. For an anterial graph G and disjoint subsets A, B, M , C,
and C1 of its node set,
hA, B | C1 i ∈ Jc (αAnG (G; M, C)) ⇐⇒ hA, B | C ∪ C1 i ∈ Jc (G).
Corollary 4. The class of anterial graphs, AN G, with c-separation
criterion is stable under marginalization and conditioning.

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

23

7. Probabilistic independence models for CMGs and AnGs and
comparison to other types of graphs. The most interesting independence models are induced by probability distributions. Consider a set V and
a collection of random variables (Xα )α∈V with joint density fV . By letting
XA = (Xv )v∈A for each subset A of V , we then use the short notation
A ⊥⊥ B | C for XA ⊥⊥ XB | XC and disjoint subsets A, B, and C of V .
For a given independence model J , a probability distribution P is called
faithful with respect to J if, for random vectors XA , XB , and XC with
probability distribution P ,
A ⊥⊥ B | C if and only if hA, B | Ci ∈ J .
We say that J is probabilistic if there is a distribution P that is faithful to
J.
From a given collection of random variables (Xα )α∈V with a probability
distribution P , one can induce an independence model J (P ) by demanding
if A ⊥⊥ B | C then hA, B | Ci ∈ J (P ).
Notice that J (P ) is obviously probabilistic.
For a chain graph G, we say that a probability distribution with density
f factorizes with respect to G if
Y
f (xτ | xpa(τ ) ),
f (x) =
τ ∈T

where T is the set of chain components of G; and
Y
φa (x),
f (xτ | xpa(τ ) ) =
a

where a varies over all subsets of τ ∪ pa(τ ) that are complete in the moral
graph of the subgraph of G induced by τ ∪ pa(τ ), and φa (x) is a function
that depends on x through xa only; see [9] for more discussion.
Now let α(P, ; M, C) be the probability distribution obtained by usual
probabilistic marginalization and conditioning for the probability distribution P . It is easy to show that if P is faithful to J then α(P, ; M, C) is
faithful to the marginal and conditional independence model α(J ; M, C);
see Theorem 7.1 and Corollary 7.3 of [18].
It is also known that if G is a CG then there is a regular Gaussian distribution that is faithful to it. In fact, almost all the regular Gaussian distributions that factorize with respect to a CG are faithful to it; see [14]. In
other words, the independence mode Jc (G) is probabilistic.

24

K. SADEGHI

By Propositions 2, 7, and 9, a considerably large subclass of CMGs or
AnGs are obtained by chain graphs after marginalization and conditioning.
Hence, it is implied by the discussion above that for a graph H in these
subclasses, Jc (H) is probabilistic; i.e. there is a distribution (in fact at least
a Gaussian distribution) that is faithful to it.
One can obtain the same result for the strictly positive discrete probability
distributions since there is such a distribution that is faithful to a given CG
[24]. These results motivate the use of CMGs and AnGs.
The next, and probably more important, question in order to justify the
use of these classes is whether it is possible to find a parametrization, e.g.
Gaussian or discrete, of these graphs.
In the Gaussian case, there exists a known parametrization for the regular
Gaussian distributions that factorize with respect to a CG; see [28] and
[14] for two slightly different but equivalent parametrizations. For maximal
ancestral graphs (MAGs), there is a known parametrization in the Gaussian
[18]. We believe that it is possible to extend this parametrization to the class
of maximal AnGs. Here is some possible actions in order to generalize this
parametrization.
Notice first that the classes of CMGs and AnGs are not maximal, as
explained in Section 5.2. However, as mentioned before, there is a method
to generate, from non-maximal CMGs and AnGs, maximal CMGs and AnGs
that induce the same independence models. Hence, one can then focus on
the class of maximal AnGs.
Considering the Gaussian parametrization for MAGs, one then needs to
define, instead of one matrix for the undirected part of the MAG, one symmetric matrix for every chain component of the maximal AnG (as it is done
in the Gaussian parametrization for CGs). It is also needed to generalize the
ordering associated to MAGs, e.g. by defining an ordering for chain components containing lines instead of an ordering for the nodes. One may then
follow the method described in Section 8 of the mentioned paper.
Since both parametrizations for CGs and MAGs are curved exponential
families, and consequently the models associated with them are identifiable,
the generalization for AnGs seems to preserve this desirable property.
Introducing a discrete parametrization for CMGs or AnGs seems much
trickier. Similar to the Gaussian case, the goal should be to find a combination of discrete parametrizations for CGs (see, e.g [13]) and summary graphs
(or alternatively ADMGs – see [4]). For CMGs, a parametrization may be
derived from the original CG with the use of structural equation models
with latent variables. This can be considered a generalization of the method
utilized in summary graph models.

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

25

Nonetheless, we again stress the importance of introducing different smooth
parametrizations for CMGs and AnGs in a future work as well as studying
additional non-independence constraints that arise in such models.
Besides the relevant parametrizations, it is clear that CMGs act similarly
to summary graphs in the problem of marginalization and conditioning for
DAGs, and AnGs act similarly to ancestral graphs. To give a more detailed
comparison between CMGs (and AnGs) and summary graphs (and ancestral graphs), we first note that the lines in all these graphs have the same
meaning. As mentioned before, there are no arrowheads at lines in the latter types, and one can think of sections with arrowheads pointing to them
in the former types in the same manner as the nodes in the latter types.
Indeed summary graphs and ancestral graphs are subclasses of CMGs and
AnGs respectively, thus every summary or ancestral graph model is a CMG
or AnG model.
l≺ k, it
In addition, in CMGs, for a collider trislide of from i ≻j
holds that i ⊥
6 c l, i ⊥
6 c l | j, but i ⊥ c l | {j, k}. However, there is no summary
graph that can capture the same independencies and dependencies. Hence,
for any induced path with 4 nodes (and, of course, for longer paths), one
can provide a CMG that is associated to a different model than summary
graph models. By this, it is clear that the class of CMG models is rich in the
sense that when the number of nodes grows, the number of distinct CMG
models grows faster than the number of distinct summary graph models.
The class of marginal AMP chain graphs (MAMP CGs) deals with a similar problem of marginalization for AMP chain graphs. The lines in these
graphs have a different meaning in independence interpretation (they are
related to lines in AMP CGs), and naturally the class of models they represent is quite different. However, both classes of models contain the class of
regression graph models [27], which itself contains the classes of undirected
(concentration) graph models and the class of multivariate regression chain
graph models as a subclass. In fact, if in a CMG, there is a section with
non-adjacent endpoints that is larger than a single node then it can be seen
that no MAMP CG can induce the same independence statements. This
implies that, in the intersection of CMG and MAMP CG models, there is
no arrowhead pointing to lines (in CMG sense). Therefore, this intersection is the same as the intersection of maximal ancestral graph and MAMP
CG models (since MAMP CGs are maximal, and maximal summary and
ancestral graphs induce the same independence model).
Acknowledgements. The author is grateful to Steffen Lauritzen and
Thomas Richardson for helpful discussions, Nanny Wermuth for helpful dis-

26

K. SADEGHI

cussions and comments, and anonymous referees for the most helpful comments, especially detecting an error in the results.
Appendix: proofs. In the Appendix, we provide proofs of the nontrivial lemmas, propositions, and theorems as well as some more technical
and yet less informative lemmas that are used in the proofs.
Proof of Lemma 1. (⇒) Suppose that there is a c-connecting walk π
between i and j given C. Consider the shortest subpath ρ0 of the section ρ
of π between k and l. If ρ is a collider then a node of ρ is in C, and since
all the nodes on ρ (including those on ρ0 ) are connected by lines, they are
all in C ∪ ant(C). If ρ is a non-collider then all the nodes on ρ (including
those on ρ0 ) are outside C. Hence, by replacing all such ρ by ρ0 we obtain
the desired walk.
(⇐) Suppose that there is a walk π between i and j whose sections are all
paths and nodes of every collider section are in C ∪ ant(C), and non-collider
sections are outside C. We keep all non-collider sections of π intact. For a
collider section ρ between k and l, if there is a node of ρ in C, we keep it
intact. Otherwise we replace ρ with ρ4 = hk, ρ1 , ρ2 , c, ρr2 , ρ3 , li, where ρ1 is
a subpath of ρ between k and h , ρ2 is a semi-directed path from h to a
member c of C, ρr2 is ρ2 in the reverse direction, and ρ3 is a subpath of ρ
between h and l. It is easy to observe that ρ4 is c-connecting given C. (If
there is an arrow on ρ2 then ρ4 consists of non-collider sections containing
ρ1 and ρ3 , and a collider section containing c; otherwise ρ4 is a collider
section containing c.) In addition, ρ and ρ4 are endpoint-identical. Hence,
by this replacement for all such ρ on π, we obtain a c-connecting walk given
C between i and j.
Finally, from the construction of walks that we have in both directions of
the proof, it is seen that the walks are endpoint-identical.
Proof of Proposition 1. The resulting graphs have obviously the three
desired types of edges, thus it is enough to prove that there is no semidirected cycle that contains an arrow in the graph. Suppose, for contradiction, that there exists such a cycle. It is easy to observe that by replacing
a generated line or arrow with the generating tripaths (cases 1, 2, 6, and 7
of Table 1) or trislide (case 8), a semi-directed path remains semi-directed.
Therefore, it is implied inductively that there is a semi-directed path in
the original chain graph. This also contains an arrow since an arrow can
only be replaced by a tripath or a trislide that contains an arrow. This is a
contradiction.

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

27

Proof of Lemma 2. (⇐) Suppose that there exists a walk π between
i and j in the graph generated after applying step 1 of Algorithm 1 to G
whose inner sections are all non-collider and whose inner nodes are all in
M . By Algorithm 1, for a section between k and l, a line between k and
l is generated, and then, for a tripath hh, q, ri consisting of a line hq with
q ∈ M , the same edge as qr is generated. Therefore, a walk is generated
between i and j whose inner nodes are in M , and on which lines may only
be adjacent to i and j, and every section is a non-collider. By applying steps
of Table 1, we trivially obtain an endpoint-identical edge between i and j.
(⇒) Suppose that there is an edge between i and j in αCM G (G; M, ∅). We
are only interested in the case where this edge does not exist after applying
step 1 of Algorithm 1. In this case, this edge is generated by step 2 by one of
the tripaths in steps 1 to 7 of Table 1 in an iteration of step 2. Each edge in
the tripath may have now been generated by a tripath with the inner node
in M . By an inductive argument, we imply that in the graph generated after
applying step 1 of Algorithm 1 to G, there is a walk π (because of possible
self-intersections) between i and j whose inner nodes are in M . We show
that there is no collider section on π: If, for contradiction, there is a collider
section ρ with endpoints hk, ρ, li then it is easy to observe that, in some
iteration of the algorithm, we obtain a collider tripath with endpoints k and
l, but no edge can be generated between k and l by the algorithm. Hence,
there is no edge between i and j in αCM G (G; M, ∅), a contradiction. Since
in every iteration of the algorithm, the existence of an arrowhead at sections
containing i and j does not change, π remains endpoint-identical to the ij
edge.
Lemma 12. Let G be a CMG and M a subset of its node set. If there
···
k≺ j or i
···
k≺ ≻ j in G, and there is
is a path i
a semi-directed path of form m1 ≻m2
...
mr
i with ms ∈ M ,
1 ≤ s ≤ r then Algorithm 1 generates an arrow from j to i or an arc between
i and j, respectively.
Proof. Consider the section between k, i, and m2 . By step 1 of Algorithm 1, an arrow from j to m2 or a jm2 arc is generated. Now by Lemma
2, when we apply step 2 of the algorithm, an arrow from j to i or an ij arc
is generated.
Lemma 13. Let G be a CMG and M a subset of its node set. There is
a walk π in G with sections {ρ1 , . . . , ρr } if and only if there is an endpointidentical walk π ′ in the graph generated after applying step 1 of Algorithm
1 for M with sections {ρ′1 , . . . , ρ′r } such that ρ′q is a subsection of ρq for

28

K. SADEGHI

1 ≤ q ≤ r. In addition, every node on π that is not on π ′ is on a subsection
of π with endpoints l and k such that l exists on π ′ and is a child of a member
of M , and there is an arrowhead to k on π.
Proof. The result follows from the fact that by replacing arrows and
arcs on π ′ by paths in cases 8 and 9 of Table 1 (the replacements that
have occurred in step 1 of Algorithm 1), sections become larger and no new
section is generated; and vice versa.
Proof of Theorem 1. (⇒) Suppose that in αCM G (αCM G (G; M, ∅); M1 , ∅),
there is an edge between i and j. Notice that i, j ∈
/ M ∪ M1 . We prove that
there is the same edge in αCM G (G; M ∪ M1 , ∅). Starting from an edge between i and j, we discuss the type of path or walk that exists between i and
j in every graph generated by different steps of Algorithm 1:
In the graph generated before applying step 2 of Algorithm 1
to αCM G (G; M, ∅) for M1 : By Lemma 2, there exists an endpoint-identical
walk π between i and j whose inner sections are all non-collider and inner
nodes are all in M1 .
In αCM G (G; M, ∅): By Lemma 13, there is a new walk, denoted by π1 .
Define l also as defined in the lemma, and notice that in this case l is both
in M1 and a child of m1 ∈ M1 .
In the graph generated before applying step 2 of Algorithm 1 to
G for M : For every edge of π1 , again by Lemma 2, there exists an endpointidentical walk between its endpoints, but with inner nodes in M . Denote the
new walk generated by replacing all edges of π1 by endpoint-identical walks
at this stage by π2 . Notice that, because of endpoint-identicality, all nodes
on π1 remain non-collider on π2 . In addition, the m1 l arrow might turn into
...
mr
l with
a walk that contains a subwalk of from m ≻m2
m ∈ M ∪ M1 and ms ∈ M , 2 ≤ s ≤ r.
In G: Again by Lemma 13, there is a new walk, denoted by π3 . Notice
that the arrow from m to m2 might be replaced by a path, but nevertheless,
by possibly changing the node m to m′ , there is the same type of walk
from m′ to l with m′ ∈ M ∪ M1 . In addition, l ∈ M1 remains the same as
an endpoint of subsections on which there are nodes on π3 that are not in
M ∪ M1 .
In αCM G (G; M ∪ M1 , ∅): By Lemma 12, all subpaths of π3 of form π ′
are replaced by the k′ l arrows or arcs respectively. Therefore, there is an
endpoint-identical walk whose inner sections are all non-collider and whose
inner nodes are all in M ∪ M1 . By Lemma 2, we conclude that there is an
endpoint-identical (i.e. the same type of) edge between i and j.

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

29

(⇐) Suppose that there is an edge between i and j in αCM G (G; M ∪
M1 , ∅). Starting from this edge, we discuss the type of path or walk that
exists between i and j in every graph generated by different steps of Algorithm 1:
In the graph generated before applying step 2 of Algorithm 1
to G for M ∪ M1 : By Lemma 2, there exists an endpoint-identical walk π
between i and j whose inner sections are all non-collider and inner nodes
are all in M ∪ M1 .
In G: By Lemma 13, there is a new walk, denoted by π1 . Define l also as
defined in the lemma, and notice that in this case l is both in M ∪ M1 and
a child of m1 ∈ M ∪ M1 .
In the graph generated after applying step 1 of Algorithm 1 to
G for M : All subpaths of π1 of the mentioned form and properties π ′ where
l is a child of M can be replaced by kl arrows or lines respectively.
In αCM G (G; M, ∅): Now the generated walk can be partitioned into subwalks with endpoints in outside M and all inner nodes in M (there might
be single edges in the partition). All these subwalks with lengths more than
two satisfy the conditions of Lemma 2 for M . Hence, there exist endpointidentical edges between the endpoints of the subwalks. These edges form a
walk, which is denoted by π2 .
In the graph generated after applying step 1 of Algorithm 1
to αCM G (G; M, ∅) for M1 : Since there are no collider sections on π1 , and
because of endpoint-identicality, there are no collider sections on π2 . In addition, the endpoints l (as defined) of subpaths of π2 whose members may
not be in M1 , are children of M1 . Therefore, again by applying step 1 of the
algorithm for M1 we obtain a walk with all inner nodes in M1 .
In αCM G (αCM G (G; M, ∅); M1 , ∅): Now by applying Lemma 2 to the generated walk, we obtain an endpoint-identical (and hence the same type ij
edge as the original ij edge).
Proof of Proposition 2. First, we prove that every CG G is
mapped into H: By proposition 1, we know that the generated graphs are
CMGs. We consider each case separately:
Suppose that there is a collider trislide of form k≺ ≻i
...
j≺ l
in the generated graph αCM G (G; M, ∅). We go through how this trislide has
been generated by steps of Algorithm 1.
In the graph generated before applying step 2 of Algorithm 1: Since by step
2 of Algorithm 1 only case 7 of Table 1 can generate lines, by an inductive
argument it is clear that between i and j there is a section. By Lemma 2,
instead of the arrow from l to j, there is a walk with non-collider sections and

30

K. SADEGHI

inner nodes in M such that there is an arrowhead at the endpoint section
containing j (say from node r, which may be l).
In addition, notice that G is a CG and by step 1 of Algorithm 1, no arc
is generated from trislides that do not contain arcs. This fact together with
Lemma 2 implies that there is a walk between i and k that only contains
lines and arrows, and, on this walk, there is an arrowhead at the endpoint
section containing i (say at node o, which may be i and has a parent in M ).
By considering the path between r and o, we conclude that by step 1 of
Algorithm 1 (case 8 of Table 1), an arrow from r to o is generated.
In αCM G (G; M, ∅): Now by Lemma 2, and considering the walk with
non-collider sections and inner node in M that connects l, r, o, and i, an
arrow from l to i is generated.
...
j ≺ ≻l
Suppose that there is a collider trislide of form k≺ ≻i
in the generated graph: r and o can be defined in the same way as in the
previous case. Notice that in this case on the walk (obtained by Lemma 2)
there is an arrowhead at the section containing l. By a similar argument
to that in the previous case, we conclude that there is an arc generated
between l and i in the generated graph. By the symmetry in the path, one
can similarly obtain an arc between k and j. Furthermore, by Lemma 2, and
considering the walk with non-collider sections and inner node in M that
connects j, r, o, and i, there exists an arc between i and j in the generated
graph, since, on this walk, there are arrowheads at both sections that contain
i an j.
Now we prove that the function is surjective: Consider an arbitrary
chain mixed graph H in H. Define a chain graph G from H as follows: keep
all arrows and lines of H in G and replace arcs ij with i≺ m ≻j; and
define a subset M of the node set of G as the set of all such m.
We first prove that G is a CG: It only contains the two desired types of
edges. In addition, it does not contain semi-directed cycles that contains an
arrow since if, for contradiction, it does then it must contain the tripath
i≺ m ≻j, which is impossible.
We now prove that αCM G (G; M, ∅) = H: The changes that might occur by step 1 of Algorithm 1 are only when, in H, there are the two types
of collider trislides in properties 1 and 2, which correspond to the walks
...
j ≺ l and k≺ m1 ≻i
...
j ≺ m2 ≻l
k≺ m ≻i
in G. In the former case, the generated arrow from l to i exists in H. In the
latter case, an arrow from m2 to i is generated, but since m2 is only adjacent
to j and l, in the next step of the algorithm, it can only generate il and ij
arcs, both of which exist in H; the same argument also works for the generated arrow from m1 to j. In addition, step 9 is not applied since there are

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

31

no arcs in G. By step 2 of the algorithm, the only type of tripath with inner
node in M is case 4 of Table 1 (except those that are already discussed).
These tripaths obviously turn into the arcs existing in H, and no other edge
is generated.
Proof of Theorem 2. We need to prove that A ⊥ c B | C1 in G ⇐⇒
A ⊥ c B | C1 in αCM G (G; M, ∅).
(⇒) Suppose that there is a c-connecting walk π given C1 between i and
j in G. Consider all maximal subwalks of π whose inner sections are all
non-collider, endpoints are not in M , and inner nodes are all in M . Notice
that all nodes of π that are in M are included in these subwalks since no
collider section on π1 has all nodes in M . Denote such a subwalk by ̟.
In the generated graph after applying step 1 of Algorithm 1: First
consider the case where the endpoints of ̟ are the same node l. Sections on
̟ are non-collider, and hence, the edge between l and an endpoint of ̟ (call
it m) is an arrow from m to l. We can easily obtain a shorter c-connecting
walk by removing ̟ from π if, by doing so, l is on a collider section or on
a non-collider section with no node in C1 . If that is not the case then there
···
◦ ≺ k or l≺ m ≻l
···
◦ ≺ ≻ k,
exists l≺ m ≻l
where l 6∈ C1 but an inner node of the section containing l is in C1 . (Notice
that if l is i or j then one can easily remove m from the walk.) By step 1, there
is a generated lk edge. We replace all these walks with the generated edge
and call the resulting walk π1 . Because the generated edges are endpointidentical to the subwalks, π1 is c-connecting.
In the generated graph after applying step 2 of Algorithm 1: The
subwalks of π1 with the property mentioned above now have distinct endpoints. By Lemma 2, instead of these subwalks, there are endpoint-identical
edges in αCM G (G; M, ∅). By replacing all the subpaths with these edges,
we obtain a walk π2 . Walk π2 exists in αCM G (G; M, ∅) since there are no
members of M on π2 . In addition, π2 is c-connecting given C1 since, because
of endpoint-identicality of the generated edges to the subwalks, every node
that is an inner node of a collider or a non-collider section on π2 is an inner
node of a collider or a non-collider section on π1 , and no node in C1 on π1
has been taken out.
(⇐) Suppose that there is a c-connecting walk π given C1 between i and
j in αCM G (G; M, ∅). We show what types of walks generated π at each step
of Algorithm 1.
In the graph before applying step 2 of Algorithm 1: By Lemma
2, for every edge kl on π, there is an endpoint-identical walk π ′ between
k and l with the stated properties in the lemma. By replacing every edge

32

K. SADEGHI

on π by such π ′ , we obtain a walk π1 . We prove that π1 is c-connecting
given C1 : Notice that π ′ is obviously c-connecting. In addition, because of
endpoint-identicality, for a replaced edge kl, if l is an inner node of a collider
or a non-collider section, after the replacement, it remains an inner node of
a collider or non-collider section respectively, and all added nodes are in M .
In G, before applying step 1 of Algorithm 1: Now a uv edge on
π1 might have been replaced by a path by step 1 of the algorithm, where
u is a child of m ∈ M . By all such replacements, we obtain a larger walk
π2 . Again, because of endpoint-identicality, if u is on a collider section or a
non-collider section ρ1 on π1 then it remains on a (possibly larger) collider
section or a non-collider section ρ2 on π2 respectively. If ρ2 is non-collider
and all inner nodes of the new path are outside C1 then it is clearly open
on π2 . If ρ2 is non-collider with a node in C1 then we modify π2 by adding
the subwalk hu, m, ui (i.e. the arrow from m to u in both directions) to π2 .
Now the subpath of ρ2 between v and u becomes a collider section and open
on π2 , and the rest of ρ2 (with an arrow pointing to it from m) remains a
non-collider section and open. If ρ2 is a collider, it is clearly open since there
is already a node in C1 on ρ1 . Therefore, by an inductive argument, π2 is a
c-connecting walk.
Proof of Lemma 3. (⇐) Suppose that there exists a walk π between i
and j in the generated graph after step 2 whose inner sections are all collider
and in C ∪ ant(C), and endpoint sections contain a single node. We prove
the result by induction on the number of edges of π. If it is 1 then we are
clearly done. If it is n > 1 then consider the trislide τ = hiρki on π, where
ρ is a section. By step 3 of the algorithm, an endpoint-identical edge ik is
generated. Notice that ik is either an arrow or an arc unless possibly k = j.
Now by replacing τ by the ik edge, we obtain a shorter walk with the same
properties. By the induction hypothesis, we obtain the result.
(⇒) Suppose that there is an edge between i and j in the graph generated
after step 3 of Algorithm 2. If this edge were generated by step 3 of Algorithm
2 then it would be generated by one of the first three trislides in Table 2 in an
iteration of step 3 of the algorithm. Each arrow or arc on the trislide may now
have been generated by a trislide with inner nodes in C ∪ ant(C) (since no
generated line can be used in the iterations). Since the trislides are endpointidentical to the generated edge, it is implied that all sections remain collider.
By an inductive argument, we imply that, in the graph generated after
applying step 2 of the algorithm, there is an endpoint-identical walk between
i and j whose inner nodes are in C ∪ ant(C) and all sections are collider. In

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

33

addition, i and j are clearly not adjacent to a line on this walk, i.e., endpoint
sections contain a single node.
Proof of Lemma 4. The first result for step 4 is trivial, and for step 3
follows directly from Lemma 3. This implies that if a generated line lies on
a collider section after step 3 then since j ∈ S, by step 4, all arrowheads at
the section will be removed.
Proof of Lemma 5. One direction of the proof is obvious since steps 1,
2, and 3 of Algorithm 2 do not remove or replace any edges, and by removing
an arrowhead at an arrow pointing to i by step 4, no new node can become
an anterior of i. Thus, suppose that i ∈ ant(C) after step 4 of the algorithm.
We go back on the steps of the algorithm in order to show that i has been
in ant(C).
Before applying step 4 of Algorithm 2: Suppose that there is a
node k on the semi-directed path π from i to C such that, on π, there is an
arrowhead at k on the opposite direction of π. In addition, suppose that this
arrowhead has been removed by step 4. It then holds that k ∈ C ∪ ant(C).
By considering the closest of such nodes to i on π, i is an anterior of k, and
consequently C.
Before applying step 3 of Algorithm 2: Consider the closest arrow
to i on π that is generated by step 3. The result then follows from Lemma
4.
Before applying step 2 of Algorithm 2: The only possible arrow on π
(say from k to l) can be generated by step 2 (case 4 of Table 2). This implies
that k ∈ ant(l). By an inductive argument, this implies the result.
Proof of Proposition 3. Graphs generated by Algorithm 2 have the
three desired types of edges. We prove that there is no semi-directed cycle
with an arrow in a generated chain mixed graph from G. Suppose, for contradiction, that a generated graph does contain a semi-directed cycle π with
an arrow. Since π does not exist in G, at least one arrow, say from j to i, or
a line, say between k and l has been generated by Algorithm 2. If ij or lk has
been generated by steps 3 or 4 of the algorithm then by Lemma 4, j, k, l ∈ S
in G. This implies that there should be no arrow on π, a contradiction.
Thus, the only option that is left is that ij has been generated by step 2,
case 4 of Table 2. In this case j ∈ ant(i) in G with an arrow existing on the
directed path from j to i. By considering all arrows generated by this step
of the algorithm on π, we conclude that there is a semi-directed cycle with
an arrow in G, a contradiction.

34

K. SADEGHI

Proof of Lemma 6. We first prove that there is an ij edge in
αCM G (G; ∅, C) if and only if there is a walk as described in the
lemma in G:
(⇒) Suppose that in αCM G (G; ∅, C) there is an edge between i and j.
We will follow how this edge might have been generated by the steps of
Algorithm 2.
In the graph generated before applying step 4: It is clear that there
is an ij edge.
In the graph generated before applying step 3: Now, by Lemma
3, there exists an endpoint-identical walk π between i and j to the edge ij
whose inner sections are all collider and in S, and whose endpoint sections
contain a single node. Notice that this means that all edges on π are either
lines or arcs except possibly those containing i and j.
In G: By replacing arcs or arrows on π by endpoint-identical paths (provided in cases 4 and 5 of Table 2), only collider sections on π become larger.
The newly added nodes to the sections will obviously be in S since they
are anteriors of the rest of the section, which is in S – the only exception
is when there is an arrowhead at i (or j) and the section containing i gets
larger. In this case, i ∈ sp(k), for k ∈ S.
(⇐) Suppose that in G, there exists a walk π as described in the lemma.
The edges of π are all arcs and lines except possibly those including i and
j. We will go through how this walk changes by the steps of Algorithm 2.
In the graph generated after applying step 2: The endpoint sections
turn into single nodes, and other sections may get shortened, but since the
generated edges are endpoint-identical to the generating paths (provided in
cases 4 and 5 of Table 2), inner sections of the resulting walk are still collider.
Lemma 5 implies that the inner sections stay in S.
In αCM G (G; ∅, C): The generated walk in the previous step satisfies the
conditions of Lemma 3. Hence, there is an ij edge generated by step 3, which
keeps existing after step 4.
We now prove the second claim in the lemma: Since all generated
edges by steps 2 and 3 of the algorithm (all cases of Table 2) are endpoint
identical to their generating paths, the generated edge after step 3 and the
walk in G are endpoint-identical. Step 4 changes endpoint-identicality only
when it removes the arrowhead at i, which always and only happens when
i ∈ ant(C).
Proof of Theorem 3. Notice that i, j ∈
/ C ∪ C1 . We first prove that
there is an ij edge in αCM G (αCM G (G; ∅, C); ∅, C1 ) if and only if there
is an ij edge in αCM G (G; ∅, C ∪ C1 ):

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

35

By Lemma 6, there is an edge between i and j in αCM G (αCM G (G; ∅, C); ∅, C1 )
if and only if there is a walk π as described in the lemma between i and j
in αCM G (G; ∅, C) with inner sections in S1 = C1 ∪ ant(C1 ).
Notice that by Lemma 4, lines on the inner sections of π exist in G. In
addition, there at most two arrows might exist on π, which are from the
endpoints i and j. Now again by Lemma 6, instead of a kl arc on π, in G,
there is an endpoint-identical walk π ′ as described in the lemma between k
and l with inner sections in S = C∪ant(C). By replacing kl by π ′ , one obtains
a walk with the same properties as in Lemma 6 for S ∪ S1 . Inductively, we
replace all such kl arcs. We also replace a possible arrow (say from i to h)
by a walk with properties as described in Lemma 6, where there might be
an arrowhead at i with i ∈ ant(C). By all these replacements, one obtains a
walk π1 in G. Since conditions of Lemma 6 are both necessary and sufficient,
it holds that there is the walk π in αCM G (G; ∅, C) if and only if there is the
walk π1 in G.
Walk π1 satisfies the properties in Lemma 6 for S ∪S1 . Again by Lemma 6,
there is the walk π1 in G if and only if there is an ij edge in αCM G (G; ∅, C ∪
C1 ).
We now prove that the ij edge is the same in both graphs:
We only need to show that there is an arrowhead at i on the ij edge in
αCM G (αCM G (G; ∅, C); ∅, C1 ) if and only if there is an arrowhead at i on the
ij edge in αCM G (G; ∅, C ∪ C1 ). This follows from the second part of Lemma
6 and the fact that if i ∈ ant(C)∪ant(C1 ) in G then there is no arrowhead at
the ij edge in αCM G (αCM G (G; ∅, C); ∅, C1 ) or αCM G (G; ∅, C ∪ C1 ). Below
we prove the latter claim:
The result for αCM G (G; ∅, C ∪ C1 ) is again clear by Lemma 6. We now
condider αCM G (αCM G (G; ∅, C); ∅, C1 ). If i ∈ ant(C) then there is no arrowhead at i on π in αCM G (G; ∅, C). If i ∈ ant(C1 ) \ ant(C) then consider
the semi-directed path from i to a member of C1 in G. This path remains
intact in αCM G (G; ∅, C) since i ∈
/ ant(C). Hence, the arrowhead at i on the
ij edge will be removed in αCM G (αCM G (G; ∅, C); ∅, C1 ).
Proof of Theorem 4. We prove that A ⊥ c B | C ∪ C1 in G if and only
if A ⊥ c B | C1 in αCM G (G; ∅, C).
(⇐) Suppose that there is a c-connecting walk π given C ∪ C1 between
i and j in G. We apply the steps of Algorithm 2 to this walk. Consider all
maximal subwalks of π whose inner sections are all collider and in C, and
endpoints are single nodes and not in C. Notice that all nodes of π that are

36

K. SADEGHI

in C are included in these subwalks since no non-collider section on π has a
node in C. Denote such a subwalk by ̟.
After applying step 2: First consider the case where the endpoints of ̟
are the same node l. Sections on ̟ are collider, and hence, the edge between
l and an endpoint of ̟ (call it c) has an arrowhead at c. We can easily obtain
a shorter c-connecting walk by removing ̟ from π if, by doing so, l is on a
collider section or on a non-collider section with no node in C ∪C1 . First, this
implies that the cl edge is an arc. In addition, if that is not the case then there
···
◦ ≺ k or l≺ ≻c≺ ≻l
···
◦ ≺ ≻ k,
exists l≺ ≻c≺ ≻l
where l 6∈ C ∪ C1 but an inner node of the section containing l is in C1 .
(Notice that if l is i or j then one can easily remove c from the walk.) By
step 2, there is a generated lk edge. We replace all these walks with the
generated edge and call the resulting walk π1 . Because the generated edges
are endpoint-identical to the subwalks, π1 is c-connecting.
After applying step 3: By Lemma 1, there is an alternative c-connecting
walk π1′ to π1 , where all sections are paths and inner nodes of collider sections
are in C ∪C1 ∪(ant(C)∪ant(C1 )). Consider all maximal subwalks of π1′ whose
inner sections are all collider and in C ∪ ant(C), and endpoints are single
nodes and not in C. Because of the previous step, the endpoints of such
subwalks are distinct nodes. Now, by Lemma 3, instead of these subwalks,
there are endpoint-identical edges. By replacing all the subwalks with these
edges, we obtain a walk π2 . Walk π2 is c-connecting given C1 since generated
edges on π2 are endpoint-identical to the subpaths on π1′ that have been
replaced.
After applying step 4: By this step, no collider sections turn into a
non-collider one on π2 since if an arrowhead on a node k is removed then
k ∈ ant(C) in G and so are all inner nodes of the section that contains
k. Hence, k cannot be on π2 by how π2 is generated. Therefore, π2 is a
c-connecting walk given C1 in αCM G (G; ∅, C).
(⇒) Suppose that there is a c-connecting walk π given C1 between i and
j in αCM G (G; ∅, C). In G, we obtain a walk π ′ by replacing every edge on
π with the corresponding walks described in Lemma 6. All these generated
walks by edges of π are c-connecting given C ∪ C1 themselves. Hence, if their
endpoints are open then π ′ would be c-connecting given C ∪ C1 .
If a generated subwalk on π ′ is endpoint-identical to the generating edge
on π with endpoint sections containing a single node then it is open. Hence,
we need to consider two cases where this does not happen for a generated
subwalk:
1) When the endpoint sections of the generated walks contain more than
a node, we know that there is an arrowhead at the section, and the endpoint

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

37

k is a spouse of s ∈ S. It is possible that the endpoint section ρ is not open
on π ′ (but the corresponding edge is open on π) if it is a non-collider with
a node in C. In this case add hk, s, ki (i.e., repeating the ks edge twice)
instead of k to π ′ . This makes ρ collider and also adds a collider section s
(containing a single node) and one non-collider section containing k, which
are all open.
2) We know that the generated walks on π ′ and the generating edges on
π are endpoint-identical except when there is an arrowhead at the endpoint
section ρ′ containing l and there is a semi-directed path ̟ from l to c ∈ C
in G. In this case, add h̟, ̟r i instead of l to π ′ (i.e. go from l to c and
come back to l on ̟). By this method, we split the collider ρ′ at l into two
subpaths, both of which are non-colliders, and obtain other open non-collider
sections along ̟ and a collider section c.
Proof of Proposition 4. The generated graphs obviously contain only
lines and arrows, thus it is enough to prove that they do not contain semidirected cycles with an arrow. Suppose, for contradiction, that a generated
graph does contain a semi-directed cycle π with an arrow. If a line ij on π
has been generated by step 4 then i, j ∈ S in G and, therefore, all nodes on
π are in S . This implies that there is no arrow on π, a contradiction. If a
line kl has been generated by step 3 then it is easy to see that both k, l ∈ S,
and again there is no arrow on π, a contradiction. Therefore, all lines on π
exist in the original graph, and no arrows are generated by the algorithm.
Hence, π exists in the original graph, a contradiction.
Proof of Lemma 7. We show that for any choice of C, i ⊥ j | C dos not
hold: Suppose that there is an arrow from an inner node k to j. If any of
the inner nodes is in C then i and j are dependent given C. If no inner
node is in C then the subwalk between i and k in addition to the kj arrow
constitutes a connecting walk given C.
Proof of Lemma 8. We prove the first claim:
(⇒) Suppose that in αCM G (αCM G (G; ∅, C); M, ∅) there is an edge between i and j.
In the graph generated before applying step 2 of Algorithm 1 to
αCM G (G; ∅, C): By lemma 2, there exists a walk π between i and j whose
inner sections are all non-collider and inner nodes are all in M .
In αCM G (G; ∅, C): By Lemma 13, there is a walk π0 between i and j with
the same non-collider sections. In addition, every node on π0 on section ρ
that is not in M is on a subsection with an endpoint that is the endpoint of

38

K. SADEGHI

ρ as well with an arrowhead pointing to it from the other adjacent node on
π0 . The other endpoint h is in M and a child of a member of M .
In G: For every edge kl on π0 , by Lemma 6, there exists a walk π ′ between
k and l whose inner sections are all collider and in C ∪ ant(C). We denote
the walk in this graph that consists of all such adjacent π ′ of π0 by π1 . Even
if the endpoint sections of π ′ are not single elements or π ′ is not endpointidentical to the kl edge, all the existing non-collider sections remain noncollider (although some sections might become larger). It is then observed
that all non-collider sections on π1 have all inner nodes outside C, and all
collider sections have inner nodes in C ∪ ant(C). In addition, every node on
π1 on section ρ′ that is not in M is on a subsection with an endpoint that is
the endpoint of ρ′ as well with an arrowhead pointing to it from the other
adjacent node on π1 . The other endpoint h is in M and either a child of a
member of M or a spouse of a member of C ∪ ant(C).
(⇐) Suppose that there is a walk between i and j in G with the two
mentioned properties. In place of this walk, we have the following walks in
the following graphs:
After applying step 1 of Algorithm 1 to G: By this step it can bee
seen that all subwalks containing non-collider sections outside M with an
endpoint that is a child of M get closed, and, therefore, we obtain a walk
on which (i) all nodes on collider sections are in C ∪ ant(C); (ii) (a) all
nodes on non-collider sections are in M or (b) on the non-collider section
one endpoint is in M and a spouse of a node in C ∪ ant(C), and the other
endpoint has an arrowhead at it from the adjacent node on the walk.
In αCM G (G; M, ∅): By Lemma 2, we obtain a walk on which all sections
are collider and in C ∪ ant(C) ∪ ant(j). Notice that the spouses of the endpoints of non-collider sections in the previous walk, which are in C ∪ ant(C),
appear on the generated walk.
In αCM G (G; M, C): By Lemma 6, we obtain an edge.
We now prove the second claim: We go through the corresponding
walks in the intermediate graph, provided above. By lemma 6, the ij edge
in αCM G (G; M, C) and the corresponding walk in αCM G (G; M, ∅) remain
endpoint-identical except when there is an arrowhead at the endpoint section
containing, say, i, and i ∈ ant(C) in αCM G (G; M, ∅). This walk, by Lemma
2, is endpoint-identical to the corresponding walk in the graph generated
after applying step 1 of Algorithm 1 to G. Since the anterior set does not
change at this step and the next step in G, and since step 1 of Algorithm 1
generates endpoint-identical edges, the result follows for the corresponding
walk in G.

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

39

Lemma 14. For a chain mixed graph G and M and C subsets of its node
set, if i ∈ ant(j) in αCM G (αCM G (G; ∅, C); M, ∅) then i ∈ ant(C ∪ {j}) in
G.
Proof. The proof follows from Lemma 8 by the following observations:
A line between k and l or an arrow from k to l on the semi-directed walk
from i to j in αCM G (αCM G (G; ∅, C); M, ∅) is not endpoint-identical to the
corresponding walk π in G if and only if k ∈ ant(C) in G. If they are
endpoint-identical then start from k and move towards l on π. At each step
we either reach a collider section and conclude that k ∈ ant(C), or we finally
reach l and conclude that k ∈ ant(l). By an inductive argument on the nodes
of π, we obtain the result.
Proof of Proposition 6. We first prove that there is an ij edge
in αCM G (αCM G (G; M, ∅); ∅, C) if and only if there is an ij edge in
αCM G (αCM G (G; ∅, C); M, ∅): We go through Algorithms 1 and 2 to follow
the types of walks corresponding to the ij edge in any of these graphs in
each step of the algorithms.
(⇒) Suppose that in αCM G (αCM G (G; M, ∅); ∅, C) there is an edge between i and j.
In αCM G (G; M, ∅): By Lemma 6, there is a walk π between i an j with
the properties described in the lemma.
In the graph generated before applying step 2 of Algorithms 1
to G: For every edge kl on π, by Lemma 2, there exists an endpoint-identical
walk π ′ between k and l whose inner sections are all non-collider and inner
nodes are all in M . We denote the walk that consists of all such adjacent
π ′ by π0 . It is easy to observe that all collider sections are in C ∪ ant(C).
In addition, either the endpoint sections of π0 still satisfy the conditions of
Lemma 6, or the endpoints that are not single elements become children of
members of M .
In G: By Lemma 13, there exists another walk π1 , on which, all collider
sections are in C ∪ ant(C). In addition, collider and non-collider sections
remain intact. In addition, it can be seen that on π1 , the conditions for
endpoint sections described in the previous paragraph still hold.
In αCM G (αCM G (G; ∅, C); M, ∅): The walk described in the previous
paragraph in G satisfies the conditions of Lemma 8. Hence, by this lemma,
we obtain the result.
(⇐) Suppose that in αCM G (αCM G (G; ∅, C); M, ∅) there is an edge between i and j. By Lemma 8, there is a walk π1 as described in the lemma
in G. We now continue to check how this walk alters along the steps of the
relevant algorithms:

40

K. SADEGHI

In the graph generated after applying step 1 of Algorithm 1
to G: All maximal subsections of non-collider sections whose nodes are
outside M , but an endpoint l is in M and a child of M can be replaced
by an endpoint-identical edge. By all such replacements, we obtain a walk
π2 , which contains collider sections in C ∪ ant(C) and non-collider sections
outside C. In addition, every node on π2 on section ρ that is not in M is
on a subsection with an endpoint that is the endpoint of ρ as well with an
arrowhead pointing to it from the other adjacent node on π2 . The other
endpoint h is in M and a spouse of a member of C ∪ ant(C).
In αCM G (G; M, ∅): First consider a non-collider trislide hr, ρ′ , qi where
ρ′ has members outside M . In addition, say r is the endpoint of ρ′ with an
arrowhead pointing to it from the other adjacent node on π2 . Consider the
node h as defined in the above paragraph, which is a spouse of s ∈ C∪ant(C).
Denote the adjacent node to h closer to r by t and the adjacent node to h
closer to q by v. By this step, an edge between t and v as well as ts and sv
arcs are generated.
In addition, by using Lemma 2, we replace the maximal subwalks of π2
that contain only non-collider sections and in which all nodes are in M , but
endpoints are outside M , by the generated endpoint-identical edges. By all
these replacements, we obtain a walk π3 that contains collider sections with
nodes in C ∪ ant(C) and non-collider sections outside C. In particular, we
obtain an sq arc as well as an arrow from t to q.
In αCM G (αCM G (G; M, ∅); ∅, C): By Lemma 6, instead of all subwalks
of π3 that contain inner collider sections, there exists an edge. In addition,
for non-collider sections, the collider tripath ht, s, qi (described in the above
paragraph) generates a tq arc. Because of the arrow from t to q and the
subwalk of the trislide between r and t, and by Lemma 7, we conclude that
the graph is not maximal except when there is an endpoint-identical edge
between r and q. Therefore, by an inductive argument, there is an edge
between the endpoints of π3 .
We now prove that the ij edge is of the same type in both
graphs: For every graph generated by a step of the algorithm, we discussed
a walk between i and j in both directions of the proof above. We focus on
the arrowhead pointing to i on these walks:
By Lemma 6, there is no arrowhead pointing to i on the ij edge in
αCM G (αCM G (G; M, ∅); ∅, C) if and only if there is no arrowhead pointing
to i or there is an arrowhead at i and i ∈ ant(C) in αCM G (G; M, ∅).
By Lemma 2 and the fact that the anterior sets do not change at this
step, the statement above is equivalent to no arrowhead pointing to i or an

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

41

arrowhead pointing to i only when i ∈ ant(C) in the graph generated before
applying step 2 of Algorithms 1 to G.
The result then follows from Lemma 8 for the corresponding walk in
αCM G (αCM G (G; ∅, C); M, ∅).

Proof of Proposition 7. We first prove that every CG G is mapped
into H: By propositions 1, 3, and 6, we conclude that the generated graphs
are CMGs. By Proposition 2, we know that H = αCM G (G; M, ∅) is in H.
We need to prove that H is mapped into H by conditioning.
...
j≺ l
Suppose that there is a collider trislide π of form k≺ ≻i
in the generated graph αCM G (G; M, C). By Lemma 4, the lines on π exist in
H. By Lemma 6, instead of the lj arrow and the ki arc, there are walks π1
and π2 , respectively, as described in the lemma, in H. Consider the node r
adjacent to the endpoint section containing j on π1 , and the node h that is
the other endpoint of the endpoint section containing i on π2 . (Notice that
r may be j and h may be i.)
Since H is in H, there is an arc (or an arrow if possibly h = l) between r
and h. Now the walk containing the subwalk of π1 between l and r, the rh
arc, and the subsection on π2 between h and i satisfies the conditions of the
walk described in Lemma 6. Hence, by this lemma, there is an arrow from l
to i in αCM G (G; M, C).
If there is a collider trislide of form k≺ ≻i
...
j ≺ ≻l in the generated graph then by the same argument as that in the previous paragraph
(and considering the fact that k, l ∈
/ S), there are il and kj arcs in the
generated graph. In addition, this time the walk containing the subwalk of
π1 between j and r, the rh arc, and the subsection on π2 between h and i
satisfies the conditions of the walk described in Lemma 6. Hence, there is
an arc between j and i in αCM G (G; M, C).
We now prove that the function is surjective: by Proposition 2,
after marginalization, CGs are surjectively mapped onto H. Thus, by letting
C = ∅, Proposition 6, and the fact that αCM G (G; ∅, ∅) = G, CGs are
surjectively mapped onto H after marginalization and conditioning.
Proof of Proposition 8. By Propositions 1 and 3, we know that, after
step 2 of Algorithm 3, we obtain a CMG. Steps 3 and 4 do not generate a
semi-directed cycle with an arrow by generating an arrow from j to i: This
is because if, for contradiction, that is the case then in the previous iteration
of step 4, j ∈ ant(k) and k ∈ ant(i) which imply that j ∈ ant(i), and, in
the previous iteration of step 3, j ∈ ant(i). This is a contradiction since it

42

K. SADEGHI

means by induction that the semi-directed cycle with an arrow exists in the
generated graph after applying step 2.
Step 5 obviously removes all arcs with one endpoint that is an anterior
of the other endpoint. This step also does not generate semi-directed cycles
with an arrow by replacing an arc ij by an arrow from j to i or an ij
line: this is because if, for contradiction, that is the case then j ∈ ant(i) in
the generated graph after applying step 4, which is a contradiction since it
means by induction that the semi-directed cycle with an arrow exists in this
graph.
Proof of Lemma 9. We show that at every step of Algorithm 3, a semidirected path from i to j remain semi-directed and vice versa. For step 3 of
the algorithm, the result is clear since the generating path of an arrow from
h to l is semi-directed from h to l. For step 4, this is correct as well since
there is a node k on the generating path such that k ∈ ant(l), and, on the
generating path, h ∈ ant(k). This is also true for step 5 since if an arc turns
into an arrow from h to l then h is already an anterior of l.
Proof of Lemma 10. First, we prove the first claim:
(⇒) Suppose that there is an ij edge in αCM G.AnG (H). We see how this
edge changes by steps of Algorithm 3:
Before applying step 5: There is still an edge between i and j.
Before applying step 4: Instead of an arrow or an arc ij at some iteration of this step of the algorithm, there may be a path between i and j,
consisting of one inner collider section and with inner nodes, say, in ant(i).
By any other iteration, the arrow or the arc kl might be replaced by another
such path. By this replacement, we obtain a path (by discarding the intersection of lines) with all inner sections to be collider. Notice that by Lemma
9, at no iteration the anterior set of the endpoints changes. In addition, regardless of whether inner nodes of the path between k and l are anteriors
of k or l, all inner nodes are anteriors of i. By an inductive argument, we
finally obtain a subprimitive inducing path from j to i.
In H: By replacements of the arrow and arcs in step 3 of the algorithm,
only sections become larger and inner nodes remain anteriors of an endpoint.
If an endpoint of the arrow or arc is i or j then an endpoint section of the
generated walk is not a single element and there is a node h such that
h ∈ ant(i) ∩ sp(i) or h ∈ ant(j) ∩ sp(j) respectively; otherwise the endpoint
sections are single elements. In the former case, we add hi, h, ii to the walk;
and similarly for j.
(⇐) Suppose that there is a subprimitive inducing walk π from j to i in
H. Consider the trislide ρ containing i. First suppose that the endpoints of

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

43

ρ are a single element i (i.e. ρ = hi, l, ii, where l ∈ ant(i)). Consider the path
hk, ρ′ i, where i is an endpoint of the section ρ′ adjacent to ρ and there is an
arc between k and the other endpoint of ρ′ (or possibly an arrow if k = j).
By step 3 of Algorithm 3, we can replace this path by an arc (or an arrow).
By step 4 of the algorithm we obtain an arc instead of this trislide. By
considering the trislide containing i after the replacement, we have that inner
nodes of the trislide are in ant(i). By repeating this argument we obtain an
ij edge.
We now prove the second claim: If j ∈ ant(i) in H then, by step 5 of
the algorithm, there is no arrowhead at j on the ij edge in αCM G.AnG (H).
If j 6∈ ant(i) in H then, by Lemma 9, j 6∈ ant(i) after applying step 4 of the
algorithm. Hence, step 5 is not applicable. The result then follows from the
fact that steps 3 and 4 generate endpoint-identical edges.
Proof of Lemma 11. By Lemma 10, it is enough to prove that (1) there
is a subprimitive inducing walk from i to j in αCM G (αCM G.AnG (H); M, C)
with single-element endpoint sections if and only if there is an endpointidentical walk of the same type from i to j in αCM G (H; M, C); (2) j ∈ ant(i)
in αCM G (αCM G.AnG (H); M, C) if and only if j ∈ ant(i) in αCM G (H; M, C).
Proving (1): By Lemma 8, every edge on the subprimitive inducing walk
π from i to j in αCM G (H; M, C) can be replaced by the described walk in the
lemma. Denote the new walk by π ′ in H. Notice that if a replaced subwalk
is not endpoint-identical to the original edge then an endpoint k of the edge
should be in ant(C) in H, which means that k is on a non-collider inner
section on π (or is an endpoint with no arrowheads pointing to it), but this
is impossible. Therefore, all such edge-replacements are endpoint identical.
In addition, by Lemma 14, if a node h is in ant(j) in αCM G (H; M, C) then
h ∈ ant(C ∪ {j}) in H.
These imply that there is a subprimitive inducing walk from i to j with
the mentioned properties in αCM G (H; M, C) if and only if in H there is
a walk between i and j on which (i) all nodes on collider sections are in
C ∪ ant(C) ∪ {j}; (ii) (a) all nodes on non-collider sections are in M , or (b)
on non-collider sections, one endpoint is in M and also either a child of a
node in M or a spouse of a node in C ∪ ant(C), and the other endpoint
has an arrowhead at it from the adjacent node on the walk. In addition, the
two walks are endpoint-identical except when there is an arrowhead at the
endpoint section containing i (or j), and i ∈ ant(C) (or j ∈ ant(C)) in H.
Now by using Lemma 9, we have that i ∈ ant(C) in H if and only if
i ∈ ant(C) in αCM G.AnG (H). Therefore, since the same statements as above
hold also for αCM G (αCM G.AnG (H); M, C) and αCM G.AnG (H), and in order

44

K. SADEGHI

to complete the proof, we need to show that there is a walk between i and j
in H with the two mentioned properties if and only if there is an endpointidentical walk π0 of the same type between i and j in αCM G.AnG (H):
To prove this, it is enough to show that by placing the walks described
in Lemma 10 in place of the edges of π0 , the form of π0 does not change:
Without loss of generality, suppose that π0 is a shortest walk of the described
form, and an rs edge on π0 has been replaced by a subprimitive inducing
walk ̟ from r to s. The newly added sections are all collider. Because of
transitivity of anteriors, and since the inner nodes of ̟ are anteriors of
s, they stay is ant(C ∪ {j}). It is now enough to only check the sections
containing r and s on π0 . Firstly, it is easy to see by Lemma 10 that the
type of these sections do not change regardless of whether they are single
elements on ̟.
Secondly, if the rs edge and ̟ are endpoint-identical then theses sections
remain of the same type. This completes the proof by using Lemma 9.
If these are not endpoint-identical then s ∈ ant(r). A problem only may
arise when the section containing s is a non-collider in αCM G.AnG (H) but
a collider in H. If, for contradiction, this is the case then there is an arrow
to s from the other adjacent node q to s on π0 . In addition, since all inner
nodes of ̟ are anteriors of s, they are anteriors of r, and hence in H, h̟, qi
is a subprimitive inducing walk from q to r, and hence π0 is not a shortest
walk, a contradiction. This completes the proof of this section.
Proving (2): Consider a semi-directed walk π in αCM G (αCM G.AnG (H); M, C)
from j to i. Since every edge is a subprimitive inducing walk, lines on π remain the same, and instead of an arrow from k to l on π we may have a
subprimitive inducing walk from k to l. It is easy to observe that k ∈ ant(l),
and by an inductive argument, we obtain the result.
The proof of other direction uses exactly the same argument (although,
in fact, edges remain edges in this case).
Proof of Proposition 9. First we prove that every CG G is
mapped into K: By Proposition 8, we know that αAnG maps CGs into
AN G. By Proposition 7, we know that after applying steps 1 and 2 of Algorithm 3, a CG G is mapped into H, defined in Proposition 2. We need to
prove that after applying steps 3, 4, and 5 of Algorithm 3, a CMG H ∈ H
is mapped into K.
Suppose that there is a trislide π = k≺ ≻i
...
j ≺ l in
the generated graph: By Lemma 10, there is a subprimitive inducing walk
from l to j in H. Denote the node on this walk adjacent to j by q. The jq
edge is an arc unless l = q, in which case it is an arrow from q to j. Since

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

45

lines are not generated by Algorithm 3, and since H ∈ H, there is an iq arc
or an arrow from l to i.
In the generated graph, j ∈ ant(i), and there is a subprimitive inducing
walk from l to i that goes through the subprimitive inducing walk from l to
j, the section from j to i, the iq edge, the jq edge, and again the section
between j and i. Hence, again by Lemma 10, there is an edge between l
and i. This edge can only be an arrow from l to i since otherwise there is
a semi-directed cycle or an arc with one endpoint that is an anterior of the
other endpoint in the generated anterial graph.
...
j ≺ ≻l in
Suppose that there is a trislide π = k≺ ≻i
the generated graph: It holds that l ∈
/ ant(i) since otherwise l ∈ ant(j),
which is impossible due to the existence of an arrowhead at l. This fact
together with the same argument as that in the previous paragraphs implies
that there is an il arc in the generated graph. By the symmetry on the
trislide we also conclude that there is a jk arc in the generated graph. In
addition, by what we proved in the previous paragraphs, there is a tripath
...
j ≺ ≻q in H, which implies that there is an ij arc in H.
q ′ ≺ ≻i
This arc turns into a line by step 5 since i and j are anteriors of one another.
We now prove that the function is surjective: Consider an arbitrary graph K ∈ K. We prove that there exists an H ∈ H such that
αCM G.AnG (H) = K, i.e. by applying steps 3, 4, and 5 of Algorithm 3 to
H, we obtain K. This completes the proof since αCM G is surjective onto H,
and αAnG = αCM G.AnG ◦ αCM G .
If K does not contain a trislide of form π = k≺ ≻i
...
j ≺ ≻l
then K ∈ H, and we simply let H = K. Since αAnG does not change
anterial graphs, we are done.
If K does contain a trislide π of the mentioned form then there is the ij
line in K. Now let H be K, but with an arc between i and j instead of the
existing line. We have that H ∈ H. Denote also the section between i and j
by ρ.
By Lemma 10, the ij arc turns into a line and clearly no other edge
changes its type in αCM G.AnG (H). Hence, it is enough to show that no
other edge is generated. If the ij arc is part of any subprimitive inducing
walk except when i or j is an endpoint then it can be replaced by ρ to obtain
another primitive inducing walk. If i or j is an endpoint then, by how H is
constructed, the possible arrows or lines that can be generated already exist
in H. This completes the proof.
Proof of Theorem 8. By Theorem 6, it is enough to prove that A ⊥ c B | C1
in αAnG (G; M, C) if and only if A ⊥ c B | C1 in αCM G (G; M, C).

46

K. SADEGHI

Since Steps 1 and 2 of Algorithm 3 generate αCM G (G; M, C), we need to
prove that there is a c-connecting walk in a chain mixed graph H if and
only if there is a c-connecting walk after applying steps 3, 4, and 5 of the
algorithm to H.
(⇒) Suppose that there is a c-connecting walk π given C1 between i and
j in H. After applying steps 3 and 4, π is intact. If an arc kl is replaced by
an arrow from k to l or a kl line, in step 5 of the algorithm then we have
the two following cases:
1) If k is on a non-collider section on π by using the kl arrow or line
instead of arc, one obtains a c-connecting walk.
2) Suppose that k is an endpoint of a collider section ρ and there is
π1 = hh, ρ, li on π. By Lemma 1, one can assume that ρ is a path. By Lemma
9, k ∈ ant(l). If h 6= l then by step 4, there is an endpoint-identical hl edge
to π1 . One can now use the hl edge instead of π1 to obtain a c-connecting
walk. If h = l then ρ can be considered to be the single node k. Now if h is
on a non-collider section then we can easily skip k to obtain a c-connecting
path. If h is an endpoint of a collider section ρ′ then from π2 = hq, ρ′ , ki
and by using step 3 of the algorithm, we obtain an endpoint-identical qh
edge, which can be replaced by π2 to obtain a c-connecting path. This, by
an inductive argument, implies the result.
(⇐) Suppose that there is a c-connecting walk π given C1 between i and
j in αCM G.AnG (H), which is graph H after applying steps 3, 4, and 5 of
Algorithm 3.
For every edge on π, by Lemma 10, there exists a subprimitive inducing
walk in H between the same endpoints. We replace all the edges on π by
these walks and call the generated walk π ′ . Notice that it can be shown that
regardless of the choice of C, a subprimitive inducing walk is c-connecting
itself. Hence, if the replaced subwalk of π ′ by an edge is endpoint-identical
to the original edge then it does not affect the c-connectivity of π ′ . We,
therefore, need to check the case where the generated walk is not endpointidentical to the edge.
Suppose that this is the case for the edge ij in αCM G.AnG (H) replaced
by a subprimitive inducing walk ̟ from j to i. By the lemma, we have that
either j ∈ ant(i) or i ∈ ant(j) in H, in which cases there is no arrowhead at
j or i on the ij edge respectively.
Assume that j ∈ ant(i). We need to consider the case where ij is an
arrow from j to i, and j is not in C, but there is an arrowhead at j on ̟.
Denote the semi-directed walk from j to i by τ . If no node on τ is in C then
we replace ̟ by τ to obtain a c-connecting walk. Otherwise, consider the
closest node k ∈ C on τ to j. The walk consisting of the subwalk of τ from j

MARGINALIZATION AND CONDITIONING FOR LWF CHAIN GRAPHS

47

to k, the same subwalk in the reverse direction (from k to j), and ̟ is now
c-connecting since j is on non-collider sections, except when j and k are on
the same subsection of τ (which is still fine).
The case where i ∈ ant(j) follows the exact same argument.
References.
[1] Andersson, S. A., Madigan, D. and Perlman., M. D. (2001). Alternative Markov
Properties for Chain Graphs. Scand. J. Stat. 28 33-85.
[2] Cox, D. R. and Wermuth, N. (1993). Linear dependencies represented by chain
graphs (with discussion). Stat. Sci. 8 204–218; 247–277.
[3] Drton, M. (2009). Discrete chain graph models. Bernoulli 15 736–753.
[4] Evans, R. J. and Richardson, T. S. (2014). Markovian acyclic directed mixed
graphs for discrete data. Ann. Statist. 42 1452-1482.
[5] Frydenberg, M. (1990). The chain graph Markov property. Scand. J. Stat. 17 333–
353.
[6] Geiger, D., Heckerman, D., King, H. and Meek, C. (2001). Stratified exponential
families: Graphical models and model selection. Ann. Statist. 29 505-529.
[7] Kiiveri, H., Speed, T. P. and Carlin, J. B. (1984). Recursive causal models. J.
Aust. Math. Soc., Ser. A 36 30–52.
[8] Koster, J. T. A. (2002). Marginalizing and conditioning in graphical models.
Bernoulli 8 817–840.
[9] Lauritzen, S. L. (1996). Graphical Models. Clarendon Press, Oxford, United Kingdom.
[10] Lauritzen, S. L. and Spiegelhalter, D. J. (1988). Local computations with probabilities on graphical structures and their application to expert systems. J. Roy. Statis.
Society B 50 157-224.
[11] Lauritzen, S. L. and Wermuth, N. (1989). Graphical models for association between variables, some of which are qualitative and some quantitative. Ann. Statist.
17 31–57.
[12] Marchetti, G. M. and Lupparelli, M. (2011). Chain graph models of multivariate
regression type for categorical data. Bernoulli 17 827-844.
[13] Peña, J. M. (2009). Faithfulness in chain graphs: The discrete case. Int. J. Approx.
Reason. 50 1306 - 1313.
[14] Peña, J. M. (2011). Faithfulness in Chain Graphs: The Gaussian Case. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics
(AISTATS 2011) 15 588-599. JMLR.org.
[15] Peña, J. M. (2014). Marginal AMP chain graphs. Int. J. Approx. Reason. 55 11851206.
[16] Pearl, J. (2009). Causality: Models, Reasoning and Inference, 2nd ed. Cambridge
University Press, New York, NY, USA.
[17] Richardson, T. (2003). Markov Properties for Acyclic Directed Mixed Graphs.
Scand. J. Stat. 30 145–157.
[18] Richardson, T. S. and Spirtes, P. (2002). Ancestral graph Markov models. Ann.
Statist. 30 962–1030.
[19] Sadeghi, K. (2013). Stable mixed graphs. Bernoulli 19 2330-2358.
[20] Sadeghi, K. (2015). Supplement to “Marginalization and conditioning for LWF chain
graphs”.
[21] Shpitser, I. and Pearl, J. (2008). Dormant independence. In Proceedings of the
twenty-third AAAI Conference on Artificial Inteligence 1081-1087. AAAI Press.

48

K. SADEGHI

[22] Studeny, M. (1998). Bayesian Networks from the Point of View of Chain Graphs.
In UAI 496-503. Morgan Kaufmann, San Francisco, CA.
[23] Studeny, M. (2005). Probabilistic Conditional Independence Structures. SpringerVerlag, London, United Kingdom.
[24] Studeny, M. and Bouckaert, R. R. (1998). On chain graph models for description
of conditional independence structures. Ann. Statist. 26 1434–1495.
[25] Verma, T. and Pearl, J. (1990). Equivalence and synthesis of causal models. In
Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence (UAI-90)
220–227.
[26] Wermuth, N. (2011). Probability distributions with summary graph structure.
Bernoulli 17 845–879.
[27] Wermuth, N. and Sadeghi, K. (2012). Sequences of regressions and their independences. TEST 21 215-252 and 274-279.
[28] Wermuth, N., Wiedenbeck, M. and Cox, D. R. (2006). Partial inversion for linear
systems and partial closure of independence graphs. BIT 46 883–901.
Statistical Laboratory
Centre for Mathematical Studies
Wilberforce Road
Cambridge, CB3 0WB
United Kingdom.
E-mail: k.sadeghi@statslab.cam.ac.uk

