# The m-connecting imset and factorization for ADMG models

Bryan Andrews  Department of Philosophy, Carnegie Mellon University  Gregory
F. Cooper  Department of Biomedical Informatics, University of Pittsburgh
Thomas S. Richardson  Department of Statistics, University of Washington
Peter Spirtes  Department of Philosophy, Carnegie Mellon University

###### Abstract

Directed acyclic graph (DAG) models have become widely studied and applied in
statistics and machine learning—indeed, their simplicity facilitates efficient
procedures for learning and inference. Unfortunately, these models are not
closed under marginalization, making them poorly equipped to handle systems
with latent confounding. Acyclic directed mixed graph (ADMG) models
characterize margins of DAG models, making them far better suited to handle
such systems. However, ADMG models have not seen wide-spread use due to their
complexity and a shortage of statistical tools for their analysis.

In this paper, we introduce the m-connecting imset which provides an
alternative representation for the independence models induced by ADMGs.
Furthermore, we define the m-connecting factorization criterion for ADMG
models, characterized by a single equation, and prove its equivalence to the
global Markov property. The m-connecting imset and factorization criterion
provide two new statistical tools for learning and inference with ADMG models.
We demonstrate the usefulness of these tools by formulating and evaluating a
consistent scoring criterion with a closed form solution.

Keywords: ADMG models, imsetal conditional independence, factorization
criterion

##  1 Introduction

Directed acyclic graph (DAG) models, also known as Bayesian networks, have
become widely studied and applied in statistics and machine learning—indeed,
their simplicity facilitates efficient procedures for learning and inference
(Bishop,, 2006; Darwiche,, 2009; Koller and Friedman,, 2009). Furthermore, DAG
models allow for causal inference under a few additional assumptions (Spirtes
et al.,, 2000; Pearl,, 2009). These models describe probability distributions
that obey the conditional independence relations represented in a DAG, and may
be characterized by a well-known recursive factorization. Moreover,
multinomial and Gaussian DAG models form curved exponential families with
known dimension (Geiger et al.,, 2001). While variables may be added to DAG
models to account for latent confounding, doing so leads to several challenges
(Richardson and Spirtes,, 2002):

  * $\bullet$

these models are not always identifiable;

  * $\bullet$

inference may be sensitive to assumptions made about the latent variables;

  * $\bullet$

these models are not curved exponential families Geiger et al., (2001);

  * $\bullet$

distributions associated with one of these models may be difficult to
characterize Settimi and Smith, (1998, 2000).

Alternatively, we could consider models that describe probability
distributions obeying the conditional independence relations represented in
margins of DAGs. In this paradigm, we treat latent confounding as marginalized
variables, thereby making no assumptions about the latent variables. However,
DAG models, are not closed under marginalization. As a result, several authors
have explored more general families of graphical models that are closed under
marginalization (Richardson and Spirtes,, 2002; Sadeghi,, 2013).

Figure 1: Graphical representations for a system with latent confounding: (i)
a DAG with an explicitly defined latent variable; (ii) an ADMG for the induced
marginal independence model.

In this work, we focus on acyclic directed mixed graph (ADMG) models due to
their simple and intuitive derivation as latent projections of DAGs (Verma and
Pearl,, 1990; Evans, 2018b, ). Figure 1 illustrates a DAG with a latent
variable and the corresponding ADMG. Notably, ADMGs generalize other families
of graphical models that are closed under marginalization, such as directed
(maximal) ancestral graphs (Sadeghi,, 2013). Accordingly, the results of this
paper directly apply to those subfamilies.

ADMG models describe probability distributions that obey the conditional
independence relations represented in an ADMG. Auspiciously, multinomial and
Gaussian ADMG models form curved exponential families with known dimension
(Richardson and Spirtes,, 2002; Evans and Richardson,, 2014). However, these
models have not seen wide-spread use due to their complexity and a shortage of
statistical tools for their analysis. Similarly, Studený, (2005) introduced
structural imsets as a non-graphical representation of conditional
independence which, while capable of representing all probabilistic
independence models, have not seen wide-spread use. Developments to the
imsetal representation of conditional independence have been largely
theoretical, except for in constrained scenarios, such as the restriction to
DAG independence models—indeed, several methods use imsets to learn DAGs
(Studený,, 2008; Studený and Cussens,, 2017; Studený and Haws,, 2014). A
recent innovation in the space of imsetal independence models introduced the
characteristic imset as a more natural representation of DAG independence
models (Hemmecke et al.,, 2012).

In this paper we introduce the m-connecting imset, which is analogous to the
characteristic imset for DAG models, in order to expand the tools available
for analysis of ADMG models. Indeed, we show how the m-connecting imset admits
a novel factorization criterion, characterized by a single equation, that is
equivalent to the global Markov property—we call this new criterion the
m-connecting factorization. Using the m-connecting factorization, we formulate
a consistent scoring criterion with a closed-form solution for curved
exponential families whose independence models are described by ADMGs. We
investigate asymptotic properties of our score and compare its ability to
recover correct independence models against the well-known FCI algorithm and
two of its variants

This paper details the methods developed in a recent PhD thesis (Andrews,,
2022) and is organized as follows. Section 2 introduces and discusses concepts
relevant to ADMGs, imsets, and independence models. Section 3 introduces the
m-connecting imset and factorization and proves the equivalence of the
m-connecting factorization to the global Markov property for ADMG models.
Section 4 formulates a consistent scoring criterion for ADMG curved
exponential families and investigates its ability to recover correct
independence models against the well-known FCI algorithm and two of its
variants. Section 5 provides a discussion and states our conclusions. For
readability, all proofs are postponed until the appendix.

##  2 Background

In this section, we introduce and discuss concepts relevant to ADMGs, imsets,
and independence models in order to facilitate the formulation of the
m-connecting imset and factorization; partially ordered sets and the Möbius
inversion are of particular importance for the latter. Throughout this paper,
$V$ denotes a non-empty finite set of variables that act as vertices in
graphical contexts. We use the following notational conventions:

  * $\bullet$

$a,b,c,\ldots\>\in V$ lowercase letters denote variables or singletons;

  * $\bullet$

$A,B,C,\ldots\>\subseteq V$ uppercase letters denote sets of variables;

  * $\bullet$

$\mathsf{A},\mathsf{B},\mathsf{C},\ldots\>\subseteq\mathcal{P}(V)$ uppercase
sans-serif letters denote sets of sets;

where $\mathcal{P}(V)$ denotes the power set of $V$. Additionally,
juxtapositions of sets denote their unions (e.g., $AB=A\cup B$).

###  2.1 Acyclic Directed Mixed Graphs

Let $\mathcal{E}(V)$ be a set of ordered and unordered pairs:

$\mathcal{E}(V)\equiv\\{(a,b)\;:\;a,b\in V\;(a\neq
b)\\}\;\cup\;\\{\\{a,b\\}\;:\;a,b\in V\;(a\neq b)\\}.$

######  Definition (directed mixed graph).

A directed mixed graph is an ordered pair $\mathcal{G}=(V,E)$ where
$E\subseteq\mathcal{E}(V)$. Graphically, the elements of $V$ act as vertices
and the elements of $E$ act as directed and bi-directed edges. Accordingly,
for $a,b\in V$ we write:

$\left\\{\\!\\!\begin{array}[]{c}a\rightarrow b\\\ a\leftrightarrow
b\end{array}\\!\\!\right\\}\>\text{in}\mkern 7.0mu\mathcal{G}\mkern
7.0mu\text{if}\>\left\\{\\!\\!\begin{array}[]{c}\mkern-4.0mu(a,b)\mkern-4.0mu\\\
\mkern-4.0mu\\{a,b\\}\mkern-4.0mu\end{array}\\!\\!\right\\}\in E.$

A directed mixed graph is mixed in the sense that it contains a mixture of
directed and bi-directed edges, and directed in the sense that it does not
contain undirected edges. This is not to be confused with a directed graph,
which is a graph that only contains directed edges. A directed mixed graph is
acyclic if it does not contain a sequence of the following form:

$v_{1}\rightarrow\dots\rightarrow v_{n}\rightarrow v_{1}\mkern
18.0mu\text{for}\>n\geq 2.$

In this paper, we focus on acyclic directed mixed graphs (ADMGs)—directed
mixed graphs that are acyclic. Next, we review a few graphical concepts used
to describe ADMGs.

######  Definition (induced subgraph).

Let $\mathcal{G}=(V,E)$ be an ADMG and $A\subseteq V$. The induced subgraph of
$\mathcal{G}$ with respect to $A$ is the ordered pair:

$\mathcal{G}_{A}\equiv(A,E\cap\mathcal{E}(A)).$

######  Definition (path).

A path $\pi=\langle v_{1},e_{1},\dots,v_{n}\rangle$ $(n\geq 2)$ is an
alternating sequence of distinct vertices and edges where
$e_{i}=(v_{i},v_{i+1})$ or $e_{i}=\\{v_{i},v_{i+1}\\}$ for $1\leq i<n$. The
endpoints of $\pi$ are the first and last vertices $\\{v_{1},v_{n}\\}$ and are
adjacent if $(v_{1},v_{n})\in E$ or $\\{v_{1},v_{n}\\}\in E$.

In this paper, we use sequences of vertices to describe paths in ADMGs even if
there is more than one edge between a pair of vertices—the intended edge for a
pair of vertices will either be obvious from the context or irrelevant.

######  Definition (triple).

A triple is a path $\pi=\langle v_{1},v_{2},v_{3}\rangle$ with three vertices
and is unshielded if its endpoints are not adjacent.

######  Definition (collider).

A collider on a path $\pi=\langle v_{1},\dots,v_{n}\rangle$ is a vertex
$v_{i}$ such that:

$\\{v_{i-1}\;{*\mkern-1.0mu\clipbox{1.5mm-1mm-1mm-1mm}{\rightarrow}}v_{i}{\clipbox{-1mm-1mm1.5mm-1mm}{\leftarrow}\mkern-1.0mu*}\;v_{i+1}\\}\mkern
7.0mu\text{in}\mkern 7.0mu\mathcal{G}$

where asterisks are used to denote edge marks that may either be an arrowhead
or a tail. Moreover, the collider is an unshielded collider if the
corresponding triple is unshielded.

######  Definition (non-collider).

A non-collider on a path $\pi=\langle v_{1},\dots,v_{n}\rangle$ is a vertex
$v_{i}$ such that:

$\left\\{\\!\\!\begin{array}[]{c}v_{i-1}\leftarrow v_{i}\rightarrow v_{i+1}\\\
v_{i-1}\;{*\mkern-1.0mu\clipbox{1.5mm-1mm-1mm-1mm}{$\rightarrow$}}v_{i}\rightarrow
v_{i+1}\\\ v_{i-1}\leftarrow
v_{i}{\clipbox{-1mm-1mm1.5mm-1mm}{$\leftarrow$}\mkern-1.0mu*}\;v_{i+1}\end{array}\\!\\!\right\\}\>\text{in}\mkern
7.0mu\mathcal{G}$

where asterisks are used to denote edge marks that may either be an arrowhead
or a tail. Moreover, the non-collider is an unshielded non-collider if the
corresponding triple is unshielded.

ADMGs arise naturally from DAGs with latent variables via a process called
latent projection (Verma and Pearl,, 1990; Evans, 2018b, ). For example, the
ADMG in Figure 1 (ii) illustrates the latent projection of the DAG in Figure 1
(i). Notably, every DAG is an ADMG. We define latent projection with respect
to ADMGs.

Input: ADMG: $\mathcal{G}$, vertex set $L$

Output: ADMG: $\mathcal{G}$

1 foreach  _$l\in L$_ do

2 foreach  _triple $\langle a,l,b\rangle$ in $\mathcal{G}$_ do

3 if  _$a\rightarrow l\rightarrow b$ in $\mathcal{G}$ and $a\rightarrow b$ not
in $\mathcal{G}$_ then

4 Add $a\rightarrow b$ to $\mathcal{G}$ ;

5

6 if  _$\left\\{\\!\\!\begin{array}[]{c}a\leftarrow l\rightarrow b\\\
a\leftrightarrow l\rightarrow b\end{array}\\!\\!\right\\}$ in $\mathcal{G}$
and $a\leftrightarrow b$ not in $\mathcal{G}$_ then

7 Add $a\leftrightarrow b$ to $\mathcal{G}$ ;

8

9

10 Remove $l$ from $\mathcal{G}$ ;

11

Algorithm 1 Latent Projection $\textsc{LP}(\mathcal{G},L)$

Next, we review standard terminology for describing how vertices relate in an
ADMG. Let $\mathcal{G}=(V,E)$ be an ADMG and $a\in V$:

$\displaystyle\textup{pa}_{\mathcal{G}}(a)$ $\displaystyle\equiv\\{b\in
V\;:\;b\rightarrow a\mkern 7.0mu\text{in}\mkern 7.0mu\mathcal{G}\\};$
$\displaystyle\textup{ch}_{\mathcal{G}}(a)$ $\displaystyle\equiv\\{b\in
V\;:\;b\leftarrow a\mkern 7.0mu\text{in}\mkern 7.0mu\mathcal{G}\\};$
$\displaystyle\textup{sib}_{\mathcal{G}}(a)$ $\displaystyle\equiv\\{b\in
V\;:\;b\leftrightarrow a\mkern 7.0mu\text{in}\mkern 7.0mu\mathcal{G}\\}$

are the parents, children, and siblings of $a$, respectively. Similarly:

$\displaystyle\textup{an}_{\mathcal{G}}(a)$ $\displaystyle\equiv\\{b\in
V\;:\;b\rightarrow\cdots\rightarrow a\mkern 7.0mu\text{or}\mkern
7.0mub\rightarrow a\mkern 7.0mu\text{in}\mkern 7.0mu\mathcal{G}\mkern
7.0mu\text{or}\mkern 7.0mua=b\\};$ $\displaystyle\textup{de}_{\mathcal{G}}(a)$
$\displaystyle\equiv\\{b\in V\;:\;b\leftarrow\cdots\leftarrow a\mkern
7.0mu\text{or}\mkern 7.0mub\leftarrow a\mkern 7.0mu\text{in}\mkern
7.0mu\mathcal{G}\mkern 7.0mu\text{or}\mkern 7.0mua=b\\};$
$\displaystyle\textup{dis}_{\mathcal{G}}(a)$ $\displaystyle\equiv\\{b\in
V\;:\;b\leftrightarrow\cdots\leftrightarrow a\mkern 7.0mu\text{or}\mkern
7.0mub\leftrightarrow a\mkern 7.0mu\text{in}\mkern 7.0mu\mathcal{G}\mkern
7.0mu\text{or}\mkern 7.0mua=b\\}$

are the ancestors, descendants, and district of $a$, respectively. These
functions are applied disjunctively to sets, in other words, applying one to a
set of vertices is the union of the operation applied to each vertex in the
set. For example, $A\subseteq V$ has parents and ancestors:

$\textup{pa}_{\mathcal{G}}(A)\equiv\bigcup_{a\in
A}\textup{pa}_{\mathcal{G}}(a)\mkern
72.0mu\textup{an}_{\mathcal{G}}(A)\equiv\bigcup_{a\in
A}\textup{an}_{\mathcal{G}}(a).$

On the other hand:

$\textup{col}_{\mathcal{G}}(a)\equiv\\{b\in
V\;:\left\\{\\!\\!\begin{array}[]{c}b\rightarrow\;\leftrightarrow\cdots\leftrightarrow\;\leftarrow
a\\\ b\rightarrow\;\leftrightarrow\cdots\leftrightarrow a\\\
b\leftrightarrow\cdots\leftrightarrow\;\leftarrow a\\\
b\leftrightarrow\cdots\leftrightarrow
a\end{array}\\!\\!\right\\}\>\text{or}\>\left\\{\\!\\!\begin{array}[]{c}b\rightarrow\;\leftarrow
a\\\ b\rightarrow a\\\ b\leftarrow a\\\ b\leftrightarrow
a\end{array}\\!\\!\right\\}\>\text{in}\mkern 7.0mu\mathcal{G}\mkern
7.0mu\text{or}\mkern 7.0mua=b\\}$

are the collider-connecting vertices of $a$. This function is applied
conjunctively to sets, in other words, applying it to a set of vertices is the
intersection of the operation applied to each vertex in the set. For example,
a set of vertices $A\subseteq V$ has collider-connecting vertices:

$\textup{col}_{\mathcal{G}}(A)\equiv\bigcap_{a\in
A}\textup{col}_{\mathcal{G}}(a).$

The use of conjunction rather than disjunction ensures that the collider-
connecting vertices of a set are contiguously connected by colliders on some
path.

Lastly, we review a few special types of sets that will be useful throughout
this paper.

######  Definition (ancestral set).

Let $\mathcal{G}=(V,E)$ be an ADMG and $A\subseteq V$. If
$A=\textup{an}_{\mathcal{G}}(A)$, then $A$ is an ancestral set. In other
words, $A$ contains its own ancestors. The set of all ancestral sets is
defined:

$\mathcal{A}(\mathcal{G})\equiv\\{A\in\mathcal{P}(V)\;:\;A=\textup{an}_{\mathcal{G}}(A)\\}.$

Figure 2 illustrates the nontrivial ancestral sets of an ADMG. Notably, the
concepts of induced subgraph and latent projection are equivalent for
ancestral sets.

######  Proposition 2.1 (Evans, (2016)).

Let $\mathcal{G}=(V,E)$ be an ADMG and $A\subseteq V$. If
$A\in\mathcal{A}(\mathcal{G})$, then:

$\mathcal{G}_{A}=\textsc{LP}(\mathcal{G},V\setminus A).$

######  Definition (collider-connecting set).

Let $\mathcal{G}=(V,E)$ be an ADMG and $C\subseteq V$. If
$C=\textup{col}_{\mathcal{G}_{C}}(C)$, then $C$ is a collider-connecting set.
In other words, the members of $C$ are collider-connecting by paths using only
members of $C$. The set of all collider-connecting sets is defined:

$\mathcal{C}(\mathcal{G})\equiv\\{C\in\mathcal{P}(V)\;:\;C=\textup{col}_{\mathcal{G}_{C}}(C)\\}.$

Figure 2 illustrates the nontrivial collider-connecting sets of an ADMG.

######  Definition (barren subset).

Let $\mathcal{G}=(V,E)$ be an ADMG and $B\subseteq V$. If
$A=\smash{\bigcup\limits_{b\in B}}\textup{an}_{\mathcal{G}}(b)\setminus b$,
then the barren subset of $B$ is defined:

$\textup{bar}_{\mathcal{G}}(B)\equiv B\setminus A.$

In other words, the barren subset of $B$ contains the members of $B$ that are
not ancestors of other members of $B$.

Figure 2 illustrates the nontrivial barren subsets of an ADMG.

$\blockarray{c@{\hskip 14.22636pt}c@{\hskip 14.22636pt}c@{\hskip
14.22636pt}c}S&S\in\mathcal{A}(\mathcal{G})S\in\mathcal{C}(\mathcal{G})\textup{bar}_{\mathcal{G}}(S)\\\
\block{c@{\hskip 14.22636pt}c@{\hskip 14.22636pt}c@{\hskip
14.22636pt}c}\\{a,b\\}10\\{a,b\\}\\\ \\{a,c\\}11\\{c\\}\\\
\\{a,d\\}01\\{a,d\\}\\\ \\{b,c\\}01\\{b,c\\}\\\ \\{b,d\\}11\\{d\\}\\\
\\{c,d\\}00\\{c,d\\}\\\ \\{a,b,c\\}11\\{b,c\\}\\\ \\{a,b,d\\}11\\{a,d\\}\\\
\\{a,c,d\\}00\\{c,d\\}\\\ \\{b,c,d\\}00\\{c,d\\}\\\
\\{a,b,c,d\\}10\\{c,d\\}\\\ $

Figure 2: An ADMG and its nontrivial ancestral sets, collider-connecting sets,
and barren subsets.

###  2.2 Partially Ordered Sets

Throughout this paper, $\mathsf{P}$ denotes a finite partially ordered set.
Notably, the elements of $\mathsf{P}$ can be variables or sets of
variables—hence our choice of notation.

######  Definition (partial order).

A partial order is a binary relation $\leq$ over a set $\mathsf{P}$ such that
$\leq$ is reflexive, antisymmetric, and transitive. In other words, for every
collection of elements $A,B,C\in\mathsf{P}$:

  1. i.

reflexivity  $A\leq A$;

  2. ii.

antisymmetry  $A\leq B$ and $B\leq A$ $\mkern 18.0mu\Rightarrow\mkern 18.0mu$
$A=B$;

  3. iii.

transitivity  $A\leq B$ and $B\leq C$ $\mkern 18.0mu\Rightarrow\mkern 18.0mu$
$A\leq C$.

######  Definition (partially ordered set).

A partially ordered set, poset for short, is a set $\mathsf{P}$ with a partial
order $\leq$. A pair of elements $A,B\in\mathsf{P}$ are comparable if $A\leq
B$ or $B\leq A$ and incomparable otherwise. If every pair of elements is
comparable, then $\leq$ is a total order.

