# Causal Discovery in the Presence of Measurement Error: Identifiability
Conditions

Kun Zhang†, Mingming Gong⋆†, Joseph Ramsey†, Kayhan Batmanghelich⋆, Peter
Spirtes†, Clark Glymour†
†Department of philosophy, Carnegie Mellon University
⋆Department of Biomedical Informatics, University of Pittsburgh

###### Abstract

Measurement error in the observed values of the variables can greatly change
the output of various causal discovery methods. This problem has received much
attention in multiple fields, but it is not clear to what extent the causal
model for the measurement-error-free variables can be identified in the
presence of measurement error with unknown variance. In this paper, we study
precise sufficient identifiability conditions for the measurement-error-free
causal model and show what information of the causal model can be recovered
from observed data. In particular, we present two different sets of
identifiability conditions, based on the second-order statistics and higher-
order statistics of the data, respectively. The former was inspired by the
relationship between the generating model of the measurement-error-
contaminated data and the factor analysis model, and the latter makes use of
the identifiability result of the over-complete independent component analysis
problem.

##  1 Introduction

Understanding and using causal relations among variables of interest has been
a fundamental problem in various fields, including biology, neuroscience, and
social sciences. Since interventions or controlled randomized experiments are
usually expensive or even impossible to conduct, discovering causal
information from observational data, known as causal discovery (Spirtes et
al., 2001; Pearl, 2000), has been an important task and received much
attention in computer science, statistics, and philosophy. Roughly speaking,
methods for causal discovery are categorized into constraint-based ones, such
as the PC algorithm (Spirtes et al., 2001), and score-based ones, such as
Greedy Equivalence Search (GES) (Chickering, 2002).

Causal discovery algorithms aim to find the causal relations among the
observed variables. However, in many cases the measured variables are not
identical to the variables we intend to measure. For instance, the measured
brain signals may contain error introduced by the instruments, and in social
sciences many variables are not directly measurable and one usually resorts to
proxies (e.g., for “regional security" in a particular area). In this paper,
we assume that the observed variables $X_{i}$, $i=1,...,n$, are generated from
the underlying measurement-noise-free variables $\tilde{X}_{i}$ with
additional random measurement errors ${E}_{i}$:

$X_{i}=\tilde{X}_{i}+E_{i}.$ (1)

Here we assume that the measurement errors $E_{i}$ are independent from
$\tilde{X}_{i}$ and have non-zero variances. We call this model the CAusal
Model with Measurement Error (CAMME). Generally speaking, because of the
presence of measurement errors, the d-separation patterns among $X_{i}$ are
different from those among the underlying variables $\tilde{X}_{i}$. This
generating process has been called the random measurement error model in
(Scheines & Ramsey, 2017). According to the causal Markov condition (Spirtes
et al., 2001; Pearl, 2000), observed variables $X_{i}$ and the underlying
variables $\tilde{X}_{i}$ may have different conditional
independence/dependence relations and, as a consequence, the output of
constraint-based approaches to causal discovery is sensitive to such error, as
demonstrated in (Scheines & Ramsey, 2017). Furthermore, because of the
measurement error, the structural equation models according to which the
measurement-error-free variables $\tilde{X}_{i}$ are generated usually do not
hold for the observed variables $X_{i}$. (In fact, $X_{i}$ follow error-in-
variables models, for which the identifiability of the underlying causal
relation is not clear.) Hence, approaches based on structural equation models,
such as the linear, non-Gaussian, acyclic model (LiNGAM (Shimizu et al.,
2006)), will generally fail to find the correct causal direction and causal
model.

In this paper, we aim to estimate the causal model underlying the measurement-
error-free variables $\tilde{X}_{i}$ from their observed values $X_{i}$
contaminated by random measurement error. We assume linearity of the causal
model and causal sufficiency relative to $\\{\tilde{X}_{i}\\}_{i=1}^{n}$. We
particularly focus on the case where the causal structure for $\tilde{X}_{i}$
is represented by a Directed Acyclic Graph (DAG), although this condition can
be weakened. In order to develop principled causal discovery methods to
recover the causal model for $\\{\tilde{X}_{i}\\}_{i=1}^{n}$ from observed
values of $\\{{X}_{i}\\}_{i=1}^{n}$, we have to address theoretical issues
include

  * •

whether the causal model of interest is completely or partially identifiable
from the contaminated observations,

  * •

what are the precise identifiability conditions, and

  * •

what information in the measured data is essential for estimating the
identifiable causal knowledge.

We make an attempt to answer the above questions on both theoretical and
methodological sides.

One of the main difficulties in dealing with causal discovery in the presence
of measurement error is because the variances of the measurement errors are
unknown. Otherwise, if they are known, one can readily calculate the
covariance matrix of the measurement-error-free variables $\tilde{X}_{i}$ and
apply traditional causal discovery methods such as the PC (Spirtes et al.,
2001) or GES (Chickering, 2002)) algorithm. It is worth noting that there
exist causal discovery methods to deal with confounders, i.e., hidden direct
common causes, such as the Fast Causal Inference (FCI) algorithm (Spirtes et
al., 2001). However, they cannot estimate the causal structure over the latent
variables, which is what we aim to recover in this paper. (Silva et al., 2006)
and (Kummerfeld et al., ) have provided algorithms for recovering latent
variables and their causal relations when each latent variable has multiple
measured effects. Their problem is different from the measurement error
setting we consider, where clustering for latent common causes is not required
and each measured variable is the direct effect of a single "true" variable.
Furthermore, as shown in next section, their models can be seen as special
cases of our setting.

##  2 Effect of Measurement Error on Conditional Independence / Dependence

We use an example to demonstrate how measurement error changes the
(conditional) independence and dependence relationships in the data. More
precisely, we will see how the (conditional) independence and independence
relations between the observed variables $X_{i}$ are different from those
between the measurement-error-free variables $\tilde{X}_{i}$. Suppose we
observe $X_{1}$, $X_{2}$, and $X_{3}$, which are generated from measurement-
error-free variables according to the structure given in Figure 1. Clearly
$\tilde{X}_{1}$ is dependent on $\tilde{X}_{2}$, while $\tilde{X}_{1}$ and
$\tilde{X}_{3}$ are conditionally independent given $\tilde{X}_{2}$. One may
consider general settings for the variances of the measurement errors. For
simplicity, here let us assume that there is only measurement error in
$X_{2}$, i.e., $X_{1}=\tilde{X}_{1}$, $X_{2}=\tilde{X}_{2}+E_{2}$, and
$X_{3}=\tilde{X}_{3}$.

$\tilde{X}_{1}$ $\tilde{X}_{2}$ $\tilde{X}_{3}$ ${X}_{1}$ ${X}_{2}$ ${X}_{3}$
Figure 1: A linear CAMME to demonstrate the effect of measurement error on
conditional independence and dependence relationships. For simplicity, we
consider the special case where there is measurement error only in $X_{2}$,
i.e., $X_{2}=\tilde{X}_{2}+E_{2}$, but $X_{1}=\tilde{X}_{1}$ and
$X_{3}=\tilde{X}_{3}$.

Let $\tilde{\rho}_{12}$ be the correlation coefficient between $\tilde{X_{1}}$
and $\tilde{X_{2}}$ and $\tilde{\rho}_{13,2}$ be the partial correlation
coefficient between $\tilde{X_{1}}$ and $\tilde{X_{3}}$ given $\tilde{X}_{2}$,
which is zero. Let ${\rho}_{12}$ and ${\rho}_{13,2}$ be the corresponding
correlation coefficient and partial correlation coefficient in the presence of
measurement error. We also let
$\tilde{\rho}_{12}=\tilde{\rho}_{23}=\tilde{\rho}$ to make the result simpler.
So we have
${\rho}_{13}=\tilde{\rho}_{13}=\tilde{\rho}_{12}\tilde{\rho}_{23}=\tilde{\rho}^{2}$.
Let
$\gamma=\frac{\mathbb{S}\textrm{td}(E_{2})}{\mathbb{S}\textrm{td}(\tilde{X}_{2})}$.
For the data with measurement error,

$\displaystyle{\rho}_{12}$
$\displaystyle=\frac{\mathbb{C}\textrm{ov}(X_{1},X_{2})}{\mathbb{V}\textrm{ar}^{1/2}(X_{1})\mathbb{V}\textrm{ar}^{1/2}(X_{2})}$
$\displaystyle=\frac{\mathbb{C}\textrm{ov}(\tilde{X}_{1},\tilde{X}_{2})}{\mathbb{V}\textrm{ar}^{1/2}(\tilde{X}_{1})(\mathbb{V}\textrm{ar}(\tilde{X}_{2})+\mathbb{V}\textrm{ar}(E_{2}))^{1/2}}$
$\displaystyle=\frac{\tilde{\rho}}{(1+\gamma^{2})^{1/2}};$
$\displaystyle{\rho}_{13,2}$
$\displaystyle=\frac{\rho_{13}-\rho_{12}\rho_{23}}{(1-\rho_{12}^{2})^{1/2}(1-\rho_{23}^{2})^{1/2}}$
$\displaystyle=\frac{\tilde{\rho}_{13}-\frac{\tilde{\rho}_{12}\tilde{\rho}_{23}}{1+\gamma^{2}}}{\big{(}1-\frac{\tilde{\rho}^{2}}{(1+\gamma^{2})}\big{)}^{1/2}\big{(}1-\frac{\tilde{\rho}^{2}}{(1+\gamma^{2})}\big{)}^{1/2}}$
$\displaystyle=\frac{r^{2}\tilde{\rho}^{2}}{1+\gamma^{2}-\tilde{\rho}^{2}}.$

As the variance of the measurement error in $X_{2}$ increases, $\gamma$ become
larger, and $\rho_{12}$ decreases and finally goes to zero; in contrast,
${\rho}_{13,2}$, which is zero for the measurement-error-free variables, is
increasing and finally converges to $\tilde{\rho}^{2}$. See Figure 2 for an
illustration. In other words, in this example as the variance of the
measurement error in $X_{2}$ increases, $X_{1}$ and $X_{2}$ become more and
more independent, while $X_{1}$ and $X_{3}$ are conditionally more and more
dependent given $X_{2}$. However, for the measurement-error-free variables,
$\tilde{X}_{1}$ and $\tilde{X}_{2}$ are dependent and $\tilde{X}_{1}$ and
$\tilde{X}_{3}$ and conditionally independent given $\tilde{X}_{2}$. Hence,
the structure given by constraint-based approaches to causal discovery on the
observed variables can be very different from the causal structure over
measurement-error-free variables.

