Learning Linear Causal Representations from Interventions under General Nonlinear Mixing
Authors: Simon Buchholz
Goutham Rajendran
Elan Rosenfeld
Bryon Aragam
Bernhard Schölkopf
Pradeep Kumar Ravikumar
Venue: NeurIPS 2023 oral (2023)
Keywords: Causal Representation Learning
Interventional data
Gaussian Structural Causal models
TL;DR: We prove identifiability of causal representation learning from interventions with general nonlinear mixing functions and unknown, latent interventions, and propose a contrastive learning algorithm to learn it.

Abstract: We study the problem of learning causal representations from unknown, latent interventions in a general setting, where the latent distribution is Gaussian but the mixing function is completely general. We prove strong identifiability results given unknown single-node interventions, i.e., without having access to the intervention targets. This generalizes prior works which have focused on weaker classes, such as linear maps or paired counterfactual data. This is also the first instance of identifiability from non-paired interventions for deep neural network embeddings and general causal structures. Our proof relies on carefully uncovering the high-dimensional geometric structure present in the data distribution after a non-linear density transformation, which we capture by analyzing quadratic forms of precision matrices of the latent distributions. Finally, we propose a contrastive algorithm to identify the latent variables in practice and evaluate its performance on various tasks.

Learning Linear Causal Representations from Interventions under General Nonlinear Mixing
Simon Buchholz
Goutham Rajendran 2*
Elan Rosenfeld?
Bryon Aragam²
Bernhard Schölkopf
Pradeep Ravikumar
Max Planck Institute for Intelligent Systems, Tübingen, Germany
CCanegiie Mellon University, Pittsburgh, USA
3 University of Chicago, Chicago, USA
Abstract
We study the problem of learning causal representations from unknown, latent interventions in general setting, where the latent distribution Gaussian but the mixing function is completely general. We prove strong identifiability results given unknown single-node interventions, i.e., without having access the intervention targets. This generalizes prior works which have focused on weaker classes, such as linear maps or paired counterfactual data. This is also the first instance identifiability from non-paired interventions for deep neural network embeddings and general causal structures. Our proof relics on carefully uncovering the high- dimensional geometric structure present in the data distribution after a non- non-linear density transformation, which we capture by analyzing quadratic forms of precision matrices of the latent distributions. Finally, propose contrastive algorithm to identify the latent variables practice and evaluate its performance on various tasks.
Introduction
Modern generative models such as GPT-4 [59] or DDPMs (26 wide variety of tasks (7]. They do this by effectively learning high-level representations which map to
achieve tremendous performance for
raw data through complicated non-linear maps, such as transformers [89] or diffusion processes [79]. However, we are unable to reason about the specific representations they learn, in particular they are not necessarily related to the true underlying data generating process. Besides their susceptibility to bias (20). they often fail to generalize out-of diitr---iitribttionn settings (5), rendering them problematic in safety-critical domains. In order to gain a deeper understanding generative models learn, one line of work has pursued the goal of causal representation learning data while simultaneously recovering
what representations deep
(CRL) 75). CRL aims to learn high-level representations the rich causal structure embedded in them, allowing us to reason about them and use them for higher-level cognitive tasks such as systematic generalization and planning. This has been used effectively in many application domains including genomics [52) and robotics
43 94
crucial primitive in representation learning is the fundamental notion identifiability (37 70,, i.e., the question whether unique (up to tolerable ambiguities) model can explain the observed data. It is well known that because of non-identifiability, CRL is impossible in general settings in the absence of In this work, consider additional information
inductive biases or additional information 29 50
Equal Contribution
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

in the form of interventional data [75]. It is common to have access to such data in many application domains such as genomics and robotics stated above (e.g. 57 58 57)). Moreover, there is pressing need in such safety-critica, domains to build reliable and trustworthy systems, making identifiable CRL particularly important. Therefore, it's important to study whether we can and also how to perform identifiable CRL from raw observational and interventional data. Here, identifiability opens the possibility to provably recover the true representations with formal guarantees. Meaningfully learning such representations with causal structure enables better interpretability, allows us to reason about fairness, and helps with performing high-level tasks such as planning and reasoning.
In this work, we study precisely this problem of causal representation learning in the presence of interventions. While prior work has studied simpler settings of linear or polynomial mixing 884 88 2 [I, we allow for general non non-linear mixing, which means our identifiability results apply to complex real-world systems and datasets which are used in practice. With our results, we make progress on fundamental questions on interventional learning raised by [75].
Concretely, we consider general model with latent variables Z and observed data X generated as X (Z) where f: Rd + Id'' is arbitrary non-linear mixing function. We assume Z satisfies a Gaussian structural equation model (SEM) which is unknown and unobserved. A Gaussian prior commonly used in practice (which implies a linear SEM over Z) and further, having a simple model for Z allows us to learn useful representations, generate data efficiently, and explore the latent causal relationships, while the non-linearity of f ensures universal approximability of the model. We additionally assume access to interventional data ( f(Z()) for i E where Z is the latent under an intervention on a single node Zr,- Notably, we allow for various kinds of interventions, we don't 't require knowledge of the targets t,, and we don't require paired data, (i.e., we don't need counterfactual samples from the joint distribution (X; ( but only their marginals). Having targets or counterfactual data is unrealistic in many practical settings but many prior identifiability results require them, so eliminating this dependence is crucial step towards CRL in the real world.
Contributions Our main contribution is a general solution to the identifiability problem that captures practical settings with non-linear mixing functions (e.g. deep neural networks) and unknown interventions (since the targets are latent). We study both perfect and imperfect interventions and additionally allow for shift interventions, where perfect interventions remove the dependence of the target variable from its parents, while imperfect interventions (also known as soft interventions) modify the dependencies. Below, we summarize our main contributions:
1. We show identifiability of the full latent variable model, given non-paired interventional data with unknown intervention targets. In particular, we learn the mixing, the targets and the latent causal structure.
2. Compared to prior works that have focused on linear/polynomial f. we allow non-linear f which encompasses representations learned by c.g. deep neural networks and captures complex real-world datasets. Moreover, we study both imperfect (also called soft) and perfect interventions, and always allow shift interventions.
3. We construct illustrative counterexamples to probe tightness of our assumptions which suggest directions for future work.
4. We propose novel algorithm based on contrastive learning to learn causal representations from interventional data, and we run experiments to validate our theory. Our experiments suggest that contrastive approach, which far has been unexplored in interventional CRL, is a promising technique going forward.
2 Related work
Causal representation learning 75 74
has seen much recent progress and applications since generalizes and connects the fields of Independent Component Analysis 13 28 30), causal inference
96 32 Fundamental to this approach is the notion of identifiability [36] 15 93 Due to non non-identifiability in general settings without
[8]
61
63
64 82] and latent variable modeling 40 B
78
inductive biases (29 [0] prior works have approached this problem from various angles - using
additional auxiliary labels 36
27
6 76): by imposing sparsity 75
42 54
[03]: ; or by restricting
the function classes [1
104 22 See also the survey (32]. Moreover, a long line of works have
proposed practical methods for CRL (which includes causal disentanglement as special case),

---

2
Z+
2
Nonlinear mixing /
Nonlinear mixing
Nonlinear miking f
X
X
X
(a) No interventions
(b) An imperfect intervention
(c) A perfect intervention
Figure I: Illustration an example latent variable model under interventions. (a) No interventions. (b) An imperfect intervention node i; 3. Dashed edges indicate the weights could have potentially been modified. (c) A perfect intervention on node t; 3.
to name few. It's worth noting that most of these approaches are essentially variants of the Variational Autoencoder framework [39 [68]
95 16
Of particular relevance this work is the setting when interventional data is available. We first remark that the much simpler case of fully observed variables (i.e., no latent variables), has been studied in e.g. [23 62, 83 34 [8] (see also the survey [82]. In this work, we consider the more
difficult setting of structure learning over latent variables, which have been explored in [46 42
104
84
88 2
72). Among these, [46] assumes that the intervention targets known, 42
specifically consider instance-level pre- and post- interventions for time-series data and 6 104
assumes access to paired counterfactual data. In contrast, we assume unknown targets and work in general settings with non non-paired interventional data, which is important in various real-worde The work 48) require several graphical restrictions on the causal graph and also require 2d interventions, while we make no graphical restrictions and only require interventions (which we also show cannot be improved under our assumptions). [11
applications 885 99].
K4 88 consider linear
mixing functions f whereas we study general non-linear f. Finally, 2 consider polynomial mixing
the more restricted class of deterministic do-interventions. Several concurrent works study related For more detailed comparison to the related works, we refer to
settings [100 35 65
45 92
Appendix
Our proposed algorithm is based on contrastive learning. Contrastive learning has been used in other contexts this domain [31] 22 (55 104 99]] (either in the setting of time-series data or paired counterfactual data), however the application to non-paired interventional settings is new to the best of our knowledge.
Notation In this work, we will almost always work with vectors and matrices in d dimensions where d is the latent dimension, and will disambiguate when necessary. For vector v, we denote by u its i-th entry. Let ld denote the d x d identity matrix with columns as the standard basis vectors el....a ed. We denote by (1,, Σ) the multivariate normal distribution with mean p and covariance Σ. For set C, let (CC) denote the uniform distribution on C. For two random variables X, X', we
write X 2 X' their distributions are the same. We denote the set (1.....d) d} by [d]. For permutation matrices use the convention that (Pw) 1 (i) for w E Sa. We use standard directed graph terminoloyy, e.g. edges, parents. When we use the term "non-linear mixing" in this work, we also include linear mixing as a special case.
3 Setting: Interventional Causal Representation Learning
We now formally introduce our main settings of interest and the required assumptions. We assume that there is latent variable distribution Z on IRd and an observational distribution X on RR given by X f(Z) where d S d' and a non-linear mixing. This encapsulates the most general definition of latent variable model. As the terminology suggests, we observe X in real-life, e.g. images of cats and Z encodes high-level latent information we wish learn and model, e.g. Z could indicate orientation and size.
Assumption (Nonlinear f). The non-linear mixing f is injective, differentiable and embeds into
ddd

---

Such an assumption is standard in the literature. Injectivity is needed in order to identify Z from X because otherwise we may have learning ambiguity if multiple Zs map to the same X. Differentiabil- ity is needed to transfer densities. Note that Assumption [allows for large class of complicated nonlinearities and we discuss in Appendix F why proving results for such a large class of mixing functions is important.
Next, we assume that the latent variables Z encode causal structure which can be expressed through a Structural Causal Model (SCM) on Directed Acyclic Graph (DAG). We focus on linear SCMs with an underlying causal graph G on vertex set [d], encoded by matrix through its non-zero entries, i.e., there is an edge + j in G iff Ays * O.
Assumption (Linear Gaussian SCM on Latent Variables). The latent variables Z follow a linear SCM with Gaussian noise,
Z = AZ + D
where D is diagonal matrix with positive entries, A encodes a DAG G and Id)
For an illustration of the model, see Fig. Ta is convenient to encode the coefficients of linear SCMs through the matrix = D--1/2 (Id - A). Then Z = B and both and A can be recovered from B, indeed the diagonal entries of agree with the entries of D-1/2, Note that we can and will always assume that the entries of D are positive since e _ -c.
Assuming that the latent variables follow a linear Gaussian SCM is certainly restrictive but never- theless a reasonable approximation of the underlying data generating process in many settings. The Gaussian prior assumption is also standard in latent variable modeling and enables efficient inference for downstream tasks, among other advantages. Importantly, under the above assumptions, model has infinite modeling capacity [53 86 33], so they'r re able to model complex datasets such as images and there's 's no loss in representational power.
The goal of representation learning to learn the non-linear mixing f and the high-level latent distribution Z from observational data X. In causal representation learning, we wish to go step further and model Z as well by learning the parameters B which then lets us easily recover A, D and the causal graph G. For general non-linear mixing. this model is not identifiable and hence we cannot hope to recover Z, but in this work we use additional interventional data, similar to the setups in recent works 2 84 88].
Assumption (Single node interventions). We consider interventional distributions 760 for i E T which are single node interventions of the latent distribution Z, i.e., for each intervention there is target node t4 and we change the assigning equation of Z(,) to
Z z(0). )c + (D
1/2 (er, + 17)) Me
(2)
while leaving all other equations unchanged. We assume that A # 0 only if + t, in G, i.e., no parents are added and (8 denotes a shift of the mean.
For an illustration, see Fig. 16 An intervention on node t; has no effect on the non-descendants of t, but will have a downstream effect on the descendants of f.. In particular, A is modified so that the weight of the edge i + f, could potentially be changed if exists already but no new incoming edges to 4; may be added. Also, the noise variable et, is also allowed to be modified via scale intervention as well as shift intervention. Note that 884 2 do not allow shift interventions, whereas we do.
Again, this can be written concisely as 7 (B(0) ()((++)7700)) e7,)) where B( = -1/2)
A Let (3) denote the row t, of B61, then we can write BLú) = B es, (B et. - (0) We
D assume that interventions are non arivirivial, i.c., z * Z. In our model, we observe interventional distributions x ((2() for various interventions E T.
Definition 1 (Intervention Types). We call an intervention perfect (or stochastic hard) if A = O. i.e. we remove all connections to former parents and potentially change variance and mean of the noise variable. Note that for nodes without parents, either (1() # Ded, or nn()) f 0 so that the 1,4,
intervention non-trivial. We call an intervention a pure noise intervention if ( A and
A # 0 (i.e., node t; has at least one parent). In other words, a pure noise intervention targets
4

---

node with parents by changing only the noise distribution through change of variance (encoded in D) mean shift (encoded in 1)).
We call single-node intervention imperfect if it is not perfect (some prior works call it soft intervention). Note that perfect interventions are never of pure noise type because they necessarily change the relation to the parents. For illustration of perfect and imperfect interventions, see Fig. Ic Fig. [b respectively. Finally, we require an exhaustive set of interventions.
Assumption 4 ((Coverage of Interventions)). All nodes are intervened upon by at least one interven- tion, i.e. {4 E = [d]
This assumption was also made the prior works 84
When the interventions don't 't cover all the nodes, we have non-identifiability as described in Section and Appendix D We also extensively discuss that none of our other assumptions can simply be dropped in these sections.
88
Remark 1.
Our theory also readily extends noisy observations, i.e., X f(2) where v is independent noise. In this case, we first denoise via a standard deconvolution argument 36 42) and then apply our theory.
Similar to the results in [84] we can assume completely unknown intervention targets, i.e.. there might be multiple interventions targeting the same node, and we do not need to know the partition. We only require coverage of all nodes. In contrast to their work we assume that we know which dataset corresponds to the observational distribution, but we expect that this restriction can be removed.
To simplify the notation, it is convenient to use ( B, 17(0) 0 for the observational distribution. We also define = I U {0}. Then, all information about the latent variable distributions Z and observed distributions (+) are contained in ((B(), ,7())),))))) (t),
4
Main Results
We can now state our main results for the setting introduced above.
Theorem 1. Suppose we are given distributions ( generated using a model ((B(), 1100, Idiee, f) such that Assumptions 4 hold and such that all interventions i are perfect. Then the model is ,t)))t identifiable up to permutation and scaling, i.e., for any model ([B(9, 7799, &a)seI, f) that generates the same data, the latent dimension d agrees and there is a permutation w E Sa (and associated permutation matrix Pa) and an invertible pointwise scaling matrix A E Diag(d) such that
T, ===((,), B(a)= = - B( j= o=
7 = (7)
(3)
This in particular implies that
こ00 D AZ
and we can identify the causal graph G up to permutation of the labels.
This result says that for the interventional model as described in the previous section, we can identify the non-linear map f. the intervention targets 4, the parameter matrices B, D, A up to permutations Pu and diagonal scaling A. Moreover, we can recover the shifts (7 exactly and also the underlying causal graph G' up to permutations.
Remark 2. Identifiability and recovery up to permutation and scaling is the best possible for our setting. This is because the latent variables Z are not actually observed, which means we cannot (and in fact don't need to) resolve permutation and scaling ambiguity without further information about Z. See 84 Proposition for the short proof.
When we drop the assumption that the interventions are perfect, we can still obtain a weaker identifiability result. Define < be the minimal partial order on [d] such that i - j if (i.j) an edge in G. i.e., KG j if and only if is an ancestor of in G. Note that any topological ordering of is compatible with the partial order <a. Then, our next result shows that under imperfect interventions, we can still recover the partial order <g.
5

---

Theorem 2. Suppose we are given the distributions X(1 generated using a model ((B() .t)see with causal graph G such that the Assumptions 4 hold and none of the interventions is a pure noise intervention. Then for any other model (( T70 ( Wee,)))) with causal graph G generating the same observations the latent dimension d agrees and there is permutation E Sa such that i, = w(t)) and i < iff w() <a w(j), Le., <g can be identified up to a permutation of the labels.
Remark 3. We emphasize that neither the full graph nor the coefficients B(0) or the latent variables Zi are identifiable in this setting, even for linear mixing functions.
Theorem D and Theorem generalize the main results of (84) which assume linear f while allow for non-linear f. The key new ingredient of our work is the following theorem, which shows identifiability of f up to linear maps.
Theorem 3. Assume that X($) is generated according to model ((BO, ,7 f)) such that the Assumptions 74 hold. Then we have identifiability up to linear transformations, i.e.
if ((B() ,,(3 3(),,,))) generates the same observed distributions f(Z())) 2 x(i,, then their latent dimensions d agree and there is an invertible linear map T such that
f=foT=,
Z = TT(
(5)
The proof of this theorem is deferred to Appendix A (44 and show how their results can be extended to obtain our main results, Theorem I and Theorem Now we provide some intuition for the proofs of the main theorems.
In Appendix B we then review the results of
Proof intuition The recent work 88 studies the special case when f is linear, and the proof is linear algebraic. In particular, they consider row spans of the precision matrices of ( project them to certain linear subspaces and use those subspaces to construct a generalized RQ decomposition of the pseudoinverse of the linear mixing matrix f. However, once are in the setting of non-linear f. such an approach not feasible because we can no longer reason about row spans of the precision matrices of X, which have been transformed non-linearly thereby losing all linear algebraic structure. Instead, we take statistical approach and look at the log densities of the X By choosing a Gaussian prior, the log-odds In p (a) In xx (z) of ( with respect to ( can be written as a quadratic form of difference of precision matrices, evaluated at non-linear functions of For simplicity of this exposition, ignore terms arising from shift interventions and determinants of covariance matrices.
Then, the log-odds looks like 0(x) = - (x) (e - s (xx), where O the precision matrix of z
At this stage, we again shift our viewpoint to geometric and observe that ( (0) has a certain structure. In particular, for single-node interventions, it has rank most 2 and for source node targets, it has rank 1. This implies that the level set manifolds of the quadratic forms ((x) also have a certain geometric structure in them, i.e., the DAG leaves geometric signature on the data likelihood. We exploit this carefully and proceed by induction on the topological ordering until we end up showing that f can be identified up to a linear transformation, which is our main Theorem 3 Here, the presence of shift interventions adds additional complexities. and we have to generalize all of our intermediate lemmas handle these. Once we identify f up to a linear transformation, we can and
apply the results of [84) to conclude Theorems |
On the optimality and limitations of the assumptions assumptions, deferring to Appendix D a full discussion and the technical construction of several illustrative counterexamples.
We make few brief remarks
1. Number of interventions: For our main results, Theorems I and we assume that there are at least d interventions (Assumption 4). This cannot be weakened even for linear mixing functions 84 In addition, we also show in Fact for the linear identifiability proved in
Theorem 3 d 2 interventions are sufficient. Thus, the required number of interventions 2 and is tight up to at most one intervention in Theorem 3
is tight in Theorems]
2. Intervention type: In the setting of imperfect interventions, the weaker identifiability guaran- tees in Theorem 2 cannot be improved even when the mixing is linear (84) Appendix CJ. We also show in Fact mact2tth thha if we drop the condition that interventions are not pure noise interventions, we have non-identifiabiiity. Concretely, we show that when all interventions

---

are of pure noise type, any causal graph is compatible with the observations. Finally, in contrast to the special case of linear mixing, we show in Lemma @ that we need exclude non-stochastic hard interventions (i.e., do 74 2;)) for identifiability up to linear maps.
3. Distributional assumptions: We assume Gaussian latent variables, while allowing for very flexible mixing f. This model has universal approximation guarantees and is moreover used ubiquitously in practice. While the result can potentially be extended to more general latent distributions (c.g., exponential families), we additionally show in Lemma that the result is not true when making no assumption on the distribution of e.
5 Experimental methodology
In this section, we explain our experimental methodology and the theoretical underpinning of our approach. Our main experiments for interventional causal representation learning focus method based on contrastive learning. We train a deep neural network to learn to distinguish observational samples x (0) from interventional samples the model to model the log-likelihood of linear Gaussian SCM. Due representational flexibility of deep neural networks, we will in principle learn the Bayes optimal classifier after optimal training, which we show is related to the underlying causal model parameters. Accordingly, with careful design of the last layer parametric form, we indirectly learn the parameters of the underlying causal model. Similar methods have been used for time-series data or multimodal data (27 [2) but to the best of our knowledge, the contrastive learning approach to interventional learning novel.
X Additionally, we design the last layer of
Denote the probability density of x ~ X (resp. ~ z by P\ (1))
((()) (resp- P/ (=)). The next
lemma describes the log-odds of sample x coming from the interventional distribution x(+) as opposed to the observational distribution ( We focus on the identifiable case (see Theorem 1 and therefore only consider perfect interventions. As per the notation in Section and Appendix A. let g(t) denote the row t; of ((0) and let 17()) X; denote the magnitude of the shift and scale intervention respectively.
Lemma 1. When we have perfect interventions, the log-odds of sample x from from ( over coming from (!) is given by
Inpx (x) - In In (0) (x)= --
1 + 1 (x), (6) (x) -n - +
for a constant 0; independent of x.
The proof is deferred to Appendix functions
F The form of the log-odds suggests considering the following
(x on Br, 7i, ( 0) = a; - 3ch (z, 0) + whi, (x, + (),
where h(c, 0) denotes a neural net parametrized by 0, parameters (t) are the rows of a matrix W and ais 3r 7/2 are learnable parameters. Note that the ground truth parameters minimize the following cross entropy loss
((.1) In (c)--9((0)) (ar(1) +
c E). g(1))))))))))
(8)
Note that (compare 66) and (7) W should learn B = D 1/2 - A) thus its off-diagonal en- tries should form a DAG. To enforee this we add the NOTEARS regularizer [102] given by RNOTEARS(N) (W") tr exp( W o W)) -d (see Appendix F.3) where Wi equals W with the main diag- onal zeroed out. We also promote sparsity by adding the i regularization term RREO(W) = [Wll Thus, the total loss is given by
C(a, 8,7, W, = Σ c + TI R + T2RREG(W)
(9)
TE!
for hyperparameters Tı and T2. Our identifiability result Theorem limlies that when we assume that the neural network has infinite capacity, the loss in ( is minimized, Ti is large and 72 small, and learn Gaussian latent variables f(xx()) (4) 0), then we recover the ground truth latent variables up the
7

---

SHD
AUROC
MCC
R²
1.000
10
0.975
0.95
5
0.995
0.950
0.90
0.925
10
20
30
10
20
30
10
20
30
10
20
30
d
d
d
Figure 2: Dependence of performance metrics for ER(d, graphs with d' 100 and nonlinear mixing f on the dimension d.
tolerable ambiguities of labeling and scale, i.e., h recovers f and W recovers B up to permutation and scale. Thus, we estimate the latent variables using 2 = h(X, 8) and estimate the DAG using Wo- Full details of the practical implementation of approach are given in Appendix H
Our experimental setup is similar to theory holds in full generality) and therefore, index i which removes the permutation ambiguity. We focus on non-zero shifts because the cross entropy loss together with the quadratic expression for the log-odds results in non-convex output layer which makes it hard to find the global loss minimizer, as we will describe in more detail in Appendix G.I] We emphasize that this is contradiction to the theoretical results stated above. Even when there is no shift intervention the latent variables are identifiable, but our algorithm often fails to find the global minimizer of the loss (9) due to the non-convex loss landscape. For the sake of exposition and to set the stage for future work, we also briefly describe an approach via Variational Autoencoders (VAE). VAEs have been widely used in causal representation learning and while feasible in interventional settings, they are accompanied by certain difficulties, which we detail and suggest how to overcome in Appendix F.4
we consider interventions with different targets (our arbitrarily assign &, based the intervention
Experiments
In this section, we implement our approach on synthetic data and image data. Complete details (architectures, hyperparameters) are deferred to Appendix H. Additional experiments investigating the effect of varsortability (66) and the noise distribution can be found in Appendix G
Data generation For all experiments we Erdös-Rényí graphs, i.e., we add each undirected edge with equal probability p to the graph and then finally orient them according to some random order of the nodes. We write ER(d, k) for the Erdös-Rény? graph distribution d nodes with kd expected edges. For given graph G we then sample edge weights from 41 1.0]) and scale matrix D. We only consider
For simplicity we assume that we have n samples from each environment the setting where each node is intervened upon once and thus the latent dimension is also known. We consider three types of mixing functions. First, we consider linear mixing functions where we sample all matrix entries i.i.d. from Gaussian distribution. Then, we consider non-linear mixing functions that are parametrized by MLPs with three hidden layers which are randomly initialized, and have Leaky ReLU activations. Finally, we consider image data as described in (2). Pairs of latent variables (22641 ; 22:42) describe the coordinates balls an image and the non-linearity f the rendering of the image. The image generation is based pygame A sample image can be found in Figure 3
Evaluation Metries We evaluate how well we can recover the ground truth latent variables and the underlying DAG. For the recovery of the ground truth latents we use the Mean Correlation Coefficient (MCC) [37 Appendix A.2]. For the evaluation of the learned graph structure we use the Structural Hamming Distance (SHD) where we follow the convention that we count the number of edge differences of the directed graphs (i.e., an edge with wrong orientation counts as two errors). Since the scale of the variables is not fixed the selection of the edge selection threshold is slightly delicate. Thus, we use the heuristic where we match the number of selected edges the expected number
Figure 3: Sample image with 3 balls.

---

of edges. As metric that is independent of this thresholding procedure, we also report the Area Under the Receiver Operating Curve (AUROC) for the edge selection.
Methods We implement our contrastive algorithm as explained in Section F) where we use an MLP (with Leaky ReLU nonlinearities) for the function h for the linear and nonlinear mixing functions and very small convolutional network for the image dataset, which are termed "Contrastive", For linear mixing function we also consider version of the contrastive algorithm where / linear function, termed "Contrastive Linear", As baselines, we consider a variational autoencoder with latent dimension d and also the algorithm for linear disentanglement introduced in [44] Since the variational autoencoder does not ouiput causal graph structure we report the result for the empty graph here which serves as baseline.
Results for linear f First, for the sake of comparison, we replicate exactly the setting from [4] i.e., we consider initial noise variances sampled uniformly from [2, and we consider perfect interventions where the new variance is sampled uniformly from [6, 8]. We set d = 5, d' 10, 3/2, and 50000. Results can be found in Table The linear contrastive method identifies the ground truth latent variables up to scaling. The failure of the nonlinear method to recover the ground truth latents will be explained and further analyzed in Appendix G.I Note that the nonlinear contrastive and the linear contrastive method recover the underlying graph better than the baseline.
Table 1: Results for linear f with d 5, d' = 10, k 3/2, 50000.
Method
SHD +
AUROC 1
MCC 1
R² f
Contrastive
4.6 + 0.5
0.84 + 0.02
0.05 + 0.02
0.02 + 0.00
Contrastive Linear
5.4 + 1.6
0.80 + 0.07
0.90 0.03
1.00 + 0.00
Linear baseline
7.0 0.5
0.64 + 0.05
0.83 0.04
1.00 +.000
Results for nonlinear f We sample all variances from ([11, 21) (initial variance and resampling for the perfect interventions) and the shift parameters r7(*) of the interventions from [([ 21). Results can be found in Table We find that our contrastive method can recover the ground truth latents and the causal structure almost perfectly, while the baseline for linear disentanglement cannot recover the graph or the latent variables (which is not surprising as the mixing is highly nonlinear). Also, training a vanilla VAE does not recover the latent variables up to a linear map as indicated by the R² scores. Figure we illustrate the dependence on the dimension d of our algorithm this setting.
Table 2: Results for nonlinear synthetic data with n 10000.
Setting
Method
SHD +
AUROC 1
MCC
R
Contrastive
1.8 0.5
0.5
0.97 + 0.01
0.97 +
0.96 + 0.00
ER(5, 2), d' 20
VAE
10.0 0.0
0.50 + 0.00
0.48
0.57 0.07
Linear baseline
1
0.48 + 0.11
0.32
0.34 0.06
Contrastive
1.0
+.00
0.99
0.98 + 0.00
ER(5, 2), d' = 100
VAE
10.0
0.50 0.00
0.09
0.68 + 0.04
Linear baseline
3.4
0.85
0.18
0.11 0.04
Contrastive
1.3
0.98 + 0.01
0.93
0.87 + 0.01
ER(10, 2), d' = 20
VAE
18.6 0.9
0.50 0.00
0.09
0.72 + 0.02
Linear baseline
2.5
0.49 0.02
0.42
0.51 0.02
Contrastive
0.5
+ 1.00
0.00
0.97 0.00
ER(10, 2), d' 100
VAE
0.9
0.50 - 0.00
0.62
0.78 - 0.01
Linear bascline
2..
0.51 + 0.04
0.17
0.13 + 0.03
Results for image data Finally, we report the results for image data. Here, we generate the graph as before and consider variances sampled from o² ~ ([(0001, 0.02)) and shifts f7 from (( 1, 0.2)) (i.e.. the shifts are still of order σ). We exclude samples where one of the balls not contained in the image which generates a slight model misspecification compared to our theory. Again we find that we recover the latent graph and the latent variables as detailed in Table 3

---

Table 3: Results for image data with ER(d, 2) graphs with environment), Robs Rint
#balls and Pint
25000 (per
d.
Balls
Method
SHD /
AUROC 1
MCC 1
R
Contrastive Learning
1.4 0.4
0.95 0.03
0.87 0.03
0.84 0.03
VAE
6.0
1.50
0.19 + 0.06
0.16 -
Contrastive Learning VAE
2.0
1.00
0
0.91 0.01
18.6 0.9
0.00
0.31 + 0.02
0.36 0.03
Contrastive Learning VAE
11.0
0.98 0.02
0.89 + 0.01
0.83 0.01
3.1
0.50
0.22 + 0.01
0.33 + 0.02
7 Conclusion
In this work, we extend several prior works and show identifiability for a widely used class of linear latent variable models with non-linear mixing, from interventional data with unknown targets. Counterexamples show that our assumptions are tight in this setting and could only potentially be relaxed under other additional assumptions. We leave to future work to extend our results for other classes of priors, such as cor-maramttric distribution families, and also to study sample complexity and robustness of our results. We also proposed a contrastive approach to learn such models in practice and showed that it can recover the latent structure various settings. Finally, we highlight that the results of our experiments are very promising and it would be interesting to scale up our algorithms to large-scale datasets such as [49]
Acknowledgments
We thank anonymous reviewers for useful comments and suggestions. We acknowledge the support of AFRL and DARPA via FA8750-23-2-1015 ONR via N00014-23-1-2368, and NSF via IIS- 18-19999166 IIS- 195-555553.. We also acknowledge the support of JPMorgan Chase & Co. Al Research. This work was also supported by the Tübingen Al Center.
References
[1] K. Ahuja, J. S. Hartford, and Y. Bengio. Weakly supervised representation learning with sparse perturbations. Advances in Neural Information Processing Systems, 35:15516-15528, 2022.
[2] K. Ahuja, D. Mahajan, Y. Wang, and Y. Bengio. Interventional causal representation learn- ing. In Proceedings of the 40th International Conference on Machine Learning, ICMI'23. JMLR.org, 2023.
[3] Arora, R. Ge, Y. Halpem, D. M. Mimno, A. Moitra, D. A. Sontag, Wu, and M. Zhu. practical algorithm for topic modeling with provable guarantees. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, volume 28 of JMLR Workshop and Conference Proceedings, pages 280-288. JMLR.org. 2013. htt:: mll. www.spressvee....ee ppress/ve///// v28/arrraal. htmml
[4] Bello, Aragam, and P. Ravikumar. DAGMA: Learning DAGs via m-matrices and log-determinant acyclicity characterization. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https //openreview wtwparrvviei.ne//ffrrrrre www..eteooormmmiic-////.ppp
[5] R. Bommasani, D. A. Hudson, E. Adeli, R. Altman, S. Arora, Arx, M. S. Bernstein, J. Bohg, A. Bosselut, F. Brunskill, et al. On the opportunities and risks of foundation models. arXiv preprint arxiv:2108.0722 2021.
[6] J. Brehmer, P. de Haan, Lippe, and S. Cohen. Weakly supervised causal representation learning. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors,
10

---

Advances in Neural Information Processing Systems, volume 35, pages 38319-38331. Curran Associates. Inc., 2022. URL URtttppp://prrreeding... neurips....pppp... wwtpseet..rrppp.ppppreeaaea. www.s//apesssssseee 2022/f p022://hhe6555522200000000007777 Paper-Conference. pdf
[7] S. Bubeck, V. Chandrasekaran, R. Eldan, J. Gehrke, E. Horvitz, E. Kamar, P. Lee, Y. T. Lee, Y. Li, S. Lundberg, et al. Sparks of artificial general intelligence: Early experiments with GPT-4. arXiv preprint arXiv:2303.12212, 2023.
[8] S. Buchholz. Some remarks identifiability of independent component analysis in restricted function classes. Transactions on Machine Learning Research, 2023, ISSN 2835-8856. URL https://openrreiiet
[9] S. Buchholz, M. Besserve, and B. Schölkopf. Function classes for identifiable nonlinear independent component analysis. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors. Advances in Neural Information Processing Systems, 2022. URL hntpss//opperreviei net net/forum?id-Dee D PY8bK
[10] F. Castelletti and S. Peluso. Network structure learning under uncertain interventions. Journal of the American Statistical Association, pages 1-12, 2022.
[11] Y. Chen, E. Rosenfeld, M. Sellke, T. Ma, and A. Risteski. Iterative feature matching: Toward provable domain generalization with logarithmic environments. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 1725-1736. Curran Associates, Inc., www.:reeriiii..ooooooo.. www..ee......ppppp....e..c...ce. http:/ppper____ feaper_ffllee files wwterfffleeepeeeeeeeee /ppprr/0022/fiee/
2022. URL
0beaxa222f53666644477111444222-2 conferneee.......eee.e.eee pdf
[12] D. M. Chickering. Optimal structure identification with greedy search. J. Mach. Learn. Res., 3:507-554, 2002.
httpaaappwrseeecccceeeeeieeeeeee ing02b. html
[13] P. Comon. Independent component analysis, new concept? 287-314, 1994.
Signal processing, 36(3):
[14] J. Cui, W. Huang, Y. Wang, and Y. Wang. Aggnce: Asymptotically identifiable contrastive learning.
[15] A. D' A'mour, K. Heller, D. Moldovan, B. Adlam, B. Alipanahi, A. Beutel, C. Chen, J. Deaton, J. Eisenstein, M. D. Hoffman, et al. Underspecification presents challenges for credibility in modern machine learning. The Journal of Machine Learning Research, 122371773771 2022.
[16] N. Dilokthanakul, P. A. Mediano, M. Garnelo, M. C. Lee, H. Salimbeni, K. Arulkumaran, and M. Shanahan. Deep unsupervised clustering with gaussian mixture variational autoencoders. arXiv preprint arXiv: 00166111.2655 2016.
[17] A. Dixit, O. Parnas, B. Li, J. Chen, C. Fulco, L. Jerby-Amon, N. D. Marjanovic, D. Dionne, T. Burks, R. Raychowdhury, B. Adamson, M. Norman, E. S. Lander, S. Weissman, N. Friedman, and A. Regev. Perturb-seq: Dissecting molecular circuits with scalable single-cell ma profiling of pooled genetic screens. Cell, (67())1853-1188)) Dee 2016. ISSN 1097-4172 (Electronic); 0092-8677 2678 (Print); 0092-8674 (Linking). doi: 10.10166j.el112011111000
[18] F. Eberhardt, C. Glymour, and R. Scheines. On the number of experiments suf- ficient and in the worst case necessary to identify all causal relations among N variables. In UAI '05, Proceedings of the 21st Conference in Uncertainty in Ar- rificial Intelligence, Edinburgh. Scotland, July 26-29. 2005, pages 178-184, AUAI Press, 2005. URL httph::t///// httpp://dslpppttt httpapppp...pppa.o.a.aaaaaaaaaaa 1 22t.a22111121ee1110222eeeeeeeeee
jjpp7mmnu
id=21
[19] F. Falck, H. Zhang, M. Willetts, G. Nicholson, C. Yau, and C. C. Holmes. Multi-facet clustering variational autoencoders. Advances in Neural Information Processing Systems, 34, 2021.
[20] E. Ferrara. Should ChatGPT be biased? challenges and risks of bias in large language models. arXiv preprint arXiv:2304.03738. 2023.

---

[21] J. L. Gamella, A. Taeb, C. Heinze-Dent and P. Bühlmann. Characterization and greedy learning of gaussian structural causal models under unknown interventions, 2022.
[22] L. Gresele, J. Von Kügelgenn V. Stimper, B. Schölkopf, and M. Besserve. Independent mechanism analysis, new concept? Advances in Neural Information Processing Systems, 34, 2021.
[23] A. Hauser and P. Bühlmann. Characterization and greedy learning of interventional markov equivalence classes of directed acyelic graphs. The Journal of Machine Learning Research, 13 (1):2409-244) 24049, 2012.
[24] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
[25] C. Heinze-Deml, J. Peters, and N. Meinshausen, Invariant causal prediction for nonlinear models. Journal of Causal Inference, 6(2), 2018.
[26] J. Ho, A. Jain, and P. Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-6855 2020.
[27] A. Hyvärinen and H. Morioka. Unsupervised feature extraction by cone-contr learning and nonlinear ICA. In D. D. Lee, M. Sugiyama, U. von Luxburg. I. Guyon, and R. Gar- nett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 3765-3773, 2016. URL /ttttpp::/ppooeeedingsssss neurips cc/ cec/pappr//0// 2016//as///////////// (805281faf9477c77accdooo cataa//aaaccceeeddeeeeeee3 Abstract. html.
[28] A. Hyvärinen and E. Oja. Independent component analysis: algorithms and applications.
Neural networks, 13(4-5):4114433 2000.
[29] A. Hyvärinen and P. Pajunen. Nonlinear independent component analysis: Existence and uniqueness results. Neural networks, 12(3):429 4399, 1999.
[30] A. Hyvarimen, J. Karhumen, and E. Oja. Independent component analysis. Studies in informatics and control, 11(2):05-227, 2002.
[31] A. Hyvarinen, H. Sasaki, and Turner. Nonlinear ica using auxiliary variables and generalized contrastive learning. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 859-868. PMLR, 2019.
[32] A. Hyvärinen, I. Khemakhem, and R. Monti. Identifiability latent-variable and structural- equation models: from linear to nonlinear. arXiv preprint arXiv:2302.02672 2023.
[33] I. Ishikawa, T. Teshima, K. Tojo, K. Oono, M. Ikeda, and M. Sugiyama. Universal approxima- tion property of invertible neural networks. arXiv preprint arXiv:2204.07415, 2022.
[34] A. Jaber, M. Kocaoglu, K. Shanmugam, and E. Bareinboim. Causal discovery from soft interventions with unknown targets: Characterization and learning. Advances in neural information processing systems, 33:9551-9561, 2020.
[35] Y. Jiang and B. Aragam. Learning latent causal graphs with unknown interventions. In Advances in Neural Information Processing Systems, 2023.
[36] I. Khemakhem, D. Kingma, R. Monti, and A. Hyvarinen. Variational autoencoders and nonlinear ica: A unifying framework. In International Conference on Artificial Intelligence and Statistics, pages 2207-2217. PMLR, 2020.
[37] I. Khemakhem, R. Monti, D. Kingma, and A. Hyvärinen. Ice-beem: Identifiable con- ditional energy based deep models based on nonlinear ICA. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and Lin, editors, Advances in Neural Information Processing Sys- tems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 12, 2020, virtual, 2020. URL hatpah/s//222e00000000//22222222 htwp://222aee22bbeeeee---aaaaaaa Abstract.htm
wwt.snie...pppppppeeeeeeeee paper/
12

---

[38] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In Y. Bengio and Y. LeCun, editors. 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http: //axxiv.org orrg/v.or//..o abs/ 1412. 6980
[39] D. P. Kingma and M. Welling. Auto-encoding variational bayes. In Y. Bengio and Y. LeCun, editors, 2nd International Conference on Learning Representations. ICLR 2014, Banff. AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL htLphtpp:// arxiv org/
abs/ 6114
[40]
B. Kivva, G. Rajendran, P. Ravikumar, and B. Aragam. Learning latent causal graphs via mixture oracles. In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, vir- tual. pages 18087-18101, 2021. URL https: URListps://proreeeddngg www.oiiinnnnnnnis..oomm cctppp///2c/pppp//222///// Abstract.
[41] B. Kivva, G. Rajendran, P. Ravikumar, and B. Aragam. Identifiabil- ity of deep generative models without auxiliary information. 2022.
In NeurIPS, URI. http://paper:: http:/pppprs.iss......... htcp/aper_fiiiie fwtesffaaeeerre/////eaaaaaaaaaee 2002//aahh/ 6G951800881111441122200000888880 hww.://22229a---aaaaaaaaae Abstract- Conference.....eo -braraa---bbbaaaac---oeeeeeeeee html
[42] S. Lachapelle, P. Rodríguez, Y. Sharma, K. Everett, R. L. Priol, A. Lacoste, and S. Lacoste- Julien. Disentanglement via mechanism sparsity regularization: A new principle for nonlinear ICA. In B. Schölkopf, C. Uhler, and K. Zhang, editors, Ist Conference on Causal Learning and Reasoning, CLeak 2022, Sequoia Conference Center, Eureka, CA, USA, 11-13 April, 2022, volume 177 of Proceedings of Machine Learning Research, pages 428-484. PMLR, 2022. URL https::/ mlr http://ceeiiiag.n..rpeereee///ee
html
[43] T. E. Lee, A. Zhao, A. S. Sawhney, S. Girdhar, and O. Kroemer. Causal reasoning in simulation for structure and transfer learning of robot manipulation policies. In 2021 IEEE International Conference on Robotics and Automation (ICRA). pages 4776-4782 IEEE, 2021.
[44] S. Li, B. Hooi, and G. H. Lee. Identifying through flows for recovering latent representations. In 8th International Conference on Learning Representations, ICIR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https: //tter////peerevier net/ nwt:forum ht/ffffrmmm/d Sk10UpEYvB
[45] W. Liang, A. Kekić, J. von Kügelgen, S. Buchholz, M. Besserve, L.. Gresele, and B. Schölkopf. Causal component analysis. In Advances in Neural Information Processing Systems, 2023.
[46] 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-13600 PMLR, 2022.
[47] C. Liu, L. Zhu, and M. Belkin. Loss landscapes and optimization in over- parameterreeee non- linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85- 116, 2022. ISSN 1063-5203. doi: https://doi.org//// org//00 101.000100.......aa..a.aa 12.009. URL (ttttsts::// www www. www.eeiceeeirrct... com/ setiieeee/rriicee///////...///// on Harmonic Analysis and Machine Learning.
Special Issue
[48] Y. Liu, Z. Zhang, D. Gong, M. Gong, B. Huang, A. d. Hengel, K. Zhang, and J. Q. Shi. Identifying werihttvariant latent causal models. arXiv preprint arXiv:2208. 2.1.:2208../153, 2022.
[49] Y. Liu, A. Alahi, C. Russell, M. Horn, D. Zietlow, B. Schölkopf, and F. Locatello. Causal triplet: An open challenge for intervention-centtic causal representation learning. In 2nd Conference on Causal Learning and Reasoning (CLeaR), 2023. arXiv:2301.05166
[50] 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 international conference on machine learning, pages 41 14 4124. PMLR, 2019.
13

---

[51] I. Loshchilov and F. Hutter. SGDR: stochastic gradient descent with warm restarts. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https //openreview wtt..eeeooorrrmndnnna00e0eee
[52] M. Lotfollahi, K. Susmelj, C. Theis, and D. Lopez-Paz. Compositional perturbation autoencoder for single-cell response modeling. BioRxiv, 2021.
De Donno, Ji, L. Ibarra, F. A. Wolf, N. Yakubova, F.
[53] Y. Lu and J. Lu. universal approximation theorem of deep neural networks for ex- pressing probability distributions. In H. Larochelle, M. Ranzato, R. Hadsell, M. Bal- can, and H. Lin, editors, Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020. NeurlPS 2020, December 6- 12, 2020, virtual, 2020. URL /ttp///t///// 2000f htt.://eeeeee010eeeeeeeeeeeee/ abseeeessettbttassabbbaaaaaaatta Abstract html.
[54] G. E. Moran, D. Sridhar, Y. Wang, and D. Blei. Identifiable deep generative models via sparse decoding. Transactions on Machine Learning Research, 2022.
[55] H. Morioka and A. Hyvarinen. Connectivity learning: Combining causal discovery and representation learning for multimodal data. In International Conference on Artificial Intelligence and Statistics, pages 3399-3426. PMLR, 2023.
[56] J. Moser. On the volume elements a manifold. Transactions of the American Mathematical Society, 120(2):28--294, 1965. ISSN 00029947. URL http:///ww/e //wp://wwwwww// www.:/jstrrrorgsstttott org/stable/ 1994022
[57] A. Nejatbakhsh, F. Fumarola, S. Esteki, T. Toyoizumi, R. Kiani, and L. Mazzucato. Predicting perturbation effects from resting activity using functional causal flow. bioRxiv, pages 2020-11, 1, 2020.
[58] T. M. Norman, M. A. Horlbeck, J. M. Replogle, A. Y. Ge, A. Xu, M. Jost, L. A. Gilbert, and J. S. Weissman. Exploring genetic interaction manifolds constructed from rich single-cell phenotypes. Science, 365(6455):786-793 2019.
[59] OpenAI. GPT-4 technical report, 2023.
[60] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury. G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Köpf, E. Z. Yang, Z. Vetooo, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang. J. Bai, and S. Chintala. Pytorch: An im- perative style, high perfoormeree deep learning library. In H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Bue, E. B. Fox, and R. Garnett, editors, Advances in Neu- ral Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 8024-8035, 2019, httphttss////:oteeee (tw.://8feee/99222aaage
wttpppppcccppppp////9// http://00--Atttttt..h.. html.
[61] J. Pearl. Causality. Cambridge university press, 2009.
[62] 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 (Statistical Methodology), 78(5):447-0012 2016. ISSN 13697412, 14679868. http //www. jstor wtw.storrrr//eeeoeeeeeeeeoooeeee http:/saalll//// wttgsttabll/446220000
[63] J. Peters, D. Janzing, and B. Schölkopf. Elements of causal inference: foundations and learning algorithms. The MIT Press, 2017.
[64] G. Rajendran, B. Kivva, M. Gao, and B. Aragam. Structure learning in polynomial time: Greedy algorithms, bregman information, and exponential families. Advances in Neural Information Processing Systems, 14:66661-18672 2021.
[65] G. Rajendran, P. Reizinger, W. Brendel, and P. K. Ravikumar. An interventional perspective on identifiability in gaussian Iti systems with independent component analysis. In UA/ 2023 Workshop on Causal inference for time series data, 2023.
14

---

[66] A. G. Reisach, C. Seiler, and S. Weichwald. Beware of the simulated dag! causal discovery benchmarks may be easy game. In M. Ranzato, Beygelzimer, N. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 14, 2021, virtual, pages 27772-27784 2021. URL http::/:de///oceeeeeeeeeee neur cuurips.cc. Abstract html
[67] G. Reisach, M. Tami, C. Seiler, A. Chambaz, and Weichwald. Simple sorting criteria help find the causal order in additive noise models. In Advances in Neural Information Processing Systems, 2023.
[68] D. J. Rezende, S. Mohamed, and D. Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In International conference on machine learning, pages 2278-1286 PMLR, 2014.
[69] J. Rissanen. Modeling by shortest data wwwereeteoon Amtoon 140)):050.___004445-444455---- 1978. doi: 10110 0005- 105-1098778)0005--00 5. URL httppp::/daa..cgg//001111/////// (1)))/00000011100)))00)0))000000 90005-5
[70] G. Roeder, L. Metz, and D. Kingma. On linear identifiability of learned representations. In International Conference on Machine Learning, pages 9030-9039, PMLR, 2021.
[71] E. Rosenfeld, P. K. Ravikumar, and A. Risteski. The risks of invariant risk minimization. In International Conference on Learning Representations, 2021. URL BRRp:httt::/opeerrrii set/forrum?iddBBlIlVVY
[72] E. Rosenfeld, P. Ravikumar, and A. Risteski. Domain-adjusted regression or: Erm may already learn features sufficient for out-of-distribution generalization. arXiv preprint (rXii:2202.06855 2022.
[73] D. Rothenhäusler, N. Meinshausen, P. 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.
[74] B. Schölkopf and J. von Kügelgen. From statistical to causal learning. arXiv preprint wrXiv:2204.00607 2022.
[75] 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-6344 2021. arXiv:2102.11 11007.
[76] 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.
[77] P. Shinners. Pygame. http://pygame /rrg///e.rr// 2011.
[78] 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.
[79] J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learning, pages 2256-2265, PMLR, 2015.
[80] P. Spirtes and C. Glymour. An algorithm for fast recovery of sparse causal graphs. Social science computer review, 911:622-7,, 1991.
[81] P. Spirtes, C. Glymour, and R. Scheines. Causation, prediction, and search. MIT press, 2000.
[82] C. Squires and C, Uhler. Causal structure learning: a combinatorial perspective. Foundations of Computational Mathematics, pages 1-35, 2022.
[83] C. Squires, Y. Wang, and C. Uhler. Permutation-basee causal structure learning with unknown intervention targets. In Conference on Uncertainty Artificial Intelligence, pages 1039-1048. PMLR, 2020.
15

---

[84] C. Squires, A. Seigal, S. S. Bhate, and C. Uhler. Linear causal disentanglement via interven- tions. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and Scarlett, editors, International Conference on Machine Learning, ICMI. 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 32540-32560. PMLR, 2023. htRL/htps::/// htt.htttts:/:poeeeeeeee http:///////ceeee.s.s...o wwt.ssesr...e./ee.eem.eeeeeeeeee press/v202/ w202//222222/222 2200//quiree23. hhmmmmmmm...mm1111mmmmmmmm
[85] S. G. Stark, J. Ficek, F. Locatello, X. Bonilla, S. Chevrier, F. Singer, G. Rätsch, and K.-V. Lehmann. Scim: universal single-cell matching with unpaired feature sets. Bioinformatics, 36 (Supplement 2):1919 -927, 2020.
[86] T. Teshima, Ishikawa, K. Tojo, K. Oono, M. Ikeda, and M. Sugiyama. Coupling- based invertible neural networks are universal diffcomorphism approximators. Advances in Neural Information Processing Systems, 33:3362-3373, 2020.
[87] B. Varici, K. Shanmugam, P. Sattigeri, and A. Tajer. Scalable intervention target estimation in linear models. Advances in Neural Information Processing Systems, 34:1494-1505 2021.
[88] B. Varici, E. Acarturk, K. Shanmugam, A. Kumar, and A. Tajer. Score-based causal represen- tation learning with interventions. arXiv preprint arXiv:2301.082300 2023.
[89] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[90] C. Villani. Optimal Transport: Old and New. Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 2008. ISBN 9783540710509. URL https://boosoks. google de/bookss7dd--Voot
_5tkC
[91] J. Von Kügelgen, Y. Sharma, L. Gresele, W. Brendel, B. Schölkopf, M. Besserve, and F. Lo- catello. Self- supervied learning with data augmentations provably isolates content from style. Advances in Neural Information Processing Systems, 34, 2021.
[92] J. von Kügelgen, M. Besserve, W. Liang, L. Gresele, A. Kekić, E. Bareinboim, D. M. Blei, and B. Schölkopf. Nonparametric identifiability of causal representations from unknown interventions. In Advances in Neural Information Processing Systems, 2023.
[93] Y. Wang, D. Blei, and J. P. Cunningham. Posterior collapse and latent variable non- identifiability, Advances Neural Information Processing Systems, 34:5443-5455, 2021.
[94] S. Weichwald, S. W. Mogensen, E. Lee, D. Baumann, O. Kroemer, Guyon, S. Trimpe, J. Peters, and N. Pfister. Learning by doing: Controlling dynamical system using causality, control, and reinforcement learning. NeurlPS 2021 Competitions and Demonstrations Track, pages 246-258. PMLR, 2022.
[95] M. Willetts and B. Paige. I don't need n: Identifiable non-linear ica without side information. arXiv preprint arXiv:2106.05235 2021.
[96] F. Xie, R. Cai, B. Huang, C. Glymour, Z. Hao, and K. Zhang. Generalized independent noise condition for estimating latent variable causal graphs. Advances in neural information processing systems, 11:1489911492, 2020.
[97] M. Yang, F. Liu,2 Z. Chen, X. Shen, J. Hao, and J. Wang. Causalvae: Disentangled representa- tion learning via neural structural causal models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 9593-9602, June 2021.
[98] Y. Yu, J. Chen, T. Gao, and M. Yu. Dag-gnn: Dag structure learning with graph neural networks. In International Conference on Machine Learning, pages 7154-7163. PMLR, 2019.
[99] J. Zhang, C. Squires, and C. Uhler. Matching a desired causal state via shift interventions. Advances in Neural Information Processing Systems, 14:19923-19934 2021.
[100] J. Zhang, C. Squires, K. Greenewald, A. Srivastava, K. Shanmugam, and C. Uhler. Iden- tifiability guarantees for causal disentanglement from soft interventions. arXiv preprint #xXi:22307.06250 2023.
16

---

[101] S. Zhao, J. Song, and S. Ermon. Infovae: Balancing learning and inference in variational autoencoders. In The Thirty-Thire AAAI Conference on Artificial Intelligence, AAAI 2019,
The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 20/9,
The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence EAAI 2019,
Honolulu, Hawaii, USA, January 27 February 1, 2019, pages 5885 AAAI Press, 2019.
doi: 10.
v33i01
33015885
[102] X. Zheng, B. Aragam, P. K. Ravikumar, and E. P. Xing. Dags with no tears: Continuous optimization for structure learning. Advances in neural information processing systems, 31, 2018.
[103] Y. Zheng, Ng, and K. Zhang. On the identifiability of nonlinear ICA: sparsity and beyond. In NewrIPS, 2022. URL http://papers: wips.miiiii............. ctpps/cccpaaae cwwpppprccppppppcceepeee httpc/pppperreeeeeeeeeeeeeeeeeee files/ www.e//epeeeeeeeeeeeeea papprr/022/haaaeeeeeeppp http://ffeeeee2eceeeeeeeeeeeeeee
html
[104] S. Zimmermann, Y. Sharma, Schneider, Bethge, and Brendel. Contrastive learning inverts the data generating process. In International Conference on Machine Learning, pages 12979-12990. PMLR, 2021.
17

---

A Proof of Identifiability up to Linear Maps
In this section we give full proof of Theorem We try to make this essential self-contained. To make this easy to read, we first introduce and recall the required notation in Section [A.1 then we prove two important key relations required for the proof in Section A.2 Finally, we prove first simpler version of Theorem 3 with more assumptions in Section A.3 and then give the full proof of
Theorem 3 in Section A.4
A.1 General Notation
Let us introduce some notation for our identifiabiiity proofs. For a full list of assumptions we refer the main text, here we just recall the relevant notation concisely. We will assume that there are two representations that generate the same observations, i.e., we assume that there are two sets of Gaussian SCMs
2 2() (D())) ew.) 700 = - + ) (E (T,) (7)))
(10)
(11)
where = NO0, Id) and = 0 corresponds to the observational distribution while i >> 0 correspond to interventional settings where we intervene on a single node 4; (or ł,) by adding shift and changing the relation to its parents (without adding new parents). Moreover, there functions f. f such
that (+) _ (()()) and ( _ ((Z(). It is convenient to define
B (D()) 1 (Id - ( (+)) 17 (B()))
(12)
(13)
so that (1 (B(0)-1e ,(9 with e ((0,Id) Note that all model information can be collected in ((B(), n7 (1) f),,
As in the main text, it is convenient to use the shorthand B = (0)), A 1
We denote the row 4 of B(0) by (t), i.e.
( (B())Ter. ex.
(14)
Note that for perfect interventions where we cut the relation to all parents of node 4 we have (()) Xzet for some A; * Similarly, for the observational distribution we refer to the row f, of ( by s(i), i...
(i) =
(B(()) el.
(15)
We thus find
B - - c, (c) B(0) B() c,,B(o))
(s (c,))) -((())))pp()
(16)
We also consider the covariance matrix ()) and the precision matrix (+) of ((i) which are given by ( ( B(0,, y (0)
(17)
Indeed,
ッの = ((( T (B(O)) - - BBle T[ (B())-
Finally, the mean
( of (t) given by
( = EZ( ,,,0 (B))
(18)
We also define similar quantities for Ž. To simplify the notation, will frequently the shorthand v & w U w" E dd for v w E Rd
18

---

A.2 Two auxiliary lemmas
The key to our identifiability results is the relation shown in the following lemma.
Lemma 2. Assume that there are two latent variable models ((B(), .f9 t.)ket, f) and (1860,77))) (,),,))) as defined above such that f(z(0) 2 f(Z()). Then their latent dimen- sion d agree and h = f-1ff-1. o f- differentiable inverse. Moreover, it satisfies the relation
exists and is diffeomorphism, i.e., bijective and differentiable with
1 (0 - 0 (r(0))=
2
(19)
= 22 ht= (6(1) (())) - - (7())))(())))
h(2)) + c6)
for all z and i and some constant c(0)) 18 = 1700) = 1his simplifies to
2 2 (
2 2 h(2) T (6 (()) +
(20)
Proof. Note first that (0) _ s(Z implies since f is an embedding by assumption that the dimension of the support of x is the same as the latent dimension and this dimension is identifiable from the observations, e.g., by considering the tangent space. As ()) and Z have full support and f and f are by assumption embeddings, the equality f(Z(0)) 2 f(Z(") implies that the two image manifolds agree and h f-1 o f is a differentiable map. Moreover, we find that h. z() Z where h, denotes the pushforward map. The variables z are Gaussian with distribution Z N(ull) E.)) This implies that its density p(*) can be written
(x)) = -2 2
n In(2T)
2 In | 1 ) ( T (z (())).
(21)
A similar relation holds for (() the density of 20,, Finally, we have the relations
(2) p (h(=)) det [z))
(22)
which is consequence of 11, 200 7 Here Jn. denotes the Jacobian matrix of partial derivatives. Thus we conclude that
n (2(2
2 In |
2 {= - - - (1)
1
2
1 2 [b())) - (M)))) In det Jn (=
2 In(2
In |
(23)
Calling this relation E", we consider the difference E E.. Then the determinant term cancels, and we obtain for some constant c(8)
2 (2 n (0) ( (() (1)) マ TT(022
1
(24)
1 (b))) ))) T (1(2) (1))) (()) M²= TTO) c(0).
2
Expanding the quadratic expression on the left-hand side we obtain
1 (2 T م ())) - (1) za
1
(0( θ)2 2 T (1) + 1
2 (1())) T( (00)
(25)
Finally we simplify the last term using
18
(0) (z (B()) T B (B(i) e,, = (B(0) cc, = rf ((1
(26)
Apply the same simplification on the right hand side. Finally, we collect the constant terms indepen- dent of z in (( to obtain
T (0(0) - ((0)) -, (r(0)) 2
(27)
1 - h(2) -6(0))(2))
+ (0)
which is 19 desired.
19

---

A second key ingredient for our identifiability results is that the specific structure of the interventions that each target single node which implies that the difference of precision matrices ( ()) has rank at most This also the key ingredient used (in a very different manner) in the proof of the main result in [84]. Here we highlight this simple result because we make use of it frequently.
Lemma 3. The precision matrices satisfy the relation
+ - ( = -(1)) @ r(0)) - 2(() 2 s()
(28)
Proof. Using 17
we find
(1) ( = (B(i) TB()) - BB
= -BO)T Σ cxek
B B(--B -T
Σ CLCN B
k=1
k==1
(29)
Σ (B(O) TEB ((B(())) Tex) Σ BJ BTex(BTer Tx)T
((BO) ee.) @ ((B()) - (B 10 (() (0) @ 80)
(BTeg) a.) @ (B)
Here we used the fact that all rows except row 4 of B(O) and ((0) agree as the intervention targets a single node, i.e., (B(O)T& T e₁ = (1(O)) T ek for # t4.
A.3
Warm-up
To provide some intuition how identifiability arises, we first provide the proof for simpler result with much stronger assumption on the set of intervention targets and the type of interventions. But note importantly that we don't 't relax the assumption of non-linearity of f.
Theorem 4. Let [(2()) 2 f(Z()) for two sets of parameters ((B(),, () (4))e) J) and (BB6, (i,,,, as in the above model. We assume that there are 2n perfect pairwise dif-
ferent interventions (i.e., Z(i) # z((") for i + f.). without shifts (i.e., - 0). Finally, assume that there are 2 interventions for each node, and we know the intervention targets of the interventions, i.e, we assume that t4 = i, for all i. Then, Z and 7 agree up to scaling, i.e.,
z = ( for a diagonal matrix D Diag(n).
Remark 4. Actually this result can be generalized to a setting where the latent SCM is non-parametric 192y.
Proof. We consider a node and two interventions i and i2 which target node ti, tig (by assumption those interventions exist and i and i2 agree for both representations). Since we assumed that the interventions are perfect, we have in our notation that
(6) = Aí, Sk.
(+2)
(30)
for two constants Xo, * Xi and similarly for 76), Indeed, assuming positivity is not restriction since follows a symmetric distribution (this is also contained the parametrisation (D()) and Xiς # Aj is necessary to ensure that the interventional distributions differ. Combining 20 from Lemma 2 with Lemma 3 we obtain the relation
2 (6)) @ (6)) (6)) 2 (b))
z (e(()) - ()))z
h1==)T(@l0) 6 ((0)))(()))(3)) 2c(()
(31)
= (7(6)) so p(b)) m16)) 8 )((1)) h(2) + 20)))
for j = 1,2.
20

---

Note that since h = ti = tig we have ((+ = s B e* by definition. Thus, we subtract the relation in the last display for i1 from the relation for 22 and find using (3))
(A - - = ===T
(h(2)) ((())) (h(2))
(( + 2(cll)) - (12)))
(32)
= (A X2, (x) + ( ct.))
for all z. Since X, # Xia > 0 we can divide and obtain
X² x2 2 = ha(2)² +2 c(f)) c1(22)
(33)
X2 $2
X2
Since h is surjective, we have that hy is also surjective which implies that the range of the right hand side is (2(c(tx) e(tz))((X( X co). The range of the left hand side is depending the sign of the prefactor and is either (-o0, 0] or 10, oo). Since the ranges have to agree we conclude that c(61) = c(22) and
X
2
hx(2) +
2k-
(34)
X2
X2
Since k was arbitrary, this ends the proof.
L
A.4 Proof of identifiability up to linear maps
The proof of our main result relies on two essentially geometric lemmas and slight extension of Lemma 2 which we discuss now. The first lemma alone is sufficient to handle the case where interventions change the scaling matrix D, while the second is required handle interventions that change B and the third allows us to consider pure shift interventions.
Lemma 4, Let RRd + R be continuous and surjective function, Q a quadratic form on Rd and R constant such that
g(z)² = Q= a
(35)
Then Q has rank and g linear, i.e., g(2) u 2 for some v E Rd
Proof. Assume that Q has the eigendccomposition Q Ei= \aaayy where is the rank of Q and
A * 0 and v, has unit norm. Clearly surjective implies r > O. Since is surjective we find that the range of the left hand side is [0, oo) and therefore Q2 2 -a. This implies that A 2 0 for all and therefore, the range of the right hand side is Ja, oo) which implies a 0. Now we fix any e > 0 and consider E, = (= E R4 Q= = c). It is easy to see that E, is the product of an ellipsoid and d and thus is connected if r 2 2. We find by (35) that g(2) = = for E. and if (2) E {-ve, V then E Eg. By continuity of and since Ee is connected this implies that g(2) = /c for all E E. or g(2) /e for all z E E. contradicting the surjectivity g. We conclude that r = 1, i.e. Q = aaanyy ē o with ō = VAroi. Thus we find that
g(2)² 10g 212
(36)
Since g continuous, this implies that g(2) -ū 2 or g(2) = - 2 As only the first functions are surjective we conclude that g(=) = + and the claim follows with = +
To handle shift interventions we need a slightly stronger version the lemma above which contains an additional linear term.
Corollary 1. Let Rd + IR be a continuous and surjective function, Q a quadratic form on IRd, E IRd vector, and a E R. constant such that
g(z)² Q2 + w + a.
(37)
Then Q has rank and g is affine, i.e., g(2) = .. z + e for some v E Rdd and c R.
21

---

Proof. Assume as before that Q has the eigendecomposition Q Ei= i where is the rank
of Q and X + 0 and ly I. First, we show that E (V)...., U,) where (.) denotes the span.
Indeed, suppose that this is not the case. Then we could find zo such that for 1 S S r, and therefore 2g Q=o O. Plugging
< 0 and 2ge; = 0
Azo for - oo in (37) the right-hand
side tends to -o while the left-hand side is non-negative. This is contradiction and therefore w E (VI,..., U,) holds. This implies that there is w' such that Qw' = w/2 and thus
Q= + w
(=+ w²) Q(z + ((=++w)++ a w' Qw'.
(38)
Then we consider g(3) = g(ž w'), ā =- w Qu' which satisfy
(3) g² w')
(39)
(3 w' 4'+wil +w') Q( - w/ + +w)) w' Qw
(40)
= QE +
(41)
Using Lemma we conclude that Q has rank and ī(ž) for some 0(2 + w²) = u + w' which concludes the proof.
But then g(z)
The second lemma is similar, but slightly simpler.
Lemma 5. Assume that there is a quadratic form Q, a vector 0 & w E IRd, w' E ERC, a E R and continuous function Rd R such that
((z)(w= 2) = z 2- + w' 2 + a.
(42)
Then g(z) --= e for some v E Rd, C I, i.e. g is an affine function.
Proof. By rescaling we can assume that has unit norm. Plugging in z we find that a Denote by Ih the orthogonal projection on w, i.c., 11 v = (w v.w and by 11 the projection on the orthogonal complement of w, i.e., 2 = II + =1 z for all E Rd. Then we find for all
0 = I =) ) IT = (T QU + (T w'_
(43)
By scaling we find that both terms the right hand side vanish and thus for all
(I==)) QI z 0, (m==) w' O.
(44)
(45)
This implies (using also the symmetry of Q)
g(=)w- II = g(z)w=
2 Q2 + w'
(IIm + 2)
2I) + w/ (In + =1
(46)
(Im==) QII, 2[I 2I= QII + Im w/
(mm (Q + 2T - w').
Now n (w mT and find
g(2) II (w 222 (Q(II, + 2II 2) + w').
(47)
This implics
9(2) w QII 2) + w/
(48)
for all 2 such that 2 + 0. By continuity we conclude that this holds for all 2, i.e., g is affine.
O
Again we need a slight generalization of this lemma. Corollary 2. Assume that there is quadratic form Q, vector 0 * E TRd, w/ E Rd,, a, E IR.
and a continuous function id + R such that
(( + 8) Qz + w'
(49)
Then g(2) v. + for some E Rd. F. i.e.. g is affine function.
22

---

Proof. Define g(2) = g(ž - /Bwlwl -). Then
( (w+ 2) = g( - -Bwluu |u| ) (2 Bw|wl [o] (2) + (3)
(3 -wl uo -3 Q(2 Bw/w| -2) w' - Bw/wll (oop +
(50)
QE + i +
for some and ã. So, we conclude from Lemma 5 that ğ is affine and thus the same is true for g-
We now discuss small extension of Lemma 2 by showing that we can complete the squares in which then allows us to obtain a relation that is very similar to (20).
19
Lemma 6. Assume the general setup as introduced above and also ) f O. Then there is a vector ((() and constant such that
(= (2
(z- -
= (z (2- 10000-00 ((1)) +c. (51)
(10))
Using the symmetry of the precision matrices and expanding all the terms, we can express the difference of the left-hand side and the right-hand side of (5T) as
Proof.
(2 (x) T - -1()) - 2 [T)0)) (z - -0-)))) ( - (2 -1()) - 1
= -- 22 (( o0h) )0 + (1()) (0) (u((0)) (()()) @ N(0
(52)
Hence, we can set at the end such the constant terms cancel and all we have to show is that there exists j/(() such that
(e O)₂ (1))
(53)
This is clearly not true for arbitrary ((() because ( - has only rank 2. However, such a μ((1
does exist for (+) = 1)(00()))) (see equation 188 Indeed, we can simplify using (17) and
Lemma 3
(0 - 0)₂(() = (()(0)))))) ( (() ((())
(54)
000 10 (B))) T (
(B()) n (B()) et, = (0)00
(55)
Now there are two cases. When (-()) and s (i) are collinear (but not identical, by assumption) we can choose (²(+)) = (9 for suitable A. Otherwise, we can pick any vector y2(()) such that (((()
(0) (9) This is always possible for non-collinear vectors (project y(8) on the orthogonal complement of g(9).
Let us now first discuss a rough sketch of the proof of our main result. This allows us to present the main ideas without discussing all the technical details required for the full proof of the result. We restate the theorem for convenience.
Theorem 3. Assume that (() is generated according to a model 1B,,, to tt)set. f) such that the Assumptions 7 hold. Then have identifiability up linear transformations, i.e. if ((B(,, (70), ,7))), F,,,, generates the same observed distributions f(Z(0) 2 ((),, then their latent dimensions agree and there is an invertible linear map T such that
j f=foT=
700 = TZ(
(5)
Proof Sketch. Sketch. have two sets of parameters (BB() (t)sse) f), (B(0) (3(0)))))))) f) generating the same observations. ((B()tt)se))
For simplicity of the sketch ignore shift interventions here. We assume that
We can relabel the interventions i and the variables Z, such that & and such that 1, 2, .. is valid causal order of the graph. The general idea is to show by induction that (h1 (2)( ... hu (z) is linear function of z. Let us sketch how this is achieved. The key ingredients here are Lemma 2 and Lemma Applying (20) from Lemma 2
in combination with Lemma we obtain
(0+++)) - ())) = h(x) (G(K+1) @ p(++1) 3(++1) 1) & 3(k+1)))(2) + (k++)
(56)
2
2
23

---

By our assumption that the variables Z follow the causal order of the underlying graph, only the entries (((+1) for S k + are non-zero and similarly for g(++1), Therefore, the right-hand side is a quadratic form of (h1 (z)......
Now we apply our induction hypothesis which states that (/1 (2). (z)) is a linear function of z. Then we find expanding the quadratic form on the right-hand side that there is matrix Q, vector v, a constant ò (which we here assume to be non-zero) and another quadratic form Q' such that
1 2 Q'= = 2² =T=== + (v. 2)/x+1(2) + (2) + clk+1)
2
2 Q= + (1)+((s) + (U-2)
2
(V-2)2
(57)
+ clk+1)
25
46
Now we can apply Corollary ! to conclude that h (z) is an affine function of z. Adding the shifts
and considering also the case ò = 0 adds several technical difficulties, which we handle in the full proof.
After all those preparations and presenting the proof sketch, we will finally prove our main theorem in full generality.
Full proof of Theorem 3 As the proof has to consider different cases and is a bit technical we structure in a series of steps.
Labeling assumptions We can assume without loss of generality (by relabeling variables and interventions) that the variables Z; are ordered such that their natural order i 1, is valid topological order of the underlying DAG and that intervention 1 I S n targets node Z,, i.c., F, = i. We make no assumption on the ordering of the Z; or targets of 4 which are not necessarily assumed to be pairwise different. Recall that we defined (and showed existence of) h = f- in Lemma (including the fact that their latent dimensions agree).
Induction claim We now prove by induction that hy (2) is linear for k 2 0. The base case & = 0 is trivially true. For the induction step, assume that this is the case for j S k, i... hy(2) my 2 for some mij E Rdd We define Mr- (mi,..., mz) so that we can write concisely
(hr ... T=(=)) M₁2
(58)
Note that since h is surjective Mr has full rank. To prove the induction step, we need to show that there exists m Rd such that hx+1(z) m*+11 z.
Precision matrix decomposition For the DAG T underlying Z, let PA, denote the indices of the set of parents of Z, and let PA, = {i} U PA, Recall the notation 3(0) = B e, (using f; = i) and (+) (B())Te Tea. Now
=(1) 8) + 0 only holds if j PA, and ordered the variables such that PA; [... In particular, z(() 0 and v5 0 for j > i (interventions do not create new parents).
By Lemma we have
( - (0)) = ( 2 p(0) 3(0) x x(0)
(59)
We find that
(b++1) - ((0) ),, 7L k +( (1+
-(t++) =
(60)
ifr 1 k + 1. In particular, there exists a symmetric A ((*+1)x(*+1) such that
b+1
((() ((0))((z)= Σ (()))
(61)
Now we decompose as
1 = A' b
(62)
8
24

---

for some A' E Rexk b E R and ò E R. Using the induction hypothesis we find
k+1
-100)(()) =
Σ h, (x)))/,,),,())
(63)
1,5=1
Maz A' A'M + 2h 1 (2)6 M&2 1
We the notation Uy RR for the vector (Vi, (U1,...,,1) UU) Then we write
ry (k+))(()+1) h(=)) = (1++))))(+)) MM + 1/ (++ 1)(k+1)) k-1 (x41(2)
(64)
Now we have to consider different cases.
Case 8 + We assume first that å + O. In this case we find using the last two displays
h(2) (6((+1)) - -6(0)) - 11+ ((())))))))))))))))))))))))))))) c(++1)
nt Ma - (b+1))
=z. M A' A'M + 8 [MAtI(2)+ +
5
k++
8
1
M bb
Maz
(65)
2 (1+1) Maz - (n) ((++))) (1 k+1
11)
Maz + (b+1))
+ 8
k+1
Next we set
9(2) h (2) + + M42 8- 111n (++1)
T+1
(66)
Looking carefully at 665 we find that there is a symmetric matrix Q vector w. and constant ō such that
((=)((((++))) (()))(>>) 21y (k+ 1) M(=) = 5g(z)² + Q wz +
(67)
We claim that g is continuous and surjective. Continuity follows directly from continuity of h.
To show that g is surjective we can ignore the constant shift, and we note that o 6-1y Mg =
8-1 Σ 1= ,,,,(2 (2) and thus surjectivity of h implies that g is surjective (for every pickk such that h (2) and (2) for k).
Using
19 from Lemma 2 we conclude that
5g(2)² 2 (0(++) - ((0) - (++ (1+) 11.++11 - Q2 -2
(68)
Q2 + w + a
(69)
for all z and some symmetric Q Rdxd
IRd. Corollary 1 then implies that
hx+1(=) - uM 1 8-1 1 (k+1)
(k+11) g(z) 2-2 k+1
(70)
for some Rdd C E. Thus hx+1 1 is an affine function, i.c. h241(2) m + a. But
0 EZ EZ mk+1 =a=a
(71)
and therefore h141 is linear.
Case 5 0, b + similarly to above
Now consider the case that 0 6. Using
63 (64) and 19
find
M AM + (2)0 Mg2 - (k+1) M - (x+1)) (k+ het1(2) + ((++))
*k = =
k+1
(00)) - (k+))
(k+1)2
(72)
Collecting all terms we find that h&+1 satisfies a relation of the type
h (2) 3) Q2 + w/ + a
(73)
for suitable Q, 8, w. w', and a. Note in particular that w: T = 2b M₁ * 0 because Mj has full rank.
w A O then Corollary 2 implies that hz(2)) is affine and, as argued above, we conclude that by linear.
25

---

Case 8 = 0, b 0 It remains to address the case b = 0 and ò = 0. Going back to the definition of b and 6 (see (6T) and ( we find
(b (b",5)= = =T ((++)) k+] (k++)))
(k++1) ((++1) (1++1) ((++1)
(74)
Now 8 = 0 implies g(k+1) = x(k+1) (because they are both positive), But then we conclude k+1
kk+1
p(k+1) = g(++1) from b = 0 and Fr x(++2) Sy
(k++)) = for r > k + 1. This implies
t [ ( = p((++) @ p(++1) g(++ @ g(h+1) =0
(75)
That is. this implies that intervention A + 1 is pure shift intervention, i.c., B ((++1) and
of (1++1)) + 0 (otherwise we do not actually intervene). In this case, we conclude from Lemma 2 and
Lemma 6 (if (k+1) * ()
( 1) h(2) + clt+1) = (2 (2- ( (o(k+1) () (/(+t) +c.
(76)
But then 17 ( V Vh((d(k+1)) 0, this implies that Vh is not invertible which is a contradiction
to h being diffeomorphism. Thus, we conclude that also ( = O, i.e., intervention k + is
also a pure shift intervention for the Z variables. But then we find
((++1)
(2) + ckk
(1++1) M+ ( ((+)))) + cl))))).
1+11
So finally conclude that also in this case h&+1 is linear function, this ends the proof.
B From Linear Identifiability to Full Identifiability
In this section, we provide the proof of Theorem T which a combination our linear identifiability result (eeoorem]pproveddd in the previous section and the main result of (84) which shows identifiability for linear mixing f. However, we need to carefully address their normalization choices and in addition consider shifts.
We emphasize that the full identifiability results could also be derived from our proof of Theorem by carefully considering ranks of quadratic forms and showing that we can inductively identify source nodes. We do not add these arguments as our reasoning is already quite complex and because for linear mixing functions this is not substantially different from the original proof in [84].
For the convenience of the reader, we will now restate the main results of 84 For our work is convenient to slightly deviate from their conventions, i.e., we define the causal order of graph by i - iff E aj)),, in particular i + implies < j.
We rephrase their results using our notation. Let S(G) denote the set of permutations of the vertices of G that preserve the causal ordering, i.e., all permutations p such that p(i) < p(j) if j. They consider linear mixing functions as specified next.
Assumption 5. Assume f(z) = I= for some matrix I, E TR.d xd with trivial kernel and pseudoinverse
H L+ such that the largest absolute value of each row of H is one and the leftmost is positive.
Then the following result holds.
Theorem 5 (Linear setting, Theorems and 2 in 184) Suppose latent variables (00 are generated following Assumptions 2 and 3 where (6) = 0 (i.e., no shift) with DAG G and all A are lower triangular. Suppose in addition that Assumptionnhhole and the mixing function satisfies Assumption Then we can identify intervention targets and the partial order -G of the underlying DAG G up to permutation of the node labels. If we in addition assume that interventions are perfect the problem identifiable in the following sense. For every representation (B(e) H) such that all B(û are lower triangular and (()()) (i) where T. H+ there is a permutation S(G) such that
- H.
B = -P
(78)
Remark 5. A few remarks are in order.
Compared to their statement in Theorem 2 we replaced Pa by P because we used the transposed convention for the permutation matrices.
26

---

2. Note that their result per se doesn't it mention identifiability up to scaling but that's ' because part of their assumptions involve normalizing f. Since we don't 't normalize the linear map f. we add scaling in the theorem statement.
3. For the case of imperfect interventions, their result talks about identifiability of the transitive closure G of the graph G, but this is the same as identifiability of the partial order -G that we state here.
4. We assume that interventions are not only acting on the noise but do change the corre- sponding row of A. Note that this is equivalent their genericity assumption which states that
,() =(B()) et, = = -Id-AAh) )c. (D)))) 8(0 = (B(o)) (Id A ){, (Di0))
(79)
(80)
are linearly independent. Indeed, this holds iff 100 + A! (by acyclicity A
0).
Let us provide brief intuition why this result holds. The key ingredient is the same as in proof of linear identifiability above, namely, Lemma] which reads
+ (c) - θ = (+) @ (0)
(1)
(81)
This expression has rank if & is not a source node in the causal graph and the intervention is not a pure noise intervention because s(6) and p()) are linearly independent as explained in the remark above. On the other hand, this expression has rank one for source nodes because s( oc et, in this case and the same is true for ,(, This allows us to identify interventions on source nodes. Moreover, (0) - (*) has rank 2 if intervention and lc target different source nodes and rank if they target the same source node. Thus we can also identify the set of interventions targeting the same source node. One can complete the proof by an induction argument based on removing source nodes from the graph and studying the effect on the precision matrix of the latent variables.
We are now ready prove our main theorems.
Theorem 1. Suppose are given distributions X generated using model ((B(), .7()) ts)ier. f) such that Assumptions 4 hold and such that all interventions i are perfect. Then the model is identifiable up to permutation and scaling, i.e., for any model ((B(1) ,700 &. that generates the same data, the latent dimension agrees and there is a permutation E Sa (and associated permutation matrix Pa)) and an invertible pointwise scaling matrix A E Diag(d) such that
T, w(,),
Ba0 = BOA- J=SoA-iPa
1 = (9
This in particular implies that
700 2 AZ()
(4)
and we can identify the causal graph G up to permutation of the labels.
Proof of Theorem Suppose there are two representations ((B6), 4)ier, f) and ((Bl) 7 Beser, f) of the distributions X 2 O. As explained in the proof of Theo- rem we can assume by relabeling the nodes that the matrices B(() are lower triangular and the corresponding DAG G has the property that for every edge + we have i < j. We now apply Theorem 3 and find that there is an invertible linear map T such that f = f o T and T 2() 2 20, One minor difference to the setting in [8] is that we in addition consider shift interventions. They are simpler to analyze than a change of variance, but we can avoid additional
arguments with the following trick. If ) ()) for some we replace z N (p((), y())
by (z(() = (0, y() (+) (I)),, otherwise we set (7 N (0, ()) and similarly for Z.
Then (Z 2 7 implies (=)(2 _ ZOO), Using (3) and 17 can be shown that this
distribution corresponds to a change of variance of the noise, i.c., a change of D())
444. This can
also be seen directly from the relation ())) 2 (B(O)- + n ('ea)))) where e' ~ N 1) and
27

---

independent of c. We can now apply Theorem t to the primed distributions. We first find a unique invertible Diag(d) such that AT has largest absolute value entry 1 in every row (and in case of ties the leftmost entry is I). We can also find a permutation p E Sa such that B P, B I is lower triangular for all i (note the distinction between B and B()) Indeed, this is possible since the underlying DAG G is acyclic by assumption, interventions do not add edges, and A is diagonal. Then find
TPPPP (B0 (T- (B(0))
(82)
-B))
(83)
_ (B()))- le.
(84)
Here the last step follows from the fact that 7(1) 2 7(0) which implies that the centered distributions agree.
Now can apply Theorem 5 (with B replaced by B and identity mixing) and find that for the alternative representation in terms of B
PAT = P. ld,
B = 3PP B
(85)
for some p S(G) because by assumption B(0) and B are lower triangular. This implies that
T = A- P..
(86)
B = P.P ( Pp P P.P.T. PoPAA.
(87)
To summarize, there is permutation (p ) 0 -1 (note that PaPp Ppoo) and a diagonal matrix such that
B = PcB A, T= A 700 = (7)) = A Pp,00
(88)
We also find the relation (1+) T, from here because Pue; cw (w)-((- Equating the means of T-1 2 and ())
we find
(B ET, -T (B())) el.
(89)
Multiplying by B(0 we find
7/ e7 = (B()) 1 PT ee:
(90)
and we conclude that 77(0 (8)
Theorem 2. Suppose we are given the distributions X(0) generated using a model (B (79 (1)iiii f) with causal graph G such that the Assumptions 4 hold and none of the interventions is a pure noise intervention. Then for any other model (B 7() F)eer. with causal graph G generating the same observations the latent dimension d agrees and there is permutation w E S4 such that f = (t;) and i ig j iff w(i) <a w(J), ie., Ka can be identified up permalation of the labels.
Proof of Theorem Suppose there are two representations ((B(), ,7((0 (4))er and (BB() 7709, J)) of the observational distribution. As shown in Theorem there is linear map such that (1)
Z00 Then the same is true for the transformed variables as explained above. Viewing ( as new observations obtained through a linear mixing we conclude from Theorem 5 that -G and the intervention targets are identifiable up to relabeling.
L
C A comparison to related works
In this section, we will discuss the relation of our results to the most relevant prior works and put them into context.
28

---

This work considers linear mixing functions f. and we directly generalize their work to non- linear f. In particular, their techniques are linear-algebraic and do not generalize to non-linear (see more technical details in proof intuition in Section 4) we handle this using mix of statistical and geometric techniques. Notably, their finding that the linearly mixed latent variables are recoverable after observing one intervention per latent node is closely related to an earlier result in domain generalization, which showed that a number of environments equal to the number of "non-causal" latent dimensions can ensure recovery of the remaining latents [71], and later work showing that this requirement can be reduced further under linear mixing with additional modeling structure 72). This connection is not coincidental that analysis was for invariant prediction with latent variables, which was originally presented as a method of causal inference using distributions resulting from unique interventions [62]. Later this approach
84
applied for the purpose of robust prediction in nonlinear settings [25], but the identifiability of the latent causal structure under general nonlinear mixing via interventional distributions remained an open question until this work.
This work also considers linear mixing f. but allow for non-linearity in the latent variables. They use score functions to learn the model and they raise an open question the setting of non-linear mixing, which we study in this work. While the models are not directly comparable, our model is more akin to real-world settings since it's not likely that high-level latent variables are linearly related to the observational distribution, e.g. pixels in an image are not linearly related to high-level concepts. Moreover, Gaussian priors and deep neural networks are extensively used in practice, and our theory as well as experimental methodology apply to them.
88
While they do not discuss interventions, this work considers the setting of multi-environment CRL with Gaussian priors and their results can be applied to interventional learning. When applied to interventional data as in our setting (as also shown in [84, Appendix DJ). they require additional restrictive assumptions such as d = d', a bijective mixing/ f and e S d where e is the number of edges in the underlying causal graph whereas we make no such restrictions on d, f and e (therefore. the maximum value of e can be as large as R d² /2 in our setting). And when these assumptions are satisfied, they require 2d interventions whereas we show that d interventions are sufficient as well as necessary.
48
This work also considers the setup of interventional causal representation learning. However, their setting is different in various ways and we now outline the key differences.
2
1. Their main results assume that the mixing I is an injective polynomial of finite degree p (see Assumption 2 in their paper). The injectivity requires their coefficient matrix to be full rank, which in turn implies d' 2 E ("Z-)) (a+d) (see the discussion below Assumption 2 in their work). This means that we cannot set the degree of the decoder polynomial to be arbitrarily large for fixed output dimension d' (which is required for universal approximation). In contrast, we only require d' 2 d. For general discussion of the relation between approximability and identifiability we refer to Appendix E
2. All their results for general nonlinear mixing functions rely on deterministic do-interventions which is a type of hard intervention that assigns a constant value to the target. However, we focus on randomized soft interventions (and also allow shift interventions which have found applications 773, 58) ). which as also pointed out by [84] 87 is less restricted. Moreover, they require multiple interventions for each latent variable (as they use an c-net argument) to show approximate identifiability, while the structural assumptions on the causal model allow us to show full identifiability with just one intervention for each latent variable. Thus, their setting is not directly comparable to ours and neither is strictly more general than the other. particular, their proof techniques and experimental methodology don't 't translate to our setting, and we use completely different ideas for our proofs and experiments.
D Counterexamples and Discussions
In this section, we first present several counterexamples to relaxed versions of our main results in Section D.I and then provide the missing proofs in Section D.2
29

---

D.1 Main counterexamples
In this section, we will discuss the optimality and limitations of various assumptions of our main results, In particular, we consider the number of interventions, the distribution of the latent variables, and the types of interventions separately.
Number of interventions Our main results all require d interventions, i.e., one intervention per node. This is necessary even in the simpler setting of linear f as was shown in [84] Proposition 4], directly implying it is also necessary for the more general class of non-linear f that we handle here. Therefore, the number of interventions Going a step further, it is natural to ask whether Theorem remains true for less than d interventions. However, as we show next, d interventions are not sufficient.
our main theorems I 2 is both necessary and sufficient.
Fact 1. Suppose we are given distributions X(6 generated by ((B(), ,T((), (,)(), .4)sEI,)) satisfying Assumption 3 If the number of interventions satisfies [I] S d it is not possible to identify f up to linear maps. Consider, e.g. d and Z (0, Id) and no interventions. Then h(Z) 2 for (nonlinear) radius dependent rotations as defined in (29 9V.
Let us next consider the case with total of environments which corresponds d interventional distributions plus one observational distribution. We can provide a non von-identifiability result for general class of heterogeneous latent variable models that satisfy an algebraic property.
Lemma 7. Assume that 2 and Z N(, ) Z (0, E and Σ > O or
((1) (()) in Löewner order (i.e., the difference is positive definite). Then there is a non-linear map for h such that h))()) 2 for 0,
0,
We provide proof of this lemma in Appendix D.2
Note that this non-identifiability lemma requires 3 in Appendix we have seen that for the interventions considered (1) generally does not hold. This is some weak indication that for Theorem 3 d - interventions might be sufficient. We leave this for future work.
the assumption on (6) In Lemma
in this work the relation (00) () (1)
As additional note, in the special case when f is permutation matrix, we are in the setting of traditional causal discovery and here, d - interventions are necessary and sufficient [0 18 [8]].
Type of intervention Even when restrict ourselves to only linear mixing functions considered as in (84), we need perfect interventions in Theorem I Otherwise, only the weaker identifiability guarantees in Theorem 2 can be obtained. This is shown in [8] linear f. Therefore, in the more general setting of nonlinear f. we cannot hope to obtain Theorem [ with imperfect interventions, showing that this assumption is needed.
Next, we clarify that for the identifiability result in Theorem are not pure noise interventions is also necessary.
2 the condition that the interventions
Fact 2. Recall that defined B(O) ((B(), ,,(,,,,,,),), (t)see) f) satisfying Assumptions
A Suppose ( is generated by 4 where all interventions are pure noise interventions. By definition, this implies A = for all i. Consider any matrix such that the corresponding DAG is acyclic. Then (Bt)), 17 t.)ver, with B(G = (D())= - & (Id for all i and
f= fo (Id A) + (Td Ā) = f (Id - A) -Id (Id-A) A) (91)
generates the same distributions (9) Indeed,
ア(ž()) f ( (B (ee))) - = = - A) - 1) (()))
=[((I- ( ()),))
(92)
=(((B")>\(et""" ((+n)))))))))))
= =S(Z())
This implies that any underlying causal graph could generate the observations. In other words, for pure noise interventions can identify the scale of the noise variables, but we obtain no intervention
30

---

about the causal variables and structure (exactly because the interventions do not target the actual causal variables but the noise variables).
Finally, we remark that in contrast to the case with linear mixing functions, we need to exclude non-stochastic hard interventions for linear identifiability.
Lemma 8. Consider d 2 and O (0, Id) and the non-stochastic hard interventions do 0) and do 0) resulting in the degenerate Gaussian distributions Z (N, e2 @ E2) and 2 ((, en @ e1). Then there is a nonlinear h such that h(((()) _22 7 for all i.
Intuitively, to show this, we choose h be identity close the supports {Z) = =0} and (Z = 0} but some nonlinear measure preserving deformation in the four quadrants. The full argument can be found in Appendix D.2] similar counterexample was discussed in (2]. However, here we in addition constrain the distribution of the latent variables, which adds a bit of complexity.
Distribution of the Noise Variables Our key additional assumption compared to the setting considered 84 88 is that we assume that the latent variables are Gaussian which allows us to put only very mild assumptions on the mixing function f. However, do this in a manner so that we still preserve universal representation guarantees.
[88 consider arbitrary noise distributions but restrict to linear mixing functions. We believe that our result can be generalized to more general distributions of the noise variables, e.g., exponential families, but those generalizations will require different proof strategies, which we leave for future work. However, the result will not be true for arbitrary noise distributions, as the following lemma shows.
Lemma 9. Consider ((0) = (61, T2) z() = (2), and 7(2) = =(1, (2) where 61, ~ u(]-1,1]) and é, 62 ~ u(1-3,3), 3).. Also define ( = ( ci -22, 2 = (á, + c2), and 7(2) ((1, 6)). Then there h such that
h)Z()) 2 2
(93)
proof of this lemma can be found in Appendix D.2 The result shows that even with perfect interventions and linear SCMs it is not possible to identify the underlying DAG (empty graph for Z and Z - Zz) and we also cannot identify f up to linear maps. While our example relies on distributions with bounded support, we conjecture that full support is not sufficient for identifiability.
Structural Assumptions A final assumption used in our results is the restriction to linear SCMs. This is used for most works on causal representation learning (see Section []. even when they restrict to linear mixing functions. Although this may potentially be nontrivial restriction, the advantage is that the simplicity of the latent space will enable us to meaningfully probe the latent variables, intervene and reason about them. Nevertheless, it's an interesting direction to study to what generality this can be relaxed. Indeed, even for the arguably simpler problem of causal structure learning (i.e., when (() observed) there are many open questions when moving beyond additive noise models. We leave this for future work.
D.2 Technical constructions
In this section, we provide the proofs for the counterexamples in Section D.I For the first two counterexamples we construct functions h such that h h()()) _ z by setting h = 4, where $ is defined as the flow of a suitable vectorfield X, i.e.
0. = x(
(94)
This is a common technique in differential geometry and was introduced to construct counterexamples to identifiability ICA with volume preserving functions in 9 g. To find suitable vectorfield X we rely on the fact that the density Pt of Pr, = (t.). P satisfies the continuity equation
dxp:(z) + (i)()) = O.
(95)
In particular P.- = P holds iff
(x)(p(())X())) = 0.
(96)
31

---

Therefore it is sufficient to find vectorfield X such that Div(p() X) = 0 for all environments to construct a suitable h 1
Lemma 7. Assume that d = 2 and ( N(0, ) z N(, E and E > Σ or E(0) Σ(0) in Lüewner order (i.e., the difference is positive definite.. Then there is non-linear map h such that () 2 z(8) for = 0,
Proof of Lemmal 7 Let us first discuss the high-level idea of the proof. The general strategy is to construct vectorfield X whose flow preserves Z for i 0, 1. This holds if and only if the densities Po. P1 of ())), z satisfy
Div(poX) Div(pIX)
(97)
Using Div(fX) = ff X Div X we find
X V(Inpo(=) In X Vpo(z) (=(2)
X- Vp)
po(z) Div X Pi(z) Div X
pz(z) 0.
(1(2)
Po(z)
(98)
We conclude that any X satisfying (97) must be orthogonal po (z)) and thus parallel to the level lines of In po()) - pi) This already fixes the direction of X and the magnitude can be inferred from (97). To simplify the calculations we can first linearly transform the data so that the directions of X. i.c., equivalently the level lines of in Po(2) - In p1 (z) have a simple form. We assume that 2g < E. Clearly, it is sufficient show the result for any linear transformation of the Gaussian distributions ((0), Note that generally for G Nu, Σ) we have AG N (Ap, AEAT) Applying reduce the problem to Id Σ In E Eg Diagonalizing Σ/ by U SO(d) it is sufficient to consider ld < A UE U where A = Diag(A, A2). Finally, we can rescale =1 and 22 such that the resulting covariance matrices A Diag Aq, X9), A Diag(A}, A1) satisfy
Eg
1
1
1
=1
(99)
Ap
A1
X2
Thus, it is sufficient to show the claim for such covariances A A and the result for arbitrary covariances follows by applying suitable linear transformation.
For such covariances we find for some constant
z 2x
(n)p - In(p) (=))
+
+
(100)
2X
2X
2X1
The level lines are circles. Thus, we consider the vector field
(-22
Xo(=)
(101)
21
We see directly that Div Xo = 0. We consider the Ansatz X(x) = f(lll)xo(z)/ppo We now
fix the radial function f R+ + F such that has compact support away from We find using
Div No = 0
Div(X())po(=)) = Div(X(x))
(102)
= =oolz)= (V|=))f((=)
(103)
22
2 (((;)
(104)
(105)
Note, that close to 0 where |a| is not differentiable the vector field vanishes by construction of f. We find similarly using (100)
Div(X())p((z)) =x(=)) (f(1=)) (1(=)))2(3) P1(2)
(106)
Po(2)
=oo(=) (1(1=))e-1APP-9
(107)
32

---

Z
R2
2(2)
Q2
z(1)
h
Z
2
(()
R1
Q1
Figure 4: Sketch of the setting in Lemma 9
The map h agrees with (æ1, 22) + (21, + 22) on the red rectangle and maps R Q2 such that the uniform measure is preserved.
Xo(z) v)([=))
(108)
(109)
Finally remark that the flow 4, of the vectorfield X generates family of functions h desired, i.e. for all f we have (..). 2z( and o is clearly nonlinear as it is the identity close to 0 but not globally.
The proof of the next lemma is similar but simpler.
Lemma 8. Consider d 2 and z (0, Id) and the non-stochastic hard interventions do 0) and do 0) resulting in the degenerate Gaussian distributions 2 N(0,, 62 @ 02) and 2 N(0, @ e1). Then there is a nonlinear h such that h(((()) 2 g for all i.
Proof of Lemma g Pick any smooth divergence free vectorfield Xo with compact support in (e, o2) for some > 0. Then the vector field X Xo/Po satisfies
Div X = Div X, = 0.
(110)
Thus the flow t; preserves the distribution of (( But it also preserved the interventional dis- tributions (4) for i = 1,2 because X(z) = 0 and thus (2 = for close to the supports of z()
Finally we prove Lemma that shows that we cannot completely drop the assumption on the distribution of the noise variables e.
Lemma 9. Consider Z = (T, z (4, (2). and z (2) where 61, '2 ~ u([-1 (1)) and é4,6/ u[133,3)) Also define (10) (e1,e1 + E2). 7(0 (éi,e) + 62), and
( (G1, C)). Then there h such that
h(Z(1) 2 Z
(93)
Proof of Lemma A sketch of the setting can be found in Figure We define ho(2) = (21, 21 + 22) l1(2) ho(2) for S 22 S we find l( D 7 for and 1. It remains to modify ho such that l preserves the uniform measure - 1, 1] [-3, 3). We do this in two steps, first
33

---

construct a modification h of the map hy such that [-1,1] x [-3,3] is mapped bijectively to itself but = ho for |22| < (so that (()))) _ ( for i = 0 and = 1 holds) and then we apply a general result to make the map measure preserving. We start with the first step. Let v R [0, 1]
be differentiable such that (b( = 1 for -1 v = S and (b) = 0 for - 5/2 S S 5/2 with | (1) < Then
h(2) - (22)) + (1 (00--((222)) (x22)) = 22 + (22)
(111)
is injective on [] [-3,3] (note that the second coordinate is increasing in 22) and maps
[-1,1] x [-3, 3] bijectively to itself and agrees with hg for |2ا| S 1. However, is not necessarily volume preserving. But applying Moser's theorem (see [56]) the image of the rectangles R₁ and
and R2 = [--1, 1]x [1,3] which are the quadrilaterals QI = h(R)) with endpoints
(-1, -3), (1). (-1, 22) and Q2 = h( R2) with endpoints (1,3), (-1,3), (-1,0), (1,2) with the same size as Ra and R2 we infer that there is sp supported in Q1 U Q2 such that h = p o h
satisfies 1((1))) _ 2 _ u([-1, 1] [-3,3])
E Identifiability and Approximation
In this section, we explain that approximation properties of function classes cannot be leveraged to obtain stronger identifiability results. The general setup is that we have two function classes G F and we assume that G is dense in F (in the topology of uniform convergence on Q), i.c., for f E F and any e 0 there g E G such that
sup [(=) - [0)] <. =e0
(112)
We now investigate the relationship of identifiability results for mixings in either 9 or in F.
While this point is completely general, will discuss this for concreteness in the context of nonlinear ICA and considering polynomial mixing functions for g. We also assume that F are all diffeomorphisms (onto their image). Suppose we have latents Z [[[[1, 11")) and observe mixture X h(Z). We use the shorthand f 1] from now Let suppose that h E g. Then the following result holds.
Lemma 10. Suppose Tz) 2 M(Z) where ~ U(2), h, h E 9 and satisfies an injectivity condition as defined in Assumption 2 in (2). Then h and h agree up to permutation of the variables.
Proof. This is a consequence of Theorem 4 in 2 Essentially, they show in Theorem 1 that and agree up to linear map and then use independence of supports to conclude (in our simpler setting here, one could also resort to the identifiability of linear ICA).
The injectivity condition is technical condition that ensures that the embedding h is sufficiently diverse, but this is not essential for the discussion here. Let us nevertheless mention here that it is not clear whether this condition is sufficiently loose ensure identifiability in dense subspace of F because it requires an output dimension depending on the degree of the polynomials.
We now investigate the implications for F. It is well known that ICA in general nonlinear function is not identifiable, i.e., for any f E F there is a f E F such that f(2) 2 f(Z). To find such an if one use, c.g., the Darmois construction, radius dependent rotations or, more generally, measure preserving transformations m such that m (Z) _ Z. Then we have the following trivial lemma.
Lemma 11. For every e > 0 there are functions g. ğ E G such that
sup lg fl<,, sup l i<<e a
(113)
and then the Wasserstein distance satisfies W2(f (Z)) <, W (2(F(2)gg(Z) <E
Remark 6. For the definition and a discussion of the Wasserstein metric we refer to (90). Alternatively we could add a small amount of noise, ie.. X f(Z) + v and then consider the total variation distance.
34

---

Proof. The first part follows directly from the Stone-Weierseee Weierstrass Theorem which shows that polyno- mials are dense the continuous function on compact domains. The second part follows from the coupling Z. (J(Z), and (13
The main message of this Lemma that whenever there are spurious solutions in the larger function class F we can equally well approximate the ground truth mixing f and the spurious solution ʃ by functions in G. In this sense, the identifiability of ICA in G does not provide any guidance resolve the ambiguity of ICA in F. So identifiability results in G are not sufficient when there is no reason to believe that the ground truth mixing exactly in G.
Actually, one could view the approximation capacity of G also as a slight sign of warning as we will explain now, Suppose the ground truth mixing satisfies y E G. Since ICA in F is not identifiable we can find f E JF which can be arbitrarily different from g but such that g(Z) f(Z). Then we can approximate by 9 with arbitrarily small error. Thus, we find almost spurious solutions, i.e., I g such that ( (). g < for arbitrary 0 but 9 and g correspond to very different data representations, in this sense the identifiability result is not robust.
When only considering the smaller space G this problem can be resolved by considering norms or seminorms on 9, for polynomials a natural choice is the degree of the polynomial. Indeed, suppose that we observe data generated using a mixing g E G. Then there might be spurious solutions f E F which can be approximated by G but this approximation will generically have larger norm (or degree for polynomials) than g. Therefore, the minimum description length principle (69 favors over g.
This reasoning can only be extended to the larger class F if the ground truth mixing f (for the relevant applications) can be better approximated (i.e., with smaller norm) by functions in G than all spurious solutions J. This is hard to verify in practice and difficult to formalize theoretically. Nevertheless, this motivates to look for identifiability results for function classes that are known to be useful representation learners and used in practice, in particular neural nets. We emphasize that alternatively one can also directly consider norms on the larger space F penalizing, e.g., derivative norms, perform model selection.
F Additional details on experimental methodology
In this appendix, we give more details about our experimental methodology. First, we derive the log-odds and prove Lemma i Appendix [F.T] Then, we use to design our model and theoretically justify our contrastive approach in Appendix F22 by connecting to the Bayes optimal classifier. Then,
we describe the NOTEARS regularizer in Appendix F.3 describe the limitations of the contrastive approach in Appendix G. and finally, in Appendix
we describe the ingredients needed for an approach via Variational Autoencoders, the difficulties involved and how to potentially bypass them.
F.4
F. Proof of Lemma
Lemma 1. When we have perfect interventions, the log-odds of sample x coming from X over coming from x(0) is given by
(8) (x) In (0) Inpx
- - + 1 (-)) (6)
for a constant independent of x.
Proof. We will write the log likelihood of (() f(Z(0) using standard change of variables. As we elaborate in Appendix A.I we have
-t) (B( + (t) with ((0)_
A , -n (B(0)
(114)
Also, denote by (+) = (L()) T B6O the precision matrix of (1) (see Appendix A.1 for full deriva- tion). By change of variables.
(z) = In | In (f (x)) In (x))
35

---

" = In =In1Jy-11-
2 (2(2 In | 1 (10)
- ()
2
where y- denotes the Jacobian matrix of partial derivatives. Let s ;(2),... ((d) denote the rows of B(,). We then compute the log-odds with respect to X the base distribution without interventions (and where μ = 0) to get
Inpx (x)
In (x)
1 In
Σ
T - -
EX
(f (x)) (r 2 (() 10 (+ (1)
G
2
- (1660))))) (
(s
c:
G: (f)
(s()) ( (f)
(=(() + o A (f) 1 500g
(f)
= = 2
for constant e; independent of For the second equality, we used Lemma 3
F22 A theoretical justification for the log-odds model
In this section, we provide more details our precise modeling choices for the contrastive approach, and show theoretically why it encourages the model to learn the true underlying parameters.
Recall that, motivated by Lemma 1 we model the log-odds as
(i 04 Ba, 7is ( 0) = 0; - 3,h (zx 0) + (x, + (M( 0), w
(115)
where h(,,0) 0) denotes neural net parametrized by 6, parameters w) are the rows of a matrix W and Og Si 7/ are learnable parameters. Moreover, we have go = 0 as we compute the log-odds with respect to ( Therefore, the cross entropy loss given by
(=)==1((0)
C ---,((( Exxx)) In
(116)
e +1
Let C(x) E {0, 1} denote the label of the datapoint indicating whether it was observational datapoint or an interventional datapoint respectively. By using the cross entropy loss, we are treating the model outputs as logits, therefore we can write down the posterior probability distribution using logistic regression model as
exp(g(x, az Bi, Yo, w(), ((,0)))))))))))))
0))
Pr[C())
1|x] + exp(g((r, 0z Bi, 7i w((, 0))
(117)
Moreover, by using sufficiently wide deep neural network with universal approximation capacity and sufficiently many samples, our model will learn the Bayes optimal classifier, as given by Lemma Therefore, can equate the probabilities arrive at
exp(9i(#, Oi Be, Yi (0)))) + explgi(z, aq Br, Yi, w))
exp 2 (x) (()) 1np
(0) (x))
(118)
( (z)) 1 exp((1l1 (())) In 1n
implying
0; - B, (I. 0) + tx,,, + (M(z, 0), w0)
(119)
----)~((000))))00))))))))))))))) + n 1 ( (x)) -1))
(120)
This suggests that in optimal settings, model will learn (up to scaling)
02 Cs B x % (9) Xs thereby inverting the nonlincarity and learning the underlying parameters.
w = (0) h(z, 0) f (xx
(121)
36

---

F3 NOTEARS [102]
In our algorithm, using the parameters w(() as rows, we learn the matrix W, which we saw in optimal settings will be B DT11/(Id - A). Note that the off-diagonal entries of B form a DAG. Therefore, the graph encoded by Wo. which is defined to be W with the main diagonal zeroed out, must also be a DAG.
However, in our algorithm, we don't explicitly enforce this acyclicity. There are two ways to get around this. One way is to assume default causal ordering the Z,s. which is feasible as we don't 't directly observe Z. Then, we can simply enforce Wi to be triangular and train via standard gradient descent and Wo is guaranteed to be a DAG. However, this approach doesn't 't work because the interventional datasets are given in arbitrary order and so we are not able to match the datasets to the vertices in the correct order. So this merely defers the issue.
Instead, the other approach that we take this work is to regularize the learnt Wo to model a directed acyclic graph. Learning an underlying causal graph from data is a decades old problem that has been widely studied in the causal inference literature, see e.g. [12 [02] 64 80 4 and references therein. In particular, the work [102] proposed an analytic expression to measure the DAGness of the causal graph, thereby making the problem continuous and more efficient to optimize over.
Lemma 12 ([02)). A matrix W E Rddd is DAG if and only if
R := tr exp(W W) d = 0 where is the matrix Hadamard product and exp is the matrix exponential. Moreover, has gradient
(122)
VR- = exp(W o W) 2W
(123)
Therefore, we add RNOTEARS(W)) = tr expp(W, ( o Wo) - d as a regularization to our loss function. As in prior works, we could also consider the augmented Lagrangian formulation however it leads to additional training complexity. There have been several follow-up works to NOTEARS such as (98 (see 44] for an overview) that suggest different regularization schemes. We leave exploring such alternatives to future work.
F4 A Variational Autoencoder approach
In this section, we describe the technical details involved with adapting Variational Autoencoders (VAEs) 39 68 for our setting, We highlight some difficulties that we will encounter and also suggest possible ways to work around them.
Indeed, most carlier approaches for causal representation learning have relied on maximum likelihood estimation via variational inference. In particular, they have relied on autoencoders or variational autoencoders (36] 22. In our setting, VAEs are a viable approach. More concretely, we can encode the distribution X (0) e, then apply the (+) parameter matrix before finally decoding to X(1,, To handle the fact that we don't 't have paired interventional data as in [6], we could potentially modify the Evidence Lower Bound (ELBO) to include some divergence measure between the predicted and measured interventional data. Finally, this can be trained end-to-end as in traditional VAEs. We now describe this in more detail.
We will use VAEs to encode the observational distribution X (0) to e, so the encoder will formally model B(O) (f) - إقن where we use the notation from Appendix A. Note here that we cannot directly design the encoder to map X to Z because we do not know the prior distribution on Z. Indeed, the objective is to learn it.
Let I denote the set of intervention targets. Assume the targets are chosen uniformly at random, which can be done in practice by subsampling each interventional distribution to have the same size. Suppose we had paired counterfactual data D = UierD, of paired interventional datasets, iee D, consists of pairs (X (x("), (0) with corresponding probability density denoted p (x((), (.)). Following [39 1011, define an amortized inference distribution as ((e)2.(0)). Then, we can bound the expected log-likelihood as
ED In ( (0) (0) [00 = E EDD (np (x())
(124)
= =ELun ED, In / (x(0)(()), c) de
(125)
37

---

= =E RD, In [100) x000, ,000 <)g(e(>((0))
de
(126)
{(c(x(0)))
p(1) x,11),,x01, ,x((,,))
BD In (emg(e/2(0))
(127)
g(cl2((0)
2 B B Pemotaton In ( (z(0)
(Jensen's inequality)
((E(x(U))
(128)
= =R ED Eemgtattn) In p (x(0) x0)) e)p(()
(129)
((Elx(0)
-BDunn) (Enggteto (x (00(c) E Eeng(x()) In {(c(x:(0))
p(e)
(130)
E B(100,)) Eematelotonn [In (n (x) [000c
(131)
KL(g(el="))) r))
(132)
where the last term is the standard Evidence Lower Bound (ELBO). This can then be trained end-to- end via the reparameterization trick. A similar approach taken in (6) who had access to paired counterfactual data.
However, we do not have access to such paired interventional data, but instead we only observe the marginal distributions (9) To this end, conditioned on we can split the term In pl)) (z: (z(+1 |c)
In ())) E) + In (() (e)) where p( denotes the density of the intervened marginal of p(), which corresponds to using the interventional decoder f ((B())-(() + ( Nevertheless, (e-gia(() In (()) (z [e)] still not tractable in unpaired settings. As a heuristic, we could consider modified ELBO by modifying this term measure some sort of divergence metric between the true interventional data ( and the generated interventional data T (z=())e), similar to [10T). We leave for future work to explore this direction.
G Additional experimental results
In this section, we provide additional experimental results and discussions to explore the effect of shift strength of the interventions, data scale, and noise distribution.
G.1
Limitations of the contrastive approach
SHD
AUROC
MCC
R2
20
1.0
1.0
1.0
0.9
10
0.5
0.5
0.8
0.0
0.0
0.5
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
n
n
n
Figure 5: Dependence of the performance metrics the shift 7). Other settings for nonlinear mixing functions (see Table 7 with ER(10,2) 2) graphs and d' = 100.
As mentioned in the main part of the paper, our contrastive algorithm struggles recover the ground truth latent variables when considering interventions without shifts. We illustrate the dependence on the shift strength in Figure 5 this section, we provide some evidence why this is the case. Apart
38

---

Cor
-2
-2
2
Figure 6: Cross entropy loss for a c 0, 20 and b 0 (left), b 2 (right) as function of the estimated latent variable 2.
from setting the stage for future works, this also enables practitioners to be aware of potential pitfalls when applying techniques.
0.4
0.4
Ground truth 1
Ground truth Z1
Recovered Z
Recovered Z
0.3
0.3
0.2
0.2
0.1
0.0
0.0
-5
-5.0
-2.5
0.0
2.5
Zi
Z1
4
3
2
N
N
0
0
-1
-1
-2
-2
-2
0
-2
Z1
Z1
Figure 7: Density of standardized ground truth latents and recovered latents for 17 = 0 (top left) and = (top right), scatter plot of the ground truth latent variables Z, and recovered latent variables 2, (bottom right). Results shown for ER(10, 2) graphs and d' 100.
for 1 0 (bottom left) and all further parameters as Table 7
We suspect that the main reason for this behavior is the non-convexity of the parametric output layer. Note that this is very different from the well known non-convexity of (overparametrized) neural networks. While neural networks parametrize non-convex functions their final layer typically convex optimization problem, e.g., least squares regression logistic regression on the features.
39

---

Moreover, it is well understood that convergence to global minimizer using gradient descent is possible under suitable conditions, see, e.g., [47]
This is different for our quadratic log-odds expression where gradient descent is not sufficient to find the global minimizer. To illustrate this consider the case of single latent, i.e., 1, then the ground truth parametric form of the log-odds in 6 can be expressed as
(0) In P (1) In Px (1) g(x)
(x)) a() +)
+
(133)
for some constants a, b, c and b = 0 if 17(1) = 0, i.e., there is no shift. We moreover assume, for the sake of argument, that the final layer implementing h(2) = a(z 6)2 + is fixed to the ground truth parametric form of the log-odds (then there is also no scaling ambiguity left). Now, let us fix a point Ty and define 2g = (xo) and
Px (ao)
eg(za)
p P(i 1|X = zo)
(134)
(1) PX
(xo) + Px (xo)
(0)
1 1 cg(wa)
Then the (sample conditional) cross entropy loss as function of & (xo( for our learned function ff is given by
(B) LCE= = ---phh 1+ ch())
( 1 + ch(z))
- -1 p1 In
pp((3) + In(1 + (8))
(135)
We here drop the intervention index, since we focus on a one dimensional illustration. We plot two examples of such loss functions for 6 = 0 and b +f 0 in Figure
To verify that this is indeed the reason for our failure to recover the ground truth latent variables, we investigate the relation between estimated latent variables and ground truth latent variables. The
result can be found Figure 7 and, as we see, when 1) = O, the distribution of the recovered latents is skewed. Moreover, we find that we essentially recover the latent variable up to a sign, i.e., 2 = |Z| (there is small offset because we enforce 2 to be centered). Note that this explains the tiny MCC scores in Table [ since Z)) 0 for symmetric distributions. This observation might also be potential starting point to improve our algorithm. For non-zero shifts we recover the latent variables almost perfectly.
G.2 Varsortability and data scale
An important observation causal discovery was that many benchmark settings exhibit specific correlation structures that can be exploited to infer causal directions. The most prominent example varsortability [66] which measures how well the causal order agrees with the order induced by the magnitude of the variance. This is measure between 0 and and for values close to 0 and I the variances contain a lot of information about the causal order while close to 0.5 this is not the case. It was shown in [66] that typical parameter choices exhibit high varsortability se which can be exploited by trivial algorithms. A related notion is R² -aaaoootrtabllity [67] which is a similar notion where the variance of the variable is replaced by the residual variance after standardizing the variables and then regressing out all other variables, i.e., the unexplained variance.
In our setting the varsortability of the latent variables Z is quite high (see [66] for the full definition), e.g., for d = 10 and & = average varsortability 0.92 0.02. Note that not obvious how this can be exploited algorithmically. Indeed, we only observe a mixture X f(Z) and the scale of is not identifiable. Nevertheless, to rule out that we implicitly use the scale of the variables ran the same experiments except that standardized the latent variables Z of the observable distribution (and apply the same scaling to the interventional distributions). The results can be found in Table and are roughly similar to the result in Table @ for the same settings without standardization. Note that R² -ortaabbbyl is not substantially different from .5 (roughly 0.4) in our settings, thus the R² -o-soraabllity cannot be exploited to infer the causal structure, even when observing Z.
G.3 Effecc of noise distribution
Our theoretical results only cover the setting of Gaussian SCMs and we even show that identifiability does not necessarily hold for uniformly distributed noise (see Appendix D.2). Nevertheless, we can
40

---

Table 4: Results for nonlinear synthetic data with 10000 and standardized latent variables Z (up to standardization the setting is the same as in Table 2 in the paper).
Setting
Method
SHD
AUROC
MCC1 1
R² 1
Contrastive Learning
2.6 + 0.4
0.92 0.02
0.96 0.01
0.93 + 0.01 0.04 = 0.01
ER(5, 2), d' 20
VAE
10.0 + 0.0
0.50 + 0.00
0.11
Contrastive Learning VAE
1.4 0.4
0.98 0.02
0.00
0.97 + 0.01
ER(5, 2), d' = 100
10.0 0.0
0.50 = 0.00
0.14
0.10 + 0.04
Contrastive Learning
9.6 + 2.1
0.90 + 0.03
+
0.84 + 0.01
ER(10, 2), d' 20
VAE
18.6 + 0.9
0.50 :: 0.00
0.27 0.04
0.29 + 0.04
Contrastive Learning
2.8 1.4
0.99 0.01
0.98 + 0.00
0.96 + 0.00
ER(10, 2), d' 100
VAE
18.6 + 0.9
0.50 + 0.00
0.14 + 0.03
0.11 + 0.04
Table Noise dependence of contrastive algorithm for ER 2), d' 20, n 10000 and nonlinear mixing (same setting first row of Table in the paper).
Noise distribution
SHD 4
AUROC
MCC1 f
R² +
Gaussian
1.8 = 0.5
0.97 0.01
0.96 0.07
0.00
Laplace
3.0 = 0.6
0.89 =
0.93
0.01
Gumbel
3.0 = 0.9
0.92 0.02
0.94
0.91 0.01
Uniform
3.4 = 0.4
0.87 +877+0003
0.00
0.93 + 0.01
Exponential
3.8 = 0.5
0.86 0.02
0.89
0.86 + 0.02
evaluate the performance of our algorithm for linear SCMs with non-Gaussian noise distribution. We rerun one of the settings in Table for different noise distributions. The results can be found in Table 5 and they show a slightly worse but still reasonable performance than for Gaussian data. This in line with the observation that using a Gaussian likelihood for non- non-Gaussian data gives good results in, e.g., causal discovery.
H Hyperparameters, architectures and further additional details on experiments
In this section, we give additional details on the experiments. We use PyTorch [60] for all our experiments.
Data generation To generate the latent DAG and sample the latent variables package (21). We always sample ER(d, k) graphs and the non-zero weights are sampled from the distribution uyy ~ [0.22.. 1.0]). To generate linear synthetic data, we sample all entries of the mixing matrix i.i.d. from a standard Gaussian distribution. For non-linear synthetic data f is given by the architecture Table 9 with weights sampled from U[[ Vinject Vinyant
the sempler
--)).
l). For image data,
similar to [2], the latents Z are the coordinates balls in an image (but we sample them differently as per our setting) and a 64 64 x RGB image is rendered using Pygame [77] which encompasses the nonlinearity. Other parameter choices such as dimensions, DAGs, variance parameters, and shifts already outlined in Section 6 but for clarity also outline them in Tables 6 and 8
For synthetic data, the model architecture for 11( 0) is a one hidden-layer MLP with 512 hidden units and LeakyReLU activation functions. For the parametric final layer, we decompose the matrix W as W D - A) where is diagonal matrix and is matrix with a masked diagonal and they both learned. This factorization shall improve stability. We initialize A 0 and D = ld. Also, the sparsity penalty and the DAGness penalty are only applied to A. For the baseline VAE we use the same architecture for both encoder and decoder. The code for the linear baseline is from [84).
Models
41

---

Table 6: Parameters used for linear synthetic data.
d
5
d'
10
k
3/2
n
(2500, 5000, 10000, 25000, 50000}
obs
U[[2, 4)
Oine
U(16, 8))
17 (8)
runs mixing
linear
Table 7: Parameters used for nonlinear syn- thetic data.
Table 8: Parameters used for image data.
{4,6]
(5, 10)
d' 64
d'
100)
k {1.2]
k
[1,2}
10000
n
25000
2(
o
(((0001,0.01))
obs
int
2((1,2)
Int
u((0.01,0.02)
s7(8)
((+00110.2)
()()
(()
runs
5
runs mixing
image rendering
mixing
3
layer mlp
Table 9: Synthetic data generation
Architecture
Layer Sequence
MLP Embedding
Input: z E Rd
FC 512, LeakyRel.U002)
FC 512, LeakyRel.
FC 512, LeakyRel.U
FC d' <- Output
For image data, the model architectures for h(r, 8) are small convolutional networks. For the contrastive approach the architecture be found in Table I0 For the VAE model, we use the encoder architecture as in Table and the decoder architecture as in Table respectively.
Table 10: Contrastive model architecture for image data.
Architecture
Layer Sequence
Conv Embedding
Input: x E T
Cony (3, 10, kernel size stride 3), ReLUO)
MaxPool (kernel size = 2, stride = 2)
FC 64, LeakyReL.UO FC d t Output 8
Training For training we use the hyperparameters outlined in Table We use a 80-20 split for train and validation/test set respectively. After subsampling each dataset to the same size, we copy the observation samples for each interventional dataset in order to have an equal number observational and interventional samples they be naturally paired during the contrastive learning. We select the model with the smallest validation loss on the validation set, where we only use the cross entropy loss for validation. For the VAE baseline use the standard VAE validation loss for model selection.
42

---

Table 11: VAE Encoder architecture for image data
Architecture
Layer Sequence
Conv Encoder
Input: x E [64X6413
Conv(3, 16, kernel size = 4, stride = 2. padding = 1), LeakyReL.UO)
Conv(16, 32, kernel size stride 2. padding 1), LeakyReI.UO
C3nv(32, 32, kernel size = 4, stride 2. padding 1), LeakyReI.UO
Conv(32, 64, kernel size stride 2. padding 1), LeakyRel.UO
FC 2d <
Output (mean, logvar)
Table 12: VAE Decoder architecture for image data
Architecture
Layer Sequence
Deconv Decoder
Input: Rd
FC (3 3) x d
DeConv (d, 32, kernel size 4, stride 2. padding 0): LeakyReL.UO
DeConv (32, 16, kernel size = 4, stride = 2, padding 1), LeakyRel.UO
DeConv (16, 8, kemnel size 4, stride 2. padding 1); LeakyReI.UO
DeConv (8, 3, kernel size = 4, stride = 2, padding = 1), LeakyRel.UO)
Sigmoid() Output
Table 13: Hyperparameters used for training.
T1 (see Eq.
10 10-5
T2 (see Eq. (9)
10-4
learning rate
10-4
batch size
512
epochs
200 (synthetic data), 100 (image data)
optimizer learning rate scheduler
Adam (38]
CosineAnnealing
S1
Compute and runtime The experiments using synthetic data were run on CPUs with 16Gb RAM on compute cluster. For image data added GPU increase the speed. The runtime per epoch for the synthetic data and 10000 samples was roughly 10s. The total run-time of the reported experiments about 100h (i.e. 200 CPU hours) and 20h GPU, but hyperparameter selection and preliminary experiments required about 10 times more CPU compute.
Mean Correlation Coefficient (MCC) Mean Correlation Coefficient (MCC) is metric that has been utilized in prior works 37 to quantify identifiability. MCC measures linear correlations up to permutation of the components. To compute the best permutation, linear sum assignment problem is solved and finally, the correlation coefficients are computed and averaged over. A high MCC indicates that the true latents have been recovered. In this work, we compute the transformation using half of the samples and then report the MCC using the other half, i.e. the out-of-distribution samples.
Further experimental attempts and dead Ends settings we tried our experiments.
We will briefly summarize a few additional
We fixed D = Id in the parametrization of W. This fixes the scaling of the latent variables in some non-trivial way. This resulted in very similar results.
We tried combine the contrastive algorithm with a VAE approach. Since the ground truth latent variables Z are highly correlated, they are not suitable for an autoencoder that typically assumes factorizing prior. Therefore, we map the estimated latent variables for the observational distribution to the noise distribution which factorizes. Note that for the ground truth latent variables the relation ()) ( holds we consider W2. We
43

---

use é as the latent space of an autoencoder on which we then stack a decoder. We train using the observational samples and the ELBO for the VAE part and with the contrastive loss (and interventional and observational samples) for the 2 embedding. This resulted in slightly worse recovery of the latent variables (as measured by the MCC score) but much worse recovery of the graph. We suspect that this originates from the fact that the matrix is used both in the paramctrization of the log-odds and to map 2 to e which might make the learning more ertor-prone. Note that this different from the suggestion in Section F44
Choosing larger learning rate for the parametric part than for the non-parametric part seemed to help initially, but using the same sufficiently small learning rate for the entire model was more robust.
We tried larger architectures for both synthetic and image data. They turned out to be more difficult to train without offering any benefit.
For image data often observed overfitting when using smaller sample sizes. The overfit- ting persisted even when we used a pre-trained ResNet [24] with frozen layers. We suspect that for image data the performance (in particular the sample complexity) be further improved by carefully tuning regularization and model size.
44


Reviews:
[{"review_id": "69fSIuYOK2", "reviewer": "Reviewer_LWnm", "summary": "In recent years, the theory of non-linear independent component analysis and causal representation learning has witnessed a lot of interesting developments. In this work, the authors study the problem of causal representation learning in the presence of interventional datasets, where interventions occur on the latents. The authors show that when the latents follow a linear structural causal model with a Gaussian distribution, then under general non-linear mixing (diffeomorphisms) the latents can be recovered up to permutation and scaling. For imperfect interventions, the authors show that it is still possible to recover the partial order under topological ordering of the underlying causal graph G can be recovered.  The authors present a new method based on contrastive learning that learns to distinguish interventional data from observational data and test it out on some synthetic datasets.  \n\n", "questions": "Please see the weakness section above. My final score depends on clarifcation to the questions I raised above.", "limitations": "The authors would benefit by having a discussion on the limitations. For instance, they should talk about why is Gaussian assumption limiting as an example.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The authors have studied an important problem in the area of intereventional causal representation learning. The results proposed in the work for the case of perfect interventions show that strong identification is achievable with perfect interventional data. The authors also make progress on the difficult problem of tackling imperfect interventions. The theory of the paper is overall quite insightful. ", "weaknesses": "I have a question and a claim about weakness. Let us consider the following setting. \n\nData generation for obervational data is given as:\n\n$\\epsilon \\sim \\mathcal{N}(0, \\sigma^2 Id)$, \n$z = A \\epsilon$, \n$x  = f(z)$\n\nwhere $A$ is invertible, $\\mathcal{N}$ is normal distribution, $\\epsilon$ is noise (each component is independent), $f(\\cdot)$ is injective. \n\nData generation in interventional environment $k$ where $p^{th}$ component is intervened is given as \n\n$\\epsilon^{(k)} \\sim \\mathcal{N}(\\mu_p e_p, \\sigma^2 Id + \\sigma_p^2 e_p e_p^{\\top})$, $z^{(k)}= A \\epsilon^{(k)}$, $x = f(z^{(k)})$\n\nwhere $e_p$ is a vector with zeros everywhere except at $p^{th}$ entry, $Id$ is identity, $\\mu_p$ is mean under intervened distribution\n\nWe index the observational data as $0$ and interventional data from $1$ to $p$.\n\nIf we condition on the index of the data, the different components of $\\epsilon$ are conditionally independent and follow an exponential distribution.  We can now leverage the theory in i-VAE applied to identifying $\\epsilon$ and mixing function $f \\circ A$.  In this case, if we have $p\\geq 2d$ and sufficient variability condition from Theorem 1 in http://proceedings.mlr.press/v108/khemakhem20a/khemakhem20a.pdf is satisfied, then we achieve permutation and scaling identification.  \n\n\nTherefore, we can assume to have identified $\\epsilon$ up to permutation and scaling. We call this estimate $\\hat{\\epsilon} = P \\Lambda z$, where $P$ is permutation, $\\Lambda$ is diagonal. Note that $\\hat{\\epsilon} =\\Lambda^{-1}P^{-1} A^{-1}z$. We now have a linear relationship between observed $\\hat{\\epsilon} $ and underlying true $z$. \n\nWe can now leverage imperfect intervention results under linear mixing from https://arxiv.org/pdf/2301.08230.pdf (Theorem 13, see Table 1) to achieve mixing consistency based identification of $z$. \n\nWe can even reduce the number of interventional distributions needed from $2d$ to $d$ provided we assume variance in Normal distribution is known by leveraging results from https://proceedings.mlr.press/v177/lachapelle22a/lachapelle22a.pdf. \n\nThe characterization I describe above suggests that it is possible to get identification results by combining i-VAE and  https://arxiv.org/pdf/2301.08230.pdf in a straightforward way. Either I am missing something? I would like the authors to clarify if they considered this simple combination? Further, if the authors agree with above characterization, how do the authors modify their contributions in this light?\n\n\nI don't quite agree with line 253, distributional assumptions. I think Gaussians is still a strong assumption and authors would benefit by being upfront about it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review and their insightful suggestion of a simpler proof strategy.\nHowever, the model considered in their argument is the very special case when the causal graph's weights do not change at all under all considered interventions. In particular, their review assumes $z^{(k)} = A\\epsilon^{(k)}$, but our setting is substantially more general and considers the case where $A$ changes (which covers more realistic interventions). We present additional details below.\nRegarding the distributional assumption, we agree it's needed in our work and it has been emphasized in the abstract and introduction. Additionally, we will carefully revise to make it more evident throughout the writeup.\n\n\n==================\n\n**Additional details:**\n\nWe follow your notation in this response, however, note that the matrix $A$ in this response corresponds to $B^{-1}$ in the paper.\nThe review considers interventions of the form $z^{(k)}=A\\varepsilon^{(k)}$ where $\\varepsilon^{(k)}$\nis obtained by shifting and rescaling the noise variable of node $k$. \nAs outlined in the review, this setting is covered by the iVAE theory and earlier identifiability results apply.\nOur work considers, in addition, interventions that change the relation to the parents, in particular perfect interventions that remove the effect from the parents.\nFor such interventions, the matrix $A\\to A^{(k)}$ also depends on the intervention. \nThis is also the interventional setting considered for linear mixing functions in the recent work [1].\nNote that the settings considered by the reviewer and our work both agree in the special ICA case when there are no causal relations but don't agree in cases beyond ICA, which we handle in our work.\n\nTherefore, to achieve our tight identifiability results, we need to exploit the specific form of the interventions. Note that our proofs are not purely linear algebraic but also topological, i.e., we explicitly exploit continuity of the mixing (see Lemma 4) making it unlikely that our results directly follow from known theorems.\nNevertheless, we agree that it is a valuable addition to our paper to clarify that the ICA case is substantially simpler and has been solved in earlier work.\n\nWe hope that this changes your view on our theoretical contribution and other points that may have contributed towards a lower score, and we are happy to discuss this issue and all other questions further.\n\n[1] C. Squires, A. Seigal, S. Bhate, and C. Uhler. Linear causal disentanglement via interventions, ICML 2023."}, {"review_id": "vCUMhYSBY8", "reviewer": "Reviewer_2jDD", "summary": "The paper considers the task of causal representation learning (causal disentanglement) from interventions, with (1) a linear latent structural causal model, (2) a nonlinear mixing function, and (3) single-node interventions. They show that, under perfect interventions, the generative model is identifiable up to trivial indeterminacies. They propose a method based on contrastive learning for recovering the generative model, and show that their method works well in practice (outperforming a baseline which only allow for linear mixing). ", "questions": "### Questions\n1. In Equation (3), why are we able to identify shifts without scaling indeterminacy? This seems odd: if we scale a variable, I would expect that the shift also scales.\n2. In Equation (7), should $h$ in the last term have a subscript? Then it is not a matrix so I don't see how it should be in the inner product.\n\n### Suggestions\n1. In line 26, the cited papers are about independent component analysis, and these are given as examples of identifiability in causal representation learning (CRL). I agree that ICA can be cast as a special case of CRL. However, I have the feeling that for the purposes of clarity, it might be best to use a different umbrella term like \"identifiable representation learning\"; there is nothing really \"causal\" about ICA.\n2. Adapt the synthetic data generation process to reduce varsortability and $R^2$-sortability [1,2]. One procedure which takes these issues into account is given by [3]. \n\n[1] Reisach, A., Seiler, C., & Weichwald, S. (2021). Beware of the simulated DAG! Causal discovery benchmarks may be easy to game.\n\n[2] Reisach, A. G., Tami, M., Seiler, C., Chambaz, A., & Weichwald, S. (2023). Simple sorting criteria help find the causal order in additive noise models.\n\n[3] Squires, C., Yun, A., Nichani, E., Agrawal, R., & Uhler, C. (2022). Causal structure discovery between clusters of nodes induced by latent factors.", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "### Significance\nThis paper presents a significant theoretical contribution to an established line of work, while introducing techniques and connections that will be useful for future works. In particular, the advance from linear (or polynomial) mixing to general non-linear mixing is a big step towards realistic generative modeling. On the practical side, they also develop a solid contribution by showing that contrastive learning can be used to disentangle the latent variables. \n\n### Clarity\nThe paper is very clear in describing its contribution and how it compares to previous work. The presentation is quite thorough: they clearly describe their setup and discuss their assumptions, they show that their sufficient conditions for identifiability are actually necessary conditions, they discuss the unsuitability of polynomial mixing, and they provide a detailed description of their experimental methodology with accompanying code.\n", "weaknesses": "There are no major weaknesses. There are some relatively minor points of confusion / potential typos and some small suggestions to improve the paper in the **Questions** section.\n\nIf I had to pick a weakness, it would be that the proposed algorithm suffers from problems with local optima. It would be ideal to have an algorithm which provably recovers the latent representation, and some sample complexity results. These results would make the paper feel very \"complete\", and with these results the paper would probably be a better fit for a journal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and positive feedback.\nWe are glad the reviewer also expects our ideas to contribute towards generative modeling in the real world, as that is one of the stronger motivations behind our work.\n\n**Regarding the questions:**\n\n1. We can identify $\\eta$ exactly because the scaling is absorbed in $B$. Or, in other words, $\\eta$ is the amount of shift in the normalized Gaussian (this is evident in equation (2)) and therefore can be identified without scaling indeterminacy.\n\n2. There should be no subscript, thanks for pointing out our typo.\n\n**Regarding the suggestions:**\n\nWe appreciate the insightful suggestion regarding varsortability and will be happy to discuss this in the paper, as well as cite the works you linked. \nWe ran an additional experiment where we standardized $Z$ before applying the non-linearity thereby removing the varsortability (we also checked that in our setting $R^2$-sortability does not deviate substantially from $1/2$). The results are in Table 2 in the attached PDF and show a slightly degraded performance.\nIn general, note that it is not directly clear how varsortability of $Z$ can be exploited because $Z$ is only identifiable up to scaling, as we show.\n\nWe agree with the reviewer that resolving the issues of local optima and sample complexity are of great interest. Although little progress has been made on them so far in this field \n(e.g.,  there are no sample complexity results for causal representation learning that we are aware of), \nthese are important directions for further research. \nWe plan to expand our discussion section to include those directions, and also incorporate your suggestions along with the suggestions by other reviewers."}, {"review_id": "9xagBXSQW5", "reviewer": "Reviewer_uV6M", "summary": "This paper aims to identify latent variables via a nonlinear mixing function interventional data. The authors prove strong identifiability results for unknown single-node interventions, extending previous work that focused on linear maps, polynomial mixing functions or paired counterfactual data. The paper proposes an interesting contrastive algorithm to identify the latent variables and evaluates its performance on some synthetic tasks and a simple image dataset modified from Ahuja et al [2023]. While there have been other very recent works that examine the interventional setting, this is the first I'm aware of that only requires $d$ interventions to recover $d$ latents with minimal constrains on the mixing function.", "questions": "* Have you experimented with non-gaussian latents? What happens?\n* How well does the method work on larger problems (e.g. 5 - 10 balls? Or more?)", "limitations": "As mentioned above, the paper could be a little more upfront about the implication of the assumptions it makes, but overall it does a good job of addressing limitations. I also liked the \"deadends\" section at the end of the appendix.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* This is the strongest theoretical result that I am aware of in causal representation learning. The gaussian assumption is obviously restrictive, but other than that, the paper proves identifiability for a very practical class of problems: they only need $d$ interventions to identify $d$ latents, and make no further restrictive assumptions on the mixing function beyond standard infectivity / diffeomorphism assumptions. \n* The paper is very clearly written both in the main text and the appendix. \n* The contrastive algorithm that they propose to implement their approach is interesting. It has some optimization issues which the paper is upfront about, but I'm still curious to see how it would work on larger problems.", "weaknesses": "I don't have many complaints, but I do have some nitpicks.\n* In the introduction (particularly the first paragraph), the paper makes it sound like the generative process for the data is via a neural network (transformers & diffusion models in line 16, and a similar comment is made in line 124 in support of Assumption 1). While we can build generative models of complex data with neural networks, that is not the $f(\\cdot)$ that we care about in causal representation learning. The real generative function, $f(\\cdot)$, is a property of the world---it's the camera or microscope that photographs a scene---and we don't have control over that. I realize this makes the diffeomorphism assumptions unrealistic, but I think it's better to just be upfront about that as a limitation. \n* I have a similar complaint about the defence of the Gaussian assumption in lines 138 - 141: real processes almost certainly are not Gaussian, so we should treat it as a model of the world and be upfront about that (in the Box, \"all models are wrong\" sense). The paper would be strong if you were upfront about the fact that it is clearly restrictive but useful (because it gives strong identifiability results), and then evaluated sensitivity of the method to non-gaussian latents in the experiments. \n\nMore minor:\n* Line 32 - I believe causal representation learning, but it remains to be seen whether it is either necessary or sufficient to build trustworthy systems, so that's a strong claim to make.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and are glad the reviewer likes both our tight identifiability results and the contrastive learning algorithm. We agree with the reviewer's suggestions to improve the exposition and are happy to be revise the wording accordingly, including being more upfront about the limitations.\nIn particular we will clarify that $f$ is a property of the world that we try to learn and Gaussian variables are often a useful approximation.\n\nWe also like the reviewer's suggestions for additional experiments.\n\n1. In Table 1 of the attached PDF, we show the results for experiments with non-Gaussian distributions (the setting agrees with the first row \nof Table 2 in the paper), in particular Laplace, Gumbel, Uniform and Exponential distributions.\nWe observe that the recovery with our contrastive learning algorithm gets slightly worse but is still very reasonable. This is in line with the performance of, e.g., causal discovery algorithms based on a Gaussian likelihood score for non-Gaussian data.\n\n2. As suggested, we also scaled up our experiments on the image dataset to 10 balls, please see Table 3. We found that for (much) larger sample size and larger models the performance can be increased significantly (compared to the results we reported), and we can handle  up to 10 balls. While there is certainly still room for improvement (e.g. via hyperparameter turning), the more challenging next step is to handle noisy observations and more complex sceneries.\n\nWe will add these tables to the paper in the final version. We welcome additional feedback to improve the work."}, {"review_id": "YAdBaXFq43", "reviewer": "Reviewer_RqDB", "summary": "The authors study the problem of learning latent causal models from interventional data. The problem was formulated under linear or polynomial mixing in previous works and this work considers a more general setting of nonlinear mixing. The main contributions are the identifiability results of the latent causal model and a contrastive algorithm that identifies the latent model.", "questions": "Whether $d$ is identifiable in the nonlinear setting? And how to identify $d$ for the contrastive method?\n\nI would like to raise my score if this problem can be addressed properly. \n\n", "limitations": "No potential negative societal impact.\n\n", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The extension to nonlinear mixing is an important and challenging problem.\n\n2. Using the contrastive algorithm to identify the model parameters is novel and sound.", "weaknesses": "1. Single-node interventions are considered, while more nodes can be intervened in each environment in practice. For theoretical results, I think focusing on single-node intervention is fine, but it should be discussed whether the results have the potential to be generalized. \n\n2. It was not mentioned whether the latent dimension $d$ is identifiable in the nonlinear setting. For all the identifiability results in the paper, the considered $\\widetilde{Z}^{(i)}$ is assumed to have the same dimension as the true latent variable $Z^{(i)}$ (i.e., $d$). Note that $d$ is identifiable and it equals to the rank of the precision matrix of X in the linear setting. (Section 3.1 [1]). \n\nThis issue occurs in the experiments as well.  $d$ is provided to the contrastive method. But it is often not possible to know $d$ in practical settings.\n\n[1] C. Squires, A. Seigal, S. Bhate, and C. Uhler. Linear causal disentanglement via interventions, 2023.\n\nAdditional comment: I think it would be helpful to provide a concrete toy example to demonstrate the identifiability since the proof intuition is a bit vague. \n\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review and their suggestions. We will address their concerns in order.\n\n**Regarding the identifiability of $d$:**\n\nYes, the dimension $d$ is identifiable from the observational distribution in our setting for the following reason. The image $f(\\mathbb{R}^d)=M\\subset \\mathbb{R}^{d'}$ is a submanifold of dimension $d$, i.e., it locally looks like a $d$ dimensional hyperplane, so its dimension can be identified from the dimension of the tangent space.  Put differently, the datapoints in a small neighborhood of a point $x$ generate essentially a $d$ dimensional linear space.\n\nIn the setting considered in [2] that the reviewer highlighted, the latent dimension can be directly estimated from the rank since the mixing $f$ was assumed to be linear (which is a specialized setting). In general, when $f$ is non-linear as in most representation learning tasks, this task of estimating the latent dimension for complex data is much harder but also highly important and has been subject to intense study.\n\nFor instance, in [1] the authors define a maximum likelihood estimator for the dimension of the data manifold around a data-point $x$ (it exploits that the volume of the $d$-dimensional ball scales like $r^d$ with the radius $r$).\nWe show in the table below our estimates when applying this estimator (for the $k=50$ nearest neighbors) to our MLP setting with observed dimension $d'=100$\nand $n=10000$ samples where we average the estimator over 10 different data-points $x$. We report the mean over 10 different runs and the  reported error is the standard deviation.\n\n| Ground truth $d$    | Estimated $\\hat{d}$ |\n| -------- | ------- |\n| $5$  | $5.3\\pm 0.3$    |\n| $10$ | $9.8 \\pm 0.6$     |\n| $20$    | $16.2 \\pm 0.6$    |\n\nSo for the settings we consider we can estimate the dimension experimentally, but, as one would expect, the problem becomes more difficult for high dimensions.\nTo use our contrastive algorithm with unknown dimension, one could first use a standard estimator to estimate the dimension $d$ of the data manifold (as in [1]) and then apply the contrastive algorithm. \nWe thank the reviewer for bringing up this point, and we will clarify in the paper, that $d$ is also identifiable.\n\n\n**Regarding multi-node interventions:** \n\nThis is an interesting direction that is beyond the scope of our present work but we expect that new block identifiability results can be derived for multi-node interventions. We will be happy to add a discussion of this along with further future directions. \n\n\nWe hope our response clarifies the reviewer's points of concern, especially the ones that led them to reduce their score. We're happy to address any further concerns and also welcome additional feedback on improving the paper.\n\n[1] Elizaveta Levina and Peter Bickel. Maximum Likelihood Estimation of Intrinsic Dimension,  NeurIPS 2004.\n\n[2] C. Squires, A. Seigal, S. Bhate, and C. Uhler. Linear causal disentanglement via interventions, ICML 2023."}]

Author rebuttal:
We thank all reviewers for their reviews pointing out that the paper 'presents a significant theoretical contribution' (R. 2jDD) that studies 'an important problem in interventional causal representation learning' (R. LWnm), proposes a 'novel and sound algorithm' (R. RqDB), and is 'very clearly written' (R. uV6m). Reviewers 2jDD and uV6m were quite positive about the paper, Reviewers RqDB and LWnm generally acknowledged the contributions of the paper but had questions regarding an alternative proof strategy and identifiability of the latent dimension.
Those are addressed in the individual responses.

Following the optional (and intriguing) suggestions of Reviewers uV6M and 2jDD, we ran additional experiments where we investigated
the effects of different noise distributions (to probe misspecification) and data standardization (to probe varsortability) on the algorithm's performance.
In addition, we considered more challenging settings for the balls dataset (scaling up from 3 balls to 10 balls). 
The results can be found in the attached PDF, for additional details we refer to our responses to Reviewers
uV6M and 2jDD.

Meta-review: This paper represents a significant contribution to the rapidly blossoming theory for identification of latent causal models. In particular, this result handles the setting of Gaussian latents and arbitrary mixing functions, while most prior works required specific parametric forms (e.g. linear or polynomial). As such, I (and, it seems, the reviewers) believe it has the potential for significant impact in the space.
Decision: Accept (oral)