Two simple examples of partially ordered sets used throughout this paper are
$V$ ordered by a total order consistent with an ADMG $\mathcal{G}=(V,E)$ and
$\mathcal{P}(V)$ ordered by inclusion.

######  Definition (consistent order).

If $\mathcal{G}=(V,E)$ is an ADMG and $\leq$ is a total order where:

$a\leq b\mkern 18.0mu\Rightarrow\mkern
18.0mub\not\in\textup{an}_{\mathcal{G}}(a)\mkern 18.0mu\text{for all}\mkern
18.0mua,b\in V\>(a\neq b),$

then $\leq$ is a consistent with $\mathcal{G}$.

######  Definition (preceding vertices).

Let $\mathcal{G}=(V,E)$ be an ADMG with consistent order $\leq$. If $b\in V$,
then the preceding vertices of $b$ with respect to $\leq$ are defined:

$\textup{pre}^{\leq}_{\mathcal{G}}(b)\equiv\\{a\in V\;:\;a\leq b\\}.$

This function is applied disjunctively to sets, in other words, applying is to
a set of vertices is the union of the operation applied to each vertex in the
set. For example, $A\subseteq V$ has preceding vertices:

$\textup{pre}^{\leq}_{\mathcal{G}}(A)\equiv\bigcup_{a\in
A}\textup{pre}^{\leq}_{\mathcal{G}}(a).$

######  Definition (inclusion order).

If $\mathsf{P}=\mathcal{P}(V)$ and $\leq$ is the partial order where:

$A\leq B\mkern 18.0mu\Leftrightarrow\mkern 18.0muA\subseteq B\mkern
18.0mu\text{for all}\mkern 18.0muA,B\in\mathsf{P}$

then $\mathcal{P}(V)$ is ordered by inclusion.

Figure 3: The Hasse diagram for the poset
$\mathsf{P}=\mathcal{P}(\\{a,b,c\\})$ ordered by inclusion.

Figure 3 illustrates the Hasse diagram for the poset
$\mathsf{P}=\mathcal{P}(\\{a,b,c\\})$ ordered by inclusion. Given a poset, we
will also reference its maximal/minimal subsets.

######  Definition (maximal/minimal subset).

If $\mathsf{P}$ is a poset with partial order $\leq$ and
$\mathsf{S}\subseteq\mathsf{P}$, then the maximal and minimal subsets of $S$
are defined:

$\lceil\mathsf{S}\rceil_{\leq}\equiv\\{A\in\mathsf{S}\;:\;A\not\leq B\mkern
18.0mu\text{for all}\;B\in\mathsf{S}\;(A\neq B)\\};$
$\lfloor\mathsf{S}\rfloor_{\leq}\equiv\\{A\in\mathsf{S}\;:\;B\not\leq A\mkern
18.0mu\text{for all}\;B\in\mathsf{S}\;(A\neq B)\\}.$

If we can guarantee that the maximal/minimal subset of $S$ is a unique
singleton, such as when $\leq$ is a total order, then we abuse notation and
interpret the output as the element of the singleton. Moreover, if no partial
order is given, then the poset is assumed to be ordered by inclusion. For
example:

  * $\bullet$

$\lceil V\rceil_{\leq}=d$ in Figure 1(ii) where $\leq$ is a consistent order;

  * $\bullet$

$\lfloor V\rfloor_{\leq}=a$ in Figure 1(ii) where $\leq$ is a consistent
order;

  * $\bullet$

$\lceil\mathcal{P}(\\{a,b,c\\})\rceil=\\{a,b,c\\}$ in Figure 3;

  * $\bullet$

$\lfloor\mathcal{P}(\\{a,b,c\\})\setminus\varnothing\rfloor=\\{\\{a\\},\\{b\\},\\{c\\}\\}$
in Figure 3.

For the remainder of this paper, unless otherwise specified, $\mathsf{P}$ is
the poset $\mathcal{P}(V)$ ordered by inclusion.

###  2.3 Möbius Inversion

Two useful functions for analyzing posets that will be fundamental to deriving
the m-connecting factorization are the zeta function and Möbius function. The
zeta function
$\zeta_{\mathsf{P}}:\mathsf{P}\times\mathsf{P}\rightarrow\\{0,1\\}$ is
defined:

$\zeta_{\mathsf{P}}(B,A)=\begin{cases}\mkern 18.0mu1\mkern 36.0mu&B\subseteq
A;\\\ \mkern 18.0mu0\mkern 36.0mu&B\not\subseteq A,\end{cases}$

and the Möbius function $\mu_{\mathsf{P}}\mkern
0.5mu:\mathsf{P}\times\mathsf{P}\rightarrow\mathbb{Z}$ is defined:

$\mu_{\mathsf{P}}(B,A)=\begin{cases}\mkern 6.0mu(-1)^{|A\setminus B|}\mkern
36.0mu&B\subseteq A;\\\ \mkern 18.0mu0\mkern 36.0mu&B\not\subseteq
A.\end{cases}$

The posets we consider are finite and may be thought of as matrices. Abusing
notation, we interpret $\zeta_{\mathsf{P}}$ and $\mu_{\mathsf{P}}$ as matrices
where the first and second arguments act as the row and column indices,
respectively. Under this interpretation, the Möbius function is the inverse of
the zeta function in the sense that $\mu_{\mathsf{P}}\mkern
0.5mu=\zeta_{\mathsf{P}}^{-1}$.

$\blockarray{ccccccccc}\zeta_{\mathsf{P}}&\varnothing\\{a\\}\\{b\\}\\{c\\}\\{a,b\\}\\{a,c\\}\\{b,c\\}\\{a,b,c\\}\\\
\block{c[cccccccc]}\varnothing 11111111\\\ \\{a\\}01001101\\\
\\{b\\}00101011\\\ \\{c\\}00010111\\\ \\{a,b\\}00001001\\\
\\{a,c\\}00000101\\\ \\{b,c\\}00000011\\\ \\{a,b,c\\}00000001\\\ $ Figure 4:
The zeta function of a poset $\mathsf{P}=\mathcal{P}(\\{a,b,c\\})$ ordered by
inclusion—the first and second arguments of the zeta function act as row and
column indices, respectively.

Figure 4 depicts the zeta function $\zeta_{\mathsf{P}}$ as a matrix for the
poset depicted in Figure 3. Notice that the matrix is invertible—it is an
upper triangular matrix with non-zero entries on the main diagonal. In
general, the rows and columns of the matrix corresponding to the zeta function
of a poset can be rearranged in this manner. Accordingly, the matrix
corresponding to the zeta function is invertible.

$\blockarray{ccccccccc}\mu_{\mathsf{P}}\mkern
0.5mu&\varnothing\\{a\\}\\{b\\}\\{c\\}\\{a,b\\}\\{a,c\\}\\{b,c\\}\\{a,b,c\\}\\\
\block{c[cccccccc]}\varnothing 1\hbox to0.0pt{\hss$-$}1\hbox
to0.0pt{\hss$-$}1\hbox to0.0pt{\hss$-$}1111\hbox to0.0pt{\hss$-$}1\\\
\\{a\\}0100\hbox to0.0pt{\hss$-$}1\hbox to0.0pt{\hss$-$}101\\\
\\{b\\}0010\hbox to0.0pt{\hss$-$}10\hbox to0.0pt{\hss$-$}11\\\
\\{c\\}00010\hbox to0.0pt{\hss$-$}1\hbox to0.0pt{\hss$-$}11\\\
\\{a,b\\}0000100\hbox to0.0pt{\hss$-$}1\\\ \\{a,c\\}0000010\hbox
to0.0pt{\hss$-$}1\\\ \\{b,c\\}0000001\hbox to0.0pt{\hss$-$}1\\\
\\{a,b,c\\}00000001\\\ $ Figure 5: The Möbius function of a poset
$\mathsf{P}=\mathcal{P}(\\{a,b,c\\})$ ordered by inclusion—the first and
second arguments of the Möbius function act as row and column indices,
respectively.

Figure 5 depicts the Möbius function $\mu_{\mathsf{P}}$ as a matrix for the
poset depicted in Figure 3. Again, notice that $\mu_{\mathsf{P}}$ is
invertible—it is an upper triangular matrix with non-zero entries on the main
diagonal. We encourage the reader to check that the matrices depicted in
Figures 4 and 5 are indeed inverses of each other. This relation holds in
general and provides a good intuition for the Möbius inversion.

######  Proposition 2.2 (Rota, (1964)).

Let $\mathsf{P}$ be a poset, and $g:\mathsf{P}\rightarrow\mathbb{R}$ and
$h:\mathsf{P}\rightarrow\mathbb{R}$ be real-valued functions. The following
expressions imply each other:

  1. i.

$g(A)=\sum\limits_{B\in\mathsf{P}}h(B)\,\mu_{\mathsf{P}}(B,A)\mkern
18.0mu\textup{for all}\;A\in\mathsf{P}$;

  2. ii.

$h(A)=\sum\limits_{B\in\mathsf{P}}g(B)\,\zeta_{\mathsf{P}}(B,A)\mkern
18.0mu\textup{for all}\;A\in\mathsf{P}$.

Alternatively, if we abuse notation and treat $g$ and $h$ as column vectors,
then the Möbius inversion states that
$g=\mu_{\mathsf{P}}^{\top}h\,\Leftrightarrow\,h=\zeta_{\mathsf{P}}^{\top}g$.
If $\mathsf{P}=\mathcal{P}(V)$ is a poset ordered by inclusion, then the
Möbius inversion simplifies to the following equivalent statements:

  1. i.

$g(A)=\sum\limits_{B\subseteq A}(-1)^{|A\setminus B|}\,h(B)\mkern
18.0mu\textup{for all}\;A\subseteq V$;

  2. ii.

$h(A)=\sum\limits_{B\subseteq A}g(B)\mkern 18.0mu\textup{for all}\;A\subseteq
V$.

######  Corollary 2.1 (Rota, (1964)).

Let $\mathsf{P}$ be a poset and $g:\mathsf{P}\rightarrow\mathbb{R}$ and
$h:\mathsf{P}\rightarrow\mathbb{R}$ be real-valued functions. The following
expressions imply each other:

  1. i.

$g(A)=\sum\limits_{B\in\mathsf{P}}\mu_{\mathsf{P}}(A,B)\,h(B)\mkern
18.0mu\textup{for all}\;A\in\mathsf{P}$;

  2. ii.

$h(A)=\sum\limits_{B\in\mathsf{P}}\zeta_{\mathsf{P}}(A,B)\,g(B)\mkern
18.0mu\textup{for all}\;A\in\mathsf{P}$.

Alternatively, if we abuse notation and view $g$ and $h$ as column vectors,
then the corollary states that $g=\mu_{\mathsf{P}}\mkern
0.5muh\,\Leftrightarrow\,h=\zeta_{\mathsf{P}}g$. If $V$ is a non-empty set of
variables and $\mathsf{P}=\mathcal{P}(V)$ is a poset ordered by inclusion,
then the corollary simplifies to the following equivalent statements:

  1. i.

$g(A)=\sum\limits_{\begin{subarray}{c}B\subseteq V\\\ A\subseteq
B\end{subarray}}(-1)^{|B\setminus A|}\,h(B)\mkern 18.0mu\textup{for
all}\;A\subseteq V$;

  2. ii.

$h(A)=\sum\limits_{\begin{subarray}{c}B\subseteq V\\\ A\subseteq
B\end{subarray}}g(B)\mkern 18.0mu\textup{for all}\;A\subseteq V$.

$\blockarray{c@{\hskip 28.45274pt}c@{\hskip 42.67912pt}c@{\hskip
28.45274pt}c@{\hskip 28.45274pt}c}S&g(S)Sh(S)\\\ \block{c@{\hskip
28.45274pt}[c]@{\hskip 42.67912pt}c@{\hskip 28.45274pt}c@{\hskip
28.45274pt}[c]}\varnothing 0\varnothing 0\\\
\\{a\\}0\smash{\overset{\zeta_{\mathsf{P}}^{\top}\;}{\longrightarrow}}\\{a\\}0\\\
\\{b\\}0\\{b\\}0\\\ \\{c\\}1\\{c\\}0\\\ \\{a,b\\}0\\{a,b\\}1\\\ \\{a,c\\}\hbox
to0.0pt{\hss$-$}1\\{a,c\\}0\\\ \\{b,c\\}\hbox
to0.0pt{\hss$-$}1\smash{\overset{\;\;\mu_{\mathsf{P}}^{\top}}{\longleftarrow}}\\{b,c\\}0\\\
\\{a,b,c\\}1\\{a,b,c\\}1\\\ $ Figure 6: An application of the Möbius
inversion.

Figure 6 depicts an application of the Möbius inversion. If
$g:\mathsf{P}\rightarrow\mathbb{R}$ and $h:\mathsf{P}\rightarrow\mathbb{R}$
are real-valued functions satisfying Proposition 2.2, then the zeta function
depicted in Figure 4 applied to $g$ returns $h$ and the Möbius function
depicted in Figure 5 applied to $h$ returns $g$. The Möbius inversion will be
used in this manner to transition between imsetal representations of
conditional independence.

###  2.4 Independence Models

Conditional independence is often used synonymously with probabilistic
conditional independence—conditional independence statements that are
represented in a probability measure. We use this term more generally to
include graphical and imsetal conditional independence—conditional
independence statements that are represented in an ADMG and an imset,
respectively.

######  Definition (disjoint triple).

If $A,B,C\subseteq V$ are disjoint, then $\langle A,B\mid C\rangle$ is the
corresponding disjoint triple. The set of all disjoint triples is defined:

$\mathcal{T}(V)\equiv\\{\langle A,B\mid C\rangle\;:\;A,B,C\subseteq
V\;\text{and}\;A\cap B=A\cap C=B\cap C=\varnothing\\}.$

######  Definition (independence statement).

If $\mathcal{O}$ is a mathematical object over $V$ and $\langle A,B\mid
C\rangle\in\mathcal{T}(V)$, then the statement “$A$ and $B$ are independent
given $C$ with respect to $\mathcal{O}$” is an independence statement. In this
case, we say $\langle A,B\mid C\rangle$ is represented in $\mathcal{O}$ and
write $A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5mu\mathcal{O}\mkern
0.5mu]$.

######  Definition (independence model).

If $\mathcal{O}$ is a mathematical object over $V$, then the independence
model induced by $\mathcal{O}$ is defined:

$\mathcal{I}(\mathcal{O})\equiv\left\\{\langle A,B\mid
C\rangle\in\mathcal{T}(V)\;:\;A\perp\mkern-9.0mu\perp B\mid C\;[\mkern
0.5mu\mathcal{O}\mkern 0.5mu]\right\\}.$

Several families of independence models have been axiomatically characterized.
The independence model $\mathcal{I}(\mathcal{O})$ is called a semi-graphoid
whenever conditions (i - v) hold for every collection of disjoint sets
$A,B,C,D\subseteq V$:

  1. i.

triviality  $A\perp\mkern-9.0mu\perp\varnothing\mid C\;[\mkern
0.5mu\mathcal{O}\mkern 0.5mu]$;

  2. ii.

symmetry  $A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5mu\mathcal{O}\mkern
0.5mu]$ $\mkern 18.0mu\Rightarrow\mkern 18.0mu$ $B\perp\mkern-9.0mu\perp A\mid
C\;[\mkern 0.5mu\mathcal{O}\mkern 0.5mu]$;

  3. iii.

decomposition  $A\perp\mkern-9.0mu\perp BD\mid C\;[\mkern
0.5mu\mathcal{O}\mkern 0.5mu]$ $\mkern 18.0mu\Rightarrow\mkern 18.0mu$
$A\perp\mkern-9.0mu\perp D\mid C\;[\mkern 0.5mu\mathcal{O}\mkern 0.5mu]$;

  4. iv.

weak union  $A\perp\mkern-9.0mu\perp BD\mid C\;[\mkern 0.5mu\mathcal{O}\mkern
0.5mu]$$\mkern 18.0mu\Rightarrow\mkern 18.0mu$ $A\perp\mkern-9.0mu\perp B\mid
CD\;[\mkern 0.5mu\mathcal{O}\mkern 0.5mu]$;

  5. v.

contraction  $A\perp\mkern-9.0mu\perp B\mid CD\;[\mkern 0.5mu\mathcal{O}\mkern
0.5mu]$ and $A\perp\mkern-9.0mu\perp D\mid C\;[\mkern 0.5mu\mathcal{O}\mkern
0.5mu]$ $\mkern 18.0mu\Rightarrow\mkern 18.0mu$ $A\perp\mkern-9.0mu\perp
BD\mid C\;[\mkern 0.5mu\mathcal{O}\mkern 0.5mu]$.

Furthermore, $\mathcal{I}(\mathcal{O})$ is called a graphoid whenever
conditions (i - vi) hold for every collection of disjoint sets
$A,B,C,D\subseteq V$:

  1. vi.

intersection  $A\perp\mkern-9.0mu\perp B\mid CD\;[\mkern
0.5mu\mathcal{O}\mkern 0.5mu]$ and $A\perp\mkern-9.0mu\perp D\mid BC\;[\mkern
0.5mu\mathcal{O}\mkern 0.5mu]$ $\mkern 18.0mu\Rightarrow\mkern 18.0mu$
$A\perp\mkern-9.0mu\perp BD\mid C\;[\mkern 0.5mu\mathcal{O}\mkern 0.5mu]$.

Moreover, $\mathcal{I}(\mathcal{O})$ is called a compositional graphoid
whenever conditions (i - vii) hold for every collection of disjoint sets
$A,B,C,D\subseteq V$:

  1. vii.

composition  $A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5mu\mathcal{O}\mkern
0.5mu]$ and $A\perp\mkern-9.0mu\perp D\mid C\;[\mkern 0.5mu\mathcal{O}\mkern
0.5mu]$ $\mkern 18.0mu\Rightarrow\mkern 18.0mu$ $A\perp\mkern-9.0mu\perp
BD\mid C\;[\mkern 0.5mu\mathcal{O}\mkern 0.5mu]$.

###  2.5 Probabilistic Conditional Independence

Throughout this paper, we consider a collection of random variables $X$ on a
measurable space $(\mathsf{X},\mathcal{X})$ indexed by $V$, and a probability
measure $P:\mathcal{X}\rightarrow[0,1]$ having density
$f:\mathsf{X}\rightarrow[0,\infty)$ dominated by a $\sigma$-finite product
measure $\mu$. If for $P$-almost all $x_{BC}\in\mathsf{X}_{BC}$:

$P(X_{A}\in\Omega\mid X_{BC}=x_{BC})=P(X_{A}\in\Omega\mid X_{C}=x_{C})\mkern
18.0mu\text{for all}\;\Omega\in\mathcal{X}_{A}$

or, alternatively, for $\mu$-almost all $x\in\mathsf{X}$:

$f_{ABC}(x)f_{C}(x)=f_{AC}(x)f_{BC}(x),$

then we say $\langle A,B\mid C\rangle$ is represented in $P$ and write
$A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5muP\mkern 0.5mu]$. The
independence model induced by $P$ is denoted by $\mathcal{I}(P)$. Moreover,
the independence model induced by a probability measure is a semi-graphoid.

######  Proposition 2.3 (Studený, (2005)).

If $P$ is a probability measure, then $\mathcal{I}(P)$ is a semi-graphoid.

In this paper, we are interested in the ADMG models that describe positive
measures.

######  Definition (positive measure).

If probability measure $P$ has density $f:\mathsf{X}\rightarrow(0,\infty)$,
then $P$ is a positive measure.

Notably, any independence model induced by a positive measure is a graphoid.

######  Proposition 2.4 (Pearl, (1988)).

If $P$ is a positive measure, then $\mathcal{I}(P)$ is a graphoid.

###  2.6 Graphical Conditional Independence

Conditional independence in an ADMG is characterized by m-connecting paths and
the m-separation criterion, which naturally extend d-connecting paths and the
d-separation criterion from DAGs to ADMGs (Richardson and Spirtes,, 2002;
Richardson,, 2003).

######  Definition (m-connecting path).

If $\mathcal{G}=(V,E)$ is an ADMG and $\langle a,b\mid
C\rangle\in\mathcal{T}(V)$ such that a path $\pi$ exists between $a$ and $b$
where:

  1. i.

every non-collider on $\pi$ is not a member of $C$;

  2. ii.

every collider on $\pi$ is an ancestor of some $c\in C$;

then $\pi$ is an m-connecting path between $a$ and $b$ relative to $C$.

######  Definition (m-separation).

If $\mathcal{G}=(V,E)$ is an ADMG and $\langle A,B\mid
C\rangle\in\mathcal{T}(V)$ such that no m-connecting path exists between $a$
and $b$ relative to $C$ for all $a\in A$ and $b\in B$, then $A$ and $B$ are
m-separated by $C$.