One might apply other types of methods instead of the constraint-based ones
for causal discovery from data with measurement error. In fact, as the
measurement-error-free variables are not observable, $\tilde{X}_{2}$ in Figure
1 is actually a confounder for observed variables. As a consequence, generally
speaking, due to the effect of the confounders, the independence noise
assumption underlying functional causal model-based approaches, such as the
method based on the linear, non-Gaussian, acyclic model (Shimizu et al.,
2006), will not hold for the observed variables any more. Figure 3 gives an
illustration on this. Figure 3(a) shows the scatter plot of $X_{1}$ vs.
$X_{2}$ and the regression line from $X_{2}$ to $X_{1}$, where
$\tilde{X}_{2}$, the noise in $\tilde{X}_{1}$, and the measurement error
$E_{2}$, are all uniformly distributed ($\rho=0.4$, and $\gamma=1.4$). As seen
from Figure 3(b), the residual of regressing $X_{1}$ on $X_{2}$ is not
independent from $X_{2}$, although the residual of regressing $\tilde{X}_{1}$
on $\tilde{X}_{2}$ is independent from $\tilde{X}_{2}$. As a result, the
functional causal model-based approaches to causal discovery may also fail to
find the causal structure of the measurement-error-free variables from their
contaminated observations.

Figure 2: The correlation coefficient $\rho_{12}$ between $X_{1}$ and $X_{2}$
and partial correlation coefficient $\rho_{13,2}$ between $X_{1}$ and $X_{3}$
given $X_{2}$ as functions of $\gamma$, the ratio of the standard deviation of
measurement error to the that of $\tilde{X}_{2}$. We have assumed that the
correlation coefficient between $\tilde{X}_{1}$ and $\tilde{X}_{2}$ and that
between $\tilde{X}_{2}$ and $\tilde{X}_{3}$ are the same (denoted by
$\tilde{\rho}$), and that there is measurement error only in $X_{2}$.

(a)

(b)

Figure 3: Illustration on how measurement error leads to dependence between
regression residual and contaminated cause. (a) Scatter plot of $X_{2}$ and
$X_{1}$ with measurement error in $X_{2}$ together with the regression line.
(b) Scatter plot of the regression residual and $X_{2}$. Note that if we
regress $\tilde{X}_{1}$ on $\tilde{X}_{2}$, the residual is independent from
$\tilde{X}_{2}$.

##  3 Canonical Representation of Causal Models with Measurement Error

Let $\tilde{G}$ be the acyclic causal model over $\tilde{X}_{i}$. Here we call
it measurement-error-free causal model. Let $\mathbf{B}$ be the corresponding
causal adjacency matrix for $\tilde{X}_{i}$, in which $B_{ij}$ is the
coefficient of the direct causal influence from $\tilde{X}_{j}$ to
$\tilde{X}_{i}$ and $B_{ii}=0$. We have,

$\tilde{\mathbf{X}}=\mathbf{B}\tilde{\mathbf{X}}+\tilde{\mathbf{E}},$ (2)

where the components of $\tilde{\mathbf{E}}$, $\tilde{E}_{i}$, have non-zero,
finite variances. Then $\tilde{\mathbf{X}}$ is actually a linear
transformation of the error terms in $\tilde{\mathbf{E}}$ because (2) implies

$\tilde{\mathbf{X}}=\underbrace{(\mathbf{I}-\mathbf{B})^{-1}}_{\triangleq\mathbf{A}}\tilde{\mathbf{E}}.$
(3)

Now let us consider two types of nodes of $\tilde{G}$, namely, leaf nodes
(i.e., those that do not influence any other node) and non-leaf nodes.
Accordingly, the noise term in their structural equation models also has
distinct behaviors: If $\tilde{X}_{i}$ is a leaf node, then $\tilde{E}_{i}$
influences only $\tilde{X}_{i}$, not any other; otherwise $\tilde{E}_{i}$
influences $\tilde{X}_{i}$ and at least one other variable, $\tilde{X}_{j}$,
$j\neq i$. Consequently, we can decompose the noise vector into two groups:
$\tilde{\mathbf{E}}^{L}$ consists of the $l$ noise terms that influence only
leaf nodes, and $\tilde{\mathbf{E}}^{\mathrm{\mathrm{NL}}}$ contains the
remaining noise terms. Equation (3) can be rewritten as

$\tilde{\mathbf{X}}=\mathbf{A}^{\mathrm{\mathrm{NL}}}\tilde{\mathbf{E}}^{\mathrm{\mathrm{NL}}}+\mathbf{A}^{L}\tilde{\mathbf{E}}^{L}=\tilde{\mathbf{X}}^{*}+\mathbf{A}^{L}\tilde{\mathbf{E}}^{L},$
(4)

where
$\tilde{\mathbf{X}}^{*}\triangleq\mathbf{A}^{\mathrm{\mathrm{NL}}}\tilde{\mathbf{E}}^{\mathrm{\mathrm{NL}}}$,
$\mathbf{A}^{\mathrm{\mathrm{NL}}}$ and $\mathbf{A}^{L}$ are $n\times(n-l)$
and $n\times l$ matrices, respectively. Here both $A^{L}$ and
$\mathbf{A}^{\mathrm{\mathrm{NL}}}$ have specific structures. All entries of
$\mathbf{A}^{L}$ are 0 or 1; for each column of $\mathbf{A}^{L}$, there is
only one non-zero entry. In contrast, each column of
$\mathbf{A}^{\mathrm{\mathrm{NL}}}$ has at least two non-zero entries,
representing the influences from the corresponding non-leaf noise term.

Further consider the generating process of observed variables $X_{i}$.
Combining (1) and (4) gives

$\displaystyle\mathbf{X}$
$\displaystyle=\tilde{\mathbf{X}}^{*}+\mathbf{A}^{L}\tilde{\mathbf{E}}^{L}+\mathbf{E}=\mathbf{A}^{\mathrm{\mathrm{NL}}}\tilde{\mathbf{E}}^{\mathrm{\mathrm{NL}}}+(\mathbf{A}^{L}\tilde{\mathbf{E}}^{L}+\mathbf{E})$
$\displaystyle=\mathbf{A}^{\mathrm{\mathrm{NL}}}\tilde{\mathbf{E}}^{\mathrm{\mathrm{NL}}}+\mathbf{E}^{*}$
(5)
$\displaystyle=\left[\begin{array}[]{c|c}\mathbf{A}^{\mathrm{\mathrm{NL}}}&\mathbf{I}\end{array}\right]\cdot\left[\begin{array}[]{c}\tilde{\mathbf{E}}^{\mathrm{\mathrm{NL}}}\\\
\hline\cr\vspace{-.27cm}\hfil\\\ \mathbf{E}^{*}\end{array}\right],$ (10)

where $\mathbf{E}^{*}=\mathbf{A}^{L}\tilde{\mathbf{E}}^{L}+\mathbf{E}$ and
$\mathbf{I}$ denotes the identity matrix. To make it more explicit, we give
how $X_{i}^{*}$ and $E_{i}^{*}$ are related to the original CAMME process:

$\displaystyle\tilde{X}_{i}^{*}$
$\displaystyle=\begin{cases}\tilde{X}_{i},&\text{if $\tilde{X}_{i}$ is not a
leaf node in $\tilde{G}$};\\\
\tilde{X}_{i}-\tilde{E}_{i},&\text{otherwise;}\end{cases},~{}\textrm{and}~{}$
(11) $\displaystyle E_{i}^{*}$ $\displaystyle=\begin{cases}E_{i},&\text{if
$\tilde{X}_{i}$ is not a leaf node in $\tilde{G}$};\\\
E_{i}+\tilde{E}_{i},&\text{otherwise.}\end{cases}$

Clearly $E^{*}_{i}$s are independent across $i$, and as we shall see in
Section 4, the information shared by difference $X_{i}$ is still captured by
$\tilde{\mathbf{X}}^{*}$.

######  Proposition 1.

For each CAMME specified by (2) and (1), there always exists an
observationally equivalent representation in the form of (5) or (10),

The proof was actually given in the construction procedure of the
representation (5) or (10) from the original CAMME. We call the representation
(5) or (10) the canonical representation of the underlying CAMME (CR-CAMME).

##### Example Set 1

Consider the following example with three observed variables $X_{i}$,
$i=1,2,3$, for which
$\tilde{X}_{1}\rightarrow\tilde{X}_{2}\leftarrow\tilde{X}_{3}$, with causal
relations $\tilde{X}_{2}=a\tilde{X}_{1}+b\tilde{X}_{3}+\tilde{E}_{2}$. That
is,

$\mathbf{B}=\begin{bmatrix}0&0&0\\\ a&0&b\\\ 0&0&0\end{bmatrix},$

and according to (3),

$\mathbf{A}=\begin{bmatrix}1&0&0\\\ a&1&b\\\ 0&0&1\end{bmatrix}.$

Therefore,

$\displaystyle\mathbf{X}$
$\displaystyle=\tilde{\mathbf{X}}+\mathbf{E}=\tilde{\mathbf{X}}^{*}+\mathbf{E}^{*}$
$\displaystyle=\begin{bmatrix}1&0\\\ a&b\\\
0&1\end{bmatrix}\cdot\begin{bmatrix}\tilde{E}_{1}\\\
\tilde{E}_{3}\end{bmatrix}+\begin{bmatrix}E_{1}\\\ \tilde{E}_{2}+E_{2}\\\
E_{3}\end{bmatrix}$ $\displaystyle=\begin{bmatrix}1&0&\vline&1&0&0\\\
a&b&\vline&0&1&0\\\
0&1&\vline&0&0&1\end{bmatrix}\cdot\begin{bmatrix}\tilde{E}_{1}\\\
\tilde{E}_{3}\\\ E_{1}\\\ \tilde{E}_{2}+E_{2}\\\ E_{3}\end{bmatrix}.$

In causal discovery from observations in the presence of measurement error, we
aim to recover information of the measurement-error-free causal model
$\tilde{G}$. Let us define a new graphical model, $\tilde{G}^{*}$. It is
obtained by replacing variables $\tilde{X}_{i}$ in $\tilde{G}$ with variables
$\tilde{X}_{i}^{*}$. In other words, it has the same causal structure and
causal parameters (given by the $\mathbf{B}$ matrix) as $\tilde{G}$, but its
nodes correspond to variables $\tilde{X}^{*}_{i}$. If we manage to estimate
the structure of and involved causal parameters in $\tilde{G}^{*}$, then
$\tilde{G}$, the causal model of interest, is recovered. Comparing with
$\tilde{G}$, $\tilde{G}^{*}$ involves some deterministic causal relations
because each leaf node is a deterministic function of its parents (the noise
in leaf nodes has been removed; see (11)). We defined the graphical model
$\tilde{G}^{*}$ because we cannot fully estimate the distribution of
measurement-error-free variables $\tilde{\mathbf{X}}$, but might be able to
estimate that of $\tilde{\mathbf{X}}^{*}$, under proper assumptions.

In what follows, most of the time we assume

  * A0.

The causal Markov condition holds for $\tilde{G}$ and the distribution of
$\tilde{X}_{i}^{*}$ is non-deterministically faithful w.r.t. $\tilde{G}^{*}$,
in the sense that if there exists $\mathbf{S}$, a subset of
$\\{\tilde{X}_{k}^{*}\,:\,k\neq i,k\neq j\\}$, such that neither of
$\tilde{X}_{i}^{*}$ and $\tilde{X}_{j}^{*}$ is a deterministic function of
$\mathbf{S}$ and $\tilde{X}_{i}^{*}\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\tilde{X}_{j}^{*}\,|\,\mathbf{S}$ holds, then
$\tilde{X}_{i}^{*}$ and $\tilde{X}_{j}^{*}$ (or $\tilde{X}_{i}$ and
$\tilde{X}_{j}$) are d-separated by $\mathbf{S}$ in $\tilde{G}^{*}$.

