Identification of Partially Observed Linear Causal Models: Graphical Conditions for the Non-Gaussian and Heterogeneous Cases
Authors: Jeffrey Adams
Niels Richard Hansen
Kun Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Causal Discovery
Structural Equation Models
Latent Variable Modeling

Abstract: In causal discovery, linear non-Gaussian acyclic models (LiNGAMs) have been studied extensively. While the causally sufficient case is well understood, in many real problems the observed variables are not causally related. Rather, they are generated by latent variables, such as confounders and mediators, which may themselves be causally related. Existing results on the identification of the causal structure among the latent variables often require very strong graphical assumptions. In this paper, we consider partially observed linear models with either non-Gaussian or heterogeneous errors. In that case we give two graphical conditions which are necessary for identification of the causal structure. These conditions are closely related to sparsity of the causal edges. Together with one additional condition on the coefficients, which holds generically for any graph, the two graphical conditions are also sufficient for identifiability. These new conditions can be satisfied even when there is a large number of latent variables. We demonstrate the validity of our results on synthetic data.

Identification of Partially Observed Linear Causal Models: Graphical Conditions for the Non-Gaussian and Heterogeneous Cases
Jeffrey Adams Niels Richard Hansen'. Kun Zhang
Department of Mathematical Sciences, University of Copenhagen, Denmark Department of Philosophy, Carnegie Mellon University, Pittsburgh, USA ja@math. taatt.....dee dk, niels. hansen@math. du. kunz1@cmu.eet edu
Abstract
In causal discovery, linear non-Gaussian acyclic models (LiNGAMs) have been studied extensively. While the causally sufficient case well understood, in many real applications the observed variables not causally related. Rather, they generated by latent variables, such as confounders and mediators, which may themselves be causally related. Existing results the identification of the causal structure among the latent variables often require very strong graphical assumptions. In this paper, we consider partially observed linear models with either non-Gaussian or heterogeneous errors. In that case we give two graphical conditions which are necessary for identification of the causal structure. These conditions are closely related to sparsity of the causal edges. Together with one additional condition on the coefficients, which holds generically for any graph, the two graphical conditions are also sufficient for identifiability. These new conditions can be satisfied even when the number of latent variables is very large. We demonstrate the validity of our results on synthetic data.
Introduction
In the standard causal discovery problem. we are given non-experimental data and aim to learn the direct causal relations between the observed variables [1, 2]. But many applications. we do not believe that all causal variables relevant to the observed system have been measured. While some of the observed variables may interact directly, others might interact indirectly via latent mediators, and still others could be generated by latent common causes; indeed, any pair of observed variables may stand all three relations at once. Further, the relevant latent variables may be causally related themselves. For example, responses to psychometric questionnaires are usually thought of as noisy views of various traits, and the researcher is predominately interested these hidden traits and their hierarchical structure. Similarly, in financial markets, stock returns may be causally related, but may also be confounded or mediated by a complicated network of unmeasured economic and political factors.
causal relations between
natural ask what conditions are both necessary and sufficient for the identification of such partially observed causal structures from observational data. Various sufficient conditions have been proposed; however, these conditions are rather restrictive, and are not in general necessary for identification of the full causal structure.
TThe work presented in this article started while JA was at CMU.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this work, we consider the case of linear causal models in which the overcomplete mixing matrix from the noise terms to the measured variables is identifiable up to permutation and scaling of columns. This is possible, for example, in the case of independent non-Gaussian noise [3], or when given access to heterogeneous domains in which the variances of the noise terms change independently across domains but the causal graph and weights remain constant (see Theorem 1 of our paper). We provide necessary and sufficient conditions under which the latent causal structure can be uniquely identified up to trivial indeterminicies.
2 Problem setup
Suppose some causal variables V (Vi.-.., V2}} follow a linear structural equation model (SEM)
FV +
(1)
where V := (V1, VT) is vector of causal variables, F is a causal adjacency matrix that can be permuted (by simultaneous row and column permutations) to strictly lower-triangular form, and = (E1,..... ,,) is vector of independent noise variables. In this paper we consider two settings for E,: 1) all E, are mutually independent and non- Gaussian, or 2) there are multiple domains, E, are uncorrelated within each domain, and their variances change independently across domains. We will make the second assumption technically precise Section
We seek necessary and jointly sufficient conditions for identifiability of F (up to trivial indetermina- cies) in the case where only some subset of (which we call X)) is measured. Thus F may encode deserved-observee interactions, latent confounding, latent-latent interactions, and latent mediation or intermediate confounding. Our results identify F from the equivalence class M, as defined in Section 2.2, of mixing matrices induced by (I). This equivalence class M is identifiable if, for example, the errors are non-Gaussian or their distribution changes over time or between domains.
2.1 Notation
For any matrix A and index sets J and K, we write A& to denote the submatrix of A with columns indexed by ./ and rows indexed by K. Observe that A = AI Thus, F describes the direct effect of {V3 j E J} on (Vx k E K}. (Remember: causes up-stream of their effects.)
The graph induced by (1) has edges V; + V3 whenever Fj * O. We write Pa(V)) (V, V; < V2} and Ch(VV) := (V, V; - Vj}. respectively, to denote the parents and children of V.. We say that (Vi..... V&) constitutes directed path from V12 to V&8 if V,
Vi+1 for every i E {1.... Trivially, for every Vi. (V)) is a directed path from V/2 to itself; we say that directed graph is acyelic (a DAG) if (V,) is the only such path. We write Ano(V. == (V, E V Vj has directed path to V.} and Desc( (V.) = {V; V, has a directed path to VjJ. respectively. to denote the ancestors and descendants of Vg For DAGs, notice that Anc Vi) n Desc(V.) = (V.). but VG & Pa(V,) Ch(V)).
1}.
We assume that only some subset X' V Vss is observed, with the remaining C = V - X being latent. We use to denote generic variable, observed or latent, while X; E X denotes an observed variable and Lj E L denotes a latent variable. When it is clear from context, we occasionally suppress the distinction between a variable Vú2 and its index i.
2.2 Identification and minimality
Since F induces a DAG, we can always solve (1) to express the causal variables in terms of the independent noise terms:
V = Mc,
(2)
where
M = FI-
(3)
is the mixing matrix with Mj being the net effect of e on Vy. This net effect is calculated by multiplying causal weights along paths and summing across paths. Notice that M; * then V, E Deso(V,). (V,).
Because L is hidden, let us explicitly write X in terms of e:
X = Mye.
(4)