Let $\mathcal{G}=(V,E)$ be an ADMG and $\langle A,B\mid
C\rangle\in\mathcal{T}(V)$. If $A$ and $B$ are m-separated by $C$, then we say
$\langle A,B\mid C\rangle$ is represented in $\mathcal{G}$ and write
$A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5mu\mathcal{G}\mkern 0.5mu]$. The
independence model induced by $\mathcal{G}$ is denoted
$\mathcal{I}(\mathcal{G})$. Moreover, the independence model induced by an
ADMG is a compositional graphoid.

######  Proposition 2.5 (Sadeghi and Lauritzen, (2014)).

If $\mathcal{G}$ is an ADMG, then $\mathcal{I}(\mathcal{G})$ is a
compositional graphoid.

Notably, multiple ADMGs can induce the same independence model. This
phenomenon is called Markov equivalence, and a complete set of Markov
equivalent ADMGs is called a Markov equivalence class (MEC).

####  2.6.1 Graphical Markov Properties

ADMGs and probability measures are linked by conditional independence using
the global Markov property.

######  Definition (global Markov property).

If $\mathcal{G}=(V,E)$ is an ADMG and $P$ is a probability measure where:

$A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5mu\mathcal{G}\mkern 0.5mu]\mkern
18.0mu\Rightarrow\mkern 18.0muA\perp\mkern-9.0mu\perp B\mid C\;[\mkern
0.5muP\mkern 0.5mu]\mkern 18.0mu\text{for all}\mkern 18.0mu\langle A,B\mid
C\rangle\in\mathcal{T}(V),$

or $\mathcal{I}(\mathcal{G})\subseteq\mathcal{I}(P)$, then $P$ satisfies the
global Markov property for $\mathcal{G}$.

However, many of the conditional independence statements characterized by the
global Markov property are redundant—implied by the semi-graphoid axioms.
Accordingly, the global Markov property can be simplified to a more succinct
property using a consistent order and a few additional concepts. Let
$\mathcal{G}=(V,E)$ be an ADMG. If $b\in V$, then:

$\textup{mb}_{\mathcal{G}}(b)\equiv\textup{col}_{\mathcal{G}}(b)\setminus
b\mkern 72.0mu\textup{cl}_{\mathcal{G}}(b)\equiv\textup{col}_{\mathcal{G}}(b)$

are the Markov boundary and closure of $b$, respectively. Together, they have
the following property.

######  Proposition 2.6.

Let $\mathcal{G}=(V,E)$ be an ADMG. If $b\in V$, then:

$b\perp\mkern-9.0mu\perp
V\setminus\textup{cl}_{\mathcal{G}}(b)\mid\textup{mb}_{\mathcal{G}}(b)\;[\mkern
0.5mu\mathcal{G}\mkern 0.5mu].$

In other words, $\textup{mb}_{\mathcal{G}}(b)$ renders $b$ independent of the
vertices not in $\textup{cl}_{\mathcal{G}}(b)$. Moreover, these sets are the
smallest sets with this property and lead directly to the ordered local Markov
property.

######  Definition (ordered local Markov property).

Let $\mathcal{G}=(V,E)$ be an ADMG with consistent order $\leq$. If $P$ is a
probability measure where:

$b\perp\mkern-9.0mu\perp
A\setminus\textup{cl}_{\mathcal{G}_{A}}(b)\mid\textup{mb}_{\mathcal{G}_{A}}(b)\;[\mkern
0.5muP\mkern 0.5mu]\mkern 18.0mu\text{for all}\mkern
18.0muA\in\mathcal{A}(\mathcal{G})\;\text{and}\;b=\lceil A\rceil_{\leq},$

then $P$ satisfies the ordered local Markov property for $\mathcal{G}$ and
$\leq$.

Auspiciously, the global and ordered local Markov properties are equivalent.

######  Theorem 2.1 (Richardson, (2003)).

If $\mathcal{G}=(V,E)$ is an ADMG with consistent order $\leq$ and $P$ is a
probability measure, then the following are equivalent:

  1. i.

$P$ satisfies the global Markov property for $\mathcal{G}$;

  2. ii.

$P$ satisfies the ordered local Markov property for $\mathcal{G}$ and $\leq$.

####  2.6.2 Factorization

The global Markov property for DAGs can be characterized by a well-known
recursive factorization that encodes the independence statements represented
in a DAG algebraically. If $\mathcal{G}=(V,E)$ is a DAG and $P$ is a
probability measure, then the following are equivalent:

  1. i.

$f(x)=\prod_{v\in V}f_{v\mid\textup{pa}_{\mathcal{G}}(v)}(x)\mkern 18.0mu$ for
$\mu$-almost all $x\in\mathcal{X}$;

  2. ii.

$A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5mu\mathcal{G}\mkern 0.5mu]\mkern
18.0mu\Rightarrow\mkern 18.0muA\perp\mkern-9.0mu\perp B\mid C\;[\mkern
0.5muP\mkern 0.5mu]\mkern 18.0mu$ for all $\langle A,B\mid
C\rangle\in\mathcal{T}(V)$.

Richardson, (2009) developed a similar factorization for ADMGs, however, in
order to state his factorization, we first must review a few additional
concepts. At a high level, Richardson’s factorization utilizes a function to
partition the variables into sets called heads. The heads are then used to
construct one or more equations. In these equations marginal densities over
ancestral sets are set equal to the products of conditional densities of heads
conditioned on accompanying sets called tails.

######  Definition (head).

Let $\mathcal{G}=(V,E)$ be an ADMG and $H\subseteq V$ $(H\neq\varnothing)$. If
$H=\textup{bar}_{\mathcal{G}}(C)$ for some $C\in\mathcal{C}(\mathcal{G})$,
then $H$ is a head. In other words, $H$ is the barren subset of a (non-empty)
collider-connecting set. The set of all heads is defined:

$\mathcal{H}(\mathcal{G})\equiv\\{\textup{bar}_{\mathcal{G}}(C)\;:\;C\in\mathcal{C}(\mathcal{G})\\}\setminus\varnothing$

######  Definition (tail).

Let $\mathcal{G}=(V,E)$ be an ADMG and $H\in\mathcal{H}(\mathcal{G})$. If
$A=\textup{an}_{\mathcal{G}}(H)$, then the tail of $H$ is defined:

$\textup{tail}_{\mathcal{G}}(H)\equiv\textup{col}_{\mathcal{G}_{A}}(H)\setminus
H.$

In other words, the tail of $H$ contains the nontrivial collider-connecting
vertices of $H$ connected by ancestors of $H$.

In order to define the function that will partition the variables into heads,
we need to define a new partial order. For the remainder of this section, let
$\mathcal{G}=(V,E)$ be an ADMG and $\leq$ be the partial order:

$A\leq B\mkern 18.0mu\Leftrightarrow\mkern
18.0muA\subseteq\textup{an}_{\mathcal{G}}(B)\mkern 18.0mu\text{for all}\mkern
18.0muA,B\in\mathcal{H}(\mathcal{G}).$

The heads $\mathcal{H}(V)$ partition $V$ with the help of two functions:
$\Phi_{\mathcal{G}}:\mathcal{P}(V)\rightarrow\mathcal{P}(\mathcal{H}(\mathcal{G}))$
and $\Psi_{\mathcal{G}}:\mathcal{P}(V)\rightarrow\mathcal{P}(V)$. For
$S\subseteq V$:

$\displaystyle\Phi_{\mathcal{G}}(S)$
$\displaystyle\equiv\lceil\\{H\in\mathcal{H}(\mathcal{G})\;:\;H\subseteq
S\\}\rceil_{\leq};$ $\displaystyle\Psi_{\mathcal{G}}(S)$ $\displaystyle\equiv
S\setminus\bigcup_{T\in\Phi_{\mathcal{G}}(S)}T.$

In other words, $\Phi_{\mathcal{G}}(S)$ returns the maximal heads contained in
$S$ and $\Psi_{\mathcal{G}}(S)$ returns the variables in $S$ not contained
within a set in $\Phi_{\mathcal{G}}(S)$. The partition function
$[\,\cdot\,]_{\mathcal{G}}:\mathcal{P}(V)\rightarrow\mathcal{P}(\mathcal{H}(\mathcal{G}))$
is defined recursively:

$[\,S\,]_{\mathcal{G}}\equiv\begin{cases}\mkern 18.0mu\varnothing\mkern
36.0mu&S=\varnothing;\\\ \mkern
18.0mu\Phi_{\mathcal{G}}(S)\cup[\Psi(S)]_{\mathcal{G}}\mkern
36.0mu&S\neq\varnothing.\end{cases}$

In other words, the partition function returns the maximal head sets contained
in $S$ and is then reapplied to the remaining variables.

######  Theorem 2.2 (Richardson, (2009)).

Let $\mathcal{G}=(V,E)$ be an ADMG and $P$ be a probability measure. The
following are equivalent:

  1. i.

$f_{A}(x)=\prod_{H\in[A]_{\mathcal{G}}}f_{H\mid T}(x)\mkern 18.0mu$ for all
$A\in\mathcal{A}(\mathcal{G})$ and $\mu$-almost all $x\in\mathcal{X}$;

  2. ii.

$A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5mu\mathcal{G}\mkern 0.5mu]\mkern
18.0mu\Rightarrow\mkern 18.0muA\perp\mkern-9.0mu\perp B\mid C\;[\mkern
0.5muP\mkern 0.5mu]\mkern 18.0mu$ for all $\langle A,B\mid
C\rangle\in\mathcal{T}(V)$.

H | $\\{a\\}$ | $\\{b\\}$ | $\\{c\\}$ | $\\{d\\}$
---|---|---|---|---
T | $\varnothing$ | $\\{a\\}$ | $\\{b\\}$ | $\\{a,b,c\\}$

Figure 7: The heads and tails of the ADMG in Figure 1 (ii) and the Hasse
diagram for the corresponding poset over the heads.

Figure 7 illustrates the heads and tails of the ADMG in Figure 1 (ii) and the
corresponding poset over the heads. The only ancestral set that admits a non-
redundant factorization is, $\\{a,b,c,d\\}$ which partitions the variables
into the following heads:

$\displaystyle[\,\\{a,b,c,d\\}\,]_{\mathcal{G}}$
$\displaystyle=\Phi_{\mathcal{G}}(\\{a,b,c,d\\})\cup[\,\Psi(\\{a,b,c,d\\})\,]_{\mathcal{G}}$
$\displaystyle=\\{\\{d\\}\\}\cup[\,\\{a,b,c\\}\,]_{\mathcal{G}}$
$\displaystyle=\\{\\{d\\}\\}\cup\Phi_{\mathcal{G}}(\\{a,b,c\\})\cup[\,\Psi(\\{a,b,c\\})\,]_{\mathcal{G}}$
$\displaystyle=\\{\\{d\\}\\}\cup\\{\\{c\\}\\}\cup[\,\\{a,b\\}\,]_{\mathcal{G}}$
$\displaystyle=\\{\\{d\\},\\{c\\}\\}\cup\Phi_{\mathcal{G}}(\\{a,b\\})\cup[\,\Psi(\\{a,b\\})\,]_{\mathcal{G}}$
$\displaystyle=\\{\\{d\\},\\{c\\}\\}\cup\\{\\{b\\}\\}\cup[\,\\{a\\}\,]_{\mathcal{G}}$
$\displaystyle=\\{\\{d\\},\\{c\\},\\{b\\}\\}\cup\Phi_{\mathcal{G}}(\\{a\\})\cup[\,\Psi(\\{a\\})\,]_{\mathcal{G}}$
$\displaystyle=\\{\\{d\\},\\{c\\},\\{b\\}\\}\cup\\{\\{a\\}\\}\cup[\,\varnothing\,]_{\mathcal{G}}$
$\displaystyle=\\{\\{d\\},\\{c\\},\\{b\\},\\{a\\}\\}.$

Accordingly, a probability measure satisfies the global Markov property with
respect to $\mathcal{G}$ if and only if the following factorization holds for
$\mu$-almost all $x\in\mathcal{X}$:

$f_{abcd}(x)=f_{d\mid abc}(x)\,f_{c\mid b}(x)\,f_{b\mid a}(x)\,f_{a}(x).$

H | $\\{a\\}$ | $\\{b\\}$ | $\\{c\\}$ | $\\{d\\}$ | $\\{a,d\\}$ | $\\{b,c\\}$
---|---|---|---|---|---|---
T | $\varnothing$ | $\varnothing$ | $\\{a\\}$ | $\\{b\\}$ | $\\{b\\}$ | $\\{a\\}$

Figure 8: The heads and tails of the ADMG in Figure 2 and the Hasse diagram
for the corresponding poset over the heads.

Figure 8 illustrates the heads and tails of the ADMG in Figure 2 and the
corresponding poset over the heads. The only ancestral sets that admit non-
redundant factorizations are $\\{a,b,c,d\\}$ and $\\{a,b\\}$ which partition
the variables into the following heads:

$\displaystyle[\,\\{a,b,c,d\\}\,]_{\mathcal{G}}$
$\displaystyle=\Phi_{\mathcal{G}}(\\{a,b,c,d\\})\cup[\,\Psi(\\{a,b,c,d\\})\,]_{\mathcal{G}}$
$\displaystyle=\\{\\{a,d\\},\\{b,c\\}\\}\cup[\,\varnothing\,]_{\mathcal{G}}$
$\displaystyle=\\{\\{a,d\\},\\{b,c\\}\\}\textup{;}$
$\displaystyle[\,\\{a,b\\}\,]_{\mathcal{G}}$
$\displaystyle=\Phi_{\mathcal{G}}(\\{a,b\\})\cup[\,\Psi(\\{a,b\\})\,]_{\mathcal{G}}$
$\displaystyle=\\{\\{a\\},\\{b\\}\\}\cup[\,\varnothing\,]_{\mathcal{G}}$
$\displaystyle=\\{\\{a\\},\\{b\\}\\}.$

Accordingly, a probability measure satisfies the global Markov property with
respect to $\mathcal{G}$ if and only if the following factorizations hold for
$\mu$-almost all $x\in\mathcal{X}$:

$\displaystyle f_{abcd}(x)$ $\displaystyle=f_{ad\mid b}(x)\,f_{bc\mid
a}(x)\textup{;}$ $\displaystyle f_{ab}(x)$ $\displaystyle=f_{a}(x)\,f_{b}(x).$

When the probability measure is positive, both Richardson’s factorization and
the m-connecting factorization proposed in this paper are equivalent to the
global Markov property and therefore equivalent to each other. The key
difference is that the factorization characterized by Richardson may require
multiple equations, while the m-connecting factorization only requires a
single equation, which makes it ideal for formulating a scoring criterion; see
Section 4.

###  2.7 Integer-valued Multisets

######  Definition (integer-valued multiset).

An integer-valued multiset, imset for short, is an integer-valued function
$u$: $\mathcal{P}(V)\rightarrow\mathbb{Z}$. Alternatively, $u$ is an element
of $\mathbb{Z}^{\mathcal{P}(V)}$.

A simple example of an imset is the identifier. The identifier for a set
$A\subseteq V$ is defined:

$\delta_{A}(S)\equiv\begin{cases}\mkern 18.0mu1&\mkern 36.0muS=A;\\\ \mkern
18.0mu0&\mkern 36.0muS\neq A.\end{cases}$

More generally, the identifier for a set of sets
$\mathsf{A}\subseteq\mathcal{P}(V)$ is defined:

$\delta_{\mathsf{A}}(S)\equiv\begin{cases}\mkern 18.0mu1&\mkern
36.0muS\in\mathsf{A};\\\ \mkern 18.0mu0&\mkern
36.0muS\not\in\mathsf{A}.\end{cases}$

The identifier imset may be used to construct elementary imsets which are the
fundamental building block of the imsetal representation of conditional
independence.

######  Definition (elementary imset).

If $\langle a,b\mid C\rangle\in\mathcal{T}(V)$, then the corresponding
elementary imset $u_{\langle a,b\mid
C\rangle}:\mathcal{P}(V)\rightarrow\mathbb{Z}$ is an imset defined:

$u_{\langle a,b\mid C\rangle}\equiv\delta_{ab\mkern
0.5muC}+\delta_{C}-\delta_{a\mkern 0.5muC}-\delta_{b\mkern 0.5muC}.$

$\blockarray{c@{\hskip 28.45274pt}rccccccccl}\block{c@{\hskip
28.45274pt}rccccccccl}S&\varnothing\\{a\\}\\{b\\}\\{c\\}\\{a,b\\}\\{a,c\\}\\{b,c\\}\\{a,b,c\\}\\\
\vspace{-5mm}\\\ u_{\langle a,b\mid c\rangle}(S)\Big{[}00010\hbox
to0.0pt{\hss$-$}1\hbox
to0.0pt{\hss$-$}11\\!\\!\\!\\!\\!\\!\\!\Big{]}^{\top}\\\ $ Figure 9: An
elementary imset: $u_{\langle a,b\mid c\rangle}$.

Figure 9 illustrates the elementary imset $u_{\langle a,b\mid c\rangle}$. The
structure of an elementary imset imitates the definition of probabilistic
conditional independence when the independent sets are singletons. This is not
a coincidence, in fact, elementary imsets were designed to represent
statements of conditional independence in this manner. Elementary imsets may
be used to construct other types of imsets, such as semi-elementary imsets and
structural imsets.

######  Definition (semi-elementary imset).

If $\langle A,B\mid C\rangle\in\mathcal{T}(V)$, then the corresponding semi-
elementary imset $u_{\langle A,B\mid
C\rangle}:\mathcal{P}(V)\rightarrow\mathbb{Z}$ is defined:

$u_{\langle A,B\mid
C\rangle}\equiv\delta_{ABC}+\delta_{C}-\delta_{AC}-\delta_{BC}.$

Semi-elementary imsets may be constructed as linear combinations of elementary
imsets with non-negative integer coefficients.

######  Proposition 2.7 (Studený, (2005)).

Every semi-elementary imset is a linear combination of elementary imsets with
non-negative integer coefficients.

Similarly, structural imsets may be constructed as linear combinations of
elementary imsets with non-negative rational coefficients.

######  Definition (structural imset).

If $u:\mathcal{P}(V)\rightarrow\mathbb{Z}$ is an imset where:

$u=\sum_{\langle a,b\mid C\rangle\in\mathcal{T}(V)}k_{a,b\mid C}\,u_{\langle
a,b\mid C\rangle}\mkern 18.0mu\text{for some}\;k_{a,b\mid
C}\in\mathbb{Q}^{+},$

then $u$ is a structural imset over $V$. Denote the set of all structural
imsets over $V$ by $\mathcal{S}(V)$.

Conditional independence in structural imsets may be characterized by
subtraction of semi-elementary imsets. If there exists $k\in\mathbb{Q}^{+}$
such that $u-k\,u_{\langle A,B\mid C\rangle}$ is a structural imset, then we
say $\langle A,B\mid C\rangle$ is represented in $u$ and write
$A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5muu\mkern 0.5mu]$. The
independence model induced by $u$ is denoted $\mathcal{I}(u)$. Moreover, the
independence models induced by structural imsets are semi-graphoids.

######  Proposition 2.8 (Studený, (2005)).

Let $u$ be an imset. If $u\in\mathcal{S}(V)$, then $\mathcal{I}(u)$ is a semi-
graphoid.

Studený, (2005) linked structural imsets and probability measures by defining
a factorization that uses the density of a probability measure to
algebraically imply the conditional independence statements represented in a
structural imset. Studený defined his factorization for probability measures
with finite multiinformation; see (Studený,, 2005). Below, we restate
Studený’s factorization for positive measures.

######  Theorem 2.3.

Let $u$ be an imset and $P$ be a positive measure. If $u\in\mathcal{S}(V)$,
then the following are equivalent:

  1. i.

$\prod\limits_{S\in\mathcal{P}(V)}f_{S}(x)^{u(S)}=1\mkern 18.0mu$ for
$\mu$-almost all $x\in\mathcal{X}$;

  2. ii.

$A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5muu\mkern 0.5mu]\mkern
18.0mu\Rightarrow\mkern 18.0muA\perp\mkern-9.0mu\perp B\mid C\;[\mkern
0.5muP\mkern 0.5mu]\mkern 18.0mu$ for all $\langle A,B\mid
C\rangle\in\mathcal{T}(V)$.

Developments to the imsetal representation of conditional independence have
been largely theoretical, except for in restricted scenarios, such as the
restriction to DAG independence models—indeed, several methods use imsets to
learn DAGs (Studený,, 2008; Studený and Cussens,, 2017; Studený and Haws,,
2014). Characteristic imsets are a recent innovation in the space of imsetal
independence models introduced by (Hemmecke et al.,, 2012) for representing
DAG independence models. In particular, for a DAG $\mathcal{G}=(V,E)$, the
Möbius inversion of a characteristic imset
$c_{\mathcal{G}}:\mathcal{P}(V)\rightarrow\\{0,1\\}$ yields a structural imset
that represents the same conditional independence statements as $\mathcal{G}$:

$u=\mu_{\mathsf{P}}\mkern 0.5mu(1-c_{\mathcal{G}})\mkern
18.0mu\Rightarrow\mkern
18.0muu\in\mathcal{S}(V)\;\text{and}\;\mathcal{I}(u)=\mathcal{I}(\mathcal{G}).$

