Linear Causal Representation Learning from Unknown Multi-node Interventions
Authors: Burak Varıcı
Emre Acartürk
Karthikeyan Shanmugam
Ali Tajer
Venue: NeurIPS 2024 poster (2024)
Keywords: Causal representation learning
interventions
score-based methods
identifiability
Primary area: causal_inference
TL;DR: We prove identifiability results and design algorithms for linear causal representation learning from unknown multi-node stochastic interventions.

Abstract: Despite the multifaceted recent advances in interventional causal representation learning (CRL), they primarily focus on the stylized assumption of single-node interventions. This assumption is not valid in a wide range of applications, and generally, the subset of nodes intervened in an interventional environment is *fully unknown*. This paper focuses on interventional CRL under unknown multi-node (UMN) interventional environments and establishes the first identifiability results for *general* latent causal models (parametric or nonparametric) under stochastic interventions (soft or hard) and linear transformation from the latent to observed space. Specifically, it is established that given sufficiently diverse interventional environments, (i) identifiability *up to ancestors* is possible using only *soft* interventions, and (ii) *perfect* identifiability is possible using *hard* interventions. Remarkably, these guarantees match the best-known results for more restrictive single-node interventions. Furthermore, CRL algorithms are also provided that achieve the identifiability guarantees. A central step in designing these algorithms is establishing the relationships between UMN interventional CRL and score functions associated with the statistical models of different interventional environments. Establishing these relationships also serves as constructive proof of the identifiability guarantees.