---

In both the non-Gannee Gaussian and heterogeneous settings we consider in this paper, M, is identifiable up to permutation and scaling of columns; that is, we can identify the equivalence class
M [MxDP: DP E DPp)
(5)
where
p= (DP E RPXP: D is full rank diagonal and P is a permutation matrix).
We argue this for both settings individually in Section 3.
We say that an adjacency matrix F generates M if (I (I-F) E M. Of course, in partially observed systems, the adjacency matrix that generates M is not unique. However, some of these matrices sparser than others. In causal discovery, as in model selection more broadly, we tend to prefer the "simplest" model that adequately fits the data [4, 5J. As result, without prior knowledge. partially observed linear causal model cannot be identified if the population distribution can be written in terms of an equally sparse or sparser model; after all, we would never select complicated model if a simpler model fits just as well. It is therefore natural to recast the question of identifiability to question of maximal sparsity.
Let the Eo "norm" of a matrix || llo denote the number of non-zero entries in that matrix. Then we say that a causal adjacency matrix F is minimal with respect to .M if F generates M and ||]|oo 2 ||llo for any F + F that generates M.
Let denote the class of minimal adjacency matrices that generate M. Clearly, since M is identifiable, so is F. We say that an adjacency matrix F is identified up to trivialities if
F (DP)-'FDP FDP: DP E DPp with (DP) =1].
(6)
The only indeterminacy remaining in F amounts to re-indexing and re- re-scaling the latent factors.
word of caution is in order. Because the adjacency matrix that generates M is not unique in the partially observed case, it is only possible to talk about identification with respect to some selection principle. Throughout this work we use minimality as such a selection principle - indeed we define identification in terms of it. As justification, in Section 5.1, we describe one class of non-minimal adjacency matrices which are pathological and whose exclusion is desirable; further, in Section 6, we show that existing works make assumptions even stronger than minimality; further still, in Section 7, we show that popular model selection criteria like BIC favor minimal graphs. Nevertheless, just as BIC is not always the most sensible criterion for model selection, so minimality is not always the most sensible principle for an identification theory. For example, Figure shows a non-minimal graph which is not pathological. Thus, if practitioner believes the true partially observed causal model to be non- non-minimal, they should content themselves with partial identification (c.F. [6]).
In Sections 4 and 5, we express identification up to trivialities in terms of two local graphical conditions, which are much easier check than (6). But first, we return to the identifiability of M.
3 Sufficient conditions for identification of M
The main results of Sections 4 and 5 rely on the identifiability of M, which is theoretically guaranteed in the two settings we consider in this paper. In the first setting, E; are assumed to be independent and non-Gaussian. Then according to Theorem 3 by Eriksson and Koivunen [7], M is identifiable from the distribution of X. The task of estimating M from X known as Overcomplete Independent Component Analysis (OICA) [3], and in practice this task is known to be computationally difficult [8]. In the second setting, S; are uncorrelated from each other with changing variances across multiple domains (or over time) and Mx has full row rank (which is always the case for acyclic models). Note that in this setting, while the components of are mutually independent within each domain, they are not necessarily mutually independent across domains because their variances may be dependent across domains. This setting is expected to apply to a number of nonstationary scenarios including brain signal analysis, and the following theorem establishes the corresponding identifibiality of M. Besides complementing Theorem 3 of Eriksson and Koivunen [7] an alternative foundation for our identification work, the identifiability of M this setting may be of independent interest in the fields of blind source separation and system identification.
3

---

Theorem 1. Suppose we have observed X generated according to the mixing procedure (4) in number of domains. t 1. I, where Mx has full row rank. Assume that E, are uncorrelated in each domain and that their variances in domain I, denoted by oy change independently across domains the sense that S, whose (1,, 8)-th entry is of has full column rank. Further assume that each {x columns of Mxx are linearly independent and that S 2 2. Then if X admits a model X Mxε, where & also follows the above assumption E. then every column of Mx must be proportional to a column of Mx and vice versa.
Note that this theorem gives sufficient conditions for the identifiability of M: our empirical results suggest that they are not necessary.
4 Necessary conditions for identification of F up to trivialities
In this section, we introduce our identification conditions and show that they are necessary for F to be identified up to trivialities. The identification conditions are graphical conditions described in terms of "bottlenecks" and "redundancies."
Let J. K, and B be subsets of the nodes of a directed graph. Note that they need not be mutually disjoint. We say that B is bottleneck from J to K if, for every j E J and every k K, each directed path from j to k includes some E B. A bottleneck B from J to K will be called minimal if every bottleneck B' from J to K has B [B), and unique minimal if the inequality is striet for B' * B. Note that bottlenecks do not in general d-separate and K' along all paths, but only directed paths from J K.
clear from the definition that, for each V., Ch(V;) a bottleneck from Ch((V) to X. However, for identification, further require:
Condition 1 (Bottleneck). For every V, Ch(V,) is the unique minimal bottleneck from Ch(V,) to X.
As illustrated in Figure 1, the bottleneck condition ensures that if we try "explain" the net effect of V; on X' by replacing Ch(V,) with any subset of Desc(V), the result is a denser graph. As illustrated in Figure 3, the strong non-redundancy condition will further ensure that we cannot "explain" the effect of V, on Ch(V)) via some of its non-descendants:
Condition 2 (Strong Non-Redundancy). For all Li, Vj. if CL()) S Ch(V)) U (V}) then L; = Vj-
Figure 2 shows graph that satisfies both of these conditions. To build intuition, let us list some simple consequences of these conditions. By the bottleneck condition, each variable must have fewer than | children; but if variable has latent children, then the bottleneck condition is satisfied trivially for that variable. By strong non-redundancy, each latent variable must have at least two children. For any pair (L,, Vj), if L; an ancestor but not parent of Vj, has more than one directed path to V,, then strong non-redundancy is satisfied for that pair. If V2 is parent of L; and they violate strong renunddund,,,,, then the bottleneck condition is violated for Vj-
Theorem 2. F is identified up trivialities, then the graph induced by F satisfies the bottleneck and strong non-redundancy conditions.
L
Figure 1: An egregious violation of the bottleneck condition. Left: {V2, Va} is strictly smaller bottleneck from Ch( V1) X. Right: a sparser yet observationally equivalent graph. Although both graphs also violate strong non-redundancy, egregious bottleneck violations are not always redundant.
Figure simple graph illustrating our structural conditions. L1 satisfies the bottleneck condition. L.2 and La are non-redundant as each has a child the other does not. X, and Lg are non- redundant as L3 + X, and X & L.

