0.8pt

# Causal Discovery in Linear Latent Variable Models Subject to Measurement
Error

Yuqin Yang
Georgia Institute of
Technology Correspondence to<EMAIL_ADDRESS>Accepted at 36th
Conference on Neural Information Processing Systems (NeurIPS 2022). AmirEmad
Ghassami
Johns Hopkins University  Mohamed Nafea
University of Detroit Mercy  Negar Kiyavash
École Polytechnique
Fédérale de Lausanne  Kun Zhang
Carnegie Mellon University
MBZUAI  Ilya Shpitser
Johns Hopkins University

###### Abstract

We focus on causal discovery in the presence of measurement error in linear
systems where the mixing matrix, i.e., the matrix indicating the independent
exogenous noise terms pertaining to the observed variables, is identified up
to permutation and scaling of the columns. We demonstrate a somewhat
surprising connection between this problem and causal discovery in the
presence of unobserved parentless causes, in the sense that there is a
mapping, given by the mixing matrix, between the underlying models to be
inferred in these problems. Consequently, any identifiability result based on
the mixing matrix for one model translates to an identifiability result for
the other model. We characterize to what extent the causal models can be
identified under a two-part faithfulness assumption. Under only the first part
of the assumption (corresponding to the conventional definition of
faithfulness), the structure can be learned up to the causal ordering among an
ordered grouping of the variables but not all the edges across the groups can
be identified. We further show that if both parts of the faithfulness
assumption are imposed, the structure can be learned up to a more refined
ordered grouping. As a result of this refinement, for the latent variable
model with unobserved parentless causes, the structure can be identified.
Based on our theoretical results, we propose causal structure learning methods
for both models, and evaluate their performance on synthetic data.

##  1 Introduction

Learning causal structure among the variables of a system from observational
data has received considerable attention in the literature, since subject
matter knowledge on causal relationships is often incomplete or impossible to
obtain in many applications (Spirtes et al., , 2000; Pearl, , 2009). In many
real-life systems, not all variables of interest or all direct common causes
of those variables can be observed. This necessitates approaches for structure
learning capable of dealing with latent variables. For the case that no
a-priori restrictions on the functional form of causal mechanisms are imposed,
constraint-based algorithms such as the Fast Causal Inference (FCI) algorithm
have been proposed (Spirtes et al., , 2000). Such approaches are often unable
to identify the direction of the majority of causal connections in the system,
which motivates placing additional, often parametric, restrictions on the
generating model. One of the most commonly used restrictions is to assume that
the model is linear with non-Gaussian exogenous noise terms (Shimizu et al., ,
2006, 2011; Hoyer et al., , 2008; Glymour et al., , 2019). This generating
model leads to identification of the existence and orientation of all edges in
a causal model, assuming that no latent variables that are common causes of
two or more variables exist (Shimizu et al., , 2006, 2011). Moreover, in such
models even when latent variable common causes exist, it is still possible to
orient additional edges compared to algorithms such as FCI (Hoyer et al., ,
2008; Salehkaleybar et al., , 2020; Adams et al., , 2021).

In certain applications, although some of the variables of interest (called
underlying variables) are latent, we may have access to noisy measurements of
them (Pearl, , 2012; Kuroki and Pearl, , 2014; Zhang et al., , 2018; Saeed et
al., , 2020; Halpern et al., , 2015). In this case, conditional independence
patterns among observed variables (that are noisy measurements of underlying
variables) are different from those among the underlying (measurement-error-
free) variables. In general, constraint-based approaches to causal discovery
are not able to correct for the difference in observed independence due to the
presence of measurement error, and thus will produce erroneous edge
adjacencies and orientations. Similarly, naive application of methods based on
non-Gaussian exogenous noise assumption may also fail in recovering the
correct causal relations in the presence of measurement error. This is due to
the fact that the extra measurement noise terms break the asymmetry utilized
by those methods.

In this paper, we bring additional insight into the problem of causal
discovery under measurement error by showing a surprising connection between
linear structural equation models (SEMs) where variables are measured with
error, and linear SEMs with hidden variables. In particular, we consider two
linear SEMs. In the first model, the unobserved variables are in fact of
interest and can appear in any part of the causal structure of the system, but
we assume that noisy measurements of these unobserved variables are available.
We refer to this model as the linear SEM with measurement error (SEM-ME). The
second model does not require measurements of the latent variables, as they
are not of primary interest, yet we assume that all latent variables are root
variables, meaning that they are not causally affected by any other latent or
observed variables in the system. We refer to this model as the linear SEM
with unobserved roots (SEM-UR). It is noteworthy that assuming latent
variables are limited to be root variables does not affect the estimated total
causal effects among the observed variables (see Remark 1 in Section 2.2), and
provides a representation of a latent variable model that is consistent with
these causal effects. For this reason, this restriction is common in the
literature of causal inference (Evans, , 2016, 2018; Hoyer et al., , 2008;
Duarte et al., , 2021).

We study the identification of linear SEM-MEs and SEM-URs in a setup where the
independent exogenous noise terms that causally (directly or indirectly)
affect each observed variable can be identified. That is, the mixing matrix of
the linear system that transforms exogenous noise terms to observed variables
is identified up to permutation and scaling of the columns. This can be
satisfied, for example, if all independent exogenous noise terms are non-
Gaussian. Our first main contribution is presenting a mapping between the
linear SEM-MEs and SEM-URs, which demonstrates a correspondence between a
weighted causal diagram111A weighted causal diagram is the directed graph
corresponding to the linear model which associates the coefficient of variable
$X_{1}$ in the structural equation for $X_{2}$ to the edge from $X_{1}$ to
$X_{2}$. generated by SEM-UR and a set of weighted causal diagrams from the
SEM-ME (Theorem 1). The models in this correspondence all possess the same
mixing matrix. Consequently, any identifiability result based on the mixing
matrix for one model is applicable to the other model. This allows us to study
the problem of causal discovery in these two models together.

Additionally, we study the identifiability of linear SEM-MEs and SEM-URs, and
show how it benefits from a two-part faithfulness assumption. The first part
prevents existence of zero total causal effects of a variable on its
descendants and the second part prevents cancellation or proportionality among
specific edges. Our second main contribution is to characterize the extent of
identifiability of the causal model under our faithfulness assumption. We
demonstrate that if only the first part of the faithfulness assumption is
imposed, the model can be learned up to an equivalence class characterized by
an ordered grouping of the variables which we call _ancestral ordered
grouping_ (AOG). In this grouping, the induced graph on the variables of each
group is a star graph (see Section 4.3). Although the AOG is identified, not
all edges across the groups or the group centers (or their exogenous noise
terms) are identifiable (Theorem 2). The AOG characterization is a refined
version of the ordered grouping proposed in (Zhang et al., , 2018). We further
show that if both parts of the faithfulness assumption are imposed, the model
can be learned up to an equivalence class characterized by a more refined
ordered grouping which we call _direct ordered grouping_ (DOG). Edges across
groups can be identified under this characterization, yet the the group
centers (or their exogenous noise terms) remain unidentified (Theorem 3). This
characterization further implies that the ground-truth structure of a SEM-UR
is uniquely identifiable (Corollary 3). Lastly, we show that models in the DOG
equivalence class are strictly sparser than other models in the AOG
equivalence class (Proposition 4). We propose causal structure learning
methods for both SEM-ME and SEM-UR based on this property, and evaluate their
performance on synthetic data.

##  2 Model description

In this section, we first introduce the two models considered in this paper,
namely linear SEM-ME and SEM-UR. We then discuss a model assumption needed for
our identifiability results.

###  2.1 Linear structural equation model with measurement error (SEM-ME)

######  Definition 1 (Linear SEM-ME)

A linear SEM-ME consists of a set of “underlying” variables which can be
partitioned into unobserved underlying variables
$\mathcal{Z}=\\{Z_{1},...,Z_{p_{z}}\\}$ and observed underlying variables
$\mathcal{Y}=\\{Y_{1},...,Y_{p-p_{z}}\\}$. In addition, we have another set of
observed variables $\mathcal{U}=\\{U_{1},\cdots,U_{p_{z}}\\}$ corresponding to
the noisy measurements of $\mathcal{Z}$. The underlying variables in
$\mathcal{Z}\cup\mathcal{Y}$ can be arranged in a total (causal) order (such
that no later variable in the order can cause any earlier variable), and
variables $V_{i}\in\mathcal{Z}\cup\mathcal{Y}$ and $U_{i}\in\mathcal{U}$ are
generated as follows:

$V_{i}=\sum_{j:\;V_{j}\in Pa(V_{i})}c_{ij}V_{j}+N_{V_{i}}\quad i\in[p];\qquad
U_{i}=Z_{i}+N_{U_{i}},\quad i\in[p_{z}],$ (1)

where $[n]:=\\{1,2,\cdots,n\\}$,
$Pa(V_{i})\subseteq\mathcal{Z}\cup\mathcal{Y}$ denotes direct causes of
$V_{i}$. $N_{V_{i}}$ (resp. $N_{U_{i}}$) is the exogenous noise term (resp.
the measurement error) corresponding to $V_{i}$ (resp. $U_{i}$).

We define the weighted causal diagram of the linear SEM-ME as a weighted
directed graph where the nodes are the variables in
$\mathcal{Z}\cup\mathcal{Y}$. There is a directed edge (causal connection)
from $V_{i}$ to $V_{j}$ with weight $c_{ji}$ if and only if $c_{ji}\neq 0$,
for $V_{i},V_{j}\in\mathcal{Z}\cup\mathcal{Y}$. Because of our causal order
assumption, the causal diagram will be acyclic. We use the terms node and
variable interchangeably. The linear SEM-ME in this work is a generalization
of the linear causal model with measurement error proposed in (Zhang et al., ,
2018), in the sense that some of the underlying variables can be observed.

We define an unobserved leaf node (u-leaf node) as an unobserved underlying
variable in $\mathcal{Z}$ that does not have any children in
$\mathcal{Z}\cup\mathcal{Y}$. The rest of the underlying variables are
referred to as non u-leaf nodes (nu-leaf nodes): These include unobserved non-
leaf underlying variables, which have children in
$\mathcal{Z}\cup\mathcal{Y}$, and observed underlying variables in
$\mathcal{Y}$. Similar to the argument in (Zhang et al., , 2018), given
observed data generated by the linear SEM-ME in Equation (1), for a u-leaf
node $Z_{i}$, its exogenous noise term $N_{Z_{i}}$ is not distinguishable from
its measurement error $N_{U_{i}}$. This follows because $Z_{i}$ is not
observed, and $N_{Z_{i}}$ only influences one observed variable which is the
noisy measurement $U_{i}$. Therefore, we restrict our focus to the following
canonical form.

######  Definition 2 (Canonical form of a linear SEM-ME)

The canonical form of a linear SEM-ME is the one in which all _u-leaf_ nodes
have no exogenous noise terms. Specifically,

$\displaystyle\begin{bmatrix}Z^{L}\\\ Z^{NL}\\\
Y\end{bmatrix}=\begin{bmatrix}\mathbf{D}\\\ \mathbf{C}_{Z}\\\
\mathbf{C}_{Y}\end{bmatrix}Z^{NU}+\begin{bmatrix}0\\\ N_{Z^{NL}}\\\
N_{{Y}}\end{bmatrix},\qquad U=\begin{bmatrix}Z^{L}\\\
Z^{NL}\end{bmatrix}+\begin{bmatrix}N_{Z^{L}}+N_{U^{L}}\\\
N_{U^{NL}}\end{bmatrix},$ (2)

where $Z^{NL}$, $Z^{L}$, $Y$ are the vectors of unobserved underlying non-leaf
variables, _u-leaf_ nodes, and observed underlying variables, respectively.
$N_{Z^{NL}}$, $N_{Z^{L}}$, and $N_{Y}$ are the corresponding noise vectors.
$Z^{NU}=[Z^{NL};\;Y]$ is the vector of _nu-leaf_ nodes. $U$ is the vector of
noisy measurements and $N_{U^{NL}}$ and $N_{U^{L}}$ denote the noise vectors
corresponding to the measurements of $Z^{NL}$ and $Z^{L}$, respectively.
$\mathbf{C}$ represents the causal connections among _nu-leaf_ nodes, and can
be partitioned into $[\mathbf{C}_{Z};\;\mathbf{C}_{Y}]$ corresponding to
$[Z^{NL};\;Y]$, respectively. $\mathbf{D}$ represents the causal connections
from _nu-leaf_ nodes to _u-leaf_ nodes. Note that $\mathbf{C}$ can be arranged
into a strictly lower triangular matrix via simultaneous column and row
permutations (due to the acyclicity assumption).

###  2.2 Linear structural equation model with unobserved roots (SEM-UR)

######  Definition 3 (Linear SEM-UR)

A linear SEM-UR consists of a set of observed variables
$\mathcal{X}=\\{X_{1},\cdots,X_{q}\\}$ and another set of latent variables
$\mathcal{H}=\\{H_{1},\cdots,H_{l}\\}$. All latent variables are assumed to be
root variables (have no direct causes). The observed variables are arranged in
a causal order, and each observed variable is directly influenced by a linear
combination of other observed and latent variables, plus an independent
exogenous noise term.

$H_{i}=N_{H_{i}},\quad i\in[l];\qquad
X_{j}={\sum}_{i\in[l]}\;b_{ji}H_{i}+{\sum}_{k<j}\;a_{jk}X_{k}+N_{X_{j}},\qquad
j\in[q].$ (3)

We define the weighted causal diagram of the linear SEM-UR as a directed graph
where the nodes are the observed and latent variables in
$\mathcal{X}\cup\mathcal{H}$. There is a causal connection from $X_{i}$ (resp.
$H_{i}$) to $X_{j}$ with weight $a_{ji}$ (resp. $b_{ji}$) if and only if
$a_{ji}$ (resp. $b_{ji}$) $\neq 0$. Because of our causal order assumption,
the causal diagram will be acyclic. Note that unlike in (Hoyer et al., , 2008)
and (Salehkaleybar et al., , 2020), we consider a broader model which allows
latent variables to have a single observed child. However, unlike the works
considering relations among latent variables (Adams et al., , 2021; Xie et
al., , 2020; Cai et al., , 2019; Xie et al., , 2022), we restrict all latent
variables to roots; see Remark 1.

A linear SEM-UR can be written in the following matrix form:

$\displaystyle H=N_{H};\qquad X=\mathbf{B}H+\mathbf{A}X+N_{X},$ (4)

where $X=[X_{1}\;\cdots\;X_{q}]^{\top}$ and $H=[H_{1}\;\cdots\;H_{l}]^{\top}$
are the vectors of observed and latent variables, respectively.
$N_{X}=[N_{X_{1}}\;\cdots\;N_{X_{q}}]^{\top}$ and
$N_{H}=[N_{H_{1}}\;\cdots\;N_{H_{l}}]^{\top}$ represent the vectors of
independent noise terms associated with $X$ and $H$, respectively.
$\mathbf{B}$ represents the causal connections from latent to observed
variables, and $\mathbf{A}$ represents the causal connections among observed
variables, which can be assumed to be a strictly lower-triangular matrix (due
to the acyclicity assumption).

###### Remark 1

There exist works aiming to find the causal relations among the latent
variables (as well as their relations with the measured variables) (Silva et
al., , 2006; Xie et al., , 2020; Cai et al., , 2019; Adams et al., , 2021; Xie
et al., , 2022). Our definition of a linear SEM-UR requires all the latent
variables to be parentless. This assumption is common in the literature of
causal inference, as it does not restrict the feasible total causal effects
(i.e., sum of products of path coefficients) among the observed variables
(Evans, , 2016, 2018; Duarte et al., , 2021). Specifically, let us start from
a general linear latent variable model in which some latent variables have
parents. Hoyer et al.,  (2008) proposed an algorithm which maps such general
model to one in which latent variables are parentless. They showed that the
resulting model is observationally and causally equivalent to the original
model, i.e., the joint distributions of observed variables are identical, and
all causal effects of observed variables on other observed variables are
identical in the models before and after the mapping.

###  2.3 Separability assumption

For both models in Sections 2.1 and 2.2, we assume that the noise components
can be separated from observations (i.e., the mixing matrices are
recoverable). We first describe the mixing process for each of the two models,
and then state our separability assumption.

From Equation (2), we can write all underlying variables in the linear SEM-ME
in terms of the independent noise terms, as follows.

$\displaystyle\begin{bmatrix}Z^{L}\\\ Z^{NL}\\\
Y\end{bmatrix}=\mathbf{W}^{ME}\begin{bmatrix}N_{Z^{NL}}\\\
N_{Y}\end{bmatrix},\qquad\text{where}\quad\mathbf{W}^{ME}=\begin{bmatrix}\mathbf{D}(\mathbf{I}-\mathbf{C})^{-1}\\\
(\mathbf{I}-\mathbf{C})_{Z}^{-1}\\\
(\mathbf{I}-\mathbf{C})_{Y}^{-1}\end{bmatrix}.$ (5)

$\mathbf{I}$ is the identity matrix, and $(\mathbf{I}-\mathbf{C})_{Z}^{-1}$
and $(\mathbf{I}-\mathbf{C})_{Y}^{-1}$ represent the rows of
$(\mathbf{I}-\mathbf{C})^{-1}$ corresponding to $Z^{NL}$ and $Y$,
respectively. Using the relation between $U$ and $Z$ in Equation (2), the two
types of observed variables, i.e., measurements $U$ and observed underlying
variables $Y$, can be written as

$\displaystyle\begin{bmatrix}U\\\
Y\end{bmatrix}=\underbrace{\begin{bmatrix}~{}\mathbf{W}^{ME}&\begin{matrix}\mathbf{I}\\\
\mathbf{0}\end{matrix}~{}\end{bmatrix}}_{\mathbf{W}}\begin{bmatrix}N_{Z^{NL}}\\\
N_{Y}\\\ N_{Z^{L}}+N_{U^{L}}\\\ N_{U^{NL}}\end{bmatrix}.$ (6)

We refer to $\mathbf{W}$ as the overall mixing matrix of the system. Given any
column permuted and rescaled version of $\mathbf{W}$, we can recover matrix
$\mathbf{W}^{ME}$ by removing the submatrix
$[\mathbf{I}\;\;\mathbf{0}]^{\top}$ of size $p\times p_{z}$ corresponding to
$U$. Recall that $p_{z}$ is the cardinality of $Z$ (which is the same as the
cardinality of $U$).

Similarly, according to Equation (4), observed variables in the linear SEM-UR
can be written in terms of the independent noise terms as

$\displaystyle X=\mathbf{W}^{UR}\begin{bmatrix}N_{H}\\\
N_{X}\end{bmatrix},\qquad\text{where}\quad\mathbf{W}^{UR}=\left[(\mathbf{I}-\mathbf{A})^{-1}\mathbf{B}\quad(\mathbf{I}-\mathbf{A})^{-1}\right].$
(7)

