Linear Causal Representation Learning from Unknown Multi-node Interventions

Authors: burak  varıcı
emre  acartürk
karthikeyan  shanmugam
google  deepmind
ali  tajer
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 03:31:14

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.

Main paper: 
 introduction: 
 Causal representation learning (CRL) is a major leap in causal inference, moving away from the conventional objective of discovering causal relationships among a 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 in a wide range of applications, a lower-dimensional latent set of variables with causal interactions generates the usually high-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 a set of latent causal random variables Z ∈ R n and a 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 X ∈ R d , 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 G can be recovered, and achievability, which refers to designing CRL algorithms that can achieve the foreseen identifiability guarantees. Identifiability has been demonstrated to be inherently under-constrained [2] , prompting the development of diverse methodologies that incorporate inductive biases to enable identifiability. Interventional CRL is one direction with significant recent advances in which interventions on latent causal variables are used to create statistical diversity in the observed data [1, [3] [4] [5] [6] .Unknown multi-node interventions. 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 singlenode, i.e., exactly one latent variable is intervened in each environment [3] [4] [5] [6] [7] [8] [9] [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-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.In this paper, we address the open problem of using unknown multi-node (UMN) stochastic interventions 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 transformation 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 interventions 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 provable guarantees. These guarantees also serve as constructive proof steps of the identifiability results.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. An immediate impact of this is that it becomes more challenging to properly capitalize on the 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 is more accessible.Single-node interventional CRL. The majority of the studies on interventional CRL focus on SN interventions [3] [4] [5] [6] [7] [8] [9] [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 transformations (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 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 to 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 partial identifiability or focus on non-stochastic do interventions. The study in [14] focuses on linear non-Gaussian latent models and linear transformations and uses soft interventions to establish identifiability up to 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. Distinct from all these studies, we address the open problem of perfect identifiability under UMN stochastic interventions.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] [19] [20] [21] , leveraging temporal sequences [22, 23] , building on nonlinear independent component analysis (ICA) principles to identify polynomial latent causal models [24] , and imposing sparsity constraints to obtain partial disentanglement [25, 26] . We refer to [27] for a detailed literature review on various CRL problems. 
crl setting and preliminaries: 
 Notations. Vectors are represented by lowercase bold letters, and element i of vector a is denoted by a i . Matrices are represented by uppercase bold letters, and we denote row i and column j of matrix A by A i and by A :,j , respectively, and A i,j denotes the entry at row i and column j.We use null({A 1 , . . . , A r }) to denote the nullspace of the matrix consisting of the row vectors {A 1 , . . . , A r }. For n ∈ N, we define [n] ≜ {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(f ) to denote the image of a function f and dim(V) to denote the dimension of a subspace V. Random variables and their realizations are presented by upper and lower case letters, respectively.Consider a latent causal space consisting of n causal random variables Z ≜ [Z 1 , . . . , Z n ] ⊤ . An unknown linear transformation G ∈ R d×n maps Z to the observed random variables denoted by X ≜ [X 1 , . . . , X d ] ⊤ according to:EQUATIONwhere d ≥ n and G is full rank. The probability density functions (pdfs) of X and Z are denoted by p X and p Z , respectively. We assume that p Z has full support on R n . Subsequently, p X is supported on X ≜ im(G). The causal relationships among latent variables Z are represented by a DAG G in which the i-th node corresponds to Z i . Hence, p Z factorizes according to:EQUATIONwhere pa(i) denotes the set of parents of node i in G. The conditional pdfs {p i (z i | z pa(i) ) : i ∈ [n]} are assumed to be continuously differentiable with respect to all z variables. We use ch(i), an(i), and de(i) to denote the children, ancestors, and descendants of node i, respectively. We say that a permutation (π 1 , . . . , π n ) of [n] is a valid causal order if the membership π i ∈ an(π j ) indicates that i < j. Without loss of generality, we assume that (1, . . . , n) is a valid causal order. We will specialize some of our results for the latent causal models with additive noise1 specified byEQUATIONwhere functions {f i : i ∈ [n]} capture the causal dependence of node i on its parents and the terms {N i : i ∈ [n]} represent the exogenous noise variables.In addition to the observational environment, we have M UMN interventional environments denoted by {E m : m ∈ [M ]}. We assume that the set of nodes intervened in each environment is unknown, and denote the set intervened in environment E m by I m ⊆ [n]. Accordingly, we define the intervention signature matrix D int ∈ {0, 1} n×M to compactly represent the intervention targets under various environments asEQUATIONThe m-th column of D int lists the indices of the nodes intervened in environment E m , which we refer to as the intervention vector of environment E m . Ensuring identifiability inevitably imposes restrictions on the structure of D int . For instance, if the i-th row of D int is a zero vector, it means that node i is not intervened in any environment, then the perfect identifiability is not possible [4] 2 . Therefore, to avoid such impossibility cases, we impose the mild condition that D int has sufficiently diverse columns, formalized next. Assumption 1. Intervention signature matrix D int defined in (4) is 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.A soft intervention on node i alters the observational causal mechanism p i (z i | z pa(i) ) to an interventional causal mechanism q i (z i | z pa(i) ). Such a change occurs in node i in all the environments E m that contain node i, i.e., i ∈ I m . Subsequently, the pdf of the latent variables in environment E m , denoted by p m Z , factorizes according to:EQUATIONHard 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 i (z i | z pa(i) ) is changed to an interventional causal mechanism q i (z i ), independent of parents of node i.To distinguish the observational and interventional data, we denote the latent and observed random variables in environment E m by Z m and X m , respectively. We note that interventions do not affect the transformation G. Hence, in E m we haveX m = G • Z m 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 Z m and X m byEQUATIONNote that, using the factorization in (5) , s m Z decomposes asEQUATIONWe denote the difference in score functions between interventional and observational environments byEQUATIONIn CRL, we use observed variables X to recover the true latent variables Z and the latent causal graph G. We denote a generic estimator of Z given X by Ẑ(X) : R d → R n . We also consider a generic estimate of G denoted by Ĝ. To assess the fidelity of the estimates Ẑ(X) and Ĝ with respect to the ground truth Z and G, we provide the following well-known identifiability measures.Definition 1 (Identifiability). For CRL under linear transformations, we define:1. Perfect identifiability: Ĝ and G are isomorphic, and the estimator Ẑ(X) satisfies thatEQUATIONwhere C s ∈ R n×n is a constant diagonal matrix with nonzero diagonal entries and P π is a row permutation matrix.2. Identifiability up to ancestors: Ĝ and transitive closure of G, denoted by G tc , are isomorphic, and the estimator Ẑ(X) satisfies thatEQUATIONwhere C an ∈ R n×n is a constant matrix with nonzero diagonal entries that satisfies [C an ] i,j = 0 for all j / ∈ {an(i) ∪ {i}}, and P π is a row permutation matrix.In the algorithm we will design, estimating Ẑ(X) and Ĝ are facilitated by estimating the inverse of the transformation G, that is Moore-Penrose inverseG † ≜ [G ⊤ • G] -1 • G ⊤, which we refer to as the true encoder. To formalize the process of estimating the true encoder, we define H as the set of candidate encoders specified byH ≜ {H ∈ R n×d : rank(H) = n and H ⊤ • H • X = X , ∀X ∈ X }.Corresponding to any pair of observation X and valid encoder H ∈ H, we define Ẑ(X; H) as an auxiliary estimate of Z generated as Ẑ(X; H)≜ H • X = (H • G) • Z.* ] t ∈ span({[G † ] πj : j ∈ [t]}) 
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 to all the existing identifiability results from SN interventions, it is necessary to have sufficient statistical diversity created by the intervention models. 3 These conditions can be generally presented in the form of regularity conditions on the probability distributions. Specifically, a commonly adopted regularity condition (or its variations) in the SN intervention setting is that for every possible pair (i, j) where i ∈ [n], j ∈ pa(i), the following term cannot be a constant function in z,EQUATION)We present a counterpart of these conditions for UMN interventions, which involves one additional term to account for the effect of intervening on multiple nodes simultaneously.Definition 2 (Intervention regularity). We say that an interventions are regular if for every possible triplet (i, j, c) where i ∈ [n], j ∈ pa(i) and c ∈ Q, the following ratio cannot be a constant function in zEQUATIONEssentially, ∂ ∂zj log pi(zi|z pa(i) )qi(zi|z pa(i) ) captures the effect of intervening on node i on the score associated with node j. In our method, we will use combinations of score differences of multi-node environments. This regularity condition ensures that the effect of a multi-node intervention is not the same on the scores associated with different nodes. Given these properties, we establish perfect identifiability for CRL with linear transformations using UMN stochastic hard interventions.  
umn interventional crl algorithm: 
 In this section, we design the Unknown Multi-node Interventional (UMNI)-CRL 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 interventional 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. for w ∈ W do ▷ W is specified in (18) 6:V ← proj null({H * i : i ∈ [t-1]}) im(∆S X • w) 7: if dim(V) = 1 then 8: pick v ∈ im(∆S X • w) \ span({H * i : i ∈ [t -1]})9: H * t ← v/M t,j ← [j -1] \ { ĉh(t) ∪ {t}} 20: for (α, β) ∈ {-(∥W :,j ∥ 1 , . . . , ∥W :,j ∥ 1 )} × [∥W :,t ∥ 1 ] do 21: w * ← α[W] :,t + β[W] :,j 22: V ← proj null({H * i : i ∈ Mt,j }) im(∆S X • w * ) 23: if dim(V) = 1 then 24: pick v ∈ im(∆S X • w * ) \ span({H * i : i ∈ M t,j })25: H * j ← v/u obs ← -Cov( Ẑt , Ẑ ân(t) ) • [Cov( Ẑ ân(t) )] -1 35:for m ∈ {i : W i,t ̸ = 0} do ▷ searching for a suitable environment 36:Ẑm ← Ẑm (X; H * ) 37:u m ← -Cov( Ẑm t , Ẑm ân(t) ) • [Cov( Ẑm ân(t) )] -1 38: if (u m • Ẑm ân(t) + Ẑm t ) ⊥ ⊥ Ẑm ân(t)and u m ̸ = u obs then 39:H * t ← H * t + u m • H * ân(t)▷ removing the effect of the ancestors on Z t 40:break 41: Ẑ ← Ẑ(X; H * ) ▷ use(x) = [G † ] ⊤ • s Z (z), where x = G • z.Using Lemma 1 for the scores and score differences defined in ( 7) and ( 8), respectively, we haveEQUATION)We compactly represent the summands in the right-hand side of ( 13) by defining the matrix-valued function Λ : R n → R n×n with the entriesEQUATIONbased on which ( 13) can be restated asEQUATIONWe note that [Λ(z)] i,j is constantly zero for i / ∈ {pa(j) ∪ {j}}, and j-th column of Λ is a function of the variables in {z k : k ∈ pa(j) ∪ {j}} which implies that the columns of Λ are linearly independent. Throughout the rest of the paper, we omit the arguments of the functions ∆s m X and Λ when the dependence is clear from the context. Note that D int has n linearly independent columns (Assumption 1). Denote the indices of the independent columns by {b 1 , . . . , b n } and define the basis intervention matrix D ∈ R n×n using these columns asEQUATIONSubsequently, it can be readily verified that the score difference functions {∆s m X : m ∈ {b 1 , . . . , b n }} are also linearly independent by leveraging (15) and linearly independent columns of Λ. Hence, these score difference functions are sufficient to reconstruct the remaining unavailable score difference functions. As such, {∆s m X : m ∈ {b 1 , . . . , b n }} serve as basis score difference functions. We stack these basis score differences, where each is a d-dimensional vector, to construct the matrix-valued function ∆S X : X → R d×n , which is used as the basis score difference matrix in the subsequent stages.∆S X ≜ ∆s b1 X , . . . ,EQUATIONFinally, we note that ∆S X is directly estimated from samples of X via learning {∆s bm X : m ∈ [n]}. Since Λ 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.Stage 2: Identifiability up to an unknown causal order. We design a process that aggregates score differences of the UMN interventions and obtains a 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 ∆S X such that those aggregate scores facilitate identifiability up to an unknown causal order. Such mixing of the columns is facilitated by computing ∆S X • W, where the mixing matrix W ∈ R n×n should be learned. Given the decomposition of ∆S X 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 ∆S X . This ensures identifiability up to an unknown causal order since rows of H * will be equal to combinations of rows of G † 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-valued vector w such that the projection of im(S X • w) onto the nullspace of the partially recovered encoder estimate becomes a one-dimensional subspace. To see why this procedure works, note that the function S X • w is essentially a combination of SN latent score differences via (17) , and the SN score difference∇ log p i (z i | z pa(i) ) -∇ log q i (z i | z pa(i) )is a one-dimensional subspace if and only if the intervened node i has no parents. By taking the projection of the im(∆ • w) onto the nullspace of partially learned 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 κ to denote maximum determinant of a matrix in {0, 1} (n-1)×(n-1) , and show that the setEQUATIONis guaranteed to contain such w vectors. The following result summarizes the guarantees of this procedure.Lemma 2. Under Assumption 1 and intervention regularity, outputs of Stage 2 of Algorithm 1 satisfy:1. D • W has nonzero diagonal entries and is upper triangular up to a row permutation. 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 O((2κ) n ) 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. 
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 4 .Data generation. To generate G, we use Erdős-Rényi model with density 0.5 and n ∈ {4, 5, 6, 7, 8} nodes. For the causal models, we adopt linear structural equation models (SEMs) with Gaussian noise. The nonzero edge weights of the linear SEMs are sampled from Unif(±[0.5, 1.5]), and the noise terms are zero-mean Gaussian variables with variances σ 2 i sampled from Unif([0.5, 1.5]). For a soft intervention on node i, the edge weight vector of node i is reduced by a factor of 1/2, and for a hard intervention, the edge weights are set to zero. The variance of the noise term is reduced to σ 2 i /4 in both intervention types. We consider target dimensions d ∈ {10, 50}, generate 100 latent graphs for each (n, d) pair, and generate n s = 10 5 samples of Z from each environment. Transformation Score functions. The algorithm uses score differences between environment pairs. Since we use a linear Gaussian model, X is also multivariate Gaussian, and its score function can be estimated by s X (x) = -Θ • 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 [28, 29] .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 tc 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 we set the density of random graphs to 0.5. Hence, the increasing SHD is also unsurprising when the latent dimension n increases from 4 to 8, and the performance remains reasonable at n = 8. Finally, we note that n = 8 is the largest latent graph size considered among the closely related SN intervention studies [4, 8, 7, 9] .Latent variable recovery. The estimates are given by Ẑ(X; 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 s and C an according to Definition 1, denoted byEQUATIONEQUATIONWe also report the mean correlation coefficient (MCC) [30] , 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.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes]Justification: The codebase for the experiments can be found at https://github.com/ acarturk-e/umni-crl.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
discussion: 
 In this paper, we established novel identifiability results using unknown multi-node (UMN) interventions for CRL under linear transformations. Specifically, we designed the provably correct UMNI-CRL algorithm, leveraging the structural properties of score functions across different environments. We start this section by introducing the additional notations used in the subsequent proofs.Additional notations. We use {e i : i ∈ [n]} to denote n-dimensional standard unit basis vectors. For a set S ∈ [n], we use A S to denote the submatrix of A constructed by the rows {A i : i ∈ S}.For a valid encoder H ∈ H, we denote the score functions associated with the pdfs of Ẑ(X; H) under environments E 0 and E m by s Ẑ (•; H) and s m Ẑ (•; H) for all m ∈ [M ]. In addition to the graph notations introduced in Section 2.1, we defineEQUATIONNext, we provide an auxiliary result that will be used throughout the proofs of the main results.Lemma 3. For every pair (i, j) where i ∈ [n] and j ∈ pa(i), the following ratio function cannot be a constant in zEQUATIONFurthermore, the columns of Λ are linearly independent vector-valued functions.Proof: See Appendix A.5. □We also restate the interventional regularity in terms of the Λ function defined in (14) , which will help clarity in the subsequent proofs.We say that an intervention on node i is regular if for every possible triplet (i, j, c) where i ∈ [n], j ∈ pa(i) and c ∈ Q, the following ratio cannot be a constant function in zEQUATION)By definition of Λ, this means that for (i, j, c) where i ∈ [n], j ∈ pa(i) and c ∈ Q, the following ratio cannot be a constant function in zEQUATIONA.1 Proof of Lemma 2First, we show that the search space in Stage 1 of Algorithm 1, i.e., the set W, has a certain property that will be needed for the rest of the proof. Recall the definition in ( 18)EQUATIONin which κ denotes the maximum possible determinant of a matrix in {0, 1} (n-1)×(n-1) . We will show that for all i ∈ [n], there exists w ∈ W such that 1([D • w] ̸ = 0) = e i . Let adj(D) be the cofactor matrix of D, which is the matrix formed by the entriesEQUATIONwhere [D] -i,-j is the first minor of D with i-th row and j-th columns are removed. Then, the inverse of D is given byEQUATIONBy multiplying both sides from left by D and rearranging we obtainEQUATIONwhere all matrices are integer-valued and I n×n denotes the n-dimensional identity matrix. The identity in (27) implies thatEQUATIONSince entries of adj(D) are upper bounded by κ, we have w * ∈ W and we conclude thatEQUATIONNext, we prove the lemma statements by induction as follows.Base case. At the base case t = 1, we will show that 1([D•W] :,1 ̸ = 0) = e i and H * 1 ∈ span([G † ] i )for some root node i. Consider a vector w ∈ W and denote c = D • w. Then, using (17) ,EQUATION)In the base case, we investigate the dimension of im(∆S X • w). Then, using (30), we haveEQUATION(29) implies that there exists w * ∈ W that makes 1(c ̸ = 0) = e i . Subsequently, if i is a root node, only nonzero entry of the column Λ :,i is Λ i,i and we haveEQUATIONHence, by searching w within W, Algorithm 1 is guaranteed to find a vector w such that dim(im(Λ • c)) = 1. Next, we show that if dim(im(Λ • c)) = 1, then 1(c ̸ = 0) = e i for a root node i. We prove this as follows. Consider the set A = {i : c i ̸ = 0} and let i be the youngest node in A, i.e., i has no Base case. At the base case, we have t = n -1 and j = n. We will show that, at the end of step(t, j) = (n -1, n), [D • W] πn-1,n ̸ = 0 implies that π n-1 ∈ pa(π n ).By Lemma 2, we know that [D • W] πn-1,n-1 ̸ = 0 , [D • W] πn,n ̸ = 0 ,EQUATIONThen, we haveEQUATIONSubsequently,EQUATIONNote that in the last step, we have used the fact that π is a causal order and j / ∈ pa(i) implies that Λ i,j = 0. Then, if π n-1 ∈ pa(π n ), interventional regularity ensures that the ratio of the two entries in (62) is not a constant function which implies that dim(EQUATIONdue to Lemma 3. Therefore, if w * satisfiesEQUATIONby setting [W] :,n = w * , we guarantee thatEQUATIONNote that the entries of [D • W] are bounded asEQUATIONHence, Algorithm 1 is guaranteed to find c * πn-1 = 0 by searching overEQUATIONTherefore, if dim(V) is never found to be 1 for any (α, β), it means that π n-1 ∈ pa(π n ), 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 ∈ {k + 1, . . . , n} and j ∈ {t + 1, . . . , n},EQUATIONWe will prove that (68) holds for t = k and j ∈ {t + 1, . . . , n}. We prove this by induction as well.Base case for the inner induction. At the base case, we have t = k and j = k + 1. Since π is a causal order, we have EQUATIONEQUATIONThen, we haveEQUATIONUsing (68), c * πi = 0 for i > k + 1. Subsequently,EQUATION)Also, recall that Λ π k ,πj = 0 for all j < k. Then,EQUATION)Using (68) again, we have c * π k+1 ̸ = 0. Then, if π k ∈ pa(π k+1 ), interventional regularity ensures that the ratio of the two entries in (74) is not a constant function which implies that dim(EQUATIONTherefore, if we haveEQUATIONby setting [W] :,k+1 = w * , we guarantee that[D • W] π k ,k+1 = 0 if π k / ∈ pa(π k+1). Note that, similarly to the base case of outer induction, Algorithm 1 is guaranteed to find c * πn-1 = 0 by searching over (α, β) ∈ {-∥W :,k ∥ 1 , . . . , ∥W :,k ∥ 1 } × {1, . . . , ∥W :,k+1 ∥ 1 }. Therefore, if dim(V) is never found to be 1 for any (α, β), it means π k ∈ pa(π k+1 ), and the algorithm adds the edge t → j, which concludes the proof of the base case for the inner induction.Induction hypothesis for the inner induction. Next, assume that for all j ∈ {k + 1, . . . , u},EQUATIONWe will prove that (77) holds for j = u + 1 as well. We work with M k,u+1 = [u -1] \ { ĉh(k) ∪ {k}}. Consider some w * = α[W] :,k + β[W] :,EQUATIONThen, we haveEQUATIONandEQUATION)We will investigate dim(V) through the ratioEQUATION)Note that, using (77) and the fact that π is a causal order, we know that c πi = 0 , ∀ i ∈ {u + 2, . . . , n} ∪ {{k + 1, . . . , u} \ ân(u + 1)} , (83) and Λ πj ,πi = 0 , ∀ π j / ∈ pa(π i ) .Then, using (83) and (84), we haveEQUATIONEQUATIONFirst, note that if there exists ℓ such that π k ∈ an(π ℓ ) and π ℓ ∈ an(π u+1 ), then by the assumptions in (68) and (77), we already have that k ∈ pa(ℓ) and ℓ ∈ pa(u + 1) which implies that k ∈ pa(u + 1).Then, we only need to consider the case where there does not exist such ℓ. In this case, the summation in ( 86) is zero and we haveEQUATIONNext, if π k ∈ pa(π u+1 ), interventional regularity ensures that this ratio is not a constant function which implies that dim(V)EQUATIONwhich is not constant due to Lemma 3 and subsequently dim(V) ≥ 2. Therefore, dim(V) = 1 implies that π k / ∈ an(π u+1 ) and c * π k = [D • W] π k ,u+1 = 0. Finally, similarly to the previous cases, Algorithm 1 is guaranteed to find such (α, β) that makes c * π k = 0 by searching over (α, β) ∈ {-∥W :,k ∥ 1 , . . . , ∥W :,k ∥ 1 } × {1, . . . , ∥W :,u+1 ∥ 1 }, e.g., (α,β) = (-[D • W] k,u+1 , [D • W] k,k ).Then, the proof of the inner induction step, and subsequently, the outer induction step is concluded, and (49) holds true. Consequently, the proof of the theorem is completed.We start with a short synopsis of the proof. Stage 4 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 as a surrogate for independence and search for unmixing vectors to 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. In the graph recovery stage, we leverage the knowledge of ancestral relationships and use a small number of conditional independence tests to remove the edges from non-parent ancestors to the children nodes.First, by Theorem 3, for the output H * of Stage 3 of Algorithm 1 we haveEQUATIONfor some lower triangular matrix L ∈ R n×n such that L has non-zero diagonal entries and L i,j = 0 for all j / ∈ an(i), and π is a causal order. We will show that the output of Stage 4 satisfies thatEQUATIONwhich will imply Ẑ(X;EQUATIONwhere P π is the row permutation matrix of π and C s 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 π 1 is a root node in G as shown in Lemma 2, (89) impliesEQUATIONand ( 90) is satisfied for t = 1. Next, assume that (90) is satisfied for all t ∈ {1, . . . , k -1}, i.e.,EQUATION)Consider k-th iteration of the algorithm in which we update H * k where {H * i : i ∈ [k -1]} already satisfy (90). We will prove that (90) will be satisfied in four steps. Consider any environment E m and use shorthand Ẑm for Ẑm (X; H * ).Step 1:EQUATION) for some nonzero constants {c 1 , . . . , c k-1 }. Specifically, by definingân(k) = {γ 1 , . . . , γ r } (95)in which the nodes are topologically ordered, thenEQUATION)Note that Cov( Ẑm ân(k) ) is invertible since the causal relationships among the entries in Ẑm ân(k) are not deterministic. Then, we haveCov(u • Ẑm ân(k) + Ẑm k , Ẑm ân(k) ) = 0 ⇐⇒ u = -Cov( Ẑm k , Ẑm ân(k) ) • [Cov( Ẑm ân(k) )] -1 .(97) For the next step, using the additive noise model specified in (3), under hard interventions we haveEQUATION)where Nπ k denotes the exogenous noise term under intervention. Let us use f and N as shorthands for f m π k and N m π k .Step 2:EQUATIONwhere c ′ ∈ R | ân(k)| and c ′ 0 is a non-zero scalar. Then, U can be restated asEQUATION)Note that U ⊥ ⊥ Ẑm ân(k) and (96) together imply that U is independent of any function of the variables in {Z m πi : i ∈ an(k)}. Hence,EQUATIONwhere the right-hand size is U and the left-hand side is a function of {Z m πi : i ∈ an(k)}. Also, since N is the exogenous noise variable associated with Z π k , we haveEQUATION)(101) and (102) imply that(u + c ′ ) • Ẑm ân(k) + c ′ 0 • f (Z pa(k) ) is a constant function of Ẑm ân(k) . Since (u + c ′ ) • Ẑm ân(k)is a linear function (or constant zero) and c ′ 0 ̸ = 0, f cannot be a nonlinear function which concludes the proof of this step. Next, we consider two possible cases, f is zero, i.e., π k ∈ I m case, and f is a linear function.Step 3: π k ∈ I m and f = 0. In this case, we have Z m π k = N . Note that for u = -c ′ , (100) becomesEQUATION)Also note that, any u vector that satisfies U ⊥ ⊥ Ẑm ân(k) also satisfies Cov(U, Ẑm ân(k) ) = 0. In Step 1, we have shown that Cov(U, Ẑm ân(k) ) = 0 has a unique solution. Therefore, U ⊥ ⊥ Ẑm ân(k) also has a unique solution, which we have found in (97). Hence, if π k ∈ I m , then Algorithm 1 updates H * k correctly.Step 4: π k / ∈ I m and f is linear. Only remaining case to check isEQUATIONin which c ′′ ∈ R | ân(k)| has nonzero entries only at the coordinates corresponding to pa(π k ). Then, for(u + c ′ ) • Ẑm ân(k) + c ′ 0 • f (Z pa(k)) to be a constant function, we need to have(u + c ′ + c ′ 0 • c ′′ ) = 0.Note that, for c ′′ ̸ = 0 case, i.e., f ̸ = 0 and π k / ∈ I m , we have already found u obs = -c ′ -c ′ 0 • c ′′ using the observational environment. Since we are searching for u = -c ′ , which is required to achieve scaling consistency, we compare the solution u m at environment E m to u obs and if they are distinct, we update H * k . To sum up, Stage 4 updates H * k correctly by identifying an environment E m in which Z π k is intervened and eliminating the effect of H * ân(k) . Finally, we note that such an environment is guaranteed to exist among {E m : W m,k ̸ = 0}. To see this, recall that [D • W] π k ,k ̸ = 0 due to (49), proven in Theorem 3. This implies that there exists m such that D π k ,m = 1 and W m,k ̸ = 0, and D π k ,m = 1 implies that π k ∈ I m . This completes the proof of (90), and subsequently the proof of the perfect latent recovery.After the first step of Stage 4, we haveEQUATIONwhereEQUATIONConsider node t ∈ [n] and node j ∈ ĉh(t). If π t ∈ pa(π j ), given the adjacency-faithfulness assumption, (108) implies that Ẑt and Ẑj 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 pa(π j ) and does not contain a node in de(π j ) satisfiesEQUATION, Ẑt ⊥ ⊥ Ẑj | { Ẑi : i ∈ S} . (110) Finally, if π t /∈ pa(π j ), then pa(j) \ {t} contains all the nodes in pa(π j ) and does not contain a node in de(π j ). Hence, the second stage of Step 4 of Algorithm 1 successfully eliminates all spurious edges between t and j ∈ ĉh(t).Under Assumption 1 and interventional regularity, Lemma 2 and Theorem 3 show that using UMN soft interventions, outputs of Algorithm 1 satisfy identifiability up to ancestors. Hence, identifiability up to ancestors is possible using UMN soft interventions. Furthermore, note that Lemma 2 and Theorem 3 are valid for both soft and hard interventions. Then, Theorem 4 shows that using UMN hard interventions, Algorithm 1 outputs satisfy perfect identifiability. Hence, perfect identifiability is possible using UMN hard interventions.We start by showing that [Λ(z)] i,i cannot be a constant function in z. This is shown in the proof of [5, Lemma 7] . For our paper to be self-contained, we repeat the proof steps in [5] as follows. For i ∈EQUATIONWe prove by contradiction that h(z i , z pa(i) ) varies with z i . Assume the contrary, i.e., let h(z i , z pa(i) ) = h(z pa(i) ). By rearranging (111) we haveEQUATIONFix a realization of z pa(i) = z * pa(i) , and integrate both sides of (112) with respect to z i . Since both p i and q i are pdfs, we haveEQUATIONThis identity implies thatp i (z i | z * pa(i) ) = q i (z i | z * pa(i) )for any arbitrary realization z * pa(i) , which contradicts with the premise that observational and interventional causal mechanisms are distinct. Consequently,EQUATIONis not a constant in z. Note that for a fixed realization of z j = z * j , z pa(i) = z * pa(i) , and z pa(j) = z * pa(j) , [Λ(z)] j,j becomes constant whereas [Λ(z)] i,i varies with z i . Hence, their ratio is not a constant in z. Finally, note that Λ(z) is an upper-triangular matrix since (1, . . . , n) is a valid causal order and for all i ∈ [n],EQUATIONis a function of only {z k : k ∈ pa(i) ∪ {i}}. Together with the fact that diagonal entries of Λ(z) are not constantly zero, the columns (and rows) of Λ are linearly independent vector-valued functions.A.6 Insufficiency of strongly separating sets Background. Recently, [16] has shown the identifiability of latent representations under a linear transformation using do interventions. Specifically, they have shown that a strongly separating set of multi-node interventions are sufficient for identifiability. It is well-known that strongly separating sets can be constructed using 2⌈log 2 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 of 2⌈log 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 n = 2 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 I 1 = {1} and I 2 = {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 in the second model such that observed variables in both models will have the same distributions. We construct a pair of indistinguishable models as follows.(134) has a real solution for b if and only ifEQUATIONThis implies that, ifV1 V2 ̸ = V * 1 V * 2 ,we can choose a and b that satisfies (134), and c is determined by (132). This means that, for any given 1. ∂f i (z pa(i) ) ∂z j is not constant and there do not exist constants{ V1 , V * 1 , V2 , V * 2 } such that V1 V2 ̸ = V * 1 V * 2 , there exists {a, b, c, d} and {V 1 , V * 1 , V 2 , V * 2 } that ensures X 1 =EQUATION∂f i (z pa(i) ) ∂z j is constant and noise term N i remains unaltered after the intervention.Proof: The additive noise model for nodes i and j are given byEQUATIONWhen nodes i and j are intervened, respectively, Z i and Z j are generated according toEQUATIONin which Ni and Nj correspond to exogenous noise terms for nodes i and j under intervention. Then, denoting the pdfs of N i , Ni , N j , Nj by h i , hi , h j , hj , respectively, we haveEQUATIONEQUATIONEQUATIONEQUATIONThen, by denoting the score functions associated with h i , hi , h j , hj by r i , ri , r j , rj , respectively, we haveEQUATIONEQUATION∂ ∂z j log p j (z j | z pa(j) ) q j (z j ) = r j (n j ) -rj (n j + f j (z pa(j) )) .Next, assume the contrary and let the ratio in (12) be a constant α ∈ R. Then, substituting (143), (144), and (145) into (12) and rearranging the terms, we haveEQUATION)Case 1:∂fi(z pa(i) ) ∂zj is not constant. Consider two distinct realizations of Z pa(i)∪pa(j) such that ∂ ∂zj f i (z pa(i) ) takes values of β 1 and β 2 where β 1 ̸ = β 2 . Then, (146) impliesEQUATIONfor some constants γ 1 , γ 2 , u 1 , u 2 for all n i ∈ R, and β 1 ̸ = β 2 . By rearranging the terms, we get rid of r i (n i ) terms and obtainEQUATIONSinceEQUATIONwhere α 1 , α 2 , α 3 are constants and α 1 ̸ = 1. Therefore, if there does not exist such constants, then the ratio in ( 12) cannot be a constant.∂fi(z pa(i) ) ∂zj = β for some nonzero constant β. In this case, (146) becomesEQUATIONNote that the right-hand side of (151) does not contain n i . Also note that since f i (z pa(i) ) is continuous, there exists an open interval Θ ⊆ R such that f i (z pa(i) ) can take all values θ ∈ Θ. Then, by taking the derivative of both sides with respect to n i and varying f i (z pa(i) ) in Θ, we find that r′ i (n i + θ) is constant for all θ ∈ Θ. Since ri is analytic, this means that ri (y) = α 1 • y + α 2 for some constants α 1 , α 2 for all y ∈ R. Then, since the noise term is invariant under intervention, we have r i = ri . Substituting this into (151), we obtain(α + β) • (αn i + α 2 ) -αα 1 • (n i + f i (z pa(i) )) = c • r j (n j ) -rj (n j + f j (z pa(j) )) . (152)Since β ̸ = 0, the left-hand side is a function of n i 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 elaborate on as follows.Stage 1: The score difference estimation is only performed once before the subsequent main algorithm 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×(2κ+1) n times. Here, κ denotes the maximum possible determinant of a matrix in {0, 1} (n-1)×(n-1) . In the proof of Lemma 2 in Appendix A.1, 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 ∥W :,j ∥ 1 × ∥W :,t ∥ 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 as a 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 2 ).Bounds on κ. In Section 4, we defined κ as the maximum determinant of a binary matrix {0, 1} (n-1)×(n-1) 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 [31] , we have However, for specific cases, we have much smaller upper bounds for κ. For instance, for the choices of n being 2, 3, 4, 5, 6, 7, κ is known to be upper bounded by 1, 1, 2, 3, 5, 9, respectively [31] .EQUATION)Furthermore, [32] shows that the determinant of a matrix in {0, 1} n×n with n + k nonzero entries is bounded by 2 k/3 . Hence, if D has n + k nonzero entries, thenEQUATIONThis implies that κ can be quite small for sparse UMN interventions. For instance, if we take the exhaustive set of SN interventions and only add two additional intervened nodes in total, then we have κ = 1.Empirical tricks. Finally, we note that various empirical tricks can be used to reduce the algorithm'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 κ can grow quickly as n becomes larger, in our experiments with up to n = 8 nodes, we observe that setting κ = 2 usually suffices for a good performance. Hence, we set κ = 2 in the simulations in Section 5.Details of evaluation metrics. For the graph recovery via hard interventions, we use conditional independence tests in Stage 4 of Algorithm 1. 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 ℓ soft defined in (19) , we first pass the entries of H * • G through a threshold of 0.1, then compute the incorrect mixing metrics.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 to study nonlinear latent causal models to investigate the relation between the algorithm's performance and the accuracy of the score function estimates. To this end, we adopt a quadratic latent causal model under varying amounts of noise in score functions. Specifically, we follow the experimental setup in [7] and adopt a quadratic latent causal model with additive noise as followsEQUATIONwhere {A i : i ∈ [n]} are positive-definite matrices, and the noise terms are zero-mean Gaussian variables with variances σ 2 i sampled randomly from Unif([0.5, 1.5]). For an intervention on node i, Z i is set to N i /2. This causal model admits a closed-form score function (see [7, Appendix E.2] for details), which enables us to obtain a score oracle. In our MN intervention setup, we use this score oracle and introduce varying levels of artificial noise according to ŝX (x; σEQUATIONto test the behavior of our algorithm under different noise regimes σ ∈ [10 -3 , 10 -1.5 ]. Figure 1 demonstrates the results for the latent graph recovery and latent variable recovery.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: The experimental procedure is described in Section 5, and detailed parameterization 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 of 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, in appendix, or as supplemental material. 
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 2 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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to 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. Guidelines:• The answer NA means that there is no societal impact of the work performed.• 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), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper is mostly theoretical and does not pose such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a 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 in the code of our experiments.Guidelines:• The answer NA means that the paper does not use 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 is used and, if 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 not available online, the authors are encouraged to reach out to the asset's creators. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.Perfect identifiability results in the closely related literature are given for additive noise models[7,4,8,16].[4, Proposition 5] shows that if the non-intervened node i has at least one parent, then perfect identifiability is not possible.Some examples include Assumption 1 in[6], generic SN interventions in[4], no pure shift interventions condition in[8], and the genericity condition in[9].The codebase for the experiments can be found at https://github.com/acarturk-e/umni-crl. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- The current evaluation of the algorithm is limited to synthetic simulations. Expanding it to more realistic datasets would substantively improve its practical significance.
questions: questions: How effectively does the proposed algorithm scale to more nodes and higher dimensions?
limitations: limitations: The paper acknowledges its main limitations in the reliance on linear transformations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The transformation from latent to observed is noiseless, which could be a limitation. 
2. 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. 
3. The experiments are only on synthetic dataset but I don’t think that is a big issue. 
4. Some potential missing citations
    
    [1] Kumar, Abhinav, and Gaurav Sinha. "Disentangling mixtures of unknown causal interventions." *Uncertainty in Artificial Intelligence*. PMLR, 2021.
    
    [2] Jiang, Yibo, and Bryon Aragam. "Learning nonparametric latent causal graphs with unknown interventions." *Advances in Neural Information Processing Systems* 36 (2024).