---

Thus the bottleneck and strong roduredundyncy conditions are necessary for identification of F up to trivialities. In Section we further show that they (along with a very mild constraint on the causal weights) are also jointly sufficient conditions.
If Ch(V)) is not least minimal bottleneck for every V,, then F き F. Figure shows example of such violation of the bottleneck condition. Otherwise, as long as bottleneck faithfulness is also satisfied, F is an equivalence class of equally sparse latent structures which all violate least one of the bottleneck and strong non-redundancy conditions. The nature of these indeterminacies is depicted in Figure 3. In Figure we show a simple yet illustrative example in which both conditions are satisfied.
(a)
(h)
(d)
Figure 3: Two equivalence classes, (a) and (b) are equivalent, the former violating the bottleneck condition (A' * Ch(L,) is minimal bottleneck from Ch(L,) to X) and the latter strong non- redundancy (Ch(T2) S Ch(Lz)). (c) and (d) are equivalent, both violating strong non-redundancy.
5 Sufficient conditions for identification of F up to trivialities
In the previous section, we introduced two structural conditions which must be satisfied for F to be identifiable up trivialities. In this section, we prove that they (along with "bottleneck faithfulness," a very mild constraint on the causal weights) are also jointly sufficient. Throughout, we assume that X is generated according to (I). In particular, we assume that M is identifiable, for example due to Theorem of Eriksson and Koivunen [7] or Theorem of the present work.
5.1 Bottleneck faithfulness
First, connect ranks of submatrices of M to minimal bottlenecks of its corresponding graph. Proposition 1. Let be a minimal bottleneck from J to K. Then Rank(M - [B.
Strict inequality in Proposition 1 for some minimal bottleneck B from J to K can make F non- identifiable even the bottleneck condition and strong non-redundancy hold. For instance, both graphical conditions hold for
0
-17
2
2
0
X
L+Ex,
L == EL.
3
[4
0
but Rank(M = 2 while the minimal bottleneck from X' is with [C] =3. The system
0 1
0 0 0
2
X
L + EX;
L
1 0
0
L
0
3
0
1
0
generates the same mixing matrix, M,,, but has a strictly sparser graph. Thus to ensure identifiability, assume that the causal coefficients satisfy:
Condition 3 (Bottleneck Faithfulness). For every J JCV, C B is a minimal bottleneck from K, then Rank (M&) BB.
In the supplementary material we characterize the set of adjacency matrices F that are bottleneck faithful for a given graph. In particular, show that generic F is bottleneck faithful.
Interestingly, in linear systems, classical faithfulness is special case of bottleneck faithfulness. Rank(M k 0 is violation of classical faithfulness if there is minimal bottleneck B * Ø from
5

---

to K. That is, if there is a path from J to K but the path coefficients cancel out so that the net effect of J on K the system is not faithful the graph. Bottleneck faithfulness generalizes this so that the net effect of J on K must have maximal rank for the given graph.
5.2 Identifiability
In this subsection, we show that if the bottleneck condition, strong non-redundancy. and bottleneck faithfulness hold for F, then F is identifiable up trivialities. Throughout, we assume the three conditions hold.
Our approach is illustrated by the following computation. For any Vi.
Mx F)' I
Let = Ch(V)) Since the support of F is J. the equation
(M (M- 1)xx M
always has a solution at x Fj. fact, (under the three assumptions of this section) this solution is unique:
Lemma 1. Let J = Ch(Vi). Then the unique solution to (8) is given by
F Cl((V)))
But there is a version of (8) each J C V. For which other choices of does (8) have solution? Clearly solution always exists if J Ch(V).. On the other hand, we can guarantee that solution with [J] & [Ch(Vi) is only possible if J contains an ancestor of Vi:
Lemma 2. Suppose J C V Anc(V)) If (M - 1) E Range (M&). then |J| 2 [Ch(Vi)), with equality if and only if J = Ch(V)).
By Lemma 2, if any superset of (V;) containing no ancestors of V, identifiable, then Ch(V;) also identifiable. Next, we will show how such superset of Ch(V)) can be identified.
Let V& S denote the variables whose longest path X' has fewer than & nodes. More formally, define recursively
Vo Ø VK+1 == (V. EV: Ch(V.) C Vil, for 2
(10)
Naturally, we define X := V& N and L. == V& n. Notice that V4 is strictly increasing, and is induced by the topological ordering V.
Proposition 2. For all k; either Vk C Ve+1, or Vi = V.
Further, for each A 2 0, define
Jk+1 (V:) =
arg min JCV eRange (M²,)
[/].
(11)
Intuitively, this denotes the set of minimal choices for J C V4 such that (8) has a solution. From Lemma 2, we know that Jk+1 (V)) (Ch(V)) V; E V Vx. The construction of (11) allows us to generalize Lemma 2 to describe which versions of (8) have solutions when we are not sure of the causal order.
Lemma 3. For every k 2 Vs and (V:) be defined as above. Then V, Va+1 V4 if and only if all of the following hold:
1. Vi & Vki
2. Support(MMz Xal 5 1;
3. Jh++1 (V:)l and
4. for all V, + satisfying points and 2, My & Range (M4)(())

---

As a result of Lemma 3. each V% is identifiable. Clearly, if V; E VK+1, then Ch(V)) E VA and Vi n Anc(V,) Ø. Hence by Lemma 2, Ch(V;) is also identifiable Thus the full DAG is identifiable, and each column of Mxx can be associated with the corresponding node in the DAG. However, Lemmas 1, 2, and 3 are not enough to distinguish which nodes correspond latent variables and which correspond to observed variables; we have yet to pair each X, with its net effects M Resolving this final indeterminacy is not hard, Intuitively, the vector of Mxx corresponding to X; must have non-zero coefficients in the i-th slot while every vector corresponding to descendants of X; will not. Lemma 4 formalizes this observation.
Lemma 4. X; E x 1 if and only if X; E V4+1 and Support (M Xx = {t).
Together, Lemmas 1, 2, 3, and 4 imply that F is identifiable if Mxx is identifiable. Of course, we do not know - M. Nevertheless, Lemmas 2, 3, and do not involve the scaling and permutation of shows that Lemma can be used to put any MD E M in one-to-one correspondence with (PD)--I(PP))
the linear dependencies of its columns. Some simple calculation
Theorem 3. Suppose F satisfies generalized non non-redundaney faitifuuesss,, and the bottle- neck condition. Then is identifiable up to indeterminacies.
6 Relation to existing work
Constraint- and score-based approaches to causal discovery based on conditional independence testing-such as SGS [1]. IC [2], PC [9]. GES [10], and FGS [lie-gcnyyllyy focus the causally sufficient case. These algorithms identify the Markov equivalence class of graphs which all encode the same set of conditional independence relations. While some methods based on conditional inde- pendence tests, such as FCI [12] and RFCI [13], are able to relax the assumption of causal sufficiency, their focus is on learning the causal relations between observed variables and distinguishing them from spurious dependencies induced by shared latent ancestors. Such methods recover only limited information about the latent structure, as only the most basic information about latent structure is identifiable from conditional independence relations alone. For one review of causal discovery methods, see Spirtes and Zhang [14].
is possible to go beyond the equivalence class with additional assumptions on causal mechanisms [14]. In particular, linear non-Gaussian models have been studied extensively. In the causally sufficient case, Shimizu et al. [15] leverages acyclicity of the causal relations and the identifiability of the square ICA problem [16, 17] to show how the causal adjacency matrix can be identified, while Lacerda et al. [18] further estimate a subclass of cyclic causal models. In both cases, one may replace the -an-Gaasiian noise assumption with the heterogeneous noise assumption (in the formal sense of Theorem 1) and the identifiability results still hold [19].
By contrast, previous works on partially observed linear non-Gaussian models only study certain special cases in which the models are partially identifiable. Hoyer et al. [20] describe a procedure to convert partially observed causal models to canonical form in which no latent variable has any parents. They further provide an algorithm which recovers all canonical forms consistent with the observed overcomplete basis M, which is identifiable by OICA [3]. This recovered equivalence class of observationally equivalent canonical forms can be huge, and by definition can neither identify causal relations among latent confounders nor distinguish latent confounders from latent mediators.
More recently, Lemma 5 of Salehkaleybar et al. [6] states that if M is identifiable, then the causal order among observed variables is identifiable if classical faithfulness holds between all variables. Their condition is strictly weaker than ours; as we discuss in Section 5. classical faithfulness is entailed by bottleneck faithfulness and imposes graphical conditions. That a weaker condition suffices for their task is not surprising, since their task is strictly easier than ours; if F is identified up to trivialities then the causal order among observed variables is also identified (while the causal order alone tells very little about F). Lemma has a reassuring consequence for our work: even the graphical conditions for total identification fail to apply, the causal order of X' is still identified.
If the practitioner is further interested the observed variables' net effects on one another, (M- - then additional graphical assumptions are needed. Theorem 16 of Salehkaleybar et al. [6] provides one condition sufficient for this purpose: no latent variable T., has precisely the same observed descendants as any observed variable X, (formally, for all L,, X,. Desc(L.) n X' of Desc(X,) n.))).. X)).
7