######  Assumption 1 (Separability)

The linear SEM-ME (resp. linear SEM-UR) is separable, that is, the mixing
matrix $\mathbf{W}^{ME}$ in Equation (5) (resp. $\mathbf{W}^{UR}$ in Equation
(7)) can be recovered from observations of $[U;\;Y]$ (resp. $X$) up to
permutation and scaling of its columns.

Separability assumption states that for every observed mixture, the
independent exogenous noise terms pertaining to this mixture can be separated,
i.e., the mixing matrix can be recovered up to permutation and scaling of its
columns. An example of a setting where this assumption holds is when all
exogenous noises are non-Gaussian. In this case, if the model satisfies the
requirement in (Eriksson and Koivunen, , 2004, Theorem 1) (SEM-ME always
does), overcomplete Independent Component Analysis (ICA) can be used to
recover the mixing matrix up to permutation and scaling of its columns.
Another example where separability assumption is satisfied is the setup in
which the noise terms are piecewise constant functionals satisfying a set of
mild conditions (Behr et al., , 2018). On the other hand, an example where
this assumption is violated is when all exogenous noise terms have Gaussian
distributions. In this case, the mixing matrix can only be recovered up to an
orthogonal transformation.

##  3 Mapping between the weighted graphs of the models for identifiability

A key observation in this work is that there exists a mapping between the
weighted causal diagrams of the introduced SEM-ME and SEM-UR, which leads to
the corresponding mixing matrices $\mathbf{W}^{ME}$ and $\mathbf{W}^{UR}$
being transposes of one another.

Define the mapping $\varphi$ from the set of weighted causal diagrams of
linear SEM-URs, denoted by $\mathcal{M}^{UR}$, to the set of weighted causal
diagrams of canonical linear SEM-MEs, denoted by $\mathcal{M}^{ME}$, where for
each diagram $M\in\mathcal{M}^{UR}$, $\varphi(M)\subset\mathcal{M}^{ME}$ is
constructed as follows: (a) Replace each latent variable in $M$ with a $Z$
variable. (b) Replace each observed root variable in $M$ with a $Y$ variable.
(c) Replace the rest of the observed variables in $M$ with either $Z$ or $Y$
variables. (d) Reverse all the edges in $M$. Note that $\varphi(M)$
encompasses a set of models, corresponding to the possible choices in step
(c).

Similarly define the mapping $\phi$ from the set $\mathcal{M}^{ME}$ to the set
$\mathcal{M}^{UR}$, where for each diagram $M^{\prime}\in\mathcal{M}^{ME}$,
$\phi(M^{\prime})\in\mathcal{M}^{UR}$ is constructed as follows. (a) Replace
each u-leaf variable in $M^{\prime}$ with a latent variable. (b) Replace the
rest of the variables in $M^{\prime}$ with observed variables. (c) Reverse all
the edges in $M^{\prime}$. Note that from the definition of the two mappings,
for any given $M\in\mathcal{M}^{UR}$, $M=\phi(\varphi(M))$. For any given
$M^{\prime}\in\mathcal{M}^{ME}$, $M^{\prime}\in\varphi(\phi(M^{\prime}))$.

###### Theorem 1

Let $M\in\mathcal{M}^{UR}$ with mixing matrix $\mathbf{W}^{UR}(M)$ and
$M^{\prime}$ be a corresponding element in $\mathcal{M}^{ME}$ with mixing
matrix $\mathbf{W}^{ME}(M^{\prime})$, where $M^{\prime}\in\varphi(M)$ and
$M=\phi(M^{\prime})$. Then there exist a permutation of the columns of
$\mathbf{W}^{UR}(M)$, denoted by $\tilde{\mathbf{W}}^{UR}(M)$, and a
permutation of the columns of $\mathbf{W}^{ME}(M^{\prime})$, denoted by
$\tilde{\mathbf{W}}^{ME}(M^{\prime})$, which satisfy
$\tilde{\mathbf{W}}^{ME}({M^{\prime}})=(\tilde{\mathbf{W}}^{UR}(M))^{\top}$.

The proofs of all the results are provided in the Appendix. Note that as it
can be seen from the proof of Theorem 1, whether the nu-leaf variables, that
are non-leaf in the SEM-ME, are observed or not does not change the
corresponding mixing matrix.

$X_{3}$$X_{1}$$X_{2}$$H$$a$$c$$b$$d$(a) Linear SEM-
UR$\begin{bmatrix}0&1&0&0\\\ d&a&1&0\\\ bd+c&ab&b&1\\\ \end{bmatrix}$
$\mathbf{W}^{UR}$

$Z_{L}$$Y_{1}$$Z_{3}/Y_{3}$$Z_{2}/Y_{2}$$a$$c$$b$$d$(b) Linear SEM-
ME$\begin{bmatrix}0&d&bd+c\\\ 0&1&b\\\ 0&0&1\\\ 1&a&ab\end{bmatrix}$
$\mathbf{W}^{ME}$

Figure 1: Example explaining the mapping.

###### Remark 2

The mapping introduced here is between a weighted diagram in SEM-UR and a set
of weighted diagrams in SEM-ME. The elements of the set in fact correspond to
different settings of the non-leaf underlying variables being observed or not.
Note that in most applications, it is clear to the researcher whether an
underlying variable is observed or measured with error. Therefore, only one
element of the set is relevant to the application and the set reduces to a
single element. Consequently, in our identifiability results, without loss of
generality, we assume the set is a singleton.

Theorem 1 implies that under separability assumption, any identifiability
result based on the mixing matrix for one model is applicable to the other
model, by reversing all edges. This allows us to study the problem of causal
discovery of these two models simultaneously.

###### Example 1

Consider the linear SEM-UR in Figure 1(a) comprised of three observed and one
latent variable (denoted by a single circle). The corresponding linear SEM-ME
under the mapping $\varphi$ is shown in Figure 1(b). Specifically, (i) the
latent variable $H$ is mapped to the _u-leaf_ variable $Z_{L}$ (denoted by a
double circle); (ii) the observed root $X_{1}$ is mapped to the observed
underlying variable $Y_{1}$; and (iii) observed variables $X_{2}$ and $X_{3}$
could be mapped to either observed or unobserved underlying variables; hence
the UR graph will be mapped to a set of 4 graphs in the ME model. The mixing
matrices for both models are shown in Figure 1. It can be readily seen that
there exists a permutation of the columns of $\mathbf{W}^{UR}$, which is equal
to the transpose of $\mathbf{W}^{ME}$.

##  4 Identifiability of models

In this section, we study the extent of identifiability of linear SEM-ME and
SEM-UR under the separability assumption. We consider both a weaker notion of
structure identification, where only the graph structure of the model is
obtained, and a stronger notion of model identification where, in addition to
the graph structure, model parameters are recovered as well. In Section 4.1,
we propose SEM-ME and SEM-UR faithfulness assumptions, which consist of two
parts, the first of which is identical to the conventional faithfulness in
linear causal models. We first discuss model identifiability under
conventional faithfulness (i.e., the first part of our assumptions), which can
be characterized by _ancestral ordered grouping_ (AOG) of the variables,
explained in Section 4.2. Next, under both parts of our proposed faithfulness
assumptions, the extent of identifiability can be characterized by _direct
ordered grouping_ (DOG) of the variables, explained in Section 4.3. This leads
to a subsequent result on structure identifiability for SEM-UR. In Section
4.4, we show that the DOG characterization possesses a sparsity property,
which can be used to construct recovery algorithms for both models.

###  4.1 Faithfulness assumption

######  Assumption 2 (SEM-ME faithfulness)

(a) The total causal effect of any underlying variable on its descendant is
not equal to zero. (b) For each variable $V$ in a SEM-ME, the causal effect of
parents of $V$ on $V$ cannot be replicated by fewer or equal variables due to
fine tuning of the parameters. (See Appendix B.1 for the formal statement.)

######  Assumption 3 (SEM-UR faithfulness)

(a) The total causal effect of any observed or latent variable on its
descendant is not equal to zero. (b) For each variable $V$ in a SEM-UR, the
causal effect of $V$ on children of $V$ cannot be replicated by fewer or equal
variables due to fine tuning of the parameters. (See Appendix B.1 for the
formal statement.)

Assumptions 2 _(a)_ and 3 _(a)_ are identical to conventional faithfulness in
linear causal models. They require that when multiple causal paths exist from
any (observed or unobserved) variable to its descendants, their combined
effect (i.e., sum of products of path coefficients) is not equal to zero, see
(Spirtes et al., , 2000). Assumptions 2 _(b)_ and 3 _(b)_ prevent certain path
cancellation or parameter proportionality. Importantly, Assumptions 2 and 3
are violated with probability zero if all model coefficients are drawn
randomly and independently from continuous distributions; see Appendix B.3 for
the proof. As an example for violation of Assumption 2 _(b)_ , consider the
linear SEM-ME generated by the graph in Figure 2(a), which satisfies
Assumption 2 _(a)_. However, we can write $Z_{4}$ as $(b+c)Z_{2}+N_{Z_{3}}$,
which is caused by the path cancellation of the triangle
$(Z_{1},Z_{3},Z_{4})$. This means that that the causal effect of $Z_{1}$ and
$Z_{2}$ on $Z_{4}$ can be summarized by $Z_{2}$ alone. Therefore, the model
violates Assumption 2 _(b)_. Lastly, Assumption 3 is strictly weaker than
bottleneck faithfulness in (Adams et al., , 2021); see Appendix B.4 for the
proof. Please refer to Appendix B for more discussion about our faithfulness
assumption and Appendix D for a detailed comparison between our
identifiability results and the results in (Adams et al., , 2021).

$Z_{1}$$Z_{2}$$Z_{3}$$Z_{4}$$a$$b$$-d$$1$$c$$d$(a)

$Z_{1}$$Z_{2}$$Z_{4}$$Z_{3}$$a$$b+c$$d$$1$$-c$(b)

$~{}\begin{bmatrix}Z_{1}\\\ Z_{2}\\\ Z_{3}\\\
Z_{4}\end{bmatrix}=\begin{bmatrix}1&0&0\\\ a&1&0\\\ ab+d&b&1\\\
a(b+c)&b+c&1\end{bmatrix}\begin{bmatrix}N_{Z_{1}}\\\ N_{Z_{2}}\\\
N_{Z_{3}}\end{bmatrix}$

Figure 2: Example explaining AOG and SEM-ME faithfulness assumption.

###  4.2 Ancestral ordered grouping

We first study the extent of identifiability of the models only under
conventional faithfulness, i.e., Assumptions 2 _(a)_ and 3 _(a)_.

######  Definition 4 (Ancestral ordered grouping (AOG))

The AOG of a SEM-ME (resp. SEM-UR) is a partition of
$\mathcal{Z}\cup\mathcal{Y}$ (resp. $\mathcal{H}\cup\mathcal{X}$) into
distinct sets. This partition is described as follows: (1) Assign each _nu-
leaf_ node (resp. observed node) to a distinct group. (2) SEM-ME: For each _u-
leaf_ node $Z_{j}\in\mathcal{Z}$, if there exists one parent $V_{i}$ such that
$Z_{j}$ has no other parents, or all other parents of $Z_{j}$ are also
ancestors of $V_{i}$, assign $Z_{j}$ to the same group as $V_{i}$. Otherwise,
assign $Z_{j}$ to a separate group (with no _nu-leaf_ node). (2) SEM-UR: For
each latent variable $H_{j}$, if there exists one child $X_{i}$ such that
$H_{j}$ has no other children, or all other children of $H_{j}$ are also
descendants of $X_{i}$, assign $H_{j}$ to the same group as $X_{i}$.
Otherwise, assign $H_{j}$ to a separate group (with no observed variable).

######  Definition 5 (AOG equivalence class)

The AOG equivalence class of a linear SEM-ME (resp. SEM-UR) is a set of models
where the elements of this set all have the same mixing matrix (up to
permutation and scaling) and same ancestral ordered groups.

For example, the two models represented by the graphs in Figure 2 have the
same mixing matrix and ancestral ordered groups. The elements of an AOG
equivalence class possess the following property.

###### Proposition 1

Models in the same AOG equivalence class have the same causal order among the
groups, but not necessarily all the same edges across the groups.

The AOG characterization is a refined version of the original ordered grouping
proposed in (Zhang et al., , 2018), where no variables in later groups cause
variables in earlier groups. Yet, the grouping introduced in that work is
order dependent and hence in general not unique. Moreover, it does not always
characterize the extent of identifiability. Our AOG characterization also uses
a similar idea as the learning approach in (Salehkaleybar et al., , 2020);
however, that work allows for latent variables which have parents and in
general does not recover the full structure. Note that the AOG can be
recovered based on the support of the mixing matrix under Assumption 2 _(a)_
(or 3 _(a)_). Please refer to Appendix A for more details.

According to Definition 4, there is at most one nu-leaf node in each ancestral
ordered group of a SEM-ME. Furthermore, each u-leaf node $Z_{j}$ is assigned
to the ancestral ordered group of at most one of its parents: Following the
true causal order among nu-leaf nodes, only the last parent of $Z_{j}$ may
have the same ancestor set. Hence, if a group has more than one node, then
there must be exactly one nu-leaf node, and the rest of the nodes are u-leaf
nodes which are children of this node. This concludes that the induced
structure on each ancestral ordered group is a star graph. Similar property
holds for SEM-UR. Define the center of the ancestral ordered group as the nu-
leaf node (resp. the observed node), or the u-leaf node (resp. latent node) if
the group is of size one. The following result illustrates that fixing the
center of the ancestral ordered groups for SEM-ME, and fixing the exogenous
noise term of the center of the ancestral ordered groups as well as the choice
of scaling and permutation of the columns of $\mathbf{B}$ for SEM-UR, leads to
unique identification of the models.

###### Proposition 2

(i) Models in an AOG equivalence class of a SEM-ME can be identified by the
choice of the centers of the groups. That is, for a given choice of the
centers, there is only one corresponding model. (ii) Models in an AOG
equivalence class of a SEM-UR can be identified (up to the permutation and
scaling of the columns of $\mathbf{B}$ in (4)) by the choice of the exogenous
noise terms associated to the centers of the groups. That is, for a given
assignment of the exogenous noise terms, all corresponding models have the
same $\mathbf{A}$ in (4), and have the same $\mathbf{B}$ up to permutation and
scaling of the columns.

Equipped with Proposition 2, we are now ready to state our identifiability
results for SEM-ME and SEM-UR under Assumptions 2 _(a)_ and 3 _(a)_),
respectively.

###### Theorem 2

Under Assumptions 1 and 2(a) (resp. 3(a)), the linear SEM-ME (resp. SEM-UR)
can be identified up to its AOG equivalence class.

###### Corollary 1

(i) Denote the AOG of a linear SEM-ME (resp. SEM-UR) as
$\\{\mathcal{G}^{(g)}\\}_{g\in[g_{k}]}$, where $g_{k}$ is the number of
ancestral ordered groups. The size of the AOG equivalence class, described in
Theorem 2, is equal to $\prod_{g\in[g_{k}]}|\mathcal{G}^{(g)}|$. (ii) Under
Assumptions 1 and 2(a), a linear SEM-ME can be uniquely identified if and only
if no _u-leaf_ node has precisely the same ancestors as any _nu-leaf_ node.
(iii) Under Assumptions 1 and 3(a), a linear SEM-UR can be identified up to
the permutation and scaling of the columns of $\mathbf{B}$ if and only if no
latent variable has precisely the same descendants as any observed variable.

As stated in Theorem 2, in general, the edges across the groups cannot all be
discovered and the centers of the groups (or their corresponding exogenous
noise terms) are not identifiable. This is due to the fact that when only
Assumption 2 _(a)_ holds, certain path cancellation or parameter
proportionality in the model can occur. This is illustrated in the following
example.

###### Example 2

Consider the SEM-ME generated by causal graph shown in Figure 2(a). The AOG is
$\\{\\{Z_{1}\\},\\{Z_{2}\\},\\{Z_{3},Z_{4}\\}\\}$. Because either $Z_{3}$ or
$Z_{4}$ can be the center of the last group, the AOG equivalence class
includes the ground-truth and the model represented by Figure 2(b). Since both
models have the same mixing matrix, an identification algorithm merely based
on the mixing matrix and Assumption 2(a) cannot distinguish these two models.
Note that not only can we not learn the direction of the edge in group
$\\{Z_{3},Z_{4}\\}$, but also the existence of some of the edge across groups,
such as $Z_{1}\rightarrow Z_{4}$, cannot be established in the ground-truth
because Assumption 2(b) is violated.

###  4.3 Identifiability of the model up to equivalence classes

Under Assumptions 1 and 2 (resp. 3), the extent of identifiability of a SEM-ME
(resp. SEM-UR) can be characterized by the direct ordered grouping defined in
Definition 6 below. We first present two conditions that are used to implement
the DOG. We then give the formal definition of DOG. In the following, we use
$Ch(V)$ to denote the set of children of variable $V$ in the causal diagram.

######  Condition 1 (SEM-ME edge identifiability)

For a given edge from an _nu-leaf_ node $V_{i}$ to a _u-leaf_ node $Z_{l}$, at
least one of the following two conditions is satisfied: (a)
$Pa(Z_{l})\setminus\\{V_{i}\\}$ is not a subset of $Pa(V_{i})$. That is, there
exists another parent $V_{j}$ of $Z_{l}$, which is not a parent of $V_{i}$.
(b) $Pa(Z_{l})$ is not a subset of $\cap_{V_{k}\in
Ch(V_{i})\setminus\\{Z_{l}\\}}Pa(V_{k})$. That is, there exists a child
$V_{k}$ of $V_{i}$ and a parent $V_{j}$ of $Z_{l}$ such that $V_{j}$ is not a
parent of $V_{k}$.

######  Condition 2 (SEM-UR edge identifiability)

For a given edge from a latent variable $H_{l}$ to an observed variable
$X_{i}$, at least one of the following two conditions is satisfied: (a)
$Ch(H_{l})\setminus\\{X_{i}\\}$ is not a subset of $Ch(X_{i})$. That is, there
exists another observed child $X_{j}$ of $H_{l}$, which is not a child of
$X_{i}$. (b) $Ch(H_{l})$ is not a subset of $\cap_{X_{k}\in
Pa(X_{i})\setminus\\{H_{l}\\}}Ch(X_{k})$. That is, there exists an observed
(or latent) parent $X_{k}$ (or $H_{k}$) of $X_{i}$ and a child $X_{j}$ of
$H_{l}$ such that $X_{j}$ is not a child of $X_{k}$ (or $H_{k}$).