Furthermore, the values of a characteristic imset may be read directly off of
a DAG.

######  Proposition 2.9.

Let $\mathcal{G}=(V,E)$ be a DAG and $S\subseteq V$ $(|S|\geq 2)$. If
$A=\textup{an}_{\mathcal{G}}(S)$ and $B=\textup{bar}_{\mathcal{G}}(S)$, then:

  1. i.

$c_{\mathcal{G}}(S)\in\\{0,1\\}$;

  2. ii.

$c_{\mathcal{G}}(S)=1\mkern 18.0mu\Leftrightarrow\mkern 18.0mu\text{there
exists}\;a\in S\;\text{such that}\;S\setminus
a\subseteq\textup{pa}_{\mathcal{G}}(a)$;

  3. iii.

$c_{\mathcal{G}}(S)=1\mkern 18.0mu\Leftrightarrow\mkern
18.0muS\subseteq\textup{col}_{\mathcal{G}_{A}}(B)$.

Properties (i) and (ii) were shown by Hemmecke et al., (2012). We add property
(iii) which is equivalent to property (ii) in order to compare the
characteristic imset to the m-connecting imset; see Section 3.

##  3 The m-connecting Imset

In this section, we introduce the m-connecting imset in order to construct a
factorization for ADMGs.

######  Definition (m-connecting imset).

If $\mathcal{G}=(V,E)$ is an ADMG, then the corresponding m-connecting imset
$m_{\mathcal{G}}:\mathcal{P}(V)\rightarrow\\{0,1\\}$ is defined:

$m_{\mathcal{G}}(S)\equiv\begin{cases}\mkern 18.0mu1&\mkern 36.0mu\\{\langle
a,b\mid C\rangle\in\mathcal{I}(\mathcal{G})\;:\;S\setminus
C=ab\\}=\varnothing;\\\ \mkern 18.0mu0&\mkern 36.0mu\\{\langle a,b\mid
C\rangle\in\mathcal{I}(\mathcal{G})\;:\;S\setminus
C=ab\\}\neq\varnothing.\end{cases}$

In other words, $m_{\mathcal{G}}(S)=1$ if and only if there exists an
m-connecting path between $a$ and $b$ relative to $C$ for all $\langle a,b\mid
C\rangle\in\mathcal{T}(V)$ where $S\setminus C=ab$.

The m-connecting imset naturally generalizes the characteristic imset in the
following sense:

######  Proposition 3.1.

Let $\mathcal{G}=(V,E)$ be an ADMG and $S\subseteq V$. If
$A=\textup{an}_{\mathcal{G}}(S)$ and $B=\textup{bar}_{\mathcal{G}}(S)$, then:

  1. i.

$m_{\mathcal{G}}(S)\in\\{0,1\\}$;

  2. ii.

$m_{\mathcal{G}}(S)=1\mkern 18.0mu\Leftrightarrow\mkern
18.0muS\subseteq\textup{col}_{\mathcal{G}_{A}}(B)$.

The (non-empty) sets for which the m-connecting imset is 1 are called
parameterizing sets and have been used to parameterize ADMG models (Evans and
Richardson,, 2014), characterize margins of discrete DAG models (Evans, 2018a,
), and to test the equivalence of ADMG independence models (Hu and Evans,,
2020).

######  Definition (parameterizing sets).

If $\mathcal{G}=(V,E)$ is an ADMG, then the parametrizing sets are defined:

$\mathcal{M}(\mathcal{G})\equiv\\{HT\in\mathcal{P}(V)\;:\;H\in\mathcal{H}(\mathcal{G})\;\text{and}\;T\subseteq\textup{tail}_{\mathcal{G}}(H)\\}$

Our choice of notation stresses that the members of these sets are connected
by m-connecting paths—this notion is made rigorous by Hu and Evans, (2020).

######  Proposition 3.2 (Hu and Evans, (2020)).

If $\mathcal{G}=(V,E)$ is an ADMG, then $M\in\mathcal{M}(\mathcal{G})$ if and
only if there exists an m-connecting path between $a$ and $b$ relative to $C$
for all $\langle a,b\mid C\rangle\in\mathcal{T}(V)$ where $M\setminus C=ab$.

Similarly, we define the non-m-connecting imset.

######  Definition (non-m-connecting imset).

If $\mathcal{G}=(V,E)$ is an ADMG, then the corresponding non-m-connecting
imset $n_{\mathcal{G}}:\mathcal{P}(V)\rightarrow\\{0,1\\}$ is defined:

$n_{\mathcal{G}}(S)\equiv\begin{cases}\mkern 18.0mu1&\mkern 36.0mu\\{\langle
a,b\mid C\rangle\in\mathcal{I}(\mathcal{G})\;:\;S\setminus
C=ab\\}\neq\varnothing;\\\ \mkern 18.0mu0&\mkern 36.0mu\\{\langle a,b\mid
C\rangle\in\mathcal{I}(\mathcal{G})\;:\;S\setminus
C=ab\\}=\varnothing.\end{cases}$

The sets for which the non-m-connecting imset is 1 are called constrained sets
(Evans, 2018a, ). Notably, some members of these sets are not connected by any
m-connecting paths. Accordingly, we denote the set of all constrained sets:

$\mathcal{N}(\mathcal{G})\equiv\mathcal{P}(V)\setminus[\mathcal{M}(\mathcal{G})\cup\\{\varnothing\\}].$

Figure 10: Several ADMGs and their parameterizing sets.

Figure 10 illustrates several ADMGs and their parameterizing sets.

###  3.1 Probabilistic Terms

To facilitate the forthcoming discussion, we define several new terms. We
define a function $\phi_{A}:\mathcal{X}_{A}\rightarrow\mathbb{R}$ as a linear
combination of log density terms motivated by the Möbius inversion:

$\log f_{A}(x)=\sum_{B\subseteq A}\phi_{B}(x)\mkern
72.0mu\phi_{A}(x)=\sum_{B\subseteq A}(-1)^{|A\setminus B|}\log f_{B}(x)\\\ .$

Defining functional vectors
$h_{\mathsf{P}}(x):\mathcal{P}(V)\rightarrow\mathbb{R}^{|\mathcal{P}(V)|}$ and
$\phi_{\mathsf{P}}(x):\mathcal{P}(V)\rightarrow\mathbb{R}^{|\mathcal{P}(V)|}$:

$\underset{S\in\mathcal{P}(V)}{[h_{\mathsf{P}}(x)]_{S}}\equiv\log
f_{S}(x)\mkern
72.0mu\underset{S\in\mathcal{P}(V)}{[\phi_{\mathsf{P}}(x)]_{S}}\equiv\phi_{S}(x),$

we equivalently have:

$h_{\mathsf{P}}=\zeta_{\mathsf{P}}^{\top}\phi_{\mathsf{P}}(x)\mkern
72.0mu\phi_{\mathsf{P}}(x)=\mu_{\mathsf{P}}^{\top}h_{\mathsf{P}}(x).$

We accept the convention $\phi_{\varnothing}(x)=0$ for all $x\in\mathcal{X}$.
The expectation of $\phi_{A}(x)$ with respect to $P$ has been previously
studied in the field of information theory by several researchers, including
McGill, (1954), who coined the term interaction information. Accordingly, we
call $\phi_{A}(x)$ the interaction information rate.

We define the following shorthand for indicators of sets of sets and their
corresponding $\phi$ terms. Let $A,B\subseteq V$ $(A\neq\varnothing)$ be
disjoint sets:

$\delta_{A\mid B}\equiv\sum_{\begin{subarray}{c}S\subseteq AB\\\ A\subseteq
S\end{subarray}}\delta_{S}\mkern 72.0mu\phi_{A\mid
B}(x)\equiv\sum_{\begin{subarray}{c}S\subseteq AB\\\ A\subseteq
S\end{subarray}}\phi_{S}(x).$

Similar to above, we call $\phi_{A\mid B}(x)$ the conditional interaction
information rate. Another case is when the set of sets corresponds to a semi-
elementary imset transformed by the Möbius inversion. Let $A,B,C\subseteq V$
$(AB\neq\varnothing)$ be disjoint sets:

$\delta_{A,B\mid C}\equiv\sum_{\begin{subarray}{c}S\subseteq ABC\\\
S\not\subseteq AC\\\ S\not\subseteq BC\end{subarray}}\delta_{S}\mkern
72.0mu\phi_{A,B\mid C}(x)\equiv\sum_{\begin{subarray}{c}S\subseteq ABC\\\
S\not\subseteq AC\\\ S\not\subseteq BC\end{subarray}}\phi_{S}(x).$

The expectation of $\phi_{A,B\mid C}(x)$ with respect to $P$ is the well-known
information theoretic concept of conditional mutual information. Accordingly,
we call $\phi_{A,B\mid C}(x)$ the mutual information rate. The conditional
mutual information rate and its corresponding imset have the following
properties.

######  Proposition 3.3.

Let $P$ be a positive measure:

  1. i.

$\displaystyle\phi_{A\mid B}(x)=\sum_{\begin{subarray}{c}T\subseteq AB\\\
B\subseteq T\end{subarray}}(-1)^{|AB\setminus T|}\log f_{T}(x)$;

  2. ii.

$\displaystyle\phi_{A,B\mid
C}(x)=\log\frac{f_{ABC}(x)f_{C}(x)}{f_{AC}(x)f_{BC}(x)}$;

  3. iii.

$u_{\langle A,B\mid C\rangle}=\mu_{\mathsf{P}}\mkern 0.5mu\delta_{A,B\mid C}$;

  4. iv.

$A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5muP\mkern 0.5mu]\mkern
18.0mu\Leftrightarrow\mkern 18.0mu\phi_{A,B\mid C}(x)=0\mkern 18.0mu\text{for
$\mu$-almost all}\;x\in\mathcal{X}$.

###  3.2 The m-connecting Factorization

In this section, we provide two versions of the m-connecting factorization.
First we give a version of the m-connecting factorization that holds for ADMGs
with bounded parameterizing set cardinality.

######  Theorem 3.1.

Let $\mathcal{G}=(V,E)$ be an ADMG. If $P$ is a positive measure and $|M|\leq
5$ for all $M\in\mathcal{M}(\mathcal{G})$, then the following are equivalent:

  1. i.

$\log f(x)=\sum\limits_{M\in\mathcal{M}(\mathcal{G})}\phi_{M}(x)\mkern 18.0mu$
for $\mu$-almost all $x\in\mathcal{X}$;

  2. ii.

$A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5mu\mathcal{G}\mkern 0.5mu]$
$\mkern 18.0mu\Rightarrow\mkern 18.0mu$ $A\perp\mkern-9.0mu\perp B\mid
C\;[\mkern 0.5muP\mkern 0.5mu]$ for every $\langle A,B\mid
C\rangle\in\mathcal{T}(V)$.

Alternatively, the summation over the parameterizing sets may be computed with
heads and tails. Let $\mathcal{G}=(V,E)$ be an ADMG with consistent order
$\leq$. If $R=\textup{pre}^{\leq}_{\mathcal{G}}(v)$ and
$T=\textup{tail}_{\mathcal{G}}(H)$ where context clarifies $v\in V$ and
$H\in\mathcal{H}(\mathcal{G})$, then:

$\displaystyle\sum_{M\in\mathcal{M}(\mathcal{G})}\phi_{M}(x)$
$\displaystyle=\sum_{H\in\mathcal{H}(\mathcal{G})}\phi_{H\mid T}(x)$
$\displaystyle=\sum_{H\in\mathcal{H}(\mathcal{G})}\sum_{S\subseteq
H}(-1)^{|H\setminus S|}\log f_{ST}(x)$ $\displaystyle=\sum_{v\in
V}\sum_{\begin{subarray}{c}H\in\mathcal{H}(\mathcal{G}_{R})\\\ v\in
H\end{subarray}}\sum_{\begin{subarray}{c}S\subseteq H\\\ v\not\in
S\end{subarray}}(-1)^{|H\setminus S|-1}\log f_{v\mid ST}(x).$

Using the alternative stated above, we derive the m-connecting factorizations
for several ADMGs with respect to total orders given by the order of the
density terms. A positive measure satisfies the global Markov property with
respect to an ADMG if and only if the corresponding factorization holds for
$\mu$-almost all $x\in\mathcal{X}$:

$\displaystyle\text{Fig. \ref{fig:dag_admg} ({ii}):}\mkern 18.0mu\log f(x)$
$\displaystyle=\log f_{d\mid abc}(x)+\log f_{c\mid b}(x)+\log f_{b\mid
a}(x)+\log f_{a}(x);$ $\displaystyle\text{Fig. \ref{fig:set_ex}:}\mkern
18.0mu\log f(x)$ $\displaystyle=\log f_{d\mid ab}(x)+\log f_{c\mid ab}(x)+\log
f_{b}(x)+\log f_{a}(x);$ $\displaystyle\text{Fig. \ref{fig:mcs} ({i}):}\mkern
18.0mu\log f(x)$ $\displaystyle=\log f_{c\mid b}(x)+\log f_{b\mid a}(x)+\log
f_{a}(x);$ $\displaystyle\text{Fig. \ref{fig:mcs} ({ii}):}\mkern 18.0mu\log
f(x)$ $\displaystyle=\log f_{b\mid ac}(x)+\log f_{c}(x)+\log f_{a}(x);$
$\displaystyle\text{Fig. \ref{fig:mcs} ({iii}):}\mkern 18.0mu\log f(x)$
$\displaystyle=\log\left[f_{c\mid abd}(x)\frac{f_{c\mid d}(x)}{f_{c\mid
ad}(x)}\right]+\log f_{b\mid a}(x)+\log f_{d}(x)+\log f_{a}(x);$
$\displaystyle\text{Fig. \ref{fig:mcs} ({iv}):}\mkern 18.0mu\log f(x)$
$\displaystyle=\log\left[f_{d\mid abc}(x)\frac{f_{d\mid b}(x)}{f_{d\mid
ab}(x)}\right]+\log f_{b\mid ac}(x)+\log f_{c}(x)+\log f_{a}(x);$
$\displaystyle\text{Fig. \ref{fig:mcs} ({v}):}\mkern 18.0mu\log f(x)$
$\displaystyle=\log\left[f_{d\mid abc}(x)\frac{f_{d}(x)}{f_{d\mid
a}(x)}\right]+\log\left[f_{c\mid ab}(x)\frac{f_{c}(x)}{f_{c\mid
b}(x)}\right]+\log f_{b\mid a}(x)+\log f_{a}(x).$

The m-connecting factorization resembles the well-known recursive
factorization for DAGs. Vertices in the density terms are conditioned on their
Markov boundaries in the subgraph induced by their preceding vertices.
Additionally, if a density term implies extraneous dependencies, then the term
is reweighted by a ratio equaling 1 if and only if the extra dependencies are
false in the probability measure.

The proof strategy for Theorem 3.1 splits the log density of a positive
measure into m-connecting and non-m-connecting pieces using the Möbius
inversion (Proposition 2.2):

$\displaystyle\log f(x)$
$\displaystyle=\phi_{\mathsf{P}}(x)^{\top}\delta_{\mathcal{P}(V)}$
$\displaystyle=\phi_{\mathsf{P}}(x)^{\top}(m_{\mathcal{G}}+n_{\mathcal{G}})$
$\displaystyle=\sum\limits_{M\in\mathcal{M}(\mathcal{G})}\phi_{M}(x)+\phi_{\mathsf{P}}(x)^{\top}n_{\mathcal{G}}.$

Notably, $\mu_{\mathsf{P}}\mkern 0.5mun_{\mathcal{G}}$ is a structural imset
if $|M|\leq 5$ for all $M\in\mathcal{M}(\mathcal{G})$.

######  Proposition 3.4.

Let $\mathcal{G}=(V,E)$ be an ADMG. If $|M|\leq 5$ for all
$M\in\mathcal{M}(\mathcal{G})$, then $\mu_{\mathsf{P}}\mkern
0.5mun_{\mathcal{G}}\in\mathcal{S}(V)$.

It follows from Proposition 3.4 and Theorem 2.3 that:

$\mathcal{I}(\mu_{\mathsf{P}}\mkern
0.5mun_{\mathcal{G}})\subseteq\mathcal{I}(P)\mkern 18.0mu\Leftrightarrow\mkern
18.0mu\phi_{\mathsf{P}}(x)^{\top}n_{\mathcal{G}}=0\mkern
18.0mu\text{for}\;\mu\text{-almost all}\;x\in\mathcal{X}.$

Accordingly, we show:

$\mathcal{I}(\mathcal{G})\subseteq\mathcal{I}(\mu_{\mathsf{P}}\mkern
0.5mun_{\mathcal{G}}).$

However, it is not difficult to construct and ADMG $\mathcal{G}$ such that
$\mu_{\mathsf{P}}\mkern 0.5mun_{\mathcal{G}}$ is not a structural imset. A bi-
directed 6-cycle is an example; see Appendix B. When $\mu_{\mathsf{P}}\mkern
0.5mun_{\mathcal{G}}$ is not a structural imset, we use the principle of
inclusion-exclusion to decompose $\mu_{\mathsf{P}}\mkern 0.5mun_{\mathcal{G}}$
with respect to a consistent order $\leq$ into an inclusion structural imset
$\mu_{\mathsf{P}}\mkern 0.5mui_{\mathcal{G}}^{\leq}$ and an exclusion
structural imset $\mu_{\mathsf{P}}\mkern 0.5mue_{\mathcal{G}}^{\leq}$ such
that $n_{\mathcal{G}}=i_{\mathcal{G}}^{\leq}-e_{\mathcal{G}}^{\leq}$. The
exclusion imset is added to the factorization as an adjustment term which
gives:

$\mathcal{I}(\mu_{\mathsf{P}}\mkern
0.5mui_{\mathcal{G}}^{\leq})\subseteq\mathcal{I}(P)\mkern
18.0mu\Leftrightarrow\mkern
18.0mu\phi_{\mathsf{P}}(x)^{\top}i_{\mathcal{G}}^{\leq}=0\mkern
18.0mu\text{for}\;\mu\text{-almost all}\;x\in\mathcal{X}$

Accordingly, we show:

$\mathcal{I}(\mathcal{G})\subseteq\mathcal{I}(\mu_{\mathsf{P}}\mkern
0.5mui_{\mathcal{G}}^{\leq}).$

Next we introduce Algorithms 2 and 3 to facilitate the decomposition of the
$\mu_{\mathsf{P}}\mkern 0.5mun_{\mathcal{G}}$. Lemma 3.1 provides two useful
properties of parameterizing sets.

######  Lemma 3.1.

If $\mathcal{G}=(V,E)$ is an ADMG and $b\in\textup{bar}_{\mathcal{G}}(V)$ and
$A\in\mathcal{A}(\mathcal{G})$, then:

  1. i.

$|\lceil\\{M\in\mathcal{M}(\mathcal{G})\;:\;b\in M\\}\rceil|=1$;

  2. ii.

$\mathcal{M}(\mathcal{G}_{A})=\\{M\in\mathcal{P}(A)\;:\;M\in\mathcal{M}(\mathcal{G})\\}$.

The intuition for Lemma 3.2 is given by the ordered local Markov property.

######  Lemma 3.2.

Let $\mathcal{G}=(V,E)$ be an ADMG and $N\subseteq V$. If
$b\in\textup{bar}_{\mathcal{G}}(N)$ and
$M=\lceil\\{M\in\mathcal{M}(\mathcal{G})\;:\;b\in M\subseteq N\\}\rceil$,
then:

$b\perp\mkern-9.0mu\perp N\setminus M\mid M\setminus b\;[\mkern
0.5mu\mathcal{G}\mkern 0.5mu].$

Input: ADMG: $\mathcal{G}=(V,E)$, barren vertex:
$b\in\textup{bar}_{\mathcal{G}}(V)$

Output: ordered lists: $\mathsf{M}$, $\mathsf{N}$

1 Initialize ordered lists $\mathsf{M}=\langle\rangle$,
$\mathsf{N}=\langle\rangle$;

2 Let $\mathsf{R}=\\{N\in\mathcal{N}(\mathcal{G})\;:\;b\in N$ } ;

3 repeat

4 Pick $N\in\lceil\mathsf{R}\rceil$;

Let $M=\lceil\\{M\in\mathcal{M}(\mathcal{G})\;:\;b\in M\subseteq N\\}\rceil$ ;
// unique by Lemma 3.1

5 Append $M$ to $\mathsf{M}$ and $N$ to $\mathsf{N}$ ;

6 $\mathsf{R}=\mathsf{R}\setminus\\{S\in\mathsf{R}\;:\;b\in S\subseteq
N\;\text{and}\;S\not\subseteq M\\}$ ;

7

8until  _$\mathsf{R}=\varnothing$_ ;

Algorithm 2 $\textsc{Pairs}(\mathcal{G},b)$

