Nonparametric Identifiability of Causal Representations from Unknown Interventions
Authors: Julius von Kügelgen
Michel Besserve
Wendong Liang
Luigi Gresele
Armin Kekić
Elias Bareinboim
David Blei
Bernhard Schölkopf
Venue: NeurIPS 2023 poster (2023)
Keywords: Causal representation learning
identifiability
theory
nonparametric
interventions
multi-environment
TL;DR: We prove identifiability for causal representation learning with nonparametric causal model and mixing function from single-node perfect interventions on unknown targets.

Abstract: We study causal representation learning, the task of inferring latent causal variables and their causal relations from high-dimensional functions (“mixtures”) of the variables. Prior work relies on weak supervision, in the form of counterfactual pre- and post-intervention views or temporal structure; places restrictive assumptions, such as linearity, on the mixing function or latent causal model; or requires partial knowledge of the generative process, such as the causal graph or intervention targets. We instead consider the general setting in which both the causal model and the mixing function are nonparametric. The learning signal takes the form of multiple datasets, or environments, arising from unknown interventions in the underlying causal model. Our goal is to identify both the ground truth latents and their causal graph up to a set of ambiguities which we show to be irresolvable from interventional data. We study the fundamental setting of two causal variables and prove that the observational distribution and one perfect intervention per node suffice for identifiability, subject to a genericity condition. This condition rules out spurious solutions that involve fine-tuning of the intervened and observational distributions, mirroring similar conditions for nonlinear cause-effect inference. For an arbitrary number of variables, we show that at least one pair of distinct perfect interventional domains per node guarantees identifiability. Further, we demonstrate that the strengths of causal influences among the latent variables are preserved by all equivalent solutions, rendering the inferred representation appropriate for drawing causal conclusions from new data. Our study provides the first identifiability results for the general nonparametric setting with unknown interventions, and elucidates what is possible and impossible for causal representation learning without more direct supervision.

Nonparametric Identifiability of Causal Representations from Unknown Interventions
Julius von Kügelgen 12 Michel Besserve', Liang Wendong', Luigi Gresele'. Armin Kekić', Elias Bareinboim', David M. Blei', and Bernhard Schölkopf'
Max Planck Institute for Intelligent Systems, Tübingen, Germany Department of Engineering. University of Cambridge, United Kingdom CCoumbia University, USA
Abstract
We study causal representation learning, the task of inferring latent causal variables and their causal relations from nigh-dimensiooal functions ("mixtures") of the vari- ables. Prior work relies weak supervision, in the form of counterfactual pre- and post-intervention views or temporal structure; places restrictive assumptions, such linearity, on the mixing function latent causal model; or requires partial knowl- edge of the generative process, such as the causal graph or intervention targets. We instead consider the general setting which both the causal model and the mixing function are nonparametric. The learning signal takes the form of multiple datasets, environments, arising from unknown interventions in the underlying causal model. Our goal is to identify both the ground truth latents and their causal graph up to a set of ambiguities which we show be irresolvable from interventional data. We study the fundamental setting of two causal variables and prove that the obser- vational distribution and one perfect intervention per node suffice for identifiability, subject a genericity condition. This condition rules out spurious solutions that involve fine-tuning of the intervened and observational distributions, mirroring sim- ilar conditions for nonlinear cause-effect inference. For an arbitrary number of vari- ables, we show that at least one pair of distinct perfect interventional domains per node guarantees identifiability. Further, demonstrate that the strengths of causal influences among the latent variables are preserved by all equivalent solutions, rendering the inferred representation appropriate for drawing causal conclusions from new data. Our study provides the first identifiability results for the general nonparametric setting with unknown interventions, and elucidates what is possible and impossible for causal representation learning without more direct supervision.
1 Introduction
Causal representation learning (CRL) seeks to describe high-dimensional, low-level observations through small number of interpretable, causally-related latent variables [108, 110]. In doing so, its goal is to combine the strengths of classical causal inference with those modern machine learning. A causal model represents entire family of distributions arising from interventions variables [10, 95, 100]. This provides a principled way for reasoning about distribution shifts, which facilitates out-of-distribution generalization and planning [9, 64, 96, 102]. However, causal models require that most (or at least some) relevant causal variables are directly observed. While reasonable in domains such as economics [7], social [91] biomedical science [48, 57], this assumption has challenged the application of causal methodology to complex and nigh-dimensiooal data [85]. Machine learning, on the other hand, has proven successful learning useful "representations". latent vectors generating the observables via some nonlinear map of high-dimensional data such as images, video, or text [16, 20, 77, 106]. However, most methods rely on independent and identically distributed (i.i.d.) data and only extract associational information. As a consequence, they often fail under distribution shifts and do not generalize beyond the training distribution [107], as exhibited by their reliance on spurious correlations [13, 87] or their vulnerability to adversarial examples [40, 1 19].
system of
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

Exogenous
Causal Variables
Mixing Function
High-dimensional Observations X E R"
Graph Identifiability Class
Variables
V2
U1
V22
U2
U
V
X
X
Figure I: (Left) Gete-Genng Process for Causal Representation Learning (CRL). Observations X are generated by applying a nonlincar mixing function f to set of causal latent variables V { {1/, V, which related through structural causal model (SCM) with independent exogenous variables U U= {U1,-.. ...,, Un illustration by Ana Martín Larrañaga. (Right) Comparison to Structure Learning. The causal direction between two unconfounded observed variables (top) is uniquely identified from a single intervention [37]; for CRL (bot- tom), this is not the case, as the nonlinear mixing introduces additional ambiguity due to spurious representations. Shaded nodes are observed, white ones unoberved, and interventions highlighted as red diamonds.
Identifiability. It has been argued that to address these shortcomings, we ought to learn representations endowed with causal model semantics. However, a major challenge to this goal is that different representations can explain the same data equally well. Strictly simpler representation learning tasks, such as disentanglement [14] or independent component analysis (ICA) [53], are already non-identifablee in general [54, 83]. Identifiability studies are thus required to characterize additional assumptions under which the desired latent variables can be provably recov- ered [4, 17, 21, 31, 42, 43, 45, 46, 51, 52, 55, 56, 66, 69, 70, 75, 76, 84, 90, 101, 1 12, 114, 127, 141]. In CRL, we need not only identify the latents, but also the causal graph encoding their relations. Even in the fully observed case, this task of causal discovery, or structure learning, is very challenging: the graph can only recovered up to Markov equivalence [115] based only on (observational) i.i.d. data [1 [1])), meaning that the direction of some edges cannot be determined. For CRL, the task gets strictly harder. For instance, the causal latents Vú in Fig. (Left) form a valid representation, then replacing them by the independent exogeneous U/ might be considered equally valid alternative.
What sets causal representations apart? A crucial feature of causal variables that they are the ones on which interventions are defined and whose relations we are interested in [95]. Causal discovery and CRL thus often rely on non-i.i.d data linked to interventions on the underlying causal variables [59, 72]. Unless all variables are subject to intervention, however, some fundamental differences between the fully observed and representation learning settings in the level ambiguity in the graph remain [117], as illustrated in Fig. 1 (Right). In a sense, the non-identifiabilite of representation and structure learning combine, and both need to be addressed in conjunction.
Problem Setting, We study the general nonparametric CRL problem ($ 2. in which both the causal mechanisms and the mixing function are completely unconstrained. Our goal ($ 2.2) is to identify the latent causal variables up to element-wise nonlinear rescaling and their graph up to isomorphism (Defn. 2.6). As motivated above, doing so without further supervision requires access to interventional data. To this end, we consider learning from heterogeneous data from multiple related domains, or environments, that arise from interventions
shared underlying causal model ($ 2.3).
Contributions. Our main contributions are theoretical in nature ($ 3). First, we establish the mini- mality of the targeted equivalence class (Prop. 3.1) in the sense that its ambiguities cannot be resolved from interventional data. We then present our main identifiability results. For the case of two latent causal variables, we show that an observational environment and one for each perfect intervention on either variable suffice (Thm. provided that the intervened and unintervened mechanisms are not "fine-tuned" each other, which we formalize in the form of genericity condition (3.2). For any number of latent causal variables, we prove that access to pairs of environments corresponding to two distinct perfect interventions on each node guarantees identifiability (Thm. 3.4). We then question how to use or interpret causal representations ($ 4), and show that certain quantities, such as the strengths of causal influences among variables, are preserved by all equivalent solutions (Thm. 4.2). We sketch possible learning objectives ($ 5), and empirically investigate training different generative models ($ 6), finding that only those based on the correct causal structure attain the best fit and identify the ground truth. We conclude by discussing limitations and extensions of our work ($ 7).

---

Related Work on Multi-Environment CRL. Most closely related are recent identifiability studies which also leverage multiple environments arising from single node interventions [5. 22. 117. 122], thus mirroring in different interventional setups the result of Brehmer et al. [18] based on counterfactual, multi-view data, which is harder to obtain. Squires et al. [117] provide results for linear causal models and linear mixing; Ahuja et al. [5] consider nonlinear causal models and polynomial mixings, subject to additional constraints on the latent support [ [125]; and Varici et al. [122] employ score-based approach for nonlinear causal models and linear mixing. The concurrent work of Buchholz et al. [22] extends the results of Squires et al. [117] to general nonlinear mixings and linear Gaussian causal models. Liu et al. [82] leverage recent advances in nonlinear ICA [55, 65] to identify a linear Gaussian causal model with context- tettext-depedeent weights and nonlinear mixing from sufficiently diverse environments. A more extensive discussion of other related works and detailed comparison of existing results with the present study are provided in Appx. A and Tab. 1.
2 Nonparametric Causal Representation Learning
In this section, describe the considered problem setting and state our main assumptions. First, we specify the assumed data generating process ($ 2.1) and learning task in the form of a target identifiability class (5 2.2). We then demonstrate the hardness of our task from i.i.d. data or imperfect interventions and use this to motivate a multi-environment approach with perfect interventions ($ 2.3).
Notation. We use upper-case X for random variables and lower-case x for their realizations. Bold uppercase X denotes random vectors and lowercase æ their realizations. We assume throughout that all distributions Px possess densities p(xx) with respect to (w.I.t)) the Lebesgue measure. We denote the pushforward of Px through a measurable function f by f. (Px), and write [n] = nI.......
2.1 Data Generating Process
The assumed data generating process consists of latent causal model and mixing function, see Fig. I (left). For the former, we build on the structural causal model (SCM) framework [95, 100].
Definition 2.1 (Latent SCM). Let V {V1, Vn } denote a set of causal "endogenous" variables, with each Vi taking values in I, and let U {UI,... ..., Un} denote a set of mutually independent "exogenous" random variables. The latent SCM consists of a set of structural equations
(V: := fe (Vptt))) U.)
(2.1)
where Vpa(s) S V (Vi) are the direct causes, or causal parents, of V4, and fa are deterministic func- tions; and a fully factorized joint distribution Po over the exogenous variables. The associated causal diagram G. directed graph with vertices V and edges Vj- + V iff. Vy E Vpa(i). assumed acyclic.
By acyclicity, recursive substitution of the assignments in (2.1) yields the reduced form f= (U). The SCM thus induces a unique distribution Py over the endogenous variables, given by the pushforward of Pu via (2.1), that is, Pv fxF= (Pu). By construction, Pv is Markovian w.r.t. the causal graph G [95, 100), meaning that its density obeys the causal Markov factorization:
p(e 2x)) = [[= (1 Ppa()))
(2.2)
We place the following additional assumption the distribution Pv induced by the SCM.
Assumption 2.2 (Faithfulness). The only conditional independence relations satisfied by Pv are those implied by (V; T Via(s) Vpa(t))eEjn)) where Vid(e) denotes the non-descendants of Vi in G.
Asm. 2.2 ensures one-to-one correspondence between (conditional) independence Pv and graphical separation in G and is a standard assumption in causal discovery [115]. Faithfulness rules out cancellations of influences along different paths, which occurs with probability zero for random path-coefficients [121]. It can thus also be viewed as minimality genericity assumption.
In contrast to classical causal inference, we assume that both the exogenous variables U and the endogenous causal variables V are unobserved. Instead, we will only have access to d-dimensional nonlinear mixtures X of V. We therefore make the following additional assumption.
Assumption 2.3 (Known n)), The number of latent causal variables is known.
Next, we specify the relationship between the unobserved causal variables V and the observed X. Definition 2.4 (Mixing function). The observations X are deterministically generated from V by applying mixing function f _ dd to V. that X == f(V).
3

---