Figure 3(b) demonstrates an example of a graph structure which satisfies
Assumption 2 while containing an edge which violates Condition 1. Condition 1
is an equivalent formulation of the conditions for unique identifiability
derived in (Zhang et al., , 2018). In that work, Zhang et al. proved that a
linear SEM-ME can be uniquely recovered if Condition 1 is satisfied for every
edge from an nu-leaf node to a u-leaf node.222Note that in their model, Zhang
et al. assumed that all the underlying variables are unobserved. They also
conjectured that this condition is necessary for identifiability. We prove
their conjecture here under a slightly different faithfulness assumption.
Furthermore, we demonstrate that the conditions can be used to characterize an
equivalence class of the models which characterizes the extent of
identifiability under Assumptions 1 and 2; the same assertion holds for linear
SEM-UR. This characterization is done based on the notion of direct ordered
grouping, defined as follows.

######  Definition 6 (Direct ordered grouping (DOG))

The DOG of a linear SEM-ME (resp. SEM-UR) is a partition of
$\mathcal{Z}\cup\mathcal{Y}$ (resp. $\mathcal{H}\cup\mathcal{X}$) into
distinct sets. This partition is described as follows:
(1) Assign each _nu-leaf_ node (resp. observed node) to a distinct ordered
group.
(2) SEM-ME: For each _u-leaf_ node $Z_{j}\in\mathcal{Z}$, if there exists one
parent $V_{i}$ such that the edge from $V_{i}$ to $Z_{j}$ violates Condition
1, assign $Z_{j}$ to the same ordered group as $V_{i}$. Otherwise, assign
$Z_{j}$ to a separate ordered group (with no _nu-leaf_ node).
(2) SEM-UR: For each latent variable $H_{j}$, if there exists one child
$X_{i}$ such that the edge from $H_{j}$ to $X_{i}$ violates Condition 2,
assign $H_{j}$ to the same ordered group as $X_{i}$. Otherwise, assign $H_{j}$
to a separate ordered group (with no observed variable).

######  Definition 7 (DOG equivalence class)

The DOG equivalence class of a linear SEM-ME (resp. SEM-UR) is a set of models
where the elements of this set all have the same mixing matrix (up to
permutation and scaling) and same direct ordered groups.

For example, the two models represented by the graphs in Figure 2 have the
same mixing matrix, but different direct ordered groups. We have the following
property regarding elements of an DOG equivalence class.

###### Proposition 3

Models in the same DOG equivalence class have the same edges across the
groups.

The counterpart of Proposition 2 holds for the case of direct ordered groups
as well and we avoid repeating it. Based on that counterpart, we have the
following result regarding identifiability of linear SEM-ME and SEM-UR under
Assumptions 2 and 3, respectively.

###### Theorem 3

Under Assumptions 1 and 2 (resp. 3), the linear SEM-ME (resp. SEM-UR) can be
identified up to its DOG equivalence class.

Theorem 3 states that we can learn the structure among the groups, but the
center of the group (or the noise term corresponding to it) will remain
unidentified. Unlike the case of the AOG equivalence class, all the edges
across the groups will be identified. That is, the choice of center does not
change the edges across groups in DOG equivalence class, while it may change
the edges in AOG equivalence class. Further, the sizes of the direct ordered
groups are smaller than the sizes of the ancestral ordered groups. As an
example, for the model shown in Figure 2(b), all direct ordered groups are of
size one.

###### Corollary 2

(i) The counterpart of Corollary 1(i) is true for the case of DOG as well and
we do not repeat it here. (ii) Under Assumptions 1 and 2, a SEM-ME can be
uniquely identified if and only if for every edge from an _nu-leaf_ node to a
_u-leaf_ node, Condition 1 is satisfied. (iii) Under Assumptions 1 and 3, a
SEM-UR can be identified up to the permutation and scaling of the columns of
$\mathbf{B}$ if and only if for every edge from a latent variable to an
observed variable, Condition 2 is satisfied.

Identifiability of the structure of the SEM-UR. As shown in Theorem 3, for a
SEM-UR, the only undetermined part in the DOG equivalence class pertains to
the assignment of the exogenous noises and coefficients, but the structure is
the same. Consequently, if only the identification of the structure without
weights is of interest, Assumptions 1 and 3 are sufficient. See Figure 3(a)
for an example of two DOG equivalent SEM-UR s. This identifiability result is
summarized in the following corollary.

###### Corollary 3

Under Assumptions 1 and 3, the structure of a SEM-UR can be uniquely
recovered.

$X_{1}$$X_{2}$$H$$N_{X_{1}}$$N_{X_{2}}$$N_{H}$$b$$1$$a$(a) Equivalence class
of a SEM-UR$X_{1}$$X_{2}$$H$$N_{H}$$N_{X_{2}}$$N_{X_{1}}$$-b$$1$$a+b$

$N_{Z_{1}}$$N_{Z_{2}}$$Z_{2}$$Z_{1}$$Z_{3}$$1$$b$$a$(b) Equivalence class of a
SEM-ME$N_{Z_{1}}$$N_{Z_{2}}$$Z_{3}$$Z_{2}$$Z_{1}$$1$$-b$$a+b$

Figure 3:  DOG Equivalence classes.

###  4.4 Recovery algorithm

We note that our faithfulness assumption implies that the ground-truth model
has strictly fewer edges than any model that has the same mixing matrix and
satisfies conventional faithfulness (i.e., in the AOG equivalence class) but
does not belong to the DOG equivalence class. This property can be leveraged
to recover the ground-truth model or a member of its DOG equivalence class.

###### Proposition 4

Suppose a SEM-ME (resp. SEM-UR) satisfies Assumptions 1 and 2 (resp. 3). Any
model that belongs to the same AOG equivalence class but does not belong to
the same DOG equivalence class has strictly more edges than any member in the
DOG equivalence class.

The steps of our recovery algorithm are as follows: (1) Recover the mixing
matrix $\mathbf{W}^{ME}$ (resp. $\mathbf{W}^{UR}$) from observational data.
(2) Return the AOG of the true model by comparing the support across different
rows/columns in $\mathbf{W}^{ME}$ (resp. $\mathbf{W}^{UR}$). See Appendix A.2
for details and pseudo-code for AOG recovery. (3) For all possible choices of
the center (resp. noise term associated to the center) of each ancestral
ordered group, find a choice that leads to the graph with fewest number of
edges in the recovery output (see the proof of Lemma 1).

##  5 Simulations

We evaluated the performance of our recovery algorithm on randomly generated
linear SEM-MEs and SEM-URs with different number of variables.333Our code is
available at: https://github.com/Yuqin-Yang/SEM-ME-UR. We considered two
cases: (1) when a noisy version of the mixing matrix is given, where the noise
is Gaussian with different choices of variance denoted by $\texttt{d}^{2}$,
and (2) when synthetic data comes from a linear generating model with non-
Gaussian noises with different sample sizes, and the mixing matrix needs to be
estimated. We used  the Reconstruction ICA algorithm (Le et al., , 2011) as
our overcomplete ICA method. For Case (1), we compared our recovery method
(which we refer to as DOG) with an approach based on AOG equivalence class
(similar to the learning method in (Salehkaleybar et al., , 2020)). In
addition to the AOG method, for Case (2), we compared our method with ICA-
LiNGAM (Shimizu et al., , 2006). Note that the ICA-LiNGAM method is not
designed for systems with latent variables, but benefits from strong
performance for recovering the mixing matrix in causally sufficient settings.
The goal of this comparison was to demonstrate the necessity of using methods
designed specifically to handle latent variables.

We compared the recovery of the adjacency matrix to the ground-truth, where we
used normalized structural Hamming distance (SHD/Edge) and F1 score as our
performance metrics. Our results for Cases (1) and (2) are shown in top and
bottom two rows in Figure 4, respectively. As seen in these figures, our
recovery algorithm outperforms recovery algorithm based on AOG. In particular,
our method recovers the structure in SEM-UR model, and can recover part of the
structure in SEM-ME that is shared among DOG equivalence classes. Moreover,
both methods outperform ICA-LiNGAM. Please refer to Appendix E for additional
results and analysis.

Figure 4: Simulation results for Case (1), noisy mixing matrix (with noise
variance d2), and Case (2), raw observational data (with sample size N$\cdot
p$ for ME and N$\cdot q$ for UR). In Case (1), x-axis corresponds to
$|\mathcal{Y}\cup\mathcal{Z}|$ in SEM-ME, and $|\mathcal{H}\cup\mathcal{X}|$
in SEM-UR. In Case (2), x-axis corresponds to $|\mathcal{Y}\cup\mathcal{U}|$
in SEM-ME, and $|\mathcal{X}|$ in SEM-UR. We compare the recovery of both
adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ (cf. Equation (4)) for SEM-
UR. Lower SHD/Edge value and higher F1 score indicate better performances.

##  6 Conclusion and Discussion

In real-world applications, we do not observe the exact value of all relevant
variables; the measurements of some variables are prone to errors, or some
other variables cannot be observed altogether. For example, in neuroscience
and genomics, measured brain signals obtained by functional magnetic resonance
imaging (fMRI) or the measured gene expression using RNA sequencing usually
contain errors through the measurement process (Saeed et al., , 2020; Zhang et
al., , 2018). Other examples include responses to psychometric questionnaires
where the questions represent noisy views of various traits (Adams et al., ,
2021; Scheines and Ramsey, , 2016), and returns in stock market, where they
may be confounded by several unmeasured economic and political factors (Adams
et al., , 2021).

In this work, we considered the problem of causal discovery in setups with
such challenges, particularly under two settings: (1) in the presence of
measurement error, and (2) with unobserved parentless causes. Unlike previous
work, our proposed SEM-ME allows for applications containing a mixture of
variables measured exactly (without error) or measured with error. We
demonstrated a mapping between these two models that preserves their mixing
matrix. Based on this mapping, we derived identifiability results for both
models under different faithfulness assumptions, and proposed structure
learning algorithms. Our results further implied conditions for unique
identifiability of the structure in SEM-UR. These conditions do not pose any
restrictions on the graphical model, and hence significantly relax the
existing graphical conditions in the literature (Salehkaleybar et al., , 2020;
Adams et al., , 2021; Wang and Drton, , 2020; Chen et al., , 2021).

Our results have several implications in the literature of causal discovery
including the following: The mapping proposed in our work between linear SEM-
ME and SEM-UR allows us to translate identifiability results for one model to
the other. We note that linear SEM-UR has been widely studied in the
literature, while only a few works considered linear SEM-ME. Therefore, an
important implication of our work is that the introduced mapping can be
utilized to fill the gaps for the less studied model. Another important
implication of our result is that it can be used for evaluating new
algorithms: We showed that under two different faithfulness assumptions, the
model can only be identified up to AOG and DOG equivalence classes. This
result provides the extent of identifiability, and can serve as a basis for
characterizing theoretical guarantees such as consistency of new algorithms.
Finally, we showed in Proposition 4 that under our faithfulness assumptions,
the true generating model is always sparser than any other model in the same
AOG equivalence class (of the ground-truth) but does not belong to the DOG
equivalence class. This serves as a ground for positing sparsity assumptions
that appear frequently in the literature without rigorous justification.

Similar to other causal discovery methods which are based on the mixing
matrix, the performance of our proposed recovery algorithms relies on the
accuracy of the utilized mixing matrix estimation approach. Hence, the
recovered structure should be interpreted with caution if the mixing matrix
estimation approach is unreliable. Devising more accurate approaches for
estimating the mixing matrix, as well as extending the method proposed in this
work to non-linear models are important directions of future research.

## Acknowledgments and Disclosure of Funding

Negar Kiyavash’s research was in part supported by the Swiss National Science
Foundation under NCCR Automation, grant agreement 51NF40_180545 and Swiss SNF
project 200021_204355 /1. Kun Zhang was partially supported by NIH under
Contract R01HL159805, by the NSF-Convergence Accelerator Track-D award
#2134901, by a grant from Apple Inc., and by a grant from KDDI Research Inc.
Ilya Shpitser was supported by grants ONR N00014-21-1-2820, NSF 2040804, NSF
CAREER 1942239 and NIH R01 AI127271-01A1.

## References

  * Adams et al., (2021) Adams, J., Hansen, N., and Zhang, K. (2021).  Identification of partially observed linear causal models: Graphical conditions for the non-gaussian and heterogeneous cases.  Advances in Neural Information Processing Systems, 34.
  * Behr et al., (2018) Behr, M., Holmes, C., Munk, A., et al. (2018).  Multiscale blind source separation.  The Annals of Statistics, 46(2):711–744.
  * Cai et al., (2019) Cai, R., Xie, F., Glymour, C., Hao, Z., and Zhang, K. (2019).  Triad constraints for learning causal structure of latent variables.  In Advances in Neural Information Processing Systems (NeurIPS).
  * Chen et al., (2021) Chen, W., Zhang, K., Cai, R., Huang, B., Ramsey, J., Hao, Z., and Glymour, C. (2021).  Fritl: A hybrid method for causal discovery in the presence of latent confounders.  arXiv preprint arXiv:2103.14238.
  * Duarte et al., (2021) Duarte, G., Finkelstein, N., Knox, D., Mummolo, J., and Shpitser, I. (2021).  An automated approach to causal inference in discrete settings.  arXiv preprint arXiv:2109.13471.
  * Efron and Tibshirani, (1994) Efron, B. and Tibshirani, R. J. (1994).  An introduction to the bootstrap.  CRC press.
  * Eriksson and Koivunen, (2004) Eriksson, J. and Koivunen, V. (2004).  Identifiability, separability, and uniqueness of linear ICA models.  IEEE signal processing letters, 11(7):601–604.
  * Evans, (2016) Evans, R. J. (2016).  Graphs for margins of bayesian networks.  Scandinavian Journal of Statistics, 43(3):625–648.
  * Evans, (2018) Evans, R. J. (2018).  Margins of discrete bayesian networks.  The Annals of Statistics, 46(6A):2623–2656.
  * Glymour et al., (2019) Glymour, C., Zhang, K., and Spirtes, P. (2019).  Review of causal discovery methods based on graphical models.  Frontiers in genetics, 10:524.
  * Halpern et al., (2015) Halpern, Y., Horng, S., and Sontag, D. (2015).  Anchored discrete factor analysis.  arXiv preprint arXiv:1511.03299.
  * Hoyer et al., (2008) Hoyer, P. O., Shimizu, S., Kerminen, A. J., and Palviainen, M. (2008).  Estimation of causal effects using linear non-gaussian causal models with hidden variables.  International Journal of Approximate Reasoning, 49(2):362–378.
  * Kuroki and Pearl, (2014) Kuroki, M. and Pearl, J. (2014).  Measurement bias and effect restoration in causal inference.  Biometrika, 101(2):423–437.
  * Le et al., (2011) Le, Q. V., Karpenko, A., Ngiam, J., and Ng, A. Y. (2011).  Ica with reconstruction cost for efficient overcomplete feature learning.  In Advances in neural information processing systems, pages 1017–1025.
  * Meek, (1995) Meek, C. (1995).  Strong-completeness and faithfulness in belief networks.  In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. Citeseer.
  * Pearl, (2009) Pearl, J. (2009).  Causality.  Cambridge university press.
  * Pearl, (2012) Pearl, J. (2012).  On measurement bias in causal inference.  arXiv preprint arXiv:1203.3504.
  * Saeed et al., (2020) Saeed, B., Belyaeva, A., Wang, Y., and Uhler, C. (2020).  Anchored causal inference in the presence of measurement error.  In Conference on uncertainty in artificial intelligence, pages 619–628. PMLR.
  * Salehkaleybar et al., (2020) Salehkaleybar, S., Ghassami, A., Kiyavash, N., and Zhang, K. (2020).  Learning linear non-gaussian causal models in the presence of latent variables.  Journal of Machine Learning Research, 21(39):1–24.
  * Scheines and Ramsey, (2016) Scheines, R. and Ramsey, J. (2016).  Measurement error and causal discovery.  In CEUR workshop proceedings, volume 1792, page 1. NIH Public Access.
  * Shimizu et al., (2006) Shimizu, S., Hoyer, P. O., Hyvärinen, A., and Kerminen, A. (2006).  A linear non-gaussian acyclic model for causal discovery.  Journal of Machine Learning Research, 7(Oct):2003–2030.
  * Shimizu et al., (2011) Shimizu, S., Inazumi, T., Sogawa, Y., Hyvärinen, A., Kawahara, Y., Washio, T., Hoyer, P. O., and Bollen, K. (2011).  DirectLiNGAM: A direct method for learning a linear non-gaussian structural equation model.  Journal of Machine Learning Research, 12(Apr):1225–1248.
  * Silva et al., (2006) Silva, R., Scheines, R., Glymour, C., and Spirtes, P. (2006).  Learning the structure of linear latent variable models.  Journal of Machine Learning Research, 7:191–246.
  * Spirtes et al., (2000) Spirtes, P., Glymour, C. N., Scheines, R., and Heckerman, D. (2000).  Causation, prediction, and search.  MIT press.
  * Wang and Drton, (2020) Wang, Y. S. and Drton, M. (2020).  Causal discovery with unobserved confounding and non-gaussian data.  arXiv preprint arXiv:2007.11131.
  * Xie et al., (2020) Xie, F., Cai, R., Huang, B., Glymour, C., Hao, Z., and Zhang, K. (2020).  Generalized independent noise condition for estimating linear non-gaussian latent variable causal graphs.  In Neural Information Processing Systems (NeurIPS).
  * Xie et al., (2022) Xie, F., Huang, B., Chen, Z., He, Y., Geng, Z., and Zhang, K. (2022).  Identification of linear non-Gaussian latent hierarchical structure.  In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S., editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 24370–24387. PMLR.
  * Yang et al., (2022) Yang, Y., Nafea, M., Ghassami, A., and Kiyavash, N. (2022).  Causal discovery in linear structural causal models with deterministic relations.  In First Conference on Causal Learning and Reasoning.
  * Zhang et al., (2018) Zhang, K., Gong, M., Ramsey, J. D., Batmanghelich, K., Spirtes, P., and Glymour, C. (2018).  Causal discovery with linear non-gaussian models under measurement error: Structural identifiability results.  In UAI, pages 1063–1072.

##  Appendix A Further discussion on ancestral ordered grouping

First, we compare our ancestral ordered grouping (AOG) in Definition 4 with
the ordered grouping proposed in (Zhang et al., , 2018). Next, we compare our
AOG to the equivalence classes for identifiability of a linear SEM with latent
variables under conventional faithfulness, proposed in (Salehkaleybar et al.,
, 2020). Finally, we present the details of our AOG recovery algorithm.

###  A.1 Comparison of AOG to previous work

In the following, we present an equivalent definition of the ordered grouping
proposed in (Zhang et al., , 2018), which is closer in spirit to our AOG
definition. As we mentioned earlier, the model proposed in (Zhang et al., ,
2018) assumes that all the underlying variables are measured with error
(unobserved), i.e., $\mathcal{Y}$ in Equation (1) is an empty set.
Subsequently, a u-leaf node is an unobserved underlying variable with no
children in $\mathcal{Z}$ and an nu-leaf node is an unobserved underlying
variable with at least one child in $\mathcal{Z}$.