This non-deterministically faithfulness assumption excludes a particular type
of parameter coupling in the causal model for $\tilde{X}_{i}$. in Figure 4 we
give a causal model in which the causal coefficients are carefully chosen so
that this assumption is violated: because
$\tilde{X}^{*}_{3}=a\tilde{X}^{*}_{1}+b\tilde{X}^{*}_{2}$ and
$\tilde{X}^{*}_{4}=2a\tilde{X}^{*}_{1}+2b\tilde{X}^{*}_{2}+E_{4}^{*}$, we have
$\tilde{X}^{*}_{4}=2\tilde{X}^{*}_{3}+E_{4}^{*}$, implying
$\tilde{X}_{4}^{*}\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\tilde{X}_{1}^{*}\,|\,\tilde{X}_{3}^{*}$ and
$\tilde{X}_{4}^{*}\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\tilde{X}_{2}^{*}\,|\,\tilde{X}_{3}^{*}$,
which are not given by the causal Markov condition on $\tilde{G}$. We note
that this non-deterministic faithfulness is defined for the distribution of
the constructed variables $\tilde{X}_{i}^{*}$, not the measurement-error-free
variables $\tilde{X}_{i}$. (Bear in mind their relationship given in (11).)
This assumption is generally stronger than the faithfulness assumption for the
distribution of $\tilde{X}_{i}$. In particular, in the causal model given in
Figure 4, the distribution of $\tilde{X}_{i}$ is still faithful w.r.t.
$\tilde{G}$. Below we call the conditional independence relationship between
$\tilde{X}_{i}^{*}$ and $\tilde{X}_{j}^{*}$ given $\mathbf{S}$ where neither
of $\tilde{X}_{i}^{*}$ and $\tilde{X}_{j}^{*}$ is a deterministic function of
$\mathbf{S}$ non-deterministic conditional independence.

$\tilde{X}_{4}$ $\tilde{X}_{2}$ $\tilde{X}_{5}$ $\tilde{X}_{1}$
$\tilde{X}_{3}$ $2b$$d$$c$$a$$b$$2a$ Figure 4: A causal model in which
$\tilde{X}^{*}_{i}$ are not non-deterministically faithful w.r.t. $\tilde{G}$
because of parameter coupling.

Now we have two concerns. One is whether essential information of the CR-CAMME
is identifiable from observed values of $\mathbf{X}$. We are interested in
finding the causal model for (or a particular type of dependence structures
in) $\tilde{\mathbf{X}}$. The CR-CAMME of $\mathbf{X}$, given by (5) or (10),
has two terms, $\tilde{\mathbf{X}}^{*}$ and $\tilde{\mathbf{E}}^{*}$. The
latter is independent across all variables, and the former preserves major
information of the dependence structure in $\tilde{\mathbf{X}}$. Such
essential information of the CR-CAMME may be the covariance matrix of
$\tilde{\mathbf{X}}^{*}$ or the matrix $\mathbf{A}^{\mathrm{\mathrm{NL}}}$, as
discussed in next sections. In the extreme case, suppose such information is
not identifiable at all, then it is hopeless to find the underlying causal
structure of $\tilde{G}$. The other is what information of the original CAMME,
in particular, the causal model over the measurement-error-free variables, can
be estimated from the above identifiable information of the CR-CAMME. Although
the transformation from the original CAMME to a CR-CAMME is straightforward,
without further knowledge there does not necessarily exist a unique CAMME
corresponding to a given CR-CAMME: first, the CR-CAMME does not tell us which
nodes $\tilde{X}_{i}$ are leaf nodes in $\tilde{G}$; second, even if
$\tilde{X}_{i}$ is known to be a leaf node, it is impossible to separate the
measurement error $E_{i}$ from the noise $\tilde{E}_{i}$ in $E^{*}_{i}$.
Fortunately, we are not interested in everything of the original CAMME, but
only the causal graph $\tilde{G}$ and the corresponding causal influences
$\mathbf{B}$.

Accordingly, in the next sections we will explore what information of the CR-
CAMME is identifiable from the observations of $\mathbf{X}$ and how to further
reconstruct necessary information of the original CAMME. In the measurement
error model (1) we assumed that each observed variable $X_{i}$ is generated
from its own latent variable $\tilde{X}_{i}$. We note that in case multiple
observed variables are generated from a single latent variable or a single
observed variable is generated by multiple latent variables (see, e.g., (Silva
et al., 2006)), we can still use the CR-CAMME to represent the process. In the
former case, certain rows of $\mathbf{A}^{\mathrm{\mathrm{NL}}}$ are
identical. For instance, if $X_{1}$ and $X_{2}$ are generated as noisy
observations of the same latent variable, then in (5) the first two rows of
$\mathbf{A}_{\mathrm{\mathrm{NL}}}$ are identical. (More generally, if one
allows different coefficients to generate them from the latent variable, the
two rows are proportional to each other.) Then let us consider an example in
the latter case. Suppose $X_{3}$ is generated by latent variables
$\tilde{X}_{1}$ and $\tilde{X}_{2}$, for each of which there is also an
observable counterpart. Write the causal model as
$X_{3}=f(\tilde{X}_{1},\tilde{X}_{2})+E_{3}$ and introduce the latent variable
$\tilde{X}_{3}=f(\tilde{X}_{1},\tilde{X}_{2})$, and then we have
$X_{3}=\tilde{X}_{3}+E_{3}$. The CR-CAMME formulation then follows.

##  4 Identifiability with Second Order Statistics

The CR-CAMME (5) has a form of the factor analysis model (FA) (Everitt, 1984),
which has been a fundamental tool in data analysis. In its general form, FA
assumes the observable random vector
$\mathbf{X}=(X_{1},X_{2},...,X_{n})^{\intercal}$ was generated by

$\mathbf{X}=\mathbf{Lf}+\mathbf{N},$ (12)

where the factors $\mathbf{f}=(f_{1},...,f_{r})^{\intercal}$ satisfies
$\mathbb{C}\textrm{ov}(\mathbf{f})=\mathbf{I}$, and noise terms, as components
of $\mathbf{N}$, are mutually independent and also independent from
$\mathbf{f}$. Denote by $\boldsymbol{\Psi}_{N}$ the covariance matrix of
$\mathbf{N}$, which is diagonal. The unknowns in (12) are the loading matrix
$\mathbf{L}$ and the covariance matrix $\boldsymbol{\Psi}_{N}$.

Factor analysis only exploits the second-order statistics, i.e., it assumes
that all variables are jointly Gaussian. Clearly in FA $\mathbf{L}$ is not
identifiable; it suffers from at least the right orthogonal transformation
indeterminacy. However, under suitable conditions, some essential information
of FA is generically identifiable, as given in the following lemma.

######  Lemma 2.

For the factor analysis model, when the number of factors
$r<\phi(n)=\frac{2n+1-(8n+1)^{1/2}}{2}$, the model is generically globally
identifiable, in the sense that for randomly generated
$(L,\boldsymbol{\Psi}_{N})$ in (12), it is with only measure 0 that there
exists another representation $(L^{\prime},\boldsymbol{\Psi}^{\prime}_{N})$
such that $(L^{\prime},\boldsymbol{\Psi}^{\prime}_{N})$ and
$(L,\boldsymbol{\Psi}_{N})$ generate the same covariance matrix for
$\mathbf{X}$ and $\boldsymbol{\Psi}^{\prime}_{N}\neq\boldsymbol{\Psi}_{N}$.

This was formulated as a conjecture by (Shapiro, 1985), and was later proven
by (Bekker & ten Berge, 1997). This lemma immediately gives rise to the
following generic identifiability of the variances of measurement errors.111We
note that this “generic identifiability” is sightly weaker than what we want:
we want to show that for certain $(\mathbf{L},\boldsymbol{\Psi}_{\mathbf{N}})$
the model is necessarily identifiable. To give this proof is non-trivial and
is a line of our future research.

######  Proposition 3.

The variances of error terms $E_{i}^{*}$ and the covariance matrix of
$\tilde{\mathbf{X}}^{*}$ in the CR-CAMME (5) are generically identifiable when
the sample size $N\rightarrow\infty$ and the following assumption on the
number of leaf nodes $l$ holds:

  * A1.

The number of leaf variables $l$ satisfies

$\frac{l}{n}>c(n)\triangleq\frac{(8n+1)^{1/2}-1}{2n}.$ (13)

Clearly $c(n)$ is decreasing in $n$ and $c(n)\rightarrow 0$ as
$n\rightarrow\infty$. To give a sense how restrictive the above condition is,
Fig. 5 shows how $c(n)$ changes with $n$. In particular, when $n=4$,
$c(n)=59.3\%$, condition (13) implies the number of leaf nodes is $l>2.4$;
when $n=100$, $c(n)=13.6\%$, condition (13) implies $l>13.6$. Roughly
speaking, as $n$ increases, it is more likely for condition (13) to hold. Note
that the condition given in Proposition 3 is sufficient but not necessary for
the identifiability of the noise variances and the covariance matrix of the
non-leaf hidden variables (Bekker & ten Berge, 1997).

Figure 5: $c(n)$ as a function of $n$.

Now we know that under certain conditions, the covariance matrices of
$\mathbf{E}^{*}$ and $\tilde{\mathbf{X}}^{*}$ in the CR-CAMME (5) are
(asymptotically) identifiable from observed data with measurement error. Can
we recover the measurement-error-free causal model $\tilde{G}$ from them?

###  4.1 Gaussian CAMME with the Same Variance For Measurement Errors

In many problems the variances of the measurement errors in different
variables are roughly the same because the same instrument is used and the
variables are measured in similar ways. For instance, this might approximately
be the case for Functional magnetic resonance imaging (fMRI) recordings. In
fact, if we made the following assumption on the measurement error, the
underlying causal graph $\tilde{G}$ can be estimated at least up to the
equivalence class, as shown in the following corollary.

  * A2.

The measurement errors in all observed variables have the same variance.

######  Proposition 4.

Suppose assumptions A0, A1, and A2 hold. Then as $N\rightarrow\infty$,
$\tilde{G}$ can be estimated up to the equivalence class and, moreover, the
leaf nodes of $\tilde{G}$ are identifiable.

