# Conditions and Assumptions for Constraint-based Causal Structure Learning

Kayvan Sadeghi<EMAIL_ADDRESS>
Department of Statistical Science
University College London
London, United Kingdom Terry Soo<EMAIL_ADDRESS>
Department of Statistical Science
University College London
London, United Kingdom

###### Abstract

We formalize constraint-based structure learning of the “true” causal graph
from observed data when unobserved variables are also existent. We provide
conditions for a “natural” family of constraint-based structure-learning
algorithms that output graphs that are Markov equivalent to the causal graph.
Under the faithfulness assumption, this natural family contains all exact
structure-learning algorithms. We also provide a set of assumptions, under
which any natural structure-learning algorithm outputs Markov equivalent
graphs to the causal graph. These assumptions can be thought of as a
relaxation of faithfulness, and most of them can be directly tested from (the
underlying distribution) of the data, particularly when one focuses on
structural causal models. We specialize the definitions and results for
structural causal models.

Keywords: ancestral graphs; causal discovery; constraint-based structure
learning; faithfulness; structural causal models

##  1 Introduction

Inferring causal relationships has always been one of the main objectives in
many fields of study, ranging from philosophy to science (Holland, 1986). In
the past decades, _causal models_ (Pearl, 2009) have been used to infer causal
relationships from observed data. Extensive research has been conducted on
defining, interpreting, and applying causal models, and these models have
become mainstream in statistics and computer science (Pearl, 1988; Spirtes et
al., 2000; Dawid, 2000; Hitchcock, 2018). Today, a very popular method for
inferring causal relationships is based on the use of statistical models over
graphs with nodes that are random variables representing the quantities of
interest. Edges indicate probabilistic dependence among these variables
conditional on some other variables in the graph, which with some additional
assumptions can be interpreted as causal relationships. These models are
called _graphical (Markov) models_ (Lauritzen, 1996).

_Structural causal models_ (SCMs), also known as _structural equation models_
, are one of the most used causal models (Spirtes et al., 2000; Pearl, 1988).
SCMs have been generally defined for directed acyclic graphs (DAGs) (i.e., a
Bayesian network), where an arrow implies a “direct” cause. However, for the
purpose of causal inference, it may not be possible to determine or measure
all common causes. For this reason, SCMs associated to DAG models with latent
variables (represented by ancestral graphs (Richardson and Spirtes, 2002)
without undirected edges) have been defined (Spirtes et al., 2000; Zhang,
2008).

A main goal of causal inference, based on graphical models, is causal
discovery; in this framework we are concerned with finding graphs, using only
observed data, that represent the causal structure, which is represented by an
unknown “true” causal graph. Algorithms for constructing or selecting such a
graph are known as _structural learning_ algorithms. There has been a surge in
defining different structural learning algorithms; they are generally
categorized as constraint-based (Spirtes et al., 2000), score-based
(Chickering, 2003) –which work on the factorization of density–, or hybrid
(Tsamardinos et al., 2006) –which is a combination of these.

We are concerned with _constraint-based_ structure-learning algorithms for the
general case of ancestral graphs without undirected edges. These algorithms
use conditional independence statements, which are theoretically testable from
observed data to find graphs that, at best, are Markov equivalent to the true
causal graph. A main sufficient condition for the algorithms to be _correct_
or _work_ , that is, to provide an output that is Markov equivalent to the
causal graph, is faithfulness (Zhang and Spirtes, 2008; Woodward, 1998; Steel,
2006; Colombo and Maathuis, 2014); this sufficient condition relates the
independencies induced by the distribution (of the SCM) and the separations
induced by the causal graph. However, faithfulness to the unknown causal
graph, or similar assumptions (Zhang and Spirtes, 2003), are generally not
testable. In addition, the (sufficient) assumption of faithfulness is in some
circumstances strong, and can be relaxed; see Section 5.

In this paper, we formalize the problem of constraint-based structure learning
from observed data. Most constraint-based structure-learning algorithms
contain two tasks which may be performed in parallel or separately: finding
the undirected edges of the graph, the skeleton; and directing the edges of
the skeleton. We show that under the assumption of faithfulness and using a
formalization of faithfulness, provided in Sadeghi (2017), if the output of
such algorithms works, then pair of conditions known as _ordered stability_
must be satisfied with respect to the output; see Section 2.3 and Remark 12.
Ordered stability is a condition that informs us how the edges of the graph
should be directed and we propose the class of _natural_ structure-learning
algorithms, which is one that should respect stability when directing the
edges; see Definition 6. We stress that in this paper, we do not provide
specific algorithms that could be implemented, but concentrate on providing
conditions that structure-learning algorithms should satisfy. More
importantly, we provide clear assumptions, many of which are directly testable
from the distribution, under which a natural structure-learning algorithm
generates the correct output.

We provide the theory for the general class of models under the assumption
that the distribution is Markovian to the true causal graph; see Theorem 25.
The assumptions are the following: the distribution satisfies ordered
stability and the converse of the pairwise Markov property with respect to the
true causal graph, and also the distribution satisfies what we call path-
stability.

We will make precise our assumptions later, and we note that they can be
thought of as a relaxation of faithfulness, and in particular, in the case of
DAGs our assumptions are logically implied by faithfulness; see Corollary 23.
We also specialize the definitions and results for SCMs; see Theorem 42, and,
in particular, provide testable sufficient conditions for the converse of the
pairwise Markov property to be satisfied. We hope that the framework provided
here will be a useful theoretical tool in defining appropriate SCMs and
concrete algorithms with strong theoretical backing.

The structure of the paper is as follows: In the next section, we provide
known definitions and results needed for the theory presented in this paper.
In Section 3, we formalize the settings of the problem. Section 4 deals with
the theory under the faithfulness assumption. In Section 5, we introduce the
structure learning theory without the faithfulness assumption. Section 6
specializes on causal structure learning for SCMs. We end the paper with a
summary and discussion in Section 7.

##  2 Preliminaries

In this section, we provide the basic definitions and concepts as well as the
known results needed for the paper.

###  2.1 Graph theoretical definitions and concepts