Let $\mathcal{G}=(V,E)$ be an ADMG and $b\in\textup{bar}_{\mathcal{G}}(V)$.
Additionally, let $\mathsf{M},\mathsf{N}=\textsc{Pairs}(\mathcal{G},b)$ be
ordered lists of parameterizing and constrained sets, respectively:

$\mathsf{M}=\langle M_{1},\dots,M_{n}\rangle\mkern 72.0mu\mathsf{N}=\langle
N_{1},\dots,N_{n}\rangle$

where $n=|\mathsf{M}|$. Additionally, we define the universe of sets with
respect to $N_{i}$ and $b$:

$\mathsf{U}_{i}\equiv\bigcup_{\begin{subarray}{c}S\subseteq N_{i}\\\ b\in
S\end{subarray}}\\{S\\}.$

We simplify notation and use $\mathsf{N}_{i,i}$ to define the set of sets that
corresponds to the conditional independence statement $b\perp\mkern-9.0mu\perp
N_{i}\setminus M_{i}\mid M_{i}\setminus b\;[\mkern 0.5mu\mathcal{G}\mkern
0.5mu]$. We call terms of this form base conditional independence terms
because they will form the basis for the principle of inclusion-exclusion. Let
$A=b$, $B=N_{i}\setminus M_{i}$, and $C=M_{i}\setminus b$, then:

$\displaystyle ABC$ $\displaystyle=(N_{i}\setminus M_{i})\cup(M_{i}\setminus
b)\cup b$ $\displaystyle=N_{i}$ $\displaystyle AC$
$\displaystyle=(M_{i}\setminus b)\cup b$ $\displaystyle=M_{i}$ $\displaystyle
BC$ $\displaystyle=(N_{i}\setminus M_{i})\cup(M_{i}\setminus b)$
$\displaystyle=N_{i}\setminus b$

therefore

$\mathsf{N}_{i,i}\equiv\bigcup_{\begin{subarray}{c}S\in\mathsf{U}_{i}\\\
S\not\subseteq
M_{i}\end{subarray}}\\{S\\}=\bigcup_{\begin{subarray}{c}S\subseteq N_{i}\\\
b\in S\\\ S\not\subseteq
M_{i}\end{subarray}}\\{S\\}=\bigcup_{\begin{subarray}{c}S\subseteq ABC\\\
S\not\subseteq AC\\\ S\not\subseteq BC\end{subarray}}\\{S\\}$

and

$\delta_{\mathsf{N}_{i,i}}=\delta_{A,B\mid C}.$

Lemma 3.3 motivates application of the principle of inclusion-exclusion to the
base conditional independence terms.

######  Lemma 3.3.

Let $\mathcal{G}=(V,E)$ be an ADMG and $b\in\textup{bar}_{\mathcal{G}}(V)$. If
$\mathsf{M},\mathsf{N}=\textsc{Pairs}(\mathcal{G},b)$ where $|\mathsf{M}|=n$
and $\mathsf{R}=\\{N\in\mathcal{N}(\mathcal{G})\;:\;b\in N\\}$, then:

$\bigcup_{i=1}^{n}\mathsf{N}_{i,i}=\mathsf{R}.$

Accordingly, we cover all constrained sets using sets of sets that represent
conditional independence relations.

Next, we generalize our notation to intersections of the sets in $\mathsf{M}$
and $\mathsf{N}$:

$M_{K}\equiv\bigcap_{k\in K}M_{k}\mkern 36.0muN_{J}\equiv\bigcap_{j\in
J}N_{j}\mkern 36.0mu\mathsf{U}_{J}\equiv\bigcup_{\begin{subarray}{c}T\subseteq
N_{J}\\\ b\in T\end{subarray}}\\{T\\}\mkern 36.0muM_{J,K}\equiv M_{K}\cap
N_{J}.$

Similarly, we use $\mathsf{N}_{J,K}$ to define the set of sets that
corresponds to the conditional independence statement $b\perp\mkern-9.0mu\perp
N_{J}\setminus M_{J,K}\mid M_{J,K}\setminus b\;[\mkern 0.5mu\mathcal{G}\mkern
0.5mu]$. We call terms that fit this more general from conditional
independence terms. If $A=b$, $B=N_{J}\setminus M_{J,K}$, and
$C=M_{J,K}\setminus b$, then:

$\displaystyle ABC$ $\displaystyle=b\cup(N_{J}\setminus
M_{J,K})\cup(M_{J,K}\setminus b)$ $\displaystyle=N_{J}$ $\displaystyle AC$
$\displaystyle=b\cup(M_{J,K}\setminus b)$ $\displaystyle=M_{J,K}$
$\displaystyle BC$ $\displaystyle=(N_{J}\setminus
M_{J,K})\cup(M_{J,K}\setminus b)$ $\displaystyle=N_{J}\setminus b$

therefore

$\mathsf{N}_{J,K}\equiv\bigcup_{\begin{subarray}{c}S\in\mathsf{U}_{J}\\\
S\not\subseteq
M_{J,K}\end{subarray}}\\{S\\}=\bigcup_{\begin{subarray}{c}S\subseteq N_{J}\\\
S\not\subseteq M_{J,K}\\\ S\not\subseteq N_{J}\setminus
b\end{subarray}}\\{S\\}=\bigcup_{\begin{subarray}{c}S\subseteq ABC\\\
S\not\subseteq AC\\\ S\not\subseteq BC\end{subarray}}\\{S\\}$

and

$\delta_{\mathsf{N}_{J,K}}=\delta_{A,B\mid C}.$

Next we define Algorithm 3 and show that it decomposes the non-m-connecting
imsets into two structural imsets using the principle of inclusion
exclusion—the inclusion and exclusion imsets. Notably, there may be some
redundancy in the imsets constructed by Algorithm 3. In Appendix B.2 we
present a non-redundant version of Algorithm 3, however, we have not verified
that removing redundant terms does not change the induced independence model.

Input: ADMG: $\mathcal{G}=(V,E)$, total order: $\leq$

Output: imsets: $i_{\mathcal{G}}^{\leq}$, $e_{\mathcal{G}}^{\leq}$

1 Initialize imsets $i_{\mathcal{G}}^{\leq}:\mathcal{P}(V)\rightarrow 0$,
$e_{\mathcal{G}}^{\leq}:\mathcal{P}(V)\rightarrow 0$ ;

2 Let $A=V$ ;

3 repeat

4 Let $b=\lceil A\rceil_{\leq}$ and
$\mathsf{M},\mathsf{N}=\textsc{Pairs}(\mathcal{G}_{A},b)$ ;

5 foreach  _$J\subseteq\\{1,\dots,|\mathsf{M}|\\}$_ do

6 foreach  _$K\subseteq J$ where $K\neq\varnothing$_ do

7 if  _$|J\setminus K|$ is even_ then

8 $i_{\mathcal{G}}^{\leq}=i_{\mathcal{G}}^{\leq}+\delta_{\mathsf{N}_{J,K}}$ ;

9

10 else

11 $e_{\mathcal{G}}^{\leq}=e_{\mathcal{G}}^{\leq}+\delta_{\mathsf{N}_{J,K}}$ ;

12

13

14

15 Remove $b$ from $A$ ;

16

17until  _$A=\varnothing$_ ;

Algorithm 3 ${\textsc{Non-m-connecting imset via In/Ex-clusion
NIE}(\mathcal{G},\leq)}$

######  Proposition 3.5.

Let $\mathcal{G}=(V,E)$ be an ADMG with consistent order $\leq$. If
$i_{\mathcal{G}}^{\leq},e_{\mathcal{G}}^{\leq}=\textsc{NIE}(\mathcal{G},\leq)$
then:

  1. i.

$n_{\mathcal{G}}=i_{\mathcal{G}}^{\leq}-e_{\mathcal{G}}^{\leq}$;

  2. ii.

$\mu_{\mathsf{P}}\mkern 0.5mui_{\mathcal{G}}^{\leq},\mu_{\mathsf{P}}\mkern
0.5mue_{\mathcal{G}}^{\leq}\in\mathcal{S}(V)$.

In what follows, we provide an intuition for Proposition 3.5 with an
illustrative example of Algorithm 3. Figure 11 depicts an ADMG
$\mathcal{G}=(V,E)$, its parameterizing sets $\mathcal{M}(\mathcal{G})$, and
its constrained sets $\mathcal{N}(\mathcal{G})$. Consider the total order
$\leq$ over $V$ where $e\leq a\leq d\leq b\leq c$.

Figure 11: An ADMG with vertices $\\{a,b,c,d,e\\}$ and the corresponding
parameterizing and constrained sets for the ADMG.

Run $\textsc{Pairs}(\mathcal{G}_{abcde},c)$ to construct ordered lists
$\mathsf{N}=\langle\\{a,b,c,e\\},\\{a,c,d,e\\}\rangle$ and
$\mathsf{M}=\langle\\{a,b,c\\},\\{c,d,e\\}\rangle$.

Figure 12: A visualization of Pairs$(\mathcal{G}_{abcde},c)$ applied to the
ADMG in Figure 11 and the base elementary conditional independence terms. The
constrained sets are bold and shaded to denote membership of a base
conditional independence term.

The intersection terms are as follows—these terms correspond to intersections
over members of $\mathsf{N}$ and $\mathsf{M}$ indexed by the loops on lines 5
and 6 of Algorithm 3.

$\mathsf{N}$ and $\mathsf{M}$ Intersection Terms:

$\displaystyle N_{1}=\\{a,b,c,e\\}$ $\displaystyle M_{1}=\\{a,b,c\\}$
$\displaystyle N_{2}=\\{a,c,d,e\\}$ $\displaystyle M_{2}=\\{c,d,e\\}$
$\displaystyle N_{12}=\\{a,c,e\\}$ $\displaystyle M_{12}=\\{c\\}$

The conditional independence terms are as follows—these terms correspond to
those added on lines 8 and 10.

Conditional Independence Terms:

$\displaystyle\mathsf{N}_{1,1}=\\{N\in\mathcal{N}(\mathcal{G})\;;\quad\delta_{c,e\mid
ab}(N)=1\\}$
$\displaystyle\mathsf{N}_{2,2}=\\{N\in\mathcal{N}(\mathcal{G})\;;\quad\delta_{c,a\mid
cd}(N)=1\\}$
$\displaystyle\mathsf{N}_{12,1}=\\{N\in\mathcal{N}(\mathcal{G})\;;\quad\delta_{c,e\mid
a}(N)=1\\}$
$\displaystyle\mathsf{N}_{12,2}=\\{N\in\mathcal{N}(\mathcal{G})\;;\quad\delta_{c,a\mid
e}(N)=1\\}$
$\displaystyle\mathsf{N}_{12,12}=\\{N\in\mathcal{N}(\mathcal{G})\;;\quad\delta_{c,ae}(N)=1\\}$

The conditional independence terms are partitioned into inclusion and
exclusion terms as follows—the inclusion terms are on the left and correspond
to those added on line 8 and the exclusion terms are on the right and
correspond to those added on line 10.

Inclusion Terms:

$\displaystyle\mathsf{N}_{1,1}=\\{N\in\mathcal{N}(\mathcal{G})\;;\quad\delta_{c,e\mid
ab}(N)=1\\}$
$\displaystyle\mathsf{N}_{2,2}=\\{N\in\mathcal{N}(\mathcal{G})\;;\quad\delta_{c,a\mid
de}(N)=1\\}$
$\displaystyle\mathsf{N}_{12,12}=\\{N\in\mathcal{N}(\mathcal{G})\;;\quad\delta_{c,ae}(N)=1\\}$

Exclusion Terms:

$\displaystyle\mathsf{N}_{12,1}=\\{N\in\mathcal{N}(\mathcal{G})\;;\quad\delta_{c,e\mid
a}(N)=1\\}$
$\displaystyle\mathsf{N}_{12,2}=\\{N\in\mathcal{N}(\mathcal{G})\;;\quad\delta_{c,a\mid
e}(N)=1\\}$

The inclusion and exclusion imsets are updated accordingly:

$\displaystyle i_{\mathcal{G}}^{\leq}$
$\displaystyle=i_{\mathcal{G}}^{\leq}+\delta_{c,e\mid ab}\\!+\,\delta_{c,a\mid
de}\\!+\,\delta_{c,ae}$
$\displaystyle=i_{\mathcal{G}}^{\leq}+\left[\delta_{abce}+\delta_{ace}+\delta_{bce}+\delta_{ce}\right]+\left[\delta_{acde}+\delta_{acd}+\delta_{ace}+\delta_{ac}\right]+\left[\delta_{ace}+\delta_{ac}+\delta_{ce}\right]$
$\displaystyle e_{\mathcal{G}}^{\leq}$
$\displaystyle=e_{\mathcal{G}}^{\leq}+\delta_{c,e\mid a}\\!+\,\delta_{c,a\mid
e}$
$\displaystyle=e_{\mathcal{G}}^{\leq}+\left[\delta_{ace}+\delta_{ce}\right]+\left[\delta_{ace}+\delta_{ac}\right].$

The difference of $i_{\mathcal{G}}^{\leq}$ and $e_{\mathcal{G}}^{\leq}$ equals
1 for all constrained subsets of $\\{a,b,c,d,e\\}$ that contain $c$:

$i_{\mathcal{G}}^{\leq}(S)-e_{\mathcal{G}}^{\leq}(S)\equiv\begin{cases}\mkern
18.0mu1&\mkern 36.0muc\in S\in\mathcal{N}(\mathcal{G});\\\ \mkern
18.0mu0&\mkern 36.0muc\in S\not\in\mathcal{N}(\mathcal{G}).\end{cases}$

We encourage the reader to reference Figure 12 in order to verify this fact.

Run $\textsc{Pairs}(\mathcal{G}_{abde},b)$ to construct ordered lists
$\mathsf{N}=\langle\\{a,b,d,e\\}\rangle$ and
$\mathsf{M}=\langle\\{a,b\\}\rangle$.

Figure 13: A visualization of Pairs$(\mathcal{G}_{abde},b)$ applied to the
ADMG in Figure 11 and the corresponding conditional independence term. The
constrained sets are bold and shaded to denote membership of the conditional
independence term.

The intersection and inclusion terms are as follows—these terms correspond to
intersections over members of $\mathsf{N}$ and $\mathsf{M}$ indexed by the
loops on lines 5 and 6 of Algorithm 3 and the terms added on line 8.

$\mathsf{N}$ and $\mathsf{M}$ Intersection Terms:

Inclusion Terms:

$\displaystyle N_{1}=\\{a,b,d,e\\}$ $\displaystyle M_{1}=\\{a,b\\}$

$\displaystyle\mathsf{N}_{1,1}=\\{N\in\mathcal{N}(\mathcal{G})\;;\quad\delta_{b,de\mid
a}(N)=1\\}$

The inclusion imset is updated accordingly (no update is made to the exclusion
imset):

$\displaystyle i_{\mathcal{G}}^{\leq}$
$\displaystyle=i_{\mathcal{G}}^{\leq}+\delta_{b,de\mid a}$
$\displaystyle=i_{\mathcal{G}}^{\leq}+\left[\delta_{abde}+\delta_{abd}+\delta_{abe}+\delta_{bde}+\delta_{bd}+\delta_{be}\right]$

The difference of $i_{\mathcal{G}}^{\leq}$ and $e_{\mathcal{G}}^{\leq}$ equals
1 for all constrained subsets of $\\{a,b,d,e\\}$ that contain $b$:

$i_{\mathcal{G}}^{\leq}(S)-e_{\mathcal{G}}^{\leq}(S)\equiv\begin{cases}\mkern
18.0mu1&\mkern 36.0mub\in S\in\mathcal{N}(\mathcal{G});\\\ \mkern
18.0mu0&\mkern 36.0mub\in S\not\in\mathcal{N}(\mathcal{G}).\end{cases}$

We encourage the reader to reference Figure 13 in order to verify this fact.

Run $\textsc{Pairs}(\mathcal{G}_{ade},d)$ to construct ordered lists
$\mathsf{N}=\langle\\{a,d,e\\}\rangle$ and
$\mathsf{M}=\langle\\{d,e\\}\rangle$.

Figure 14: A visualization of Pairs$(\mathcal{G}_{ade},d)$ applied to the ADMG
in Figure 11 and the corresponding conditional independence term. The
constrained sets are bold and shaded to denote membership of the conditional
independence term.

The intersection and inclusion terms are as follows—these terms correspond to
intersections over members of $\mathsf{N}$ and $\mathsf{M}$ indexed by the
loops on lines 5 and 6 of Algorithm 3 and the terms added on line 8.

Intersection Terms:

Positive Conditional Terms:

$\displaystyle N_{1}=\\{a,d,e\\}$ $\displaystyle M_{1}=\\{d,e\\}$

$\displaystyle\mathsf{N}_{1,1}=\\{N\in\mathcal{N}(\mathcal{G})\;;\quad\delta_{d,a\mid
e}(N)=1\\}$

The inclusion imset is updated accordingly (no update is made to the exclusion
imset):

$\displaystyle i_{\mathcal{G}}^{\leq}$
$\displaystyle=i_{\mathcal{G}}^{\leq}+\delta_{d,a\mid e}$
$\displaystyle=i_{\mathcal{G}}^{\leq}+\left[\delta_{ade}+\delta_{ad}\right]$

The difference of $i_{\mathcal{G}}^{\leq}$ and $e_{\mathcal{G}}^{\leq}$ equals
1 for all constrained subsets of $\\{a,d,e\\}$ that contain $d$:

$i_{\mathcal{G}}^{\leq}(S)-e_{\mathcal{G}}^{\leq}(S)\equiv\begin{cases}\mkern
18.0mu1&\mkern 36.0mud\in S\in\mathcal{N}(\mathcal{G});\\\ \mkern
18.0mu0&\mkern 36.0mud\in S\not\in\mathcal{N}(\mathcal{G}).\end{cases}$

We encourage the reader to reference Figure 14 in order to verify this fact.

Run $\textsc{Pairs}(\mathcal{G}_{ae},a)$ to construct ordered lists
$\mathsf{N}=\langle\\{a,e\\}\rangle$ and $\mathsf{M}=\langle\\{a\\}\rangle$.

Figure 15: A visualization of Pairs$(\mathcal{G}_{ae},a)$ applied to the ADMG
in Figure 11 and the corresponding conditional independence term. The
constrained sets are bold and shaded to denote membership of the conditional
independence term.

The intersection and inclusion terms are as follows—these terms correspond to
intersections over members of $\mathsf{N}$ and $\mathsf{M}$ indexed by the
loops on lines 5 and 6 of Algorithm 3 and the terms added on line 8.

Intersection Terms:

Positive Conditional Terms:

$\displaystyle N_{1}=\\{a,e\\}$ $\displaystyle M_{1}=\\{a\\}$

$\displaystyle\mathsf{N}_{1,1}=\\{N\in\mathcal{N}(\mathcal{G})\;;\quad\delta_{a,e}(N)=1\\}$

The inclusion imset is updated accordingly (no update is made to the exclusion
imset):

$\displaystyle i_{\mathcal{G}}^{\leq}$
$\displaystyle=i_{\mathcal{G}}^{\leq}+\delta_{ae}$

The difference of $i_{\mathcal{G}}^{\leq}$ and $e_{\mathcal{G}}^{\leq}$ equals
1 for all constrained subsets of $\\{a,e\\}$ that contain $a$:

$i_{\mathcal{G}}^{\leq}(S)-e_{\mathcal{G}}^{\leq}(S)\equiv\begin{cases}\mkern
18.0mu1&\mkern 36.0mua\in S\in\mathcal{N}(\mathcal{G});\\\ \mkern
18.0mu0&\mkern 36.0mua\in S\not\in\mathcal{N}(\mathcal{G}).\end{cases}$

We encourage the reader to reference Figure 15 in order to verify this fact.

Run $\textsc{Pairs}(\mathcal{G}_{e},e)$ to construct ordered lists
$\mathsf{N}=\langle\rangle$ and $\mathsf{M}=\langle\rangle$.

Figure 16: A visualization of Pairs($\mathcal{G}_{e}$,e) applied to the ADMG
in Figure 11.

There are no intersection terms or updates to be made. Trivially, the
difference of $i_{\mathcal{G}}^{\leq}$ and $e_{\mathcal{G}}^{\leq}$ equals 1
for all constrained subsets of $\\{e\\}$ that contain $e$:

$i_{\mathcal{G}}^{\leq}(S)-e_{\mathcal{G}}^{\leq}(S)\equiv\begin{cases}\mkern
18.0mu1&\mkern 36.0mue\in S\in\mathcal{N}(\mathcal{G});\\\ \mkern
18.0mu0&\mkern 36.0mue\in S\not\in\mathcal{N}(\mathcal{G}).\end{cases}$

After all iterations of Algorithm 3:

$\displaystyle i_{\mathcal{G}}^{\leq}$ $\displaystyle=\delta_{c,e\mid
ab}\\!+\,\delta_{c,a\mid de}\\!+\,\delta_{c,ae}\\!+\,\delta_{b,de\mid
a}\\!+\,\delta_{d,a\mid e}\\!+\,\delta_{a,e}$
$\displaystyle=\left[\delta_{abce}+\delta_{ace}+\delta_{bce}+\delta_{ce}\right]+\left[\delta_{acde}+\delta_{acd}+\delta_{ace}+\delta_{ac}\right]+\left[\delta_{ace}+\delta_{ac}+\delta_{ce}\right]$
$\displaystyle e_{\mathcal{G}}^{\leq}$ $\displaystyle=\delta_{c,e\mid
a}\\!+\,\delta_{c,a\mid e}$
$\displaystyle=\left[\delta_{ace}+\delta_{ce}\right]+\left[\delta_{ace}+\delta_{ac}\right].$

Lastly, we apply the the Möbius inversion:

$\displaystyle\mu_{\mathsf{P}}\mkern 0.5mui_{\mathcal{G}}^{\leq}$
$\displaystyle=u_{\langle c,e\mid ab\rangle}+u_{\langle c,a\mid
de\rangle}+u_{\langle c,ae\rangle}+u_{\langle b,de\mid a\rangle}+u_{\langle
d,a\mid e\rangle}+u_{\langle a,e\rangle}$
$\displaystyle=\left[\delta_{abce}+\delta_{ab}-\delta_{abc}-\delta_{abe}\right]+\left[\delta_{acde}+\delta_{de}-\delta_{ade}-\delta_{cde}\right]+\left[\delta_{ace}-\delta_{ae}-\delta_{c}\right]$
$\displaystyle\quad+\left[\delta_{abde}+\delta_{a}-\delta_{ade}-\delta_{ab}\right]+\left[\delta_{ade}+\delta_{e}-\delta_{ae}+\delta_{de}\right]+\left[\delta_{ae}-\delta_{a}-\delta_{e}\right]$
$\displaystyle\mu_{\mathsf{P}}\mkern 0.5mue_{\mathcal{G}}^{\leq}$
$\displaystyle=u_{\langle c,e\mid a\rangle}+u_{\langle c,a\mid e\rangle}$
$\displaystyle=\left[\delta_{ace}+\delta_{a}-\delta_{ac}-\delta_{ae}\right]+\left[\delta_{ace}+\delta_{e}-\delta_{ae}-\delta_{ce}\right].$

Clearly $\mu_{\mathsf{P}}\mkern
0.5mui_{\mathcal{G}}^{\leq},\mu_{\mathsf{P}}\mkern
0.5mue_{\mathcal{G}}^{\leq}\in\mathcal{S}(V)$ and
$n_{\mathcal{G}}=i_{\mathcal{G}}^{\leq}-e_{\mathcal{G}}^{\leq}$.

Lemma 3.4 shows that for an ADMG $\mathcal{G}$ with consistent order $\leq$,
the independence statements represented in the structural imset
$\mu_{\mathsf{P}}\mkern 0.5mui_{\mathcal{G}}^{\leq}$ imply the independence
statements required by the ordered local Markov property.

######  Lemma 3.4.

Let $\mathcal{G}=(V,E)$ be an ADMG and $\leq$ be a total order consistent with
$\mathcal{G}$. If
$i_{\mathcal{G}}^{\leq},e_{\mathcal{G}}^{\leq}=\textsc{NIE}(\mathcal{G},\leq)$,
$A\in\mathcal{A}(\mathcal{G})$, and $b=\lceil A\rceil_{\leq}$, then:

$b\perp\mkern-9.0mu\perp
A\setminus\textup{cl}_{\mathcal{G}_{A}}(b)\mid\textup{mb}_{\mathcal{G}_{A}}(b)\;[\mkern
0.5mu\mu_{\mathsf{P}}\mkern 0.5mui_{\mathcal{G}}^{\leq}\mkern 0.5mu].$

Accordingly, we get the first of the following two results.

######  Proposition 3.6.

Let $\mathcal{G}=(V,E)$ be an ADMG, $\leq$ be a total order consistent with
$\mathcal{G}$. If
$i_{\mathcal{G}}^{\leq},e_{\mathcal{G}}^{\leq}=\textsc{NIE}(\mathcal{G},\leq)$,
then:

  1. i.

$\mathcal{I}(\mu_{\mathsf{P}}\mkern
0.5mui_{\mathcal{G}}^{\leq})=\mathcal{I}(\mathcal{G})$;

  2. ii.

$\mathcal{I}(\mu_{\mathsf{P}}\mkern
0.5mue_{\mathcal{G}}^{\leq})\subseteq\mathcal{I}(\mathcal{G})$.

######  Corollary 3.1.

If $\mathcal{G}$ be an ADMG with consistent order $\leq$, then:

  1. i.

$\mathcal{I}(\mathcal{G})\subseteq\mathcal{I}(P)\mkern
18.0mu\Leftrightarrow\mkern
18.0mu\phi_{\mathsf{P}}(x)^{\top}i_{\mathcal{G}}^{\leq}=0\mkern 18.0mu$ for
$\mu$-almost all $x\in\mathcal{X}$;

  2. ii.

$\mathcal{I}(\mathcal{G})\subseteq\mathcal{I}(P)\mkern 18.0mu\Rightarrow\mkern
18.0mu\phi_{\mathsf{P}}(x)^{\top}e_{\mathcal{G}}^{\leq}=0\mkern 18.0mu$ for
$\mu$-almost all $x\in\mathcal{X}$.

Combining all the results above, we now state the main theorem of this paper.

######  Theorem 3.2.

Let $\mathcal{G}=(V,E)$ be an ADMG with consistent order $\leq$. If $P$ is a
positive measure, then the following are equivalent:

  1. i.

$\log
f(x)=\sum\limits_{M\in\mathcal{M}(\mathcal{G})}\phi_{M}(x)-\phi_{\mathsf{P}}(x)^{\top}e_{\mathcal{G}}^{\leq}\mkern
18.0mu$ for $\mu$-almost all $x\in\mathcal{X}$;

  2. ii.

$A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5mu\mathcal{G}\mkern 0.5mu]$
$\mkern 18.0mu\Rightarrow\mkern 18.0mu$ $A\perp\mkern-9.0mu\perp B\mid
C\;[\mkern 0.5muP\mkern 0.5mu]$ for all $\langle A,B\mid
C\rangle\in\mathcal{T}(V)$.

Alternatively, the adjusted sum over the parameterizing sets may be computed
as an adjusted sum over conditional densities. Let $\mathcal{G}=(V,E)$ be an
ADMG with consistent order $\leq$. If $R=\textup{pre}^{\leq}_{\mathcal{G}}(b)$
where context clarifies $b\in V$, then:

$\displaystyle\sum\limits_{M\in\mathcal{M}(\mathcal{G})}\phi_{M}(x)-\phi_{\mathsf{P}}(x)^{\top}e_{\mathcal{G}}^{\leq}$
$\displaystyle=\sum_{S\in\mathcal{P}(V)}[m_{\mathcal{G}}(S)-e_{\mathcal{G}}^{\leq}(S)]\,\phi_{S}(x)$
$\displaystyle=\sum_{b\in
V}\sum_{\begin{subarray}{c}S\subseteq\textup{cl}_{\mathcal{G}_{R}}(b)\\\ b\in
S\end{subarray}}[1-i_{\mathcal{G}}^{\leq}(S)]\,\phi_{S}(x)$
$\displaystyle=\sum_{b\in V}\bigg{[}\log
f_{b\mid\textup{mb}_{\mathcal{G}_{R}}(b)}(x)-\sum_{\begin{subarray}{c}S\subseteq\textup{cl}_{\mathcal{G}_{R}}(b)\\\
b\in S\end{subarray}}i_{\mathcal{G}}^{\leq}(S)\,\phi_{S}(x)\bigg{]}.$

This alternative formulation of the m-connecting factorization in conjunction
with the notion of a dominating DAG gives a nice intuition.

######  Definition (dominating DAG).

Let $\mathcal{G}=(V,E)$ be an ADMG with consistent order $\leq$. If
$R=\textup{pre}^{\leq}_{\mathcal{G}}(b)$ where context clarifies $b\in V$,
then the corresponding dominating DAG is defined:

$\textup{dom}(\mathcal{G},\leq)\equiv(V,\\{(a,b)\in\mathcal{E}(V)\;:\;a\in\textup{mb}_{\mathcal{G}_{R}}(b)\\}).$

If $\mathcal{G}=(V,E)$ be an ADMG with consistent order $\leq$ and dominating
DAG $\mathcal{D}=\textup{dom}(\mathcal{G},\leq)$, then:

$\log f(x)=\sum_{b\in V}\bigg{[}\log
f_{b\mid\textup{pa}_{\mathcal{D}}(b)}(x)-\sum_{S\subseteq\textup{pa}_{\mathcal{D}}(b)}i_{\mathcal{G}}^{\leq}(bS)\,\phi_{bS}(x)\bigg{]}.$

Using this formulation, the m-connecting factorization becomes the well-known
recursive factorization for the dominating DAG with a few additional
conditional mutual information rate terms to adjust for any superfluous
dependencies induced by $\mathcal{D}$.

##  4 Consistent Scoring Criterion

In this section, we discuss an application of the m-connecting factorization.
In particular, we formulate a consistent scoring criterion with a closed-form
solution for many curved exponential families, such as Gaussian and
multinomial ADMG models. We investigate asymptotic properties of the score and
compare its ability to recover correct independence models against the well-
known FCI algorithm and two of its variants

######  Definition (exponential family).

An exponential family is a family of probability measures that admit densities
with respect to $\sigma$-finite measure $\mu$:

$f(x\mid\theta)=\exp\left[\theta^{\top}t(x)-\psi(\theta)\right]\mkern
18.0mu\textup{for all}\;\theta\in\Theta\;\textup{where}$

  * $\bullet$

$\Theta\equiv\\{\theta\in\mathbb{R}^{|t(x)|}\,:\,\int_{x\in\mathcal{X}}\exp\left[\theta^{\top}t(x)\right]\textup{d}\mu(x)<\infty\\}$
is the natural parameter space;

  * $\bullet$

$t(x)$ is the sufficient statistic;

  * $\bullet$

$\psi(\theta)\equiv\int_{x\in\mathcal{X}}\exp\left[\theta^{\top}t(x)\right]\textup{d}\mu(x)$
is the cumulant function.

Let $P_{\theta}$ denote a member of some curved exponential family
parameterized by $\theta$.

Let $\mathcal{G}=(V,E)$ be an ADMG. We are interested in exponential families
restricted to positive measures whose conditional independence relations are
represented in $\mathcal{G}$. We denote the general parameter space
constrained by $\mathcal{I}(\mathcal{G})$:

$\Theta_{\mathcal{G}}\equiv\\{\theta\in\Theta\;:\;\mathcal{I}(\mathcal{G})\subseteq\mathcal{I}(P_{\theta})\\}.$

When $\Theta_{\mathcal{G}}$ is a smooth manifold, the family of probability
measures $\\{P_{\theta}\;:\;\theta\in\Theta_{\mathcal{G}}\\}$ is a curved
exponential family; see Kass and Vos, (1997).

######  Proposition 4.1 (Richardson and Spirtes, (2002)).

If $\mathcal{G}=(V,E)$ is an ADMG and
$\mathcal{F}_{\textup{G}}(\mathcal{G})\equiv\\{P_{\theta}\;:\;\theta\in\Theta_{\mathcal{G}}\\}$
is a family of Gaussian ADMG models, then
$\mathcal{F}_{\textup{G}}(\mathcal{G})$ is a curved exponential family with
dimension:

$|\Theta_{\mathcal{G}}|=|V|+|\\{M\in\mathcal{M}(\mathcal{G})\;:\;|M|\in\\{1,2\\}\\}|.$

######  Proposition 4.2 (Evans and Richardson, (2014)).

If $\mathcal{G}=(V,E)$ is an ADMG and
$\mathcal{F}_{\textup{M}}(\mathcal{G})\equiv\\{P_{\theta}\;:\;\theta\in\Theta_{\mathcal{G}}\\}$
is a family of multinomial ADMG models, then
$\mathcal{F}_{\textup{M}}(\mathcal{G})$ is a curved exponential family with
dimension:

$|\Theta_{\mathcal{G}}|=\sum_{H\in\mathcal{H}(\mathcal{G})}|\mathcal{X}_{\textup{tail}_{\mathcal{G}}(H)}|\prod_{h\in
H}(|\mathcal{X}_{h}|-1)$

where the convention $|\mathcal{X}_{\varnothing}|=1$ is accepted.

Let $X$ be a collection of random variables indexed by $V$ with positive
measure $P_{\theta}$ that admits density $f(x\mid\theta)$ with respect to
dominating $\sigma$-finite product measure $\mu$. Throughout this section, let
$P_{\theta}$ belong to a curved exponential family with parameter space
$\Theta$ and $x^{1},\dots,x^{n}\overset{iid}{\sim}f(x\mid\theta)$. The log-
likelihood for parameter estimate $\hat{\theta}\in\Theta$ is defined:

$\ell(\hat{\theta}\mid x^{1},\dots,x^{n})\equiv\sum_{i=1}^{n}\log
f(x^{i}\mid\hat{\theta}).$

Moreover, the maximum log-likelihood estimate of the parameters is defined:

$\hat{\theta}_{n}^{\text{mle}}\equiv\operatorname*{arg\mkern
2.0mumax}_{\hat{\theta}\in\Theta}\ell(\hat{\theta}\mid x^{1},\dots,x^{n})$

and the maximum log-likelihood estimate of the parameters constrained by
$\mathcal{G}$ is defined:

$\hat{\theta}_{\mathcal{G},n}^{\text{mle}}\equiv\operatorname*{arg\mkern
2.0mumax}\limits_{\hat{\theta}\in\Theta_{\mathcal{G}}}\ell(\hat{\theta}\mid
x^{1},\dots,x^{n}).$

Let $\hat{\theta}\in\Theta$ be an estimate of the parameters. If
$T=\textup{tail}_{\mathcal{G}}(H)$ and
$R=\textup{pre}^{\leq}_{\mathcal{G}}(b)$ where context clarifies
$H\in\mathcal{H}(\mathcal{G})$ and $b\in V$, then we approximate the log-
likelihood constrained by $\mathcal{G}$ using $\hat{\theta}$ and the
m-connecting factorization as:

$\displaystyle\hat{\ell}_{\mathcal{G}}(\hat{\theta}\mid x^{1},\dots,x^{n})$
$\displaystyle\equiv\sum_{M\in\mathcal{M}(\mathcal{G})}\sum_{i=1}^{n}\phi_{M}(x^{i}\mid\hat{\theta})$
$\displaystyle=\sum_{H\in\mathcal{H}(\mathcal{G})}\sum_{i=1}^{n}\phi_{H\mid
T}(x^{i}\mid\hat{\theta})$
$\displaystyle=\sum_{H\in\mathcal{H}(\mathcal{G})}\sum_{S\subseteq
H}(-1)^{|H\setminus S|}\sum_{i=1}^{n}\log f_{ST}(x^{i}\mid\hat{\theta})$
$\displaystyle=\sum_{b\in
V}\sum_{\begin{subarray}{c}H\in\mathcal{H}(\mathcal{G}_{R})\\\ b\in
H\end{subarray}}\sum_{\begin{subarray}{c}S\subseteq H\\\ b\not\in
S\end{subarray}}(-1)^{|H\setminus S|-1}\sum_{i=1}^{n}\log f_{b\mid
ST}(x^{i}\mid\hat{\theta})$

Similarly, if $\mathcal{D}=\textup{dom}(\mathcal{G},\leq)$, then the log-
likelihood constrained by $\mathcal{G}$ and $\leq$ is approximated using
$\hat{\theta}$ and the m-connecting factorization as:

$\hat{\ell}_{\mathcal{G}}^{\leq}(\hat{\theta}\mid
x^{1},\dots,x^{n})\equiv\sum_{b\in V}\bigg{[}\sum_{i=1}^{n}\log
f_{b\mid\textup{pa}_{\mathcal{D}}(b)}(x^{i}\mid\hat{\theta})\,-\sum_{S\subseteq\textup{pa}_{\mathcal{D}}(b)}i_{\mathcal{G}}^{\leq}(bS)\sum_{i=1}^{n}\phi_{bS}(x^{i}\mid\hat{\theta})\bigg{]}.$

###  4.1 Bayesian Information Criterion

The Bayesian information criterion (BIC) score provides a computationally
efficient $O_{p}(1)$ approximation for the log marginal likelihood of an
exponential family. Schwarz, (1978) originally formulated the BIC score for
models defined by affine transformations of their natural parameter space
which was later extended to curved exponential families by Haughton, (1988).
The BIC score of a model has a simple formulation using the model’s maximum
likelihood estimate and dimension:

$\text{BIC}(\mathcal{G},x^{1},\dots,x^{n})\equiv\ell(\hat{\theta}_{\mathcal{G},n}^{\text{mle}}\mid
x^{1},\dots,x^{n})-\frac{|\Theta_{\mathcal{G}}|}{2}\log(n).$

Notably, a positive measure $P_{\theta}$ satisfies the global Markov property
with respect to an ADMG $\mathcal{G}$ if and only if
$\theta\in\Theta_{\mathcal{G}}$. Moreover, the BIC score is a consistent score
for model selection.

######  Proposition 4.3 (Proposition 1.2 Haughton, (1988)).

Let $\mathcal{G}=(V,E)$ and $\mathcal{G}^{\prime}=(V,E^{\prime})$ be ADMGs.
Furthermore, let $X$ be a collection of random variables indexed by $V$ with
positive measure $P_{\theta}$ that admits density $f(x\mid\theta)$ with
respect to dominating $\sigma$-finite product measure $\mu$. Let
$x^{1},\dots,x^{n}\overset{iid}{\sim}f(x\mid\theta)$. If either
$\theta\in(\Theta_{\mathcal{G}^{\prime}}\setminus\Theta_{\mathcal{G}})$ or
$\theta\in(\Theta_{\mathcal{G}}\cap\,\Theta_{\mathcal{G}^{\prime}})$ and
$|\Theta_{\mathcal{G}^{\prime}}|<|\Theta_{\mathcal{G}}|$, then:

$\lim_{n\rightarrow\infty}\textup{Pr}(\textup{BIC}(\mathcal{G},x^{1},\dots,x^{n})<\textup{BIC}(\mathcal{G}^{\prime},x^{1},\dots,x^{n}))=1.$

The BIC score has a closed-form solution for many curved exponential families,
such as Gaussian and multinomial DAG models. Unfortunately, this is not always
the case when the parameter space is constrained by the independence model
induced by an ADMG. We develop an approximation for the BIC score, called the
$\textup{BIC}_{\textup{MF}}$ score, that has a closed-form solution in both
cases. Let $\mathcal{D}=\textup{dom}(\mathcal{G},\leq)$, we define the
$\textup{BIC}_{\textup{MF}}$ score using the approximate maximum log-
likelihood characterized by the m-connecting factorization:

$\textup{BIC}_{\textup{MF}}(\mathcal{G},\leq,x^{1},\dots,x^{n})\equiv\begin{dcases*}\mkern
18.0mu\hat{\ell}_{\mathcal{G}}(\hat{\theta}_{\mathcal{D},n}^{\text{mle}}\mid
x^{1},\dots,x^{n})-\frac{|\Theta_{\mathcal{G}}|}{2}\log(n)\mkern
36.0mu&$|M|\leq 5$ for all $M\in\mathcal{M}(\mathcal{G})$\\\ \mkern
18.0mu\hat{\ell}_{\mathcal{G}}^{\leq}(\hat{\theta}_{\mathcal{D},n}^{\text{mle}}\mid
x^{1},\dots,x^{n})-\frac{|\Theta_{\mathcal{G}}|}{2}\log(n)\mkern
36.0mu&otherwise\end{dcases*}$

which has nice asymptotic properties and simplifies to BIC if $\mathcal{G}$ is
a DAG.

######  Lemma 4.1.

Let $\mathcal{G}=(V,E)$ and $\mathcal{G}^{\prime}=(V,E^{\prime})$ be ADMGs and
$\leq$ and $\leq^{\prime}$ be total orders consistent with $\mathcal{G}$ and
$\mathcal{G}^{\prime}$, respectively. Furthermore, let $X$ be a collection of
random variables indexed by $V$ with positive measure $P_{\theta}$ that admits
density $f(x\mid\theta)$ with respect to dominating $\sigma$-finite product
measure $\mu$. Let $x^{1},\dots,x^{n}\overset{iid}{\sim}f(x\mid\theta)$.

If and $\theta\in\Theta_{\mathcal{G}}\setminus\Theta_{\mathcal{G}^{\prime}}$,
then:

$\lim_{n\rightarrow\infty}\,\frac{1}{n}\left|\textup{BIC}_{\textup{MF}}(\mathcal{G},\leq,x^{1},\dots,x^{n})-\textup{BIC}_{\textup{MF}}(\mathcal{G}^{\prime},\leq^{\prime},x^{1},\dots,x^{n})\right|=\mathbb{E}_{P_{\theta}}\left[\phi_{\mathsf{P}}(x)^{\top}i_{\mathcal{G}^{\prime}}^{\leq}\right].$