######  Definition 8 (Ordered group decomposition (OGD) (Zhang et al., ,
2018))

The ordered group decomposition of a linear SEM-ME is a partition of
$\mathcal{Z}$ into distinct sets. This partition is described as follows:

  1. (1)

Select a causal order $k$ among _nu-leaf_ nodes in $\mathcal{Z}$ that is
consistent with the generating model. Assign each _nu-leaf_ node to a distinct
ordered group.

  2. (2)

For each _u-leaf_ node $Z_{j}\in\mathcal{Z}$, assign $Z_{j}$ to the same group
as its parent with the largest index in $k$.

The ordered grouping by (Zhang et al., , 2018) depends on the selected causal
order and hence might not be unique, since there can be more than one causal
order consistent with the generating model. Subsequently, this ordered
grouping does not permit characterizing the extent of identifiability under
conventional faithfulness alone, i.e., the equivalence classes of the
generating model in Theorem 2. In contrast, our AOG is a more refined grouping
than Definition 8 and returns a unique partition that does not depend on the
selection of the causal order. Further, our AOG characterizes the extent of
identifiability under conventional faithfulness (cf. Theorem 2). The following
example illustrates the difference between the ordered grouping in (Zhang et
al., , 2018) and our AOG.

###### Example 3

Consider a collider structure over three underlying variables in a linear SEM-
ME: $Z_{1}\rightarrow Z_{3}\leftarrow Z_{2}$, where $Z_{3}$ is a _u-leaf_
node. There are two possible causal orders that correspond to this structure,
namely (1,2,3) and (1,3,2). Hence, based on the ordered grouping definition of
(Zhang et al., , 2018), there are two possible corresponding partitions,
namely, $\\{\\{Z_{1}\\},\\{Z_{2},Z_{3}\\}\\}$ and
$\\{\\{Z_{2}\\},\\{Z_{1},Z_{3}\\}\\}$. However, following our definition of
AOG, i.e., Definition 4, the AOG is
$\\{\\{Z_{1}\\},\\{Z_{2}\\},\\{Z_{3}\\}\\}$, which is a refined partition of
either of the two partitions by (Zhang et al., , 2018). Further, the AOG of
the model can be recovered based on (the support of) the mixing matrix
$\mathbf{W}^{ME}$: $Z_{3}$ includes two noise terms, while $Z_{1}$ and $Z_{2}$
each includes one.

Next, we show the connection between our AOG and the observed descendant sets
in (Salehkaleybar et al., , 2020) proposed for a linear SEM with latent
variables. The “observed descendant set” of a (latent or observed) variable
$V_{i}$ is defined as the set of all observed descendants of $V_{i}$,
including $V_{i}$ itself if it is observed. The following proposition states
the equivalence of the two notions in a linear SEM-UR.

###### Proposition 5

In a linear SEM-UR, two variables are in the same ancestral ordered group if
and only if they have the same observed descendant set.

The authors of (Salehkaleybar et al., , 2020) showed that using “observed
descendant sets”, the causal order among the observed variables can be
identified under conventional faithfulness assumption (i.e., Assumption 3
_(a)_). Further, the total causal effects among observed variables can be
estimated. However, the model in (Salehkaleybar et al., , 2020) allows for
latent variables which have parents (i.e., not roots) and in general, the full
structure cannot be identified. In contrast, our AOG equivalence class
characterization (Theorem 2) extends the result in (Salehkaleybar et al., ,
2020). Specifically, we can recover the causal order among the ancestral
ordered groups, where each ancestral ordered group has at most one observed
variable. Moreover, we can estimate the exact structure and the coefficients
of every model in the AOG equivalence class.

###  A.2 AOG recovery algorithm

Based on Assumption 1, we can recover $\mathbf{W}^{ME}$ (resp.
$\mathbf{W}^{UR}$) from the observed data. The following property can be
implied from the definition of AOG, which shows that under conventional
faithfulness assumption, we can identify the AOG of the model only based on
the support of the mixing matrix.

###### Proposition 6

(a) Under Assumption 2 _(a)_ , two variables in a SEM-ME belong to the same
ancestral ordered group if and only if the two rows in $\mathbf{W}^{ME}$
corresponding to these variables have the same support. (b) Under Assumption 3
_(a)_ , two variables in a SEM-UR belong to the same ancestral ordered group
if and only if the two columns in $\mathbf{W}^{UR}$ corresponding to the
exogenous noise terms of these variables have the same support.

Equipped with this proposition, Algorithm 1 shows how to recover the AOG in
Definition 4 from $\mathbf{W}^{ME}$. The Algorithm first randomly chooses a
row in $\mathbf{W}^{ME}$ with one non-zero entry and finds all other rows with
the same support, and puts all the corresponding variables in a single
ancestral ordered group. Next, it removes the selected rows and the column
that contains the corresponding non-zero entry. In the remaining matrix, say
$\tilde{\mathbf{W}}$, the Algorithm again chooses a row $\mathbf{w}$ with one
non-zero entry, but has the smallest number of non-zero entries in
$\mathbf{W}^{ME}$. Then, it selects all other rows in $\tilde{\mathbf{W}}$
with the same support and the same number of non-zero entries in
$\mathbf{W}^{ME}$, as $\mathbf{w}$. The rows in $\tilde{\mathbf{W}}$ with
exactly one non-zero entry and having the same (fewest) number of non-zero
entries in $\mathbf{W}^{ME}$ correspond to an nu-leaf node and its direct
children (with the same support in $\mathbf{W}^{ME}$), and hence they go
together into the same group. The remaining rows with more non-zero entries in
$\mathbf{W}^{ME}$ are u-leaf nodes that go to separate distinct groups.
Finally, this procedure is repeated until all variables are assigned to
ancestral ordered groups.

Since Algorithm 1 is based on the mixing matrix, it follows from the
constructed mapping in Theorem 1 that the same Algorithm can be applied to
recover the AOG of a linear SEM-UR, by replacing “rows” with “columns” and
vice versa, in the Algorithm.

Input: Recovered mixing matrix $\mathbf{W}^{ME}$.

1 Calculate the number of non-zero entries in each row of $\mathbf{W}^{ME}$.
Denote the vector of these numbers as $\mathbf{n}$, where each entry in
$\mathbf{n}$ corresponds to a row in $\mathbf{W}^{ME}$.

2 Initialize $\tilde{\mathbf{W}}=\mathbf{W}^{ME}$.

3 while  _$\tilde{\mathbf{W}}$ is not empty_ do

4 Find a row in $\tilde{\mathbf{W}}$ that contains only one non-zero entry,
and has the smallest corresponding value in $\mathbf{n}$. If there are
multiple such rows, randomly select one. Denote the selected row as
$\mathbf{w}$, and its corresponding value in $\mathbf{n}$ as $n_{0}$.

5 Consider the rows in $\tilde{\mathbf{W}}$ with the same support as
$\mathbf{w}$ (including $\mathbf{w}$ itself). Denote the set of variables that
correspond to these rows as $\mathcal{Z}_{W}$.

6 Assign all variables in $\mathcal{Z}_{W}$, with the same corresponding value
as $n_{0}$ in $\mathbf{n}$, to a single ordered group.

7 Assign each of the remaining variables in $\mathcal{Z}_{W}$ to a separate
ordered group.

8 Remove from $\tilde{\mathbf{W}}$ the rows corresponding to the variables in
$\mathcal{Z}_{W}$, and the column containing the corresponding non-zero
entries in these rows.

9

Output: AOG of the SEM-ME.

Algorithm 1 Recovering ancestral ordered grouping in linear SEM-ME.

##  Appendix B SEM-ME and SEM-UR faithfulness assumptions

We first present the formal statement of SEM-ME and SEM-UR faithfulness
assumptions in Appendix B.1. We also provide examples of violations of
faithfulness. In Appendix B.2, we present an equivalent representation of SEM-
ME and SEM-UR faithfulness, using the mixing matrix. Next, in Appendix B.3, we
show that violation of faithfulness assumptions is a measure-zero event.
Finally, we present the relation between bottleneck faithfulness (Adams et
al., , 2021) and SEM-UR faithfulness assumptions in Appendix B.4.

###  B.1 Formal statement of faithfulness assumption

For a variable $V_{i}$, we define the ancestor set, $An(V_{i})$ (resp. the
descendant set, $De(V_{i})$) as the sets of variables that have directed paths
to $V_{i}$ (resp. from $V_{i}$); both excluding $V_{i}$ itself. Note that in
the literature, some works use the convention $V_{i}\in An(V_{i})$ and
$V_{i}\in De(V_{i})$. We do not use this convention here.

For SEM-ME, define the possible parent set of a variable
$V_{i}\in\mathcal{Z}\cup\mathcal{Y}$, as the union of the ancestor set of
$V_{i}$, $An(V_{i})$, and the set of u-leaf nodes whose parents are subsets of
$An(V_{i})$. For any set $\mathcal{V}\subseteq\mathcal{Z}\cup\mathcal{Y}$,
define $\texttt{TE}(\mathcal{V},V_{i})$ as the vector whose entries represent
the total causal effects (i.e., sum of products of path coefficients) of the
elements of $\mathcal{V}$ on $V_{i}$. We define the total causal effect of a
variable on itself to be 1. Similarly, for SEM-UR, define the possible
children set of $V_{i}\in\mathcal{H}\cup\mathcal{X}$ as the union of the
descendant set of $V_{i}$, $De(V_{i})$, and the set of latent variables whose
children sets are subsets of $De(V_{i})$. For any set
$\mathcal{V}\subseteq\mathcal{H}\cup\mathcal{X}$, define
$\texttt{TC}(V_{i},\mathcal{V})$ as the vector whose entries represent the
total causal effects of $V_{i}$ on the elements of $\mathcal{V}$.

######  Assumption 2 (SEM-ME faithfulness)

(a) The total causal effect of an underlying variable
$V_{i}\in\mathcal{Z}\cup\mathcal{Y}$ on its descendant
$V_{j}\in\mathcal{Z}\cup\mathcal{Y}$ is not equal to zero.
(b) For each variable $V_{i}\in\mathcal{Z}\cup\mathcal{Y}$, (b1)
$\emph{{TE}}(An(V_{i}),V_{i})$ is linearly independent of any
$k\leq|Pa(V_{i})|$ vectors in $\\{\emph{{TE}}(An(V_{i}),V):V\text{ is a
possible parent of }V_{i}\\}$, except for the case when $k=|Pa(V_{i})|$ and
for each _u-leaf_ node $V_{l}$ that corresponds to one of these $k$ vectors,
$Pa(V_{l})\subseteq Pa(V_{i})$; (b2) If $V_{i}$ is a _u-leaf_ node, then for
each parent $V_{j}$ of $V_{i}$,
$\emph{{TE}}(An(V_{i})\setminus\\{V_{j}\\},V_{i})$ is linearly independent of
any $k\leq|Pa(V_{j})\cup Pa(V_{i})|-1$ vectors in
$\\{\emph{{TE}}(An(V_{i})\setminus\\{V_{j}\\},V):V\text{ is a possible parent
of }V_{j}\\}$, except for the case when $k=|Pa(V_{j})\cup Pa(V_{i})|-1$ and
for each _u-leaf_ node $V_{l}$ that corresponds to one of these $k$ vectors,
$Pa(V_{l})\subseteq Pa(V_{j})\cup Pa(V_{i})$.

######  Assumption 3 (SEM-UR faithfulness)

(a) The total causal effect of an observed (latent) variable
$X_{i}\in\mathcal{X}$ $(H_{i}\in\mathcal{H})$ on its descendant
$X_{j}\in\mathcal{X}$ is not equal to zero.
(b) For each variable $V_{i}\in\mathcal{X}\cup\mathcal{H}$, (b1)
$\emph{{TC}}(V_{i},De(V_{i}))$ is linearly independent of any
$k\leq|Ch(V_{i})|$ vectors in $\\{\emph{{TC}}(V,De(V_{i})):V\text{ is a
possible child of }V_{i}\\}$, except for the case when $k=|Ch(V_{i})|$ and for
each latent variable $H_{l}$ that corresponds to one of these $k$ vectors,
$Ch(H_{l})\subseteq Ch(V_{i})$; (b2) If $V_{i}$ is a latent variable, then for
each child $X_{j}$ of $V_{i}$,
$\emph{{TC}}(V_{i},De(V_{i})\setminus\\{X_{j}\\})$ is linearly independent of
any $k\leq|Ch(X_{j})\cup Ch(V_{i})|-1$ vectors in
$\\{\emph{{TC}}(V,De(V_{i})\setminus\\{X_{j}\\}):V\text{ is a possible child
of }X_{j}\\}$, except for the case when $k=|Ch(X_{j})\cup Ch(V_{i})|-1$ and
for each latent variable $H_{l}$ that corresponds to one of these $k$ vectors,
$Ch(H_{l})\subseteq Ch(X_{j})\cup Ch(V_{i})$.

$Z_{1}$$Z_{2}$$Z_{3}$$Z_{4}$$Z_{5}$$Z_{6}$$~{}1$$~{}1$$b$$d$$1$$1$$a$$c$(a)

$Z_{1}$$Z_{4}$$Z_{5}$$Z_{2}$$Z_{3}$$Z_{6}$$a+1$$c+1$$b$$d$$1$$1$$-a$$-c$(b)

$~{}\begin{bmatrix}Z_{1}\\\ Z_{2}\\\ Z_{3}\\\ Z_{4}\\\ Z_{5}\\\
Z_{6}\end{bmatrix}=\begin{bmatrix}1&0&0\\\ 1&1&0\\\ 1&0&1\\\ a+1&1&0\\\
c+1&0&1\\\ b+d&b&d\\\ \end{bmatrix}\begin{bmatrix}N_{Z_{1}}\\\ N_{Z_{2}}\\\
N_{Z_{3}}\end{bmatrix}$ $\mathbf{W}^{ME}$(c)

Figure 5: Example explaining Assumption 2 _(b)_. (a) The ground-truth model of
a linear SEM-ME. (b) An alternative linear SEM-ME. (c) If $ab+cd=0$, then both
models have the same mixing matrix $\mathbf{W}^{ME}$.

We explain the aforementioned faithfulness assumptions using the following
examples, which investigate various cases of violation of SEM-ME faithfulness,
and show that our identifiability result in Theorem 3 may no longer hold under
such violation. In Appendix B.3, we show that violation of SEM-ME faithfulness
is a measure-zero event.

###### Example 4

Consider the linear SEM-ME generated by the graph in Figure 2(a).444This
example was stated in Section 4.1, and we repeat it here using the notation
$\texttt{TE}(\cdot,\cdot)$ in the formal statement of Assumption 2 _(b)_. The
mixing matrix is given in Figure 2. We have
$\emph{{TE}}(\\{Z_{1},Z_{2}\\},Z_{4})=[a(b+c);b+c]=(b+c)\emph{{TE}}(\\{Z_{1},Z_{2}\\},Z_{2})$.
This implies that $\emph{{TE}}(An(Z_{4})\setminus\\{Z_{3}\\},Z_{4})$ is
linearly dependent on one vector
$\emph{{TE}}(An(Z_{4})\setminus\\{Z_{3}\\},Z_{2})$ where $Z_{2}$ is a possible
parent of $Z_{3}$. Hence the model violates Assumption 2(b2).

According to Definition 6, the DOG of the ground truth model (Figure 2(a)) is
$\\{\\{Z_{1}\\},\\{Z_{2}\\},\\{Z_{3},Z_{4}\\}\\}$. Because either $Z_{3}$ or
$Z_{4}$ can be the center of the last group, the DOG equivalence class should
include both the ground-truth and the model represented by Figure 2(b).
However, due to violation of Assumption 2(b2), the model represented by Figure
2(b), does not belong to the same DOG equivalence class as the ground-truth,
and hence can be distinguished from the ground truth. Therefore, our
identifiability result in Theorem 3 does not hold because of violation of
faithfulness.

###### Example 5

Consider the linear SEM-ME generated by the graph in Figure 5(a). The mixing
matrix is given in Figure 5(c). We have
$\emph{{TE}}(An(Z_{6}),Z_{6})=[b+d;b;d]$,
$\emph{{TE}}(An(Z_{6}),Z_{4})=[a+1;1;0]$, and
$\emph{{TE}}(An(Z_{6}),Z_{5})=[c+1;0;1]$. If $ab+cd=0$, then
$\emph{{TE}}(An(Z_{6}),Z_{6})$ can be written as
$b\emph{{TE}}(An(Z_{6}),Z_{4})+d\emph{{TE}}(An(Z_{6}),Z_{5})$. That is,
$\emph{{TE}}(An(Z_{6}),Z_{6})$ can be written as the linear combination of two
vectors; however, the variables corresponding to these two vectors, i.e.,
$Z_{4},Z_{5}$, are both _u-leaf_ nodes and have a parent $Z_{1}$ that is not a
parent of $Z_{6}$. Therefore the model violates Assumption 2(b1). Note that
$ab+cd=0$ is a measure-zero event if all parameters are randomly and
independently drawn from continuous distributions.

Note that each of the six variables in the ground-truth model belongs to a
separate direct ordered group. This means that the DOG equivalent class only
includes the ground-truth. However, if $ab+cd=0$, then the linear SEM-ME
generated by the graph in Figure 5(b) is indistinguishable from the ground
truth, since it has the same mixing matrix and the same structure (i.e., the
two graphs are isomorphic). Once again, our identifiability result in Theorem
3 does not hold because of violation of faithfulness.

###  B.2 Equivalent matrix form for faithfulness assumptions

In this section we present an equivalent matrix representation of Assumptions
2 _(b)_ and 3 _(b)_. For each variable $V_{i}$ in SEM-ME, define $Supp(V_{i})$
as the support of the row in $\mathbf{W}^{ME}$ corresponding to $V_{i}$:
$Supp(V_{i})=\\{N_{V_{j}}|j:[\mathbf{W}^{ME}]_{ij}\neq 0\\}$. For each
variable $V_{i}$ in SEM-UR, define $Supp(N_{V_{i}})$ as the support of the
column in $\mathbf{W}^{UR}$ corresponding to $N_{V_{i}}$:
$Supp(N_{V_{i}})=\\{V_{j}|j:[\mathbf{W}^{UR}]_{ji}\neq 0\\}$.

Under this formulation, a variable $V_{j}$ in a SEM-ME is a possible parent of
$V_{i}$ if and only if $V_{j}\neq V_{i}$, and $Supp(V_{j})$ is a subset of
$Supp(V_{i})\setminus\\{N_{V_{i}}\\}$, i.e., $Supp(V_{i})$ excluding the
exogenous noise term $N_{V_{i}}$ if $V_{i}$ is an nu-leaf node (Yang et al., ,
2022). A variable $V_{j}$ in a SEM-UR is a possible child of $V_{i}$ if and
only if $V_{j}\neq V_{i}$ and $Supp(N_{V_{j}})$ is a subset of
$Supp(N_{V_{i}})\setminus\\{V_{i}\\}$, i.e., $Supp(V_{i})$ excluding ${V_{i}}$
itself if $V_{i}$ is observed.