We usually refer to a graph as an ordered pair $G=(V,E)$, where $V$ is the
_node_ set and $E$ is the _edge_ set. When nodes $i$ and $j$ are the endpoints
of an edge, we call them _adjacent_ , and write $i\sim j$, and otherwise
$i\nsim j$. Graphs in this paper are _simple_ , that is, they have at most one
edge between a pair of nodes. We consider two types of edges: _arrows_
($i\mbox{$\hskip 0.50003pt\frac{\hskip 4.89998pt\hskip 4.89998pt}{\hskip
4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}j$) and _bidirected edges_
or _arcs_ ($i\mbox{$\hskip 0.59998pt\prec\\!\\!\\!\\!\\!\frac{\hskip
4.89998pt\hskip 4.89998pt}{\hskip 4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip
1.07639pt$}j$). We do not consider graphs that have simultaneous third type of
edge: _undirected edges_ or _lines_ ($i\mbox{$\,\frac{\hskip 4.89998pt\hskip
4.89998pt\;}{\hskip 4.89998pt\hskip 4.89998pt}$}j$). The completely undirected
graph, obtained from a graph $G$, is called the _skeleton_ of $G$, denoted by
$\mathrm{sk}(G)$; it is obtained by removing all arrowheads from the edges of
the graph $G$. We say that we _direct_ the edges of a skeleton by assigning
arrowheads at the edges, which results in a graph.

A _subgraph_ of a graph $G_{1}$ is graph $G_{2}$ such that $V(G_{2})\subseteq
V(G_{1})$ and $E(G_{2})\subseteq E(G_{1})$ and the assignment of endpoints to
edges in $G_{2}$ is the same as in $G_{1}$. An _induced subgraph_ by nodes
$A\subseteq V$ is a subgraph that contains all and only nodes in $A$ and all
edges between two nodes in $A$.

A _walk_ is a list $\langle v_{0},e_{1},v_{1},\dots,e_{k},v_{k}\rangle$ of
nodes and edges such that for $1\leq i\leq k$, the edge $e_{i}$ has endpoints
$v_{i-1}$ and $v_{i}$. A _path_ is a walk with no repeated node or edge. When
we define a path, we only write the nodes (and not the edges). A _cycle_ is a
walk with no repeated nodes or edges except for $v_{0}=v_{k}$.

We call the first and the last nodes _endpoints_ of the path and all other
nodes _inner nodes_. A path can also be seen as a certain type of connected
subgraph of $G$; a _subpath_ of a path $\pi$ is an induced connected subgraph
of $\pi$.

For an arrow $j\mbox{$\hskip 0.50003pt\frac{\hskip 4.89998pt\hskip
4.89998pt}{\hskip 4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}i$, we
say that the arrow is _from_ $j$ _to_ $i$. We also call $j$ a _parent_ of $i$,
$i$ a _child_ of $j$ and we use the notation $\mathrm{pa}(i)$ for the set of
all parents of $i$ in the graph. In the cases of $i\mbox{$\hskip
0.50003pt\frac{\hskip 4.89998pt\hskip 4.89998pt}{\hskip
4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}j$ or $i\mbox{$\hskip
0.59998pt\prec\\!\\!\\!\\!\\!\frac{\hskip 4.89998pt\hskip 4.89998pt}{\hskip
4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}j$ we say that there is an
arrowhead at $j$ or pointing to $j$. A path $\langle
i=i_{0},i_{1},\dots,i_{n}=j\rangle$ is _directed_ from $i$ to $j$ if all
$i_{k}i_{k+1}$ edges are arrows pointing from $i_{k}$ to $i_{k+1}$. If there
is a directed path from $j$ to $i$, then node $j$ is an _ancestor_ of $i$ and
$i$ is a _descendant_ of $j$. We denote the set of ancestors of $i$ by
$\mathrm{an}(i)$; unlike some authors, we do not assume that
$i\in\mathrm{an}(i)$.

A _tripath_ is a path with three nodes. Note that Sadeghi (2013) used the term
V-configuration for such a path. We follow Kiiveri et al. (1984) and most
texts by letting a _V-configuration_ be a tripath with non-adjacent endpoints.
The inner node $t$ in each of the three tripaths

$i\mbox{$\hskip 0.50003pt\frac{\hskip 4.89998pt\hskip 4.89998pt}{\hskip
4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}\,t\mbox{$\hskip
0.50003pt\prec\\!\\!\\!\\!\\!\frac{\hskip 4.89998pt\hskip 4.89998pt}{\hskip
4.89998pt}$}\,j,\ i\mbox{$\hskip 0.59998pt\prec\\!\\!\\!\\!\\!\frac{\hskip
4.89998pt\hskip 4.89998pt}{\hskip 4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip
1.07639pt$}\,t\mbox{$\hskip 0.50003pt\prec\\!\\!\\!\\!\\!\frac{\hskip
4.89998pt\hskip 4.89998pt}{\hskip 4.89998pt}$}\,\ j,\ i\mbox{$\hskip
0.59998pt\prec\\!\\!\\!\\!\\!\frac{\hskip 4.89998pt\hskip 4.89998pt}{\hskip
4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}\,t\mbox{$\hskip
0.59998pt\prec\\!\\!\\!\\!\\!\frac{\hskip 4.89998pt\hskip 4.89998pt}{\hskip
4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}\,j$

is a _collider_ (or a collider node) and the inner node of any other tripath
is a _non-collider_ (or a non-collider node) on the tripath or, more
generally, on any path of which the tripath is a subpath; i.e., a node is a
collider if two arrowheads meet. Notice that in some causal inference
literature, the term _V-structure_ is used for a collider V-configuration. A
path is called a _collider_ path if all its inner nodes are colliders.

In this paper, we are mainly concerned with _directed ancestral graphs_ ;
these are _ancestral graphs_ (AGs) (Richardson and Spirtes, 2002) without
lines, i.e., graphs with arrows and arcs without a directed cycle and without
an arc with one endpoint being an ancestor of the other. Sometimes we simply
refer to such graphs as “graphs,” dropping any modifiers. Some results we use
in this paper have originally been proven for the more general classes of
chain mixed graphs (CMGs) and anterial graphs (AnGs) (Sadeghi, 2016) as well
as acyclic directed mixed graphs (ADMGs) (Richardson, 2003), all of which
contain directed ancestral graphs.

The class of directed ancestral graphs also contains _bidirected graphs_
(BGs), containing only bidirected edges, and _directed acyclic graphs_ (DAGs),
containing only arrows and being acyclic. DAGs have been particularly useful
to describe causal Markov relations; see for example Kiiveri et al. (1984);
Pearl (1988); Lauritzen and Spiegelhalter (1988); Geiger et al. (1990);
Spirtes et al. (2000). For an extensive discussion on the subclasses of
acyclic graphs and their relationships and hierarchy, see Lauritzen and
Sadeghi (2018).

###  2.2 Independence models and their properties

An _independence model_ $\mathcal{J}$, over a finite set $V$, is a set of
triples $\langle X,Y\,|\,Z\rangle$, called _independence statements_ , where
$X$, $Y$, and $Z$ are disjoint subsets of $V$; $Z$ may be empty, but
$\langle\varnothing,Y\,|\,Z\rangle$ and $\langle X,\varnothing\,|\,Z\rangle$
are always included in $\mathcal{J}$. The independence statement $\langle
X,Y\,|\,Z\rangle$ is read as “$X$ is independent of $Y$ given $Z$.”
Independence models may have a probabilistic interpretation, but this is not
necessarily the case. Similarly, not all independence models can be easily
represented by graphs. For further discussion on general independence models,
see Studený (2005).

In order to define probabilistic independence models, consider a set $V$ and a
collection of random variables $\\{X_{\alpha}\\}_{\alpha\in V}$ with state
spaces $\\{\mathcal{X}_{\alpha}\\}_{\alpha\in V}$ and joint distribution $P$.
We let $X_{A}=\\{X_{v}\\}_{v\in A}$ for each subset $A$ of $V$. For disjoint
subsets $A$, $B$, and $C$ of $V$ we use the short notation
$A\mbox{\,$\perp\\!\\!\\!\perp$\,}B\,|\,C$ to denote that $X_{A}$ is
_conditionally independent of $X_{B}$ given $X_{C}$_ (Dawid, 1979; Lauritzen,
1996), that is, for any measurable $S\subseteq\mathcal{X}_{A}$ and $P$-almost
all $x_{B}$ and $x_{C}$, we have

$\mathbb{P}(X_{A}\in S\,|\,X_{B}=x_{B},X_{C}=x_{C})=\mathbb{P}(X_{A}\in
S\,|\,X_{C}=x_{C}),$

where we make suitable interpretations in terms of regular conditional
probabilities when necessary; see for example Chang and Pollard (1997). We can
now induce an independence model $\mathcal{J}(P)$ by letting

$\langle A,B\,|\,C\rangle\in\mathcal{J}(P)\iff A\mbox{$\>\perp\perp$
}B\,|\,C\text{ w.r.t.\ $P$}.$

Similarly we use the notation $A\nolinebreak{\not\mbox{$\>\perp\perp$
}}B\,|\,C$ for $\langle A,B\,|\,C\rangle\notin\mathcal{J}(P)$. In this paper,
we present the results for “$P$,” but in fact all the conditions and
assumptions are on $\mathcal{J}(P)$. We remark that all the results and
conditions could be presented using an abstract independence model
$\mathcal{J}$.

In order to use graphs to represent independence models, the notion of
_separation_ in a graph is fundamental. A path $\pi$ is _connecting_ given $C$
if every collider node of $\pi$ is in $C$ or an ancestor of a node in $C$, and
every non-collider node is not in $C$. For pairwise disjoint subsets
$(A,B,C)$, we write $A\,\mbox{$\perp$}\,B\,|\,C$ if there are no connecting
paths between $A$ and $B$ given $C$, and say that $A$ and $B$ are _separated
given_ $C$. We will also use the notation
$A\nolinebreak{\not\,\mbox{$\perp$}\,}B\,|\,C$ for $A$ and $B$ not separated
given $C$. This separation criterion is generally known as the _$m$
-separation_, used in Richardson and Spirtes (2002), Wermuth (2011), and
Wermuth and Sadeghi (2012), for ancestral graphs and summary graphs, and is a
generalization of the _d-separation_ of Pearl (1988).

If $A$, $B$, or $C$ has only one member $\\{i\\}$, $\\{j\\}$, or $\\{k\\}$,
for better readability, we write $\langle i,j\,|\,k\rangle\in\mathcal{J}$
instead of $\langle\\{i\\},\\{j\\}\,|\,\\{k\\}\rangle\in\mathcal{J}$; and
similarly for $i\,\mbox{$\perp$}\,j\,|\,k$ and $i\mbox{$\>\perp\perp$
}j\,|\,k$. We also write $A\,\mbox{$\perp$}\,B$ when $C=\varnothing$; and
similarly $A\mbox{$\>\perp\perp$ }B$.

A graph $G$ induces an independence model $\mathcal{J}(G)$ by separation,
letting

$\langle A,B\,|\,C\rangle\in\mathcal{J}(G)\iff
A\,\mbox{$\perp$}\,B\,|\,C\text{ in }G.$

A graph is called _maximal_ if the absence of an edge between $i$ and $j$
corresponds to a conditional separation statement for $i$ and $j$, i.e., there
exists for some $C$ a statement of form $i\,\mbox{$\perp$}\,j\,|\,C$. In
addition, we call two graphs $G$ and $H$ _Markov equivalent_ if
$\mathcal{J}(G)=\mathcal{J}(H)$. Conditions for Markov equivalence for most
classes of graphs are known; see Verma and Pearl (1990); Ali et al. (2009);
Wermuth and Sadeghi (2012). Notice that two Markov equivalent maximal graphs
have the same skeleton. We require conditions for Markov equivalence of the
classes of graphs discussed here. A collider path $\pi=\langle i,B,j\rangle$
is called a _minimal collider path_ if $i\nsim j$ and there is no proper
subset $B^{\prime}\subset B$ such that $\langle i,B^{\prime},j\rangle$ is a
collider path between $i$ and $j$.

######  Lemma 1 (Zhao et al. (2004))

Two maximal ancestral graphs (and consequently maximal directed ancestral
graphs) are Markov equivalent if and only if they have the same skeletons and
minimal collider paths.

For DAGs, there is a simpler condition for Markov equivalence:

######  Lemma 2 (Verma and Pearl (1990))

Two DAGs are Markov equivalent if and only if they have the same skeletons and
collider V-configurations.

An independence model $\mathcal{J}$ over a set $V$ is a _semi-graphoid_ if it
satisfies the four following properties for disjoint subsets $A$, $B$, $C$,
and $D$ of $V$:

  1. 1.

$\langle A,B\,|\,C\rangle\in\mathcal{J}$ if and only if $\langle
B,A\,|\,C\rangle\in\mathcal{J}$ (_symmetry_);

  2. 2.

if $\langle A,B\cup D\,|\,C\rangle\in\mathcal{J}$, then $\langle
A,B\,|\,C\rangle\in\mathcal{J}$ and $\langle A,D\,|\,C\rangle\in\mathcal{J}$
(_decomposition_);

  3. 3.

if $\langle A,B\cup D\,|\,C\rangle\in\mathcal{J}$, then $\langle A,B\,|\,C\cup
D\rangle\in\mathcal{J}$ and $\langle A,D\,|\,C\cup B\rangle\in\mathcal{J}$
(_weak union_);

  4. 4.

if $\langle A,B\,|\,C\cup D\rangle\in\mathcal{J}$ and $\langle
A,D\,|\,C\rangle\in\mathcal{J}$, then $\langle A,B\cup
D\,|\,C\rangle\in\mathcal{J}$ (_contraction_).

Notice that the reverse implication of contraction clearly holds by
decomposition and weak union. A semi-graphoid for which the reverse
implication of the weak union property holds is said to be a _graphoid_ ; that
is, it also satisfies

  * 5.

if $\langle A,B\,|\,C\cup D\rangle\in\mathcal{J}$ and $\langle A,D\,|\,C\cup
B\rangle\in\mathcal{J}$, then $\langle A,B\cup D\,|\,C\rangle\in\mathcal{J}$
(_intersection_).

Furthermore, a graphoid or semi-graphoid for which the reverse implication of
the decomposition property holds is said to be _compositional_ , that is, it
also satisfies

  * 6.

if $\langle A,B\,|\,C\rangle\in\mathcal{J}$ and $\langle
A,D\,|\,C\rangle\in\mathcal{J}$, then $\langle A,B\cup
D\,|\,C\rangle\in\mathcal{J}$ (_composition_).

Another important property of independence models is _singleton-transitivity_
(also called _weak transitivity_ in Pearl (1988)). For $i$, $j$, and $k$,
single elements in $V$,

  * 7.

if $\langle i,j\,|\,C\rangle\in\mathcal{J}$ and $\langle
i,j\,|\,C\cup\\{k\\}\rangle\in\mathcal{J}$, then $\langle
i,k\,|\,C\rangle\in\mathcal{J}$ or $\langle j,k\,|\,C\rangle\in\mathcal{J}$
(singleton-transitivity).

Probabilistic independence models are always semi-graphoids (Pearl, 1988),
whereas the converse is not necessarily true; see Studený (1989). If $P$ has
strictly positive density, the induced independence model is always a
graphoid; see, for example, Proposition 3.1 in Lauritzen (1996). See also
Peters (2015) for a necessary and sufficient condition for the intersection
property to hold. If the distribution $P$ is a regular multivariate Gaussian
distribution, then $\mathcal{J}(P)$ is a singleton-transitive compositional
graphoid; for example see Studený (2005) and Pearl (1988). For this reason, a
different axiomatization of singleton-transitive compositional graphoid is
called a _Gaussoid_ in Lněnička and Matúš (2007). On the other hand,
separation in graphs satisfies all these properties; see Propositions 1 and 2
in Sadeghi (2017). If $\mathcal{J}(P)$ satisfies any of these properties, then
we may simply say that “P satisfies that property.”

###  2.3 Ordered upward- and downward-stabilities

The definitions and results below are a special case of those in Section 4 of
Sadeghi (2017). Consider a _partial order_ $\leq$ over the set $V$. If $a\leq
b$ or $b\leq a$, then $a$ and $b$ are _comparable_ ; otherwise they are
_incomparable_. Henceforth, we speak of “orders” referring to “partial
orders.”

We say that a graph $G=(V,E)$ admits a _valid order_ $\leq$ if for nodes $i$
and $j$ of $G$, $i\mbox{$\hskip 0.50003pt\frac{\hskip 4.89998pt\hskip
4.89998pt}{\hskip 4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}j$
implies that $i>j$; and $i\mbox{$\hskip
0.59998pt\prec\\!\\!\\!\\!\\!\frac{\hskip 4.89998pt\hskip 4.89998pt}{\hskip
4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}j$ implies that $i$ and $j$
are incomparable. Notice that this specifies the partial order via its cover
relations. There may be many different orders that are valid for a graph.
However, we obtain a unique ordering for a graph as follows: Given a graph
$G$, if $i\notin\mathrm{an}(j)$ and $j\notin\mathrm{an}(i)$, then set $i$ and
$j$ to be incomparable. Otherwise, let $i>j$ when $i\mbox{$\hskip
0.50003pt\frac{\hskip 4.89998pt\hskip 4.89998pt}{\hskip
4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}j$. We call this ordering
the _minimal order_ for $G$ since it gives the fewest possible comparable
pairs of nodes. It can also be seen that if $G$ is ancestral, then the minimal
order for $G$ is a valid order.

We now exploit the ordering for independence models in order to define two
other properties in addition to the seven properties defined in Section 2.2
(namely singleton-transitive compositional graphoid axioms). We say that an
independence model $\mathcal{J}$ over the set $V$ respectively satisfies
_ordered upward-_ and _downward-stability_ w.r.t. an order $\leq$ of $V$ if
the following hold:

  * 8.

if $\langle i,j\,|\,C\rangle\in\mathcal{J}$, then $\langle
i,j\,|\,C\cup\\{k\\}\rangle\in\mathcal{J}$ for every $k\in
V\setminus\\{i,j\\}$ such that $i<k$ or $j<k$ (ordered upward-stability);

  * 9.

if $\langle i,j\,|\,C\rangle\in\mathcal{J}$, then $\langle
i,j\,|\,C\setminus\\{k\\}\rangle\in\mathcal{J}$ for every $k\in
V\setminus\\{i,j\\}$ such that $i\nless k$, $j\nless k$, and $l\nless k$ for
every $l\in C\setminus\\{k\\}$ (ordered downward-stability).

Sometimes we refer to the pair of Conditions 8 and 9, together, simply as
_ordered stability_.

Ordered upward-stability is a generalization of a modification of _upward
stability_ , defined in Fallat et al. (2017), and _strong union_ , defined in
Pearl and Paz (1985), for undirected graphs. A similar concept was used in
Claassen and Heskes (2012) for the class of DAGs for inferring causal
relations; see Lemma 2 of the mentioned manuscript.

Sadeghi (2017) proved that the independence model induced by ancestral graphs
satisfies ordered upward- and downward-stability w.r.t. their minimal order.
If an independence model $\mathcal{J}$ satisfies ordered upward- and downward-
stability w.r.t. the minimal order of a graph $G$, then we simply say that
“$\mathcal{J}$ satisfies upward- and downward-stability w.r.t. $G$.” In
addition, similar to compositional graphoids, if $\mathcal{J}(P)$ satisfies
ordered upward- or downward-stability, then we may simply say that “$P$
satisfies that property.”

###  2.4 Markov and faithful independence models

For a graph $G=(V,E)$, a probability distribution defined over $V$ satisfies
the _global Markov property_ w.r.t. $G$, or is simply _Markovian_ to $G$, if
for disjoint subsets $A$, $B$, and $C$ of $V$ it holds that

$A\,\mbox{$\perp$}\,B\,|\,C\implies A\mbox{$\>\perp\perp$ }B\,|\,C,$

or equivalently $\mathcal{J}(G)\subseteq\mathcal{J}(P)$. Notice that every
probability distribution over $V$ is Markovian to the complete graph with the
node set $V$.

We say that $P$ and a graph $G$ are _faithful_ if
$\mathcal{J}(P)=\mathcal{J}(G)$. If $P$ and $G$ are faithful, then we may
sometimes also say that $P$ is _faithful to_ $G$ or vice versa, although in
principle faithfulness is a symmetric relation. Thus, if $P$ and $G$ are
faithful, then in addition to $P$ being Markovian to $G$, every conditional
independence statement corresponds to a separation in $G$. Notice that,
originally in Spirtes et al. (2000), faithfulness was defined only to be the
opposite direction to the Markov property. If there is a graph $G$ and a
distribution $P$ that are faithful, then we say that $P$ is _graphical_ and
$G$ is _probabilistic_.

For a given probability distribution $P$, we define the _skeleton_ of $P$,
denoted by $\mathrm{sk}(P)$, to be the undirected graph that is obtained from
$P$ as follows: we define the node set of $\mathrm{sk}(P)$ to be $V$, and for
every pair of nodes $i,j$, we check whether $i\mbox{$\>\perp\perp$ }j\,|\,C$
holds for some $C\subseteq V\setminus\\{i,j\\}$; if it does not then we draw
an edge between $i$ and $j$. The resulting undirected graph is the same as the
one obtained by the first step of the SGS algorithm (Glymour et al., 1987).

Suppose that there exists an order $\leq$ over $V$. We can uniquely direct the
edges of $\mathrm{sk}(P)$ based on $\leq$ in order to define a $G(P,\leq)$
induced by $P$ and $\leq$. It can be seen that $G(P,\leq)$ is ancestral.

We are only interested in orderings that are minimal orders of graphs. Given
$P$, we define an ordering $\leq$ to be _$P$ -compatible_ if $\leq$ is the
minimal order for $G(P,\leq)$.

If $P$ is Markovian to a graph $G$, then $\mathrm{sk}(P)$ is a subgraph of
$\mathrm{sk}(G)$; see Sadeghi (2017). Hence, if $P$ is Markovian to a graph
$G$ such that $\mathrm{sk}(G)=\mathrm{sk}(P)$, then $G$ has the fewest number
of edges among those to which $P$ is Markovian. We say that $P$ is _minimally
Markovian_ to a graph $G$ if $P$ is Markovian to $G$ and
$\mathrm{sk}(G)=\mathrm{sk}(P)$ (Sadeghi, 2017). Notice that only minimally
Markovian independence models to a graph can also be faithful to the graph.

######  Remark 3 (Related versions of minimality)

There are several similarly defined minimality assumptions in the literature.
Notice that we do not define the concept of minimal Markovian as an assumption
in this paper, since minimality is implied by some other assumptions used in
this paper; see Corollary 15.

The definition given here is subtly different from the (causal) minimality
assumption (Pearl, 2009; Spirtes et al., 2000; Zhang and Spirtes, 2008;
Neapolitan, 2004), which holds if $P$ is Markovian to $G$, but not to any
proper subgraph of $G$ — in fact, it can be seen that being minimal Markovian
implies causal minimality. It is also different from the P-minimality
assumption (Zhang, 2012), which states that no proper I-structure of $G$ is
Markovian to $P$, where I-structure of $G$ is any subgraph of $G$ whose
induced independence model is a subset of that of $G$. Again, being minimal
Markovian implies P-minimality since there could be a graph with fewer edges
than $G$ that is not an $I$-structure of $G$.

The sparsest Markov representation (SMR) assumption (Raskutti and Uhler, 2018)
for $G$ and $P$ (originally defined for DAGs) states that $P$ is Markovian to
$G$ and every $G^{\prime}$ to which $P$ is Markovian and not Markov equivalent
to $G$ has more edges than $G$ does. A similar concept is the frugality
assumption (Forster et al., 2018). In the special case of interest here, where
$G$ is Markovian to $P$, it states that $G$ satisfies frugality if it is in
the set of sparsest Markov representations. If $G$ and $P$ satisfy SMR, then
$G$ is not necessarily minimally Markovian to $P$ (see Figure 5 of Forster et
al. (2018) as an example). It is also possible to create two non-Markov
equivalent graphs with the same skeleton, and a $P$ that is Markovian to both.
This implies that the minimal Markovian assumption does not imply SMR either.

We make use of the necessary and sufficient conditions for faithfulness to
directed ancestral graphs, proven in Sadeghi (2017) for the more general case
of anterial graphs:

######  Proposition 4 (Sadeghi (2017))

Let $P$ be a probability distribution defined over $X_{V}$. Then $P$ is
graphical if and only if

  1. (A)

$P$ is a singleton-transitive compositional graphoid; and

  2. (B)

there exists a $P$-compatible order $\lesssim$ over $V$ w.r.t. which $P$
satisfies ordered downward- and upward-stability.

In addition, if (A) and (B) are satisfied, then $P$ is faithful to
$G(P,\lesssim)$.

###  2.5 Structural causal models

Here we define the _structural causal models_ (SCMs) (also known as the
_structural equation models_ (SEMs)) (Pearl, 2009; Spirtes et al., 2000) for
the class of directed ancestral graphs, as introduced in Richardson and
Spirtes (2002). Consider a graph $G$ with $N$ nodes, which in the context of
causal inference may be referred to as the “true causal graph.” An SCM
$\mathfrak{C}$ associated with $G$ is defined as a collection of $N$ equations

$X_{i}=\phi_{i}(X_{\mathrm{pa}(i)},\epsilon_{i}),\hskip
6.99997pti\in\\{1,\dots,N\\},$ (1)

where $\mathrm{pa}(i)$ is defined on $G$, and, for any subsets $A$ and $B$, we
require that $\epsilon_{A}\mbox{$\>\perp\perp$ }\epsilon_{B}$ if and only if,
in $G$, there is no arc between any node in $A$ and any node in $B$. Notice
that in the more widely-used case where $G$ is a DAG, all the $\epsilon_{i}$
are jointly independent. Sometimes the $X_{i}$ are called _endogenous
variables_ and the _noises_ $\epsilon_{i}$ are also called _exogenous
variables_ (which are generally assumed to be latent). For both mathematical
and causal discussions on SCMs with DAGs, see Peters et al. (2017). In the
case where $\phi_{i}$ represent multivariate linear regressions, SCMs are also
known as the system of linear equations (Cox and Wermuth, 1996).

Notice that the minimal order of $G$ induces an order for $X_{i}$s in
$\mathfrak{C}$. In addition, by using the equations iteratively, it is easy to
see that each $X_{i}$ can be written as a function of
$\epsilon_{\mathrm{an}(i)\cup\\{i\\}}$. An SCM also entails a unique joint
distribution $P$ over the variables $(X_{1},\dots,X_{N})$.

A more complete representation of the graph associated with an SCM is obtained
by including the random variables $\epsilon_{i}$. These graphs, called
_augmented graphs_ , are denoted by $G(X,\epsilon)$. We construct the
augmented graph in our setting as follows: we denote the nodes in $G$ by the
original notation $\\{X_{1},\dots,X_{N}\\}$; we add the nodes
$\\{\epsilon_{1},\dots,\epsilon_{N}\\}$ and add arrows from each
$\epsilon_{i}$ to $X_{i}$; we also remove all arcs between $X_{i}$s, and
instead of every $X_{i}X_{j}$-arc, add an arc between $\epsilon_{i}$ and
$\epsilon_{j}$.

For example, in Figure 1, the graph on the right, is the augmented graph of
the, graph on the left. An SCM associated to these graphs, in which $\phi_{i}$
are linear is as follows:

$X_{4}=\epsilon_{4},\hskip 6.99997ptX_{3}=\epsilon_{3},\hskip
6.99997ptX_{2}=\alpha X_{4}+\epsilon_{2},\hskip 6.99997ptX_{1}=\beta
X_{3}+\epsilon_{1}.$

$3$$1$$2$$4$$X_{3}$$X_{1}$$X_{2}$$X_{4}$$\epsilon_{3}$$\epsilon_{1}$$\epsilon_{2}$$\epsilon_{4}$
Figure 1: A graph $G$ (left) and its augmented graph $G(X,\epsilon)$ (right).

The above setting and construction of the augmented graph is in line with the
idea originally presented in Richardson and Spirtes (2002) for linear
functions and Gaussian distributions, although unlike in the mentioned
manuscript, noises corresponding to endpoints of variables adjacent by an arc
are _required_ to be dependent. This setting is different from the dominant
setting in the literature (e.g. Peters et al. (2017)) for directed ancestral
graphs, where for every arc $X_{i}X_{j}$ it is assumed that there exists an
exogenous variable $\epsilon_{ij}$, where, in the directed acyclic augmented
graph, it points to both $X_{i}$ and $X_{j}$, and that $\epsilon_{ij}$s are
mutually independent.

###### Remark 5

Our setting is more general than the other alternative presented above. Notice
that we can write a noise $\epsilon_{i}$ as a tuple $(\epsilon_{is})_{s\in
S}$, where $S$ is the set of nodes connected to $i$ by an arc. However, by
writing $\epsilon_{ij}=(\epsilon_{i},\epsilon_{j})$, we would not obtain
independent noises in the other setting.

##  3 General setting for structure learning

We start by assuming the existence of an _unknown_ distribution $P$, which is
Markovian to an unknown _(true) causal graph_ $G_{0}$. Indeed, this setting
requires additional models and assumptions to be considered “causal.” This
stems from the fact that, in the causal model, interventional probabilities
and observational conditional probabilities coincide. For more discussion on
this, see Pearl (2009); Spirtes et al. (2000); Peters et al. (2017).
Nevertheless, the setting presented here is what is required for causal
discovery using conditional independence under any causal model.

The main goal of structure learning is to use observational data to find a
graph that belongs to the Markov equivalence class of $G_{0}$. The
distribution $P$ induces an independence model $\mathcal{J}(P)$ whose elements
we can test for using the observed data. Although we can, in principle, test
each statement in $\mathcal{J}(P)$, testing for all independence statements is
computationally intractable. In a constraint-based structural learning
algorithm, one uses some of the independence statements in $\mathcal{J}(P)$ to
construct a graph, which is (hopefully) in the Markov equivalence class of
$G_{0}$. Notice that, in this paper, we concern ourselves only with the oracle
setting, i.e., assuming we have an oracle that will always correctly tell us
whether or not a given conditional independence relation holds in the
distribution.

Indeed the exact relationship between $P$ (or more specifically
$\mathcal{J}(P)$) and the constructed graph depends on the specific algorithm
used. Here, we propose the following class of generic algorithms.

######  Definition 6 (Natural structure-learning algorithm)

Let $P$ be a joint probability distribution on $X_{V}$. We say that a natural
constraint-based structure-learning algorithm is an algorithm whose output
graph with node set $V$, denoted by $G(P)$, has the following properties:

  1. 1.

It holds that $\mathrm{sk}(G(P))=\mathrm{sk}(P)$;

  2. 2.

The distribution $P$ satisfies ordered downward- and upward-stability w.r.t.
$G(P)$, that is, $G(P)=G(\mathcal{J}(P),\leq)$, for a partial order $\leq$,
w.r.t. which $P$ satisfies ordered downward- and upward-stability.

In short, the diagram below shows the relationship between the concepts used
in this setting:

$G_{0}\stackrel{{\scriptstyle\text{Markovian}}}{{\dashleftarrow}}P\stackrel{{\scriptstyle\text{conditional
independence}}}{{\rightarrow}}\mathcal{J}(P)\stackrel{{\scriptstyle\text{Algorithm}}}{{\rightarrow}}G(P)\stackrel{{\scriptstyle\text{Markov
equivalent}}}{{\sim}}G_{0}$

In the same fashion as many constraint-based structural learning algorithms,
the skeleton of the output of a natural structure-learning algorithm is the
same as $\mathrm{sk}(P)$. Under the faithfulness assumption of $P$ and
$G_{0}$, we will show in Section 4 that not only is $G(P)$ Markov equivalent
to $G_{0}$, but also $P$ satisfies ordered downward- and upward-stability
w.r.t. every graph Markov equivalent to $G_{0}$; thus the class of natural
structure-learning algorithms contains all well-known “exact” algorithms that
work under faithfulness, so we use term “natural.” Under alternative
conditions, provided in Section 5, we show that the output $G(P)$ is Markov
equivalent to $G_{0}$. Notice again that we will always use $G(P)$ to denote
an output of a natural structure-learning algorithm.

The algorithms in the literature, generally generate a completed partially
directed acyclic graph (CPDAGs) (Andersson et al., 1997; Spirtes et al., 2000)
or partial ancestral graphs (PAGs) (Richardson and Spirtes, 2002; Ali et al.,
2009), which are a representative of the Markov equivalence class of $G_{0}$
with the fewest arrowheads. Here, we are not concerned with making a CPDAG or
a PAG from $G(P)$.

We assume, without loss of generality, that the causal graph $G_{0}$ is
maximal: the reason is that if $G_{0}$ is not maximal, then there is always a
maximal graph that is Markov equivalent to $G_{0}$, which could be used to
find graphs Markov equivalent to $G_{0}$; see Richardson and Spirtes (2002);
Sadeghi and Lauritzen (2014). Note that the first condition of the natural
structure-learning algorithm in Definition 6 also ensures that the generated
$G(P)$ is maximal.

Since Markov equivalent maximal graphs have the same skeleton, the obtained
$G(P)$ must have the same skeleton with $G_{0}$. We are looking for
conditions, under which this holds.

Let $\mathrm{an}(i,j)=(\mathrm{an}(i)\cup\mathrm{an}(j))\setminus\\{i,j\\}$.
We say that $P$ is _converse pairwise Markovian_ to $G_{0}$ if

$i\mbox{$\>\perp\perp$ }j\,|\,\mathrm{an}(i,j)\Rightarrow i\nsim j\text{ in
}G_{0};$ (2)

note that the converse of this condition is the well-known pairwise Markov
property (Lauritzen, 1996). To ensure the equality of the mentioned skeletons,
we need the following lemma:

###### Lemma 7

Suppose that the distribution $P$ is Markovian to the causal graph $G_{0}$,
and that the following two conditions are satisfied:

  1. (a)

$P$ is converse pairwise Markovian to $G_{0}$;

  2. (b)

if there exists $C$, not containing $i$ and $j$, such that
$i\mbox{$\>\perp\perp$ }j\,|\,C$, then $i\mbox{$\>\perp\perp$
}j\,|\,\mathrm{an}(i,j)$.

Then $\mathrm{sk}(G_{0})=\mathrm{sk}(G(P))$, where $G(P)$ is an output of a
natural structure-learning algorithm.

Proof  We have on $G_{0}$ the equivalence

$i\nsim j\text{ in }G_{0}\iff i\mbox{$\>\perp\perp$ }j\,|\,\mathrm{an}(i,j),$

where assumption (a) gives the reverse direction, and the forward direction
follows from the fact that $P$ is Markovian to $G_{0}$, and $\mathrm{an}(i,j)$
always separates non-adjacent $i$ and $j$. Since
$\mathrm{sk}(P)=\mathrm{sk}(G(P))$, we have the equivalence

$i\nsim j\text{ in }G(P)\iff\exists C\text{ s.t.\ }i\mbox{$\>\perp\perp$
}j\,|\,C.$

Hence, assumption (b) allows us to tie these two conditions together and
obtain that

$i\nsim j\text{ in }G(P)\iff i\nsim j\text{ in }G_{0},$

from which the desired result follows.

###### Remark 8

The two conditions of Lemma 7 are equivalent to the adjacency-faithfulness
condition (Ramsey et al., 2006; Zhang and Spirtes, 2008) (defined for DAGs),
which states that for every edge between $i$ and $j$ in $G_{0}$, there are no
independence statements $i\mbox{$\>\perp\perp$ }j\,|\,C$ for any $C$. This
breakdown of the adjacency faithfulness assumption allows us to later provide
useful sufficient conditions (in general and for SCMs) that ensure that these
two conditions are satisfied; see also the discussion below.

We need some additional assumptions on the distributions to determine when the
assumptions of Lemma 7 hold; i.e., when an existing edge implies dependence
given the joint ancestors, and when an arbitrary conditional independence of a
pair implies their conditional independence given their joint ancestors. A
condition under which these assumptions hold is faithfulness, as will be
discussed in the next section. However, weaker conditions will be provided in
Section 5. Specific conditions for SCMs will also be provided in Section 6.

##  4 Structure learning under faithfulness

Faithfulness of $P$ and $G_{0}$ is a main assumption in the literature for
structure learning. It is well-known that under faithfulness, $P$ is
_identifiable_ , i.e., an ancestral graph (or a DAG) (in reality a PAG (or a
CPDAG)) Markov equivalent to $G_{0}$ can be identified (Spirtes et al., 2000;
Zhang and Spirtes, 2008). Under faithfulness, if $P$ is faithful to $G_{0}$,
then any structure-learning algorithm should provide an output $G(P)$ that is
faithful to $P$, in the setting where an oracle can be queried regarding the
validity of statements of conditional independence.

By Proposition 4, if the assumption of $P$ being graphical holds, then $P$ is
singleton-transitive compositional graphoid and there is an ordering $\leq$ of
the nodes of $\mathrm{sk}(P)$ w.r.t. which $P$ satisfies ordered downward- and
upward-stability. Notice that among all these conditions required for
graphicality, ordered downward- and upward-stability are the only ones that
are related to, and in fact determine, the direction of the edges of
$\mathrm{sk}(P)$; these considerations also motivate the definition of natural
structure-learning algorithms in Definition 6.

We work towards a proof, that under faithfulness, a natural structure-learning
algorithm works.

###### Proposition 9

Suppose that $P$ is faithful to the causal graph $G_{0}$. The output of a
natural structure-learning algorithm satisfies
$\mathrm{sk}(G_{0})=\mathrm{sk}(G(P))$.

Proof  We show that the conditions of Lemma 7 hold.

  1. (a)

If $i\mbox{$\>\perp\perp$ }j\,|\,\mathrm{an}(i,j)$, then faithfulness gives,
$i\,\mbox{$\perp$}\,j\,|\,\mathrm{an}(i,j)$ in $G_{0}$, which implies that
$i\nsim j$ in $G_{0}$.

  2. (b)

If there exists a $C$ such that $i\mbox{$\>\perp\perp$ }j\,|\,C$, then
faithfulness gives, $i\,\mbox{$\perp$}\,j\,|\,C$ in $G_{0}$, which implies
that $i\nsim j$ in $G_{0}$. Since $P$ is Markovian to $G_{0}$, we have that
$i\mbox{$\>\perp\perp$ }j\,|\,\mathrm{an}(i,j)$.

###### Proposition 10

Suppose that $P$ is faithful to the causal graph $G_{0}$. All potential
outputs of natural structure-learning algorithms are Markov equivalent, and
they are Markov equivalent to $G_{0}$.

Proof  Since $P$ is graphical, by Proposition 4, it is singleton-transitive
compositional graphoid. Let $G(P)$ and $H(P)$ be two potential graphs
generated by a natural structure-learning algorithm. By Proposition 9, we have
that $\mathrm{sk}(G_{0})=\mathrm{sk}(G(P))=\mathrm{sk}(H(P))$.

In addition, $P$ satisfies ordered upward- and downward-stability w.r.t. both
$G(P)$ and $H(P)$. Hence, again by Proposition 4, $P$ is faithful to both.
Therefore, these graphs are all Markov equivalent.

In addition, the other direction of the above result also holds:

###### Proposition 11

Suppose that $P$ is faithful to $G_{0}$. If $G$ is Markov equivalent to
$G_{0}$, then $P$ satisfies ordered upward- and downward-stability w.r.t. $G$.

Proof  The graph $G$ and $P$ have to be faithful. Therefore, by Proposition 4,
we know that $P$ satisfies ordered upward- and downward-stability w.r.t. $G$.

###### Remark 12

Therefore, ordered downward- and upward-stability w.r.t. $G(P)$ are also
necessary conditions of an output of a structure-learning algorithm that
generates Markov equivalent graphs to $G_{0}$. This justifies Definition 6,
when $P$ is graphical. Hence, any “exact” (as opposed to approximate)
constraint-based algorithms that work under the assumption of faithfulness
(such as the SGS and PC algorithms (Spirtes et al., 2000)) must (and, in fact,
do) ensure that, w.r.t. their output, $P$ satisfies ordered downward- and
upward-stability.

##  5 Conditions and assumptions for the structure-learning algorithm

Recall that the general goal of constraint-based structure learning is to
consider algorithms for which the output $G(P)$ is Markov equivalent to (the
unknown) causal graph $G_{0}$. In Section 4, we saw that under the assumption
of faithfulness of $P$ and $G_{0}$, this goal is achieved for the class of
algorithms falling under Definition 6, the class of natural structure-learning
algorithms. However, in fact, faithfulness is not necessary for this goal, as
will be shown below in Example 13; see also Example 18 for when one focuses
solely on the class of DAGs.

######  Example 13 (Ordered stability and faithfulness)

Consider the graph in Figure 2, and assume that it is $G_{0}$ in the setting
of this manuscript. Let $\mathcal{J}(P)$ be the set of statements implied by
the global Markov property plus $i\mbox{$\>\perp\perp$ }j\,|\,k$. First of
all, notice that $P$ does not satisfy singleton-transitivity. Notice also that
$P$ is minimally Markovian to $G_{0}$, but $P$ and $G_{0}$ are not faithful.
In addition, $P$ satisfies ordered upward- and downward-stability w.r.t.
$G_{0}$.

However, all graphs, including the true causal graph $G_{0}$, w.r.t. which $P$
satisfies ordered downward- and upward-stability are Markov equivalent. To see
this, suppose that there is a graph $H$ with the same skeleton, w.r.t. which
$P$ satisfies ordered upward- and downward-stability, and that $H$ is not
Markov equivalent to $G_{0}$. If, in $H$, $k$ is non-collider then $k>\ell$ or
$k>i$, which, by ordered upward-stability, implies $i\mbox{$\>\perp\perp$
}\ell\,|\,k$; but this is not in $\mathcal{J}(P)$. Now, if in $H$, the node
$\ell$ is collider, then $k,j>\ell$, which by ordered downward-stability and
conditional independence $k\mbox{$\>\perp\perp$ }j\,|\,\ell$, implies
$k\mbox{$\>\perp\perp$ }j$, which is again not in $\mathcal{J}(P)$.

$i$$k$$\ell$$j$ Figure 2: $G_{0}$

Below, we find assumptions under which a natural structure-learning algorithm
works; these assumptions can be thought of as a relaxation of faithfulness.

###  5.1 Equivalence of the skeletons of $G_{0}$ and $G(P)$

We first need to provide assumptions so that $G_{0}$ and $G(P)$ have the same
skeletons. One of the main assumptions we employ is that $P$ satisfies ordered
downward- and upward-stability w.r.t. $G_{0}$.

###### Theorem 14

Consider a distribution $P$ that is Markovian to the causal graph $G_{0}$
satisfying the following conditions:

  1. (i)

$P$ is converse pairwise Markovian to $G_{0}$;

  2. (ii)

$P$ satisfies ordered upward- and downward-stability w.r.t. $G_{0}$.

Then $\mathrm{sk}(G_{0})=\mathrm{sk}(G(P))$.

Proof  It suffices to show that assumption (b) of Lemma 7 is satisfied.
Suppose $i\mbox{$\>\perp\perp$ }j\,|\,C$. Consider all the nodes in
$C\setminus\mathrm{an}(i,j)$. Since $P$ satisfies ordered downward-stability
w.r.t. $G_{0}$, one can remove the node $k_{0}$ with a lowest order in this
set to obtain $i\mbox{$\>\perp\perp$ }j\,|\,C\setminus\\{k_{0}\\}$.
Inductively, we will obtain $i\mbox{$\>\perp\perp$
}j\,|\,C\cap\mathrm{an}(i,j)$. Now, by the use of ordered upward-stability, we
add other nodes in $\mathrm{an}(i,j)$ to the conditioning set, and obtain
$i\mbox{$\>\perp\perp$ }j\,|\,\mathrm{an}(i,j)$.

###### Corollary 15

Consider a distribution $P$ that satisfies the conditions of Theorem 14. Then
$P$ is minimally Markovian to $G_{0}$.

###### Remark 16

Notice that there exist cases where there is a unique Markov equivalent class
of graphs including $G_{0}$ to which the distribution $P$ is Markovian, but
the skeleton of $G_{0}$ is not the same as the skeleton of $P$; see Forster et
al. (2018), where such examples are used as a motivation for the assumption of
frugality; see Remark 3. In such cases, conditions of Theorem 14 (or
equivalently adjacency-faithfulness) are not satisfied. This suggests that
there could be extensions to the setting of this paper.

###  5.2 Markov equivalence of $G(P)$ and $G_{0}$

In this section, we will describe under what additional testable conditions
$G_{0}$ and $G(P)$ are Markov equivalent. We provide the conditions and
results both for the case where $G_{0}$ is a DAG and the structure-learning
algorithm only generates DAGs, and also for the general case where $G_{0}$ is
a directed ancestral graph and the structure-learning algorithm generates such
graphs.

We formalize the problem using the following concept: We say that a
distribution $P$ satisfies the _uniqueness property_ (up to Markov
equivalence) when the following holds: maximal graphs with skeleton
$\mathrm{sk}(P)$ w.r.t. which $P$ satisfies ordered upward- and downward-
stability are Markov equivalent. For the special case of DAGs, we say that a
distribution $P$ satisfies the _DAG-uniqueness property_ if the graphs
concerned in the definition of the uniqueness property are restricted to DAGs.

The distribution $P$ satisfying the uniqueness property is equivalent to the
potential outputs of the structure-learning algorithm being unique up to
Markov equivalence. This is an obvious requirement of the structure-learning
algorithm so that the algorithm cannot generate two graphs that are not Markov
equivalent.

In order to ensure that the output of a natural structure-learning algorithm
is correct, we need the following important lemma:

###### Lemma 17

Consider a distribution $P$ that is Markovian to $G_{0}$. Suppose that the
conditions of Theorem 14 are satisfied; that is, $P$ is converse pairwise
Markovian to $G_{0}$ and $P$ satisfies ordered upward- and downward-stability
w.r.t. $G_{0}$. Let $G(P)$ be the output of a natural structure-learning
algorithm.

  1. (a)

If $P$ satisfies the uniqueness property, then $G(P)$ is Markov equivalent to
$G_{0}$.

  2. (b)

If $G_{0}$ is a DAG, then $P$ satisfying the DAG-uniqueness property implies
that a DAG output $G(P)$ is Markov equivalent to $G_{0}$.

Proof  The proof follows from Theorem 14.
In what follows, we provide and study explicit conditions under which the
uniqueness property is satisfied.

By Corollary 15, we know that, under the assumptions for $P$, which we have so
far utilized, $P$ is minimally Markovian to $G_{0}$. In Example 18, we observe
that, if we replace the faithfulness assumption with the assumption of being
minimal Markovian, then the uniqueness property no longer holds.

###### Example 18

Let $\mathcal{J}(P)=\\{1\mbox{$\>\perp\perp$ }4\,|\,\\{2,3\\},\
1\mbox{$\>\perp\perp$ }4\,|\,3,\ 2\mbox{$\>\perp\perp$ }3\,|\,4\\}$. For
example, there is an SCM that induces such an independence model: Let
$\epsilon_{1},\epsilon_{2},\epsilon_{3}$, and $\epsilon_{4}$ be i.i.d. Define

$X_{1}=\max(X_{2},X_{3},\epsilon_{1});\hskip
6.99997ptX_{2}=\max(X_{4},\epsilon_{2});\hskip
6.99997ptX_{3}=\max(2X_{4},\epsilon_{3});\hskip 6.99997ptX_{4}=\epsilon_{4}.$

It can be seen that $(X_{i})_{i\in\\{1,\dots,4\\}}$ induces $\mathcal{J}(P)$.

First notice that $P$ does not satisfy the uniqueness property: w.r.t. both
graphs $G_{1}$ and $G_{2}$ in Figure 3(b) and 3(c), $\mathcal{J}(P)$ satisfies
ordered upward- and downward-stability. However, these two graphs are not
Markov equivalent.

Since $P$ satisfies the compositional graphoid axioms (but not singleton-
transitivity), this also shows that compositional graphoid plus ordered
upward- and downward-stability are not in general sufficient for the
uniqueness property to hold.

However, if we assume that the structure-learning algorithm is only DAG-
generating, then there is a unique graph w.r.t. which $P$ satisfies ordered
upward- and downward-stability (and consequently the DAG-uniqueness property
holds).

$4$$3$$2$$1$$4$$3$$2$$1$$4$$3$$2$$1$(a)(b)(c) Figure 3: (a) The skeleton of
$P$ with no arrows. (b) A DAG $G_{1}$. (c) A graph $G_{2}$ with arcs.

From Example 13, we see that singleton-transitivity is not necessary for the
uniqueness property. We provide a (weaker) condition, which together with
assumptions of Theorem 14, are still sufficient for uniqueness.

We say that an independence model $\mathcal{J}$ is _path-unstable_ if there
exists a path

$\langle i=i_{0},i_{1},\cdots,i_{r},k,j\rangle,\hskip 6.99997pt\hskip
6.99997pti\not\sim j\text{ and }i_{r}\sim j\text{ for every }r\geq 1$

in $\mathrm{sk}(\mathcal{J})$ such that $i\mbox{$\>\perp\perp$ }j\,|\,U\cup C$
and $i\mbox{$\>\perp\perp$ }j\,|\,U\cup C\cup\\{k\\}$, for some $C$ disjoint
from $\\{i,j,k\\}$, where $U=\\{i_{1},\cdots,i_{r}\\}$ or $U=\emptyset$ when
$r=0$. An independence model that is not path-unstable is called _path-
stable_.

In the case where the structure-learning algorithm is DAG-generating, the
required condition is simpler. We say that an independence model $\mathcal{J}$
is _V-unstable_ if there exists a V-configuration $\langle i,k,j\rangle$ in
$\mathrm{sk}(\mathcal{J})$ such that $i\mbox{$\>\perp\perp$ }j\,|\,C$ and
$i\mbox{$\>\perp\perp$ }j\,|\,C\cup\\{k\\}$, for some $C$ disjoint from
$\\{i,j,k\\}$. An independence model that is not V-unstable is called _V-
stable_. In the same fashion as before, if $\mathcal{J}(P)$ satisfies path- or
V-stability then we simply say that “$P$ satisfies these conditions.”

###### Remark 19

As will be seen in the proof of Proposition 24, the path that appears in the
definition of a path-unstable $P$ can be thought of as the skeleton of (and
can be directed to become) a _discriminating path_ (Ali et al., 2009) from $i$
to $j$; i.e., a path $\langle i=i_{0},i_{1},\cdots,i_{r},k,j\rangle$ that is a
collider path, and $i_{n}\in\mathrm{pa}(j)$, for every $1\leq n\leq r$.

###### Remark 20

The well-known orientation-faithfulness assumption (which is defined as a part
of the restricted-faithfulness assumptions) (Ramsey et al., 2006) states that
for all V-configurations $\langle j,l,k\rangle$ and all subsets $S\subset
V\setminus\\{j,k\\}$ such that $j$ is d-connected to $k$ given $S$ it holds
that $j\nolinebreak{\not\mbox{$\>\perp\perp$ }}k\,|\,S$. Notice that, unlike
orientation-faithfulness, V-stability (and also path stability) are purely
defined on the distribution $P$ and not on the unknown causal graph $G_{0}$.
Indeed, if the conditions of Theorem 14 are satisfied to ensure that
$\mathrm{sk}(G_{0})=\mathrm{sk}(G(P))$, then orientation-faithfulness implies
V-stability. However, even under these extra assumptions, the other direction
does not hold; see Example 21 below.

###### Example 21

Consider the true causal graph $G_{0}$ in Figure 4. Let $\mathcal{J}$ contain
all the conditional independence statements implied by the global Markov
property on $G_{0}$, with the addition of $j\mbox{$\>\perp\perp$ }k\,|\,s$. We
have that $\mathrm{sk}(\mathcal{J})=\mathrm{sk}(G_{0})$. By looking at
$\mathrm{sk}(\mathcal{J})$, it can be seen that V-stability is satisfied, but
orientation-faithfulness is not: Consider the V-configuration $\langle
j,l,k\rangle$. We have that $j$ is d-connected to $k$ given $s$, but that
$j\mbox{$\>\perp\perp$ }k\,|\,s$.

$l$$m$$s$$k$$j$ Figure 4: A directed acyclic graph $G_{0}$.

V-stability is weaker than singleton-transitivity:

###### Proposition 22

Singleton-transitivity implies V-stability.

Proof  Towards a contradiction, suppose that there is a V-configuration
$\langle i,k,j\rangle$ in $\mathrm{sk}(P)$ such that $i\mbox{$\>\perp\perp$
}j\,|\,C$ and $i\mbox{$\>\perp\perp$ }j\,|\,C\cup\\{k\\}$, for some $C$
disjoint from $\\{i,j,k\\}$. By singleton-transitivity, $i\mbox{$\>\perp\perp$
}k\,|\,C$ or $k\mbox{$\>\perp\perp$ }j\,|\,C$, which is absurd since both $ik$
and $jk$ are edges in $\mathrm{sk}(P)$.
In addition, the converse of the above result does not hold; see Example 13.
Hence, we have the following corollary:

###### Corollary 23

If $P$ is faithful to a graph, then it satisfies V-stability.

Proof  The proof follows from the fact that $P$ being graphical implies it
satisfies singleton-transitivity (Proposition 4).
Also notice that singleton-transitivity and path-stability do not imply each
other (for one direction, see Example 13 again), but there are considerably
fewer independence statements to test for for path-stability than for
singleton-transitivity. In a similar fashion, there could be cases where $P$
is graphical, but path-stability is not satisfied: one can take the skeleton
of a discriminating path and direct the edges (with the path not being
collider) so that the induced independence model (by separation) is path
unstable. However, notice again that unlike faithfulness, path-stability is
purely defined on $P$, and hence, in principle, testable. We now have the
following relationship to the uniqueness property:

###### Proposition 24

Let $P$ be a distribution.

  1. (a)

If $P$ is path-stable, then it satisfies the uniqueness property.

  2. (b)

If $P$ is V-stable, then it satisfies the DAG-uniqueness property.

Proof  We start with the proof for the case of DAGs, which is more elementary
than the general case.

(b) Suppose that $P$ satisfies ordered upward- and downward-stability w.r.t.
two orders $\leq^{\prime}$ and $\leq^{\prime\prime}$. Towards a contradiction,
suppose that the two DAGs, $G(P,\leq^{\prime})$ and $G(P,\leq^{\prime\prime})$
are not Markov equivalent.

By Lemma 2, there is a collider V-configuration $\langle i,k,j\rangle$, say,
in $G(P,\leq^{\prime})$, which is a non-collider in $G(P,\leq^{\prime\prime})$
(say $k>^{\prime\prime}j$). Since $G(P,\leq^{\prime})$ is maximal,
$i\mbox{$\>\perp\perp$ }j\,|\,C$, for some $C$. By ordered downward-stability
w.r.t. $\leq^{\prime}$, we obtain $i\mbox{$\>\perp\perp$ }j\,|\,C^{\prime}$,
for some $C^{\prime}$ such that $k\notin C^{\prime}$. Now by ordered upward-
stability w.r.t. $\leq^{\prime\prime}$, we obtain $i\mbox{$\>\perp\perp$
}j\,|\,C^{\prime}\cup\\{k\\}$. This shows that $P$ is V-unstable, which is a
contradiction.

(a) Suppose that $P$ satisfies ordered upward- and downward-stability w.r.t.
two orders $\leq^{\prime}$ and $\leq^{\prime\prime}$. Towards a contradiction,
suppose that the two maximal graphs $G(P,\leq^{\prime})$ and
$G(P,\leq^{\prime\prime})$ are not Markov equivalent.

By Lemma 1, there is a minimal collider path $\pi$, say, in
$G(P,\leq^{\prime})$, which is not a minimal collider path in
$G(P,\leq^{\prime\prime})$. Consider a shortest minimal collider subpath
$\pi^{\prime}$ of $\pi$ in $G(P,\leq^{\prime})$ that is not a minimal collider
in $G(P,\leq^{\prime\prime})$. Furthermore, we can assume that $\pi^{\prime}$
is not a collider path in $G(P,\leq^{\prime\prime})$, since if $\pi^{\prime}$
is a collider path, but not minimal, we consider the minimal collider subpath
$\pi^{\prime\prime}$ in $G(P,\leq^{\prime\prime})$. Note that
$\pi^{\prime\prime}$ is not a minimal collider in $G(P,\leq^{\prime})$. We can
then continue the proof using $\pi^{\prime\prime}$ instead of $\pi^{\prime}$,
and the roles of $G(P,\leq^{\prime})$ and $G(P,\leq^{\prime\prime})$ reversed.

Let $i$ and $j$ be the endpoints of $\pi^{\prime}$ which is not a collider in
$G(P,\leq^{\prime\prime})$. Consider a node $k$, which is a non-collider node
on $\pi^{\prime}$. We show that $k$ is adjacent to $i$ or $j$ on
$\pi^{\prime}$. Towards a contradiction, suppose that it is not adjacent to
either. Consider a subpath of $\pi^{\prime}$ given by $\langle
i^{\prime},h,k,\ell,j^{\prime}\rangle$. Recall that the endpoints of a minimal
collider path are not adjacent. Hence $h\sim\ell$, otherwise, $\langle
h,k,\ell\rangle$ is a shorter minimal collider subpath in $G(P,\leq^{\prime})$
that is not a minimal collider in $G(P,\leq^{\prime\prime})$. Similarly,
$h\sim j^{\prime}$ and $i^{\prime}\sim\ell$. Since $\pi^{\prime}$ is a minimal
collider, the $h\ell$-edge cannot be an arc, and the $hj$\- and $i\ell$-edge
have to be arrows from $h$ to $j^{\prime}$ and $\ell$ to $i^{\prime}$,
respectively. Since directed cycles are not permissible in an ancestral graph,
it is easy to rule out the existence of an arrow from $h$ to $\ell$ and vice-
versa; we already ruled out the possibility that the $h\ell$-edge is an arc,
and we require that $h\sim\ell$, which is absurd.

Without loss of generality, assume that $k$ is adjacent to $j$ on
$\pi^{\prime}$. Let $\pi^{\prime}=\langle
i=i_{0},i_{1},\cdots,i_{r},k,j\rangle$, where $r$ may be $0$. If $r>0$, then
by minimality, $i_{r}\sim j$ and $i_{r}\mbox{$\hskip 0.50003pt\frac{\hskip
4.89998pt\hskip 4.89998pt}{\hskip 4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip
1.07639pt$}j$. From an inductive argument along $\pi^{\prime}$, if $r>0$, we
conclude that $\pi^{\prime}$ is a discriminating path from $i$ to $j$.

Since $G(P,\leq^{\prime})$ is maximal, $i\mbox{$\>\perp\perp$ }j\,|\,C$, for
some $C$; moreover, $k\notin\mathrm{an}(i)$ since otherwise $i$ and $j$ are
not separated. Since $k$ is a collider in $G(P,<^{\prime})$, we have $k\not\in
an(j)$. Therefore, by ordered downward-stability w.r.t. $\leq^{\prime}$, we
obtain $i\mbox{$\>\perp\perp$ }j\,|\,C^{\prime}$, for some $C^{\prime}$ such
that $k\notin C^{\prime}$. By ordered upward-stability w.r.t. $\leq^{\prime}$,
and the previously established discrimination, we obtain
$i\mbox{$\>\perp\perp$ }j\,|\,U\cup C^{\prime}$, where
$U=\\{i_{1},\cdots,i_{r}\\}$ (and if $r=0$, then $U=\emptyset$). Now by
ordered upward-stability w.r.t. $\leq^{\prime\prime}$, we obtain
$i\mbox{$\>\perp\perp$ }j\,|\,U\cup C^{\prime}\cup\\{k\\}$, since $k$ is not a
collider node on $G(P,\leq^{\prime\prime})$. Thus $P$ is path-unstable, which
is a contradiction.

This leads to the main result, which provides conditions under which a natural
structure-learning algorithm works.

###### Theorem 25

Suppose that $P$ satisfies the conditions of Theorem 14, that is, it is
Markovian and converse pairwise Markovian to $G_{0}$, and satisfies ordered
upward- and downward-stability w.r.t. $G_{0}$. Let $G(P)$ be the output of a
natural structure-learning algorithm.

  1. (a)

If $P$ is also path-stable, then $G(P)$ is Markov equivalent to $G_{0}$.

  2. (b)

If $G_{0}$ is a DAG and $P$ is V-stable, then a DAG-output $G(P)$ is Markov
equivalent to $G_{0}$.

Proof  The proof follows from Proposition 24 and Lemma 17.
As an example for the theorem above, we can revisit our motivating Example 13
to observe that although faithfulness is not satisfied, all the conditions of
Theorem 25, and, in particular, V-stability are satisfied.

However, notice that, under the conditions presented here, ordered downward-
and upward-stability w.r.t. $G_{0}$ are not necessary in the sense that there
are cases where ordered downward- and upward-stability are not satisfied
w.r.t. $G_{0}$ , but an output of the algorithm is Markov equivalent to
$G_{0}$. This stems from the fact that there could be two Markov equivalent
graphs and a $P$ such that $P$ satisfies ordered downward- and upward-
stability w.r.t. one but not the other; see example below.

###### Example 26

Consider the causal graph $G_{0}$ and its Markov equivalent graph $G_{1}$
below. Let $\mathcal{J}$ (which, in principle could be induced by a
probability distribution) contain all the independencies induced by the global
Markov property plus $k\mbox{$\>\perp\perp$ }m\,|\,l$ and additional
independence statements implied by applying ordered upward-stability w.r.t.
$G_{1}$ and semi-graphoid axioms. It can be checked that
$k\nolinebreak{\not\mbox{$\>\perp\perp$ }}m\,|\,\\{i,l\\}$. Hence,
$\mathcal{J}$ does not satisfy ordered upward-stability w.r.t. $G_{0}$.
However, by definition, $\mathcal{J}$ satisfies ordered upward-stability
w.r.t. $G_{1}$. Notice also that, in this example, $V$-stability (and path-
stability) are satisfied.

$j$$k$$h$$t$$m$$l$$i$$j$$k$$h$$t$$m$$l$$i$(a)(b) Figure 5: (a) $G_{0}$, (b)
$G_{1}$

The above discussion suggests that one can replace the condition “$P$
satisfying ordered upward- and downward-stability w.r.t. $G_{0}$” in Theorem
25 with “$P$ satisfying ordered upward- and downward-stability w.r.t. a graph
in the Markov equivalence class of $G_{0}$” in order to make the condition
necessary.

##  6 Structure learning for structural causal models

First, we give a proof for the global Markov property for general SCMs, which
allow for the possibility of arcs. Then we find conditions on the functions of
the SCM to ensure the converse pairwise Markov property; see (2).

###  6.1 Global Markov property for general SCMs

The main assumption used in the general setting for structure learning is that
$P$ is Markovian to the causal graph $G_{0}$. A main reason for popularity of
SCMs for causal learning is that this condition is automatically satisfied for
the joint distribution of an SCM. Indeed, the joint distribution of an SCM
with mutually independent errors being Markovian to the DAG $G_{0}$ is a well-
known result (Verma and Pearl, 1988; Pearl, 2009), but we are not aware of
such a result in an explicit and non-parametric form when unobserved variables
are existent; see Koster (1999) for a similar result in the Gaussian case and
with a slightly different type of graph. Recently, in Bongers et al. (2021), a
similar result is proven for directed SCMs, but for a less general setting
when one focuses on ancestral graphs; see Remark 5. See also Forre and Mooij
(2017) for various equivalent notions of the Markov property.

###### Theorem 27

The joint distribution $P$ of an SCM is Markovian to $G_{0}$.

The proof of the above theorem requires some definitions and results that are
not used in the subsequent sections. We provide the proof together with these
definitions and results in the remainder of this subsection. Readers may skip
the proof without loss of continuity.

We first need some primary definitions and results mostly from Richardson
(2003). The _district_ of node $i$, denoted by $\mathrm{dis}(i)$, is the set
of nodes connected to $i$ by a collider path on which every edge is an arc. We
also define a set $A$ to be _ancestral_ if it is closed under the ancestor
relation, i.e., if $A\cup\mathrm{an}(A)=A$. If $A$ is an ancestral set in a
graph $G$, and $i$ is a node in $A$ that has no children in $A$, then we
define the _Markov blanket_ of $i$ w.r.t. the induced subgraph $G[A]$ on $A$
by

$\mathrm{mb}(i,A)=\mathrm{pa}_{G[A]}(\mathrm{dis}_{G[A]}(i))\ \cup\
(\mathrm{dis}_{G[A]}(i)\setminus\\{i\\}).$

We use the notation $\mathrm{pst}(i)$ for the set of nodes with an order
larger that $i$. We say that a probability distribution satisfies the _ordered
local Markov property_ w.r.t. the ordering $\leq$, if for any node $i$, and
ancestral set $A$ such that $i\in A\subseteq\mathrm{pst}(i)$, we have

$i\mbox{$\>\perp\perp$
}[A\setminus(\mathrm{mb}(i,A)\cup\\{i\\})]\,|\,\mathrm{mb}(i,A).$

We have the following equivalence, which does not require any extra
assumptions, originally proven for ADMGs (which is a more general class than
directed ancestral graphs):

######  Lemma 28 (Richardson (2003))

For a valid ordering $\leq$ of the nodes of a graph $G$, a distribution $P$
satisfying the ordered local Markov property w.r.t. $\leq$ is equivalent to
$P$ being Markovian to $G$.

In this section, we also utilize the concept of marginalization over
probability distributions and graphs. Let $\alpha(P,M)$ be the marginalized
distribution over $M\subset V$ so that $\alpha(P,M)$ is defined over
$X_{V\setminus M}$. Notice that the induced independence model of
$\alpha(P,M)$ is $\mathcal{J}(\alpha(P,M))=\\{A\mbox{$\>\perp\perp$
}B\,|\,D:(A\cup B\cup D)\cap M=\varnothing\\}$.

By marginalizing over the node set $M$ of graph $G$, a new graph $\alpha(G,M)$
is obtained from which the node set $M$ is removed: For every path $\pi$ in
$G$ between $i,j\notin M$, whose inner nodes are all non-collider and in $M$,
we generate an edge in $\alpha(G,M)$, which preserves the (lack of) arrowheads
pointing to $i$ and $j$ in $\pi$; We apply this repeatedly until no new edges
are being generated, and then remove all the nodes in $M$; for more details of
this algorithm, refer to Richardson and Spirtes (2002); Sadeghi (2013). The
following result is well-known (Richardson and Spirtes, 2002; Sadeghi, 2013):

###### Lemma 29

For a graph $G$ and disjoint node sets $A$, $B$, $C$, and $M$, it holds that

$A\,\mbox{$\perp$}\,B\,|\,C\text{ in }\alpha(G,M)\iff
A\,\mbox{$\perp$}\,B\,|\,C\text{ in }G.$

We shall need the following corollary of this result:

###### Lemma 30

Suppose that a distribution $P$ is Markovian to the graph $G$. Then
$\alpha(P,M)$ is Markovian to $\alpha(G,M)$.

Proof  $P$ being Markovian to $G$ implies that $A\,\mbox{$\perp$}\,B\,|\,C$ in
$G$ implies that $A\mbox{$\>\perp\perp$ }B\,|\,C$.
$A\,\mbox{$\perp$}\,B\,|\,C$ in $\alpha(G,M)$ implies that $(A\cup B\cup
C)\cap M=\varnothing$, and also $A\,\mbox{$\perp$}\,B\,|\,C$ (by Lemma 29).
$(A\cup B\cup C)\cap M=\varnothing$ implies that $A\mbox{$\>\perp\perp$
}B\,|\,C$ exists in $\mathcal{J}(\alpha(P,M))$. Therefore,
$A\,\mbox{$\perp$}\,B\,|\,C$ in $\alpha(G,M)$ implies $A\mbox{$\>\perp\perp$
}B\,|\,C$ exists in $\mathcal{J}(\alpha(P,M))$.

We are now ready to provide the proof of Theorem 27.

Proof of Theorem 27 Consider the augmented graph $G_{0}(X,\epsilon)$ and the
joint distribution $P_{X,\epsilon}$. Consider the ordering similar to the
ordering in the SCM for $X_{i}$s, and, for $\epsilon_{i}$s, let
$X_{i+1}>\epsilon_{i}>X_{i}$. We show that $P_{X,\epsilon}$ satisfies the
ordered local Markov property w.r.t. this ordering in $G_{0}(X,\epsilon)$.
Hence by Lemma 28, we obtain that $P_{X,\epsilon}$ is Markovian to
$G_{0}(X,\epsilon)$. Consider a node in $G_{0}(X,\epsilon)$. We have two
cases:

First, assume that this node is of $\epsilon$ form, i.e., say it is
$\epsilon_{i}$. Consider also $A\subseteq\mathrm{pst}(\epsilon_{i})$. We have
that $\mathrm{mb}(\epsilon_{i},A)=\\{\epsilon_{j}\in A:\hskip
3.50006ptX_{j}\in\mathrm{dis}(X_{i})\text{ in }G_{0}\\}$. If
$\mathrm{mb}(\epsilon_{i},A)=A$, then $\epsilon_{i}\mbox{$\>\perp\perp$
}[A\setminus(\mathrm{mb}(\epsilon_{i},A)\cup\\{\epsilon_{i}\\})]\,|\,\mathrm{mb}(\epsilon_{i},A)$
is trivial; otherwise there is no edge between $\mathrm{mb}(\epsilon_{i},A)$
and $A\setminus(\mathrm{mb}(\epsilon_{i},A)\cup\\{\epsilon_{i}\\})$ in
$G_{0}(X,\epsilon)$, which, by joint independence of such $\epsilon_{j}$,
implies that
$\\{\epsilon_{i}\\}\cup\mathrm{mb}(\epsilon_{i},A)\mbox{$\>\perp\perp$
}A\setminus(\mathrm{mb}(\epsilon_{i},A)\cup\\{\epsilon_{i}\\})$. This, by the
weak union property, implies

$\epsilon_{i}\mbox{$\>\perp\perp$
}[A\setminus(\mathrm{mb}(\epsilon_{i},A)\cup\\{\epsilon_{i}\\})]\,|\,\mathrm{mb}(\epsilon_{i},A).$

Secondly, assume that this node is of $X$ form, i.e., say it is $X_{i}$.
Consider also
$A\subseteq\mathrm{pst}(X_{i})=(\epsilon_{i},X_{i+1},\epsilon_{i+1},\dots,X_{n},\epsilon_{n})$.
We have that $\mathrm{mb}(X_{i},A)=\\{\epsilon_{i}\\}\cup\\{X_{j}:\hskip
3.50006ptX_{j}\in\mathrm{pa}_{G_{0}[A]}(X_{i})\\}$. However, given
$\mathrm{mb}(X_{i},A)$, we have that $X_{i}$ is deterministic; hence, it is
independent of all disjoint random vectors including
$A\setminus(\mathrm{mb}(X_{i},A)\cup\\{X_{i}\\})$.

Finally, since the inner nodes of $\langle
X_{i},\epsilon_{i},\epsilon_{j},X_{j}\rangle$ are non-collider in
$\alpha(G_{0}(X,\epsilon)$, it can be seen that
$\alpha(G_{0}(X,\epsilon),\epsilon)=G_{0}$. Hence, $P_{X,\epsilon}$ being
Markovian to $G_{0}(X,\epsilon)$, by Lemma 30, implies that $P$ is Markovian
to $G_{0}$.

###  6.2 Conditions and assumptions for structure learning of SCMs

The general setting for structure learning for SCMs is the same as in the
previous sections, and, in fact, the case of SCM could be considered a special
case of the theory presented above: We start by assuming the existence of an
_unknown_ SCM $\mathfrak{C}$ associated to an _unknown_ causal graph $G_{0}$
as described in Section 2.5. For structure learning (from observational data),
we find a graph that belongs to the Markov equivalence class of $G_{0}$. As
discussed, the SCM $\mathfrak{C}$ entails a joint distribution $P$, which is
still unknown. Therefore, the relationships can be illustrated in the
following diagram:

$G_{0}\leftarrow\mathfrak{C}\rightarrow
P\stackrel{{\scriptstyle\text{conditional
independence}}}{{\rightarrow}}\mathcal{J}(P)\stackrel{{\scriptstyle\text{Algorithm}}}{{\rightarrow}}G(P)\stackrel{{\scriptstyle\text{Markov
equivalent}}}{{\sim}}G_{0}$

We begin our discussion with a few examples. In general, the independence
models of the SCMs are not faithful to $G_{0}$. Although there are many
examples where faithfulness fails, the following simple and perhaps familiar
example will help to motivate further considerations regarding the converse
pairwise Markov property.

######  Example 31 (Failure of faithfulness)

Consider the following SCM where $2\mbox{$\hskip 0.50003pt\frac{\hskip
4.89998pt\hskip 4.89998pt}{\hskip 4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip
1.07639pt$}1$, and $2$ is the only parent of $1$. Suppose $X_{2}=\epsilon_{2}$
and $X_{1}=X_{2}\oplus\epsilon_{1}\bmod 2$, where $\epsilon_{2}$ and
$\epsilon_{1}$ are independent Bernoulli random variables with parameter
$p=\tfrac{1}{2}$. It is easy to verify that $X_{2}$ is also independent of
$X_{1}$.

For a continuous example, we exploit of the invariance of Lebesgue measure on
the circle. Take $\epsilon_{1}$ and $X_{2}=\epsilon_{2}$ to be independent
continuous real-valued random variables. Let $F$ and $G$ be the cumulative
distribution functions for $X_{2}$ and $\epsilon_{1}$, respectively. Set
$X_{1}=F(X_{2})\oplus G(\epsilon_{1})\bmod 1$. It is easy to verify that
$X_{2}$ is independent of $X_{1}$.

Motivated by Example 31 and the elementary fact that a random rotation that is
independent of a standard bivariate normal remains independent of the randomly
rotated bivariate normal, and more generally the connection between symmetries
and independence (Dawid, 1985), we have the following lemma.

###### Lemma 32

Consider the SCM with associated graph $2\mbox{$\hskip 0.50003pt\frac{\hskip
4.89998pt\hskip 4.89998pt}{\hskip 4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip
1.07639pt$}1$, so that $2$ is the only parent of $1$. Suppose that
$X_{2}=\epsilon_{2}$, $X_{1}=\phi_{1}(X_{2},\epsilon_{1})$ and that
$\epsilon_{2}$ and $\epsilon_{1}$ are independent. Then $X_{2}$ is independent
of $X_{1}$ if and only

$\phi_{1}(x_{2},\epsilon_{1})\stackrel{{\scriptstyle d}}{{=}}X_{1}$ (3)

for almost every $x_{2}\in\mathcal{X}_{2}$.

Note that (3) is easily satisfied if $\phi_{1}$ is actually a function of
$\epsilon_{1}$ alone. In (3), it may be helpful to think of $x_{2}$ as
indexing (distinct) ways of generating a random variable with law $X_{1}$,
given the randomization $\epsilon_{1}$.

Proof of Lemma 32 Let $S_{2}\subset\mathcal{X}_{2}$ and
$S_{1}\subset\mathcal{X}_{2}$ be measurable subsets. Let $Q_{X_{2}}$ and
$Q_{\epsilon_{1}}$ be the laws of $X_{2}$ and $\epsilon_{1}$, respectively.
Since $2\mbox{$\hskip 0.50003pt\frac{\hskip 4.89998pt\hskip 4.89998pt}{\hskip
4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}1$, and $X_{2}$ and
$\epsilon_{1}$ are independent, we have

$\displaystyle\mathbb{P}(X_{1}\in S_{1},X_{2}\in S_{2})$ $\displaystyle=$
$\displaystyle\mathbb{P}(\phi_{1}(X_{2},\epsilon_{1})\in S_{1},X_{2}\in
S_{2})$ $\displaystyle=$
$\displaystyle\int\int\mathbf{1}[\phi_{1}(x_{2},e_{1})\in
S_{1})]\mathbf{1}[x_{2}\in S_{2}]dQ_{X_{2}}(x_{2})dQ_{\epsilon_{1}}(e_{1})$
$\displaystyle=$
$\displaystyle\int_{S_{2}}\mathbb{P}(\phi_{1}(x_{2},\epsilon_{1})\in
S_{1})dQ_{X_{2}}(x_{2}).$

Thus if (3) holds, we have

$\displaystyle\mathbb{P}(X_{1}\in S_{1},X_{2}\in S_{2})$ $\displaystyle=$
$\displaystyle\int_{S_{2}}\mathbb{P}(X_{1}\in S_{1})dQ_{X_{2}}(x_{2})$
$\displaystyle=$ $\displaystyle\mathbb{P}(X_{1}\in S_{1})Q_{X_{2}}(S_{2})$
$\displaystyle=$ $\displaystyle\mathbb{P}(X_{1}\in S_{1})\mathbb{P}(X_{2}\in
S_{2})$

and the desired independence follows.

If $X_{2}$ and $X_{1}$ are independent, then

$\mathbb{P}(X_{1}\in S_{1})=\frac{1}{\mathbb{P}(X_{2}\in
S_{2})}\int_{S_{2}}\mathbb{P}(\phi_{1}(x_{2},\epsilon_{1}))\in
S_{1})dQ_{X_{2}}(x_{2})$

for all measurable subsets $S_{2}$ with $Q_{X_{2}}(S_{2})>0$. By setting

$S_{2}=\\{x_{2}\in\mathcal{X}_{2}:\mathbb{P}(\phi_{1}(x_{2},\epsilon_{1})\in
S_{1})>\mathbb{P}(X_{1}\in S)\\},$

we see that $Q_{X_{2}}(S_{2})=0$. Hence together with reversing the inequality
in the definition of $S_{2}$, we obtain (3).

In fact, the joint distributions of SCMs may not satisfy any of the axioms for
faithfulness, presented in Proposition 4, and discussed in the Sections 2.2
and 2.3. For a counter-example and a thorough discussion on the intersection
property, see Peters (2015). For an example of an SCM not satisfying
singleton-transitivity, see Example 18. For counter-examples for other axioms,
we provide the following examples:

######  Example 33 (Failure of composition and ordered upward-stability)

Consider the following SCM associated to the graph $G_{0}$ in Figure 6:

$X_{3}=\epsilon_{3};\hskip 6.99997ptX_{2}=\epsilon_{2};\hskip
6.99997ptX_{1}=X_{2}\oplus X_{3}\oplus\epsilon_{1}\bmod 2;$

where $\epsilon_{1},\epsilon_{2},$ and $\epsilon_{3}$ are independent
Bernoulli random variables, $\epsilon_{2}$ and $\epsilon_{3}$ with parameter
$\tfrac{1}{2}$, and $\epsilon_{1}$ with parameter $\tfrac{1}{3}$.

It is easy to verify that $X_{1}\mbox{$\>\perp\perp$ }X_{2}$, and
$X_{1}\mbox{$\>\perp\perp$ }X_{3}$, but
$X_{1}\nolinebreak{\not\mbox{$\>\perp\perp$ }}(X_{2},X_{3})$ and
$X_{1}\nolinebreak{\not\mbox{$\>\perp\perp$ }}X_{2}\,|\,X_{3}$. Hence this is
an example for an SCM not satisfying the composition property or ordered
upward-stability.

$1$$2$$3$ Figure 6: A directed acyclic graph $G_{0}$.

######  Example 34 (Failure of ordered downward-stability)

Consider a complete DAG with nodes $(1,2,3)$. Let $\epsilon_{3}=(N_{3},U_{3})$
and $\epsilon_{2}=(U_{2},V_{2})$, where $N_{3},U_{3},U_{2}$, and $V_{2}$ are
all independent, and $N_{3}$ is Poisson distributed, and $U_{3},U_{2}$ and
$V_{2}$ are uniformly distributed on $[0,1]$. Let $X_{3}=\epsilon_{3}$. Let
$X_{2}=\phi_{2}(X_{3},\epsilon_{2})=(\psi_{2}(N_{3},U_{2}),V_{2})$, where
$\psi_{2}$ is a deterministic function such that $\psi_{2}(n_{3},U_{2})$ is
uniformly distributed on the integers $\\{1,\ldots,n_{3}+1\\}$. Let
$X_{1}=\phi_{1}(X_{3},X_{2})=(N_{3},V_{2})$. Clearly, $X_{2}$ is not
independent of $X_{3}$. However, conditional on $X_{1}$, we have that $X_{2}$
is independent of $X_{3}$.

An important property used in the results of previous section is converse
pairwise Markov property. Here, we are mainly concerned with providing
conditions for verifying this property. For an SCM $\mathcal{C}$, we provide
an assumption on the joint distribution of $\mathcal{C}$ that implies the
converse pairwise Markov property. Consider the following extension of Lemma
32.

###### Proposition 35

Consider an SCM, where $j\mbox{$\hskip 0.50003pt\frac{\hskip 4.89998pt\hskip
4.89998pt}{\hskip 4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}i$. Write
$X_{i}=\phi_{i}(X_{\mathrm{pa}(i)\setminus\\{j\\}},X_{j},\epsilon_{i})$.
Suppose that $\mathrm{an}(i,j)\not=\emptyset$. Then $i\mbox{$\>\perp\perp$
}j\,|\,\mathrm{an}(i,j)$ if and only if for almost all
$x_{\mathrm{an}(i,j)}\in\mathcal{X}_{\mathrm{an}(i,j)}$ the conditional law of
$X_{i}$ given $X_{\mathrm{an}(i,j)}=x_{\mathrm{an}(i,j)}$ is the same as the
law of $\phi_{i}(x_{\mathrm{pa}(i)\setminus\\{j\\}},x_{j},\epsilon_{i})$ for
almost all $x_{j}\in\mathcal{X}_{j}$ in the support of the conditional
distribution of $X_{j}$ given $x_{\mathrm{an}(i,j)}$.

Proof  Let $\mathcal{F}_{j}$ and $\mathcal{F}_{i}$ be the $\sigma$-algebras
for $\mathcal{X}_{j}$ and $\mathcal{X}_{i}$. Let
$D:\mathcal{X}_{\mathrm{an}(i,j)}\times(\mathcal{F}_{j},\mathcal{F}_{i})\to[0,1]$
be a regular conditional distribution for $(X_{j},X_{i})$ given
$X_{\mathrm{an}(i,j)}$. Fix
$x_{\mathrm{an}(i,j)}\in\mathcal{X}_{\mathrm{an}(i,j)}$. All the parents of
$i$ are included in $\mathrm{an}(i,j)$, except $j$. Let $Q_{i}$ and $Q_{j}$ be
marginal distributions of $X_{i}$ and $X_{j}$ under
$D_{x_{\mathrm{an}}(i,j)}=D(x_{\mathrm{an}}(i,j),\cdot,\cdot)$. Following the
proof of Lemma 32, since $j\mbox{$\hskip 0.50003pt\frac{\hskip 4.89998pt\hskip
4.89998pt}{\hskip 4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}i$ and
the graph is ancestral, we have that $\epsilon_{i}$, with law
$Q_{\epsilon_{i}}$, is independent of $(X_{\mathrm{an}(i,j)},X_{j})$. Thus for
$S_{j}\in\mathcal{F}_{j}$ and $S_{i}\in\mathcal{F}_{i}$, we have

$\displaystyle D_{x_{\mathrm{an}(i,j)}}(S_{j},S_{i})$ $\displaystyle=$
$\displaystyle\int\int_{S_{j}}\mathbf{1}[\phi_{i}(x_{{\mathrm{pa}(i)\setminus\\{j\\}}},x_{j},e_{i})\in
S_{i})]dQ_{j}(x_{j})dQ_{\epsilon_{i}}(e_{i})$ $\displaystyle=$
$\displaystyle\int_{S_{j}}\mathbb{P}(\phi_{i}(x_{{\mathrm{pa}(i)\setminus\\{j\\}})},x_{j},\epsilon_{i})\in
S_{i})dQ_{j}(x_{j}).$

Thus, if

$Q_{i}(S_{i})=\mathbb{P}(\phi_{i}(x_{{\mathrm{pa}(i)\setminus\\{j\\}})},x_{j},\epsilon_{i})\in
S_{i})$ (4)

for all $Q_{j}$-almost all $x_{j}\in\mathcal{X}_{j}$, then

$D_{x_{\mathrm{an}(i,j)}}(S_{j},S_{i})=Q_{j}(S_{j})Q_{i}(S_{i})$

as desired.

A routine variation of the rest of the proof of Lemma 32, gives that the
condition on $\phi_{i}$ expressed in (4) is also necessary for the conditional
independence of $X_{j}$ and $X_{i}$.

Proposition 35 includes Lemma 32 by making the suitable interpretations in the
case that $\mathrm{an}(i,j)=\emptyset$.

Proposition 35 suggests the following condition that implies the converse
pairwise Markov property, in the case that true causal graph is a DAG. We say
that the (joint distribution) of an SCM satisfies _positivity_ if
$\mathbb{P}(X_{B}\in S|X_{A}=x_{A})>0$ almost surely, for every set of nodes
$B$ disjoint from $A$ and every measurable $S$ for which $\mathbb{P}(X_{B}\in
S)>0$, for almost every $x_{A}\in\mathcal{X}_{A}$.

Observe that each function $\phi$ in an SCM has the form

$\phi:\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{n}\times\mathcal{E}\to\mathcal{X}_{n+1},$

which is endowed with a product probability measure $\mu\otimes Q_{\epsilon}$,
the joint law of the parents and exogenous variable on
$\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{n}\times\mathcal{E}$, and a
probability measure $\nu=(\mu\otimes Q_{\epsilon})\circ\phi^{-1}$ on
$\mathcal{X}_{n+1}$, the law of the child. Let $\mu^{j}$ be the projection of
$\mu$ to space

$\mathcal{X}^{j}:=\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{j-1}\times\mathcal{X}_{j+1}\times\cdots\times\mathcal{X}_{n}.$

Let $\epsilon$, $X=(X_{1},\ldots,X_{n})$, and $X_{j}$ have laws
$Q_{\epsilon}$, $\mu$, and $\mu_{j}$ respectively. We say that $\phi$ has
_non-constant fibers_ if for all $1\leq j\leq n$ there is some
$F\subset\mathcal{X}^{j}$ with positive $\mu^{j}$-measure for each

$x^{j}=(x_{1},\ldots,x_{j-1},x_{j+1},\ldots,x_{n})\in F$

and there is some $S\subset\mathcal{X}_{n+1}$ such that the function
$k:\mathcal{X}_{j}\to[0,1]$ given by

$k(x_{j})=\mathbb{P}(\phi(x_{1},\ldots,x_{j},\ldots,x_{n},\epsilon)\in S)$

is non-constant $\mu_{j}$-almost surely. We say that an SCM has _non-constant
fibers_ if every function in the SCM has non-constant fibers.

###### Remark 36

Note that in the proof of Proposition 35, equality (4) fails if $\phi_{i}$ has
non-constant fibers and the SCM satisfies positivity.

###### Remark 37

It is easy to see that additive noise models with the form

$\phi(x,\epsilon)=h(x)+\epsilon$

will have non-constant fibers under the mild condition that for any $1\leq
j\leq n$, and any fixed $x_{1},\ldots,x_{j-1},x_{j+1},\ldots,x_{n}$, the
function

$g(x_{j})=h(x_{1},\ldots,x_{j},\ldots x_{n})$

is non-constant almost surely; assume for simplicity that all the relevant
conditional distributions are equivalent to Lebesgue measure. Hence, by Remark
36, these additive noise models will satisfy the converse pairwise Markov
property, provided that the true causal graph is a DAG.

Recall that if $i\mbox{$\hskip 0.59998pt\prec\\!\\!\\!\\!\\!\frac{\hskip
4.89998pt\hskip 4.89998pt}{\hskip 4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip
1.07639pt$}j$, then $\epsilon_{i}$ and $\epsilon_{j}$ are dependent. In order
to deal with the possibility of arcs, we have the following restriction that
allows us to preserve dependence. We say that
$\phi:\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{n}\times\mathcal{E}\to\mathcal{X}_{n+1}$
in an SCM is _noise injective_ if for each fixed $x_{1},\ldots,x_{n}$, the
function $e\mapsto\phi(x_{1},\ldots,x_{n},e)$ is injective.

###### Lemma 38

Consider an SCM, where $j\mbox{$\hskip
0.59998pt\prec\\!\\!\\!\\!\\!\frac{\hskip 4.89998pt\hskip 4.89998pt}{\hskip
4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}i$. If both $\phi_{i}$ and
$\phi_{j}$ are noise injective, then $i\nolinebreak{\not\mbox{$\>\perp\perp$
}}j\,|\,\mathrm{an}(i,j)$.

Proof  Fix $x_{\mathrm{an}(i,j)}$. Since $j\mbox{$\hskip
0.59998pt\prec\\!\\!\\!\\!\\!\frac{\hskip 4.89998pt\hskip 4.89998pt}{\hskip
4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}i$, all the parents of $i$
and $i$ are included in $\mathrm{an}(i,j)$ and $\epsilon_{i}$ and
$\epsilon_{j}$ are dependent. The conditional distribution of $(X_{i},X_{j})$
given $X_{\mathrm{an}(i,j)}=x_{\mathrm{an}(i,j)}$ is the law of

$\big{(}(\phi_{i}(x_{\mathrm{pa}(i)},\epsilon_{i}),\phi_{j}(x_{\mathrm{pa}(j)},\epsilon_{j})\big{)},$

since the graph is ancestral and the joint law of
$(\epsilon_{i},\epsilon_{j})$ remains the same under this conditioning. Since
$\phi_{i}$ and $\phi_{j}$ are noise injective, it follows that
$\phi_{i}(x_{\mathrm{pa}(i)},\epsilon_{i})$ and
$\phi_{j}(x_{\mathrm{pa}(j)},\epsilon_{j})$ are dependent if and only if
$\epsilon_{i}$ and $\epsilon_{j}$ are dependent.

From the proof of Lemma 38, we see that noise injectivity is a condition which
allows us to preserve the dependencies of the noises; in general if the random
variables $\epsilon_{i}$ and $\epsilon_{j}$ are dependent, we cannot conclude
(like independence) that functions of $\epsilon_{i}$ and $\epsilon_{j}$ will
remain dependent. It is easy to verify that noise injectivity is satisfied by
the additive noise models.

###### Corollary 39

The additive noise models of Remark 37 satisfy the converse pairwise
assumption, without the assumption that the true causal graph is a DAG.

Proof  Immediate from Remark 37 and Lemma 38.

We also say that an SCM is _noise injective_ if every function in the SCM is
noise injective. Notice that these conditions do not depend on the structure
of the causal graph.

###### Corollary 40

Any SCM satisfying positivity, with non-constant fibers, and noise injectivity
has the converse pairwise Markvov property; furthermore, if the true causal
graph is a DAG, then the noise injectivity assumption may be dropped.

Proof  Immediate from Proposition 35, Lemma 38, and Remark 36.

Hence, under some additional assumptions, the SCMs are not only Markovian, but
minimal Markovian to their true causal graph:

###### Corollary 41

Consider an SCM with positivity, non-constant fibers, noise injectivity, and
ordered upward- and downward-stability w.r.t. $G_{0}$. Then $P$ is minimally
Markovian to $G_{0}$; furthermore, if the true causal graph is a DAG, then the
noise injectivity assumption may be dropped.

Proof  The proof follows from the Corollary 15 together with Theorem 27 and
Corollary 40.
We can now present our main result for structure learning for SCMs:

###### Theorem 42

Consider an SCM with positivity, non-constant fibers, and a distribution $P$,
which satisfies ordered upward- and downward-stability w.r.t. the causal graph
$G_{0}$. Consider natural structure-learning algorithms.

  1. 1.

If $P$ is path-stable, and the SCM is noise injective, then $G(P)$, an output
of a natural structure-learning algorithm, is Markov equivalent to $G_{0}$.

  2. 2.

If $G_{0}$ is a DAG, and $P$ is V-stable, then a DAG-output of a natural
structure-learning algorithm is Markov equivalent to $G_{0}$.

Proof  The proof follows from Theorem 25, Theorem 27, and Corollary 40.

In Theorem 42, the most difficult condition to verify are ordered stabilities,
which may not be directly testable.

###  6.3 Specialization to specific SCMs

We consider some more restrictive assumptions on an SCM that will imply the
converse pairwise Markov property.

####  6.3.1 Discrete random variables

For discrete distributions, we have the following simple sufficient condition
for an SCM to satisfy the converse pairwise Markov property. We say that an
SCM is _discrete_ if both the endogenous and exogenous random variables are
discrete.

###### Proposition 43

Consider an SCM that is discrete and satisfies positivity. Suppose that for
all the nodes $i$, the cardinality of the support of $\epsilon_{i}$ is
strictly less than the support of $X_{i}$.

  1. 1.

If $P$ is path-stable, and the SCM is noise injective, then $G(P)$, an output
of a natural structure-learning algorithm, is Markov equivalent to $G_{0}$.

  2. 2.

If $G_{0}$ is a DAG, and $P$ is V-stable, then a DAG-output of a natural
structure-learning algorithm is Markov equivalent to $G_{0}$.

Proof From Theorems 25 and 27 it suffices to verify the converse pairwise
Markov property for a pair of adjacent nodes $i$ and $j$. Lemma 38 takes the
care of the case where $i\mbox{$\hskip
0.59998pt\prec\\!\\!\\!\\!\\!\frac{\hskip 4.89998pt\hskip 4.89998pt}{\hskip
4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}j$. Suppose that
$i\mbox{$\hskip 0.50003pt\frac{\hskip 4.89998pt\hskip 4.89998pt}{\hskip
4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip 1.07639pt$}j$. If the support of
$\epsilon_{i}$ is strictly less than the support of $X_{i}$, then positivity
implies that (4) is not satisfied so that Proposition 35 gives that the
conditional independence statement $i\mbox{$\>\perp\perp$
}j\,|\,\mathrm{an}(i,j)$ does not hold.

The assumption on the cardinality of the supports has the interpretation that
information at a node is not mostly noise.

In the next lemma, we show that under some assumptions, the failure of the
converse pairwise Markov property for $j\mbox{$\hskip 0.50003pt\frac{\hskip
4.89998pt\hskip 4.89998pt}{\hskip 4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip
1.07639pt$}i$, forces the uniform distribution on both $X_{i}$ and
$\epsilon_{i}$. Let
$\phi:\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{n}\times\mathcal{E}\to\mathcal{X}_{n+1}$
be a noise injective function in a discrete SCM. Given
$x_{1},\ldots,x_{j},\ldots,x_{n}$, let
$\Phi_{x_{j}}^{x_{1},\ldots,x_{j-1},x_{j+1},\ldots,x_{n}}=\Phi_{x_{j}}^{x^{j}}$
denote the inverse of $\phi$. Suppose that for all choices of $1\leq j\leq n$
and $x^{j}$ there exists $x_{n+1}^{*}\in\mathcal{X}_{n+1}$ such that

$\\{\Phi_{x_{j}}^{x^{j}}(x_{n+1}^{*}):x_{j}\in\mathcal{X}_{j}\\}=\mathcal{E}.$

Then we say that $\phi$ is _noise surjective_.

###### Proposition 44

Consider the following SCM, where $j\mbox{$\hskip 0.50003pt\frac{\hskip
4.89998pt\hskip 4.89998pt}{\hskip 4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip
1.07639pt$}i$ and

$X_{i}=\phi_{i}(X_{\mathrm{pa}(i)\setminus\\{j\\}},X_{j},\epsilon_{i}).$

Suppose that the joint distribution is discrete and satisfies positivity.
Suppose also that $\phi_{i}$ is noise injective and surjective. If
$i\mbox{$\>\perp\perp$ }j\,|\,\mathrm{an}(i,j)$, then $\epsilon_{i}$ and
$X_{j}$ are both uniformly distributed and $\mathcal{E}_{i}$ and
$\mathcal{X}_{i}$ have the same cardinality.

Proof  Fix $x_{\mathrm{an}(i,j)}$. Note that all the parents of $i$, save $j$,
are included in $\mathrm{an}(i,j)$, By Proposition 35, we have

$\displaystyle\mathbb{P}(X_{i}=x_{i}|X_{\mathrm{an}(i,j)}=x_{\mathrm{an}(i,j)})$
$\displaystyle=$
$\displaystyle\mathbb{P}(\phi_{i}(x_{{\mathrm{pa}(i)\setminus\\{j\\}})},x_{j},\epsilon_{i})=x_{i})$
$\displaystyle=$
$\displaystyle\mathbb{P}(\epsilon_{i}=\Phi_{x_{j}}^{x_{\mathrm{pa}(i)\setminus\\{j\\}}}(x_{i}))$

for all $x_{i}\in\mathcal{X}_{i}$ and all $x_{j}\in\mathcal{X}_{j}$, by
positivity. By noise surjectivity, substituting $x_{i}=x_{i}^{*}$, we deduce
that $\epsilon_{i}$ is uniformly distributed, with finite support
$\mathcal{E}_{i}$. Thus

$\mathbb{P}(X_{i}=x_{i}|X_{\mathrm{an}(i,j)}=x_{\mathrm{an}(i,j)})=\frac{1}{\\#\mathcal{E}_{i}}$

for all $x_{i}$. Hence it follows that $X_{i}$ is also uniformly distributed.

###### Corollary 45

Consider a discrete SCM satisfying positivity. Suppose that all the functions
are noise injective and noise surjective. If each of the exogenous random
variables are not uniformly distributed, then the converse pairwise Markov
property is satisfied.

Proof  Immediate from Proposition 44 and Lemma 38.

###### Corollary 46

Consider an SCM that is discrete and satisfies positivity. Suppose that all
the functions are noise injective and noise surjective. Assume each of the
exogenous random variables are not uniformly distributed.

  1. 1.

If $P$ is path-stable, then $G(P)$, an output of a natural structure-learning
algorithm, is Markov equivalent to $G_{0}$.

  2. 2.

If $G_{0}$ is a DAG, and $P$ is V-stable, then a DAG-output of a natural
structure-learning algorithm is Markov equivalent to $G_{0}$.

Proof  The previous corollary assures us that the converse pairwise Markov
property is satisfied, so that the result follows from Theorems 25 and 27.

Returning to Example 31, it is easy to verify that the simple SCM is both
noise injective and surjective. Notice that if $\epsilon_{1}$ is chosen with
Bernoulli parameter $p\not=\tfrac{1}{2}$, and all other choices are left the
same, then $X_{2}$ is no longer independent of $X_{1}$. Corollaries 45 and 46
suggest that if it is possible to avoid or exclude the possibility that the
exogenous random variables are uniformly distributed, then a natural
structure-learning algorithm is more likely to work.

####  6.3.2 Continuous random variables

We note that the modular addition in Example 31 is not continuous. We show
that under some regularity conditions, up to a change of coordinates, only
trivial functions can result in independence. Given
$\phi:\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{n}\times\mathcal{E}\to\mathcal{X}_{n+1}$,
we say that $\psi$ is a _$j$ -change of coordinates_ if there exists
$g:[-1/2,1/2]\to\mathcal{E}$ such that for all $x^{j}\in\mathcal{X}^{j}$,
there exists $h_{x^{j}}:\mathcal{X}_{n+1}\to[-1/2,1/2]$ such that if $U$ is
uniformly distributed on $[-1/2,1/2]$ and

$\psi(x_{j},u):=h_{x^{j}}\circ\phi(x_{1},\ldots,x_{j},\ldots,x_{n},g(u)),$

then $g(U)$ has the law of $\epsilon$ and $\psi(x_{j},\epsilon)$ is uniformly
distributed on $[-1/2,1/2]$ for all $x_{j}\in\mathcal{X}_{j}$. We say that
$\psi$ is _regular_ if for fixed $x_{j}$, the function
$\zeta(u)=\psi(x_{j},u)$ is injective and $\zeta(u)$ is monotone; note that
under these conditions an easy argument given in Lemma 47 shows that $\psi$ is
a _reflection_ of the form $\psi(x_{j},u)=u$ or $\psi(x_{j},u)=-u$ for all
$x_{j}\in\mathcal{X}_{j}$ and all $u\in[-1/2,1/2]$. We say that $\phi$ is
_non-trivial_ if for each $j$, there does not exist a regular $j$-change of
coordinates. We say that an SCM is _non-trivial_ if every function in the SCM
is non-trivial. We say that a function $\phi$ in an SCM is _noise monotone_ if
for all $x_{1},\ldots,x_{n}$, the function
$e\mapsto\phi(x_{1},\ldots,x_{n},e)\in\mathcal{X}_{n+1}\subset\mathbb{R}$ is
monotone in $e\in\mathcal{E}\subset\mathbb{R}$.

###### Proposition 47

Consider the following SCM, where $j\mbox{$\hskip 0.50003pt\frac{\hskip
4.89998pt\hskip 4.89998pt}{\hskip 4.89998pt}\\!\\!\\!\\!\\!\succ\\!\hskip
1.07639pt$}i$ and

$X_{i}=\phi_{i}(X_{\mathrm{pa}(i)\setminus\\{j\\}},X_{j},\epsilon_{i}).$

Suppose that $\phi_{i}$ is noise injective and noise monotone. Also assume
that $\epsilon_{i}$ is a continuous random variable, and that for almost all
$x_{\mathrm{an}(i,j)}$, the conditional distribution law of $X_{i}$ given
$X_{\mathrm{an}(i,j)}$ is continuous with respect to Lebesgue measure. If
$i\mbox{$\>\perp\perp$ }j\,|\,\mathrm{an}(i,j)$, then $\phi_{i}$ admits a
$j$-regular change of coordinates and any such change of coordinates is a
reflection.

Proof  Recall that if $F$ is the cumulative distribution function for a
continuous random variable $Z$, then $F$ is non-decreasing and
$F(Z)-\tfrac{1}{2}$ is uniformly distributed on $[-1/2,1/2]$. In addition, the
inverse transform method tells us that $F^{-1}(U+\tfrac{1}{2})$ has law $Z$ if
$U$ is uniformly distributed on $[-1/2,1/2]$. Hence by Proposition 35, and the
absolute continuity assumptions, it follows that $\phi_{i}$ has a $j$-regular
change of coordinates $\psi$. Fix $x_{j}\in\mathcal{X}_{j}$ and write
$\psi(x_{j},u)=\psi(u)$. If $\psi$ is increasing in $u$, then for
$z\in[-1/2,1/2]$, we have for $U$ uniformly distributed on $[-1/2,1/2]$ that

$z+1/2=\mathbb{P}(\psi(U)\leq
z)=\mathbb{P}(U\leq\psi^{-1}(z))=\psi^{-1}(z)+1/2,$

from which it follows that $\psi(x_{j},z)=z$. If $\psi$ is decreasing, then a
similar argument gives that $\psi(x_{j},z)=-z$.

###### Corollary 48

If the law of an SCM is given by a jointly continuous distribution, and the
SCM is noise injective and monotone, and is non-trivial, then it satisfies the
converse pairwise Markov property. Moreover,

  1. 1.

If $P$ is path-stable, then $G(P)$, an output of a natural structure-learning
algorithm, is Markov equivalent to $G_{0}$.

  2. 2.

If $G_{0}$ is a DAG, and $P$ is V-stable, then a DAG-output of a natural
structure-learning algorithm is Markov equivalent to $G_{0}$.

Proof  The converse pairwise Markov property is immediate from Proposition 47
and Lemma 38. Hence the latter assertions that a natural structure-learning
algorithm works follow from Theorems 25 and 27.

##  7 Summary and discussion

We formalized the problem of structure learning from independence statements
to find a graph that is Markov equivalent to the “true causal graph,” which is
the unknown graph to which the distribution is assumed to be Markovian. In
fact, all the results presented here are also correct for an abstract
independence model $\mathcal{J}$ instead of a probability distribution $P$.

A main message of this paper is that an important property of constraint-based
structure-learning algorithms is to direct the edges of the skeleton of the
probability distribution $P$ so that ordered upward- and downward-stability
are satisfied by $P$ w.r.t. the generated graph. We call such algorithms a
natural constraint-based structure-learning algorithm. Among the conditions
that constitute the widely-used assumption of faithfulness, provided in
Proposition 4, ordered upward- and downward-stability are the only ones that
induce an ordering, which is what is used for directing the edges in structure
learning. Since, under faithfulness, ordered upward- and downward-stability
are necessary for the output of the algorithm, all exact structure-learning
algorithms that assume faithfulness in the literature are members of the class
of natural structure-learning algorithms. Therefore, for any (newly) proposed
algorithm, to prove that the algorithm works, it is sufficient to test whether
$P$ satisfies ordered upward- and downward-stability w.r.t. its output.

Following this line of thinking, this result could lead to finding the
“optimal” natural constraint-based structure-learning algorithm. The idea is
that such an algorithm would be designed to solely direct the edges of the
skeleton to ensure an ordering w.r.t. which ordered upward- and downward-
stability are satisfied. Hence, for certain recorded independence statements,
one should perform some additional tests on whether independence is preserved
by certain additions to the conditioning set of those statements. The results
of such tests determine the direction of the edges of the output. This is a
direction for future work.

Moreover, we provided two assumptions, both of which are satisfied by
faithfulness, in order to ensure that the skeleton of the output of a natural
structure-learning algorithm is the same as the skeleton of the causal graph.
One condition is the converse pairwise Markov property and the other one is
satisfied by the assumption that the distribution satisfies ordered upward-
and downward-stability w.r.t. the causal graph. In order to ensure that
directing the edges of the skeleton of the output will result to a Markov
equivalent graph to the causal graph, a sufficient condition is path-stability
in the general case of directed ancestral graphs, and V-stability in the case
where we only deal with DAGs.

In contrast to well-known conditions in the literature such as orientation-
faithfulness, path- and V-stability are only properties of the distribution
and _not_ the causal graph. V-stability is also weaker than singleton-
transitivity, and consequently faithfulness. However, there are cases where
faithfulness is satisfied, but not path-stability. Path- and V-stability are
easier to test than singleton-transitivity as one needs to only test
independence for the endpoints of specific paths or V-configurations in
$\mathrm{sk}(P)$ respectively. In addition to singleton-transitivity, out of
the equivalent conditions to faithfulness, provided in Sadeghi (2017),
intersection and composition properties are not needed. In the case of a
Gaussian distribution, however, all these assumptions are automatically
satisfied, and therefore, our assumptions imply faithfulness.

It is commonplace to perform structure learning for SCMs. We have specialized
the theory for SCMs. For SCMs that we associate with directed ancestral
graphs, we showed that the main assumption of $P$ being Markovian to the
causal graph is always satisfied.

In addition, we provided simple sufficient conditions on the SCM that imply
the converse pairwise Markov property. Although converse pairwise Markov
property is indeed related to the causal graph, these sufficient conditions
are not. Our key condition of having non-constant fibers has a simple
interpretation when the function of an SCM has only one discrete endogenous
variable and one exogenous variable: there is a choice of two values for the
endogenous variable, whereby the distributions of the random variables given
by evaluating the function at these two fixed values and the exogenous random
variable are distinct. In the general case where the SCM may not be a DAG, we
need to impose a further strong injectivity condition on the functions.

The assumption of distributions (of the SCM) satisfying ordered upward- and
downward-stability w.r.t. the causal graph is, in principle, not directly
testable. However, in our primary study, we observe that it is difficult to
come up with natural examples of distributions that do not satisfy these
conditions when dealing with SCMs. Nevertheless, a thorough study of these
conditions for SCMs and other causal models is needed, and is subject of
future work.

Acknowledgments

We are grateful to Steffen Lauritzen for providing Example 18, to Joris Mooij
for stimulating discussions with the first author especially on the examples
involving modular arithmetic, and to Jonas Peters for hosting a first author’s
visit, during which some of the ideas used in this paper were discussed. We
are also truly thankful to the associate editor and three anonymous reviewers
for detailed and helpful comments.

## References

  * Ali et al. (2009) R. A. Ali, T. S. Richardson, and P. Spirtes.  Markov equivalence for ancestral graphs.  _Ann. Statist._ , 37(5B):2808–2837, 2009.
  * Andersson et al. (1997) S. A. Andersson, D. Madigan, and M. D. Perlman.  A characterization of markov equivalence classes for acyclic digraphs.  _Ann. Statist._ , 25(2):505–541, 1997.
  * Bongers et al. (2021) S. Bongers, P. Forré, J. Peters, and J. M. Mooij.  Foundations of structural causal models with cycles and latent variables.  _Ann. Statist._ , 49(5):2885–2915, 2021.  doi: 10.1214/21-aos2064.
  * Chang and Pollard (1997) J. T. Chang and D. Pollard.  Conditioning as disintegration.  _Statist. Neerlandica_ , 51(3):287–317, 1997\.  doi: 10.1111/1467-9574.00056.
  * Chickering (2003) D. M. Chickering.  Optimal structure identification with greedy search.  _J. Mach. Learn. Res._ , 3:507–554, 2003.  doi: 10.1162/153244303321897717.
  * Claassen and Heskes (2012) T. Claassen and T. Heskes.  A logical characterization of constraint-based causal discovery.  _CoRR_ , abs/1202.3711, 2012.  URL http://arxiv.org/abs/1202.3711.
  * Colombo and Maathuis (2014) D. Colombo and M. H. Maathuis.  Order-independent constraint-based causal structure learning.  _J. Mach. Learn. Res._ , 15:3741–3782, 2014.
  * Cox and Wermuth (1996) D. R. Cox and N. Wermuth.  _Multivariate Dependencies : models, analysis and interpretation_.  Chapman & Hall, London, United Kingdom, 1996.
  * Dawid (1979) A. P. Dawid.  Conditional independence in statistical theory (with discussion).  _J. R. Stat. Soc. Ser. B. Stat. Methodol._ , 41(1):1–31, 1979.
  * Dawid (1985) A. P. Dawid.  Invariance and independence in multivariate distribution theory.  _J. Multivariate Anal._ , 17(3):304–315, 1985\.  doi: 10.1016/0047-259X(85)90086-7.
  * Dawid (2000) A. P. Dawid.  Causal inference without counterfactuals.  _J. Amer. Statist. Assoc._ , 95(450):407–424, 2000.
  * Fallat et al. (2017) S. Fallat, S. Lauritzen, K. Sadeghi, C. Uhler, N. Wermuth, and P. Zwiernik.  Total positivity in markov structures.  _Annals of Statistics_ , 45(3):1152–1184, 2017\.
  * Forre and Mooij (2017) P. Forre and J. M. Mooij.  Markov properties for graphical models with cycles and latent variables.  _ArXiv preprint:1710.08775_ , 2017.
  * Forster et al. (2018) M. Forster, G. Raskutti, R. Stern, and N. Weinberger.  The frugal inference of causal relations.  _The British Journal for the Philosophy of Science_ , 69:821 – 848, 2018.
  * Geiger et al. (1990) D. Geiger, T. S. Verma, and J. Pearl.  Identifying independence in Bayesian networks.  _Networks_ , 20:507–534, 1990.
  * Glymour et al. (1987) C. Glymour, R. Scheines, P. Spirtes, and K. Kelly.  _Discovering Causal Structure_.  Academic Press, 1987.
  * Hitchcock (2018) C. Hitchcock.  Causal models.  In E. N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, fall 2018 edition, 2018.
  * Holland (1986) P. W. Holland.  Statistics and causal inference.  _J. Amer. Statist. Assoc._ , 81(396):945–970, 1986.  With discussion and a reply by the author.
  * Kiiveri et al. (1984) H. Kiiveri, T. P. Speed, and J. B. Carlin.  Recursive causal models.  _J. Aust. Math. Soc., Ser. A_ , 36:30–52, 1984.
  * Koster (1999) J. T. A. Koster.  On the validity of the markov interpretation of path diagrams of gaussian structural equations systems with correlated errors.  _Scand. J. Stat._ , 26(3):413–431, 1999.
  * Lauritzen (1996) S. L. Lauritzen.  _Graphical Models_.  Clarendon Press, Oxford, United Kingdom, 1996.
  * Lauritzen and Sadeghi (2018) S. L. Lauritzen and K. Sadeghi.  Unifying Markov properties for graphical models.  _Ann. Statist._ , 46(5):2251–2278, 2018.
  * Lauritzen and Spiegelhalter (1988) S. L. Lauritzen and D. J. Spiegelhalter.  Local computations with probabilities on graphical structures and their application to expert systems.  _J. R. Stat. Soc. Ser. B. Stat. Methodol._ , 50:157–224, 1988.
  * Lněnička and Matúš (2007) R. Lněnička and F. Matúš.  On Gaussian conditional independence structures.  _Kybernetika_ , 43(3):327–342, 2007.
  * Neapolitan (2004) R. E. Neapolitan.  _Learning Bayesian networks_.  Prentice Hall, Upper Saddle River, NJ, USA, 2004.
  * Pearl (1988) J. Pearl.  _Probabilistic Reasoning in Intelligent Systems : networks of plausible inference_.  Morgan Kaufmann Publishers, San Mateo, CA, USA, 1988.
  * Pearl (2009) J. Pearl.  _Causality: Models, Reasoning and Inference_.  Cambridge University Press, New York, NY, USA, 2nd edition, 2009.  ISBN 052189560X, 9780521895606.
  * Pearl and Paz (1985) J. Pearl and A. Paz.  _Graphoids: A Graph-based Logic for Reasoning about Relevance Relations_.  University of California (Los Angeles). Computer Science Department, 1985\.
  * Peters (2015) J. Peters.  On the intersection property of conditional independence and its application to causal discovery.  _J. Causal Inference_ , 3:97–108, 2015.
  * Peters et al. (2017) J. Peters, D. Janzing, and B. Schölkopf.  _Elements of Causal Inference - Foundations and Learning Algorithms_.  Adaptive Computation and Machine Learning Series. The MIT Press, Cambridge, MA, USA, 2017.
  * Ramsey et al. (2006) J. Ramsey, P. Spirtes, and J. Zhang.  Adjacency-faithfulness and conservative causal inference.  In _Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence_ , UAI’06, page 401–408, Arlington, Virginia, USA, 2006. AUAI Press.  ISBN 0974903922.
  * Raskutti and Uhler (2018) G. Raskutti and C. Uhler.  Learning directed acyclic graph models based on sparsest permutations.  _Stat_ , 7(1):e183, 2018.  doi: https://doi.org/10.1002/sta4.183.  e183 sta4.183.
  * Richardson (2003) T. Richardson.  Markov properties for acyclic directed mixed graphs.  _Scand. J. Stat._ , 30(1):145–157, 2003.
  * Richardson and Spirtes (2002) T. S. Richardson and P. Spirtes.  Ancestral graph Markov models.  _Ann. Statist._ , 30(4):962–1030, 2002.
  * Sadeghi (2013) K. Sadeghi.  Stable mixed graphs.  _Bernoulli_ , 19(5(B)):2330–2358, 2013.
  * Sadeghi (2016) K. Sadeghi.  Marginalization and conditioning for lwf chain graphs.  _Ann. Statist._ , 44(4):1792–1816, 2016.
  * Sadeghi (2017) K. Sadeghi.  Faithfulness of probability distributions and graphs.  _J. Mach. Learn. Res._ , 18(148):1–29, 2017.
  * Sadeghi and Lauritzen (2014) K. Sadeghi and S. L. Lauritzen.  Markov properties for mixed graphs.  _Bernoulli_ , 20(2):676–696, 2014.
  * Spirtes et al. (2000) P. Spirtes, C. Glymour, and R. Scheines.  _Causation, Prediction, and Search_.  MIT press, 2nd edition, 2000.
  * Steel (2006) D. Steel.  Homogeneity, selection, and the faithfulness condition.  _Minds and Machines_ , 16(3):303–317, 2006.
  * Studený (1989) M. Studený.  Multiinformation and the problem of characterization of conditional independence relations.  _Problems of Control and Information Theory_ , 18:3–16, 1989.
  * Studený (2005) M. Studený.  _Probabilistic Conditional Independence Structures_.  Springer-Verlag, London, United Kingdom, 2005.
  * Tsamardinos et al. (2006) I. Tsamardinos, L. E. Brown, and C. F. Aliferis.  The max-min hill-climbing bayesian network structure learning algorithm.  _Machine Learning_ , 65(1):31–78, 2006.
  * Verma and Pearl (1988) T. Verma and J. Pearl.  Causal networks: Semantics and expressiveness.  _Proceedings of the Fourth Workshop on Uncertainty in Artificial Intelligence (UAI)_ , 4:352–359, 03 1988.
  * Verma and Pearl (1990) T. Verma and J. Pearl.  On the equivalence of causal models.  In _Proceedings of the Proceedings of the Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-90)_ , pages 220–227, New York, NY, 1990. Elsevier Science.
  * Wermuth (2011) N. Wermuth.  Probability distributions with summary graph structure.  _Bernoulli_ , 17(3):845–879, 2011.
  * Wermuth and Sadeghi (2012) N. Wermuth and K. Sadeghi.  Sequences of regressions and their independences.  _TEST_ , 21(2):215–252 and 274–279, 2012.
  * Woodward (1998) J. Woodward.  Causal independence and faithfulness.  _Multivariate Behavioral Research_ , 33(1):129–148, 1998.
  * Zhang (2008) J. Zhang.  On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias.  _Artif. Intell._ , 172(16–17):1873–1896, 2008\.
  * Zhang (2012) J. Zhang.  A comparison of three Occam’s razors for Markovian causal models.  _British Journal for the Philosophy of Science_ , 64(2):423–448, June 2012.  ISSN 0007-0882.  doi: 10.1093/bjps/axs005.
  * Zhang and Spirtes (2003) J. Zhang and P. Spirtes.  Strong faithfulness and uniform consistency in causal inference.  In _Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence_ , UAI’03, pages 632–639, San Francisco, CA, USA, 2003\. Morgan Kaufmann Publishers Inc.
  * Zhang and Spirtes (2008) J. Zhang and P. Spirtes.  Detection of unfaithfulness and robust causal inference.  _Minds and Machines_ , 18(2):239–271, 2008.
  * Zhao et al. (2004) H. Zhao, Z. Zheng, and B. Liu.  On the Markov equivalence of maximal ancestral graphs.  _Science in China Ser. A, Mathematics_ , 48:548–562, 2004\.