Causal Discovery with Linear Non-Gaussian Models under
Measurement Error: Structural Identifiability Results

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
Causal discovery methods aim to recover thecausal process that generated purely observational data. Despite its successes on a numberof real problems, the presence of measurement
error in the observed data can produce serious mistakes in the output of various causal
discovery methods. Given the ubiquity ofmeasurement error caused by instruments or
proxies used in the measuring process, thisproblem is one of the main obstacles to reliable causal discovery. It is still unknown towhat extent the causal structure of relevant
variables can be identified in principle. This
study aims to take a step towards filling that
void. We assume that the underlining process or the measurement-error free variables
follows a linear, non-Guassian causal model,
and show that the so-called ordered groupdecomposition of the causal model, which contains major causal information, is identifiable.
The causal structure identifiability is further
improved with diﬀerent types of sparsity constraints on the causal structure. Finally, we
give rather mild conditions under which thewhole causal structure is fully identifiable.

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 andreceived 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), andscore-based ones, such as Greedy Equivalence Search(GES) (Chickering, 2002).
Almost all current causal discovery methods assume
that the recorded values are realizations of the variablesof interest. Typically, however, the measured values
are not identical to the values of the variables that they
are intended to measure. The measuring process may
involve nonlinear distortion, as already address by the
post-nonlinear causal model (Zhang & Hyvärinen, 2009;
Zhang & Chan, 2006), and may introduce a lot of error.
For instance, in neuroscience the measured brain signals obtained by functional magnetic resonance (fMRI)
usually contain error introduced by instruments. In
this paper, we consider the so-called random measurement error model, as defined by Scheines & Ramsey(2017), in which observed variables Xi , i = 1, ..., n, aregenerated from the underlying measurement-error-freevariables X̃i with additive measurement errors Ei :Xi = X̃i + Ei .

(1)

We further assume that the errors Ei are mutuallyindependent and independent from X̃i . Putting thecausal model for X̃i and the random measurement
error model together, we have the whole process thatgenerates the measured data. We call this process the
CAusal Model with Measurement Error (CAMME).
Generally speaking, because of the presence of measurement errors, the d-separation patterns among Xi
are diﬀerent from those among the underlying variables 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 Xi and the underlying variables X̃i may havediﬀerent conditional independence/dependence relations and, as a consequence, the output of approaches
to causal discovery that exploit conditional independence and dependence relations are unreliable in thepresence of such errors, as demonstrated in (Scheines& Ramsey, 2017). In Section 2 we will give an example
to show how conditional independence/dependence between the variables is changed by measurement error,
and discuss its implication in applications of causal discovery to real problems. Furthermore, because of themeasurement error, the structural equation models according to which the measurement-error-free variablesX̃i are generated usually do not hold for the observed
variables Xi . (In fact, Xi 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.
In this paper, we aim to estimate the causal model underlying the measurement-error-free variables X̃i fromtheir observed values Xi contaminated by random measurement error. We assume linearity of the causal
model and causal suﬃciency relative to {X̃i }ni=1 . We
particularly focus on the case where the causal structure for X̃i is represented by a Directed Acyclic Graph(DAG), although this condition can be weakened. Inorder to develop principled causal discovery methods
to recover the causal model for {X̃i }ni=1 from observed
values of {Xi }ni=1 , we have to address theoretical issues
include 1) whether the causal model of interest is completely or partially identifiable from the contaminatedobservations and 2) what are the precise identifiability
conditions.
There exist causal discovery methods, such as the Fast
Causal Inference (FCI) algorithm (Spirtes et al., 2001),
to deal with confounders, i.e., hidden direct common
causes. However, they cannot estimate the causal relations among the “latent" variables, which is what we
aim to recover in this paper. Silva et al. (2006) andKummerfeld et al. (2014) have provided algorithms forrecovering latent variables and their causal relations
when each latent variable has multiple measured eﬀects;
Shimizu et al. (2011a) further applied LiNGAM to therecovered latent variables to improve the estimatedcausal relations between them. 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 eﬀectof a single "true" variable. As discussed in Section 3,
their models can be seen as special cases of our setting.

2

EFFECT OF MEASUREMENT
ERROR

Suppose we observe variables X1 , X2 , and X3 , which
are generated from measurement-error-free variablesX̃i according to the structure given in Figure 1. By

the Markov condition and Faithfulness assumption, allthree of the X̃i variables are dependent on one another,while X̃1 and X̃3 are conditionally independent givenX̃2 . That conditional independence does not hold for
Xi , the variables actually observable. The measurement error E2 produces the trouble. We will treat the
distributions as Gaussian purely for illustration; again,
the point is general.
X̃1

X̃2

X̃3

X1

X2

X3

Figure 1: A linear CAMME to demonstrate the eﬀectof measurement error on conditional independence anddependence relationships. For simplicity, we consider
the special case where there is measurement error onlyin X2 , i.e., X2 = X̃2 + E2 , but X1 = X̃1 and X3 = X̃3 .
Let ⇢˜12 be the correlation coeﬃcient between X̃1 andX̃2 and ⇢˜13,2 be the partial correlation coeﬃcient between X̃1 and X̃3 given X̃2 , which is zero. Let ⇢12and ⇢13,2 be the corresponding correlation coeﬃcientand partial correlation coeﬃcient in the presence ofmeasurement error. We let ⇢˜12 = ⇢˜23 = ⇢˜ to make theargument simpler, but the point is quite general. So
Std(E2 )we have ⇢13 = ⇢˜13 = ⇢˜12 ⇢˜23 = ⇢˜2 . Let = Std(
. For
X̃2 )
the data with measurement error, we have
⇢12 =Cov(X1 , X2 )1/2
Var (X1 )Var1/2 (X2 )Cov(X̃1 , X̃2 )Var1/2 (X̃1 )(Var(X̃2 ) + Var(E2 ))1/2⇢˜=;(1 + 2 )1/2
⇢13 ⇢12 ⇢23⇢13,2 =
(1 ⇢212 )1/2 (1 ⇢223 )1/2
=

⇢˜13

=
1
=

1/2
⇢˜2
(1+ 2 )
2 2

r ⇢˜
1+

2

⇢˜2

⇢˜12 ⇢˜23
1+ 2

1

1/2
⇢˜2
(1+ 2 ).

As the variance of the measurement error in X2 increases, become larger, and ⇢12 decreases and finallygoes to zero; in contrast, ⇢13,2 , which is zero for themeasurement-error-free variables, is increasing and finally converges to ⇢˜2 . See Figure 2 for an illustration.
In other words, in this example as the variance of themeasurement error in X2 increases, X1 and X2 become more and more independent, while X1 and X3
are conditionally more and more dependent given X2 .
However, for the measurement-error-free variables, X̃1and X̃2 are dependent and X̃1 and X̃3 and conditionally independent given X̃2 . The PC algorithm andother methods that explicitly or implicitly exploit con-ditional independence and dependence relations willfind an edge between X1 and X3 that does not exist
between X1 and X3 . Multiple regression of X3 on
X1 and X2 , or X1 on X3 and X2 , will make the sameerror.

⇢ 12⇢˜

Data points

X1

2.5Linear regression line0

⇢ 12
⇢ 13, 2

−2.5
−5

0
X2

⇢˜ 2

(a)
Residual of regressing X1 on X2⇢˜ 2⇢ 13, 2
0

5

2

4
6
8
= S td(E 2)/S td( X̃ 2)

10

Figure 2: The correlation coeﬃcient ⇢12 between X1
and X2 and partial correlation coeﬃcient ⇢13,2 between
X1 and X3 given X2 as functions of , the ratio of thestandard deviation of measurement error to the that ofX̃2 . We have assumed that the correlation coeﬃcient
between X̃1 and X̃2 and that between X̃2 and X̃3 are
the same (denoted by ⇢˜), and that there is measurement
error only in X2 .
Roughly speaking, originally conditionally independent(or dependent) variables will become less independent(or dependent), due to the eﬀect of measurement error.
In order to correctly detect conditional independence relations between measurement-error-free variables fromthe observed noisy values, one may use a very small
significance level (or type I error level, ↵) when performing conditional independence tests–the smaller thesignificance level, the less often the independence null
hypothesis is rejected, and more pairs of variables arelikely to be considered as conditionally independent.
This, inevitably, risks high type II errors (i.e., conditionally dependent variable pairs are likely to beconsidered as independent), especially when the sample size is relatively small. Therefore it is desirable todevelop principled causal discovery methods to deal
with measurement error.
One might apply other types of methods instead of theconstraint-based ones for causal discovery from datawith measurement error. In fact, as the measurementerror-free variables are not observable, X̃2 in Figure 1
is actually a confounder for observed variables. As aconsequence, generally speaking, due to the eﬀect 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 forthe observed variables any more. Figure 3 gives an

2

0

−2
−4

−2

0
X2

2

4

(b)
Figure 3: Illustration on how measurement error leads
to dependence between regression residual and contaminated cause. (a) Scatter plot of X2 and X1 withmeasurement error in X2 together with the regression
line. (b) Scatter plot of the regression residual andX2 . Note that if we regress X̃1 on X̃2 , the residual isindependent from X̃2 .
illustration on this. Figure 3(a) shows the scatter plotof X1 vs. X2 and the regression line from X2 to X1 ,where X̃2 , the noise in X̃1 , and the measurement error
E2 , are all uniformly distributed (⇢ = 0.4, and = 1.4).
As seen from Figure 3(b), the residual of regressing
X1 on X2 is not independent from X2 , although theresidual of regressing X̃1 on X̃2 is independent fromX̃2 . As a result, the functional causal model-based
approaches to causal discovery may also fail to find thecausal structure of the measurement-error-free variablesfrom their contaminated observations. The eﬀect ofmeasurement error on causal direction identification in
the two-variable case was also studied by Wiedermann
et al. (2018) under some further assumptions.

3

MODEL CANONICALREPRESENTATIONLet G̃ be the acyclic causal model over X̃i . Here wecall it measurement-error-free causal model. Let B be
the corresponding causal adjacency matrix for X̃i , inwhich Bij is the coeﬃcient of the direct causal influencefrom X̃j to X̃i and Bii = 0. We have,(2)X̃ = BX̃ + Ẽ,