Proofs are given in Appendix. The proof of this corollary inspires a procedure
to estimate the information of $\tilde{G}$ from contaminated observations in
this case, which is denoted by FA+EquVar. It consists of four steps. (1) Apply
FA on the data with a given number of leaf nodes and estimate the variances of
$E^{*}_{i}$ as well as the covariance matrix of
$\tilde{\mathbf{X}}^{*}$.222Here we suppose the number of leaf nodes is given.
In practice one may use model selection methods, such as BIC, to find this
number. (2) The $(n-l)$ smallest values of the variances of $E^{*}_{i}$
correspond to non-leaf nodes, and the remaining $l$ nodes correspond to leaf
nodes. (3) Apply a causal discovery method, such as the PC algorithm, to the
sub-matrix of the estimated covariance matrix of $\tilde{\mathbf{X}}^{*}$
corresponding to non-leaf nodes and find the causal structure over non-leaf
nodes. (4) For each leaf node $X_{i}^{*}$, find the subset of non-leaf nodes
that determines $X_{i}^{*}$, and draw directed edges from those nodes to
$X_{i}^{*}$, and further perform orientation propagation.

###  4.2 Gaussian CAMME: General Case

Now let us consider the general case where we do not have the constraint A2 on
the measurement error. Generally speaking, after performing FA on the data,
the task is to discover causal relations among $\tilde{X}_{i}^{*}$ by
analyzing their estimated covariance matrix, which is, unfortunately,
singular, with the rank $(n-l)$. Then there must exist deterministic relations
among $\tilde{{X}}^{*}_{i}$, and we have to deal with such relations in causal
discovery. Here suppose we simply apply the Deterministic PC (DPC) algorithm
(Glymour, 2007; Luo, 2006) to tackle this problem. DPC is almost identical to
PC, and the only difference is that when testing for conditional independence
relationship $U\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}V\,|\,\mathbf{W}$, if $U$ or $V$ is a
deterministic function of $\mathbf{W}$, one then ignores this test (or
equivalently we do not remove the edge between $U$ and $V$). We denote by
FA+DPC this procedure for causal discovery from data with measurement error.

Under some conditions on the underlying causal model $\tilde{G}$, it can be
estimated up to its equivalence class, as given in the following proposition.
Here we use $\mathrm{PA}(\tilde{X}_{j})$ to denote the set of parents (direct
causes) of $\tilde{X}_{j}$ in $\tilde{G}$.

######  Proposition 5.

Suppose Assumptions A0 and A1 hold. As $N\rightarrow\infty$, compared to
$\tilde{G}$, the graph produced by the above DPC procedure does not contain
any missing edge. In particular, the edges between all non-leaf nodes are
corrected identified. Furthermore, the whole graph of $\tilde{G}$ is
identifiable up to its equivalence class if the following assumption further
holds:

  * A3.

For each pair of leaf nodes $\tilde{X}_{j}$ and $\tilde{X}_{k}$, there exists
$\tilde{X}_{p}\in\mathrm{PA}(\tilde{X}_{j})$ and
$\tilde{X}_{q}\in\mathrm{PA}(\tilde{X}_{k})$ that are d-separated in
$\tilde{G}$ by a variable set $\mathbf{S}_{1}$, which may be the empty set.
Moreover, for each leaf node $\tilde{X}_{j}$ and each non-leaf node
$\tilde{X}_{i}$ which are not adjacent, there exists
$\tilde{X}_{r}\in\mathrm{PA}(\tilde{X}_{j})$ which is d-separated from
$\tilde{X}_{i}$ in $\tilde{G}$ by a variable set $\mathbf{S}_{2}$, which may
be the empty set.

##### Example Set 2 and Discussion

Suppose assumption A0 holds.

  * •

$\tilde{G}_{A}$, given in Figure 6(a), follows assumptions A1 and A3.
According to Proposition 5, the equivalence class of this causal DAG can be
asymptotically estimated from observations with measurement error.

  * •

Assumptions A0, A1, and A3 are sufficient conditions for $\tilde{G}$ to be
recovered up to its equivalence class and, they, especially A3, may not be
necessary. For instance, consider the causal graph $\tilde{G}_{B}$ given in
Figure 6(b), for which assumption A3 does not hold. If assumption A2 holds,
$\tilde{G}_{B}$ can be uniquely estimated from contaminated data. Other
constraints may also guarantee the identifiability of the underlying graph.
For example, suppose all coefficients in the causal model are smaller than one
in absolute value, then $\tilde{G}_{B}$ can also be uniquely estimated from
noisy data. Relaxation of assumption A3 which still guarantees that
$\tilde{G}$ is identifiable up to its equivalence class is a future line of
research.

  * •

The causal graphs $\tilde{G}_{C}$ and $\tilde{G}_{D}$, shown in Figure 6(c),
do not follow A1, so generally speaking, they are not identifiable from
contaminated observations with second-order statistics. This is also the case
for $\tilde{G}_{E}$, shown in Figure 6(d).

$\tilde{X}_{1}$ $\tilde{X}_{2}$ $\tilde{X}_{3}$ $\tilde{X}_{4}$
$\tilde{X}_{5}$ $\tilde{X}_{6}$ $\tilde{X}_{7}$ $\tilde{X}_{8}$
$\tilde{G}_{A}:$

$\tilde{X}_{1}$ $\tilde{X}_{2}$ $\tilde{X}_{3}$ $\tilde{X}_{4}$
$\tilde{G}_{B}:$

$\tilde{X}_{4}$ $\tilde{X}_{2}$ $\tilde{X}_{5}$ $\tilde{X}_{6}$
$\tilde{X}_{1}$ $\tilde{X}_{3}$ $\tilde{G}_{C}$ (solid lines as its edges):
$\tilde{G}_{D}$ (all lines as its edges):

$\tilde{X}_{3}$ $\tilde{X}_{2}$ $\tilde{X}_{6}$ $\tilde{X}_{7}$
$\tilde{X}_{8}$ $\tilde{X}_{1}$ $\tilde{X}_{5}$ $\tilde{X}_{4}$
$\tilde{G}_{E}$:

Figure 6: (a) $\tilde{G}_{A}$: a causal DAG $\tilde{G}$ which follows
assumptions A1 and A3. (b) $\tilde{G}_{B}$: a DAG which follows assumption A1,
but not A3; however, the structure is still identifiable if either assumption
A2 holds or we know that all causal coefficients are smaller than one in
absolute value. (c) Two DAGs that do not follow assumption A1; $\tilde{G}_{C}$
has only the solid lines as its edges, and $\tilde{G}_{D}$ also includes the
dashed line. (d) $\tilde{G}_{E}$: another DAG that does not follow assumption
A1.

##  5 Identifiability with Higher Order Statistics

The method based on second-order statistics exploits FA and deterministic
causal discovery, both of which are computationally relatively efficient.
However, if the number of leaf-nodes is so small that the condition in
Proposition 3 is violated (roughly speaking, usually this does not happen when
$n$ is big, say, bigger than 50, but is likely to be the case when $n$ is very
small, say, smaller than 10), the underlying causal model is not guaranteed to
be identifiable from contaminated observations. Another issue is that with
second-order statistics, the causal model for $\tilde{\mathbf{X}}$ is usually
not uniquely identifiable; in the best case it can be recovered up to its
equivalence class (and leaf nodes). To tackle these issues, below we show that
we can benefit from higher-order statistics of the noise terms.

In this section we further make the following assumption on the distribution
of $\tilde{E}_{i}$:

  * A4.

All $\tilde{E}_{i}$ are non-Gaussian.

We note that under the above assumption, $\mathbf{A}^{\mathrm{\mathrm{NL}}}$
in (10) can be estimated up to the permutation and scaling indeterminacies
(including the sign indeterminacy) of the columns, as given in the following
lemma.

######  Lemma 6.

Suppose assumption A4 holds. Given ${\mathbf{X}}$ which is generated according
to (10), $\mathbf{A}^{\mathrm{\mathrm{NL}}}$ is identifiable up to permutation
and scaling of columns as the sample size $N\rightarrow\infty$.

###### Proof.

This lemma is implied by Theorem 10.3.1 in (Kagan et al., 1973) or Theorem 1
in (Eriksson & Koivunen, 2004). ∎

###  5.1 Non-Gaussian CAMME with the Same Variance For Measurement Errors

We first note that under certain assumptions the underlying graph $\tilde{G}$
is fully identifiable, as shown in the following proposition.

######  Proposition 7.

Suppose the assumptions in Corollary 4 hold, and further suppose assumption A4
holds. Then as $N\rightarrow\infty$, the underlying causal graph $\tilde{G}$
is fully identifiable from observed values of $X_{i}$.

###  5.2 Non-Gaussian CAMME: More General Cases

In the general case, what information of the causal structure $\tilde{G}$ can
we recover? Can we apply existing methods for causal discovery based on
LiNGAM, such as ICA-LiNGAM (Shimizu et al., 2006) and Direct-LiNGAM (Shimizu
et al., 2011), to recover it? LiNGAM assumes that the system is non-
deterministic: each variable is generated as a linear combination of its
direct causes plus a non-degenerate noise term. As a consequence, the linear
transformation from the vector of observed variables to the vector of
independent noise terms is a square matrix; ICA-LiNGAM applies certain
operations to this matrix to find the causal model, and Direct-LiNGAM
estimates the causal ordering by enforcing the property that the residual of
regressing the effect on the root cause is always independent from the root
cause.

In our case, $\mathbf{A}^{\mathrm{NL}}$, the essential part of the mixing
matrix in (10), is $n\times r$, where $r<n$. In other words, for some of the
variables $\tilde{X}_{i}^{*}$, the causal relations are deterministic. (In
fact, if $\tilde{X}_{k}$ is a leaf node in $\tilde{G}$, $\tilde{X}_{k}^{*}$ is
a deterministic function of $\tilde{X}_{k}$’s direct causes.) As a
consequence, unfortunately, the above causal analysis methods based on LiNGAM,
including ICA-LiNGAM and Direct-LiNGAM, do not apply. We will see how to
recover information of $\tilde{G}$ by analyzing the estimated
$\mathbf{A}^{\mathrm{NL}}$.

We will show that some group structure and the group-wise causal ordering in
$\tilde{G}$ can always be recovered. Before presenting the results, let us
define the following recursive group decomposition according to causal
structure $\tilde{G}$.

######  Definition 8 (Recursive group decomposition).

Consider the causal model $\tilde{G}^{*}$. Put all leaf nodes which share the
same direct-and-only-direct node in the same group; further incorporate the
corresponding direct-and-only-direct node in the same group. Here we say a
node $\tilde{X}_{i}^{*}$ is the “direct-and-only-direct" node of
$\tilde{X}_{j}^{*}$ if and only if $\tilde{X}_{i}^{*}$ is a direct cause of
$\tilde{X}_{j}^{*}$ and there is no other directed path from
$\tilde{X}_{i}^{*}$ to $\tilde{X}_{j}^{*}$. For those nodes which are not a
direct-and-only-direct node of any leaf node, each of them forms a separate
group. We call the set of all such groups ordered according to the causal
ordering of the non-leaf nodes in DAG $\tilde{G}^{*}$ a recursive group
decomposition of $\tilde{G}^{*}$, denoted by $\mathcal{G}_{\tilde{G}^{*}}$.

##### Example Set 3

