# Greedy causal discovery is geometric

Svante Linusson  Matematik, KTH, SE-100 44 Stockholm, Sweden
<EMAIL_ADDRESS>,  Petter Restadh  Matematik, KTH, SE-100 44 Stockholm,
Sweden<EMAIL_ADDRESS>and  Liam Solus  Matematik, KTH, SE-100 44 Stockholm,
Sweden<EMAIL_ADDRESS>
###### Abstract.

Finding a directed acyclic graph (DAG) that best encodes the conditional
independence statements observable from data is a central question within
causality. Algorithms that greedily transform one candidate DAG into another
given a fixed set of moves have been particularly successful, for example the
GES, GIES, and MMHC algorithms. In 2010, Studený, Hemmecke and Lindner
introduced the characteristic imset polytope, $\mathop{\rm CIM}\nolimits_{p}$,
whose vertices correspond to Markov equivalence classes, as a way of
transforming causal discovery into a linear optimization problem. We show that
the moves of the aforementioned algorithms are included within classes of
edges of $\mathop{\rm CIM}\nolimits_{p}$ and that restrictions placed on the
skeleton of the candidate DAGs correspond to faces of $\mathop{\rm
CIM}\nolimits_{p}$. Thus, we observe that GES, GIES, and MMHC all have
geometric realizations as greedy edge-walks along $\mathop{\rm
CIM}\nolimits_{p}$. Furthermore, the identified edges of $\mathop{\rm
CIM}\nolimits_{p}$ strictly generalize the moves of these algorithms.
Exploiting this generalization, we introduce a greedy simplex-type algorithm
called _greedy CIM_ , and a hybrid variant, _skeletal greedy CIM_ , that
outperforms current competitors among hybrid and constraint-based algorithms.

###### Key words and phrases:

graphical model, Bayesian network, causal discovery, characteristic imset,
polytope, edge-walk, GES, Max Min Hill Climbing

###### 2010 Mathematics Subject Classification:

Primary: 62D20, 52B12; Secondary: 62H22, 52B05

##  1\. Introduction

The use of directed acyclic graphs (DAGs) to model complex systems has
increased rapidly during the last thirty years, and today they are used in a
wide variety of fields [6, 13, 17, 19]. Given a positive integer $p$ we let
$[p]\coloneqq\\{1,2,\dots,p\\}$. To each DAG $\mathcal{G}=([p],E)$ we
associate a set of random variables $X_{1},\dots,X_{p}$, and the conditional
independence (CI) statements $X_{i}\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}X_{\operatorname{nd}_{\mathcal{G}}(i)\setminus\operatorname{pa}_{\mathcal{G}}(i)}|X_{\operatorname{pa}_{\mathcal{G}}(i)}$
for all $i\in[p]$. Here, $\operatorname{pa}_{\mathcal{G}}(i)$ denotes the
parents and $\operatorname{nd}_{\mathcal{G}}(i)$ denotes the non-descendants
of $i$ in $\mathcal{G}$. A joint probability distribution
$P(X_{1},\dots,X_{p})$ is _Markov_ to a DAG $\mathcal{G}$ if it entails all
such CI statements. The goal of causal discovery is to learn an unknown DAG
$\mathcal{G}=([p],E)$ from samples drawn from a joint distribution $P$ over
$(X_{1},\dots,X_{p})$ that is assumed to be Markov to $\mathcal{G}$.
Unfortunately, this cannot generally be done as multiple DAGs can encode the
same set of CI statements. Two such DAGs are called _Markov equivalent_ , and
they belong to the same _Markov equivalence class_ (MEC). Thus, the basic
problem of causal discovery is to identify the MEC of $\mathcal{G}$, and
variety of _causal discovery algorithms_ for doing so have been proposed [4,
8, 20, 25].

Many of the more competitive algorithms are score-based and greedy, like the
Greedy Equivalence Search (GES) [4], or the Greedy Interventional Equivalence
Search (GIES) applied to only observational data [8]. These algorithms aim to
maximize a score function, such as the Bayesian Information Criterion (BIC).
Others aim to recover the MEC from a collection of CI statements by treating
causal discovery as a constraint-satisfaction problem, like the PC algorithm
[20, 25]. While the score-based methods tend to be more accurate on both
simulated and real data, the constraint-based algorithms are usually faster.
More recent algorithms have tried using a hybrid approach, like Max-Min Hill
Climbing (MMHC) [26], where the authors restrict the search space by using CI
tests and then take a greedy score-based approach. In the hybrid setting, one
can leverage the speed of constraint-based methods versus the accuracy of
score-based methods.

Alternatively, Studený, Hemmecke and Lindner gave a geometric interpretation
of MECs by realizing them as $0/1$-vectors called _characteristic imsets_
[23]. Maximizing a score equivalent and (additive) decomposable function over
the MECs of DAGs on $p$ nodes then becomes equivalent to maximizing a linear
function over these vectors. Thus, finding the BIC-optimal MEC can be seen as
a linear optimization problem over the _characteristic imset (CIM) polytope_ ,
$\mathop{\rm CIM}\nolimits_{p}$. This approach has also been used to learn
decomposable models, with promising results [24]. While most research on these
polytopes has focused on the identification of facets, our main focus will be
their edges and other lower-dimensional faces.

We begin by showing that the reduced search space of the aforementioned
popular hybrid and constraint-based algorithms are realized as faces of
$\mathop{\rm CIM}\nolimits_{p}$ (see Proposition 2.5). In Section 3, we then
identify classes of edges corresponding to, and strictly generalizing, the
moves of GES, GIES, and MMHC. Thus, we obtain a geometric interpretation of
these algorithms as edge-walks along faces of a convex polytope. A more recent
hybrid algorithm called greedy SP [18] also admits a geometric interpretation
as an edge-walk along a convex polytope. Since GES, GIES, MMHC, and greedy SP
are currently the benchmark standards for greedy causal discovery algorithms
based solely on observational data, we can then view greedy causal discovery
as a purely geometric process; i.e., as an edge-walk along a convex polytope
(see Theorem 3.17). Furthermore, as the characterized edges of $\mathop{\rm
CIM}\nolimits_{p}$ strictly generalize the moves of GES, GIES, and MMHC, we
propose a hybrid algorithm that we call _skeletal greedy CIM_ (Algorithm 1)
and a greedy score-based algorithm that we call _greedy CIM_ (Algorithm 2).

In Section 4 we give a complete graphical characterization of the
characterized edges of a face of $\mathop{\rm CIM}\nolimits_{p}$ when the
underlying graph is a tree. For trees we also identify two new classes of
edges and we use them to completely characterize the edges of the faces of
$\mathop{\rm CIM}\nolimits_{p}$ corresponding to MECs whose underlying
skeleton is a path or cycle. We then present some computational results. In
Section 5.1, we study how greedy CIM and skeletal greedy CIM perform on
simulated data and compare their performance with the state-of-the-art. We
observe that the additional moves given by the classified edges of
$\mathop{\rm CIM}\nolimits_{p}$ result in both the hybrid and purely score-
based algorithms performing at least as well as all (respective) benchmark
standards. In the case of hybrid algorithms, skeletal greedy CIM consistently
outperforms all other hybrid alternatives. These observations purport the
edges of the characteristic imset polytope as the natural object of study in
efforts to improve the accuracy of modern causal discovery algorithms.
Finally, in Section 5.2, we analyze the complete edge structure of
$\mathop{\rm CIM}\nolimits_{4}$, and relate our observations to our
theoretical results. Here we see how many edges we have characterized in the
previous sections and give an explanation for the additional ones. The more
technical proofs of the main theorems in Sections 3 and 4 can be found in
Appendices B and C, respectively.

##  2\. Preliminaries

A brief summary of the basic graph theory and convex geometry needed in this
paper is given in Appendix A. The _skeleton_ of a directed graph $\mathcal{G}$
is the undirected graph produced by replacing each edge of $\mathcal{G}$ with
an undirected edge. A _v-structure_ is an induced subgraph of the form $i\to
j\leftarrow k$. The following is a classic result of Verma and Pearl.

######  Theorem 2.1.

[28] Two DAGs are Markov equivalent if and only if they have the same skeleton
and the same v-structures.

Let $\mathcal{G}=([p],E)$ be a DAG. It is well-known that a joint distribution
over $(X_{1},\ldots,X_{p})$ is Markov to $\mathcal{G}$ if and only if its
probability density function $P$ factorizes as

$P(X_{1},\dots,X_{p})=\prod_{i\in[p]}P(X_{i}|X_{\operatorname{pa}_{\mathcal{G}}(i)}).$
(2.1)

To obtain a unique graphical representation of each MEC, Andersson, Madigan,
and Perlman proposed and gave a complete characterization of _essential
graphs_ [1]. Studený proposed a more geometric interpretation of Markov
equivalence via vectors that encode the CI statements, called the _standard
imset_ [21, 22]. Following this idea, in [23] Studený, Hemmecke, and Lindner
introduced the _characteristic imset_ , $c_{\mathcal{G}}$, of a DAG
$\mathcal{G}$ that encodes the factorization of Equation 2.1. As the
factorization determines the MEC, this gives us a unique representation of
each MEC. Formally it is a function
$c_{\mathcal{G}}\colon\left\\{S\subseteq[p]\colon|S|\geq
2\right\\}\to\\{0,1\\}$ defined as

$c_{\mathcal{G}}(S)\coloneqq\begin{cases}1&\text{ if there exists $i\in S$
such that for all $j\in S\setminus\\{i\\}$,
$j\in\operatorname{pa}_{\mathcal{G}}(i)$},\\\ 0&\text{ otherwise}.\\\
\end{cases}$

As $c_{\mathcal{G}}$ is a function from a finite set we can identify it with a
vector in $\mathbb{R}^{2^{p}-p-1}$ where the basis vectors, $e_{S}$, are
indexed by the sets in $\left\\{S\subseteq[p]\colon|S|\geq 2\right\\}$.
Similar to essential graphs, characteristic imsets then give us a unique
representation for each MEC.

######  Lemma 2.2.

[23] Two DAGs $\mathcal{G}$ and $\mathcal{H}$ are Markov equivalent if and
only if $c_{\mathcal{G}}=c_{\mathcal{H}}$.

The next lemma follows from the definition of characteristic imsets and
provides a way to recover the structure of the graph from this vector
encoding.

######  Lemma 2.3.

[23] Let $\mathcal{G}$ be a DAG on $[p]$. Then for any distinct nodes $i$,
$j$, and $k$ we have

  1. (1)

$i\leftarrow j$ or $j\rightarrow i$ in $\mathcal{G}$ if and only if
$c_{\mathcal{G}}(\\{i,j\\})=1$.

  2. (2)

$i\rightarrow j\leftarrow k$ is a v-structure in $\mathcal{G}$ if and only of
$c_{\mathcal{G}}(\\{i,j,k\\})=1$ and $c_{\mathcal{G}}(\\{i,k\\})=0$.

As we can see, the characteristic imset encodes the skeleton and the
v-structures in the 2- and 3-sets. This, combined with the fact that every
characteristic imset uniquely encodes an MEC (Lemma 2.2) and with the
graphical characterization of the MECs (Theorem 2.1), yields the following
lemma:

######  Lemma 2.4.

[11, Corollary 2.2.6] Two characteristic imsets $c_{\mathcal{G}}$ and
$c_{\mathcal{H}}$ are equal if and only if
$c_{\mathcal{G}}(S)=c_{\mathcal{H}}(S)$ for all sets $|S|\in\\{2,3\\}$.

Any (additive) decomposable and score equivalent function can be seen as an
affine linear function over the vectors $c_{\mathcal{G}}$ [23]. An important
example of such a function is the _Bayesian Information Criterion_ (BIC).
Given $n$ independent samples, $\mathbf{D}$, drawn from the joint distribution
of $(X_{1},\dots,X_{p})$, the BIC is defined as

$\mathop{\rm
BIC}\nolimits(\mathcal{G},\mathbf{D})=\log{P}\left(\mathbf{D}|\theta,\mathcal{G}^{h}\right)-\frac{d}{2}\log(n).$
(2.2)

Here $\theta$ is the maximum-likelihood estimate for the network parameters,
$d$ denotes the number of free parameters of $\mathcal{G}$, and
$\mathcal{G}^{h}$ denotes the hypothesis that $\mathbf{D}$ are i.i.d samples
from a distribution that entails exactly the CI statements encoded by
$\mathcal{G}$ [4]. Thus, the question of learning the BIC-optimal MEC can be
stated as finding the maximum of an affine linear function over a finite set
of vectors in a finite-dimensional real vector space. This motivates the
definition of the _characteristic imset polytope_ (CIM polytope) for DAGs on
$p$ nodes:

$\mathop{\rm CIM}\nolimits_{p}\coloneqq\mathop{\rm
conv}\nolimits\left(c_{\mathcal{G}}\in\mathbb{R}^{2^{p}-p-1}\colon\text{
$\mathcal{G}=([p],E)$ a DAG}\right).$

As $\mathop{\rm CIM}\nolimits_{p}$ is defined as a $0/1$-polytope (that is,
the convex hull of vectors with entries that are either $0$ or $1$) the
vertices of $\mathop{\rm CIM}\nolimits_{p}$ are precisely
$\\{c_{\mathcal{G}}\colon\text{ $\mathcal{G}=([p],E)$ a DAG}\\}$ [29].

A classic constraint-based causal discovery algorithm is the PC algorithm [20,
25]. It first utilizes CI tests to learn a skeleton $G$ and then to orient
v-structures. The Max-Min Hill Climbing (MMHC) algorithm [26] utilizes CI
tests to learn possible edges in the skeleton, and then uses a score-based
method to construct a DAG restricted to using only these edges. Following the
idea of utilizing CI tests to obtain a skeleton, we consider another polytope,
closely related to $\mathop{\rm CIM}\nolimits_{p}$. Let $G=([p],E)$ be an
undirected graph and define the _CIM polytope for $G$_ to be

$\mathop{\rm CIM}\nolimits_{G}\coloneqq\mathop{\rm
conv}\nolimits\left(c_{\mathcal{G}}\in\mathbb{R}^{2^{p}-p-1}\colon\text{
$\mathcal{G}=([p],E)$ a DAG with skeleton $G$}\right).$

Thus, like the PC algorithm, we can learn an undirected skeleton, $G$, via CI
tests, and then take a score-based approach via an edge-walk on $\mathop{\rm
CIM}\nolimits_{G}$ optimizing the BIC. Such a method is called a _hybrid
algorithm_ as it first uses a constraint-based approach to restrict the search
space, and then uses a score-based approach to find the optimal DAG. An
immediate question is then: what is the relationship between $\mathop{\rm
CIM}\nolimits_{p}$ and $\mathop{\rm CIM}\nolimits_{G}$? To this end we have
the following proposition:

######  Proposition 2.5.

Let $H=([p],E)$ and $H^{\prime}=([p],E^{\prime})$ be two undirected graphs
such that $E\subseteq E^{\prime}$. Then

$\mathop{\rm
conv}\nolimits\left(c_{\mathcal{G}}\in\mathbb{R}^{2^{p}-p-1}\colon\mathcal{G}\text{
a DAG with skeleton $G=([p],D)$ where $E\subseteq D\subseteq
E^{\prime}$}\right)$

is a face of $\mathop{\rm CIM}\nolimits_{p}$.

###### Proof.

It is enough to find a cost function, $w_{H,H^{\prime}}$, which maximizes
precisely over the set

$\left\\{c_{\mathcal{G}}\in\mathbb{R}^{2^{p}-p-1}\colon\mathcal{G}\text{ a DAG
with skeleton $G=([p],D)$ where $E\subseteq D\subseteq E^{\prime}$}\right\\},$

out of all characteristic imsets. So define

$w_{H,H^{\prime}}(S)\coloneqq\begin{cases}0&\text{if $|S|\neq 2$,}\\\
1&\text{if $S\in E$,}\\\ 0&\text{if $S\in E^{\prime}\setminus E$,}\\\
-1&\text{otherwise.}\end{cases}$

Notice that $w_{H,H^{\prime}}$ is only non-zero for sets with cardinality $2$.
Then if we have $\mathcal{G}$ with skeleton $G=([p],D)$ we get via Lemma 2.3

$\displaystyle w^{T}_{H,H^{\prime}}c_{\mathcal{G}}$
$\displaystyle=\sum_{S\subseteq[p],|S|\geq
2}w_{H,H^{\prime}}(S)c_{\mathcal{G}}(S)$
$\displaystyle=\sum_{S\subseteq[p],|S|=2}w_{H,H^{\prime}}(S)c_{\mathcal{G}}(S)$
$\displaystyle=|D\cap E|-|D\setminus E^{\prime}|.$

The right-hand-side is maximized exactly when $E\subseteq D\subseteq
E^{\prime}$. Thus $w_{H,H^{\prime}}$ maximizes exactly over the given set. ∎

The relationship between $\mathop{\rm CIM}\nolimits_{p}$ and $\mathop{\rm
CIM}\nolimits_{G}$ is then the following:

######  Corollary 2.6.

Let $G=([p],E)$ be an undirected graph. Then $\mathop{\rm CIM}\nolimits_{G}$
is a face of $\mathop{\rm CIM}\nolimits_{p}$.

###### Proof.

Choose $H=H^{\prime}=G$ in Proposition 2.5. ∎

##  3\. Edges of the $\mathop{\rm CIM}\nolimits$ Polytope

To construct efficient algorithms for finding the maximum of a linear score
function over a polytope, we need some description of the polytope. Assume we
are given an arbitrary polytope $P$ and a linear function $s$. It is immediate
that the set maximizing $s^{T}p$ for $p\in P$ is a face of $P$ (see Section
A.2). Thus, any linear function assumes its maximum value over $P$ at at least
one vertex of $P$. An _edge-walk_ on $P$ to maximize a linear function $s$ is
done in the following way: Start at any vertex $p_{0}$ of $P$, and set
$i\coloneqq 0$. At each step, choose $p_{i+1}$ such that $\mathop{\rm
conv}\nolimits(p_{i},p_{i+1})$ is an edge of the polytope and
$s^{T}p_{i}<s^{T}p_{i+1}$. If no such edges exist, return $p_{i}$.

Assuming that we know every edge of $P$, such an edge-walk will always return
a vertex maximizing $s$. Making additional assumptions on the score function
or looking for edges in a certain order can sometimes give us similar
guarantees. For example, see [18]. As a direct computation of all edges of
$\mathop{\rm CIM}\nolimits_{p}$ and $\mathop{\rm CIM}\nolimits_{G}$ is not
feasible for large $p$, we will instead identify edges of these polytopes in
terms of relations between the characteristic imsets they connect. As the
characteristic imsets are the vertices of these polytopes we will see how
these relations label edges of the polytope.