questions: 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?
2. 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: limitations: 1. Theorem 1 only works for additive noise model.
2. The transformation from latent to observed noiseless.
3. Experiments are only on synthetic dataset. 
4. I am unsure if the algorithm is practical because it needs to estimate the score function.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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).

[1] Bing et al. “Identifying Linearly-Mixed Causal Representations from Multi-Node Interventions” CLeaR 2024.
questions: 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.
- 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?
- 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.
- 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?
- Are there any distributional assumptions on the exogenous noise in the latent additive noise causal model?
- 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?
- 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.
- 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: Limitations are discussed in Section 6.
paper_summary: paper_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.
strength_weakness: strength_weakness: * The paper primarily focuses on causal models with linear transformations. This limits its applicability in many real scenarios

* The applicability of the assumptions in real scenarios was not discussed

* The method was not applied on real world-data
questions: questions: * Can you please elaborate on the computational complexity and on why it is dominated by step 2?

* Can you please discuss the applicability of the assumptions in real scenarios?

* I think that adding some real world application can increase the impact of this paper. Is it possible to find such an application?
limitations: 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.
paper_summary: paper_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.
Overall, I find this work serves as an important step for interventional CRL towards more realistic settings.

&nbsp;

### References

[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.

[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.

[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.
strength_weakness: strength_weakness: 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.

2. 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].

3. 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).
questions: questions: See the first point in **weakness** section. I am very happy to raise my rating if this issue is resolved.
limitations: limitations: The authors discussed the remaining open problems and limitations in Section 6.

Comments: comment: Thank you for your response to my question. I increased the score to 7.
Thanks for your rebuttal. I have raised my score leaning towards acceptance.
I thank the authors for the response. After reviewing the reviews and considering the responses, I will raise my score to 7.
I greatly appreciate the authors taking the time to answer my questions and provide clarifications. My questions and concerns have been addressed quite well in the response. The new empirical results for a larger number of causal variables further strengthen the paper. I believe this is a high-quality submission with significant theoretical results of great interest to the CRL community. Thus, I raise my score to 8.
I thank the authors for clarifying and providing additional experiment results. I increased the score correspondingly.