---

Again, this being relatively easy subtask of the problem we consider, it is not surprising that our conditions are not strictly weaker. With that said, our conditions are not strictly stronger, either; the bottleneck and strong non-redundancy conditions can be satisfied even when I;; and X, have the same observed descendants, as shown in Figure 4.
X2
X3
Figure 4: Examples of graphs identifiable from M. From left to right: a graph where Desc L) nX' Deso( (e) 1) O X'; widening hierarchical structure; a hierarchical structure with intra-layer relations.
To recover causal structures of the hidden variables, many results rely on strong assumptions about clusters of pure variables (sets of observed variables which each share a latent confounder and have no other parents). For example, Spearman's 's classical Tetrad condition [21] identifies latent causes with four pure observed children from covariance information alone. In the linear non-Gaussian case, existing work reduces the number of pure observed children to three [22], and more recently two [23, 24]. Clearly, these are all special cases of both the bottleneck and non ron-edduny conditions. As such, our graphical assumptions are strictly weaker.
Proposition 3. Suppose each Li in a partially observed DAG has at least two pure children (latent or observed). Then the DAG satisfies the bottleneck and non non-redundancy conditions.
However, identification is possible even when no latent confounder has any pure children; for example, Anandkumar al. [25] present model in which latent variables with pure children identifiable. Rather than purity, they require a graph expansion property-for all non-singleton S C L. UULes Ch(L)) 2 d where d'aax max,
-as as well as rank condition on F& which places hard-to-check graphical constraints on the model and bounds |C] I 1 redundancy among latent variables can be derived from the expansion property by considering the case where [S] = 2. and the bottleneck condition by considering S = [Li} U Ch(L,) C. Thus be seen as a refinement on the expansion property: however, also remove the many hard-to-check graphical consequences of the rank condition, and further show that many graphs even with [4] >> | are identifiable. For example, Figure 4 shows identifiable hierarchical model in which the number of latent variables increases with depth. Moreover, we show that our conditions are sufficient for identifying hierarchical structures in which variables in the same layer are causally related. Figure 4 shows one such system.
3 | Non-
in sense, our conditions
Proposition 4. Suppose F satisfies the rank and graph expansion conditions of Anandkumar et al. [25]. Then F also satisfies the bottleneck and strong non-redundancy conditions.
Propositions and 4 show that our conditions are indeed more general than previous identification conditions; not only do our conditions allow and identily causal relations among observed variables, they also identify latent structures which no previous works could. (See, for example, Figure 4.) Furthermore, in light of Theorems 2 and 3, they show that many existing works implicitly took sparsity of causal edges as useful primitive for what means for partially observed causal model to be identifiable. Such a primitive is widely used throughout causal discovery, even in the causally sufficient case [4, 5].
Although many of these conditions for latent structure identification rely on non-Gaussian independent noise, direct estimation of the mixing matrix is often avoided in practice, especially in the causally insufficient case, as estimation of the overcomplete mixing matrix is computationally challenging [8]. Estimation of the mixing matrix can be avoided by directly using the independent additive noise assumption and exploiting graphical conditions such as causal sufficiency or purity. For example, in the causally sufficient case, Pa(X,) is identifiable by regressing X, on C X' and testing the independence of the regression residuals and Z [26]. This approach may be adapted to the non-linear (27, 28] and post-nonlinear [29] cases. Tashiro et al. [30] extend this idea to identify causal relations among observed variables in the causally insufficient case, and a related condition is developed by Xie et al. [24] to identify one special type of confounder. However, such methods owe their efficiency to the strong structural conditions under which they guarantee identifiability. As the bottleneck
8

