Causal Discovery in Linear Latent Variable Models Subject to Measurement Error
Authors: Yuqin Yang
AmirEmad Ghassami
Mohamed S Nafea
Negar Kiyavash
Kun Zhang
Ilya Shpitser
Venue: NeurIPS 2022 Accept (2022)
Keywords: Causal discovery
Measurement error
Latent variable models
Faithfulness
Structural identification

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


Causal Discovery in Linear Latent Variable Models Subject to Measurement Error
Yugin Yang" Georgia Institute of Technology
AmirEmad Ghassami
Mohamed Nafea University of Detroit Mercy
Johns Hopkins University
Negar Kiyavash
Kun Zhang Carnegic Mellon University & MBBUAI
Ilya Shpitser Johns Hopkins University
École Polytechnique Fédérale de Lausanne (EPFL)
Abstract
We focus causal discovery in the presence of measurement error in linear sys- tems where the mixing matrix, i.e., the matrix indicating the independent exogenous noise terms pertaining to the observed variables, is identified up to permutation and scaling of the columns. We demonstrate somewhat surprising connection between this problem and causal discovery in the presence of unobserved parentless causes, in the sense that there is a mapping, given by the mixing matrix, between the un- derlying models to be inferred in these problems. Consequently, any identifiability result based on the mixing matrix for one model translates to an identifiability result for the other model. We characterize what extent the causal models be identified under a two-part faithfulness assumption. Under only the first part of the assumption (corresponding to the conventional definition of faithfulness), the structure can be learned up to the causal ordering among an ordered grouping of the variables but all the edges across the groups can be identified. We further show that if both parts of the faithfulness assumption are imposed, the structure can be learned up to more refined ordered grouping. As result of this refinement, for the latent variable model with unobserved parentless causes, the structure can be identified. Based our theoretical results, we propose causal structure learning methods for both models, and evaluate their performance on synthetic data.
1 Introduction
Learning causal structure among the variables of system from observational data has received considerable attention in the literature, since subject matter knowledge on causal relationships is often incomplete or impossible to obtain in many applications [24, 16]. In many real-life systems, not all variables of interest or all direct common causes of those variables can be observed. This necessitates approaches for structure learning capable dealing with latent variables. For the case that no a-priori restrictions on the functional form of causal mechanisms are imposed, constraint-based algorithms such as the Fast Causal Inference (FCI) algorithm have been proposed [24]. Such approaches are often unable to identify the direction of the majority of causal connections in the system, which motivates placing additional, often parametric, restrictions on the generating model. One of the most commonly used restrictions is assume that the model is linear with non-Gaussian exogenous noise terms [21, 22, 12, 10]. This generating model leads to identification the existence and orientation of all edges in causal model, assuming that no latent variables that are common causes of two or more variables exist [21, 22]. Moreover, in such models even when latent variable common causes exist, it is still possible to orient additional edges compared to algorithms such FCI [12, 19, 1].
*Correspondence to: yuginyangggatech.ed.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In certain applications, although some of the variables of interest (called underlying variables) are latent, we may have access to noisy measurements of them [17, 13, 29, 18, 11]. In this case. condi- tional independence patterns among observed variables (that are noisy measurements of underlying variables) are different from those among the underlying (measurement-ernog frree) variables. In general, constraint-based approaches to causal discovery are not able to correct for the difference in observed independence due to the presence of measurement error, and thus will produce erroncous edge adjacencies and orientations. Similarly, naive application of methods based on non-Gaussian exogenous noise assumption may also fail in recovering the correct causal relations in the presence of measurement error. This is due to the fact that the extra measurement noise terms break the asymmetry utilized by those methods.
In this paper, we bring additional insight into the problem of causal discovery under measurement error by showing a surprising connection between linear structural equation models (SEMs) where variables are measured with error, and linear SEMs with hidden variables. In particular, we consider two linear SEMs. the first model, the unobserved variables are in fact of interest and can appear in any part of the causal structure of the system, but we assume that noisy measurements of these unobserved variables are available. We refer to this model as the linear SEM with measurement error (SEM-ME). The second model does not require measurements of the latent variables, as they are not of primary interest, yet we assume that all latent variables are root variables, meaning that they are not causally affected by any other latent or observed variables in the system. We refer to this model as the linear SEM with unobserved roots (SEM-UR). It is noteworthy that assuming latent variables are limited to be root variables does not affect the estimated total causal effects among the observed variables (see Remark 1 in Section 2.2), and provides a representation of a latent variable model that is consistent with these causal effects. For this reason, this restriction is common in the literature of causal inference [8.9 9, 12, 5].
We study the identification of linear SEM-MES and SEM-URs in a setup where the independent exogenous noise terms that causally (directly or indirectly) affect each observed variable can be identified. That is, the mixing matrix of the linear system that transforms exogenous noise terms to observed variables is identified up to permutation and scaling of the columns. This can be satisfied, for example, if all independent exogenous noise terms are non- -on-Gaussian. Our first main contribution is presenting a mapping between the linear SEM-MEs and SEM-URs, which demonstrates a corre- spondence between a weighted causal diagram² generated by SEM-UR and set of weighted causal diagrams from the SEM-ME (Theorem 1). The models in this correspondence all possess the same mixing matrix. Consequently, any identifiability result based on the mixing matrix for one model is applicable to the other model. This allows us to study the problem of causal discovery in these two models together.
Additionally, we study the identifiability of linear SEM-MES and SEM-URs, and show how it benefits from two-part faithfulness assumption. The first part prevents existence of zero total causal effeets of a variable on its descendants and the second part prevents cancellation or proportionality among specific edges. Our second main contribution is to characterize the extent of identifiability of the causal model under our faithfulness assumption. We demonstrate that if only the first part of the faithfulness assumption is imposed, the model can be learned up an equivalence class characterized by an ordered grouping of the variables which we call ancestral ordered grouping (AOG). In this grouping, the induced graph on the variables of each group a star graph (see Section 4.3). Although the AOG is identified, not all edges across the groups or the group centers (or their exogenous noise terms) are identifiable (Theorem 2). The AOG characterization is a refined version of the ordered grouping proposed in [29]. We further show that if both parts of the faithfulness assumption are imposed, the model can be learned up to an equivalence class characterized by more refined ordered grouping which we call direct ordered grouping (DOG). Edges across groups can be identified under this characterization, yet the the group centers (or their exogenous noise terms) remain unidentified (Theorem 3). This characterization further implies that the ground-truth structure of SEM-UR is uniquely identifiable (Corollary 3). Lastly, we show that models in the DOG equivalence class are strictly sparser than other models in the AOG equivalence class (Proposition 4). We propose causal structure learning methods for both SEM-ME and SEM-UR based on this property, and evaluate their performance on synthetic data.
A weighted causal diagram is the directed graph corresponding to the linear model which associates the coefficient of variable X₁ in the structural equation for X2 to the edge from X₁ to X2.

