Linear SCM Identification in the Presence of Confounders and Gaussian Noise
Authors: Vahideh Sanjaroonpouri
Pouria Ramazi
Venue: ICLR 2025 Spotlight (2025)
Keywords: identifiability
SCM
causal discovery; linear SCM; confounder
Primary area: causal reasoning
TL;DR: Identifiability of Linear SCMs with Gaussian noise is investigated in both cases of Gaussian and non-Gaussian confounders.

Abstract: Noisy linear structural causal models (SCMs) in the presence of confounding variables are known to be identifiable if all confounding and noise variables are non-Gaussian and unidentifiable if all are Gaussian.
    The identifiability when only some are Gaussian remains concealed. 
    We show that, in the presence of Gaussian noise, a linear SCM is uniquely identifiable provided that \emph{(i)} the number of confounders is at most the number of the observed variables, \emph{(ii)} the confounders do not have a Gaussian component, and \emph{(iii)} the causal structure of the SCM is known.
    If the third condition is relaxed, the SCM becomes finitely identifiable; more specifically, it belongs to a set of at most $n!$ linear SCMS, where $n$ is the number of observed variables.
    The confounders in all of these $n!$ SCMs share the same joint probability distribution function (PDF), which we obtain analytically.  
    For the case where both the noise and confounders are Gaussian, we provide further insight into the existing counter-example-based unidentifiability result and demonstrate that every SCM with confounders can be represented as an SCM without confounders but with the same joint PDF.

Published as a conference paper at ICLR 2025
LINEAR SCM IDENTIFICATION IN THE PRESENCE OF CONFOUNDERS AND GAUSSIAN NOISE
Vahideh Sanjaroon
Pouria Ramazi
Department of Electrical & Computer Engineering
Department of Mathematics & Statistics Brock University St. Catharines, ON L.2 3A1, Canada pramazi @brocku.ca
Isfahan University of Technology
Isfahan, 8415683111 Iran
vahidehsan jaroone@aaar i com
ABSTRACT
Noisy linear structural causal models (SCMs) in the presence of confounding variables are known to be identifiable if all confounding and noise variables are non-Gaussian and unidentifiable all are Gaussian. The identifiability when only some are Gaussian remains unclear. We show that, in the presence of Gaussian noise, a linear SCM is uniquely identifiable provided that (i) the number of con- founders is at most the number of the observed variables, (ii) the confounders do not have a Gaussian component, and (ii)) the causal structure of the SCM is known. If the third condition is relaxed, the SCM becomes finitely identifiable, belonging to a set of at most n! linear SCMs, where n is the number of observed variables. The confounders in all of these nt SCMs share the same joint probability distribution function (PDF), which we obtain analytically. For the case where both the noise and confounders are Gaussian, we provide further insight into the existing counter-ee counter-example example- based unidentifiability result and demonstrate that every SCM with confounders can be represented as an SCM without confounders but with the same joint PDF.
INTRODUCTION
Achieving desired state in a system requires appropriate interventions, which necessitate a causal model rather than a purely probabilistic or correlation-base approach. This is because interventional queries are not always answered by probabilistic models. A Structural Causal Model (SCM) (Peters) (ct al.) 2017) formalizes the common sense intuition of the notion of causality. its general form, an SCM consists of number of random variables, and enforcing each variable to be deterministic function single noise variable and a subset of the other random variables, known as its causes. The noise variables are assumed to be disjoint.
An SCM allows systematic answers to observation queries (Spirtes et al, 2000), such as the prob- ability of X given Y, intervention queries, like the probability of X if Y intervened upon, and counterfactual queries, for example, what is the probability of X had Y taken a different value. However, first the structure of the SCM, namely, the functions assigned to each variable, must be estimated from data, task referred to as causal discovery (Chen et al. 2021 Yang et al. 2022] Xie et al. 2023 Agrawal et al., 202T) The available data usually limited observations rather than interventions due to infeasibility or high costs of experiments. The question then is up to what extent, an SCM can be estimated from observation data. More specifically, given the joint probability distribution function (PDF) of the random variables, is it possible to uniquely obtain the functions of an SCM; namely, is the SCM identifiable (Hyvärinen et al. 2023)?
There is yet another intrinsic challenge in answering the identifiability question: the existence of confounders, i.e. unobserved variables that affect the considered observed variables in the SCM. Indeed, it is often the case that several variables have strong associations without any causal re- lationship, indicating the presence of one or more confounders (Spirtes et al., 2000 Witty et al. 2021). It is nearly impossible claim that all causes of a specified process considered; hence, the consideration of confounders inevitable. While there has been some progress on the identifiability of SCMs in the presence of confounders in the general case where the assigned functions can be

---

Published as a conference paper at ICLR 2025
nonlinear (Shimizu 2014 Hyvärinen et al. 2023 Wu et al. 2022 Witty al. 2021 Agrawal et al. 202I), this problem remains open and chalnenging due to the information inaccessibility regarding the confounders and the complexity of the analysis. Thanks to the linearization techniques around the operating point of a system, the assigned functions are often supposed linear, resulting in a linear SCM, resulting in the system of equations X AX + BH CZ, where random variables X, 1. Z are the observed variables, confounders, and noise variable, and A, B, C' are the coefficient matrices (Eriksson & Koivunen 2003). The identifiability of the SCM then reduces to determining the triple (A, B, C) from the joint PDF of the observed variables P(X).
1.1 RELATED LITERATURE ON LINEAR SCMS
The base of many existing work on the identification of linear SCMs is Independent Component Analysis (ICA) (Hyvärinen & Oja 2000) applied to the so-called ICA model where the observed variables X are assumed to be a linear combination of some independent components, denoted by the vector S. and are governed by the equation X := AS, where is known as the mixing matrix. In fact, ICA is developed based on Darmois-Skitovin mixing matrix A for a non- Gon-Gaassian ICA model is identifiable up to the permutation and scaling of its columns. Namely, two mixing matrices A and A = AT ,n Pr. may result in the same observation PDF P(X), where T m and Pm are scaling and permutation matrices. However, if two mixing matrices and Å result the same P(X) and one column of is independent of the columns in A, then at least one of the sources are Gaussian (Taleb & Jutten 1999). For the case where the number of sources exceeds the observable variables, the overcomplete ICA is developed (Podosinnikova et al. 2019).
Theorem (Pavan & Miranda 2018). It is proven that a
Clearly, the idea of ICA are also applicable to the framework of SCMs. However, based on the assumptions and model limitations, researchers are suggesting new algorithms (Xie et al., 2023 Yang et al. 2022 Salchkaleybar et al.) 2020; Adams et al. 2021). In the presence of unobserved variables (also called latent variables) the identifiability was shown in (Xie et al. (003)) under the assumption that every latent variable has at least two pure measurement variables (those that do not have an observable cause and have at most one latent cause). Yang et al. (2022) introduce two different classes of linear SCMs, i.e., P-SCM and its subset D-P-SCM, in which some latent variables are considered as noise and influence only one variable. It is proved that in the set of P-SCM, a D-P-SCM is not identifiable. Under the faithfulness assumption and using ICA, (Salehkaleybar et al. 2020 show that non- Gaussian noise and confounders, the SCM is unidentifiable but there are a finite number of SCMs that result in the PDF of the observed variables and that these SCMs can be obtained.
The authors in (Xie et al. 2022) study the identification of Hicrarchical Structures, where the observed variables do not interact and are caused only by the latent variables. [Adams al. (202T) show that if strong reduddaunyy and bottleneck faithfulness hold, the SCM is identifiable up to trivialities. Giraud & Tsybakov| (2012) and Frot et al. (2019) study linear systems with sparsely related observed variables. GGraud & Tsybakov (2012) estimate the number of latent variables and the conditional graphical model structure among the observed variables, and Frot et al. (2019) estimate the Markov equivalence class of the directed acyclic graph over the observed variables.
Moreover, Shimizu et al. (2009); Cai et al. (211)); : Xie et al. (2020); Anandkumar et al. (013)) estimate the causal structures of hidden variables with the assumption that the observable variables are not caused by each other. Nowzohour et al. (017)) study bow-free graph in which there cannot be both directed edge and bow (confounder) between the same pair of variables. Chen al. (202T) consider linear non-Gaussian SCMs in the presence of latent confounders and present hybrid algorithms to determine unknown causal relations by means of regression, independence tests, Traid conditions (Cai et al. 2019). and over complete ICA algorithm. Over complete ICA has a closed form solution for the mixing matrix in specific cases using higher order cumulants (Cai et al., 2003). Xie et al. (2020) propose a Generalized Independent Noise (GIN) condition to discover the causalities under the assumption that there is no direct edge between observed variables, which the same assumption considered in the structure in (Squires et al.) 2022). D' Amour (2019) present examples in which the system is not identifiable, such as the special case of a Gaussian linear SCM. Li et al.) (2024) provide a sufficient condition for the identifiability of linear SCM with observed and latent variables under the faithful assumption. The condition requires having either for each latent variable one pure child, that is observed variable that is caused only by that latent variable and itself does not cause any other variable, or no pure child but a non non-Gaussian distribution for a subset of noise variables.
2

---

Published as a conference paper at ICLR 2025
1.2 CONTRIBUTION
In this paper, we distinguish between noise, which we assume to be Gaussian and affects only one observed variable, and confounders, which can be either all Gaussian or all non-Gaussian and can affect multiple observed variables. Our contribution and distinction from existing work are as follows:
(I) For the case where both the noise and confounders are Gaussian, we show that there are infinitely many SCMs consistent with the same observed PDF-Theorem| II This provides further insight into the existing counter-example-base unidentifiability results (Eriksson & Koivunen 2004 [Hoye et al.) 2008). (2) We then show that in order for the SCM to be finitely identifiable that is only a finite number of SCMs result in the observed PDF-it is sufficient for the confounders to be non non-Gaussian (Theorem 2 not necessarily also the noise as in (Salehkaleybar al., 2020). The work in (Li et al., 2024) also allows some noise variables to be Gaussian, however unique identifiability results rely on restrictive conditions, such having generalized pure pair. In contrast, our work demonstrates that while identifiability may not be unique, is possible to identify a finite (equivalence) set of causal structures without relying extra assumptions. finite set in the case of Gaussian noise and non-Gaussian confounders. We provide an algorithm that given SCM, obtains all other SCMs in its equivalence set Algorittit []] those who share the same observed PDF as the given SCM. (4) Thanks to the novel approach of using characteristic functions in this paper, we obtained precisely the PDF of the confounders- (3) in Theorem 2 (5) For Gaussian noise and non- Gan-Gaasiian confounders, distinct SCMs within the finite set must have different causal orders. Thus, unique identifiability would be achieved, should the causal order be specified. In contrast, as illustrated in (Salehkaleybar et al., 2020), when all variables are non-Gaussian, it is possible for two SCMs to have the same causal order.
(3) We provide an upper bound on the size of this
In Section II, we present the problem formulation. Section III addresses Gaussian Structural Causal Models (SCMs). Section IV, we examine the identifiability of non- non-Gaussian SCMs. A compari- son of identifiabiliyy results based on noise and confounder distributions is provided in Section V. Numerical examples are discussed in Section VI. Finally, Section VII concludes the paper.
2
SYSTEM MODEL AND PRELIMINARIES
2.1 NOTATIONS
Vectors are denoted by underline, c.g., Deterministic variables are lowercase and random variables are uppercase. Matrices are uppercase and boldface, e.g., A. The notation (.) represents the matrix transpose and F][-] denotes the expected value operator. A Gaussian random distribution with expected value and covariance matrix Σ is denoted by N(,, Σ). I& is the identity matrix with dimension k. The component located at the 7th row and 1dh column of matrix M is represented by Mij- The cardinality of a set X' is denoted by |
2.2 PROBLEM FORMULATION
Consider the linear SCM C defined by
X= A BH CZ
where observed vector X Rax1 is vector of zero-mean observed variables X,, i 1,..., R. with n 2 2, H E k k 2 0, is a vector of mutually independent zero-mean confounding variables (or confounders), Z E Rax1 is vector of zero-mean mutually independent Gaussian noise variables with Z ~ (O x I,). A E I nxn is a matrix with zero diagonal components in which Ay = O due to the casual structure. B E Raxk and C E B= is positive definite diagonal matrix. Without loss of generality, we assume ETHH Ig.
The joint PDF of the observed vector X and confounder vector H are denoted by P(X) and P())). respectively. It follows that [I] can be written as
X + QZ
where Q =(I, A)- is a positive definite matrix with 25y for every * j. and B.. The parameters in (1) can be derived according to (M, Q) as follows. C is
M (I, A)-1 1-1.
3

---

Published as a conference paper at ICLR 2025
diagonal matrix where its diagonal elements are equal to the diagonal elements of Q. Then A and B are computed, respectively, as A = I, CQ and B = M AM. Thus, an SCM E can be represented either by the ordered pair ((M, Q) ordered triple C,A,
The SCM induces a (causal) DAG over the observed and confounders, where there is a link from observed variable X; (resp. confounder H;) observed variable X, if A₁₁ + O (resp. Bjs # 0). In this case, we say that X; (resp. H;) causes/ifluences Xj. The confounders are not linked to each other.
Remark 1 (Canonical model) The SCM defined by matches the so-called canonical model in which each confounder is a root variable, i.e. with no parent. For SCMs with non- non-GGussian confounders where the confounders are not root variables, an observationally and causally equivalent canonical model can be obtained using Algorithm in (Hoyer et al. 2008 (by skipping step 3 the algorithm).
Definition (Informative observable variables) A set of informative observed variables (of size m) is a set of observed variables corresponding to any m linearly independent rows of matrix M. The remaining m observed variables are called non-informative (with respect to this set).
Definition 2 (Causal (structure) order) A causal order for SCM e denoted by Oe is defined as the topological order of the variables in the induced DAG, that is, an ordering over the observed variables, i.e., X;, -ii.... > Xi. where {Xi,.... X,, = (XI....; Xn), such that there is no futhfrrm Xia12 to Xs, in the induced DAG for every l E (1, n..
The causal structure order is not necessarily unique, because the induced DAG may not be connected. The set De denotes the set of all possible causal orders for the SCM C.
We use the concept of equality in distribution, denoted as d Y, for random variables X and that have the same distribution (Definition 12). In particular, when X and X' are the observed variables of SCMs C and C² X X' implies that they share the same support and have identical distributions, i.e., ((X) P(X').
Definition 3 (SCM finite identifiahility) SCM E in the form of ①T is finitely identifiable if and only if there exists a finite number of SCMs E such that X 1 X' where X and X' are the observed variables in SCMs E and C.. The set of all such SCMs is called the finite equivalence class of SCM C. The SCMs in this class are said to be equivalent to each other.
Unique identifiability is the same finite identifiability but when the cardinality of the equivalence class equals one. The following is the equivalent definition used in the literature.
Definition 4 (SCM unique identifiability) SCM C(A, B, C) in the form of is uniquely identift- able if and only for every other SCM C' (A', B', C') it holds that
X - X' + = A', M,B- B'
or equivalently for C(M, Q) and e (M',0) Q"),
4
x' M Q
Correspondingly, we say that SCMs C(A, (A, B, C) and CA',, B', C') are distinct if (, # (A', B', C") or equivalently, (M,Q) + (M', Q').
Definition 5 (Dependent random vector) A random vector Y is independent if its entries are mulu- ally independent; otherwise, Y is dependent.
Refer to Definition 13 and Remarks 5 and 6 in the Appendix for the definition of the characteristic function (CF) and its fundamental properties.
Definition 6 (Decomposable characteristic function) LLkacs 1972) A CF is decomposable if can be written as the product of two CF's such that neither take a degenerate distribution. A degenerate distribution is distribution of constant number with probability one.
4

---

Published as a conference paper at ICLR 2025
3 LINEAR SCM WITH GAUSSIAN CONFOUNDERS
The SCM defined in (1 with Gaussian confounders is not finitely identifiable, because the noise variables are also Gaussian. Specifically, each noise variable Z; (for = 1, .....,,7) can be expressed as the sum of another noise component Z and a confounder H; where Hi affects only the observed variable X, This decomposition satisfies F F[ F[ + F.[H,)). Since Zi and Hi can have different variances, there are infinitely many SCMs corresponding to different choices of these variances. To avoid addressing these trivial cases and provide meaningful distinction between noise and confounding variables, we make the following assumption.
Assumption Each confounder causes at least two observed variables.
The assumption ensures that every column matrix B has at least two nonzero entries. The following theorem shows that even under this assumption, the SCM is not finitely identifiable.
Theorem Under Assumption 1 SCM e defined in ① with Gaussian confounders is not finitely identifiable if and only if the observed vector dependent. Moreover, if the observed vector is independent, then SCM C is uniquely identifiabl.
Proposition 1 SCM E defined in ① with Gaussian confounders and dependent observed vector can be modeled as another SCM without confounders that has the same PDF for the observed variables and vice versa.
Proposition hholds even if SCM e satisfies Assumption
As discussed earlier, Assumption is not restrictive for the sufficiency part of Theorem | as each noise can be decomposed into another noise and confounder component. This result holds even if the number of confounders are restricted to be less than the number of observed variables, which is often assumed in practice.
Proposition 2 SCM defined in ① with Gaussian confounders and dependent observed vector is not finitely identifiable. The result remains valid if the number of confounders is known to be less than the number of observed variables.
LINEAR SCM WITH NON- NON-GAUSSIAN CONFOUNDERS
We present the sufficient conditions for finite identifiability of the SCMs when the confounders satisfy the following assumption.
ki are non-constant, non-Gaut Gaussiasn, and cannot be decomposed into finite random variables where any Gaussian. In other words, for any Y and Y for which 6H, (t) Øy (t)oy (t), neither Y nor Y is Gaussian.
Assumption Confounders H; 1,....k;
The enumeration of the confounders can be done arbitrarily, as for any enumeration, the columns of matrix B (resp. M) can be reordered to maintain the consistency of the product BH (resp. MD). which encapsulates the confounders' impact the observed variables. Therefore, to avoid complications with confounder enumeration, we assume the following without loss of generality.
Assumption The columns of M are sorted in the ascending lexicographical order:
Assumption The columns of M are linearly independent.
Intuitively, this assumption means that the confounders' "impacts" on the observed variables are independent, and hence, distinguishable. The following is the main result of this section.
Theorem Under Assumptions confounders, $.55
n-dimensional linear SCM C(M, Q) defined by ( with
1. is finitely identifiable, and the size of the equivalence class is most n!!
5

---

Published as a conference paper at ICLR 2025
2. for every SCM (M' Q') in this class, it holds that M' = M and Q' = p for some permutation matrix P where Qp is the lower triangular matrix obtained from the Cholesky decomposition of PQQ" PT, and
3. the CF of the confounder vector is the same in all SCMs in the equivalence class and is given by
(t) = 0g xx(M (T)
(3)
o (M Tt))
where dx(t) denotes the CF of a standard k-dimensional Gaussian random variable, and X is vector of informative observed variables. whose corresponding rows in M and Q form the matrices M and Q, respectively.
As described in Theorem 2. each matrix P corresponds to SCM C' that is equivalent to the SCM C. In what follows, we examine how matrix P affects the causal structure of SCM C'. To this aim, consider the following definitions. Due to the uniqueness of the Cholesky decomposition, each permutation matrix P in Theorem Sacoorem@coran corresponds to exactly one SCM C'. This uniqueness guarantees the existence of function that maps P to e.
Definition 7 Consider SCM ((M.Q) Q) with ls confounders, where S h S n. Let Assump- tions] 2 to Ahold. Define the function Fe that maps a permutation matrix to its corresponding 2 Part 2, i.e., Fe(P) C, where (M, P P.P.Pppppp P) with Qp being the lower triangular matrix obtained from the Cholesky decomposition of PQQ"P..
SCM C' in the finite equivalence class of C, described in Theorem
Definition The "order" of entries XI,..., Xn in a vector X = = X,]" is X1
X
The "permutation order" Op(X) for n permutation matrix P represents the order of variables X in PX.
The following theorem presents the conditions under which the permutation matrix leads to a new SCM e and subsequently shows how P affects the causal order of C.
Theorem Consider SCM C(M, Q) defined by ② with confounders, S k: S n, and let Assumptions 2 to hold. Let P be permutation matrix with permutation order (p(X) and (P) = Then,
1. E and E' are distinct SCMs if and only if OX() De: and
2. the permutation order (p(X) an element of the set Der.
For the proof of part (1), we need the following lemma.
Lemma Consider SCM C(M, Q) defined by ② with k confounders, 151 S n, and Assump- tions 2 to 7 hold. Let P be permutation matrix with permutation order Op(X (X) and (P) = C.
Then, (MM Q) and E (M,, Q') are distinct SCMs (i.e., Q * Q') if and only if PQP is a lower triangular matrix.
Corollary SCM ((M, Q) defined by 2 satisfying Assumptions
2 to and with k confounders,
1 S n, is uniquely identifiable if the causality order specified.
Definition 9 (Partial causal (structure) order) A partial causal order for SCM C is an order Xi > ...Xm where X Xm partition the observed variables {X1..... ..,), and there is no path from any node in X, node in X, in the induced DAG for every i.j (1.2....,m)) m))
Corollary 2 Consider SCM C(M, Q) defined by (2) satisfying Assumptions 2 to 4 with k con- founders, < k S n. If a partial causal order X1 ... Xm is specified, then the size of the equivalence class of E is at most m |
Define an isolated observed variable as an observed variable that is not caused by any other observed variable.

---

Published as a conference paper at ICLR 2025
Definition 10 (Isolated observed variable) Given SCM ① observed variable X, is said to be isolated if the 1th row and ith column of A are zero.
The next corollary implies that an SCM is uniquely identifiable if all observed variables are influenced only by unobserved variables, i.e., confounders and noise.
Corollary 3 SCM C(M, Q) defined by ② satisfying Assumptions 2 to and with k confounders, 1 S n, is uniquely identifuble if and only if all observed variables are isolated.
Definition 11 (Isolated variable set) Given SCM ① an observed variable set (Xig Xim is said to be isolated if Aab- = Aba- = 0 for all a E (il,-..,ho, bm) and b & (i1....,ho 1m
Corollary Consider SCM ((M,Q) defined by 2 satisfying Assumptions 2 to and with confounders, 1 1 k S n. If E consists of isolated variable sets Xy,..., Xm, then so is every other SCM in the equivalence class of C. Moreover, the size of the equivalence class is at most ms &
COMPARISON OF IDENTIFIABILITY RESULTS FOR DIFFERENT NOISE AND CONFOUNDER DISTRIBUTIONS
Building on the findings of this article and (Pavan & Miranda 2018), in the following remarks, we compare the identifiability of SCM (MM, Q) in different scenarios, depending on whether noise and confounders follow a Gaussian distribution.
Remark 2 (Unique identifiability) Consider SCM C (MM Q) with equations defined in and with i confounders. Then
Gaun-aausiaan noise and confounders: SCM E is identifiable up to the permutations of the matrix [,, Q Paaan & Miranda 2018), i.e., C. is finitely identifiable. Unlike in (Pavan & Miranda 2018), the scaling of [ Q] changes the observed PDF, because the covariance matrices are assumed to equal the identity matrix. Also, permutations are acceptable only if they preserve the structure of the Q matrix, specifically, Qij Qji = and Qus + 0 for n,, j E 1,2.... ,...,, i & j. Now if all "aacepteble" permutation matrices result in the same
M, Q) SCM E is uniquely identifiabl.
Gaussian noise and non-Gaussian confounders: SCM C is finitely identifiable under Assumptions too I and 1 S k S n. All observed variables being isolated is the necessary and sufficient condition for unique identifiabilit.
Gaussian noise and confounders: SCM C is not finitely identifiable. Under Assumption ! observed variables are mutually independent is the necessary and sufficient condition for unique identifiability.
Suppose the causal order is known, for example, through expert knowledge. Would the SCM then be identifiable? The following remark answers this question.
Remark 3 (Unique identifiability given the causal order) Consider SCM C(M, Q) with equa- tions defined in 2 and with k. confounders. Assume that the causal order of SCM C is known. Then
Non-Gaussian noise and confounders: SCM E may or may not be uniquely identifiable;
Gaussian noise and non-Gaussian confounders: SCM e is uniquely identifiable; Gaussian noise and confounders: SCM E is not finitely identifiable for dependent observed variables.
In certain cases, even the SCM itself not identifiable, determining the causal order can still be of value. The following remark outlines the conditions under which this may be possible.
Remark 4 (Identifiahility of the causal order) Consider SCM C (MM, Q) with equations defined in 2 and with k confounders. Consider the case where SCM E is not uniquely identifiable. Then for
Gan--Gassian noise and confounders: The causal order of SCM may or may not be
unique in its equivalence class;
7

---

Published as a conference paper at ICLR 2025
Gaussian noise and non-Gaussian confounders: The causal order of SCM C is not unique in its equivalence class;
Gaussian noise and confounders: The causal order of SCM C is not unique in its equiva- lence class.
The third parts of Remarks and are proven in the appendix. The first parts of the remarks, i... non-Gaussian noise and confounders, are illustrated by the following SCMs:
[M) 1
1
0
07
1 0
- 1 1
0
1
0
M2 Q2
0
1
1 0
[M3. Qal - 0
M Q.
There no acceptable permutation for [M1, Q1] to result in new matrix [M, Q), implying that the corresponding SCM is uniquely identifiable. For [M2 Q2), the only acceptable permutation is to swap the first and second columns, which leads new SCM but with the same causal order. This demonstrates two different SCMs with the same PDF and causal order. In the case of [Ms. Qa). the causal order is X1 > X2 > X3. Permuting [M4. Qa) is acceptable and results in an SCM with new causal order X2 X1 X3.
6 FINDING EQUIVALENCE CLASS AND NUMERICAL EXAMPLES
The following algorithm illustrates how an equivalence class is obtained for specified SCM C(M, Q) that satisfies Assumptions 2 The computational complexity is dominated by operations on matrices. The most intensive steps-matrix multiplication (Σ = QQ" ), Cholesky decomposition of Ep. and inversion of Q' Q'-cach require ( time. Thus, the overall complexity is O(n").
Algorithm Finding the SCM equivalent to SCM and corresponding to permutation matrix P
Require: matrices Q, M, and P
M' +M
Σ + QQ
Σ, + PEPT
E6 P < Cholesky decomposition (Ep)
Q' < PT
if Q' Q then
print This does result in distinct SCM.
else
C' 0nxn
for i = 1 n do
C² + Q22
end for A' In C'Q'-1
B' + (In A'
return A', C" end if
In the following, present two examples. First, discuss 2-dimensional SCM, also presented in (Hoyer et al., 2008; Salehkaleybar et al.) 2020), and illustrate the identifiability of the SCM under different distributions for the noise and confounders.
Example Consider the SCM defined by
Xi H /2Z1.
X2 H + X1 + Zz.
where F[X?] = F[X1X2] = 4, and 2 = 7, We examine this SCM in three different scenarios to determine whether there are other SCMs with the same PDF
(1) All variables are non-Gaussian: Then under the assumption that H' = 21, Z = H, and Za Zzy the following SCM has the same joint PDF over the observed variables:
X /2H' Z
X = - /2H' 2X Zzg
8

---

Published as a conference paper at ICLR 2025
(2) All variables are Gaussian: There are infinite SCMs e with the same joint PDF, defined
{ b1 + 012 +, X2 = byH' + a21 + +z222
e'
where 012.021 O. For P(X') = P(X) to hold, it suffices that either 012 0. |b < v3, 3a21 byb1 4, and b3 3a2) 20mibib2 < 7 or 021 0, [by] < V7, Ta12 + beb1 4, and bi + 7aīz + 2012bbbb,
3. It can be verified that there exist infinitely many parameter values that satisfy these conditions, implying that there are infinitely many SCMs, confirming Theorem) 7 Moreover, setting 012 b1 b2 0, 021 = =/3,, results in o = and cj 5/3. That is, an SCM without confounders can also be obtained, which consistent with Proposition 7
(3) Gaussian noise and non-Gaussian confounders: Let Assumption be in force. Then in view of Theorem 2 there at most one other SCM with the same joint PDF, which has a different causal order X2 X1, and equals the following (which can be obtained from Algorithm 7
x I//H' + 2/332/ + /2/37i. X2
C'
2H + /3Zz.
The next example a 3-dimensional SCM satisfying Assumptions The example illustrates given an SCM e, when a permutation matrix P results in a distinct SCM C in the equivalence class of C.
Example 2 Consider the following SCM:
0
1
2
0
0
E:
X
=
0
0
X
+
2
H +
1
Z,
(4)
0
--1
1
0
0
v33
11
2
0
0
4
M (I--))
2
2
3
Q = (Is (13-A)- -C-
2
1
0
E
QQ
4
5
0
3
2
2
0
v3
7
follows that D. (X1> X2
X
X1 Xa N2). Clearly, Assumptions) Bnnd 4 hold. Let
Assumption to also be in force. Since n = 3, there are six permutation matrices corresponding to different causal orders:
7
0
0
1
07 0
0
0
11
7
0
07
0
17
7
1
0
P
0
1
0
P
1 0
P3
0
0
P4
0
0
Ps
1
0
0
P
0
0
0
0
1
0
0
0
0
0
0
By applying Algorithm to each permutation matrix, the following results are obtained. The numbers rounded to two decimal places:
(I) P1: According to Proposition 3
this permutation matrix implies the permutation order Op, X1 X2 > X3. The algorithm outputs the same SCM as in 4 This consists with Theorem 3 as
Op, E De.
(2) P2 The corresponding permutation order is Op, X2 algorithm outputs the following distinct SCM:
X1
X3. Thus, Op & De. The
0
0.8
-0666
0.6
-0.6
1.4
00.89
0
0
:'
X'X
1
X'
2
3
H'
+
0
2.24
0
Z'.
1
0
0
1.73]
(3) Ps The corresponding permutation order Ops algorithm outputs the following distinct SCM:
X3 >
X2 >
X1. Thus, Ops & De. The
0
0.63
0.217
0.26
0.89
1.32
T0.79
0
0
c X
0
0
0.57
X'
+
2
0.29
1.85
H'
1.65
0
Z'.
0
0
0
3
2
0
0
2.65
(4) PA The corresponding permutation order is Op, does not result in distinct SCM.
X > Xg > X2. This, Op, E De, which

---

Published as a conference paper at ICLR 2025
(5) Ps: The corresponding permutation order is X3 outputs the following distinct SCM:
X1 > X2. Thus, Ops & De. The algorithm
0
0
0.57
1
-0.71
-0.147
1.31
0
0
C3S X
1
0
X
+
2
H'
0 1
0
Z'
0
0
3
2
0
0
2.65
(6) Pa: The corresponding permutation order is X2 > X3 > outputs the following distinct SCM:
X1. Thus, Op & De. The algorithm
0 0.63
0.211
0.26
-0.89
-1.2
T0.79
: X = 0 0 0
0
X
2
H' +
2.24
Z'
0.8
1.6
1.4
-0.4
1.95
Therefore, the 3- 3-dieeniional SCM in this example is identifiable with an equivalence class size of five.
CONCLUSION
We studied the identifiability of SCMs from observational data, i.e., sampled from TP(X), focusing scenarios with Gaussian and non-Gaussian noise and confounders. When both noise and confounders Gaussian, it is impossible determine the causal order solely from observational data. This scenario often results in the existence of infinitely many SCMs with the same causal order and same PDF of observed variables P (), confirming that Gaussian SCMs are not finitely identifiable.
In contrast, in scenarios where all variables are non non-Gaussian it was already known from the literature that the SCM is identifiable up permutations of the structural matrices [M. Q] (Pavan & Mirandal 2018 Friksson & Koivunen 2004 Tharwat 2021), resulting in finite identifiability. Depending on structure of [M, Q), the equivalence class may either include a unique SCM, multiple SCMs with different causal orders, multiple SCMs sharing the same causal order.
For Gaussian noise and non- -an-aassi confounders, we showed that the SCM is finitely identifiable. More importantly, the SCM is uniquely identifiable once the causal order is known; however, determining the causal order is not possible unless the observed variables are isolated.
Looking ahead, we acknowledge several assumptions that restrict the scope of this study, such as the SCM being linear and the confounders lack Gaussian components. Additionally, while we discussed deriving other SCMs from known SCM, we did not show how to estimate that "first" SCM from observational data. Future research should aim to relax these constraints to investigate more realistic scenarios.
REFERENCES
Jeffrey Adams, Niels Hansen, and Kun Zhang. Identification of partially observed linear causal models: Graphical conditions for the non-gaussian gaussian and heterogeneous cases. Advances Neural Information Processing Systems, 34:22822 22833, 2021.
Raj Agrawal, Chandler Squires, Neha Prasad, and Caroline Uhler. The decamfounder: Non-linear causal discovery in the presence of hidden variables. arXiv preprint arXiv:2102.07921, 2021.
Animashree Anandkumar, Daniel Hsu, Adel Javanmard, and Sham Kakade. Learning linear bayesian networks with latent variables. In International Conference on Machine Learning, pp. 249-257,
PMLR, 2013.
Hojbjerre Andersen and Eriksen Sorensen. Linear and graphical models: for the multivariate complex normal distribution. Springer Science & Business Media, 1995.
R. Cai, Z. Huang, W. Chen, 7. Hao, and K. Zhang. Causal discovery with latent confounders based on higher-order cumulants. In Proceedings of the International Conference on Machine Learning (ICML). PMLR, 2023,
Ruichu Cai, Feng Xie, Clark Glymour, Zhifeng Hao, and Kun Zhang. Triad constraints for learning causal structure of latent variables. Advances in neural information processing systems, 32, 2019.
10

---

Published as a conference paper at ICLR 2025
Wei Chen, Kun Zhang, Ruichu Cai, Biwei Huang, Joseph Ramsey, Zhifeng Hao, and Clark Glymour. Fritl: A hybrid method for causal discovery in the presence of latent confounders. arXiv preprint arXiv:2103.14238, 2021. 2021.
Alexander D' D'mourr. On multi-cause causal inference with unobserved confounding: Counterexam- ples, impossibility, and alternatives. arXiv preprint http:/992..028000 2019.
Jan Eriksson and Visa Koivunen. Characteristic-functiie based independent component analysis. Signal Processing, 83(10):2195-2208 2003.
Jan Eriksson and Visa Koivunen. Identifiability, separability, and uniqueness linear ica models. IEEE signal processing letters, 11(7):601-604, 2004.
Benjamin Frot, Preetam Nandy, and Marloes H Maathuis. Robust causal structure learning with some hidden variables. Journal of the Royal Statistical Society Series B: Statistical Methodology, 81(3): 459-487, 2019.
Christophe Giraud and Alexandre Tsybakov. Discussion: Latent variable graphical model selection via convex optimization. The Annals of Statistics, 40(4):1984-1988 2012.
GH Golub and CF Van Loan. Matrix computations, johns hopkins studies in math. Sciences, Johns Hopkins University Press, Baltimore, 1996.
Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, Cambridge,
UK, 2012. ISBN 978-0521548236.
Patrik O Hoyer, Shohei Shimizu, Antti 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.
Aapo Hyvärinen and Erkki Oja. Independent component analysis: algorithms and applications.
Neural Networks, 13(4-5):411 4-00, 2000.
Aapo Hyvärinen, Ilyes Khemakhem, and Ricardo Monti. Identifiability of latenl-variable and structural-cquation models: from linear to nonlinear. arXiv preprint arXiv:2302.02662, 2023.
Xiu-Chuan Li, Kun Zhang, and Tongliang Liu. Causal structure recovery with latent variables under milder distributional and graphical assumptions. In The Twelfth International Conference on Learning Representations, 2024.
Eugene Lukacs. A survey of the theory of characteristic functions. Advances in Applied Probability, 4(1):1-37, 1972.
Christopher Nowzohour, Marloes H. Maathuis, Robin J. Evans, and Peter Bühlmann. Distributional equivalence and structure learning for bow-free acyclic path diagrams. Electronic Journal of Statistics, 11(2):5342 5374, 2017. doi: 10.1214/17-ESS1372. URL http:/as:///i..oo/o///o 1214/17-EJS133
Flávio RM Pavan and Maria D Miranda. On the darmois-skitovich theorem and spatial independence in blind source separation. Journal of Communication and Information Systems, 33(1), 2018.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. The MIT Press, 2017.
Anastasia Podosinnikova, Amelia Perry, Alexander S Wein, Francis Bach, Alexandre d' Aspremont, and David Sontag. Overcomplete independent component analysis via sdp. In The 22nd Interna- tional Conference on Artificial Intelligence and Statistics, pp. 2583-2592. PMLR, 2019.
Saber Salehkaleybar, AmirEmad Ghassami, Negar Kiyavash, and Kun Zhang. Leaaning linear non-gaussian causal models in the presence of latent variables. The Journal of Machine Learning Research,
2020.
Shohei Shimizu. Lingam: Non-gaussian methods for estimating causal structures. Behaviormetrika, 41:65-98, 2014,
11

---

Published as a conference paper at ICLR 2025
Shohei Shimizu, Patrik O Hoyer, and Aapo Hyvärinen. Estimation of linear non-gaussian acyclic models for latent factors. Neuroconputing. 72(7-9):222--0223 2009.
Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, prediction, and search. MIT press, 2000.
Chandler Squires, Annie Yun, Eshaan Nichani, Raj Agrawal, and Caroline Uhler. Causal structure discovery between clusters of nodes induced by latent factors. In Conference Causal Learning and Reasoning, pp. 669-687. PMLR, 2022.
Anisse Taleb and Christian Jutten. On underdetermined source separation. In 1999 IEEE International Conference Acoustics, Speech, and Signal Processing. Proceedings. ICASSP99 (Cat. No. 99CH36258), volume 3, pp. 1445-1448. IEEE, 1999.
Alaa Tharwat. Independent component analysis: An introduction. Applied Computing and Informat- ics, 17(2):22-224, 2021.
Gautam Tripathi. matrix extension of cauchy-schwarz inequality. Economics Letters, 63(1): 1-3, 1999.
Sam Witty, David Jensen, and Vikash Mansinghka. Sbi: A simulation-based test of identifiability for bayesian causal inference. arXiv preprint arXiv:2102.1 11761, 2021.
Anpeng Wu, Kun Kuang, Ruoxuan Xiong, Bo Li, and Fei Wu. Confounder balancing for instrumental variable regression with latent variable. arXiv preprint arXiv:2211.10000 2022.
Feng Xie, Ruichu Cai, Biwei Huang, Clark Glymour, Zhifeng Hao, and Kun Zhang. Generalized independent noise condition for estimating latent variable causal graphs. Advances in neural information processing systems, 33:1 -891199994 2020.
Feng Xie, Biwei Huang, Zhengming Chen, Yangho He, Zhi Geng, and Kun Zhang. Identification of linear non-gaussian latent hierarchical structure. In International Conference Machine Learning, 24370-24387 PMLR, 2022.
Feng Xie. Yan Zeng, Zhengming Chen, Yangbo He. Zhi Geng, and Kun Zhang, Causal discovery of 1-factor measurement models in linear latent variable models with arbitrary noise distributions. Neurocomputing. 2023.
Yuqin Yang, Mohamed S Nafea, AmirEmad Ghassami. and Negar Kiyavash. Causal discovery in linear structural causal models with deterministic relations. In Conference on Causal Learning and Reasoning, pp. 944-993. PMLR, 2022.
A APPENDIX
Definition 12 (Equal in distribution) Two real random variables X and Y. with the same state space are equal the distribution sense, denoted by X Y, for any measurable set the state space, P(X E A) PP A).
Definition 13 (Characteristic function) Define (x the Characteristic Function (CF) of (X1,X2, X,,..., X,) as
X t...
tn) = E(x..aamxxa) exp (J(Xit + X2t2 +... +xatt)))
(5)
where j2 -1
Remark 5 The CF of m independent random variables Y,,... .i...,,m Ym can be obtained as the product of each random variable CF. (t = II Φy; (t+).
Remark The CF of the sum of independent random variables Yı,...,
,,.....,,,, Ym can be obtained the
multiplication of their CF's. Therefore, the CF of Em Y; obtained ds(()) II Φy; (t).
12

---

Published as a conference paper at ICLR 2025
Lemma 2 For random vectors X and Y AX + (where i constant matrix and b a constant vector), (t) explib (A where j² -1 (Andrsen & Sorensen 1995).
Lemma 3 Every positive definite matrix can be written as the sum of another positive matrix and diagonal positive definite matrix.
Proof. Consider a positive definite matrix Σ, and denote its eigenvalues be denoted by X (x which are all positíve. Choose positive number d such that
< min (=) 2
Form the diagonal matrix D with entries d on the diagonal. Define S = D. We show that S is positive definite. First, since Σ symmetric and is diagonal, S is also symmetric. To show that S is positive definite, consider its eigenvalues. Second, the eigenvalues of S are {;(E) - d (Horn & Johnson 2012). Since < m (Z). it follows that (5) for all (1.2.... n Thus, 5 is positive definite matrix.
Lemma 4 Let L be the Cholesky factor of a positive definite matrix S. Define matrix B as the collection of those columns of C that have more than one non-zero element, in an arbitrary order. T is a non-negeenee -eg-tivte diagonal matrix.
Then, S = BBB
Proof. Let c= LL Lo...... -.l. where L, denotes the ht column. Then LC = E Since S is positive definite, all diagonal entries of are non-zero. Now, let denote the indices of the columns with more than one non-zero elements. Then BB = Eier LiL: Consequently, S = CC -BB = EjØT راري Since each column Lj. of T. has exactly one non-zero entry, located the jth row, LnLe is matrix with all zero entries except for the jth column and row, which positive entry. Thus, the summation of رارر j & T, is non-negative diagonal matrix. O
Proof of Theorem [ Consider the covariance matrix of the observed vector, denoted by Σ F[XX Being positive definite, Σ can be decomposed as Σ D + S, where D positive definite diagonal matrix and S is positive definite matrix, according to Lemma 3
(sufficiency) The dependent observed vector implies that Σ is not diagonal. Thus, cannot be diagonal. Consider an arbitrary E R that meets two conditions: (i) 0 < < min I...., (D:) and (ii) S + eIn is not a diagonal matrix. Define SCM e as
where C and B are defined as follows. Let L denote the Cholesky factor S + el,, The matrix B' is formed by selecting all columns of L that have at least two non-zero elements. Let be the number of such columns in L implying that each confounder causes at least two observed variables in C Then the dimension of B is n x m where m is necessarily the same k, the number of confounders in C. Due to non-diagonality of - e/n, it follows that 1 S m, which guarantees the existence of B Define S. = S + eln B ( It is easy to verify that Se is diagonal matrix with non-negative entries (Lemma 4). Therefore, the matrix D + S' eI, is positive definite diagonal matrix due to the upper bound on c. Define C as the Cholesky factor of D + 5' -I,..
Now we show that the covariance of observed vector under e' is the same as that under C. Given the independence of the noise vector Z and the confounder vector Ht, the covariance matrix of the equals
observed vector = E (X
Σ (B") + +CCCT
(BB (D 5 -c,)
B (B) + -5 5-B -BB(B)
(6)
=
(7)
where (6 follows from the definition of $e. As X and X are 7ero-mean Gaussian random variables, the equality their covariance matrices implics that X X. This completes the proof as there are infinitely many that meets the aforementioned two conditions.
13

---

Published as a conference paper at ICLR 2025
(necessity) If the observed vector X in the SCM CAA, C) is independent, then the covariance matrix Σ of X is diagonal. This implies that A a zero matrix. Similarly, Assumption | that B is zero matrix. Hence, C' can be uniquely identified the Cholesky factor of Σ.
implies
Proof of Proposition | Denote SCM C by C(M, ((M,)). Consider confounder-free SCM CO, Q') where Q' is the Cholesky factor of MM + QQ* i.e.,
Q'Q"T TQ"=MM'' +QQ".
(8)
On the other hand, According to (2) and Given the independence of noise and confounder case, the covariance matrix of the observed variables in equals MM + +QQ and equals Q'Q'T in e. In view of (8), the two covariance matrices match, implying equivalence in distribution of X and X' as they are zero-mean Gaussian variables, completing the proof. A second proof is provided in the following, by considering Gaussian SCM e" in the form of (T) (rather than (2) and obtaining
(A', O, C") for e. To prove the converse of proposition, we can follow the proof of the sufficiency of Theorem] by letting M O.
Second proof of Proposition 1 Consider SCM CA, C). Without loss of generality assume that matrix A is lower triangular as this can be obtained by re-ordering the observed variables. we prove the proposition for B * 0. Consider the following Gaussian SCM, denoted by (,,,,,,, without confounder variables:
: A'X' + C'Z',
where A' is lower triangular matrix with zero diagonal entries whose entries below the main diagonal in the (i + 1)th row equals A = y+1 (M")) for i 2 1, where
D E[[ I X.Il.
X.]] (9)
Due to the dependency among the observed variables, E|XX"] is not diagonal. Consequently, the matrix A' is non-zero. Also, let C' be diagonal matrix whose diagonal entries are defined as follows for i 2 1:
C441111 F[X (E
(E+
(10)
and C E(X7). Due to the Cauchy inequality Tripathi 1999 SCM C" is well-defined. Let E' denote the covariance matrix of X" under SCM e'. We show by induction that hhen Mnn For i = I E'11, For every Then, for i + 1, it holds that
Cy 141.44 is positive, and therefore,
assume Eús Σd
1
E|X [ X(I]
E X
X1 X [X x1I E XII
A ni +0
(b)
(
i
(11)
-1+1
(12)
where (a) holds due to the fact that X Xi,..., X depend only on Zj,... 7 which are independent
of Zip by definition and therefore, E 1/ [X X
= 0, Also, (b) is due to the induction
assumption. Therefore, y git Now, we prove that E[X = E E for i = I,...,
F[x = F. (X X + ('4115474411
A hi 1
+ (
=EEt (
E| 1 -(E+)) -I
= =
(13)
Thus. 12 and (33) imply 11111 = L++, which completes the induction step. Therefore,
mm
Σ nm
On the other hand, Gaussian variables X and X' are defined mean. Hence,
14

---

Published as a conference paper at ICLR 2025
the mean and covariance matrices of the observed variables under SCM e match those under e, implying X' _ X.
Proof of Proposition 2 In the proof of Theorem under Assumption we showed the existence of a vector H E R", where m represents the number of columns in L with more than one non-zen entry. Matrix L was derived from the Cholesky decomposition. On the other hand, being lower triangular, every Cholesky factor admits at most n - 1 columns with more than one non-zero entry. Consequently, all SCMs considered in this proof satisfy identifiable even when the number of confounders is less than the number of observed variables.
n, indicating that the SCM is not
Now, if Assumption | is violated, there exists a confounder-free SCM equivalent to SCM e. By decomposing
Gaussian noise of this SCM into two subcomponents, one for the confounder, one for the noise variable which can happen by infinitely different ways- new equivalent SCM with n 11 Gaussian confounders is generated. D
For the proof of Theorem 2 we need the following lemmas.
Lemma 5 (based on Paavan& & Miranda] 2018), Theorem 3) Let U1, U.... Un be real and mu- tually independent random variables. Define V1 and V/2 as two real random variables, each equal to linear combination U1, U2,.. Un in distribution sense,
Vi - U,U1 + + anUn:
(14)
V22 - UU + +... bn
where a, and for 1....,n n are real constants, If 11 and V2 are independent, then for each index i such that abb; + it follows that U; must be either a constant Gaussian random variable.
Proof of Lemma 5: This lemma is similar to Theorem in (aavan & Miranda 2018) with the key difference that the theorem assumed equality rather than equality in distribution sense. There, using the equality, vv t2) = II Pv (t + t2b;) is concluded in the beginning of the proof, where Lv1, v. (41,4g (2) the joint CF of V1 and V2, and &e,, (1) is the CF of U,. Here, we can conclude the same using the equality in distribution and the independence of U.'s. Therefore, the rest of the proof of this lemma follows the same arguments as those in Theorem in (Pavan & Miranda, 2018).
Let U. be a vector of m mutually independent random variables, none of which are Gaussian or constant, with covariance matrix I Let V. be vector of n. mutually independent random variables with covariance matrix In. V & RU, then R E Rxx has orthogonal rows, and each column of R has at most one non-zero entry.
Lemma 6
Proof of Lemma 6 Given V d RU, have E[VV = REJU RR. Since V. and U have identity covariance matrices. RR = I,. Thus, R has orthogonal rows. Now. to show that each column of R has at most one non-zero entry, we proceed by contradiction. Suppose that there exists column of R. say the jth with at least two non-zero entries. Then U, appears in the linear combinations of at least two independent random variables in V. This contradicts Lemma 5 as then Uj must be Gaussian constant.
Lemma 7 Let Σ E Ruxn be a positive definite matrix. There are at most n! different matrices Q such that Σ QQ where Qi 0 for every i,j E {1, n.). i + j. For every matrix Q, there exists a permulation matrix P such that Q P Q P where Qp is the lower triangular matrix obtained by the Cholesky decomposition of PEPT.
Proof of Lemma Due the structure of Q, there is a permutation matrix P that reshapes Q as lower triangular matrix denoted by Qp. i.e., Qp = PQP Due to the fact that P P = In, we P
have Q = =PT PTQ.P. which in view of Σ QQ yields:
Σ QQT
3 Σ = PT TTQPT
PEPT = QT
15

---

Published as a conference paper at ICLR 2025
The last equality is the Cholesky decomposition of PEPT since Qp is a lower triangular matrix. The Cholesky decomposition for real-vate valued positive-definite matrices is unique (Golub & Van Loan 1996). Therefore, corresponding to every permutation matrix P. there is unique Cholesky factor of PEP or equivalently a unique Qp = PQPT. Given that there are n! permutation matrices P. there are n! matrices Q P Qp satisfying Σ = QQ", although some may be identical. Hence, there most n! distinct matrices Q satisfying Σ QQ
Proof of Theorem Consider the following two SCMs E and EL where X x _ X".
(15) consider the causal structure order X1 > X2 > Xn, for SCM C. Therefore, Q is a lower triangular matrix. The proof consists of two steps. First, we show that M M'. Second, we show the existence of at most n! noise matrices Q'
C: X MH+ + QZ,
M'H +''Z.
Without loss of generality,
Step Due to Assumption 4 the rank of matrix M is Therefore, for an arbitrary mh row of M, there are 1 other rows that together with row m, form full-rank & x sub-mu matrix denoted M. Denote the vector of variables corresponding to these rows by X, which form an informative variable set. The equality P(X)) PXX')) implies Φx (t) = (t), where [t1, f2,-.., tt]T, because two random variables have the same CF if and only if they have the same PDF Now, considering Remark have:
and the independence of noise and confounders,
(MH(t) = bw (t)
(16)
Due to Assumption 2 the non-Gaussian (resp. Gaussian) components on both sides must match. Thus,
ΦM (t) = bM (t).
(17)
Constraining this equation to the informative observed variables X yields o MH (1) PT'H'' (L)
This is equivalent to ΦH (M t) ow 6M t), due to Lemma For an arbitrary value of w E R
set = (M )-'w.. Therefore,
( (M T. )- ou (M (M )-'w)
ΦH (H(ww) = ΦH (M (M' (M T -ww)
(18)
H d M M'H'.
Define R E R as R M M'. In view of ( and Assumption 2 the conditions of Lemma 6 are met for V = H and U = H' Thus, R is full row rank, implying that k'' 2 k. Now
show that 1/' = k. According to the definition of R, M' = MR, which in view of {18) results in & (w()) T H Ruc). Thus, R is independent of m, resulting in M' M R. row m was arbitrary. Now, if K" > k. the columns of R are linearly dependent. Since M' = M, the columns of M' are also linearly dependent, which contradicts Assumption 4 Thus, k' k. Hence, R is permutation matrix as it is full rank with orthogonal rows and each of its columns have at most one none-zero entry. On the other hand, Assumption 3 implies that both M and M are lexicographically sorted. Hence, R is the identity matrix and M' M.
Step In view of (16), Assumption 2 implies
(Qz(() Φ z
(19)
where Z and Z' zero-mean Gaussian random vectors of the same dimension Therefore. (19 is
equivalent the covariance matrices Σ = QQ and Σ' Q'Q' being equal, i.e., Σ Σ' Now,
it follows from the definition of SCMs (see T and (2) that Σ and Σ' are positive definite matrices.
Moreover, Q as well as Q' satisfy Q5 and D = 0 for every i, E {1, 2.... n). i # j.
Therefore, according Lemma 7 there are most n! possible Q' matrices.
Now, we prove the third part of the Theorem. Substituting M MM' = I in 18 D (w) Additionally, (15) implics that
t (w))
M
x H M QZ.
16

---

Published as a conference paper at ICLR 2025
The proof is complete considering the independence of noise and confounders and according to Remark and Lemma
Proof of Lemma The following equations hold:
Q' = Q
P QpP=Q
(20)
Qp PQP
(21)
PQP is a lower triangular matrix
(22)
where (20) holds due to Lemma
21 is result of PPT = In, and (22 holds in the forward
direction since Qp p is the lower trannulaar matrix. Now, we prove the reverse direction of (22). It is
clear that ( (PQP) P (PQPT)T PEP Therefore, if PQPT is lower triangular matrix, it is
exactly the result of the Cholesky decomposition of PEP According to Lemma 7 Qp p is also
derived from the Cholesky decomposition of PEP Therefore, due to the uniqueness of Cholesky decomposition, Qp PQP
The following result is straightforward.
Lemma 8 Consider a vector of random variables X "i,...,,,]] A Permutation matrix P has a one-to-one relationship with the permutation order (X)), Le, P ts Op(X), such that P.j = 1 if and only if X3 is located at the t row in PX.
Proof of Theorem 3 (PART 1): and C' are distinet SCMs if and only if
PQP is not lower triangular matrix
(23)
+ Ji,j E
<, )ij #0 + 3i, j. k, n3) 1, = = -, Q. #0
(24)
(25)
+ Or $ De
(26)
where (23 follows from Lemma D and 24 follows from the definition of a lower triangular matrix.
The properties of the permutation matrix lead to (25) where in the 7th row of P. only one column k is non-zero and equal to one. To show that (26 holds, note that according to Lemma 8 Psx = 1 and Ps = imply that X and X are ranked Td and jth respectively, in the causality order Op. On the other hand, since < X precedes X in Op, i... X > -X/. Furthermore, Qu * 0 indicates that noise variable Zi appears the equation of X₂ in 2 for SCM e. This implies the causality order X1 > X in every causality order in De. Therefore, Op & De.
(Part 2) Multiply in both sides of (2 to obtain
PX PMH+ (PQP))(2))
(27)
Here, PQPT is not necessarily lower triangular matrix. Now since SCM e' shares the same M and only differs in Q', it holds that
PX' PMH + (PQ'
(28)
Also, from Theorem Q' = PT O yielding
PX' = PMH + (PZ')..
(29)
Since Qp is lower triangular, the order defined by PX' is a valid causality order of C'. On the other hand, the order defined by PX' is the same as the permutation order Op(X), completing the proof.
Proof of Corollary [: The causality order determines the permutation matrix P uniquely. Conse- quently, e' (F( is determined uniquely by the permutation matrix P.
O
Proof of Corollary 2 In view of Theorem 2 Part 2, every SCM in the equivalence class of C(M, Q) can be written as C'MM, PT Q with Qp being the lower triangular matrix obtained from the Cholesky decomposition of PQQ PT. for some permutation matrix P. By Theorem 3 the causal order set of each SCM C' C'MM, P QpP) includes the permutation order Op. On the
17

---

Published as a conference paper at ICLR 2025
other hand, SCM e' respects the specified partial causal order. Consequently, valid permutation matrix P rearranges the rows of the observed variables X, only within X; itself. The number of such permutations, and in turn the size of the equivalence class, is given by I |&|!!.
Proof of Corollary 3 (sufficiency) Since all observed variables are isolated, matrix Q is diagonal. Therefore, for any permutation matrix P. matrix PQP is diagonal, and hence, also lower triangular. Consequently, for any P. SCMs e and e' are the same (i.e., Q = Q') according to Lemmal [ where Fe C". Thus, C is uniquely identifiable. (necessity) Unique identifiability implies that for every permutation matrix P. Q Q' or equivalently PQP is lower triangular. This implies that Q must be a diagonal matrix. In other words, all observed variables in must be isolated.
Proof of Corollary 4 First, we prove that an isolated set in SCM C is also an isolated set in all other SCMs in the equivalence class of C. Without loss of generality, let X' (......, }x be an isolated variable set for e. In view of Theorem 2 Part 2, every SCM in the equivalence class of ((M, Q) can be written as (M, P o, with Qp being the lower triangular matrix obtained from the Cholesky decomposition of PQQT PT, for some permutation matrix P. Now, consider the case where P takes the block-diagonal form Diag( P1, P2) where P1 is r matrix. According to Definition [1 matrix Q is block diagonal, and we have Σ = QQ = Diag(E,, (E1, Σ2) as a block- diagonal matrix, where En and Σg represent the blocks corresponding to the isolated set and the remaining variables, respectively. Clearly, PEP remains block diagonal matrix. This implies that the Cholesky decomposition factor Qp and Q'= variable set X is isolated in every SCM C' Let be the set of all such SCMs e' whose permutation matrix P are block-diagonal. Now, consider the case where P does not take the aforementioned block-diagonal form. Then can be shown that there exists an SCM e E C whose causality order set includes the permutation order Op. Thus, according to Theorem 3 no new SCM arises from this permutation. Hence, C is the equivalence class of C. It follows that if C consists of several isolated variable sets X₁ ....... Am,. all of which will be isolated in every SCM of the equivalence class. Moreover, each of these SCMs correspond to a permutation matrix P in the block diagonal form Diag Pr.g.P....... Pm) where P. is [X,) x [X,] permutation matrix, for all = 1,..., m. On the other hand, there are at most s! permutation matrices of dimension 8 x 8. This completes the proof. O
= P QP are also block diagonal. Therefore, the
Proof of Remark Part 3: According to the proof of Theorem T when the observed vector is dependent, there exist infinitely many SCMs (M", Q*) whose observed variables are equal in distribution with those of SCM C. Since Q a lower triangular matrix, the causality orders of all these SCMs are identical.
Proof of Remark Part 3: We provide two SCMs C' Q') and CO Q") that are in the equiv- alence class of SCM e but have different causal orders. We choose Q' as the Choleskey factor of E = QQ Hence, Q' is a lower triangular but not diagonal matrix, indicating dependence among the observed variables. Consequently, there exists a permutation matrix P such that PQ'P" is not lower triangular matrix. Define Q" = P' Q P where Q, is the lower triangular matrix obtained by the Cholesky decomposition of PΣPT (see according to Lemma 7). Now, in view of Lemma 7 E Q"Q"" which according Σ Q'Q'T implies that E' and e" are in the same equivalence class as SCM C. On the other hand, based on the proof of Lemma Q" * Q' as PQ'PT is not lower triangular matrix. Then, similar to the proof of Theorem it can be shown that e and e" have different causality orders.
18


Reviews:
[{"review_id": "nqcYDHlQyB", "reviewer": "Reviewer_tdTc", "summary": "The paper establishes general conditions under which linear structured causal models are identifiable in the presence of hidden confounding variables and Gaussian noise. Briefly, if the number of confounding random variables is at most the number of observable random variables, then a finite number of equivalent models can be recovered from observations of the observables (the number of models is $n!$, where $n$ is the number of observables). If, in addition, the confounders are non-Gaussian, then the model is uniquely identifiable. Some minor technical assumptions are needed.", "questions": "None", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is a very general result on a fundamental model of causality.", "weaknesses": "The result is information-theoretic. It assumes perfect statistics and does not analyze the resilience to perturbations due to finite sampling. Also, the paper does not state clearly any algorithmic consequences (complexity etc.), though the methods are mostly linear-algebraic and hence possibly effective.", "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": "", "extra_scores": {}}, {"review_id": "CoIyHYrWbd", "reviewer": "Reviewer_AfH3", "summary": "This paper is a theoretical work on the identifiability problem of the linear structure causal models. Specifically, the authors showed that under the general Gaussian assumptions for all components, the linear SCM is unidentifiable. The authors also provided mild sufficient conditions for the linear SCM mode to be (i) uniquely identifiable or (ii) finitely identifiable.", "questions": "Major questions:\n1. Assumption 2 requires \"Confounders $H_i$ .... cannot be decomposed into multiple random variables where any is Gaussian\".  This is difficult to verify. Can this condition be translated to any condition on the characteristic functions? For example, suppose we let $Z\\sim N(0, v)$ and let another independent variable $W$ have the c.f. $\\phi_W(t)=\\phi_H(t)e^{vt^2}$. Then $\\phi_W$ should not be in $L_2$ space for any $v>0$. \nAlso, this condition mentioned \"multiple\" random variables. \nHowever, any density function can be approximated by an infinite mixture of Gaussians (in the weak topology sense). Does this limit scenario break this assumption?\n\n2. Suppose for a real data where $\\mathrm{X}$ and $\\mathrm{H}$ are collected. How do we verify the model is identifiable? \n3. For Definition 3, the rigorous definition for $X\\stackrel{d}{=}Y$ should be: for any measurable set $A$ in the space, $P(X\\in A)=P(Y\\in B)$.  The equality in p.d.f. is a bit unrigorous. \n4. In terms of finding the equivalence class in Sec. 6, is that equivalent to finding the invariant permutations of $\\mathbf{\\Sigma}$, i.e. {$\\mathbf{P}\\in\\mathcal P: \\mathbf{P}\\mathbf{\\Sigma}\\mathbf{P}^T$}, where $\\mathcal P$ is the permutation class? If so, one can divide the indices {1,2,.., n} (corresponding to rows/cols of $\\mathbf{\\Sigma}$) into equivalent classes ($i\\sim j$ if and only $\\Sigma_{ik}=\\Sigma_{jk}\\ \\forall k$). The invariant permutation of $\\mathbf{\\Sigma}$ is group-isomorphic to the direct product of the permutation groups of the equivalent classes.\n\nMinor issues:\n1. For narrative citations, please remove the paratheses. \n2. Pg. 2. Ln 56. Add a space between \",\" and \"$\\mathbf{B}$\".\n3. Remarks 4 and 5 are important results. They can be transformed into two Theorems/Propositions.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Originality: The paper is a novel work that discusses the identifiability of the SCM model under different model assumptions. \n- Quality: The paper provides a thorough discussion of the identifiability issue with complete theoretical justification. It is of high quality in terms of the results and writing. \n- Clarity: The paper is organized in a mathematical paper style. It is easy to follow the assumptions and theorems. \n- Significance: The result of this paper is appealing. The analysis is solid.", "weaknesses": "- One assumption seems confusing to me (see details in the questions part). \n- Although the paper has solid theoretical results, it is a bit difficult to directly apply the results to any real application as the assumptions are hard to verify for real data.", "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": "", "extra_scores": {}}, {"review_id": "4oVfTqdHAQ", "reviewer": "Reviewer_AGFs", "summary": "The paper discusses identifiability criteria for linear structural causal models (SCMs) with different scenarios for Gaussianity of confounders and noise, and varying assumptions. More specifically, the paper fills in the gap of identifiability for Gaussian noise and non-Gaussian confounders. The main proof technique involves analysis of characteristic functions and reliance on Gaussian properties. Some numerical examples are provided.", "questions": "The paper does a good job of addressing multiple aspects of the problem. The largest concern is the scope of the problem and whether it has sufficient significance. Some questions and suggestions include:\n\n1. It may be helpful to highlight the main theoretical tools used in the proof (i.e., the use of characteristic functions) and connect these tools with other contexts beyond the SCM. While the technique may be novel within applications to SCM, it is not particularly novel in the broader statistical literature. Are there other areas in machine learning that can significantly benefit from the techniques?\n\n2. Regarding causal orders -- the SCM is uniquely identifiable given the causal order, provided gaussian noise and non-gaussian confounders. What if an expert only gives a partial order, would it still be uniquely identifiable in some scenarios?\n\n3. Are there any existing results in identifying the SCM that can benefit from results presented in this paper? How are the results of identifiability connected with classical results in estimating linear model parameters?\n\n4. A minor typo: Line 125 \"novel approached\".", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper shows that linear SCMs with Gaussian noise are finitely identifiable under the assumption that confounders are non-constant and cannot be decomposed into random variables where any are Gaussian (Assumption 2). This result fills in gaps in identifiability where earlier results already identified finite identifiability of SCMs with non-Gaussian noise and confounders. From this perspective, the paper contributes original new results.\n\nIn terms of significance, it is clear that the main results contribute to the field of linear SCMs and is a relevant topic for the conference. While the framework may be simple, the main results are interesting. \n\nFinally, it is worthwhile to point out that the paper is clearly polished. The authors provided an extensive discussion of existing literature, problem formulations, main results, and concerns.", "weaknesses": "- The linear model framework restricts the scope of the paper\n- As the authors also pointed out, there are no discussions of algorithms to find an SCM\n- Novelty in proof techniques are limited and appear to be a mixture of gaussian properties, characteristic function analysis, and reliance on Gaussianity assumptions\n\nWhile the points above raise concerns of weaknesses on the applicability of the results, the paper's main theoretical results are still meaningful and interesting.", "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": "", "extra_scores": {}}, {"review_id": "MXnkEuyRgN", "reviewer": "Reviewer_huy7", "summary": "The paper investigates the identifiability of noisy linear structural causal models (SCMs) in settings where confounders and noise variables have distributions with Gaussian and/or non-Gaussian components. Specifically, the authors investigate necessary and sufficient conditions for the SCM to be uniquely, finitely or infinitely identifiable, depending on the distributions of confounders and noise and certain assumptions on the causal structure of the model. Theorem 1 extends the known counter examples addressing identifiablity under Gaussian confounders.\n\nTheorem 2 provides sufficiency conditions for linear SCM's to be finitely identifiable and provides a wonderful characterization in terms of the number of permutations and the characteristic function of the confounders. Theorem 3 characterizes when a permutation of an SCM leads to a new SCM and affects the causal order. Section 6 provides numerous examples and illustrations of the results.", "questions": "Full identifiability of a causal model is typically a strong ask. Often, one only cares for a small part of the model to be identifiable (e.g. some treatment effect). Do the findings of the authors (in particular Theorem 2) give immediate insight in when part of the model is uniquely identifiable, even when the full model is not?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Solid contributions: The paper provides significant insights into SCM identifiability, that extend existing work. \n\nClear writing and proof structure: The writing is clear and concise, with proofs that are both rigorous and easy to follow. The presentation of theoretical results is structured and clear. I enjoyed reading the article.", "weaknesses": "I think the writing/accessibility of the article could be improved slightly:\n\nGrammar and Punctuation: There are minor punctuation issues in the introduction, particularly with the use of commas. For example in line 41, line 42, or \"It is near impossible to claim that all causes of a specified process are considered, and hence, the consideration of confounders is inevitable\" in line 49 (I would suggest \"It is nearly impossible to claim that all causes of a specified process are considered; hence, the consideration of confounders is inevitable.\" or two separate sentences).\n\nCertain definitions can be assumed to be known by the reader, such as Definition 3 and Definition 7 (along with Remark 2 and Remark 3). I would suggest moving these to the appendix to streamline the main text.\n\nThe examples illustrating Remarks 5 and 6 could use some further steps to help the reading along. This could be done in the appendix. \n\nTypos:\nline 67: \"base on\"\n200: \\ref used instead of \\eqref{}\n387: 'is' illustrated by SCMs:", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)