where the components of Ẽ, Ẽi , have non-zero, finite
variances. Then X̃ is actually a linear transformationof the error terms in Ẽ because (2) implies
X̃ = (I B) 1 Ẽ.
| {z }(3),A

Now let us consider two types of nodes of G̃, namely,leaf nodes (i.e., those that do not influence any othernode) and non-leaf nodes. Accordingly, the noise termin their structural equation models also has distinct
behaviors: If X̃i is a leaf node, then Ẽi influences onlyX̃i , not any other; otherwise Ẽi influences X̃i and at
least one other variable, X̃j , j 6= i. Consequently, we
can decompose the noise vector into two groups: ẼL
consists of the l noise terms that influence only leaf
nodes, and ẼNL contains the remaining noise terms.
Equation (3) can be rewritten asX̃ = ANL ẼNL + AL ẼL = X̃⇤ + AL ẼL ,(4)

where X̃ , A Ẽ , A
and A are n ⇥ (n l)and n ⇥ l matrices, respectively. Here both AL and
ANL have specific structures. All entries of AL are 0
or 1; for each column of AL , there is only one non-zero
entry. In contrast, each column of ANL has at least
two non-zero entries, representing the influences fromthe corresponding non-leaf noise term.
⇤

NL

NL

NL

L

We give a more formal way to derive the above resultand make it clear how ANL and AL depend on B. For
any graph G̃ there always exists a suitable permutation
matrix, denoted by ⌦, such that the last l elements ofthe permuted
 NL variables ⌦X̃ are all leaf nodes. Hence,Ẽ⌦Ẽ =. Accordingly, (2) implies thatẼL
(5)⌦X̃ = B⌦ · ⌦X̃ + ⌦Ẽ,

where B⌦ = ⌦B⌦| . Since the last l variables in ⌦X̃are leaf nodes, the last l columns of B⌦ are zero. Let
BNL⌦ be the causal influence matrix for the non-leaf
nodes and BL⌦ denote the causal influencefrom nonBNL
0⌦leaf nodes to leaf nodes. We have B⌦ =.
BL
0⌦Consequently,
(I BNL ) 1
0
1(I B⌦ ) =.
(6)
BL (I BN ) 1 I
Combining (5) and (6) gives

X̃ = ⌦| (I B⌦ ) 1 ⌦Ẽ


0
I
NL
|
1 NL
= ⌦| ·
·
(I
B
)
Ẽ
+
⌦
.
BL
ẼL
|
{z
}
|
{z
}
ANL

AL ẼL

Further consider the generating process of observed
variables Xi . Combining (1) and (4) gives
X = X̃⇤ + AL ẼL + E = ANL ẼNL + (AL ẼL + E)
= ANL ẼNL + E⇤
 NL
⇥
⇤
Ẽ
= ANL I ·
E⇤

(7)
,

(8)