---

2 Model description
In this section, we first introduce the two models considered in this paper, namely linear SEM-ME and SEM-UR. We then discuss model assumption needed for our identifiability results.
2.1 Linear structural equation model with measurement error (SEM-ME)
Definition 1 (Linear SEM-ME) A linear SEM-ME consists of sel of "underlying" variables which can be partitioned into unobserved underlying variables 2 = =Z7,,..,,2 -,,,,p.). underlying variables y = (Yi..., "T....,,--p Yp-p, }. In addition, we have another set of observed variables u (U,,... ,Up,} corresponding to the noisy measurements of Z. The underlying variables in 2 Jy can be arranged in a total (causal) order (such that no later variable in the order can cause any earlier variable), and variables V; E Z U and U. E l are generated as follows:
and observed
V1
Σ
CitV, + NN; i [p];
U Ze +Nu, i <ppp).
(1)
j: (EP((())))
where [n] := (1.2....., PV(V.) S ZUY denotes direct causes of Vg. Nv, (resp. Nu.) is the exogenous noise term (resp. the measurement error) corresponding to V₁ (resp. U.).
We define the weighted causal diagram of the linear SEM-ME as weighted directed graph where the nodes are the variables in Z U V. There is directed edge (causal connection) from V; to Vj with weight Cjs if and only if Cji + O, for V2, Vj E Z V.V Because of our causal order assumption, the causal diagram will be acyclic. We use the terms node and variable interchangeably. The linear SEM-ME in this work is a generalization of the linear causal model with measurement error proposed in [29], in the sense that some of the underlying variables can be observed.
We define unobserved leaf node (u-leaf node) an unobserved underlying variable in 2 that does not have any children in 2 U U.Y. The rest of the underlying variables are referred to as non u-leaf nodes (nu-leaf nodes): These include unobserved non-leaf underlying variables, which have children in Z Y., and observed underlying variables in V. Similar to the argument in [29], given observed data generated by the linear SEM-ME in Equation (1), for a u-leaf node Zi, its exogenous noise term Nz, is not distinguishable from its measurement error No.- This follows because Z; is not observed, and Nz, only influences one observed variable which the noisy measurement U.. Therefore, we restrict our focus to the following canonical form.
Definition (Canonical form of a linear SEM-ME) The canonical form of linear SEM-ME is the one in which all u- lele nodes have no exogenous noise terms. Specifically,
D
z NN
NzL + No
N.
Cz CCy
Z
NU
NZNz U=
+
NNNN
(2)
Y
[Ny
where LNL, ZL, Y are the vectors of unobserved underlying non-leaf variables, u-leaf nodes, and observed underlying variables, respectively. Nzwc, Nzu, and Ny are the corresponding noise vectors. NNU = \ZA Y) is the vector of nu-leaf nodes. U is the vector of noisy measurements and NUNL and Nu denote the noise vectors corresponding to the measurements of N and Z respectively. C represents the causal connections among nu- leaf nodes, and can be partitioned into [Czi Cy] corresponding to NI; Y). respectively. nu-leaf nodes u-leaf nodes. Note that C can be arranged into strictly lower triangular matrix via simultaneous column and row permutations (due to the acyclicity assumption).
represents the causal connections from
2.2 Linear structural equation model with unobserved roots (SEM-UR)
Definition 3 (Linear SEM-UR) A linear SEM-UR consists of a set of observed variables X = (X1..... .yy) and another set of latent variables H. (H..... ..).. All latent variables are assumed to be root variables (have no direct causes). The observed variables are arranged in causal order, and each observed variable is directly influenced by a linear combination of other observed and latent variables, plus an independent exogenous noise term.
= HN=NH, i E [1]
X, "y=E,en kew bj: H, +
Ex + Nx,:
JE [g]-
(3)
We define the weighted causal diagram of the linear SEM-UR as a directed graph where the nodes are the observed and latent variables in X' U H. There is a causal connection from X; (resp. H2) to X; with weight ajz (resp. by:) if and only if aze (resp. by:) # O. Because of our causal order assumption, the causal diagram will be acyclic. Note that unlike in [12] and [19], consider a broader model
3

---