---

and non-redunyancy conditions are much more general, this naturally complicates the question of estimation.
Estimation
In Theorems 1 and 3, have shown that causal system which satisfies the conditions of Section 4 is uniquely identifiable whenever Mx is identifiable. However, as indicated Section 6, estimation of Mx from homogeneous non- Non-Gaussian data for example, by overcomplete ICA- iss computa- tionally hard. Further, whereas the estimation algorithms presented in [15], [18], and [6] require the practitioner to test which entries of Mxx exact zeros, naive algorithm inspired by Lemmas 1, 3, and 4 would further require them to test which submatrices' singular values are exact zeros. Such
an algorithm is not advisable.
As a proof of concept, we therefore focus our experiments on partially observed linear causal models in the heterogeneous case. In this setting, F can be learned directly by optimizing the regularized likelihood with respect to F, given the sample covariance matrices of X. We leave more efficient estimation in more general settings to future work.
7.1 Simulations
Suppose we have access to samples from T heterogeneous domains. The data the I-th domain follow
= FV tE,
(12)
where E (O0 Ex) for diagonal Σ, Then in the t-th domain,
x= M
(13)
The negative log likelihood is
-2E8(F, Σ ne (og(m))( log (St) + Tr (s, [xxx"xx)))
(14)
where Xt,i is the i-th row of the design matrix for the t-th domain, È [x is the empirical second moment of the d-th domain, S, M, Ey and n, is the sample size in the t-th domain. If X is generated according to (12), the independent change condition in Theorem holds for the noise variances, and F satisfies the assumptions of Section 4, then by Theorems and 3, F is identifiable up to trivialities. Hence we can in principle optimize the regularized log likelihood.
As sanity check for our theoretical results, simulate data according to (12); for every identifiable graph structure with three observed variables and at most five directed edges, we generated ten causal adjacency matrices with weights randomly drawn from (-0.9, -055) (0.5, 0.9). We estimate F and IC] by minimizing the BIC via exhaustive search. By enumerating candidate graphs from sparsest to densest, single search could take anywhere from 10 to 60 minutes
Intel core i7 processor.
To verify that our estimation method was actually leveraging the noise's heterogeneity, we ran the experiment with one domain and 5000 observations. Only 3% of graphs were identified. Not surprisingly, only 15% of Iearned graphs had any latent variables at all. Increasing the number of domains from to 3 but keeping the total sample size at 5000 (i.e. 1666 per domain) improved the rate of structure identification to 50% of trials.
With 5 domains and 500 samples per domain, the correct graph is identified on 50% of trials: with 1000 samples per domain, this improves to 70%; and with 10 000, this further improves to 80%. In every case that the wrong graph was recovered, the equivalence class mixing matrices M generated by F had incorrect support, perhaps due to insufficient domains or accidentally coupled changes in the noise variances. This supports the main theory of Theorem 3, which, in light of Theorem 1, claims that the structure of F is uniquely determined from a correctly identified M. We report detailed results in the supplement for all graphs studied.
To verify our claims in Theorem 2, we also tested simulated data from ten non-identifiable par- tially observed DAGs-six of which stand in the main equivalence class relations of Figure 3, and

---

four of which are not minimal. Not surprisingly, members of the same equivalence class were indistinguishable. each system achieving the same log likelihood up to eight significant digits.
Because exhaustive search over graphs is computationally expensive (even for this toy problem, there 1759 graphs, and so 1759 non-convex optimization problems), it would be desirable to instead optimize the LI -penalize negative log likelihood:
L Σ) FF Σ) + A Σ Figl-
(15)
As before, simulated data from (12). Numerical experiments verify that L(F", Σ²) is very a local minimum for all practical > O, where (F): _E0) denotes the true adjacency matrix and noise covariances. However, experiments also suggest that this local minimum is generally quite far from the global minimum, both in parameter space and in I.1 loss. Moreover, while the I.1 penalty successfully drives many parameters zero (as would expect), our experiments frequently converge to minima which are denser than the true system. Intuitively, the LI penalty does not care about the density of F; a dense system with small coefficients may have comparable LI penalty as a sparse system with large coefficients. Naturally, denser systems are better equipped fit the observed domain covariances. We summarize these experiments in the supplement.
8 Conclusion and discussions
In many fields, we do not believe that all causally relevant variables have been measured. In such partially observed settings, beyond accurately estimating the causal relations among observed variables, practitioners may want to further identify the causal relations among the hidden variables which generate the observed data. Inspired by this issue, we have contributed to the identification theory of partially observed linear causal models by providing necessary and sufficient graphical conditions for the identification of the full causal graph. Throughout, we assume the additive noise terms in the structural equation model follow non-Gaussian distributions or have independently changing variances across time between domains. Such assumptions, unlike the single-domain Gaussianity assumption, render the mixing procedure from the noise terms to the observed variables identifiable up to the permutation and scaling of columns, thereby facilitating our final identifiability results. These conditions are expected to be applicable to a wide variety of partially observed structures. To deal with real applications, efficient estimation methods needed, and hope our theoretical identifiability results will stimulate algorithmic development to finally solve this important causal discovery problem. As future work, we will focus developing practical estimation methods and extending our results to nonlinear cases.
Acknowledgements
This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Cunn grant agreement No 199.
The work presented in this article was supported in part by Novo Nordisk Foundation Grant NNF200C0062897.
This work was supported in part by the National Institutes of Health (NIH) under Contract R01HL,59805, by the NSF-Convergence Accelerator Track-D award #2134901, by the United States Air Force under Contract No. PA8650-17-C777 and by grant from Apple Inc. The NIH or NSF is not responsible for the views reported in this article.
We are grateful to the anonymous reviewers for their careful reading and helpful comments.
References
[1] Peter Spirtes, Clark Glymour, Richard Scheines, and David Heckerman. Causation, Prediction, and Search. MIT Press, 2000.
[2] Judea Pearl. Causality. Cambridge University Press, 2009.
[3] Michael Lewicki and Terrence Sejnowski. Learning overcomplete representations. Neural Computation, 12(2):337-365, 2000.
10

---

[4] Malcolm Forster, G. Raskutti, Reuben Stern, and Naftali Weinberger. The frugal inference of causal relations. The British Journal for the Philosophy of Science, 69, 04 2017.
[5] Garvesh Raskutti and Caroline Uhler. Learning directed acyclic graphs based on sparsest permutations. Stat, 2018.
[6] Saber Salehkaleybar, 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))11,,, 2020.
[7] J. Eriksson and V. Koivunen. Identifiability, separability, and uniqueness of linear ICA models. IEEE Signal Processing Letters, 11(7):601-604, 2004.
[8] Chenwei Ding, Mingming Gong, Kun Zhang, and Dacheng Tao. Aikelihood-free overcomplete ICA and applicationsin causal discovery. Advances Neural Information Processing Systems, 2019.
[9] Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social Science Computer Review, 91)x62-72, 1991.
[10] David Maxwell Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3(Nov):507-554, 2002.
[11] Joseph Ramsey, Madelyn Glymour, Ruben -omber, and Clark Glymour. A million vari- ables and more: the Fast Greedy Equivalence Search algorithm for learning high-dimensn digh-dimensional graphical causal models, with application to functional magnetic resonance images. Interna- lional Journal of Data Science and Analytics, 3(2):12 2017.
[12] Peter Spirtes, Christopher Meek, and Thomas Richardson. An algorithm for causal inference in the presence of latent variables and selection bias. Computation, Causation, and Discovery, 1999.
[13] Diego Colombo, Marloes Maathuis, Markus Kalisch, and Thomas S Richardson. Learning high-dimensional directed acyclic graphs with latent and selection variables. The Annals of Statistics, pages 294-321, 2012.
[14] Peter Spirtes and Kun Zhang. Causal discovery and inference: Concepts and recent method- ological advances. Applied Informaties, 2016.
[15] Shohei Shimizu, Patrik O. Hoyer, Aapo Hyvärinen, and Antti Kerminen. A linear non-Gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 2006.
[16] Comon. Independent Component Analysis - a new concept? Signal Processing, 36:287-314, 1994.
[17] A. Hyvärinen, J. Karhunen, and E. Oja. Independent Component Analysis. John Wiley & Sons, Inc, 2001.
[18] G. Lacerda, Spirtes, J. Ramsey, and O. Hoyer. Discovering cyclic causal models by Independent Components Analysis. Uncertainty in Artificial Intelligence, 2008.
[19] Kiyotoshi Matsuoka, Masahiro Ohoya, and Mitsuru Kawamoto. A neural for blind separation of nonstationary signals. Neural Networks, 8(3):11-419, 1995.
[20] 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 of Approximate Reasoning, 49(2):362-378, 2008.
[21] Charles Spearman. Pearson's 's contribution to the theory of two factors. British Journal of Psychology, 19(1):95, 1928.
[22] Shohei Shimizu, Patrik Hoyer, and Aapo Hyvärinen. Estimation of linear non-Gaussian acyclic models for latent factors. Neurocomputing, 72(7-9):2024-2022 2009.
11

---

[23] Ruichu Cai, Feng Xie, Clark Glymour, Zhifeng Hao, and Kun Zhang. Triad constraints for learning causal structure of latent variables. Advances Neural Information Processing Systems, 2019.
[24] Feng Xie, Ruichu Cai, Biwei Huang, Clark Glymour, Zhifeng Hao, and Kun Zhang. Generalized independent noise condition for estimating linear non mon-Gaussiaa latent variable graphs Advances in Neural Information Processing Systems, 2020.
[25] Animashree Anandkumar, Daniel Hsu, Adel Javanmard, and Sham M. Kakade. Learning linear Bayesian networks with latent variables. Proceedings of the 30th International Conference on Machine Learning. 2013.
[26] 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 linear non- oon-aassian structural equation model. The Journal of Machine Learning Research, 12: 1..1225-1244 1248, 2011.
[27] PO. Hoyer, D. Janzing, JM. Mooij, J. Peters, and B. Schölkopf. Nonlinear causal discovery with additive noise models. Advances in neural information processing systems, pages 689-696, Red Hook, NY, USA, June 2009, Max-Pl Max-Planck-GGr Gestll,, Curran.
(28) Jonas Peters, Joris M Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. Journal of Machine Learning Research, 2014.
[29] Kun Zhang and Aapo Hyvärinen. On the identifiability the post-nonlinear causal model. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, pages 647-655.
AUAI Press, 2009.
[30] Tatsuya Tashrro, Shohei Shimizu, Aapo Hyvärinen, and Takashi Washio. causal ordering method robust against latent confounders. Neural Computation, 2014.
A
12


Reviews:
[{"review_id": "duy4ia4JVkG", "reviewer": "Reviewer_jP5B", "summary": "The paper provides necessary and sufficient graphical conditions for full identification of linear causal models with latent variables. It introduces the so-called ‘bottleneck’ and ‘strong-redundancy’ condition in combination with bottleneck faithfulness that together ensure identifiability (up to irrelevant permutations/scaling). It also considers likelihood approaches to estimating the unique solution from data that exploit heterogeneity in the independent noise terms over multiple domains. Experimental results are reported to illustrate feasibility of the method.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Challenging and relevant problem that has been studied in many versions before. The main contribution of this paper is that it provides some generic graphical criteria that determine whether or not this identification problem is uniquely solvable, thereby bringing together several other approaches.\n\nDrawback is that it is hard to asses to what extent the accompanying assumptions apply in practice or whether they are very restrictive or not. Naturally ‘linear’ is often assumed but not always valid. Also the need to know the number of latents beforehand makes it harder to apply in real-world scenarios. Often the goal is to infer what latent variables / constructs can be recognised/identified  from the observed distribution. Similarly, on applying the reconstruction estimation described in section 6, it is not easy to verify from the output obtained whether the assumptions actually did hold or not. And actually determining the full model F itself may involve an exhaustive search over graphs, or hope that a penalised log-likelihood approach will converge to the true optimum quickly … which is by no means guaranteed either. \nPerhaps the ‘full identifiability’ is more than what is actually needed. For example, a model with subpath Li -> Lj -> Xk would not satisfy the conditions, but the marginal over Li -> Xk would, and still be equally informative or useful to have. And for the reconstruction problem based on available X that would be perfectly fine.\n\nTechnical quality is good, with attention to detail and good efforts to interpret the sometimes quite abstract theoretical results. Clarity can be improved at some points where concepts are used before they are actually defined, but overall very readable for a challenging subject like this. Experimental evaluation could be a bit more extensive but is ok to illustrate some of the remaining challenges.\n\noriginality: well-known problem, but interesting and original approach\nquality: high quality\nclarity: ok with minor suggestions for improvement below\nsignificance: not directly applicable as an off-the-shelf algorithm, but certainly a meaningful theoretical contribution that provides new insights\n\nminor comments:\np3.82: typo ‘the the’\np3.93: ‘uncorrelated in each domain’ => does this mean they all *have* to change between domains? if so, then that is a rather strong and unrealistic setting, as in most cases only a subset of noise terms is likely to differ between domains / over time\np3.116: can the nodes in J and K themselves be part of the bottleneck from J to K? (ok later becomes clear)\np4,123-8: These two assumptions are at first sight quite artificial and hard to parse in terms of what graphs are excluded and what not. In other words, it is not easy to see how restrictive / realistic these assumptions are in practice. It would be helpful to give some hints/pointers to see what types of graphs generally satisfy these conditions. For example if the variables can be separated so that there are no directed paths from X to L, does the causal structure between the X influence the ‘unique minimal bottleneck condition’?\np4.133: explain/define ‘bottleneck faithful’ … (ok later found at p5.156, just refer here)\np6.192: weird character ‘one?’ in the pdf (or perhaps just my reader)\np6.213: ‘only recover limited information about the causal structure’ => true, but it would be interesting to see if starting from these to reduce the full search space to ‘local latent structure discovery’ would make the assumptions provided here much less restrictive in practice … and with it greatly enhance the applicability\np9.321-324: doesn’t L1 typically induce sparsity by driving certain small coefficients to zero?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no negative societal impact", "review_text": "", "extra_scores": {"ethical_concerns": "no ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "dEgKNnY19Ow", "reviewer": "Reviewer_NMAx", "summary": "This paper is about statistical causal inference. More specifically, this paper is about causal discovery that infers causal graphs. The data used is observational data without intervention. All the variables are continuous.\n\nThis paper considers linear causal models with hidden variables. This setup can be written using an overcomplete mixing matrix as in (1). This overcomplete mixing matrix is known to identifiable up to the permutation and signs of the columns if the hidden variables are non-Gaussian and independent [4]. This is known in the field of independent component analysis. When the number o the hidden variables are the same as the observed variables, it is known that changing noise variance assumption is sufficient to make the overcomplete mixing matrix identifiable even when the hidden variables are Gaussian [16]. A contribution of this paper is Theorem 1 that extends the identifiability result [16] to overcomplete cases. \n\nBased on the two identifiability results, they further consider the sufficient and necessary conditions of the linear causal models after the overcomplete mixing matrix has been identified. They aim to identify the underlying causal model beyond the Markov equivalence class.\n\nThey further assume the sparseness of the causal adjacency matrix F, i.e., the sparsest causal model is true if multiple causal models give the same overcomplete mixing matrix M.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originality: This paper tries to investigate the sufficient and necessary conditions for linear causal models with hidden variables, including linear causal models with hidden common causes and those with latent factors being causally related. This general framework would be new because those models have been investigated separately. \n\nThe estimation method based on exhaustive search in Section 3 looks a naïve method. Another proposed estimation based on sparse regularization is proposed. The idea seems not so new. \n\nQuality: \nI’m not sure if the assumption on the sparseness on lines 106-111 is reasonable or effective in which application domains. I wonder if there is a reasonable scientific reason to think that the sparsest models are the truth.\n\nFurther, I’m interested in how the identifiability results change if the sparsest model assumption has been removed. I thought previous works [17-22] do not make this assumption. \n\nI would appreciate it if the authors make these points above clear.\n\nThe proposed estimation methods look not very fresh or very solid. One is a simple exhaustive search. It is not clear if the other regularization method is consistent or consistently selects the truth. In fact, they say this regularization method did not work well (lines 317-324).\n\nI was not sure if an underdetermined version of [16] has been already considered in the literature of independent component analysis or signal processing.\n\nClarity: There are serval unclear things. \n1.\tLine 116: A set B. Is B a set of what?\n2.\tLine 29: might not not - > might not \n3.\tLine 133: Bottleneck faithfulness\nBottleneck faithfulness has not been defined at this point.\nFigure 2: “is not a redundancy” What would be the definition of this?\nFigure 3: Co-parental non-redundancy, parental non-redundancy\nI couldn’t find their definitions in the paper. Ah, I see. I found them in the supplement.\n4.\tLine 192: at least one?\nWhat is this ? here?\n5.\tIn the supplement, on page 11, what Times of Times (i) means?\n6.\tIn 6.1, were the artificial data generated under the assumption that the underlying model is the sparsest.\n7.\tHow is the number of hidden variables selected?\n\nSignificance: \nThis work could contribute to a deeper theoretical understanding of causal discovery methods in the presence of hidden variables, including hidden common causes and latent factors, by considering a general framework includes both classes of linear causal models with hidden common causes and latent factors. \nRelating to this, I have a question. Previous works [17-22] gave sufficient conditions. Did the authors of this submission find some other sufficient conditions for any of the models considered in [17-22]? If there are no other sufficient conditions, does this mean that the conditions given by [17-22] turned out to be also necessary?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "More discussion on the assumption that the sparsest graph is the truth would be desirable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "Yoetz5inmJf", "reviewer": "Reviewer_FkNC", "summary": "This paper considers one of important problems that under what condition a directed acyclic graphical model, especially linear structural equatioon models, can be inferred without the causal sufficientcy assumption. Hence, the proposed method provide a novel approch that can cope with learning linear structural equation models even when there are several latent variables. The key conditions are (i) sparsest true model, (ii) minimal bottleneck, (iii) strong non-redundancy, (iv) bottleneck faithfulness. It tried to explain a lot of new concepts with examples, and to compare the proposed idea to the existing conditions such as faithfulness. ", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I enjoyed the idea and I think the main problem of learning latent causal graphical models is very important; however, this paper should clarify some necessary definitions, concepts and examples; otherwise I cannot properly evaluate its originality and contribution. \n\nline 41/43/84: It is unclear that \n\"\\epsilon is a vector of independent noise variables\", \"\\epsilon_i are uncorrelated within each domain, ...\", and \"\\epsilon_i are not necessarily mutually independent...\"\n\nIn the linear structural equation models (SEM) settings, is independence of \\epilson_i required? Otherwise it may violate the markov condition and it seems to be a mixture of directed and undirected graphical model. \n\n(1) line 55: definition of the directed path says that (V_i) is a directed path from V_i to itself. Then, Pa(V_i) should include V_i. \n\nline 91, the conditions in Theorem 1 is not clear. It should clarify that \"Suppose we have observed X generated according to the mixing procedure (4) in a number of domains, t = 1, 2, T\"\n\nIf T =2, then is the considered model is X = Y M \\epsilon_1 + (1- Y) M \\epsilon_2 where Y is Bernoulli distribution with known/unknown probabilities?, X_j = \\beta X_{Pa(j)} + Y_{1j} \\epsilon_{j1} + (1 - Y_{1j}) \\epsilon_{j2} where (Y_{1j}) are independent Bernoulli distribution with known/unknown probabilities, or X = M (p \\epsilon_1 + (1- p) M \\epsilon_2)? In addition, in the finite sample setting, is it assumed to be known what distribution of error (\\epsilon_t) the sample follows? \n\nline 116, the definition of the bottleneck should be clarified when J and K are sets of nodes. \n\"We say that a set B is a bottleneck from J to K if every directed path from J to K includes some b \\in B.\"\nline 121 From the definition, for each Vi, Ch(Vi) is a bottleneck from Ch(Vi) to X.\n\nFirst of all, if J includes two nodes, saying J = {1, 2}, and K = {3}, the directed path from J to K is not defined. \nIt is one of the key definitions to provide an important condition in this paper, it should be precisely defined.\n\ne.g., I at first conjecture that it means that the directed path from j to k, for all j \\in J and k \\in K. Then, all directed paths are (1,3), (2,3). Hence, {3} is only bottleneck. However, then, it is contradictory to line 121. \n\nline 160, it is also unclear that \"Rank(M_K^J) = 0 is a violation of classical faithfulness if there...\". It is in fact not true that without considering the error variances of (\\epsilon). The statement is true if all error variances are the same, otherwise there is no guarantees that \"there is a path from J to K but the path coefficients cancel out so that the net effect of J on K is 0\". \n\nIn addition, the term \"bottleneck faithfulness\" might better to be modified, because it is completely based on the graph, the original faithfulness assumption is based on the graph and its probability distribution. Hence, the name \"bottleneck faithfulness\" might lead to incorrect understanding of the concept of the bottleneck faithfulness. \n\nline 179, it should be clarified that \"Let V_k \\to V denote the variables whose longest path to X has fewer than k nodes.\"\nFor example, 1->2->3<-4. Then, by the definition of V_k, we can see V_1 = {3}, V_2 = {2,3,4}, V_3 = {1,2,3,4}, while the longest path is 1->2->3. Hence, it should be the variables whose paths to X has fewer than k nodes. \n\nFigure 4, it is unclear that how Desc(X_2) = Desc(L_1) in all graphs. For instance, in G_1, Desc(X_2) = (X_2, X_3) and L_1 does not exist. \n\nline 285, it should be clarified that the expectation of the variable corresponding to a node is zero, somewhere in Section 2.\n \nI agree that learning a SEM with latent variables is very difficult, and hence, it is worthy to investigate the necessary and sufficient condition for the identifiability. In addition, it is possible that I do not understand some parts of the paper and I amy not be familiar with the line of works. Howeve, without the concrete defintion of the model and concepts, I am pretty sure that common readers cannot understand the part that I fail to understand. Hence, it should clarify the model the paper focuses and it would be better to provide how to check the proposed conditions are satisfied from finite samples or prior information. \n\nMinor:\nline 29 not not\nline 82 matrix \\mathcal{X}\nline 173 equation (8) and does (8)\nline 287 d-th domain might be t-th domain\n\n******** Updated Review **********\nThanks for the kind answer. I increase the rate based on the answer. I hope the paper contains the model specified in term of math termonology. In addition, the statements that have potential misunderstanding are clarified. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not related. ", "review_text": "", "extra_scores": {"ethical_concerns": "None. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12 - 24 hours"}, "extra_text": {}}, {"review_id": "K8OPSUDxRI1", "reviewer": "Reviewer_8tp4", "summary": "This paper provides two graphical conditions for identifying a linear causal model under non-Gaussian error or heterogenous errors across domains when a subset of variables are latent. Specifically, the paper introduces necessary (‘unique minimal bottleneck’ criterion and strong non-redundancy) and sufficient conditions (bottleneck faithfulness) for the identifiability. These conditions indeed form an identifiability condition.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "\noriginality:\nThe paper is original. The related work section is comprehensive enough to appreciate the original contributions of this paper.\n\n\nquality:\nConsidering the readability, I was pleased to read the paper. Notations, texts, theorems, and explanations are all placed perfectly. Sections are organized coherently. Figures are simple yet informative. Technically, the authors made progress in identifiability via graphical and matrix-related understanding, connecting other existing conditions (as demonstrated in the related work section). \n\n\nclarity:\nIs theorem 1 if and only if condition? It is currently written like sufficiency. Given that some of the space is left, it would be helpful if Section 4.2 contains figures that can explain the Lemmas in the section. Similarly, the section may have an algorithm (pseudocode?).\n\n\nsignificance:\nThis paper provides necessity, sufficiency, and identification results (in addition to estimation). Since (theoretical) causality research focuses on the existence of clearly defined estimands, such conditions will be valuable resources to develop the causal theory further. \n\n\nlimitation:\nAlthough linearity is a strong assumption over the functions of causal models, since it allows us to study a class of causal models in depth, I would not consider the assumption restrictive. In the future, it would be desirable to provide some details about the estimation procedure for overcomplete ICA. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": ".", "review_text": "", "extra_scores": {"ethical_concerns": ".", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers appreciated the relevance of the paper to the NeurIPS community and the strength of the technical results. 

Additionally, the authors did a good job of engaging with the reviewers to dispel most concerns. Hopefully, the discussion clarified to the authors which parts of the paper are less readable, and they can use this information to improve the writing.
Decision: Accept (Poster)