###### Proposition 7

Assumptions 2(b) and 3(b) have the following equivalent matrix form:

Assumption 2(b): For a variable $V_{i}\in\mathcal{Z}\cup\mathcal{Y}$, (b1)
denote $\mathbf{W}^{ME}_{i}$ as the submatrix of $\mathbf{W}^{ME}$ with rows
corresponding to the possible parents of $V_{i}$, and columns corresponding to
$Supp(V_{i})\setminus\\{N_{V_{i}}\\}$. Then the vector
$\mathbf{W}^{ME}[V_{i},Supp(V_{i})\setminus\\{N_{V_{i}}\\}]$ cannot be written
as any linear combination of $k\leq|Pa(V_{i})|$ rows in $\mathbf{W}^{ME}_{i}$,
except for the case when $k=|Pa(V_{i})|$ and for each _u-leaf_ node $V_{l}$
that corresponds to one of these $k$ rows, $Pa(V_{l})\subseteq Pa(V_{i})$.
(b2) If $V_{i}$ is a _u-leaf_ node, then for each parent $V_{j}$ of $V_{i}$,
denote $\mathbf{W}^{ME}_{ij}$ as the submatrix of $\mathbf{W}^{ME}$ with rows
corresponding to the possible parents of $V_{j}$, and columns corresponding to
$Supp(V_{i})\setminus\\{N_{V_{j}}\\}$. Then
$\mathbf{W}^{ME}[V_{i},Supp(V_{i})\setminus\\{N_{V_{j}}\\}]$ cannot be written
as any linear combination of $k\leq|Pa(V_{i})\cup Pa(V_{j})|-1$ rows in
$\mathbf{W}^{ME}_{ij}$, except for the case when $k=|Pa(V_{i})\cup
Pa(V_{j})|-1$ and for each _u-leaf_ node $V_{l}$ that corresponds to one of
these $k$ rows, $Pa(V_{l})\subseteq Pa(V_{i})\cup Pa(V_{j})$.

Assumption 3(b): For a variable $V_{i}\in\mathcal{H}\cup\mathcal{X}$, (b1)
denote $\mathbf{W}^{UR}_{i}$ as the submatrix of $\mathbf{W}^{UR}$ with
columns corresponding to the exogenous noise terms of the possible children of
$V_{i}$, and rows corresponding to $Supp(N_{V_{i}})\setminus\\{V_{i}\\}$. Then
the vector $\mathbf{W}^{UR}[Supp(N_{V_{i}})\setminus\\{V_{i}\\},N_{V_{i}}]$
cannot be written as any linear combination of $k\leq|Ch(V_{i})|$ columns in
$\mathbf{W}^{UR}_{i}$, except for the case when $k=|Ch(V_{i})|$ and for each
latent variable $H_{l}$ whose exogenous noise term corresponds to one of these
$k$ columns, $Ch(H_{l})\subseteq Ch(V_{i})$.
(b2) If $V_{i}$ is a latent variable, then for each child $X_{j}$ of $V_{i}$,
denote $\mathbf{W}^{UR}_{ji}$ as the submatrix of $\mathbf{W}^{UR}$ with
columns corresponding to the exogenous noise terms of the possible children of
$X_{j}$, and rows corresponding to $Supp(N_{V_{i}})\setminus\\{X_{j}\\}$. Then
$\mathbf{W}^{UR}[Supp(N_{V_{i}})\setminus\\{X_{j}\\},N_{V_{i}}]$ cannot be
written as any linear combination of $k\leq|Ch(V_{i})|-1$ columns in
$\mathbf{W}^{UR}_{ji}$, except for the case when $k=|Ch(X_{j})\cup
Ch(V_{i})|-1$ and for each latent variable $H_{l}$ whose exogenous noise term
corresponds to one of these $k$ columns, $Ch(H_{l})\subseteq Ch(X_{j})\cup
Ch(V_{i})$.

###  B.3 Violation of our faithfulness assumptions is a measure-zero event

In the following, we show that Assumption 2 is violated with probability zero
if all model coefficients are randomly and independently drawn from continuous
distributions. Same argument holds for Assumption 3, and hence the proof is
omitted. Note that Assumption 2 _(a)_ is identical to conventional
faithfulness in linear causal models, the violation of which is known to be a
measure-zero event Meek,  (1995); Spirtes et al.,  (2000). Thus, it suffices
to show that violation of Assumption 2 _(b)_ is a measure-zero event. We do so
for both parts of Assumption 2 _(b)_.

Assumption 2 _(b1)_ whiteAssumption 2 _(b1)_ : Let $\mathcal{T}_{i}$ denote
the set of vectors $\\{\texttt{TE}(An(V_{i}),V):V\text{ is a possible parent
of }V_{i}\\}$. Recall that the total effects of $An(V_{i})$ on $V_{i}$, i.e.,
$\texttt{TE}(An(V_{i}),V_{i})$, can be written as a linear combination of the
total effects of $An(V_{i})$ on parents of $V_{i}$, i.e.,
$\mathcal{P}_{i}=\\{\texttt{TE}(An(V_{i}),V):V\in Pa(V_{i})\\}$:

$\texttt{TE}(An(V_{i}),V_{i})=\sum_{V_{j}\in
Pa(V_{i})}a_{ij}\texttt{TE}(An(V_{i}),V_{j}).$ (8)

Further, $\mathcal{A}_{i}=\\{\texttt{TE}(An(V_{i}),V):V\in An(V_{i})\\}$
constitutes a basis for ${\rm{span}}(\mathcal{T}_{i})$: Vectors in
$\mathcal{A}_{i}$ are linearly independent (because each ancestor has its
exogenous noise term) and every vector in $\mathcal{T}_{i}$ (which corresponds
to a possible parent of $V_{i}$) can be written as a linear combination of
vectors in $\mathcal{A}_{i}$. Note that
$\mathcal{P}_{i}\subseteq\mathcal{A}_{i}$. Therefore, if Assumption 2 _(b1)_
is violated, then $\texttt{TE}(An(V_{i}),V_{i})$ can either be (i) linearly
dependent on $k<|Pa(V_{i})|$ vectors in $\mathcal{T}_{i}$, or (ii) linearly
dependent on $|Pa(V_{i})|$ vectors in $\mathcal{T}_{i}$ and at least one of
these vectors does not belong to ${\rm{span}}(\mathcal{P}_{i})$. Both of these
events are of measure zero, when all $\\{a_{ij}|j:V_{j}\in Pa(V_{i})\\}$ in
Equation (8) are randomly and independently selected from continuous
distributions. This follows because if we represent
$\texttt{TE}(An(V_{i}),V_{i})$ and all vectors in $\mathcal{T}_{i}$ as linear
combinations of the vectors in $\mathcal{A}_{i}$, then case (i) corresponds to
a solution of a linear system with $k$ variables and at least $|Pa(V_{i})|$
equations (constraints), and case (ii) corresponds to a solution of a linear
system with $|Pa(V_{i})|$ variables and at least $|Pa(V_{i})|+1$ equations.

Assumption 2 _(b2)_ whiteAssumption 2 _(b2)_ : Similarly, we first show that
for any parent $V_{j}$ of $V_{i}$,
$\texttt{TE}(An(V_{i})\setminus\\{V_{j}\\},V_{i})$ can be written as the
linear combination of $|Pa(V_{i})\cup Pa(V_{j})|-1$ linearly independent
vectors in $\mathcal{T}_{i}$ with probability one. To show this, we first note
that Equation (8) holds for any subvector of $\texttt{TE}(An(V_{i}),V_{i})$.
Therefore,

$\texttt{TE}(An(V_{i})\setminus\\{V_{j}\\},V_{i})=\sum_{V_{j^{\prime}}\in
Pa(V_{i})}a_{ij^{\prime}}\texttt{TE}(An(V_{i})\setminus\\{V_{j}\\},V_{j^{\prime}}).$

Further, similar to Equation (8), $\texttt{TE}(An(V_{j}),V_{j})$ can also be
written as a linear combination of the vectors in
$\\{\texttt{TE}(An(V_{j}),V_{k}):V_{k}\in Pa(V_{j})\\}$. Since the total
causal effect from any variable in
$An(V_{i})\setminus(An(V_{j})\cup\\{V_{j}\\})$ to $V_{j}$ or any parent of
$V_{j}$ is zero, we have

$\texttt{TE}(An(V_{i})\setminus\\{V_{j}\\},V_{j})=\sum_{V_{k}\in
Pa(V_{j})}a_{jk}\texttt{TE}(An(V_{i})\setminus\\{V_{j}\\},V_{k}).$

Combining these two equations, we have

$\displaystyle\texttt{TE}(An(V_{i})\setminus\\{V_{j}\\},V_{i})={}$
$\displaystyle\sum_{V_{j^{\prime}}\in
Pa(V_{i})\setminus\\{V_{j}\\}}a_{ij^{\prime}}\texttt{TE}(An(V_{i})\setminus\\{V_{j}\\},V_{j^{\prime}})$
(9) $\displaystyle+\sum_{V_{k}\in
Pa(V_{j})}a_{ij}a_{jk}\texttt{TE}(An(V_{i})\setminus\\{V_{j}\\},V_{k}).$

Note that the right hand side of Equation (9) includes $|Pa(V_{i})\cup
Pa(V_{j})|-1$ vectors, and for each vector that is included in both
summations, the coefficients cancel out each other with probability zero.

Let $\mathcal{T}_{ji}$, $\mathcal{A}_{ji}$, $\mathcal{P}_{ji}$ denote the set
of vectors $\\{\texttt{TE}(An(V_{i})\setminus\\{V_{j}\\},V):V\text{ is a
possible parent of }V_{j}\\}$,
$\\{\texttt{TE}(An(V_{i})\setminus\\{V_{j}\\},V):V\in An(V_{j})\\}$,
$\\{\texttt{TE}(An(V_{i})\setminus\\{V_{j}\\},V):V\in Pa(V_{j})\cup
Pa(V_{i})\setminus\\{V_{j}\\}\\}$, respectively. Similarly, $\mathcal{A}_{ji}$
constitutes a basis of ${\rm{span}}\mathcal{T}_{ji}$. If Assumption 2 _(b2)_
is violated, then all parents of $V_{i}$ are ancestors of $V_{j}$, otherwise
$\texttt{TE}(An(V_{i})\setminus\\{V_{j}\\},V_{i})$ cannot belong to
${\rm{span}}(\mathcal{T}_{ji})$. This means that all vectors on the right hand
side of Equation (9), i.e., $\mathcal{P}_{ji}$, belong to $\mathcal{A}_{ji}$.
Further, $\texttt{TE}(An(V_{i})\setminus\\{V_{j}\\},V_{i})$ can either be (i)
linearly dependent on $k<|Pa(V_{i})\cup Pa(V_{j})|-1=|\mathcal{P}_{ji}|$
vectors in $\mathcal{T}_{ji}$, or (ii) linearly dependent on $|Pa(V_{i})\cup
Pa(V_{j})|-1$ vectors in $\mathcal{T}_{ji}$ and at least one of these vectors
does not belong to ${\rm{span}}(\mathcal{P}_{ji})$. Both of these events are
measure zero, when all $\\{a_{ij^{\prime}}|j^{\prime}:V_{j^{\prime}}\in
Pa(V_{i}),j^{\prime}\neq V_{j}\\}\cup\\{a_{jk}|k:V_{k}\in Pa(V_{j})\\}$ in
Equation (9) are randomly and independently selected from continuous
distributions.

###  B.4 Bottleneck faithfulness implies SEM-UR faithfulness

We show that our SEM-UR faithfulness is weaker than Bottleneck faithfulness in
(Adams et al., , 2021), in the sense that more models satisfy SEM-UR
faithfulness. Bottleneck faithfulness is defined as follows:

######  Condition 3 (Bottleneck faithfulness)

Define a bottleneck $B$ from $\mathcal{J}$ to $\mathcal{K}$ as a set of
variables where any directed path from $j\in\mathcal{J}$ to $k\in\mathcal{K}$
includes some variables in $B$, and a minimal bottleneck $B$ from
$\mathcal{J}$ to $\mathcal{K}$ as the bottleneck with the smallest size. Then
for every $\mathcal{J}\subseteq\mathcal{H}\cup\mathcal{X}$,
$\mathcal{K}\subseteq\mathcal{X}$, if $B$ is a minimal bottleneck from
$\mathcal{J}$ to $\mathcal{K}$, then
${\rm{Rank}}(\mathbf{W}_{\mathcal{K}}^{\mathcal{J}})=|B|$, where
$\mathbf{W}_{\mathcal{K}}^{\mathcal{J}}$ is the submatrix of $\mathbf{W}^{UR}$
representing the total causal effect from variables in $J$ to variables in
$K$.

“Bottleneck faithfulness implies SEM-UR faithfulnesswhiteBottleneck
faithfulness implies SEM-UR faithfulness”: It has been shown in (Adams et al.,
, 2021) that Condition 3 implies Assumption 3 _(a)_. For Assumption 3 _(b)_ ,
it suffices to show that if either Assumption 3 _(b1)_ or _(b2)_ is violated,
then Condition 3 is violated.

_Assumption 3(b1)_: Suppose $V_{i}$ violates Assumption _(b1)_. Then
$\texttt{TC}(V_{i},De(V_{i}))$ is either: (i) linearly dependent on
$k<|Ch(V_{i})|$ vectors in the set
$\mathcal{T}_{i}=\\{\texttt{TC}(V,De(V_{i})):V\text{ is a possible child of
}V_{i}\\}$, or (ii) linearly dependent on $k=|Ch(V_{i})|$ vectors in
$\mathcal{T}_{i}$ and the children set of at least one latent variable $H_{j}$
corresponding to these vectors is not a subset of $|Ch(V_{i})|$. Without loss
of generality, suppose $k$ is minimal, i.e, $\texttt{TC}(V_{i},De(V_{i}))$ is
linearly independent of any $l$ vectors in $\mathcal{T}_{i}$ for any $l<k$.
Denote the set of possible children of $V_{i}$ corresponding to these vectors
as $\mathcal{P}$. Consider the set $\mathcal{J}=\mathcal{P}\cup\\{V_{i}\\}$,
and $\mathcal{K}=Des(V_{i})$.555Recall that we do not include $V_{i}$ itself
in $Des(V_{i})$. This is different from (Adams et al., , 2021) where they
include $V_{i}$. Then
${\rm{Rank}}(\mathbf{W}_{\mathcal{K}}^{\mathcal{J}})=|\mathcal{P}|=k$, because
(i) $\mathbf{W}_{\mathcal{K}}^{V_{i}}$ can be written as a linear combination
of the columns in $\mathbf{W}_{\mathcal{K}}^{\mathcal{P}}$, and (ii) columns
in $\mathbf{W}_{\mathcal{K}}^{\mathcal{P}}$ are linearly independent
(otherwise $k$ is not minimal).

In the following we show that any bottleneck from $\mathcal{J}$ to
$\mathcal{K}$ is at least of size $k+1$. First, any bottleneck from
$\mathcal{P}$ to $\mathcal{K}$ is at least of size $|\mathcal{P}|=k$. This is
because if there exists a bottleneck of size $k-1$, then according to
Proposition 1 of (Adams et al., , 2021),
${\rm{Rank}}(\mathbf{W}_{\mathcal{K}}^{\mathcal{J}})\leq k-1$. This
contradicts the minimality of $k$. Next, for any bottleneck $B$ from
$\mathcal{P}$ to $\mathcal{K}$ with size $k$: (i) If $k<|Ch(V_{i})|$, then $B$
will cover at most $k$ children of $V_{i}$. (ii) If $k=|Ch(V_{i})|$. Note that
there exists at least one child of $H_{j}$, denoted by $X_{k}$, that is not a
child of $V_{i}$. Therefore, to block the edge $H_{j}\rightarrow X_{k}$, $B$
must include at least one variable between $H_{j}$ and $X_{k}$. This implies
that $B$ includes at most $|Ch(V_{i})|-1$ children of $V_{i}$.

In either case, there is at least one directed edge from $V_{i}$ to one of its
children that cannot be blocked by $B$. Therefore, the minimal bottleneck from
$\mathcal{J}$ to $\mathcal{K}$ is at least of size $k+1$, which violates
bottleneck faithfulness condition.

_Assumption 3(b2)_: Similarly, suppose $V_{i}$ and its child $X_{j}$ violates
Assumption _(b2)_. Then $\texttt{TC}(V_{i},De(V_{i})\setminus\\{X_{j}\\})$ is
either: (i) linearly dependent on $k<|Ch(V_{i})\cup Ch(X_{j})|-1$ vectors in
the set
$\mathcal{T}_{ji}=\\{\texttt{TC}(V,De(V_{i})\setminus\\{X_{j}\\}):V\text{ is a
possible child of }X_{j}\\}$, or (ii) linearly dependent on $k=|Ch(V_{i})\cup
Ch(X_{j})|-1$ vectors in $\mathcal{T}_{ji}$, and the children set of at least
one latent variable $H_{k}$ corresponding to these vectors is not a subset of
$Ch(V_{i})\cup Ch(X_{j})$.

Suppose $k$ is minimal, and denote the set of possible children corresponding
to these $k$ vectors as $\mathcal{P}$. Consider the set
$\mathcal{J}=\mathcal{P}\cup\\{V_{i}\\}$ and
$\mathcal{K}=Des(V_{i})\setminus\\{X_{j}\\}$. Then
${\rm{Rank}}(\mathbf{W}_{\mathcal{K}}^{\mathcal{J}})=|\mathcal{P}|=k$.
However, any bottleneck from $\mathcal{J}$ to $\mathcal{K}$ is at least of
size $k+1$. This is because: (i) Any bottleneck from $\mathcal{P}$ to
$\mathcal{K}$ is at least of size $|\mathcal{P}|=k$; (ii) For any bottleneck
$B$ from $\mathcal{P}$ to $\mathcal{K}$ with size $k$, there are
$|Ch(V_{i})\cup Ch(X_{j})\setminus\\{X_{j}\\}|$ variables in $\mathcal{K}$
that is a child of either $V_{i}$ or $X_{j}$. Therefore there is at least one
directed edge from $V_{i}$ or $X_{j}$ to one of their children (excluding
$X_{j}$) that cannot be blocked by $B$. (If $|B|=|Ch(V_{i})\cup Ch(X_{j})|-1$,
then there is at least one variable in $B$ that blocks the edge from $H_{k}$
to its child that does not belong to $Ch(V_{i})\cup Ch(X_{j})$.) Therefore
bottleneck faithfulness condition is violated.

