Identification of Partially Observed Linear Causal Models: Graphical Conditions for the Non-Gaussian and Heterogeneous Cases
Year: 2022

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 applications 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 the number of latent variables is very large. We demonstrate the validity of our results on synthetic data.

text: In causal discovery, linear non-Gaussian acyclic models (LiNGAMs) have been studied extensively. While the causally sufficient case is well understood, in many real applications 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 the number of latent variables is very large. We demonstrate the validity of our results on synthetic data.

heading: 1 Introduction
text: 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 in 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 in 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 in the causal relations between 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.
It is natural to 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.
∗The work presented in this article was started while JA was at CMU.
35th Conference on Neural Information Processing Systems (NeurIPS 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.

heading: 2 Problem setup
text: Suppose some causal variables V = {V1, . . . , Vp} follow a linear structural equation model (SEM) V = FV + ε, (1)
where V := (V1, . . . , Vp)T is a 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 ε = (ε1, . . . , εp)
T is a vector of independent noise variables. In this paper we consider two settings for εi: 1) all εi are mutually independent and non-Gaussian; or 2) there are multiple domains, εi are uncorrelated within each domain, and their variances change independently across domains. We will make the second assumption technically precise Section 3.
We seek necessary and jointly sufficient conditions for identifiability of F (up to trivial indeterminacies) in the case where only some subset of V (which we call X ) is measured. Thus F may encode observed-observed interactions, latent confounding, latent-latent interactions, and latent mediation or intermediate confounding. Our results identify F from the equivalence classM, as defined in Section 2.2, of mixing matrices induced by (1). This equivalence classM is identifiable if, for example, the errors are non-Gaussian or if their distribution changes over time or between domains.

heading: 2.1 Notation
text: For any matrix A and index sets J and K, we write AJK to denote the submatrix of A with columns indexed by J and rows indexed by K. Observe that AJK = IKAI
J . Thus, FJK describes the direct effect of {Vj : j ∈ J} on {Vk : k ∈ K}. (Remember: causes are up-stream of their effects.)
The graph induced by (1) has edges Vi → Vj whenever Fij 6= 0. We write Pa(Vi) := {Vj : Vi ← Vj} and Ch(Vi) := {Vj : Vi → Vj}, respectively, to denote the parents and children of Vi. We say that (V1, ..., Vk) constitutes a directed path from V1 to Vk if Vi → Vi+1 for every i ∈ {1, ..., k − 1}. Trivially, for every Vi, (Vi) is a directed path from Vi to itself; we say that a directed graph is acyclic (a DAG) if (Vi) is the only such path. We write Anc(Vi) := {Vj ∈ V : Vj has a directed path to Vi} and Desc(Vi) := {Vj : Vi has a directed path to Vj}, respectively, to denote the ancestors and descendants of Vi. For DAGs, notice that Anc(Vi) ∩Desc(Vi) = {Vi}, but Vi 6∈ Pa(Vi) ∪ Ch(Vi). We assume that only some subset X ⊆ V is observed, with the remaining L = V − X being latent. We use Vi to denote a generic variable, observed or latent, whileXi ∈ X denotes an observed variable and Lj ∈ L denotes a latent variable. When it is clear from context, we occasionally suppress the distinction between a variable Vi and its index i.

heading: 2.2 Identification and minimality
text: Since F induces a DAG, we can always solve (1) to express the causal variables in terms of the independent noise terms: V = Mε, (2) where M := (I− F)−1 (3) is the mixing matrix with Mij being the net effect of εi on Vj . This net effect is calculated by multiplying causal weights along paths and summing across paths. Notice that if Mij 6= 0, then Vj ∈ Desc(Vi). Because L is hidden, let us explicitly write X in terms of ε:
X = MX ε. (4)
In both the non-Gaussian and heterogeneous settings we consider in this paper, MX is identifiable up to permutation and scaling of columns; that is, we can identify the equivalence class
M = {MXDP : DP ∈ DPp}, (5) where
DPp := {DP ∈ Rp×p : 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 generatesM if (I−F)−1X ∈M. Of course, in partially observed systems, the adjacency matrix that generatesM is not unique. However, some of these matrices are 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, 5]. As a result, without prior knowledge, a 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 a complicated model if a simpler model fits just as well. It is therefore natural to recast the question of identifiability to a question of maximal sparsity.
Let the `0 “norm” of a matrix ‖ · ‖0 denote the number of non-zero entries in that matrix. Then we say that a causal adjacency matrix F is minimal with respect toM if F generatesM and ‖F̂‖0 ≥ ‖F‖0 for any F̂ 6= F that generatesM. Let F 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)−1FDP : DP ∈ DPp with (DP)XX = I } . (6)
The only indeterminacy remaining in F amounts to re-indexing and re-scaling the latent factors. A word of caution is in order. Because the adjacency matrix that generatesM 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 1 shows a non-minimal graph which is not pathological. Thus, if a practitioner believes the true partially observed causal model to be 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 to check than (6). But first, we return to the identifiability ofM.
3 Sufficient conditions for identification ofM
The main results of Sections 4 and 5 rely on the identifiability ofM, which is theoretically guaranteed in the two settings we consider in this paper. In the first setting, εi 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 estimatingM from X is known as Overcomplete Independent Component Analysis (OICA) [3], and in practice this task is known to be computationally difficult [8].
In the second setting, εi 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 ofM. Besides complementing Theorem 3 of Eriksson and Koivunen [7] as an alternative foundation for our identification work, the identifiability ofM in this setting may be of independent interest in the fields of blind source separation and system identification.
Theorem 1. Suppose we have observed X generated according to the mixing procedure (4) in a number of domains, t = 1, 2, ..., T , where MX has full row rank. Assume that εi are uncorrelated in each domain and that their variances in domain t, denoted by σ2ti, change independently across domains in the sense that S, whose (t, i)-th entry is σ2ti, has full column rank. Further assume that each |X | columns of MX are linearly independent and that p ≤ 2|X | − 2. Then if X admits a model

heading: X = M̃X ε̃, where ε̃ also follows the above assumption on ε, then every column of M̃X must be
text: proportional to a column of MX and vice versa.
Note that this theorem gives sufficient conditions for the identifiability ofM; our empirical results suggest that they are not necessary.

heading: 4 Necessary conditions for identification of F up to trivialities
text: 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 a bottleneck from J to K if, for every j ∈ J and every k ∈ K, each directed path from j to k includes some b ∈ 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 strict for B′ 6= B. Note that bottlenecks do not in general d-separate J and K along all paths, but only directed paths from J to K.
It is clear from the definition that, for each Vi, Ch(Vi) is a bottleneck from Ch(Vi) to X . However, for identification, we further require: Condition 1 (Bottleneck). For every Vi, Ch(Vi) is the unique minimal bottleneck from Ch(Vi) to X .
As illustrated in Figure 1, the bottleneck condition ensures that if we try to “explain” the net effect of Vi on X by replacing Ch(Vi) with any subset of Desc(Vi), 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 Vi on Ch(Vi) via some of its non-descendants: Condition 2 (Strong Non-Redundancy). For all Li, Vj , if Ch(Li) ⊆ Ch(Vj) ∪ {Vj} then Li = Vj .
Figure 2 shows a 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 |X | children; but if a variable has no 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 (Li, Vj), if Li is an ancestor but not a parent of Vj , or has more than one directed path to Vj , then strong non-redundancy is satisfied for that pair. If Vj is a parent of Li and they violate strong non-redundancy, then the bottleneck condition is violated for Vj . Theorem 2. If F is identified up to trivialities, then the graph induced by F satisfies the bottleneck and strong non-redundancy conditions.
Thus the bottleneck and strong non-redundancy conditions are necessary for identification of F up to trivialities. In Section 5, we further show that they (along with a very mild constraint on the causal weights) are also jointly sufficient conditions.
If Ch(Vi) is not at least a minimal bottleneck for every Vi, then F 6∈ F . Figure 1 shows one example of such a 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 at least one of the bottleneck and strong non-redundancy conditions. The nature of these indeterminacies is depicted in Figure 3. In Figure 2 we show a simple yet illustrative example in which both conditions are satisfied.

heading: 5 Sufficient conditions for identification of F up to trivialities
text: In the previous section, we introduced two structural conditions which must be satisfied for F to be identifiable up to 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 (1). In particular, we assume thatM is identifiable, for example due to Theorem 3 of Eriksson and Koivunen [7] or Theorem 1 of the present work.

heading: 5.1 Bottleneck faithfulness
text: First, we connect ranks of submatrices of M to minimal bottlenecks of its corresponding graph. Proposition 1. Let B be a minimal bottleneck from J to K. Then Rank(MJK) ≤ |B|.
Strict inequality in Proposition 1 for some minimal bottleneck B from J to K can make F nonidentifiable – even if the bottleneck condition and strong non-redundancy hold. For instance, both graphical conditions hold for
X = 0 1 −12 2 03 3 0 4 0 4 L + εX , L = εL, but Rank(MLX ) = 2 while the minimal bottleneck from L to X is L with |L| = 3. The system
X = 0 1 −10 2 00 3 0 0 0 4 L + εX , L = [0 0 01 0 0 1 0 0 ] L + εL
generates the same mixing matrix, MX , but has a strictly sparser graph. Thus to ensure identifiability, we assume that the causal coefficients satisfy: Condition 3 (Bottleneck Faithfulness). For every J ⊆ V,K ⊆ X , if B is a minimal bottleneck from J to K, then Rank ( MJK ) = |B|.
In the supplementary material we characterize the set of adjacency matrices F that are bottleneck faithful for a given graph. In particular, we show that a generic F is bottleneck faithful.
Interestingly, in linear systems, classical faithfulness is a special case of bottleneck faithfulness. Rank(MJK) = 0 is a violation of classical faithfulness if there is a minimal bottleneck B 6= ∅ from
J 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 is 0, the system is not faithful to the graph. Bottleneck faithfulness generalizes this so that the net effect of J on K must have maximal rank for the given graph.

heading: 5.2 Identifiability
text: In this subsection, we show that if the bottleneck condition, strong non-redundancy, and bottleneck faithfulness hold for F, then F is identifiable up to trivialities. Throughout, we assume the three conditions hold.
Our approach is illustrated by the following computation. For any Vi,
MX (I− F)i = IiX . (7)
Let J = Ch(Vi). Since the support of Fi is J , the equation
(M− I)iX = MJXx. (8)
always has a solution at x = FiJ . In 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 x = FiCh(Vi).
But there is a version of (8) for each J ⊆ V . For which other choices of J does (8) have a solution? Clearly a solution always exists if J ⊇ Ch(Vi). On the other hand, we can guarantee that a solution with |J | ≤ |Ch(Vi)| is only possible if J contains an ancestor of Vi: Lemma 2. Suppose J ⊆ V − Anc(Vi). If (M − I)iX ∈ Range ( MJX ) , then |J | ≥ |Ch(Vi)|, with equality if and only if J = Ch(Vi).
By Lemma 2, if any superset of Ch(Vi) containing no ancestors of Vi is identifiable, then Ch(Vi) is also identifiable. Next, we will show how such a superset of Ch(Vi) can be identified.
Let Vk ⊆ V denote the variables whose longest path to X has fewer than k nodes. More formally, we define recursively
V0 := ∅, (9) Vk+1 := {Vi ∈ V : Ch(Vi) ⊆ Vk} , for k ≥ 0. (10)
Naturally, we define Xk := Vk ∩ X and Lk := Vk ∩ L. Notice that Vk is strictly increasing, and is induced by the topological ordering on V . Proposition 2. For all k, either Vk ⊂ Vk+1, or Vk = V .
Further, for each k ≥ 0, define
Jk+1(Vi) := arg min J∈ { J⊆Vk:MiXk∈Range ( MJXk )} |J |. (11)
Intuitively, this denotes the set of minimal choices for J ⊂ Vk such that (8) has a solution. From Lemma 2, we know that Jk+1(Vi) = {Ch(Vi)} if Vi ∈ Vk+1 − Vk. 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 ≥ 0, let Vk and Jk(Vi) be defined as above. Then Vi ∈ Vk+1 − Vk if and only if all of the following hold:
1. Vi 6∈ Vk;
2. |Support(MiX )−Xk| ≤ 1;
3. |Jk+1(Vi)| = 1; and 4. for all Vj 6= Vi satisfying points 1 and 2, MjXk 6∈ Range ( M Jk(Vi) Xk ) .
As a result of Lemma 3, each Vk is identifiable. Clearly, if Vi ∈ Vk+1, then Ch(Vi) ∈ Vk and Vk ∩ Anc(Vi) = ∅. Hence by Lemma 2, Ch(Vi) is also identifiable. Thus the full DAG is identifiable, and each column of MX can be associated with the corresponding node in the DAG. However, Lemmas 1, 2, and 3 are not enough to distinguish which nodes correspond to latent variables and which correspond to observed variables; we have yet to pair each Xi with its net effects MiX . Resolving this final indeterminacy is not hard. Intuitively, the vector of MX corresponding to Xi must have non-zero coefficients in the i-th slot while every vector corresponding to descendants of Xi will not. Lemma 4 formalizes this observation.
Lemma 4. Xi ∈ Xk+1 if and only if Xi ∈ Vk+1 and Support (MXiX )−Xk = {i}.
Together, Lemmas 1, 2, 3, and 4 imply that F is identifiable if MX is identifiable. Of course, we do not know MX—only M. Nevertheless, Lemmas 2, 3, and 4 do not involve the scaling and permutation of MX—only the linear dependencies of its columns. Some simple calculation shows that Lemma 1 can be used to put any MXPD ∈ M in one-to-one correspondence with (PD)−1F(PD).
Theorem 3. Suppose F satisfies generalized non-redundancy, bottleneck faithfulness, and the bottleneck condition. Then F is identifiable up to indeterminacies.

heading: 6 Relation to existing work
text: 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 [11]—generally focus on 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 independence 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].
It 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 non-Gaussian 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 a 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 basisM, 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 ifM 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.1, classical faithfulness is entailed by bottleneck faithfulness and imposes no 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 5 has a reassuring consequence for our work: even if the graphical conditions for total identification fail to apply, the causal order of X is still identified. If the practitioner is further interested in the observed variables’ net effects on one another, (M− I)XX , then additional graphical assumptions are needed. Theorem 16 of Salehkaleybar et al. [6] provides one condition sufficient for this purpose: no latent variable Li has precisely the same observed descendants as any observed variable Xj (formally, for all Li, Xj ,Desc(Li) ∩X 6= Desc(Xj) ∩X ).
Again, this being a 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 Li and Xj have the same observed descendants, as shown in Figure 4.
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 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 to two [23, 24]. Clearly, these are all special cases of both the bottleneck and non-redundancy 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-redundancy conditions.
However, identification is possible even when no latent confounder has any pure children; for example, Anandkumar et al. [25] present a model in which latent variables with no pure children are identifiable. Rather than purity, they require a graph expansion property—for all non-singleton S ⊆ L, | ⋃
Li∈S Ch(Li)∩X | ≥ |S|+dmax, where dmax = maxi |Ch(Li)∩X |—as well as a rank condition on FLX which places hard-to-check graphical constraints on the model and bounds |L| ≤ 13 |X |. Nonredundancy 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} ∪ Ch(Li) ∩ L. Thus in one sense, our conditions can be seen as a refinement on the expansion property; however, we also remove the many hard-to-check graphical consequences of the rank condition, and further show that many graphs even with |L| |X | are identifiable. For example, Figure 4 shows an 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. 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 3 and 4 show that our conditions are indeed more general than previous identification conditions; not only do our conditions allow and identify 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 a useful primitive for what it means for a 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(Xi) is identifiable by regressing Xi on Z ⊆ 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
and non-redundancy conditions are much more general, this naturally complicates the question of estimation.

heading: 7 Estimation
text: In Theorems 1 and 3, we have shown that a causal system which satisfies the conditions of Section 4 is uniquely identifiable whenever MX is identifiable. However, as indicated in Section 6, estimation of MX from homogeneous non-Gaussian data—for example, by overcomplete ICA—is computationally hard. Further, whereas the estimation algorithms presented in [15], [18], and [6] require the practitioner to test which entries of MX are exact zeros, a naive algorithm inspired by Lemmas 1, 2, 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.

heading: 7.1 Simulations
text: Suppose we have access to samples from T heterogeneous domains. The data in the t-th domain follow V = FV + ε, (12) where ε ∼ N (0,Σt) for diagonal Σt. Then in the t-th domain,
X = MXΣtM T X . (13)
The negative log likelihood is
−2``(F,Σ) = T∑
t=1
nt ( |X | log(2π) + log det(St) + Tr ( S−1t Ê [ xtx T t ])) , (14)
where xt,i is the i-th row of the design matrix for the t-th domain, Ê [ xtx T t ] is the empirical second moment of the d-th domain, St = MXΣtMTX , and nt is the sample size in the t-th domain. If X is generated according to (12), the independent change condition in Theorem 1 holds for the noise variances, and F satisfies the assumptions of Section 4, then by Theorems 1 and 3, F is identifiable up to trivialities. Hence we can in principle optimize the regularized log likelihood.
As a sanity check for our theoretical results, we 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,−0.5)∪ (0.5, 0.9). We estimate F and |L| by minimizing the BIC via exhaustive search. By enumerating candidate graphs from sparsest to densest, a single search could take anywhere from 10 to 60 minutes on an 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 learned graphs had any latent variables at all. Increasing the number of domains from 1 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 of 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 identifiedM. 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 partially 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 are 1759 graphs, and so 1759 non-convex optimization problems), it would be desirable to instead optimize the L1-penalized negative log likelihood:
L(F,Σ) = −2``(F,Σ) + λ ∑ |Fi,j |. (15)
As before, we simulated data from (12). Numerical experiments verify that L(F0,Σ0) is very near a local minimum for all practical λ > 0, where (F0,Σ0) 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 L1 loss. Moreover, while the L1 penalty successfully drives many parameters to zero (as we would expect), our experiments frequently converge to minima which are denser than the true system. Intuitively, the L1 penalty does not care about the density of F̂; a dense system with small coefficients may have a comparable L1 penalty as a sparse system with large coefficients. Naturally, denser systems are better equipped to fit the observed domain covariances. We summarize these experiments in the supplement.

heading: 8 Conclusion and discussions
text: 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 or 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 are needed, and we hope our theoretical identifiability results will stimulate algorithmic development to finally solve this important causal discovery problem. As future work, we will focus on developing practical estimation methods and extending our results to nonlinear cases.

heading: Acknowledgements
text: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 801199.
The work presented in this article was supported in part by Novo Nordisk Foundation Grant NNF20OC0062897.
This work was supported in part by the National Institutes of Health (NIH) under Contract R01HL159805, by the NSF-Convergence Accelerator Track-D award #2134901, by the United States Air Force under Contract No. FA8650-17-C7715, and by a 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.

Review summaries:
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.  This 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.   Based 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.  They 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. 

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. 

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.

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.