As seen from the process of recursive group decomposition, each non-leaf node
is in one and only one recursive group, and it is possible for multiple leaf
nodes to be in the same group. Therefore, in total there are $(n-l)$ recursive
groups. For example, for $\tilde{G}_{A}$ given in Figure 6(a), a corresponding
group structure for the corresponding $\tilde{G}^{*}$ is
$\mathcal{G}_{\tilde{G}_{A}^{*}}=(\\{\tilde{X}_{1}^{*}\\}\rightarrow\\{\tilde{X}_{2}^{*},\tilde{X}_{5}^{*}\\}\rightarrow\\{\tilde{X}_{3}^{*},\tilde{X}_{6}v\\}\rightarrow\\{\tilde{X}_{4}^{*},\tilde{X}_{7}^{*},\tilde{X}_{8}^{*}\\})$,
and for $\tilde{G}_{B}$ in Figure 6(b), there is only one group:
$\mathcal{G}_{\tilde{G}_{B}^{*}}=(\\{\tilde{X}_{1}^{*},\tilde{X}_{2}^{*},\tilde{X}_{3}^{*},\tilde{X}_{4}^{*}\\})$.
For both $\tilde{G}_{C}$ and $\tilde{G}_{D}$, given in Figure 6(c), a
recursive group decomposition is
$(\\{\tilde{X}_{1}^{*}\\}\rightarrow\\{\tilde{X}_{2}^{*},\tilde{X}_{3}^{*}\\}\rightarrow\\{\tilde{X}_{4}^{*}\\}\rightarrow\\{\tilde{X}_{5}^{*},\tilde{X}_{6}^{*}\\})$.

Note that the causal ordering and the recursive group decomposition of given
variables according to the graphical model $\tilde{G}^{*}$ may not be unique.
For instance, if $\tilde{G}^{*}$ has only two variables $\tilde{X}_{1}^{*}$
and $\tilde{X}_{2}^{*}$ which are not adjacent, both decompositions
$(\tilde{X}_{1}^{*}\rightarrow\tilde{X}_{2}^{*})$ and
$(\tilde{X}_{2}^{*}\rightarrow\tilde{X}_{1}^{*})$ are correct. Consider
$\tilde{G}^{*}$ over three variables,
$\tilde{X}_{1}^{*},\tilde{X}_{2}^{*},\tilde{X}_{3}^{*}$, where
$\tilde{X}_{1}^{*}$ and $\tilde{X}_{2}^{*}$ are not adjacent and are both
causes of $\tilde{X}_{3}^{*}$; then both
$(\tilde{X}_{1}^{*}\rightarrow\\{\tilde{X}_{2}^{*},\tilde{X}_{3}^{*}\\})$ and
$(\tilde{X}_{2}^{*}\rightarrow\\{\tilde{X}_{1}^{*},\tilde{X}_{3}^{*}\\})$ are
valid recursive group decompositions.

We first present a procedure to construct the recursive group decomposition
and the causal ordering among the groups from the estimated
$\mathbf{A}^{\mathrm{NL}}$. We will further show that the recovered recursive
group decomposition is always asymptotically correct under assumption A4.

####  5.2.1 Construction and Identifiability of Recursive Group Decomposition

First of all, Lemma 7 tells us that $\hat{\mathbf{A}}^{\mathrm{NL}}$ in (10)
is identifiable up to permutation and scaling columns. Let us start with the
asymptotic case, where the columns of the estimated $\mathbf{A}^{\mathrm{NL}}$
from values of ${X}_{i}$ are a permuted and rescaled version of the columns of
$\mathbf{A}^{\mathrm{NL}}$. In what follows the permutation and rescaling of
the columns of $\mathbf{A}^{\mathrm{NL}}$ does not change the result, so below
we just work with the true $\mathbf{A}^{\mathrm{NL}}$, instead of its
estimate.

$\tilde{X}_{i}^{*}$ and $\tilde{X}_{i}$ follow the same causal DAG,
$\tilde{G}$, and $\tilde{X}_{i}^{*}$ are causally sufficient, although some
variables among them (corresponding to leaf nodes in $\tilde{G}^{*}$) are
determined by their direct causes. Let us find the causal ordering of
$\tilde{X}_{i}^{*}$. If there are no deterministic relations and the values of
$\tilde{X}_{i}^{*}$ are given, the causal ordering can be estimated by
recursively performing regression and checking independence between the
regression residual and the predictor (Shimizu et al., 2011). Specifically, if
one regresses all the remaining variables on the root cause, the residuals are
always independent from the predictor (the root cause). After detecting a root
cause, the residuals of regressing all the other variables on the discovered
root cause are still causally sufficient and follow a DAG. One can repeat the
above procedure to find a new root cause over such regression residuals, until
no variable is left.

However, in our case we have access to $\mathbf{A}^{\mathrm{NL}}$ but not the
values of $\tilde{X}^{*}_{i}$. Fortunately, the independence between
regression residuals and the predictor can still be checked by analyzing
$\mathbf{A}^{\mathrm{NL}}$. Recall that
$\tilde{\mathbf{X}}^{*}=\mathbf{A}^{\mathrm{NL}}\tilde{\mathbf{E}}^{\mathrm{NL}}$,
where the components of $\tilde{\mathbf{E}}^{\mathrm{NL}}$ are independent.
Without loss of generality, here we assume that all components of
$\tilde{\mathbf{E}}^{\mathrm{NL}}$ are standardized, i.e., they have a zero
mean and unit variance. Denote by $\mathbf{A}^{\mathrm{NL}}_{i\cdot}$ the
$i$th row of $\mathbf{A}^{\mathrm{NL}}$. We have
$\mathbb{E}[\tilde{X}^{*}_{j}\tilde{X}^{*}_{i}]=\mathbf{A}^{\mathrm{NL}}_{j\cdot}\mathbf{A}^{NL\intercal}_{i\cdot}$
and
$\mathbb{E}[{\tilde{X}^{*2}_{i}}]=\mathbf{A}^{\mathrm{NL}}_{i\cdot}\mathbf{A}^{NL\intercal}_{i\cdot}=||\mathbf{A}^{\mathrm{NL}}_{i\cdot}||^{2}$.
The regression model for $\tilde{X}^{*}_{j}$ on $\tilde{X}^{*}_{i}$ is

$\displaystyle\tilde{X}^{*}_{j}=\frac{\mathbb{E}[\tilde{X}^{*}_{j}\tilde{X}^{*}_{i}]}{\mathbb{E}[\tilde{X}^{*2}_{i}]}\tilde{X}^{*}_{i}+R_{j\leftarrow
i}=\frac{\mathbf{A}^{\mathrm{NL}}_{j\cdot}\mathbf{A}^{NL\intercal}_{i\cdot}}{||\mathbf{A}^{\mathrm{NL}}_{i\cdot}||^{2}}\tilde{X}^{*}_{i}+R_{j\leftarrow
i}.$

Here the residual can be written as

$\displaystyle R_{j\leftarrow i}$
$\displaystyle=\tilde{X}^{*}_{j}-\frac{\mathbf{A}^{\mathrm{NL}}_{j\cdot}\mathbf{A}^{NL\intercal}_{i\cdot}}{||\mathbf{A}^{\mathrm{NL}}_{i\cdot}||^{2}}\tilde{X}^{*}_{i}$
$\displaystyle=\underbrace{\big{(}\mathbf{A}^{\mathrm{NL}}_{j\cdot}-\frac{\mathbf{A}^{\mathrm{NL}}_{j\cdot}\mathbf{A}^{NL\intercal}_{i\cdot}\mathbf{A}^{\mathrm{NL}}_{i\cdot}}{||\mathbf{A}^{\mathrm{NL}}_{i\cdot}||^{2}}\big{)}}_{\triangleq\alpha_{j\leftarrow
i}}\tilde{\mathbf{E}}^{\mathrm{NL}}.$ (14)

If for all $j$, $R_{j\leftarrow i}$ is either zero or independent from
$\tilde{X}^{*}_{i}$, we consider $\tilde{X}^{*}_{i}$ as the current root cause
and put it and all the other variables which are deterministically related to
it in the first group, which is a root cause group. Now the problem is whether
we can check for independence between nonzero residuals $R_{j\leftarrow i}$
and the predictor $\tilde{X}^{*}_{i}$. Interestingly, the answer is yes, as
stated in the following proposition.

######  Proposition 9.

Suppose assumption A4 holds. For variables $\tilde{\mathbf{X}}^{*}$ generated
by (5), regression residual $R_{j\leftarrow i}$ given in (14) is independent
from variable $\tilde{{X}}_{i}^{*}$ if and only if

$|\alpha_{j\leftarrow i}\circ\mathbf{A}^{\mathrm{NL}}_{i\cdot}|_{1}=0,$ (15)

where $\circ$ denotes entrywise product.

So we can check for independence as if the values of $\tilde{\mathbf{X}}^{*}$
were given. Consequently, we can find the root cause group.

We then consider the residuals of regressing all the remaining variables
$\tilde{X}^{*}_{k}$ on the discovered root cause as a new set of variables.
Note that like the variables $\tilde{X}_{j}^{*}$, these variables are also
linear mixtures of $\tilde{{E}}_{i}$. Repeating the above procedure on this
new set of variance will give the second root cause and its recursive group.
Applying this procedure repeatedly until no variable is left finally discovers
all recursive groups following the causal ordering. The constructed recurse
group decomposition is asymptotically correct, as stated in the following
proposition.

######  Proposition 10.

(Identifiable recursive group decomposition) Let ${X}_{i}$ be generated by the
CAMME with the corresponding measurement-error-free variables generated by the
causal DAG $\tilde{G}$ and suppose assumptions A0 and A4 hold. The recursive
group decomposition constructed by the above procedure is asymptotically
correct, in the sense that as the sample size $N\rightarrow\infty$, if non-
leaf node $\tilde{X}_{i}$ is a cause of non-leaf node $\tilde{X}_{j}$, then
the recursive group which $\tilde{X}_{i}$ is in precedes the group which
$\tilde{X}_{j}$ belongs to. However, the causal ordering among the nodes
within the same recursive group may not be identifiable.

The result of Proposition 10 applies to any DAG structure in $\tilde{G}$.
Clearly, the indentifiability can be naturally improved if additional
assumptions on the causal structure $\tilde{G}$ hold. In particular, to
recover information of $\tilde{G}$, it is essential to answer the following
questions.

  * •

Can we determine which nodes in a recursive group are leaf nodes?

  * •

Can we find the causal edges into a particular node as well as their causal
coefficients?

Below we will show that under rather mild assumptions, the answers to both
questions are yes.

####  5.2.2 Identifying Leaf Nodes and Individual Causal Edges

If for each recursive group we can determine which variable is the non-leaf
node, the causal ordering among the variables $\tilde{X}^{*}_{i}$ is then
fully known. The causal structure in $\tilde{G}^{*}$ as well as the causal
model can then be readily estimated by regression: for a leaf node, its direct
causes are those non-leaf nodes that determine it; for a non-leaf node, we can
regress it on all non-leaf nodes that precede it according to the causal
ordering, and those predictors with non-zero linear coefficients are its
parents. (Equivalently, its parents are the nodes that causal precede it and
in its Markov blanket.)