If $x^{1},\dots,x^{n}\overset{iid}{\sim}f(x\mid\theta)$ and
$\theta\in\Theta_{\mathcal{G}}\cap\,\Theta_{\mathcal{G}^{\prime}}$ with
$|\Theta_{\mathcal{G}}|<|\Theta_{\mathcal{G}^{\prime}}|$, then:

$\lim_{n\rightarrow\infty}\frac{1}{\log
n}\left|\textup{BIC}_{\textup{MF}}(\mathcal{G},\leq,x^{1},\dots,x^{n})-\textup{BIC}_{\textup{MF}}(\mathcal{G}^{\prime},\leq^{\prime},x^{1},\dots,x^{n})\right|=\frac{|\Theta_{\mathcal{G}^{\prime}}|-|\Theta_{\mathcal{G}}|}{2}.$

The $\textup{BIC}_{\textup{MF}}$ is a consistent score for model selection;
see Appendix B.3 for a discussion of $\textup{BIC}_{\textup{MF}}$ use as an
approximation of log marginal likelihoods for exponential families.
Furthermore, this score is readily applied to Gaussian and multinomial ADMG
models by Propositions 4.1 and 4.2.

######  Proposition 4.4.

Let $\mathcal{G}=(V,E)$ and $\mathcal{G}^{\prime}=(V,E^{\prime})$ be ADMGs and
$\leq$ and $\leq^{\prime}$ be total orders consistent with $\mathcal{G}$ and
$\mathcal{G}^{\prime}$, respectively. Furthermore, let $X$ be a collection of
random variables indexed by $V$ with positive measure $P_{\theta}$ that admits
density $f(x\mid\theta)$ with respect to dominating $\sigma$-finite product
measure $\mu$. If $x^{1},\dots,x^{n}\overset{iid}{\sim}f(x\mid\theta)$ and
$\theta\in\Theta_{\mathcal{G}}\setminus\Theta_{\mathcal{G}^{\prime}}$ or
$\theta\in\Theta_{\mathcal{G}}\cap\,\Theta_{\mathcal{G}^{\prime}}$ where
$|\Theta_{\mathcal{G}}|<|\Theta_{\mathcal{G}^{\prime}}|$, then:

$\lim_{n\rightarrow\infty}\textup{Pr}(\textup{BIC}_{\textup{MF}}(\mathcal{G}^{\prime},\leq^{\prime},x^{1},\dots,x^{n})<\textup{BIC}_{\textup{MF}}(\mathcal{G},\leq,x^{1},\dots,x^{n}))=1.$

###  4.2 Empirical Evaluation

While the BIC score is a consistent scoring criterion, it does not always have
a closed-form solution for ADMG models. In particular, the calculation of the
maximum log-likelihood requires the development of model specific optimizers.
Such optimizers have been developed for Gaussian and multinomial ADMG models
by Drton and Richardson, (2004); Drton et al., (2009) and Evans and
Richardson, (2014), respectively. In contrast, the approximate maximum log-
likelihood calculation developed in this paper uses the maximum likelihood
estimate of the parameters for a dominating DAG model. Accordingly, the
$\textup{BIC}_{\textup{MF}}$ score has a closed form solution for many curved
exponential families, such as Gaussian and multinomial ADMG models.

In this section, we compare the ability of the $\textup{BIC}_{\textup{MF}}$
score to recover the correct MEC for Gaussian ADMG models against the
$\textup{BIC}_{\textup{ICF}}$—the BIC score where the maximum likelihood
estimate of the parameters is approximated using an R implementation of the
iterative conditional fitting (ICF)
procedure111https://CRAN.R-project.org/package=ggm (Drton and Richardson,,
2004). ICF optimizes the log-likelihood for curved exponential families
constrained by an ADMG independence model, however, this space is not
necessarily convex. Accordingly, ICF is not guaranteed to converge to the
maximum likelihood estimate of the parameters.

In addition to the $\textup{BIC}_{\textup{ICF}}$ score, we compare the
$\textup{BIC}_{\textup{MF}}$ score’s ability to recover the correct MEC for
Gaussian ADMG models against three causal discovery algorithms:

  * $\bullet$

FCI (Spirtes et al.,, 1999; Zhang,, 2008) using the zero partial correlation
test of conditional independence.

  * $\bullet$

$\text{FCI}_{\text{max}}$ (Raghu et al.,, 2018) using Fisher’s Z test of
conditional independence.

  * $\bullet$

$\text{GFCI}_{i}$ (Ogarrio et al.,, 2016) using the BIC score with penalty
discount $i\in\\{1,2\\}$ and Fisher’s Z test of conditional independence.

We used Java implementations of these algorithms from the TETRAD
project222https://github.com/cmu-phil/tetrad. In our simulations, we generated
data from a subfamily of ADMGs called directed maximal ancestral graphs
(MAGs); directed MAGs induce the same independence models as ADMGs and have a
straightforward parameterization (Richardson and Spirtes,, 2002). Algorithm 4
outlines the procedure used to simulate $n$ data instances with respect to
directed MAG $\mathcal{G}$.

Input: directed MAG: $\mathcal{G}=(V,E)$, number of instances: $n$

Output: data: $x^{1},\dots x^{n}$

1

2repeat

3 $\Omega=(\omega_{ab})_{a,b\in
V}\;\text{where}\;\omega_{ab}\sim\Bigg{\\{}\\!\\!\begin{array}[]{ll}\text{Uniform}\,[-0.7,-0.3]\cup[0.3,0.7]&\quad\text{if}\;\\{a,b\\}\in
E\\\ \text{Uniform}\,[1.0,3.0]&\quad\text{if}\;a=b\\\
0&\quad\text{otherwise}\end{array}$ ;

4

5until  _$\Omega$ is symmetric and positive-definite_;

6$B^{\top}=(\beta_{ab})_{a,b\in
V}\;\text{where}\;\beta_{ab}\sim\Big{\\{}\\!\\!\begin{array}[]{ll}\text{Uniform}\,[-0.7,-0.3]\cup[0.3,0.7]&\quad\text{if}\;(a,b)\in
E\\\ 0&\quad\text{otherwise}\end{array}$ ;

7 $\Sigma=(I-B)^{-1}\,\Omega\,(I-B)^{-\top}$ ;

8 $x^{1},\dots,x^{n}\sim\text{Gaussian}(0,\Sigma)$ ;

Algorithm 4 $\textsc{Simulate}(\mathcal{G},n)$

We use a Python implementation of $\textup{BIC}_{\textup{MF}}$ to exhaustively
rank all ADMG MECs333https://github.com/bja43/agMm. Histograms show the
distribution of the rank of the data generating MEC. That is, the
$i^{\textup{th}}$ bin counts the number of times the data generating MEC is
ranked $i^{\textup{th}}$ among all models. Notably, there are 24,259 possible
positions in the ranking for graphs with 5 vertices.

For all experiments, we simulate datasets with 500, 5,000 and 50,000
instances. We run experiments for two prespecified graphs and two sets of
random graphs with 5 vertices; The first set has between 0 and 5 edges and the
second set has between 6 and 10 edges. For each scenario, we run 1,000
repetitions (100 for comparison to $\textup{BIC}_{\textup{ICF}}$). When not
prespecified, graphs are resampled with equal probability assigned to each
directed MAG satisfying the experimental parameters. The tables below report
the proportion of times that algorithms recovered the correct MEC. These
numbers may be compared to the counts reported in the first bin of each
histogram divided by 1,000. All experiments were run on a system with the
following hardware:

  * $\bullet$

Memory: 7.7 GiB

  * $\bullet$

Processor: Intel® CoreTM i5-5200U CPU @ 2.20GHz $\times$ 4

Directed MAG
MEC Recovery  $\textup{BIC}_{\textup{ICF}}$ $\textup{BIC}_{\textup{MF}}$ FCI
FCI${}_{\text{max}}$ GFCI1 GFCI2 repetitions 100 100 1,000 1,000 1,000 1,000
1,000 $\alpha$-level - - - 0.01 0.001 0.01 0.001 0.01 0.001 0.01 0.001 n = 500
0.49 0.47 0.544 0.836 0.702 0.499 0.444 0.223 0.213 0.08 0.08 n = 5,000 0.91
0.93 0.932 0.978 0.999 0.933 0.948 0.779 0.786 0.575 0.576 n = 50,000 1.0 1.0
0.985 0.975 0.998 0.975 0.998 0.99 0.991 0.977 0.977

Figure 17: An evaluation of the $\textup{BIC}_{\textup{MF}}$ relative to the
$\textup{BIC}_{\textup{ICF}}$ and state-of-the-art algorithms on data
generated from the depicted directed MAG.

In Figure 17, the prespecified graph is a bi-directed chain of length five.
The $\textup{BIC}_{\textup{MF}}$ score performs nearly identically to the
$\textup{BIC}_{\textup{ICF}}$ score and consistently ranks the correct MEC in
the top 10 with the ranking converging to a point-mass in the first bin as
$n\rightarrow\infty$. The top ranked model according to the
$\textup{BIC}_{\textup{MF}}$ score was correct less often than the model
returned by FCI, and more often than the model returned by GFCI for small
sample sizes.

Directed MAG
MEC Recovery  $\textup{BIC}_{\textup{ICF}}$ $\textup{BIC}_{\textup{MF}}$ FCI
FCI${}_{\text{max}}$ GFCI1 GFCI2 repetitions 100 100 1,000 1,000 1,000 1,000
1,000 $\alpha$-level - - - 0.01 0.001 0.01 0.001 0.01 0.001 0.01 0.001 n = 500
0.12 0.14 0.138 0.006 0.0 0.005 0.0 0.0 0.0 0.0 0.0 n = 5,000 0.53 0.54 0.538
0.052 0.028 0.048 0.028 0.041 0.029 0.032 0.02 n = 50,000 0.77 0.79 0.804
0.307 0.23 0.296 0.221 0.304 0.247 0.28 0.221

Figure 18: An evaluation of the $\textup{BIC}_{\textup{MF}}$ relative to the
$\textup{BIC}_{\textup{ICF}}$ and state-of-the-art algorithms on data
generated from the depicted directed MAG.

In Figure 18, the prespecified graph contains a discriminating path of length
five; see (Richardson and Spirtes,, 2002) for details. The
$\textup{BIC}_{\textup{MF}}$ score performs nearly identically to the
$\textup{BIC}_{\textup{ICF}}$ score and consistently ranks the correct MEC in
the top 10 with the ranking converging to a point-mass in the first bin as
$n\rightarrow\infty$. The top ranked model according to the
$\textup{BIC}_{\textup{MF}}$ score was correct more often than the models
returned by other methods.

Random Directed MAGs with $|V|=5$ and $|E|\in[0,5]$
MEC Recovery  $\textup{BIC}_{\textup{ICF}}$ $\textup{BIC}_{\textup{MF}}$ FCI
FCI${}_{\text{max}}$ GFCI1 GFCI2 repetitions 100 100 1,000 1,000 1,000 1,000
1,000 $\alpha$-level - - - 0.01 0.001 0.01 0.001 0.01 0.001 0.01 0.001 n = 500
0.57 0.58 0.495 0.273 0.16 0.398 0.338 0.349 0.324 0.258 0.252 n = 5,000 0.9
0.88 0.871 0.776 0.741 0.788 0.78 0.741 0.732 0.676 0.671 n = 50,000 0.99 0.99
0.966 0.919 0.915 0.92 0.919 0.904 0.9 0.893 0.888

Figure 19: An evaluation of the $\textup{BIC}_{\textup{MF}}$ relative to the
$\textup{BIC}_{\textup{ICF}}$ and state-of-the-art algorithms on data
generated using random directed MAGs with specified vertex and edge ranges.

In Figure 19, the $\textup{BIC}_{\textup{MF}}$ score performs nearly
identically to the $\textup{BIC}_{\textup{ICF}}$ score and consistently ranks
the correct MEC in the top 10 with the ranking converging to a point-mass in
the first bin as $n\rightarrow\infty$. The top ranked model according to the
$\textup{BIC}_{\textup{MF}}$ score was correct more often than the models
returned by other methods.

Random Directed MAGs with $|V|=5$ and $|E|\in[6,10]$
MEC Recovery  $\textup{BIC}_{\textup{ICF}}$ $\textup{BIC}_{\textup{MF}}$ FCI
FCI${}_{\text{max}}$ GFCI1 GFCI2 repetitions 100 100 1,000 1,000 1,000 1,000
1,000 $\alpha$-level - - - 0.01 0.001 0.01 0.001 0.01 0.001 0.01 0.001 n = 500
0.24 0.24 0.188 0.026 0.009 0.072 0.031 0.035 0.021 0.022 0.019 n = 5,000 0.61
0.59 0.603 0.311 0.243 0.354 0.319 0.297 0.261 0.238 0.216 n = 50,000 0.9 0.91
0.865 0.665 0.617 0.687 0.671 0.641 0.622 0.595 0.579

Figure 20: An evaluation of the $\textup{BIC}_{\textup{MF}}$ score relative to
the $\textup{BIC}_{\textup{ICF}}$ score and state-of-the-art algorithms on
data generated using random directed MAGs with specified vertex and edge
ranges.

In Figure 20, the $\textup{BIC}_{\textup{MF}}$ score performs nearly
identically to the $\textup{BIC}_{\textup{ICF}}$ score and consistently ranks
the correct MEC in the top 100 with the ranking converging to a point-mass in
the first bin as $n\rightarrow\infty$. The top ranked model according to the
$\textup{BIC}_{\textup{MF}}$ score was correct more often than the models
returned by other methods.

| $\textup{BIC}_{\textup{ICF}}$ | $\textup{BIC}_{\textup{MF}}$
---|---|---
sample size | n = 500 | n = 5,000 | n = 50,000 | n = 500 | n = 5,000 | n = 50,000
Figure 17 | 74.6 (5.8) | 72.8 (5.7) | 71.9 (5.8) | 0.64 (0.02) | 0.63 (0.01) | 0.63 (0.01)
Figure 18 | 81.3 (8.5) | 80.9 (8.1) | 80.8 (8.4) | 0.64 (0.06) | 0.63 (0.06) | 0.63 (0.07)
Figure 19 | 77.7 (7.5) | 76.5 (7.8) | 75.5 (7.7) | 0.32 (0.1) | 0.29 (0.07) | 0.28 (0.03)
Figure 20 | 80.9 (10.5) | 80.3 (10.1) | 80.3 (10.4) | 0.26 (0.01) | 0.26 (0.01) | 0.26 (0.01)
Table 1: The mean run times (stds in parentheses) for the simulations in
seconds (100 reps).

Table 1 tabulates the time it took the $\textup{BIC}_{\textup{MF}}$ and
$\textup{BIC}_{\textup{ICF}}$ scores to rank all 24,259 models. Both scores
were given a sample covariance matrix as input. The time to calculate the
sample covariance matrix generally took between 2 and 5 milliseconds. In
general, we find that the $\textup{BIC}_{\textup{MF}}$ and
$\textup{BIC}_{\textup{ICF}}$ scores have little to no difference in
performance, while the $\textup{BIC}_{\textup{MF}}$ score takes a fraction of
the time. Both scores perform well with small sample sizes and compare
favorably to FCI and two of its variants on recovering correct independence
models.

##  5 Discussion

In this paper, we introduce the m-connecting imset which provides an
alternative representation for ADMG independence models. Furthermore, we
define the m-connecting factorization criterion for ADMG models and prove its
equivalence to the global Markov property. The m-connecting imset and
factorization criterion provide two new statistical tools for learning and
inference with ADMG models. We demonstrate the usefulness of these tools by
formulating and evaluating a consistent scoring criterion for Gaussian and
multinomial ADMG models with a closed form. Unlike existing methods for
scoring ADMG models, our proposed approach does not require the development of
a distribution specific optimizer. Consequently, we do not solve for
parameters in a non-convex space.

In the past five years, there has been an influx of methods capable of
learning ADMGs by optimizing a score, such as the methods of Chen et al.,
(2021); Nowzohour et al., (2017); Triantafillou and Tsamardinos, (2016);
Tsirlis et al., (2018)—these methods rely on the $\textup{BIC}_{\textup{ICF}}$
score. One could both improve the efficiency of these algorithms and allow
them to be extended to more general distributions by replacing the
$\textup{BIC}_{\textup{ICF}}$ score with the $\textup{BIC}_{\textup{MF}}$
score. Additionally, since our score is formulated using the m-connecting
imset, one could also explore a geometric approach for learning ADMGs, similar
to existing DAG learning methods Studený and Haws, (2014); Studený and
Cussens, (2017); Linusson et al., (2021).

## Acknowledgements

We thank Joe Ramsey, Kun Zhang, Clark Glymour, Robin Evans, and Zhongyi Hu for
insightful discussion and comments on earlier versions of the draft. The
research reported in this paper was supported by grant U54HG008540 awarded by
the National Human Genome Research Institute through funds provided by the
trans-NIH Big Data to Knowledge (BD2K) initiative, grant #4100070287 from the
Pennsylvania Department of Health (DOH), and grant IIS-1636786 from the
National Science Foundation. Author BA also received support from training
grant T15LM007059 from the National Library of Medicine. The content of this
paper is solely the responsibility of the authors and does not necessarily
represent the official views of these funding agencies.

## References

  * Andrews, (2022) Andrews, B. J. (2022).  Inducing Sets: A New Perspective for Ancestral Graph Markov Models.  PhD thesis, University of Pittsburgh.
  * Berk, (1972) Berk, R. H. (1972).  Consistency and asymptotic normality of mle’s for exponential models.  The Annals of Mathematical Statistics, pages 193–204.
  * Bishop, (2006) Bishop, C. M. (2006).  Pattern Recognition and Machine Learning.  Information Science and Statistics. Springer.
  * Chen et al., (2021) Chen, R., Dash, S., and Gao, T. (2021).  Integer programming for causal structure learning in the presence of latent variables.  arXiv preprint arXiv:2102.03129.
  * Darwiche, (2009) Darwiche, A. (2009).  Modeling and Reasoning with Bayesian Networks.  Cambridge University Press.
  * Dawid, (2011) Dawid, A. P. (2011).  Posterior model probabilities.  In Philosophy of Statistics, pages 607–630. Elsevier.
  * Drton et al., (2009) Drton, M., Eichler, M., and Richardson, T. S. (2009).  Computing maximum likelihood estimates in recursive linear models with correlated errors.  Journal of Machine Learning Research, 10.
  * Drton and Richardson, (2004) Drton, M. and Richardson, T. S. (2004).  Iterative conditional fitting for Gaussian ancestral graph models.  In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pages 130–137.
  * Evans, (2016) Evans, R. J. (2016).  Graphs for margins of Bayesian networks.  Scandinavian Journal of Statistics, 43:625–648.
  * (10) Evans, R. J. (2018a).  Margins of discrete Bayesian networks.  The Annals of Statistics, 46:2623–2656.
  * (11) Evans, R. J. (2018b).  Markov properties for mixed graphical models.  In Handbook of Graphical Models, pages 39–60. CRC Press.
  * Evans and Richardson, (2014) Evans, R. J. and Richardson, T. S. (2014).  Markovian acyclic directed mixed graphs for discrete data.  The Annals of Statistics, pages 1452–1482.
  * Geiger et al., (2001) Geiger, D., Heckerman, D., King, H., and Meek, C. (2001).  Stratified exponential families: Graphical models and model selection.  Annals of statistics, pages 505–529.
  * Haughton, (1988) Haughton, D. M. (1988).  On the choice of a model to fit data from an exponential family.  The Annals of Statistics, 16:342–355.
  * Hemmecke et al., (2012) Hemmecke, R., Lindner, S., and Studený, M. (2012).  Characteristic imsets for learning Bayesian network structure.  International Journal of Approximate Reasoning, 53:1336–1349.
  * Hu and Evans, (2020) Hu, Z. and Evans, R. J. (2020).  Faster algorithms for Markov equivalence.  In Proceedings of the Conference on Uncertainty in Artificial Intelligence, volume 124 of Proceedings of Machine Learning Research, pages 739–748. PMLR.
  * Kass and Vos, (1997) Kass, R. E. and Vos, P. W. (1997).  Geometrical Foundations of Asymptotic Inference.  John Wiley & Sons.
  * Koller and Friedman, (2009) Koller, D. and Friedman, N. (2009).  Probabilistic Graphical Models: Principles and Techniques.  Adaptive computation and machine learning. MIT press.
  * Linusson et al., (2021) Linusson, S., Restadh, P., and Solus, L. (2021).  Greedy causal discovery is geometric.  arXiv preprint arXiv:2103.03771.
  * McGill, (1954) McGill, W. (1954).  Multivariate information transmission.  Transactions of the IRE Professional Group on Information Theory, 4:93–111.
  * Nowzohour et al., (2017) Nowzohour, C., Maathuis, M. H., Evans, R. J., and Bühlmann, P. (2017).  Distributional equivalence and structure learning for bow-free acyclic path diagrams.  Electronic Journal of Statistics, 11:5342–5374.
  * Ogarrio et al., (2016) Ogarrio, J. M., Spirtes, P., and Ramsey, J. (2016).  A hybrid causal search algorithm for latent variable models.  In Conference on Probabilistic Graphical Models, pages 368–379. PMLR.
  * Pearl, (1988) Pearl, J. (1988).  Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference.  Morgan Kaufmann series in representation and reasoning. Morgan Kaufmann Publishers.
  * Pearl, (2009) Pearl, J. (2009).  Causality.  Cambridge University Press.
  * Raghu et al., (2018) Raghu, V. K., Ramsey, J., Morris, A., Manatakis, D. V., Sprites, P., Chrysanthis, P. K., Glymour, C., and Benos, P. V. (2018).  Comparison of strategies for scalable causal discovery of latent variable models from mixed data.  International Journal of Data Science and Analytics, 6:33–45.
  * Richardson, (2003) Richardson, T. S. (2003).  Markov properties for acyclic directed mixed graphs.  Scandinavian Journal of Statistics, 30:145–157.
  * Richardson, (2009) Richardson, T. S. (2009).  A factorization criterion for acyclic directed mixed graphs.  In Proceedings of the Conference on Uncertainty in Artificial Intelligence, page 462–470. AUAI Press.
  * Richardson and Spirtes, (2002) Richardson, T. S. and Spirtes, P. (2002).  Ancestral graph Markov models.  The Annals of Statistics, 30:962–1030.
  * Rota, (1964) Rota, G.-C. (1964).  On the foundations of combinatorial theory. I. Theory of Möbius functions.  Probability Theory and Related Fields, 2:340–368.
  * Sadeghi, (2013) Sadeghi, K. (2013).  Stable mixed graphs.  Bernoulli, 19:2330–2358.
  * Sadeghi and Lauritzen, (2014) Sadeghi, K. and Lauritzen, S. L. (2014).  Markov properties for mixed graphs.  Bernoulli, 20:676–696.
  * Schwarz, (1978) Schwarz, G. (1978).  Estimating the dimension of a model.  The Annals of Statistics, 6:461–464.
  * Settimi and Smith, (1998) Settimi, R. and Smith, J. Q. (1998).  On the geometry of Bayesian graphical models with hidden variables.  In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pages 472–479.
  * Settimi and Smith, (2000) Settimi, R. and Smith, J. Q. (2000).  Geometry, moments and conditional independence trees with hidden variables.  Annals of Statistics, pages 1179–1205.
  * Spirtes et al., (2000) Spirtes, P., Glymour, C., and Scheines, R. (2000).  Causation, Prediction, and Search.  Adaptive computation and machine learning. MIT Press.
  * Spirtes et al., (1999) Spirtes, P., Meek, C., and Richardson, T. S. (1999).  An algorithm for causal inference in the presence of latent variables and selection bias.  In Glymour, C. and Cooper, G. F., editors, Computation, Causation, and Discovery. MIT Press.
  * Studený, (2005) Studený, M. (2005).  Probabilistic Conditional Independence Structures.  Information Science and Statistics. Springer.
  * Studený, (2008) Studený, M. (2008).  Mathematical aspects of learning Bayesian networks: Bayesian quality criteria.  Technical report, Institute of Information Theory and Automation, Prague.
  * Studený and Cussens, (2017) Studený, M. and Cussens, J. (2017).  Towards using the chordal graph polytope in learning decomposable models.  International Journal of Approximate Reasoning, 88:259–281.
  * Studený and Haws, (2014) Studený, M. and Haws, D. (2014).  Learning Bayesian network structure: Towards the essential graph by integer linear programming tools.  International Journal of Approximate Reasoning, 55:1043–1071.
  * Triantafillou and Tsamardinos, (2016) Triantafillou, S. and Tsamardinos, I. (2016).  Score-based vs constraint-based causal learning in the presence of confounders.  In Workshop on Causation: Foundation to Application, pages 59–67.
  * Tsirlis et al., (2018) Tsirlis, K., Lagani, V., Triantafillou, S., and Tsamardinos, I. (2018).  On scoring maximal ancestral graphs with the max–min hill climbing algorithm.  International Journal of Approximate Reasoning, 102:74–85.
  * Verma and Pearl, (1990) Verma, T. S. and Pearl, J. (1990).  Equivalence and synthesis of causal models.  In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pages 255–270.
  * Wildberger, (2003) Wildberger, N. J. (2003).  A new look at multisets.  preprint.
  * Zhang, (2008) Zhang, J. (2008).  On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias.  Artificial Intelligence, 172:1873–1896.

##  Appendix A Proofs

Proposition 2.6 Let $\mathcal{G}=(V,E)$ be an ADMG with consistent order
$\leq$. If $b\in V$ and $R=\textup{pre}^{\leq}_{\mathcal{G}}(b)$ then:

$b\perp\mkern-9.0mu\perp
V\setminus\textup{cl}_{\mathcal{G}}(b)\mid\textup{mb}_{\mathcal{G}}(b)\;[\mkern
0.5mu\mathcal{G}\mkern 0.5mu].$

###### Proof.

By Proposition 2.5 $\mathcal{I}(\mathcal{G})$ is a compositional graphoid, so
we may apply the compositional graphoid axioms. Let $a\in
V\setminus\textup{cl}_{\mathcal{G}}(b)$ and $\pi_{ab}$ be a path between $a$
and $b$. Traverse $\pi_{ab}$ from $a$ to $b$ until reaching a member of
$\textup{cl}_{\mathcal{G}}(b)$ denoting it $c$ and the vertex immediately
preceding it on the transversal $d$. Notably, if $b=c$ or $c$ is a collider on
$\pi_{ab}$, then $d\in\textup{cl}_{\mathcal{G}}(b)$ which is false by
construction. Accordingly, $c\in\textup{mb}_{\mathcal{G}}(b)$ and is a non-
collider on $\pi_{ab}$. It follows that $\pi_{ab}$ is not an m-connecting path
between $a$ and $b$ relative to $\textup{mb}_{\mathcal{G}}(b)$. Since we
picked $a$ and $\pi_{ab}$ arbitrarily, $a\perp\mkern-9.0mu\perp
b\mid\textup{mb}_{\mathcal{G}}(b)\;[\mkern 0.5mu\mathcal{G}\mkern 0.5mu]$ for
all $a\in V\setminus\textup{cl}_{\mathcal{G}}(b)$. By the composition graphoid
axiom that $b\perp\mkern-9.0mu\perp
V\setminus\textup{cl}_{\mathcal{G}}(b)\mid\textup{mb}_{\mathcal{G}}(b)\;[\mkern
0.5mu\mathcal{G}\mkern 0.5mu]$. ∎

Theorem 2.3 Let $u$ be an imset and $P$ be a positive measure. If
$u\in\mathcal{S}(V)$, then the following are equivalent:

  1. i.

$\sum\limits_{S\in\mathcal{P}(V)}u(S)\log f_{S}(x)=0\mkern 18.0mu$ for
$\mu$-almost all $x\in\mathcal{X}$;

  2. ii.

$A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5muu\mkern 0.5mu]\mkern
18.0mu\Rightarrow\mkern 18.0muA\perp\mkern-9.0mu\perp B\mid C\;[\mkern
0.5muP\mkern 0.5mu]\mkern 18.0mu$ for all $\langle A,B\mid
C\rangle\in\mathcal{T}(V)$.

###### Proof.

Notably:

$\displaystyle\sum\limits_{S\in\mathcal{P}(V)}u(S)\log f_{S}(x)$
$\displaystyle=\sum\limits_{S\in\mathcal{P}(V)}\sum_{\langle a,b\mid
C\rangle\in\mathcal{T}(V)}k_{a,b\mid C}u_{\langle a,b\mid C\rangle}(S)\log
f_{S}(x)$ $\displaystyle=\sum_{\langle a,b\mid
C\rangle\in\mathcal{T}(V)}k_{a,b\mid
C}\sum\limits_{S\in\mathcal{P}(V)}u_{\langle a,b\mid C\rangle}(S)\log
f_{S}(x)$ $\displaystyle=\sum_{\langle a,b\mid
C\rangle\in\mathcal{T}(V)}k_{a,b\mid
C}\log\frac{f_{abC}(x)f_{C}(x)}{f_{aC}(x)f_{bC}(x)}$

for $k_{\langle a,b\mid C\rangle}\in\mathbb{Q}^{+}$.

($i\Rightarrow ii$) If:

$\sum_{\langle a,b\mid C\rangle\in\mathcal{T}(V)}k_{a,b\mid
C}\log\frac{f_{abC}(x)f_{C}(x)}{f_{aC}(x)f_{bC}(x)}=0\mkern 18.0mu\text{for
$\mu$-almost all}\;x\in\mathcal{X},$

then:

$\mathbb{E}_{P}\log\frac{f_{abC}(x)f_{C}(x)}{f_{aC}(x)f_{bC}(x)}=0\mkern
18.0mu\text{for all}\;k_{a,b\mid C}\neq 0.$

Accordingly, $a\perp\mkern-9.0mu\perp b\mid C\;[\mkern 0.5muu\mkern
0.5mu]\;\Rightarrow\;a\perp\mkern-9.0mu\perp b\mid C\;[\mkern 0.5muP\mkern
0.5mu]$ for all $\langle a,b\mid C\rangle\in\mathcal{T}(V)$ and by repeated
application of the graphoid axoims $A\perp\mkern-9.0mu\perp B\mid C\;[\mkern
0.5muu\mkern 0.5mu]\;\Rightarrow\;A\perp\mkern-9.0mu\perp B\mid C\;[\mkern
0.5muP\mkern 0.5mu]$ for all $\langle A,B\mid C\rangle\in\mathcal{T}(V)$.

($i\Leftarrow ii$) If $A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5muu\mkern
0.5mu]\;\Rightarrow\;A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5muP\mkern
0.5mu]$ for all $\langle A,B\mid C\rangle\in\mathcal{T}(V)$, then:

$\log\frac{f_{abC}(x)f_{C}(x)}{f_{aC}(x)f_{bC}(x)}=0\mkern 18.0mu\text{for
all}\;k_{\langle a,b\mid C\rangle}\neq 0.$

Accordingly:

$\sum_{\langle a,b\mid C\rangle\in\mathcal{T}(V)}k_{a,b\mid
C}\log\frac{f_{abC}(x)f_{C}(x)}{f_{aC}(x)f_{bC}(x)}=0.$

∎

Proposition 2.9 Let $\mathcal{G}=(V,E)$ be a DAG and $S\subseteq V$ $(|S|\geq
2)$. If $A=\textup{an}_{\mathcal{G}}(S)$ and
$B=\textup{bar}_{\mathcal{G}}(S)$, then:

  1. i.

$c_{\mathcal{G}}(S)\in\\{0,1\\}$;

  2. ii.

$c_{\mathcal{G}}(S)=1\mkern 18.0mu\Leftrightarrow\mkern 18.0mu\text{there
exists}\;b\in S\;\text{such that}\;S\setminus
b\subseteq\textup{pa}_{\mathcal{G}}(b)$;

  3. iii.

$c_{\mathcal{G}}(S)=1\mkern 18.0mu\Leftrightarrow\mkern
18.0muS\subseteq\textup{col}_{\mathcal{G}_{A}}(B)$.

###### Proof.

Properties (i) and (ii) were shown by Hemmecke et al., (2012). Accordingly, we
show the following are equivalent:

  1. i.

$S\subseteq\textup{col}_{\mathcal{G}_{A}}(B)$;

  2. ii.

$\text{there exists}\;b\in S\;\text{such that}\;S\setminus
b\subseteq\textup{pa}_{\mathcal{G}}(b)$.

($i\Rightarrow ii$) If $S\subseteq\textup{col}_{\mathcal{G}_{A}}(B)$, then let
$\leq$ be a total order consistent with $\mathcal{G}$ and $b=\lceil
S\rceil_{\leq}$. It follows that $S\setminus b=\textup{pa}_{\mathcal{G}}(a)$
since $\mathcal{G}$ is a DAG.

($i\Leftarrow ii$) If $b\in S\;\text{such that}\;S\setminus
b\subseteq\textup{pa}_{\mathcal{G}}(b)$, then by definition,
$S\subseteq\textup{col}_{\mathcal{G}_{A}}(B)$ ∎

Proposition 3.3 If $P$ is a positive measure, then:

  1. i.

$\displaystyle\phi_{A\mid B}(x)=\sum_{\begin{subarray}{c}T\subseteq AB\\\
B\subseteq T\end{subarray}}(-1)^{|AB\setminus T|}\log f_{T}(x)$

  2. ii.

$\displaystyle\phi_{A,B\mid
C}(x)=\log\frac{f_{ABC}(x)f_{C}(x)}{f_{AC}(x)f_{BC}(x)}$

  3. iii.

$u_{\langle A,B\mid C\rangle}=\mu_{\mathsf{P}}\mkern 0.5mu\delta_{A,B\mid C}$

  4. iv.

$A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5muP\mkern 0.5mu]\mkern
18.0mu\Leftrightarrow\mkern 18.0mu\phi_{A,B\mid C}(x)=0\mkern 18.0mu\text{for
$\mu$-almost all}\;x\in\mathcal{X}$

###### Proof.

(i):

$\displaystyle\phi_{A\mid B}(x)$
$\displaystyle=\sum_{\begin{subarray}{c}S\subseteq AB\\\ A\subseteq
S\end{subarray}}\phi_{S}(x)$
$\displaystyle=\sum_{\begin{subarray}{c}S\subseteq AB\\\ A\subseteq
S\end{subarray}}\sum_{T\subseteq S}(-1)^{|S\setminus T|}\log f_{T}(x)$
$\displaystyle=\sum_{T\subseteq AB}\log
f_{T}(x)\sum_{\begin{subarray}{c}S\subseteq AB\\\ A,T\subseteq
S\end{subarray}}(-1)^{|S\setminus T|}$ $\displaystyle=\sum_{T\subseteq AB}\log
f_{T}(x)\sum_{U\subseteq B\setminus T}(-1)^{|A\setminus T|+|U|}$
$\displaystyle=\sum_{\begin{subarray}{c}T\subseteq AB\\\ B\subseteq
T\end{subarray}}(-1)^{|AB\setminus T|}\log f_{T}(x)$

where

$\sum_{U\subseteq B\setminus T}(-1)^{|A\setminus T|+|U|}=\begin{cases}\mkern
18.0mu(-1)^{|AB\setminus T|}\mkern 36.0mu&B\subseteq T;\\\ \mkern
18.0mu0\mkern 36.0mu&B\not\subseteq T\end{cases}$

since whenever $B\not\subseteq T$ note that $|A\setminus T|$ is constant and
$B\setminus T\neq\varnothing$:

$\sum_{S\subseteq B\setminus T}(-1)^{|A\setminus T|+|S|}=0$

and whenever $B\subseteq T$ note that $B\setminus T=\varnothing$ and
$A\setminus T=AB\setminus T$:

$\sum_{S\subseteq B\setminus T}(-1)^{|A\setminus T|+|S|}=(-1)^{|AB\setminus
T|}.$

(ii):

$\displaystyle\phi_{A,B\mid C}(x)$
$\displaystyle=\sum_{\begin{subarray}{c}T\subseteq ABC\\\ T\not\subseteq AC\\\
T\not\subseteq BC\end{subarray}}\phi_{T}(x)$ $\displaystyle=\sum_{T\subseteq
ABC}\phi_{T}(x)+\sum_{T\subseteq C}\phi_{T}(x)-\sum_{T\subseteq
AC}\phi_{T}(x)-\sum_{T\subseteq BC}\phi_{T}(x)$ $\displaystyle=\log
f_{ABC}(x)+\log f_{C}(x)-\log f_{AC}(x)-\log f_{BC}(x).$

(iii): Note that $\sum_{T\subseteq A}\delta_{T}=\zeta_{\mathsf{P}}\mkern
0.5mu\delta_{A}$:

$\displaystyle\delta_{A,B\mid C}$
$\displaystyle=\sum_{\begin{subarray}{c}T\subseteq ABC\\\ T\not\subseteq AC\\\
T\not\subseteq BC\end{subarray}}\delta_{T}$ $\displaystyle=\sum_{T\subseteq
ABC}\delta_{T}+\sum_{T\subseteq C}\delta_{T}-\sum_{T\subseteq
AC}\delta_{T}-\sum_{T\subseteq BC}\delta_{T}$
$\displaystyle=\zeta_{\mathsf{P}}\mkern
0.5mu\delta_{ABC}+\zeta_{\mathsf{P}}\mkern
0.5mu\delta_{C}-\zeta_{\mathsf{P}}\mkern
0.5mu\delta_{AC}-\zeta_{\mathsf{P}}\mkern 0.5mu\delta_{BC}$
$\displaystyle=\zeta_{\mathsf{P}}\mkern
0.5mu\left[\delta_{ABC}+\delta_{C}-\delta_{AC}-\delta_{BC}\right]$
$\displaystyle=\zeta_{\mathsf{P}}\mkern 0.5muu_{\langle A,B\mid C\rangle}.$

(iv): This immediately follows from (ii) and the definition of probabilistic
conditional independence.

∎

Theorem 3.1 Let $\mathcal{G}=(V,E)$ be an ADMG with consistent order $\leq$.
If $P$ is a positive measure and $|M|\leq 5$ for all
$M\in\mathcal{M}(\mathcal{G})$, then the following are equivalent:

  1. i.

$\log f(x)=\sum\limits_{M\in\mathcal{M}(\mathcal{G})}\phi_{M}(x)\mkern 18.0mu$
for $\mu$-almost all $x\in\mathcal{X}$;

  2. ii.

$A\perp\mkern-9.0mu\perp B\mid C\;[\mkern 0.5mu\mathcal{G}\mkern 0.5mu]$
$\mkern 18.0mu\Rightarrow\mkern 18.0mu$ $A\perp\mkern-9.0mu\perp B\mid
C\;[\mkern 0.5muP\mkern 0.5mu]$ for every $\langle A,B\mid
C\rangle\in\mathcal{T}(V)$.

###### Proof.

This result immediately follows from the enumeration of m-connecting
factorizations for ADMG MECs in Appendix C. ∎

Proposition 3.4 Let $\mathcal{G}=(V,E)$ be an ADMG. If $|M|\leq 5$ for all
$M\in\mathcal{M}(\mathcal{G})$, then $\mu_{\mathsf{P}}\mkern
0.5mun_{\mathcal{G}}\in\mathcal{S}(V)$.

###### Proof.

This result immediately follows from the enumeration of m-connecting
factorizations for ADMG MECs in Appendix C. ∎

Lemma A.1 shows that every collider-connecting set is a parameterizing set,
and that every maximal collider-connecting set is a maximal parameterizing
set.

######  Lemma A.1.

If $\mathcal{G}$ is an ADMG, then:

  1. i.

$\mathcal{C}(\mathcal{G})\subseteq\mathcal{M}(\mathcal{G})$;

  2. ii.

$\lceil\mathcal{C}(\mathcal{G})\rceil=\lceil\mathcal{M}(\mathcal{G})\rceil$.

###### Proof.

$(i)$: If $S\in\mathcal{C}(\mathcal{G})$, then by the definitions of head and
tail, there exist $H\in\mathcal{H}(\mathcal{G})$ and
$T=\textup{tail}_{\mathcal{G}}(H)$ such that $S=HT$. Therefore, by the
definition of parameterizing sets, $S\in\mathcal{M}(\mathcal{G})$ and
$\mathcal{C}(\mathcal{G})\subseteq\mathcal{M}(\mathcal{G})$.

$(ii)$: Notably, if
$\mathcal{C}(\mathcal{G})\subseteq\mathcal{M}(\mathcal{G})$, then
$\lceil\mathcal{C}(\mathcal{G})\rceil\subseteq\mathcal{M}(\mathcal{G})$. If
$S\in\lceil\mathcal{M}(\mathcal{G})\rceil$, then by Proposition 2.9,
$S\subseteq\textup{col}_{\mathcal{G}_{A}}(B)$ where
$A=\textup{an}_{\mathcal{G}}(S)$ and $B=\textup{bar}_{\mathcal{G}}(S)$.
Moreover, $S=\textup{col}_{\mathcal{G}_{A}}(B)$ by the maximality of $S$.
Therefore, since
$\mathcal{C}(\mathcal{G}_{A})\subseteq\mathcal{C}(\mathcal{G})$,
$S\in\mathcal{C}(\mathcal{G})$ and
$\lceil\mathcal{M}(\mathcal{G})\rceil\subseteq\mathcal{C}(\mathcal{G})$. If
$\lceil\mathcal{C}(\mathcal{G})\rceil\subseteq\mathcal{M}(\mathcal{G})$ and
$\lceil\mathcal{M}(\mathcal{G})\rceil\subseteq\mathcal{C}(\mathcal{G})$, then
$\lceil\mathcal{M}(\mathcal{G})\rceil=\lceil\mathcal{C}(\mathcal{G})\rceil$. ∎