We begin by focusing on edges of $\mathop{\rm CIM}\nolimits_{G}$. Based on our
observations, we will then propose a hybrid algorithm that first learns an
undirected skeleton via conditional independence tests and then performs an
edge-walk along $\mathop{\rm CIM}\nolimits_{G}$, greedily optimizing
$\mathop{\rm BIC}\nolimits$. We will then look at the entire characteristic
imset polytope $\mathop{\rm CIM}\nolimits_{p}$, identifying edges of the form
$\mathop{\rm conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ where
$\mathcal{G}$ and $\mathcal{H}$ have different skeletons. Finally, we will
combine these results to define a purely score-based algorithm that performs
an edge-walk on $\mathop{\rm CIM}\nolimits_{p}$, again greedily optimizing the
$\mathop{\rm BIC}\nolimits$.

The edges we identify will include, as a special case, the moves of Greedy
Equivalence Search (GES) [4]. This positively answers a question raised by
Steffen Lauritzen at the _Workshop on Graphical Models: Conditional
Independence and Algebraic Structures, TU Munich, 2019_ : Do the moves of GES
have a geometric interpretation in terms of the $\mathop{\rm
CIM}\nolimits_{p}$ polytope? More generally, we recover a geometric
interpretation of the GIES algorithm [8] in the case of purely observational
data, as well as the hybrid MMHC algorithm.

To this end, we will begin by defining relations between imsets. These
relations are motivated by our graphical understanding of Markov equivalence,
but also turn out to generalize our intuition. We will then show that these
relations indeed constitute edges of the $\mathop{\rm CIM}\nolimits_{p}$ and
$\mathop{\rm CIM}\nolimits_{G}$ polytopes. Since both $\mathop{\rm
CIM}\nolimits_{p}$ and $\mathop{\rm CIM}\nolimits_{G}$ are $0/1$-polytopes, a
natural first question is what happens when two imsets differ in a single
coordinate.

######  Definition 3.1 (Addition).

Let $\mathcal{G}$ and $\mathcal{H}$ be two DAGs on node set $[p]$. We say the
pair $\\{\mathcal{G},\mathcal{H}\\}$ is an _addition_ if
$c_{\mathcal{H}}=c_{\mathcal{G}}+e_{S^{\ast}}$ for some $S^{\ast}\subseteq[p]$
with $|S|\geq 2$. We further say that $\\{\mathcal{G},\mathcal{H}\\}$ is an
_edge addition_ if $|S^{\ast}|=2$ and a _v-structure addition_ if
$|S^{\ast}|=3$.

One can equivalently define an addition as $c_{\mathcal{G}}$ and
$c_{\mathcal{H}}$ having Hamiltonian distance $1$ from one another. As edges
of a polytope are undirected, we likewise define an addition to be an
unordered pair of DAGs. In [18], where edges of a polytope were labeled by a
reversal of a _covered arrow_ [3] that transforms the DAG labeling one
endpoint of the edge into the other, the directionality of the edge-walk given
by the transformation is unimportant. This is because any greedy edge-walk
utilizing this edge may choose to walk in either direction. Hence, following
the convention of greedy SP [18] we view our relations between characteristic
imsets and their corresponding DAGs as unordered pairs, as opposed to ordered
pairs.

The partition into edge/v-structure additions becomes clearer in light of the
following proposition. We see that not only are all additions either an edge
or v-structure addition, but we also characterize them in terms of the
underlying graphs, $\mathcal{G}$ and $\mathcal{H}$.

######  Proposition 3.2.

Let $\mathcal{G}$ and $\mathcal{H}$ be DAGs on node set $[p]$, and suppose
that the pair $\\{\mathcal{G},\mathcal{H}\\}$ is an addition such that

$c_{\mathcal{H}}=c_{\mathcal{G}}+e_{S^{\ast}},$

where $|S^{\ast}|\geq 2$. Then either $S^{\ast}=\\{i,j\\}$ for some
$i,j\in[p]$, all v-structures of $\mathcal{H}$ are present in $\mathcal{G}$,
and the skeletons of $\mathcal{G}$ and $\mathcal{H}$ differ by the presence of
the edge $\\{i,j\\}$, or $S^{\ast}=\\{i,j,k\\}$ and $\mathcal{G}$ and
$\mathcal{H}$ have the same skeleton but differ by a single v-structure
$i\rightarrow k\leftarrow j$.

###### Proof.

Suppose first that $|S^{\ast}|=2$. Then $S^{\ast}=\\{i,j\\}$ for some
$i,j\in[p]$ for which $c_{\mathcal{G}}(\\{i,j\\})=0$ and
$c_{\mathcal{H}}(\\{i,j\\})=1$, and so the skeletons of $\mathcal{G}$ and
$\mathcal{H}$ differ by the presence of the edge $\\{i,j\\}$. Since
$c_{\mathcal{H}}=c_{\mathcal{G}}+e_{S^{\ast}}$, it follows that
$c_{\mathcal{H}}(S)=c_{\mathcal{G}}(S)$ for all $S\subseteq[p]$ with $|S|=3$.
By Lemma 2.3 we have $c_{\mathcal{H}}(S)=1$ for such an $S$ if and only if $S$
is complete in $\mathcal{H}$ or if the induced subgraph $\mathcal{H}_{S}$ is a
v-structure. Moreover, if the set $S=\\{i,j,k\\}$ is not complete in the
skeleton of $\mathcal{H}$, then there is at most one way to orient its edges
on $\\{i,j,k\\}$ to produce a v-structure. Thus, since
$c_{\mathcal{H}}(S)=c_{\mathcal{G}}(S)$ for all $S\subseteq[p]$ with $|S|=3$,
it follows that $\mathcal{G}$ and $\mathcal{H}$ have the same v-structures
except for possibly v-structures on the form $i\to k\leftarrow
j\in\mathcal{G}$ for some $k\in[n]$.

Suppose now that $|S^{\ast}|=3$. Then $S^{\ast}=\\{i,j,k\\}$ for some
$i,j,k\in[p]$. Since $c_{\mathcal{H}}=c_{\mathcal{G}}+e_{S^{\ast}}$, it
follows that $\mathcal{G}$ and $\mathcal{H}$ have the same skeleton and that
$c_{\mathcal{G}}(S^{\ast})=0$. Hence, we know that $S^{\ast}$ is not complete
in either of $\mathcal{G}$ or $\mathcal{H}$. From this, and the fact that
$c_{\mathcal{H}}(S^{\ast})=1$, it follows that the induced subgraph
$\mathcal{H}|_{S^{\ast}}$ of $\mathcal{H}$ is a v-structure. Since
$c_{\mathcal{G}}(S)=c_{\mathcal{H}}(S)$ for all $S\neq S^{\ast}$ with $|S|=3$,
a similar argument to the previous case shows that all other $v$-stuctures in
$\mathcal{G}$ and $\mathcal{H}$ are the same.

Finally suppose that $|S^{\ast}|\geq 4$. That gives us
$c_{\mathcal{G}}(S)=c_{\mathcal{H}}(S)$ for all $|S|\leq 3$ and by Lemma 2.4
we have $c_{\mathcal{G}}=c_{\mathcal{H}}$, a contradiction. ∎

Thus additions correspond to graphs that differ by an edge that is not part of
a v-structure or that differ by the presence of a single v-structure. A
natural extension of this would be if we can add in several v-structures at
the same time, as opposed to only adding in one. This can be necessary if we
already have a v-structure $s\to i\leftarrow j$ and want to direct another
edge towards $i$.

######  Definition 3.3 (Budding).

Let $\mathcal{G}$ and $\mathcal{H}$ be two DAGs on node set $[p]$ with
skeleton $G$. Suppose there exists $i,j\in[p]$ and
$S^{\ast}\subseteq[p]\setminus\\{i,j\\}$, with $|S^{\ast}|\geq 2$, such that

  1. (1)

$c_{\mathcal{G}}(\\{i,j\\})=1$;

  2. (2)

$c_{\mathcal{G}}(S\cup\\{i\\})=1$ for all $S\subseteq S^{\ast}$ with $|S|\geq
1$;

  3. (3)

$S^{\ast}\centernot\subseteq\operatorname{ne}_{G}(j)$.

We say the pair $\\{\mathcal{G},\mathcal{H}\\}$ is a _budding_ with respect to
$(i,j,S^{\ast})$ if

$c_{\mathcal{H}}=c_{\mathcal{G}}+\sum_{S\in\mathcal{S}^{+}}e_{S},$

where $\mathcal{S}^{+}\coloneqq\\{T\cup\\{i,j\\}\colon T\subseteq
S^{\ast},T\not\subseteq\operatorname{ne}_{G}(j)\\}$.

Note that since $c_{\mathcal{G}}$ and $c_{\mathcal{H}}$ are $0/1$-vectors it
is implicit in the definition that $c_{\mathcal{G}}(S)=0$ for all
$S\in\mathcal{S}^{+}$.

######  Example 3.4.

Take $\mathcal{G}$ and $\mathcal{H}$ to be the graphs in Figure 1 and let
$S^{\ast}=\\{s_{1},s_{2}\\}$.

$\mathcal{G}\coloneqq$$i$$j$$s_{1}$$s_{2}$$i$$j$$\mathcal{H}\coloneqq$$s_{1}$$s_{2}$
Figure 1. An example of a budding.

It can be verified that
$\mathcal{S}^{+}=\left\\{\\{i,j,s_{1}\\},\\{i,j,s_{1},s_{2}\\}\right\\}$ and
that
$c_{\mathcal{H}}=c_{\mathcal{G}}+e_{\\{i,j,s_{1}\\}}+e_{\\{i,j,s_{1},s_{2}\\}}$.
Thus $\\{\mathcal{G},\mathcal{H}\\}$ is a budding with respect to
$(i,j,S^{\ast})$.

In the previous definitions we have looked at the case where we wanted to add
in, or remove, v-structures. Hence, moving from $\mathcal{G}$ to $\mathcal{H}$
via an addition or budding allows us to either add in or remove v-structures,
but never both at the same time. The next definition alleviates this
restriction.

######  Definition 3.5 (Flip).

Let $\mathcal{G}$ and $\mathcal{H}$ be two DAGs on node set $[p]$ and with
skeleton $G$. Suppose there exists $i$, $j$,
$S_{i}\subseteq[p]\backslash\\{i,j\\}$ and
$S_{j}\subseteq[p]\backslash\\{i,j\\}$ such that

  1. (1)

$c_{\mathcal{G}}(\\{i,j\\})=1$;

  2. (2)

$c_{\mathcal{G}}(S\cup\\{i\\})=1$ for all $S\subseteq S_{i}$ with $|S|\geq 1$;

  3. (3)

$c_{\mathcal{G}}(S\cup\\{j\\})=1$ for all $S\subseteq S_{j}$ with $|S|\geq 1$;

  4. (4)

$S_{i}\not\subseteq\operatorname{ne}_{G}(j)$;

  5. (5)

$S_{j}\not\subseteq\operatorname{ne}_{G}(i)$.

Then we say that $\\{\mathcal{G},\mathcal{H}\\}$ is a _flip_ with respect to
$(i,j,S_{i},S_{j})$ if

$c_{\mathcal{H}}=c_{\mathcal{G}}+\sum_{S\in\mathcal{S}^{+}}e_{S}-\sum_{S\in\mathcal{S}^{-}}e_{S}$

where $\mathcal{S}^{+}\coloneqq\\{T\cup\\{i,j\\}\colon T\subseteq S_{i},\
T\not\subseteq\operatorname{ne}_{G}(j)\\}$ and
$\mathcal{S}^{-}\coloneqq\\{T\cup\\{i,j\\}\colon T\subseteq S_{j},\
T\not\subseteq\operatorname{ne}_{G}(i)\\}$.

######  Remark 3.6.

By symmetry in Definition 3.5 we have that $\\{\mathcal{G},\mathcal{H}\\}$ is
a flip with respect to $(i,j,S_{i},S_{j})$ if and only if
$\\{\mathcal{G},\mathcal{H}\\}$ is a flip with respect to $(j,i,S_{j},S_{i})$.
Hence, in this case the relation is symmetric, and thus flips are genuinely
unordered pairs.

######  Example 3.7.

Take $\mathcal{G}$ and $\mathcal{H}$ to be as in Figure 2. Let
$S_{i}=\\{s_{1},s_{2}\\}$ and $S_{j}=\\{s_{3}\\}$.

$\mathcal{G}\coloneqq$$i$$j$$s_{1}$$s_{2}$$s_{3}$$i$$j$$\mathcal{H}\coloneqq$$s_{1}$$s_{2}$$s_{3}$
Figure 2. An example of a flip.

It can be verified that
$\mathcal{S}^{+}=\left\\{\\{i,j,s_{1}\\},\\{i,j,s_{2}\\},\\{i,j,s_{1},s_{2}\\}\right\\}$
and $\mathcal{S}^{-}=\left\\{\\{i,j,s_{3}\\}\right\\}$. We also have
$c_{\mathcal{H}}=c_{\mathcal{G}}+e_{\\{i,j,s_{1}\\}}+e_{\\{i,j,s_{2}\\}}+e_{\\{i,j,s_{1},s_{2}\\}}-e_{\\{i,j,s_{3}\\}}$.
Thus $\\{\mathcal{G},\mathcal{H}\\}$ is a flip with respect to
$(i,j,S_{i},S_{j})$.

We have so far focused on how the characteristic imset $c_{\mathcal{G}}$
changes when adding in or removing v-structures involving an edge $i-j$. To
this end, we defined v-structure additions, buddings, and flips as an
interpretation of such changes in terms of characteristic imsets. As we will
see in Proposition 3.10 each of these moves appears as a result of changing
the direction of the edge $i\to j$ into $i\leftarrow j$. Thus, we collect
these concepts into one definition:

######  Definition 3.8 (Turn pair).

Let $\mathcal{G}$ and $\mathcal{H}$ be DAGs with skeleton $G$. We say that
$\\{\mathcal{G},\mathcal{H}\\}$ is a _turn pair_ if
$\\{\mathcal{G},\mathcal{H}\\}$ is either

  1. (1)

a v-structure addition;

  2. (2)

a budding with respect to some $(i,j,S^{\ast})$;

  3. (3)

or a flip with respect to some $(i,j,S_{i},S_{j})$.

The name “turn pair” is explained via the next proposition. Worth noting is
that $i\in\operatorname{ne}_{\mathcal{G}}(j)$ can be expressed in terms of the
characteristic imset, as seen in Lemma 2.3. Thus the properties of a turn pair
are in fact properties of MECs rather than the DAGs they contain.

######  Remark 3.9.

We note that in the case that $\\{\mathcal{G},\mathcal{H}\\}$ satisfy all
conditions of being a flip except for
$S_{j}\subseteq\operatorname{ne}_{G}(i)$, the flip criteria reduces to the
criteria of a budding or, in the case of $|S_{i}|=1$ and $S_{j}=\emptyset$, a
v-structure addition. Thus, we can discuss $\mathcal{G}$ and $\mathcal{H}$
being a turn pair with respect to $(i,j,S_{i},S_{j})$ without necessarily
specifying whether $\\{\mathcal{G},\mathcal{H}\\}$ is an addition, budding, or
flip. As we saw in Remark 3.6, this further motivates our decision to define
additions and buddings as unordered pairs, as opposed to ordered pairs.

If $\mathcal{G}$ is a directed graph with $i\to j\in\mathcal{G}$ we denote by
$\mathcal{G}_{i\leftarrow j}$ the directed graph identical to $\mathcal{G}$
except that the edge $i\to j$ is replaced with $i\leftarrow j$.

######  Proposition 3.10.

Let $\mathcal{G}$ be a DAG with $i\to j\in\mathcal{G}$. If
$\mathcal{G}_{i\leftarrow j}$ is a DAG, then either $\mathcal{G}$ and
$\mathcal{G}_{i\leftarrow j}$ are Markov equivalent, or
$\\{\mathcal{G},\mathcal{G}_{i\leftarrow j}\\}$ is a turn pair.

The case in which $\mathcal{G}$ and $\mathcal{G}_{i\leftarrow j}$ are Markov
equivalent is characterized in [3]. In [8] the authors define a collection of
turning moves in terms of the essential graph (see [8, Propositions $31$ and
$34$]). They characterize when $\mathcal{G}_{i\leftarrow j}$ is a DAG and the
relation between the essential graphs of $\mathcal{G}$ and
$\mathcal{G}_{i\leftarrow j}$ when this is the case. The above proposition
shows that in the case of no interventions, their turning moves are turn
pairs. The converse is not true, as shown in Example 3.11. Although, when the
underlying graph is a tree, the turning moves in [8, Propositions $31$ and
$34$] coincide with turn pairs. This is shown in Section 4.1.

######  Example 3.11.

By Proposition 3.10, turn pairs capture whenever we turn an edge in a DAG,
transforming it into another (non-Markov equivalent) DAG, in terms of
characteristic imsets. The converse of Proposition 3.10 is, on the other hand,
not true. That is, there exists a turn pair $\\{\mathcal{G},\mathcal{H}\\}$
for which there is no DAG $\mathcal{D}$ Markov equivalent to $\mathcal{G}$
such that $\mathcal{D}_{i\leftarrow j}$ is Markov equivalent to $\mathcal{H}$.
As an example of this, take $\mathcal{G}$ and $\mathcal{H}$ as in Figure 3.

$\mathcal{G}\coloneqq$$s_{1}$$s_{2}$$i$$j$$k_{1}$$k_{2}$

$\mathcal{H}\coloneqq$$s_{1}$$s_{2}$$i$$j$$k_{1}$$k_{2}$

Figure 3. An example of a turn pair not arising from changing the direction of
any one edge in any DAG in the MEC.

It can be checked that $\\{\mathcal{G},\mathcal{H}\\}$ is a budding with
respect to $(i,j,\\{s_{1},s_{2}\\})$, but it follows from Theorem 2.1 that
$i\leftarrow j\in\mathcal{D}$ for all DAGs $\mathcal{D}$ Markov equivalent to
$\mathcal{G}$ or $\mathcal{H}$.

By Proposition 3.10, turn pairs arise naturally from an intuitive graphical
interpretation of reversing an edge and, as Example 3.11 shows, strictly
generalize this intuition. Recall that we want to characterize relations
between the characteristic imsets that label edges of $\mathop{\rm
CIM}\nolimits_{G}$. The following theorem states that all turn pairs
constitute edges in the $\mathop{\rm CIM}\nolimits_{G}$ polytope.

######  Theorem 3.12.

If $\\{\mathcal{G},\mathcal{H}\\}$ is a turn pair, then $\mathop{\rm
conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ is an edge of $\mathop{\rm
CIM}\nolimits_{G}$ where $G$ is the skeleton of $\mathcal{G}$ and
$\mathcal{H}$.

###### Proof.

This is the combined result of Proposition B.1, Proposition B.3, and
Proposition B.5. ∎

The above theorem tells us that moving via turn pairs is in fact an edge-walk
along $\mathop{\rm CIM}\nolimits_{G}$. For algorithms based on such edge-walks
to be able to perform well we would like to move around $\mathop{\rm
CIM}\nolimits_{G}$ relatively freely. In the following proposition we show
that the edges labeled by turn pairs are enough to traverse the polytope
$\mathop{\rm CIM}\nolimits_{G}$.

######  Proposition 3.13.

Let $G$ be a graph and $\mathcal{G}$ and $\mathcal{H}$ two DAGs with skeleton
$G$. Then there exists a sequence of edges

$\mathop{\rm conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{G}_{1}}),\mathop{\rm
conv}\nolimits(c_{\mathcal{G}_{1}},c_{\mathcal{G}_{2}}),\ldots,\mathop{\rm
conv}\nolimits(c_{\mathcal{G}_{m-1}},c_{\mathcal{G}_{m}}),\mathop{\rm
conv}\nolimits(c_{\mathcal{G}_{m}},c_{\mathcal{H}}),$

of $\mathop{\rm CIM}\nolimits_{G}$ such that each pair
$\\{\mathcal{G},\mathcal{G}_{1}\\},\\{\mathcal{G}_{1},\mathcal{G}_{2}\\},\ldots,\\{\mathcal{G}_{m-1},\mathcal{G}_{m}\\},\text{
and }\\{\mathcal{G}_{m},\mathcal{H}\\}$ is a turn pair.

The edges labeled by turn pairs thus connect the polytope $\mathop{\rm
CIM}\nolimits_{G}$ in the sense that for any two DAGs, $\mathcal{G}$ and
$\mathcal{H}$, with skeleton $G$, there exists a sequence of turn pairs that
begins at $c_{\mathcal{G}}$ and ends at $c_{\mathcal{H}}$. Thus we can take a
simplex-type approach to finding the BIC-optimal MEC. To this end, we propose
a hybrid greedy causal discovery algorithm in which we first learn the
skeleton $G$ via CI tests, similar to the PC algorithm, and then perform a
restricted edge-walk on $\mathop{\rm CIM}\nolimits_{G}$ utilizing the edges
labeled by turn pairs, which we call the _turn phase_. We call this algorithm
_skeletal greedy CIM_ (see Algorithm 1).

Input: Data $D$.

Output: A characteristic imset $c_{\mathcal{G}}$.

1 Do CI tests to find the underlying skeleton $G$;

2 Let $\mathcal{G}$ a DAG with skeleton $G$;

3 $c_{\mathcal{D}}\leftarrow\texttt{null}$;

4 while  _$c_{\mathcal{D}}\neq c_{\mathcal{G}}$_ do

5 $c_{\mathcal{G}}\leftarrow c_{\mathcal{D}}$;

$c_{\mathcal{D}}\leftarrow$ turn phase ;

// Algorithm 4 (Appendix D) with $c_{\mathcal{D}}$ as input.

6

7 end while

8return $c_{\mathcal{G}}$;

Algorithm 1 Skeletal Greedy CIM

Up until now we have primarily studied $\mathop{\rm CIM}\nolimits_{G}$, but we
would like to move between vertices of $\mathop{\rm CIM}\nolimits_{G}$ and
$\mathop{\rm CIM}\nolimits_{H}$ when $G$ and $H$ are not equal. We have
already seen in Proposition 3.2 that edge additions can do this, but only in a
very restricted manner. Moreover, a direct consequence of Proposition 3.10 and
Theorem 3.12 is that the turning phase of GIES [8] is a type of edge-walk over
$\mathop{\rm CIM}\nolimits_{G}$. The question then arises whether it holds for
the forward and backward phases as well. Thus, we would like a definition
similar to Definition 3.8 but for adding an edge.

######  Definition 3.14 (Edge pair).

Let $\mathcal{G}$ and $\mathcal{H}$ be two DAGs on node set $[p]$. Suppose
there exists distinct nodes $i$, $j$ and a set
$S^{\ast}\subseteq[p]\backslash\\{i,j\\}$ such that

  1. (1)

$c_{\mathcal{G}}(\\{i,j\\})=0$,

  2. (2)

$c_{\mathcal{G}}(S\cup\\{i\\})=1$ for all $S\subseteq S^{\ast}$ with $|S|\geq
1$.

Then we say that $\\{\mathcal{G},\mathcal{H}\\}$ is a _edge pair_ with respect
to $(i,j,S^{\ast})$ if

$c_{\mathcal{H}}=c_{\mathcal{G}}+\sum_{S\in\mathcal{S}_{+(j,i)}}e_{S}$

where $\mathcal{S}_{+(j,i)}\coloneqq\\{S\cup\\{i,j\\}\colon S\subseteq
S^{\ast}\\}$.

Note that if $S^{\ast}=\emptyset$ then $\mathcal{S}_{+(j,i)}=\\{\\{i,j\\}\\}$.
Thus, edge pairs generalize edge additions. Let $\mathcal{G}$ be a DAG and
assume $i$ and $j$ are not adjacent in the skeleton of $\mathcal{G}$. We
denote by $\mathcal{G}_{+j\to i}$ the directed graph identical to
$\mathcal{G}$ with the edge $j\to i\in\mathcal{G}_{+j\to i}$. Then, similar to
Proposition 3.10, we have the following:

######  Proposition 3.15.

Let $\mathcal{G}$ be a DAG and assume $i$ and $j$ are not adjacent in the
skeleton of $\mathcal{G}$. If $\mathcal{G}_{+j\to i}$ is a DAG, then
$\\{\mathcal{G},\mathcal{G}_{+j\to i}\\}$ is an edge pair.

Thus edge pairs give an interpretation, in terms of characteristic imsets, of
adding an edge to a graph the same way as turn pairs give an interpretation of
changing the direction of an edge.

######  Theorem 3.16.

If $\\{\mathcal{G},\mathcal{H}\\}$ is an edge pair, then $\mathop{\rm
conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ is an edge of $\mathop{\rm
CIM}\nolimits_{p}$ where $p$ is the number of nodes in $\mathcal{G}$ and
$\mathcal{H}$.

By combining Proposition 3.15 with Theorem 3.16 we obtain a positive answer to
the aforementioned question by Steffen Lauritzen; namely, we see that the
moves of GES have a geometric interpretation as edges of $\mathop{\rm
CIM}\nolimits_{p}$. Going even further, by combining this observation with
Proposition 3.10 and Theorem 3.12, we see that the moves of the GIES
algorithm, which (in the case of purely observational data) extends GES with
an additional turn phase, also admit a geometric interpretation as edges of
$\mathop{\rm CIM}\nolimits_{p}$. Similarly, the MMHC algorithm performs a
greedy search akin to that of GES, but it first restricts the search space to
a subset of edges that are allowed to appear in the skeleton. An application
of Proposition 2.5 with $H=([p],\emptyset)$ thus extends these results to the
MMHC algorithm. Since greedy SP [18] is defined as an edge-walk along another
family of convex polytopes (called DAG associahedra [12]), these observations
imply that the popular greedy score-based and hybrid causal discovery
algorithms (GES, GIES, MMHC, and greedy SP) can all be viewed as edge-walks
along a convex polytope. Thus greedy causal discovery is, in a sense,
geometric. We summarize this observation in the following theorem:

######  Theorem 3.17.

The following causal discovery algorithms are greedy edge-walks along a convex
polytope:

  1. (1)

GES,

  2. (2)

GIES with purely observational data,

  3. (3)

MMHC, and

  4. (4)

Greedy SP.

Example 3.11 further shows that the edges of $\mathop{\rm CIM}\nolimits_{p}$
labeled by turn and edge pairs are a strict generalization of the moves of GES
and GIES. Hence, any edge-walk that greedily optimizes BIC over $\mathop{\rm
CIM}\nolimits_{p}$ can be viewed as an extension of these causal discovery
algorithms.

In regards to Theorem 3.16, we propose the purely score-based algorithm
_greedy CIM_ (Algorithm 2) which extends GES and GIES. This algorithm is, as
opposed to skeletal greedy CIM (Algorithm 1), not a hybrid algorithm, as we do
not rely on conditional independence tests to find the skeleton. Instead it
relies on an _edge phase_ that consists of a restricted edge-walk, utilizing
the edges of $\mathop{\rm CIM}\nolimits_{p}$ determined by edge pairs. Due to
Theorem 3.16, the greedy CIM algorithm consists solely of an edge-walk on
$\mathop{\rm CIM}\nolimits_{p}$.

Input: Data $D$.

Output: A characteristic imset $c_{\mathcal{G}}$ where $\mathcal{G}$ is a DAG.

1 Let $\mathcal{G}$ be the DAG without any edges;

2 $c_{\mathcal{D}}\leftarrow\texttt{null}$;

3 while  _$c_{\mathcal{D}}\neq c_{\mathcal{G}}$_ do

4 $c_{\mathcal{G}}\leftarrow c_{\mathcal{D}}$;

$c_{\mathcal{D}}\leftarrow$ edge phase ;

// Algorithm 3 (Appendix D) with $c_{\mathcal{D}}$ as input.

$c_{\mathcal{D}}\leftarrow$ turn phase ;

// Algorithm 4 (Appendix D) with $c_{\mathcal{D}}$ as input.

5

6 end while

7return $c_{\mathcal{G}}$;

Algorithm 2 Greedy CIM

In Section 5 we analyze how greedy CIM and skeletal greedy CIM perform on
simulated data relative to GES, GIES, MMHC, greedy SP, and the PC algorithm.

##  4\. Edges of $\mathop{\rm CIM}\nolimits_{G}$ for Trees and Cycles

In this section we will examine the edge structure of $\mathop{\rm
CIM}\nolimits_{G}$ in the special cases that $G$ is a tree or a cycle. We
first see that, for trees, all turn pairs $\\{\mathcal{G},\mathcal{H}\\}$
admit a graphical characterization in terms of the structure of the DAGs
$\mathcal{G}$ and $\mathcal{H}$. For a general tree, we also show that two
more types of edges appear in $\mathop{\rm CIM}\nolimits_{G}$, in addition to
turn pairs. We then observe that, with these additional types of edges, we can
completely characterize the edges of $\mathop{\rm CIM}\nolimits_{G}$ in some
special cases; namely, when $G$ is a path or a cycle.

###  4.1. Trees

As we saw in Example 3.11, turn pairs do not all come from changing the
direction of a single edge in one of the DAGs labeling its two vertices.
However, the following proposition states that, for trees, all turn pairs do
indeed arise from such a combinatorial move. That is, the converse of
Proposition 3.10 holds when the underlying skeleton $G$ is a tree.

######  Proposition 4.1.

Assume $\\{\mathcal{G},\mathcal{G}^{\prime}\\}$ is a turn pair where $G$, the
skeleton of $\mathcal{G}$, is a tree. Then there exists a DAG $\mathcal{H}$
such that

  1. (1)

$\mathcal{G}$ and $\mathcal{H}$ are Markov equivalent,

  2. (2)

$i\to j\in\mathcal{H}$,

  3. (3)

$\mathcal{H}_{j\to i}$ is a DAG, and

  4. (4)

$\mathcal{G}^{\prime}$ and $\mathcal{H}_{j\to i}$ are Markov equivalent,

###### Proof.

This is the combined result of Lemma C.1, Lemma C.2 and Lemma C.3. ∎

Thus, for trees, turn pairs are exactly the turning moves of [8] utilized in
the turning phase of the GIES algorithm. We now introduce two new types of
edges of $\mathop{\rm CIM}\nolimits_{G}$ that arise when $G$ is a tree.
Similar to how turn pairs are motivated by the combinatorial move of turning
an edge in one DAG to produce another (non-Markov equivalent) DAG, the new
edges arise from a similar graphical intuition. The idea this time is that we
shift and add v-structures along a path in $G$.

######  Definition 4.2 (Shift).

Let $\mathcal{G}$ and $\mathcal{H}$ be two DAGs on node set $[p]$. We say the
pair $\\{\mathcal{G},\mathcal{H}\\}$ is a _shift_ if there exists a path
$\pi=\langle i_{0},i_{1},\ldots,i_{2m+1}\rangle$ in $\mathcal{G}$ and
$\mathcal{H}$ such that

$c_{\mathcal{H}}-\sum_{S\in\mathcal{S}_{\pi,\mathop{\rm
odd}\nolimits}}e_{S}=c_{\mathcal{G}}-\sum_{S\in\mathcal{S}_{\pi,\mathop{\rm
even}\nolimits}}e_{S},$

where we have $\mathcal{S}_{\pi,\mathop{\rm
odd}\nolimits}\coloneqq\big{\\{}\\{i_{j-1},i_{j},i_{j+1}\\}\colon
j=1,3,\ldots,2m-1\big{\\}}$ and $\mathcal{S}_{\pi,\mathop{\rm
even}\nolimits}\coloneqq\big{\\{}\\{i_{j-1},i_{j},i_{j+1}\\}\colon
j=2,4,\ldots,2m\big{\\}}$.

######  Definition 4.3 (Split).

Let $\mathcal{G}$ and $\mathcal{H}$ be two DAGs on node set $[p]$. We say the
pair $\\{\mathcal{G},\mathcal{H}\\}$ is a _split_ if there exists a path
$\pi=\langle i_{0},i_{1},\ldots,i_{2m}\rangle$ such that

$c_{\mathcal{H}}-\sum_{S\in\mathcal{S}_{\pi,\mathop{\rm
odd}\nolimits}}e_{S}=c_{\mathcal{G}}-\sum_{S\in\mathcal{S}_{\pi,\mathop{\rm
even}\nolimits}}e_{S},$

where we have $\mathcal{S}_{\pi,\mathop{\rm
odd}\nolimits}\coloneqq\big{\\{}\\{i_{j-1},i_{j},i_{j+1}\\}\colon
j=1,3,\ldots,2m-1\big{\\}}$ and $\mathcal{S}_{\pi,\mathop{\rm
even}\nolimits}\coloneqq\big{\\{}\\{i_{j-1},i_{j},i_{j+1}\big{\\}}\colon
j=2,4,\ldots,2m-2\\}$.

Both shifts and splits correspond to edges of $\mathop{\rm CIM}\nolimits_{G}$
when $G$ is a tree.

######  Proposition 4.4.

Let $\mathcal{G}$ and $\mathcal{H}$ be two DAGs with the same skeleton $G$,
and suppose that $G$ is a tree. If $\\{\mathcal{G},\mathcal{H}\\}$ is a split
or a shift then $\mathop{\rm conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$
is an edge of $\mathop{\rm CIM}\nolimits_{G}$.

###### Proof.

This is the combined result of Proposition C.4 and Proposition C.5. ∎

While the above proposition only applies to $\mathop{\rm CIM}\nolimits_{G}$
when $G$ is a tree, we believe that shifts and splits can be generalized to
edges of $\mathop{\rm CIM}\nolimits_{G}$ for more arbitrary $G$. For instance,
in the coming subsection we see that these moves also label edges of
$\mathop{\rm CIM}\nolimits_{G}$ when $G$ is a cycle.

###  4.2. Paths and Cycles

Let $I_{p}$ denote the path of length $p-1$ and $C_{p}$ denote the cycle of
length $p$. In this section, we will give a complete characterization of the
edges of $\mathop{\rm CIM}\nolimits_{I_{p}}$ and $\mathop{\rm
CIM}\nolimits_{C_{p}}$. To do this we will make use of another well-known
polytope. Let $G=([p],E)$ be an undirected graph. A set of nodes
$S\subseteq[p]$ is called _stable_ (or _independent_) if no nodes of $S$ are
joined by an edge. Given a set $S\subseteq[p]$, its _incidence vector_
$\chi_{S}\in\\{0,1\\}^{p}$ is defined by

$\chi_{S}(u)=\begin{cases}1&\mbox{if $u\in S$},\\\ 0&\mbox{if $u\notin S$}.\\\
\end{cases}$

The _stable set polytope_ of $G$ is the convex hull

$\mathop{\rm STAB}\nolimits(G)\coloneqq\mathop{\rm
conv}\nolimits\left(\chi_{S}:\mbox{ $S$ is a stable set in
$G$}\right)\subseteq\mathbb{R}^{p}.$

######  Proposition 4.5.

For the path $I_{p}$ on $p\geq 2$ nodes, $\mathop{\rm
CIM}\nolimits_{p}=\mathop{\rm STAB}\nolimits(I_{p-2})$. Similarly, for the
cycle $C_{p}$ on $p\geq 4$ nodes, $\mathop{\rm
CIM}\nolimits_{C_{p}}=\mathop{\rm STAB}\nolimits(C_{p})$.

###### Proof.

Since $I_{p}$ is the path on $p$ nodes with edges $\\{i,i+1\\}$ for all
$i\in[p-1]$ then for every pair of characteristic imsets $c_{\mathcal{G}}$,
$c_{\mathcal{H}}$ where $\mathcal{G}$ and $\mathcal{H}$ are DAGs with skeleton
$I_{p}$, we have that $c_{\mathcal{G}}(S)=c_{\mathcal{H}}(S)$ for all
$S\subseteq[p]$ with $|S|\geq 2$ and $S\neq\\{i-1,i,i+1\\}$ for any
$i\in\\{2,\ldots,p-1\\}$. Hence, $\mathop{\rm CIM}\nolimits_{I_{p}}$ is
affinely equivalent to its projection into $\mathbb{R}^{p-2}$, where we
associate the standard basis vector $e_{i-1}$ with the standard basis vector
$e_{\\{i-1,i,i+1\\}}$ in $\mathbb{R}^{2^{p}-p-1}$. We let
$\rho(c_{\mathcal{G}})$ denote the image of $c_{\mathcal{G}}$ under this
projection. The natural bijection between MECs with skeleton $I_{p}$ and
independent sets of $I_{p-2}$ described in [15, Theorem 2.1] then implies that

$\displaystyle\\{\rho(c_{\mathcal{G}})\in\mathbb{R}^{p-2}\colon\mathcal{G}$
$\displaystyle\text{ is a DAG with skeleton $I_{p}$}\\}=$
$\displaystyle\left\\{\chi_{S}\in\mathbb{R}^{p-2}\colon S\text{ an independent
set in $I_{p-2}$}\right\\}.$

Similarly, since $C_{p}$ is the cycle on $p$ nodes with edges $\\{i,i+1\\}$
for $i\in[p-1]$ and $\\{1,p\\}$, and $p\geq 4$, then for every pair of imsets
$c_{\mathcal{G}}$ and $c_{\mathcal{H}}$ where $\mathcal{G}$ and $\mathcal{H}$
are DAGs with skeleton $C_{p}$, we have that
$c_{\mathcal{G}}(S)=c_{\mathcal{H}}(S)$ for all $S\subseteq[p]$ with $|S|\geq
2$ and $S\neq\\{i-1,i,i+1\\}$ for every $i\in[p]$ (where we treat addition
modulo $p$). Hence similar to the case of $I_{p}$, the characteristic imset
polytope $\mathop{\rm CIM}\nolimits_{p}$ is affinely equivalent to its
projection into $\mathbb{R}^{p}$, where we map the standard basis vector
$e_{i-1,i,i+1}$ in $\mathbb{R}^{2^{p}-p-1}$ to the standard basis vector
$e_{i-1}$ in $\mathbb{R}^{p}$, for all $i\in[p]$. Again, applying the
bijection in [15, Theorem 2.1] between MECs with skeleton $C_{p}$ and
independent sets in $C_{p}$ implies that

$\\{\rho(c_{\mathcal{G}})\in\mathbb{R}^{p}:c_{\mathcal{G}}\in\mathop{\rm
CIM}\nolimits_{C_{p}}\\}=\\{\chi_{S}\in\mathbb{R}^{p}:S\text{ an independent
set in $C_{p}$}\\},$

which completes the proof. ∎

Since $\mathop{\rm CIM}\nolimits_{I_{p}}$ and $\mathop{\rm
CIM}\nolimits_{C_{p}}$ are affinely equivalent to stable set polytopes, we can
apply a result of Chvátal [5] to give a complete characterization of the edges
of $\mathop{\rm CIM}\nolimits_{I_{p}}$ and $\mathop{\rm CIM}\nolimits_{C_{p}}$
in terms of the families of edges of $\mathop{\rm CIM}\nolimits_{G}$
characterized in Section 3 and Section 4.1.

######  Theorem 4.6.

[5, Theorem 6.2] Let $G=([p],E)$ be an undirected graph, let
$a,b\in\mathbb{R}^{p}$ be two vertices of $\mathop{\rm STAB}\nolimits(G)$, and
let $A$ and $B$ be their corresponding independent sets. Then $\mathop{\rm
conv}\nolimits(a,b)$ is an edge of $\mathop{\rm STAB}\nolimits(G)$ if and only
if the subgraph of $G$ induced by $A\setminus B\cup B\setminus A$ is
connected.

Hence, to show the desired characterization of the edges of $\mathop{\rm
CIM}\nolimits_{I_{p}}$ and $\mathop{\rm CIM}\nolimits_{C_{p}}$, it suffices to
characterize the pairs of stable sets in $I_{p}$ and $C_{p}$, respectively,
for which the subgraph of $I_{p}$ (or $C_{p}$) induced by the symmetric
difference $A\setminus B\cup B\setminus A$ is connected (i.e., a path or the
full cycle).

######  Lemma 4.7.

Let $A$ and $B$ be independent sets in $I_{p}$ (or $C_{p}$). Then $\mathop{\rm
conv}\nolimits(\chi_{A},\chi_{B})$ is an edge of $\mathop{\rm
STAB}\nolimits(I_{p})$ (or $\mathop{\rm STAB}\nolimits(C_{p})$) if and only if

  1. (1)

$A\setminus B=\\{i,i+2,\ldots,i+2j\\}$ for some $i$ and $j$, and

  2. (2)

$B\setminus A=\\{i+1,i+3,\ldots,i+2j-1\\}$ or $B\setminus
A=\\{i+1,i+3,\ldots,i+2j+1\\}$.

###### Proof.

The proof for $C_{p}$ works the same as for $I_{p}$ by taking addition modulo
$p$, so we only state it for $I_{p}$. Suppose that $A$ and $B$ are two
independent sets in $I_{p}$ such that $A\setminus B$ and $B\setminus A$
satisfy conditions $(1)$ and $(2)$. Then $A\setminus B\cup B\setminus
A=\\{i,i+1,i+2,\ldots,i+2j+1\\}$ for some $i$ and $j$, and hence the induced
subgraph on this set is connected. It follows from Theorem 4.6 that
$\mathop{\rm conv}\nolimits(\chi_{A},\chi_{B})$ is an edge of $\mathop{\rm
STAB}\nolimits(I_{p})$.

Conversely, if $A$ and $B$ are independent sets of $I_{p}$ such that
$\mathop{\rm conv}\nolimits(\chi_{A},\chi_{B})$ is an edge of $\mathop{\rm
STAB}\nolimits(I_{p})$, then by Theorem 4.6, we know that the subgraph of
$I_{p}$ induced by $A\setminus B\cup B\setminus A$ is connected, and hence
must be a subpath of $I_{p}$, say $\langle i,i+1,\ldots,i+t\rangle$. Since $A$
and $B$ are independent, then two neighbors on this path cannot belong to the
same set $A$ or $B$. It follows that $A\setminus B$ and $B\setminus A$ must
satisfy conditions $(1)$ and $(2)$, completing the proof. ∎

As a consequence of Lemma 4.7, we can characterize all edges of $\mathop{\rm
CIM}\nolimits_{I_{p}}$ and $\mathop{\rm CIM}\nolimits_{C_{p}}$.

######  Theorem 4.8.

Let $c_{\mathcal{G}}$ and $c_{\mathcal{H}}$ be two characteristic imsets for
DAGs whose skeletons both are the path $I_{p}$ (or the cycle $C_{p}$). Then
$\mathop{\rm conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ is an edge of
$\mathop{\rm CIM}\nolimits_{I_{p}}$, for $p\geq 2$ (or $\mathop{\rm
CIM}\nolimits_{C_{p}}$, for $p\geq 4$) if and only if
$\\{\mathcal{G},\mathcal{H}\\}$ is a v-structure addition, shift, or split.

###### Proof.

By Proposition 4.5, we know that $\mathop{\rm
CIM}\nolimits_{I_{p}}=\mathop{\rm
STAB}\nolimits(I_{p-2})\subseteq\mathbb{R}^{p-2}$, for $p\geq 2$, and
$\mathop{\rm CIM}\nolimits_{C_{p}}=\mathop{\rm
STAB}\nolimits(C_{p})\subset\mathbb{R}^{p}$, for $p\geq 4$, where we have
identified the standard basis vector
$e_{\\{i-1,i,i+1\\}}\in\mathbb{R}^{2^{p}-p-1}$ with the standard basis vector
$e_{i-1}\in\mathbb{R}^{p-2}$ and $e_{i-1}\in\mathbb{R}^{p}$, respectively.
Here, we again consider addition modulo $p$ in the case of the cycle $C_{p}$.
As the same proof works for both the cycle and the path, in the following we
state it only for the path $I_{p}$.

By Lemma 4.7, we get that for two independent sets $A$ and $B$ in $I_{p}$,
$\mathop{\rm conv}\nolimits(\chi_{A},\chi_{B})$ is an edge of $\mathop{\rm
STAB}\nolimits(I_{p-2})$ if and only

  1. (1)

$A\setminus B=\\{i,i+2,\ldots,i+2j\\}$ for some $i$ and $j$, and

  2. (2)

$B\setminus A=\\{i+1,i+3,\ldots,i+2j-1\\}$ or $B\setminus
A=\\{i+1,i+3,\ldots,i+2j+1\\}$.

As $A\setminus B\cup B\setminus A=\\{i,i+1,\ldots,i+m\\}$, where $m=2j$ or
$m=2j+1$ accordingly, it follows that $\mathop{\rm
conv}\nolimits(\chi_{A},\chi_{B})$ is an edge of $\mathop{\rm
STAB}\nolimits(I_{p-2})$ if and only if $\pi=\langle
i,i+1,i+2,\ldots,i+m\rangle$ is a path in $I_{p-2}$, and

$\chi_{A}-\sum_{k\in A\setminus B}e_{k}=\chi_{B}-\sum_{k\in B\setminus
A}e_{k}.$

Following the correspondence between vertices of $\mathop{\rm
CIM}\nolimits_{I_{p}}$ and vertices of $\mathop{\rm STAB}\nolimits(I_{p-2})$
established above, $\mathop{\rm
conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ is an edge of $\mathop{\rm
CIM}\nolimits_{I_{p}}$ if and only if $\pi=\langle
i,i+1,i+2,i+3,\ldots,i+m+2\rangle$ is a path in $I_{p}$ and

$c_{\mathcal{G}}-\sum_{\begin{subarray}{c}\\{k-1,k,k+1\\}:\\\ i+\ell=k\leq
i+m+1\\\ \text{ and $\ell$ is
odd}\end{subarray}}e_{\\{k-1,k,k+1\\}}=c_{\mathcal{H}}-\sum_{\begin{subarray}{c}\\{k-1,k,k+1\\}:\\\
i+\ell=k\leq i+m+1,\\\ \ell\geq 2\text{ and $\ell$ is
even}\end{subarray}}e_{\\{k-1,k,k+1\\}}.$

When $m=0$, then $\\{\mathcal{G},\mathcal{H}\\}$ is a v-structure addition,
when $m>0$ and odd $\\{\mathcal{G},\mathcal{H}\\}$ is a shift, and when $m>0$
and even $\\{\mathcal{G},\mathcal{H}\\}$ is a split. Hence, $\mathop{\rm
conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ is an edge of $\mathop{\rm
CIM}\nolimits_{I_{p}}$ if and only if $\\{\mathcal{G},\mathcal{H}\\}$ is a
shift, split, or v-structure addition. ∎

##  5\. Simulations and Computational Results

In Section 3 we proposed two algorithms, skeletal greedy CIM (Algorithm 1),
and greedy CIM (Algorithm 2). In Section 5.1 we compare the performance of
these algorithms on simulated data with the state-of-the-art. In Section 5.2
we give some computational results regarding the characteristic imset polytope
$\mathop{\rm CIM}\nolimits_{4}$ that help explain the results seen in Section
5.1.

###  5.1. Simulations

An implementation of all algorithms discussed in this section is available at
[16]. The simulated data was produced in $R$ [14] using linear structural
equation models with Gaussian noise. The true underlying DAG
$\mathcal{G}^{\ast}$ was chosen randomly using an Erdős-Rényi model on $p=8$
vertices and expected neighborhood size $d$, which we varied over the interval
$[0.5,7]$. Each edge $i\to j$ was given an edge-weight $w_{i,j}$ chosen
uniformly from $[-1,-0.25]\cup[0.25,1]$. The direction of the edges were given
by a linear order of the vertices, sampled uniformly from all linear orders.
We then sampled from a multivariate Gaussian distribution over the random
variables $X_{1},\dots,X_{p}$ where
$X_{i}=\varepsilon_{i}+\sum_{k\in\operatorname{pa}_{\mathcal{G}^{\ast}}(i)}w_{k,i}X_{k}$.
Here the $\varepsilon_{i}$ are independent and normally distributed random
variables with mean $0$ and variance $1$. We produced $100$ models for each
$d$ and from each model we drew $n=10,000$ samples. This was done via the MASS
library [27]. As the implementation of greedy CIM and skeletal greedy CIM
available at [16] is done in Python, we used the rpy2 module for the $R$-to-
Python conversions.

To produce the undirected skeleton in Algorithm 1 we used the skeleton
algorithm in the pcalg package [8, 9]. The algorithm skeleton requires a
significance level $\alpha$ for the CI tests, which we varied over
$\\{0.01,0.001,0.0001\\}$. Skeletal greedy CIM, greedy CIM, GES, and GIES all
aim to optimize BIC (see Equation 2.2) which we computed for our models via
the GaussL0penObsScore-class from the pcalg package. In order to fairly
compare the different algorithms that are each a single edge-walk along a
convex polytope (according to Theorem 3.17) we ran greedy SP with no restarts
and unbounded search depth ($r=1$, $d=\infty$) [18]. In Figure 4 we see the
ratio of models recovered from the samples versus the expected neighborhood
size $d$. In Figure 5 we compare the model recovery rate and the average
Structural Hamming Distance (SHD) (see [26] for a definition) to the true
model versus the average expected neighborhood size $d$.

a $p=8$, $n=10,000$, $\alpha=0.01$

b $p=8$, $n=10,000$, $\alpha=0.001$

c $p=8$, $n=10,000$, $\alpha=0.0001$

d $p=8$, $n=10,000$

Figure 4. Ratio of models recovered versus the expected neighborhood size of
the true graph. In Figures 4a–4c we ran PC, MMHC, and skeletal greedy CIM on
$100$ models. Each model had $p=8$ nodes and the weights of the edges were
sampled uniformly in $[-1,-0.25]\cup[0.25,1]$. We used a sample size of
$n=10,000$, and varied $\alpha$ in $\\{0.01,0.001,0.0001\\}$. In Figure 4d we
see how GES, GIES, and greedy CIM perfomed on the same data.

In Figure 4a, Figure 4b, and Figure 4c we compared all algorithms relying on
CI tests (i.e., all constraint-based and hybrid algorithms). We see that
skeletal greedy CIM has a higher recovery rate than greedy SP, MMHC and the PC
algorithm. Note that both skeletal greedy CIM and PC are restricted by the
performance of the skeleton algorithm. Thus we have also included how often
this algorithm finds the true skeleton. We see that, if the correct skeleton
is identified, skeletal greedy CIM almost always learns the true MEC. However,
the same is not true for the PC algorithm. Thus, we cannot expect the
performance of skeletal greedy CIM to increase by much, even if more edges of
$\mathop{\rm CIM}\nolimits_{G}$ are identified and added to the
implementation. The main difference of skeletal greedy CIM and MMHC is that
skeletal greedy CIM relies on CI tests to determine the skeleton, as opposed
to MMHC, which only restricts to a set of possible skeletons. The fact that
skeletal greedy CIM outperforms MMHC in Figure 4 suggests that the set of
moves used by skeletal greedy CIM, given by turn pairs, is diverse enough that
there is no advantage of hybrid methods that rely on score-based edge
specification from a restricted set compared to methods that fully specify a
skeleton and then rely on turning edges. This increase in accuracy could also
be explained by the number of edge pairs in comparison to the total number of
edges in $\mathop{\rm CIM}\nolimits_{p}$. As we will see in Section 5.2, we
seem to have found and implemented many edges of $\mathop{\rm
CIM}\nolimits_{G}$, but very few in total of $\mathop{\rm CIM}\nolimits_{p}$.
Thus, MMHC is restricted when moving between MECs with different skeletons,
which is a non-issue for skeletal greedy CIM.

In Figure 4d we compared the purely score-based algorithms. By Proposition
3.10 and Proposition 3.15, greedy CIM can do all moves of GES and GIES, and
more. Recall that greedy CIM was implemented using edge pairs and turn pairs,
performing only a depth-first search, whereas GES and GIES perform recurrent
phased, breadth-first searches. To estimate the extent to which turn pairs and
edge pairs generalize the moves of GES and GIES, we also implemented a
recurrent phased breadth-first version of greedy CIM. That is, we first only
consider edge pairs that increase the number of edges, then the ones that
decrease the number of edges, then we enter the turn phase. We then cycle
through these three phases, analogous to GIES. We call this algorithm
_recurrent phased breadth-first greedy CIM_. As can be seen in Figure 4d, this
version of greedy CIM replicates the output of GIES. On the other hand, GES
and GIES perform better than greedy CIM. This suggests that recurrent phased
approaches to optimizing BIC will typically yield better results. Moreover,
the fact that recurrent phased breadth-first greedy CIM matches the best
performing algorithm (GIES) suggests that characterizing more edges of
$\mathop{\rm CIM}\nolimits_{p}$ and incorporating them into the implementation
of greedy CIM could yield even better performing greedy score-based causal
discovery algorithms.

a The ratio of models recovered.

b The average SHD between the true model and the result of different
algorithms.

Figure 5. A comparison between all algorithms discussed based on $100$
simulations. Each model had $p=8$ nodes and the weights of the edges were
sampled uniformly in $[-1,-0.25]\cup[0.25,1]$. We used a sample size of
$n=10,000$, and $\alpha=0.0001$.

In Figure 5 we give a complete comparison of the recovery ratios of all
algorithms discussed as well as the SHD between the result for each algorithm
and the true model. Even though greedy CIM has a higher recovery ratio than
the PC algorithm and MMHC, the average SHD is higher as well. This indicates
that, while greedy CIM typically succeeds in finding the true DAG more often
than these algorithms, when it fails to do so it returns a less accurate MEC
than the other algorithms. Thus, greedy CIM likely does a move early on from
which it cannot move, since we do not have access to all edges of $\mathop{\rm
CIM}\nolimits_{p}$. (Note that, as BIC is linear over $\mathop{\rm
CIM}\nolimits_{p}$, this would never happen given a complete characterization
of the edges of $\mathop{\rm CIM}\nolimits_{p}$.) On the other hand, skeletal
greedy CIM is one of the top performers in regards to average SHD. As opposed
to skeletal greedy CIM, greedy CIM will probably improve if more edges are
found. As can be seen in Section 5.2 the number of edges of the form
$\mathop{\rm conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$, where
$\mathcal{G}$ and $\mathcal{H}$ have the same skeleton, seems to be only a
small fraction of all edges of the polytope $\mathop{\rm CIM}\nolimits_{p}$.

###  5.2. The characteristic imset polytope for $p=4$

In this section we will study the edges of $\mathop{\rm CIM}\nolimits_{4}$ as,
in this case, $p$ is small enough for us to analyze the polytope with the help
of polymake [2, 7]. Using this software, we calculated how many edges are
encoded by turn and edge pairs. These numbers appear in Figure 6.

Type of edge | # edges
---|---
v-structure additions | 96
Buddings | 60
Flips | 24
Turn pairs | 180

Type of edge | # edges
---|---
Edge additions | 276
Edge pairs that are |
not edge additions | 480
Edge pairs | 756

Figure 6. The number of each type of edge in $\mathop{\rm CIM}\nolimits_{4}$.

The polytope $\mathop{\rm CIM}\nolimits_{4}$ has $241$ edges of the form
$\mathop{\rm conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ where
$\mathcal{G}$ and $\mathcal{H}$ have the same skeleton. As we can see from
Figure 6, all but possibly $61$ of these edges constitute turn pairs. In
Figure 7, we have counted the number of edges that are not turn pairs and
divided them into cases depending on the skeleton.

$G$ | # edges | Case #
---|---|---
| 21 | Case 1
| 16 | Case 2
| 12 | Case 3
| 12 | Case 4
Figure 7. The number of edges that are not turn pairs in $\mathop{\rm
CIM}\nolimits_{G}$, where $G$ has four vertices, counted by underlying graph.
Here, $G$ is specified up to isomorphism.

Notice that we only give $G$ up to isomorphism. We have already characterized
the missing edges in case 1 in Section 4.2. For cases 2 and 3 we prove the
following proposition.

######  Proposition 5.1.

Assume $G^{\prime}=([p-1],E^{\prime})$ is a vertex disjoint union of complete
graphs $K_{p_{1}},\dots,K_{p_{m}}$. Let $G=([p],E)$ be the graph with
$\operatorname{ne}_{G}(p)=[p-1]$ and the induced graph
$G|_{[p-1]}=G^{\prime}$. Then $\mathop{\rm CIM}\nolimits_{G}$ is a $d$-simplex
with $d=2^{p-1}-1-\sum_{s\in[m]}\left(2^{p_{s}}-1\right)$.

To prove this, we need one lemma. Given a finite set $P$ let $\mathbb{R}[P]$
be the vector space of dimension $|P|$ where the basis vectors are indexed by
the elements of $P$.

######  Lemma 5.2.

Given a finite partial order $(P,\preceq)$. Define $b_{p}$ for any $p\in P$ as

$b_{p}\coloneqq\sum_{q\preceq p}e_{q}$

where $e_{q}$ denotes the standard basis of $\mathbb{R}[P]$. Then
$\\{b_{p}\\}_{p\in P}$ is a basis for $\mathbb{R}[P]$.

###### Proof.

By the Möbius inversion formula $e_{p}=\sum_{q\preceq p}\mu_{P}(q,p)b_{q}$.
Thus $b_{p}$ is the image of $e_{p}$ under an invertible linear
transformation. The result follows. ∎

###### Proof of Proposition 5.1.

We begin by counting the number of MECs. As the MEC is determined by the
skeleton and v-structures, and we have fixed the skeleton, we only need to
consider sets $\\{i,j,k\\}$ such that $G|_{\\{i,j,k\\}}=i-j-k$. From the
assumptions all triples on this form have $j=p$, $i\in K_{p_{s}}$, and $k\in
K_{p_{s^{\prime}}}$ where $s\neq s^{\prime}$.

Thus, the MEC of $\mathcal{G}$ is completely determined by
$\operatorname{pa}_{\mathcal{G}}(p)$. If
$|\operatorname{pa}_{\mathcal{G}}(p)|\leq 1$ we have no v-structures, and all
such DAGs are Markov equivalent. Likewise, if
$\operatorname{pa}_{\mathcal{G}}(p)\subseteq K_{p_{s}}$ for some $s\in[m]$.
Hence, the number of MECs are counted as $1$ plus the number of ways to choose
$\operatorname{pa}_{\mathcal{G}}(p)$ such that
$|\operatorname{pa}_{\mathcal{G}}(p)|\geq 2$ and
$\operatorname{pa}_{\mathcal{G}}(p)\not\subseteq K_{p_{s}}$ for any $s\in[m]$.
Using that $\sum_{s\in[m]}p_{s}=p-1$, this quantity is

$1+2^{p-1}-(p-1)-1-\sum_{s\in[m]}\left(2^{p_{s}}-p_{s}-1\right)=2^{p-1}-\sum_{s\in[m]}\left(2^{p_{s}}-1\right).$

Next we wish to show that all $c_{\mathcal{G}}$ are affinely independent. Let
$\mathcal{D}$ be a DAG such that
$\operatorname{pa}_{\mathcal{D}}(p)=\emptyset$ and skeleton $G$, then
$\mathcal{D}$ has no v-structures. Using the above, a straightforward
calculation then gives us that for any DAG $\mathcal{G}$ with skeleton $G$ we
get

$c_{\mathcal{G}}=c_{\mathcal{D}}+\sum_{S\in\mathcal{S}}e_{S}$

where $\mathcal{S}=\left\\{T\cup\\{p\\}\colon
T\subseteq\operatorname{pa}_{\mathcal{G}}(p),\centernot\exists s\in[m]\textrm{
such that }T\subseteq_{p_{s}}K_{p_{s}}\right\\}$. Notice that we do not have
any sets of size $2$ or less in this set. Moreover, the parents of $p$
uniquely determines the MEC unless we are in the class containing
$\mathcal{D}$. Thus we can infer a partial order on characteristic imsets as
$c_{\mathcal{G}}\preceq c_{\mathcal{H}}$ if $c_{\mathcal{G}}=c_{\mathcal{D}}$
or
$\operatorname{pa}_{\mathcal{G}}(p)\subseteq\operatorname{pa}_{\mathcal{H}}(p)$.
Notice that this is well-defined since the parents of $p$ is determined by the
MEC in all MECs except for the one containing $\mathcal{D}$, which by
definition is the smallest one in this partial order. Thus we can apply Lemma
5.2 to

$\left\\{c_{\mathcal{G}}-c_{\mathcal{D}}\colon\mathcal{G}\text{ a DAG with
skeleton $G$ and $\mathcal{G}$ is not Markov equivalent to
$\mathcal{D}$}\right\\},$

and the result follows. ∎

The only case left from Figure 7 is case 4. In this case, again, $\mathop{\rm
CIM}\nolimits_{G}$ is a simplex. We can prove this in a similar manner, using
Lemma 5.2.

######  Proposition 5.3.

Let $G=([p],E)$ be the complete graph missing only the edge $1-2$, that is
$K_{p}\setminus\\{1,2\\}$. Then $\mathop{\rm CIM}\nolimits_{G}$ is a simplex
of dimension $2^{p-2}-1$.

###### Proof.

By the structure of $G$ the only possible v-structures are on the form
$1\rightarrow i\leftarrow 2$ for some $2<i\leq p$. We wish to show that for
any subset $S\subseteq\\{3,\dots p\\}$ we have a DAG $\mathcal{D}_{S}$ such
that $1\rightarrow i\leftarrow 2\in\mathcal{D}_{S}$ for all $i\in S$ but for
no $i\in\\{3,\dots p\\}\setminus S$. As every MEC is characterized by the
v-structures we will then have a representative from each MEC.

As for the construction of $\mathcal{D}_{S}$, for every $i\in S$ we direct the
edges $1-i-2$ as $1\rightarrow i\leftarrow 2$ and for every $i\in\\{3,\dots
p\\}\setminus S$ we direct the edges $1-i-2$ as $1\leftarrow i\rightarrow 2$.
Notice that we have thus far not created any cycles. Then the currently
directed edges induces a partial order on $[p]$. Extending this order to a
total order and directing the remaining edges of $\mathcal{D}_{S}$ according
to this order gives us a DAG. Notice that no new v-structures can have been
created in this last step. This because all possible triples that could have
been v-structures were already directed. Then we can calculate the
characteristic imset of $\mathcal{D}_{S}$ as

$c_{\mathcal{D}_{S}}=c_{\mathcal{D}_{\emptyset}}+\sum_{T\in\mathcal{S}}e_{T}$

where $\mathcal{S}=\\{U\cup\\{1,2\\}\colon U\subseteq S,|U|\geq 1\\}$.

Thus we get a partial order on the characteristic imsets as
$c_{\mathcal{D}_{X}}\preceq c_{\mathcal{D}_{Y}}\Leftrightarrow X\subseteq Y$,
and the rest follows by Lemma 5.2. ∎

It follows that we have a complete classification of the edges of $\mathop{\rm
CIM}\nolimits_{G}$ when $G=([4],E)$. $\mathop{\rm CIM}\nolimits_{4}$ has
$4259$ edges in total. As can be seen in Figure 6, $180$ of these are turn
pairs, $756$ are edge pairs, and $61$ additional edges are characterized by
Theorem 4.8, Proposition 5.1 and Proposition 5.3. Thus, we have an explanation
of $997$ out of $4259$ edges of $\mathop{\rm CIM}\nolimits_{4}$. Hence, turn
pairs and edge pairs constitute less than a quarter of all edges. As discussed
in Section 5.1, we capture relatively many edges of $\mathop{\rm
CIM}\nolimits_{G}$, for given $G$, with turn pairs. In total $180$ out of
$241$. However, we capture very few edges outside of the faces $\mathop{\rm
CIM}\nolimits_{G}$ with edge pairs: only $756$ out of $4018$. The lack of
characterized edges between MECs with different skeletons may explain why MMHC
performs worse than skeletal greedy CIM.

##  6\. Discussion

In this paper, we have studied the characteristic imset polytope $\mathop{\rm
CIM}\nolimits_{p}$ and its faces $\mathop{\rm CIM}\nolimits_{G}$. We have
shown that most common moves utilized in greedy causal discovery algorithms,
such as reversing or adding an edge, correspond to edges of $\mathop{\rm
CIM}\nolimits_{p}$. Utilizing this, we introduced skeletal greedy CIM
(Algorithm 1) and greedy CIM (Algorithm 2). These algorithms are greedy depth-
first search edge-walks over the $\mathop{\rm CIM}\nolimits_{G}$ and
$\mathop{\rm CIM}\nolimits_{p}$ polytopes, respectively. Skeletal greedy CIM
is a hybrid algorithm that first does CI tests to learn a skeleton $G$, and
then passes to a restricted edge-walk over $\mathop{\rm CIM}\nolimits_{G}$,
attempting to maximize the BIC by walking along edges labeled by turn pairs or
edge pairs. Greedy CIM performs a similar restricted edge-walk over
$\mathop{\rm CIM}\nolimits_{p}$. Both algorithms could likewise be implemented
using any score-equivalent and decomposable score function. We showed that
(recurrent phased breadth-first) greedy CIM is a geometric generalization of
GES and GIES in the case of purely observational data. Consequently, GES and
GIES admit a geometric interpretation as edge-walks along a convex polytope.
It further follows that MMHC has a similar interpretation. As greedy SP
already has such an interpretation in terms of the DAG associahedron [12] it
follows that all greedy algorithms discussed in this paper have a geometric
interpretation as an edge-walk along a convex polytope. In this sense, we have
observed that greedy causal discovery is geometric.

An implementation of skeletal greedy CIM and greedy CIM is available at [16].
Given data drawn from a joint distribution on 8 variables, these
implementations return a graph in approximately $1$ and 10 seconds on average,
respectively. We believe that a more efficient implementation is possible, but
we leave that for future work.

Skeletal greedy CIM was shown to outperform the other hybrid algorithms such
as MMHC and greedy SP on simulated Gaussian data. The main difference between
these algorithms is that skeletal greedy CIM relies on CI tests to determine
the skeleton, while MMHC only utilizes the CI tests to restrict the set of
possible skeletons. This is likely due to the fact that we capture a
relatively small fraction of the edges between MECs with different skeletons.
Thus, finding more edges of $\mathop{\rm CIM}\nolimits_{p}$ could lead to a
better algorithm, outperforming both.

Finally, recall that GIES first adds in edges without considering the deletion
of edges, then deletes edges without considering the addition of edges, then
reverses edges, and then cycles through each of these phases. GIES also does a
breadth-first search. Thus, we believe that the depth-first nature of greedy
CIM induces a preference on the edges which is avoided by GIES via a breadth-
first search. A recurrent phased breadth-first version of greedy CIM was
implemented and performed identically, in terms of accuracy, with GIES in our
simulations. A natural follow-up question is then: how often, if ever, does
recurrent phased breadth-first search greedy CIM utilize the extra moves to
which it has access? Presently, what we can surmise is that finding and
implementing more edges of the $\mathop{\rm CIM}\nolimits_{p}$ polytope could
lead to even better greedy causal discovery algorithms than the current front-
runners (GIES and recurrent phased breadth-first greedy CIM).

##  7\. Acknowledgements

All three authors were partially supported by the Wallenberg AI, Autonomous
Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg
Foundation. Liam Solus was partially supported a Starting Grant (No.
2019-05195) from Vetenskapsrådet (The Swedish Research Council).

##  Appendix A Basics of Graphs and Polytopes

In this chapter we will introduce the fundamentals of graphs and polytopes.
For the more interested reader we recommend [10] for a background on graphs
and DAG models, and [29] for a background on polytopes.

###  A.1. Graph Fundamentals

Here we will discuss the graph theory we will need. Let $G=([p],E)$ be an
undirected graph. For a pair of distinct nodes $i,j\in[p]$ we denote $i-j\in
G$ if $\\{i,j\\}\in E$. In this paper we assume all graphs are simple. That
means we do not have loops, edges in the form $i-i\in G$, or multiple edges. A
node $k$ is said to be a _neighbor_ of $i$ if $i-k\in G$. We denote the set of
neighbors of $i$ in $G$ by $\operatorname{ne}_{G}(i)$. Given an undirected
graph $G$ we say that $(k_{0},k_{1},\dots,k_{n})$ is a _path_ in $G$ if
$k_{i}-k_{i+1}\in G$ for all $0\leq i\leq n-1$. A path is a _cycle_ if
$k_{0}=k_{n}$ and $G$ is called a _forest_ if there does not exists a cycle in
$G$. If there exists a path between any two nodes $G$ is called _connected_
and a connected forest is called a _tree_.

For any directed graph $\mathcal{G}=([p],E)$ we likewise write $i\to
k\in\mathcal{G}$ if $(i,k)\in E$. Then $k$ is said to be a _parent_ of $i$ if
$k\to i\in\mathcal{G}$. The set of parents of $i$ in $\mathcal{G}$ is denoted
by $\operatorname{pa}_{\mathcal{G}}(i)$. A node $i$ is the _child_ of $k$ if
$k$ is the parent of $i$, and we likewise let
$\operatorname{ch}_{\mathcal{G}}(k)$ be the set of all children of $k$. The
_skeleton_ of a directed graph $\mathcal{G}$ is the undirected graph $G$ where
we replace $k\to i\in\mathcal{G}$ with $k-i\in G$. We say that two nodes are
neighbors in $\mathcal{G}$ if they are neighbors in the skeleton of
$\mathcal{G}$. For a directed graph $\mathcal{G}$ we say that $\langle
k_{0},k_{1},\dots,k_{n}\rangle$ is a _directed path_ from $k_{0}$ to $k_{n}$
in $\mathcal{G}$ if $k_{i}\to k_{i+1}\in\mathcal{G}$ for all $0\leq i\leq
n-1$. We say that $\langle k_{0},k_{1},\dots,k_{n}\rangle$ is a path in
$\mathcal{G}$ if it is a path in the skeleton of $G$. Then a _directed cycle_
is a directed path where $k_{0}=k_{n}$ and $\mathcal{G}$ is a _directed
acyclic graph_ (DAG) if $\mathcal{G}$ is a directed graph and $\mathcal{G}$
does not have a directed cycle. A node $i$ is the _descendant_ of $k$ if there
exists a directed path from $k$ to $i$, we denote this set with
$\operatorname{de}_{\mathcal{G}}(k)$. Every other node that is not a decendent
of $k$ is a _non-descendent_ , and the set of all such nodes is denoted
$\operatorname{nd}_{\mathcal{G}}(i)$. The _induced subgraph_
$\mathcal{G}|_{A}=(A,E^{\prime})$, for a subset $A\subseteq[p]$, is the graph
with node set $A$ and we have an edge if and only if we have an edge in
$\mathcal{G}$ and both endpoints lie in $A$.

###  A.2. Polytopes

Let $p_{1},\dots,p_{n}$ be points in $\mathbb{R}^{d}$. We define the _convex
hull_ of $p_{1},\dots,p_{n}$ as

$\mathop{\rm
conv}\nolimits(p_{i})=\left\\{\sum_{i=0}^{n}\alpha_{i}p_{i}\colon\sum_{i=0}^{n}\alpha_{i}=1\right\\}.$

A _polytope_ $P$ is then defined as the convex hull of a finite set of points.
We say that a linear inequality $c^{T}p\leq a$ is _valid_ for a polytope $P$
if it holds for all points $p\in P$. Then a _face_ of $P$ is defined as
$P\cap\\{c^{T}p=a\\}$ where $c^{T}p\leq a$ is a valid inequality. A _vertex_
is any face consisting of a single point. Any face is the convex hull of all
vertices it contains. The dimension of a face is the affine dimension of the
span of all points in that face, or equivalently the affine dimension of the
span of $F$’s vertices. An edge of the polytope is a face of dimension $1$. It
can be shown that any edge is the convex hull of exactly two vertices of the
polytope.

##  Appendix B Proofs to Theorems in Section 3

### Proof of Proposition 3.10

We have the following equality

$c_{\mathcal{G}_{j\to
i}}=c_{\mathcal{G}}+\sum_{S\in\mathcal{A}^{+}}e_{S}-\sum_{S\in\mathcal{A}^{-}}e_{S}$

for some $\mathcal{A}^{+}$ and $\mathcal{A}^{-}$. We begin by giving a
possible description of $\mathcal{A}^{+}$ and $\mathcal{A}^{-}$. We only
changed the edge $j\leftarrow i$. So for any set $S$, the only node that could
have become the child of every other node in $S$, that was not before, is $i$.
Taking this as a definition of $\mathcal{A}^{+}$ we get that $\mathcal{A}^{+}$
is all sets $S$ such that $S\subseteq\operatorname{pa}_{\mathcal{G}_{j\to
i}}(i)\cup\\{i\\}$ and
$S\not\subseteq\operatorname{pa}_{\mathcal{G}}(i)\cup\\{i\\}$. Letting
$\mathcal{A}^{-}$ be all sets $S$ such that $j\in S$ and all other elements of
$S$ has $j$ as a common child in $\mathcal{G}$ but not in $\mathcal{G}_{j\to
i}$, we get $\mathcal{A}^{-}=\\{S\colon
S\not\subseteq\operatorname{pa}_{\mathcal{G}_{j\to i}}(j)\cup\\{j\\},\
S\subseteq\operatorname{pa}_{\mathcal{G}}(j)\cup\\{j\\}\\}$. If we have a set
$S$ such that $\\{i,j\\}\not\subseteq S$, then the graphs induced by
$\mathcal{G}$ and $\mathcal{G}_{j\to i}$ on $S$ are identical and thus $S$ is
neither in $\mathcal{A}^{+}$ nor $\mathcal{A}^{-}$.

If $S\in\mathcal{A}^{+}$, $i$ is the child of every other node in $S$ in
$\mathcal{G}_{j\to i}$, that is
$S\subseteq\operatorname{pa}_{\mathcal{G}_{j\to
i}}(i)\cup\\{i\\}=\operatorname{pa}_{\mathcal{G}}(i)\cup\\{i,j\\}$. The other
way around, if $\\{i,j\\}\subseteq
S\subseteq\operatorname{pa}_{\mathcal{G}_{j\to i}}(i)\cup\\{i\\}$ we did not
have $i$ as a child of $S\setminus\\{i\\}$ in $\mathcal{G}$ but we do in
$\mathcal{G}_{j\to i}$. Thus

$\mathcal{A}^{+}=\left\\{S\cup\\{i,j\\}\colon
S\subseteq\operatorname{pa}_{\mathcal{G}}(i)\right\\}$

and by symmetry

$\mathcal{A}^{-}=\left\\{S\cup\\{i,j\\}\colon
S\subseteq\operatorname{pa}_{\mathcal{G}}(j)\right\\}.$

Thus we see that $\mathcal{A}^{+}\cap\mathcal{A}^{-}=\\{S\cup\\{i,j\\}\colon
S\subseteq\operatorname{pa}_{\mathcal{G}}(i)\cap\operatorname{pa}_{\mathcal{G}}(j)\\}$.

Now let us consider the following cases:

  1. (a)

$\operatorname{pa}_{\mathcal{G}}(i)=\operatorname{pa}_{\mathcal{G}}(j)\backslash\\{i\\}$

  2. (b)

$\operatorname{pa}_{\mathcal{G}}(i)\backslash\operatorname{pa}_{\mathcal{G}}(j)\neq\emptyset\neq\operatorname{pa}_{\mathcal{G}}(j)\backslash(\\{i\\}\cup\operatorname{pa}_{\mathcal{G}}(i))$

  3. (c)

$\operatorname{pa}_{\mathcal{G}}(j)\subsetneq\operatorname{pa}_{\mathcal{G}}(i)\cup\\{i\\}$

    1. (i)

$|\operatorname{pa}_{\mathcal{G}}(i)|\geq 2$

    2. (ii)

$|\operatorname{pa}_{\mathcal{G}}(i)|=1$

  4. (d)

$\operatorname{pa}_{\mathcal{G}}(i)\subsetneq\operatorname{pa}_{\mathcal{G}}(j)\backslash\\{i\\}$

    1. (i)

$|\operatorname{pa}_{\mathcal{G}}(j)\backslash\\{i\\}|\geq 2$

    2. (ii)

$|\operatorname{pa}_{\mathcal{G}}(j)\backslash\\{i\\}|=1$

See Figure 8 for a picture of the different cases.

$i$$j$ a
$\operatorname{pa}_{\mathcal{G}}(i)=\operatorname{pa}_{\mathcal{G}}(j)\backslash\\{i\\}$

$i$$j$ b
$\operatorname{pa}_{\mathcal{G}}(i)\backslash\operatorname{pa}_{\mathcal{G}}(j)\neq\emptyset$
and
$\operatorname{pa}_{\mathcal{G}}(j)\backslash(\\{i\\}\cup\operatorname{pa}_{\mathcal{G}}(i))\neq\emptyset$

$i$$j$ c
$\operatorname{pa}_{\mathcal{G}}(j)\subsetneq\operatorname{pa}_{\mathcal{G}}(i)\cup\\{i\\}$

$i$$j$ d
$\operatorname{pa}_{\mathcal{G}}(i)\subsetneq\operatorname{pa}_{\mathcal{G}}(j)\backslash\\{i\\}$

Figure 8. The four cases in the proof of Proposition 3.10.

  1. (a)

In this case $\mathcal{G}$ and $\mathcal{G}_{j\to i}$ are Markov equivalent.
This was first proved by Chickering in [3]. From the viewpoint of imsets it
follows that $\mathcal{A}^{+}=\mathcal{A}^{-}$ and thus
$c_{\mathcal{G}}=c_{\mathcal{G}_{j\to i}}$ and the result follows.

  2. (b)

Let $S_{i}=\operatorname{pa}_{\mathcal{G}}(i)$ and
$S_{j}=\operatorname{pa}_{\mathcal{G}}(j)\backslash\\{i\\}$. In case this we
claim that $\\{\mathcal{G},\mathcal{G}_{j\to i}\\}$ is a flip with respect to
$(i,j,S_{i},S_{j})$. Indeed, conditions (1)-(3) in Definition 3.5 are direct.
Condition (4) follows from $\operatorname{ne}_{G}(i)\setminus
S_{j}\subseteq\operatorname{pa}_{\mathcal{G}}(i)\setminus\operatorname{pa}_{\mathcal{G}}(j)\neq\emptyset$,
and likewise condition (5). Then we get

$\displaystyle c_{\mathcal{G}_{j\to i}}$
$\displaystyle=c_{\mathcal{G}}+\sum_{S\in\mathcal{A}^{+}}e_{S}-\sum_{S\in\mathcal{A}^{-}}e_{S}$
$\displaystyle=c_{\mathcal{G}}+\sum_{S\in\mathcal{A}^{+}\backslash\mathcal{A}^{-}}e_{S}-\sum_{S\in\mathcal{A}^{-}\backslash\mathcal{A}^{+}}e_{S}$

and

$\displaystyle\mathcal{A}^{+}\backslash\mathcal{A}^{-}$
$\displaystyle=\\{S\cup\\{i,j\\}\colon
S\subseteq\operatorname{pa}_{\mathcal{G}}(i),S\not\subseteq\operatorname{pa}_{\mathcal{G}}(j)\\}$
$\displaystyle=\\{S\cup\\{i,j\\}\colon S\subseteq
S_{i},S\not\subseteq\operatorname{ne}_{G}(j)\\}$
$\displaystyle=\mathcal{S}^{+}.$

The second equality follows as $\mathcal{G}$ is a DAG and thus
$\operatorname{pa}_{\mathcal{G}}(i)\cap\operatorname{ne}_{G}(j)\subseteq\operatorname{pa}_{\mathcal{G}}(j)$.
The proof that $\mathcal{A}^{-}\backslash\mathcal{A}^{+}=\mathcal{S}^{-}$ is
similar.

  3. (c)

    1. (i)

Here we claim that $\\{\mathcal{G},\mathcal{G}_{j\to i}\\}$ is a budding. Let
$S^{\ast}=\operatorname{pa}_{\mathcal{G}}(i)$. We see that all the conditions
of Definition 3.3 except possibly the equality holds. Then
$\mathcal{A}^{-}\backslash\mathcal{A}^{+}=\\{S\cup\\{i,j\\}\colon
S\subseteq\operatorname{pa}_{\mathcal{G}}(j)\setminus\\{i\\},\
S\not\subseteq\operatorname{pa}_{\mathcal{G}}(i)\\}=\emptyset$ and as above

$\displaystyle\mathcal{A}^{+}\backslash\mathcal{A}^{-}$
$\displaystyle=\\{S\cup\\{i,j\\}\colon
S\subseteq\operatorname{pa}_{\mathcal{G}}(i),S\not\subseteq\operatorname{pa}_{\mathcal{G}}(j)\\}$
$\displaystyle=\\{S\cup\\{i,j\\}\colon S\subseteq
S^{\ast},S\not\subseteq\operatorname{ne}_{G}(j)\\}$
$\displaystyle=\mathcal{S}^{+}$

and thus this is a budding.

    2. (ii)

In this case we claim that $\\{\mathcal{G},\mathcal{G}_{j\to i}\\}$ is a
v-structure addition. As above we get that
$\mathcal{A}^{-}\backslash\mathcal{A}^{+}=\emptyset$. Now we want to show that
$\mathcal{A}^{+}\backslash\mathcal{A}^{-}$ contains a single set. Denote the
single parent of $i$ in $\mathcal{G}$ by $p_{i}$. Then we get
$\mathcal{A}^{+}\backslash\mathcal{A}^{-}=\\{S\cup\\{i,j\\}\colon
S\subseteq\\{p_{i}\\},S\not\subseteq\operatorname{pa}_{\mathcal{G}}(j)\\}=\\{\\{i,j,p_{i}\\}\\}$.
Then by choosing $S^{\ast}=\\{i,j,p_{i}\\}$ in Definition 3.1 we get the
desired result.

  4. (d)

This case is symmetric with case (c). Indeed, we get back $\mathcal{G}$ from
$\mathcal{G}_{j\to i}$ by again reversing the edge $j\to i$, and the turn pair
is unordered.

∎

######  Proposition B.1.

Let $\\{\mathcal{G},\mathcal{H}\\}$ be an addition. Then $\mathop{\rm
conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ is an edge of $\mathop{\rm
CIM}\nolimits_{p}$. If $\mathcal{G}$ and $\mathcal{H}$ have the same skeleton
$G$ then $\mathop{\rm conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ is also
an edge of $\mathop{\rm CIM}\nolimits_{G}$.

###### Proof.

To prove the claim it suffices to find a cost vector
$w\in\mathbb{R}^{2^{p}-p-1}$ such that $w^{T}x$ is maximized at exactly
$c_{\mathcal{G}}$ and $c_{\mathcal{H}}$ over the set of characteristic imsets
in $\mathop{\rm CIM}\nolimits_{p}$. To this end, define the cost vector $w$
such that the coordinate $w(S)$ for $S\subseteq[p]$ with $|S|\geq 2$ satisfies

$w(S)=\begin{cases}1&\text{ if $c_{\mathcal{G}}(S)=1$},\\\ 0&\text{ if
$S=S^{\ast}$},\\\ -1&\text{ otherwise},\\\ \end{cases}$

where $c_{\mathcal{H}}=c_{\mathcal{G}}+e_{S^{\ast}}$. It follows that
$w^{T}c_{\mathcal{H}}=w^{T}c_{\mathcal{G}}$. So it only remains to show that
if $\mathcal{D}$ a DAG on node set $[p]$ that is not Markov equivalent to
either $\mathcal{G}$ or $\mathcal{H}$ then
$w^{T}c_{\mathcal{D}}<w^{T}c_{\mathcal{G}}=w^{T}c_{\mathcal{H}}$. Assume that
$\mathcal{D}$ is such a DAG. By Lemma 2.2, it follows that either

  1. (1)

$c_{\mathcal{D}}(S)=1$ and $c_{\mathcal{G}}(S)=0$ for some $S\subseteq[p]$
with $|S|\geq 2$ and $S\neq S^{\ast}$,

  2. (2)

$c_{\mathcal{D}}(S)=0$ and $c_{\mathcal{G}}(S)=1$ for some $S\subseteq[p]$
with $|S|\geq 2$, or

  3. (3)

some combination of cases (1) and (2).

Let $\alpha$ denote the number of $S$ for which case (1) occurs, and let
$\beta$ denote the number of $S$ for which case (2) occurs. Then
$\alpha+\beta\neq 0$. Moreover,

$w^{T}c_{\mathcal{D}}=w^{T}c_{\mathcal{G}}-\alpha-\beta<w^{T}c_{\mathcal{G}}=w^{T}c_{\mathcal{H}},$

which completes the proof that $\mathop{\rm
conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ is an edge of $\mathop{\rm
CIM}\nolimits_{p}$. To see that it is also an edge of $\mathop{\rm
CIM}\nolimits_{G}$ when $\mathcal{G}$ and $\mathcal{H}$ have the same skeleton
$G$, use the exact same argument when maximizing $w^{T}x$ over the set
$\mathop{\rm CIM}\nolimits_{G}$. ∎

######  Lemma B.2.

Let $\mathcal{G}$ and $\mathcal{H}$ be two DAGs on the same skeleton $G$, and
suppose that the pair $\\{\mathcal{G},\mathcal{H}\\}$ is a budding with
respect to $(i,j,S^{\ast})$. If $S\subseteq S^{\ast}$ satisfies
$S\cup\\{i,j\\}\in\mathcal{S}^{+}$ then there exists $k\in S$ such that
$c_{\mathcal{G}}(\\{k,j\\})=0$.

###### Proof.

If $c_{\mathcal{G}}(\\{k,j\\})=1$ for all $k\in S$ it follows that
$S\subseteq\operatorname{ne}_{G}(j)$. This contradicts that
$S\cup\\{i,j\\}\in\mathcal{S}^{+}$. ∎

######  Proposition B.3.

Let $\mathcal{G}$ and $\mathcal{H}$ be two DAGs with the same skeleton $G$. If
$\\{\mathcal{G},\mathcal{H}\\}$ is a budding then $\mathop{\rm
conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ is an edge of $\mathop{\rm
CIM}\nolimits_{G}$.

###### Proof.

To prove the claim, it suffices to find a cost vector
$w\in\mathbb{R}^{2^{p}-p-1}$ such that $w^{T}x$ is maximized at exactly
$c_{\mathcal{G}}$ and $c_{\mathcal{H}}$ over the vertices of $\mathop{\rm
CIM}\nolimits_{G}$. To this end, we let $m:=|\mathcal{S}^{+}|$ and define the
cost vector $w$ such that for $S\subseteq[p]$, with $|S|\geq 2$, $w$ satisfies

$w(S)=\begin{cases}2&\text{ if $c_{\mathcal{G}}(S)=1$}\\\ 1&\text{ if
$S=S^{\ast}\cup\\{i,j\\}$},\\\ \frac{-1}{m-1}&\text{ if
$S\in\mathcal{S}^{+}\setminus\\{S^{\ast}\cup\\{i,j\\}\\}$},\\\
-2&\text{otherwise}.\\\ \end{cases}$

Notice that since $|S^{\ast}|\geq 2$ we have $m\geq 2$ so this indeed well
definied. Then we have $w^{T}c_{\mathcal{G}}=w^{T}c_{\mathcal{H}}$ since

$\begin{split}w^{T}c_{\mathcal{H}}&=w^{T}\left(c_{\mathcal{G}}+\sum_{S\in\mathcal{S}^{+}}e_{S}\right),\\\
&=w^{T}c_{\mathcal{G}}+w(S^{\ast}\cup\\{i,j\\})(1)+\sum_{S\in\mathcal{S}^{+}\setminus\\{S^{\ast}\cup\\{i,j\\}\\}}w(S)(1),\\\
&=w^{T}c_{\mathcal{G}}+1+\left(\frac{-1}{m-1}\right)(m-1),\\\
&=w^{T}c_{\mathcal{G}}.\\\ \end{split}$

It then remains to check that $w^{T}c_{\mathcal{D}}<w^{T}c_{\mathcal{G}}$ for
any DAG $\mathcal{D}$ with skeleton $G$ and $\mathcal{D}$ is not Markov
equivalent to $\mathcal{G}$ or $\mathcal{H}$.

Let us denote $\mathcal{S}^{+}\coloneqq\\{S\colon w(S)=2\\}$ and
$\mathcal{S}^{-}\coloneqq\\{S\colon w(S)=-2\\}$. Notice that for all
$0/1$-vectors $v$ we have

$\displaystyle w^{T}v$ $\displaystyle=w^{T}\sum_{S\in\mathcal{S}^{+}\colon
v(S)=1}e_{S}+w^{T}\sum_{S\in\mathcal{S}^{+}\colon
v(S)=1}e_{S}+w^{T}\sum_{S\in\mathcal{S}^{+}\colon v(S)=1}e_{S}$
$\displaystyle=2\left|\left\\{S\in\mathcal{S}^{+}\colon
v(S)=1\right\\}\right|-2\left|\left\\{S\in\mathcal{S}^{-}\colon
v(S)=1\right\\}\right|+w^{T}\sum_{S\in\mathcal{S}^{+}\colon v(S)=1}e_{S}.$

Noting that $c_{\mathcal{G}}(S)=c_{\mathcal{H}}(S)=1$ for all
$S\in\mathcal{S}^{+}$, $c_{\mathcal{G}}(S)=c_{\mathcal{H}}(S)=0$ for all
$S\in\mathcal{S}^{-}$ and that

$-1\leq w^{T}\sum_{S\in\mathcal{S}^{+}\colon v(S)=1}e_{S}\leq 1$

we immidiately get that $w^{T}v<w^{T}c_{\mathcal{G}}$ whenever
$\left\\{S\in\mathcal{S}^{+}\colon v(S)=1\right\\}\neq\mathcal{S}^{+}$ or
$\left\\{S\in\mathcal{S}^{-}\colon v(S)=1\right\\}\neq\mathcal{S}^{-}$. Thus
we can assume that $c_{\mathcal{D}}(S)=c_{\mathcal{G}}(S)$ whenever
$S\notin\mathcal{S}^{+}$.

Since $\mathcal{D}$ was assumed to not be Markov equivalent to $\mathcal{G}$
we have the following cases:

  1. (1)

$c_{\mathcal{D}}(S^{\ast}\cup\\{i,j\\})=0$ and for some set
$S\in\mathcal{S}^{+}\backslash\\{S^{\ast}\cup\\{i,j\\}\\}$ we have
$c_{\mathcal{D}}(S)=1$, or

  2. (2)

$c_{\mathcal{D}}(S^{\ast}\cup\\{i,j\\})=1$.

In case (1) it follows immidately that $w^{T}c_{\mathcal{D}}\leq
w^{T}c_{\mathcal{G}}+\frac{-1}{m-1}<w^{T}c_{\mathcal{G}}$.

As for case (2), by definition of the characteristic imset we have a node $n$
such that $x\to n$ for all $x\in S^{\ast}\cup\\{i,j\\}\backslash\\{n\\}$. By
Lemma B.2 we get that $n\neq j$. If $n=i$ we get that $c_{\mathcal{D}}(S)=1$
for all $S\in\mathcal{S}^{+}$, and thus $\mathcal{D}$ is Markov equivalent to
$\mathcal{H}$. Thus the only case left is that $n\in S^{\ast}$.

By assumtion $S^{\ast}\cup\\{i,j\\}\in\mathcal{S}^{+}$. Then using Lemma B.2
and the fact that $j\to n$ in $\mathcal{D}$ there must exists a node
$k\notin\\{i,j,n\\}$ such that $k$ is not a neighbour of $j$ in $G$. As
$\\{j,k\\}\subseteq
S^{\ast}\cup\\{i,j\\}\subseteq\operatorname{pa}_{\mathcal{D}}(n)\cup\\{n\\}$
we get $c_{\mathcal{D}}(\\{j,n,k\\})=1$. By definition
$\\{j,n,k\\}\notin\mathcal{S}^{+}$. Thus we must have that
$1=c_{\mathcal{D}}(\\{j,n,k\\})=c_{\mathcal{G}}(\\{j,n,k\\})=c_{\mathcal{H}}(\\{j,n,k\\})$.
That is $\\{j,n,k\\}$ is a v-structure in $\mathcal{D}$, $\mathcal{G}$ and
$\mathcal{H}$. We have that $c_{\mathcal{G}}(\\{i,j,k\\})=0$ since
$\\{i,j,k\\}\in\mathcal{S}^{+}$, thus since $\mathcal{G}$ is acyclic it
follows that $i\to n$ in $\mathcal{G}$. In the terminology used in [1], $i\to
n$ will be strongly protected in $\mathcal{G}$. Thus $n$ is a child of $i$,
$j$ and $k$ in $\mathcal{G}$, thus $c_{\mathcal{G}}(\\{i,j,n,k\\})=1$. But
$\\{i,j,n,k\\}\in\mathcal{S}^{+}$, a contradiction. ∎

######  Lemma B.4.

Let $\mathcal{G}$ and $\mathcal{H}$ be two DAGs on the same skeleton $G$, and
suppose that the pair $\\{\mathcal{G},\mathcal{H}\\}$ is a flip with respect
to $(i,j,S_{i},S_{j})$. Then there exists nodes $k_{i}\in S_{i}\setminus
S_{j}$ and $k_{j}\in S_{j}\setminus S_{i}$ such that
$c_{\mathcal{G}}(\\{k_{i},j\\})=c_{\mathcal{G}}(\\{k_{j},i\\}))=0$.

###### Proof.

If $c_{\mathcal{G}}(\\{k,j\\})=1$ for all $k\in S_{i}$ it follows that
$S_{i}\subseteq\operatorname{ne}_{G}(j)$. A contradiciton. Thus we have a node
$k_{i}\in S_{i}\setminus\operatorname{ne}_{G}(j)$. As
$S_{j}\subseteq\operatorname{ne}_{G}(j)$ if follows that $k_{i}\in
S_{i}\setminus S_{j}$. The other case is similar. ∎

######  Proposition B.5.

Let $\mathcal{G}$ and $\mathcal{H}$ be two DAGs with skeleton $G$. If
$\\{\mathcal{G},\mathcal{H}\\}$ is a flip then $\mathop{\rm
conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ is an edge of $\mathop{\rm
CIM}\nolimits_{G}$.

###### Proof.

To prove the claim, it suffices to find a cost vector
$w\in\mathbb{R}^{2^{p}-p-1}$ such that $w^{T}x$ is maximized at exactly
$c_{\mathcal{G}}$ and $c_{\mathcal{H}}$ over the vertices of $\mathop{\rm
CIM}\nolimits_{G}$.

Notice that by definition $\mathcal{S}^{+}\cap\mathcal{S}^{-}=\emptyset$. Let
$m^{+}\coloneqq|\mathcal{S}^{+}|$ and $m^{-}\coloneqq|\mathcal{S}^{-}|$. If
$m^{+},m^{-}\geq 2$ define

$w(S)=\begin{cases}5&\text{ if $c_{\mathcal{G}}(S)=c_{\mathcal{H}}(S)=1$},\\\
2&\text{ if $S=S_{i}\cup\\{i,j\\}$ or $S=S_{j}\cup\\{i,j\\}$}\\\
\frac{-1}{m^{+}-1}&\text{ if
$S\in\mathcal{S}^{+}\setminus\\{S_{i}\cup\\{i,j\\}\\}$},\\\
\frac{-1}{m^{-}-1}&\text{ if
$S\in\mathcal{S}^{-}\setminus\\{S_{j}\cup\\{i,j\\}\\}$},\\\ -5&\text{ if
$c_{\mathcal{G}}(S)=c_{\mathcal{H}}(S)=0$},\\\ \end{cases}$

If $|\mathcal{S}^{+}|=1$ we have that
$\mathcal{S}^{+}=\\{S_{i}\cup\\{i,j\\}\\}$, and thus we let
$w(S_{i}\cup\\{i,j\\})=1$. Likewise, if $|\mathcal{S}^{-}|=1$ we have that
$\mathcal{S}^{-}=\\{S_{j}\cup\\{i,j\\}\\}$, and we let
$w(S_{j}\cup\\{i,j\\})=1$. Otherwise let $w$ be as above. Thus by definition
we have

$\sum_{S\in\mathcal{S}^{+}}w(S)=\sum_{S\in\mathcal{S}^{-}}w(S)=1$

First we have that

$\displaystyle w^{T}c_{\mathcal{H}}-w^{T}c_{\mathcal{G}}=$ $\displaystyle
w^{T}\left(c_{\mathcal{G}}+\sum_{S\in\mathcal{S}^{+}}e_{S}-\sum_{S\in\mathcal{S}^{-}}e_{S}\right)-w^{T}c_{\mathcal{G}}$
$\displaystyle=$ $\displaystyle
w^{T}\left(\sum_{S\in\mathcal{S}^{+}\setminus\mathcal{S}^{-}}e_{S}-\sum_{S\in
S\in\mathcal{S}^{-}\setminus\mathcal{S}^{+}}e_{S}\right)$ $\displaystyle=$
$\displaystyle\sum_{S\in\mathcal{S}^{+}\setminus\mathcal{S}^{-}}w(S)-\sum_{S\in
S\in\mathcal{S}^{-}\setminus\mathcal{S}^{+}}w(S)$ $\displaystyle=$
$\displaystyle 1-1=0$

So left to show is that for any DAG $\mathcal{D}$ with skeleton $G$ we have
$w^{T}c_{\mathcal{D}}<w^{T}c_{\mathcal{G}}$ if $c_{\mathcal{D}}$ is neither
$c_{\mathcal{G}}$ or $c_{\mathcal{H}}$.

Let $\mathcal{A}^{+}\coloneqq\\{S\colon
c_{\mathcal{G}}(S)=c_{\mathcal{H}}(S)=1\\}$ and
$\mathcal{A}^{-}\coloneqq\\{S\colon
c_{\mathcal{G}}(S)=c_{\mathcal{H}}(S)=0\\}$. Similar to the case of buddings,
we begin by concluding that for any $0/1$ vector $v$ we have

$\displaystyle w^{T}v=\ $ $\displaystyle w^{T}\sum_{S\in\mathcal{A}^{+}\colon
v(S)=1}e_{S}+w^{T}\sum_{S\in\mathcal{A}^{-}\colon v(S)=1}e_{S}$
$\displaystyle+w^{T}\sum_{S\in\mathcal{S}^{+}\colon
v(S)=1}e_{S}+w^{T}\sum_{S\in\mathcal{S}^{-}\colon v(S)=1}e_{S}$
$\displaystyle=$ $\displaystyle\ 5\left|\left\\{S\in\mathcal{A}^{+}\colon
v(S)=1\right\\}\right|-5\left|\left\\{S\in\mathcal{A}^{-}\colon
v(S)=1\right\\}\right|$ $\displaystyle+w^{T}\sum_{S\in\mathcal{S}^{+}\colon
v(S)=1}e_{S}+w^{T}\sum_{S\in\mathcal{S}^{-}\colon v(S)=1}e_{S}.$

We also have that

$-1\leq w^{T}\sum_{S\in\mathcal{S}^{+}\colon v(S)=1}e_{S}\leq 2$

and

$-1\leq w^{T}\sum_{S\in\mathcal{S}^{-}\colon v(S)=1}e_{S}\leq 2.$

We immediately get that $w^{T}v<w^{T}c_{\mathcal{G}}$ whenever
$\left\\{S\in\mathcal{A}^{+}\colon v(S)=1\right\\}\neq\mathcal{A}^{+}$ or
$\left\\{S\in\mathcal{A}^{-}\colon v(S)=1\right\\}\neq\mathcal{A}^{-}$. Thus
we can assume that $c_{\mathcal{D}}(S)=c_{\mathcal{G}}(S)$ whenever
$c_{\mathcal{G}}(S)=c_{\mathcal{H}}(S)$.

If $c_{\mathcal{D}}(S_{i}\cup\\{i,j\\})=c_{\mathcal{D}}(S_{j}\cup\\{i,j\\})=0$
then it follows that $w^{T}c_{\mathcal{D}}\leq
5|\mathcal{A}^{+}|<5|\mathcal{A}^{+}|+1=c_{\mathcal{G}}$. Thus for
$w^{T}c_{\mathcal{D}}\geq w^{T}c_{\mathcal{G}}$ to be true we must have
$c_{\mathcal{D}}(S_{i}\cup\\{i,j\\})=1$ or
$c_{\mathcal{D}}(S_{j}\cup\\{i,j\\})=1$. By symmetry we can assume
$c_{\mathcal{D}}(S_{i}\cup\\{i,j\\})=1$.

Thus there exists $n_{i}\in S_{i}$ such that
$S_{i}\cup\\{i,j\\}\subseteq\operatorname{pa}_{\mathcal{D}}(n_{i})\cup\\{n_{i}\\}$.
By Lemma B.4 we have that $n_{i}\notin\\{k_{i},j\\}$. Then we have two cases
$n_{i}\neq i$ and $n_{i}=i$.

If $n_{i}\neq i$ we have that $c_{\mathcal{D}}(\\{n_{i},k_{i},j\\})=1$. As
$\\{n_{i},k_{i},j\\}\notin\mathcal{A}^{+}\cup\mathcal{S}^{-}$ we get
$c_{\mathcal{D}}(\\{n_{i},k_{i},j\\})=c_{\mathcal{G}}(\\{n_{i},k_{i},j\\})=c_{\mathcal{H}}(\\{n_{i},k_{i},j\\})=1$.
Then by acyclicity we get $c_{\mathcal{G}}(\\{n_{i},k_{i},j,i\\})=1$. But as
$\\{n_{i},k_{i},j,i\\}\in\mathcal{S}^{+}\backslash\mathcal{S}^{-}$ we get
$c_{\mathcal{G}}(\\{n_{i},k_{i},j,i\\})=0$, a contradiction.

Thus $n_{i}=i$. Then, by definition, it follows that $c_{\mathcal{D}}(S)=1$
for all $S\in\mathcal{S}^{+}$. If $c_{\mathcal{D}}(S_{j}\cup\\{i,j\\})=1$ we
can in the same way argue that the corresponding $n_{j}=j$ and thus that
$c_{\mathcal{D}}(S)=1$ for all $S\in\mathcal{S}^{-}$. More specifically we get
that we have the following two graphs induced by $\mathcal{D}$, $k_{j}\to
j\leftarrow i$ and $k_{i}\to i\leftarrow j$. A contradiction, thus if
$c_{\mathcal{D}}(S_{i}\cup\\{i,j\\})=1$ we have
$c_{\mathcal{D}}(S_{j}\cup\\{i,j\\})=0$.

In conclusion, if $w^{T}c_{\mathcal{D}}\geq w^{T}c_{\mathcal{G}}$ we could
conclude that $c_{\mathcal{D}}(S)=c_{\mathcal{G}}(S)$ for all $S$ such that
$c_{\mathcal{G}}(S)=c_{\mathcal{H}}(S)$. By symmetry we assumed that
$c_{\mathcal{D}}(S_{i}\cup\\{i,j\\})=1$ and thus concluded that
$c_{\mathcal{D}}(S)=1$ for all $S\in\mathcal{S}^{+}$ and
$c_{\mathcal{D}}(S_{j}\cup\\{i,j\\})=1$. Then it follows that
$c^{T}c_{\mathcal{D}}\leq c^{T}c_{\mathcal{G}}$ with equality if and only if
$c_{\mathcal{D}}=c_{\mathcal{H}}$. The result follows. ∎

### Proof of Proposition 3.13

Since $\mathcal{H}$ is a DAG it induces a partial order of $[p]$ as $i\geq j$
if there exists a directed path $i$ to $j$. We can extend this to a total
order, say $v_{1}\leq v_{2}\leq\dots\leq v_{p}$. We will show that we can, in
turn, change the direction of edges in $\mathcal{G}$ so that they respect this
total order and we in each intermediate step have a DAG. As $\mathcal{G}$ and
$\mathcal{H}$ have the same skeleton we are done.

So inductively assume we have directed all edges between
$\\{v_{m}\\}_{m=1}^{k-1}$ as described and we currently have the DAG
$\mathcal{D}$. To simplify notations, let $V_{k}=\\{v_{m}\\}_{m=1}^{k-1}$. We
now wish to reverse an edge $v_{k}\to i\in\mathcal{D}$ with
$i\in\operatorname{ch}_{\mathcal{D}}(v_{k})\backslash V_{k}$ to create a DAG
$\mathcal{D}_{i\to v_{k}}$. Then by Proposition 3.10 the pair
$\\{\mathcal{D},\mathcal{D}_{i\to v_{k}}\\}$ will be a turn pair or Markov
equivalent.

So if $\operatorname{ch}(v_{k})\backslash V_{k}=\emptyset$ we are done and can
proceed to $v_{k+1}$. If not we claim there exists a vertex
$i\in\operatorname{ch}(v_{k})\backslash V_{k}$ such that $\mathcal{D}_{i\to
v_{k}}$ is a DAG. As $\mathcal{D}$ is a DAG we get a partial order on the
elements of $\operatorname{ch}(v_{k})\backslash V_{k}$ as before. Let $i$ be a
maximal element in this order. If there exists a directed cycle in
$\mathcal{D}_{i\to v_{k}}$ but not in $\mathcal{D}$ then it would have to use
the edge $i\to v_{k}$. So assume such a path exists as $i\to v_{k}\to a_{1}\to
a_{2}\to\dots\to a_{l}\to i$. By definition of our partial order we then get
$a_{1}\geq i$, a contradicition as $i$ was a maximal element. Thus
$\mathcal{D}_{i\to v_{k}}$ is a DAG.

Thus using only turn pairs we can always reverse another edge from $v_{k}$ to
$\operatorname{ch}(v_{k})\backslash V_{k}$. This completes our induction step.

As there is only a finite set of edges and we never reverse an edge twice we
are done. ∎

### Proof of Proposition 3.15

For any $k\neq i$ we have that $k\in
S\subseteq\operatorname{pa}_{\mathcal{G}}(k)\cup\\{k\\}$ if and only if $k\in
S\subseteq\operatorname{pa}_{\mathcal{G}_{+j\to i}}(k)\cup\\{k\\}$, this
because
$\operatorname{pa}_{\mathcal{G}}(k)=\operatorname{pa}_{\mathcal{G}_{+j\to
i}}(k)$ for all such $k$. As the value of $c_{\mathcal{G}}(S)$ and
$c_{\mathcal{G}_{+j\to i}}(S)$ is determined by this property the only case
where we can have $c_{\mathcal{G}}(S)\neq c_{\mathcal{G}_{+j\to i}}(S)$ is for
sets such that $i\in
S\not\subseteq\operatorname{pa}_{\mathcal{G}}(i)\cup\\{i\\}$ or $i\in
S\subseteq\operatorname{pa}_{\mathcal{G}_{+j\to i}}(i)\cup\\{i\\}$.

Moreover, for any $S$ such that $\\{i,j\\}\centernot\subseteq S$ we have that
the induced subgraphs of $\mathcal{G}$ and $\mathcal{G}_{+j\to i}$ are
identical. Thus $c_{\mathcal{G}}(S)=c_{\mathcal{G}_{+j\to i}}(S)$ for all such
$S$. This together with the fact that
$\operatorname{pa}_{\mathcal{G}}(i)\cup\\{j\\}=\operatorname{pa}_{\mathcal{G}_{+j\to
i}}(i)$ tells us that the only sets of interest are $\\{i,j\\}\subseteq
S\subseteq\operatorname{pa}_{\mathcal{G}}(i)\cup\\{i,j\\}$.

Then we divide this in two cases:

  1. (1)

If $\operatorname{pa}_{\mathcal{G}}(i)=\emptyset$ the criterion
$\\{i,j\\}\subseteq S\subseteq\operatorname{pa}_{\mathcal{G}}(i)\cup\\{i,j\\}$
reduces to $S=\\{i,j\\}$. Then as the edge $(j,i)$ is not present in
$\mathcal{G}$ but is so in $\mathcal{G}_{+j\to i}$ we get
$c_{\mathcal{G}}=c_{\mathcal{G}_{+j\to i}}+e_{\\{i,j\\}}$. Thus we have an
edge addition, which, as we have noted before, is a edge pair.

  2. (2)

If $\operatorname{pa}_{\mathcal{G}}(i)\neq\emptyset$ we claim that
$c_{\mathcal{G}_{+j\to i}}(S)=1$ and $c_{\mathcal{G}}(S)=0$ for all $S$ such
that $\\{i,j\\}\subseteq
S\subseteq\operatorname{pa}_{\mathcal{G}}(i)\cup\\{i,j\\}$, making this a edge
pair with respect to $(i,j,\operatorname{pa}_{\mathcal{G}}(i))$. That
$c_{\mathcal{G}_{+j\to i}}(S)=1$ for all such $S$ follows as $i\in
S\subseteq\operatorname{pa}_{\mathcal{G}}(i)\cup\\{i,j\\}=\operatorname{pa}_{\mathcal{G}_{+j\to
i}}(i)\cup\\{i\\}$. Assume that $c_{\mathcal{G}}(S)=1$ for one $S$ such that
$\\{i,j\\}\subseteq
S\subseteq\operatorname{pa}_{\mathcal{G}}(i)\cup\\{i,j\\}$. Then we have a $k$
such that $k\in S\subseteq\operatorname{pa}_{\mathcal{G}}(k)\cup\\{k\\}$. As
$j\centernot\in\operatorname{pa}_{\mathcal{G}}(i)$ and
$i\centernot\in\operatorname{pa}_{\mathcal{G}}(j)$ we get
$k\centernot\in\\{i,j\\}$. But as
$S\subseteq\operatorname{pa}_{\mathcal{G}}(i)\cup\\{i,j\\}$ we get
$k\in\operatorname{pa}_{\mathcal{G}}(i)$, and $i\in
S\subseteq\operatorname{pa}_{\mathcal{G}}(k)\cup\\{k\\}$ gives us a
contradiction as $\mathcal{G}$ was assumed to be a DAG. Condition (1) in
Definition 3.14 follows since $i$ was not a neighbor of $j$ in $\mathcal{G}$,
and condition (2) follows since we choose $S^{\ast}$ to be
$\operatorname{pa}_{\mathcal{G}}(i)$.

∎

### Proof of Theorem 3.16

If $\\{\mathcal{G},\mathcal{H}\\}$ is an edge addition then this was proven in
Proposition B.1, thus assume that $|S^{\ast}|>0$. We partition the elements in
$S^{\ast}$ based on if they are adjacent to $j$ in $\mathcal{G}$ or not. So
let $X=\\{x\in S^{\ast}\colon c_{\mathcal{G}}(\\{x,j\\})=0\\}$ and $Y=\\{y\in
S^{\ast}\colon c_{\mathcal{G}}(\\{y,j\\})=1\\}$. Define $s\coloneqq|X|$ and
$t\coloneqq|Y|$. We treat the cases when $X\neq\emptyset$ and $X=\emptyset$
separately.
Case I, $X\neq\emptyset$: Let $M\coloneqq 2^{s+t}-(s+t+1)$ and notice that
$\left|\\{S\in\mathcal{S}_{+(j,i)},|S|\geq 4\\}\right|=M$. We define the
following objective function $w$ in order to prove that $\mathop{\rm
conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ is an edge of $\mathop{\rm
CIM}\nolimits_{p}$.

$w(S)=\begin{cases}t+2&\text{ if $c_{\mathcal{G}}(S)=1$}\\\ -1&\text{ if
$S=\\{i,j\\}$},\\\ -1&\text{ if $S=\\{i,j,y\\}$, some $y\in Y$},\\\
\frac{1}{s}(t+\frac{1}{2})&\text{ if $S=\\{i,j,x\\}$, some $x\in X$},\\\
\frac{1}{2M}&\text{ if $S\in\mathcal{S}_{+(j,i)},|S|\geq 4$},\\\
-(t+2)&\text{otherwise}.\\\ \end{cases}$

The negative weights for $S\in\mathcal{S}_{+(j,i)}$ sum to $-(t+1)$ and the
positive to $t+1$. Since the imsets differ exactly on $\mathcal{S}_{+(i,j)}$,
for which $w$ sum to 0, we get $w^{T}c_{\mathcal{H}}=w^{T}c_{\mathcal{G}}$.
Assume we have a DAG $\mathcal{D}$ such that $w^{T}c_{\mathcal{D}}\geq
w^{T}c_{\mathcal{G}}$. Then it must have $c_{\mathcal{D}}(S)=1$ if
$c_{\mathcal{G}}(S)=1$ and $c_{\mathcal{D}}(S)=0$ if $c_{\mathcal{H}}(S)=0$.
If $c_{\mathcal{D}}(S)=0$ for all $S\in\mathcal{S}_{+(j,i)}$ then
$c_{\mathcal{D}}=c_{\mathcal{G}}$, so we can assume that is not the case. Such
a DAG $\mathcal{D}$ must thus pick up some of the positive weights in
$\mathcal{S}_{+(j,i)}$. There are two possibilities to consider. First, if
$c_{\mathcal{D}}(\\{i,j,x\\})=1$ for some $x\in X$, then, by definition of
$c_{\mathcal{D}}$, $\mathcal{D}$ must have v-structure $x\to i\leftarrow j$,
since we know there is no edge between $x$ and $j$. Therefore we must have
$c_{\mathcal{D}}(\\{i,j\\})=1$, and it follows that
$c_{\mathcal{D}}(\\{i,j,y\\})=1$, for all $y\in Y$, since $y$ is adjacent to
both $i$ and $j$. Thus $w^{T}c_{\mathcal{D}}$ picks up all the negative
weights in $\mathcal{S}_{+(j,i)}$. To then get $w^{T}c_{\mathcal{D}}\geq
w^{T}c_{\mathcal{G}}$ we must thus have
$c_{\mathcal{D}}(S)=c_{\mathcal{H}}(S)$ for all $S$, and they are thus
$\mathcal{D}$ is Markov equivalent to $\mathcal{H}$.

Second, if $c_{\mathcal{D}}(\\{i,j,x\\})=0$ for all $x\in X$, but
$c_{\mathcal{D}}(S)=1$, for some $S\in\mathcal{S}_{+(j,i)},|S|\geq 4$, then by
definition there exist $k\in S$ with
$S\subseteq\operatorname{pa}_{\mathcal{D}}(k)\cup\\{k\\}$. If $k\in\\{i,j\\}$
we immediately get $c_{\mathcal{D}}(\\{i,j\\})=1$. Otherwise we have
$c_{\mathcal{D}}(\\{i,j,k\\})=1$, and since there is no edge between $j$ and
elements in $X$ we know that $k\in Y$. In either case $w^{T}c_{\mathcal{D}}$
picks up a $-1$. The sum of the positive weights $w(S)$ for
$S\in\mathcal{S}_{+(j,i)},|S|\geq 4$ is only $\nicefrac{{1}}{{2}}$ and we can
not have $w^{T}c_{\mathcal{D}}\geq w^{T}c_{\mathcal{G}}$.

Case II, $X=\emptyset$: Now, we use the following objective function $w$ in
order to prove that $\mathop{\rm
conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ is an edge of $\mathop{\rm
CIM}\nolimits_{p}$. Here $s=0$, so $M=2^{t}-t-1$.

$w(S)=\begin{cases}t+1&\text{ if $c_{\mathcal{G}}(S)=1$}\\\
t-\frac{1}{2}&\text{ if $S=\\{i,j\\}$},\\\ -1&\text{ if $S=\\{i,j,y\\}$, some
$y\in Y$},\\\ \frac{1}{2M}&\text{ if $S\in\mathcal{S}_{+(j,i)},|S|\geq 4$},\\\
-(t+1)&\text{otherwise}.\\\ \end{cases}$

The reasoning is very similar to Case I. The negative weights for
$S\in\mathcal{S}_{+(j,i)}$ sum to $-t$ and the positive to $t$. Thus,
$w^{T}c_{\mathcal{H}}=w^{T}c_{\mathcal{G}}$, and again if another DAG
$\mathcal{D}$ were to have $w^{T}c_{\mathcal{D}}\geq w^{T}c_{\mathcal{G}}$,
then it must have $c_{\mathcal{D}}(S)=1$ if $c_{\mathcal{G}}(S)=1$ and
$c_{\mathcal{D}}(S)=0$ if $c_{\mathcal{H}}(S)=0$. There are two possibilities
to consider. First, if $c_{\mathcal{D}}(\\{i,j\\})=1$, then $\mathcal{D}$ have
complete triangles on every $\\{i,j,y\\}$ and therefore
$c_{\mathcal{D}}(\\{i,j,y\\})=1$, for all $y\in Y$. Thus by Lemma 2.4 we get
$c_{\mathcal{D}}=c_{\mathcal{H}}$. The second possibility is that
$c_{\mathcal{D}}(\\{i,j\\})=0$ but $c_{\mathcal{D}}(S)=1$, for some
$S\in\mathcal{S}_{+(j,i)},|S|\geq 4$, then by definition there exist $k\in S$
with $S\subseteq\operatorname{pa}_{\mathcal{D}}(k)\cup\\{k\\}$. As $i$ and $j$
are not adjacent we get $k\centernot\in\\{i,j\\}$. This implies that
$c_{\mathcal{D}}(\\{i,j,k\\})=1$, for $k\in Y$, which gives a $-1$ in
$w^{T}c_{\mathcal{D}}$. The sum of the positive weights $w(S)$ for
$S\in\mathcal{S}_{+(j,i)},|S|\geq 4$ is $\nicefrac{{1}}{{2}}$ and thus we
cannot have $w^{T}c_{\mathcal{D}}\geq w^{T}c_{\mathcal{G}}$. ∎

##  Appendix C Proofs to Theorems in Section 4

######  Lemma C.1.

Let $\mathcal{G}$ and $\mathcal{H}$ be two DAGs on the same skeleton $G$.
Assume that $G$ is a tree and that $\\{\mathcal{G},\mathcal{H}\\}$ is an
addition with

$c_{\mathcal{H}}=c_{\mathcal{G}}+e_{S^{\ast}}.$

Then there exists a DAG $\mathcal{D}$ and nodes $i$ and $j$ such that
$\mathcal{D}$ is Markov equivalent to $\mathcal{H}$ and $\mathcal{D}_{i\to j}$
is Markov equivalent to $\mathcal{G}$.

###### Proof.

Since $\mathcal{G}$ and $\mathcal{H}$ has the same skeleton it follows by
Proposition 3.2 that they differ by a single v-structure. That is the induced
graph of $\mathcal{H}$ on $S^{\ast}$ is a v-structure, $k\to i\leftarrow j$.
As $c_{\mathcal{G}}(S^{\ast})=0$ we have that $k\leftarrow i\in\mathcal{G}$ or
$i\to j\in\mathcal{G}$. We can by symmetry assume that $i\to j\in\mathcal{G}$.
Assume we have a node
$s\in\operatorname{pa}_{\mathcal{G}}(j)\setminus\\{i\\}$, as $G$ was a tree it
follows that $s\neq k$. Then $c_{\mathcal{G}}(\\{s,j,i\\})=1$ and as
$\\{s,j,i\\}\neq S^{\ast}$ we get $c_{\mathcal{H}}(\\{s,j,i\\})=1$. Again
since $G$ was a tree we get that $i\to j\leftarrow s\in\mathcal{H}$, a
contradiction. Thus $\operatorname{pa}_{\mathcal{G}}(j)=\\{i\\}$.

Assume we have a node
$s\in\operatorname{pa}_{\mathcal{H}}(i)\setminus\\{k,j\\}$. Then we have $s\to
i\leftarrow j\in\mathcal{H}$ and thus $c_{\mathcal{H}}(\\{s,i,j\\})=1$. But as
$\\{s,i,j\\}\neq S^{\ast}$ we get $s\to i\leftarrow j\in\mathcal{G}$, a
contradiction. Thus $\operatorname{pa}_{\mathcal{H}}(i)=\\{k,j\\}$.

Now let us construct $\mathcal{D}$. Let $G^{\prime}$ denote the graph
identical to $G$ except it does not have the edge $i-j$. Let $G_{i}$ be the
connected part of $G^{\prime}$ containing $i$ and let $G_{j}$ be the rest of
$G^{\prime}$. Define $\mathcal{D}$ as the orientation of $G$ where we direct
$G_{i}$ according to $\mathcal{H}$, direct $G_{j}$ according to $\mathcal{G}$
and direct $i-j$ as $i\leftarrow j$.

First we want to show that $\mathcal{D}$ is Markov equivalent to
$\mathcal{H}$. As $\mathcal{G}$ and $\mathcal{H}$ only differ by a single
v-structure and $\mathcal{D}$ is everywhere directed like either $\mathcal{G}$
or $\mathcal{H}$ the only area where $\mathcal{D}$ can differ by a v-structure
from $\mathcal{H}$ is around $i$. But since
$\operatorname{pa}_{\mathcal{H}}(i)=\operatorname{pa}_{\mathcal{D}}(i)=\\{k,j\\}$
they must be Markov equivalent. Then $\mathcal{D}_{i\to j}$ does not have the
v-structure $k\to i\leftarrow j$ but no new are created as
$\operatorname{pa}_{\mathcal{D}}(j)=\operatorname{pa}_{\mathcal{G}}(j)\setminus\\{i\\}=\emptyset$.
Thus $\mathcal{D}_{i\to j}$ is Markov equivalent to $\mathcal{G}$. ∎

######  Lemma C.2.

Assume $\\{\mathcal{G},\mathcal{H}\\}$ is a budding with

$c_{\mathcal{H}}=c_{\mathcal{G}}+\sum_{S\in\mathcal{S}^{+}}e_{S}$

with respect to $(i,j,S^{\ast})$ and let $G$ be the skeleton of $\mathcal{G}$
and $\mathcal{H}$. Assume moreover that $G$ is a tree.

Then $\operatorname{pa}_{\mathcal{G}}(i)=S^{\ast}$,
$\operatorname{pa}_{\mathcal{G}}(j)=\\{i\\}$ and $\mathcal{G}_{i\leftarrow j}$
is Markow equivalent to $\mathcal{H}$.

###### Proof.

For any $k\in S^{\ast}$ we have that $c_{\mathcal{G}}(\\{k,i\\})=1$ and as $G$
was a tree the skeleton of $\mathcal{G}\mid_{S^{\ast}}$ must be a star. Then
as $c_{\mathcal{G}}(S^{\ast}\cup\\{i\\})=1$ and $|S^{\ast}|\geq 2$ we must
have $k\to i\in\mathcal{G}$ for all $k\in S^{\ast}$. That is
$S^{\ast}\subseteq\operatorname{pa}_{\mathcal{G}}(i)$. Take any $k\in
S^{\ast}$. As $G$ is a tree we have $\\{i,j,k\\}\in\mathcal{S}^{+}$ and thus
$c_{\mathcal{G}}(\\{i,j,k\\})=0$. Since
$S^{\ast}\subseteq\operatorname{pa}_{\mathcal{G}}(i)$ we get that we must have
$i\to j\in\mathcal{G}$, otherwise $c_{\mathcal{G}}(\\{i,j,k\\})=1$. Then we
have $i\leftarrow j\in\mathcal{H}$ since otherwise we have
$c_{\mathcal{H}}(\\{i,j,k\\})=0$ for all $k\in S^{\ast}$ which cannot be since
$\\{i,j,k\\}\in\mathcal{S}^{+}$.

If there exists a node
$k^{\prime}\in\operatorname{pa}_{\mathcal{G}}(i)\setminus S^{\ast}$ we have
$c_{\mathcal{G}}(\\{i,j,k^{\prime}\\})=0$ and
$c_{\mathcal{H}}(\\{i,j,k^{\prime}\\})=1$ but
$\\{i,j,k^{\prime}\\}\notin\mathcal{S}^{+}$. Thus
$\operatorname{pa}_{\mathcal{G}}(i)=S^{\ast}$. Assume there exists a node
$k^{\prime\prime}\in\operatorname{pa}_{\mathcal{G}}(j)\setminus\\{i\\}$. Then
we have $c_{\mathcal{G}}(\\{i,j,k^{\prime\prime}\\})=1$ but
$c_{\mathcal{H}}(\\{i,j,k^{\prime\prime}\\})=0$ but
$\\{i,j,k^{\prime\prime}\\}\notin\mathcal{S}^{+}$ as
$k^{\prime\prime}\notin\operatorname{pa}_{G}G(i)=S^{\ast}$.

Left to show is that $\mathcal{G}_{i\leftarrow j}$ is Markov equivalent to
$\mathcal{H}$. In the proof of Proposition 3.10, case (c)(i), we characterize
how imsets change when reversing an edge of the graph. Similar reasoning
applied to $\mathcal{G}_{i\leftarrow j}$ gives us that
$c_{\mathcal{G}_{i\leftarrow j}}=c_{\mathcal{H}}$.

∎

######  Lemma C.3.

Assume $\\{\mathcal{G},\mathcal{H}\\}$ is a flip with

$c_{\mathcal{H}}=c_{\mathcal{G}}+\sum_{S\in\mathcal{S}^{+}}e_{S}-\sum_{S\in\mathcal{S}^{-}}e_{S}$

with respect to $(i,j,S_{i},S_{j})$ and let $G$ be the skeleton of
$\mathcal{G}$ and $\mathcal{H}$. Assume moreover that $G$ is a tree.

Then $\operatorname{pa}_{\mathcal{H}}(i)\setminus\\{j\\}=S_{i}$,
$\operatorname{pa}_{\mathcal{G}}(j)\setminus\\{i\\}=S_{j}$ and there exists a
DAG $\mathcal{D}$ such that $\mathcal{D}$ is Markov equivalent to
$\mathcal{H}$ with $i\leftarrow j\in\mathcal{D}$ such that $\mathcal{D}_{i\to
j}$ is Markov equivalent to $\mathcal{G}$.

###### Proof.

If there exists a node $k\in S_{i}\cap S_{j}$ then we have
$c_{\mathcal{G}}(\\{i,j\\})=c_{\mathcal{G}}(\\{i,k\\})=c_{\mathcal{G}}(\\{j,k\\})=1$.
Thus we have a triangle in $G$, a contradiction as $G$ was a tree. Thus
$S_{i}$ and $S_{j}$ are disjoint.

Take nodes $p_{i}\in S_{i}$ and $p_{j}\in S_{j}$. Then as
$c_{\mathcal{H}}(\\{i,p_{i}\\})=c_{\mathcal{H}}(\\{i,j,p_{i}\\})=c_{\mathcal{H}}(\\{i,j\\})=1$
and since $G$ was a tree we get that $p_{i}\to i\leftarrow j\in\mathcal{H}$.
Then we get
$c_{\mathcal{G}}(\\{j,p_{j}\\})=c_{\mathcal{G}}(\\{i,j,p_{j}\\})=c_{\mathcal{G}}(\\{i,j\\})=1$
and since $G$ was a tree we get that $p_{j}\to j\leftarrow i\in\mathcal{G}$.
Since this holds for all $p_{i}$ and $p_{j}$ we get
$S_{i}\subseteq\operatorname{pa}_{\mathcal{H}}(i)\setminus\\{j\\}$ and
$S_{j}\subseteq\operatorname{pa}_{\mathcal{G}}(j)\setminus\\{i\\}$.

Assume we have
$k\in\operatorname{pa}_{\mathcal{H}}(i)\setminus(S_{i}\cup\\{j\\})$. Then we
get $c_{\mathcal{H}}(\\{i,j,k\\})=1$ and as $\\{i,j,k\\}\notin\mathcal{A}^{+}$
we get $c_{\mathcal{G}}(\\{i,j,k\\})=1$. But then $k\to i\leftarrow
j\in\mathcal{G}$, which is inconsistent with what we had before. Therefore
$\operatorname{pa}_{\mathcal{H}}(i)\setminus\\{j\\}=S_{i}$ and
$\operatorname{pa}_{\mathcal{G}}(j)\setminus\\{i\\}=S_{j}$.

Now let us construct $\mathcal{D}$. Let $G^{\prime}$ denote the graph
identical to $G$ except it does not have the edge $i-j$. Let $G_{i}$ be the
connected part of $G^{\prime}$ containing $i$ and let $G_{j}$ be the rest of
$G^{\prime}$. Define $\mathcal{D}$ as the orientation of $G$ where we direct
$G_{i}$ according to $\mathcal{H}$, direct $G_{j}$ according to $\mathcal{G}$
and direct $i-j$ as $i\leftarrow j$.

First we wish to show that $\mathcal{D}$ is Markov equivalent to
$\mathcal{H}$. By definition they both have the same skeleton, $G$. If we have
a subgraph $a-b-c\in G$ and a DAG $\mathcal{D}^{\prime}$ with skeleton $G$, we
have $c_{\mathcal{D}^{\prime}}(\\{a,b,c\\})=1$ if and only if $a-b-c$ is a
v-structure in $\mathcal{D}^{\prime}$.

Since $c_{\mathcal{H}}(S)=c_{\mathcal{G}}(S)$ for all
$S\notin\mathcal{S}^{+}\cup\mathcal{S}^{-}$ we get that if $\mathcal{G}$ and
$\mathcal{H}$ differ by a v-structure $a\to b\leftarrow c$ then
$\\{a,b,c\\}\in\mathcal{S}^{+}\cup\mathcal{S}^{-}$. So assume that we have a
v-structure in $\mathcal{D}$, name it $a\to b\leftarrow c$. If we do not have
$\\{a,b,c\\}\in\mathcal{S}^{+}\cup\mathcal{S}^{-}$ then this v-structure is in
either $\mathcal{G}$ or $\mathcal{H}$, by definition of $\mathcal{D}$. As
stated above $\mathcal{G}$ and $\mathcal{H}$ share all such v-structures, and
thus $a\to b\leftarrow c$ is a v-structure in $\mathcal{H}$.

If $\\{a,b,c\\}\in\mathcal{S}^{+}\cup\mathcal{S}^{-}$, then, up to symmetry,
we have that $b=i$, $c=j$ and $a\in\operatorname{pa}_{\mathcal{D}}(i)$ as we
directed $i\leftarrow j$ in $\mathcal{D}$. But as $i\leftarrow
j\in\mathcal{H}$ and we directed $\mathcal{D}$ as $\mathcal{H}$ in $G_{i}$,
$\mathcal{D}$ and $\mathcal{H}$ must share these v-structures as well. If we
have a v-structure in $\mathcal{H}$ it must be in $\mathcal{D}$ by the same
reasoning. Thus, via Theorem 2.1, $\mathcal{D}$ is Markov equivalent to
$\mathcal{H}$.

That $\mathcal{D}_{i\to j}$ and $\mathcal{G}$ are Markov equivalent follows by
a similar reasoning.

∎

######  Proposition C.4.

Let $\mathcal{G}$ and $\mathcal{H}$ be two DAGs on the same skeleton $G$, and
suppose that $G$ is a tree. If $\\{\mathcal{G},\mathcal{H}\\}$ is a shift then
$\mathop{\rm conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ is an edge of
$\mathop{\rm CIM}\nolimits_{G}$.

###### Proof.

It again suffices to construct an appropriate cost function
$w\in\mathbb{R}^{2^{p}-p-1}$ for which the maximum value of $w^{T}x$ over the
vertices of $\mathop{\rm CIM}\nolimits_{G}$ is achieved at exactly
$w_{\mathcal{G}}$ and $w_{\mathcal{H}}$. Let $\pi=\langle
i_{0},i_{1},\ldots,i_{2m+1}\rangle$ be the path where the shift occurs. Let
$S_{j}=\\{i_{j-1},i_{j},i_{j+1}\\}$. Let $\epsilon<m^{-2}$ and define

$w(S)=\begin{cases}m+1&\text{ if $c_{\mathcal{G}}(S)=1$ and $S\neq S_{j}$ for
all $1\leq j\leq 2m$ },\\\ 1+k\cdot\epsilon&\text{ if $S=S_{2k+1}$ for all
$0\leq k\leq m-1$},\\\ 1+k\cdot\epsilon&\text{ if $S=S_{2(m-k)}$ for all
$0\leq k\leq m-1$ },\\\ -(m+1)&\text{ otherwise}\\\ \end{cases}$

Since
$\sum_{k=0}^{m-1}w(S_{2k+1})=\sum_{k=0}^{m-1}w(S_{2(m-k)})=m+\binom{m}{2}\cdot\epsilon$
it follows that $w^{T}c_{\mathcal{G}}=w^{T}c_{\mathcal{H}}$. Note that
$\binom{m}{2}\cdot\epsilon<\frac{1}{2}$ by our choice of $\epsilon$.

As $G$ is a tree we have that $c_{\mathcal{D}}(S_{j})=1$ if and only if we
have a v-structure $i_{j-1}\rightarrow i_{j}\leftarrow i_{j+1}$ for any DAG
$\mathcal{D}$ with skeleton $G$. Thus we cannot have
$c_{\mathcal{D}}(S_{j})=c_{\mathcal{D}}(S_{j+1})=1$, again for any DAG
$\mathcal{D}$ with skeleton $G$, as that would give us $i_{j}\leftarrow
i_{j+1}$ and $i_{j}\rightarrow i_{j+1}$ in $\mathcal{D}$.

Now it only remains to check that if $\mathcal{D}$ is a DAG with skeleton $G$
that is not Markov equivalent to either $\mathcal{G}$ or $\mathcal{H}$, then
$w^{T}c_{\mathcal{D}}<w^{T}c_{\mathcal{G}}$. Since $\pi$ has odd length (even
number of vertices), $\mathcal{D}$ can have at most $m$ of the v-structures
encoded by $S_{j},1\leq j\leq 2m$. If $\mathcal{D}$ has less than $m$
v-structures then
$\sum_{i=1}^{2m}w(S_{i})c_{\mathcal{D}}(S_{i})<m-1+2\binom{m}{2}\cdot\epsilon<m$
and thus $w^{T}c_{\mathcal{D}}<w^{T}c_{\mathcal{G}}$.

If $\mathcal{D}$ has exactly $m$ of the v-structures along $\pi$ they must be
encoded by the sets $S_{1},S_{3},\dots,S_{2k-1}$ and
$S_{2k+2},S_{2k+4},\dots,S_{2m}$ for some $0\leq k\leq m$. If
$w^{T}c_{\mathcal{D}}=w^{T}c_{\mathcal{G}}$ then $k=0$ or $k=m$ which is the
same as $c_{\mathcal{D}}=c_{\mathcal{G}}$ or
$c_{\mathcal{D}}=c_{\mathcal{H}}$. ∎

######  Proposition C.5.

Let $\mathcal{G}$ and $\mathcal{H}$ be two DAGs on the same skeleton $G$, and
suppose that $G$ is a tree. If $\\{\mathcal{G},\mathcal{H}\\}$ is a split then
$\mathop{\rm conv}\nolimits(c_{\mathcal{G}},c_{\mathcal{H}})$ is an edge of
$\mathop{\rm CIM}\nolimits_{G}$.

###### Proof.

To start, we set $\mathcal{S}_{\pi}\coloneqq\mathcal{S}_{\pi,\mathop{\rm
even}\nolimits}\cup\mathcal{S}_{\pi,\mathop{\rm odd}\nolimits}$ for
$\pi=\langle i_{0},\dots,i_{2m}\rangle$. To prove the claim, it suffices to
find a cost vector $w\in\mathbb{R}^{2^{p}-p-1}$ such that $w^{T}x$ is
maximized at precisely $c_{\mathcal{G}}$ and $c_{\mathcal{H}}$ over the
vertices of $\mathop{\rm CIM}\nolimits_{G}$. To this end, define the cost
vector $w$ such that for $S\subseteq[p]$ with $|S|\geq 2$, $w$ satisfies

$w(S)=\begin{cases}1&\text{ if $c_{\mathcal{G}}(S)=1$},\\\
\frac{m-1}{m}&\text{ if $S\in\mathcal{S}_{\pi,\mathop{\rm odd}\nolimits}$},\\\
-1&\text{ otherwise}.\\\ \end{cases}$

Note first that, by the definitions of split and the fact that characteristic
imsets are $(0,1)$-vectors, we know that $c_{\mathcal{G}}(S)=1$ for all
$S\in\mathcal{S}_{\pi,\mathop{\rm even}\nolimits}$. It is then straightforward
that

$\begin{split}w^{T}c_{\mathcal{H}}&=w^{T}\left(c_{\mathcal{G}}-\sum_{S\in\mathcal{S}_{\pi,\mathop{\rm
even}\nolimits}}e_{S}+\sum_{S\in\mathcal{S}_{\pi,\mathop{\rm
odd}\nolimits}}e_{S}\right)\\\
&=w^{T}c_{\mathcal{G}}-(m-1)(1)+m\left(\frac{m-1}{m}\right)\\\
&=w^{T}c_{\mathcal{G}}.\\\ \end{split}$

So it remains to show that if $\mathcal{D}$ is a DAG with skeleton $G$ and
$\mathcal{D}$ is not Markov equivalent to either $\mathcal{G}$ or
$\mathcal{H}$ then $w^{T}c_{\mathcal{D}}<w^{T}c_{\mathcal{G}}$. Suppose that
$\mathcal{D}$ is such a DAG. We first make the following observation: Since
$G$ is a tree, we know that $c_{\mathcal{D}}(S)=1$ for $S\in\mathcal{S}_{\pi}$
if and only if $\mathcal{D}\\!\\!\mid_{S}$ is a v-structure of the form
$i_{j-1}\rightarrow i_{j}\leftarrow i_{j+1}$ for
$S=\\{i_{j-1},i_{j},i_{j+1}\\}$. Moreover, it follows that
$c_{\mathcal{D}}(S)=1$ and $c_{\mathcal{D}}(S^{\prime})=1$ for distinct
$S,S^{\prime}\in\mathcal{S}_{\pi}$ only if $S=\\{i_{j-1},i_{j},i_{j+1}\\}$ and
$S^{\prime}=\\{i_{k-1},i_{k},i_{k+1}\\}$ for some $j,k\in[2m-1]$ satisfying
$|j-k|>1$. For $x\in\mathbb{R}^{2^{p}-p-1}$ let
$x\\!\\!\mid_{\mathcal{S}_{\pi}}$ denote the restriction of $x$ to coordinates
in $\mathcal{S}_{\pi}$. It then, similarly as in proof of Proposition C.4,
follows that the maximum value of
$w\\!\\!\mid_{\mathcal{S}_{\pi}}^{T}\\!\\!c_{\mathcal{D}}\\!\\!\mid_{\mathcal{S}_{\pi}}$
over the vertices of $\mathop{\rm CIM}\nolimits_{G}$ is $m$, and this maximum
is achieved precisely when either $c_{\mathcal{D}}(S)=1$ for all
$S\in\mathcal{S}_{\pi,\mathop{\rm even}\nolimits}$ and $c_{\mathcal{D}}(S)=0$
for all $S\in\mathcal{S}_{\pi,\mathop{\rm odd}\nolimits}$ or when
$c_{\mathcal{D}}(S)=1$ for all $S\in\mathcal{S}_{\pi,\mathop{\rm
odd}\nolimits}$ and $c_{\mathcal{D}}(S)=0$ for all
$S\in\mathcal{S}_{\pi,\mathop{\rm even}\nolimits}$. Thus any $\mathcal{D}$
achieving $w^{T}c_{\mathcal{D}}=w^{T}c_{\mathcal{G}}$ must have
$c_{\mathcal{D}}(S)=c_{\mathcal{G}}(S)$ for all $S\notin S_{\pi}$ and either
$c_{\mathcal{D}}\\!\\!\mid_{S_{\pi}}=c_{\mathcal{G}}\\!\\!\mid_{S_{\pi}}$ or
$c_{\mathcal{D}}\\!\\!\mid_{S_{\pi}}=c_{\mathcal{H}}\\!\\!\mid_{S_{\pi}}$ That
is $c_{\mathcal{D}}=c_{\mathcal{G}}$ of $c_{\mathcal{D}}=c_{\mathcal{H}}$. ∎

##  Appendix D The Turn Phase and the Edge Phase Algorithms

Here we present the implementations of the edge phase and turn phase used in
Algorithm 1 and Algorithm 2. The edge phas and turn phase algorithms are
presented in Algorithm 3 and Algorithm 4, respectively.

Input: An imset $c_{\mathcal{G}}$ corresponding to a DAG $\mathcal{G}$. Data
$D$.

Output: A characteristic imset $c_{\mathcal{G}}$ where $\mathcal{G}$ is a DAG.

1 Let $G$ be the skeleton of $\mathcal{G}$;

2 $check\leftarrow\texttt{true}$;

3 while  _$check$_ do

4 $check\leftarrow\texttt{false}$;

5 for  _$i,j\in[p]$_ do

6 for  _$S^{\ast}\subseteq\operatorname{ne}_{G}(i)$_ do

7 if  _We have a DAG $\mathcal{H}$ such that $\\{\mathcal{G},\mathcal{H}\\}$
is an edge pair with respect to $(i,j,S^{\ast})$_ then

8 if  _$\mathop{\rm BIC}\nolimits(\mathcal{H}|D) >\mathop{\rm
BIC}\nolimits(\mathcal{G}|D)$_ then

9 $c_{\mathcal{G}}\leftarrow c_{\mathcal{H}}$;

10 Let $G$ be the skeleton of $\mathcal{G}$;

11 $check\leftarrow\texttt{true}$;

12 break;

13

14 end if

15

16 end if

17

18 end for

19

20 end for

21

22 end while

23return $c_{\mathcal{D}}$;

Algorithm 3 Edge phase

Input: An imset $c_{\mathcal{G}}$ corresponding to a DAG $\mathcal{G}$. Data
$D$.

Output: A characteristic imset $c_{\mathcal{G}}$ where $\mathcal{G}$ is a DAG.

1 $c_{\mathcal{D}}\leftarrow c_{\mathcal{G}}$;

2 Let $G$ be the skeleton of $\mathcal{G}$;

3 $check\leftarrow\texttt{true}$;

4 while  _$check$_ do

5 $check\leftarrow\texttt{false}$;

6 for  _$i,j\in[p]$_ do

7 for  _$S_{i}\subseteq\operatorname{ne}_{G}(i)$ and
$S_{j}\subseteq\operatorname{ne}_{G}(j)$_ do

8 if  _We have a DAG $\mathcal{H}$ such that $\\{\mathcal{D},\mathcal{H}\\}$
is an turn pair with respect to $(i,j,S_{i},S_{j})$_ then

9 if  _$\mathop{\rm BIC}\nolimits(\mathcal{H}|D) >\mathop{\rm
BIC}\nolimits(\mathcal{D}|D)$_ then

10 $c_{\mathcal{D}}\leftarrow c_{\mathcal{H}}$;

11 $check\leftarrow\texttt{true}$;

12

13 end if

14

15 end if

16

17 end for

18

19 end for

20

21 end while

22return $c_{\mathcal{G}}$;

Algorithm 4 Turn phase

## References

  * [1] Steen A. Andersson, David Madigan, and Michael D. Perlman.  A characterization of markov equivalence classes for acyclic digraphs.  Ann. Statist., 25(2):505–541, 04 1997.
  * [2] Benjamin Assarf, Ewgenij Gawrilow, Katrin Herr, Michael Joswig, Benjamin Lorenz, Andreas Paffenholz, and Thomas Rehn.  Computing convex hulls and counting integer points with polymake.  Math. Program. Comput., 9(1):1–38, 2017.
  * [3] David Maxwell Chickering.  A transformational characterization of equivalent bayesian network structures.  In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, UAI’95, pages 87–98, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc.
  * [4] David Maxwell Chickering.  Optimal structure identification with greedy search.  J. Mach. Learn. Res., 3:507–554, 2002.
  * [5] Vašek Chvátal.  On certain polytopes associated with graphs.  Journal of Combinatorial Theory, Series B, 18.2:138–154, 1975.
  * [6] Nir Friedman, Michal Linial, Iftach Nachman, and Dana Pe'er.  Using bayesian networks to analyze expression data.  Journal of Computational Biology, 7(3-4):601–620, August 2000.
  * [7] Ewgenij Gawrilow and Michael Joswig.  polymake: a framework for analyzing convex polytopes.  In Polytopes—combinatorics and computation (Oberwolfach, 1997), volume 29 of DMV Sem., pages 43–73. Birkhäuser, Basel, 2000.
  * [8] Alain Hauser and Peter Bühlmann.  Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs.  J. Mach. Learn. Res., 13(1):2409–2464, August 2012.
  * [9] Markus Kalisch, Martin Mächler, Diego Colombo, Marloes H. Maathuis, and Peter Bühlmann.  Causal inference using graphical models with the R package pcalg.  Journal of Statistical Software, 47(11):1–26, 2012.
  * [10] Steffen L. Lauritzen.  Graphical Models.  Oxford University Press, 1996.
  * [11] Silvia Lindner.  Discrete optimisation in machine learning: learning of Bayesian network structures and conditional independence implication.  PhD thesis, Technical University Munich, 2012.
  * [12] Fatemeh Mohammadi, Caroline Uhler, Charles Wang, and Josephine Yu.  Generalized permutohedra from probabilistic graphical models.  SIAM Journal on Discrete Mathematics, 32(1):64–93, 2018.
  * [13] Judea Pearl.  Causality : models, reasoning, and inference.  Cambridge University Press, Cambridge, U.K. New York, 2000.
  * [14] R Core Team.  R: A Language and Environment for Statistical Computing.  R Foundation for Statistical Computing, Vienna, Austria, 2020.
  * [15] Adityanarayanan Radhakrishnan, Liam Solus, and Caroline Uhler.  Counting markov equivalence classes for dag models on trees.  Discrete Applied Mathematics, 244:170 – 185, 2018.
  * [16] Petter Restadh and Liam Solus.  causalCIM. GitHub Repository.  Available at https://github.com/soluslab/causalCIM, 2021.
  * [17] James M. Robins, Miguel Ángel Hernán, and Babette Brumback.  Marginal structural models and causal inference in epidemiology.  Epidemiology, 11(5):550–560, September 2000.
  * [18] Liam Solus, Yuhao Wang, and Caroline Uhler.  Consistency guarantees for greedy permutation-based causal inference algorithms.  Biometrika, 2021.
  * [19] Peter Spirtes.  Causation, prediction, and search.  MIT Press, Cambridge, Mass, 2001.
  * [20] Peter Spirtes and Clark Glymour.  An algorithm for fast recovery of sparse causal graphs.  Social Science Computer Review, 9(1):62–72, 1991.