Now the problem is whether it is possible to find out which variable in a
given recursive group is a leaf node; if all leaf nodes are found, then the
remaining one is the (only) non-leaf node. We may find leaf nodes by “looking
backward" and “looking forward"; the former makes use of the parents of the
variables in the considered group, and the latter exploits the fact that leaf
nodes do not have any child.

######  Proposition 11.

(Leaf node determination by “looking backward") Suppose the observed data were
generated by the CAMME where assumptions A0 and A4 hold.333In this non-
Gaussian case (implied by assumption A4), the result reported in this
proposition may still hold if one avoids the non-deterministic faithfulness
assumption and assumes a weaker condition; however, for simplicity of the
proof we currently still assume non-deterministic faithfulness. Let the sample
size $N\rightarrow\infty$. Then if assumption A5 holds, leaf node $O$ is
correctly identified from values of $\mathbf{X}$ (more specifically, from the
estimated $\mathbf{A}^{\mathrm{NL}}$ or the distribution of
$\tilde{\mathbf{X}}^{*}$); alternatively, if assumption A6 holds, leaf nodes
$O$ and $Q$ are correctly identified from values of $\mathbf{X}$.

  * A5.

According to $\tilde{G}^{*}$, leaf node $O$ in the considered recursive group,
$g^{(k)}$, has a parent which is not a parent of the non-leaf node in
$g^{(k)}$.

  * A6.

According to $\tilde{G}^{*}$, leaf nodes $O$ and $Q$ in the considered
recursive group, $g^{(k)}$, are non-deterministically conditionally
independent given some subset of the nodes in $g^{(1)},g^{(2)},...,g^{(k)}$.

##### Example Set 4

Suppose assumptions A0 and A4 hold.

  * •

For $\tilde{G}_{A}$ in Figure 6(a), assumption A6 holds for
$\tilde{X}^{*}_{7}$ and $\tilde{X}^{*}_{8}$ in the recursive group
$\\{\tilde{X}^{*}_{4},\tilde{X}^{*}_{7},\tilde{X}^{*}_{8}\\}$: they are non-
deterministically conditionally independent given
$\\{\tilde{X}_{2}^{*},\tilde{X}_{4}^{*}\\}$; so both of them are identified to
be leaf nodes from the estimated $\mathbf{A}^{\mathrm{NL}}$ or the
distribution of $\tilde{\mathbf{X}}^{*}$, and $\tilde{X}^{*}_{4}$ can be
determined as a non-leaf node. (In addition, assumption A5 holds for
$\tilde{X}_{8}^{*}$, allowing us to identify this leaf node even if
$\tilde{X}^{*}_{7}$ is absent in the graph.)

  * •

For both $\tilde{G}_{C}$ and $\tilde{G}_{D}$ in Figure 6(c),
$\tilde{X}_{6}^{*}$, in the recursive group
$\\{\tilde{X}_{5}^{*},\tilde{X}_{6}^{*}\\}$, follows assumption A5 and can be
found to be a leaf node from the distribution of $\tilde{X}^{*}_{i}$;
accordingly, $\tilde{X}_{5}^{*}$ has to be a non-leaf node.

  * •

For $\tilde{G}_{E}$ in Figure 6(d), assumption A5 holds for
$\tilde{X}_{5}^{*}$ and $\tilde{X}_{8}^{*}$, which can then be found to be
leaf nodes.

We can also determine leaf nodes by looking at the relationships between the
considered variables and the variables causally following them, as stated in
the following proposition.

######  Proposition 12.

(Leaf node determination by “looking forward") Suppose the observed data were
generated by the CAMME where assumptions A0 and A4 hold. Then as the sample
size $N\rightarrow\infty$, we can correctly identify the leaf node $U$ in the
considered recursive group $g^{(k)}$ from values of $\mathbf{X}$ if assumption
A7 holds for it:

  * A7.

For leaf node $U$ in $g^{(k)}$, there exists at least one node causally
following $g^{(k)}$ that 1) is d-separated from $U$ by a subset of variables
in $g^{(1)},...,g^{(k-1)},g^{(k)}$ which does not include all parents of $U$
and 2) is a child of the non-leaf node in $g^{(k)}$ .

##### Example Set 5

Suppose assumptions A0 and A4 hold.

  * •

For data generated by $\tilde{G}_{A}$ in Figure 6(a), we already found
$\tilde{X}_{4}^{*}$ in recursive group
$\\{\tilde{X}^{*}_{4},\tilde{X}^{*}_{7},\tilde{X}^{*}_{8}\\}$ to be a non-leaf
node because of Proposition 11. Proposition 12 further indicates that
$\tilde{X}^{*}_{2}$ (in group $\\{\tilde{X}^{*}_{2},\tilde{X}^{*}_{5}\\}$) and
$\tilde{X}^{*}_{3}$ (in group $\\{\tilde{X}^{*}_{3},\tilde{X}^{*}_{6}\\}$) are
non-leaf nodes, and all leaf nodes are identified.

  * •

For $\tilde{G}_{B}$ in Figure 6(b), there is only one recursive group, and it
does not provide further information by looking “backward" or “forward", and
it is impossible to find the non-leaf node with Proposition 11 or 12.

  * •

For both $\tilde{G}_{C}$ and $\tilde{G}_{D}$ in Figure 6(c),
$\tilde{X}^{*}_{6}$ was found to be a leaf node due to Proposition 11; thanks
to Proposition 12, the other leaf node, $\tilde{X}^{*}_{3}$, was also
detected. In particular, in $\tilde{G}_{C}$, for leaf node $\tilde{X}^{*}_{3}$
both $\tilde{X}^{*}_{4}$ and $\tilde{X}^{*}_{6}$ satisfy the two conditions in
assumption 12; however, in $\tilde{G}_{D}$, for leaf node $\tilde{X}^{*}_{3}$
only $\tilde{X}^{*}_{4}$ satisfies them. All leaf nodes were successfully
found.

  * •

For $\tilde{G}_{E}$ in Figure 6(d), Proposition 11 already allows us to
identify leaf nodes $\tilde{X}_{5}^{*}$ and $\tilde{X}_{8}^{*}$. Because
assumption A7 holds for $\tilde{X}^{*}_{4}$ (for it $\tilde{X}_{7}^{*}$
satisfies the two conditions), we can further identify this leaf node.

For contaminated data generated by any of $\tilde{G}_{A}$, $\tilde{G}_{C}$,
$\tilde{G}_{D}$, and $\tilde{G}_{E}$, now we can find all leaf nodes in the
measurement-error-free causal model. One can then immediately estimate the
whole measurement-error-free model, as seen next.

The above two propositions are about the identifiably of leaf nodes in the
measurement-error-free causal model. By applying them to all leaf nodes, we
have the (sufficient) conditions under which the causal graph of $\tilde{G}$
is fully identifiable.

######  Proposition 13.

(Full identifiability) Suppose the observed data were generated by the CAMME
where assumptions A0 and A4 hold. Assume that for each leaf node in
$\tilde{G}^{*}$, at least one of the three assumptions, A5, A6, and A7, holds.
Then as the sample size $N\rightarrow\infty$, the causal structure in
$\tilde{G}$ is fully identifiable from the contaminated observations.

In the general case, the causal structure in $\tilde{G}$ might not be fully
identifiable, and the above propositions may allow partial identifiability of
the underlying causal structure. Roughly speaking, the recursive group
decomposition is identifiable in the non-Gaussian case; with Propositions 11
and 12 one can further identify some leaf nodes as well as their parents.

##  6 Conclusion and Discussions

For variables of interest in various fields, including social sciences,
neuroscience, and biology, the measured values are often contaminated by
additional measurement error. Unfortunately, the outcome of existing causal
discovery methods is sensitive to the existence of measurement error, and it
is desirable to develop causal discovery methods that can estimate the causal
model for the measurement-error-free variables without using much prior
knowledge about the measurement error. To this end, this paper is concerned
with the identifiability conditions for the underlying measurement-error-free
causal model given contaminated observations. We have shown that under various
conditions, the causal model is partially or even fully identifiable.

Table 1 summarizes the identifiability results presented in this paper.
Propositions 4 and 5 make use of second-order statistics of the data, and
Propositions 7 to 13 further exploit non-Gaussianity of the data. The
identifiability conditions reported in this paper are sufficient and might not
be necessary. Below are some high-level interpretations of the conditions.

  * •

Roughly speaking, in the Gaussian case (Propositions 4 and 5) the
identifiability conditions are mainly about the number of leaf nodes in the
measurement-error-free causal model and the sparsity of the underlying causal
structure. The measurement-error-free causal model may be identifiable up to
its equivalence class.

  * •

In the non-Gaussian case, the conditions for full identifiability are mainly
about the sparsity of the measurement-error-free causal structure.

  * •

In the non-Gaussian case, the identifiability conditions of the recursive
group decomposition (including causal ordering between groups) are rather
general (Proposition 7).

  * •

The identifiability of the measurement-error-free causal model may greatly
benefit from additional knowledge about the measurement error (e.g, that all
measurement errors have the same variance, as discussed in Propositions 4 and
7).

  * •

Suppose assumptions A0 and A4 hold (the non-Gaussian case is considered);
without additional knowledge about the measurement error, we conjecture that
the necessary and sufficient condition for the non-leaf node to be
identifiable is that at least one of the three assumptions, A5, A6, and A7,
holds. To falsify or prove this conjecture is part of our future work.

Table 1: Summary of the identifiability results. Proposition $\\#$ |  Assumptions |  What information of $\tilde{G}$ is identifiable?
---|---|---
Proposition 4 |  A0, A1, and A2 |  up to the equivalence class; leaf nodes identifiable
Proposition 5 |  A0, A1, and A3 |  up to the equivalence class
Proposition 7 |  A0, A4, A1, and A2 |  Fully identifiable
Proposition 10 |  A0 and A4 |  Recursive group decomposition (including causal ordering between the groups)
Proposition 11 |  A0, A4, and A5 or A6 for some leaf nodes in $\tilde{G}^{*}$ |  Recursive group decomposition; the leaf nodes
Proposition 12 |  A0, A4, and A7 for some leaf nodes in $\tilde{G}^{*}$ |  Recursive group decomposition; the leaf nodes
Proposition 13 |  A0, A4, and A5 or A6 or A7 for each leaf node |  Fully identifiable

We note that in principle, all assumptions except A0 (regarding the causal
Markov condition and non-deterministic faithfulness assumption related to
causal model $\tilde{G}^{*}$) are testable from the observed data. This
suggests that it is possible to develop practical causal discovery methods to
deal with measurement error that are able to produce reliable information at
least in the asymptotic case.

We have verified the validity of the algorithms briefly given in the paper on
large samples, including FA+EquVar and FA+DPC outlined in Sections 4.1 and
4.2, respectively, and the procedure to find recursive group decomposition
given in Section 5.2. All of them are two-step methods: in the first step, the
first two methods apply factor analysis on the data, and the last procedure
applies over-complete independent component analysis; in the second step all
the methods do causal discovery with subsequent analysis on the estimated
information of the canonical representation of the CAMMA. These methods might
not be statistically efficient for the purpose of causal discovery because of
estimation errors in the first step. We are currently studying their behavior
on finite samples and aim at developing statistically more efficient
algorithms. Such methods are also expected to be able to learn the optimal
number of leaf nodes in the causal graph (in this paper we assume this number
is given).