where E⇤ = AL ẼL + E and I denotes the identity
matrix. To make it more explicit, we give how X̃i⇤ andEi⇤ are related to the original CAMME process:(X̃i ,if X̃i is not a leaf node in G̃;
⇤
X̃i =
, and
X̃i Ẽi , otherwise;
(9)
(
Ei ,
if X̃i is not a leaf node in G̃;Ei⇤ =Ei + Ẽi , otherwise.
Clearly Ei⇤ s are independent across i, and as we shallsee in Section 4, the information shared by diﬀerence
Xi is still captured by X̃⇤ . For each CAMME specified
by (2) and (1), there always exists an observationallyequivalent representation in the form of (7). We callthe representation (7) the canonical representation of
the CAMME (CR-CAMME).
Example Set 1 Consider the following example withthree observed variables Xi , i = 1, 2, 3, for which X̃1 !
X̃2X̃3 , with causal relations X̃2 = aX̃1 + bX̃3 + Ẽ2 .
That is,
2
3
2
3
1 0 0
0 0 0
B = 4a 0 b 5 , and A = 4a 1 b 5 .
0 0 0
0 0 1
Therefore,

X = X̃ + E = X̃⇤ + E⇤
2
3
2
3
E1
1 0 
Ẽ
= 4a b 5 · 1 + 4Ẽ2 + E2 5
Ẽ3
0 1
E3
2
3
Ẽ1
2
3
7
1 0
1 0 0 6
6 Ẽ3 7
7.
0 1 05 · 6= 4a bE1
6
70 1
0 0 1 4Ẽ2 + E2 5
E3
In causal discovery from observations in the presenceof measurement error, we aim to recover informationof the measurement-error-free causal model G̃. Let us
define a new graphical model, G̃⇤ . It is obtained byreplacing variables X̃i in G̃ with variables X̃i⇤ . In otherwords, it has the same causal structure and causal
parameters (given by the B matrix) as G̃, but with

variables X̃i⇤ as its nodes. If we manage to estimate
the structure of and the involved causal parameters inG̃⇤ , then the causal model of interest, G̃, is recovered.
We defined the graphical model G̃⇤ because we cannot
fully estimate the distribution of measurement-errorfree variables X̃, but might be able to estimate that ofX̃⇤ under proper assumptions, as shown in Section 4.
Compared to G̃, 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 (9)). For instance, suppose in G̃⇤ ,PA(X̃3⇤ ) = {X̃1⇤ , X̃2⇤ }, where PA(X̃3⇤ ) denotes the set ofparents of X̃3⇤ in G̃⇤ , and that X̃3 is a leaf node. Theneach of X̃1 , X̃2 , and X̃3 is a deterministic function of
the remaining two. More generally, let X̃l⇤ be a leaf
node in the causal graph G̃⇤ ; then each of the variables
in {X̃l⇤ } [ PA(X̃l⇤ ), denoted by X̃k⇤ , is a deterministic
function of the remaining variables.
To make it possible to identify the structure of G̃ fromthe distribution of X, in what follows we assume the
distribution of X̃⇤ satisfies the following assumption.
A0. The causal Markov condition holds for G̃ andthe distribution of X̃i is faithful w.r.t.
G̃.
Furthermore, the distribution of X̃i⇤ is nondeterministically faithful w.r.t. G̃⇤ , in the sensethat if there exists S, a subset of {X̃k⇤ : k 6= i, k 6=j}, such that neither of X̃i⇤ and X̃j⇤ is a deterministic function of S and X̃i⇤ ?
? X̃j⇤ | S holds, then⇤⇤X̃i and X̃j (or X̃i and X̃j ) are d-separated by Sin G̃⇤ .
This non-deterministically faithfulness assumption excludes a particular type of parameter coupling in thecausal model for X̃i . in Figure 4 we give a causal
model in which the causal coeﬃcients are carefully
chosen so that this assumption is violated: becauseX̃3⇤ = aX̃1⇤ + bX̃2⇤ and X̃4⇤ = 2aX̃1⇤ + 2bX̃2⇤ + E4⇤ , wehave X̃4⇤ = 2X̃3⇤ + E4⇤ , implying X̃4⇤ ?
? X̃1⇤ | X̃3⇤ and
⇤
⇤
⇤
X̃4 ?
? X̃2 | X̃3 , which are not given by the causal
Markov condition on G̃. We note that this nondeterministic faithfulness is defined for the distributionof the constructed variables X̃i⇤ , not the measurementerror-free variables X̃i . (Bear in mind their relationshipgiven in (9).) This assumption is generally stronger
than the faithfulness assumption for the distribution ofX̃i . In particular, in the causal model given in Figure 4,
the distribution of X̃i is still faithful w.r.t. G̃. Below
we call the conditional independence relationship between X̃i⇤ and X̃j⇤ given S where neither of X̃i⇤ andX̃j⇤ is a deterministic function of S non-deterministic
conditional independence.
Now we have two concerns. One is whether essential
information of the CR-CAMME is identifiable from

2a
X̃1

c
a

b

X̃2

2b

X̃4

d

X̃5

X̃3

Figure 4: A specification of the causal model G̃ inwhich X̃i⇤ are not non-deterministically faithful w.r.t.
G̃ because of parameter coupling.
observed values of X. The other is what information of
the original CAMME, in particular, the causal modelover X̃i , can be estimated from the above identifiable
information of the CR-CAMME. Although the transformation from the original CAMME to a CR-CAMME isstraightforward, 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 X̃i are leaf nodes in G̃; second,even if X̃i is known to be a leaf node, it is impossible toseparate the measurement error Ei from the noise Ẽi in
Ei⇤ . Fortunately, we are not interested in everything of
the original CAMME, but only the causal graph G̃ andthe corresponding causal influences B. Accordingly, inthe next section we will explore what information of the
CR-CAMME is identifiable from the observations of X
and how to further reconstruct necessary informationof the original CAMME.
In the measurement error model (1) we assumed thateach observed variable Xi is generated from its own latent variable 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 canstill use the CR-CAMME to represent the process. In
the former case, certain rows of ANL are identical. For
instance, if X1 and X2 are generated as noisy observations of the same latent variable, then in (7) the
first two rows of ANL are identical. (More generally,
if one allows diﬀerent coeﬃcients to generate themfrom the latent variable, the two rows are proportional
to each other.) Let us then consider an example in
the latter case. Suppose X3 is generated by latentvariables X̃1 and X̃2 , for each of which there is also
an observable counterpart. Write the causal model as
X3 = f (X̃1 , X̃2 ) + E3 and introduce the latent variableX̃3 = f (X̃1 , X̃2 ), and then we have X3 = X̃3 + E3 .
The CR-CAMME formulation then follows.

4

IDENTIFIABILITY IN THE
LINEAR, NON-GAUSSIAN CASE

The CR-CAMME (7) has a form of the factor analysis
model (FA) (Everitt, 1984), which has been a funda-

mental tool in data analysis. Accordingly, one canstudy the identifiability for CAMME by making useof the identifiability of FA, as reported by Zhang et al.
(2017). The identifiability of FA, however, replies heavily on the assumption that there are a relatively large
number of leaf variables in the causal graph G̃ (Bekker& ten Berge, 1997), which seems rather strong. Moreover, it has been shown that second-order statistics
usually is not informative enough to recover a uniquecausal model (Spirtes et al., 2001). Interestingly, weshow that the identifiability results can greatly benefit
from the non-Gaussianity assumption on the data. In
this paper we make the following assumption on the
distribution of Ẽi :A1. All Ẽi are non-Gaussian.
We note that under the above assumption, ANL in (8)can be estimated up to the permutation and scaling
indeterminacies (including the sign indeterminacy) of
the columns, as given in the following lemma. Thiscan be achieved by using overcomplete Independent
Component Analysis (ICA) (Hyvärinen et al., 2001).
Lemma 1. Suppose assumption A1 holds. Given X
which is generated according to (8), ANL is identifiable
up to permutation and scaling of columns as the sample
size N ! 1.
Proof. This lemma is implied by Theorem 10.3.1 in(Kagan et al., 1973) or Theorem 1 in (Eriksson &Koivunen, 2004).
What information of the causal structure 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.,2011b), to recover it? LiNGAM assumes that thesystem is non-deterministic: each variable is generated
as a linear combination of its direct causes plus a nondegenerate noise term. As a consequence, the linear
transformation from the vector of observed variables tothe vector of independent noise terms is a square matrix; ICA-LiNGAM applies certain operations to thismatrix to find the causal model, and Direct-LiNGAM
estimates the causal ordering by enforcing the property
that the residual of regressing the eﬀect on the root
cause is always independent from the root cause.
In our case, ANL , the essential part of the mixing
matrix in (8), is n ⇥ r, where r < n. In other words,
for some of the variables X̃i⇤ , the causal relations are
deterministic. (In fact, if X̃k is a leaf node in G̃, X̃k⇤ isa deterministic function of X̃k ’s direct causes.) As aconsequence, unfortunately, the above causal analysis
methods based on LiNGAM, including ICA-LiNGAM

and Direct-LiNGAM, do not apply. We will see how torecover information of G̃ by analyzing the estimatedANL .
We will show that some group structure and the groupwise causal ordering in G̃ can always be recovered.
Before presenting the results, let us define the following ordered group decomposition according to causal
structure G̃.
Definition 2 (ordered group decomposition).
Consider the causal model G̃⇤ . Decompose all involved
nodes into disjoint groups in the following way. Firstput all leaf nodes which share the same direct-and-onlydirect cause in the same group; further incorporate thecorresponding direct-and-only-direct cause in the samegroup. Here we say a node X̃i⇤ is the “direct-and-onlydirect" cause of X̃j⇤ if and only if X̃i⇤ is a direct causeof X̃j⇤ and there is no other directed path from X̃i⇤ to
X̃j⇤ . After forming all groups each of which involves atleast one leaf node, each of the remaining nodes forms a
separate group. Each node is guaranteed to be in
one and only one group. We call the set of all suchgroups ordered according to the causal orderingof the non-leaf nodes in DAG G̃⇤ an ordered groupdecomposition of G̃⇤ , denoted by GG̃⇤ .
G̃A :

G̃B :

X̃8

X̃1

X̃2
X̃5

X̃3
X̃6

X̃4

X̃2

X̃7

(b)

G̃C (solid lines as its edges):G̃D (all lines as its edges):
X̃2
X̃3
(c)

X̃4

X̃3

X̃4

(a)

X̃1

X̃1

X̃5
X̃6

G̃E :

X̃1

X̃4
X̃2

X̃3

X̃5

X̃6

X̃8

X̃7
(d)

Figure 5: A set of causal DAGs G̃ as illustrative examples. (a) DAG G̃A . (b) G̃B . (c) Two DAGs G̃C andG̃D . (d) G̃E .
Example Set 2 As seen from the process of orderedgroup decomposition, each non-leaf node is in one andonly one ordered group, and it is possible for multiple leaf nodes to be in the same group. Therefore,
in total there are (n l) ordered groups. For example, for G̃A given in Figure 5(a), a corresponding
group structure for the corresponding G̃⇤ is GG̃⇤ =A({X̃1⇤ } ! {X̃2⇤ , X̃5⇤ } ! {X̃3⇤ , X̃6⇤ } ! {X̃4⇤ , X̃7⇤ , X̃8⇤ }),and for G̃B in Figure 5(b), there is only one group:GG̃⇤ = ({X̃1⇤ , X̃2⇤ , X̃3⇤ , X̃4⇤ }). For both G̃C and G̃D ,Bgiven in Figure 5(c), an ordered group decompositionis ({X̃1⇤ } ! {X̃2⇤ , X̃3⇤ } ! {X̃4⇤ } ! {X̃5⇤ , X̃6⇤ }).

Note that the causal ordering and the ordered groupdecomposition of given variables according to the graphical model G̃⇤ may not be unique (this will actually
give rise to the possibility of distinguishing between the
non-leaf and leaf node in the group, as shown next). For
instance, if G̃⇤ has only two variables X̃1⇤ and X̃2⇤ which
are not adjacent, both decompositions ({X̃1⇤ } ! {X̃2⇤ })and ({X̃2⇤ } ! {X̃1⇤ }) are correct. Consider G̃⇤ overthree variables, X̃1⇤ , X̃2⇤ , X̃3⇤ , where X̃1⇤ and X̃2⇤ arenot adjacent and are both causes of X̃3⇤ ; then both({X̃1⇤ } ! {X̃2⇤ , X̃3⇤ }) and ({X̃2⇤ } ! {X̃1⇤ , X̃3⇤ }) are valid
ordered group decompositions.
We first present a procedure to construct the orderedgroup decomposition and the causal ordering among
the groups from the estimated ANL . We will further
show that the recovered ordered group decompositionis always asymptotically correct under assumption A1.
4.1

Construction and Identifiability ofordered Group Decomposition

First of all, Lemma 1 tells us that ÂNL in (8) is identifiable up to permutation and scaling columns. Let us
start with the asymptotic case, where the columns of
the estimated ANL from values of Xi are a permuted
and rescaled version of the columns of ANL . In what
follows the permutation and rescaling of the columnsof ANL does not change the result, so below we justwork with the true ANL , instead of its estimate.
X̃i⇤ and X̃i follow the same causal DAG, G̃, and X̃i⇤ arecausally suﬃcient, although some variables among them(corresponding to leaf nodes in G̃⇤ ) are determined bytheir direct causes. Let us find the causal orderingof X̃i⇤ . If there are no deterministic relations andthe values of X̃i⇤ are given, the causal ordering canbe estimated by recursively performing regression andchecking independence between the regression residual
and the predictor (Shimizu et al., 2011b). Specifically,
if one regresses all the remaining variables on the root
cause, the residuals are always independent from thepredictor (the root cause). After detecting a root cause,
the residuals of regressing all the other variables on the
discovered root cause are still causally suﬃcient andfollow a DAG. One can repeat the above procedure tofind a new root cause over such regression residuals,
until no variable is left.
However, in our case we have access to ANL but not
the values of X̃i⇤ . Fortunately, the independence between regression residuals and the predictor can still bechecked by analyzing ANL . Recall that X̃⇤ = ANL ẼNL ,where the components of ẼNL are independent. Without loss of generality, here we assume that all components of ẼNL are standardized, i.e., they have azero mean and unit variance. Denote by ANL
the
i·
N L|
ith row of ANL . We have E[X̃j⇤ X̃i⇤ ] = ANL
A
and
j·
i·
N L|
NL 2
E[X̃i⇤2 ] = ANL
A
=
||A
||
.
The
regression
model
i·
i·
i·
for X̃j⇤ on X̃i⇤ isX̃j⇤ =

E[X̃j⇤ X̃i⇤ ]E[X̃i⇤2 ]X̃i⇤ + Rj

i =

NL|
ANL
j· Ai·
X̃i⇤ + Rj
2
||ANL
i· ||

i.

Here the residual can be written as
Rj⇤
i = X̃j

ANL
j·

=
|

NL|
ANL
j· Ai·
X̃i⇤
2
||ANL
i· ||

NL| NLANL
Ai·
j· Ai·ẼNL .
2
||ANL
||
i·
{z
}
,↵j

(10)

i

If for all j, Rj i is either zero or independent from X̃i⇤ ,we consider X̃i⇤ as the current root cause and put it
and all the other variables which are deterministicallyrelated to it in the first group, which is a root cause
group. Now the problem is whether we can check forindependence between nonzero residuals Rj i and thepredictor X̃i⇤ . Interestingly, the answer is yes, as statedin the following proposition.
Proposition 3. Suppose assumption A1 holds. For
variables X̃⇤ generated by (7), regression residual Rj igiven in (10) is independent from variable X̃i⇤ if andonly if↵j i ANL
= 0,
(11)
i·
2

where

denotes entrywise product.

So we can check for independence between the predictor
and regression residual as if the values of X̃⇤ were given.
Consequently, we can find the root cause group.
We then consider the residuals of regressing all theremaining variables X̃k⇤ on the discovered root cause as
a new set of variables. Note that like the variables X̃j⇤ ,these variables are again linear mixtures of Ẽi . Repeating the above procedure on this new set of variables
will give the second root cause and its ordered group.
Applying this procedure repeatedly until no variable
is left finally discovers all ordered groups following
the causal ordering. The constructed ordered groupdecomposition is asymptotically correct, as stated in
the following proposition. We denote by OICA+Reg theabove two-stage procedure: we first apply overcomplete
ICA to find an estimate of ANL , and then do regression
and check for independence between the residuals andthe current candidate root cause by analyzing ANL .

Proposition 4. (Identifiable ordered group decomposition) Let Xi be generated by the CAMME
with the corresponding measurement-error-free variables generated by the causal DAG G̃ and suppose assumptions A0 and A1 hold. The ordered group decomposition constructed by the above procedure is asymptotically correct, in the sense that as the sample size
N ! 1, if non-leaf node X̃i is a cause of non-leaf nodeX̃j , then the ordered group which X̃i is in precedes thegroup which X̃j belongs to. However, the causal ordering among the nodes within the same ordered group
may not be identifiable.
The result of Proposition 4 applies to any DAG structure G̃. Clearly, the identifiability can be naturally
improved if additional assumptions on the causal structure G̃ hold. In particular, to recover information ofG̃, it is essential to answer the following questions.

generated by the CAMME where Assumptions A0 and
A1 hold.1 Let the sample size N ! 1. Then if assumption A2 holds, leaf node O is correctly identified
from observations of X (more specifically, from theestimated ANL or the distribution of X̃⇤ ).
A2. According to G̃⇤ , for leaf node O in the considered
ordered group g (k) , at least one of its parents is
not a parent of the non-leaf node in g (k) or someother leaf node in g (k) .
Example Set 3 Suppose Assumptions A0 and A1
hold.

• Can we determine which nodes in an ordered groupare leaf nodes?

• For G̃A in Figure 5(a), assumption A2 holds forX̃7⇤ and X̃8⇤ in the ordered group {X̃4⇤ , X̃7⇤ , X̃8⇤ }:each of them has a parent which is not a parent of
the other; so both of them are identified to be leaf
nodes from the estimated ANL or the distributionof X̃⇤ , and X̃4⇤ can then be determined as a nonleaf node.

• Can we find the causal edges into a particularnode?

• For G̃B , we cannot detect which node is a leaf
node or a non-leaf node.

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

Identifying Leaf Nodes and Individual
Causal Edges

If for each ordered group we can determine which variable is the non-leaf node, the causal ordering among thevariables X̃i⇤ is then fully known. The causal structurein G̃⇤ as well as the causal model can then be readily estimated by regression: for a leaf node, its directcauses are those non-leaf nodes that determine it; fora non-leaf node, we can regress it on all non-leaf nodes
that precede it according to the causal ordering, andthose predictors with non-zero linear coeﬃcients are
its parents. This way the structure can be estimateduniquely under Assumption A0, although whether thecausal parameters in the causal model are uniquely
identifiable is another issue for investigation.
Now the goal is to see whether it is possible to find out
which variables in a given ordered group are leaf nodes;
if all leaf nodes are found, then the remaining one
is the (only) non-leaf node in the considered orderedgroup. Below we will show that it is possible to findleaf nodes by “looking backward" or “looking forward";
the former makes use of the parents of the variables in
the considered group, and the latter exploits the fact
leaf nodes do not have any child.
Proposition 5. (Leaf node determination by“looking backward") Suppose the observed data were

• For both G̃C and G̃D in Figure 5(c), X̃6⇤ , in theordered group {X̃5⇤ , X̃6⇤ }, follows assumption A2
and can be found to be a leaf node from the matrix
ANL ; accordingly, X̃5⇤ has to be a non-leaf node.
• For G̃E in Figure 5(d), assumption A2 holds for
all leaf nodes, X̃4⇤ , X̃5⇤ , and X̃8⇤ , which can thenbe found to be leaf nodes.
We can also determine leaf nodes by looking at therelationships between the considered variables and thevariables causally following them, as stated in the following proposition.
Proposition 6. (Leaf node determination by“looking forward") Suppose the observed data weregenerated by the CAMME where Assumptions A0 and
A1 hold. Then as the sample size N ! 1, we can correctly identify the leaf node U in the considered orderedgroup g (k) from values of X if assumption A3 holds forit:
A3. 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 (2) ... [g (k) \ {U } which does not include all parents of U
and 2) is a child of the non-leaf node in g (k) .
1
In this non-Gaussian case (implied by assumption A1),
the result reported in this proposition may still hold if
one avoids the non-deterministic faithfulness assumption
and assumes a weaker condition; however, for simplicityof the proof we currently still assume non-deterministic
faithfulness.

Example Set 4

Let Assumptions A0 and A1 hold.

• For data generated by G̃A in Figure 5(a), we already found X̃4⇤ in ordered group {X̃4⇤ , X̃7⇤ , X̃8⇤ }to be a non-leaf node because of Proposition 5.
Proposition 6 further indicates that X̃2⇤ (in group{X̃2⇤ , X̃5⇤ }) and X̃3⇤ (in group {X̃3⇤ , X̃6⇤ }) are nonleaf nodes, and all leaf nodes are identified.
• For G̃B in Figure 5(b), there is only one orderedgroup, and it does not provide further information
by looking “backward" or “forward", and it is impossible to find the non-leaf node with Proposition
5 or 6.
• For both G̃C and G̃D in Figure 5(c), X̃6⇤ was foundto be a leaf node due to Proposition 5; thanks to
Proposition 6, the other leaf node, X̃3⇤ , was also
detected. In particular, in G̃C , for leaf node X̃3⇤
both X̃4⇤ and X̃6⇤ satisfy the two conditions inAssumption A3; however, in G̃D , for leaf nodeX̃3⇤ only X̃4⇤ satisfies them. All leaf nodes weresuccessfully found.
• For G̃E in Figure 5(d), Proposition 5 already allows us to identify all leaf nodes, X̃4⇤ , X̃5⇤ , andX̃8⇤ . The assumptions in Propositions 5 and 6 are
not exclusive: Assumption A3 also holds for X̃4⇤
(for it X̃7⇤ satisfies the two conditions), we canalternatively identify this leaf node by making use
of Proposition 6.
For contaminated data generated by any of G̃A , G̃C ,G̃D , and G̃E , now we can find all leaf nodes in
the measurement-error-free causal model. One canthen immediately estimate the whole structure of themeasurement-error-free model.
The above two propositions are about the identifiably ofleaf nodes in the measurement-error-free causal model.
By applying them to all leaf nodes, we have (suﬃcient)conditions under which the causal graph of G̃ is fully
identifiable.
Proposition 7. (Full identifiability) Suppose theobserved data were generated by the CAMME where
Assumptions A0 and A1 hold. Assume that for eachleaf node in G̃⇤ , at least one of the the two assumptions,A2 and A3, holds. Then as the sample size N ! 1,
the causal structure G̃ is fully identifiable from theobservations with random measurement error.
In the general case, the causal structure G̃ might not be
fully identifiable, and the above propositions may allow
partial identifiability of the underlying causal structure.
Roughly speaking, the ordered group decomposition is
identifiable in the non-Gaussian case; with Propositions
5 and 6 one can further identify some leaf nodes as wellas their parents.

5

CONCLUSION ANDDISCUSSIONS

The measured values of variables of interest in various
fields, including the social sciences, neuroscience, andbiology, are often contaminated by measurement error.
Unfortunately, the output 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 themeasurement-error-free variables without using muchprior knowledge about the measurement error. To thisend, this paper investigates identifiability conditions forthe underlying measurement-error-free causal structure
given contaminated observations. We have shown that
under appropriate conditions, the causal structure ofinterest is partially or even fully identifiable.
We formulated four assumptions. Assumption A0 is
about the Markov condition and non-deterministic
faithfulness assumption for causal model G̃⇤ . Assumption A1 is about the distribution of the underlying noise
terms in the causal process. The remaining two areabout particular types of “sparsity" of the underlying
causal graph. We note that in principle, all assumptions except A0 are testable from the observed data.
This suggests that it is possible to develop practicalcausal discovery methods to deal with measurement error that are able to produce reliable information at leastin the asymptotic case. In addition, it is worth noting that some involved assumptions may be weakened.
For instance, faithfulness is not required to find thecorrect ordered group decomposition, but just neededfor detecting leaf nodes in the ordered groups. Suppose Assumptions A0 and A1 hold; we conjecture thatthe necessary and suﬃcient condition for the non-leaf
node to be identifiable is that at least one of the two
assumptions, A2 and A3, holds. To falsify or prove thisconjecture is part of our future work.
It is worth noting that various kinds of backgroundknowledge of the causal model may further help improve the identifiability of the measurement-error-freecausal model. For instance, if one knows that all
causal coeﬃcients are smaller than one in absolutevalue, then the measurement-error-free causal modelin Figure 5(b) is immediately identifiable from contaminated data. Our future research further includes 1)
establishing identifiability conditions that allow cycles
in the measurement-error-free causal model in light ofubiquity of cycles in causal models, 2) developing computationally eﬃcient algorithms for causal discovery
under measurement error based on the established theory, and 3) proposing eﬃcient methods for particularcases where each measurement-error-free variable has
multiple measured eﬀects or multiplied measurementerror-free variables generate a single measured eﬀect.