The terminology and setting of a deterministic mixing is rooted in the nonlinear ICA literature [56]. In deep generative models, is commonly relaxed by considering additive noise in Defn. 2.4 [65, 90]. For representation learning scenarios, we are particularly interested in the case n. < d. To allow for re- covery of V from X, we assume that f is invertible, which a standard assumption for identifiability.
Assumption 2.5 (Difteomorphic mixing). f is a diffeomorphism' onto its image Im(f) = X S R
2.2 Learning Target: The CRL Identifiability Class CORL
Our goal is to infer the underlying latent causal variables V (X) and their causal relations. We therefore consider the true unmixing function f and the causal graph G our joint learning target: f informs us how to map observations X to causal variables V. and G tells us how to factorise the implied joint p(v) into the causal mechanisms Pr(e; Upp(t) from (2.2). Given only observations of X, this is a challenging task since neither V nor G are directly observed or known a priori.
When is candidate solution (h, G') that satisfies a given learning objective (such as maximizing the likelihood, possibly subject to additional constraints) guaranteed to match the ground truth 1 G)? This is the subject of identifiability studies and the main focus of our work. statistical model P= {po A E } with parameter space θ is identifiable if the mapping 0 ~ Po is injective [78]. For representation learning tasks, full identifiability is often not attainable, as there are some fundamental ambiguities that cannot be resolved. One therefore typically instead considers identifiability up an appropriately chosen equivalence class in the model space [2. 65, 127].
For the assumed data generating process ($ 2.1), the order of the causal variables is arbitrary, since V is unobserved. We can therefore assume without loss of generality (w.l.o.g.) that the Ví's are partially or- dered w.r.t. G. that is. V; - V = i < j. Learning G thus reduces to inferring whether the edges (Vi..... VV-.....VV-13: + Vi exist for i = 2....; n. The only remaining permutation ambiguity arises from permutations that preserve the partial order: for example, if G is given by V1_ - V/3 <- V/2, the order of V/2 and V22 cannot be uniquely determined without further assumptions. Moreover, the scaling of the causal variables is also arbitrary: any invertible element- -wie transformation can be undone part of f. We therefore define the desired identifiability class through the following equivalence relation."
Definition 2.6 (~<cu-identifff -ideniffiabiltyy). Let H. be space of unmixing functions h : X + IR" and let G be the space of DAGs over n vertices. Let -ERt. be the equivalence relation on H. x G defined as
(h1, G1) CCRL (h2, G2)
(h2, G2) = (P,-1 10000000 h1, π (G1))
(2.3)
for some element-wise diffeomorphism ((v) = (ói (v1)..... on (vn)) of TR" and a permutation i of [n] such that ग. : G2 + G2 is graph isomorphism and P., the corresponding permutation matrix.
Remark 2.7. When G has no edges, any permutation is admissible and <CRL reduces to the standard notion of identifiability up to permutation and element-wise reparametrisation of nonlinear ICA [56].
The ground truth (f-1, G) is identified up to <VRL by given learning objective if any candidate solu- tion (h, G') satisfies (h, G") ~CRL (f-1, G). We seek to discover suitable conditions that ensure this.
2.3 Multi-Envirommen Data
Given only single dataset of i.i.d. observations from Px, there no hope for ~ERI, -ww.---eeetiiiine -identiiaaaiiitty. Even for observed V (i.e., with d and known f = =id). G can only be identified up to Markov equivalence [115]. With unknown mixing f. the degree of observational non-identifiability gets even worse: for example, by using the reduced form of the SCM ($ 2. we express X in terms of the latent exogenous variables U via X = fVV)= = fo fur (U) [108]. This gives rise to a "spurious ICA solution" (f==² f-1 Gica) where GIca denotes the empty graph with independent components. Due to the non-identifiability of nonlinear ICA [54, 83], however, we cannot even learn the composition for let alone separate it into its constituents f and far to isolate the intermediate causal variables V.
Motivated by these challenges to identifiability from i.i.d. data, we instead consider learning from multiple environments E &. That is, we assume access to heterogenous data from multiple distinct distributions Px- Environments can arise, for example, from different experimental settings or
A diffeomorphism is a bijective function f such that both f and f are continuously differentiable.
If they were not such order to begin with, we could apply an appropriate permutation to and incorpo- rate the inverse permutation into the unknown mixing f without affecting X = f(V) = (fo [fo [117].
ceu satisfies symmetry and transitivity because permutations and sementtwwse functions commute.

---

Unknown Ground Truth
Data
Inference Model
G
co:
Vi
V2
V ~ PV
X
Px
Z ~ Q%
Z
Z2
c1:
V ~ PV
S
X ~
PX
h
2 ~ 22
21
Z2
e21
V1
V
V~
X PX
~ QZ
Z
Zz
Figure 2: Enttromnnvi Setup with Single-Node Perfect Interventions and Shared Mixing Function.
Illustration of the considered multi-nniiroment setup for 2 causal variables V = =V,, V2) with graph G the
given by V, - V2. shared mixing function f. and environments observational setting (ev) and perfect stochastic interventions on V12 (in ε1) and V22 (in ey). The learnt unmixing function, or encoder, is denoted by h, and the inferred latent representation by Z = (. The corresponding inferred latent distributions Q2 h.())) are Markovian w.r.t the candidate graph G' (here, equal to G). Since the intervention targets not known, they may in principle differ in Q2& shown here. However, as we prove in Thm. 3.2, such misalignment is only possible if a certain genericity condition (3.2) is violated.
{co, e1, , ez). corresponding
correspond broader contexts such as climate time. Previous work has shown that this setting can, in principle, provide useful causal learning signals [5, 8, 19, 32, 34, 47, 50, 59, 71-73, 82, 89, 98, 99, 102, 104, 109, 117, 120, 122]. However, multi-environmenn data is not necessarily useful if the corre- sponding distributions P& are allowed to differ in arbitrary ways. What makes this setting interesting the assumption that certain parts of the causal generative process shared across environments.
Here, we assume that all environments share the same invariant mixing function and underlying SCM, and that any distribution shifts arise from interventions some of the causal mechanisms. General interventions can be modelled in SCMs by replacing some of the equations in (2.1) by new assignments V, := =f.(Vaa()) Ud), resulting in "intervened" mechanisms (1, Upa()) replacing the corresponding conditionals p: (v ppp()) in (2.2) [29, 36, 95]. We summarise this as follows. Assumption 2.8 (Shared mixing and mechanisms). Each environment e shares the same mixing f.
P = (.
and each Pt results from the same SCM through an intervention on a subset of mechanisms Ie S [n]:
p² (v) = (11, mn) = II
p (vs (Pptt)))))))
II
Uy (pp(s))
Pj
EEI
jE(n](Z=
Importantly, the intervention targets Ie are not assumed to be known.
An intervention some V4 that fully removes the influence from its parents V Ppa(s) is referred to as perfect, otherwise as imperfect. It has been shown that imperfect interventions are generally insufficient for full identifiability [18], even in the linear case [117]. This is intuitive: if arbitrary imperfect interventions were allowed, including ones which preserve f:( fv(ppu()):)) and only replace U, with some new Ü. then the spurious ICA solution (J f- GIea) should be indistinguishable from the ground truth. In line with prior work [5, 18, 17, 122], we therefore assume perfect interventions. Assumption 2.9 (Perfect interventions). For all E & and i I", we have p" Upa(s) = (v:).
Based on the principle of independent causal mechanisms [100, 109]. the sparse mechanism shift hypothesis [98, 110] posits that distribution changes tend to manifest themselves in a sparse or local way in the causal factorization. In this spirit, we will assume single-node ("atomic") interventions, [ for our main results, as also required for existing results [5, 18, 117, 122).
consider candidate solutions of the form (h, G') where h is an unmixing functioon or encoder, which maps observations X to the inferred latents Z h(X), and G' is causal graph capturing the relations among the Z, The corresponding distributions of the inferred latents are thus given by the push-forward
As motivated in $ 2.2, given data from {P* }eE8
Q = h. (P&) (h f).P
The multi- environment setup with unknown single-node perfect interventions is illustrated in Fig. 2.
One could also say that there exists only one environment and each dataset corresponds intervention.
5

---

3 Identifiability Theory
We start by showing that identifiability up to <CRL is, in fact, the best we can hope for when learning from interventional data, without any more direct forms of supervision. To this end, we state the following result, which is presented more formally and proven in Appx. B.
Proposition 3.1 (Minimality of <CRL; informal). Let Z be any representation that is CCRL equivalent to V. with G' = π (G') the associated DAG. Then for any intervention on Vi S V in G. there exists an equally sparse intervention on Zx(I)= S Z in G' inducing the same observed distribution on X.
We now present our identifiability results, We first study the most fundamental bivariate case with two latent causal variables V/2 and V22 This can loosely be seen the CRL analogue of the widely studied cause- effectt problem (X-+Y or Y-X)) in classical structure learning [88, 100].
Theorem 3.2 (Bivariate identifiability up to ~oRt. from one perfect stochastic intervention per node). Suppose that we have access to multiple environments {P& { JeeE generated as described in $ 2. Let (h, G") be any candidate solution such that the
under Asms. 2.2, 2.5, 2.8 and 2.9 with inferred latent distributions Q2 = h2 (Px) of Z = h(X) and the inferred mixing function h- satisfy the above assumptions w.E.. the candidate causal graph G'. Assume additionally that
(AI) all densities ye and df are continuously disserentiable and fully supported on R.
(A2) we have access to a known observational environment en and one single node perfect interven- tion for each node, with unknown targets: there exist n-+1 environments & {e,) such that Ie0 Ø and.fo each i E [n] we have I = {T)) for an unknown permutation x of [n]:
(A3) for all i E [nt], the intervened mechanisms pe(1s) differ from the corresponding base mechanisms Pe(U;] Upa(i) everywhere, in the sense that
0
(v()))
Vo
* 0;
(3.1)
Nu; Pa( Upa(i)
(A4) ("genericity"") the base and intervened mechanisms are not fine-tuned to each other, in the sense that there exists a continuous function yp R+ + foror which
) (2
D2(U2)
(
(2((2) )2(02))
E
(p2t(22 v1
* E
(2 101)
(3.2)
Then the ground truth is identified in the sense of Defin. 2.6, that is, (f- G) MCRL (h,
Proof sketch (full proof in Appx. C.2). Consider V1 V/2 (the proof for VI A V/ is similar). Let x) o -1, RB + R"" such that V = (Z). By the change of variable formula, for all
(= = p² (z)) det [x)
(3.3)
where (Z)())
Be (z) denotes the Jacobian of t). We consider two separate cases, depending on Zzy
whether the intervention targets in 4f for 6 E {e1, E2) match those in yf (Case 1) or not (Case 2).
Case 1: Aligned Intervention Targets. According to Asm. 2.8 and (A2), (3.3) applied to the known ob- servational environment eo and the interventional environments e1, 62 leads to the system of equations:
(=()))2(22 ()a(2;0r) = P1 (1I(=)) p2 (12(2) (1)))) det J (z)
(3.4)
क (2)))2(22 ())(2:0r) pi (VI())) pa (12(2) [1)))) det (z)
(3.5)
@ (21))22(2) Pı (V1(z)) D2 (1))()) |dct J.i
(3.6)
where =pa(2;07) denotes the parents of 22 in G.. Taking quotients of (3.5) and (3.4) yields
Φ1 (21)
p1 (x)
0 =
P1
( (z))
Ouh
(43)
0eh
(z) 0.
(3.7)
P1
P1
Oz2
Oz
Thus V1 = (Z1) and (21) pz (1 (21))
(21)
Substitution into (3.6) yields
0=n
(x(22) = po (W2(21, 22))
(21, 22)
(3.8)
222
By Asm. 2. h. and thus also fo are diffoomorphisms. Hence, &e is well-defined and also diffeomorphic.

---

where we have used that, according to (3.7), Jg is triangular. According to (3.8), for all 21, the mapping 22 + 222(21, 22) is measure preserving for 92 and p2. By Lemma C.1 [18. $ A.2, Lemma 2]. it follows that the must be constant in 21. Hence, 16 is an element-wise function. Finally, G = G' fol- lows from faithfulness (Asm. 2.2), for otherwise (V1, V2)) (41 (Z1), 1/2 (Z2)) would be independent.
Case 2: Misaligned Intervention Targets. If + G, similar argument to Case I (with the roles of 2 and 22 interchanged) also yields a contradiction to faithfulness. This leaves G = G². Writing down the system of equations similar to (3.4)-(3.6), and then taking ratios of e₁ and e2 with en yields
41 (=1)
P2 222 (z)
and
22 (2)
(v)( P
P1
(3.9)
P2 (z2(z) (1))
22 (22
21)
These conditions highlight the misalignment in intervention targets (see Fig. 2). Unlike in Case 1, they do not directly imply that some elements of Ju need to be zero, that is can be arbitrarily mixed w.r.t. V. However, (3.9) imposes constraints on the form of & that, by exploiting the invariance of ạ1 across en and E1 while pi changes to Pl. can ultimately be shown to only be satisfied if the two ex- pectations in (3.2) are equal for all continuous yo. However, such fine-tuning is ruled out by (A4). O
Remark 3.3. The main difficulty of the proof is that (3.9) may, in principle, hold when (p. fr q, 7) and di are completely unconstrained. This does not arise in prior work the intervention targets are known [80, 81, 126] (Case I), or the densities or mixing are parametrically constrained [3, 117, 122].
On the Genericity Condition (A4). The condition in (3.2) contrasts expectations of the same quantity w.r.t. the observational distribution PV and the interventional distribution Pt corresponding to an intervention on 1/1 that turns P1 into Pl. The shared argument, on the other hand, is a function of the ratio between the intervened mechanism ño2 and its base mechanism p2. While the two expectations are always equal for linear yo, other choices imply non-trivial constraints. For instance, yov) = y² yields
/
pi(())) ʃ (2
duz dej #0.
(2 v2)
Since p1 + ii by assumption (A3), we argue that (A4) should generally hold for randomly chosen (PI, P2. P2) and can only be violated if they are fine-tuned to each other. It can thus be viewed as encoding some notion of genericity-in line with the principle of independent causal mecha- nisms [15, 43, 61, 100, 109], but also involving the intervened mechanisms. Interestingly, related genericity conditions also arise in the study of nonlinear cause-effect inference from observational data, where identifiability is often obtained up to set of pathological ("fine-tuned") spurious so- lutions satisfying a partial differential equation involving the original mechanisms [49, 58, 118, 137]. Further, we note that & in (3.2) can also be thought of as witness function of genericity, similar to witness functions in kernel-based two sample and independence testing [44].
Next, we provide our identifiability result for an arbitrary number of causal variables.
Theorem 3.4 (Identifiability up to <CRI. from two paired perfect stochastic interventions per node). Suppose that we have access to multiple environments }eE generated as described in $ under Asms. 2.2, 2.3, 2.5, 2.8 and 2.9. Let (h, G') be any candidate solution such that the inferred latent distributions Q2 = (Px of = (x( and the inferred mixing function i satisfy the above assumptions w.rt. the candidate causal graph G'. Assume additionally that
(AI) all densities oe and qe are continuously differentiable and fully supported on R":
(A2') we have access to at least one pair of single-node perfect interventions per node, with unknown targets: there exist m 2 n known pairs of environments & = -[(e,, <,)))" such that for each
i E [n]] there exists some unknown j E [m] for which Ie; = =I {i]:
(A3') for
forall all [m), the intervened mechanisms (T)) and pr(vs) differ everywhere, in the sense that
Vus
(vt) + 0;
(3.10)
P5
Then the ground truth is identified in the sense of Defin 2.6, that is, (f-) reR. (h, G').
'This step is where the assumption of perfect interventions (Asm. 2.9) is leveraged: the conclusion would not hold for arbitrary imperfect interventions for which (3.8) would involve (z2 22)) and pa (22(21,22) (z))).
7

---

Proof sketch (full proof in Appx. C.3). By considering ratios between ej and c,, taking partial derivatives w.r.t. 21, and using assumptions (A3'). we can identify a subset &n E E of exactly n pairs of environments corresponding to distinct intervention targets in p (for otherwise to cannot be invertible). For e() E En, w.l.o.g. fix the intervention largets in p to I I { and let be a permutation of [n] such that (i) denotes the inferred intervention target in that by (A2") is shared across (ei, e(). By the same argument as before, we must have V, - 1b; (5:((,n,)) (Zx(1)) ). that is, v is a per- mutation composed with an element-wist wise function. It remains to show that и is a graph isomorphism, that is, V/2 Vi in G > (x) Zn(z) in G". We prove = the other direction is analogous. Suppose for contradiction that there exist (i, such that Vi + V3 in G, but Za(i A Za(s)) in G'. Consider e; in which there are perfect interventions on Zn(i) and V,, For ==(x)= E pp((+(i)a') let
V. = th. (z)) and denote = U. CV) {Vi, V.). Since (x(()) and Zx(() are d-separated by pa( in the post-intervention graph GZ--00 with arrows pointing into (x() removed [95], it follows by Markovianity of w.r.t. G" that Zx(i) 1 Z=τ) ppa(7());0)) in Q2. By applying the corresponding diffeomorphic functions the, it follows from Lemma C.2 in Appx. C. that V, 1 V; V in pV. This violates faithfulness (Asm. 2.2) of Pv to G since Vi and Vg are d-connected in Gv, C
(A2') states that we know that a pair of datasets corresponds to two distinct interventions on the same underlying variable, even though we may not know the exact target of the intervention. This situation could arise, for example, if both datasets are collected under the same experimental setup but with varying experimental parameters. We stress that this is different from data consisting of pairs of views (æt, 2) sharing the values of some variables, which is counterfactual in nature [4, 18, 1 123]. One of the main challenges for our analysis (compared to counterfactual multi-view setting) thus stems from the lack of correspondences across observations from different datasets. We also stress that a purely observational environment is not needed in this case, cf. (A2) in Thm. 3.2.
(A3') states that the intervention mechanisms are distinct in that their ratio is strictly monotonic, simi- lar to (3.1) in (A3). This is slightly stronger version of the assumption of interventional discrepancy proposed by Wendong et al. [126],' which has been shown to be necessary for identifiability even if the graph G' is known. For Gaussian pt. Pt, (A3') is satisfied, for example, by a shift in mean. In the proofs, this is used to show that & must be an element-wise function, see (3.7). Intuitively, if p; = P; in some open set for more than one i, then the underlying variables can be nonlinearly mixed by geaasrr--preeevvnng automorphism within this set without affecting the observed distributions [126].
4 Interpreting Causal Representations
Suppose that succeed in identifying V and G up to ~CRL (Defn. 2.6). How can such a causal representation? Since the scale of the variables is arbitrary ($ 2.2), we clearly cannot predict the exact outcomes of interventions. We therefore seek causal quantities that are preserved by the irresolvable ambiguities of ~CRL. A prime candidate for this are interventional causal notions defined in terms of information theoretic quantities [28] and in particular the KL divergence DXL- Definition 4.1 (Causal influence; based on Defn. of Janzing et al. [62]. Let Pv be Markovian w.r.t. a DAG G with vertices V. For any V; > Vj in G, the causal influence of V2 on V, is given by
interpret
City == Dxu (Pv P(*)), where P) p) (cy) ()a)))))) -f ps (uy upals) (ealt))p((())) (v:) de;
and Pi is the interventional distribution arising from replacing the 7th mechanism by pj 3
The following result, proven in Appx. C.4, states that the causal influences are invariant to reparametri- sation and equivariant to permutations, the two irresolvable ambiguities of the CURL equivalence class. Theorem 4.2 (Preservation of causal influences under r.RL)). Let Pv be Markovian w.r.t. G, let be a graph isomorphism of G, and let o be an element- wise diffeomorphism. Let Z = Px-1 o (VV and denote its induced distribution by Qz. Then for any V: + Vj in G we have e/V; = Qz (())-
Thm. 4.2 implies that the strength of causal relations among variables in the inferred graph carry mean- ing. They can thus be used to uncover changes to the latent causal mechanisms underlying different experimental datasets, for example, to gain scientific insights when combined with domain knowledge.
"Cr. the interventional regularity assumption of Varici et al. [122, Asm. 2] which instead considers partial derivatives w.r.t the parents and is related to c-faithfulness [59, Defn. 7].
"Intuitively, this intervention captures the process of removing the arrow V + V, in G and "feeding" the con- ditional p(u5 Upa with an independent copy of V,, distributed according to its marginal, see [62] for details.
8

---

Identifiabilit Scores
Model Fits
1.00
0.24
0.85
A log-ilkelihooo
MCC
0.16
0.70
0.08
0.55
0.00
G' = G. aligned targets
G' = G. misaligned targets
G'vG, aligned targets
G' misaligned targets
G' = G. misaligned targets
G G. aligned targets
G misaligned targets
Figure 3: Empirical Comparison of Correctly and Incorrectly Specified Normalizing Flow-Based Models.
For n = 2 latent causal variables with graph G given by Vi V2. we compare a generative model based on the correct causal graph G" = G and intervention targets (blue) to other generative models assuming the wrong graph G' # G or misaligned intervention targets (yellow, red, purple). We show mean correlation coefficients (MCCs) between the learned and ground truth latents (Left) and the difference in validation model log- likelihhoodd between the well-specified and misspecified models (Right). Each violin plot is hased on 50 different ground truth data generating processes; the horizontal lines indicate the minimum, median and maximum values.
Learning Objectives
While our main focus is on studying identifiability, our theoretical insights also suggest approaches to learning causal representations from finite interventional datasets sampled from {P* Jeee- The main idea is to fit the data in a way that preserves the sparsity of interventions [98, 10] by employing the same (un)mixing function and sharing mechanisms across environments (Asm. 2.8). We sketch two approaches, which, according to our theory, should both asymptotically identify the ground truth up to cCRL if the set of available environments & is sufficiently diverse (and the other assumptions hold).
Autoencoder Framework: Jointly learn an encoder h, graph G². and intervention targets Ie such that the encoded latents Z = h(X) can be used to reconstruct the observed X across all environments, while ensuring all but the intervened mechanisms environment indicator, the latter corresponds to the constraint Z, L E Z Zpa(i:(") for e I implementable, for example, through suitable conditional independence test [39, 94, 138).
shared. Using F. as
Generative Modelling Approach: Fit base generative model (G', p f) and intervention models (I", (pf)iez )cgE by maximizing the likelihood of the multi-environman data. For example, given a candidate graph G' and candidate intervention targets )ee, learn the base and intervened mechanisms and mixing; then pick the graph and intervention targets that achieve the best fit.
Experiments
Setup. We experimentally pursue the second, generative approach. Specifically, model the mixing function generating X from Z as a normalizing, flow [30, 93] with different environment-specifee base distributions, determined by the underlying causal graph, intervention targets, and (learnt) base and intervened mechanisms. Here, we focus on the bivariate case with two ground-truth causal latent variables V1 V/2 According to Thm. 3.2, this setting should be identifiable from three environments: an observational one and one perfect intervention on each of V1 and V2. Our goal is to verify this empirically in light of finite data and optimization issues. We fix the observation dimension to d = 2 to facilitate exact likelihood training of the normalizing flows, and fit separate generative model for each choice of graph and intervention targets.' The base and intervened mechanisms are linear Gaussian and the mixing function three-laye MLP, see Appx. D.1 for implementation details.
Results. The results are summarized in Fig. 3. Our main findings two-fold: First, we observe that, in the majority of cases, the well-specified model attains the highest held-out log-likelihood, as shown in Fig. 3 (Right). This suggests that the likelihood of otherwise comparable generative models can act as a reliable criterion to select the correct causal graph and intervention targets. Second, we find that the ground truth latent causal variables are approximately identified up element-wise rescaling (MCC values close to onc) by the correctly specified model and not by any other model, as shown in Fig. (Left). This indicates that recovering the correct graph and targets is not only sufficient but also necessary for reliable identification of the causal representation. Taken together, these findings are consistent with our notion of ~CRL- -ddntifiability (Defn. 2.6) and Thm. 3.2.
This can be viewed as a nested approach in which the inner loop corresponds to the method for Causal Component Analysis (CauCA) of Wendong et al. [126], and the outer loop to a search over G" and {I" heee. Code reproduce experiments is available at: https///gguubb.co/aakkecccceee compoaataaloooottttaaaaaaaaaaaaa

---

In Appx. D.2, we perform an additional experiment with n = 3 variables, nonlinear latent SCMs, fixed causal order without graph search, and one interventional environment per node, thus assaying violations of assumption (A2") in the context of Thm. 3.4. Generally, we find that correct choice of intervention targets can be selected based on model likelihood, leading to approximate identification of the causal variables, even when only the causal order is given, see Fig. 4 and Appx. D.2 for details.
7 Conclusions and Discussion
The world is full of domain shifts and different environments. Often, we cannot pin down what exactly differs between two domains, but it may reasonably be modelled change in some causal mech- anisms. While prior work relied on harder-to-obtain counterfactual data or parametric constraints for identifiability, our study demonstrates that interventional data can be sufficient- even in the nonpara- metric case where the spaces of mixing functions and mechanisms are infinite dimensional. Our results can be considered step towards justifying the use of expressive machine learning methods for learn- ing interpretable causal representations from high-dimensional experimental data in situations where parametric assumptions are undesirable, e.g., for complex systems in physics, biology, or medicine.
Weaker Notions of Identifiability. In this work, we have focused on the strongest notion of identifia- bility that is achievable in nonparametric setting (Defn. 2.6). However, subject to the available data and assumptions, identifiability up to ~CRL is not always possible. In this case, weaker notions of identifiability are of interest. For example, not targeted by interventions [5, 80, 123], or only recover groups of variables up to (non-)ling Jinear mix- ing [5, 122, 123] and the graph up transitive closure if interventions are imperfect, soft [117, 136]. A precise characterization of weaker notions of nonparametric identifiability from different types of in- terventions (cf. [74] for temporal, semi-parametric setting) is an interesting direction for future work.
may not be able to uniquely recover variables that are
Known vs. Unknown Intervention Targets. When intervention targets can be considered known appears to be more nuanced concept in CRL than in fully observed setting, see also [126, $E] for an extended discussion. Recall that we assume w.l.o.g. that V12 1 ... I Vn and only consider graphs respecting this ordering ($ 2.2), see also [117, Remark 1]. The intervention targets are then unknown w.r.t. the pre- reppsdd causal ordering. This is a key aspect that makes our setting more realistic, but also substantially complicates the analysis (see (3.9) and Remark 3.3). Similar to [122], for Thm. 3.2 we require a set of exactly n environments (one intervention on each node). 10 However, we relax this requirement to mere coverage ("at least 1") in Thm. 3.4 as shown for linear causal models in [22, 117].
Identifiability From One Intervention per Node for Any n. We conjecture that Thm. 3.2 can be generalized to n. > 2, subject to suitably adjusted set of genericity conditions involving several intervened and base mechanisms, akin to (3.2) in the bivariate case. The main challenge to such generalization appears to be combinatorial, targets across p and q. In Thm. 3.4, we sidestep this issue by assuming pairs of environments. Thus, while two single-node perfect interventions are sufficient, we do not believe this to be necessary.
there are n! - ways of misaligning intervention
On the Assumption of Known and Its Relation to Markovianity, Asm. 2.3 relates to causal suf- ficiency or Markovianity in classical causal inference, which correspond to the assumption of indepen- dent U, in Defn. 2.1, implying the causal Markov factorization (2.2) [95, 100, 115]. With unobserved V and unknown nt, the notion of "unobserved confounders" gets blurred, since one can, in principle, always construct a causally sufficient system by increasing n and adding any causes of two or more en- dogenous variables to V. Asm. 2.3 then states that the minimum number of variables required to do so is known." 11 However, this can lead to very large systems, which may in turn challenge the assumption of an invertible mixing (Asm. 2.5). Extensions of our analysis to unknown n [63, 68], non-Markovian, or non-invertible [131] models constitute an interesting direction for future investigations.
Practicality. The method explored in $ 6 requires searching over graphs and intervention targets, which gets intractable even for moderate n. Simultaneously learning an (un)mixing function, causal graph, intervention targets, and mechanisms is challenging. Further work is needed to make methods for nonparametric CRL from multi-environmen data more practical, e.g., by exploring the proposed autoencoder framework with a continuous parametrisation of graph [139, 140] and targets [60].
By dropping the assumption of a fixed ordering and considering all DAGs, in this case one could also call V, the variable intervened upon in enviromment i, and then consider the targets "known" in this sense.
"Tehhniques for estimating the intrinsic dimensionality n of the observation manifold X C Rd or methods rooted in Bayesian nonparametries could provide means of relaxing this assumption.
10

---

Acknowledgments and Disclosure of Funding
We thank Simon Buchholz, Jiaqi Zhang, and the anonymous reviewers for helpful discussions, comments, and suggestions.
This work was supported by the Tübingen Al Center and by the Deutsche Forschungsgemeinschatt (DFG, German Research Foundation) under Germany's Excellence Strategy, EXC number 2064/1, Project number 390727645. L.G. was supported by the VideoPredict project, FKZ: 011221088.
References
[1] J. Adaas, N. Hansen, and K. Zhang. Identification of partially observed linear causal models: Graphical conditions for the non-gaussian and heterogeneous cases. Advances in Neural Information Processing Systems, 34:22822-222 228333, 2021. [Cited on p. 20.]
[2] K. Ahuja, J. Hartford, and Y. Bengio. Properties from mechanisms: equivariance per- spective on identifiable representation learning. In International Conference on Learning Representations, 2021. [Cited on 4 and 20.]
[3] K. Ahuja, D. Mahajan, V. Syrgkanis, and I. Mitliagkas. Towards efficient representation identification in supervised learning. In First Conference on Causal Learning and Reasoning, 2021. [Cited on 7 and 20.]
[4] K. Ahuja, J. Hartford, and Y. Bengio. Weakly supervised representation learning with sparse perturbations. In Advances in Neural Information Processing Systems, volume 35, pages 15516-15528, 2022. [Cited on p. 2 and 8.]
[5] Ahuja, D. Mahajan, Y. Wang, and Y. Bengio. Interventional causal representation learning. In International Conference on Machine Learning, pages 372-407. PMLR, 2023, [Cited on p. 5, 10, and 21.]
[6] T. V. Anand, A. H. Ribeiro, J. Tian, and E. Bareinboim. Effect identification in cluster causal diagrams. In Proceedings of the 37th AAAI Conference on Artificial Intellignce, 2023. [Cited p. 20.]
[7] J. D. Angrist and J.-S. Pischke. Mostly harmless econometrics; An empiricist's 's companion. Princeton University Press, 2009. [Cited on p. 1.]
[8] M. Arjovsky. L. Bottou, I. Gulrajani, and D. Lopez-Paz. Invariant risk minimization. arXiv preprint 1907.02893, 2019. [Cited on p. 5 and 20.]
[9] E. Bareinboim and Pearl. Causal inference and the data-fusion problem. Proceedings of the National Academy of Sciences, 113(27):7355-77 -3552, 2016. [Cited on p. 1.]
[10] E. Bareinboim, D. Correa, D. Ibeling, and Icard. On Pearl's hicrarchy and the foundations of causal inference. In Probabilistic and Causal Inference: The Works of Judea Pearl, page 507-556. Association for Computing Machinery, 2022. [Cited on and 20.]
[11] S. Beckers and Y. Halpem. Abstracting causal models. In Proceedings of the AAAI conference on Artificial Intelligence, volume 33, pages 2688-2685, 2019. [Cited on p. 20.]
[12] S. Beckers, F. Eherhardt, and J. Y. Halpern. Approximate causal abstractions. In Uncertainty in Artificial Intelligence, pages 606 615. PMLR, 2020. [Cited p. 20.]
[13] S. Beery, G. Van Hor,, and P. Perona. Recognition in terra incognita. In Proceedings of the European Conference on Computer Vision (ECCV), pages 456-473, 2018 [Cited on p. 1.]
[14] Y. Bengio, A. Courville, and P. Vincent. Representation learning: A review and new perspec- tives. JEEE Transactions on Pattern Analysis and Machine Intelligence, (7(8):1798-1888 2013. [Cited on p. 2.]
[15] M. Besserve, N. Shajarisales, B. Schölkopf, and D. Janzing, Group invariance principles for causal generative models. In International Conference on Artificial Intelligence and Statistics, pages 557-565. PMLR, 2018. [Cited on p. 7.]

---

[16] D. M. Blei, A. Y. Ng. and M. I. Jordan. Latent dirichlet allocation. Journal of Machine Learning Research, 3(1a)) 2003. [Cited on p. 1.]
[17] J. Brady, R. S. Zimmermann, Y. Sharma, B. Schölkopf, J. von Kügelgen, and W. Brendel. Provably learning object-centric representations. In International Conference on Machine Learning, 2023. [Cited on 2.]
[18] J. Brehmer, P. De Haan, P. Lippe, and Cohen. Weakly supervised causal representation learning. In Advances in Neural Information Processing Systems, volume 35, pages 38319- 38331, 2022. [Cited on p. 3, 7, 8, 20, 21, 23, and 25.]
[19] P. Brouillard, S. Lachapelle, A. Lacoste, S. Lacoste-Julien, and A. Drouin. Differentiable causal discovery from interventional data. In Advances in Neural Information Processing Systems, volume 33, pages 21865-21877, 2020. [Cited on p. 5.]
[20] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pages 1877-1901, 2020. [Cited on p. 1.]
[21] S. Buchholz, M. Besserve, and B. Schölkopf. Function classes for identifiable nonlinear independent component analysis. In Advances in Neural Information Processing Systems, 2022. [Cited on p. 2.]
[22] S. Buchholz, G. Rajendran, E. Rosenfeld, B. Aragam, B. Schölkopf, and P. Ravikumar. Learning linear causal representations from interventions under general nonlinear mixing. In Advances in Neural Information Processing Systems, 2023. [Cited on p. 3, 10, and 21.]
[23] R. Cai, F. Xie, C. Glymour, Z. Hao, and K. Zhang. Triad constraints for learning causal structure of latent variables. In Advances in Neural Information Processing Systems, volume 32, pages 12883-12892, 2019. [Cited on p. 20 and 21.]
[24] K. Chalupka. P. Perona, and F. Eberhardt. Visual causal feature learning. In Proceedings of the Thirty-First Conference on Uncertainty Artificial Intelligence, pages 181-190. AUAI Press, 2015. [Cited on p. 20.]
[25] K. Chalupka, F. Eberhardt, and P. Perona. Multi-level cause-effect systems. In Artificial Intelligence and Statistics, pages 361-369, PMLR, 2016.
[26] K. Chalupka, F. Eberhardt, and P. Perona. Causal feature learning: an overview. Behav- iormetrika, 44(1):137-164, 2017. [Cited on 20.]
[27] P. Comon. Independent component analysis, a new concept? Signal processing, 36(3): 287-314, 1994. [Cited on p. 20.]
[28] T. M. Cover. Elements of information theory. John Wiley & Sons, 1999. [Cited on p. 8.]
[29] A. P. Dawid. Influence diagrams for causal modelling and inference. International Statistical Review, 70(2):161-18, 2002. [Cited on p. 5.J
[30] C. Durkan, A. Bekasov, I. Murray, and G. Papamakarios. Neural spline flows. In Advances in Neural Information Processing Systems, volume 32, pages 7511-7522, 2019. [Cited on p. and 33.]
[31] C. Eastwood, A. L. Nicolicioiu, Von Kügelgen, A. Kekić, Träuble, A. Dittadi, and B. Schölkopf. DCI-ES; An extended disentanglement framework with connections to identifia- bility, In The Eleventh International Conference on Learning Representations, 2022. [Cited on p. 2.]
[32] C. Eastwood, A. Robey, S. Singh, J. von Kügelgen, H. Hassani, G. J. Pappas, and B. Schölkopf. Probable domain generalization via quantile risk minimization. In Advances in Neural Infor- mation Processing Systems, 2022. [Cited p. 5 and 20.]
[33] C. Eastwood, S. Singh, A. L. Nicolicioiu, M. Vlastelica, J. von Kügelgen, and B. Schölkopf. Spuriosity didn't kill the classifier: Using invariant predictions to harness spurious features. In Advances in Neural Information Processing Systems, 2023. [Cited on p. 20.]
12

---

[34] D. Eaton and K. Murphy. Exact bayesian structure learning from uncertain interventions. In Artificial Intelligence and Statistics, pages 107-114. PMLR, 2007. [Cited on p. 5.]
[35] F. Eberhardt. Green and grue causal variables. Synthese, 193(4):1029-1044 2016. [Cited on
p. 20.]
[36] F. Eberhardt and R. Scheines. Interventions and causal inference. Philosophy of science, 74 (5):981 1995, 2007. [Cited on p. 5.]
[37] F. Eberhardt, C. Glymour, and R. Scheines, N-1 experiments suffice to determine the causal relations among n variables. Innovations in Machine Learning: Theory and Applications, pages 97-112, 2006. [Cited on p. 2.]
[38] J. Eriksson and V. Koivumen. Identifiability, separability, and uniqueness of linear ICA models. IEEE Signal Processing Letters, 11(7):0016004 2004. [Cited on p. 20.]
[39] K. Fukumizu, A. Gretton, X. Sun, and B. Schölkopf. Kernel measures of conditional depen- dence. In Advances in Neural Information Processing Systems, volume 20, pages 489-496. Curran Associates, Inc., 2007. [Cited on p. 9.]
[40] I. Goodfellow, J. Shlens, and C. Szegedy, Explaining and harnessing adversarial examples. In 3rd International Conference on Learning Representations, 2015. [Cited on p. 1.]
[41] L. Gresele, G. Fissore, A. Javaloy, B. Schölkopf, and A. Hyvarinen. Relative gradient optimization of the Jacobian term in unsupervised deep learning. In Advances in Neural Information Processing Systems, volume 33, pages 16567-16578, 2020. [Cited p. 33.]
[42] L. Gresele, P. K. Rubenstein, A. Mehrjou, F. Locatello, and B. Schölkopf. The incomplete rosetta stone problem: Identifiability results for multi-view nonlinear ICA, In Uncertainty in Artificial Intelligence, pages 217-227. PMLR, 2020. [Cited on 2.]
[43] L. Gresele, J. von Kügelgen, V. Stimper, B. Schölkopf, and M. Besserve. Independent mechanism analysis, new concept? In Advances in Neural Information Processing Systems, volume 34, pages 28233 28248, 2021. [Cited on p. 2 and 7.]
[44] Gretton, K. M. Borgwardt, M. J. Rasch, Schölkopf, and Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012. [Cited on p. 7.]
[45] H. Hälvä and A. Hyvarinen. Hidden markov nonlinear ica: Unsupervised learning from nonstationary time series. In Conference on Uncertainty in Artificial Intelligence, pages PMLR, 2020. [Cited on 2.]
[46] H. Hälvä, S. Le Corff, L. Lehéricy, J. So, Y. Zhu, E. Gassiat, and A. Hyvarinen. Disentangling identifiable features from noisy data with structured nonlinear ica. In Advances in Neural Information Processing Systems, volume 34, pages 1624-1633, 2021. [Cited on p. 2.]
[47] Heinze-Deml, Peters, and N. Meinshausen. Invariant causal prediction for nonlinear models. Journal of Causal Inference, 6(2), 2018. [Cited on p. 5.]
[48] M. A. Hernán and J. M. Robins. Causal inference: What if. Boca Raton: Chapman & Hall/CRC., 2020. [Cited on p. 1.]
[49] P. Hoyer, D. Janzing, J. M. Mooij. J. Peters, and B. Schölkopf. Nonlinear causal discovery with additive noise models. In Advances in Neural Information Processing Systems, volume 21, pages 689-696, 2008. [Cited on p. 7.]
[50] B. Huang, K. Zhang, J. Zhang, J. D. Ramsey, R. Sinchez-RRmerd C. Glymour, and Schölkopf. Causal discovery from heterogeneoussnonsttiinnn data. Journal of Ma- chine Learning Research, 21(89):1-53, 2020. [Cited on p. 5.]
[51] A. Hyvarinen and H. Morioka. Unsupervised feature extraction by time-contrastive learning and nonlinear ICA. In Advances in Neural Information Processing Systems, pages 3765-3773,
2016. [Cited on p. 2.]
[52] Hyvarinen and H. Morioka. Nonlinear ICA of temporally dependent stationary sources. In Artificial Intelligence and Statistics, pages 460-469. PMLR, 2017. [Cited on p. 2.J
13

---

[53] A. Hyvärinen and E. Oja. Independent component analysis: algorithms and applications. Neural networks. 13(4-5):11--30, 2000. [Cited on p. 2.]
[54] A. Hyvärinen and P. Pajunen. Nonlinear independent component analysis: Existence and uniqueness results. Neural networks, 12(3):429 439, 1999. [Cited on 2 and 4.]
[55] A. Hyvarinen, H. Sasaki, and R. Turner. Nonlinear ICA using auxiliary variables and general- ized contrastive learning. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 859-868, 2019. [Cited on 2 and 3.]
[56] A. Hyvarinen, Khemakhem, and H. Morioka. Nonlinear independent component analysis for principled disentanglement in unsupervised deep learning. arXiv preprint arXiv:2303. 16535, 2023. [Cited on and 4.]
[57] G. W. Imbens and D. B. Rubin. Causal inference in statistics, social, and biomedical sciences. Cambridge University Press, 2015. [Cited p. 1.]
[58] A. Immer, C. Schultheiss, J. E. Vogt, B. Schölkopf. P. Bühlmann, and A. Marx. On the identifiability and estimation of causal location-scale noise models. In 40th International Conference on Machine Learning, 2023. [Cited on p. 7.]
[59] A. Jaber, M. Kocaoglu, K. Shammugam, and E. Bareinboim. Causal discovery from soft interventions with unknown targets: Characterization and lcarning. In Advances in Neural Information Processing Systems, volume 33, pages 9551-9561, 2020. [Cited on p. 2, 5, and 8.]
[60] E. Jang, S. Gu, and B. Poole. Categorical reparamettrizztion with gumbel-softmax. In International Conference on Learning Representaations 2017. [Cited on p. 10.]
[61] Janzing, J. Mooij, K. Zhang, J. Lemeire, J. Zscheischler, P. Daniušis, B. Steudel, and B. Schölkopf. coormatiiongeomeette approach to inferring causal directions. Artificial Intelligence, 182:1-31, 2012. [Cited on p. 7.]
[62] D. Janzing. D. Balduzzi, M. The Annals of Statistics, 41():22324 - 2358, 2013. [Cited on p. 8.]
and B. Schölkopf. Quantifying causal influences.
[63] Y. Jiang and B. Aragam. Learning nonparametric latent causal graphs with unknown inter- ventions. In Advances in Neural Information Processing Systems, 2023. [Cited on p. 10 and 20.]
[64] A.H. Karimi, J. von Küggelgen, B. Schölkopf, and I. Valera. Towards causal algorithmic recourse. In xxAI Beyond Explainable AI. Lecture Notes in Computer Science, volume 13200, pages 139-166. Springer, 2022. [Cited on p. 1.]
[65] I. Khemakhem, D. Kingma, R. Monti, and A. Hyvarinen. Variational autoencoders and nonlinear ICA: unifying framework. In International Conference on Artificial Intelligence and Statistics, pages 2207-2217, 2020. [Cited on 3 and 4.]
[66] I. Khemakhem, R. Monti, D. Kingma, and A. Hyvarinen. ICF-BeeM: Identifiable conditional energy-based deep models based on nonlinear ICA. In Advances in Neural Information Processing Systems, volume 33, pages 12768-12778, 2020. [Cited on p. 2.]
[67] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representationss 2015. [Cited on p. 34.]
[68] B. Kivva, G. Rajendran, P. Ravikumar, and B. Aragam. Learning latent causal graphs via mixture oracles. In Advances in Neural Information Processing Systems, volume 34, pages 18087-18 101, 2021. [Cited on p. 10, 20, and 21.]
[69] B. Kivva, G. Rajendran, P. Ravikumar, and B. Aragam. Identifiability of deep generative models without auxiliary information. In Advances in Neural Information Processing Systems, volume 35, pages 15687-15701, 2022. [Cited p. 2.]
[70] D. A. Klindt, L. Schott, Y. Sharma, I. Ustyuzhaninov, W. Brendel, M. Bethge, and D. Paiton. Towards nonlinear disentanglement natural data with temporal sparse coding. In Interna- tional Conference Learning Representations, 2020. [Cited on p. 2.]
14

---

[71] M. Kocaoglu, K. Shanmugam, and E. Bareinboim. Experimental design for learning causal graphs with latent variables. In Advances in Neural Information Processing Systems, volume 31, pages 7021-7031, 2017. [Cited on p. 5.]
[72] M. Kocaoglu, A. Jaber, K. Shanmugam, and E. Bareinboim. Characterization and learning of causal graphs with latent variables from soft interventions. In Advances in Neural Information Processing Systems, volume 33, pages 14369-14377 2019. [Cited on p. 2.]
[73] D. Krueger, E. Caballero, J. Jacobsen, A. Zhang, J. Binas, D. Zhang, R. Le Priol, and A. Courville. Out-of-distribution generalization via risk extrapolation (rex). In International Conference on Machine Learning, pages 5815-5826. PMLR, 2021. [Cited on p. 5 and 20.]
[74] S. Lachapelle and S. Lacoste-Julien. Partial disentanglement via mechanism sparsity, arXiv preprint arXiv:2207.07732. 2022. [Cited on p. 10 and 20.]
[75] S. Lachapelle, P. Rodriguez, Y. Sharma, K. E. Everett, R. Le Priol, A. Lacoste, and S. Lacoste- Julien, Disentanglement via mechanism sparsity regularization: A new principle for nonlinear ICA. In Conference Causal Learning and Reasoning, pages 428-484 PMLR, 2022. [Cited on p. 2 and 20.]
[76] S. Lachapelle, T. Deleu, D. Mahajan, I. Mitliagkas, Y. Bengio, S. Lacoste-Julien, and Q. Bertrand. Synergies between disentanglement and sparsity: Generalization and iden- tifiability in multi-task learning. In International Conference Machine Learning, pages 18171-18206. PMLR, 2023. [Cited on p. 2.]
[77] Y. LeCun, Y. Bengio, and G. Hinton. Deep learning. nature, 521((553))436, 2015. [Cited on p. 1.]
[78] E. L. Lehmann and G. Casella. Theory of point estimation. Springer Science Business Media, 2006. [Cited on p. 4.]
[79] M. S. Lewicki and T. J. Sejnowski. Learning overcomplete representations. Neural computa- tion, 12(2):337-365, 2000. [Cited on p. 20.]
[80] P. Lippe, S. Magliacane, S. Löwe, Y. M. Asano, T. Cohen, and S. Gavves. Citris: Causal identifiability from temporal intervened sequences. International Conference on Machine Learning, pages 13557-13603, PMLR, 2022. [Cited on 7, 10, and 20.]
[81] P. Lippe. S. Magliacane, S. Löwe, Y. M. Asano, T. Cohen, and Gavves. Causal representation learning for instantaneous and temporal effects in interactive systems. In The Eleventh International Conference on Learning Representations, 2023. [Cited on p. and 20.]
[82] Y. Liu, Z. Zhang, D. Gong. M. Gong, B. Huang, A. v. d. Hengel, K. Zhang, and J. Q. Shi. Identifying weight-variant latent causal models. arXiv preprint arXiv:2208. 14153, 2022. [Cited p. 3, and 20.]
[83] F. Locatello, S. Bauer, M. Lucic, G. Raetsch, S. Gelly, B. Schölkopf, and O. Bachem. Chal- lenging common assumptions in the unsupervised learning of disentangled representations. In 36th International Conference on Machine Learning, pages 4114 4124. PMLR, 2019. [Cited on p. 2 and 4.]
[84] F. Locatello, B. Poole, G. Rätsch, B. Schölkopf, O. Bachem, and M. Tschannen. Weakly- supervised disentanglement without compromises. In International Conference on Machine Learning, pages 6348-6359, PMLR, 2020. [Cited on p. 2.]
[85] D. Lopez-Paz, R. Nishihara, S. Chintala, B. Schölkopf, and L. Bottou. Discovering causal signals in images. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2017), pages 58-66, 2017. [Cited on p. 1.]
[86] C. Lu, Y. Wu, M. Hernández-Lobato, and B. Schölkopf. Invariant causal representation learning for out-of-distribution generalization. In International Conference on Learning Representattinss 2022. [Cited on p. 20.]
[87] C. Mao, K. Xia, J. Wang, H. Wang, J. Yang, E. Bareinboim, and C. Vondrick. Causal transportability for visual recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7521-7531, 2022. [Cited p. 1.]
15

---

[88] J. M. Mooij, J. Peters, D. Janzing, J. Zscheischler, and B. Schölkopf. Distinguishing cause from effect using observational data; methods and benchmarks. The Journal of Machine Learning Research, 17(1): 103-1204, 2016. [Cited on p. 6.]
[89] J. M. Mooij, S. Magliacane, and T. Claassen. Joint causal inference from multiple contexts. The Journal of Machine Learning Research, 21(1):3919-40) 4026, 2020. [Cited on p. 5.]
[90] G. E. Moran, D. Sridhar, Y. Wang, and D. Blei. Identifiable deep generative models via sparse decoding. Transactions on Machine Learning Research, 2022. ISSN 2835-8856. [Cited on p. 2 and 4.]
[91] S. L.. Morgan and C. Winship. Counterfactuals and Causal Inference: Methods and Principles for Social Research. Cambridge University Press, 2014. [Cited on p. 1.]
[92] K. Muandet, D. Balduzzi, and B. Schölkopf. Domain generalization via invariant feature representation. In Proceedings of the 30th International Conference on Machine Learning, volume 28, pages (0-18,22 2013. [Cited on p. 20.]
[93] G. Papamakarios, E. Nalisnick, D. J. Rezende, S. Mohamed, and B. Lakshminarayanan. Normalizing flows for probabilistic modeling and inference. The Journal of Machine Learning Research, 22(1) 11227:6-6680, 2021. [Cited on p. and 33.]
[94] J. Park, U. Shalit, B. Schölkopf. and K. Muandet. Conditional distributional treatment effect with kernel conditional mean embeddings and u-statistic regression. In International Conference on Machine Learning, pages 8401-8412. PMLR, 2021. [Cited on p. 9.]
[95] J. Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, NY, 2nd edition, 2009. [Cited p. 1, 3, 5, 8, 10, and 31.]
[96] J. Pearl and E. Bareinboim. External validity: From do-calculus to transportability across populations. Statistical Science, pages 579-595, 2014. [Cited on p. 1.]
[97] J. Pearl and D. Mackenzie. The book why: the new science of cause and effect. Basic books, 2018. [Cited on 20.]
[98] R. Perry, J. von Kügelgen, and B. Schölkopf. Causal discovery in heterogeneous environments under the sparse mechanism shift hypothesis. In Advances in Neural Information Processing Systems, 2022. [Cited on p. 5 and 9.]
[99] J. Peters, P. Bühlmann, and N. Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 7855:997-1 2016. [Cited on p. 5.]
[100] J. Peters, D. Janzing, and B. Schölkopf. Elements of causal inference: foundations and learning algorithms. MIT Press, 2017, [Cited on p. 1, 5, 6, 7, and 10.]
[101] G. Roeder, L. Metz, and D. Kingma. On linear identifiability of learned representations. In International Conference on Machine Learning, pages 9030-9039, 2021. [Cited on p. 2.]
[102] M. Rojas-Carulla, B. Schölkopf, R. Turner, and Peters. Invariant models for causal transfer learning. Journal of Machine Learning Research, (14):1100--1322, 2018. [Cited on p. 1 and 5.]
[103] K. Roth, M. Ibrahim, Z. Akata, P. Vincent, and D. Bouchacourt. Disentanglement of correlated factors via hausdorff factorized support. In The Eleventh International Conference Learning Representations, 2023. [Cited on p. 21.]
[104] D. Rothenhäusler, N. Meinshausen, Bühlmann, and J. Peters. Anchor regression: Hetero- geneous data meet causality. Journal of the Royal Statistical Society Series B: Statistical Methodology, 83(2):215-246, 2021. [Cited on 5.]
[105] P. Rubenstein, S. Weichwald, S. Bongers, J. Mooij, D. Janzing, M. Grosse Wentrup, and
B. Schölkopf. Causal consistency of structural equation models. In 33rd Conference Uncertainty in Artificial Intelligence, pages 808-817. Curran Associates, Inc., 2017. [Cited on
p. 20.]
16

---

[106] J. Schmidhuber. Deep learning in neural networks: An overview. Neural networks, 61:85-117, 2015. [Cited on p. 1.]
[107] B. Schölkopf. Causality for machine learning. In Probabilistic and Causal Inference: The Works of Judea Pearl, pages 765-804, 2022. [Cited on p. 1.]
[108] B. Schölkopf and J. Kügelgen. From statistical to causal learning. In Proceedings the International Congress of Mathematicians, 2022. [Cited on p. and 4.]
[109] B. Schölkopf, D. Janzing, J. Peters, E. Sgouritsa, K. Zhang, and J. Mooij- On causal and anticausal learning. In Proceedings of the 29th International Conference on Machine Learning,
pages 459-466, 2012. [Cited on p. and 7.]
[110] B. Schölkopf, F. Locatello, S. Bauer, N. R. Ke, N. Kalchbrenner, A. Goyal, and Y. Bengio. Toward causal representation learning. Proceedings of the IEEE, 109(5);612-655 634, 2021. [Cited on p. 1, 5, 9, and 20.]
[111] Shen, F. Liu, H. Dong, Q. Lian, Z. Chen, and T. Zhang. Weakly supervised disentangled generative causal representation learning. Journal of Machine Learning Research, 23:1-55, 2022. [Cited on p. 20.]
[112] R. Shu, Y. Chen, A. Kumar, S. Ermon, and B. Poole. Weakly supervised disentanglement with guarantees. In International Conference on Learning Representations, 2019. [Cited on p. 2.]
[113] R. Silva, R. Scheines, C. Glymour, P. Spirtes, and D. M. Chickering. Learning the structure of linear latent variable models. Journal of Machine Learning Research, 7(2), 2006. [Cited on p. 20.]
[114] P. Sorrenson, C. Rother, and U. Köthe. Disentanglement by nonlinear ICA with general incompressible-foot networks (gin). In International Conference on Learning Representations. 2019. [Cited on 2.]
[115] P. Spirtes, C. Glymour, and Scheines. Causation, Prediction, and Search. The MIT Press, 2001. [Cited on 2, 3, 4, 10, and 20.]
[116] Squires and C. Uhler. Causal structure learning: a combinatorial perspective. Foundations of Computational Mathematics, pages 1-35, 2022. [Cited p. 2.]
[117] C. Squires, A. Seigal, S. Bhate, and C. Uhler. Linear causal disentanglement via interventions. In 40th International Conference on Machine Learning. 2023. [Cited on p. 4,5, 7, 10, 21, and 36.]
[118) E. V. Strobl and T. A. Lasko. Identifying patient-specifie root causes with the heteroscedastic noise model. arXiv preprint arXiv:2205. /3055, 2022. [Cited on 7.]
[119] Szegedy, W. Zaremba, I. Sutskever, J. Bruna, Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, 2014. [Cited on p. 1.]
[120] J. Tian and J. Pearl. Causal discovery from changes. In Proceedings of the 17th Annual Conference on Uncertainty in Artificial Intelligence, pages 512-522, 2001. [Cited on p. 5.]
[121] C. Uhler, G. Raskutti, P. Bühlmann, and B. Yu. Geometry of the faithfulness assumption in causal inference. The Annals of Statistics, pages 436-463, 2013. [Cited on 3.J
[122] B. Varici, E. Acarturk, K. Shanmugam, A. Kumar, and A. Tajer. Score-based causal represen- tation learning with interventions. arXiv preprint 0rXiv:2301.08: 08230, 2023. [Cited on p. 3, 5, 7, 8, 10, and 21.]
[123] J. von Kügelgen, Y. Sharma. L. Gresele, W. Brendel, B. Schölkopf. M. Besserve, and F. Lo- catello. Self-supervised learning with data augmentations provably isolates content from style. In Advances in Neural Information Processing Systems, volume 34, pages (6451-16467, 2021. [Cited on p. 8, 10, 20, and 21.]
[124] Y. Wald, A. Feder, D. Greenfeld, and U. Shalit. On calibration and out-of-domain generaliza- tion. Advances in Neural Information Processing Systems, volume 34, pages 2215-2227, 2021. [Cited on p. 20.]
17

---

[125] Y. Wang and M. I. Jordan. Desiderata for representation learning: A causal perspective. arXiv preprint arXiv:2109.03795, 2021. [Cited on p. 3. 20, and 21.]
[126] L. Wendong, A. Kekić, J. von Kügelgenn, S. Buchholz, M. Besserve, L. Gresele, and B. Schölkopf. Causal component analysis. Advances in Neural Information Process- ing Systems, 2023. [Cited on p. 7, 8, 9, 10, and 20.]
[127] Q. Xi and B. Ridem-Reddy, Indeterminacy in generative models: Characterization and strong identifiability. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, volume 206. PMLR, 2023. [Cited on p. and 4.]
[128] F. Xie. R. Cai, B. Huang. C. Glymour, Z. Hao, and K. Zhang. Generalized independent noise condition for estimating latent variable causal graphs. In Advances Neural Information Processing Systems, volume 33, pages 14891-14902, 2020. [Cited on p. 20 and 21.]
[129] F. Xie, B. Huang. Z. Chen, Y. He, Z. Geng, and K. Zhang. Identification of linear non- gaussian latent hierarchical structure. In International Conference on Machine Learning, pages 24370-24388 PMLR, 2022. [Cited on p. 20 and 21.]
[130] M. Yang, F. Liu, Z. Chen, X. Shen, J. Hao, and J. Wang. VausalVAE: Disentangled representa- tion learning via neural structural causal models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9593-9602, 2021. [Cited on p. 20.]
[131] Yao, D. Xu, S. Lachapelle, S. Magliacane, P. Taslakian, G. Martius, J. von Kügelgen, and F. Locatello. Multi-view causal representation learning with partial observability. arXiv preprint arXiv:231 1, 1,0055, 2023. [Cited on p. 10.]
[132] W. Yao, Y. Sun, A. Ho, C. Sun, and K. Zhang. Learning temporally causal latent processes from general temporal data. In International Conference on Learning Representations, 2021. [Cited on p. 20.]
[133] W. Yao, G. Chen, and Zhang. Temporally disentangled representation learning. In Advances in Neural Information Processing Systems, 2022. [Cited on 20.]
[134] F. M. Zennaro. Abstraction between structural causal models: review of definitions and properties, arXiv preprint arXiv:2207.0800 086603, 2022. [Cited on p. 20.]
[135] F. M. Zennaro. M. Drávuez, G. Apachitei, W. D. Widanage, and T. Damoulas. Jointly learning consistent causal abstractions over multiple interventional distributions. In 2nd Conference on Causal Learning and Reasoning, 2023. [Cited on p. 20.]
[136] J. Zhang, K. Greenewald, C. Squires, A. Srivastava, K. Shanmugam, and C. Uhler. Identifia- bility guarantees for causal disentanglement from soft interventions. In Advances in Neural Information Processing Systems, 2023. [Cited on p. 10 and 20.]
[137] Zhang and A. Hyvärinen. On the identifiability of the post-nonlinear causal model. In 25th Conference on Uncertainty in Artificial Intelligence, pages 647-655. AUAI Press, 2009. [Cited on p. 7.]
[138] K. Zhang. J. Peters, D. Janzing, and B. Schölkopf. Kernel-based conditional independence test and application in causal discovery. In 27th Conference on Uncertainty in Artificial Intelligence, pages 804-813. AUAI Press, 2011. [Cited on p. 9.]
[139] Zheng, B. Aragam, P. Ravikumar, and Xing. DAGs with no tears: Continuous optimiza- tion for structure learning. In Advances in Neural Information Processing Systems, volume 31, 2018. [Cited on p. 10.]
[140] X. Zheng. C. Dan, B. Aragam, P. Ravikumar, and E. Xing. Learning sparse nonparametric dags. In International Conference on Artificial Intelligence and Statistics, pages PMLR, 2020. [Cited on p. 10.]
[141] S. Zimmermann, Y. Sharma, Schneider, M. Bethge, and W. Brendel. Contrastive learning inverts the data generating process. In International Conference on Machine Learning, pages 12979-12990. PMLR, 2021. [Cited on p. 2.]
18

---

Appendices
Table of Contents
A Extended Discussion of Related Work
20
A.1 Comparison of Related Identifiability Results
20
B Proof of Minimality of the CRL Equivalence Class m-e..
22
Identifiability Proofs
23
C.I Auxiliary Lemmata
23
C.2 Proof of Thm. 3.2
................................
24
C.3 Proof of Thm. 3.4
29
C,4 Proof of Thm. 4.2
31
Experimental Details and Additional Results
33
Experimental Details for
33
D.2 Additional Results: Learning Nonlinear Latent SCMs from Partial Causal Order
34
E Discussion of the Role of Our Assumptions
36
19

---

A Extended Discussion of Related Work
Prior work on causal representation learning with general nonlinear relationships (both among latents and between latents and observations) and without an explicit task or label typically relies on some form of weak supervision. One example of weak supervision is "multi-view" data consisting of tuples of related observations. von Küggelgen al. [123] consider counterfactual pairs of observations arising from imperfect interventions through data augmentation, and prove identifiability for the invariant non-descendannss of intervened- upon variables. Brehmer et al. [18] also use counterfactual pre- and post-intervention views and show that the latent SCM can be identified given all single-node perfect stochastic interventions. Another type of weak-supervision is temporal structure [2], possibly
combined with nonstationarity [132, 133], interventions on known targets [80, 8 81], or observed actions inducing sparse mechanism shifts [74, 75, 110]. Other works use more explicit supervision in the form of annotations of the ground truth causal variables or a known causal graph [111, 126, 130].
A different line of work instead approaches causal representation learning from the perspective of causal discovery in the presence of latent variables [115]. Doing so from purely observational the
i.i.d data requires additional constraints on the generative process, such restrictions graph structure or particular parametric and distributional assumptions, and typically leverages the identifiability of linear ICA [27, 38, 79]. For linear, Gaussiasn models, Silva et al. [113] show that the causal DAG can be recovered up to Markov equivalence if all observed variables are "pure" in that they have unique latent causal parent. Cai et al. [23] and Xie et al. [128, 129] extend this result to identify the full graph given two pure observed children per latent, and Adams et al. [1] provide sufficient and necessary graphical conditions for full identification. For discrete causal variables, Kivva et al. [68] introduce a similar "no twins" condition to reduce the task of learning the number and cardinality of latents and the Markov-equivalence class of the graph to mixture identifiability.
Other lines of work have investigated the relationship between causal models at different levels of morse-graining or abstraction [6. 11, 12, 24-26, 35, 105, 134, 135], or learning invariant represen- tations in a supervised setting [3, 8, 32, 33, 73, 86, 92, 124, 125], often for domain generalization.
Other concurrent works address, e.g., learning from soft interventions with polynomial mixing [136], or inferring both causal graph and the number of latents subject to graphical constraints [63].
A.1 Comparison of Related Identifiability Results
To complement the presentation of related multienvironment CRL works in $ 1, we provide a structured overview of and comparison with existing identifiability results for causal representation learning in Tab. 1. The table categorizes work along different dimensions. First, we make distinction based on the type of data (observational, interventional, or counterfactual) results rely on (colour coded in green, yellow, and red, respectively). These are also referred to different rungs in the [97] or layers in the Pearl Causal Hierarchy [10]. Second, we categorize work depending on the assumptions placed on the latent causal model and the mixing function. As can be seen, works relying solely on observational data often require restrictive graphical assumptions on the mixing function. On the other hand, access much more informative counterfactual data has allowed identification even for nonparametric causal models and mixing functions. Our work can be viewed as step towards addressing the lack of nonparametric identifiability results in the interventional regime.
"ladder of causation"
We emphasize that Tab. is not exhaustive: certain relevant works did not casily fit into our catego- rization or the causal representation learning framework adopted in the present work. For example, not listed are works that leverage temporal structure [2, 74, 75, 80, 81], rely on heterogenous data and distribution shifts which are not directly expressed in terms of linked to interventions [82, 132, 133], allow for edges from observed to latent variables [1], or require more direct supervision [111, 130].
20

---

Table Comparison Existing Identifiahility Results for Causal Reresentation Learning. the listed works assume invertibility (or injectivity) of the mixing function, as well as causal sufficiency (Markovianity) for the causal latent variables. Most all of the listed results require additional technical assumptions. and may provide additional results, which omit for sake of readability: the references for more details.
Work
Layer
Causal Model
Mixing Function
Main Identifiability Result
linear with Gaussian noise s.t. each V2 has pure (obs, unobs.) children
Cai [23], Xie al. [128, 129]
observational
linear, non- non-Gaussian
numher latents
indentifiable mixture model s.t. obs. children of V; g ohs. children V;
number, cardinality dist. of dis- crete latents + G up Markow equivalence
Kivva al. [68]
observational
discrete, nonparametric
Abuja et
[S.
observational
nonlinear w. indepen- dent support (103, 125)
finite dettee polynomial
up to permutation, shift, linear scaling
Thm. 4]
G and V up partial order preserv- ing permutations from obs. dist. all single-node perfect interveations
Squires et [117, Thms. &]
interventional
linear
linear
up transitive closure from dist. & all single- node imporfect in- terventions
Squires et al. [117, Thm. 1]
interventional
linear
Tinear
and V up partial order preserv- permutations from ohs. dist. all single-node perfect interventions
Varici et al. [122, Thm. 16]
interventional
nonparametric
linear
V up to permulation, shift, and lin- ear scaling from single node per- feet hard interventions
Ahuja al. [S. Thm. 2]
interventional
nonparametric
finite degree polynomial
G and V up to permutation from obs. dist, & all single node perfect interventions
Buchholz al. [22]
interventional linear Gaussian
nomparametric
This
for 2: G and from all single-node perfect inter- ventions, subject to genericity (3.2)
rea.
interventional
nonparametric
nonparametric
Work (Thm. 3.2)
This
up rem. tinct, paired single-node perfect in- terventions per node
Work (Thm. 3.4)
interventional
nonparametric
nonparametric
block non-noneeee descendannss Vadezy up invertible function from fat-hand imperfeet interveations en Vi
von Kügelgen al. [123]
counterfuctual
nonparametric
nonparametric
G and V up <ea. from all single- node perfect interventions
Brehmer al. [18]
comnterfactual
nonparametric
nonparametric
21

---

B Proof of Minimality of the CRL Equivalence Class CRRL
First, let us recall the main statements from $ 2.2.
Definition 2.6 (~ecu--dden -ianniddiiiifibiittyy, Let H be space of unmixing functions h X IR" and let g be the space of DAGs over n vertices. Let -CRL. be the equivalence relation on H. x 9 defined as
(h1, G1) MCRL (h2, G2)
=
(h2, G2) = P h1 (G1))
(2.3)
for some element- diffeomorphism d(v) = (01 (01),.... ................................ On (vn)) of R" and permutation of [n]] such that π : G1 H G2 is a graph isomorphism and 77 the corresponding permutation matrix.
Proposition 3.1 (Minimality of MERLi informal). Let Z be any representation that is ~ORL equivalent to V, with G' = (G) the associated DAG. Then for any intervention on VI S V in G, there exists an equally sparse intervention Zx(I)= S Z in G' inducing the same observed distribution on X.
We now restate this result more formally.
Proposition B.1 (Minimality of rcu)). Let (h, G") MCRL (f" with denoting the graph isomorphism mapping G to G' (i.e., a permutation that preserves the partial topological order of G). Let Z = (X) be the inferred representation with distribution Qz (Px)) Markov w.r.t. G' and associated density q. Let I C [n]] denote a sel of intervention targets, and consider an intervention that changes pe(us] ppp(() some intervened mechanism (r( Upa(s)) for all Ie, giving rise to the interventional distributions Py and P = (PV).. Then there exist appropriately chosen Tott) (ato((z()) (Zx(s) Epa(a(0),r)) ) for E I such that the resulting interventional distribution Oz gives rise to the same observed distributions, that is, Px = 1x= (Q%).
Proof. Since (h, G¹) MCRL (f-1, G), by Defn. 2.6 we have = P o (VV)
(B.1)
for some clement-wise diffeomorphism with inverse sb =6- Then (B.1) implies that for all
i [n]
V = (1(2
(B.2)
According to (B.2), each conditional in the Markov factorization of Qz is given in terms of by
(x(1) (x(()) =pa()(())))) pi tha (2x(3) p/ppt) (spatr(()))))
du
(zn(()
(B.3)
dza(e)
where we have used the change of variables in (B.2) and the fact that क (pa(1)) = pa( (i); G') since G G' is graph isomorphism.
Consider an intervention that changes p. (. Upa(t) to some intervened mechanism (v ppa(s) for all i E Z Denote the corresponding intervened joint distribution by Pe with joint density p given by
(v)
II SEZ*
pi (F Upa(t)
II jE[m](Z=
Pj
(B.4)
Denote by O7 = (Pa-1 1 o ()) the corresponding distribution over with joint density given by dºd of (2) = (1b o P. (z)) /det J.oP.
(B.5)
II Pi 4/ (mr())) (pp(t) (2p0))(02000))
du's dzz(1)
(t{())
II jE(m](zz
gm(i)
(zx(s)
(B.6)
where we have used (B.3), (B.4), and the fact that J. is diagonal. By defining
(n(1) (#x(0) =pa(7(0):0)) = (yr (zx(o) I (ppa(() (=20))(10:011)
di d2z(()
(2x(1)
(B.7)
22

---

we finally arrive at
oe (z) This shows that any intervention on {Vitiet C V which replaces
II RE
(m(1)
(an(i)
)pats())cr))
pm(i) (2r()) =pa(a():on)) jE/n|/z
II
(B.8)
(p:(o: (pa(t))
REI* + (pi(vs) mpa(t)) iez
(B.9)
can equivalently be captured by intervention on (iEE) S Z which replaces
{ ( (x)()) (
+ { (m(()) (2x0)) I xmato())0))
(B.10)
iEze
iEI
with q: defined according to (B.7).
C Identifiability Proofs
C.1 Auxiliary Lemmata
Lemma C.1 (Lemma 2 of Brehmer et al. [18]). Let A= C = R and B = RR. Let f: A B C be differentiable. Define two differentiable measures PA on A and pc on C. Let vb B, f(,,b): A + C be measure-preseeringg in the sense that the pushforward of PA is always Pc- Then
f(;bb) b) constant in b on B.
Proof. See Appendix A.2 of Brehmer et al. [18].
Lemma C.2 (Preservation of conditional independence under invertible transformation.). Let and Y be continuous real-valued random variables, and let Z be continuous random vector taking values in TR. Suppose that (X,Y Y, Z) have a joint density w.r.t. the Lebesgue measure. Let f - R,
9: R R. and h R - IR" be diffeomorphisms. Then X YY| Z = f(X) 1 g(Y) [Z).
Proof. Denote by p(r,3) y. 2) the density of (X, 2). Then 1 Y Z implies that for all (x, y, =). p can be factorized as follows:
p(. 2) = (=(=))))_()) 2), =2).
(C.1)
Let (A, B) = (f())) (2)). and write f= = f- = g g- and h-1
Then (A, B, C) also has density ((a, b, c). which for all (a, b, c) is given by the change of variable formula:
df dğ da (a)
a(a, b, = (p (f(o). Me))
det Ja(c)
(C.2)
ab
=p= [(()) det [c)c) Pe (f(a) M(e)
a5 (a) Pv (o(b) M(e) db
dg
(b)
(C.3)
da
where in (C.2) we have used the fact that (X, Y, Z) + ((Y)))))))))))) (Z)) has block-diagonal Jacobian, and in (C.3) that p factorises as in (C.1). Next, define
gc(c) P= (n(e))
|det J [c)]
(C.4)
d$
ga (a c) = Px. ((a)) h(c))
(a)
(C.5)
da
dg
(b c) = Pv (x(6) h(c))
(b)
(C.6)
Since Pz, Pz. and Py are valid densities neon-iegative and integrating to one), so are ge, qa, and qb-
Substitution into (C.3) yields for all (a, b, c),
q(a, b, c) ge (a(c)aa(a cb c),
(C.7)
which implies that A 1 B C, concluding the proof.
23

---

C.2 Proof of Thm. 3.2
Theorem 3.2 (Bivariate identifiability up to ~CRL from one perfect stochastic intervention per node). Suppose that we have access to multiple environments {Px beee generated as described in $ under Asms. 2.2, 2.5, 2.8 and 2.9 with = 2. Let (h, G') ) be any candidate solution such that the inferred latent distributions 2z h_(P)) of Z h(X) and the inferred mixing function h-1 satisfy the above assumptions w.r.t the candidate causal graph G'. Assume additionally that
(AI) all densities p" and qe are continuously differentiable and fully supported on R";
(A2) we have access known observational environment Eg and one single node perfect interven- tion for each node, with unknown targets: there exist n++1 environments & = {e such that To Ø and for each i [n] we have I (i)) for unknown permutation π of [m]:
(A3) for all i E [n], the intervened mechanisms pe(vs) differ from the corresponding base mechanisms Pi(Ui] ppa(() everywhere, in the sense that
0
(v))
Yo
Ou; P;(0; Upa(t) + 0:
(3.1)
(A4) ("genericity") the base and intervened mechanisms are not fine-tuned each other, in the sense that there exists continuous function yp R- - R for which
(22222 vn (()
B2(U2)
[ (0/ (2222))
ppl(2 m1)) (m1
+ E Eowey
(3.2)
Then the ground truth is identified in the sense of Defn. 2.6, that is, (f) G) MeR. (h, G').
Proof. From the assumption of a shared mixing f and shared encoder across all environments, we have that
Z h (X) h(f(V)) o f(V).
(C.8)
Let v/ = 1--hh- RR" RR such that
V= (Z).
By Asm. 2.5, f. h, and thus also h o f are diffeomorphisms. Hence, v is well-defined and also diffeomorphic.
By the change of variable formula, for all and all z the density (x) is given by
(x) = (vb(2) det (z))
(C.9)
where (J+(z))
Bii (z) denotes the Jacobian of vb.
Dey
We now consider two separate cases, depending on whether the intervention targets in g for e E [ei,e2) match those in p (Case 1) not (Case 2).
Case Aligned Intervention Targets. According to Asm. 2.8 and (A2), (C.9) applied to the known observational environment eo and the interventional environments C1 e2 leads the system of equations:
a (=1)g2(<> )pa(2;0r) = pi (1)())) p2 (12(2) Vipa22) (z)) det (z)]
(C.10)
ã (222))(22 ?pa(2;0')) p1 (v)()) p2 (12(() (z) 4pp(22) (z) det J (z)
(C.11)
ai (21)2(22)) Pi (x) D2 (v>(=)) det J (z)
(C.12)
where 2pa(2;0P) denotes the parents of in G². and pa(2) denotes the parents of V2 in G.
Note that neither side of the previous equations can be zero due the full support assumption (A1) and a being diffeomorphic implying the determinant is non-zero.
This also be relaxed fully supported Cartesian product of intervals.

---

Taking quotients of (C.11) and (C.10), yields
p1
(21)
(1)(
(C.13)
q1
pi
Next, we take the partial derivative w.r.t. 2g on both sides and use the chain rule to obtain:
P1
dui (z).
(1b1 (z))
(C.14)
022
Now, by assumption (A3), the first term on the RHS of (C.14) is non-zero everywhere. Hence,
0uh (z) 0.
(C.15)
O22
follows that vi is, fact, a scalar function, and
Vi 1/ (Z1).
(C.16)
Since & is a diffeomorphism, e1 must also be diffcomorphic. Hence, by the change of variable formula applied to (6, the marginal density 21 (21) is given by
J4h1
(x)) = pi (11((21))
(21)
(C.17)
Further, since Ju is triangular due to (C.15), its determinant is given by
0v
0222
dett Jo [=) =
(=1)
(=1, 22)
(C.18)
021
Oz2
Substituting (C.17) and (C.18) into (C.12) yields (after cancellation of equal terms):
O2/2
(2() = P2 (12(211 (2))
(21 22)
(C.19)
0z2
The expression in (C.19) implies that, for all 21, the mapping 4/2 (2)
R + R is measure
preserving for the differentiable Ø2 and P2. By Lemma C.1 (Lemma 2 of Brehmer et al. [18, A.2)). then follows that 2he must, in fact, be constant in 21, that is
Ouh2 (z) = 0.
Vz:
(C.20)
0z1
Note that this last step where the assumption of perfect interventions (Asm. 2.9) is leveraged: the conclusion would not hold for arbitrary imperfect interventions for which (3.8) would involve (2 21) and P2 (1/2 #2) th (21)).
Hence, we have shown that vb is an element- wise function:
(V1, 1/2) v () (#1(Z1), (2) (Z2))
(C.21)
Finally, since a diffeomorphism, (C.21) implies that
Vi T 1/2 > Zi 1 22.
(C.22)
then follows from the faithfulness assumption (Asm. 2.2) that we also must have G G².
This concludes the proof Case 1, as we have shown that (h, G') ~CRL (f-1, G) with G' = (G) G (ar being the identity permutation) and h c f = .- =: ø an element-wise diffeomorphism.
Case 2: Misaligned Intervention Targets. Writing down the system of equations similar to (C.10) but for the case with misaligned intervention targets across p and yields:
a (x1))2(222) ())(2)0)) = P1 (V1 (z)) p2 ((2(z) (2)) ddct (x)
(C.23)
ă (21)92(22 (2m((200)) = Pi (Vi (=)) Do (1)(2)) |det Jos (z)
(C.24)
sn (=1))2(22) -i (=)) pa (=))=) (ppce) del [x)
(C.25)
25

---

Taking ratios of é1 and 62 with yields
P2 (z))
21
(C.26)
(2(2)) ()p((2)(2)
P2
02 22
P1 (wi (z))
(C.27)
(2 =pa(2.G)))
P1
We separate the remainder of the proof of Case into different subcases depending on G and G': as we will see, we can use a similar reasoning as Case 1, except for the case where both and G' are missing no edge.
Case 2a V1 A V2 G, that pa(2) 2. Then we can proceed similarly to Case 1. First, we take the partial derivative of (C.26) w.r.t. 22 to arrive at:
P2
(1))
04' (z).
(C.28)
0z2
Using (A3), this implies that V2 does not depend on Zz, that is, 1/2 = (21).
Next, again write ((11) in terms of p2 (2)) using the univariate change of variable formula, substitute into (C.25), cancel the corresponding terms, and arrive at:
(2(22) = pi (2) 22))
(z1, x2)
(C.29)
8z2
Lemma C.I applied to th (z), which preserves ū2 and p1 for all ž shows that ti is constant in Z1, that
(V1, (Z) (Z2( (Z1))
(C.30)
Since Vi 1/2 by the assumption of Case 2a, it follows from the invertible element-wise reparametrisation above that Zı 1 Zz and hence, by faithfulness, Z1 A Zz in G'.
Finally, note that there is no partial order the empty graph and G' = G and Z = P +6 (VV) where π is the nontrivial permutation of {1,
Case 2b: Vi 1/2 in G, that is pa(2) = {1}. Gf + G. that is Z1 A Z2 in G", then the same argument as Case 2a, this time starting by taking the partial derivative of (C.27) w.r.t. 21, can used to reach the same conclusion in (C.30). However, this contradicts faithfulness since V1 A. V22 in G.
Hence, we must have G' G. and the following two equations must hold for all 2:
71 (21)
Du (1>2(z))
(C.31)
Q1 (21)
P2 (#2(2)) (2))
To (22)
Pi (wi (z))
(C.32)
Q2 (22
21)
Pi (z))
The remainder of the proof consists of exploring the implications of (C.32) and (C.31), ultimately resulting in a violation of the genericity condition (A4).
To ease notation, define the following auxiliary functions:
a(=1) = T1 (21)
(C.33)
@n (21)
b(v) = (2(U2)
(C.34)
P2(U2 v1)
c(x) = (x2)
(C.35)
22 (22 (1)
P1 (v1)
d(v1)
(C.36)
Pi (v1)
26

---

With this, (C.31) and (C.32) take the following form:
a(z1) (()(2)))
(C.37)
c(z) = (z)),
(C.38)
Next, define the following maps:
a((1) )
R:2
c(z)
(C.39)
b(u)
p:v-
d(v1)
(C.40)
Then, (C.37) and (C.38) together imply that
K po...
(C.41)
Recalling that by (A1) all densities are continuously differentiable, the Jacobians of and are given by:
(=1
Jn(z)=
Bc
(z)
de
(C.42)
U52
Ov (v)
(v)
(z(D)
8112
(C.43)
d((e1)
and the corresponding determinants are given by
dc
dett J=(
a' (z(21)
O22 (z)
#
(C.44)
ab
det J,(w)) d' (wr
(v)
#0
(C.45)
O0z
where the inequalities for all z follow since, by assumption (A3), the derivatives ratios of intervened and original mechanisms are non-vanishing everywhere:
dc
ab (v),
a' (21) # 0
and
d'(u1) 0
(C.46)
Oz2
Ouz
This implies that the following families of maps continuously differentiable, monotonic, and invertible,
21 a(21), bn 02 + b(11, W2)
(C.47)
(C.48)
ca 22 c(21, #2),
(C.49)
d: 12 + d(vi).
(C.50)
with continuously differentiable inverses
W1 a (wr)
(C.51)
b Wi by (wi)
(C.52)
c W2 c (w2) d
(C.53)
We + d' (w2).
(C.54)
This implics that and i are valid diffcomorphisms onto their image and their inverses are given by:
a (wi)
K
8 (wz) (w2)
(C.55)
d 1 (w2z)
(C.56)
b b (w-))))) (wi)
27

---

Since V = (Z), by (C.41) we have
W (V) po (Z) k(Z).
(C.57)
Denote the distributions of W by Rw and its density by r(w). Since for all e, have
PV (Qz)
(C.58)
follows from (C.57) that
Rw = (. (Qz))
(C.59)
This provides two different ways of applying the change of variable formula compute r(w). First, we consider the pushforward QZ by n:
r(w) q x (w)) |et JN (w))
(C.60)
= qi (w1)) 92 (5= (w22 a (w1))
d
a (mn) d
duz (w))
(C.61)
dw
By integrating this joint density with respect to w2, we obtain the following expression for the marginal rı (ww)::
d a (w)) a1 (w=(w)) / 92 (5= ((w)) (wz) | a (w1)) dw
d
(1(1))
c ((w)) (wz) dw2
duo
(C.62)
By the diffeomorphic change of variable
22 ca ((w1) (wz). 13 this can be written as (we)
d a a-
ạ (a (w=) f 92 (22 a a dz2
ri (w))
(C.63)
dwj d a -a-1(ss) (wi) Q1 (a (a=)
(C.64)
dw3
Next, we earry out the same calculation for the pushforward of poe by pt
r(w) p (p (p-'(w)
(w)) ddet Jp-1 (ww)
(C.65)
P1 (d (wz)) p2 (w2)) (wz) d ((ww))) d d (wx)
d
duc dwj b (wg) (wn)
(C.66)
leading to the marginal
ri (w()) = / pi (d- (w2)) p2 (wn-( | d'' '(w2))
d -ー- (w)) d d (w2) dw2
dwn
duz
(C.67)
= f p/ (wr) | 01)
d
b (Wz) den,
de1
(C.68)
dw
where the second line is obtained by the diffeomorphic change of variable i1 d d (wz). Equating the two expressions for r(w1) in eo (C.68) and (C.64), we obtain for all w1:
(wm1) (a-(ww)) -f Pi (vi)p2 (w)) 0i
dw b (wi) del.
(C.69)
dw
Applying the same approach to the environment in which Vi is intervened upon changing to Pi while Ze is intervened upon leaving qı invariant, yields for all wi:
a (wr) qi (a (o=))w)) = pr (12))) (wr( vi) dw
o (w)) dug
(C.70)
dwi
Note that: f (2(22(102)
dza desz
dwz2 = f (2() d22.
28

---

Finally, by equating (C.69) and (C.70), we arrive at the following expression which must hold for all wi:
f pi(u))p (Dr) (wr) vi)
d dwc
dub b,, (wr))
(i((o))22 (bzi (w1)
vi) d dwn
bb (wi)
dei (C.71)
which we rewrite as
/ (bi(v1) prlt)) P2 (bz) (brr((w)) | 01) deo
- ". du 0.
(C.72)
Multiplying by any continuous function p(w1), integrating w.r.t wi and applying the diffeomorphic change of variable 2/2 = byy (wi), this can be expressed as:
0 = ((mr)) / (0i()1) (1())) (w)) I mi) dwo
byg (w1))
dui dwi
(C.73)
= = (Den (12)) (pi(01) - pi (1())) p2(02 vn) du2
(C.74)
/ / ( P2(12)
U1 duz dej (2(U22 I vi)) (f1(11) (11( p2(02
(C.75)
where we have resubstituted the expression for b (U2) in the last line. Equivalently, this can be written as: for any continuous function yp,
P2(02 m1) )
D2 (222
P2 (2))
s0
E Pij
(C.76)
(2(122
U2/ Un
However, the genericity condition (A4) precisely rules this out, since the above equality must be violated for at least one sp, concluding this last case.
To sum up, all cases either lead to contradiction, or imply the conclusion that (f-1,G mORL (h, G'), concluding the proof.
C.3 Proof of Thm. 3.4
Theorem 3.4 (Identifiability up to ~CRL from two paired perfect stochastic interventions per node). Suppose that have access multiple environments {P'x Jeee generated as described in $ under Asms. 2.2, 2.3, 2.5, 2.8 and 2.9. Let (h, G') be any candidate solution such that the inferred latent distributions Q2 h, (Px)) of Z = (( and the inferred mixing function h satisfy the above assumptions w.r.t. the candidate causal graph G". Assume additionally that
(AI) all densities of and of are continuously differentiable and fully supported on R";
(A2') we have access to least one pair of single-node perfect interventions per node, with unknown targets: there exist m 2 n known pairs of environments & = [((e, (eee,ee))1 ef)) such that for each
E [n]] there exists some unknown j E [m] for which I =I (i}:
(A3') for all i [n), the intervened mechanisms P: (1;) and Pr(vz) differ everywhere, in the sense that
P1 p.
Yug :
(v.)
#
(3.10)
Then the ground truth is identified in the sense of Defn. 2.6, that is, (S-1,) ~em. (h, G').
Proof. First, we show that we can extract from the m 2 n available pairs of environments a suitable subset En of exactly n pairs, containing pair of interventional environments for each node.
Let &n C be a subset n pairs of environments which are assumed to correspond to distinet targets in the model and suppose for a contradiction that this is not actually the case for the ground truth p (i.e., there are duplicate and missing interventions w.r.t. p). Then there must two pairs of environments (c., e,), (es. e6) E,. both corresponding to interventions some V, in p, but which
29

---

are modelled as interventions on distinct nodes 2, and 2% with - l: in 9. We show that this implies that V must simultaneously be deterministic function of only Zz and only Zg. Similar to the proof of Thm. 3.2, we obtain the following equations,
i
Pi (v:(z))
(C.77)
i
Pi
is
Pi
(2k)
(v)(z))
(C.78)
U
By taking partial derivatives w.r.t. 22 and applying assumption (A3'), we find that
0
(C.79)
Zz
VI + k.
(C.80)
221
Since & k, this implies that 0 0 for all which contradicts invertibility of sb Thus. by contradiction, we find that E,, must contain exactly one pair of intervention per node also w.r.t. p. For the remainder of the proof, we only consider En.
W.l.o.g.. for any (ei, e() E E,, we now fix the intervention targets in to I = I = {i} and let π be a permutation of [n]] such that (i( denotes the inferred intervention target in that by (A2') is shared across (e;, et)) (We will show later that not all permutations are admissible, but only ones that preserve the partial order of G.)
The first part of the proof is similar to Case in the proof of Thm. 3.2. Consider the densities in environments ej and e,, which are related through the change of variable formula by:
(a(t) (xx())
II JE(m)((())
Øi (zj =pa(t:cr) Pa (17(2))
II JEMIN(
Pj (15(2) (pa(s)(2)) det Jx(2))
(C.81)
(a())
(x(())
II Øj (351 (pa(sio)) (17(2))
II JE(M)(()
Ps (15(2) (pacs)(z)) det J Jz)
(E(M]M((i)
(C.82)
where p S Z {Zz) denotes the parents of Zj in G². Taking the quotient of the two equations yields
In(()
D: (V:(z))
(x(())
(C.83)
Next, for any j + (1), taking partial derivatives w.r.t. 2j on both sides yields
0
Pa
(z)(
Ou (z).
(C.84)
p
Ozy
By assumption (A3'), the first term on the RHS is non-zero everywhere. Hence, (C.84) implies
Oui θzj
Vj x(), Vz
(z)
0
(C.85)
from which we can conclude that
V = t/s
(C.86)
for all E [n]. That is, ub is the composition of the permutation म with an element-wise reparametri- sation.
remains to show that n must, in fact, be graph isomorphism, which is equivalent to the statement
V1 in G
Zx(0) + Zn(G) in G².
(C.87)
30

---

Suppose for a contradiction that there exist (i.j) such that V + Vj in G, but Za(e) A ZT(i)
in G".
The main idea is to demonstrate that the lack of such direct arrow implies certain conditional independence which, by faithfulness, would contradict the unconditional dependence of V; and Vj.
Consider environment e; in which there are perfect interventions on Za(ii and V,, which has the effect of removing all incoming arrows Zz(1) and V, in the respective post-intervention graphs and Gv. C² Z7-0
As result of this and the lack of direct arrow by assumption, any d-connecting path between Zx(i) and Z))) must enter the latter via pa(x()): [95].
It then follows from Markovianity of w.r.t. G' that the following holds in Q2:
(i) 1 Zx() pa(
(C.88)
We now consider the corresponding implication for PV. Define
V V& the (Zmlk)) Zm(k)) mmattsiion CV (V, (V)
(C.89)
and note that by assumption, (z))) & pa( and hence Vi & V. By applying the corresponding diffeomorphic functions 1/ from (C.86) to (C.88), it follows
from Lemma C.2 that
Vi T Vg IV
(C.90)
in Pe. However, this violates faithfulness (Asm. 2.2) of Py since VÚ and Vj are d-connected in Gv.
Thus, by contradiction, we must have (z(s)= - Za(j) in G'.
(+) Now, suppose for contradiction that there exist (i such that Zz(1) ZN() in G², but Vi A Vy in G.
By the same argument before, find that
Vi ll V3 Vpa())
(C.91)
in P and thus by Lemma C.2
Zm()) mn(s) 2
(C.92)
in Q% where
2 z= = Zm(k))
V& Vpa()) } C Z (Z)) Z=01
However, this contradicts faithfulness of Qz to G'. Hence, we must have that V4 Vú in G. This shows that n must be graph isomorphism, thus concluding the proof.
C.4 Proof of Thm. 4.2
Theorem 4.2 (Preservation of causal influences under r.c.).. Let Pv be Markovian w.r.t. G, let be a graph isomorphism of G, and let é be an element wise diffeomorphism. Let Z P- o (VV) and denote its induced distribution by Qz. Then for any V - Vj in G we have C-jj = Oz
-x()
Proof. First, recall that according to Defn. 4.1,
cht; = DEL (Pv P(7))
(C.93)
where pi-s denotes the interventional distribution obtained by replacing PA ij (paci) with
pj (1, (pa())))) Py (,(2,, (paatt) (pans)))((3)))) du;
(C.94)
31

---

Writing out the KL divergence and noting that all terms except the interved mechanism j cancel inside the log, we obtain
Pj (os (ppai))
Ps Upa(s) Upacs))p((e)) deg 1108 log
ple)
(C.95)
and similarly
(x(1) (Za(s) =pa(n(s)io))
cZ (1))+)(()) = =/2 log
(()) (C.96)
Szees (+(1) (z+(5) ( (=(()) (2x(0) dzn(()
Since Z = P OVV), we have V, the (Z))) for all E [n] where & = 6-1
Thus, by the change of variable formula, and using the fact that (pa(ii) pa( G') since T: - G' is graph isomorphism, we have for all i E [n]]
(=(1) (Za(t) #pa(=()):0)) (u0k (2<()) e/ppat)) (fmat)(0))0)))
duA
(2n(s))
(C.97)
dzz(1)
as well as for the marginal density
(m())) (2<13) = ps s/s (2xcs)
di's
(37(3))
(C.98)
dzz(s)
and
g(z) p(u Px(2)) ddt Jo
(C.99)
Substitution into the expression for 8Z2 (())- yields:
bb (2+(1)) ('patt)) (ipal) (Epu(=)):c)))
Pj
692 ((())x(())
log
S2,co Pj (15((+(6) v/p(t)) (2p((((1:0))) pi p:(tv(Z=(1))
deh
(2m(0)
dzz(1)
d=.
(C.100)
plu (z)) |det (z) dz.
(C.101)
Pj Ug upali)
/ log
p(v) do
(C.102)
Jvs Py (wy Upa(s)) (1:) dey
(C.)03)
where the second to last line follows by integration by substitution, applied to both integrals.
32

---

D Experimental Details and Additional Results
In this appemndix, we describe the experiments presented in 6 in more details (Appx. D.1), and present additional results (Appx. D.2).
D.1 Experimental Details for $ 6
Synthetic Data Generating Process.
We consider linear Gaussian latent SCMs of the form
V/2 = aV1 + U2, with standard normal U1 and U2. As mixing function, (MLP),
V := U1,
(D.1)
three-layer multilayer perceptron
/ W W W1
(D.2)
where W1, 22, W3 x2x are invertible weight matrices, and a is an element- wise invertible nonlinear leaky-tanh activation function used in [41]:
(σx) tanh(x) 0.1r
(D.3)
To compute averages of our results over multiple runs, we construct different ground truth data generating processes as follows. We generate different latent SCMs by drawing a uniformly from [-10,-2] [2, 10). (We exclude (-2, 2) to avoid sampling near unfaithful models.) We generate the corresponding mixing functions by uniformly sampling each element of the weight matrices, (Ww),, ~ (0, 1). (To avoid the sampled weight matrices being too close to singular, we reject and resample if |det W < 0.1.)
Interventional Environments. In line with Thm. 3.2, for each choice of latent SCM and mixing function, we generate three environments: one observational environment and one interventional environment for each perfect single-node intervention. For i 1,2, we model a perfect intervention on Vn2 by removing the influence of the parent variables and changing the exogenous noise by shifting its mean up or down. Specifically, we replace the corresponding assignment (D.1) by
V Üs where Ü, ~ ((m,, 1)
(D.4)
where the mean m. of the shifted Gaussian noise is fixed per environment and sampled uniformly from (+
We label the observational environment as e = 0 and the environment arising from intervention on Vi by e i for i = 1, 2. Samples from ye are then generated by sampling latents from the respective (un)intervened SCM and then applying the mixing function.
Model Architecture. We use normalizing flows [93] to model observations as the result of an invertible, differentiable transformation y of some latent (noise) variable z,
= -2)).
(D.5)
We apply series of L such transformations g 122 22 such that g = g" o.... g which we refer to as flow layers. We use Neural Spline Flows [30] for the invertible transformation, with 3-layer feedforward neural network with hidden dimension 128 and permutation in each flow layer and L = 12 layers. The transformations 9. 9.9" .......'''"" g¹ biases of the neural networks), which we omit to simplify notation.
have learnable parameters (the weights and
Typically, simple distributions such as a uniform or isotropic Gaussian are used as base distribution q(2) in normalizing flows. Here, we instead choose a base distribution that encodes information about the latent SCM. Specifically, we model the base mechanism as
qu (2) W (f),
42(22 21) = NV (a21,
(2(22) = (u2
(D.6)
and the intervened mechanism
क (21) N _
T2(22) N ((2r,
(D.7)
33

---

Candidate Graphs and Intervention Targets. We train a separate normalizing- flow based model for each choice of candidate graph G' and inferred intervention targets. For the bivariate case with n 2, this gives rise to four models, depending on whether G' matches G or not, and whether the interven- tion targets are aligned or misaligned w.r.t. the ground truth intervention targets. To model the setting G' * G in which 1 and Z2 are assumed independent, we use 42 (2() ) in place of 42 (22 | 21) in (D.6). the intervention targets are aligned, we use qi instead of q; in e = i for i = 1, 2. Else, if they are mis- 2. By multiplying the respective
aligned, we use /2 instead of 92 in = 1 and ğı instead of qi in mechanisms, we thus obtain three environment-speetiee specciff joint base distributions qe (z) for = 0,
Learning Objective. Given multi-ennvionnan in and ã are jointly learned with the parameters of the invertible transformations g¹ by maximising the log- log-likelihood of the data under our model, which is given by:
data, the parameters μr. 01, à, 02 p2, 02. F22, ø2.
EBeep((n) (m) [log Prmndee (z)] 3EE
(m) .EE
log of (h(æ)) + log det Jn (x))
(D.8)
where the encoder h := g-1 is the inverse of the normalizing flow which is readily available by con- struction; and where the expectations are empirical averages over the respective datasets in practice.
Training and Model Selection Details. Each environment comprises a total of 200k data points. We use the ADAM optimizer [67] with cosine annealing learning rate scheduling, starting with a learning rate of 5 x 10-3 and ending with x 10-7. We train the model for 200 epochs with a batch size of 4096. We split the dataset into 70% for training, and 15% for validation and held-out test data, each sampled randomly across all environments. For each drawn data generating process, we train three versions of each model with different random initializations and select the one with the highest validation log likelihood at the end of training for evaluation.
Evaluation Metries. We evaluate the trained models w.r.t. mean correlation coefficient (MCC) on held-out data and log-likelihood on validation data (for model selection).
The MCC measures the extent to which there is one-to-one correspondence between the ground truth latents Vú and (a permuted version of) the inferred latents Z, = (X)).. Its maximum value of one indicates perfect correlation between the two. MCC is thus proxy measure for the level of identifiability up to permutation and invertible reparametrisation. We report MCC based Pearson (linear) correlation, though we found the results based on Spearman (nonlinear monotonic) correlation to be almost identical.
The logllielihood, on the other hand, measures how well a model explains or fits the data. Since the ground truth is typically unknown, a reasonable procedure when training multiple models is to select the one that attains the highest likelihood. For this reason, we report the difference in log- likelihood between misspecified models (ones assuming a wrong graph or intervention targets) to the correctly specified model. Whenever this difference is larger than zero, the correct model fits the data better and would thus be selected.
D.2 Additional Results: Learning Nonlinear Latent SCMs from Partial Causal Order
In this subsection, we present an additional experiment, in which we extend the setting investigated in & 6 and Appx. D.1 along the following axes.
We fit generative models over three instead of two variables, corresponding to the setting of Thm. 3.4.
The truth SCM is now given by nonlinear mechanisms with non-additive, non-Gaussian noise.
The generative model, including the learnt mechanisms, is now fully nonlinear.
Despite Thm. 3.4 formally requiring two environments per single-node intervention, we only provide one interventional environment per node.
Rather than searching over candidate graphs, only fix the causal order and fit the reduced form of the SCM (see $ 2.1) with second normalizing flow.
Below, we describe these differences in more detail.
34

---

Identifiability Scores
Model Fits
1,0
0.9
log-llkellhood
0.2
MCC
0.7
0.6
0.0
0.4
-0.1
123
132("
213
231
312
321
132(
213
231
312
321
Intervention target permutation
Intervention target permutation
Figure 4: Comparison of Correctly and Incorrectly Specified Models for V22 + V - V/3 with Fixed Causal Order and Nonlinear SCM. Each violinplot corresponds to one setting where the intervention target labels are permuted. The blue plot (123*) is the setting with correct intervention target labels. The yellow plot (132(*)) has the targets for the two children V/2 and Va3 permuted, which also corresponds correct causal ordering and should thus be considered equivalent. We show mean correlation coefficients (MCCs) between the learned and ground truth latents (Left) and the difference in validation model log-likeo liglliiel between the well-specified (blue) and misspecified models (Right). Each violin plot based on 20 different ground truth data generating processes; the horizontal lines indicate the minimum, median and maximum values.
Three- Variable Graph. The unknown ground truth graph is given by
V/ V1 + V/3
(D.9)
This is consistent with the partial ordering V, V22 < V3, which is assumed for all models priori w.l.o.g., see $ 2.2. Note that, due to the encoding of causal structure in the nonparametric model explained below, we only iterate over different permutations of the intervention targets and not over latent graph configurations. Due to the causal order implied by the graph (D.9), the permutations (1, 2, 3) (no permutaioo) and (1, 3, 2) (permutation of the two effects) are equivalent since the latter also implies the correct causal ordering.
Nonlinear, Non-Gaussian SCM.
The mechanisms in the ground-trute SCM are now given by
V; = 3f.oe (pp(t)) + preale (eeaal((pa())) (Vp
(D.10)
for all i, where the location and scale functions f glpa(() + R are parameterized by random 3-layer neural networks (sampled as the random mixing function in (D.2) and the noise variables are Gaussian, U; NVO0, 1). The factor 8 controls the influence of the parent variables relative to the exogenous noise. As increases, variables tend to become more dependent, also the mean shifts as a function of the parent variables. We set 10 for the experiments shown in Fig. 4.
Nonparametric Latent SCM. We use a second normalizing flow to learn a reduced form of the latent SCM via the transformation g SCM RS - R mapping an exogenous noise variable the latent variable z,
z = g=SSMM SCM(E)
(D.11)
The distribution of the exogenous noise variable as well as the distribution of the intervened mechanisms (2(2)) for 1, 3 is fixed and standard (isotropic) Gaussian. The flow layers in SCM have an upper triangular Jacobian and thus allow us to encode assumptions about the causal graph: by passing the variables in topological order, which we can assume w.l.o.g.. we ensure that an exogenous noise variable can only influence endogenous variables in z that are descendants of z,. The learned weights of the flow layers then implicitly encode which endogenous variables are connected. Therefore, only different choices of the permutations of the intervention targets need to be considered as candidate models. We use similar architecture based on Neural Spline Flows. However, omit permutation layers, which would violate the topological order of the variables.
35

---

Results. In Fig. 4, we present identifiability scores and model fits for both well-specified and misspecified models (corresponding to different intervention target choices). Notably. we observe that the well-specified model (in blue) or its equivalent (in yellow) yield the highest. log-likelihood in the majority of cases, as depicted in Fig. (Right). This demonstrates that, even in this nonparametric setting without fully specified graph, the log-likelihone remains reliable criterion for selecting the correct intervention targets. Fig. (Left) shows that the selected models (blue or yellow) approximately identify the ground-truth latent variables up element-wise rescaling, whereas other choices lead to much lower MCCs.
It is worth noting that, compared to the parametric setting investigated in $ 6 and Fig. 3, the nonparametric setting appears to be more challenging (as expected), as there is less pronounced distinction between well- well-specified and misspecified models, both in terms of identifiability scores and model fits. Moreover, future work needed to parse the implicitly learned causal relationships in the transformation gSCM in (D.1 1D.11) I): since only the (pre-imposed) causal order is specified, in practice, g SSM may learn use additional fewer edges than the true graph G.
E
Discussion of the Role of Our Assumptions
Below, we summarize the rationale and intuition behind each assumption:
Asm. 2.2 helps rule out degenerate cases (cancellation along different paths) in which variables are (conditionally) independent despite being causally related. It is a standard assumption classical causal discovery from observational data, and therefore also helps in CRL to recover the true causal graph.
Asm. 2.3 is required to know how many latent variables we are looking for. It is standard assumption in identifiable representation learning (that is often made implicitly). However, it may be dropped when suitable techniques for estimating the intrinsic dimensionality X can be employed.
Asm. 2.5 is needed for the mapping between latents and observations to be invertible in the first place. Without it, full recovery of the causal variables (up to CRL equivalence) infeasible. This assumption is also standard for the simpler problem of nonlinear ICA.
Asm. 2.8 a characterisation of our generative setup. Sharing of some mechanisms and the mixing function is needed for the multi-enviromment setting provide useful additional information: everything may change across environments, the datasets can only be analysed in isolation, running into the non-identifiability of CRL from iid data.
Asm. 2.9 and (A2) / (A2') are needed since with imperfect interventions or interventions not on all nodes, identifiability is not achievable even in the linear setting as shown by Squires et al. [117].
Asm. (A1) is a technical assumption needed for our analysis. It is not strictly necessary (it can also be relaxed to fully supported on Cartesian product of intervals) but substantially eases the readability and accessibility of the proof, without major impact on the main causal aspects of the problem setup.
Asm. (A3) / (A3') is needed to avoid spurious solutions based on applying measure preserving part of the domain unaffected by the intervention.
transformation
Asm. (A4) is needed to rule out fine-tuning of the ground-truth generating process that are possible due to fully non parameerittic nature of the setup, see also Remark 4.2 and the following paragraph.
36


Reviews:
[{"review_id": "ndMpQGXApQ", "reviewer": "Reviewer_FsUF", "summary": "This paper gives an identifiability result in a setting that is relevant to causal representation learning, where we wish to infer latent causal variables and their causal graph from high-dimensional observations. They work in a setting that is more general than prior work that relies on, for example, weak supervision, temporal structure, or known intervention targets. Their setting assumes that both the causal model and the mixing function are nonparametric, and the targets of the interventions are unknown.\n\nTheir identifiability results are up to trivial indeterminacies (permutations and element-wise diffeomorphisms) and identify both the causal graph and the mixing function. Their first theoretical result shows identifiability for two causal variables given one perfect stochastic intervention per node. Their second theoretical result shows identifiability for an arbitrary number of variables when there are two paired perfect stochastic interventions per node.\n\nThe main text of the paper does not have an experiment section.", "questions": "- Does your theory suggest any empirical validation that you could add to this paper? See the last bullet point in \"weaknesses\" section for empirical approaches that could be relevant to this kind of theoretical contribution.", "limitations": "- The conclusion section includes a thorough treatment of limitations of this work, which helps future work to extend these results. No concerns about negative societal impacts.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This paper frames a problem setting for identifiability that is interesting to causal representation learning, which begins to bridge the gap from existing identifiability results to modern machine learning that occurs on high-dimensional observed data.\n- They work in a highly general setting where both the causal model and the mixing function are nonparametric, and the targets of the interventions are unknown. In my opinion, the problem framing and the choice of this general setting are the primary contributions of this work even if the theoretical results have limitations.\n- The paper is generally well-written and well-structured.", "weaknesses": "- Their first theoretical result is in a setting with only two causal variables, where you have an observation distribution and one perfect intervention per node. This result would be much stronger in a setting with n>2, as the authors note in the conclusion.\n- Their second theoretical result is in a setting with arbitrary number of variables, but requires two distinct perfect paired interventions. Requiring these pairs of interventions is not a terribly realistic assumption, even though they don't require the intervention targets to be known.\n- There is no estimation method or experiment results. Other identifiability papers often contribute an estimation method (e.g. a VAE using a regularizer that encourages sparsity of a mixing function), perform disentanglement experiments in settings that match their theoretical assumptions, or perform ablations on synthetic data where they can control which of their theoretical assumptions are met in order to empirically study the necessity / sufficiency of their assumptions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for reviewing our work. We address your questions and comments below.\n\n> “The main text of the paper does not have an experiment section.” “There is no estimation method or experiment results. Other identifiability papers often contribute an estimation method [...], perform disentanglement experiments in settings that match their theoretical assumptions, or perform ablations on synthetic data where they can control which of their theoretical assumptions are met” “Does your theory suggest any empirical validation that you could add to this paper?”\n\nAs our main focus is on identifiability theory, we did not have space for including an experiment section in the main paper for the initial submission. However, we did, in fact, carry out an empirical validation similar to what you suggest. This was initially included in Appendix D (see Fig. 3 and its caption for the main points) and we will use the additional page to move some of this material to the main paper.\n\nIn short, we consider an estimation method that involves fitting multiple generative models based on normalizing flows with built-in causal structure for different choices of graphs and intervention targets. Consistent with our theoretical claims, our empirical results show that (i) the correct choice of graph and intervention targets are indeed identified as the ones that yield the best model fit in terms of held-out likelihood; and (ii) the true causal variables are recovered (up to rescaling) as supported by the high MCC values—the standard disentanglement/ICA metric to assess this.\n\nIn addition to what is already described in Appendix D, we performed some additional experiments during the rebuttal period, which are summarised in more detail in our general response to all reviewers.\n\nWe hope that adding a summary of these (new and old) experiments to the main paper satisfactorily addresses what appeared to be your main concern.\n____\n\n> Extension of the identifiability result from single interventions to $n>2$\n\nWe completely agree that this is desirable. As summarised in l.374-379, we do not see any fundamental reason why this should not be possible, but there are technical obstacles. Thus far, we were not able to find a simple characterisation of the set of genericity conditions required for n>2 variables, but we will continue to investigate this matter.\n"}, {"review_id": "19xqmo1L5N", "reviewer": "Reviewer_U76e", "summary": "This paper proposed to identify the latent causal representations and their underlying causal structure, which is a very challenging and interesting problem. The \\sim_{CRL} is introduced to describe the equivalent class up to elementwise operations and permutation, which is sufficiently meaningful for practical use. The CRL-identifiability theory is given under the data from paired interventional data and other assumptions, such as the pre-given number of nodes and others. In appendix, the authors presented a simple version of learning method and validates it on a synthetic dataset. ", "questions": "1. Intuitively, it appears that with paired interventional data, we can identify the latent representation with a unique permutation. For example, if we intervene to place a ball at position A on the table in e_i and at position B on the table in e'_i, we can infer that the position is the intervened variable through a simple comparison. Could you please provide a more in-depth explanation of the challenges encountered in theoretical analysis?\n\n2. The requirement of the genericity condition is specified in Theorem 4.1, whereas it is not explicitly mentioned in Theorem 4.2, which is presented as a more general version of Theorem 4.1. Additionally, the assumption A_2' does not degenerate to A_2 when n=2; instead, it is stronger than extending A_2 to a general n. I would appreciate a more detailed clarification regarding this matter.\n", "limitations": "Yes, the authors adequately addressed the limitations. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "In general, I found this paper to be highly enjoyable and insightful. It successfully addresses a challenging and captivating problem of extracting causal representations and their relationships. Given the increasing prevalence of unstructured data, such an endeavor holds significant importance. The authors have provided a comprehensive overview and engaging discussions that effectively highlight the unique contributions of their work in relation to existing literature. Moreover, the use of paired interventional data, which is more readily obtainable in practical scenarios, adds to the paper's practical relevance. Besides, the organization and writing of this paper are commendable.", "weaknesses": "1. I recommend that the authors provide practical demonstrations of the proposed method in real-world scenarios. While acquiring paired interventional data can be challenging in real-world settings, the authors could consider utilizing datasets generated from virtual environments, such as the causal world (https://sites.google.com/view/causal-world/home), to showcase the utility of their approach.\n\n2. In practical applications, determining the number of latent nodes n, is often difficult. Consequently, verifying whether the number of paired intervention data includes all latent variables becomes challenging. This limitation may restrict the scope of application for the proposed theory and learning methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for reviewing our work. We address your two main questions and other comments below.\n\n### Main questions\n\n> “Intuitively, it appears that with paired interventional data, we can identify the latent representation with a unique permutation. For example, if we intervene to place a ball at position A on the table in e_i and at position B on the table in e'_i, we can infer that the position is the intervened variable through a simple comparison. Could you please provide a more in-depth explanation of the challenges encountered in theoretical analysis?”\n\nIf we correctly interpret the question, there may be a misunderstanding as to what we mean by “pairs of environments” (“paired interventional data” in your comment). Unlike other works considering counterfactual, multi-view data (e.g., [17,110]), we do NOT observe pairs of observations $(x,x’)$ as in your example with the moving ball. Instead, we only have access to two datasets drawn from $P^1_X$ and $P^2_X$ which we know both arise from two distinct stochastic interventions on the same *unknown* latent variable. However, none of the images in the two datasets need to show the same ball (with only position differing): all other latent variables are resampled for each observation and will never agree exactly across datasets (except on a set of measure zero). At a high level, the main challenge of the analysis (compared to a counterfactual or multi-view setting) thus stems from the lack of correspondence across observations from different datasets: we may never see the same object more than once, and it may be non-trivial to infer what was intervened upon if multiple generative factors differ. \n\nMoreover, in your example, we only observe the pixels but not directly the position variable; the mapping between latents and observations, as well as the latent distributions are unknown and may be arbitrarily complex due to the nonparametric nature of the problem. Another key challenge thus arises from the flexible nonparametric problem setting.\n\nPlease let us know if we misunderstood your question or require further clarification.\n\n___\n\n> The requirement of the genericity condition is specified in Theorem 4.1, whereas it is not explicitly mentioned in Theorem 4.2, which is presented as a more general version of Theorem 4.1. Additionally, the assumption A_2' does not degenerate to A_2 when n=2; instead, it is stronger than extending A_2 to a general n. I would appreciate a more detailed clarification regarding this matter.\n\nThe distinction between the two settings may not have been emphasised enough in the initial manuscript. Allow us to clarify: Thm. 4.2 is not simply a direct extension of Thm. 4.1 to $n>2$, but a different statement relying on a related but distinct set of assumptions. As you correctly note, assumption (A2’) in Thm. 4.2 is indeed stronger than and different from assumption (A2) in Thm. 4.1. We chose the similar naming as both are assumptions about the available environments (but we are open to changing this to prevent confusion). Due to the stronger assumption (A2’), the genericity condition is indeed not needed for Thm. 4.2. We hope that this clarifies the matter and will highlight these subtleties in the revised manuscript.\n\n___\n\n### Other comments\n\n> “practical demonstrations of the proposed method in real-world scenarios”\n\nWhile we appreciate the suggestion and agree that this would be interesting, this was unfortunately out of the scope for the limited rebuttal period.\n\nHowever, we refer to Appendix D and our general response to all reviewers for more details on our experiments (on synthetic data), parts of which we will move to the main text. \n\n> “determining the number of latent nodes $n$”\n\nWe agree that this can be challenging, which is also why we explicitly included Asm. 3.3. We briefly touch upon practical methods for estimating the dimensionality $n$ of the observational manifold in footnote 8 in the last paragraph, which we will happily move to the main text. "}, {"review_id": "OyMUKLgwP6", "reviewer": "Reviewer_E44d", "summary": "The paper studies the problem of inferring causal relationships between $n$ latent variables through observations under a mixing function. Given data $X$ from multiple environments (each of which corresponds to an unknown perfect atomic intervention), where $X$ is the observation of the latents under a fixed mixing function $f$, the goal is to recover $f^{-1}$ and the causal graph $G$ on the latent variables (up to $\\sim_{CRL}$ equivalence).", "questions": "Line 175:\nMaybe write what CRL stands for somewhere (possibly in the footnotes)?\n\nAssumptions:\nThere are a lot of assumptions (which is okay, if they are well-justified and discussed). Can you explain or discuss why each of them is necessary or reasonable to have (without trivializing the problem)? I understand that you believe \"pairs of environments\" is not necessary in general, but what about the other assumptions? What happens if all but one is satisfied? What goes wrong? I am happy to further increase my score if this is sufficiently addressed and if the other reviewers did not raise any damning issues that I missed.\n\nTable 1 caption:\nTypo: \"Reresentation Learning\"", "limitations": "Nil.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem is well-motivated and interesting. The authors did a good job explaining how this paper differs from prior work while providing a pretty good literature review. Some experiments are also given in Appendix D.", "weaknesses": "While I am not an expert in the area and did not check all the proofs in detail, I do not see any glaring weaknesses. The theorem statements and proof sketches seem believable, especially since there is a lot of assumptions that were made to \"make things go through\". My biggest gripe is that there is a lack of discussion about the assumptions (see Questions section).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for reviewing our work. We will fix the typo and add an explanation for the CRL abbreviation. We answer your main question below.\n\n> There are a lot of assumptions (which is okay, if they are well-justified and discussed). Can you explain or discuss why each of them is necessary or reasonable to have (without trivializing the problem)?\n\nWe summarize below the rationale behind each assumption, most of which are also highlighted in our proof sketches.\n- Asm. 3.2 is required to rule out degenerate cases (cancellation along different paths) in which variables are (conditionally) independent despite being causally related. It is a standard assumption in classical causal discovery, and therefore also needed in CRL to recover the causal graph. \n- Asm. 3.3 is required to know how many latent variables we are looking for. It is a standard assumption in identifiable representation learning (that is often made implicitly). However, as discussed in footnote 8 and our response to reviewer `U76e`, it may be dropped when suitable techniques for estimating the intrinsic dimensionality of $\\mathcal{X}$ can be employed.\n- Asm. 3.5 is needed for the mapping between latents and observations to be invertible in the first place. Without it, full recovery of the causal variables (up to CRL equivalence) is infeasible. This assumption is also standard for the simpler problem of nonlinear ICA. \n- Asm. 3.9 is a characterisation of our generative setup. Sharing of some mechanisms and the mixing function is needed for the multi-environment setting to provide useful additional information: if everything may change across environments, the datasets can only be analysed in isolation, running into the non-identifiability of CRL from iid data. \n- Asm. 3.10 and (A2) / (A2’) are needed since with imperfect interventions or interventions not on all nodes, identifiability is not achievable even in the linear setting as shown by Squires et al. [104].\n- Asm. (A1) is a technical assumption needed for our analysis. It is not strictly necessary (see, e.g., footnote 9 on p. 21 in Appx. C.3) but substantially eases the readability and accessibility of the proof, without a major impact on the main causal aspects on the problem setup. \n- Asm. (A3) / (A3’) is needed to avoid spurious solutions based on applying a measure preserving transformation on a part of the domain unaffected by the intervention, see also l. 318-320.\n- Asm. (A4) is needed to rule out a fine-tuning of the ground-truth generating process that are possible due to fully non-parametric nature of the setup, see also Remark 4.2 and the following paragraph. \n\nWe hope that this sufficiently addresses your question. If so, we kindly ask whether you would consider increasing your score, also considering the lack of “any damning issues raised by other reviewers”."}, {"review_id": "qFdQRDzSPB", "reviewer": "Reviewer_ZLAN", "summary": "The paper discusses the task of identifying causal variables from high-dimensional observations under non-parametric mixing functions and causal mechanisms. This is done under the assumption of single-node, perfect interventions being available for all causal variables, as well as distinct paired perfect interventions in the case of having more more than two causal variables. The paper proves that causal variables are identifiable under this setup, when taking additional assumptions on the interventions being sufficiently different from the observational distribution. Thereby, weaker assumptions are possible for 2 variables than for more variables. Finally, the paper sketches possible implementations of learning algorithms for this setting.", "questions": "### Review summary\n\nThe theoretical results of the paper provide a new setting under which causal variables are identifiable in CRL. However, the paper is limited by its strong reliance on single-node, perfect interventions and very limited empirical study. I consider the theoretical results outweighing the drawbacks a bit, although the paper would strongly benefit from empirical validation of the setup. Thus, my recommendation is 'Weak Accept'.\n\n### Questions\n\n- What is a real-world scenario in which the setup of pairs of single-node, perfect interventions is practical and common?\n- Do you require the knowledge of the intervention targets up to permutation, or do you allow for more environments/environment pairs as long as each variable has been intervened upon once?", "limitations": "Limitations have been discussed in different parts of the paper. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is overall well written, even if it is aimed at researchers in identifiability and/or causal representation learning (CRL) specifically. A consistent notation is used throughout the paper, and all assumptions are clearly stated before the theorems. It is appreciated that proof sketches have been included in the main paper to support the claimed theorems and make the main paper a bit more standalone. The paper discusses all necessary related work and puts itself into context of the current field of research.\n\nThe main contribution of the paper is its theoretical result. It extends the domain of identifiable causal representation by considering yet another setup, where environment pairs with single-node, perfect interventions are given. The benefit of this setup is that it does not require counterfactual observations, while supporting a large function class despite taking needed assumptions on the interventions. The proofs for supporting the claimed theorems are given in the appendix, following common proof strategies in CRL. The proofs appear sound and intuitive, although a very careful check of the proofs was not possible during the review period. Overall, it is a good contribution to the theoretical identifiability in CRL. ", "weaknesses": "While the derived theory in the paper puts weaker constraints on the mechanisms of the causal variables and mixing function, its assumption of having access to single-node, perfect interventions on all causal variables is restrictive. Being able to perform an intervention on a variable is already commonly considered expensive or often not easily feasible, especially if it is a perfect intervention and single-node. However, doing this twice and even different between the two setups is challenging. Further, obtaining such a dataset requires non-trivial prior knowledge of the causal system, since it necessitates the ability to perform such single-node, perfect interventions on causal variables that are yet to be identified. The paper misses to give real-world examples to motivate the setup and its assumptions, which puts it in a more limited spot. \n\nBesides the theoretical results, it is also important to validate the setup and the practicality of the theory in empirical studies. The paper only sketches some potential ideas, where all unknown parts are learned. However, optimizing the latent encoder, the causal graph, and the intervention targets all at the same time is not trivial as shown in previous works. Further, the appendix shows some limited results on a generative model, where one would need to iterate over all possible causal graphs and intervention targets. Still, this is not practical for systems larger than very few causal variables or high-dimensional observations.\n\nThe paper states that the intervention targets are not known. However, under the identifiability up to permutation, the intervention targets in this setup appear to be known. Specifically, assumption (A2') states that there exist $n$ environment pairs, where each pair intervenes on a different causal variable. Thus, the intervention targets for these pairs, as stated in the assumption, are known as $\\pi(i)$. Since the variables cannot be identified up to permutation $\\pi$ anyway, permuting the causal variables and thus the targets are still considered to be the same targets in the same identifiability class, e.g. as in the works cited for known intervention targets [69, 70]. Thus, the claim of unknown intervention targets appears not valid given the assumptions, or the assumptions should be clarified to e.g. have at least $n$/$n+1$ environments.\n\n### Typos:\n- Table 1: 'Causal Representation Learning'", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for reviewing our work. We address your questions and comments below.\n___\n\n> Restrictiveness of the assumption of access to all single-node perfect interventions. \n\n\nWhile we agree that this is a strong assumption, it has previously been shown to be necessary even for more restricted settings. For example, Squires et al. [111] showed the necessity of access to all single node perfect interventions even in the fully linear interventional case, and Brehmer et al. [18] did so for a counterfactual, multi-view nonparametric setting. In this sense, it is unsurprising that at least as strong an assumption is needed in the nonparametric interventional case (and interesting that the same can be sufficient).\n___\n\n> Limited empirical study and the need to iterate over all possible causal graphs\n\nAs described in more detail in our general response to all reviewers, we now provided additional empirical results for a nonparametric setting with three variables. In particular, enumeration of causal graphs is avoided in this setting. Our main focus was on new theoretical results and validations thereof, and we believe that our new and existing experimental results are helpful to this end. That being said, we completely agree that “optimizing the latent encoder, the causal graph, and the intervention targets all at the same time is not trivial” and that further work is needed to make CRL methods more practical. \n___ \n\n> Clarification regarding assumption (A2’) and (un)known intervention targets.\n\nThis is a subtle point that may not have been sufficiently clear in the initial manuscript. For the setting of Thm 4.2, assumption (A2’) states that (i) datasets come in pairs; (ii) we know that, within each pair, the same variable was intervened upon; (iii) we do not know which variable was intervened upon in each pair, only that each variable was intervened upon (at least) in one pair. Importantly, note that $\\pi$ in (A2’) is defined as any permutation of $[n]$ and is not restricted to the subset of permutations that are isomorphisms of the unknown true graph (which is the partial permutation ambiguity of the CRL equivalence class). The conclusion that this is the same as knowing the intervention targets is therefore not supported. We will make the above more clear in the revised manuscript. \n\nWe are not quite sure what exactly is meant by “the assumptions should be clarified to e.g. have at least n/n+1 environments” and would welcome further clarification if this remains an open issue after our response. \n\n___\n\n> Real world examples\n\nWe are not experts in this domain (so the following is to be taken with a grain of salt), but we try to sketch a possible scenario and how it relates to our assumptions. \n\nConsider genetic experiments, where tools like CRISPR-Cas9 may permit one to perform targeted and (near) perfect interventions on individual genes. The observations in this case could correspond to some downstream effect that is influenced by gene activity, such as counts of different proteins. One might target different genes (for multiple cells) and thus collect multiple environments or datasets. Moreover, different types or concentrations of CRISPR-Cas9 might give rise to (two or more) interventional environments affecting the same target. It may be natural to think of this setting as one with known intervention targets. However, if we consider a less well-studied genome of another species, the exact places where certain DNA or RNA sequences are found may not be known a prior, corresponding to unknown intervention targets.\n\nWe will happily add the above example, or other suggestions the reviewer may have, to the revised manuscript."}]

Author rebuttal:
We thank all reviewers for their feedback and time in reviewing our work. All reviewers recommend acceptance, rating the soundness and contribution of our work as good and its presentation as good or excellent. 

We are pleased to read that our paper is “well-motivated and interesting” (`E44d`), ”relevant to causal representation learning”, “more general than prior work” (`FsUF`), “highly enjoyable and insightful”, that it “successfully addresses a challenging and captivating problem”, and “holds significant importance” and “practical relevance” (`U76e`). Reviewers also highlighted that the paper is “well-written” (`FsUF`, `ZLAN`), with `U76e` stating “the organization and writing of this paper are commendable”; and well-situated in the relevant literature (`ZLAN`,`E44d`,`U76e`), “highlight[ing] the unique contributions of [our] work” (`U76e`).

A shared issue raised by reviewers concerns the lack of experiments (in the main paper). To address this, we will use the additional page to add an experiments section to the main paper in the revised version. There we will include a summary of our empirical validation using normalizing flows, which was presented in Appendix D during the initial submission. Moreover, we also conducted some additional experiments during the rebuttal phase, see below and the attached PDF for details and a results figure. We will also add this to the new experiments section.

____


### Summary of New Experiments

**Setting.** Our new experiments extend our initial experiments along several axes:
- more variables: instead of focusing on the setting of Thm. 4.1 with $n=2$, we consider a setting with 3 causal variables and graph $V_2 \leftarrow V_1 \to V_3$

- nonlinear, non-additive noise data-generating process: we use location-scale models instead of linear Gaussian ones for the ground-truth SCMs

- nonparametric causal model: instead of fitting a set of linear parametric conditionals, we use a second normalizing flow (from exogenous variables U to causal variables V) as a nonparametric function approximator of the causal relations

- no enumeration of causal graphs: instead of training a separate generative model for each graph, we only specify the causal ordering (the natural ordering on [n]) and enforce the flow from U to V to have triangular Jacobian, consistent with the causal ordering and acyclic structure; this only leaves an enumeration of the intervention targets.

- violation of assumption (A2’): we consider only one interventional environment per node, thus investigating our conjecture that two paired interventions may not be required for Thm 4.2

**Results.** The results are summarised as a figure in the attached PDF. 

(Due to the limited time for hyper-parameter tuning etc, as well as the more challenging training task in this more general setting, the results are more noisy than in the initial experiments. We therefore focus on describing trends.)

We find that the model with correctly specified intervention targets achieves the best fit in terms of likelihood, as well as high MCC. The second-best fit is attained by the $132^{(*)}$ model (yellow violin), for which the targets are misaligned in a way that should, *in principle*, be consistent with the partial permutation ambiguity of the true underlying causal graph. (Note, however, that none of the flow weights are a priori forced to be zero even in the absence of an edge $V_2 \not \to V_3$---this may induce *practical* differences between these two theoretically equivalent models.) This model achieves equally high MCC. All other models (for which the misalignment of intervention targets is incompatible with the partial permutation ambiguity of the true graph) achieve poorer model fits and lower MCC.  

**Interpretation.** Overall, these results suggest that enumeration of graphs may not be needed, since 1, …, n is always a valid causal order w.l.o.g., and only choices of intervention targets compatible with the true causal graph achieve the best fits and MCC. Moreover, these results lend empirical support to our conjecture that 1 intervention per node may indeed be sufficient even for n>2 variables.

We will include a more detailed description of the experimental settings and results of these new experiments in the revised manuscript. 
____

We address further questions and comments in our responses to the individual reviews. 

Meta-review: This paper contributes to the growing literature on identifiability of latent causal models. The authors consider the setting of a nonparametric mixing function, although for > 2 nodes some paired data is required. All reviewers recommend acceptance. The authors should incorporate the changes suggested by the reviewers, for example, more discussion and the promised empirical examples.
Decision: Accept (poster)