“SEM-UR faithfulness does not imply bottleneck faithfulnesswhiteSEM-UR
faithfulness does not imply bottleneck faithfulness”: In the following we will
provide an example which satisfies Assumption 3 but violates Condition 3. This
example is introduced in (Adams et al., , 2021). Consider the following linear
SEM-UR involving three latent variables $H=[H_{1},H_{2},H_{3}]$ and four
observed variables $X=[X_{1},X_{2},X_{3},X_{4}]$:

$H=N_{H},\quad X=\begin{bmatrix}0&1&-1\\\ 2&2&0\\\ 3&3&0\\\
4&0&4\end{bmatrix}H+\mathbf{0}X+N_{X}.$

It has been shown in (Adams et al., , 2021) that the minimal bottleneck from
$\mathcal{H}=\\{H_{1},H_{2},H_{3}\\}$ to
$\mathcal{X}=\\{X_{1},X_{2},X_{3},X_{4}\\}$ is $\mathcal{H}$ with
$|\mathcal{H}|=3$, while
${\rm{Rank}}(\mathbf{W}_{\mathcal{X}}^{\mathcal{H}})=2$. Therefore the model
violates Condition 3. On the contrary, the model satisfies Assumption 3. This
is because the possible children set of each observed variable is empty set
(meaning that _(b2)_ is satisfied), and the possible children set of each
latent variable only includes its children (meaning that _(b1)_ is satisfied).

##  Appendix C Proofs of the main results

###  C.1 Proof of Theorem 1

We first observe that in a SEM-ME, whether a non-leaf underlying variable
$V_{i}$ is observed (i.e., $V_{i}\in\mathcal{Y}$) or measured with error
(i.e., $V_{i}\in\mathcal{Z}$) does not change the relevant mixing matrix
$\mathbf{W}^{ME}$. Specifically, in the overall mixing matrix $\mathbf{W}$,
cf. Equation (6), the exogenous noise terms associated with non-leaf
underlying variables correspond to columns with at least two non-zero entries.
This follows because a non-leaf variable influences at least two other
variables (its own measurement and its child(ren) in
$\mathcal{Z}\cup\mathcal{Y}$). On the other hand, the measurement error terms
associated with the non-leaf underlying variables correspond to columns with
only one non-zero entry, since the measurement error term only influences one
variable (i.e., the corresponding measurement in $U$). Thus, by removing the
identity matrix part of $\mathbf{W}$, the remaining part, i.e.,
$\mathbf{W}^{ME}$ does not change if a non-leaf underlying variable is
observed or measured with error.

For a linear SEM-ME, $M^{\prime}$, without loss of generality, suppose that
all non-leaf underlying variables are observed. That is, all nu-leaf nodes
belong to $\mathcal{Y}$, and u-leaf nodes belong to $\mathcal{Z}$. Denote the
dimension of $Y$ (i.e., the number of the nu-leaf nodes) as $p_{n}$. Let us
first permute the variables in $Y$ in the reversed causal order, and denote
the result of this permutation by $Y^{*}$. Thus,

$\displaystyle
Y^{*}=\mathbf{P}Y\quad\Longrightarrow\quad\begin{bmatrix}Z^{L}\\\
Y^{*}\end{bmatrix}=\begin{bmatrix}\mathbf{D}\\\
\mathbf{C}^{*}\end{bmatrix}Y^{*}+\begin{bmatrix}0\\\
N_{{Y}^{*}}\end{bmatrix},$

where $\mathbf{P}$ is a $p_{n}\times p_{n}$ permutation matrix, and
$N_{{Y}^{*}}=\mathbf{P}N_{Y}$ is the permuted noise vector corresponding to
$Y^{*}$. Further, $\mathbf{C}^{*}=\mathbf{P}\mathbf{C}\mathbf{P}^{\top}$ is a
row and column permuted version of $\mathbf{C}$, such that $\mathbf{C}^{*}$ is
strictly upper triangular. Therefore, the mixing matrix $\mathbf{W}^{ME}$
corresponding to $M^{\prime}$ can be written as

$\displaystyle\mathbf{W}^{ME}(M^{\prime})=\begin{bmatrix}\mathbf{I}&\mathbf{0}\\\
\mathbf{0}&\mathbf{P}^{\top}\end{bmatrix}\mathbf{W}^{ME}_{*}\mathbf{P},\quad\text{where}\quad\mathbf{W}^{ME}_{*}=\begin{bmatrix}\mathbf{D}(\mathbf{I}-\mathbf{C}^{*})\\\
(\mathbf{I}-\mathbf{C}^{*})\end{bmatrix}.$ (10)

Next, we derive the mixing matrix of the corresponding SEM-UR under the
mapping $\phi$. Suppose the corresponding SEM-UR can be written as

$H_{\phi}=N_{H_{\phi}},\qquad
X_{\phi}=\mathbf{B}_{\phi}H_{\phi}+\mathbf{A}_{\phi}X_{\phi}+N_{X_{\phi}}.$

Note that under mapping $\phi$, all u-leaf nodes in $M^{\prime}$ are mapped to
latent variables in $H_{\phi}$, and all nu-leaf nodes in $M^{\prime}$ are
mapped to observed variables in $X_{\phi}$. Further, all edges are reversed.
This means that there exists a permutation of $H_{\phi}$, denoted by
$H^{*}_{\phi}$, such that $Z_{i}$ is mapped to $H^{*}_{\phi_{i}}$ and
$Y^{*}_{i}$ is mapped to $X_{i}$. Note that the $X$ variables are arranged
according to a certain causal order, which is not necessarily the case for the
$Y$ variables. Further, if there is an edge from $Y^{*}_{i}$ to $Y^{*}_{j}$ in
$M^{\prime}$ with weight $w$, then there exists an edge from $X_{i}$ to
$X_{j}$ in $\phi(M^{\prime})$ with weight $w$. Therefore,
$\mathbf{A}_{\phi}=(\mathbf{C}^{*})^{\top}$. Similarly,
$\mathbf{B}_{\phi}\mathbf{P}_{H}=\mathbf{D}^{\top}$, where $\mathbf{P}_{H}$
represents the re-permutation of the latent variables corresponding to the
order of the u-leaf nodes. The mixing matrix of $\phi(M^{\prime})$ can be
written as

$\mathbf{W}^{UR}(M)=\left[\left(\mathbf{I}-(\mathbf{C}^{*})^{\top}\right)\mathbf{D}^{\top}\mathbf{P}_{H}^{\top}\;\;\left(\mathbf{I}-(\mathbf{C}^{*})^{\top}\right)\right]=\left[\left(\mathbf{I}-\mathbf{C}^{*}\right)^{\top}\mathbf{D}^{\top}\mathbf{P}_{H}^{\top}\;\;\left(\mathbf{I}-\mathbf{C}^{*}\right)^{\top}\right].$
(11)

Comparing Equation (10) to Equation (11), we have

$\mathbf{W}^{ME}(M^{\prime})=\begin{bmatrix}\mathbf{I}&\mathbf{0}\\\
\mathbf{0}&\mathbf{P}^{\top}\end{bmatrix}\begin{bmatrix}\mathbf{P}^{\top}_{H}&\mathbf{0}\\\
\mathbf{0}&\mathbf{I}\end{bmatrix}\left(\mathbf{W}^{UR}(M)\right)^{\top}\mathbf{P}$

Therefore, there exist column permutations of $\mathbf{W}^{ME}(M^{\prime})$
and $\mathbf{W}^{UR}(M)$, namely,

$\tilde{\mathbf{W}}^{ME}(M^{\prime})=\mathbf{W}^{ME}(M^{\prime})\mathbf{P}^{\top},\qquad\tilde{\mathbf{W}}^{UR}(M)=\mathbf{W}^{UR}(M)\begin{bmatrix}\mathbf{P}_{H}&\mathbf{0}\\\
\mathbf{0}&\mathbf{P}\end{bmatrix}$

such that
$\tilde{\mathbf{W}}^{ME}(M^{\prime})=(\tilde{\mathbf{W}}^{UR}(M))^{\top}$.

###  C.2 Proof of Theorem 2

In order to prove Theorem 2, we need to prove Propositions 1 and 2, and that
the AOG equivalence class is the extent level of identifiability under
Assumption 2 _(a)_. We begin by proving Proposition 2 (and its counterpart for
direct ordered grouping). We formulate these in the following lemma.

###### Lemma 1

Given the mixing matrix $\mathbf{W}^{ME}$ (resp. $\mathbf{W}^{UR}$) and the
AOG/DOG of the model, all the coefficients are identified (up to the
permutation and scaling of the columns of $\mathbf{B}$ in SEM-UR) if and only
if the centers (resp. exogenous noise assignments) of the ancestral/direct
ordered groups are identified.

Proof.  “only-if directionwhiteonly-if direction”: If all the coefficients are
identified, i.e., matrices $\mathbf{C},\mathbf{D}$ in Equation (2) (and
matrices $\mathbf{A},\mathbf{B}$ in Equation (4)) are identified, then the
structure of the model is identified. Therefore, we can identify
ancestral/direct ordered grouping of the model and find the center of each
ancestral/direct ordered group.

“if directionwhiteif direction”: For SEM-ME, given the identified centers in
each ordered group, we compute the coefficients of the model from the mixing
matrix $\mathbf{W}^{ME}$ as follows. According to the definition of AOG/DOG,
only the first $p_{n}$ ordered groups can include more than one element;
recall that $p_{n}$ denotes the number of nu-leaf nodes. Therefore, for any
possible selection of the centers in each group, consider the submatrix of
$\mathbf{W}^{ME}$ where the rows correspond to the first $p_{n}$ selected
centers. This submatrix can be permuted to a lower-triangular matrix with non-
zero diagonal, and maps to $(\mathbf{I}-\mathbf{C})^{-1}$ in Equation (5);
recall that $\mathbf{C}$ represents the edges among the first $p_{n}$ centers
(i.e., the nu-leaf nodes in the model). That is, $\mathbf{C}$ can be
identified by first normalizing the columns of $\mathbf{W}^{ME}$, and then
taking the inverse of the submatrix that corresponds to the identified
centers. Note that the lower-triangular matrix (after permutation) must have
diagonal one. If the diagonal entry has value not equal to one, then this
number represents the noise coefficient, and can be removed by column
normalization. Matrix $\mathbf{D}$, which represents the edges from nu-leaf
nodes to u-leaf nodes can be deduced from remaining submatrix of
$\mathbf{W}^{ME}$ that maps to $\mathbf{D}(\mathbf{I}-\mathbf{C})^{-1}$.
Therefore, all coefficients can be identified.

For SEM-UR, given the exogenous noise terms of the identified centers in each
ordered group, we use a similar method to compute the coefficients of the
model from the mixing matrix $\mathbf{W}^{UR}$. Specifically, $\mathbf{A}$ in
Equation (4) can be identified using the submatrix of $\mathbf{W}^{UR}$ where
the columns correspond to the last $q$ selected centers ($q$ denotes the
number of observed variables). Matrix $\mathbf{B}$ can be deduced from the
remaining submatrix of $\mathbf{W}^{UR}$. Note that permuting and normalizing
the columns of the submatrix that maps to $(\mathbf{I}-\mathbf{A})^{-1}$ does
not affect the the submatrix that maps to
$\mathbf{B}(\mathbf{I}-\mathbf{A})^{-1}$. This means that the true permutation
and scaling of $\mathbf{B}$ cannot be identified.

In the remainder of the proof of Theorem 2, we focus on linear SEM-ME; the
proof for linear SEM-UR follows similarly. The proof of the remaining
assertions consists of two parts. In the first part, we show that models in
the same AOG equivalence class satisfy Proposition 1 and Assumption 2 _(a)_.
That is, given the mixing matrix $\mathbf{W}^{ME}$, under different choices of
the center in each ancestral ordered group, the alternative model (1)
satisfies Assumption 2 _(a)_ , and (2) preserves the causal order among the
ancestral ordered groups. In the second part, we show that any alternative
model that has the same mixing matrix as the ground-truth but does not belong
to the same AOG equivalence class violates Assumption 2 _(a)_. We can see from
the proof of Lemma 1 that the model can be identified once all the nu-leaf
nodes (i.e., variables corresponding to the rows of $\mathbf{C}$) are
identified. Therefore, we show that, if at least one of the first $p_{n}$
ancestral ordered groups in the ground-truth does not include any of the nu-
leaf nodes in the alternative model, then the alternative model violates
Assumption 2 _(a)_.

We use $Pa_{M}(V_{i})$ and $An_{M}(V_{i})$ to denote the parent set and
ancestor set of variable $V_{i}$ in model $M$ throughout the remaining of the
proof.

Proof of the first part:

_Proof of (1)_ : Note that Assumption 2 _(a)_ (i.e., conventional faithfulness
assumption) is equivalent to the following: If $V_{i}$ is an ancestor of
$V_{j}$, then the support of the row of $\mathbf{W}^{ME}$ corresponding to
$V_{i}$ is a subset of the support of the row of $\mathbf{W}^{ME}$
corresponding to $V_{j}$. Further, the converse is also true given that
$V_{i}$ is an nu-leaf node.

Let $M$ denote the ground-truth, and let $M^{\prime}$ denote an alternative
model that belongs to the same AOG equivalence class as $M$. We first show
that if some center nodes in $M$ are swapped with other nodes in their
respective ancestral ordered groups, then an added edge(s) to any node $V$ in
$M^{\prime}$ can only originate from variables in $An_{M}(V)$. To show this,
suppose that $V_{i_{1}},\cdots,V_{i_{m}}$ represent some centers of the
ancestral ordered groups in $M$, where $m\leq p_{n}$, and
$\\{i_{1},\cdots,i_{m}\\}$ is consistent with the causal order among the nu-
leaf nodes in $M$. Now, the centers in $M^{\prime}$ are changed from
$V_{i_{1}},\cdots,V_{i_{m}}$ to $V_{j_{1}},\cdots,V_{j_{m}}$, where
$V_{i_{k}}$ and $V_{j_{k}}$ are in the same ancestral ordered group, $\forall
k\in[m]$.

Consider the structural equations of $V_{i_{1}}$ (first changed center in $M$)
and $V_{j_{1}}$ (the swapped center in $M^{\prime}$), and $V_{k_{1}}$ which is
any child of $V_{i_{1}}$ in $M$ (other than $V_{k_{1}}$). Since $V_{i_{1}}$
and $V_{j_{1}}$ belong to the same ancestral ordered group, if follows by the
definition of AOG that parents of $V_{j_{1}}$, except for $V_{i_{1}}$, are
also ancestors of $V_{i_{1}}$ in $M$. Therefore the structural equations are:

$\displaystyle V_{i_{1}}$ $\displaystyle=\sum_{l:V_{l}\in
Pa_{M}(V_{i_{1}})}a_{i_{1}l}V_{l}+N_{V_{i_{1}}},$ $\displaystyle V_{j_{1}}$
$\displaystyle=a_{j_{1}i_{1}}V_{i_{1}}+\sum_{l_{j}:V_{l_{j}}\in
An_{M}(V_{i_{1}})}a_{j_{1}l_{j}}V_{l_{j}},$ $\displaystyle V_{k_{1}}$
$\displaystyle=a_{k_{1}i_{1}}V_{i_{1}}+\sum_{l_{k}:V_{l_{k}}\in
Pa_{M}(V_{k_{1}})}a_{k_{1}l_{k}}V_{l_{k}}+N_{V_{k_{1}}}.$

Now, we choose $V_{j_{1}}$ to be the center of the corresponding ordered group
in $M^{\prime}$ (replacing the center $V_{i_{1}}$ in $M$). Now, in
$M^{\prime}$, $V_{i_{1}}$ is a child of $V_{j_{1}}$ and is a u-leaf node.
Also, the children of $V_{i_{1}}$ in $M$ are now children of $V_{j_{1}}$ in
$M^{\prime}$. Therefore, the structural equations of $V_{i_{1}}$, $V_{j_{1}}$
and $V_{k_{1}}$ in $M^{\prime}$ are

$\displaystyle V_{j_{1}}$ $\displaystyle=\sum_{l_{j}:V_{l_{j}}\in
An_{M}(V_{i_{1}})}a_{j_{1}l_{j}}V_{l_{j}}+\sum_{l:V_{l}\in
Pa_{M}(V_{i_{1}})}a_{j_{1}i_{1}}a_{i_{1}l}V_{l}+a_{j_{1}i_{1}}N_{V_{i_{1}}},$
$\displaystyle V_{i_{1}}$
$\displaystyle=a^{-1}_{j_{1}i_{1}}V_{j_{1}}+\sum_{l_{j}:V_{l_{j}}\in
An_{M}(V_{i_{1}})}a^{-1}_{j_{1}i_{1}}a_{j_{1}l_{j}}V_{l_{j}},$ $\displaystyle
V_{k_{1}}$
$\displaystyle=a_{k_{1}i_{1}}\left(a^{-1}_{j_{1}i_{1}}V_{j_{1}}+\sum_{l_{j}:V_{l_{j}}\in
An_{M}(V_{i_{1}})}a^{-1}_{j_{1}i_{1}}a_{j_{1}l_{j}}V_{l}\right)+\sum_{l_{k}:V_{l_{k}}\in
Pa_{M}(V_{k_{1}})}a_{k_{1}l_{k}}V_{l_{k}}+N_{V_{k_{1}}}.$

Comparing both sets of structural equations, we see that the additional edges
to $V_{j_{1}}$ and $V_{k_{1}}$ in $M^{\prime}$ originate from variables in
$An_{M}(V_{i_{1}})$. Since $V_{i_{1}}$ is a parent of both, this means that
variables in $An_{M}(V_{i_{1}})$ are also ancestors of $V_{j_{1}}$ and
$V_{k_{1}}$. This further implies that the ancestor sets of all variables
remain the same after this change, i.e., if $V_{i}$ is an ancestor of $V_{j}$
in $M$, then $V_{i}$ (or the node that replaces $V_{i}$) is an ancestor of
$V_{j}$ (or the node that replaces $V_{j}$) in $M^{\prime}$. By repeating the
same procedure, i.e., swapping $V_{i_{k}}$ with $V_{j_{k}}$ for
$k=2,3,\cdots,m$, the resulting model $M^{\prime}$ will only add edges from
variables in $An_{M}(V)$ to $V$, $\forall V\in\mathcal{Y}\cup\mathcal{Z}$.