Linear Causal Representation Learning from Unknown Multi-node Interventions
Burak Varier' Camegie Mellon University
Emre Acartürk Rensselaer Polytechnic Institute
Karthikeyan Shanmugam Google DeepMind
Ali Tajer
Rensselaer Polytechnic Institute
Abstract
Despite the multifaceted recent advances in interventional causal representation learning (CRL), they primarily focus on the stylized assumption of single-node interventions. This assumption is not valid in wide range of applications, and generally, the subset of nodes intervened in an interventional environment is fully unknown. This paper focuses on interventional CRL under unknown multi-node (UMN) interventional environments and establishes the first identifiability results for general latent causal models (parametric or nonparametric) under stochastic in- terventions (soft or hard) and linear transformation from the latent to observed space. Specifically, is established that given sufficiently diverse interventional environ- ments, (i) identifiability
to ancestors is possible using only soft interventions, and (ii) perfect identifiability possible using hard interventions. Remarkably, these guarantees match the best-known results for more restrictive single-node interventions. Furthermore, CRL algorithms are also provided that achieve the iden- tifiability guarantees. A central step designing these algorithms is establishing the relationships between UMN interventional CRL and score functions associated with the statistical models of different interventional environments. Establishing these relationships also serves as constructive proof of the identifiability guarantees.
1
Introduction
Causal representation learning (CRL) is a major leap in causal inference, moving away from the conventional objective of discovering causal relationships among set of variables and learning the variables themselves. By combining the strengths of causal inference and machine learning, CRL specifies data representations that facilitate reasoning and planning [1]. CRL is motivated by the premise that a wide range of applications, a sover-dimensional latent set of variables with causal interactions generates the usually high- tigh-dimensional observed data. Therefore, CRL's objective is to use the observed data and learn the latent causal generative factors, which include the causal latent variables and their causal relationships.
CRL objectives. Formally, consider set of latent causal random variables Z TR and directed acyclic graph (DAG) G that encodes the causal relationships among Z. The latent variables are transformed by an unknown function g to generate the observed random variables E Rd, where X g( (Z). CRL aims to use X to recover the latent causal variables Z and the causal structure G.
Two central questions of CRL pertain to identifiability, which refers to determining the conditions under which Z and can be recovered, and achievability, which refers designing CRL algorithms that can achieve the foreseen identifiability guarantees. Identifiability has been demonstrated to
Work was done while was a Ph.D. student at Rensselaer Polytechnic Institute.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

be inherently under- contrrcon [2], prompting the development of diverse methodologies that incorporate inductive biases to enable identifiability. Interventional CRL one direction with significant recent advances in which interventions on latent causal variables are used to create statistical diversity the observed data [1, 3-6].
Despite covering many aspects of interventional CRL, such as parametric versus nonparametric causal models, parametric versus nonparametric transformations, and intervention types, the majority of the existing studies assume that the interventions are single- node, i.e., exactly one latent variable is intervened in each environment [3-10]. This assumption, however, is restrictive in some of the application domains of CRL such as biology and robotics in which generally the subset of nodes intervened in an intervention environment can be fully unknown. For instance, biological perturbations in genomics are imperfect interventions with off- off-target effects on other genes [11, 12], or interventions on robotics applications are likely to affect multiple causal variables [13]. Hence, realizing the promises of CRL critically hinges on dispensing with the assumption of single-node interventions.
Unknown multi-node interventions.
In this paper, we address the open problem of using unknown multi-node (UMN) stochastic interven- tions to recover the latent causal variables Z and their causal graph G. wherein each environment an unknown subset of nodes are intervened. We consider a general latent causal model (parametric or nonparametric) and focus on the linear transformations as an important class of parametric transfor- mation models. We establish identifiability results and design algorithms to achieve them under both soft and hard interventions. For this purpose, we delineate connections between UMN interventions and the properties of score functions, i.e., the gradients of the logarithm of density functions. This score-based framework is the UMN counterpart of the single-node framework proposed in [5, 7], albeit with significant technical differences. Our contributions are summarized below.
We show that under sufficiently diverse interventional environments, UMN stochastic hard inter- ventions suffice to guarantee perfect identifiability of the latent causal graph and the latent variables (up to permutations and element-wise scaling).
We show that under sufficiently diverse interventional environments, UMN soft interventions guarantee identifiability up to ancestors transitive closure of the latent DAG is recovered, and latent variables are recovered up to a linear function of their ancestors. Remarkably, these guarantees match the best possible results in the literature of single-node interventions.
We design score-based CRL algorithms for implementing CRL with UMN interventions with prov- able guarantees. These guarantees also serve as constructive proof steps of the identifiability results.
Challenges of UMN interventions. There are two broad challenges specific to addressing the UMN intervention setting that render it substantially distinct from the single-node (SN) intervention setting. First, in SN interventions, since the learner knows exactly one node is intervened in each environment, it can readily identify the intervention targets up to a permutation. In contrast, in UMN interventions, the learner does not know how many nodes are intervened in each environment. Therefore, the nature of resolving the uncertainty about the intervention targets becomes fundamentally different. properly capitalize the
An immediate impact of this is that it becomes more challenging statistical diversity embedded in the interventional data. Secondly, in SN interventions, only one causal mechanism changes across the environments. Such sparse variations of the causal mechanisms are a core property leveraged by various existing CRL approaches, e.g., contrastive learning [8], and score-based framework [6. 7]. On the contrary, UMN interventions allow for many concurrent causal mechanism changes, which renders leveraging sparsity patterns in mechanism variations futile. Finally, since intervention targets are unknown, our central algorithmic idea is to properly aggregate the UMN interventional environments to create new distinct environments under which the inherent statistical diversity more accessible.
1.1 Related literature
Single-node interventional CRL. The majority of the studies on interventional CRL focus on SN interventions [3-10, 14], which can be categorized based on their assumptions on the latent causal model, transformation, and intervention model. Based on this taxonomy, it has been shown that SN hard interventions suffice for identifiability with general latent causal models and linear transforma- tions (one intervention per node) [7], with linear Gaussian latent models and general transformations (one intervention per node) [8], and with general latent models and general transformations (two interventions per node) [6. 9]. For the less restrictive SN soft interventions, identifiability up to

---

Table 1: Comparison of the results existing work in multi-node interventional CRL. We note that all studies
assume linear transformation.
Work
Latent model
Int. type
Main assumption on interventions
Identifiability (ID)
[14]
Linear
Soft
pa(i)] independent int. mechanisms
ID up surrounding perfect perfect
[16]
General
do
strongly separated interventions
Theorem
General
Hard
lin. indep. interv. (Assumption 1)
Theorem 2
General
Soft
lin. indep. interv. (Assumption 1) ID up to ancestors
ancestors is shown for general latent models and linear transformations [7] and linear Gaussian latent models and general transformations [8]. Furthermore, under additional assumptions such as sufficiently nonlinear latent models, the latent DAG is shown be perfectly identifiable [7, 10, 14]. In a related study, [15] focuses on learning the latent DAG (but without learning latent causal variables) using SN hard interventions without parametric assumptions on the model.
Multi-node interventional CRL. The studies on MN intervention settings are sparser than the SN intervention settings. Table 1 summarizes the results closely related to the scope of this paper along with the identifiability results established in this paper. In summary, the existing studies either provide focus on non-stochastic do interventions. The study in [14] focuses on linear non Gaussann latent models and linear transformations and uses soft interventions to establish identifiability up surrounding variables by using multiple interventional mechanisms for each node. In a different study, [16] uses strongly separated multi-node do interventions and provides perfect identifiability results for general latent models and linear transformations. We also note the partially related study in [17] that applies soft interventions on a subset of nodes and aims to disentangle the non-intervened variables from the intervened ones. Distinet from all these studies, we address the open problem of perfect identifiability under UMN stochastic interventions.
partial identifiability
Other approaches to CRL. We note that there exist other interesting settings that address CRL without interventions. Some examples include using multi-view data [18-21], leveraging temporal sequences [22, 23], building
nonlinear independent component analysis (ICA) principles to
identify polynomial latent causal models [24], and imposing sparsity constraints to obtain partial disentanglement [25, 26], and grouping of observational variables [27]. We refer to [28] for detailed literature review on various CRL problems.
CRL setting and preliminaries
Notations. Vectors are represented by lowercase bold letters, and element of vector a is denoted by a, Matrices are represented by uppercase bold letters, and we denote row i and column of matrix A by A; and by A.,j respectively, and Ar,, denotes the entry at row and column j. We use [[l([[11....
A, to denote the nullspace of the matrix consisting of the row vectors {A (Ai...., A, For E N, we define [n] A (1...., n). The row permutation matrix associated with any permutation ı of [n] is denoted by p,- We denote the indicator function by 1. We use im()) to denote the image of a function f and dim(V) denote the dimension of subspace V. Random
variables and their realizations are presented by upper and lower case letters, respectively.
2.1 Latent causal model
Consider a latent causal space consisting of causal random variables Z & [Z,,...,Z,, ZT An unknown linear transformation G E d maps Z to the observed random variables denoted by x A [X...... Xz) according to:
G 7,
(1)
where d 2 n and G is full rank. The probability density functions (pdfs) of X and Z are denoted by px and pz, respectively. We assume that pz has full support on IR". Subsequently, px is supported on X A im(G). The causal relationships among latent variables 7 are represented by a DAG G in which the i-th node corresponds to Z, Hence, pz factorizes according to:
pz(2) = p((z; =pa(0)
(2)
3

---

where pa( denotes the set of parents of node in G. The conditional pdfs {pr(2z] ²pa(t)) : E [n]] are assumed to be continuously differentiable with respect to all variables. We use ch(i). an()). and de(i) to denote the children, ancestors, and descendants of node i, respectively, We say that a permutation (Tı,..., Ta) of [r]] is a valid causal order if the membership π. E an(T;) indicates that i < j. Without loss of generality, we assume that (I,..., n) is a valid causal order. We will specialize some of our results for the latent causal models with additive noise specified by
Z, = (zp(tt) + Ni,
where functions (ff é E [n|]] capture the causal dependence of node on its parents and the terms [N; i E [n]} represent the exogenous noise variables.
2.2 Unknown multi-node intervention models
In addition to the observational environment, we have M UMN interventional environments denoted by {ETh : m E [M]} We assume that the set of nodes intervened in each environment is unknown, and denote the intervened in environment e. by 1T C [m]. Accordingly, we define the intervention signature matrix Dint E {0, 1 1 to compactly represent the intervention targets under various environments as
Dinkk.m = =ii
[ Vm E [M].
The m-th column of Dine lists the indices of the nodes intervened in environment 8 which refer to as the intervention vector of environment E Ensuring identifiability inevitably imposes restrictions the structure of D For instance, if the i-th row of Dint is zero vector, it means that node v is not intervened in any environment, then the perfect identifiability is not possible [4] Therefore, to avoid such impossibility cases, we impose the mild condition that Dint has sufficiently diverse columns, formalized next.
Assumption 1. Intervention signature matrix Dimt defined in (4) full row rank, i.e., it contains n linearly independent intervention vectors.
In this paper, we consider UMN stochastic interventions and address identifiability results under both hard interventions as well as soft interventions as the most general form of intervention.
Soft interventions. A soft intervention node alters the observational causal mechanism pt(z; ?pa(t) to an interventional causal mechanism q (zz Zpa(t)). Such a change occurs in node in all the environments ed that contain node i, i..., E 1 . Subsequently, the pdf of the latent variables in environment ~ denoted by pzz factorizes according to:
pZ (2)
II g:(2; zpa(t) $E!"
II P=(= I =pa(t)) Vm E [M]. "
(5)
Hard interventions. Under a hard intervention on node i, the functional dependence of node i on its parents is removed, and the observational causal mechanism p; (z4 ?pp((t) is changed to an interventional causal mechanism q: (2,). independent of parents of node i.
To distinguish the observational and interventional data, denote the latent and observed random variables in environment 8d by 7m and X" respectively. We note that interventions do not affect the transformation G. Hence, in mm we have Xm G 7m for all m [M).
Score functions. The score function of a pdf is defined as the gradient of its logarithm. We denote the score functions associated with the distributions of zm and X by
2 (z) V log (z), and s (z) A logg
Vm E [M]
(6)
Note that, using the factorization in (5), 87 decomposes as
V log (2: Epa(t)) + Σ V (pa(1))
T
m
We denote the difference in score functions between interventional and observational environments by
A (2) (2) 82) and Az) A (x) sx()). Vm [M]
(8)
Perfect identifiability results the closely related literature are given for additive noise models [7, 4. 8, 16). 214. Proposition 5] shows that if the in-iiterreeed node i has at least one parent, then perfect identifiability is not possible.

---

2.3 Identifiability criteria
In CRL, we use observed variables X to recover the true latent variables Z and the latent causal graph G. We denote generic estimator of Z given X by 2(X) R + R". We also consider generic estimate of G denoted by G. To assess the fidelity of the estimates (X) and 9 with respect
to the ground truth Z and G, we provide the following well-known identifiability measures.
Definition (Identifiabilitty. For CRL under linear transformations, we define:
1. Perfect identifiability: 9 and 9 are isomorphic, and the estimator (X) satisfies that
2(x)= Px C. 4Z E ER"
(9)
where Cg E R is constant diagonal matrix with nonzero diagonal entries and P is a row permutation matrix.
2. Identifiability up to ancestors: 9 and transitive closure of 9, denoted by Gie, are isomorphic, and the estimator (X) satisfies that
(()) = P= Can Z,
(10)
where Can E Ruxx is a constant matrix with nonzero diagonal entries that satisfies [Can]a.j = 0 for all & {an(i) (i)), and P is row permutation matrix.
In the algorithm we will design, estimating (x) and 9 are facilitated by estimating the inverse of the transformation G, that is Moore-Penrose inverse G [G G GT, which we refer to as the true encoder. To formalize the process estimating the true encoder, we define H. as the set of candidate encoders specified by H. _ {H Raxd rank(H) n and H - X X VX E X). Corresponding to any pair of observation X and valid encoder H H. we define 2(X; H) as an auxiliary estimate of Z generated as 2(X; H) - H X (H G) Z.
3 Identifiability under UMN interventions
In this section, we present the main identifiability and achievability results for CRL with UMN interventions and interpret them in the context of the recent results in the literature. We start by specifying the regularity conditions on the statistical models, which are needed to ensure sufficient statistical diversity and establish identifiability results for hard and soft UMN interventions. The constructive proofs of the results are based on CRL algorithms, the details of which are presented in Section 4. Complete proofs are deferred to Appendix A.
We note that the UMN setting subsumes SN interventions. Similarly all the existing identifiability results from SN interventions, it is necessary to have sufficient statistical diversity created by the intervention models.² These conditions can be generally presented in the form of regularity conditions on the probability distributions. Specifically, commonly adopted regularity condition (or its variations) in the SN intervention setting that for every possible pair (i. where i [m]].] E pa(i). the following term cannot be a constant function in 2,
log pr(z: Epp(t))
θ dz.
pi(z; =pa(1))
log
(11)
Øz,
(2: Epace)
( Epa(e)
We present a counterpart of these conditions for UMN interventions, which involves one additional term account for the effect of intervening on multiple nodes simultaneously.
Definition (Intervention regularity). We say that an interventions are regular for every possible triplet (i,j,c) where i E [n],] E pa(i) and E Q the following ratio cannot be constant function in
2pa(t)) log (s(=;
+ c log Ps(25 =pall))
p<(2 Epa(i))
log
(12)
(z; =
4;(=; Epa(s))
Oz;
4: Epa(s))
3 'Soe examples include Assumption 1 in [6], generic SN interventions in [4], no pure shift interventions condition in [8], and the genericity condition in [9].
5

---

(((a:)) captures the effect of intervening on node i on the score associated with node j. In our method, we will use combinations score differences of multi-node environments. This regularity condition ensures that the effect of a multi-node intervention is not the same the scores associated with different nodes. Given these properties, we establish perfect identifiability for CRL with linear transformations using UMN stochastic hard interventions.
Essentially, 2 Pa(aa Apola)
Bay log
Theorem 1 (Identifiability under UMN hard interventions). Under Assumption I and a latent model with additive noise,
1. perfect latent recovery is possible using regular UMN hard interventions; and
2. if the latent causal model satisfies adjacency-fattfilness, then perfect latent DAG recovery is possible using regular UMN hard interventions.
Theorem 1 is the first perfect identifiability result using UMN stochastic hard interventions. In contrast, [16] establishes perfect latent recovery using highly more stringent do-interventions. Fur- thermore, Theorem 1 establishes the first perfect latent DAG recovery result (under any type of multi-node interventions) for nonparametric latent models. We note that the capability of handling nonparametric latent models stems from leveraging the score functions. Similar properties are demon- strated by the prior work on score-based CRL for SN interventions [7]. It is noteworthy that we use a total of n + 1 environments whereas the study in [16] requires 2 1oog2 n do interventions of strongly separating sets. However, we show that identifiability is impossible using strongly separating sets of UMN stochastic hard interventions (see Appendix A.
Next, we consider UMN soft interventions. Since soft interventions retain the ancestral dependence of the intervened node, in general, the identifiability guarantees for soft interventions weaker than those of hard interventions. Next, we establish that UMN soft interventions guarantee identifiability up to ancestors for the general causal latent models and linear transformations.
Theorem 2 (Identiiability under UMN soft interventions). Under Assumption 1, identifiability up to ancestors is possible using regular UMN soft interventions.
Identifiability up ancestors has recently shown to be possible using SN soft interventions on general latent models [7]. Theorem 2 establishes the same identifiability guarantees without the restrictive assumption of SN interventions. Furthermore, Theorem is significantly different from existing results for UMN soft interventions. Specifically, the study in [14] focuses on linear non-Gaussian latent models and requires pa(i)] distinct mechanisms for each node i. In contrast, Theorem 2 does not make parametric assumptions on latent variables and works with sufficiently diverse interventions described by Assumption instead of requiring multiple interventional mechanisms for the same node.
4 UMN interventional CRL algorithm
In this section, we design the Unknown Multi-node Interventional (UMNI)-CL algorithm that achieves identifiability guarantees presented in Section 3. This algorithm falls in the category of score-based frameworks for CRL [5, 7] and incorporates novel components to this framework that facilitate UMN interventions with provable guarantees. Our score- based approach uses the structural properties of score functions and their variations across different interventional environments to find reliable estimates for the true encoder G The critical step involved is a process that can aggregate the score differences under the available interventional environments, which have entirely unknown intervention targets, and reconstruct the score differences for any desired hypothetical set of intervention targets. In particular, we establish that such desired score differences can be computed by aggregating the score differences available under the given UMN interventions. The proposed UMNI-CRL algorithm consists of four stages for implementing CRL. The properties of these stages also serve as the steps of constructive proof for identifiability results. We present the key algorithmic stages and their properties in the remainder of this section and defer their proofs to Appendix A.
Stage 1: Basis score differences. In the first stage, we compute score differences for each interven- tional environment and construct the basis score difference functions that are linearly independent. The purpose of these functions is to subsequently use them and reconstruct the score differences under any arbitrary hypothetical interventional environment. To this end, we use the following relationship between score functions of X and Z.

---

Algorithm Unknown Multi-node Interventional (UMNI)-CRL
Input: Samples of X from environment e and interventional environments (E"h m [M]}
2: Stage 1: Choose basis score differences and construct A8x using (17)
3: Stage 2: Identifiability up to causal order
4: for E (1.....1) do
5: for w E W do
W is specified in (18)
6: V
:i im(AS, w) 7: if dFdi(V)== = then
8:
pick im(ASx w) span( : : (]])
9:
H; - v/llv/22 and [W], t w
break
11: Stage 2 outputs: H" and W
12: Stage 3: Identifiability up ancestors
13: Initialize & with empty graph over nodes [n]
for L (n 1, ,,...,1) do
15:
for j E (t 1,....,...0 ,..., do
j E ch(()) then
17:
continue
if-parent + True
Mr,, + [ - 1] (ch(t) U (t)
20:
for (a, 8) E (- 1i,l1....... 1...., ()ll)) x (.lll do
21:
w + a [. &
22:
+ projnull((H :E Mi.3)) im AAx w*)
dVm then
24:
pick E im(ASx w*) span : E Myjh)
25:
H + 1/1lv/12 and [W] w
26:
Set if_pareet + False and break
27:
if if___prrent is True then
28:
Add and to 9 for all E de(j)
edges to identified descendants
29:
Stage outputs: ف, H and W
30:
if the interventions are hard then
31: Stage 4: Unmixing for hard interventions
32:
for t E (2....,7) do
refine rows of H* sequentially
33:
2 + H
34:
ubs + Cov(2r 2 ) (Cov(Zan())]
35:
for m E {i W., + 0} do
>> searching for a suitable environment
36:
2m 2m (X; (X;H")
T Cov( 2 ) [Cov (
38:
if (u 7m an()) 2:m 11. 2m
and n noos then
H < H
+ m H an()))
removing the effect of the ancestors on Z
40:
break
41:
ă H")
recovered Z in obs. env. for graph recovery it 2, 11 2, (2, pa(j) (t) then Remove from 9
42:
for /. E (1, do
43:
for j E ch(t) do
44:
removing the edges from the nonparent ancestors
46:
Return 9 and Ž

---

Lemma 1 (17, Corollary 2)). Latent and observational score functions are related via s sx(x)
[G (22(2), where x = G 2.
Using Lemma for the scores and score differences defined in (7) and (8), respectively, we have
Pi #pa(t))
As (x) = [G As (2)
V
logg
(13)
q: 2pa(1))
iE
We compactly represent the summands in the right-hand side of (13) by defining the matrix-valued function A IF" + R2"x" with the entries
(=))) - á
log p= (pa(i))
Vi,j [
(14)
(: 2pa(t))
based on which (13) can be restated as
( |Gt]T A(2) ((z))(Dit)..m [Dmtl..m.
(15)
We note that [A()]], is constantly zero for & (pa(j) U (()), and j-th column of A is a function
of the variables in {zk k E pa(j) U {i}} which implies that the columns of A are linearly independent. Throughout the rest of the paper, we omit the arguments of the functions As and A when the dependence is clear from the context. Note that Din has n linearly independent columns (Assumption 1). Denote the indices of the independent columns by (bi....,bu, bn} and define the basis intervention matrix D E TR using these columns
DDam Dinttl. = 1 E } Vi, E [m].
(16)
Subsequently, it can be readily verified that the score difference functions {AsT m (bi..... bn are also linearly independent by leveraging (15) and linearly independent columns of A. Hence, these score difference functions functions. As such, { fAs : m E (bi..... b,. } serve as basis score difference functions. We stack these basis score differences, where each is d-dimensional vector, to construct the matrix-valuee function ASx X' > Rdxn, which is used as the basis score difference matrix in the subsequent stages.
sufficient to reconstruct the remaining unavailable score difference
ASx A
As [ D.
(17)
Finally, we note that ASx is directly estimated from samples of X via learning { (As Am Since A encodes the score differences in latent space, it cannot be estimated directly. Furthermore, D is unknown, and (17) is given to emphasize the relationship between observed and latent score differences.
: m E [n]]-
Stage 2: Identifiability up to an unknown causal order. We design a process that aggregates score differences of the UMN interventions and obtains partial identifiability guarantee (identifiability up to an unknown causal order) as an intermediate step toward more accurate identifiability. Specifically, we linearly aggregate the columns of ASx such that those aggregate scores facilitate identifiability up to an unknown causal order. Such mixing of the columns is facilitated by computing ASx W, where the mixing matrix W R should be learned. Given the decomposition of ASx in (17), if we learn W such that D W is upper triangular up to a row permutation, then we can subsequently learn an intermediate estimate H' using the image of ASx. This ensures identifiability up to unknown causal order since rows of H" will be equal to combinations of rows of GJ up to a causal order.
We design an iterative process to sequentially learn the columns of W. Specifically, at each iteration of Stage 2, we learn an integer-valuee vector w such that the projection of im (ASSx w) onto the nullspace of the partially recovered encoder estimate becomes one-dimensional subspace. To see why this procedure works, note that the function ASx w essentially combination of SN latent score differences via (17), and the SN score difference V log (2 | =pa(s)) - V log 4, 9,(z; *pa(t)) is a one-ooneeeet -iddimennional subspace if and only if the intervened node has no parents. By taking the projection of the im ASx w) onto the nullspace of the partially Iearned encoder while searching for a desired w, we ensure that the final encoder estimate H* of this stage will be full-rank. Finally,
we use k to denote maximum determinant of a matrix in {0, 13 (n ()), and show that the set
W K, ... +*}"
(18)
guaranteed to contain such w vectors. The following result summarizes the guarantees of this procedure.
8

---

Lemma 2. Under Assumption and intervention regularity, outputs of Stage 2 of Algorithm I satisfy:
1. D. W has nonzero diagonal entries and upper triangular up to row permulation.
2. [ E span([[G") : [d]) all E [n)] and {[H') ] : t [n]] are linearly independent.
Proof: See Appendix A.1.
Stage 3: Identifiability up ancestors. Next, we refine the outcome of Stage to ensure identifia- bility up to ancestors by updating the columns of W such that the entries of D W can be nonzero only for the coordinates that correspond ancestor-descendant node pairs. For this purpose, we design Stage 3 of UMNI-CRL that iteratively updates the columns of W. The key idea is that the edges the transitive closure graph Gte can be determined by investigating the subspaces' dimensions similarly to Stage 2. Leveraging this property, for all node pairs that do not constitute an edge in Gie- we aggregate the corresponding columns of W such that the corresponding entry of D W will be zero. In Theorem 3, we show that the outputs of this stage achieve identifiability up to ancestors, that is & is isomorphic to Gte and Z; is a linear function of {Zx; j an(i) U {i}} for all i [n]. Theorem 3. Under Assumption I and regular UMN soft interventions, outputs of Stage 3 of Algo- rithm I have the following properties.
1. The estimate (X; H*) sutisfies identifiabliiyy up ancestors.
2. 9 and Gie are related through a graph isomorphism.
Proof: See Appendix A.2.
Stage 4: Perfect identifiability via hard interventions. In the case of hard interventions, we apply an unmixing procedure further refine our estimates and achieve perfect identifiabiliyy. This stage consists of two steps. The first step relies on the property that the intervened node becomes independent of its nonddescessants and updates rows of the encoder estimate sequentially. In the second step, we leverage the knowledge of ancestral relationships and use a small number of conditional independence tests to refine the graph estimate from transitive closure Gre to the true latent DAG g. The following theorem summarizes the guarantees achieved by Algorithm 1.
Theorem 4. Under Assumption and regular UMN hard interventions for an additive noise model, oufputs of Stage 4 of Algorithm have the following properties.
1. Estimate 2(X: H*) satisfies perfect latent variable recovery.
2. pz is adjacency-faithfu to G, then & and G are related through graph isomorphism.
Proof: See Appendix A.3.
Finally, we note that the computational cost of UMNI-CRL is dominated by the cardinality of the search space for aggregating the score differences, e.g., in the worst-case, Stage 2 has ((2x)))) complexity. Therefore, the structure of the UMN interventions determines the complexity via its determinant. We elaborate on the computational complexity of the algorithm and the range of in Appendix A.8.
5 Simulations
We empirically assess the performance of the UMNI-CRL algorithm for recovering the latent DAG g and latent variables Z. Implementation details and additional results are provided in Appendix B
Data generation. To generate G, nodes. For the causal models, we adopt linear structural equation models (SEMs) with Gaussian noise. The nonzero edge weights of the linear SEMs sampled from Unif(+ 1.5)). and the noise terms are zero-mean Gaussian variables with variances of sampled from Unif([0.5, 1.5)). For soft intervention on node i, the edge weight vector of node i reduced by a factor of 1/2, and for hard intervention, the edge weights are set to zero. The variance of the noise term is reduced to of/1 in both intervention types. We consider target dimensions d {10, 50). generate 100 latent graphs for each (n, d) pair, and generate n, = 10 samples of Z from each environment. Transformation
Erdōs-Rény Rényi model with density 0.5 and {4, 5, 6, 7,8}
'The codebase for the experiments be found at https: //tgt/gtttttbtt///////// wwwiittb..oomaeeec.e.oeooeoo

---

Table 2: UMNI-CRL for linear causal model with UMN interventions (mean standard error)
UMN Soft
UMN Hard
SHD(G 9)
MCC
Esoft
SHD(G,g)
MCC
Eoard
4
10
0.91 0.12
0.95 = 0.01
0.08 0.01
0.75 + 0.11
0.98 - 0.02
0.13 0.02
5
10
1.67 0.20
0.93 = 0.01
0.09
1.65 0.11
0.97 0.02
0.13 0.02
6
10
3.19 0.26
0.92 - 0.01
0.12
3.12 0.25
0.96 +
0.12
7
10
5.44 0.34
0.00
5.36 0.15
0.15 0.03
8
7.63 0.41
0.89 = 0.01
0.06
9.70
0.87 0.03
0.20 0.03
4
50
0.77
0.96
0,66 0.00
0.98
0.13
5
50
1.93 0.20
0.93
0.10
1.80+0.11
0.13 0.00
6
50
3.39
0.27
0.02
0.03
3.05 0.25
0.95
0.03
7
50
4.62 + 0.30
0.91 0.01
0.13
6.12 + 0.34
0.91 0.02
0.16
8 50
8,26 1 0.49
0.90
0.14 0.01
9.01 + 0.53
0.88 + 0.03
0.28 1 0.02
G E [R [Rd is randomly sampled under full-rank constraint, and observed variables are generated as
X = G Z. Finally, for each graph realization, intervention matrix D is chosen randomly among column permutations of full-rank {0, 12,11 1 matrices, which satisfies Assumption 1.
score differences between environment pairs. Since a linear Gaussian model. X is also multivariate Gaussian, and its score function can be estimated by (x) = - in which θ is the sample estimate of the precision matrix of X. We note that the design of UMNI-CRL is agnostic to the choice of the estimator and can adopt any reliable score estimator for nonparametric distributions [29, 30].
Score functions. The algorithm
Graph recovery. To assess the graph recovery, we report the structural Hamming distance (SHD) between the true and estimated DAGs. Recall that UMN hard and soft interventions ensure different levels of identifiability guarantees. Hence, we report the SHD between (i) transitive closure G.o and for soft interventions, and (ii) true DAG G and & for hard interventions. Table 2 shows that latent graph recovery performance remains consistent for both soft and hard interventions when observed variables dimension d increases from 10 to 50, which conforms to our expectations due to theoretical results. Note that the expected number of edges is n(n 1)/4 since set the density of random graphs to 0.5. Hence, the increasing SHD is also unsurprising when the latent dimension n increases from 8, and the performance remains reasonable largest latent graph size considered among the closely related SN intervention studies [4, 8, 7, 9].
8. Finally, we note that n is the
Latent variable recovery. The estimates are given by H)) = (H' G) Z. Hence, we scrutinize the effective mixing matrix (H' G) and report the ratio of its incorrect mixing entries to the number of zeros in constant matrices C, and Can according to Definition 1, denoted by
nard Σj 1( H G)(, 0)
Σ L)gan(s) 1(H -Gly *
and Esoft
(19)
n12 n1
n² -. aa((i)]
We also report the mean correlation coefficient (MCC) [31], which measures linear correlations between the estimated and ground truth latent variables and is commonly used in related work. Table 2 shows that the UMNI-CRL algorithm achieves strong MCC performance (over 0.90) in all cases. Furthermore, the ratio of incorrect mixing entries remains less than 0.20 for both soft and hard interventions This demonstrates a strong performance of the UMNI-CRL algorithm at recovering latent variables for as many as n = 8 latent variables even for observed variables dimension d = 50.
6 Discussion
In this paper, we established novel identifiability results using unknown multi-node (UMN) in- terventions for CRL under linear transformations. Specifically, we designed the provably correct UMNI-CRL algorithm, leveraging the structural properties of score functions across different en- vironments. To facilitate identifiability, we introduced sufficient condition for the set of UMN interventions, abstracted as having n sufficiently diverse interventional environments. Investigating the necessary conditions for UMN interventions to enable identifiability remains an open problem. The main limitation the assumption of linear transformations. Given existing results for general transformations using two SN interventions per node [6, 9], promising direction for future work is extending our results to general transformations using UMN interventions with multiple interventional mechanisms per node.
10

---

Acknowledgements and disclosure of funding
This work was supported by IBM through the -B-s-lessellerr Future of Computing Research Collaboration.
References
[1] Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings the IEEE, 109(5)611-6634 May 2021.
[2] 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 Proc. International Conference on Machine Learning, Long Beach, CA, June 2019.
[3] Kartik Ahuja, Divyat Mahajan, Yixin Wang, and Yoshua Bengio. Interventional causal repre- sentation learning. In Proc. International Conference Machine Learning, Honolulu, Hawaii, July 2023.
[4] Chandler Squires, Anna Seigal, Salil S. Bhate, and Caroline Uhler. Linear causal disentangle- ment via interventions. In Proc. International Conference Machine Learning, Honolulu, Hawaii, July 2023.
[5] Burak VaniI, Emre Acartürk, Karthikeyan Shanmugam, Abhishek Kumar, and Ali Tajer. Score- based causal representation learning with interventions. 0rXIv:2301.08230 2023.
[6] Burak Vancı, Emre Acartürk, Karthikeyan Shanmugam, and Ali Tajer. General identifiability and achievability for causal representation learning. In Proc. International Conference on Artificial Intelligence and Statistics, Valencia, Spain, May 2024.
[7] Burak Varieı, Emre Acartürk, Karthikeyan Shanmugam, Abhishek Kumar, and Ali Tajer. Score- based causal representation learning: Linear and general transformations. arXiv:2402.00849. 2024.
[8] Simon Buchholz, Goutham Rajendran, Elan Rosenfeld, Bryon Aragam, Bernhard Schölkopf, and Pradeep Ravikumar. Learning linear causal representations from interventions under general nonlinear mixing. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA,, December 2023.
[9] 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 rep- resentations from unknown interventions. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2023.
[10] Jiaqi Zhang, Chandler Squires, Kristjan Greenewald, Akash Srivastava, Karthikeyan Shan- mugam, and Caroline Uhler. Identifiability guarantees for causal disentanglement from soft interventions. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2023.
[11] Chandler Squires, Yuhao Wang, and Caroline Uhler. Permutation- based causal structure learning with unknown intervention targets. In Proc. Conference in Uncertainty in Artificial Intelligence, August 2020.
[12] Alejandro Tejada-Lapuerta, Paul Bertin, Stefan Bauer, Hananeh Aliee, Yoshua Bengio, and Fabian Theis. Causal machine learning for single-cell genomics. arXiv:2310.14935. 2023.
[13] Tabitha Edith Lee, Shivam Vats, Siddharth Girdhar, and Oliver Kroemer. Scale: Causal learning and discovery of robot manipulation skills using simulation. In CoRL. 2023 Workshop on Learning Effective Abstractions for Planning, Atlanta, GA, November 2023.
[14] Jikai Jin and Vasilis Syrgkanis. Learning causal representations from general environments: Identifiability and intrinsic ambiguity. arXiv:2311.12267, 2023.

---

[15] Yibo Jiang and Bryon Aragam. Learning nonparametric latent causal graphs with unknown interventions. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2023.
[16] Simon Bing, Unmi Ninad, Jonas Wahl, and Jakob Runge. Identifying linearly-mixed causal representations from multi-node interventions, In Proc. Causal Learning and Reasoning, Los Angeles, CA. April 2024.
[17] Kartik Ahuja, Amin Mansouri, and Yixin Wang. Multi-domain causal representation learning via weak distributional invariances. In Proc. International Conference on Artificial Intelligence and Statisties, Valencia, Spain, May 2024.
[18] 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. In Proc. Advances in Neural Information Processing Systems, virtual, December 2021.
[19] Johann Brehmer, Pim De Haan, Phillip Lippe, and Taco S Cohen. Weakly supervised causal representation learning. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2022.
[20] Dingling Yao, Danru Xu, Sebastien Lachapelle, Sara Magliacane, Perouz Taslakian, Georg Martius, Julius von Kügelgen, and Francesco Locatello. Multi-view causal representation learn- ing with partial observability. Proc. International Conference on Learning Representations. Vienna, Austria, May 2024.
[21] Nils Sturma, Chandler Squires, Mathias Drton, and Caroline Uhler. Unpaired multi-domain causal representation learning. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2023.
[22] Phillip Lippe, Sara Magliacane, Sindy Löwe, Yuki M Asano, Taco Cohen, and Efstratios Gavves. Causal representation learning for instantaneous and temporal effects in interactive systems. In Proc. International Conference on Learning Representations, Kigali, Rwanda, May 2023.
[23] Phillip Lippe. Sara Magliacane, Sindy Löwe, Yuki M Asano, Taco Cohen, and Efstratios Gavves. BISCUIT: Causal representation learning from binary interactions. In Proc. Uncertainty in Artificial Intelligence, Pittsburgh, PA, August 2023.
[24] Yuhang Liu, Zhen Zhang, Dong Gong, Mingming Gong, Biwei Huang, Anton van den Hengel, Kun Zhang, and Javen Qinfeng Shi. Identifiable latent polynomial causal models through the lens of change. In Proc. International Conference on Learning Representations, Vienna, Austria, May 2024.
[25] Sébastien Lachapelle, Pau Rodríguez López, Yash Sharma, Katie Everett, Rémi Le Priol, Alexan- dre Lacoste, and Simon Lacoste-Julics Nonparametric partial disentangiement via mechanism sparsity: Sparse actions, interventions and sparse temporal dependencies. arXiv:2401.04l 000490, 2024.
[26] Kun Zhang, Shaoan Xie, Ignavier Ng, and Yujia Zheng. Causal representation learning from multiple distributions: A general setting. In Proc. International Conference on Machine Learning, Vienna, Austria, July 2024.
[27] Hiroshi Morioka and Aapo Hyvärinen. Causal representation Icarning made identifiable by grouping of observational variables. In Proc. International Conference Machine Learning, Vienna, Austria, July 2024.
[28) Aneesh Komanduri, Xintao Wu, Yongkai Wu, and Feng Chen. From identifiable causal repre- sentations controllable counterfactual generation: A survey on causal generative modeling. Transactions on Machine Learning Research, May 2024.
[29] Yang Song, Sahaj Garg, Jiaxin Shi, and Stefano Ermon. Sliced score matching: A scalable approach to density and score estimation. In Proc. Uncertainty in Artificial Intelligence, virtual, August 2020.
12

---

[30] Yuhao Zhou, Jiaxin Shi, and Jun Zhu. Nonparametric score estimators. In Proc. International Conference on Machine Learning, virtual, July 2020.
[31] Ilyes Khemakhem, Ricardo Monti, Diederik Kingma, and Aapo Hyvärinen. Ice-beem: Iden- tifiable conditional energy-based deep models based on nonlinear ICA. In Proc. Advances in Neural Information Processing Systems, virtual, December 2020.
[32] Joel Brenner and Larry Cummings. The hadamard maximum determinant problem. The American Mathematical Monthly, 79(6):626 630, 1972.
[33] Igor Araujo. József Balogh, and Yuzhou Wang. Maximum determinant and permanent sparse
0-1 matrices. Linear Algebra and its Applications, 645:194-228, 2022.
13

---

Linear Causal Representation Learning from Unknown Multi-node Interventions Appendices
Table of Contents
A Proofs
14
A.1 Proof of Lemma 2
15
Proof Theorem
A.3 Proof of Theorem 4
20
A.4 Proofs of Theorem and Theorem
................................
22
A.5 Proof of Lemma 3
23
A.6 Insufficiency of strongly separating sets
23
A.7 Analysis of interventional regularity..
25
A.8 Computational complexity of UMNI-CRL algorithm
26
B Additional simulations
27
B.1 Simulations with nonlinear latent causal models and sensitivity to noisy scores
27
A
Proofs
We start this section by introducing the additional notations used in the subsequent proofs.
Additional notations. We use (e; i [m]] denote n-dimennional standard unit basis vectors. For set S E [n:]. we use As to denote the submatrix of constructed by the rows {A; : E S)- For valid encoder H H. we denote the score functions associated with the pdfs of 2(X; H) under environments 0 and m by s²(=: H) and 2 (:: H) for all m [M]. addition the graph
notations introduced in Section 2.1, we define
(i A pa(i) U (i),
ch(i) ch(i) U (i). and an(i) an(i) (t}
(20)
Next, we provide an auxiliary result that will be used throughout the proofs the main results.
Lemma 3. For every pair (i,j) where E [n]] and E pa(i), the following ratio function cannot be constant in
A())lss A(=)
Pi(zz Epa(i)) ) (2) Epa(s)) 0z,
log i Pi(z; =pa(1))
log
(21)
azg
q:(2; Zpa(t))
Furthermore, the columns of A are linearly independent vector-valued functions..
Proof: See Appendix A.5.
We also restate the interventional regularity terms of the function defined in (14), which will help clarity in the subsequent proofs.
14

---

Definition (Intervention regularity) We say that an intervention node is regular for every possible triplet (i.j.c) c) where i E [n].] j pa(i) and Q, the following ratio cannot be a constant function in z
log Pi(zi 2pa(t)) qi (i(zi Apa(())
Pı(2) (pa(s))
[
a
Pi(zi (pa(())
+ c. log
log
(22)
4i {z(2) ?palj))
Ozz
q:(2i Apa(i))
By definition of A, this means that for (i, c) where E [n], E pa(i) and Q the following ratio cannot be constant function in
AA))] j +c. [A()))
(23)
AA)))
A.1 Proof of Lemma 2
First, we show that the search space in Stage I of Algorithm 1, ie.. the set W, has a certain property that will be needed for the rest of the proof. Recall the definition in (18)
W W - {-x, ...,, +x]"
(24)
in which x denotes the maximum possible determinant of a matrix in {0, (]((1))x(=x) We will show that for all [n]. there exists w W such that I ((D w] * 0) e,, Let adj(D) be the cofactor matrix of D, which is the matrix formed by the entries
(adj(D)) (D)
(25)
where D D]- is the first minor of D with i-th row and j-th columns removed. Then, the inverse of is given by
1 [adj(D))
D
(26)
dDt
By multiplying both sides from left by D and rearranging obtain
D [adj(D))] (Dt Iaxn
(27)
where all matrices are integer-valued valued and Lax denotes the n-dimensional identity matrix. The identity in (27) implies that
D w dDt(DD c., where w [adj(D)].
(28)
Since entries of Dd)(D) are upper bounded by K, we have w W and we conclude that
Vi Fw E W such that ID w * 0) e,
(29)
Next, we prove the lemma statements by induction as follows.
Base case. At the base case 1, we will show that ([D- 0) e, and H; e span([G]) for some root node i. Consider a vector w E W and denote = D w. Then, using (17),
[])
ASx
|G A. w [G+]T_ c.
(30)
In the base case, we investigate the dimension of im (ASx w). Then, using (30), we have
dim (Am w)) = =dim (im((G')
c)) dim ( (im(A A c))
(31)
(29) implies that there exists w E W that makes (c + 0) = e;. Suhsequently, is a root node, only nonzero entry of the column A. is Agii and we have
dim (im(ASx w)) = dim (im((G)T A.))) = dim (im([G)), A..)) = (32)
Hence, by searching w within W, Algorithm is guaranteed to find vector w such that dim(im( A c)) = 1. Next, we show that if dim((m(A c)) = 1, then I (c * 0) = e, for root node We prove this as follows. Consider the set A = {i e, 0} and let be the youngest node in A, i.c., has no
15

---

descendants within A. Using the fact that A = 0 for all l & pa(k) and C₁ = 0 for all & E de(i), we have
c Excch(e) cs Ar
Exeonte)
A
vl [n]]
(33)
A Exech(s) Oy: Ai,
C2 A
If has multiple nonzero entries, let o₁ denote the second youngest node in A. if & pa(i), then for f = j. (33) reduces to
A J.C Gj G.AAj.
(34)
A, C. Ais
which is not constant due to Lemma 3. j pa(i), then (33) reduces
A _
Cy Ass + C. As C, Ais
(35)
which is not constant due interventional regularity. Hence, in either case, there exist multiple vectors im(A c) with distinct directions. Therefore, dim (im(in (A .c) = 1 implies that c has only one nonzero entry C; + 0. Finally, if is not root node, for E pa(i), (33) reduces to
c AJ
(36)
A
which is not constant due interventional regularity. Therefore, dim(in(A c)) implies that (c & 0) = I[D W).1 + 0) = e; for a root node i. Next, using (30), we have
ASx = A (G']
(37)
Hence, denoting the root node by TI, setting H; DD WD.1..1 Cx, and Hi E spann[[*)] which completes the base step of the induction.
for any im(ASx w) ensures that
Induction hypothesis. For the induction step, assume that for all t [kt] we have linearly independent vectors Hi spann[[[ ; pa(())) and
{ 0, j>t t 0
[D [D- Wl
AE (j)
(38)
j ==
t
where { } constitutes the first & nodes of a causal order æ. We will show that if
dim(V) = where
V projnutt (i)) im(ASx w)
(39)
then w W satisfies
D D.wlz, [0, j>k+1
(40)
40 j=k+1
for the causal order æ. First, define M A [n] (mi,..., 3 Note that, by the induction premise,
null( {H; : Ze [+]}) null([ : :e [K]))
(41)
Then, for any w E W and c = D w, we have
:EE V = (10, (G im(A c))
(42)
Subsequently, we have
dim(V) dim (im (IG") AM .c) dim
cc)
(43)
Note that, if node M6+1 has no ancestors in MR+1, using the vector W which makes ( & 0) e, ensures that (annii(AMMa.)))) within W, Algorithm 1 guaranteed to find vector w such that dim (iimiiiMae... (AM c)) Next, consider the set A = {i E M c, # 0}. Since Ti...., Ty are first k-nodes of a causal order π, we have
dim(in(A,,, ee,)) 1. Hence, by searching w
A A =0, Vi MA41, Vj [k]
(44)
16

---

Then, if dim(V) = 1, A is not empty since otherwise (AM++1 c) is equal to zero vector and
dim(V) = 0. Let i be youngest node in A, ie, has no descendants within A. Similarly (33), we have
c Exerr( Cb
Ag,
VLE MMMM-1.
(45)
A; 2..0 c
Ci. As
If A has multiple elements, let j be the second youngest node in A. jf & pa(i), then for l = j. (45)
reduces
A S3.An
(46)
A. C. A,
which is not constant due to Lemma 3. if pa(i), then for 8= j. (45) reduces to
A Cj Ajs + Az
(47)
c
C₁ A.
which is not constant due to interventional regularity. Hence, in either case, there exist vectors with different directions in im M Therefore, Limmimm(AM,,) only one element, i.e., there is only one node i E [n]]
c)) 1 implies that A has (TI...., Jhe such that c; * 0, and also pa(i) S f........ }. Hence, denoting Th+1 i, [D Why nonzero for j = k ++ and zero for for any im(ASx w) (span((H)) (HH)
all j > h 1. Subsequently, by setting H H we have
[}]])
H E span [ In, : (]})
(48)
Finally, note that the contribution of [G*] in H is nonzero since c; 7 O. Hence, H is linearly independent of {Hi..... Hj]. which completes the proof of the induction hypothesis. Therefore, (38) holds for all t [n]. which implies that P. D W is upper triangular and has nonzero diagonal entries, and concludes the proof of the lemma.
A.2 Proof of Theorem
We will prove the theorem by proving the following equivalent statements: The output W of Stage 3 of Algorithm I satisfies
0 Te $ an(TT) D D.Wwe = {
(49)
and
t E pa(j) - Te an())
(50)
for all j E [n.] The second statement of the theorem, graph recovery up to transitive closure, is equivalent to (50) by definition. Next, we show that (49) implics the first statement of the theorem, that is identifiability of latent variables up mixing with ancestors. For this purpose, using (17), for any w E IR"", we have
|G]] A. w. ASX =
(51)
Then, for W Mig, using the fact that A A 0 for all Ti & pa(m)), the coefficient of [G*],. on the right-hand side becomes
Σ W E()
A [D W =
Σ A D D W
(52)
T.ECH(()))
If Te an(TT) (,,),, then T E ch(mT)) implies that T & aT(())) Then, using (49), the sum in (52), i.e.,
the coefficient of [G+] m, in function (ASx w), becomes zero. Furthermore, since [D W * 0.
the coefficient of [Gt],, m, in (ASx w) is nonzero. Therefore, (49) ensures, by choosing H; E
im(ASx (W)..) for all E [n], we have
H E span ([G'),, :j E am()))) and H H are linearly independent. This implies that we have H' P.. C.n G
(53)
(54)
where P,r is the row permutation matrix of π, and Can E IR is constant matrix with nonzero diagonal entries that satisfies [Canli.j = 0 for all j an()) Subsequently,
H(; - H X P.. Can .. G. 2 - P,, Can Z, which is the definition of identifiability up to ancestors for latent variables, specified in Definition 1. In the rest of the proof, we will prove (49) by induction.
(55)
17

---

Base case. At the base case, we have t = n- and j n. We will show that, at the end of step (t.j) (n 1,,,, DD Wh o implies that nn E pa(m,)) J. By Lemma 2, we know that
D
m- #0, [D W Whan # 0, and [ W m = 0.
(56)
Consider some integers E {-nk...... nR) and B E (1....,nd Let w a aWW],nn-1 [ and c* D w Since + 0, (56) implies that c, + 0. Using Lemma 2, we have
null( i E [n 21]) null([]!)) JR. : [n 2
(57)
Then, have
V projmull (H; : (--2))) im (Ax w")
(58)
pro]nut(([ : [n- (G im A c*))
(59)
Subsequently,
G G
(A
[ATo-]]
c**) )
dim(V) = dim
Tn-1
im
(60)
ATn
nm
A A Ara
-c*)
dim
im
(61)
= dim
im
C
1,
+ Cx., A Amm-11;T
(62)
Tm Annin
Note that in the last step, we have used the fact that π is causal order and j & pa(i) implies that A., = 0. Then, if F2-1 E pa(a)), interventional regularity ensures that the ratio of the two entries in (62) is not constant function which implies that dim(V) 2. Furthermore, if πn-1 & pa(m.) but cx f 0, then (62) reduces to
dim (V) dim im ([
( -A A ) c A
-2
(63)
due to Lemma 3. Therefore, if w" satisfies
(im(proinull :i)(n-2)) im (ASx ww)) = 11
(64)
by setting W) :. = =w", we guarantee that D W -a-1.m = 0) if .n & pa(m,)) Note that, for this
case, setting either (a, B) (- [D. WIn-in; D Wmn-1n-1) achieves
W 11- or (a, 3) (D. W 1,1: D
D w 1x-1 = a. a..D W a. 1 B D W m. 1.x = =0.
(65)
Note that the entries of [D W] are bounded as
D. Wl- = Σ WRJ S
Wx.l = W.ll, [m]
(66)
kEin]
kE(n)
Hence, Algorithm is guaranteed to find cx Rn-1
by searching over
(a, | -in-
W W.n-11hb) (1..... (.
(67)
Therefore, if dim(V) is never found to be 1 for any (a, 3). means that mn-1 pa(m.), and the algorithm adds the edge (n 1) + n, which concludes the proof of the base case.
Induction hypothesis. Next, assume that for all t E {lt + 1.....
n and j E {t+ 1....,,,,
{ m. an(T)) and Te an(T)) + t E pa(i).
DD W|
(68)
n J
We will prove that (68) holds for t i and {t + 1, I...., n). We prove this by induction as well.
18

---

Base case for the inner induction. At the base case, we have t = k and j = k + 1. Since т is causal order, have
E (T(nTT+)))))))))))))))) = Th E pa(T<+1).
(69)
Also, ch(k) is empty this iteration of the algorithm. Then, Mr,k+1 [k 11. Consider
some integers a E {-nk.... nx) and 3 E {I....,,x)} nx.. Let w = a + 3[W], and
c" D w Using Lemma 2, we have
i [k 11}) null([[('), :E (
(70)
Then, have
V pr :E(--- im w")
(71)
pro].ii(( :)((--I)) ([ -immm c²))
(72)
Using (68), cx
for h: Subsequently,
G Jm G [e
Ama
.. .e))= =dim
dim im ([An A ..))
Arx
dim(V) dim
im
(73)
A A
Also, recall that A Ame.m
= 0 for all j < k. Then,
A Th ATT+1
.ce) dim
im ((
Argire
+ C
dim(V) = dim
im
Cap41 Austiso4t
(74)
Using (68) again, we have c # Then, if TTy E pa( interventional regularity ensures
that the ratio of the two entries (74) is not a constant function which implies that dim(V) = Furthermore, if & pa(T=+1) but CT2 jf O, based Lemma 3, (74) reduces to
dim(V) = dim ii ([c=
((r
C+ ATEIT
A
()) =2.
-22.
(75)
Therefore, if we have
dim(proinut( :
(k-1]]) ( 1k) im ASx w")) 1,
(76)
by setting [W]. M.,++ = w", we guarantee that [D W W] m 0 if n & pa( Note that, similarly the base case of outer induction, Algorithm
guaranteed to find c - = 0 by searching wl, } X (I...., I x+1l11). Therefore, if dim(V) is never
over (a, 9) E -..l... found to be for any (a,, B), means тr pa(**+1), and the algorithm adds the edge t - which concludes the proof of the base case for the inner induction.
Induction hypothesis for the inner induction.
Next, assume that for all {k: + 1, 1....,u).
{
0
& ()())) Tkk π
D
W mhe
and T E En((T)) - k pa(p)
(77)
We will prove that (77) holds for j = u + as well. We work with ME = [u - 1] ( (
Consider some w a a ] + 3 W Juut1 in which # and let c" D w Due to
the assumption in (77), ancestors of any node in M are contained in M Then using Lemma 2 again, we have
( E MR,+t1)) null([[('), : Mautti))
(78)
Then, we have
V = projmul(( iiMM im AmsA w")
(79)
projnut(([ NEMM (G T. iin(A c²)),
(80)
and
c²)) 2 dim im Ar.
.-') .c))
dim(V) = dim
(81)
19

---

We will investigate dim(V) through the ratio
Amp C²
(82)
Amut c²
Note that, using (77) and the fact that π is causal order, we know that
Cx. 0 Vi E (u + 2,.... n) (1k: + ,...,, m) \ aan(u +1},
(83)
and
A Agy = O
Vay & pa(m))
(84)
Then, using (83) and (84), we have
A An
Σ
Cr A Autii Creen -Auus
(85)
M.ECh(Tu41)
Ax. c² cr, AT + c Amamous
c Am
(86)
6: Ecc(ec ) and (Ean((+1)
First, note that if there exists l such that тa E an(TT)) and nT E an(Tu41). then by the assumptions in (68) and (77), we already have that it E pa({) and & E pa(u + 1) which implies that & E pa(u + 1). Then, we only need to consider the case where there does not exist such f. In this case, the summation in (86) is zero and we have
A c² A Auti
Cr. AT + C ATT
(87)
Au4110u41
Next, if my E pa( 1): interventional regularity ensures that this ratio is not a constant function which implies that dim(V) 2 2. Furthermore, Ty & an(TT+1)) but cr * 0, then (87) reduces to
A Amut. c²
-
(88)
which is not constant due to Lemma 3 and subsequently dim (V) 2 2. Therefore, dim(V) 1 implies that Ta & an(Tu+1) and ct [D WITTL.ut
Finally, similarly the previous
cases, Algorithm 1 is guaranteed find such (a. () that makes c²= 0 by searching over (a, () {-I[W ........ [ *, 1, {l...., W 1 e.g., (a, (-ID Wik,,tt, [D W)k..). Then, the proof the inner induction step, and subsequently, the outer induction step is concluded, and (49) holds true. Consequently, the proof of the theorem is completed.
A.3 Proof of Theorem 4
We start with a short synopsis of the proof. Stage of Algorithm 1 consists of two steps. The first step resolves the mixing with ancestors in recovered latent variables and the second step refines the estimated graph to the edges from non-parent ancestors to children nodes. The proof of the first step uses similar ideas to that of [7, Lemma 10]. Specifically, we use zero-covariance
surrogate for independence and search for unmixing vectors eliminate the mixing with ancestors. Since we do not have SN interventions unlike the setting in [7], we use additional proof techniques to identify an environment in which a certain node is intervened. knowledge of ancestral relationships and use small number of conditional independence tests to remove the edges from non con-parent ancestors to the children nodes.
the graph recovery stage, we leverage the
A.3.1 Recovery of the latent variables
First, by Theorem 3, for the output H of Stage of Algorithm we have
H G P
(89)
for some lower triangular matrix L Raxn such that L has non-zero diagonal entries and L,,j for all j & ai)), and π is a causal order. We will show that the output of Stage 4 satisfies that
1(H -G() = -T
V [n]
(90)
which will imply
2(:: = X H G. - P .Z,
(91)
20

---

where Px is the row permutation matrix of x and C. is a constant diagonal matrix with nonzero diagonal entries. Note that this is the definition of perfect identifiability for latent variables, specified in Definition 1. We prove that Stage 4 output H* satisfies (90) as follows.
We start by noting that since Ti is root node in 9 shown in Lemma 2, (89) implies
H G = Lm Ci,, and 1 ( G|1) =c
(92)
and (90) is satisfied for = 1. Next, assume that (90) is satisfied for all & E {1...., k 11. i.e.
1 ((H'. [[])'))))= = e
(93)
Consider k-th iteration of the algorithm in which we update Hद where {H; i E [k - 1}} already satisfy (90). We will prove that (90) will be satisfied four steps. Consider any environment 8 and use shorthand 2m for 2m H*)
2m [k)(k) Step Cov(u implies
+ 2xn 2m an(k)) has a unique solution for u. For any E [k 1), (93)
2 [H* G] - = C; -m
(94)
for some nonzero constants {c1,..., Ct 1). Specifically, by defining
ain(k) (n. m 7+
(95)
in which the nodes topologically ordered, then
Z = , 2 [c,, 4T, -T, ..... Cy, -
(96)
Note that Cov(2 (k)))) is invertible since the causal relationships among the entries in 2m not deterministic. Then, we have
(k))
Cov(u (x)R)) + 2%th ())( =0
u -Cov (2 2m(x)) (Cov(2
) (97)
For the next step, using the additive noise model specified in (3), under hard interventions we have
Ta & I (fTNY Now), No,,
2T 5m (Zpa(T))) N where (SH N & {
(98)
Th E I
where NT, denotes the exogenous noise term under intervention. Let us use f and N shorthands for fm and Kk-
Step 2: Cov(u 2m (R) + 2 2m (x)( 0 and u am)(k) 11. (n(()) implies that f cannot be
nonlinear. Define random variable U A (u ah(R) + ).) Suppose that Cov(U, 2m (m)))) = 0 and
U 11 2m an(ay) Recall that using (89), 2Thh is linear combination of the variables ( : E an)))
and 2m i.e.,
2 = c' 2m (k) c -mm
(99)
where c' E [R|si((k)) and cb is non-zero scalar. Then, U can be restated as
==u u 2m (k) + 2Th = (u + c') 2m (n(k) + có (f(Z + N).
(100)
Note that U 1L 2m ki(()) and (96) together imply that U is independent of any function of the variables in mmmm E ak))). Hence,
(u + c') (M)()) + cb ((((a(())) II (u c') 2m + c6(l((Za(()) N),
(101)
where the right-hand size is U and the left-hand side is function of (Z : E an())) Also, since N is the exogenous noise variable associated with Z we have
(u + c') Z
c6 f(Zpa(k) 1 N. N.
(102)
(101) and (102) imply that (u + c')- (m)()) + c f(pp(R)) is constant function of 2m ( Since (u + c') -2m is linear function (or constant zero) and c/ A 0, f cannot be nonlinear function which concludes the proof of this step. Next, we consider two possible cases, / zero, i.e., Ta E m case, and f is linear function.
21

---

Step 3: E I" and f = 0. In this case, we have z = N. Note that for = -c', (100)
becomes
U U= c N = c/ mm
(103)
which implies
(H) + u H an))))
G. m 7% skn(k) U cj 7
(104)
and
1 1( u (. (x)) G) m
(105)
Also note that, any vector that satisfies U 11. 7m also satisfies Cov(U, 2mm (n)())) 0. In Step 1,
(k)
we have shown that Cov(U, ( 0 has a unique solution. Therefore, U 1L ( also has unique solution, which we have found in (97). Hence, if 1 then Algorithm updates H; correctly.
Step 4: & 1 and f is linear. Only remaining case to check is Tae & 1 and f is a linear function. Let
p((xr) c" 2
an(k)
(106)
in which c" E RR [an(()] has nonzero entries only the coordinates corresponding to pa(*k). Then, for (u+ c') zm
si(k) + +c f(Zpa()) to be a constant function, we need to have (u+ + c")) = Note that, for c"
case, i.e., * and mu & 1" have already found uobs -c' co c" using the observational environment. Since we are searching for u -c', which is required to achieve scaling consistency, we compare the solution u" at environment e to a and they are distinct, we update Hy.
To sum up, Stage 4 updates Hi correctly by identifying environment 5 in which ZT, intervened and eliminating the effect of H (n) Finally, we note that such an environment is guaranteed to exist
among {Emh Wm,. * 0}. To see this, recall that D W W| This implies that there exists m such that D Na, m and W m, * O, and D Dx.,m
m F 0 due to (49), proven in Theorem 3. implies that Th E 1" This completes the proof of (90), and subsequently the proof of the perfect latent recovery.
A.3.2 Recovery of the latent graph
After the first step of Stage 4, we have
2, = 2m
14 E [n]
(107)
where {er & E [n]} are nonzero constants. Then,
2, LL 2, :i::ie))
Zm. 1 Znz 12 : S}.
(108)
Consider node t E [n] and node j E ch(t). If E pa(TT), given the adjacency- udjacency-faithfunes, faithfulness assump- tion, (108) implies that 2, and Ê, cannot be made conditionally independent for any conditioning set. On the other hand, note that for any set S that contains all the nodes in ра(π;) and does not contain a
node in de(zz) satisfies
2m. 11 Zx, 12 iE
(109)
and subsequently,
2, 11 2, :2
(110)
Finally, if ग. & pa(T;), then pa(j) \ {t) contains all the nodes in pa(T,) and does not contain a node in de(TT). Hence, the second stage of Step 4 of Algorithm I successfully eliminates all spurious edges between and j e ch(().
A.4 Proofs of Theorem and Theorem 2
Under Assumption and interventional regularity. Lemma 2 and Theorem 3 show that using UMN soft interventions, outputs of Algorithm satisfy identifiability up to ancestors. Hence, identifiability up to ancestors possible using UMN soft interventions.
Furthermore, note that Lemma 2 and Theorem 3 are valid for both soft and hard interventions. Then, Theorem shows that using UMN hard interventions, Algorithm outputs satisfy perfect identifiability. Hence, perfect identifiability is possible using UMN hard interventions.
22

---

A.5 Proof of Lemma
We start by showing that [A(=)]s,s cannot be constant function in z. This is shown in the proof of [5, Lemma 7J. For paper be self-contained, repeat the proof steps in [5] as follows, For i [n]] define
Pi(zs ?pa(t))
(12,, =pa(s))
(111)
(i(2 ?pa(t))
We prove by contradiction that h=z;, *pa(s)) varies with 2;. Assume the contrary, i.e., let h(zi, (pa(t)) = h(2pa(t)). ) By rearranging (111) we have
ps(zi (pa(t)) = h((pa(s)) (:(2; 2pa(t))
(112)
Fix a realization of Epa(() - * pa(()) and integrate both sides of (112) with respect to 2,. Since both p; and qi are pdfs, we have
1 = pi(zi (pa(s)) / h(spact)) go(2i (pa(c)
(113)
JR
= -((pp((o) ( golos I epa(t)) )dz;
(114)
= -)(faa(1))
(115)
This identity implies that pı(2: A(aat)) = (=(=; (n)) ) for any arbitrary realization "pa(i) which contradicts with the premise that observational and interventional causal mechanisms are distinct. Consequently,
a p=(2; 2pa(i))
[A(=)),,
log
(116)
0z, (2; {pa(i))
is not constant in 2. Note that for fixed realization of = 27. =pa(i) "pa(s)- and ppa()) (a))))
[A (2)las becomes constant whereas [A(z)),, varies with 2,. Hence, their ratio is not constant 2. Finally, note that A22) is an upper-triangular matrix since (I...., is a valid causal order and for all i [n].
Pa(2 Epa(K))
log
(117)
(:(2; Zpa(t))
function of only (zk k E pa(i) (i)). Together with the fact that diagonal entries of A(z) not constantly zero, the columns (and rows) of A are linearly independent vector-valued functions.
A.6 Insufficiency of strongly separating sets
Background. Recently, [16] has shown the identifiability of latent representations under linear transformation using do interventions. Specifically, they have shown that strongly separating set of multi-node interventions are sufficient for identifiability. It is well-known that strongly separating sets can be constructed using 2 2[log, n elements. Hence, identifiability can be achieved using 2 log n:) do interventions. In this section, we show that a similar result is impossible when using stochastic hard interventions.
Lemma 4 (Impossibility). A strongly separated set 2 n. stochastic hard interventions are not guaranteed to be sufficient for perfect identifiability In fact, they are not even sufficient for identifiability up to ancestors.
Proof: We prove the claim for nodes. The smallest strongly separating set for two nodes is {{1}, {2}}. We will consider two distinct models of latent variables and latent graphs that are not distinguishable using interventional data of / = {1} and / = {2) (without observational data). The key idea is that after the linear transformation in the first model is fixed, we can design the linear transformation the second model such that observed variables both models will have the same distributions. We construct pair of indistinguishable models follows.
23

---

First model. Let G consists of the edge 1 + 2. Consider a linear Gaussian latent model with the edge weight of 1 on Z2 is set to 1, and consider identity mapping, i.e..
Ni 9 2, G= 1 z = Ni + No
N1 N2
Z
(118)
N1 ~ Vi). No NO0, VT), ~00 V2).
N2 ~ ~O, V22)
(119)
where Vi, V/', 12, V nonzero variances of the exogenous noise terms such that Vi + V to ensure that interventional and observational mechanisms of node I are distinct. Then, the observed variables X in two environments given by
VT
V
V/2 1)
x 2 N
0,
(120)
VT
VT
Vi
and X² G 2Z N
(121)
0
V
Second model. Let & be the empty graph. Consider a linear Gaussian latent model under a non-identity mapping parameterized by
G= a
N; N₂
N1
g empty,
2
z
(122)
d
N
N₁ ~ VI). ~ NT~N00,V73) VT). N₂ ~ ~N, Va),
N₁ ~ ~0, V22)
(123)
where V1, Vr, V2 V are nonzero variances of the exogenous noise terms such that V1 * V and V/2 * Vig' to ensure that interventional mechanisms are distinct from the observational ones. Then, the observed variables X in two environments are given by
a v + VV acVi bdV2
acVi + bdVz VVVi + d VVV2
X' G 2 N
0,
(124)
and x2 G 2 N (1,,
V + PV acVi + bdV
acVi WVV," V V2
(125)
Non-identifiability We will show a nontrivial construction that ensures X X and X² X2, which implies the non-identifiability from intervention set {{1). {21) First, using (120), (121), (1 (124), and (125), we write all requirements for X = X and X = X²2 to hold:
V = V/- + 82
(126)
V VcVi + bdVe2
(127)
V/2 (c² ac) + (ef - -bd)
(128)
V1 a + +bT
(129)
V V + +VV
(130)
0 = a + bdV2
(131)
Now, let V1, Vi,, Vz, Vy take any values such that ViV₂ * V.Vg. We want to show that there exist ba,b,c, c, d} and (Vi, V V2, Vi' values that satisfy all the six equations. Note that, the values of Vi, V2, and V/J are not constrained by multiple equations or additional conditions. Hence, for any given (a,b, d, and (Vi Vi V2, V2'), can readily Vi, V2, and V to satisfy (129), (128), and (130), respectively. Therefore, we only need to ensure that we can choose {a, b, c, c,d) such that the identities (127),122), and (131) are satisfied. Next, after substituting only need to choose {a.b, c} that satisfy
1, and rearranging, we
acV, bV = 0, (a² - -d²-ac) + (6² b) 0.
(132)
(133)
Substituting ac = -b into (133), we require
Vi
Vi V
d" Vi -0
(134)
V
24

---

(134) has a real solution for if and only if
V V22 Vi V/2
2
a² 5 1V
(135)
This implies that, if V.V V22 + V.VV we can choose a and b that satisfies (134), and e is determined by (132). This means that, for any given (V1, Vr. V2, V2 such that Vi * V V2 there exists {a, b, c, d) and (Vi, Vi" V2, V22 that ensures X X and X² = X2. Hence, interventions on the strongly separating set { are sufficient to distinguish the first and second models, which completes the proof of non-identifiabiiiy.
A.7 Analysis of interventional regularity
Lemma Consider additive noise models under hard interventions. Interventional regularity is satisfied if the poxt-intervention score function of Ni, denoted by i, is analytic and one of the following true.
af((2)a()) is not constant and there do not exist constants 01 + 1, 022 E R such that Ozj
1.
F(y) = on . Fly + 02) +03 Vy ER.
(136)
2. @f((2pa(i) Ozj
is constant and noise term N₃ remains unaltered after the intervention.
Proof:
The additive noise model for nodes and j are given by
Z: ((((pa()) No. and Zg [2(Ppa()) + N₃. When nodes and j are intervened, respectively, Zi and Z₁ are generated according to
(137)
Z: = N and Zj Ng
(138)
in which N; and N, correspond to exogenous noise terms for nodes and j under intervention. Then, denoting the pdfs of N,, N₁, N,, N, by h4 h, h2 h, respectively, we have
(= ?pa(i)) h4(2 fi(Epa(t)))
(139)
q: (2,) hu(2z),
(140)
P5(2) #pa(1)) = hr(23 -f((pa(t))),
(141)
(,(2) = h))(z))
(142)
Then, by denoting the score functions associated with hi h4 h2g hy by ri. Fe, Fyy Ty. respectively, have
0
Pi(z 2pa(t)) = (2())) - [m, + fe(zpa(i))).
log
(143)
02;
(2()))
0
Pr(2; 2pa(i)) -r((n)) Of((2pa(e))
log
(144)
0zj
qi(2))
θzj
P5(E Spali)) ry((t)) ( Fy( fs(pa(()))
log
(145)
0z,
(z(z))
Next, assume the contrary and let the ratio in (12) be a constant E R. Then, substituting (143), (144), and (145) into (12) and rearranging the terms, we have
0f((Epn(1)) (r((n)) a Fe(nn + f((2pa())) (ry(m,) - rn(n, + fs((((()))) (146)
02,
25

---

Case 1: (S((aputa) is not constant. Consider two distinct realizations of pa(())pp()) such that 0
dzg
0z, f((ppa()) takes values of 31 and B2 where 31 o B2. Then, (146) implies
(a + (1) re(m)) - a fn + 71) = c u1 fn + 72) U2
(147)
(a 82) r((m))
(148)
for some constants 7/1 72, M1, W2 for all n, E R. and 31 + B2. By rearranging the terms, we get rid of r, (m,) terms and obtain
a ((a + 32) Fr( + m)) - (a + 31) F((m + 72)) = c ((a + B1) u2 - (a + (2) 21
(149)
Since 31 + B2. (149) implies that
Fv(y) a1 F. + x22) 0z
(150)
where 01 22 ag are constants and a * Therefore, there does not exist such constants, then the ratio in (12) cannot be constant.
Case 2: afelspatt)) 33 for some nonzero constant |. In this case, (146) becomes
dz,
(a + (+))): (n:) F,(n;: (=(a((s))
(1y(n)) Fy(ny (f(psts)))
(151)
Note that the right-hand side of (151) does not contain n,, Also note that since (=(ppa(t) is continuous, there exists open interval θ S TR such that fi(=pa(1) can take all values 0 θ Then, by taking the derivative of both sides with respect to n, and varying fa (Zpa())) in O, we find that F, + 0) is constant for all 0 E O. Since Fn is analytic, this means that 7e(y) = on y + 02 for some constants on, 02 for all y IR. Then, since the noise term is invariant under intervention, have r; fz. Substituting this into (151), we obtain
(a + () (an; + 02) 001 f((p(ts)
(n)(n))- f1 ()(po(())))
(152)
Since 3 + 0, the left-hand side a function of n; whereas the right-hand side is not, which is invalid. Hence, the ratio in (12) cannot be constant in this case.
A.8 Computational complexity of UMNI-CRL algorithm
UMNI-CRL (Algorithm 1) consists of four stages that we claborate on as follows.
Stage 1:
The score difference estimation is only performed once before the subsequent main algo- rithm steps. Since our results and the algorithm do not rely on a specific score difference estimation technique, studying the computational complexity of this step is out of scope.
Stage 2: In this step, we check the dimension of V, a projection of a subspace (see line 6 of Algorithm 1) at most n 12x++)" times. Here, x denotes the maximum possible determinant of matrix in {0, 11 In the proof of Lemma in Appendix A. we discuss why this choice facilitates the identifiability guarantees.
Stage 3: In this step, we check the dimension of V (see line 23 of Algorithm 1) at most || (.. x | 1 times for every (t.j) )) in Stage 3. Note that W is updated within the steps of Stage 3. Therefore, the exact computational complexity would be a function of the graph structure and the outputs of Stage 2.
Stage 4: Unmixing procedure for hard interventions essentially operates post- post-processing step that does not pose additional computational challenges. For instance, the total number of conditional independence tests in Stage 4 is O(n²).
Bounds on K. Section 4, we defined i. as the maximum determinant of a binary matrix {0, (1==-)))(-11 and noted that the computational complexity of UMNI-CRL algorithm depends on n and as seen in Stage 2 above. In general, using the well-known bound for the determinant of {0, 1) matrices [32], we have
n/2
k < [2(n/4)
[add [adj(D))
<
(153)
2n-1
26

---

d'
d
soft Iwett. ancestors)
0.30
-+. sort (wrt ancestor))
hard ownt true DAGI
-# hard twin thu DAC)
Incorrect mixing ratio
0.25
3
10.00
SHD
0.15
0.10
0.06
0.00
30
35
40
45
50
60
30
35
45
50
55
Signal to noise ratio (dB)
Signal to noise ratio (dB)
(a) Graph recovery
(b) Latent variable recovery
Figure 1: Sensitivity analysis of UMNI-CRL algorithm for quadratic latent causal models. The results for = 5 latent nodes and d = 20 observed variables, 10a samples, and for average of 100 runs. (a): SHD 9) versus SNR (soft) and SHD 9) versus SNR (hard). (b): Incorrect mixing ratio (soft versus SNR (soft) and hard versus SNR (hard).
However, for specific cases, we have much smaller upper bounds for K. For instance, for the choices of n being 2, 3, 4, 5, 6, 7, K is known to be upper bounded by 2,,, 3, 3,5,5,, 9, respectively [32]. Furthermore, [33] shows that the determinant of a matrix in {0, juxxn with n + k nonzero entries is bounded by 2k/3, Hence, if D has n + k nonzero entries, then
< 1
(154)
This implies that in can be quite small for sparse UMN interventions. For instance, we take the exhaustive set of SN interventions and only add two additional intervened nodes in total, then have k = 1.
Empirical tricks. Finally, we note that various empirical tricks be used reduce the algorithm's 's computational complexity. For instance, after every update to W, we can divide the columns of W by the greatest common divisor of its entries. Furthermore, even though becomes larger, in our experiments with up to n nodes, we observe that setting x = 2 usually suffices for good performance. Hence, we K 2 in the simulations in Section 5.
grow quickly
B Additional simulations
Details of evaluation metrics. For the graph recovery via hard interventions, we use conditional independence tests in Stage 4 of Algorithm Since we adopt a linear Gaussian SEM latent model, we use a partial correlation test and set the significance level to 0.05. For the latent variable recovery error metrics hard and foot defined in (19), we first pass the entries of H through a threshold of 0.1, then compute the incorrect mixing metrics.
B.1 Simulations with nonlinear latent causal models and sensitivity to noisy scores
In Section 5, we have adopted linear Gaussian SEMs as latent causal models for which the score estimation can be done via estimating the precision matrices of the observed variables. In this section, we perform additional simulations study nonlinear latent causal models investigate the relation between the algorithm's 's performance and the accuracy of the score function estimates. To this end, we adopt a quadratic latent causal model under varying amounts noise in score functions. Specifically, we follow the experimental setup in [7] and adopt a quadratic latent causal model with additive noise as follows
2,
V ZT pa(t) A; Zpa(i) + N.
(155)
where {A, i [n]] are positive-definite matrices, and the noise terms are zero-mean Gaussian variables with variances of sampled randomly from 00.5 1.5)). For an intervention on node i, Z, is set to / This causal model admits a closed-form score function (see [7, Appendix E.2] for
27

---

details), which enables us to obtain score oracle. In our MN intervention setup, we use this score oracle and introduce varying levels of artificial noise according
(x (z) (1 =),
where E ~~ NO, o² -Iadd)
(156)
to test the behavior of our algorithm under different noise regimes a E [10-9,10-14 demonstrates the results for the latent graph recovery and latent variable recovery.
10-11.3. Figure
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Sections 3 and 4 establish the results claimed in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 to other settings.
It is fine to 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]
Justification: The limitations of the work, e.g., linear transformations, are clarified through- out the paper and discussed in Section 6.
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 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 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, e.g., if the approach was only tested on 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 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 to handle technical jargon.
The authors should discuss the computational efficiency of 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
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]

---

The assumptions for the theoretical results are clearly stated in the theorem statements, and the proofs of the results are provided in Appendix A.
Justification:
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The algorithm details are summarized in Algorithm 1, and described in Section 4. The experimental procedure and details of parameterization are described in Section 5 and Appendix B. The codebase for the experiments can be found at https:
//github. com/ acarturk-es eet-eeemmmrrllrllmeee-
Guidelines:
The answer NA means that the paper does not include experiments.
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 a dataset and/or model, the authors should describe the steps taken make their results reproducible 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 a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of 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 a 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 a 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- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
30

---

5. Open access to data and code
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?
Question:
Answer: [Yes]
Justification: The codebase for the experiments can be found https: :otps://Bet http::://ghhtbt com/ acarturk-ed haiikk/cmmmnrrr....
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
ceaibbmissiooooiccyy... for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for 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: / //iiss... wwwpcccppcc//aee.cc.ccccce.cetle ppubli/gguides....//ee//// /ttegguuiieeeooeuuuaiiiii /CodeSubmissiond ssiooolccyy 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).
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: The experimental procedure described Section 5, and detailed parameteri- zation is provided in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification:
The experiments in Table are reported for an average of 100 runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
31

---

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 a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is 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 of 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 text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Experiments are run on a single commercial CPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https : pettpa://neurs http///eeeripp.eeeee cc waabblic/Ethicchiiieii
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics and confirm that the research in this paper conforms with 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: This paper is mostly theoretical and does not pose potential negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
32

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess 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 tied to particular applications, let alone deployments. However, if there is 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 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 are 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 to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper is mostly theoretical and does not pose such risks.
Guidelines:
The answer NA means that the paper poses 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 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 challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. 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: [Yes]
Justification: Portions of the publicly available code of [7], available under Apache 2.0 license, are adopted the code our experiments.
Guidelines:
The answer NA means that the paper does 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 (e.g., website), the copyright and terms of service of that source should be provided.
33

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The codebase for the experiments be found https://github. com/ acarturk-e/ wateeeemmmmirrrreeeee and is released under Apache 2.0 license.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/mooel 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 is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not 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 much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, 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 the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending 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.
34

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS 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.
35


Reviews:
[{"review_id": "APqzS9xzbA", "reviewer": "Reviewer_GLEY", "summary": "This paper introduces new identifiability results for CRL in environments with unknown multi-node interventions. It shows that, with sufficiently diverse interventional environments, one can achieve identifiability up to ancestors using soft interventions and perfect identifiability using hard interventions. The paper also provides an algorithm with identifiability guarantees.", "questions": "How effectively does the proposed algorithm scale to more nodes and higher dimensions?", "limitations": "The paper acknowledges its main limitations in the reliance on linear transformations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper tackles the complex and underexplored multi-node intervention setting. The established identifiability can be crucial for extending current CRL theories into more practical contexts.\n- The introduced algorithm that leverages score functions with different interventional environments is also interesting and insightful.\n- The paper is well-motivated and articulated with high clarity.", "weaknesses": "- The proposed algorithm, while theoretically sound, seems computationally demanding. In fact, even a 4-node low-dimensional case requires a large number of environments and samples. The paper could benefit from a deeper discussion on the scalability of the algorithm.\n- The current evaluation of the algorithm is limited to synthetic simulations. Expanding it to more realistic datasets would substantively improve its practical significance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding our results crucial for extending CRL into more practical contexts, for finding our algorithm insightful, and for noting the clarity of the paper. We address the raised questions about the algorithm’s scalability as follows.\n \n-    **Dimension of $X$**: Our algorithm is readily scalable to arbitrarily high-dimensional observations $X$. Please see the additional experiments reported in our general response, in which we use $d=50$.\n \n-    **Dimension of $Z$**: Please see the additional experiments reported in our general response, in which we use $n \\in \\\\{4, 5, 6, 7, 8\\\\}$ latent nodes.\n \n-    **Number of environments**: We note that $n$ environments are *necessary* in general (without further structural assumptions) for identifiability via single-node interventions (shown by Squires et al. 2023, Proposition 5). Since our unknown multi-node intervention setting subsumes the single-node interventions, we require at least $n$ environments as well.\n\n-    **Number of samples**: We remark that the main purpose of our algorithm is to establish a framework for identifiability via multi-node interventions. In future work, we aim to address the efficient score difference estimation, which is a separate line of work that can significantly increase the efficiency of our framework. We also kindly note that, even in the much simpler single-node intervention setting, related CRL literature uses a similar number of samples to $10^5$ that we used in our experiments for good performance (e.g., $10^5$ samples for $n=5$ nodes in Squires et al. (2023), $5 \\times 10^4$ samples for $n=5$ nodes in Buchholz et al. (2023), and  $5 \\times 10^4$ samples for $n=5$ nodes in Varici et al. (2024)).\n \n-    **Toward realistic settings**: Finally, we acknowledge the need for working with more realistic datasets in the CRL field. We believe this paper serves as a significant step in this direction by removing the stringent assumption of single-node interventions, and we leave addressing realistic applications to future work.", "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": "fwEEZYb5am", "reviewer": "Reviewer_q4pN", "summary": "This paper extends previous results on using score function for causal representation learning to the settings with unknown multi-node interventions. This new setting poses significant new challenges as opposed to the single node intervention case. The author first present theoretical identifiability result on hard interventions with latent additive noise model and on soft interventions. They then propose an algorithm called (UMNI)-CRL and test it on synthetic linear Gaussian dataset.", "questions": "1. (UMNI)-CRL requires estimating the score function. How do you ensure a good estimate of the score function to unsure that the algorithm is useful in practice?\n2. One small question: on line 141-143, it is mentioned that if a node is not intervened on, perfect identifiability is not possible. But there are cases like A→B where I don’t need to intervene on A?", "limitations": "1. Theorem 1 only works for additive noise model.\n2. The transformation from latent to observed noiseless.\n3. Experiments are only on synthetic dataset. \n4. I am unsure if the algorithm is practical because it needs to estimate the score function.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is clearly written, easy to follow and with good motivations.", "weaknesses": "1. The transformation from latent to observed is noiseless, which could be a limitation. \n2. Line 199 says that: “This regularity condition ensures that the effect of a multi-node intervention is not the same on different nodes”. But how realistic or neccessary is this condition? It seems like it is very possible that an intervention can cause two downstream nodes to have the same effect although these two nodes is not influenced the same by all type of interventions. \n3. The experiments are only on synthetic dataset but I don’t think that is a big issue. \n4. Some potential missing citations\n    \n    [1] Kumar, Abhinav, and Gaurav Sinha. \"Disentangling mixtures of unknown causal interventions.\" *Uncertainty in Artificial Intelligence*. PMLR, 2021.\n    \n    [2] Jiang, Yibo, and Bryon Aragam. \"Learning nonparametric latent causal graphs with unknown interventions.\" *Advances in Neural Information Processing Systems* 36 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the challenges of the unknown multi-node intervention setting and noting the clarity of the paper. We address the raised concerns as follows.\n\n**Noiseless transformation:** The current scope of the paper cannot handle noisy transformations. We also kindly note that the closely related CRL literature (see references [3]-[10] in the paper) also considers deterministic transformations $X = g(Z)$. Our paper’s primary goal is to relax the restrictive assumption of single-node interventions. As such, we consider noisy transformations a major future direction.\n \n**Interventional regularity**: We thank the reviewer for raising the need for elaboration on the interventional regularity condition. We explain its rationale and emphasize that it is not a restrictive assumption as follows.\n \n- First, we want to clarify what we meant by \"effect of an intervention.” Essentially, $\\frac{\\partial}{\\partial z_j}\\log\\frac{p_i(z_i\\mid z_{{\\rm pa}(i)})}{q_i(z_i\\mid z_{{\\rm pa}(i)})}$ is the effect of intervening on node $i$ on the *score* associated with node $j$. Therefore, the effect in the score function is not on downstream nodes of $i$ but on the parents of $i$. \n \n- Note that we use *combinations* of different multi-node environments to generate new score difference functions. Therefore, to ensure that the effect of this new “combined” intervention will be different on the $i$-th and $j$-th coordinates of the score function, we require the ratio in Eq.(12) to be not constant.\n \n- Next, we emphasize that **interventional regularity is not a restrictive assumption**. In Appendix A.8., we present some sufficient conditions that make the interventional regularity valid (see Lemma 5). For instance, if we consider a linear latent causal model under a hard intervention and the distribution of the exogenous noise term remains the same after the intervention, then interventional regularity is satisfied. Therefore, interventional regularity is not a restrictive assumption.\n\n- Furthermore, note that if there exist $k\\in{\\rm pa}(j)\\setminus{\\rm pa}(i)$, then $\\log\\frac{p_j(z_j\\mid z_{{\\rm pa}(j)})}{q_j(z_j\\mid z_{{\\rm pa}(j)})}$ is a function of $Z_k$, whereas the other terms in Eq.(12) are not. This implies that the ratio in Eq.(12) is not a constant function of $Z$ and again exemplifies that the interventional regularity is not a restrictive condition.\n\n**Estimating score function differences:**\n-    Our algorithm is agnostic to the choice of score estimator, and we can adopt popular score-matching methods as mentioned in Line 325, e.g., Song et al. (2020) or Zhou et al. (2020). We also note that score function estimation is finding increasingly more applications in diffusion models, and it is an active research field. Hence, our algorithms can modularly adopt any new score estimation algorithm and benefit from advances in the score estimation literature.\n \n-    We also emphasize that our algorithm only requires **score differences** and does not require the score functions themselves. We conjecture that the direct estimation of score differences can be much more efficient than estimating the individual score functions, a lá direct estimation of precision difference matrices [R1]. Furthermore, density ratio estimation methods, e.g., classification-based approaches [R2], can be potentially useful for direct score difference estimation.\n \n[R1] Jiang, Wang, and Leng. \"A direct approach for sparse quadratic discriminant analysis.\" JMLR, 2018.\n \n[R2] Gutmann and Aapo Hyvärinen. \"Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics.\" JMLR, 2012.\n \n**Non-identifiability when missing an intervened node**: In lines 141-143, we meant that “when a node is not intervened on, perfect identifiability is not possible **in general**”, i.e., without imposing additional restrictions such as structural assumptions. Our reference for non-identifiability is Proposition 5 of Squires et al. (2023). Their proof for non-identifiability only requires that the non-intervened node $i$ has at least one parent. We will add this note to the updated manuscript.\n \nWe note that the example of $A\\rightarrow B$ under an intervention on only $B$ is also discussed by Remark 2 of Squires et al. (2023). Even though the graph $A\\rightarrow B$ can be discovered in this specific case, we are not aware of any results for the identifiability of the latent variables. Squires et al. (2023) empirically suggest that the latent variables are not identifiable.\n \n**Additive noise models (ANM)**: Please refer to our general response. \n\n**Additional references**: Thank you for the suggestions; we will include and discuss them in the paper. In summary, Jiang and Aragam (NeurIPS 2023) focus on recovering the latent DAG without recovering the latent variables as opposed to our complete CRL objectives. On the other hand, Kumar and Sinha (2021) focus on an entirely different setting in which the causal variables are observed, and the distributions are given in a mixture. In contrast, our CRL setting focuses on latent variables observed through the same transformation when observing distinct interventional distributions.", "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": "9KTqx3TsPE", "reviewer": "Reviewer_Vtz8", "summary": "This work studies interventional causal representation learning, where one has access to interventional data, to identify latent causal factors and latent DAG in the unknown multi-node interventions regime. The authors consider a setting where the mixing function is linear and the latent causal model is nonparametric. Under the assumption of sufficient interventional diversity, the authors use score function arguments to show that the underlying causal factors of variation (and DAG) can be recovered (1) up to permutation and scaling from stochastic hard interventions and (2) up to ancestors from soft interventions. The authors propose a score-based framework (UMNI-CRL) and evaluate it on synthetic data generated from Erdős–Rényi random graph model.", "questions": "- I would like some clarification on the intervention regularity condition. Specifically, why does the additional term ensure that multi-node interventions have a different effect on different nodes? It would be good to elaborate on this condition when introduced since it is a central assumption that needs to be satisfied for the results to hold.\n- How do you obtain $\\Lambda$ in Eq. (14)? It seems that this matrix encodes the summands with the latent space score differences. However, since the distribution of the latents is unknown, how would you go about estimating $\\Lambda$ and score differences $\\Delta S_X$ in general cases of nonparametric distributions?\n- How do you learn the integer-valued vectors $\\mathbf{w}$ in Stage 2 of the algorithm? From Eq (18), it seems that $\\mathcal{W}$ is a fixed predefined set and you choose the vectors $\\mathbf{w} \\in \\mathcal{W}$ that satisfy a specific condition in the algorithm. To my understanding, this is central to recovering the approximate unmixing $\\mathbf{H}^*$ up to a combination of the rows of the true unmixing $\\mathbf{G}^{\\dagger}$. I would appreciate it if the authors could elaborate on how this procedure was done.\n- From Appendix A.8, it seems that $\\kappa$ is determined by the number of causal variables $n$. Could the authors give some more intuition on what $\\kappa$ represents in Stage 2 with respect to how the unmixing is recovered?\n- Are there any distributional assumptions on the exogenous noise in the latent additive noise causal model?\n- It seems that the UMN hard intervention result (Theorem 1) requires a latent model with additive noise. Would perfect recovery still be possible for latent models with non-additive noise under UMN hard interventions?\n- The empirical results suggest that increasing sample size improves DAG recovery, which is intuitive. However, what do the results look like as the number of causal variables scales up? Currently, the authors only show results for n=4 latent causal variables. I only offer this as a suggestion due to the short rebuttal period.\n- How would the assumptions made need to change to be applied to general mixing functions? I know that generality in one aspect of the model (i.e., general SCM) may require other aspects to take some parametric form (i.e., linear mixing) for identifiability guarantees, but do the authors have any intuition on how to achieve identifiability results for the UMN setting in a completely nonparametric setup?", "limitations": "Limitations are discussed in Section 6.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This work provides significant results in the unknown multi-node intervention setting, which is much more realistic than the common single-node intervention regime. As opposed to other works, this work studies CRL from a more general class of multi-node interventions (stochastic hard and soft).\n- The paper is well-written, the concepts are explained well, and the theoretical identifiability results add a lot of value to the current CRL literature.\n- The use of score functions and score differences in the observation space to estimate the unmixing function, especially for the UMN setting, is a novel and interesting approach for CRL.\n- This work is the first to establish latent DAG recovery in the UMN setting under any type of multi-node intervention for arbitrary nonparametric latent causal models.", "weaknesses": "Although the theoretical contribution of this work is strong, the empirical evaluation is quite weak compared to other works in CRL. There are only experiments for n=4 causal variables. There is also no baseline comparison of the proposed framework with other methods in the UMN setting (e.g., [1]). Also, some discussions are a bit abridged and could use more elaboration in the paper (see below for details).\n\n[1] Bing et al. “Identifying Linearly-Mixed Causal Representations from Multi-Node Interventions” CLeaR 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging our strong theoretical and algorithmic contributions. We address the questions as follows.\n \n**Empirical results**:\n-   *Increasing $n$*: Thanks for the suggestion. Please refer to the general response for experiment results for up to $n=8$ nodes.\n-   *Baseline*: We note that Bing et al. use “do” interventions. Hence, the algorithms are not comparable.\n \n**Interventional regularity**: We explain the rationale and details as follows.\n \n- First, we emphasize that **interventional regularity is not a restrictive assumption**. In Appendix A.8.(Lemma 5), we present some sufficient conditions in which the interventional regularity holds. For instance, under a hard intervention on a linear causal model, if the distribution of the exogenous noise remains the same, then interventional regularity holds. Hence, it is not a restrictive assumption.\n\n- Next, we clarify what we mean by the *effect of an intervention*. Essentially, $\\frac{\\partial\\log p_i/q_i}{\\partial z_j}$ is the effect of intervening on node $i$ on the *score* associated with node $j$. Note that we use *combinations* of different multi-node environments to generate new score difference functions. Without the additional term in Eq.(12), $\\frac{\\partial\\log p_j/q_j}{\\partial z_j}$, the ratio in Eq.(11) considers only a single node intervention on $i$ and its effects on scores of $i$ and $j$.\n \n- To ensure that the effect of a *combined* intervention is different on scores of $i$ and $j$, we need to consider interventions on both $i$ and $j$. As such, the additional term in Eq.(12), $\\frac{\\partial\\log p_j/q_j}{\\partial z_j}$, denotes the effect of the additional intervention on $j$ on the node $j$. \n \n**Score function differences**:\n-   **We do not require estimating $\\Lambda$**. It is correct that $\\Lambda$ encodes score differences in latent space, and we cannot estimate it. Therefore, the algorithm **only** takes $\\Delta S_X$ as input. $\\Lambda$ is defined to provide intuition on the rationale of the algorithm and the connection between latent score differences and $\\Delta S_X$ in Eq.(17).\n \n-   Our algorithm is agnostic to the choice of score estimator, and we can adopt popular score-matching methods as mentioned in Line 325, e.g., Song et al. (2020) or Zhou et al. (2020). We also note that score function estimation is finding increasingly more applications in diffusion models, and it is an active research field. Hence, our algorithms can modularly adopt any new score estimation algorithm and benefit from advances in the score estimation literature.\n \n-   We also emphasize that our algorithm only requires **score differences** and does not require the score functions themselves. We expect that the direct estimation of score differences can be much more efficient than estimating the individual score functions, à la direct estimation of precision difference matrices [R1]. Furthermore, density ratio estimation methods, e.g., classification-based approaches [R2], can be potentially useful for direct score difference estimation.\n\n[R1] Jiang et al. A direct approach for sparse quadratic discriminant analysis. JMLR, 2018.\n \n[R2] Gutmann and Hyvärinen. Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics. JMLR, 2012.\n\n**Additive noise models (ANM)**: Please refer to our general response. \n\n**Stage 2 of the algorithm**: We elaborate on learning the vectors $\\bf w$ and the role of $\\kappa$ as follows.\n-   Note that $\\Delta S_X\\cdot\\bf w$ is essentially a combination of SN latent score differences via Eq.(15) and (17) (also shown in (30)). Also, since the score difference $\\nabla\\log p_i(z_i\\mid z_{{\\rm pa}(i)})-\\nabla\\log q_i(z_i\\mid z_{{\\rm pa}(i)})$ is a function of $Z_{{\\rm pa}(i)}$ and $Z_i$, the dimension of the image of this function will be 1 if and only if the intervened node $i$ has no parents.\n \n-   Leveraging this property, at the first step $t=1$, we search for a linear combination of the given MN environments (via $\\bf w$) to emulate a single node intervention on a root node. For such a vector $\\bf w$, using Eq.(15) and (17), the image of $\\Delta S_X\\cdot\\bf w$ contains only one vector (up to scaling), which is the encoder $\\bf G^\\dagger$’s row corresponding to the $i$-th node where $i$ is a root node.\n \n-   Subsequently, at each step, we follow the same routine to estimate a row of the true encoder. While checking the dimension of the emulated intervention, we project $\\Delta S_X\\cdot\\bf w$ to the nullspace of the submatrix recovered so far. This ensures that the learned encoder will be full-rank.\n \n-   **Role of $\\kappa$**: Vector ${\\bf w=[D^{-1}]}_i$ is a valid choice that makes $\\Delta S_X\\cdot\\bf w$ correspond to a single node intervention. Then, by constructing a set $\\cal W$ that contains the rows of $\\bf D^{-1}$, we ensure that the procedure described above will work by an exhaustive search over $\\cal W$. We note that the entries of $\\bf D^{-1}$ can be found via the cofactor matrix of $\\bf D$, for which the $\\kappa$ denotes the maximum possible entry. For detailed derivation, please refer to lines 479-490 in Appendix A.1.\n \n**Intuition for general mixing functions**: Our core technical idea is using combinations of MN interventions to construct new interventions with desired properties, e.g.,sparsity. Our intuition is that we can extend the intervention matrix in Eq.(4) to handle multiple interventional mechanisms. For instance, to represent two interventional mechanisms per node, the columns of the intervention matrix would be in $\\\\{0,1\\\\}^{2n}$. Subsequently, the goal is to find combinations of MN environments to create two different SN interventions for each node so that the problem simplifies to the known results for general transformations under two SN int/node (see references [6],[9]). However, building on this intuition to prove identifiability is challenging and is a major direction for future work.", "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": "95yHyFudZf", "reviewer": "Reviewer_NxzW", "summary": "This paper advances Causal Representation Learning (CRL) by addressing the challenge of using unknown multi-node (UMN) interventions to identify latent causal variables and their structures.  The authors develop a score-based CRL algorithm that leverages UMN interventions to guarantee identifiability of latent variables and their causal graphs under both hard and soft interventions, achieving perfect identifiability with hard interventions and identifiability up to ancestors with soft interventions. Their method outperforms existing single-node approaches by ensuring robust recovery of causal structures in more complex, multi-intervention environments.", "questions": "* Can you please elaborate on the computational complexity and on why it is dominated by step 2?\n\n* Can you please discuss the applicability of the assumptions in real scenarios?\n\n* I think that adding some real world application can increase the impact of this paper. Is it possible to find such an application?", "limitations": "The paper acknowledges certain limitation. One notable limitation is the assumption of linear transformations in the causal models considered. This restricts the applicability to scenarios where causal relationships are adequately approximated by linear relationships. Additionally, while the paper addresses the challenge of UMN interventions, it acknowledges the complexity involved in identifying intervention targets in such settings, which can affect the ability to fully leverage the statistical diversity inherent in UMN interventions.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Extending the causal representation learning to unknown multi-node interventions\n\n* Proofs are provided \n\n* Pseudocode is provided\n\n* Computational complexity is discussed\n\n* Limitations are clearly stated", "weaknesses": "* The paper primarily focuses on causal models with linear transformations. This limits its applicability in many real scenarios\n\n* The applicability of the assumptions in real scenarios was not discussed\n\n* The method was not applied on real world-data", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful review and accurate summary. We address the questions as follows.\n \n**Computational complexity**: Stage 1 (score difference estimation) is only performed once before the main algorithm starts. Stage 4 (unmixing procedure for hard interventions) essentially works as a post-processing step that does not pose computational challenges. Below, we elaborate on the computational complexity of Stage 2 and Stage 3.\n \n-   *Stage 2*: We check dimension of $\\mathcal{V}$ (line 6 of the algorithm) at worst $n \\times (2 \\kappa + 1)^n$ times in Stage 2 of the algorithm. Here, $\\kappa$ denotes the maximum possible determinant of a matrix $\\\\{0,1\\\\}^{(n-1) \\times (n-1)}$. In the proof of Lemma 2 in Appendix A.1, we discuss why this choice facilitates the identifiability guarantees. We also discuss how $\\kappa$ grows with $n$ in Appendix A.8, and give special cases, such as sparse multi-node interventions, in which $\\kappa$ is upper bounded by small numbers even for large $n$ values.\n \n-   *Stage 3*: Here, we check dimension of $\\mathcal{V}$ (line 23 of the algorithm) at worst $\\\\|\\mathbf{W}\\_{:,j}\\\\|_1 \\times \\\\|\\mathbf{W}\\_{:,t}\\\\|_1$ times for every $(t,j)$ in Stage 3 of the algorithm. Note that $\\mathbf{W}$ is updated within the steps of Stage 3. Therefore, the exact computational complexity would be a function of the graph structure, and the outputs of Stage 2.\n \n-   *Empirical tricks*: Finally, we note two empirical tricks that can reduce the computational complexity greatly. First, even though $\\kappa$ can grow quickly as $n$ becomes larger, in practice, setting $\\kappa=2$ usually works fine (see additional experiment results in the general response). Second, additional empirical tricks can greatly increase the speed of the algorithm, e.g., dividing the columns of $\\mathbf{W}$ by the greatest common divisor of its entries after every step. Since our focus is on establishing the identifiability results, we omit the investigation of empirical tricks that would disturb the flow of the paper and distract from the main focus.\n \n \n**Toward realistic settings**: We believe this paper serves as a significant step in this direction by removing the stringent assumption of single-node interventions. For instance, genomics datasets such as Perturb-seq (Norman et al. 2019) are used by single-node interventional CRL (Zhang et al. 2023). However, the genomic interventions are known to have unknown off-target effects (Fu et al. 2013, Squires et al. 2020) that violate the single-node intervention assumption. Therefore, establishing unknown multi-node interventional results is fundamental to unlocking the use of CRL in realistic datasets. The implementation of real applications is beyond the scope of this work and is an important future direction.\n \n**References**\n \nT. M. Norman, M. A. Horlbeck, J. M. Replogle, A. Y. Ge, A. Xu, M. Jost, L. A. Gilbert, and J. S. Weissman. Exploring genetic interaction manifolds constructed from rich single-cell phenotypes. Science, 365(6455):786–793, 2019.\n \nJ. Zhang, C. Squires, K. Greenewald, A. Srivastava, K. Shanmugam, and C. Uhler. Identifiability guarantees for causal disentanglement from soft interventions. NeurIPS 2023\n \nY. Fu, J. A. Foden, C. Khayter, M. L. Maeder, D. Reyon, J. K. Joung, and J. D. Sander, “High frequency off-target mutagenesis induced by CRISPR-Cas nucleases in human cells,” Nature Biotechnology, vol. 31, no. 9, pp. 822–826, 2013\n \nC. Squires, Y. Wang, and C. Uhler. Permutation-based causal structure learning with unknown intervention targets. UAI 2020", "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": "aXPSL6PhGh", "reviewer": "Reviewer_8PAL", "summary": "This paper studies identifiability under unknown muilti-node  interventions (soft/hard), with general models (parametrtic/nonparametric) and **linear** mixing functions. This work provides both detailed proof which justifies the main theoretical statement, and a step-by-step algorithm which guides how to achieve identifiability in practice.\nOverall, I find this work serves as an important step for interventional CRL towards more realistic settings.\n\n&nbsp;\n\n### References\n\n[1] Burak Varıcı, Emre Acartürk, Karthikeyan Shanmugam, Abhishek Kumar, and Ali Tajer. Score- based causal representation learning with interventions. arXiv:2301.08230, 2023.\n\n[2] Burak Varıcı, Emre Acartürk, Karthikeyan Shanmugam, Abhishek Kumar, and Ali Tajer. Score- based causal representation learning: Linear and general transformations. arXiv:2402.00849, 2024.\n\n[3] Julius von Kügelgen, Michel Besserve, Wendong Liang, Luigi Gresele, Armin Kekic ́, Elias Bareinboim, David M Blei, and Bernhard Schölkopf. Nonparametric identifiability of causal rep- resentations from unknown interventions. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2023.", "questions": "See the first point in **weakness** section. I am very happy to raise my rating if this issue is resolved.", "limitations": "The authors discussed the remaining open problems and limitations in Section 6.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper is extremely well written and clearly structured: it communicates clearly motivations, formulation, technical details, and theoretical implications. The experimental results adequately validate the theory in case of a linear causal model.", "weaknesses": "1. The proposed UMNI-CRL algorithm is claimed to work with *general* non-parametric causal models; however, the simulation experiment only showed results on *linear* structural equation model.  It would be great if the authors could report further experimental results on non-parametric causal models, to align with the theoretical claims. If there is a valid reason why it cannot be done, I am also very happy to hear.\n\n2. Following the previous point, since this approach requires density estimation, it might not be scalable on nonparametric models. But to be fair, this seems to be a common limitation in many interventional CRL works [1, 2, 3].\n\n3. Linearity assumption on the mixing function is restrictive, but the authors have acknowledged it and discussed possible future directions to overcome this limitation (sec. 6).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding our results an important step towards more realistic CRL settings and noting the clarity of the paper.\n \n**General causal models**:\nWe did not provide results using non-linear causal models since our algorithm, due to its combinatorial nature, is sensitive to input noise. While we are actively trying to make our algorithms work better using generic score estimators, for this response, in the interest of time, we have elected to provide a complementary analysis, where we investigate the performance of our algorithms under different levels of artificially introduced noise.\n\nFor this set of experiments, we adopt a non-linear additive noise model with a score oracle. Specifically, the observational mechanism for node $i$ is generated according to\n\n\\begin{align}\nZ_i = \\sqrt{Z\\_{{\\rm pa}(i)}^\\top {\\bf A}_i Z\\_{{\\rm pa}(i)}} + N_i \\ , \n\\end{align}\n\nwhere $N_i \\sim {\\cal N}(0, \\sigma_i)$, and the interventional mechanisms set $Z_i = N_i / 2$. This causal model admits a closed-form score function (see [7, Eq.(393–395]), which enables us to obtain a score oracle. In our experiments, we use this score oracle and introduce varying levels of artificial noise according to\n\n\\begin{align}\n\\hat{s}_X(x; \\sigma^2) = s_X(x) \\cdot \\big( 1 + \\Xi \\big) \\ , \\quad \\mbox{where} \\quad \\Xi \\sim {\\cal N}(0, \\sigma^2 \\cdot {\\bf I}\\_{d \\times d}) \\ ,\n\\end{align}\n\nto test the behavior of our algorithm under different noise regimes ($\\sigma \\in [10^{-3}, 10^{-1.5}]$). Results à la Table 2 versus different $\\sigma$ values are provided in Figure 1 in the PDF document attached to the general response.\n \n**Score estimation**: We kindly note three things regarding the score functions on nonparametric models. \n\n- Our algorithm is agnostic to the choice of score estimator, and we can adopt popular score-matching methods as mentioned in Line 325, e.g., Song et al. (2020) or Zhou et al. (2020). We also note that score function estimation is finding increasingly more applications in diffusion models, and it is an active research field. Hence, our algorithms can modularly adopt any new score estimation algorithm and benefit from advances in the score estimation literature.\n\n- *Score vs. density estimation*: We also note that score estimation in a high-dimensional setting is generally easier than density estimation, as it avoids the difficulty of finding the normalizing constants.\n\n\n- Finally, we emphasize that our algorithm only requires **score differences** and does not require the score functions themselves. We conjecture that the direct estimation of score differences can be much more efficient than estimating the individual score functions, a lá direct estimation of precision difference matrices [R1]. Furthermore, density ratio estimation methods, e.g., classification-based approaches [R2], can be potentially useful for direct score difference estimation.\n  \n[R1] Jiang, Wang, and Leng. \"A direct approach for sparse quadratic discriminant analysis.\" JMLR, 2018.\n\n[R2] Gutmann and Aapo Hyvärinen. \"Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics.\" JMLR, 2012.", "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:
We thank all the reviewers for their thorough feedback and thoughtful questions. Below we address some shared questions by the reviewers.

### **Additional experiments**
We address the shared concerns of the reviewers regarding the scalability of the algorithm via the following additional experiment results.
 
**Setting**: We follow the same setting as in Section 5 of the paper; Erdös-Rényi model with density 0.5 and linear structural equation models (SEMs) with Gaussian noise.
- **Dimension of observed variables $X$**: We increase $d$ to $50$ in this additional experiments.
- **Number of latent nodes**: We perform experiments for $n \in \\{4,5,6,7,8\\}$ nodes. We also note that $n=8$ is the largest graph size considered in the closely related single-node interventional CRL literature (e.g., Squires et al. (2023) and Buchholz et al. (2023) consider 5 nodes, Varici et al. (2024) consider 8 nodes, von Kügelgen et al. (2023) consider 2 nodes).
- We use $n_{\rm s} = 10^5$ samples for each realization and repeat the experiments 100 times for each $(n,d)$ pair.

The table below shows that the average rate of incorrect mixing entries, captured by $\ell_{\rm soft}$ and $\ell_{\rm hard}$, remains low for increasing values of $n$. Graph recovery metric SHD increases with $n$, since the number of expected edges also increases with $n$ under a fixed edge density.
 
|    $n$   |    $d$    |  SHD (Soft)  | $\ell_{\rm soft}$ |  SHD (Hard) | $\ell_{\rm hard}$ |
|:--------:|:---------:|:------------:|:-----------------:|:-----------:|:-----------------:|
|     4    |     50    |      0.44    |        0.72       |     0.04    |        0.11       |
|     5    |     50    |      0.96    |        1.25       |     0.05    |        0.10       |
|     6    |     50    |      2.41    |        3.20       |     0.09    |        0.14       |
|     7    |     50    |      4.22    |        6.00       |     0.11    |        0.16       |
|     8    |     50    |      5.67    |        8.75       |     0.10    |        0.16       |
 
**Empirical trick**: We recall that our algorithm involves searching for proper $\mathbf{w} \in \\{-\kappa,\dots,\kappa\\}^n$ vectors in which $\kappa$ denotes $\kappa$ denotes the maximum determinant of a matrix in $\\{0,1\\}^{(n-1) \times (n-1)}$. Even though $\kappa$ is a function of $n$, e.g., $\kappa=2$ for $n=4$ and $\kappa=5$ for $n=6$, we observe that setting $\kappa=2$ does not disturb the performance noticeably. Therefore, we set $\kappa=2$ in all our experiments to reduce runtime.

### **General causal models**
In addition to our experiments with linear causal models, we investigate general causal models. Specifically, we provide a sensitivity analysis where we investigate the performance of our algorithms under different levels of artificially introduced noise.

For this set of experiments, we adopt a non-linear additive noise model with a score oracle. Specifically, the observational mechanism for node $i$ is generated according to
$$Z_i = \sqrt{Z\_{{\rm pa}(i)}^\top {\bf A}_i Z\_{{\rm pa}(i)}} + N_i \ ,$$
where $N_i \sim {\cal N}(0, \sigma_i)$, and the interventional mechanisms set $Z_i = N_i / 2$. This causal model admits a closed-form score function (see [7, Eq.(393–395]), which enables us to obtain a score oracle. In our experiments, we use this score oracle and introduce varying levels of artificial noise according to
$$\hat{s}_X(x; \sigma^2) = s_X(x) \cdot \big( 1 + \Xi \big) \ , \quad \mbox{where} \quad \Xi \sim {\cal N}(0, \sigma^2 \cdot {\bf I}\_{d \times d}) \ ,$$
to test the behavior of our algorithm under different noise regimes ($\sigma \in [10^{-3}, 10^{-1.5}]$). Results à la Table 2 versus different $\sigma$ values are provided in Figure 1 in the PDF document attached to the general response.


### **Additive noise models (ANM)**
 -   We emphasize that the core component of our work – minimizing score differences to estimate the true encoder – does not require ANMs, as shown by Theorem 2 for soft interventions.
-   ANM is introduced for the analysis of CI tests in Stage 4 (hard interventions). Specifically, given a different causal model, it may be possible to analyze Stage 4 of the algorithm in a different way. For simplicity, we have adopted ANMs which are commonly adopted by both causal discovery and CRL literature (e.g., for perfect identifiability, Squires et al. (2023), Buchholz et al. (2023), Varici et al. (2024), and Bing et al. (2024) use ANMs).
-   Finally, we only require the exogenous noise in the ANM to have full support, which is already implied by the full support of $z$. Hence, we don’t make any specific assumptions for ANM.

Meta-review: This paper develops new results for multi-node causal representation learning, which is an important open direction for the field. All reviewers are in favor of acceptance. Clear accept.
Decision: Accept (poster)