It is worth noting that various kinds of background knowledge of the causal
model may further help improve the identifiability of the measurement-error-
free causal model. For instance, if one knows that all causal coefficients are
smaller than one in absolute value, then the measurement-error-free causal
model in Figure 6(b) is immediately identifiable from contaminated data. Our
future research also includes establishing identifiability conditions that
allow cycles in the measurement-error-free causal model and developing
efficient methods for particular cases where each measurement-error-free
variable has multiple measured effects or multiplied measurement-error-free
variables generate a single measured effect.

## References

  * Bekker & ten Berge (1997) Bekker, P. A. and ten Berge, J. M. F.  Generic global indentification in factor analysis.  _Linear Algebra and its Applications_ , 264:255–263, 1997\.
  * Chickering (2002) Chickering, D. M.  Optimal structure identification with greedy search.  _Journal of machine learning research_ , 3(Nov):507–554, 2002.
  * Eriksson & Koivunen (2004) Eriksson, J. and Koivunen, V.  Identifiability, separability, and uniqueness of linear ICA models.  _IEEE Signal Processing Letters_ , 11(7):601–604, 2004.
  * Everitt (1984) Everitt, B. S.  _An introduction to latent variable models_.  London: Chapman and Hall, 1984.
  * Glymour (2007) Glymour, C.  Learning the structure of deterministic systems.  In Gopnik, A. and Schulz, L. (eds.), _Causal learning: psychology, philosophy and computation_. Oxford University Press, 2007.
  * Kagan et al. (1973) Kagan, A. M., Linnik, Y. V., and Rao, C. R.  _Characterization Problems in Mathematical Statistics_.  Wiley, New York, 1973.
  * (7) Kummerfeld, E., Ramsey, J., Yang, R., Spirtes, P., and Scheines, R.  Causal clustering for 2-factor measurement models.  In Calders, T., Esposito, F., Hüllermeier, R., and Meo, R. (eds.), _Proc. ECML PKDD_.
  * Luo (2006) Luo, W.  Learning bayesian networks in semi-deterministic systems.  In _Proc. Canadian Conference on Artificial Intelligence_ , pp. 230–241, 2006.
  * Pearl (2000) Pearl, J.  _Causality: Models, Reasoning, and Inference_.  Cambridge University Press, Cambridge, 2000.
  * Scheines & Ramsey (2017) Scheines, R. and Ramsey, J.  Measurement error and causal discovery.  In _Proc. CEUR Workshop 2016_ , pp. 1–7, 2017.
  * Shapiro (1985) Shapiro, A.  Identifiability of factor analysis: Some results and open problems.  _Linear Algebra and its Applications_ , 70:1–7, 1985.
  * Shimizu et al. (2006) Shimizu, S., Hoyer, P.O., Hyvärinen, A., and Kerminen, A.J.  A linear non-Gaussian acyclic model for causal discovery.  _Journal of Machine Learning Research_ , 7:2003–2030, 2006\.
  * Shimizu et al. (2011) Shimizu, S., Inazumi, T., Sogawa, Y., Hyvärinen, A., Kawahara, Y., Washio, T., Hoyer, P. O., and Bollen, K.  Directlingam: Adirect method for learning a linear non-gaussian structural equation model.  _Journal of Machine Learning Research_ , pp. 1225–1248, 2011.
  * Silva et al. (2006) Silva, R., Scheines, R., Glymour, C., and Spirtes, P.  Learning the structure of linear latent variable models.  _Journal of Machine Learning Research_ , 7:191–246, 2006\.
  * Spirtes et al. (2001) Spirtes, P., Glymour, C., and Scheines, R.  _Causation, Prediction, and Search_.  MIT Press, Cambridge, MA, 2nd edition, 2001.

## Appendix: Proofs

### A.1: Proof of Proposition 4

###### Proof.

According to Proposition 3, the variances of $E_{i}^{*}$ are identifiable. If
they are not identical, then their smallest value is the variance of
measurement errors $E_{i}$. If the estimated variance of $E^{*}_{j}$ is
greater than the smallest value, according to the definition of $E^{*}_{i}$ in
(11), $\tilde{X}_{j}$ must be a leaf node in $\tilde{G}$. There are in total
three types of edges in $\tilde{G}$.

  1. 1.

First consider the edges between leaf nodes. According to the definition of
leaf nodes, there is no edge between them. Since we know which nodes are leaf
nodes, it is guaranteed that there is no edge between them.

  2. 2.

Then consider the edges between non-leaf nodes. Remove all the leaf nodes, and
we have the set of non-leaf nodes, which is causally sufficient. The subgraph
of $\tilde{G}$ over this set of variables satisfies the causal Markov
condition and the faithfulness assumption. Then by applying any consistent
constraint-based causal discovery method, such as the PC algorithm, this
subgraph is corrected identified up to its equivalence class as
$N\rightarrow\infty$. That is, the edges between non-leaf nodes are correctly
identified.

  3. 3.

Finally consider the edges between leaf nodes and non-leaf nodes. Each leaf
node $\tilde{X}_{i}^{*}$ is a deterministic, linear function of its direct
causes, which are among non-leaf nodes. Denote by the set of the direct causes
of $\tilde{X}_{i}^{*}$ by $S_{i}$. Recall that the covariance matrix of non-
leaf nodes is non-singular. As a consequence, $\tilde{X}_{i}^{*}$, as a linear
combination of elements of $S_{i}$, cannot be represented as a deterministic,
linear combination of other non-leaf nodes; otherwise some leaf node can be
written as a deterministic, linear function of other non-leaf nodes, leading
to a contradiction. As a result, $S_{i}$ is identifiable and, as a
consequence, the edges between each leaf node and non-leaf nodes are
identifiable.

Therefore, $\tilde{G}$ is identifiable at least up to its equivalence class.
Furthermore, we know that for all edges between leaf nodes and non-leaf nodes,
the direction points to the leaf nodes. ∎

### A.2: Proof of Proposition 5

###### Proof.

The deterministic relations among $\tilde{X}_{i}^{*}$ and their conditional
independence/dependence relations can be seen from the covariance matrix of
$\tilde{X}_{i}^{*}$. First, notice that the conditional independence relations
detected by DPC are correct but may not be complete. Hence, asymptotically
speaking, the edges removed by DPC do not exist in the true graph, i.e., DPC
does not produce any missing edge.

We then note that there is no deterministic relation among non-leaf nodes and
that two non-leaf nodes in $\tilde{G}$ which are not adjacent are d-separated
by a proper subset of other non-leaf nodes; as a consequence, DPC will
successfully detect the conditional independence relationships as well as the
edges between non-leaf nodes. Therefore, the edges between all non-leaf nodes
are identifiable.

Next, we shall consider whether DPC is able to correctly identify the edges
between leaf nodes (which are actually not adjacent in $\tilde{G}$) and those
between leaf nodes and non-leaf nodes. First consider the relationships
between leaf nodes. According to the former part of assumption A3, all paths
between leaf nodes $\tilde{X}_{j}$ and $\tilde{X}_{k}$ that go through at most
one of $\tilde{X}_{p}$ and $\tilde{X}_{q}$ are blocked by
$(\mathrm{PA}(\tilde{X}_{j})\setminus\tilde{X}_{p})\cup(\mathrm{PA}(\tilde{X}_{k})\setminus\tilde{X}_{q})$;
the paths that go through both of $\tilde{X}_{p}$ and $\tilde{X}_{q}$ are
blocked by $\mathbf{S}_{1}$. Therefore, all paths between $\tilde{X}_{j}$ and
$\tilde{X}_{k}$ are blocked by
$(\mathrm{PA}(\tilde{X}_{j})\setminus\tilde{X}_{p})\cup(\mathrm{PA}(\tilde{X}_{k})\setminus\tilde{X}_{q})\cup\mathbf{S}_{1}$,
which does not deterministically determine $\tilde{X}_{j}$ or $\tilde{X}_{k}$,
so such an conditional independence relationship is detected by DPC. Hence
each pair of leaf nodes in $\tilde{G}$, $\tilde{X}_{j}$ and $\tilde{X}_{k}$,
are not adjacent in the output of DPC.

Finally, we consider the d-separation relationships between each leaf node
$\tilde{X}_{j}$ and its non-adjacent non-leaf node $\tilde{X}_{i}$. According
to the latter part of assumption A3, all paths between $\tilde{X}_{j}$ and
$\tilde{X}_{i}$ that do not go through $\tilde{X}_{r}$ are blocked by
$\mathrm{PA}(\tilde{X}_{j})\setminus\tilde{X}_{r}$, and the paths between them
that go through $\tilde{X}_{r}$ are blocked by $\mathbf{S}_{2}$. Therefore,
all paths between $\tilde{X}_{j}$ and $\tilde{X}_{i}$ are blocked by
$(\mathrm{PA}(\tilde{X}_{j})\setminus\tilde{X}_{r})\cup\mathbf{S}_{2}$. That
is, the outcome of DPC does not contain any extra edge between leaf nodes and
non-leaf nodes.

Hence, the skeleton given by DPC is the same as the skeleton of $\tilde{G}$
under assumptions A0, A1, and A3. Furthermore, according to Lemma 4 in (Luo,
2006), DPC correctly identifies all colliders in $\tilde{G}$. Therefore, under
such assumptions $\tilde{G}$ is recovered up to its equivalence class. ∎

### A.3: Proof of Proposition 7

###### Proof.

Denoted by $\hat{\mathbf{A}}^{\mathrm{NL}}$ the estimate of
$\mathbf{A}^{\mathrm{NL}}$. First note that according to Corollary 4, leaf
nodes in $\tilde{G}$ are identifiable. Then for each leaf node
$\tilde{X}_{l}$, find the combination of the non-leaf nodes which determines
$\tilde{X}_{l}$ in terms of $\hat{\mathbf{A}}^{\mathrm{NL}}$, which is
achieved by finding the combination of the rows of
$\hat{\mathbf{A}}^{\mathrm{NL}}$ corresponding to non-leaf nodes to determine
the $l$-th row of $\hat{\mathbf{A}}^{\mathrm{NL}}$. All nodes involved in this
combination are direct causes of $\tilde{X}_{l}$. The solution in this step is
unique because the rows of $\hat{\mathbf{A}}^{\mathrm{NL}}$ corresponding to
non-leaf nodes are linearly independent, as implied by the non-deterministic
relations among $\tilde{X}_{i}$ (or non-zero variances of $\tilde{E}_{i}$).