Next, we show, by contradiction, that if $M$ satisfies Assumption 2 _(a)_ ,
then $M^{\prime}$ also satisfies Assumption 2 _(a)_. Suppose $M^{\prime}$
violates Assumption 2 _(a)_. This means that there exist $V_{0}$ and $V$ such
that $V_{0}$ is an ancestor of $V$ in $M^{\prime}$ but the support of $V_{0}$
(i.e., its corresponding row in $\mathbf{W}^{ME}$) is not a subset of the
support of $V$. Note that since $V_{0}$ is an nu-leaf node in $M^{\prime}$,
hence it is a center node of some ancestral ordered group in $M^{\prime}$. Let
$V^{\prime}_{0}$ denote the center of the ancestral ordered group of $V_{0}$
in $M$ (which can be $V_{0}$ itself). Note that $V_{0}$ has the same support
as $V^{\prime}_{0}$ since they belong to the same ancestral ordered group.
Therefore, the support of $V^{\prime}_{0}$ is not a subset of the support of
$V$. Since $M$ satisfies Assumption 2 _(a)_ , this means that $V^{\prime}_{0}$
is not an ancestor of $V$ in $M$. However, in obtaining $M^{\prime}$ from $M$
(i.e., by switching some centers in $M$), the edges added to $V$ in
$M^{\prime}$ only come from ancestors of $V$ in $M$. This means that $V_{0}$
cannot be an ancestor of $V$ in $M^{\prime}$, which leads to a contradiction.
Therefore, $M^{\prime}$ satisfies Assumption 2 _(a)_.

_Proof of (2)_ : Given that the alternative model $M^{\prime}$ satisfies
Assumption 2 _(a)_ , we show that $M^{\prime}$ preserves the causal order
among the ancestral ordered groups. We show this by contradiction. Suppose
that a variable $V_{0}$ in a later group causes another variable $V$ in an
earlier group in $M^{\prime}$; according to the causal order among the groups
in $M$. Note that $V_{0}$ is an nu-leaf node in $M^{\prime}$ since it causes
$V$, and hence it is the center of some ancestral ordered group in
$M^{\prime}$. Let $V^{\prime}_{0}$ be the center of the corresponding group in
$M$, with an associated exogenous noise term denoted by $N_{V^{\prime}_{0}}$.
Since $V_{0}$ and $V_{0}^{\prime}$ belong to the same ancestral ordered group,
$N_{V^{\prime}_{0}}$ must belong to the support of $V_{0}$. However, since $V$
is in an earlier group than $V_{0}$ in $M^{\prime}$, $N_{V^{\prime}_{0}}$ is
not in the support of $V$. Therefore the support of $V_{0}$ is not a subset of
the support of $V$, and hence, $M^{\prime}$ violates Assumption 2 _(a)_.

Proof of the second part:

If the alternative model $M^{\prime}$ does not belong to the AOG equivalence
class of the ground-truth $M$, then at least one of the first $p_{n}$
ancestral ordered groups in $M$ does not include any of the nu-leaf nodes in
$M^{\prime}$. Denote the center of this ordered group as $V_{i}$, and let
$N_{V_{i}}$ denote its exogenous noise. Since $V_{i}$ is a u-leaf node in
$M^{\prime}$, there is at least one parent of $V_{i}$ in $M^{\prime}$ that
also includes $N_{V_{i}}$ (i.e., is affected by $N_{V_{i}}$ directly or
indirectly). Denote this variable as $V_{j}$. Since $V_{j}$ includes
$N_{V_{i}}$, it must be a descendant of $V_{i}$ in $M$. As $M$ satisfies
Assumption 2 _(a)_ , this means that the support of $V_{j}$ (in
$\mathbf{W}^{ME}$) is a superset of the support of $V_{i}$. Further, since the
ancestral ordered group of $V_{i}$ does not include any nu-leaf nodes in
$M^{\prime}$, $V_{j}$ does not belong to the ancestral ordered group of
$V_{i}$. This means that the support of $V_{j}$ (in $\mathbf{W}^{ME}$) is not
the same as the support of $V_{i}$. Therefore, the support of $V_{j}$ (in
$\mathbf{W}^{ME}$) is a strict superset of the support of $V_{i}$. Since
$V_{j}$ is a parent of $V_{i}$ in $M^{\prime}$, this violates Assumption 2
_(a)_ on the alternative model $M^{\prime}$.

Conclusion: We showed that by under different choices of the centers in the
ancestral ordered groups, we can always find a model $M^{\prime}$ that: (1)
has the same mixing matrix; (2) satisfies Assumption 2 _(a)_ ; (3) preserves
the causal order among ancestral ordered groups. Thus, we cannot distinguish
$M^{\prime}$ from the ground-truth under Assumption 2 _(a)_ alone. Further, we
show that any model that have the same mixing matrix but does not belong to
the AOG equivalence class does violate Assumption 2 _(a)_ and can be
distinguished from the ground-truth $M$. Therefore the extent level of
identifiability can be characterized by AOG equivalence class.

###  C.3 Proof of Theorem 3

To prove Theorem 3, we need to prove Propositions 3 and 4, and that the DOG
equivalence class is the extent level of identifiability under Assumption 2.
The proof can be divided into two parts. We first show the necessity part,
that is, models in the same DOG equivalence class as the ground-truth satisfy
Assumption 2 and Proposition 3, hence cannot be distinguished from the ground-
truth. We then show the sufficiency part, i.e., any model that has the same
mixing matrix but does not belong to the DOG equivalence class of the ground-
truth violates Assumption 2.

####  C.3.1 Proof of necessity

We have shown in Lemma 1 that models in the same DOG equivalence class can be
identified by the choice of centers of the direct ordered groups. In the
following, given the ground-truth model $M$ and a certain choice of the
centers that corresponds to an alternative model $M^{\prime}$, where
$M^{\prime}$ belongs to the same DOG equivalence class as $M$, we show that in
the alternative model: (1) No edges are added; (2) No edges are removed; (3)
Faithfulness is preserved. Therefore we cannot distinguish the alternative
model from the ground truth.

Suppose that $V_{i_{1}},\cdots,V_{i_{m}}$ represent some centers of the direct
ordered groups in the ground-truth $M$, where $m\leq p_{n}$, and
$\\{i_{1},\cdots,i_{m}\\}$ is consistent with the causal order among the nu-
leaf nodes in $M$. Now, the centers in $M^{\prime}$ are changed from
$V_{i_{1}},\cdots,V_{i_{m}}$ to $V_{j_{1}},\cdots,V_{j_{m}}$, where
$V_{i_{k}}$ and $V_{j_{k}}$ are in the same direct ordered group, $\forall
k\in[m]$. It follows by the definition of DOG that the edge
$V_{i_{k}}\rightarrow V_{j_{k}}$ violates Condition 1, $\forall k\in[m]$.

Note that according to Condition 1, we have the following two properties: (1)
For each nu-leaf node $V$ and each u-leaf node $V^{\prime}$ that belongs to
the same direct ordered group as $V$, $Pa(V^{\prime})\setminus\\{V\\}\subseteq
Pa(V)$. (2) All u-leaf nodes that belong to the same direct ordered group have
the same parent set; otherwise, Condition 1 will be satisfied and the u-leaf
nodes cannot belong to the same direct ordered group.

Lastly, for any model $M$, any set of variables $\mathcal{V}$ and variable
$V_{j}$, let $\texttt{TE}_{M}(\mathcal{V},V_{j})$ denote the vector of total
causal effects from variables in $\mathcal{V}$ to $V_{j}$ in model $M$. Note
that the total effect from a variable $V_{i}$ to $V_{j}$ in $M_{0}$ is equal
to the entry in $\mathbf{W}^{ME}$ with row corresponding to $V_{j}$ and column
corresponding to $N_{V_{i}}$. Since $M$ and $M^{\prime}$ has the same mixing
matrix, if $N_{V_{i}}$ is the exogenous noise term of another variable
$V^{\prime}_{i}$ in $M^{\prime}$, then the total effect from a variable
$V_{i}$ to $V_{j}$ in $M$ is equal to the total effect from $V^{\prime}_{i}$
to $V_{j}$ in $M^{\prime}$, i.e.,
$\texttt{TE}_{M_{0}}(\\{V_{i}\\},V_{j})=\texttt{TE}_{M^{\prime}}(\\{V^{\prime}_{i}\\},V_{j})$.

Proof of (1): Consider a set of models $M_{0},M_{1},\cdots,M_{m}$, where
$M_{0}=M$, and $M_{k}$ changes the centers $V_{i_{1}}\cdots,V_{i_{k}}$ in
$M_{0}$ to $V_{j_{1}}\cdots,V_{j_{k}}$; $k\in[m]$. In the following, we show
that for all $k\in[m]$, obtaining $M_{k}$ from $M_{0}$ as described above does
not add extra edges in $M_{k}$.

We start with $k=1$. The structural equations of $V_{i_{1}}$ and $V_{j_{1}}$
in $M_{0}$ are:

$\displaystyle V_{i_{1}}$ $\displaystyle=\sum_{l:V_{l}\in
Pa_{M_{0}}(V_{i_{1}})}a_{i_{1}l}V_{l}+N_{V_{i_{1}}},$ (12) $\displaystyle
V_{j_{1}}$ $\displaystyle=\sum_{l_{j}:V_{l_{j}}\in
Pa_{M_{0}}(V_{j_{1}})\setminus\\{V_{i_{1}}\\}}a_{j_{1}l_{j}}V_{l_{j}}+a_{j_{1}i_{1}}V_{i_{1}},$
(13)

Further, the structural equation of any child $V_{k_{1}}$ of $V_{i_{1}}$ in
$M_{0}$ is:

$\displaystyle V_{k_{1}}$ $\displaystyle=\sum_{l_{k}:V_{l_{k}}\in
Pa_{M_{0}}(V_{k_{1}})\setminus\\{V_{i_{1}}\\}}a_{k_{1}l_{k}}V_{l_{k}}+a_{k_{1}i_{1}}V_{i_{1}}+N_{V_{k_{1}}}.$
(14)

Note that $N_{V_{k_{1}}}=0$ if and only if $V_{k_{1}}$ is a u-leaf node.

In $M_{1}$, since we only swap $V_{i_{1}}$ and $V_{j_{1}}$, the structural
equations of all variables in
$\mathcal{Z}\cup\mathcal{Y}\setminus\\{V_{i_{1}},V_{j_{1}}\\}\cup
Ch_{M_{0}}(V_{i_{1}})$ remain the same as those in $M_{0}$. From (12) and
(13), the structural equation of $V_{j_{1}}$ in $M_{1}$:

$\displaystyle V_{j_{1}}$ $\displaystyle=\sum_{l_{j}:V_{l_{j}}\in
Pa_{M_{0}}(V_{j_{1}})\setminus\\{V_{i_{1}}\\}}a_{j_{1}l_{j}}V_{l_{j}}+a_{j_{1}i_{1}}\left(\sum_{l:V_{l}\in
Pa_{M_{0}}(V_{i_{1}})}a_{i_{1}l}V_{l}+N_{V_{i_{1}}}\right)$
$\displaystyle=\sum_{l:V_{l}\in
Pa_{M_{0}}(V_{i_{1}})}a_{j_{1}i_{1}}a_{i_{1}l}V_{l}+\sum_{l_{j}:V_{l_{j}}\in
Pa_{M_{0}}(V_{j_{1}})\setminus\\{V_{i_{1}}\\}}a_{j_{1}l_{j}}V_{l_{j}}+a_{j_{1}i_{1}}N_{V_{i_{1}}}.$

Since the edge $V_{i_{1}}\rightarrow V_{j_{1}}$ violates Condition 1(a),
$Pa_{M_{0}}(V_{j_{1}})\setminus\\{V_{i_{1}}\\}\subseteq
Pa_{M_{0}}(V_{i_{1}})$. By defining $a^{\prime}_{j_{1}l}\triangleq
a_{j_{1}i_{1}}a_{i_{1}l}+a_{j_{1}l}\mathbf{1}[V_{l}\in Pa_{M_{0}}(V_{j_{1}})]$
for all $V_{l}\in Pa_{M_{0}}(V_{i_{1}})$, we can re-write $V_{j_{1}}$ as

$V_{j_{1}}=\sum_{V_{l}\in
Pa_{M_{0}}(V_{i_{1}})}a^{\prime}_{j_{1}l}V_{l}+a_{j_{1}i_{1}}N_{V_{i_{1}}}.$
(15)

Next, from (13), the structural equation of $V_{i_{1}}$ in $M_{1}$ is:

$V_{i_{1}}=\frac{1}{a_{j_{1}i_{1}}}V_{j_{1}}-\sum_{l_{j}:V_{l_{j}}\in
Pa_{M_{0}}(V_{j_{1}})\setminus\\{V_{i_{1}}\\}}\frac{a_{j_{1}l_{j}}}{a_{j_{1}i_{1}}}V_{l_{j}}.$
(16)

Lastly, by substituting $V_{i_{1}}$ in (14) by (16), the structural equation
of $V_{k_{1}}$ in $M_{1}$ is:

$\displaystyle V_{k_{1}}$ $\displaystyle=\sum_{l_{k}:V_{l_{k}}\in
Pa_{M_{0}}(V_{k_{1}})\setminus\\{V_{i_{1}}\\}}a_{k_{1}l_{k}}V_{l_{k}}+a_{k_{1}i_{1}}\left(\frac{1}{a_{j_{1}i_{1}}}V_{j_{1}}-\sum_{l_{j}:V_{l_{j}}\in
Pa_{M_{0}}(V_{j_{1}})\setminus\\{V_{i_{1}}\\}}\frac{a_{j_{1}l_{j}}}{a_{j_{1}i_{1}}}V_{l_{j}}\right)+N_{V_{k_{1}}}.$

Since $V_{i_{1}}\rightarrow V_{j_{1}}$ violates Condition 1(b),
$Pa_{M_{0}}(V_{j_{1}})\subseteq Pa_{M_{0}}(V_{k_{1}})$. Therefore, by defining
$a^{\prime}_{k_{1}l_{k}}\triangleq
a_{k_{1}l_{k}}-\frac{a_{k_{1}i_{1}}a_{j_{1}l_{k}}}{a_{j_{1}i_{1}}}\mathbf{1}[V_{l_{k}}\in
Pa_{M_{0}}(V_{j_{1}})]$, we can re-write $V_{k_{1}}$ as

$V_{k_{1}}=\sum_{l_{k}:V_{l_{k}}\in
Pa_{M_{0}}(V_{k_{1}})\setminus\\{V_{i_{1}}\\}}a^{\prime}_{k_{1}l_{k}}V_{l_{k}}+\frac{a_{k_{1}i_{1}}}{a_{j_{1}i_{1}}}V_{j_{1}}+N_{V_{k_{1}}}.$
(17)

Recall that in $M_{1}$, the structural equations of all underlying variables
in $\mathcal{Z}\cup\mathcal{Y}\setminus\\{V_{i_{1}},V_{j_{1}}\\}\cup
Ch_{M_{0}}(V_{i_{1}})$ are the same as $M_{0}$. Further, the structural
equations of $V_{i_{1}}$, $V_{j_{1}}$ and any $V_{k_{1}}\in
Ch_{M_{0}}(V_{i_{1}})$ in (12)-(14) are replaced by (15)-(17). Thus, we have
$Pa_{M_{1}}(V_{j_{1}})=Pa_{M_{0}}(V_{i_{1}})$,
$Pa_{M_{1}}(V_{i_{1}})=\\{V_{j_{1}}\\}\cup
Pa_{M_{0}}(V_{j_{1}})\setminus\\{V_{i_{1}}\\}$, and
$Pa_{M_{1}}(V_{k_{1}})=\\{V_{j_{1}}\\}\cup
Pa_{M_{0}}(V_{k_{1}})\setminus\\{V_{i_{1}}\\}$. Therefore no edge will be
added in $M_{1}$, and $V_{i_{g}}\rightarrow V_{j_{g}}$ still violates
Condition 1 in $M_{1}$ for all $g=[2:m]$.

Note that $Pa_{M_{1}}(V_{j_{1}})$ (resp. $Pa_{M_{1}}(V_{k_{1}})$) may be a
subset of $Pa_{M_{0}}(V_{i_{1}})$ (resp. $\\{V_{j_{1}}\\}\cup
Pa_{M_{0}}(V_{k_{1}})\setminus\\{V_{i_{1}}\\}$) due to certain parameter
cancellation in $a^{\prime}_{j_{1}l}$ (resp. $a^{\prime}_{k_{1}l_{k}}$).
However, it does not affect our conclusion here as we show that no edges are
added in $M_{1}$. We will show in Part (2) that if this parameter cancellation
happens (at any point of the procedure of swapping centers), then the model
violates faithfulness assumption.

Next, consider $k=2$. Repeating the same procedure of swapping centers, the
structural equations of $M_{2}$ can be obtained from $M_{1}$. Similarly, we
have $Pa_{M_{2}}(V_{j_{2}})=Pa_{M_{1}}(V_{i_{2}})$,
$Pa_{M_{2}}(V_{i_{2}})=\\{V_{j_{2}}\\}\cup
Pa_{M_{1}}(V_{j_{2}})\setminus\\{V_{i_{2}}\\}$, and
$Pa_{M_{2}}(V_{k_{2}})=\\{V_{j_{2}}\\}\cup
Pa_{M_{1}}(V_{k_{2}})\setminus\\{V_{i_{2}}\\}$. Therefore, no edge will be
added when obtaining $M_{2}$ from $M_{0}$.

By repeating the same procedure for $k=3,\cdots,m$, we conclude that obtaining
the final model $M_{m}$ from $M_{0}$ does not add additional edges in $M_{m}$
compared to $M_{0}$.

Proof of (2): Following the procedure of swapping centers described in Part
(1), we show that if any edge from $M_{0}$ is removed in $M_{m}$, then the
ground-truth model $M_{0}$ violates Assumption 2. Suppose the edge from
$V_{0}$ to $V$ in $M_{0}$ is removed in $M_{m}$. Here “edge removal” means
that there is an edge from $V_{0}$ to $V$ in $M_{0}$, but there is no edge
from $V_{0}$ (or the node that replaces $V_{0}$) to $V$ (or the node that
replaces $V$) in $M_{m}$. Note that $V_{0}$ is an nu-leaf node in $M_{0}$,
which is not necessarily the case for $V$. Hence we consider each of the
following cases:

  1. (i)

$V$ is not swapped with any other nodes, i.e.,
$V\not\in\\{V_{i_{1}},\cdots,V_{i_{m}},V_{j_{1}}\cdots,V_{j_{m}}\\}$. This
means that $V_{0}$ is a parent of $V$ in $M_{0}$, but $V_{0}$ (or the node
that replaces $V_{0}$) is not a parent of $V$ in $M_{m}$.

  2. (ii)

$V=V_{i_{k}}$ for some $k\in[m]$. This means that $V_{0}$ is a parent of a
center node $V_{i_{k}}$ in $M_{0}$, but $V_{0}$ (or the node that replaces
$V_{0}$) is not a parent of the center node $V_{j_{k}}$ in $M_{m}$.

  3. (iii)

$V=V_{j_{k}}$ for some $k\in[m]$. This means that $V_{0}$ is a parent of a
non-center node $V_{j_{k}}$ in $M_{0}$, but $V_{0}$ (or the node that replaces
$V_{0}$) is not a parent of the non-center node $V_{i_{k}}$ in $M_{m}$.