References
Bekker, P. A. and ten Berge, J. M. F. Generic global
indentification in factor analysis. Linear Algebra andits Applications, 264:255–263, 1997.
Chickering, D. M. Optimal structure identification withgreedy search. Journal of machine learning research,3(Nov):507–554, 2002.
Eriksson, J. and Koivunen, V. Identifiability, separability, and uniqueness of linear ICA models. IEEE
Signal Processing Letters, 11(7):601–604, 2004.
Everitt, B. S. An introduction to latent variable models.
London: Chapman and Hall, 1984.
Hyvärinen, A., Karhunen, J., and Oja, E. Independent
Component Analysis. John Wiley & Sons, Inc, 2001.
Kagan, A. M., Linnik, Y. V., and Rao, C. R. Characterization Problems in Mathematical Statistics. Wiley,
New York, 1973.
Kummerfeld, E., Ramsey, J., Yang, R., Spirtes, P., andScheines, R. Causal clustering for 2-factor measurement models. In Calders, T., Esposito, F., Hüllermeier, R., and Meo, R. (eds.), Proc. ECML PKDD,
pp. 34–49, 2014.
Pearl, J. Causality: Models, Reasoning, and Inference.
Cambridge University Press, Cambridge, 2000.
Scheines, R. and Ramsey, J. Measurement error andcausal discovery. In Proc. CEUR Workshop 2016, pp.
1–7, 2017.
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, S., Hoyer, P. O., and Hyvärinan, A. Estimation of linear non-gaussian acyclic models for latent
factors. Neurocomputing, 72:2024–2027, 2011a.
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, 2011b.
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, P., Glymour, C., and Scheines, R. Causation,
Prediction, and Search. MIT Press, Cambridge, MA,
2nd edition, 2001.
Wiedermann, W., Merkle, E. C., and von Eye, A. Direction of dependence in measurement error models.
British Journal of Mathematical and Statistical Psychology, 71:117–145, 2018.
Zhang, K. and Chan, L. Extensions of ICA for causality
discovery in the hong kong stock market. In Proc.
13th International Conference on Neural Information
Processing (ICONIP 2006), 2006.

Zhang, K. and Hyvärinen, A. On the identifiabilityof the post-nonlinear causal model. In Proceedingsof the 25th Conference on Uncertainty in Artificial
Intelligence, Montreal, Canada, 2009.
Zhang, K., Gong, M., Ramsey, J., Batmanghelich, K.,
Spirtes, P., and Glymour, C. Causal discovery in
the presence of measurement error: Identifiability
conditions. In UAI 2017 Workshop on Causality:
Learning, Inference, and Decision-Making, 2017.