which allows latent variables to have single observed child. However, unlike the works considering relations among latent variables [1, 26, 27], we restrict all latent variables roots; see Remark
linear SEM-UR can be written in the following matrix form:
H Nı;;
X BH + AX Nx,
where X [X, XyI" and H [H Hi] are the vectors of observed and latent variables, respectively. Nx [Nx,
NH.l" represent the vectors of independent noise terms associated with X and H, respectively. B represents the causal connections from latent to observed variables, and A represents the causal connections among observed variables, which can be assumed to be a strictly lower-triangulat matrix (due to the acyclicity assumption).
Nx, and NH [NH,
Remark There exist works aiming to find the causal relations among the latent variables (as well as their relations with the measured variables) [23, 26, 3, 1, 27]. Our definition of a linear SEM-UR requires all the latent variables to be parentless. This assumption is common in the literature of causal inference, it does not restrict the feasible total causal effects (i.e., sum of products of path coefficients) among the observed variables [8, 9, SJ. Specifically, let us start from a general linear latent variable model in which some latent variables have parents. Hoyer el al. [12] proposed an al glgoitthm which maps such general model to one in which latent variables are parentless. They showed that the resulting model is observationally and causally equivalent the original model, i.e., the joint distributions of observed variables are identical, and all causal effects of observed variables on other observed variables are identical in the models before and after the mapping.
2.3 Separability assumption
For both models in Sections 2.1 and 2.2, we assume that the noise components can be separated from observations (i.e.. the mixing matrices are recoverable). We first describe the mixing process for cach of the two models, and then state our separability assumption.
From Equation (2), we can write all underlying variables in the linear SEM-ME in terms of the independent noise terms, follows.
z N Y
D(I C) -1 C) (I- C)
NzNz Ny
W
where
WAB
(5)
I is the identity matrix, and (I C) and (I (I-C)y' represent the rows of (I- (-C)-1 corresponding to 7 NI. and Y, respectively. Using the relation between U and Z Equation (2), the two types of observed variables, i.e., measurements U and observed underlying variables Y, can be written
NZwL NY
T Y
I WAÉ
0
N2c + No NyNe
W
We refer W as the overall mixing matrix of the system. Given any column permuted and rescaled version of W. we can recover matrix WMEE by removing the submatrix [I 0J of size p X p. corresponding to U. Recall that p= the cardinality of Z (which is the same as the cardinality U).
Similarly, according to Equation (4), observed variables in the linear SEM-UR can be written in terms of the independent noise terms as
X= WUR
NH Nx
where W (I-
(I (I-A
(7)
Assumption (Separability) The linear SEM-ME (resp. linear SEM-UR) is separable, that is, the mixing matrix WME in Equation (5) (resp. WUR in Equation (7)) can be recovered from observations of [U; Y) (resp. X) up to permutation and scaling of its columns.
Separability assumption states that for every observed mixture, the independent exogenous noise terms pertaining to this mixture can be separated, i.e., the mixing matrix can be recovered up to permutation and scaling of its columns. An example of a setting where this assumption holds when all exogenous noises are non-Gaussian In this case, if the model satisfies the requirement in [7, Theorem 1] (SEM-ME always does), overcomplete Independent Component Analysis (ICA) can be used to recover the mixing matrix up permutation and scaling of its columns. Another

---

example where separability assumption is satisfied is the setup in which the noise terms are piecewise constant functionals satisfying set of mild conditions [2]. On the other hand, an example where this assumption is violated is when all exogenous noise terms have Gaussian distributions. In this case, the mixing matrix can only be recovered up to an orthogonal transformation.
3 Mapping between the weighted graphs of the models for identifiability
key observation in this work is that there exists mapping between the weighted causal diagrams of the introduced SEM-ME and SEM-UR, which leads to the corresponding mixing matrices W and WUR being transposes of one another.
Define the mapping y from the set of weighted causal diagrams of linear SEM-URs, denoted by M to the set of weighted causal diagrams of canonical linear SEM-MEs, denoted by MM where for each diagram M E MM (p(M) C -MME is constructed as follows: (a) Replace each latent variable in M with a Z variable. (b) Replace each observed root variable in M with a Y variable. (c) Replace the rest of the observed variables in M with either Z or Y variables. (d) Reverse all the edges in M. Note that (MM encompasses set of models, corresponding to the possible choices in step (c).
Similarly define the mapping & from the set MME to the set MUR where for each diagram M' E MMM,, & (M') E M is constructed as follows. (a) Replace each u-leaf variable in M' with latent variable. (b) Replace the rest of the variables in M' with observed variables. (c) Reverse all the edges in M'. Note that from the defimition of the two mappings, for any given M E MMRR
M ((((M))). For any given M' E MME,, M' E ((((M')).
Theorem Ler M MUR with mixing matrix WUR(M (M) and M' be a corresponding element in M with mixing matrix WME (M"), where M' E (p(M) and M = ((M)). Then there exist a permulation of the columns of (UURU)), demoted by WUR(M), and a permutation of the columns of (MM'). denoted by WME. (M'). which satisfy W MEMEMM) (W))(M))
The proofs of all the results are provided in the Appendix. Note that can be seen from the proof of Theorem 1, whether the nu-leaf variables, that are non-leaf in the SEM-ME, are observed or not does not change the corresponding mixing matrix.
Remark 2 The mapping introduced here is between a weighted diagram in SEM-UR and set of weighted diagrams in SEM-ME. The elements of the set in fact correspond to different settings of the non-leaf underlying variables being observed or not. Note that in most applications, it is clear to the researcher whether an underlying variable is observed or measured with error. Therefore, only one element of the set is relevant to the applicution and the set reduces to single element. Consequently. in our identifiaillity results, without loss of generality, we assume the set is a singleton.
Theorem I implics that under separability assumption, any identifiability result based on the mixing matrix for one model is applicable to the other model, by reversing all edges. This allows us to study the problem of causal discovery of these two models simultaneously.
H
XI
d
1
0
d
a
0
bd
+
C
ab
b
1
X3
X2
W
Example 1 Consider the linear SEM-UK UR in Figure I(a) comprised of three observed and one latent variable (denoted by a single circle). The corresponding linear SEM-ME under the mapping ip is shown in Figure I(b). Specifically, (i) the latent variable is mapped to the u-leaf variable ZL (denoted by double circle): (ii) the observed root X1 is mapped to the observed underly- ing variable Y;: and (iii) observed variables X2 and X3 could be mapped to either observed or unobserved un- derlying variables; hence the UR graph will be mapped to a set of graphs in the ME model. The mixing matri- ces for both models are shown in Figure 1. It can be readily seen that there exists permutation of the columns of WUR H which is equal to the transpose of W.E.
(a) Linear SEM-UR
Z
d
Y1
0
d
bd
+ c
0
b
Zz/Yss Y33
ZZ
122
G
ab
W
ME
(b) Linear SEM-ME
Figure 1: Example explaining the map- ping.
4 Identifiability of models
In this section, we study the extent of identifiability of linear SEM-ME and SEM-UR under the separability assumption. We consider both a weaker notion of structure identification, where only
5

---

the graph structure of the model is obtained, and stronger notion of model identification where, in addition to the graph structure, model parameters are recovered as well. In Section 4.1, we propose SEM-ME and SEM-UR faithfulness assumptions, which consist of two parts, the first of which is identical to the conventional faithfulness in linear causal models. We first discuss model identifiability under conventional faithfulness (i.e., the first part of our assumptions), which can be characterized by ancestral ordered grouping (AOG) of the variables, explained in Section 4.2. Next, under both parts of our proposed faithfulness assumptions, the extent of identifiability can be characterized by direct ordered grouping (DOG) of the variables, explained in Section 4.3. This leads to a subsequent result on structure identifiability for SEM-UR. In Section 4.4, show that the DOG characterization possesses a sparsity property, which can be used to construct recovery algorithms for both models.
4.1 Faithfulness assumption
Assumption 2 (SEM-ME faithfulness) (a) The total causal effect of any underlying variable on its descendant is not equal to zero. (b) For each variable V in a SEM-ME, the causal effect of parents of V on V cannot be replicated by fewer or equal variables due to fine tuning of the parameters. (See Appendix B. I for the formal statement.)
Assumption 3 (SEM-UR faithfulness) (a) The total causal effect of any observed or latent variable on its descendant is not equal to zero. (b) For each variable V in a SEM-UR, the causal effect of V on children of V cannot be replicated by fewer or equal variables due to fine tuning of the parameters. (See Appendix B. for the formal statement.)
Assumptions 2(a) and 3(a) are identical to conventional faithfulness in linear causal models. They require that when multiple causal paths exist from any (observed or unobserved) variable to its descendants, their combined effect (i.e., sum of products of path coefficients) is not equal to zero, see [24]. Assumptions 2(b) and 3(b) prevent certain path cancellation or parameter proportionality. Importantly, Assumptions and 3 are violated with probability zero if all model coefficients are drawn randomly and independently from continuous distributions; see Appendix B.3 for the proof. As an example for violation of Assumption 2(b), consider the linear SEM-ME generated by the graph in Figure 2(a), which satisfies Assumption 2(a). However, we can write Z4 as (b + 2) + NZ,, which is caused by the path cancellation of the triangle (Z,, Z3, Za). This means that that the causal effect of Z₁ and Zz on Z4 can be summarized by Ze alone. Therefore, the model violates Assumption 2(b). Lastly, Assumption 3 is strictly weaker than bottleneck faithfulness in [1]; see Appendix B B.4 for the proof. Please refer Appendix B for more discussion about our faithfulness assumption and Appendix D for a detailed comparison between our identifiability results and the results in [1].
4.2 Ancestral ordered grouping
Z
a
72
21
Z2
We first study the extent of identifiability of the models only under conventional faithfulness, i.e., Assumptions 2(a) and 3(a).
d
b+c
Zu
Z
Za
Za
Definition 4 (Ancestral ordered grouping (AOG)) The AOG of a SEM-ME (resp. SEM-UR) is partition of Z Y (resp. HU X) into distinct sets. This partition is described as follows: (I) Assign each nu-leaf node (resp. observed node) to a distinct group. (2) SEM-ME: For each u-leaf node Zj E Z, if there exists one parent V such that Zj has no other parents, or all other parents of Z, are also ancestors of V,, assign Zj the same group as Vz, Otherwise, assign Zy to a separate group (with no nu-leaf node). (2) SEM-UR: For each latent variable H;, if there exists one child X, such that H, has no other children, or all other children of H, are also descendants of X,, assign H, the same group as X². Otherwise, assign H, to a separate group (with no observed variable).
(a)
(b)
Z1
1
0
0
N2,
Z2
a
1
0
Nz,
Z3
ab
+ d
b
1
_Nz
aab
(bb+c)
b+c
Figure 2: Example explaining AOG and
SEM-ME faithfulness assumption.
Definition 5 (AOG equivalence class) The AOG equivalence class of linear SEM-ME (resp. SEM- UR) is a set of models where the elements of this set all have the same mixing matrix (up to permutation and scaling) and same ancestral ordered groups
For example, the two models represented by the graphs in Figure 2 have the same mixing matrix and ancestral ordered groups. The elements of an AOG equivalence class possess the following property.
Proposition 1 Models in the same AOG equivalence class have the same causal order among the groups, but not necessarily all the same edges across the groups.

---

The AOG characterization is a refined version of the original ordered grouping proposed in [29], where no variables in later groups cause variables in earlier groups. Yet, the grouping introduced in that work is order dependent and hence in general not unique. Moreover, it does not always characterize the extent of identifiability. Our AOG characterization also uses a similar idea as the learning approach in [19]; however, that work allows for latent variables which have parents and in general does not recover the full structure. Note that the AOG can be recovered based on the support of the mixing matrix under Assumption 2(a) (or 3(a)). Please refer to Appendix A for more details.
According to Definition 4, there is at most one nu-leaf node in each ancestral ordered group of a SEM-ME. Furthermore, each u- u-leaf node 2 is assigned to the ancestral ordered group of at most one of its parents: Following the true causal order among nu-leat nodes, only the last parent of Zz may have the same ancestor set. Hence, if group has more than one node, then there must be exactly one nu-leaf node, and the rest of the nodes are u-leaf nodes which are children of this node. This concludes that the induced structure on each ancestral ordered group is star graph. Similar property holds for SEM-UR. Define the center of the ancestral ordered group as the nu-leaf node (resp. the observed node), or the u-leaf node (resp. latent node) if the group is of size one. The following result illustrates that fixing the center of the ancestral ordered groups for SEM-ME, and fixing the exogenous noise term of the center of the ancestral ordered groups as well as the choice of scaling and permutation of the columns of B for SEM-UR, leads to unique identification of the models.
Proposition 2 (i) Models in an AOG equivalence class of a SEM-ME can be identified by the choice of the centers of the groups. That is, for a given choice of the centers, there is only one corresponding model. (ii) Models in an AOG equivalence class of a SEM-UR can be identified (up to the permulation and scaling of the columns of B in (4)) by the choice of the exogenous noise terms associated to the centers of the groups. That is. for a given assignment of the exogenous noise terms, all corresponding models have the same A in (4), and have the same B up to permutation and scaling of the columns.
Equipped with Proposition 2, we are now ready to state our identifiability results for SEM-ME and SEM-UR under Assumptions 2(a) and 3(a)). respectively.
Theorem 2 Under Assumptions 1 and 2(a) (resp. 3(a)), the linear SEM-ME (resp. SEM-UR) can be identified up to its AOG equivalence class.
Corollary (i) Denote the AOG of a linear SEM-ME (resp. SEM-UR) as {g(9) (g(9)))E(o)) where 9k is the number of ancestral ordered groups. The size of the AOG equivalence class, described in Theorem 2, is equal to [gelg.1 [g(9) [ (ii) Under Assumptions I and 2(a), a linear SEM-ME can be uniquely identified if and only if no u-leaf node has precisely the same ancestors as any nu-leaf node. (iii) Under Assumptions I and 3(a), a linear SEM-UR can be identified up to the permutation and scaling of the columns of B if and only if no latent variable has precisely the same descendants as any observed variable.
As stated in Theorem 2, in general, the edges across the groups cannot all be discovered and the centers of the groups (or their corresponding exogenous noise terms) are not identifiable. This is due to the fact that when only Assumption 2(a) holds, certain path cancellation or parameter proportionality in the model can occur. This is illustrated in the following example.
Example 2 Consider the SEM-ME generated by causal graph shown in Figure 2(a). The AOG is {[Z),, (2)), (73, 7. Because either 7:3 or Z4 can be the center of the last group, the AOG equivalence class includes the ground-truth and the model represented by Figure 2(b). Since both models have the same mixing matrix, identification algorithm merely based on the mixing matrix and Assumption 2(a) cannot distinguish these two models. Note that not only can we not learn the direction of the edge in group {Za, Za} }. but also the existence of some of the edge across groups, such as Z1- + Z4. cannot be established in the ground-truit because Assumption 2(b) is violated.
4.3 Identifiability of the model up to equivalence classes
Under Assumptions 1 and 2 (resp. 3), the extent of identifiability of SEM-ME (resp. SEM-UR) can be characterized by the direct ordered grouping defined in Definition 6 below. We first present two conditions that are used to implement the DOG. We then give the formal definition of DOG. In the following, we use Ch(V) to denote the set of children of variable V in the causal diagram.
Condition 1 (SEM-ME edge identifiability) For given edge from an ne-f node V, to u-leaf node Zr, at least one of the following two conditions is satisfied: (a) Pa(Zi) \ (V.) is not a subset of Pa(V.). That is, there exists another parent V; of Zu, which is not a parent of V. (b) Pa( Zz) is not subset of Eeveewn 2,) Pa(V)). That is, there exists a child Vy of V; and a parent V2 of Zi such that V, is not a parent of Vk-
7

---

Condition 2 (SEM-UR edge identifiability) For given edge from a latent variable Hi to an ob- served variable X., at least one of the following two conditions satisfied: (a) Ch(Hi) \ {X+} is not a subset of Ch(X;). That is, there exists another observed child Xj of Hi, which is not child of MHH.CHHHHHHCC...C... ())) That is, there exists an observed (or latent) parent X5 for Hg) of X, and a child X3 of H1 such that X3 is not child of Xx (or Hz).
x, (b) Ch((H) is not a subset Of MMH..
Figure 3(b) demonstrates an example of a graph structure which satisfies Assumption 2 while containing an edge which violates Condition Condition is an equivalent formulation of the conditions for unique identifiability derived in [29]. In that work, Zhang et al. proved that a linear SEM-ME can be uniquely recovered Condition is satisfied for every edge from an nu-leaf node to u-leef node.' 3 They also conjectured that this condition is necessary for identifiability. We prove their conjecture here under a slightly different faithfulness assumption. Furthermore, we demonstrate that the conditions can be used to characterize equivalence class of the models which characterizes the extent of identifiability under Assumptions and 2; the same assertion holds for linear SEM-UR. This characterization is done based on the notion of direct ordered grouping, defined as follows.
Definition 6 (Direct ordered grouping (DOG)) The DOG of a linear SEM-ME (resp. SEM-UR UR) is a partition of 2 U U (resp. H. U X) into distinct sets, This partition is described as follows:
(1) Assign each nu-leaf node (resp. observed node) to a distinct ordered group.
(2) SEM-ME: For each u-leaf node 7, E 2, if there exists one parent V; such that the edge from V;
to Z violates Condition 1, assign Z, to the same ordered group as V.. Otherwise, assign Z5 to
separate ordered group (with nu-leaf node).
(2) SEM-UR: For each latent variable H2, if there exists one child X5 such that the edge from H; to X; violates Condition 2, assign H, to the same ordered group as Xi. Otherwise, assign H2 to separate ordered group (with no observed variable).
Definition (DOG equivalence class) The DOG equivalence class of a linear SEM-ME (resp. SEM- UR) is set of models where the elements of this set all have the same mixing matrix (up to permutation and scaling) and same direct ordered groups.
For example, the two models represented by the graphs in Figure 2 have the same mixing matrix, but different direct ordered groups. We have the following property regarding elements of an DOG equivalence class.
Proposition 3 Models in the same DOG equivalence class have the same edges across the groups.
The counterpart of Proposition 2 holds for the case of direct ordered groups as well and avoid repeating it. Based on that counterpart, we have the following result regarding identifiability of linear SEM-ME and SEM-UR under Assumptions 2 and 3, respectively.
Theorem Under Assumptions 1 and (resp. 3). the linear SEM-ME (resp. SEM-UR) can be identified up to its DOG equivalence class.
Theorem 3 states that we can learn the structure among the groups, but the center of the group (or the noise term corresponding to it) will remain unidentified. Unlike the case of the AOG equivalence class, all the edges across the groups will be identified. That is, the choice of center does not change the edges across groups in DOG equivalence class, while it may change the edges in AOG equivalence class. Further, the sizes of the direct ordered groups are smaller than the sizes of the ancestral ordered groups As an example, for the model shown in Figure 2(b), all direct ordered groups are of size one.
Corollary 2 (i) The counterpart of Corollary I(i) is true for the case of DOG as well and we do not repeat it here. (ii) Under Assumptions and 2, a SEM-ME can be uniquely identified if and only for every edge from an nu-leaf node to a u-leaf node, Condition I is satisfied. (iii) Under Assumptions I and 3, a SEM-UR UR can be identified up to the permutation and scaling of the columns of B if and only for every edge from a latent variable to observed variable, Condition 2 is satisfied.
Identifiability of the structure of the SEM-UR. As shown in Theorem for a SEM-UR, the only undetermined part in the DOG equivalence class pertains to the assignment of the exogenous noises and coefficients, but the structure is the same. Consequently, if only the identification of the structure without weights is of interest, Assumptions and 3 are sufficient. See Figure 3(a) for an example of two DOG equivalent SEM-URs. This identifiability result is summarized in the following corollary.
Corollary Under Assumptions I and 3, the structure of a SEM-UR can be uniquely recovered.
Note that in their model, Zhang et al. assumed that all the underlying variables are unobserved.
8

---

4.4 Recovery algorithm
Nis
H
H
Nx
We note that our faithfulness assumption implies that the ground-truth model has strictly fewer edges than any model that has the same mixing matrix and satisfies conventional faithfulness (i.e., in the AOG equivalence class) but does not belong to the DOG equivalence class. This property can be leveraged to recover the ground- truth model or a member of its DOG equivalence class.
b
Nx X1
Nx2
Nu
X2 Nx2
X2
X1
a
a
(a) Equivalence class of a SEM-UR
Za
Z
Proposition 4 Suppose a SEM-ME (resp. SEM-UR) satisfies Assumptions I and 2 (resp. 3). Any model that belongs to the same AOG equivalence class but does not belong to the same DOG equivalence class has strictly more edges than any member in the DOG equivalence class.
b
1
b
Nz. Z
NZ. NE.
Nz,
Nz
a Z2
Z3
Z2
+ b
(b) Equivalence class of a SEM-ME
Figure 3: DOG Equivalence classes.
The steps of our recovery algorithm are as follows: (1)
Recover the mixing matrix W (resp. WUR) from observational data. (2) Return the AOG of the true model by comparing the support across different rows/columns in WMEE (resp. WU').. See Appendix A.2 for details and pseudo-code for AOG recovery. (3) For all possible choices of the center (resp. noise term associated to the center) of each ancestral ordered group, find choice that leads to the graph with fewest number of edges in the recovery output (see the proof of Lemma 1).
5 Simulations
We evaluated the performance of our recovery algorithm on randomly generated linear SEM-MEs and SEM-URs with different number of variables.* We considered two cases: (1) when noisy version of the mixing matrix is given, where the noise is Gaussian with different choices of variance denoted by d², and (2) when synthetic data comes from linear generating model with non-Gaussian noises with different sample sizes, and the mixing matrix needs to be estimated. We used the Reconstruction ICA algorithm [14] as our overcomplete ICA method. For Case (1), we compared our recovery method (which we refer to as DOG) with an approach based on AOG equivalence class (similar to the learning method in [19]). In addition to the AOG method, for Case (2). we compared our method [21]. Note that the ICA-LiNGAM method is not designed for systems with
with ICA- latent variables, but benefits from strong performance for recovering the mixing matrix in causally sufficient settings. The goal of this comparison was to demonstrate the necessity of using methods designed specifically to handle latent variables.
We compared the recovery of the adjacency matrix to the ground-truth, where we used normalized structural Hamming distance (SHD/Edge) and Fl score as our performance metrics. Our results for Cases (1) and (2) are shown in top and bottom two rows in Figure 4, respectively. As seen in these figures, our recovery algorithm outperforms recovery algorithm based on AOG. In particular, our method recovers the structure in SEM-UR model, and can recover part of the structure in SEM-ME that is shared among DOG equivalence classes. Moreover, both methods outperform ICA-LINGAM. Please refer to Appendix E for additional results and analysis.
6 Conclusion and Discussion
In real-world applications, we do not observe the exact value of all relevant variables; the measure- ments of some variables are prone to errors, or some other variables cannot be observed altogether. For example, in neuroscience and genomics, measured brain signals obtained by functional magnetic resonance imaging (fMRI) or the measured gene expression using RNA sequencing usually contain errors through the measurement process [18, 29]. Other examples include responses to psychometric questionnaires where the questions represent noisy views of various traits [1, 20], and returns in stock market, where they may be confounded by several unmeasured economic and political factors [1].
In this work, we considered the problem of causal discovery in setups with such challenges, par- ticularly under two settings: (1) in the presence of measurement error, and (2) with unobserved parentless causes. Unlike previous work, our proposed SEM-ME allows for applications containing a mixture of variables measured exactly (without error) or measured with error. We demonstrated mapping between these two models that preserves their mixing matrix. Based on this mapping, we derived identifiability results for both models under different faithfulness assumptions, and proposed *Our code is available at: https: httts:://githbb. www./omm//uuaa Saamm/uggin-aaa Baigiin-Yang/ll Yang/SEM MME ME- UR.

---

Case (1), ME
Case (1), UR(A&B)
Case (1), ME
Case (1), UR(A&B)
1.0
1.0
0.9
1.5
FI 5.core
0.9
0.8
SHD
0.5
1.0
0.7
0.8
0.6
0.7
0.0
10
20
10
20
10
20
10
20
Total Variables (p)
Variables +g++)
Total Variabi AOG, d=0 05
Total Variables (q
DOG, d=0.01
--- AOG, d=0.01
DOG, d=0.05
DOG, dm0 15
AOG, dm0.15
Case (2), ME
Case (2), UR(A)
Case (2), UR(B)
SHDD Edge
0.6
0.8
1.0
0.6
0.4
0.5
0.9
0.9
F1 Scoore
0.7
0.7
Observed Variables (p)
Observed Variab es (q]
Observed Variables (q)
DOG, N-500
DOG, N-200
AOG, N-500
AGG, N-200
LINAAM, N-500
LINGAM, N-200
Figure 4: Simulation results for Case (1), noisy mixing matrix (with noise variance d?), ). and Case (2), raw observational data (with sample size N-p for ME and N-q for UR). In Case (1), x-axis corresponds to } U Σ| in SEM-ME, and [ U X in SEM-UR. In Case (2), x-axis corresponds to І>/ U in SEM-ME, and |X in SEM-UR. We compare the recovery of both adjacency matrices and (cf. Equation (4)) for SEM-UR. Lower SHD/Edge value and higher F1 score indicate better performances.
structure learning algorithms. Our results further implied conditions for unique identifiability of the structure in SEM-UR. These conditions do not pose any restrictions on the graphical model, and hence significantly relax the existing graphical conditions in the literature [19, 1, 25, 4].
Our results have several implications in the literature of causal discovery including the following: The mapping proposed in our work between linear SEM-ME and SEM-UR allows us to translate identifiability results for one model to the other. We note that linear SEM-UR has been widely studied in the literature, while only few works considered linear SEM-ME. Therefore, an important implication of our work is that the introduced mapping can be utilized fill the gaps for the less studied model. Another important implication of our result is that it can be used for evaluating new algorithms: We showed that under two different faithfulness assumptions, the model can only be identified up to AOG and DOG equivalence classes. This result provides the extent of identifiability, and can serve as a basis for characterizing theoretical guarantees such as consistency of new algorithms. Finally, we showed in Proposition 4 that under our faithfulness assumptions, the true generating model is always sparser than any other model in the same AOG equivalence class (of the ground-truth) but does not belong to the DOG equivalence class. This serves as ground for positing sparsity assumptions that appear frequently in the literature without rigorous justification.
Similar to other causal discovery methods which are based on the mixing matrix, the performance of our proposed recovery algorithms relies on the accuracy the utilized mixing matrix estimation approach. Hence, the recovered structure should be interpreted with caution if the mixing matrix estimation approach is unreliable. Devising more accurate approaches for estimating the mixing matrix, as well as extending the method proposed in this work to non-linear models are important directions of future research.
A cknooweesssnnts and Disclosure of Funding
Negar Kiyavash's 'ss research was in part supported by the Swiss National Science Foundation under NCCR Automation, grant agreement 5 SANF40_180544 and Swiss SNF project 200021_204355 /1.
Kun Zhang was partially supported by NIH under Contract R01 HL 15999805, by the NSF-Convergence Accelerator Track-D award #21 134901, by grant from Apple Inc., and by a grant from KDDI Research Inc. Ilya Shpitser was supported by grants ONR N00014-21-1-2880 NSF 2040804, NSF
CAREER 1942239 and NIH R01 A1127271-01AI.
10

---

References
[1] Jeffrey Adams, Niels Hansen, and Kun Zhang. Identification of partially observed linear causal models: Graphical conditions for the non-gaussian and heterogeneous cases. Advances in Neural Information Processing Systems, 34, 2021.
[2] Merle Behr, Chris Holmes, Axel Munk, et al. Multiscalc blind source separation. The Annals of Statistics, 46(2):111774,, 2018.
[3] Ruichu Cai, Feng Xie, Clark Glymour, Zhifeng Hao, and Kun Zhang. Triad constraints for learning causal structure of latent variables. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[4] Wei Chen, Kun Zhang, Ruichu Cai, Biwei Huang, Joseph Ramsey, Zhifeng Hao, and Clark Glymour. Fritl: A hybrid method for causal discovery in the presence of latent confounders. arXiv preprint arXiv:2103.144 142.38888... 2021.
[5] Guilherme Duarte, Noam Finkelstein, Dean Knox, Jonathan Mummolo, and llya Shpitser. An automated approach to causal inference in discrete settings. arXiv preprint arXiv:2109.1344 2021.
[6] Bradley Efron and Robert J Tibshirani. An introduction to the bootstrap. CRC press, 1994.
[7] Jan Eriksson and Visa Koivunen. Identifiability, separability, and uniqueness of linear ICA models. JEEE signal processing letters, 11(7)6011 604, 2004.
[8] Robin J Evans. Graphs for margins of bayesian networks. Scandinavian Journal of Statistics, 43(3):225- 648, 2016.
[9] Robin J Evans. Margins of discrete bayesian networks. The Annals of Statistics, 46(6A))2623-2666 2018.
[10] Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based on graphical models. Frontiers genetics, 10:524, 2019.
[11] Yoni Halpem, Steven Homg, and David Sontag. Anchored discrete factor analysis. arXiv preprint arXiv:1511.03299 2015.
[12] Patrik O Hoyer. Shohei Shimizu, Antti J Kerminen, and Markus Palviainen. Estimation of causal effects using linear non-gaussian causal models with hidden variables. International Journal Approximate Reasoning, 49(2):362-377 -388, 2008
[13] Manabu Kuroki and Judea Pearl. Measurement bias and effect restoration in causal inference. Biometrika. 101(2):423-435 437, 2014.
[14] Quoc V Le, Alexandre Karpenko, Jiquan Ngiam, and Andrew Y Ng. Ica with reconstruction cost for efficient overcomplete feature learning. In Advances in neural information processing systems, pages 1017-1025, 2011.
[15] Chris Meek. Strong-completnnes and faithfulness in belief networks. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. Citeseer, 1995.
[16] Judea Pearl. Causality. Cambridge university press, 2009.
[17] Judea Pearl. On measurement bias in causal inference. arXiv preprint arXiv:100.33544, 2012.
[18] Basil Saeed, Anastasiya Belyaeva, Yuhao Wang, and Caroline Uhler. Anchored causal inference in the presence of measurement error. In Conference uncertainty in artificial intelligence, pages 619-628. PMIRR, 2020.
[19] Saber Salchkaleybar, AmirEmad Ghassami, Negar Kiyavash, and Kun Zhang. Learning linear non- gaussian causal models in the presence of latent variables. Journal of Machine Learning Research, 21(39): 1-24, 2020.
[20] Richard Scheines and Joseph Ramsey. Measurement error and causal discovery. In CEUR workshop proceedings, volume 1792, page 1. NIH Public Access, 2016.
[21] Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen. and Anti Kerminen. A linear non- gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(ct))2003-2030, 2006.
[22] Shohei Shimizu, Takanori Inazumi, Yasuhiro Sogawa, Aapo Hyvärinen, Yoshinobu Kawahara, Takashi Washio, Patrik O Hoyer, and Kenneth Bollen. DirectLiNGAM: A direct method for learning a linear non gaussian structural equation model. Journal of Machine Learning Research, 12(Apr):1225- 2.11.

---

[23] R. Silva, R. Scheines, C. Glymour, and P. Spirtes, Learning the structure of linear latent variable models. Journal of Machine Learning Research, 7:191-246, 2006.
[24] Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, prediction, and search. MIT press, 2000.
[25] Y Samuel Wang and Mathias Drton. Causal discovery with unobserved confounding and non-gaussian data, arXiv preprint ar arXiv:2007.11133 2020.
[26] F. Xie, R. Cai, B. Huang, C. Glymour, Z. Hao, and K. Zhang. Generalized independent noise condition for estimating linear non-gaussian latent variable causal graphs. In Neural Information Processing Systems (NeurIPS), 2020.
[27] Feng Xie, Biwei Huang. Zhengming Chen, Yangbo He, Zhi Geng, and Kun Zhang. Identification of linear non-Gaussian latent hicrarchical structure. In Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 24387-24387. PMLR, 17-23 Jul 2022.
[28] Yuqin Yang, Mohamed Nafea, AmirEmad Ghassami, and Negar Kiyavash. Causal discovery in linear structural causal models with deterministic relations. In First Conference on Causal Learning and Reasoning, 2022.
[29] Kun Zhang, Mingming Gong, Joseph D Ramsey, Kayhan Batmanghelich, Peter Spirtes, and Clark Glymour. Causal discovery with linear non-gaussian models under measurement error: Structural identifiability results. UAL pages 1062-1072, 2018.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Please refer to Section 6.
(c) Did you discuss any potential negative socictal impacts your work? [No] We believe that causal structure learning from observational data avoids potential negative socictal impacts in causal discovery that might be associated with conducting randomized experiments.
(d) Have you read the cthics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Assumptions and 2 (resp. 3) are our identifiability assumptions for linear SEM-ME (resp. SEM-UR).
(b) Did you include complete proofs of all theoretical results? [Yes] Please refer to Appendix C.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] Please refer to Appendix for instructions. Our code is available at: https://ee //gittubb
Yutinn (b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)?
ME- UR.
[Yes] This is explained in detail in Appendix E.
(c) Did you report eтror hars (c.g., with respect to the random seed after running experiments multiple times)? [Yes] Please refer to Appendix E.4.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [No] Simulations are conducted using the CPU of MacBook laptop.
4. If you are using existing assets (e.g.. code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cited the original paper of the haseline algorithm.
(b) Did you mention the license of the assets? [N/A] Our simulations conducted synthetic
data only.
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did discuss whether and how consent was obtained from people whose data you 're using/cu- rating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable informa- tion or offensive content? [N/A]
12

---

5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include full text of instructions given to participants and screenshols, if applicable?
[N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(C) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "p5Iq_Gf09g2", "reviewer": "Reviewer_WQ2G", "summary": "The authors study causal discovery of linear models in the presence of measurement errors and unobserved confounders, for the situation where the mixing matrix can be identified up to column scaling and permutation. They show that there is a one-to-many relationship between models subject to measurement error and models with unobserved parentless causes. Given this mapping, they analyze the identifiability of both models and propose additional faithfulness assumptions for the two classes of models leading to identifiable structures, and in some cases, to identifiable parameters. Finally, they define graphical partitions (ordered groupings) that are invariant for the identified models.", "questions": "On page 7, line 300, why does the structure defined in Definition 4 lead to a star graph? This does not seem immediately obvious to me and perhaps should be explained in a few sentences. I would also briefly describe what a star graph is.\n\nHow many simulations were performed in Figure 4? If the experiments were replicated multiple times, as they should be, then why are there no confidence bars reported?", "limitations": "The authors have not discussed any potential negative societal impacts of their work, which can be excused for such a highly theoretical work. I concur with the authors' claim that causal structure learning from observational data is less prone to these impacts than randomized experiments.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The analogy between linear causal models in the presence of measurement error and linear causal models with (top-level) latent variables is, to best of my knowledge, novel and constitutes an interesting perspective on causal discovery without causal sufficiency. The technical quality of the paper is high, the text is clearly written for the most part, and the results seem to bridge an important gap in the causal discovery literature. The simulation section is brief, but comprehensive enough.\n\nOn the negative side, confidence bars are missing from the simulation results in Figure 4, even though the authors mention in the checklist that they have been reported. The figure is a bit hard to read, and some minor writing errors hinder clarity.\n\nMinor comments:\n- p1 (page 1), l34 (line 34): \"application\" $\\to$ 'applications'\n- p1, l56: \"casual\" $\\to$ 'causal'\n- p3, l95: \"latter\" $\\to$ 'later', to be consistent with p6, l289 \n- p6, l263: \"passes\" $\\to$ 'pass'\n- p7, l341: \"exist\" $\\to$ 'exists'\n- p8, l356: \"parent\" $\\to$ 'parents'\n- p8, l359: \"child\" $\\to$ 'children'\n- p8, l371: \"the edge in\" $\\to$ 'edges in the'\n- p8, l372: \"are\" $\\to$ 'is'\n- p8, l373: \"group\" $\\to$ 'groups'\n- p9, l409: add 'the' before \"Reconstruction\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dVoWyGEocTj", "reviewer": "Reviewer_C5rx", "summary": "The paper shows a correspondence between linear SEMs with measurement error and linear SEMs with hidden variables.\n\nThe paper then characterizes the equivalence class for these cases which can be learned when variables are linear and non-Gaussian under two faithfulness assumptions.\n\nA recovery algorithm is provided along with simulation results, which is shown to outperform LiNGAM.", "questions": "What is the primary impact of these results on causal discovery broadly?\n\nWhat are some applications that these results contribute to?", "limitations": "Some discussion of limitations.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- Rigorous theoretical results that contribute to the literature on identifiability of linear non-Gaussian models\n- Very detailed and generally well written paper\n\nWeaknesses\n- Very limited discussion of motivation and impact of the work\n- Limited empirical results and extremely limited discussion of empirical results", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "X0Yb616lsH5", "reviewer": "Reviewer_KoAc", "summary": "The article studies causal discovery in linear systems where some of the variables are observed with measurement error. The identification is based on the mixing matrix (which maps independent exogenous noise to the observations). The article first shows that the model with measurement error is equivalent to a linear latent variable model where the latent variables don't have any parents, so any identifiability results based on the mixing matrix are applicable to both cases (Thm 1).\n\nThm 2 states that under the regular faithfulness assumption the models can be identified up to an equivalence class consisting of systems with the same ancestral ordered grouping (AOG), but the edges between the groups can't be identified. Then the article presents an additional condition (Condition 1) such that iff every edge from a non-leaf node satisfies the condition, then even the edges between the groups can be identified, in other words, the system can be identified up to the Directed Ordered Grouping (DOG).\n\nFurthermore, the assumptions imply that any ground-truth generating model has fewer edges than any model that has the same mixing matrix but does not belong to the same DOG as the true model. This insight can be used to devise an algorithm for structure recovery: 1) find mixing matrix, 2) find AOG of the true model, 3) find the center for each group that leads to the graph with fewest edges.\n\nA simple simulation study shows that using the algorithm with DOG identifies the correct model better than recovery based on just AOG or another published baseline: ICA-LiNGAM.\n", "questions": "Figure 4 could benefit from additional annotation of the rows/columns and a more detailed caption.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts:\n\nThe presentation is clear for this kind of work that is somewhat heavy on technical detail. All the math is presented accurately (though I only glanced through the supplement) and the theorems are associated with illustrative figures and examples that demonstrate the concepts in concrete setups.\n\nThe main novelty are the theoretical results connecting the two types of graphs as well as the new results on identifiability that are stronger than the previous ones. I find these results original and significant in the sub-field machine learning studying causal identifiability with latent variable models.\n\nWeaknesses: \n\nThere are no major weaknesses. Some real-world example would have strengthened the paper further, but that might not be necessary in this kind of paper where the main contribution are the new theoretical results.\n\nOne major assumption for identifiability is that the noise terms are non-Gaussian. Whereas this might be true in many real-world situations, it is equally true that Gaussian noise is the default assumption in the majority of applications. Hence, the assumption may be limiting.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept