Learning Linear Causal Representations from General Environments: Identifiability and Intrinsic Ambiguity
Authors: Jikai Jin
Vasilis Syrgkanis
Venue: NeurIPS 2024 spotlight (2024)
Keywords: causal representation learning; causal inference
Primary area: causal_inference

Abstract: We study causal representation learning, the task of recovering high-level latent variables and their causal relationships in the form of a causal graph from low-level observed data (such as text and images), assuming access to observations generated from multiple environments. Prior results on the identifiability of causal representations typically assume access to single-node interventions which is rather unrealistic in practice, since the latent variables are unknown in the first place. In this work, we consider the task of learning causal representation learning with data collected from general environments. We show that even when the causal model and the mixing function are both linear, there exists a surrounded-node ambiguity (SNA) [Varici et al. 2023] which is basically unavoidable in our setting. On the other hand, in the same linear case, we show that identification up to SNA is possible under mild conditions, and propose an algorithm, LiNGCReL which provably achieves such identifiability guarantee. We conduct extensive experiments on synthetic data and demonstrate the effectiveness of LiNGCReL in the finite-sample regime.

Learning Linear Causal Representations from General Environments: Identifiability and Intrinsic Ambiguity
Jikai Jin
Institute for Computational and Mathematical Engineering Stanford University Stanford, CA 94305 jkj ikjin@staffodd.c
Vasilis Syrgkanis
Management Science and Engineering
Stanford University Stanford, CA 94305
vsyrga@stanford. edu
Abstract
We study causal representation learning, the task of recovering high-level latent variables and their causal relationships in the form of causal graph from low- level observed data (such as text and images), assuming access to observations generated from multiple environments. Prior results on the identifiability of causal representations typically assume access to single-node interventions which is rather unrealistic practice, since the latent variables are unknown in the first place. In this work, we consider the task of learning causal representation learning with data collected from general environments. We show that even when the causal model and the mixing function are both linear, there exists surrounded -ode ambiguity (SNA) [46] which is basically unavoidable our setting. On the other hand, the same linear case, we show that identification up to SNA is possible under mild conditions, and propose an algorithm, LiNGCReL. which provably achieves such identifiability guarantee. We conduct extensive experiments synthetic data and demonstrate the effectiveness of LiNGCReL in the linite-samlle regime.
1 Introduction
Artificial intelligence (AI) has achieved tremendous success in various domains in the past decade [4, 40, 6]. However, current approaches are largely based on learning the statistical structures and relationships in the data that we observe. As a result, it is not surprising that these approaches often capture spurious statistical dependencies between different features, resulting in poor performance in the presence of test distribution shift [30, 22] or adversarial attacks [3, 50].
In view of these pitfalls, recent line of work has explored the problem of causal representation learning (CRL) [34], the task of learning the causal relationships between high-level latent variables underlying our low-level observations. Notably, it is widely believed in cognitive psychology that humans take a causal approach to distill information from the world and make decisions to achieve their goals [37, 12, 19]. As result, there is reason to believe that learning causal representations has the potential to significantly improve the power AI, especially on tasks where performance lags far behind human level [17].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Despite such promise, a crucial challenge in CRL is the identifiability of the data generating process; in other words, given the data that we observe, can we uniquely identify the underlying causal model. It has been shown that given observational data (ie., i.i.d. data generated from a single environment) the model is already non-identifiable in strietly simpler settings where the latent variables are known to be independent [25, 26], or where there is no mixing function and one directly observes the latent variables [39]. As a result, existing algorithms for CRL with observational data [52, 53, 11] typically require additional assumptions on the structure of the underlying causal graph. A natural question that arises is what types of data do we need to acquire to make identification possible in the general
case.
One line of works assumes access counterfactual data [27, 48, 5], where some form of weak supervision is typically required. A common assumption here is that one observes data in pairs, where each pair of data is related via sharing part of the latent representation. However, such data hard to acquire since it requires direct control on the latent representation.
Another line of works [1, 49, 7, 47] instead considers an interventional setting, where the learner observes data generated from multiple different environments. This is arguably a much more realistic setup and reflects common practices in robotics [24] and genomics [28, 43] applications. However, a vast majority of identifiability guarantees assume that each environment corresponds to single-node, hard interventions, which defined as interventions that isolate a single latent variable from its causal parents. Again, this is quite a restrictive assumption because of two reasons. First, since the latent variables are unknown and need to be learned from data, is unclear how to perform interventions that only affect one variable. Second, even if one can perform single-node interventions, it may not be feasible to artificially remove causal effects in the data generating processes. This issue is ubiquitous in real-world applications as pointed out in Campbell [8], Eberhardt [14], Eronen [15]. Motivated by these challenges, we make the following contributions in this paper:
Assuming access to data collected from multiple environments, but not necessarily from single-node, hard interventions, we identify an intrinsic surrounded-node ambiguity (SNA) in learning the underlying causal representations. We show in Theorem 3 that SNA is unavoidable even if (1) both the mixing function and the causal model are known to be linear and (2) one has access to single-node, soft interventions. This highlights a remarkable difference with existing literature which shows that perfect identification can be achieved with hard interventions.
When the causal model and the mixing function are both linear, we prove in Theorem 1 that identification up to SNA is achievable with (dd diverse environments (Assumption 4), where is the size of the latent causal graph. To the best of our knowledge this is the first identification guarantee that applies to fully general environments and makes assumption on their relationship or similarity. Interestingly, we also show in Theorem 2 that one would require (dd²) single-node soft interventions to achieve the same identification guarantee, indicating the benefit of learning from diverse environments.
We propose algorithm, LiNGCReL, in Section 5 that provably recovers the ground-truth model up to SNA (Theorem 4) in the setting of Theorem I when perfect information of the observation distributions is available. To demonstrate the effectiveness of LiNGCReL in finite-sample regime, we conduct extensive experiments on synthetic data, and our results reported in Section 6 show that LiNGCReL capable of recovering the true causal model up to SNA with high accuracy.
Due to space limit, proofs of all our statements and additional theoretical results are given in the appendix.
2 Preliminaries
We consider the standard setup of CRI from multiple environments F. E É. Let G = (V,E) be the ground-truth causal graph which is directed and acylic (DAG), where [d] and describes the causal relationship between different nodes. Each node corresponds to latent variable E R.
For any node i, we let pig( (i)( anso (i) and ndd to be the set of all parents, children, ancestors and non-descendants of in 9 respectively. We also define (i) (1) U (i) and similarly for ci) ansg (i) and (i). Assuming that all probability distributions have continuous

---

densities, the joint density of the latent variables z can then be written as
(F II p (z: Fpag())
where of is the (unknown) latent generating distribution from environment E at node i. Here for given vector v. we write v, - =e, v, and let vy (v; S) E RISS,
The causal graph model with density given by (1) necessarily enjoys the following property:
Definition (Causal Markov Condition). For any node conditioned on zpag (6) is independent
of (nd As consequence, for any node i.j [d] and S S [d]. if S d-separates from j (cf.
Definition 7), then 2; 1 2j øs.
The latent variables are unknown the learner. Instead, the learner has access observations In (n > d) from all environments E' E C that are related to the latent via an injective mixing function g:
x g=)(
The main assumption here that the mixing function is the same across all environments: Assumption 1. All environments E È share the same diffeomorphic mixing function R + R
In CRL, the goal of the learner is to 1) recover the inverse of the mixing function h = 9--- (often called the unmixing function) which allows recovering the latent variables given any observations, and, 2) recover the underlying causal graph G. In the remaining part of this paper, we refer (h, 9) as the causal model to be learned. Obviously, there would be some ambiguities in learning (h, g). For example, choosing a different permutation of the nodes in the causal graph would lead to a different model, and so does element-wise transformations on each component h, of h.
line of recent works show that the ground-truth model be identified up these ambiguities in various settings, assuming access to single-node hard interventions [36, 49, 47]. On the other hand, some weaker notions of identifiability have also been proposed and studied in the literature
[36, 46, 23] for single-node soft interventions. Here, we provide a generic definition of single-node soft interventions that we will rely on in this paper.
Definition 2. We say that collection of environments è is a set of (soft) interventions on subset of latent variables { E S} if any E [d] and any Fr, F.2 E, Fn # E2,, we have p. = Pi if and only i
Ea
i & S (the notation 2 comes from (1)). Equivalently, write I
We note that soft interventions are very different from hard interventions, since they do not remove causal relationships between latent variables. The goal of this paper is to address the following question:
What is the best-achievable identification guarantee when hard interventions are not available, and what are the intrinsic ambiguities?
3
The surrounding set and notion of identifiability
One may expect that identifiability with soft interventions is not much different from hard interven- tions, since soft interventions can approximate hard interventions with arbitrary accuracy. However, we will show that this is not the case. At a high level, hard intervention is more powerful than soft intervention because it is capable of isolating latent variable from its direct cause while soft interventions is not, so soft interventions can sometimes fail to identify the true causal relationship from mixture of causal effects.
To quantify what kind of ambiguities may arise, we can define the surrounding set for each node in a causal graph G as follows:
Definition 3. (46, Definition 3) For two nodes i,j e [d] in G, we say that j is surrounded by or
i (Jrg()) i E pag(j), and cjz( C chz( Moreover, we define surę(j) = surg(j) U (j).
Intuitively, if there exists some surg(j), then ambiguities may arise for the causal variable at node since any effect of j on any of its child & can also be interpreted as a mixture of the effect of i
3

---

and j. In Appendix E we discuss example with three causal variables to further illustrate such ambiguities.
chç(j) S chg(
J1
J2
J3
Figure An illustration Definition 3; here E su)g
Definition 3 naturally induces the following relationship between causal models:
Definition Using the notations in Definition 10, we write (h, 9) "sur (h, if there exists
permutations nt on [d], and diffeomorphism di Ted H RRd where the j-th component of v. denoted by (z),, is function of Esung()) for Vj [d], such that the following holds:
* For any i.j E [d], iE pag (i) if and only if (() E pag (T()),, and
PP o 1b o h, where Pa is a permutation matrix satisfying (P*)is = 1 1f = (i) and (P=) = otherwise.
In other words, ~ssur requires that the causal graph to be exactly the same up to some permutation of nodes, but allows each latent variable v, to a mixture of =s)rg(s)- Although not obvious from definition, one can actually check that ~sur defines an equivalence relation (see Lemma I). Moreover, we will show in the following section that suur general the best that we can hope for in our problem setting.
4 Identifiability theory for linear CRL with general environments
In this section, we consider learning causal models from general environments. Specifically, we assume that the environments Fg, [K] share the same causal graph, but the dependencies between connected nodes (latent variables) are completely unknown, and, in contrast with existing literature single-node interventions, impose similarity constraints the environments. We begin our investigation of identifiability in this setting in the context of linear causal models with linear mixing function.
4.1 Problem setup
Formally, we assume the following generative model K distinct environments C = {Ex : k [K] with data generating process
- A,2 S. x= Gz k E [K],
(3)
where the matrix Ag satisfies (Ax);; + 0 if and only if + in G. We refer to (Ax. 22g) as the weight matrices of latent variables in the environment Eg. It is easy to see that Assumption I in our general setup translates into the following assumption:
Assumption 2. The mixing matrix G Roxd has full column rank. Equivalently, the unmixing matrix H = G has full row rank.
E [K]. then we have c B = H. Since in the linear case, there is an easy to one-to-one correspondence between the matrix H and the un-mixing function x + x, we abuse the notation and write (H,9) to represent the model instead (h, 9). Using h, denote the i-th row of H. the following lemma translates Definition 4 the the linear setting:
Let B = (I
Lemma 1. According to Definition 4, (H,9) G) ~eur (H, 9) if and only if there exists a permutation
on [d), such that the following statements hold:

---

1. For all i.j E [d], i E pag(i) if and only ifi) E pag(T(()), and
2. For all i E [d]. h, E span (hy : x(i) E surg(i)).
We also need make the following assumption on noise.
Assumption 3. The noise vector E IRd has independent components, al most one component is Gaussian distributed, and any two components have different distribution.
The non-gaussianity of the noise vectors is typical assumption in causal discovery within linear mod- els [9, 39] and is always assumed in the LinGAM setting [38]. The assumption that all components have a different distribution is not so standard, but is quite natural in real-world scenarios.
4.2 Identifiability guarantee
For each node E [d] of g, we use wp to be the weight vector of environment Eş at node i, i.e., (1((1) ((Ab), j E pag(i)) I (9)(0) In other words, the structural equation for node in environment l is of the form:
24 = w= (1) Epag(1) + VWk,iat;
To obtain identifiability result, the main assumption need make is the non-degeneracy of the weights at each node:
Assumption For each node i E [d] of G. we have afl (un, (1) [K] = TR. (agg(() where ... a-) denotes the affine hull. Equivalently, the weights wy((), k 1,2, ........ K do not lie in (1pag(0) - 1)-dimensional hyperplane of plpaa(0).
This assumption is quite mild since it only requires the weight vectors be in general positions, and it holds with probability 1 if the weights at each node are sampled from continuous distributions. Moreover, as shown in Lemma 5, it is equivalent to the following assumption.
Assumption 5 (Node-level non-degeneracy). We say that the matrices { (Ba) are node-level non-degenerate if for all node i E [d]. we have dim dimspan ((Ba); k [K]} ppag(t) + 1, where (Ba), is the i-th row of B
In the following, state main result in this section, which shows that K non-degenerate environments suffices for the model to be identifiable up to Maur-
Theorem Suppose that K > d and we have access to observations generated from the linear causal model (H,9) across multiple environments E = {Ex k E [K]} with observation distributions {IPE) J Bee, and the data generating processes are given by (3), Let (H, () be any candidate solution with the hypothetical data generating process
A & == H.v in the environment Es
where H has full row rank, such that
(i) the observation distribution that this hypothetical model generates in Eş is exactly PE
(ii) all environments share the same causal gruph: Vk E [K] and i, E [d], (Ax)y # #0#) pag( (Ax)is + + (i) and Stk, Si are diagonal matrices with positive entries;
(iii) (B and { (Bx 52 (()-)))) x-1 are non-degenerate in the sense of Assump- tion 5;
(iv) the noise variables and satisfy Assumption 3.
Then we must have (H, 9) ~aur (H,G))
The proof of Theorem given in Appendix H.1. In the next section, we will introduce an algorithm, Li NGGCReL, that provably recovers the ground-truth up to <sur.
5

---

To the best of our knowledge, this is the first identifiability guarantee in the literature for CRL from general environments, even for the linear case. Our result closely related but fundamentally different from Xie et al. [52, 53], Dong et al. [11] that consider the task of linear CRI using observational data. As discussed before, with observational data the causal graph can best be identified up to Markov equivalence. As a result, one typically requires additional assumptions on the structure of the causal graph to obtain stronger guarantees. contrast, we show that with data from multiple environments, exact recovery of the causal graph is possible without any structural assumptions.
Interestingly, while the fact that existing works focus on single- node interventions seem suggest that learning from diverse environments is hard, it turns out that such diversity is actually helpful. Specifically, we show that in the worst case, (d²)) interventions are required for identifying the ground truth model under surr
Theorem 2 (informal version of Theorem 6). There exists causal graph g with (dd)) edges, such that for any unmixing mulrix H E Bgdx with full row runk, any independent noise variables and any < s, & ppagii) , [d], the ground-trute model (H, G) is non non-identiffable up to ~eur with ss soft interventions for node unless the (ground-truth and intervened) weights of the causal model lie in a null set (w.rt the Lebesgue measure).
formal version and the proof of Theorem 2 can be found in Appendix H.2. On the other hand, by having d single-node interventions per node, Assumption 5 can be satisfied as long as the weights are in general positions, so in this case we have (H, 9) -sur (H, 9) by Theorem 1. Therefore, Theorems I and 6 together imply that (df) single-node interventions are necessary and sufficient for identification up to -suur-
Given that Theorem only guarantees identification up to Ysur that is strictly weaker than full identification, one might naturally ask whether Theorem can be further improved. Our last theorem in this section indicates that ssur is indeed a fundamental barrier that exists even when we access to single node, soft interventions.
Theorem 3 (Counterpart to Theorem 1, informal version of Theorem 9). For any linear causal model (H, G) and any set of environments E [Ex k E [K]] such that all conditions in Theorem I are satisfied, there must exists candidate solution (H,9) and hypothetical data generating process that satisfy the same set of conditions, but
dv: # O, Vj E surg(())
dz,
Moreover. if we additionally assume that the environments are groups of single-node soft interventions, then we can guarantee the existence of (H,9) 9) and weight matrices which, besides the properties listed above, also groups of single-node soft interventions.
5 LinGCReL: Algorithm for linear non-Gaussian causal representation learning
In this section, we introduce Linear Von-Gaussian Causal Representation Learning (LiNGCReL), an algorithm that provably recovers the underlying causal graph and latent variables up to <uur in the infinite-sampi limit. At this point, it is instructive to recall the celebrated LiNGAM algorithm [38] for linear causal graph discovery. Different from their setting, we only observe some unknown linear mixture of the latent variables. Hence, running linear ICA as in LiNGAM only gives us M2 B H rather than the weight matrix B₁ itself.
The key idea in our approach is an effect cancellation scheme that allows us to determine the "remaining degree of freedom" (RDF) of any node (a.k.a. latent variable) given any subset of its ancestors. This scheme allows us to not only find a topological order of the nodes, but also figure out direct causes by tracking the changes of the RDF. In the following, we present the main steps of LiNGCReL in more details.
Suppose that we are given samples of observations (K) = (xx(() k e [K] where (x( the i-th sample from the k-th environment.
Step Recover the matrices Ms- = B, H Since B = B₁ Hr in the k-th environment, so can use any identification algorithm for linear ICA to recover the matrix M.. Then we properly

---

rearrange the rows of M2 so that all Ma 1.2. K correspond to the same permutation of noise variables. This step is quite standard and details can be found in Appendix B.I.
Step 2. CRL based on M2 Now we have obtained M3 B₁ H, but the unmixing matrix H is still unknown. We propose Algorithm 3 to learn H and the causal graph G. The main part of Algorithm contains loop that maintains a node set which, we will show later, is ancestral, i.e. i S + (i) S S. In each round the algorithm finds a new node & S such that ansg (i) S S, and a subroutine Identify-Parenta (Algorithm 2) is used to find all parents of i. After that, we append into and continue until contains nodes G. Finally, the rows of the mixing matrix H is obtained by intersections of properly-choser row spaces of Mg.
Both Algorithm 2 and Algorithm include crucial step, which call it orthogonal projection, as described in Algorithm 1. At a high level, helps determine the minimal RDF for 2; after fixing the latent variables zs. and this exactly corresponds the number of parents of that are not in zş. We provide a simple example Appendix E.2 to illustrate why this approach works.
The following result states that Algorithm 3 can recover the ground-truth causal model up to ~auri
Theorem Suppose that M k E [K] are perfectly identified in Step Let (H.9) be the solution returned by Algorithm 3, then we must have (H, 9) ~sur (H,9).
The full proof of Theorem 4 is given in Appendix H.3. It crucially relies the following two propositions that reveal how Algorithm and the subroutine Algorithm 2 work.
Algorithm Orthogonal- projjecciisssoossiioonn
1: Input: Ordered set S = {s1. $2, 82, 8m) S [d], index i o S, matrices Mg E RRdxn k [K]
2: Output: Set of vectors {p*
3: for k < to K do
4: W + span ((Mg), ) : E S)
(Mx)s the s-th row of M
5: Py < projw ((M&):
6: end for
Proposition 1. The following two propositions hold for Algorithm 3:
ai) S + the if condition in line 8 of Algorithm is fulfiled:;
the set maintained in Algorithm 3 is always an ancestral set, in the sense that j E ansg(j) C S.
Proposition 2. Given any ordered ancestral set S that contains pag (i) for some i & S, Algorithm returns set P; that exactly (i)
Algorithm 2 Edentify-Parentt
1: Input: An ordered set = {s1, $2, 8m S [d]. a node & S and matrices M k E [K]
2: Output: The parent P. of node
3: Pt =00
4: for m' <- 0 do
5: {p*]k- + -rtthogona--proojettinnn (1sy 1 < m'}, (M& M&(n))
6: T'o +- dim span (px : k E [K])
7:
im'm and r'm mm'-1 then
8:
P. + I.P.U {m²}
9:
end if'
10:
end for
Experiments
In this section, we present our experimental setup and results for LiNGCReL. Note that LiNGCReL as described in the previous section only works in the population regime. When the number of samples limited, two main challenges in implementing LiNGCReL are to accurately compute the dimension
7

---

Algorithm 3 Learn-CausallModel!
1: Input: Matrices Ma, k E [K]
2: Output: The edge set & the vertex set [d] and the mixing matrix H
3: S 5-00: 0:
D. S an ordered set of nodes
4: E 0;
E is the edge set
5: while |S|| < do
6: for $ do
7:
[px)k=1 +
(S, (Mr )ε(K))
8: dims (qk: l E [K]) = 1 then
9: break
b Proposition 1 guarantees that such an i must exist
10: end
11: end for
12: P. Identify-Parents/a
S-SU
14:
S-EU(U.)):
15: end while
16: for i to d do
Eg + span ((M&); : : &s E [K])
18: end for
for 1 to d do
20: h; f- any non-zero vector in (Niies)e E,) n E,
end for
H hT hT
hJ
of subspace (line of Algorithm 2 and line 8 of Algorithm 3), and to find a vector in the intersection of multiple subspaces (line 20, Algorithm 3). Due to space limit, the implementation details are described in Appendix B.2.
Experimental setup. We generate the independent noise variables from generalized Gaussian distributions (*) α exp (-1al*) with parameters B* = 0.222 1,2, ... d. multiplied by normalization constants make their variances equal The ground-truth causal graph is generated by first fixing a total order of the vertices, say 1,2, ... ,d, then add directed edges i > j(i < j) according to i..dd Bernoulli(p) distributions, where p (0, 1). The non-zero entries of matrices By and H are all generated independently from Gaussian distributions. For simplicity, we focus on the case d since recovery of the latent graphs only requires information from d components æ.
Metries of estimation error. Since CRL seeks to learn both the causal graphs and the latent variables, for each output of our algorithm first check if it exactly recovers the ground-truth causal graph. Then, recall that the latent variables and the observations are related by z H x. given any output unmixing matrix H from Algorithm 3, we define the relative estimation error A, for z; as the solution of the following optimization problem:
proj projepan (hp.eeaannn ( (1) (ha)
min A ooc
S.L.A
h
(5)
H = PH for some signed permutation matrix P.
where signed permutation is allowed here since the noise distribution in our experiments is symmetric and the order of latent variables 2,, 1 1,2,- ...... d does not matter. We refer the errors A; defined in (5) the SNA error. The SNA in the span of the ground-truth rows ı E sirç(i). Indeed, recall that given any observation æ, the
measures how much of the row h, that learn is contained
Hæ while our algorithm outputs è; h. æ. so the SNA error essentially captures whether the recovered latent variable close to some linear mixture of latent variables in the effect-dominating set of i. When the SNA emror is zero for some node i, we know that the recovered latent variable at node exactly linear mixture of the ground-truth latent variables in surg(i), (i), according to Lemma 1.
ground-truth latent variable is

---

Sumple bort)
Sinple COPP
(a) (a)== =
(b) d= 5, k
move
ko)=K=8
(d) d = K 10
surg(i)
SNA
True
0
2. 2.8e-3
2.8e-3
(1>
4.0e-3
9.6e-2
3
0
3.4e-3
3.4e-3
{3}
1.1e-2
0.99
(3}
1.4e-2
0.41
(f) Result for identifying Figure 2e by rumning LiNGCReL
(c) An example causal graph in our experiment
Figure 2: First two as functions of sample size (per environment) for different choices of graph size and number of environments K. Third row: example of causal graph generated in experiments, and the estimation error of LiNGCReL for each node.
plots of SNA Error and graph recovery accuracy achieved by LiNGCReL
We also define the true for estimating each latent variable. Formally, let H be the unmixing matrix that corresponds to the solution of (5), then define the true estimation error Å; of
A = (I -1- h,hhh) h
(6)
Results. We randomly sample 100 causal models with size 5, 30 causal models with size d ad 30 causal models of size d 10. In light of Theorem 1, for each d {5, 8, 10}. sample data 20 to study how
from K randomly chosen environments; for = 5 we also consider different choices of K can affect the result. We run LiNGCReL for each model with different sample sizes, compute the SNA error and true error of the obtained solution from (5) and (6) respectively for each latent variable, and check whether the ground-trun -ruth causal graph is exactly recovered.
Figure 2 shows how the average SNA error (over all latent variables) and the accuracy of graph recovery changes when sample size grows. We can see LiNGCReL successfully recovers about 80% of all models within each category, and the median the average SNA сгrоr smaller than 1%. Moreover, by comparing Figure 2a with Figure 2b, one observe that if we fix the total number of samples but choose a larger (i.e., fewer samples per environment), LiNGCReL can still achieve the same level of performance compared with the choice K = d. Intuitively, this is because K > d vectors sampled from an r(r & d) dimensional subspace are unlikely to approximately lie in an (r 1) ddimensioonal subspace, so that the calculation of line 6 of Algorithm 2 and line 8 of Algorithm can be more accurate. We leave better and quantitative understanding of the trade-off between and K to future work.
SNA error v.S. true error. To understand the implication of our theory, we dive deeper by looking into the learning outcome of LiNGCReL on specific model, of which the causal graph is shown in

---

Figure 2e. In Figure 2f, we list the surrounding set of each node and the corresponding SNA error and true error. We can see that if surg(i) 0. the two errors equal and both are small, but if surg(i) + the true enror is much larger than the SNA error. This indicates that LiNGCReL. indeed learns the ground-truth model up to suur, as Theorem predicts.
7 Conclusions
This paper studies the limit of learning identifiable causal representations using data from multiple environments. When hard interventions are not available, provide theory and algorithm for identification up to SNA, and also show that SNA is an intrinsic ambiguity our setting.
It is interesting to further investigate the setting where we do not assume that the causal model linear. Moreover, it is important to understand the concrete form of available interventions in real-world applications. For instance, it is suggested that for single-cell genomics, the intervention is sometimes "mixture" of hard and soft interventions, and sometimes can even reverse the direction of edge [43]. Modelling such more complicated interventions appears to be crucial to reveal the underlying causal mechanisms in real-world problems.
Acknowledgments and Disclosure of Funding
VS is supported by NSF Award I13-3337116 and a 2023 Google Research Scholar Award.
References
[1] Kartik Ahuja, Divyat Mahajan, Yixin Wang. and Yoshua Bengio. Interventional causal repre- sentation learning. International Conference on Machine Learning, pages 372-407, PMLR, 2023.
[2] Kartik Ahuja, Amin Mansouri, and Yixin Wang. Multi-domain causal representation learning via weak distributional invariances. arXiv preprint arXiv:2310.0285: 2023.
[3] Naveed Akhtar and Ajmal Mian. Threat of adversarial attacks on deep learning in computer vision: A survey. leee Access, 6:14410-14433 2018
[4] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 35)) 1798-1828, 2013.
[5] Johann Brehmer, Pim De Haan, Phillip Lippe, and Taco S Cohen. Weakly supervised causal representation learning. Advances in Neural Information Processing Systems, 35:38319-38331, 2022.
[6] Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303. 12712, 2023.
[7] Simon Buchholz, Goutham Rajendran, Elan Rosenfeld, Bryon Aragam, Bernhard Schölkopf, and Pradeep Ravikumar. Learning linear causal representations from interventions under general nonlinear mixing. arXiv preprint N.Xiv:233660223333 2023.
[8] John Campbell. An interventionist approach to causation in psychology. Causal learning: Psychology, philosophy, and computation, pages 58-66, 2007.
[9] Pierre Comon. Independent component analysis, a new concept? Signal processing, 36(3): 287-314, 1994.
[10] Gregory F Cooper and Changwon Yoo. Causal discovery from a mixture of experimental and observational data. In Proceedings of the Fifleenth conference on Uncertainty artificial intelligence, pages 116-125, 1999.
10

---

[11] Xinshuai Dong, Biwei Huang, Ignavier Ng. Xiangchen Song. Yujia Zheng, Songyao Jin, Roberto Legaspi, Peter Spirtes, and Kun Zhang. A versatile causal discovery framework to allow causally-related hidden variables. In The Twelfth International Conference on Learning Representations, 2023.
[12] Kevin N Dunbar and Jonathan A Fugelsang. Causal thinking in science: How scientists and students interpret the unexpected. In Scientific and technological thinking, pages 57-79. Psychology Press, 2004.
[13] Frederick Eberhardt. Almost optimal intervention sets for causal discovery. In Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence, pages 161-168, 2008.
[14] Frederick Eberhardt. Direct causes and the trouble with soft interventions. Erkenntnis, 79: 755-777, 2014.
[15] Markus Eronen. Causal discovery and the problem of psychological interventions. New Ideas Psychology. 59:100785, 2020.
[16] Ronald Aylmer Fisher et al. The design of experiments. The design of experiments,, (7th Ed), 1960.
[17] Robert Geirhos, Hern-Herrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann. Shorteut learning in deep neural networks. Nature Machine Intellience, (11))665-666 2020.
[18] Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 55(4):926-939, 2014.
[19] Keith J Holyoak and Patricia W Cheng. Causal learning and inference rational process: The new synthesis. Annual review of psychology, 62:135-166 2011.
[20] Antti Hyttinen, Frederick Eberhardt, and Patrik O Hoyer. Experiment selection for causal discovery. Journal of Machine Learning Research, 14:3041-3071, 2013.
[21] Ilyes Khemakhem, Diederik Kingma, Ricardo Monti, and Aapo Hyvarinen. Variational au- toencoders and nonlinear ica: A unifying framework. In International Conference on Artificial Intelligence and Statistics, pages 2207-2217, PMLR, 2020.
[22] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, al. Wilds: A benchmark of in-the-will distribution shifts. In International Conference on Machine Learning, pages 5637-5664. PMLR, 2021.
[23] Wendong Liang, Armin Kekić, Julius von Kügelgen, Simon Buchholz, Michel Besserve, Luigi Gresele, and Bernhard Schölkopf. Causal component analysis. arXiv preprint 23.. 2023.
[24] Phillip Lippe. Sara Magliacane, Sindy Löwe, Yuki M Asano, Taco Cohen, and Efstratios Gavves. Biscuit: Causal representation learning from binary interactions. arXiv preprint arXiv:2306.. 09643, 2023.
[25] Francesco Locatello, Stefan Bauer, Mario Lucic, Gunnar Raetsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem. Challenging common assumptions in the unsupervised learning of disentangled representations. In international conference machine learning, pages 41 14
4124. PMLR, 2019.
[26] Francesco Locatello, Stefan Bauer, Mario Lucic, Gunnar Rätsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem. A sober look at the unsupervised learning of disentangled representations and their evaluation. The Journal of Machine Learning Research, 21(1):8629- 8690, 2020.
[27] Francesco Locatello, Ben Poole, Gunnar Rätsch, Bernhard Schölkopf, Olivier Bachem, and Michael Tschannen. Seperve disentanglement without compromises. In International Conference Machine Learning, pages 6348-6359. PMLR, 2020.

---

[28] Romain Lopez, Natasa Tagasovska, Stephen Ra, Kyunghyun Cho, Jonathan Pritchard, and Aviv Regev, Learning causal representations of single cells via sparse mechanism shift modeling. In Conference Causal Learning and Reasoning, pages 661-691. PMLR, 2023.
[29] Chaochao Lu, Yuhuai Wu, José Miguel Hemández-Lobato and Bernhard Schölkopf. Invariant causal representation learning for out-of distribbtutioo generalization. In International Conference on Learning Representations, 2021.
[30] Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. Advances in neural information processing systems, 32, 2019.
[31] Judea Pearl. Causality. Cambridge university press, 2009.
[32] Geoffrey Roeder, Luke Metz, and Durk Kingma. On linear identifiability of learned rep- resentations. In International Conference on Machine Learning, pages 9030-9039, PMLR, 2021.
[33] Mark Rudelson and Roman Vershynin. Smallest singular value of random rectangular matrix. Communications on Pure and Applied Mathematics: Journal Issued by the Courant Institute of Mathematical Sciences, 62(12): 170--179,7 2009.
[34] Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings of the IEEE, 10265):61-6634 2021.
[35] J Schwartz. The formula for change variables a multiple integral. The American Mathe- maticul Monthly, (2):811885 1954.
[36] Anna Seigal, Chandler Squires, and Caroline Uhler. Linear causal disentanglement via interven- tions. arXiv preprint arXiv:2211.1644 2022.
[37] David R Shanks and Anthony Dickinson. Associative accounts of causality judgment. In Psychology of learning and motivation, volume 21, pages 229-261. Elsevier, 1988.
[38] Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
[39] Ricardo Silva, Richard Scheines, Clark Glymour, Peter Spirtes, and David Maxwell Chickering. Learning the structure of linear latent variable models. Journal of Machine Learning Research, 7(2), 2006.
[40] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schritwieseer, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, al. Mas- tering the game of with deep neural networks and tree search. nature, 529(7587):844488) 2016.
[41] Peter Spirtes, Clark N Glymour, and Richard Scheines. Causation, prediction, and search. 2000.
[42] Michael Strevens. Review of woodward," making things happen", 2007.
[43] Alejandro Tejada-Lapuerta, Paul Bertin, Stefan Bauer, Hananeh Aliee, Yoshua Bengio, and Fabian Theis. Causal machine learning for single-cell genomics. arXiv preprint 1rX 2023.
[44] Robert E Tillman and Frederick Eberhardt. Learning causal structure from multiple datasets with similar variable sets. Behaviormetrika, 41(1):41-64, 2014.
[45] Simon Tong and Daphne Koller. Active learning for structure in bayesian networks. In International joint conference on artificial intelligence, volume 17, pages 863-869. Citeseer, 2001.
12

---

[46] Burak Varici, Emre Acarturk, Karthikeyan Shanmugam, Abhishek Kumar, and Ali Tajer. Score- based causal representation learning with interventions. arXiv preprint arXiv:2301.082.0 2023.
[47] Burak Vaneı, Emre Acartürk, Karthikeyan Shanmugam, and Ali Tajer. General identifiability and achievability for causal representation learning. arXiv preprint arXiv:2310.15450 2023.
[48] Julius Von Kügelgen, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf, Michel Besserve, and Francesco Locatello. Self-supervised learning with data augmentations provably isolates content from style. Advances in neural information processing systems, 34: 16451-16467, 2021.
[49] Julius von Kügelgen, Michel Besserve, Wendong Liang, Luigi Gresele, Armin Kekić, Elias Bareinboim, David M Blei, and Bernhard Schölkopf. Nonparametric identifiability of causal representations from unknown interventions. arXiv preprint arXiv:2306. 00542, 2023.
[50] Tony Tong Wang, Adam Gleave, Tom Tseng, Kellin Pelrine, Nora Belrose, Joseph Miller, Michael D Dennis, Yawen Duan, Viktor Pogrebniak, Sergey Levine, al. Adversarial policies beat superhuman go ais. 2023.
[51] James Woodward. Making things happen: theory of causal explanation. Oxford university press, 2005.
[52] 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:14891-14901 2020.
[53] Feng Xie, Biwei Huang. Zhengming Chen, Yangbo He, Zhi Geng, and Kun Zhang. Identification of linear non-gaussian latent hierarchical structure. In International Conference Machine Learning, pages 24370-24387 PMIR, 2022.
[54] Jiaqi Zhang, Chandler Squires, Kristjan Greenewald, Akash Srivastava, Karthikeyan Shan- mugam, and Caroline Uhler. Identifiability guarantees for causal disentanglement from soft interventions. arXiv preprint arXiv:2307.06250, 2023.
13

---

A Related works
The interventionist approach to causation For the problem of causal graph discovery, it is well- known that the underlying causal structure is non-identifiable given only "passively observed" (equivalently, i.i.d) data alone. As a result, randomized controlled experiments [16] is often used to infer causality. These experiments typically take the form of interventions [41, i.e., manipulations on the "natural state" of the system of interest. Early works [51, 42] define the "hard" (also called "surgical" or "arrow-bress (errow-beaakin") interventions in which the value of the intervened variable is entirely determined by the experimenter, thereby removing the dependence of this variable on its direct causes. This type of intervention arguably the most natural one to consider, and following this definition, line of works explore sufficient conditions for designing experiments that guarantee identifiability of the causal model in various settings [10, 45, 13, 20, 18].
Intervention v.s. passive observation While extensive works demonstrate the success of the interventionist approach, it faces several key challenges that significantly limit its applicability. First, Eberhardt [14] finds that in the presence of unobserved variables, certain causal structures are indistinguishable if we only perform hard interventions. This issue can be resolved by performing soft interventions i.e., interventions that do not remove the dependency on direct causes but only changes the conditional distribution. Second, pointed out in [44], interventions soft - are often expensive or even infeasible to perform in practice. For example, a psychological intervention is likely to affect multiple psychological variables simultancously Eronen [15]. As result, [44] returns to the "passive observation" setting but with multiple datasets with overlapping latent variables.
whether hard
Interventional causal representation learning Motivated by the interventionist literature in causal graph discovery, recent line of works [1, 16, 46, 49, 7, 54, 47] consider performing interventions to resolve the non-identifiability issue in causal representation learning [25]. Roughly speaking, these result indicate that identification (possibly with some ambiguities) is possible if one can perform intervention on every latent variable. However, it is unclear how to perform such interventions in practice, given that the underlying latent variables are unknown. Khemakhem et al. [21], Lu et al. [29]. Roeder et al. [32] do not require single-node interventions to achieve identifiability, but assumes that the joint distribution of latent variables in each environment lie in a certain exponential family, This assumption can be understood as prior on the latent variables, but it is unclear when or why it reasonable to make in reality. Recently, Ahuja et al. [2] considers learning causal representations from multiple domains that relate to each other via an invariance constraint on the subset S of stable latent variables, and they prove identification up to affine mixtures within S.
B Experiment details for Section 6
B.1 Details for step in Section 5
Since = B& = B& Ha in the k-th environment, so we can use any identification algorithm for linear ICA to recover the matrix M3. Note that while standard linear ICA algorithms only apply to the case where n d, for n > we can arbitrarily choose d principal components of æ to reduce to the n d case. This is without loss of generality, since when > d there is redundant information in xc
After recovering Mj for each & by running linear ICA, we still do not know whether each Ma corresponds to the same permutation of the ground- truth noise variables e. To resolve this issue, we choose test function v mapping any distribution on R to a deterministic real value, which we expect to take different values for different c; 's. We choose V (P)) = P[| < 1] in our experiments. For all k >> 2, we calculate the T value of each component of the d-dimensional empirical distribution P. : E 11 (N)) and choose a permutation F. rearrange them in increasing order. Then, rearrange the columns of M& using the same permutation Tk- This procedure would asymptotically produce correct alignments as long (c,,, i E [d] are different, and we find that it empirically works well.
Alternatively, this alignment step can be done as follows: for each pair of environments (E1, Ee), and for each pair of nodes (i,j), we calculate the distribution distance between 6; in environment E, and ey in environment E,, based some notion of distribution distance (e.g. kernel maximum
14

---

mean discrepancy). Then we find the min-cost perfect matching, where the cost of an edge is the distribution distance.
B.2 Details for the implementation of LiNGCReL in the finite-sample regime
Although LiNGCReL provably works in the population regime, faces several challenges when there only finite number of samples:
First, since rank is not a continuous function, it is sensitive to finite-sample estimation errors. In our implementation of Algorithm 3, in each iteration we instead choose & S that has the largest ratio between the first and second singular values of [q) 92, ........... qxl- And in line of Algorithm 2, we introduce hyper-parameter t1 such that the matrix (q) 92, ... qKK] { than tl. Since the smallest singular value of random matrix A E R-Kxm (K
is considered to have rank Tm'-1 if its -th singular value is smaller
K > m)
at the order of VK-
m with high probability [33], when K = d one shall choose
tl vd-vd- O Vdl On the other hand, for larger K we can correspondingly
choose larger t1. Note that small tl potentially has the risk of being dominated the noise in the estimation, which means that we need more samples per environment to reduce the noise. In contrast, for larger tl the estimation is more robust to noise and we can use fewer samples.
Second, sample estimation errors of M2 make it harder to obtain h; in Algorithm of Algorithm 3. We implement this step in the following way: first let Q2 be the orthogonal projection matrix onto E i.e., Q, x proje. (æ), then choose h; to be the singular vector
of Σ =r. j=z Q, Qj that corresponds to the smallest singular value (including zero). Indeed, in the noiseless case would have Er QjQ;) h; 0 if and only if h2 E (Dyit.))es n Ea.
C Further experiment results
SNA error v.s. true error We plot the SNA error true error achieved by LiNGCReL in Figure 3. We observe that
For most nodes, SNA error is exactly equal the true and both errors small, indi- cating that the corresponding latent variables have been successfully learned by LiNGCReL.
The remaining nodes typically have true error much larger than SNA error. This indicates that there exists some ambiguities these nodes in the sense that surg(i) (i) * 0. Note that the true error for many nodes are close to 1; one possible reason is that one selects the wrong singular vector in the second part of Appendix B.2, so that it is orthogonal to the ground-truth vector.
Sensitivity of LiNGCReL to the hyperparameter t1 We examine how different choices of t1 would affect the performance LiNGCReL. Specifically, we run LiNGCReL on the 100 models with size d = 5 and number of environments K sampled in Section with tl (0.1, 0.2, 0.25, 0.3) and the results are reported Figure 4. We can see that the permance is actually quite sensitive to tl.
15

---

SNA
10-2
10.
10
True error
Figure 3: Comparing SNA error with true error for the 500 latent variables in the 100 graphs of size d = 5 that we sample in Section 6.
Gooph recovry
Figure 4: Performance LiNGCReL as a function of 0.15 achieves the best performance in terms of both SNA error and graph recovery accuracy.
D Background on causal representation learning
is common to assume some axioms on what kind of (conditional) dependency information is encoded in a causal graph (see 41, Section 3.4 for detailed discussion). The most natural one the Causal Markov Condition introduced in Definition that gives sufficient conditions for conditional independence via d-separation. We introduce the formal definition of d d-separation below:
Definition (paths and colliders). Let i, two nodes of a DAG 9, a path a sequence of nodes dp i, f1, , = such that there is an edge (in either direction) between and izt1,J = 0,1, ,k-
node i, is called collider on this path if i E chg (iz-1) n chg (1++1)
Definition (blocked path). path in DAG G between node and node j is said to blocked by node set S if either of the following holds:
there exists a node on the path that is in S but not a collider, or
there exists node u on the path that is collider, but none of its descendants (including itself) are S.
Definition 7 (d-separation). For a DAG with node set [d], any two nodes i + j are said to be d-separated by set S C [d] \ {i.5} if all paths from i to j are blocked by S.
The minimality condition states that there is no redundant edges in the causal graph, and is a natural consequence of the Occam's 's Razor Principle.
Assumption (Causal minimality, 41, Section 3.4.2). For latent variables z, removing any edge from & would render violation of the causal Markov condition Definition 1. In other words, let 9 be the graph obtained by removing any single edge from G, then there must exist E [d] such that z; H. (ndg,()) (6) (p)g,())
16

---

The faithfulness condition states that the Causal Markov Condition actually entails all (conditional) independence in the latent variables.
Assumption 7 (Faithfulness, 41, Section 3.4.3). Every (conditional) independence in the latent variables is entailed by the Causal Markov Condition applied to G. In other words, 1 Z3 28 + 1.j are d d-separated by S.
Existing works have explored different notions of identifiability. For observational data, it is well known that Markov equivalence of graphs an intrinsic ambiguity that one cannot resolve:
Definition 8 (Markov equivalence/Faitful Indistinguisaabiityy. 41, Section 4.2). If two DAGs encodes the same set of dependency relations, we say that they are Markov equivalent.
Any DAG G induces a partial order on its nodes which we denote by <g- In the special case when for all i * j. either <g <g holds, say that <g is total order. This partial order is equivalent to the transitional closure of the graph, as defined below:
Definition (Transitional closure). Given any DAG G, its transitional closure defined to be the graph obtained by connecting all edges i + j where is ancestor of j in G.
When <g is total order, each pair of nodes are connected by directed edge in its transitive closure G. Such G is often called tournament in graph theory.
In the following, we list different forms of identifiability that appear in the literature:
Definition 10 (different notions of identifiability). Let H. RR 2 X + Rd be the space of diffeomorphic mappings from observation to latent, and B be the space of all DAGs with d nodes, thenfor h, h H. and G, 9 E C, we write
(i) [36, 23] (h,9) La (h. ②) if there exists a permutation π on [d] such that (g) and have the same transitional closure;
(ii) [49, 47] (h, 9) ~RLL (h, 9) if we actually have G = 9 for the & defined above.
Given an equivalence relation ~ on H x 6, we say that a causal model (h,9) is identifiable under ~ if any candidate solution (f,, 9) satisfies (h, ~ (h, The notion of identification up to -G. as shown in Seigal et al. [36] with single-node soft interventions linear causal models, is highly related to this paper. Compared with their result, our sur guarantee is must stronger, since not only the causal graph can be fully recovered, but the latent variables can be identified up mixtures of the effect- difect-dommnating sets as well.
E Illustrating examples for our theory and algorithm
E.1 An example for understanding the SNA ambiguity
We provide simple example below to illustrate the SNA ambiguity discussed in Section 3.
Example 1. Let G be causal graph with d = 3 nodes and edges + 2 and 2 + 3. We have access observations from a set of environments C. It turns out that there is way to distinguish between the following two structural equation models:
22 1 (z1, E2,
U2 1 (v), E2
23 J (22, 63
E
V3 U2 + J (v2, E3
8 (2), (2, k3)
x (V), U2 V3 02
where <F, i matter what environment E that we have.
1,2,3 are independent noise variables, if we do not change the causal graph G, no
This issue does not exist when we assume access to hard interventions on node 3, which effectively removes the edge 2 + 3. Specifically, with hard intervention on 23, the variables 22 and 23 become independent. But by definition, V2 22 and V3 22 23 must be dependent, so this intervention
17

---

cannot be realized by any hard intervention on V3 thereby providing way to distinguish between the above models.
Without node 3, the same ambiguity would arise on node 2. However, node 3 can help us to overcome this ambiguity, thanks to the fact that node 2 is the only causal parent of node 3. Suppose for example that v22 m(21, 22) is some mixture of 21 and 22, then v3 = f (v2, ( = f (m(21, #2), +5)) Since all environments share the same mixing function. V3 must be of z, where 1ha is the same across all environment Ft. Hence, we have
deterministic function (2(2))
J (m) the (21, 22, 22, 13 (22, (22,(3)
Now note that the dependencies of LHS 21 and #2 through single scalar-valued function m, but since we would have different f in different environments, this in general does not hold for the RHS. Therefore, any causal model with latent variable v2 as a mixture of 21 and 22 cannot be equivalent to the ground-trune trutt model.
According to Definition 3, in Example we have surg(1) (urg(2) = but surg(3) = [2].
E.2 An example for the main idea behind LiNGCReL
To illustrate main algorithm how can recover the graph G and the matrix H, first provide some intuition using a simple three-node example:
Example 2. Let G be the graph with d 3 nodes and edges + 2, + and 2 >> 3, that each Bg is of form
0
b&1
B& =
X
X
~y bu2
(8)
X
X
b&3
We can identify the graph as follows: first, E (1,2,3) 3). look at the space W; spanned by the rows (M&)i, k E [K]. If dim W; = 1, we know that i is source node (i.e.. pag(i) 0) in G. Otherwise is not, due to Assumption
Hence we can know that node is a source node.
In our example, there is no other node that satisfies this requirement. We then proceed to search for some + 1 such that the projection of W; onto Wir has dimension If this holds, then one can show that pag(1) {1}. Otherwise, i must have parents other than 1.
span (h1, h22)) = 1, but is not It turns this requirement is satisfied for node 2 since dim (projn, span satisfied for node 3 since dim (projn, span (h1, h2, ha)) > 2 (by Lemma 4). Hence we know that (2g(2) = [1}.
Finally, it remains determine (3) To do this, we first note that dim W3 3. Then we project W3 onto W and Wz respectively, and the resulting dimensions are 2 and As we rigorously show in Proposition 2, a decrease of the dimension exactly indicates finding a new parent. Thus we have (3g(3) = {1,2), completing the recovery of the graph.
Finally, we recover the unmixing matrix (and thus the latent variables) by noticing that h E W1. h2 E W₂ n W3 and h& W3. Ambiguities would arise at nodes and 3, which are exactly the nodes that have non-empty effect-dominnttin sets.
F Auxiliary lemmas
Lemma 2. For any family of m-dimensionall vectors {wx Jk and { if Uz 2&T and E Rmmxm is invertible, then
dim span (v, k [K]) dim dimsspan (zx : [K]]
Theorem 5 (Darmois-Skitoiis Theorem). Let 6,, [d] be independent random variables and X Xi -i= O,s,, Ysc,,Y = -i=1B344 If X Y, then for Vi E [d], oaB + O + <; is Gaussian
distributed.
Lemma 3. Suppose that 6 = (6 6d) is a d-dimensional random vector with independent components such that Var(c) 11 [d], and there exists invertible and non-diagonal matrix
M such that Me then at least one of the following statements must hold:
18

---

(1) there exists at least two Gaussian variables in 6
ccd ,
(2) M is permutation matrix and there exists & j & d such that 6 6--
Proof. Suppose that (1) does not hold, then there is at most one Gaussian variable in c,...,, Ca. We assume WLOG that é1, fdd1 are all non-Gaussian. Then by the Darmois-Skitovie Theorem, Ma = there is at most one non-zero
know that for < j entry in each of the first d columns of M.
< [d] and E 1], Mj
Assume that M * 0. E [d-1]: 1]. Since M is invertible, we know that k.. E [d 1] must be different. Let ka be the remaining element in [d] that does not appear in k i < d. then (Me),, ded while (Me),, M + Ma.dea Since the components of Me are independent, is easy to see that Mid # 0, Vi & ka. In other words, M only has non-zero entries at (ki, a), [d].
Since Var(e;) = 1, we know that M must be a signed permutation matrix. Finally, let и be the permutation on [d] such that Mis()) + O. Since M is diagonal, π must have cycle (i1, i2.... ......... .ik) with length & > 2. that - ,A all have the same distribution, which implies that (2) holds, as desired.
Lemma Let V1, V2 be two subspaces of RR such that V1 n NV {0), and Pv. be the orthogonal projection onto V₁ then we have that dim(V2) = dim Pv.- V/2
Proof. Obviously we have dim( V2) > dim (v: v2). On the other hand, let u1, U2, Mm be basis of V22 then w; = Pv. u,, = 1,2, m are also independent. Indeed, suppose that \ = 1,2, ... satisfy Ei Aww; 0, then Pvtt (E ).u,) 0, implying that Em duu; E Vi. However, we know that V n V2 (0). so λ1 Am This concludes the proof.
Lemma 5, Assumption is equivalent to Assumption
Proof. The main observation is that for each & [K], (BR); only has non-zero entries the j-th coordinate where j E (i) Moreover, let (i) be the vector consisting of these entries, then T (i) (52) (i), 1). Hence, dim span (( (Bx);
[K]) = dim span ((-w)(1),1) [K])
Suppose that Assumption 4 holds, then for Vo E (l) there exists d R, 1 & k < |pgg()) (i) Hence,
such that ΣΦ A = 1 and Σx d (()
(x, 1) = Σ Au (i) E span ((Ba): [K])
This immediately implies that span (Bx) E [K] R [l)gg()))++ so that Assumption holds.
Conversely, suppose that Assumption 5 holds, then for Vo E IR ( there exists d E R, < k < [iag(1) such that Et (1 = (x, 1). Hence we have E. ( = x and Σx d = implying Assumption 4.
G Properties of effect-domination sets
Lemma 6.
j surg(i) if and only if (i) C chg (j);
when + j. E surç(i) if and only if chg C ())
Proof. j E sir by definition E cha(i) and cha(1) C che(i), , so that cha(f) C cha()). Conversely, chg(() C chę(j) implies that chç(i) and chg S che(f), so surg(i). This proves the first claim.
19

---

To prove the second claim, assume that ch) S chg(() holds but (i) S chg(j) does not hold, then we must have j E (i) since j * i, we have j E (ig but then & chg(j), which is contradiction. Hence cig(()) S chg(s) and the conclusion follows from the first claim.
Lemma 7. Let 9 be a DAG and be its node, then for Vj pag(1), we have surg(i) S pag(1).
Proof. Let E surg(i), then by definition we have cha(s) S cha In particular, we have i chg(k) = pag(i).
Lemma 8. Let 9 be a DAG and be its node, then for Vj E surg (i), we have surg(i) C surg(i).
Proof. Let k E (i), then by definition we have cha(f) (k) We also know that chę (i) C (i) so (t) (h)( implying that surg(i).
Lemma 9. If M E Mar(()) (9), then M-1 E MM (9).
Proof. Assume WLOG that the nodes of G satisfy i E pag(i) + < (otherwise we can choose a different index of the nodes and correspondingly swap some rows and columns of M). Since i (J) = E pag (J), it follows that M must be lower triangular and the diagonal entries are nonzero.
Let N = M then for vi E [d]. we have
Σ
M2
VE o sur s (i).
Since M (9), we have Mie for Vj such that & sug (j). By Lemma 8, jf E surg (i). then &f (i)g(i) necessarily implies that l & su)g(j). Hence the left hand side of (9) is essentially
sum over j & surg (i). i.e.
Σ (1)
M2 0, 0, Vl (i)
Viewing the above as system of linear equations Ney. & surg(i), the coefficient matrix (Mje) (.E must be invertible since it is sub-matrix of the invertible lower-triangull matrix
M. As result, we necessary have No = 0, Vj & (i)g(i). Finally, N = =M-1 must be invertible, so N M (9) as desired.
Rd is diffcomorphism and G be DAG, such that for Vi [d]. (z) is function of Zsmeg(() Then Vj E [d]. (x))))(00) is a function Usung 0sm (1)-
Lemma 10. Suppose that Rdd HR
Proof. Let J= (z) be the Jacobian matrix of vb. Since v is diffeomorphism, J= is invertible for any z E Fdd Moreover, our assumption implies that (J2)ss By Lemma 9, J= Mo (G). But J= is exactly the Jacobian matrix of th follows that (v ()))) is only a function ()) as desired.
Vj & suig (i), so Jæ e M (9).
(2),,, hence
Lemma 11. The binary relation rsu defined in Definition 4 is an equivalence relation.
Proof. is obvious that (h, 9) Ysur (h, 9) holds for any model (h, 9).
Suppose that (h1, G1) suur (h2, G2), then there exists permutation i [d] and diffcomorphism Rd + Rdd where (z) is function of Zaure, (4), such that i E pag, (j) <> T(i) E pag, (=())
and Ps o h2 = ab hj. Then we can write P o h = & h2 where & = -P-' - - Pa.
By Lemma 10. know that (b-1), (v) is function of Usure, (i), so (v), is function of 2 (x(a,, (1) = Manre (1)> implying that (h2, 92) ~uur (h1,
20

---

Finally, let (h1, 91) Nour (h2, (2) and (h2, G2) ouur (h2. Gs), then we can write
Pa h2 - vb o h1 and Ps hg = & a h2
where: for Vi E [d], (z) is function of Saure, (1), (z) is function of (1), E pag, (i) +> T(i) E pag, (i()) and E pag, (i) + #(i) E pag, (f(j)). Then,
write
Px O 0 Ps o P o h1.
Since (z) function of Zsurg, (1), we deduce that Px o Pr (z) a function of Ssurg (+)
Hence, (P+ o P ) (z) = Px o up Pa. (1b(2)) is function of Meura, (1) (z). The definition of do implies that for each E surg, (1), (2) is a function of Ssuro, (i)- By Lemma 8,
we have Ujssure, ( (i) S surg, (i). Hence
Px o Po (z) is still function of e (i)- Moreover, we also have i E pag, (j) + x1) E pag, (T(i)) + स (() pag, ( π (f)).
so by definition, (h1.9)) ~sur (hz, Gz). as desired.
H Omitted proofs from Section 4 and Section
H.1 Proof of Theorem
According to the assumption, we have that 6 = B₁ Ha and = BaHr so that é = B₁ H HB,, vk E [K]. By Lemma 3, we know that for each k. Ph = (B,l)) is
a signed permutation matrix, so that ε = P.ć. Since for any * j. & + Ej. we must have Pix P and the absolute value of all entries in M. Thus, we can WLOG assume that c = é, since otherwise we permute the noise variables 2, and also permute the rows of B₁ correspondingly. In other words, suppose that the permutation matrix P| has Pl 1, E [d], then we can assign to each node i & a new index k; and work with the new indices.
[P] = PP2
Pé, where M denotes the resulting matrix by taking
In this case, by Lemma 3 we have B E, Yk E [K] equivalently E, B,T, where HHİ gaxd, and Σg is a diagonal matrix with diagonal entries in {+1, -1]. Let B₁ Bg then the rows of B& equals (up sign) to the rows of B
To summarize, we now know that i) B₁ B,T,K k E [K], ii) (Bu)y #0 (i). and similarly, (Bx)ss + 4 + j E (i) and iii) Both { and [x satisfy the node-level non- degeneracy assumption Assumption 5, For any two such matrices that satisfy such set of conditions, it must necessarily be true that G = G
Lemma 12 (Graph Identifiability) Consider any two sets matrices (BR and (BakKeK]) and associated graphs G.G. If these sets and graphs satisfy that:
1. B
[K];
2. (Bx)i # #0 j pag(i), and similarly, (Ba).g #0 E pag(i).
3. Both {Bx} and {Ba)) satisfy the node-level non-degeneracy assumption Assumption 5.
then it must hold that G G.
Proof. We prove this via induction on the size of the graph d. Note that here G = G is not up to permutation and our statement equivalent to pag (i) = pag Vi E [d].
If d 1, i.e. G 9 obviously holds since both graphs with only node.
21

---

X x Suppose that for all graphs g of size d - 1, the graph 9 satisfying all given assumptions must necessarily be equal to g. Now, we consider the case that & has nodes. WLOG we can assume that the nodes of G are properly indexed such that i E p)g = i < J. so Bg, k E [K] are lower-triangular matrices. (However, it is currently unknown whether B₁ also lower-triangular))
By our assumption that i E pag(j) + i < j. the node d in 9 has no child. Thus we can write
B BB bk
(
T T X
and B B (
k
X
where BB T, 2 B T E R(d-11x((d)) by E Rd-1, Ck R and denotes irrelevant entries.
Let AT, A and S be the top-left (d - 1) (d - 1) sub-matrices of Ak; A, and S2 respectively, and g- and 9 are graphs obtained by deleting node d and all related edges from G and g. Then it is easy to see that
(A #0 j E pag (1) and (Ai). in
#0= paz-(a)))) (1).
(10)
Moreover,
(
B R b%
0
2 (I An) - By 2t
(S2g)
0
)
(
I
A
x )) = -
x
(St
(I
- A
x
Cj
x
x
x
x
so that B (1%))
$ (I A ). Similarly, we have B (5
(I A
We can also verify that { B ] K sumption 5. We only prove this for Bx x= the arguments used for {B are exactly the same as the first case considered below. Now for each E [d 1]. let R. E IR xxd be the matrix whose k-th row is the i-th row of B2, and R E (xd-((1)) be the matrix whose k-th row is the i-th row of BR then obviously R; is of form [RT rr:]. We consider two cases:
k=1 and [B, 1* K K
k=1 are node-level independent in the sense of As-
Case 1.d é (1) This means that the last entry of the i-th row of B₁ is zero. Thus r; =0 O, and rank (R. rank (R,) paag pag- (i)] where the second equality follows from Assumption 5.
Case 2.d E (i) In this case we have rank (R,) > rank (R,) - = pa (i) 1
pag- (i) Due to our assumption on A and the relationship B = (52
(I- A
we know that each row of R,, namely the i-th row of some 7, only has |pa (i)
pag-(1) (i) non-zero entries, so that rank (R, ) = pag- (i) holds.
Since we have shown that the matrices B3 and B satisfy the three properties that we assume for induction with T replaced by T and G, 9 replaced by -- respectively, by induction hypothesis, we can thus deduce that g g- To prove G = 9 it remains to show that the dependency of node d on the remaining nodes are the same in & and g.
First, we show that ch& (d) = 0. Suppose in contrary that there some E cha(d), then (ia = |pag- (+) = |pag- (i) = |pag (i) - 1. Recalling that (B); denotes the i-th row of matrix B, we have
dim (span ( (Bx) :1 < :I< K)) dim (span (Bxx), 1 & k < K))
(11)
< (1) + < pia (i) +
where the first inequality follows from (Bx), = (Bx), T and Lemma 2, the second holds since each (Bx); has nonzero elements only at coordinates in j E pāg (i), and the last one holds since
22

---

(0) = (aa - 1. However, (11) contradicts the non non-degeneracy condition Assumption that we assume for matrices B k E [K] in the statement of the theorem. Therefore we have clg(d) (d) = 0 (d)(
Second, by similar argument comparing the number of nonzero elements the last row of Bg and Bg, we can also deduce that
(d) = |pag(d)
Indeed, since (Bs) d
= (Bk)a T, by Lemma we have
dim span (Bx) 1 ( dim (span ((Bx) : 1 k & K))
However, since assume that Assumption is satisfied for {Bw) and BB ) K
we know that + respectively,
the LHS and RHS of the above equation are equal to (pag(d) + 1 and |pag (d) k=1 implying (12).
Third, we show that (d) = pag(d) Suppose the contrary, let be the smallest element in (d) where AAB == (A B) U (B A). Recall that while G and & are originally not symmetric as nodes are topologically sorted according to 9, now we have shown that G = 9 and that (d)(d) = (c) = 0, so can assume WLOG that & E pag(d) and & & (ag(d), and the other case can be handled symmetrically. Since By lower triangular and (Bx),, = (5t) * 0, Vjj E [d]. the top-left f x sub-matrix Bx, which we denote by [Bx],e. must be invertible. This implies that [BRlI. A: AE R$) -R', can always find coefficients Akj.J [E] such that the first& & entries of the vector (Bx)d Ei dni (Bx); R.d are all zero. Since B, B&T and T is invertible, we have (Bb). - Ei=1 Aaj (Bx), = ((bs) - Ej= Aay (Bx), T. vk e [K]
and
dim
span
(Bx)
Σ Akj BBx) k E {KK]
= dim
span (Bx) Σ
ARj (Bx), : k E (K))
j=1
< (pa \ [E] +1.
Here, the inequality holds because for any coordinate / E [d].
0 ift
(Ba)a Σ AkS (Ba), 5=1
- (Bx)) otherwise
(12)
where we note that B& is lower lower-triangulat and thus (Bx),,: = 0,4o & l,t > l. This implies that
((Bs)a (Ba)a-En- A (B+);), ); nonzero only if andnd E pa)(d).
On the other hand, let (pag(d) [e]²) U {d), then
span ( ((B)).
dim
span (Bx)
Σ 1=1
Akj (Bx), k E (((K)
> dim
- - Ans (Bu), j=1
: k E [(])
((Br))) k (ki) <KEIK)))
= dim
Span
S|).
where we recall that u. denotes the vector (w; i S) E RiS Here the first equality holds due to the same reason as (12), and the second follows from Assumption 5. To see why this is the case, note that Assumption implies that the K ([pag(d) 1) having ((Bx)d)pxgh (d) as the k-th row has
full column rank, so that the sub-matrix obtained by extracting columns corresponding to the node set S also has full column rank.
23

---

We have shown that (d) n [49 |s| < (da n [4] + 11 = pa (d) n |89 On the other hand, recall that by choice of L, have |pag (d) n [ | pa n 1] and l E (ag(d) \ pag(d). Putting these together, we have [pag(d) > [pag(d)] However, we know from (12) that |pag (d) = (pag(d) leading to a contradiction. Hence, such é shouldn't exist and we must have (d) = pag(d) completing the induction step for graphs of size
By the principle of induction, have shown that = 9 holds for any graphs under given assump- tions.
Now that we have established that G = G. we prove the remaining part of the theorem. Note that for any i.j E [d] such that i & pāz(j), we have (Be)ji (Bx),= = 0, vk E [K]. Since B, BBT, we have
Σ
B =0
éEpa (1)
By Assumption 5, the above implies that Ta = for ve E pāg(i). ) In short, we have argued that if there exists such that (f) and pag(i), then Ta =
This implies that Ta is non-zero only if (hg(e) S chg(1). Since Tz, we have Vy Ei Te = Exed (h Tazz, Note that when + cha(f) S chç(1) equivalent to i E surg((), so by only depends on (s))(()) by Lemma 6, as desired.
H.2 Formal version and proof of Theorem 2
In previous works [36, 54], is common to consider single-node soft interventions in the following sense:
Assumption For 42 < < K, there exists is E [d], such that the structural equation in environment k satisfies (4) satisfies (1) wi(1) and Wk,t, W1,1, for Vi + ig.
Let S; = (k: : 2 & K = i) E [d] and 8; = |S:|- Suppose that G has 6 Eie (i) edges, then we can view the weight vectors {(wx(1) wa. : = or = ix. as elements of the
Euclidean space E
1 Under Assumption the models can be fully determined by these weight vectors. The following result states that if we restrict ourselves to single-node interventions, then in the worst case, ( interventions are required.
Theorem 6. There exists causal graph with (dd²) edges, such that for any unmixing matrix H E dd with full row rank, any independent noise variables and any 8; 0, [d] such that 8; & |pag(()] for some i, the following holds: except from a null set of the weight space Re Re+EN [pagpll R4-K-1 (wort the Lebesgue measure), there must exist a candidate solution (H, 9) and a hypothetical data generating process
Ak E [K], v A&u D.c. x =
such that
(t') the unmixing matrix H E Bdxn has full row rank;
(it') Yk E [K] and i,j E [d], (Ax)is + #0 j E paa(1) and 2n is a diagonal matrix with positive entries;
(ii') for 42 < & K, the weight matrices A Su of environment Ex are from a single-node soft intervention E, on node ig, in the sense of Assumption 8,
but is con-isomopphic G.
In this subsection we give the full proof of Theorem 6. We say that S C I is null set if it has zero Lebesgue measure. Obviously, any hyperplanes in m are null sets. We will also need the following simple lemma:
24

---

Lemma 13. Suppose that m E 2, and V is subspace of m.. Then for any set of vectors E R. i 1.2, ,n that does not lie in V. there must exists R such that u, + 0, vi [n] but V+,, where V is the orthogonal space of V.
Proof. Let w, be the orthogonal projection of u, onto V Since u, & V. know that w, # 0. The solution space of each equation w; v = V must then be proper subspace V Equipped with the Lebesgue measure, all these spaces are null sets in V+, so one can always choose a E V- that does not lie in any of these solution spaces. Such v satisfies all the requirements. O
We choose 9 be the graph with i + j for V1 <i<j & d, so that & has d(d-1) edges. Suppose 2 that in E [d] satisfies s; < ( - 1, then we must have in > 2, so there is an edge + io in G.
Let & be the resulting graph obtained via removing the edge + ip in G, then G and 9 are clearly non-isomorphic.
Note that the i-th row of By can be written as w (e; - (Ax).). Let's choose lower-triangular matrix T = -(ti)) E Rdxd with columns t; E [d] such that the following holds:
= O, Vk [1] US. = and & E {1] U.
and i io
(Ax((A))) (Ax)c) 1,3 =
-
> O,
i} # O, v remaining (i.j, k) E (k 1,j < -
2i
(13)
and
4 # O, Vi [d].
(14)
We now show that: except from a null set in the weight space, such can always be chosen. To see why this is the case, first consider all the constraints on t
= 0, Vk {1) U S., and i i (e: (Ax)) t1
> O, = 1 and & E U
(15)
# O, A remaining (i,k) E (k (k=1, ((
Now let V = span (e, (As);
U1, and i =
io) and It be the set of pairs (i, k) specified
in the second and third row of (15). For v(i, let w)((1) be the weight vector of node in the environment k. i.e., the vector of nonzero entries in (Ax).. Then for V(i, k) R, the following set (as a subset of the weight space)
U
{ero wk- (1o) E span (e, wx(1), ei wp) :Kk: (1) \(*H)) (16)
k E11jUSs
must be a null set. Thus
E
U
U
(eio wk- (fo) span (c: wk. (i), Cig ww (1o): E (1) Sip \ (K*)))
(R.))ER
(17)
also a null set. For any weights that are not in E, we necessarily have
e; wx & span (e: (As): & E (1) U St, and i io) VV. (L,
Let U = {e: un (i) ki, E RR, then we can apply Lemma 13 to deduce that there exists t such
that
f= 0, vk E (1) US, and in (e. - (Au))) T ti = { 0, v remaining (i, k) E {k 2 i
(18)
2,
Note that the only difference between (18) and (15) that the latter one further requires that
(e1 (As)1) > O. vk E (1)
while the former only guarantees that these terms are nonzero. However, recall that (Aa)s; # 0 + j E (i) + j < i, so the above essentially says that (11 > 0. This can be easily guaranteed by replacing the solution t obtained satisfying (18) with -t, if needed.
25

---

Assuming that the weights do not lie in the null set E we have shown that ti can always be chosen to satisfy all constraints imposed on it. We now proceed choose the remaining entries of T. The remaining entries in i can be chosen arbitrarily. For f > 1, we note that the remaining constraints in (13) that need to be satisfied consist of the "nonzero" part and the "positivity" part. The positivity constrains can always be satisfied by choosing sufficiently large رزj for j > 1.
After choosing the i is satisfying the positivity constraints, the nonzero constraints along with (14) are easy to fulfill by slightly perturbing Łj if they are violated; since each of these constraints are only violated in zero-measure set of the weight space, Hence, we have shown that except a null set E in the weight space, there always exists some T satisfying (13). Such T must be invertible since it is lower-triangular and its diagonal entries are nonzero. Now let H = T H and Q2 be the diagonal matrix with entries W = ta Wk.ii. i E [d] and
A = 1 - 22 Ac)
(19)
First since T is invertible and H has full rank, H must also have full row rank. Second,
{ -ot (e: (Aa)i) t, =0 ifj (e, - (Aw))) t if i.j.. where we again recall that both Ag and T are lower-triangular. From (13) we can see that
- a W = 0 if =
(Ax)as
When i = io and j = 1. we have
(An)io.1 = Of & E (1) Sig, U and
(Ax) = kA. = if & {1)U Sig, by definition of S and Assumption 8.
When i j and (i.j) + (io, 1). we have
- (Ax)ss # 0 Of k- = 1 or i = d which directly follows from (13), and - -(Ax);) = (Á kg # O. by Assumption 8.
To summarize, for each k (At); + 0
(1g and (i,j) * (fu, 1).
Finally, let (i) be the weight vector of node in environment & in the hypothetical model i.e., the vector of nonzero entries in (Ac). and Ts be the submatrix of T by selecting the rows and columns in the index set S, then by (19) we have that
if io W k (i)( [10, (b)(()) if i ig
WRii, 1s
Wkiid
(20)
By our assumption, for Vk > 2, 2 is + wx(i) w (i) and Wk.s. = W1,1.. Thus (20) imply that vk > 2, i * i = (i) = td (f) and WR.i.; = W1.... In other words, single-node intervention on node 4 environment A in the ground- -ruth model corresponds to single-node intervention on node 4 in environment & in the hypothetical model, thereby completing the proof.
H.3 Proof of Theorem
We first prove lemmas.
Lemma 14. Vi E [d], we have span ((M+); : k E [K]) = span (hy ; E pag(i)).
Proof. Since (M&); = (B and (Bt);s * 0 + j E (ig( we can see that (Mş); i E span (h, : E (i)( On the other hand, since H is invertible, by Assumption 5 we have dim span ((M&); k E [K]) = dim span ((Bb): : l E (K]) = [pa)())- Thus we must have span ((M+); k E [K]) span (h, : (i)(
O
Lemma 15. Let S be an ancestral set of graph G and V span ((Ma):: : kk ke [K]. Then
we have V1 V2 -... VK = span (hg E 5).
26

---

Proof. Recall that M₁-- = B H, so for Vss E the s-th row of M2 can be written as
(M&). Σ (Bssshh = Σ
(Be)sthe E span hhs 8 E ES)
(21)
sepu (s)
where the last equation is because $ is ancestral 7 pāg(s) S S. Thus, for Vk E [K]
Ve span (Me), : E s) S span hh, is E s). On the other hand, recall that both B
and H have full rank, Mg has full row rank well, which implies that dim Va dim span h, E 5). Hence, V span (h, : E 8) wk E [K].
|||
The following two propositions show that our algorithm always maintain an ancestral set, recursively adds a new node into the set and correctly identifies its parents.
Proposition 3 (Proposition I restated). The following two propositions hold for Algorithm 3:
aisg(1) C + the if condition in line 8 of Algorithm is fulfiled;;
the set S maintained in Algorithm 3 is always an ancestral set, in the sense that j E S ansg(j)
Proof. At the starting point, we have S 0 which is obviously an ancestral set. Now suppose that after the f-th iteration, S = {3i. $2, 8t) } is an ancestral set. In the following, we show that (i) S S the if condition in line 8 is fulfilled. This would immediately imply that there always exists node that can be added into S in the (f + 1)-th iteration, and that after adding i, S is still an ancestral set.
Suppose that (i) S. S. for some & S. by Lemma 14 we know that (M&)s E span (h, j E pag (i)). so there exists Og E TK such that (M&); - agh, E Espan (h, =J E pa)(i)). Moreover, since (M&); = EoEpag(o) (Bx)g (Bx)u Wkii, & o O and H has full row rank by assumption, we must have (M&)) & span (h, : E (i)((t)) and so ag * O. Thus, we have by the linearity of the projection operator
4k = projve ((M+). = proiv. ((Ms): - axh;) + proiv; (axh, = axproiv; (h:).
Recall that all the V 's are the same and equal span (h, E by Lemma 15. So dim span (qx:
[K] & 1. Since has full row rank, we have h; É span (h, :hsss S) Va. so that dim spaspan span (gk k E [K]) = 1 holds, which is exactly the if condition in line 8.
Conversely, suppose that there is an é S such that ais & S but dim span (qx- : k E [K]) holds. Since S is ancestral, we know that there must be some j E pag(i) such that $ S. Since e; and e, both have support on the coordinates in (a) by Assumption we know that span(e,, eạ) C span(( (By): l E [K]). so that span (h, h2) = span (e,, e,) H S (Baa((BB))
k [K] H span ((M)); ):: k E [K]). Since dim span (gk k [K])
1, there must exist some vector u E _R" and 0% aý E IR such that h, a,u, h2 a, u E V4 = span(h,
E S). Since i and H has full row rank, we can deduce that h, h, & span (h : E S), and so both of a; and ay are non-zero. Hence h, - a,h, span(h, E S), which is impossible since we know that H has full row-rank.
Proposition 4 (Proposition 2 restated), Given any ordered ancestral set that contains pag (i) for some & S, Algorithm 2 returns set P. C S that is exactly pag(().
Proof. As we have shown in Proposition 1, for each possible input (S, to Algorithm 2, both and UU {i} are ancestral sets, so that ansg(i) C S. Similarly one can see that inside the set S: {81, 82, ...... (mm] J. all the ancestors of 8j are contained in {81, 82, ,8j-1). In the following. show that Vm'
I'm
pag (i) {sy j < m²) (*).
27

---

By Lemma 15 we have W1 = W2 = Wk = span (hee : m²). Let 12, :. be elements of (i) that are not in (sy j & m² J. then
I'm dimspan (p&
[K]) dim proj span ( (ho, stem!)
span ((M)) k [K])
dim
proj span (M, J span h pāy(i)) (by Lemma 14)
dim
[ro] (h,, u span (ht, hes hi,)
=t (by Lemma 4 and non-degeneracy of H)
which proves (*). From (*) it easy to see that vi' (ig (and thus in pag(1) since & S) if and only rm
-m
Now we conclude the proof of Theorem 4. Propositions and 2 directly imply that Algorithm able to exactly recover the ground-truth causal graph G. It remains to show that Line 20 in Algorithm produces the correct h4's. By Lemma 14 know that Ej span (he : & pag (j)),
()) Ej = (e (he paa(i)) = span (h4 l surg (i))
where the last step holds because H has full row rank and Nye (1) pāg(j) = (1) by definition. Hence, each h, is linear combination of h2, E (i)g completing the proof.
I Identification limit of general causal models with soft interventions
While Theorem guarantees identifiability with general environments, only applies linear causal models. In this section, we show that if we have access to single-node soft interventions, then we can identify general non-parametric causal models up to ~uur- To obtain identifiability result, also require that the environments are non non- -on-eegeeeeate in the following sense:
Definition 11 (Non-degenee) degeneraccy set of interventions). Let P& (z: ()ag(1))
[K,] be conditional
probability densities node i, then (Px {px)k=,, said to be non non-degenerate node i point & B if all these conditional densities are well-defined and positive at 2, and the matrix
T (5z/ 0z,
R (Kx:)1)((ppa(X)))
Kr.EKr)) ===
has full row rank. Moreover, we say that {px (px)K= is non-degenerate in point set O for all O. is non-degenrate at 2.
The following lemma shows how Definition 11 related to Assumption 5 in the linear setting:
Lemma 16. Suppose that pk(22) I Pk (z: (pag(t) k E [K] be probability distribu- tions of latent variables generated from the linear causal models (3), such that for Vi E [d], Pk (zi ()) kk E [K] are non-degenerate node i in the sense of Definition 11. Then the corresponding matrices B k [K] satisfy Assumption 5.
Now we are ready to state our main result in this section:
Theorem 7. Suppose that we have access to observations generated from multiple environments (P&) FEe. Let (n.9) be any candidate solution with data generated according to Assumption 1 with latent variables h((x) and joint distribution qE with factors of Assuming that
(i) the joint densities {pæ(z)) BEe are continuous differentiable on Id with common support continuous differentiable on IRd with common support O.:
Oz, and (4)(v)
(ii) we have access to multiple single-node soft interventions each node with unknown targets: there exists partition - E. such that I.. = {m(1)), IS. = (x)())) E [d] for some unknown permutations and x' on [d];
(x'
28

---

(iii) the intervention distributions on each node are non-degenerate in the sense of Defini- tion 11: there exists N= S O² and N. S O satisfying No N @ where S denotes the interior of a set S, such that for all i E [d], ():() E (x-1(n) (resp. {gt (.) E (x) ) non-degenerate on node i O₂ N₂ (resp. O,, No).
Then must have (h, 9) suur (h. 9).
Previous works on the identifiability of non-parametric causal models typically require that all the joint distributions supported on the whole space IRd [49, 23, 47]. In contrast, we only assume that the densities have common and unknown support across all interventions.
Theorem 7 can be regarded as a soft- inttintteveenion version of 49, Theorem 4.3, which assumes access to hard interventions and only need two paired interventions per node. While they are able to show full identifiabilitt we show in the following that identifiability up <sur the best we can hope for with soft interventions.
Theorem 8 (Counterpart to Theorem 7, informal version of Theorem 10). For any causal model (h,9) G) and any set of environments c {Ex k E [K] such that all conditions in Theorem are satisfied, there must exists a candidate solution (h, and hypothetical data generating process that satisfy the same set of conditions, but
# O, Vj E Suig(i). θz,
Finally, the ambiguity still exists if we additionally assume standard axioms such as causal minimality (Assumption 6) and faithfulness (Assumption 7) on the causal model.
I.1 Proof of Lemma 16
Let (x)()) E R (8) be the vector obtained by removing all zero entries in the i-th row of
A and Wh,i, be the i-th diagonal entry O2k then for the k-th environment we have 2; (1) (())(t) + + wi.,, so that
Pu (zs ()))(()
Wk Pe, (w (wx(i). (p))
where Pe, (.) is the density of 6,. result, we have
P1
Vlog PI (zi (p))(1))
(z: x1)g(t))
(zz (1))(())
P&
pk.
P1
(z: (p))(t))
Icn (1, w)]( - cu (ix))
Pk
where for convenience we use V to denote the gradient with respect to all variables ppaz (1) and
1 p/g Gsk w Pes
( (uxx (pmc (we omit the dependency on for simplicity).
Definition 11 implies that span (ca (1, w (i)) Csa (1, w. (i)) : 2 k < K) 10/+1
thus it holds that (()) : E [K]) = (1)++ as well. By definition of Bg, this immediately implies that dim (span ((Bx); ) E [K])) = ppgg (i) as desired.
I.2 Proof of Theorem
Define T : h o h-1 Rd + Rdd then we have that v 7xx). Since both h and h are diffeomor- phisms by assumption, so is т. To avoid confusion, in this section we use z (resp. v) to denote random variables while using & (resp. Ô) to denote (deterministic) vectors.
be the j-th collection of environments according to our assumption. We first prove the following lemma:
Let E, = EEE
[K,]] }
Lemma 17. O, T.2)).
29

---

Proof. By the change of variable formula [35], for V2 E R and AE E E we have P5(2) qr det (2)1. where (()). Since is a diffeomorphism, we must have |det J,(2)] + 80 2 E O= e 0 (2) E Ou: concluding the proof.
17
Lemma 18. Let E 22 For vj E [d] and 2 & & Kj, we have
B
Pj
(2) (p))(1))
q
@pag())
(22)
Pj
qj
where ô = =2) w...
Proof. Since T(2), by the change-of-mennn mewssre formula [35] we have that for 42 E Oz,
II pp (2: (p))(()) = p=(2) (0( Idet J-(+)| II of (Tr(#) (1)) det J (x) i=1
i=1
(23)
E(1)
for all E' E E, where e = T By Assumption (ii) and Definition 2, we know that p; = P; 4
E
E(3)
i + and q, qi + i 1 for all k: > Thus, we have that
(2: 2pp)(())
Pj
(2)
(p)
Ps
(2: (1)
Pj
and
9:
(Øt
(a))
9:
0; 0
pagg())
Since the LHS of the above two equations are the same by (23), the RHS must also be the same, concluding the proof.
We assume WLOG that the vertices of are labelled such that + + i < j. and that t(i) = i, Vi E [d]. Also we can assume the nodes are fixed and only consider how they are connected, i.e., x (i) = i, Vi E [d].
Lemma 19. We have (T(Nz)) (N.) = 0.
Proof. The result immediately follows from the assumption that N No = and that r is a diffeomorphism.
For any vertex set V, we use Gy to denote its corresponding induced subgraph of G. We first prove the following statements by induction j:
(1) vi VjiE pag(i) + i pag. (i);
(2) Vjj E [d]. there exists continuously differentiable function & such that ey = 03 (zpa,ti)
Moreover, del žz, # 0 (i.e. not always zero).
(3) Vj E [d]. there exists a continuously differentiable function Y, such that Upa.()) = Y (i))
For j = 1, by assumption pag = 0. Lemma 18 implics that for any O.,
(())
E(3)
P
(21)
q1
(ppg(1)) 42 < k < K1.
(24)
P1
q1
'This also WLOG because we now groups of soft interventions where each group corresponds to single node, just relabel the node in & that corresponds to the i-th group node i.
30

---

Then for Vi E pag (1), taking the partial derivative w.r.t by gives
1))
4 k
E
0 91
01
opag(is) =
P1 P1
(21)
dz1 0e:
(1
8pag(o) =
P1
(2)) V
0ū:
Ela
Up
E
E Pi
91
Thus,
2 (
rank
V tt)
(n )paa(1) 2 & K1 E
<
Note that the above inequality holds for VO E Og. If (ag * 0. then this would contradict the non-degeneracy assumption (iii) which implies that the above matrix should have rank / 2 at some point ê E O Hence we must have p1g(1) = 0, implying that (1) holds for j 1.
g0
Taking the derivative of both sides of (24) w.r. 21, i > 2 implies that
4s
i1))
801 82
= 0. By
91
our assumption (iii), for VO E Oz No. there exists 2 < k < Ki such that
21 (ö1) + 0.
91
and thus we have 0ē, 0, E - (Op N.). Since is diffeomorphism, we can deduce that 05,
T (Op \ No) 0² T (N+) and (T (N+ = 0 by Lemma 19. As a result, we actually have 85. 0, V2 E Oz. Hence in O₂ there exists a continuous differentiable function Φ1 such that 11 = (21) ). proving (2). Finally, (3) directly follows from (2) since p1g(1) 0, concluding the proof for = 1.
Now suppose that the statement holds up to j -- and we need to prove it for j. Again by Lemma 18 we have for V2 E O₂ that
Pj
ref (3)
2 2p)g(()
= 9j
0g
0pag()))
& Kj.
(25)
P3
qj
For all & (j), taking partial derivative w.r.t. 2i gives
00: 0 0pac())
0= Σ
O2,"
(EDA
qj
i.e.
E(5)
q
0g 8pp66)) :2 1 k < K3
0ipx, 0.
Tpp ( (3)
E
02,
qj
Similar to the j = 1 case, by assumption (iii), we know that the above corfficient matrix has full row
rank for V0 E O, \ No. so for Vz E ET- [O. No) = =0 1 (Nv), we have 06ps2(5) 0. Since (T (N.))
8z:
0 by Lemma 19, for all 2 N= we can choose a sequence of points 20)) i = 1, ... in O₂ such that 2(1) + 2. Since T is a diffeomorphism, its derivatives are
a650
continuous and we can deduce that 06mp lim as
0. As a result, 00mg(0) 0
02.
dz.
actually holds for all z Oz. Hence, there exists continuous differentiable function T, such that Up=z() = T2 (n))
By our assumption. ()) S [j- Suppose that pas(i) & (i:i< j.. let pas(i) j}. then by induction hypothesis, ú; = 7 (2), 2 Oz, t= 1,2, .j. l are all functions of 21, 23- Since T is a diffeomorphism and O₂ is the support of the distributions Pg, E E E, we can deduce that the support of the latent variables (v, t = 1,2,... ... .J. lie submanifold with dimension < j, which is impossible since is supported on the open set O C R2 by assumption (i).
31

---

Hence, we must have () S (i: Furthermore, if there exists E pag(5) such that i $ pag(i), then the induction hypothesis implies that /2. # O, but v, is function of (pag()) as previously derived, which also a contradiction. Thus we actually have pag(i) S pag(i).
In a completely symmetric manner, we can take the derivatives of (25) w.r.t. Vi, Vi ( and obtain that (f) C pagg(j) Hence, pag (i) - (J) completing the proof of (1) and (3) for the j case.
Finally, if 00; = 0, then by (3) and the induction hypothesis, 11 , by are all functions of 1|-- āz; which implies that (v1,... ,yy lies submanifold with dimension & 1, again contradicting assumption (i). Thus de,
0zy # O. This completes the proof of our inductive step.
To recap, we now know that
. G = G and
* For Vi E [d], there exists a function Y2 such that (png(() = Tr (Zpag(t)).
It remains to show that for Ak pig(1) \ surg(t), T, doesn't 't depend on #
By definition, l E (ig(i) \ surg (i), we know that there exists j E chg (i) such that j & chg (k). We have shown that ug as a component of (p)g()) is a function of mpaz(i) By the choice of k we have& k & (i), so that does not depend on Z). The conclusion follows.
Omitted Proofs for Theorem 3 and Theorem 8
In this section we provide detailed proofs of main ambiguity results.
Definition 12. We say that matrix M E Raxd is rffect-respecting for causal graph G, or M E M (9), if Mij # + j E (u). We also write M E MM (9) )) if M is invertible and Mi # + j E (i)g(i). Finally, we write M E Maur (G) if Mij & +0=3 E suig(i).
Remark 1. By definition (9) is the set of all matrices M where Múj + 0, Vj & (1), so it can be identified Rd+do where dg = =i= [surg(i)]- Equipped with the Lebesgue measure, we have Maur (9) C Man C M (G) and Ms)( Maur(9 (g) is null set. In the remaining part of this section, we will use measure- measure-theoretee statement for M E (Mau(G) in the above sense.
We first present a result that serves as a good starting point to understand why this is the case. It states that latent representations that are equivalent under ssur are essentially generated from the same causal graph.
Let M be an invertible matrix such that My + 0 + j E silg Suppose that the latent variables z E IRd are generated from any distributions ps (z; =pag(t) , E [d] with joint density p(z)= = I Pi (z: =pag()) then the joint density of v M² can be written as q(t)) I d (val (t))(t)) for some density functions qi, E [d]]
Proposition 5.
J.1 Proof of Proposition 5
We first prove the following lemma:
Lemma 20. Let M E Maur (9) and latent variables = Mz, then for Vi [d], there exists invertible matrices M; and M; such that Upag(1) M, (p))(i) and (p) Mi
Proof. Vj E (i), we know that vy is a linear function of zz, E surg (j). By Lemma 7, we know that surg (j) S (i), so each 3 E pig(i) is a linear function of (i) Thus we can write (1) M, ( In the following we argue that M; is invertible. Let a be permutation on p such that k E paa(() T(k) Tl) (such क can always be chosen since is acyclic), then we can write
(Üx() : (i) M, (2x)) :j pi)(
(26)
32

---

where M; is an upper triangular matrix with non-zero diagonal entries by our choice of M. Since M, can be obtained from M, be exchanging few rows and columns, M, is invertible as well. Similarly, using the fact that Vj pag(1), surg(i) E pag(i), invertible matrix M; such that (1) M, (p))
prove the existence of an
Returning to the proof of Proposition 5. Assume WLOG that the nodes of & are ordered in way such that E pag(i) = < j. so that M is a lower-triangllar matrix. The joint density of v can be written
d II q (v; 01,".", 12-1).
(
Since = and M is lower triangular and invertible (hence, with non-zero diagonals), we know that (01, 222, ... 10:1) is an invertible linear function of (21: 22, 2;-1) 1) and (#), "2, 04) an invertible linear function of (z1, 22, Z:). Let e M Rd then we have
000 02
,0,)
p(21 22 .. 22) del M
q (6; 01, 11-1)
q( 11 02
0:-1)
p 22 2 det M 1,1--1
p(2 82
21)
(2: ",, , = pa (2: (p))(())
x
p( 11, 22
2;-1)
where Mia,a denotes that lep- submatrix M of size x i, and the last step follows from the causal Markov condition (Definition 1). On the other hand, let qi (Ø; (())(()) be the conditional density of its parents at Ô E Rd. For Vj E pia( from M z we know that Vj is linear function ()) By Lemma we know that (f) is a linear function of &paz( and U (() a linear function of (t)) so that
(0) x (2)) and a (()mo(1) x (2)
and
p (E)ma(() ps (Ee (p))(t))
qi (ôs (0)
(8)pa((1)
Hence, we have qi (ù; è (1)) x (0;
01...., úz-1), so that
( = II ao (0x (p))(()) x II as (6: (p))()))
1=1
i=1
Since both sides integrate 1, it turns out that they equal, as desired.
J.2 Formal version and proof of Theorem 3: the linear case
Theorem (Counterpart Theorem 1). For any causal model (H,9) and any set of environments EEx t E [K]], suppose that have observations' {P& \ Bee satisfying Assumption 1:
Yk [K], == A42 SE x H
such that
(i) the unmixing matrix H E Rdxa has full row rank;
(ii) Vk E [K] and i,j E [d], (Ak)i # + E pag(1) and Sy is a diagonal matrix with positive entries;
(ii) BB (B:=0t S. 2 ((-)a)) k=1 are node level non-degenerate in the sense of Assumption 5,
then there must exist candidate solution (H,9) 9) and hypothetical data generating process
wk [K], == A D2 x =
such that
33

---

(i') the unmixing matrix H E Raxa has full row rank;
(if') vk E [K] and i [d]. (An)is 40 j pag(i) and S2 is diagonal matrix with positive entries;
(ii') {Bx 22 +
are node level non-degenerate in the sense of Assumption 5, $1I - Aa)] k=1
but
du: + 0, Vj E siTg(1).
Finally, if we additionally assume that
(iii) the environments are groups of single-node interventions: there exists a partition Ud i= E such that I = {i} (see Definition 2).
then we can guarantee the existence of (H,9) and weight matrices which, besides the properties listed above, also satisfy
(iif') for the same partition é = I
C, we have I = {i).
In other words, additionally assuming that the environments are from single-node interventions does not resolve the ambiguity.
Remark 2. Compared with our identifiability guarantee Theorem 1, Theorem 9 actually demonstrates a stronger form of impossibility. Specifically, states that the SNA cannot be resolved even if both the ground-truth causal graph and the noise variables are known.
We define
V
M
(27)
where M is an effect-respecting matrix. At this point we do not make any other restrictions on M, but we will specify the appropriate choise of M later.
By assumption, the latent variables the k-th environment are generated by
= A& + Sie
then M(I A₂) - Let f2g be the diagonal matrix with entries M (S2x),, i [d] and A 12 22 (1--((AA) AA)M then A&u + 52 Note that the choice of 12g here is to that the diagonal entries of A, are zero, as we show below. It remains to show that: for almost all M E ( it holds for Ak E [K] that (Ax) = + & pig(i).
For the = direction, since M E Manr (9), M- E Muur(() as well. Thus, Vj & pag(1) we have
[II A:M J
I
AR)ie (M (M-))es
Σ
(I Ax)ie (M "
E=1
jf pag(1)
(M-)) if =
where the last step holds because VE [d]. l pag(1), surg(f) = j E pa,, and when the only such is Hence, we can see that our choice of Å satisfies
{
if j & pag
(Az) ij
11
(M )( = if i
so (Ax) #0 + j E pag (i).
ig
Conversely, for Vj E (ia(
(Ax)) 0 Σ (I- As)
=0 Σ (-1)*(I &Epag(1)
Ablie det M, = 0 (28)
(1)
34

---

where M,j is the (d- x (d-1) matrix obtained by removing the s-th row and j-th column of M, and the second step in the equation above follows from the fact that M dct(M) aa where (d) denotes the adjugate matrix of M whose (i.j)-th entry is (-1) det M...
(28) holds if only M takes values on a lower-dimensional algebraic manifold of its embedded space RRd+d (see Remark 1). As result, for almost every M M (9), is generated from
linear causal model with graph G as defined in (3). Moreover, let B₃ B&M E [K] so that
== -x in the k-th environment. Then for all nodes E [d] and S pa(t) U {i}, we have
dim span (Bs, ei) k E [K1) dim dimspan (M-T (B ei) e [K]))
dim span (B, h [K]) = (pgg(1) +
implying that Ba, k E [K] satisfy Assumption 5.
Now we have shown that for almost every M E EMaur (9), we can construct a hypothetical data generating process with latent variables = Mr that satisfies all requirements Theorem 9, Choose an arbitrary M that is in Maur (9), then we have that
Dv. + O, j (i)
dz,
Finally, we additionally assume single-node interventions, Vk, l E e, we have that (Bx), * (Be), = i. For any M E M (G) (and specifically the M that we have already chosen above),
we have (Bx); = BB,) M and (Be), ( Vj E (d]. Thus, (Bx), + (Be), + j = as well, implying that é; is also group of single-node interventions on n, concluding the proof.
J.3 Formal statement and proof of Theorem 10: the non-parametric case
Theorem 10 (Counterpart to Theorem 7). For any causal model 9) and any set of environments
C, suppose that we have observations {P& FEe satisfying Assumption 1:
VE E E, PP = II
B (Z; 2pag()) = (z)
1=1
such that
(i) all densities y are continuously differentiable and the joint densily pr: is posilive every- where;
(ii) the environments are groups of single-node interventions: there exists a partition J E, such that -
(ii) the intervention distributions on each node are non-degenerate: Vi E [d], the set of distribu- tions {pf E E { satisfy Definition 11 at any point é E Rd.
then there must exist a candidate solution (h, 9) and a hypothetical data generating process
YE E C (.)0)
II of (0s (pag(() x -==h- h--(v)) ==1
such that
(i)) all densities q. are continuously differentiable and the joint density qF is positive every- where;
(it) for the same partition é = = E, we have I = {i);
(itt') Vi e [d], the set of distributions {&,t E E C.) satisfy Definition 11 at any point ú Rd
35

---

but
Ov;
*0, 0, Vj E sutg(1). dz, Remark 3. Similar to the case of Theorem 9, Appendix J.3 also establishes stronger form of identifiability. First, it is assumed that the causal graph G is known. Second, we only focus on special case of the setting of Theorem 7 by assuming that the support is the whole space, and the non-degeneracy condition Definition II holds at any point. Even in this case, we show that our identification guarantee up to SNA cannot be improved.
We state and prove stronger version of Theorem 10:
Theorem 11. For any causal model (h,9) () and any set of environments C, suppose that we have observations ( EEE satisfying Assumption I:
EEEÊ, z~ =~pp(z) = II p. (z: Apap(()) h (z) 2=1
such that
(i) all densities P F where;
are continuously differentiable and the joint density pg is positive every-
(ii) the environments are groups of single-node interventions: there exists a partition U E, such that I = (i);
(ii) the intervention distributions on each node are non-degenerate: Vi E [d], the set of distribu- tions {p. E {;} satisfy Definition 11,
then there must exist candidate solution (h, 9) and a hypothetical data generating process
VE E E, V gE(U)= = II of (vz (ppg())) = h (w)
1=1
such that
(i') all densities q. are continuously differentiable and the joint density qE is positive every- where;
(il)) for the same partition E = = E, we have I {i}:
(it') E [d], the set of distributions {o E E { satisfy Definition 11,
but
Ov: # 0, Vj E si)g(i).
dz, Finally, if we additionally assume minimality (Assumption 6) and/or faithfulness (Assumption 7) of all pe 's we can guarantee the existence of (h, 9) and qE satisfying minimality and/or faithfulness in addition to the properties listed above. In other words, assuming minimality and/or faithfulness does not resolve the ambiguity.
Proof. We define
= M=
(29)
where M is resecinni matrix. At this point do make any other restrictions M, and we will choose appropriate M later. By Lemma 20, there exists invertible matrices M; and M," such that Upag (s) = M, (() and (pzg(1) = M. (i) so for all environment E E C we have
E q
(t)) p. (t)) (dc qf (1)))(t) p. (zpag(t) [dct(M.)-1
so that
det M,
F. (vs (p))(()) =p. (z+ (1))
Vi E [d].
(30)
det(MM; -1
36

---

In the following, assuming that (p. : e) satisfies any of the listed assumptions, we show that (g. E E e) satisfies the same assumption as well.
Firstly, (30) immediately implies that the density of is continuous differentiable and positive everywhere. Secondly, vk, l E E₁ we have that
Pj (zj #png()) = =p (z) Zpag(t))
+ =i.
By (30) it is easy to see that
tfth (vz (pap(i)) - oj (wy Up) +=j=i
as well, ie., g", k E e, are single-node interventions on vs according to Definition 2. Thirdly, we verify the non-degeneracy condition for di 's Indeed we have for bk > 2 that
" V Ppng(t) (8) Es (vs: (pag(()) @zpzg (1)
Ei
En
V
(zi =pag(t)) M,' V =pag(t)
Tf
(zi ppaz(0)
Epng (+)
Ev
Es
Ci
Since M, is invertible, the above equation and the non-degeneracy of Bx E [K] immediately implies that non-degeneracy of ghx, E [K].
Thus, for arbitrary M E (G), we have constructed a hypothetical data generating process with latent variable e- Mz that satisfies all given conditions. It remains to show that such construction is still possible under additional minimality and faithfulness conditions.
Claim 1. There exists neighbourhood O of the identity matrix I in (g) (in the sense of Remark 1) such that for VM E eonMau. (9), Bk, k E [K] satisfy Assumption 7 = Bxx k [K] satisfy Assumption 7.
For y not d-separated by S C [d]. for all k [K] there exists & Rd such that A (6.1.5) = p (ši, Es) - B (&: Es) p (žj ES) * O. By continuous differen- tiability of p we know that there exists 8615.8)
0 such that for all M E M)) o(...)) the density of the variable v
such that |M - IlFF < kk E (0,, 0j ês)) * f (0: 05) (Ø, ês) for ό M which implies that v, and vy are dependent given ug. Now choose ő = mink.ig,s of (1...)) > O, then for all M E M such that || IM- - - & 8, the resulting distributions 9 g k E [K] satisfy assumption Assumption 6.
Mz satisfies
Claim 2. There exists a neighbourhood O of I in (g) (in the sense of Remark 1) such that for almost all M E EOMM" sur (9), p & [K] satisfies Assumption 6 = B k E [K] satisfies Assumption 6.
The proof is similar to the previous statement. Since Assumption 6 causal minimality is satisfied for 2, for Vk E [K], i [d]. let Gij be the resulting graph obtained by removing the edge j - from G. then there must exists some aijk E [d] such that Zaiza L Zudary (arga)) Zpag, (aesu)) Hence, there
exists gútk E Rdd such that
p Fe
Lijk aagi
ziik Paary (asse) D
gisk Ande., (ouss) I Epacy (owsk) # #D
(giي nno., (Drsw)
gisk Pagay (ansk)
By continuous differentiability of Bx, there exists (((h1) > 0 such that for all M Msue (9) such that || IllF < 8%%-0, the density gig
Fx of the variable gish = M satisfies
Ex Darge o (oesk) )
Liit (ndd, (mes)) I glik
* 5
(gisk "ndoy (ang))) pagsa (onsk)
gifk
for 6isk = Mgisk This implies that removing the edge - in G would break the causal Markov condition for Fx. Now let 8 = ming.i,3 ((133) O, then for all M Maur (G) such that
|| 1||F & 6, the resulting distributions g k E [K] satisfy assumption Assumption 1.
Combining the above two statements and what we have proven before, it is straightfoward to see that one can choose some M E Maur (9) in small neighbourhood of that satisfies all the requirements. completing the proof.
37

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] pprovided proper justification is given (e.g., "error bars are not reported because would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our abstract and introduction provide the readers a sense of our main results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
We compare with existing works in the introduction and the related work sections.
Justification:
38

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Rigorous proofs are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We introduce our experimental setup in details.
Guidelines:
The answer NA means that the paper does not include experiments.
39

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification:
Code will be released after review.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: Cooeeubmiii wesisssssssiiiiiiee
/ /nips. httc//ubllc/gguddeeo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
40

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Details are provided.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: run experiments on 100 random causal graphs and report the overall accuracy.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split. initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еттог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: The experiments do not require huge computational resources and can be run local computer.
Guidelines:
The answer NA means that the paper does not include experiments.
41

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https:/ http:////eeupp..eeeeee wwwpeuuriss.ccppul.leeeee wttp:ccplc/teeeiiccceoocccccccce http:/tttiisiiiieeeeeeeeeeee
Answer: [Yes]
Justification: The paper conforms the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
42

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi weworsswthhodeee thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
43

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
44


Reviews:
[{"review_id": "sb7pTGp1pg", "reviewer": "Reviewer_FDC3", "summary": "The paper studies causal representation learning (CRL) in the linear setting, that is, linear latent SEMs and a linear mixing function. Key contributions include:\n* Identifying an intrinsic surrounded-node ambiguity (SNA) that exists when the causal model and mixing function are linear. This ambiguity is unavoidable without hard interventions.\n* Proving that identification up to SNA is possible for linear models under reasonable conditions with data from $O(d)$ diverse environments, where $d$ is the number of latent variables.\n* Proposing an algorithm called LiNGCReL that provably achieves identification up to SNA in the linear case.\n* Showing that $\\Omega(d^2)$ single-node soft interventions would be required to achieve the same identification guarantee, highlighting the benefit of diverse environments.\n* Demonstrating LiNGCReL's effectiveness on synthetic data in recovering the true causal model up to SNA.\n\nThe paper provides some new theoretical insights into the identifiability limits of CRL and an algorithm to achieve those limits in the linear case with general environments.", "questions": "I overall think that the paper would be a nice contribution to NeurIPS. Here are some moderate/minor comments:\n\n* Regarding my comment above on \"all environments share the same causal graph\", if my understanding is correct, what's the main challenge on allowing partial removal of parents during a soft intervention?\n\n* L113-114: \"One may expect that identifiability with soft interventions is not much different from hard interventions, since soft interventions can approximate hard interventions with arbitrary accuracy\". I am not sure really sure about this sentiment on soft interventions, I particularly would expect the identifiability to be different.\n\n* In many places I see \"for $\\forall$\", I think either use \"for all\" or simply \"$\\forall$\".\n\n* In line 133, it reads \"each latent variable $v_i$\" but $z_i$ was used to denote latent variables. \n\n* In Theorem 1, $v$ is used to denote the candidate/hypothetical latent varaibles, wouldn't it be easier to use $\\hat z$? This would keep the consistency with $\\hat H$, $\\hat A$, etc.\n\n* In the model setup in eq.(3), you might want to index the variables $z$ per environment too since these are not exactly the same r.vs.\n\n* I think you want to cite the proceedings version of Squires et al 2023 and not the arxiv version from 2022.\n\n* In Definition 10 in the appendix, what is $\\phi$? I also think there might be a better way to state Definition 4 instead of relying on a definition in the appendix as early as in page 3.\n\n* L627 in appendix, typo \"must stronger\".", "limitations": "The natural limitations that come from the assumptions are discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* New theoretical insights on identifiability limits for CRL, particularly connecting the SNA concept.\n* The authors propose an algorithm which provides a concrete way to achieve the theoretical guarantees.\n* Experimental results validate the theoretical findings on synthetic data.", "weaknesses": "* Limited to linear causal models and mixing functions. Nonlinear extensions not discussed.\n* All environments share the same causal graph. My understanding on this is that soft interventions considered in this work do not allow for  removal of a subset of the parents.\n* Experiments only on synthetic data. Real-world applications or datasets not tested. Perhaps a semi-synthetic experiment following Squires et al. 2023. Specially when a key point is that the assumptions are less stringent than prior work, an experiments like this might help.\n* Computational complexity of LiNGCReL not thoroughly analyzed.\n* Implications of SNA for downstream tasks not explored.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our work and for giving insightful comments. Below are our responses to the questions and weaknesses mentioned by the reviewer.\n\n**Q1: All environments share the same causal graph. My understanding of this is that soft interventions considered in this work do not allow for removal of a subset of the parents…… Regarding my comment above on \"all environments share the same causal graph\", if my understanding is correct, what's the main challenge of allowing partial removal of parents during a soft intervention?**\n\nWe are sorry for the confusion here. There are actually three different settings that existing works consider:\n\n1). single-node, hard interventions. Hard intervention means removing the edge between the intervened node and all its parents.\n\n2). single-node, soft interventions. This means changing the weights of the edges between the interveded node and its parents.\n\n3). general environments (a.k.a. soft interventions that allow simultaneously intervening an arbitrary number of nodes. This is more general than 2) and is the setting this paper focuses on.\n\nWhile we highlight in our paper that we can deal with the case where the weights are nonzero, implying that the causal graph does not change, our setting does allow some weights to be zero. This is because our Assumption 4 (and 5) only requires a non-degeneracy condition, and this condition does not necessarily require  all weights to be nonzero. for example,let there by a three-node graph with edges $1\\to 3$ and $2\\to 3$, and we have access to three environments $E_i,i=1,2,3$ where $E_1$ has nonzero weights for both $1\\to 3$ and $2\\to 3$, $E_2$ only has nonzero weights for the former edge and $E_3$ only has nonzero weights for the latter edge, then Assumption 4 and 5 are satisfied on node $3$ since the third rows of the $B_i$’s are of forms $(x_1,x_2,1),(y_1,0,1),(0,z_2,1)$ (where $x_1,x_2,y_1,z_2$ denotes some nonzero numbers) and they span $\\mathbb{R}^3$. We will make this point more explicit in a revised version of our paper.\n\n**Q2: L113-114: \"One may expect that identifiability with soft interventions is not much different from hard interventions, since soft interventions can approximate hard interventions with arbitrary accuracy\". I am not really sure about this sentiment on soft interventions, I particularly would expect the identifiability to be different.**\n\nWe thank the reviewer for pointing this out, and we will delete this sentence to avoid unnecessary confusion.\n\n**Q3: In line 133, it reads \"each latent variable $v_i$\" but $z_i$  was used to denote latent variables. L627 in appendix, typo \"must stronger\". In the model setup in eq.(3), you might want to index the variables z per environment too since these are not exactly the same r.vs. I think you want to cite the proceedings version of Squires et al 2023 and not the arxiv version from 2022.**\n\nWe are sorry for these issues and will fix it in a revised version.\n\n**Q3: In Theorem 1, v is used to denote the candidate/hypothetical latent variables, wouldn't it be easier to use z^? This would keep the consistency with H^, A^, etc.**\n\nThe reviewer is correct about this. We will change the notations in the revision.\n\n**Q4: In Definition 10 in the appendix, what is $\\phi$? I also think there might be a better way to state Definition 4 instead of relying on a definition in the appendix as early as in page 3.**\n\nWe are very sorry for the typo. We restate this definition below:\n\nWe write $(h,G)\\sim_{CRL}(\\hat{h},\\hat{G})$ if there exists a permutations $\\pi$ on $[d]$, and a diffeomorphism $\\psi:R^d\\to R^d$ where the $j$-th component of $\\psi$, denoted by $\\psi_j(z)$, is a function of $z_j$ for $\\forall j\\in[d]$, such that the following holds: \n For $\\forall i,j\\in[d]$, $i\\in pa_{G}\\left(j\\right) \\Leftrightarrow \\pi(i)\\in pa_{\\hat{G}}\\left(\\pi(j)\\right)$,\n$P_{\\pi}\\circ\\hat{h}=\\psi\\circ\\hat{h}$, where $P_{\\pi}$ is a permutation matrix satisfying $(P_{\\pi})_{ij}=1 \\Leftrightarrow j=\\pi(i)$.\n\nIntuitively, this means that one can find a permutation of the nodes, such as the two models have node-wise correspondence.\n\nWe thank the reviewer again for the positive feedback and are happy to address any other questions that the reviewer might have.", "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": "x6xkFBZ3tk", "reviewer": "Reviewer_mSkL", "summary": "This paper investigates causal representation learning from low-level observed data across multiple environments. The authors address the surrounded-node ambiguity (SNA) in linear causal models and propose the LiNGCReL algorithm, which achieves identifiability up to SNA without relying on single-node interventions. Experiments on synthetic data show the effectiveness of LiNGCReL in the finite-sample regime.", "questions": "The paper considers the problem of learning linear causal representations from general environments. Is the information about these different environments known? If so, it indeed provides some additional information for structure learning.", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1.  It addresses the limitations of previous methods that rely on single-node interventions, providing a more practical approach to causal representation learning.\n2. The proposed LiNGCReL algorithm achieves identifiability up to SNA under mild conditions", "weaknesses": "1. Could you provide an intuitive explanation or motivations for the assumptions? What do they represent in real-world data scenarios?\n\n2. The authors mentioned that this work differs from Xie et al. [54, 55] and Dong et al. [11] because the latter requires structural assumptions. However, it seems that the proposed model in this paper also inherently assumes that there are no direct causal edges between observed variables.\n\n3. In the first step of the proposed algorithm, \"any identification algorithm for linear ICA is used to recover the matrix $M_k$\". This may introduce some errors, as perfect identification cannot be achieved. These methods typically assume that the dimensions of $X$ and $Z$ are the same and other restrictions.\n\n4. In Figure 2(e), the arrows on the edges could be made larger, as they currently look like undirected edges.\n\n5. How would the proposed method perform when applied to real-world data?\n\n6. The authors only provided the results of the LiNGCReL algorithm on simulated data. It would be more objective and validate the effectiveness of the proposed method if results of other baselines or classical methods on the same data were also provided for comparison.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing insightful comments and feedback. Below are our responses to the reviewer’s questions and concerns of our paper.\n\n**Q1: Could you provide an intuitive explanation or motivations for the assumptions? What do they represent in real-world data scenarios?**\n\nCertainly. Our paper considers the task of learning linear representations from general environments. Assumption 1 states that all environments share the same mixing function, which is a standard assumption in CRL literature [1,2]. For example, the generating process of images can be thought of as first generating a few causally related features (scheme, location, weather, etc.) and then these features are transformed by some mixing function into high level representations (pixels in images). Assumption 1 basically states that the relationship between features and the final image remains the same for all environments, but that those features are generated with different probabilities. Assumption 2 requires that the mapping from features to images is injective, i.e. there can’t be two different feature vectors that correspond to the same image. Assumption 3 requires the noise variables to be non-Gaussian and have different distributions. The non-Gaussian assumption is relatively standard in causal graph discovery, while requiring different distributions is not restrictive, since real-world noise distributions are seldom the same. Assumptions 4 and 5 are the main assumptions in our theory and intuitively state that the environments should contain enough information for all latent variables. Notably, it does not require single-node soft interventions, a widely-adopted assumption [1,4,5] but is questionable in real-world applications such as genomics (see e.g. Figure 1 of [3]), while interventions typically affect multiple nodes.\n\n\n[1] Squires, Chandler, et al. \"Linear causal disentanglement via interventions.\" International Conference on Machine Learning. PMLR, 2023.\n\n[2] von Kügelgen, Julius, et al. \"Nonparametric identifiability of causal representations from unknown interventions.\" Advances in Neural Information Processing Systems 36 (2024).\n\n[3] Tejada-Lapuerta, Alejandro, et al. \"Causal machine learning for single-cell genomics.\" arXiv preprint arXiv:2310.14935 (2023).\n\n[4] Wendong, Liang, et al. \"Causal component analysis.\" Advances in Neural Information Processing Systems 36 (2024).\n\n[5] Varici, Burak, et al. \"Score-based causal representation learning with interventions.\" arXiv preprint arXiv:2301.08230 (2023).\n\n\n**Q2: The authors mentioned that this work differs from Xie et al. [54, 55] and Dong et al. [11] because the latter requires structural assumptions. However, it seems that the proposed model in this paper also inherently assumes that there are no direct causal edges between observed variables.**\n\nWe thank the reviewer for pointing out the possible confusion here, and we will modify the sentence in a revised version. Our point is that since these works rely on observational data only, the underlying causal models may at best be recovered up to Markov equivalence. If we hope to establish stronger identification guarantees, more structural assumptions must be made.\n\n\n**Q3: In the first step of the proposed algorithm, \"any identification algorithm for linear ICA is used to recover the matrix $M_k$\". This may introduce some errors, as perfect identification cannot be achieved. These methods typically assume that the dimensions of $X$ and $Z$ are the same and other restrictions.**\n\nAs the reviewer noticed, standard linear ICA only applies to the case where $X\\in\\mathbb{R}^n$ and $Z\\in\\mathbb{R}^d$ have the same dimension. If $n>d$, then this means that our observation $X$ contains redundant information, and we can naively ignore the last $n-d$ components of $X$. Alternatively, we can run PCA to identify the top $d$ components of observation $X$ and use the new $d$-dimensional vector to run linear ICA. We will make this point more precise in a revised version of the paper.\n\n\n**Q4: In Figure 2(e), the arrows on the edges could be made larger, as they currently look like undirected edges.**\n\nWe thank the reviewer for pointing out this issue and will make the arrows larger in an updated version.\n\n**Q5: How would the proposed method perform when applied to real-world data?**\n\nThe experiments conducted in this paper mainly aims to verify the correctness of our theory and algorithm. We have not tested it on real-world data, because it is unclear how to evaluate the performance, since the underlying causal structure is generally unknown, and there is no benchmark in our setting. We agree with the reviewer that dealing with real-world data is an important future direction of CRL, and we will definitely explore it in future studies.\n\n**Q6: The authors only provided the results of the LiNGCReL algorithm on simulated data. It would be more objective and validate the effectiveness of the proposed method if results of other baselines or classical methods on the same data were also provided for comparison.**\n\nTo the best of our knowledge, LiNGCReL is the first algorithm that can handle CRL problems given data from multiple environments. We are not aware of any other algorithms that work for this task.\n\n\n**Q7: The paper considers the problem of learning linear causal representations from general environments. Is the information about these different environments known? If so, it indeed provides some additional information for structure learning.**\n\nWe assume that the environments are unknown; the weights in the linear causal models can be arbitrarily different across different environments. \n\n\nWe hope that the above explanations have properly addressed the reviewer’s questions, and feel free to let us know if the reviewer has any other questions.", "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": "M0qBk1ulDy", "reviewer": "Reviewer_Vjor", "summary": "The paper is about causal representation learning (i.e, learning the latent causal graph and the unmixing function) from high-dimensional observations in the case of linear SCMs where the mixing function is also linear. The paper defines the notion of surrounded node ambiguity (SNA) and then performs studies for CRL under assumptions of soft interventions (where there are K environments that share the causal graph). Theoretical analysis is performed and the authors also introduce a method, LinGCRel that can perform CRL upto SNA and is provably identifiable.", "questions": "* Figure 2e looks like an undirected graph but on zooming looks like there might be directed edges. If so, this figure can be corrected.\n* Font size for the axis labels is too small to read in Fig 2a-2d\n* Apart from the interventional CRL works already cited which mainly focuses on identifiability, the authors could also cite BIOLS [1] which studies CRL from a more empirical perspective and proposes an algorithm to learn linear latent causal graphs from high-dimensional data under hard, multi-node interventions.\n\n[1] Subramanian, Jithendaraa, et al. \"Learning latent structural causal models.\" arXiv preprint arXiv:2210.13583 (2022).", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors introduce the idea of SNA and identifiability upto SNA which is novel and also important for understanding ambiguities in the CRL setup, even for the simple case of linear SCMs with a linear mixing function.\n\n2. LinGCRel, a practical method is also proposed to perform CRL in such a setting, provably identifying upto SNA. The paper is also about soft single node interventions, in comparison to other previous work which has primarily dealt with hard interventions.", "weaknesses": "Since I am not aware of many theoretical results and proofs for CRL, which seems to be the main contribution of the paper (apart from LinGCRel), I do not have particular weaknesses to state.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and comments. In the following, we respond to the questions raised by the reviewer.\n\n**Q1: Figure 2e looks like an undirected graph but on zooming looks like there might be directed edges. If so, this figure can be corrected.**\n\nThat was indeed the case – the graph is directed. We thank the reviewer for pointing out this issue, and will correct them in a revised version.\n\n**Q2: Font size for the axis labels is too small to read in Fig 2a-2d**\n\nWe thank the reviewer for pointing out this issue. We will update these labels to make them bigger.\n\n**Q3: Apart from the interventional CRL works already cited which mainly focuses on identifiability, the authors could also cite BIOLS [1] which studies CRL from a more empirical perspective and proposes an algorithm to learn linear latent causal graphs from high-dimensional data under hard, multi-node interventions.**\n\nWe thank the reviewer for pointing to this super interesting and closely related paper, and we will definitely cite it in the revision.\n\nWe thank the reviewer again for appreciating our work and are happy to address any other questions that the reviewer might have.", "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": "N2uhvi6lHm", "reviewer": "Reviewer_Cu44", "summary": "This paper considers the task of learning linear causal representation with data collected from general environments. Authors show that there exists a surrounded-node ambiguity (SNA) which is basically unavoidable in their setting. On the other hand,  identification up to SNA is possible under mild conditions in their considered setting. An algorithm, LiNGCReL, is further proposed to achieve such identifiability guarantee.", "questions": "1. what does \"general environments\" mean? I don't think it is a widely used concept, so perhaps describe it more explicitly and accurately.\n\n2. Definition 2: this definition is questionable, or at least inaccurate. \n\n   - Line 105: here \"$i \\in S$\" and then \"for all $i\\in [d]$\"? what is $S$ and what is the difference bewtten $S$ and $[d]$? \n   - Further, when you write $<=>$ , what does $i\\notin S$ indicate?\n\n3. Similarly in Def. 4, line 121: it is difficult to interpret what you mean by <=>. Can you give a complete sentence of the condition?\n\n4. More importantly, I find several motivations/claims are not convincing/accurate, which is particularly critical to a theory-heavy paper: \n\n   1) a motivation of considering soft interventions is that, ”the latent variables are unknown and need to be learned from data, it is unclear how to perform interventions that only affect one variable. “, but how soft interventions avoid this concern?\n   2) lines 123-124： \"if there exists some i ∈ surG(j), then ambiguities may arise for the causal variable at node j, since any effect of j on any of its child k can also be interpreted as an effect of i.\"  in pearl's book or the topic of mediation analysis, you can define clearly the effect of $j$ and the effect of $i$ on child $k$ , and why would I interpret the effect of $j$ as that of $i$? That is not sound.\n   3) I also have a question with the example with three causal variables in Appendix E, which aims to show the different between hard and soft interventions. It seems that one can distinguish the two even with soft interventions, e.g., by setting $z_3=z_2+\\epsilon_3$, $v_3=v_2+\\epsilon_3$, then $z_2$ and $z_3$ (or $x_2, x_3$) would still be dependent while in the right, $v_2$ and $v_3-v_2$ (or $x_2, x_3$) are independent.\n   4) lines 139-142: \"in contrast with existing literature on single-node interventions, we impose no similarity constraints on the environments.\": however, assumptions 4 and 5 seem to assume the environments are sufficiently diverse, which are not weaker.\n\nI just stop here, since the presentation and rigorousness issues have led to the decision for the submitted version. While I tend to believe the paper may contribute some interesting ideas and results, at least a major revision is required.", "limitations": "See above.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Learning linear causal representation using soft-interventions seem to be new.\n\n- The surrounded-node ambiguity (SNA) identifiability is new.", "weaknesses": "- The placed assumptions do not seem to be weaker, compared with existing ones.\n\n- Many places/claims are vague/incorrect, and presentation is poor.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing insightful feedback and suggestions. Below are our responses to the reviewer’s questions and concerns of our paper.\n\n**Q1: What does \"general environments\" mean? I don't think it is a widely used concept, so perhaps describe it more explicitly and accurately.**\n\nAs the reviewer notices, the “general environments” setting is relatively new in the literature. As a result, we include discussions of this concept in several parts of our paper. The most notable one might be at the beginning of Section 4, where we wrote that “In this section, we consider learning causal models from general environments. Specifically, we assume that the environments share the same causal graph, but the dependencies between\nconnected nodes (latent variables) are completely unknown, and, in contrast with existing literature on single-node interventions, we impose *no* similarity constraints on the environments.” The motivation of considering such a setting is discussed in Section 1 line 41-51. We thank the reviewer for pointing this out and we will improve exposition by moving the definition from Section 4 to the introduction so that the reader has a more precise understanding of the use of the term earlier on.\n\n**Q2: Definition 2: this definition is questionable, or at least inaccurate. Line 105: here \"$i\\in S$\" and then \"for all $i\\in[d]$\"? What is $S$ and what is the difference between $S$ and $[d]$? Further, when you write $\\Leftrightarrow$, what does $i\\notin S$ indicate?**\n\nThank you for pointing at potential points of confusion/improved readability and let us clarify below the accuracy of the statements and ways that we plan to address the readability issues.\n\n\"i\\in S\" is part of the sentence “......a subset of latent variables $z_i,i\\in S$”, so it describes for which zi’s we are defining the soft intervention. On the other hand, \"if for all $i\\in[d]$\" belongs to the sentence that follows: if $\\forall i\\in[d]$, $\\forall E_1, E_2 \\in \\hat{\\mathfrak{E}}, E_1 \\neq E_2$, we have $p_i^{E_1}=p_i^{E_2} \\Leftrightarrow i\\notin S$. So these two $i$’s are essentially the subscripts of different objects: latent variables $z_i$ and distribution $p_i$, not contradictory statements or typos. We will use different subscripts in the two sentences for improved readability in a revised version.\n\nThe notation $\\Leftrightarrow$ stands for “if and only if”. We will replace the arrow with the if and only if text to make it clearer in a revised version.\n\nSo, to summarize, Definition 2 can be rephrased as follows: “We say that a collection of environments $\\hat{\\mathfrak{E}}$ is a set of (soft) interventions on a subset of latent variables $z_i, i\\in S$ if the following statements hold for any $i\\in[d]$: $\\forall E_1, E_2 \\in \\hat{\\mathfrak{E}}, E_1 \\neq E_2$, we have $p_i^{E_1}=p_i^{E_2}$ if and only if $i\\notin S$.\n\n\n**Q3: Similarly in Def. 4, line 121: it is difficult to interpret what you mean by <=>. Can you give a complete sentence of the condition?**\n\nSimilar to Q2, we use the mathematical convention that <=> means if and only if. The sentence reads “For all $ i,j\\in[d]$, $i\\in pa_{G}\\left(j\\right)$ if and only if $ \\pi(i)\\in pa_{G}\\left(\\pi(j)\\right)$. We will replace the arrow with the \"if and only if\" text for improved readability.\n\n**Q4.1: a motivation of considering soft interventions is that, ”the latent variables are unknown and need to be learned from data, it is unclear how to perform interventions that only affect one variable. “, but how do soft interventions avoid this concern?**\n\nWe are afraid that the reviewer mixed up the following two settings: one is the “general environment” setting, which is the main focus of our paper (Theorem 1, 3 and the LingCReL algorithm), the other is the “soft intervention” setting, for which we only include a negative result (Theorem 2) to highlight its difference from the general environment setting. In fact, soft interventions exactly inherit the limitations that the reviewer quoted, and this is the main motivation for us to consider general environments that do not have this limitation. We included the soft-intervention result in our paper, as it only makes the negative result stronger. Obviously the negative impossibility result holds for general environments too, but proving it for soft interventions only strengthens the impossibility result. All our positive and constructive results are for general environments, which exactly bypass the requirement that the reviewer describes as a problem.\n\n**Q4.2: lines 123-124： \"if there exists some i ∈ surG(j), then ambiguities may arise for the causal variable at node j, since any effect of j on any of its child k can also be interpreted as an effect of i.\" in pearl's book or the topic of mediation analysis, you can define clearly the effect of 𝑗 and the effect of 𝑖 on child 𝑘, and why would I interpret the effect of 𝑗 as that of 𝑖? That is not sound.**\n\nWe thank the reviewer for pointing to the references. Note that this sentence is only an intuitive description and serves as a supplement to Definition 3, which is mathematically rigorous.\n\nIn this section, the word “interpret” is used in the following sense: from the learner’s perspective, the task is to find a suitable data model that matches the data. intuitively, there would be two indistinguishable but non-equivalent data generating processes, so in other words, there are two distinct causal mechanisms that match observation data. So you can of course define these theoretical causal quantities, but given the data you cannot conclude which of these two causal effects are at play. We hope this explanation would make things clear, and we point the reviewer to Definition 3 for a more rigorous mathematical formulation.\n\nDue to space limits, the remaining parts of the rebuttal can be found in the official comment that follows this post.", "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:

Meta-review: The submission addresses causal representation learning in the linear setting (latent structural causal model and mixing), based on data from general environments (soft interventions possibly on groups of nodes). 

Reviewers have acknowledged that the work:
- provides novel theoretical identifiability guaranties for a challenging setting,
- for that, they introduce the insightful concept of surrounded-node ambiguity (SNA),
- provides a practical algorithm for estimation,
- provides validation on synthetic data. 

Given the progress made in a challenging setting of practical importance (general environments), the AC recommends acceptance as a spotlight.
Decision: Accept (spotlight)