_Case (i)._ Suppose $V$ is not swapped with any other nodes. Since the edge
from $V_{0}$ to $V$ is removed in $M_{m}$, $V$ has at least one less parent in
$M_{m}$ than in $M_{0}$. This means that the total effects of $An_{M_{m}}(V)$
on $V$, i.e., $\texttt{TE}_{M_{m}}(An_{M_{m}}(V),V)$, can be written as a
linear combination of the total effects of $An_{M_{m}}(V)$ on parents of $V$
in $M_{m}$, i.e., vectors in
$\\{\texttt{TE}_{M_{m}}(An_{M_{m}}(V),V^{\prime}):V^{\prime}\in
Pa_{M_{m}}(V)\\}$. Further, following the procedure of swapping centers, all
parents of $V$ in $M_{m}$ are possible parents of $V$ in $M_{0}$. Note that
$\texttt{TE}_{M_{m}}(An_{M_{m}}(V),V)=\texttt{TE}_{M_{0}}(An_{M_{0}}(V),V)$,
and for any possible parents $V^{\prime}$ of $V$ in $M_{0}$,
$\texttt{TE}_{M_{m}}(An_{M_{m}}(V),V^{\prime})=\texttt{TE}_{M_{0}}(An_{M_{0}}(V),V^{\prime})$.
Therefore, $V$ violates Assumption 2 _(b1)_ on $M_{0}$.

_Case (ii)._ Suppose $V=V_{i_{k}}$ for some $k\in[m]$. Since the edge from
$V_{0}$ to $V_{j_{k}}$ is removed in $M_{m}$, $V_{j_{k}}$ has at least one
less parent in $M_{m}$ than $V_{i_{k}}$ has in $M_{0}$. This means that
$\texttt{TE}_{M_{m}}(An_{M_{m}}(V_{j_{k}}),V_{j_{k}})$ can be written as a
linear combination of at most $|Pa_{M_{0}}(V_{i_{k}})|-1$ vectors in
$\\{\texttt{TE}_{M_{m}}(An_{M_{m}}(V_{j_{k}}),V^{\prime}):V^{\prime}\in
Pa_{M_{m}}(V_{j_{k}})\\}$. Note that $|Pa_{M_{0}}(V_{i_{k}})\cup
Pa_{M_{0}}(V_{j_{k}})|-1=|Pa_{M_{0}}(V_{i_{k}})|$ since
$Pa_{M_{0}}(V_{j_{k}})\setminus\\{V_{i_{k}}\\}$ is a subset of
$Pa_{M_{0}}(V_{i_{k}})$. Further, all parents of $V_{j_{k}}$ in $M_{m}$ are
possible parents of $V_{i_{k}}$ in $M_{0}$. Note that
$\texttt{TE}_{M_{0}}(An_{M_{0}}(V_{j_{k}})\setminus\\{V_{i_{k}}\\},V_{j_{k}})=\texttt{TE}_{M_{m}}(An_{M_{m}}(V_{j_{k}}),V_{j_{k}})$,
and for any possible parents $V^{\prime}$ of $V_{i_{k}}$ in $M_{0}$,
$\texttt{TE}_{M_{0}}(An_{M_{0}}(V_{j_{k}})\setminus\\{V_{i_{k}}\\},V^{\prime})=\texttt{TE}_{M_{m}}(An_{M_{m}}(V_{j_{k}}),V^{\prime})$.
Therefore, $V_{j_{k}}$ violates Assumption 2 _(b2)_ on $M_{0}$.

_Case (iii)._ Suppose $V=V_{j_{k}}$ for some $k\in[m]$. Note that following
the procedure of swapping centers, for any $g>k$, replacing $V_{i_{g}}$ by
$V_{j_{g}}$ does not change the structural equations of $V_{i_{k}}$ and
$V_{j_{k}}$. Therefore, if $V_{0}$ (or the node that replaces $V_{0}$) is not
a parent of $V_{i_{k}}$ in $M_{m}$, then it is not a parent of $V_{i_{k}}$ in
$M_{k}$. Further, according to Equations (13) and (16), when replacing
$V_{j_{k}}$ by $V_{i_{k}}$, the parent set of $V_{i_{k}}$ in $M_{k}$,
excluding $V_{j_{k}}$, is exactly the same as the parent set of $V_{j_{k}}$
before the swapping (i.e., in $M_{k-1}$) excluding $V_{i_{k}}$. Therefore,
$V_{0}$ (or the node that replaces $V_{0}$) is not a parent of $V_{j_{k}}$ in
$M_{k-1}$, while $V_{0}$ is a parent of a $V_{j_{k}}$ in $M_{0}$. Recall that
$V_{j_{k}}$ is not swapped with any other nodes from $M_{0}$ to $M_{k-1}$.
Therefore this reduces to the Case (i) above, which indicates that $V_{j_{k}}$
violates Assumption 2 _(b1)_ in $M_{0}$.

In conclusion, if the ground-truth satisfies Assumption 2, then the procedure
of swapping centers described in Part (1) does not remove any edge from
$M_{0}$.

Proof of (3): From Parts (1) and (2), we conclude that the structure of the
new model $M_{m}$ is isomorphic to $M_{0}$. Specifically, we can construct a
mapping $\sigma$ from the nodes in $M_{0}$ to the nodes in $M_{m}$, where

$\displaystyle\sigma(V)=V,\quad
V\in\mathcal{Z}\cup\mathcal{Y}\setminus\\{V_{i_{1}},\cdots,V_{i_{m}},V_{j_{1}},\cdots,V_{j_{m}}\\};$
$\displaystyle\sigma(V_{i_{k}})=V_{j_{k}},\quad\sigma(V_{j_{k}})=V_{i_{k}},\quad\forall
k\in[m].$

Under this mapping, there is an edge from node $V^{\prime}$ to
$V^{\prime\prime}$ in $M_{0}$ if and only if this is an edge from
$\sigma(V^{\prime})$ to $\sigma(V^{\prime\prime})$ in $M_{m}$, for all
$V^{\prime},V^{\prime\prime}\in\mathcal{Z}\cup\mathcal{Y}$. Note that this
mapping only switches pairs of nodes that belong to the same direct ordered
group. This means that $M_{m}$ has the same edges across groups, which
completes the proof of Proposition 3.

In the following, we show that if $M_{0}$ satisfies Assumption 2, then $M_{m}$
satisfies Assumption 2. Note that since the DOG is a more refined partition of
AOG, according to the proof of Theorem 2, Assumption 2 _(a)_ is satisfied.
Therefore we only need to verify Assumption 2 _(b)_. For each variable $V$, we
consider each of the three following cases:

  1. (i)

$V\not\in\\{V_{i_{1}},\cdots,V_{i_{m}},V_{j_{1}}\cdots,V_{j_{m}}\\}$, i.e.,
$V$ is not changed from $M_{0}$ to $M_{m}$.

  2. (ii)

$V=V_{i_{k}}$ for some $k\in[m]$, i.e., $V$ is a center node in $M_{0}$ and is
changed to a non-center node in $M_{m}$.

  3. (iii)

$V=V_{j_{k}}$ for some $k\in[m]$, i.e., $V$ is a non-center node in $M_{0}$
and is changed to a center node in $M_{m}$.

_Case (i)._ Suppose
$V\not\in\\{V_{i_{1}},\cdots,V_{i_{m}},V_{j_{1}}\cdots,V_{j_{m}}\\}$. Note
that any possible parent of $V$ in $M_{0}$ is also a possible parent of $V$ in
$M_{m}$, and for all $V^{\prime}\in\\{\text{Possible parents of }V\text{ in
}M_{m}\\}\cup\\{V\\}$,
$\texttt{TE}_{M_{0}}(An_{M_{0}}(V),V^{\prime})=\texttt{TE}_{M_{m}}(An_{M_{m}}(V),V^{\prime})$.
Further, if the parent set of any u-leaf node $V^{\prime}$ in $M_{0}$ is a
subset of $Pa_{M_{0}}(V)$, then the parent set of any u-leaf node in this
direct ordered group in $M_{m}$ is a subset of $Pa_{M_{m}}(V)$. Therefore
Assumption 2 _(b1)_ holds for $V$ on $M_{m}$.

Similarly, for Assumption 2 _(b2)_ , for each parent $V_{0}$ of u-leaf node
$V$ in $M_{m}$, denote $V^{\prime}_{0}$ as the center of the direct ordered
group of $V_{0}$ in $M_{m}$. Then any possible parent of $V^{\prime}_{0}$ in
$M_{0}$ is also a possible parent of $V_{0}$ in $M_{m}$, and for all
$V^{\prime}\in\\{\text{Possible parents of }V_{0}\text{ in
}M_{m}\\}\cup\\{V\\}$,
$\texttt{TE}_{M_{0}}(An_{M_{0}}(V)\setminus\\{V^{\prime}_{0}\\},V^{\prime})=\texttt{TE}_{M_{m}}(An_{M_{m}}(V)\setminus\\{V_{0}\\},V^{\prime})$.
Therefore Assumption 2 _(b2)_ holds for $V$ on $M_{m}$.

_Case (ii)._ Suppose $V=V_{i_{k}}$ for some $k\in[m]$. Since $V_{i_{k}}$ is a
nu-leaf node in $M_{0}$,
$\texttt{TE}_{M_{0}}(An_{M_{0}}(V_{i_{k}}),V_{i_{k}})=\texttt{TE}_{M_{m}}(An_{M_{m}}(V_{i_{k}})\setminus\\{V_{j_{k}}\\},V_{i_{k}})$.
Further, any possible parent of $V_{i_{k}}$ in $M_{0}$ is a possible parent of
$V_{j_{k}}$ in $M_{m}$, and
$|Pa_{M_{0}}(V_{i_{k}})|=|Pa_{M_{m}}(V_{j_{k}})|=|Pa_{M_{m}}(V_{j_{k}})\cup
Pa_{M_{m}}(V_{i_{k}})\setminus\\{V_{j_{k}}\\}|$. Besides, if the parent set of
any u-leaf node $V^{\prime}$ in $M_{0}$ is a subset of
$Pa_{M_{0}}(V_{i_{k}})$, then the parent set of any u-leaf node in this direct
ordered group in $M_{m}$ is also a subset of $Pa_{M_{m}}(V_{j_{k}})$.
Therefore, since Assumption 2 _(b1)_ holds for $V_{i_{k}}$ on $M_{0}$,
Assumption 2 _(b2)_ holds for $V_{i_{k}}$ on $M_{m}$.

As for Assumption 2 _(b1)_ , note that the set of possible parents of
$V_{i_{k}}$ in $M_{m}$ includes all other variable in the same ancestral
ordered group as $V_{i_{k}}$ in $M_{0}$, and is not the same as the set of
possible parents of $V_{i_{k}}$ in $M_{0}$. If
$\texttt{TE}_{M_{m}}(An_{M_{m}}(V_{i_{k}}),V_{i_{k}})$ can be written as a
linear combination of $k\leq|Pa_{M_{m}}(V_{i_{k}})|$ vectors from the set
$\\{\texttt{TE}_{M_{m}}(An_{M_{m}}(V_{i_{k}}),V^{\prime}):V^{\prime}\text{ is
a possible parent of }V_{i_{k}}\text{ in }M_{0}\\}$, denote the set of the
possible parents that corresponds to these vectors as $\mathcal{K}$. Then at
least one of the variables in $\mathcal{K}$ belongs to the ancestral ordered
group of $V_{i_{k}}$ in $M_{0}$. Denote this variable as $V$. This means that
$\texttt{TE}_{M_{m}}(An_{M_{m}}(V_{i_{k}}),V)$ can be written as a linear
combination of $k$ vectors which includes
$\texttt{TE}_{M_{m}}(An_{M_{m}}(V_{i_{k}}),V_{i_{k}})$ and
$\\{\texttt{TE}_{M_{m}}(An_{M_{m}}(V_{i_{k}}),V^{\prime}):V^{\prime}\in\mathcal{K}\setminus\\{V\\}\\}$.
Since $V$ is a u-leaf node in $M_{0}$, any variable in
$\mathcal{K}\setminus\\{V\\}$ is a possible parent of $V$ in $M_{0}$, and
$\texttt{TE}_{M_{m}}(An_{M_{m}}(V_{i_{k}}),V^{\prime})=\texttt{TE}_{M_{0}}(An_{M_{0}}(V),V^{\prime})$
for all $V^{\prime}\in\mathcal{K}\cup\\{V_{i_{k}}\\}$. This means that that
$\texttt{TE}_{M_{0}}(An_{M_{0}}(V),V)$ can be written as a linear combination
of $k$ vectors which includes $\texttt{TE}_{M_{0}}(An_{M_{0}}(V),V_{i_{k}})$
and
$\\{\texttt{TE}_{M_{0}}(An_{M_{0}}(V),V^{\prime}):V^{\prime}\in\mathcal{K}\setminus\\{V\\}\\}$.
Besides, according to our condition,
$|Pa_{M_{m}}(V_{i_{k}})|\leq|Pa_{M_{0}}(V)|$ (otherwise $V_{i_{k}}$ does not
belong to the same direct ordered group as $V_{j_{k}}$). Therefore, since
Assumption 2 _(b1)_ holds for $V$ on $M_{0}$,
$|Pa_{M_{0}}(V)|=|Pa_{M_{m}}(V_{i_{k}})|=k$, and the parent set of the
variables in $\mathcal{K}$ that are u-leaf nodes in $M_{0}$ must be a subset
of $Pa_{M_{0}}(V)$. This implies that parent set of the variables in
$\mathcal{K}$ that are u-leaf nodes in $M_{m}$ must be a subset of
$Pa_{M_{m}}(V_{i_{k}})$. Therefore, Assumption 2 _(b1)_ holds for $V_{i_{k}}$
on $M_{m}$.

_Case (iii)._ Suppose $V=V_{j_{k}}$ for some $k\in[m]$. Since $V_{j_{k}}$ is a
u-leaf node in $M_{0}$,
$\texttt{TE}_{M_{m}}(An_{M_{m}}(V_{j_{k}}),V_{j_{k}})=\texttt{TE}_{M_{0}}(An_{M_{0}}(V_{j_{k}})\setminus\\{V_{i_{k}}\\},V_{j_{k}})$.
Further, any possible parent of $V_{i_{k}}$ in $M_{0}$ is a possible parent of
$V_{j_{k}}$ in $M_{m}$, and $|Pa_{M_{m}}(V_{j_{k}})|=|Pa_{M_{0}}(V_{i_{k}})|$.
Besides, if the parent set of any u-leaf node $V^{\prime}$ in $M_{0}$ is a
subset of $Pa_{M_{0}}(V_{i_{k}})$, then the parent set of any u-leaf node in
this direct ordered group in $M_{m}$ is also a subset of
$Pa_{M_{m}}(V_{j_{k}})$. Therefore, since Assumption 2 _(b2)_ holds for
$V_{j_{k}}$ on $M_{0}$, Assumption 2 _(b1)_ holds for $V_{j_{k}}$ on $M_{m}$.

To sum up, Assumption 2 _(b)_ holds for every variable on $M_{m}$. Hence
$M_{m}$ satisfies Assumption 2.

Conclusion: We showed that by replacing some centers in the ground-truth
$M_{0}$ by some other nodes in the same direct ordered group, we can get an
alternative model $M_{m}$ that (1) has the same mixing matrix, (2) has an
isomorphic graph structure to $M_{0}$, and (3) satisfies Assumption 2.
Therefore we cannot distinguish $M_{0}$ from any other model in the DOG
equivalence class.

####  C.3.2 Proof of sufficiency

To prove sufficiency, we show that any model that has the same mixing matrix
as the ground-truth but does not belong to the same DOG equivalence class
violates Assumption 2. Recall that Theorem 2 implies that any model with the
same mixing matrix as the ground-truth, but does not belong to its AOG
equivalence class, violates Assumption 2 _(a)_. Consequently, it remains to
prove that any model that belongs to the AOG equivalence class of the ground-
truth, but does not belong to its DOG equivalence class, violates Assumption 2
_(b)_. Recall from Proposition 2 that models in the same AOG equivalence class
can be identified by the choice of the centers in each ancestral ordered
group. Therefore, we show that, given the ground-truth and the choice of the
centers, where at least one selected center does not belong to the direct
ordered group of the u-leaf node in the ground-truth: (1) at least one edge is
added to the ground-truth; (2) no edge in the ground-truth is removed, and at
least one added edge is not removed; (3) the alternative model violates
Assumption 2 _(b)_. Therefore Proposition 4 holds.

In the following, we refer to the centers as the centers of the ancestral
ordered groups, unless otherwise stated.

Suppose that $V_{i_{1}},\cdots,V_{i_{m}}$ represent some centers of the
ancestral ordered groups in the ground-truth $M$, where $m\leq p_{n}$, and
$\\{i_{1},\cdots,i_{m}\\}$ is consistent with the causal order among the nu-
leaf nodes in $M$. Now, the centers in $M^{\prime}$ are changed from
$V_{i_{1}},\cdots,V_{i_{m}}$ to $V_{j_{1}},\cdots,V_{j_{m}}$, where
$V_{i_{k}}$ and $V_{j_{k}}$ belong to the same ancestral ordered group,
$\forall k\in[m]$. Further, at least one pair of $(V_{i_{k}},V_{j_{k}})$,
$k\in[m]$ does not belong to the same direct ordered group.

Proof of (1): Consider the same set of models $M_{0},M_{1},\cdots,M_{m}$ as in
the necessity proof, where $M_{0}=M$, and $M_{k}$ changes the centers
$V_{i_{1}}\cdots,V_{i_{k}}$ in $M_{0}$ to $V_{j_{1}}\cdots,V_{j_{k}}$;
$k\in[m]$. In the following, we show that if at least one pair of
$(V_{i_{g}},V_{j_{g}})$, $g\in[k]$ does not belong to the direct ordered
group, then obtaining $M_{k}$ from $M_{0}$ as described above adds at least
one extra edge.

We start from $k=1$. We have shown that if $V_{j_{1}}$ and $V_{i_{1}}$ are in
the same direct ordered group, then obtaining $M_{1}$ from $M_{0}$ does not
add any edge to the model. Therefore we only focus on the case when
$V_{j_{1}}$ and $V_{i_{1}}$ are in different direct ordered groups. The true
structural equations of $V_{i_{1}}$ and $V_{j_{1}}$ and $V_{k_{1}}\in
Ch_{M_{0}}(V_{i_{1}})$ in $M_{0}$ are the same as Equations (12)-(14) so we
will not repeat them here. The structural equation of $V_{j_{1}}$ in $M_{1}$
is:

$\displaystyle V_{j_{1}}$ $\displaystyle=\sum_{l:V_{l}\in
Pa_{M_{0}}(V_{i_{1}})}a_{j_{1}i_{1}}a_{i_{1}l}V_{l}+\sum_{l_{j}:V_{l_{j}}\in