We have found all edges between leaf nodes and non-leaf nodes, and the
remaining edges are those between non-leaf nodes. If we remove all leaf nodes
and edges into them from $\tilde{G}$, we have the causal graph over non-leaf
nodes and the graph is still acyclic, and the set of non-leaf nodes is
causally sufficient. Denote by $\hat{\mathbf{A}}^{\mathrm{NL}}_{s}$ the matrix
consisting of the rows of $\hat{\mathbf{A}}^{\mathrm{NL}}$ corresponding to
non-leaf nodes. According to the identifiability of LiNGAM (Shimizu et al.,
2006), the causal relations among non-leaf nodes are uniquely determined by
$\hat{\mathbf{A}}^{\mathrm{NL}}_{s}$ or its inverse. ∎

### A.4: Proof of Proposition 9

###### Proof.

Both $R_{j\leftarrow i}$ and $\tilde{{X}}_{i}^{*}$ are linear mixtures of
independent, non-Gaussian variables $\tilde{E}_{i}$. According to the Darmois-
Skitovich theorem (Kagan et al., 1973), $R_{j\leftarrow i}$ and
$\tilde{X}^{*}_{i}$ are statistically independent if and only if the for any
$k$, at most one of the $k$th entries of their coefficient vectors,
$\alpha_{j\leftarrow i}$ and $\mathbf{A}^{\mathrm{NL}}_{i\cdot}$, is non-zero,
which is equivalent to the condition (15). ∎

### A.5: Proof of Proposition 10

###### Proof.

In the constructed recursive group decomposition, each group has one and only
one non-leaf node. Just consider the non-leaf nodes in the recursive
decomposition. Combining Lemma 1 in (Shimizu et al., 2011) and Proposition 9,
one can see that the discovered causal ordering among them must be correct. ∎

### A.6: Proof of Proposition 11

###### Proof.

In each recursive group, there is a single non-leaf node, and all the others
are leaf-nodes. Denote by $\tilde{X}^{*(k)}_{q}$ the $q$th node in the
recursive group $g^{(k)}$. Denoted by $\tilde{X}^{*(k)}_{\mathrm{NL}}$ the
only non-leaf node in the recursive group $g^{(k)}$. Denote by
$\mathrm{PA}(\tilde{X}^{*(k)}_{\mathrm{NL}})$ the set of direct causes of
$\tilde{X}^{*(k)}_{\mathrm{NL}}$ in $\tilde{G}^{*}$.

First consider assumption A5. Let us regress each variable
$\tilde{X}^{*(k)}_{q}$ in this group on all variables $\tilde{X}^{*}_{i}$ in
the first $(k-1)$ recursive groups; in this regression task, all predictors
are causally earlier than $\tilde{X}^{*(k)}_{q}$ because of the identifiable
causal ordering among the recursive groups. Although the realizations of
variables $\tilde{X}^{*}_{i}$ are unknown, such regression models can be
estimated from the estimated matrix $\hat{\mathbf{A}}^{\mathrm{NL}}$, as done
in Section 5.2.1, or by analyzing the estimated covariance matrix of
$\tilde{\mathbf{X}}^{*}$, which is
$\hat{\mathbf{A}}^{\mathrm{NL}}\hat{\mathbf{A}}^{NL\intercal}$ (we have
assumed that $\mathbb{V}ar(\tilde{E}^{\mathrm{NL}}_{i})=1$ without loss of
generality). There are two possible cases to consider.

  * i)

For the non-leaf node $\tilde{X}^{*(k)}_{\mathrm{NL}}$ in the $k$th group, all
predictors with non-zero coefficients are its direct causes, and their set is
$\textrm{PA}(\tilde{X}^{*NL}_{(k)})$.

  * ii)

Then consider a leaf node in this group, $\tilde{X}^{*(k)}_{q^{\prime}}$,
$\tilde{X}^{*(k)}_{q^{\prime}}\neq\tilde{X}^{*(k)}_{\mathrm{NL}}$. Recall that
when regressing $\tilde{X}^{*(k)}_{q^{\prime}}$ on the variables in causally
earlier recursive groups, $\tilde{X}^{*(k)}_{\mathrm{NL}}$ is not among the
predictors because it is also in the $k$th group. First note that each node in
$\tilde{X}^{*(k)}_{\mathrm{NL}}$ is always d-connected to
$\tilde{X}^{*(k)}_{q^{\prime}}$ given any variable set that does not include
$\tilde{X}^{*(k)}_{\mathrm{NL}}$. As a consequence, in the regression model
for $\tilde{X}^{*(k)}_{q^{\prime}}$, all predictors in
$\mathrm{PA}(\tilde{X}^{*(k)}_{\mathrm{NL}})$ have non-zero coefficients, so
all predictors with non-zero coefficients form a superset of
$\mathrm{PA}(\tilde{X}^{*(k)}_{\mathrm{NL}})$. Furthermore, under assumption
A5, $O$ has at least a direct cause that is not in
$\textrm{PA}(\tilde{X}^{*(k)}_{\mathrm{NL}})$. Therefore, in the regression
model for $O$, the set of predictors with non-zero coefficients is a proper
superset of $\textrm{PA}(\tilde{X}^{*NL}_{(k)})$ (the former has more
elements).

That is, when regressing variables $\tilde{X}^{*(k)}_{q}$ in the considered
group on variables in earlier groups, the non-leaf node, as well as possibly
some of the leaf nodes, always has a smaller number of predictors with non-
zero coefficients, compared to the model for leaf node $O$. Hence we can
determine $O$ as a leaf node.

Then consider assumption A6. According to assumption A0, A6 implies that $O$
and $Q$ are d-separated by a proper subset of the variables. Consequently,
they are not adjacent in $\tilde{G}^{*}$. Bear in mind that the non-leaf node
in $g^{(k)}$ is adjacent to all leaf nodes in the same group in
$\tilde{G}^{*}$. Therefore both $O$ and $Q$ are leaf nodes. ∎

### A.7: Proof of Proposition 12

###### Proof.

We note that the recursive group decomposition can be correctly identified
from the values of $\mathbf{X}$ as $N\rightarrow\infty$, as implied by
Proposition 10. Denote by $W$ the non-leaf node in $g^{(k)}$. Let us first
find a subset of the nodes causally following $g^{(k)}$ in which each node,
denoted by $S$, is always non-deterministically dependent on at least one of
the nodes in $g^{(k)}$ relative to $g^{(1)}\cup g^{(2)}\cup...\cup
g^{(k)}\cup{S}$. Denoted by $\mathbf{S}$ this set of nodes. If assumption A7
holds, $\mathbf{S}$ is non-empty.

We then see that the non-leaf node $W$ is always non-deterministically
dependent on every node in $\mathbf{S}$. Suppose this is not the case, i.e.,
there is $S\in\mathbf{S}$ which is non-deterministically independent from $W$
given a subset of $g^{(1)}\cup g^{(2)}\cup...\cup g^{(k)}$. Denote by
$\mathbf{R}_{1}$ this subset. If $\mathbf{R}_{1}$ contains any leaf nodes in
$\tilde{G}^{*}$, let us remove those leaf nodes from $\mathbf{R}_{1}$ and
denote by $\mathbf{R}^{\prime}_{1}$ the resulting variable set. Further note
that $S$ and $W$ are still de-separated by $\mathbf{R}^{\prime}_{1}$. Then
$U^{\prime}$, a leaf node in $g^{(k)}$, is always d-separated from $S$ given
$\mathbf{R}_{1}^{\prime}\cup(\mathrm{PA}(U^{\prime})\setminus W)$. Since all
nodes in $\mathbf{R}_{1}^{\prime}\cup(\mathrm{PA}(U^{\prime})\setminus W)$ are
non-leaf nodes, $W$ can not be represented as their linear combination; thus
$U^{\prime}$ is not their deterministic function. Furthermore, $S$ is not a
deterministic function of nodes in
$\mathbf{R}_{1}^{\prime}\cup(\mathrm{PA}(U^{\prime})\setminus W)$ either;
otherwise, according to the construction procedure of the recursive group
decomposition, $S$ will belong to $g^{(1)}\cup g^{(2)}\cup...\cup g^{(k)}$
because all elements of
$\mathbf{R}_{1}^{\prime}\cup(\mathrm{PA}(U^{\prime})\setminus W)$ belong to
it. Hence any leaf node $U^{\prime}$ in $g^{(k)}$ will be non-
deterministically independent from $S$ relative to $g^{(1)}\cup
g^{(2)}\cup...\cup g^{(k)}\cup{S}$, so $S$ is non-deterministically
independent from every node in $g^{(k)}$ given a subset of $g^{(1)}\cup
g^{(2)}\cup...\cup g^{(k)}$. That is, $S\notin\mathbf{S}$, leading to a
contradiction.

Next, we show that for leaf node $U$ in $g^{(k)}$, there exists at least one
element of $\mathbf{S}$ which is non-deterministically conditionally
independent from $U$ given a subset of $g^{(1)}\cup g^{(2)}\cup...\cup
g^{(k)}$. Denote by $V$ one of the nodes that causally follow $g^{(k)}$ and
satisfy the two conditions in assumption A7. Because of condition 2),
$V\in\mathbf{S}$. Condition 1) states that $V$ and leaf node $U$ are
d-separated by a subset of variables in $g^{(1)},...,g^{(k-1)},g^{(k)}$ that
does not include all parents of $U$. Denote by $\mathbf{R}_{2}$ this variable
set. If $\mathbf{R}_{2}$ contains any leaf nodes in $\tilde{G}^{*}$, remove
them from $\mathbf{R}_{2}$ and denote by $\mathbf{R}_{2}^{\prime}$ the
resulting variable set. $V$ and $U$ are still de-separated by
$\mathbf{R}_{2}^{\prime}$, but all elements of $\mathbf{R}_{2}^{\prime}$ are
non-leaf nodes. Because all non-leaf nodes in $\tilde{G}^{*}$ are linearly
independent, the parents of $U$ that are not in $\mathbf{R}_{2}^{\prime}$ can
not be written as linear combinations of the elements of
$\mathbf{R}_{2}^{\prime}$. Therefore, $U$ is not a deterministic function of
$\mathbf{R}_{2}^{\prime}$. Moreover, $V$ is not a deterministic function of
$\mathbf{R}_{2}^{\prime}$ either, because otherwise $V$ will not in groups
causally following $g^{(k)}$. This means that leaf node $U$ is non-
deterministically independent from $V$, as an element of $\mathbf{S}$, given
$\mathbf{R}_{2}^{\prime}$.

That is, we can distinguish between leaf node $U$ and the non-leaf node in the
same recursive group by checking non-deterministic conditional independence
relationships in $\tilde{X}_{i}^{*}$.

∎

### A.8: Proof of Proposition 13

###### Proof.

First note that under the assumptions in the proposition, the recursive group
decomposition is identifiable, and all leaf nodes are asymptotically
identifiable. The causal ordering among the variables $\tilde{X}^{*}_{i}$ is
then fully known. The causal graph $\tilde{G}$ as well as the causal model can
then be readily estimated by regression: for a leaf node, its direct causes
are those non-leaf nodes that determine it; for a non-leaf node, we can
regress it on all non-leaf nodes that causally precede it according to the
causal ordering, and those predictors with non-zero linear coefficients are
its parents. ∎