Jacobian-based Causal Discovery with Nonlinear ICA
Authors: Patrik Reizinger
Yash Sharma
Matthias Bethge
Bernhard Schölkopf
Ferenc Huszár
Wieland Brendel
Venue: Accepted by TMLR ()

Abstract: Today's methods for uncovering causal relationships from observational data either constrain functional assignments (linearity/additive noise assumptions) or the data generating process (e.g., non-i.i.d. assumptions). Unlike previous works, which use conditional independence tests, we rely on the inference function's Jacobian to determine nonlinear cause-effect relationships. We prove that, under strong identifiability, the inference function's Jacobian captures the sparsity structure of the causal graph; thus, generalizing the classic LiNGAM method to the nonlinear case. We use nonlinear Independent Component Analysis (ICA) to infer the underlying sources from the observed variables and show how nonlinear ICA is compatible with causal discovery via non-i.i.d data.  Our approach avoids the cost of exponentially many independence tests and makes our method end-to-end differentiable. We demonstrate that the proposed method can infer the causal graph on multiple synthetic data sets, and in most scenarios outperforms previous work.


Published in Transactions on Machine Learning Research (03/2023)
Jacobian-based Causal Discovery with Nonlinear ICA
Patrik Reizinger"
University of Tübingen, Germany
International Mox Planck Research School for Intelligent Systems (IMPRS-IS) European Laboralory for Learning and Intelliend. Systems (ELLIS)
Yash Sharma
yusd.shharmmddeen--tuubbinnn.ee
University of Tübingen, Germany
International Mor Planck Research School for Intelligent Systems (IMPRS-1S)
Matthias Bethge
mafthios mafthios. buennnnneennnnnneeeeeeeeenn...n
University of Tübingen, Germany
Bernhard Schölkopf
bs@Stubhingn.mpp de
Maz. Planck Institute for Intelligent Systems, Tübingen, Germany
Ferenc Huszár
fh2770com.ace uk
University of Combridge, United Kingdom
Wieland Brendel!
wieland wielandd.brndde@@uueenngg..gg
Maa Planck Institute for Intelligend Systems, Tübingen, Germany
Reviewed on OpenReview: https: openreview. net/ forun? id= 2Yo9ngR6Ab
Abstract
Today's methods for uncovering causal relationships from observational data either constrain functional assignments finearity/additive /additive noise assumptions) the data generating process (e.g,, non ii.d. assumptions). Unlike previous works, which use conditional independence tests, we rely on the inference function's Jacobian to determine nonlinear cause-effect relationships. We prove that, under strong identifiability, the inference function's 's Jacobian captures the sparsity structure of the causal graph; thus, generalizing the classic LINGAM method to the nonlinear case. We use nonlinear Independent Component Analysis (ICA) to infer the underlying sources from the observed variables and show how nonlinear ICA is compatible with causal discovery via non-i..d. data. Our approach avoids the cost of exponentially many independence tests and makes our method end-to-end differentiable. We demonstrate that the proposed method can infer the causal graph on multiple synthetic data. sets, and in most scenarios outperforms previous work.
1 Introduction
Traditional statistical learning methods model corrclations in data. Though they have achieved super-human performance in multiple fields, they have limited value in understanding cause-effect relationships. A prevalent consequence of this shorteoming is the models' tendency to learn from spurious features or shortcuts (Geirhos et al., 2020) (c.g., classifying objects based on their backgrounds). In contrast, causal models construct the world according to the Independent Causal Mechanisms (ICM) principle (Peters et al., 2017), where building blocks (mechanisms) neither influence nor inform each other. Modeling temperature T and altitude A is a clas- sic example (Peters al., 2017): changing A affects T,, but not vice versa this relationship is described by the Directed Acyclic Graph (DAG) A + T. The ICM principle means that the same mechanism p(T)A) describes how altitude alfects lemperature for diflerent p(A), but the same cannot be said about p(A[T) and p(T). Causal Discovery (CD) describes the process of extracting causal structure from data in the form of DAG. Having interventional data such as in the form of Randomized Controlled Trials (RCTs) is desirable as it enables answering questions of interventional nature, such as 'What will happen if variable X is changed?"
" Corresponding author. Code available at: github, hwtp:///aa....e//oaaaaaaaaaaeeee
i Joint supervision

---

Published in Transactions on Machine Learning Research (03/2023)
N1 +
X1
N1
Inference Model s
2₂
X
N₂
No.
N3
X
1 = f1(N1)
X₂ (,(NI,N))
g-1
X3 I,
Figure The Jacobian of the inference network J informs about the DAG. We show that if observations X are generated from noise variables N via general nonlinear Structural Equation Model (SEM) f, then the corresponding DAG can be inferred from the Jacobian of model that identifies N under certain assumptions on N
However, RCTs can be costly, infeasible (Eberhardt et al., 2005), or even unethical. Thus, developing effective CD methods reliant on observational data alone is of significant interest. In general, inferring the causal direction is provably impossible without additional constraints or assumptions (Zhang et al., 2015); therefore, existing methods constrain either the model class (i.e., the functions generating the observations) or the data distribution. On the model side, these constraints include lincar (Shimizu et al., 2006; Tashiro al., 2014; Shahbazinia et al., 2021; Zheng et al., 2018) specific nonlinear relationshipe (e.g., with additive noise) (Hoyer et al., 2008; Peters et al., 2011; Schölkopf et al., 2021a; Yu et al., 2019; Shen et al., 2022; Lachapelle et al., 2020; Ng et al., 2022). On the data side, assumptions include non-stationarity (Hyvärinen & Morioka, 2016; Monti et al., 2019) or exchangeability (Guo et al., 2022).
CD aims infer the ground-truth cause-effect. relationships, which connects to the identifiabillly literature, where the goal to learn a model equivalent to the ground truth (up indeterminacies, such as permutations element-wise nonlincarities).
An extensively studied method for learning identifiable representations is Independent Component Analysis (ICA) (Comon, 1994; Hyvärinen et al., 2001), which requires that the inferred components (sowrces) are independent. Recent work has relied on nonlinear Independent Component Analysis (NLICA) for identifia- bility (Zimmermann et al., 2021; Klindt et al., 2021; Hyvärinen & Morioka, 2016; Willetts & Paige, 2021; Khemakhem et al., 2020a; Hyvärinen et al., 2019; Morioka et al., 2021; Monti et al., 2019; Khemakhem et al., 2020b; Gresele et al., 2019; Hyvärinen & Morioka, 2017; Hyvärinen et al., 2010; Hälvä & Hyvärinen, 2020;
Lachapelle et al., 2022).
Instead of using pairwise independence tests, draw inspiration from the Linear Non- Non-Gaussian Acyclic Model (LINGAM) (Shimizu et al., 2006), which uses weight matrix to infer the DAG of a lincar causal model. We extend this approach to the nonlinear case by showing that the Jacobian of the ground-truth inverse Data Generating Process (DGP) (mapping from observations X to noise variables N) captures the sparsity structure the DAG (Prop. 1). Since the ground truth model is generally unknown, we transfer our insight to the Jacobian of the learned inference model! (i.c., the empirical estimate of the ground-trun X N map; ef. Prop. 2). There, we quantify the requirements on the inference model with the notion of strong identifiability is fulfilled (Khemakhem et al., 2020b, Def. 2) (cf. Defn. B.1) and show that causal models provide inductive bias to resolve the permutation indeterminacy (Lem. 1). We guarantee identifiabiiitty via NLICA; thus, our work is akin to the NonSENS method (Monti et al., 2019), which showed that NLICA can be used for bivariate CD with general nonlinear functions and non-i.i.d. abservational data. However, our proposal works in the multivariable case. Relying on the Jacobian removes the cost d2 independence tests for DAG with d nodes. However, with current NLICA methods, we could only scale up to ten nodes. Our contributions can be summarized follows:
In our paper, inference refers only this process and amortized inference for direct graph discovery as proposed in Lorch et al. (2022)
2

---

Published in Transactions on Machine Learning Research (03/2023)
1. We prove that the inverse DGP's Jacobian encodes the DAG structure (Prop. 1);
2. We show that causal models allow us to resolve the permutation indeterminacy of ICA (Tem. 1);
3. Our main result (Prop. 2) proves that we can infer the DAG from the Jacobian of the inference function, while removing the need for independence tests;
We propose an end-to-end multivariable CD method for nonlinear functions from observational but. non-L..d. data and show how contrastive NLICA is compatible with CD;
5. We experimentally show that our proposed method can infer the DAG across multiple synthetic data sets.
2 Background
Here, we describe causal models and connect their estimation to ICA and defer the details to Appx. A.
Structural Equation Models (SEMs). Given d-dimensional observed X ( Xa) and noise (independent) variables I NN), their causal relationship is given by d deterministic functional assignments (Pearl, 2009), constituting the generative model:
I== N.)
4i,
where Pa; C X are the parents of X; and fi are the components of the vector-valued function f. We describe the computation of X for given N with an iterative process (denoting the iteration step with superscript), which is a useful concept for justifying our proposal ($ 3). Initially, N is drawn from its density. To calculate X for N, the functional assignment f needs to be applied d times. Namely, according to (1), each X, requires that its parents Pa, are calculated. After sampling N, only the (empty) parent sets of root nodes are calculated. Thus, the first application of f yields the X; values for such nodes. In the second iteration, the children of root nodes can be calculated (since we have all parents from the first itcration), and so on. This yields an iterative algorithmic formulation of the SEM, describing the computational graph given by the DAG as:
X x (X. ff(( (x(d-1,, = (X(),)))((
(2)
where X is the initial value (w.l.o.g., we assume X 0, since calculating the functional assignments will overwrite every X;). We will also denote X (NV to indicate that X is delerministically determined by a particular N. As in most previous works (Vowels et al., 2022, Table 1), we assume no confounders (all variables are observed) and faithfulness (loosely speaking, the coefficients/funneeee /functions will not cancel an edge, cf. Assum. 1).
Causal Discovery (CD). In CD, the data is assumed to be generated by a causal process, and the aim is to infer the corresponding DAG, which enables reasoning about interventions (without the DAG, the joint distribution p(N) only admits obscrvational queries) (Peters et al., 2017; Pearl, 2009). Algorithmic approaches include combinatoric search (Shimizu et al., 2006; Hoyer et al., 2008; Hyttinen et al., 2013; Mitrovic et al., 2018; Raskutti & Uhler, 2018; Spirtes et al., 2000; Vowels et al., 2022), continuous optimization (Zheng et al., 2018; Lee et al., 2019; Wei et al., 2020; Ng al., 2020; Vowels al., 2022), and neural networks (Yu et al., 2019; Ng et al., 2022: Khemakhem et al., 2021; Yang et al., 2021: Goudet et al.,
2018; Kalainathan et al., 2018; Vowels et al., 2022; Kyono et al., 2020; Moralfah et al., 2020)- we focus on the latter. Zhang et al. (2015) proved that identifying the causal direction in a general SEM is impossible without constraints on the function class and/or data distribution.
Functional constraints can inchude linear (Shimizu et al., 2006; Zheng et al., 2018; Squires et al., 2023), additive nonlinear (X, = (Pa:) + N.) (Hoyer et al., 2008; Ng et al., 2022; Lachapelle et al., 2020; Schälkopf et al., 2021a; Yang al., 2021), affine nonlinear (X; = (Pa.) + (N())) (Khemakhem et al., 2021; Shen et al., 2022), or polynomial (Ahuja et al., 2022b) models. Regarding the data distribution, some models require access to interventions (Brouillard et al., 2020; Ke et al., 2020; Lippe et al., 2021; Ahuja et al., 2022b); others assume that N is Gaussian (Kalainathan et al., 2018; Lachapelle et al., 2020) or non- Gaussian (Shimizu et al., 2006); or require non-stationarity (Monti et al., 2019), exchangeability (Guo el al., 2022), or discreteness (Ke et al., 2020) of N. Variational-inferenea -nfeeence--based formulations require a prior over the DAGs (Lorch et al., 2021: 2022; Charpentier et al., 2022) or utilize labels (Yang et al., 2021). Our work was inspired by (Monti et al., 2019), which provides a bivariate CD method for general nonlinear functions and non-stationary data. The authors leverage recent results in NLICA (cf. next section for details) to identify the causal direction.
3

---

Published in Transactions on Machine Learning Research (03/2023)
Although they demonstrate applicability to multivariable problems, the use of pairwise independence tests constrains scalability. In our work, we extend these results with an end-to-end solution in $ 3.
Identifiability and ICA. Independent Component Analysis (ICA) (Comon, 1994; Hyvärinen et al., 2001) models the observed variables X as a mixture of independent variables N via a deterministic function f, and focuses on defining models that are identifiable -ie N can be recovered up to indeterminacies (e.g,, scaling, permutation, sign flips, element-wee wise transformations). Since this is provably impossible in the nonlincar case without further assumptions (Darmois, 1951: Hyvärinen & Pajunen, 1999; Locatello et al., 2019), recent work has focused on incorporating auziliary variables (Hyvärinen et al., 2019; Gresele et al., 2019; Khemakhem et al., 2020a; Gassiat et al., 2022), exploiting temporal structure in the data (Hyvärinen & Morioka, 2017; 2016; Hälvä & Hyvärinen, 2020; Morioka et al., 2021; Monti et al., 2019; Hyvärinen et al., 2010; Klindt et al., 2021; Zimmermann et al., 2021), or restricting the model class (Shimizu et al., 2006; Hoyer et al., 2008; Zhang& & Hyvärinen, 2009; Gresele et al., 2021). Several works have related (nonlincar) ICA to SEM estimation (Gresele et al., 2021; Monti et al., 2019; Shimizu et al., 2006; Von Kügelgen et al., 2021; Hyvärinen et al., 2023) by inverting the DGP-ic., estimating f with an inference model f
3 Inferring causal structure from Jacobians
3.1 Intuition
The method we propose can be intuitively understood as a nonlinear extension of LINGAM (Shimizu et al., 2006; Hoyer et al., 2008; Peters et al., 2011). LiNGAM assumes a linear causal relationship between observations X and the noise variables N, i.e. X WN. Since the noise variables are assumed to be statistically independent, lincar ICA can uncover the (non-Gaussian) sources N from the observations X, which allows us to extract the DAG from W-1 as we show in the following example.
Example (Motivating example for linear SEMs). Assume linear causal model with three variables, the DAG X1-X2-X2 and functional relationships: X == N1; x2 == ax, N2; X3 == bX2+ : a, ER The DGP generates samples according to the DAG and has the matrie form on the left-we we focus on the elements below the main diagonal as for recovering the DAG, only the paths (i.e., series of directed edges) between X and X2 are required and the main diogonal expresses the N, + Xx edges. Inverting the DGP with an inference model (i.e., expressing N; as a function of 3;; LiNGAM uses ICA estimate the DGP) yields the matriz on the right with elements below the main diagonal copturing the DAG's X, + X, edges (as shown by color coding):
X1
1
0
N1
N1
0
0
X1
2
a
2₂
N₂
1 0
X2
X3 ab
b
1
N3
N₂
b
[3]
Overview of theoretical results. Our method extends LiNGAM to noulinear DGPs. First, we show that the inverse DGP's Jacobian and the DAG structure are structurally equivalent (Prop. 1). To apply Prop. 1 to a learned inference model, we describe up to what indeterminacies the inference model is need to be known. Because the ground-truth DGP can only be identified up to certain indeterminacies like scaling, permutation, and sign flips, we need to show for which identifiability notion structural equivalence is preserved (Prop. 2). This requires that we can resolve permutation indeterminacies, which we prove for SEMs in Lem. 1, then design algorithm for this purpose (6 3.4).
3.2 DAG equivalence
To justify using the Jacobian of f-1, i.e., the inverse of the DGP, (denoted as Jy-:), akin to LIGAA''s use of weight matrix, we first connect the DAG and Jy-1 via fundamental concepts from graph theory. The adjacency matriz A of graph with d nodes is a binary d x d matrix where each matrix element indicates the presence, or absence, of an edge (i.e., direct connection) between a pair of nodes X, (Defn. A.8). The conmectivity matrix C of a graph with d nodes is a binary d x d matrix where each matrix clement indicates the presence, or absence, of a directed puth between two nodes X,, X; (Defn. A.9). For DAGs, both A and C are strictly lower- trinerrrrinnrrr-rr thiiisrr-tiiiiiiiii is why we considered only the elements below the main diagonal in Ex. 1. Furthermore, the main diagonal of Jy- has non-zero elements (Ex. 1). We describe the relationship between Jy-1 and (Ią- A) for a DAG via structural equivalence, and investigate its symmetries. Ex. intuits why our claim refers to A and not C: in the matrix mapping from X to N only the edges (captured by A) are
4

---

Published in Transactions on Machine Learning Research (03/2023)
present. Similar to the linear case (and shown more formally below), J and (Ia A) have the same sparsity structure, meaning V (Jz-) = 0 + (La A)ij = 0. We denote this structural equivalence as J DDG (La A), with the full definition and its properties formalized as:
Definition 1 (~DAC). Two matrices S.R of same dimensions are structurally equivalent if (S) =0 (R) 0: ji, Structural equivalence, denoted as DDAG, has the following properties (o denotes composition):
D D-énvariance: a non-singular diagonal matrir D preserves the sporsity structure; thus,
DD o S) DDAG S
(ii) ho -ivariaace: for zero-pre proppeeeervingg transformations ho: (ho(S)),; + (S) 0 then h(S) DAG
(iii प r-equivariance:
permutation π affects the positions of zeros; thus, both operands need to be permated with the same π to maintain DAG, i.e., S MDAG R + (T oT) DAA (T o R),
(iv) Transitivity: SDDAG P PAPPDAA DAG R = S~DAG R
(v) Commutativviy:: S ~DAG R = R ~DGG S.
Before proving structural equivalence, we state our assumptions about the SEM:
Assumption 1 (SEM assumptions). We assume that the cousal DGP fulfils:
(1) The SEM generalive model is given by (1), for which there erists on underlying DAG;
(ti) N₂ are jointly independent;
(tti) There are no hidden confounders cttthfflnnsssstabilliii moreover, the Jacobians J,, -- are structurally faithful (Assum. A.1);
(io) each Is is bijective; and
(v) each X; depend on N; (i.e., 2f(X.N) ON
X.N is diagonal with non-zero elements)
Relying on the properties of ~AGG prove that J--1 can be used to extract the DAG for nonlinear SEMs under Assum. 1 (akin to the linear case shown in Ex. 1; the proof is deferred to Appx. E.2)
Proposition 1. g- DAA Ah) inverse DGP's Jucobian Jr-1 is structurally equivalent to (Is A), when Assum. holds.
Proof (Sketch). From the iterative formulation of the SEM in eq. (2), we note that X (or more precisely, X (N)), a fixpoint of f. Thus, when we apply the chain rule to calculate Jy, we will only have two types of terms (on both sides), namely:
A
8f(X.N) 8X
X.N B = N)(XNN)
(3)
X.N
This expression leads us to a closed form of J.. Then we apply the inverse function theorem at (X, N) to get J-- As the last step, we incorporate the indeterminacies coming from strong ident iiiaiiiitbty- and show based on the properties of ~AAG that the statement of the proposition holds.
Prop. implies that we can extract the DAG from f ie., we can reason about interventions (cf. & 2). We note that if B = La, then (29) describes Additive Noise Models (ANMs) (Hoyer et al., 2008), whereas when additionally A is constant, we recover LiNGAM (Shimizu al., 2006). Prop. 1 assumes that we have access to f'; however, this is non-trivial assumption. In the following, we investigate to what extent we need to estimate f (in form of f to exploit Prop. 1 for this, we leverage the notion of identifiability.
3.3 Identifiability requirements of
The inference model f- we learn from the observed data generally differs from the true inverse of up to certain indeterminacies depending the identifiability guarantees of the (most commonly) NLICA algorithm. This can include scaling, permutation, sign flips, and monotonic element-wise transformations (Hyvärinen et al., 2001; Khemakhem et al., 2020a; Zimmermann et al., 2021). While element- transformations such as scaling or sign-flips do not influence the sparsity structure of the Jacobian, permutations break structural equivalence between the Jacobian and the ground-truth adjacency matrix. That is, we need to resolve the permutation indeterminacy to apply Prop. 1 to Jn 1. With the right ordering(s)?, the Jacobian J, features lower-triangular structure. The following lemma shows that this property determines the ordering of the noise variables such that they yield a lower-triangular Jacobian, ie., all possible causal orderings that ensure structural equivalence to the ground-truth adjacency matrix (the proof is deferred to Appx. E.1):
2hee causal ordering does not need be unique, e.g. the DAG X, X, + Xx the nodes X, and X & are interchangeable

---

Published in Transactions on Machine Learning Research (03/2023)
Lemma 1. (DAG DGPs resolve the permutation ambiguity of ICA| When the DGP is SEM with functional relationships f and an underlying DAG, then the permalation indeterminacy of ICA TICA can be accounled for such that the Jacobian of the inference network will have tower-triangular Jacobian, even with unknown causal ordering a.
Proof (Sketch). Given that the DGP is structured by a DAG, the adjacency matrix A is lower triangular and Assum. ensures that diagonal elements are nonzero. The permutation indeterminacy of ICA (which is expressed as left-multiplicatinn, i.e,, affects the rows) comprises matrices that do not violate lower- triangularity. This gives a single permutation (for unique causal ordering) or set of permutations, each of which ensures lower triangular A.
We emphasize that Lem. 1 refers to two permutations: the permutation indeterminacy of ICA (Lem. makes claim about this) and the causal ordering of the SEM. These can be thought of as permuting the rows (ICA indeterminacy) and columns (causal ordering) of the inference model's Jacobian. Most importantly, Lem. 1 shows that we can resolve the permutation indeterminacy, leading to the following result:
Proposition 2 (J DAG Jz-1 for strongly identified f }().. When the inference model f is strongly identified in the sense of Defn. B.1, the permutation indeterminacies are resolved, and Assum. 1 holds, then J-- DAG J g
Proof. The indeterminacies of strong identifiability (Defn. B.1) include scalings, sign flips, and permutations. By Def. 1(i), ~DAG is invariant to scalings and sign flips; whereas Def. 1iii) states equivariance for permutations, but by Lem. 1, those can resolved for SEMs.
By Def. (ii), Prop. 2 also holds when indeterminacies include zero-preserving transformations.
3.4 Algorithm for CD and determining π
Based on Lem. 1 and Props. 1 and 2, we propose a two-step approach for extracting the DAG from observational but non non-i.i.d i.i.d. data for general nonlinear f
First, we use a suitable nonlinear ICA algorithm to estimate f up to permutations and zero- preserving element-wise nonlincaritics with an inference model g
2. Second, we resolve the permutation indeterminacy by accounting for the causal graph structure. Regarding the second step, we learn the permutations after training with objective that enforces the estimated Jacobian to be lower- wwirntriang To this end, we need to learn both permutation x for the causal ordering as well as a permutation TICA that resolves the indeterminacy in the noise variables introduced by ICA. We use the permuted absolute Jacobian K defined as
K : -Icas
(4)
where SICA, S, are doubly-stochastic matrices that represent a soft permutation on both noise and observation variables, which we parametrize via Sinkhorn networks (Mena et al., 2018) and learn after ICA training cf. 5.1 and Fig. 10 for details. We then introduce training loss inspired by LiNGAM (Shimizu et al., 2006) that encourages K to be lower-triangular by simultancously maximizing i) the sum of the main diagonal and ii) the lower-triangular part, while also iii) minimizing the stricly-upper triangular part of K,
C
Σ aa (K) a (K) + au (K) (K) 2.
(5)
where i E (d, u, u,1; a; > The full learning algorithm is presented in Alg. 1. Compared to LiNGAM, our method is differentiable and works for noulinear SEMs; thus, it does not require itcrating over all permutations. Although Sinkhorn networks (Mena et al., 2018) were previously proposed represent permutation probabilities (Charpentier et al., 2022), we are the first to represent the indeterminacy of ICA with such models.

---

Published in Transactions on Machine Learning Research (03/2023)
Algorithm 1 Algorithm for multivariable CD and determining the causal order π
Input:
dataset D, network parameters 8, Sinkhorn networks SICA, Sx, contrastive loss LCL (eq. (6)),
ordering loss L. (eq. (5)), positive scalars Od, Oa:
Initialize 0
while LCL. not converged do calculate LCL for a batch from D
update A
end while
extract I
while L. not converged do
K- = SICAJa-IS.
G = Eig ad (K) - as (K) + au (K) (K)ss) i4j
update SICA, S.r end while
4 Identifiability in Contrastive Learning
There are fundamental limits to how much one can learn about a DGP from only iid. observations: neither causal structure (Pearl, 2009), nor nonlinear mixing of independent signals (Hyvärinen Pajunen, 1999) are identifiable in the general case. In this work, we describe a non ii.d. (contrastive) DGP, in which significantly more structure can be identified from observations.
In contrastive DGP (Zimmermann et al. (2021); 4.2), generate so-called positive pairs containing two d-dimensional samples (X,X) Underlying X and X are a pair of latent variables of the same dimension N and N, such that X = f(N) and X = f(N). Both N and N have statistically independent components, i.e. Vi.j N, 1 N2 and Ñ, 1 Ny. Furthermore, each component of N depends only the corresponding component of N, such that Vi: N, ~ p(|[N,). In this work, we will often assume that the mapping f is defined as SEM (S 2).
4.1 Identifiability of causal graphs via the ICM principle
In the contrastive DGP, we draw i.id. samples of positive pairs. Inasmuch as consider X and X two observations, the generative process is non-i.i.d. This non-i.i.d DGP leaves more fingerprints in the obscrved data, allowing the identification of causal dependencies that are non-identifiable in the ii.d case We will illustrate why this is the case in the following two-variable example.
N
N₂
N
N
N
N
X1 L X₂ X1 1 X2
X1 /
Xi 1 Xa|Xi
X1
X
X
X
X
X₂ 1 X1
(a) No data augmentation.
(b) Data augmentation. Superscripts denote the two components of the positive pair.
Figure 2: Comparing conditional independencies between observables X, a bivariate model without (Fig. 2a) and with (Fig. 2b) data augmentations in the contrastive pair.
Example 2 (Positive pairs induce additional conditional independencies). Assume bivariate, faithful SEM without confounders, where X1 X2 (Fig. 2a). Observing only i.i.d. copies of X, and X2, the direction of the cause-effedd effect relationship cannot be discerned, the only stalement can make is X, X₂ (Pearl, 2009).
7

---

Published in Transactions on Machine Learning Research (03/2023)
However, consider observing positive pairs from the contrustive DGP, illustrated graphically in (Fig. 2b). As X and X are dependent, there a broader set of conditional independence statements we can make, and these resolve the ambiguity in the causal direction. Namely, X1 (the cause component of X) and X2 (the effect component of X) are statistically dependent via the path X1 < N1 N1 + X X2. However, conditioning on X, blocks this poth, thus X1 1 1 Notably, such conditional independence holds only when 11 + 22, but would not hold, if the direction were reversed to X1 + X2.
Ex. 2 sheds light how Contrastive Learning (CL) enables CD by introducing additional conditional inde- pendencies in the positive pair. This line of reasoning connects our work to the Causal de Finetti (CdF) theorem (Guo et al., 2022), which proves identifability of fully observed causal graphs under a very similar generative process. The key concept in the CdF' is the notion of Independent Causal Mechanisms (ICM), That is, the assumption that various mechanisms that make up the generative process (e.g., individual equations in SEM) change vary in statistically independent manner. In our generative model, when f is a SEM, the ICM principle manifests in the assumption that Vi : 1 Ny. One can thus think of X as an observed counterfactual outcome (also noted in Liu et al. (2023)), where the structural equations have been independently perturbed.
Exploiting the connection to CdF, one can show that in our generative process, all causal relationships become identifiable even in multivariable data in the absence of unobserved (confounder) variables. While showing this is somewhat involved in the asymmetric contrastive DGP of Zimmermann et al. (2021) presented here, other variants of contrastive DGPs including the original model proposed in SimCLR (Chen et al., 2020) or (Dubois et al., 2022)-produce exchangeable positive pairs by relying on two augmented samples (X1, x²), and thus map directly to the CdF setting.
Showing that causal relationships are identifiable from the conditional independence structure in CL is mathematically interesting, but does not yield a practical algorithm. As noted by Guo et al. (2022), the CdF requires an exponential number of conditional independence tests for multivariable CD. Here, we take a different approach, that exploits the full identifiability of the functional relationships f in the same setting.
4.2 Identifiability of the causal graph via identifiability of
We assume the setting of (Zimmermann et al., 2021, Thm. with the additional constraint that dim N = dim d-, under which, an inference model f which minimizes a contrastive loss was proven to estimate the noise variables (often referred to as "sources' the ICA literature) up to a composition of input independent permutations, sign flips, and rescaling. For completeness, we restate the assumptions both for the DGP (Assum. 2) in the main text and defer the model assumptions (Assum. F.1) to the appendix (Appx. F). We denote positive pairs with (-) and negative pairs with (-)-.
Assumption 2 (DGP on Rd). We assume that the DGP satisfies the following conditions: (i) The space of the noise variables to be a convex body (fepperrectangle); i.e., N S R2; (i) The observation space to be X S Rd;
(ii)) The generalor (the SEM) to
1. be béjective,
2. map N C idd+ X, and
3. be differentiable in the vicinity N.
(iv) The marginal distribution p(N) over latent variables N E N is uniforme; i.e,, p(N)=|WT)
(v) The condilionall distribution over posilive pairs p(N () is a rolationally asymmelric generalized normal distribution (Subbotin, 1923) with shape perameter with the corresponding La metric (de- noted as 8), where a 2 1Aa 2 i.c., pNN = (N)e (000e-28(8.) (N..N. with Cp == fé= -16 (N. dN. where X > 0 a porameter controlling the width of the distribution.
We note that Guo et al. (2022) develop CdF from the ICM principle; however, Pearl's autonomous mechanism principle Pearl (2009) might be more appropriate term to use 'Since any random variable in Rd can be emulated by passing a uniformly distributed random variable through the corresponding inverse CDF, if the CDF is differentiable,
can abosrb it into f iIn our experiments, we use a (the Laplace distribution), since certain transitions in natural videos seem to follow the generalized Laplace distribution, and can modeled successfully with the Laplace distribution (Klindt et al., 2021)
8

---

Published in Transactions on Machine Learning Research (03/2023)
We parametrize the conditional distribution (NN[)) via f as in Assum. 2 and calculate the loss
exp 6 ( (X), (x) /T
B (xxxxxx)
- log
(6)
exp -8 (f (x). (x) /T| + E, M exp -8 (f ).
f (x) /T
where X the positive pair, X are the negative pairs, and M is the number of negative samples. During training one has access to observations X, which are samples from these distributions transformed by the generator function (i.e., the SEM) f.
Compatibility of CL and CD. Using observation pairs for CD might seem fundamentally different from conventional approaches, but there is conceptual connection to interventions (Brouillard et al., 2020; Ke et al., 2020; Lippe et al., 2021; Mansouri et al., 2022; Bagi et al., 2023) indeed, several methods rely on data pairs to identify the causal variables (Locatello et al., 2020; Brehmer et al., 2022; Von Kügelgen et al., 2021; Liu et al., 2023; Ahuja et al., 2022a). As stated by Liu et al. (2023), the positive pairs in CL can be thought of as sparsity information about mechanism shifts, making the paradigm suitable for CD. Locatello et al. (2020) relies on interventional pairs to for causal disentanglement. Brehmer et al. (2022) rely on pairs of pre-and post-interventional observations (with perfect interventions, which might be restrictive in practice (Liu et al., 2023)). Namely, since positive samples are "more similar' to the anchor point, the conditional distribution is more restricted (compared to the marginal; c-g., it should have a smaller variance) for the latent factors. However, this will only alfect specific mechanisms (i.e., factors in the factorizing conditional), such as making the factor responsible for the class-determining variable degenerate (i.e., if the anchor depicts a chair, the mechanism encoding the class information will have a delta distribution). Ahuja et al. (2022a) provides identifiability results for sparse perturbations (generalizing (Von Kügglgen et al., 2021); thus, emphasizing the connection to between interventions and contrastive methods. The recent. work of Bagi al. (2023) proposes variational ffeerencebbased approach from interventional data, where the authors partition their latent space into invariant (content) and variant (style) features, which is paradigm also found in CL, including ideutifiability guarantees and competitive performance on the Causal3DIdent dataset (Von Kügelgen et al., 2021). Compared to assuming perfect interventions (Brehmer et al., 2022), degenerate (delta) conditionals for the invariant (content) partition of the latent space (Von Kügelgen et al., 2021), or Gaussian/ Gaussian Mixture priors (Bagi et al., 2023), our rotationally asymmetric generalized normal assumption on the conditional (Assum. 2(v)) is less restrictive.
between identifying the DAG and f. Assum. implies restrictions on the class of SEM we can represent in this framework. In particular, Assum. 2(iv) requires that the noise variables are uniform. This however, is a minimal restriction, considering that any real-valued random variable can be emulated by passing uniform random variable through its inverse cumulative distribution funetion (CDF). Thus, so long the inverse CDF is differentiable, we can absorb it into f without modifying the causal structure implied by the SEM. Assum. 2(v) relates to the type of random perturbation under which the positive pairs are generated. We note that Assum. 2 is specific to the contrastive ICA framework of (Zimmermann et al., 2021) but our approach is not fundamentally limited to the this setting, and can be used in principle in any situation where nonlinear ICA is identifiable, such as in (Hyvärinen & Morioka, 2016; 2017; Morioka et al., 2021; Monti et al., 2019).
Differences
That is, our results state that identifiability of f entails identifiability of the causal graph. However, this is not necessarily true in the other direction, since knowing the Jacobian (which is sufficient to recover the DAG) does not contain all information about f. It remains an open question how practically relevant these differences are.
5 Experiments
5.1
Experimental setup
Data Generating Process (DGP). We experiment with three DGPs; i) linear and ii) nonlinear SEMs (in the form of X fWWN), as well as with iii) Multi-Layer Percoptrons (MLPs) with triangular weight matrices (as used in (Monti et al., 2019)). In all cases, the nonlinear activations (i.c., f) are leaky ReLUs (with a slope of 0.25 for the SEMs and 0.1 for the triangular MLPs). For the SEM DGPs, we exlore three
9

---

Published in Transactions on Machine Learning Research (03/2023)
Table Validation Lem. 1 for linear and nonlinear SEMs with unknown causal ordering to measure how well our method recovers the causal ordering. Mean Correlation Coefficient (MCC) measures identifiaillity, [E*] the maximum number of edges in a DAG, Acc, is the accuracy of recovering the pairwise causal ordering n, whereas gives the ratio of learning a (any) permutation in S and SHD is the Structural Hamming Distance
LINEAR
NONLINEAR
d
MCC
Acc
Acc,
SHD
MCC
Acc
Accx
SHD
3
1.
1.
1.
1.
0.
1.
1.
1.
0.
15
5
0.989 039
0.998 009
0.97420.076
0.76
0.002 o coe
0.988=o.om
0.99419.0a 021
0.957 129
0.583 0.006 021
36
0.834
+0. 23s
0.031
0.851 +0.18a
0.414
0.065 o81
0.781
20.219
0.934+o.0s4
0.889 18
0.345
0.066+0.08.
55
10
0.852
25.
0.931+o.00
0.921+0.14
0.233 0.069+a.os1
0.794-o.
0.255
0.924+0.07a
0.739 252
0.276 0.076+o.07s
options: a) no permutation w.r.t. the causal ordering (i.e., only the ICA permutation remains); b) sparse DGP (with each X; - X edge being nonzero with 0.25 probability); and c) permuted causal ordering (with dense A). Additionally, we ensure that the ordering of N, is unique (all cases), and that the DGP weights are >> (for the SEM DGPs) as otherwise we would be unable to distinguish weak connections from small elements in the Jacobian. That is, the estimate of a weak connection could be the same order of magnitude as the estimate of zero element due to the stochasticity of training-wi we do not enforce this property for the triangular MLPs to compare to the results of (Monti et al., 2019), where such modification was not present. For the permuled SEM DGPs, sample 6 different orderings and 5 seeds for each problem dimensionality 13;5; 8; 100-the the number of seeds is 10 for non-permuted and sparse SEMs. For the triangular MLP, we use d = 6 and 5 scods to compare to (Monti et al., 2019, Fig. 2) and vary the number of layers in the mixing. To use contrastive NLICA for training the inference model, the DGPs needs to satisfy the assumptions underlying the proof of identifiability (Zimmermann et al., 2021, Thm. 6)): the latent space is hypere in Rdd the marginal p(N) is uniform, the conditional p p(N[N) is Laplace, X is generated by a smooth and bijective mapping.
Inference model. To (strongly) identify the SEM, we use contrastive NLICA (Zimmermann et al., which is consistent when the nimber of negative samples goes to infinity- estimate f --1 with a hyperrectangle latent space in gd and the contrastive loss uses the same metric as the conditional, which L, for our case (Assums. and F.1). Our architecture for the inference model is the same MLP as in (Zimmermann et al., 2021) (Tab. 6). To account use two Sinkhorn networks (Mena
for the permutation indeterminacies, et al., 2018) (similar to Charpentier et al. (2022)). A Sinkhorn network is trainable parametrization of sett-permutation matrices (the Birkhoff polytope) (Mena et al., 2018), consisting of two levels: i) the Sinkhorn operator (Fig. 10) normalizes each row and column (in this order) of a matrix to one, relyin on the log-sum-exp operator; ii) the network layer contains the trainable matrix W with the scalar temperature value to ensure convergence to the Birkhoff polytope's vertices, i.c., to yield (hard) permutation matrix. We observed that setting the lowest d (d - 1) /2 elements (for dense DAGs) to zero and converting the resulting K matrix to binary often helped the convergence of the Sinkhorn networks. We calculate the Jacobian of the inference model with the autograd module of PyTorch (Paszke et al., 2019) in the forward pass and vectorize the operation with the recently released functorch library (Horace He, 2021). Moreover, instead using max to aggregate the different Jacobians over the batch, we found using the mean operator more stable in practice.
Figure 3: Hinton diagrams (d = 5): ground truth (left), estimate (right). Size equals magnitude.
Metrics. We measure learning the correct ordering by the ordering accuracy (Acoz, only for the permuted case)-iee the ratio of causal variable pairs Vi < NN), such that the ranking (expressed by sign (i (i-3) j)) matches that in the inferred (permuted) ordering æ, i.c., sign (N (1) r (f)). To normalize, we divide by the number of distinct edge pairs (12((d 1)d) We also report the accuracy (Ace, i.c., the ratio of correctly identified edges, or lack thereof, divided by (E*l) and the Structural Hamming Distance (SHD) (we use
10

---

Published in Transactions on Machine Learning Research (03/2023)
Table 2: Causal discovery performance for linear and nonlinear SEMs with known causal ordering. Mean Correlation Coefficient (MCC) measures identifiability, |E-| is the maximum number of edges in a DAG, Acc is accuracy, Ours is our proposal, HSIC refers to using HSIC independence tests, and SHD is the Structural Hamming Distance
LINEAR Acc(HSIC) SHD
NONLINEAR Acc(Ours) Acc(HSTC) SHD
|89
d
MCC
Acc(Ours)
MCC
3
1.
0.7=0.1
0.741 10G
0.049=0.14
15 5
0.96920.0ms
0.928 13:1
0.828
0.072
2.94
0.858
1.0
0.142
36
8
1.
1.
0.68222.17
0.982
0. 198 0.
0.128
55
10
0.9.663...00
0.832 0.551 20.003 0.168 178 0.962 0.636 0.638 134
2..64
1e-3 as the threshold in all scenarios) for inferring the edges of the DAG, as is standard practice in the literature (Lachapelle et al., 2020; Monti et al., 2019; Ke et al., 2020; Vowels et al., 2022).
Comparison. We use the linear and nonlinear SEM DGPs to showcase that our method can infer the DAG while also learning the correct ordering. Then, we compare to NonSENS (Monti et al., 2019), which, unlike our proposal, does CD on an edge-by-edge basis. Thus, the causal ordering π does not affect how NonSENS operates. We use the HSIC independence test (Gretton et al., 2005) top of contrastive NLICA (Zimmermann et al., 2021) to provide a close comparison with NonSENS (Monti et al., 2019). Notably, since our assumptions provide identifiability up to generalized permutations, there is no need to perform linear ICA on top of contrastive NLICA. Thus, we test independence between the observations X; and the inferved noise variables , although the number tests is d,, we use a Bonferroni correction factor of 4, since each edge determined based on four tests (Monti et al., 2019).
5.2 Results
In all experiments except those in Tab. 1, we used the output of the matching problem as an oracle (solved via the Hungarian algorithm (Kuhn, 1955)) to correct for the permutation indeterminacy of ICA.
The permutation indeterminacies can be resolved (veri- fying Lem. 1). Tab. 1 corroborates the result of Lem. it is possible to resolve the permutalion indeterminacy by assuming a DAG DGP. However, Acc, strongly depends the performance of NLICA, measured by Mcan Correlation Coefficient (MCC). As MCC deteriorates, the correct causal ordering cannot be recovered. Nonetheless, erroneous solutions resulting ing from training stochastic- ity (the most frequent problem according to our observations) can be simply filtered out: in this case the doubly stochastic matrices usually do not converge a pormutation matrix. Inspecting their elements or automatically rejecting such solutions is straightfor- ward. Thus, we report two quantities in Tab. 1: Acc, is the ratio of inferring the order of causal variable pairs when the Sinkhorn networks converged to permutation matrices; æ (with a slight abuse of notation), on the other hand, reports the ratio the successful
10-
03
Preetsion
0.0
0.4
0.6
Recall
Figure Precision vs recall for thresh- olds in [1c-7; 1c0) for lincar (dashed) and nonlinear (solid) sporse SEMs
attempts recover permutation matrices. Clearly, failing to converge to permutation matrix is the bottleneck of this step, since despite failing to scalably recover म, in case of converging to permutation matrix the captured graph reflects most of the edges. This is reported by the Acc, column that is calculated after applying the learned (not necessarily correct) permutations.
Competitive performance on linear and nonlinear SEMs. Tab. 2 demonstrates (with i being known) that our method outperforms HSIC in the lincar case and is at least comparable to HSIC in the nonlinear case- case-note that the entries in J JJ-- were ordered by absolute value and the smallest ones were zeroed namela these are the elements of the Jacobian that most probably correspond to the zeros in the true Jacobian. However, this modification might require additional knowledge about the sparsity of the
11

---

Published in Transactions on Machine Learning Research (03/2023)
DAG. Fig. 4 describes how precision and recall changes for threshold values from [1c-7; 1c0] for sparse DAGs. Notably, the nonlinear curves are better than the linear ones. For additional results on sparse SEMs (Tab. 7) and SEMs with unknown causal ordering (Tab. 8, evaluation is done after accounting for the causal ordering), cf. Appx. G. For sparse SEMs, HSIC is slightly better for larger graphs, whereas in the case of unknown causal ordering, our proposal has better accuracy in most cases. To visualize the inferred graph structure, we plot a Hinton diagram of the true and estimated Jacobians in Fig. 3, showing that J, can capture the edges of an underlying sparse DAG.
Competitive performance on triangular MLPs from (Monti et al., 2019). Tab. 3 summarizes our results with the triangular MLP of (Monti et al., 2019). Despite having small weights in the ground truth Jacobian Jy- (appr. 2e-3 for one and 1e-8 for five layers), our method was able to infer most odges in the DAG. Importantly, the resulting accu- racies are larger than those of our adapted version of NonSENS (Monti et al., 2019). Moreover, our method has the advantage of simultaneously infer- ring all edges based on the structure of J th-ssh
Table 3: Causal discovery performance for the trian- gular MLP from (Monti et al., 2019) with d= 6. ||] denotes the number of MLP layers, Acc the accuracy, Ours is our proposal, HSIC refers to using HSIC inde- pendence tests. Chance level is (for the dense MLP) 21 /36 0.583
||| MCC
Acc (Ours)
Acc (HSIC)
1 1.
0.933+o.042
0.583
it does not require d? pairwise independence test for a DAG with d nodes, Our application of HSIC inde- pendence tests resulted surprisingly low accuracy, despite utilizing an NLICA method with identifi- ability guarantees up to generalized permutations. Interestingly, HSIC resulted in (close-to) chanco-level performance in our repeated experiments-byy by careful inspection of the DGP, we found that the weights are in the order of le-4, which might explain such bad performance. As noted above, since Monti et al. (2019) did not constrain the weights, we used a uniform initialization scheme, which might led to mismatching experimental conditions. Though the use of HSIC was inspired by NonSENS (Monti et al., 2019), since we made different assumptions on the DGP, the results only represent HSIC's (but not NonSENS's) performance.
2 1.
0.944
0.583
3 0.997
20.
1.
0.583
4 0.978
0.9221n.0sr
0.61:
5 0.603 oc2 0.711 0.589
6 Related work
We provide a detailed comparison of related CD methods (Tab. 4) and the use of the Jacobian (Tab. 5) in Appx. D.
Independence tests for CD. Traditional CD methods (Pcarl, 2009; Spirtes & Zhang, 2016; Spirtes et al., 2000; Peters et al., 2017) rely on statistical (conditional) independence tests to infer the graph structure. Recent works also leverage such tests (Shimizu et al,, 2006; Monti et al., 2019; Guo et al., 2022; Karlsson & Krijthe, 2022) to uncover hidden confounders (Karlsson & Krijthe, 2022), for bivariate (Janzing et al., 2009; Monti et al., 2019) or multivariable CD (Guo et al., 2022) for nonlinear SEMs. LiNGAM (Shimizu et al., 2006), which inspired our work, also relies on independence tests to prune edges. Although independence tests provide additional information via significance values, they are not differentiable and can be costly, as d latents require d² tests.
Optimization--aacd CD. Zheng et al. (2018) introduced the continuous optimization-basse NOTEARS algorithm for linear SEMs, which has inspired further research (Khemakhem et al., 2021; Lorch et al., 2021; Ng et al., 2022; Schölkopf et al., 2021a; Yu et al., 2019; Lachapelle et al., 2020; Kalainathan et al., 2018) to provide differentiable methods for CD in neural networks Most of the differentiable solutions (Khemakhem et al., 2021; Ng et al., 2022; Schölkopf et al., 2021a; Yu et al., 2019) constrain the function class, some of them (Tachapelle et al., 2020; Kalainathan et al., 2018) both the function class and the data distribution.
Using the adjacency matrix A. Our work shows that the adjaconcy matrix A and the Jacobian of the inference model - can both be used to model the edges in a graph. We review both, starting with the adjacency matrix for CD: Zheng et al. (2018) use A as regularizer in NOTEARS, Ng et al. (2022) reformulates the SEM with an adjacency matrix for additive models, Schölkopf et al. (2021a) models A with an LSTM in
12

---

Published in Transactions on Machine Learning Research (03/2023)
variational framework. In (Brouillard et al., 2020), A appears for the interventional case. Lorch et al. (2022) leverage amortized variational inference for CD, where they deploy multi-head attention Vaswani et al. (2017)
and use the softmax probabilities as proxy for the adjacency matrix (i.e., their model represents the probability of edges in the graph). Charpenticr et al. (2022) defines a probabílistic model over A to differentiably sample DAGs, then use variational inference to estimate the causal structure, similar to Faria et al. (2022). The proposed method has strong empirical performance, but does not provide thcoretical guarantees for CD.
Using the Jacobian. The Jacobian matrix of either the generative (N + +x)) or the inference (X + N) models are used throughout the literature, both for identifiability and CD (Tab. 5). LINGAM Shimizu et al. (2006) uses the Jacobian (i.c., a constant matrix) to infer the DAG in the linear case, whereas Lachapelle et al. (2020) calculates the Jacobian of the inference work to enforce acyelicity, generalizing to nonlinear additive models. Rolland et al. (2022) consider the same model class as Lachapelle et al. (2020), but they rely on the Jacobian of the score function. Leveraging properties of the Jacobian is also present in the identifiability literature: Independent Mechanism Analysis (IMA) relies on the assumption that the generative model's 's Jacobian has orthogonal columns Gresele et al. (2021) work reasons about the inference network's 's Jacobian, without functional constraints. Although the inspiration comes from the causal principle of independent mechanisms, the claims are about identifiability and not about CD: the IMA function class is locally identifiable, whereas the subclass of conformal maps are identifiable Buchholz et al. (2022). Similar to IMA, Zheng et al. (2022) also utilize the Jacobian of the generative model and prove identifiability for NLICA under a sparsity assumption. Alanackovic et al. (2023) propose a Bayesian approach for CD in dynamical systems, including cyclic graphs, where they associate the graph's edges with the sparsity pattern of the Jacobian of the SEM (in this case an ODE), but the authors do not prove identifiability. That is, although the use of the Jacobian is prevalent in the literature, to the best of our knowledge, we are the first to use the Jacobian of the inference model for causal models without constraining the function class (but using non-ii.d. data, while providing identifiability guarantees.
CD from interventions. Many algorithms can incorporate interventions (Brouillard et al., 2020; Ke et al., 2020; Lippe et al., 2021; 2022; Lorch al., 2021). Interestingly, (Ke al., 2020) provide an extension of (Yu et al., 2019; Zheng et al., 2018) to interventional data, and of the bivariate method of (Bengio et al., 2020) to multivariable one. It is remarkably similar to our proposal, (i.e., admitting general nonlinear functional relationships), but as (Ke et al., 2020) requires interventions, its path is orthogonal to ours. So is the work of (Lippe et al., 2021), which removes any requirement on the data, scales to multiple variables, but requires interventions.
both make assumptions only the data
7 Discussion
Limitations. Our theory requires the guarantees of strong identifiability but not the use of a specific (NLICA) algorithm. Though our experiments demonstrate that fulfilling strong identifiability is sufficient. for CD, we do not vary the NLICA algorithm. Additionally, we acknowledge that since contrastive NLICA requires unique assumptions via the positive pair, it is non-trivial to design a task where the assumptions for multiple methods hold, making comparisons challenging. Our method's applicability is limited for inferring weak edges, similar to (Shimizu et al., 2006; Tashiro et al., 2014; Shahbazinia et al., 2021; Lachapelle et al., 2020). As demonstrated in $ 5, despite its competitive performance, the success of our proposed method highly relies on the performance of NLICA, which can be limited for digens-di problems. Nonetheless, based on our comparisons, this seems to be an issue for the HSIC independence test as well. A possible explanation could be that the class of SEMs is harder to learn with specific NLICA algorithms; indeed, we observed that deploying contrastive NLICA (Zimmermann et al., 2021) achieves much better MCC on general (non-triangular) invertible MLPs. To ensure that particular entries in the Jacobian are non-zero everywhere, our assumptions require that the underlying DAG for the DGP is the same for all data points, which might be restrictive.. . For instance, if the DAG models the interaction of physical objects, then cause-effect relationships are only present when, o.g., the objects are touching each other or their magnotic/electte /electric fields affect each other in the literature, this setting is considered in (Sontakke al., 2021; Seitzer al., 2021).
CD with identifiabiiity beyond CL. As noted in the Limitations section above, our method agnostic to how we achieve identifiabiliy;; however, our investigation only showcased contrastive NLICA. To empha- size that other NLICA -TsCA-based methods are applicable for CD, we discuss how Time-Contrastive Learning
13

---

Published in Transactions on Machine Learning Research (03/2023)
(TCL) Hyvärinen & Morioka (2016) and the Sparse Mechanism Shift (SMS) hypothesis (Schölkopf et al., 2021b) can be leveraged for CD. Monti et al. (2019) relies on TCL. for bivariate CD. The authors show the correspondence between SEMs and the ICA generative model and study temporal sequences. Since the arrow of time defines a cause-effect relationship, relying on TCL is compatible with CD. The assumptions for identi- fiability in TCL (Hyvärinen & Morioka, 2016, Thm. 1) require smooth invertible functions, dim N = dim X, and exponential family distributions with sufficient variability. That is, TCL, needs access to temporal data from different segments, where the intervention targets are the variance parameters. Perry et al. (2022) rely the SMS hypothesis (Schölkopf et al., 2021b) to provably identify causal structures. Assuming that only a subset of mechanisms changes in each environment, the setting is akin to sufficient variability across time segments in TCL.
Unknown causal ordering. Accounting for the causal ordering is, to the best of our knowledge, only found in (Shimizu et al., 2006). Binary CD methods such as (Monti et al., 2019) alleviate this step as they work on an edge-by-edge basis. Other non-ICA-basel methods can also avoid this step since the DAG is invoriant to changes in the causal gelering-mmanninn that reordering X, in the observation vector X (cf. Defn. A.1 does not affect the edges of the graph, only their represenlation in form of an adjacency matrix. However, to resolve the permutation indeterminacy of ICA, we need to account for the causal ordering, since only then can the Jacobian be lower-triangular. Although extracting a lower-triangular Jacobian is casier to interpret and potentially better suiled, e.g,, as a building block of causal representation learning (since the causal ordering of N; is always the same), our method extracts the DAG even without resolving these indeterminacies. That is, our demonstration that the permutation indeterminacies can be resolved should mostly be considered as corroboration of Lem.
Extensions to related work. Using neural networks for CD is discussed in several papers (Monti et al., 2019; Khemakhem et al., 2021; Lachapelle et al., 2020; Lippe et al., 2021; 2022; Brouillard et al., 2020); many of them uses the adjacency matrix, the Jacobian of the inference network (Shimizu et al., 2006; Schölkopf et al., 2021a; Lachapelle et al., 2020) or that of the score function Rolland et al. (2022). On the other hand, the Jacobian of the generative model is prevalent in the identifiability literature Gresele et al. (2021); Buchholz et al. (2022); Zheng et al. (2022), but they do not make claims about CD. Furthermore, methods that can handle general nonlinear relationships either require interventions (Brouillard et al., 2020; Lippe et al., 2021; 2022) or rely on independence tests (Guo et al., 2022; Monti et al., 2019). Our method was inspired by LINGAM (Shimizu et al., 2006) to use the Jacobian of the inference network for inferring the DAG and utilizes NLICA (similar to Monti et al. (2019)) to provide theoretical guarantees (Props. 1 and 2) for multivariable CD. Furthermore, we also prove (Lem. 1) and demonstrate (Tab. 1) that the permutation indeterminacy of ICA and that of an unknown causal ordering can be resolved in the nonlinear case. Concurrent to our work, Morioka & Hyvarinen (2023) leverage CL for multimodal data and show that under specific assumptions both idebbifiability of the latent factors and CD are possible.
Conclusion. Our method uses the Jacobian of the inference function (mapping from observables to independent variables) and can be thought as generalization of LiNGAM (Shimizu et al., 2006) to noulinear Causal Discovery (CD). We prove that the inverse DGP's Jacobian captures the sparsity structure of the DAG (Prop. 1), and show that under strong identifiabilly, the inference model also encodes the same information (Prop. 2). For the latter, we leverage that causal models enable resolving the permutation indeterminacy of ICA under certain assumptions (Lem. 1). We introduced a two-step process to leverage strong identifiability for inferring the DAG of multivariable causal models without constraints on the function class, but assuming non-ii.d. data. That is, our approach leverages NLICA with auxiliary information (coming from the positive pairs, cf. Ex. 2) for CD. We do not claim that NLICA is a CD method per se; however, we show that when the underlying generative model can be described by a causal graph and we have non-i.i.d. data, then CD is possible with NLICA. Particularly, we show that contrastive NLICA (Zimmermann et al., 2021) is compatible with CD. Although the use of the Jacobian is prevalent in the literature, to the best of our knowledge, we are the first to use the inference model's Jacobian for causal discovery without constraining the function class (but using non-i.i.d. data), while also providing identifiability guarantees. Since we do not use conditional independence tests, but learn the causal ordering with Sinkhorn networks, our method provides an end-to-end solution for CD and avoids the cost of exponentially many independence tests. We experimentally demonstrate that our proposal can infer the DAG in multiple synthetic data sets.
14

---

Published in Transactions on Machine Learning Research (03/2023)
Author Contributions
Wicland Brendel initiated the project and guided it together with Forenc Huszár, with input from Matthias Bethge and Bernhard Schölkopf. Ferenc Huszár and Patrik Reizinger derived the theory, Yash Sharma set up the codebase from (Zimmermann et al., 2021), Patrik Reizinger ran the experiments, evaluated the results, and created the figures. All authors wrote the paper.
Acknowledgments
The authors would like to thank Ricardo Pio Monti and Scott W. Linderman for helpful correspondence. We thank Luigi Gresele and Julius von Kügelgen for fruitful discussions. Wieland Brendel acknowledges financial support via an Emmy Noether Grant funded by the German Research Foundation (DFG) under grant no. BR 6382/1-1. Wieland Brendel is a member of the Machine Learning Cluster of Excellence, EXC number 2064/1 Project. number 390727645. Ferenc Huszár acknowledges financial support from UKRI, this research partially supported by Turing AI Fellowship, grant ref: EP HPP/W02265/LL The authors thank the International Max Planck Rescarch School for Intelligent Systems (IMPRS-IS) for supporting Yash Sharma and Patrik Reizinger. Patrik Reizinger acknowledges his membership in the European Laboratory for Learning and Intelligent Systems (ELLIS) PhD program.
References
Kartik Ahuja, Jason Hartford, and Yoshua Bengio. Weakly supervised representation learning with sparse perturbations. In Advances in Newral Information Processing Systems, 2022a. 9
Kartik Ahuja, Yixin Wang, Divyat Mahajan, and Yoshua Bengio. Interventional causal representation learning. In NewrIPS 2022 Workshop on Neuro Causal and Symbolic Al (nCSI), 2022b. URL https: izuaCqx. // //openreview wwt.:neeeennnieeeeeeeeeo kjzzaqg 3, 27
Lazar Atanackovic, Alexander Tong, Jason Hartford, Leo Lee, Bo Wang, and Yoshua Bengio. DynGFN: Bayesian Dynamic Causal Discovery using Generative Flow Networks, February 2023. URL http://arxiv.
org/abs/2302 04178. arXiv:2302.04178 [cs] version: 1. 13, 27
Shayan Shirahmad Gale Bagi, Zahra Gharaee, Oliver Schulte, and Mark Crowley, Generative Causal Representation Learning for Diiitib-Ditiiittiiin Motion Forocasting, February 2023. URL http://arxiv.
org/abs/2300 2w1.2232222222322 arXiv:2302.08635 [cs, stat] version: 1. 9
Yoshua Bengio, Tristan Deleu, Nasim Rahaman, Nan Rosemary Ke, Sébastien Lachapelle, Olexa Bilaniuk, Anirudh Goyal, and Christopher J. Pal. A meta-transfer objective for learning to disentangle causal mochanisms. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.nug net, 2020. 13
Johann Brehmer, Pim de Haan, Phillip Lippe, and Taco Cohen. Weakly supervised causal representation learning. ArXiv preprint, abs/2203.166871 2022.
Philippe Brouilard, Sébastien Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien, and Alexandre Drouin. Dilferentiable causal discovery from interventional data. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. 3, 9, 13, 14, 27
Simon Buchholz, Michel Besserve, and Beruhard Schölkopf. Function classes for ideblifiable nonlinear independent component analysis. In Advances in Neural Information Processing Systems, 2022. 13, 14, 28
Bertrand Charpentier, Simon Kibler, and Stephan Günnemann. Differentiable dag sampling. In International Conference on Learning Representations, 2022. 3, 6, 10, 13, 27
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 1607 PMI.R, 2020.
15

---

Published in Transactions on Machine Learning Research (03/2023)
Pierre Comon. Independent component analysis, new concept? Signal processing, 36(3):287-3)) -144,, 1994. 2, 4 George Darmois. Analyse des liaisons de probabilité. In Proc. Int. Stat. Conferences 1947, pp. 231, 1951. 4
Yann Dubois; Stefano Ermon, Tatsunori Hashimoto, and Percy Liang. Improving sell-supervised learning by characterizing idealized representations. In Advances in Neural Information Processing Systems, 2022.
Frederick Fberhardt; Clark Glymour, and Richard Scheines. On the number of experiments sufficient. and the worst case necessary to identify all causal relations among variables. In Proceedings of the Twenty- First Conference on Uncertainty in Artificial Intelligence, pp. 178-184, 2005.
Gonçalo Rui Alves Faria, Andre Martins, and Mario A. T. Figueiredo. Differentiable Causal Discovery Under Latent Interventions. In Proceedings of the First Conference on Causal Learning and Reasoning, pp. 253 274. PMLR, June 2022. URL https: https::/pproeeedings mlr wtt.pp/s///////ariia/// html. ISSN: 2640-3498. 13, 27
Elisabeth Gassiat, Sylvain Le Corff, and Lue Lehéricy. Deconvolution with unknown noise distribution is possible for multivariate signals. Ann. Statist., 50(1), February 2022. ISSN 0090-5364. doi: 10.1214/ 21-aos2106. URL
10114/21-as22000 4
Robert Geirhos, Jörn-Henria Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann. Shortcut lcarning in deep neural networks. Nature Machine Intelligence, 2(11): 665-673, 673, 2020. 1
Olivier Goudet, Diviyan Kalainathan, Philippe Caillou, Isabelle Guyon, David Lopez- Sopez-Paz, and Michele Sebag. Learning functional causal models with generalive neural networks. In Explainable and interprelable models in computer vision and machine learning, pp. 39-80, Springer, 2018. 3
Luigi Gresele, Paul K. Rubenstein, Arash Mehrjou, Francesco Locatello, and Bernhard Schölkopf. The Incomplete Rosetta Stone problem: Identifiability results for Multi-view Nonlinear ICA. In Proceedings of the 35th Conference on Uncertainly in Artificial Intelligence (UAI), volume 115 of Proceedings of Machine Learning Research, pp. 217-227. PMLR, July 2019. URL https: ptttpp://proceeddngg .mlr mll. p.rrpress/ v115 tall//rreseee22ahtta 2,
Luigi Gresele, Julius von Kügelgen, Vincent Stimper, Bernhard Schölkopf, and Michel Besserve. Independent mechanisms analysis, a new concept? In Advances in Neural Information Processing Systems 34 (NeurIPS 2021), pp.
Curran Associates, Inc., December 2021. URL https : pttp//edccceee.ss.o/ee/e www.ddiiinnnnnnnnn....oo.
4, 13, 14, 24, 27, 28
Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf. Mcasuring statistical dependence with Hilbert-Schmidt norms. In Sanjay Jain, Hans Ulrich Simon, and Etsuji Tomita (eds.), Algorithomic Learning Theory, Lecture Notes in Computer Science, pp. 63-77, Berlin, Heidelberg, 2005. Springer. ISBN 7. 11
978-3-540-31696-1. doi: 10.1007/1156400
Siynan Guo, Viktor Tóth, Bernhard Schölkopf, and Ferenc Huszár. Causal de Finetti: On the Identification of Invariant Causal Structure in Exchangeable Data. ArXiv preprint, abs/ 255/2203..5756, 2022. 2, 3, 8, 12, 14, 27
Hermanni Hälvä and Aapo Hyvärinen. Hidden Markov nonlinear TCA:
Unsupervised learning from nonstation- ary time series. In Ryan P. Adams and Vibhav Gogate (eds.), Proceedings of the Thirty-Sixth Conference on Uncerlainty in Artificial Intelligence, UAI 2020, virtual online, August 3-6, 2020, volume 124 of Proceedings of Machine Learning Research, pp. 939-90 108-948.44 AUAI Press, 2020. 2, 4
Richard Zou Horace He. functorch: Jax-like composable function transforms for pytorch. https://githut:
com/pytorch/ www.rr/cccfcctoccccccoomo 2021. 10
Patrik O. Hoyer, Dominik Janzing, Joris M. Mooij, Jonas Peters, and Bernhard Schölkopf. Noulinear Causal Discovery with Additive Noise Models. In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Léon Bottou (ods.), Advances Neural Information Processing Systems 21, Proceedings of the Twenty-Secome Annuua Conference on Neural Information Processing Systems, Vancowver, British Columbio, Canada, December 8-1,, 2008, pp. 689 696. Curran Associates, Inc., 2008. 2, 3, 4,
16

---

Published in Transactions on Machine Learning Research (03/2023)
Antti Hyttinen, Patrik O Hoyer, Frederick Eberhardt, and Matti Järvisalo. Discovering cyclic causal models with latent variables: a general sat-based procedure. In Proceedings of the Twenly-Ninn Ninlll Conference Uncertainty in Artificial Intelligence, pp. 201-310, 2013. 3
Aapo Hyvärinen and Hiroshi Morioka. Unsupervised Feature Extraction by Time-Contern Chno-Contraative Learning and Nonlinear ICA. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 29: Annual Conference on Newral Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 3765 3773, 2016. 2, 4, 9, 14
Aapo Hyvärinen and Hiroshi Morioka. Nonlinear ICA of temporally dependent stationary sources. In Aarti Singh and Xiaojin (Jerry) Zhu (eds.), Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, volume 54 of Proceedings of Machine Learning Research, pp. 460-469. PMLR, 2017. 2, 4, 9, 24
Aapo Hyvärinen and Petteri Pajunen. Nonlinear Independent. Component Analysis: Existence and Uniqueness Results. Neural Networks, 12(3):429 439, April 1999. ISSN 0893-6080, doi: 10.1016 000016/00933-00 ///////0000000988)) 0000033 URL https: /ttp://oo..ooo /ttp::///oo..oo//////o 10 1016/ 6080 (98) 30140-3. 4, 7
Aapo Hyvärinen, Juha Karhunen, and Erkki Oja. Independent Component Analysis. John Wiley &
Sons, Inc., New York, May 2001. ISBN 047140540X, 0471221317. doi: 10.1002/0471221117.. URL
http::////oi.ogg111/.1 11t.111.0000//4122211111111 2, 4,
Aapo Hyvärinen, Kun Zhang, Shohei Shimizu, and Patrik O Hoyer. Estimation of a Structural Vector Autoregression Model Using Non-Gaussianity. Journal of Machine Learning Research, 11((), 2010. 2, 4
Aapo Hyvärinen, Hiroaki Sasaki, and Richard E. Turner. Nonlinear ICA Using Auxiliary Variables and Generalized Contrastive Learning. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), The 22nd International Conference Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Machine Learning Research, pp. 859 868. PMLR, 2019. 2, 4
Aapo Hyvärinen, Ilyes Khemakhem, and Ricardo Monti. Identifiability of latent-variable and structural- equation models: from linear to nonlinear, February 2023. URT. http://arxiv.oo http://wwww.rgg//////../... 02672. arXiv:2302.0267 [cs, stat]. 4, 24
Dominik Janzing, Jonas Peters, Joris Mooij, and Bernhard Schölkopf. Identifying confounders using additive noise models. In Proceedings of the Twenty-Fii Fifth Conference on Uncertainty in Artificial Intelligence, pp.
249-253 257, 2009. 12
Diviyan Kalainathan, Olivier Goudet, Isabelle Guyon, David Lopez-Paz, and Michèle Sebag. Structural Agnostic Modeling: Adversarial Learning of Causal Graphs. ArXiv preprint, abs/ abs/1803.04929, 2018. 3, 12, 27
Rickard K. A. Karlsson and Jesse H. Krijthe. Combining observational datasets from multiple environments to detect hidden confounding, May 2022. URL http://arxiv [cs, stat]. 12
www.ariivvoovog/eeeeee wtgg/aa////0..o..////gg/g/ 13935. arXiv:2205.13985
Nan Rosemary Ke, Olexa Bilaniuk, Anirudh Goyal, Stefan Bauer, Hugo Larochelle, Bernhard Schölkopf, Michael C. Mozer, Chris Pal, and Yoshua Bengio. Learning Neural Causal Models from Unknown 0.0000...55/...1 [cs, stat), August 2020. URL 1910.01075. 3, 9, 11, 13, 27
Interventions.
01075. arXiv:
Tless Khemakhem, Diederik P. Kingma, Ricardo Pio Monti, and Aapo Hyvärinen. Variational Autoeneoders and Nonlinear ICA: A Unifying Framework. In Silvia Chiappa and Roberto Calandra (eds.), The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy), volume 108 of Proceedings of Machine Learning Research, pp. 2207-222 2217. PMLRR, 2020a. 2, 4,
17

---

Published in Transactions on Machine Learning Research (03/2023)
Ilyes Khemakhem, Ricardo Pio Monti, Diederik P. Kingma, and Aapo Hyvärinen. ICE-BeeM: Identifiable conditional energy-based deep models based on nonlinear TCA. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Ilsuan-Tien Lin (eds.), Advances in Neurol Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 2- 2020, virtual, 2020b. 2, 23, 24
Tyes Khemakhem, Ricardo Pio Monti, Robert Leech, and Aapo Hyvärinen. Causal Autoregressive Flows. Tn Arindam Banerjee and Kenji Fukumizu (eds.), The 24th International Conference Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pp. 3520 3528. PMLR, 2021. 3, 12, 14, 24, 27
David A. Klindt, Lukas Schott, Yash Sharma, Ivan Ustyuzhaninov, Wieland Brendel, Matthias Bethge, and Dylan M. Paiton. Towards nonlinear disentanglement in natural data with temporal sparse coding. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021.
OpenReview.nel, 2021. 2, 4, 8
Andrej N Kolmogorov. Sulla determinazione empirica di una legge didistribuzione. Giorn Dell inst Ital Degli Att, 4:89 91, 1933. 30
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2 (1-2):83 97, 1955. 11
Trent Kyono, Yao Zhang, and Mihacla van der Schaar. Castle: Regularization via auxiliary causal graph discovery. Advances in Neural Information Processing Systems, 33:1501 1512, 2020.
Sébastien Lachapelle, Philippe Brouillard, Tristan Deleu, and Simon Lacoste-Julien. Gradient- neural DAG learning. In 8th International Conference on Learning Represenlations, ICLR 2020, Addis Abala, Ethiopia, April 26-30, 2020. OpenReview.nee net, 2020. 2, 3, 11, 12, 13, 14, 27
Sébastien Lachapelle, Pau Rodriguez, Yash Sharma, Katie E Everett, Rémi Le Priol, Alexandre Lacoste, and Simon Lacoste-Julien. Disentanglement via mechanism sparsity regularization: A new principle for nonlinear ica. In Conference on Causal Learning and Reasoning, pp. 428 484. PMLR, 2022. 2
Hao-Chih Lee, Matteo Danieletto, Riccardo Miotto, Sarah T Cherng, and Joel T Dudley. Scaling struc- tural learning with no-bears to infer causal transcriptome networks. In PACIFIC SYMPOSTUM ON
BIOCOMPUTING 2020, pp. 391-402. World Scientific, 2019. 3
Phillip Lippe, Taco Cohen, and Eistratios Gavves. Efficient neural causal discovery without acyclicity constraints. ArXiv preprint, bos//210..1044 2021. 3, 9, 13, 14, 27
Phillip Lippe, Sara Magliacane, Sindy Löwe, Yuki M Asano, Taco Cohen, and Stratis Gavves, CITRIS: Causal Identifiability from Temporal Intervened Sequences. In International Conference on Machine Learning, pp. 13557 13603. PMLR, 2022. 13, 14
Yuejiang Liu, Alexandre Alahi, Chris Russell, Max Horn, Dominik Zietlow, Bernhard Schölkopf, and Francesco Locatello. Causal Triplet: An Open Challenge for interventionn-cetricc Causal Representation Learning, January 2023. URL
0001100//2011.0111..... 05169. arXiv:2301.05/0 00511699111111 [cs]. 8, 9
Francesco Locatello, Stefan Bauer, Mario Lucic, Gunnar Räisch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem. Challenging common assumptions in the unsupervised learning of disentangled representations. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 4114 4124. PMIR, 2019. 4
Francesco Locatello, Ben Poole, Gunnar Rätsch, Bernhard Schölkopf, Olivier Bachem, and Michael Tschan- nen. Weakly-supervised disentanglement without compromiscs. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 18-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 6348 6359. PMLR, 2020. 9
18

---

Published in Transactions on Machine Learning Research (03/2023)
Lars Lorch, Jonas Rothfuss, Bernhard Schölkopf, and Andreas Krause. DiBS: Differentiable Bayesian Structure Learning. Advances in Newral Information Processing Systems, 34:24111 14:221111-4123,, 2021. 3, 12, 13, 27
Lars Lorch, Scott Sussex, Jonas Rothfuss, Andreas Krause, and Bernhard Schölkopf. Amortized inference for causal structure learning. In NewrIPS 2022 Workshop on Causality for Real-world Impact, 2022. 2, 3, 13, 27
Ian D. Maedonald. The theory of groups / Ian D. Macdonald. Clarendon Press Oxford, 1968. ISBN 0198531389. 25
Amin Mansouri, Jason Hartford, Kartik Ahuja, and Yoshua. Bengio. Object-centric causal representation learning. November 2022. URL https://openreview http://wnnnne/oommmmmd/daaaaoooo
9
Gonzalo E. Mena, David Belanger, Scott W. Linderman, and Jasper Snoek. Learning latent permutations
with gumbel-sinkhorn networks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 2018, Conference Track Proceedings. OpenReview.net, 2018. 6, 10, 31
Jovana Mitrovic, Dino Sejdinovic, and Yee Whye Teh. Causal inference via kernel deviance measures. Advances in neural information processing systems, 31, 2018. 3
Ricardo Pio Monti, Kun Zhang, and Aapo Hyvärinen. Causal discovery with general non-linear relationships using non-linear ICA. In Amir Globerson and Ricardo Silva (eds.); Proceedings of the Thirly-Fifth Conference on Uncertainty in Artificial Intelligence, UAT 2019, Tel Aviv, Israel, July 22-25, 2019, volume 115 of Proceedings of Machine Learning Research, pp. 186 195. AUAI Press, 2019. 2, 3, 4, 9, 10, 11, 12, 14, 24, 27
Raha Moraffah, Bahman Moraffah, Mansooreh Karami, Adrienne Raglin, and Huan Liu. Causal adversarial network for learning conditional and interventional distributions. ArXis preprint, abs/2008.11377 2020. 3
Hiroshi Morioka and Aapo Hyvarinen. Conneciivity.contrasi learning: Combining causal discovery and representation learning for multimodal data. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, pp. 3399-3426. PMLR, April 2023. URL https://proceeddng: mlr.
press//v26/moccitt223..l html. ISSN: 2640-3498. 14
Hiroshi Morioka, Hermanni Hälvä, and Aapo Hyvärinen. Independent innovation analysis for nonlinear vector antoregrossive process. In Arindam Banerjee and Kenji Fukumizu (eds.), The 24th International Conference on Arlificial Intelligence and Stalislics, AISTATS 2021, April 13-15, 2021, Virtual Event, volune 130 of Proceedings of Machine Learning Research, pp. 1549 1557. PMLR, 2021. 2, 9
Ignavier Ng, AmirEmad Ghassami, and Kun Zhang. On the Role of Sparsity and DAG Constraints for Learning Linear DAGs. Advances in Neural Information Processing Systems, 33:17943- 17954, 2020. 3
Ignavier Ng, Shengyu Zhu, Zhuangyan Fang, Haoyang Li, Zhitang Chen, and Jun Wang. Masked Gradient- Based Causal Structure Learning. In Proceedings of the 2022 SIAM International Conference on Dala Mining (SDM), pp. 424-432. SIAM, 2022. 2, 3, 12, 27
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deop learning library. Advances in neural information processing systems, 32, 2019. 10
Judea Pearl. Causalily- Cambridge University Press, Cambridge, 2 edition, September 2009. ISBN 9780511803161, 9780521895606, 9780521749190. doi: 10.1017/ccb097555118888666 URL /ttps://doil org/ 10. 00011077/c00977001188111111 3, 7, 8, 12
Ronan Perry, Julius von Küigelgen, and Bernhard Schölkopf. Causal Discovery in Heterogeneous Environments Under the Sparse Mechanism Shift Hypothesis. In Advances in Neural Information Processing Systems, 2022. 14
19

---

Published in Transactions on Machine Learning Research (03/2023)
J Peters, J Mooij, D Janzing, and B Schölkopf. Identifiability of causal graphs using functional models. In FG Cozman and A Pfeffer (eds.); 27th Conference on Uncertainly in Artificial Intelligence (UAT 2011), 1), pp- 589 598, Corvallis, OR, USA, 2011. AUAI Press. 2,
J. Peters, D. Janzing, and B. Schölkopf. Elements of Causal Inference Foundations and Learning Algorithms.
MIT Press, Cambridge, MA, USA, 2017. 1, 12, 22
Garvesh Raskutti and Caroline Uhler. Learning directed acyclic graph models based on sparsest permutations. Stat, 7(1), 2018.
Paul Rolland, Volkan Cevher, Matthäus Kleindessner, Chris Russell, Dominik Janzing, Bernhard Schölkopf, and Francesco Locatello. Score Matching Enables Causal Discovery of Nonlinear Additive Noise Models.
In International Conference on Machine Learning, pp. 17741-1753, PMLR, 2022. 13, 14, 27
Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proc. IEEE, 109(5):612-634, May 2021a. ISSN 0018-9219, 1558-220 2256. doi: (0.1109/jproc. tttp:/poo......1.....2 2021.305894.. URL 3058954. 2, 3, 12, 14, 27
2021.
Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proc. IEEE, 109(5):612-65) 6344 May 2021b. ISSN 0018-9219, 1558-2256. doi: 111109//proo.2221.33555 3058954. 14
URL /ttt: 2021.
Maximilian Seitzer, Bernhard Schölkopf, and Georg Martius. Causal influence detection for improving elficiency in reinforcement learning. Advances in Neural Information Processing Systems, 34:22905 -209900--22118--
2021. 13
Amirhossein Shahbazinia, Saber Salehkaleybar, and Matin Hashemi. ParaLiNGAM: Parallel causal structure learning for lincar non-gaussian acyclic modcls. arXio: Distributed, Parallel, and Cluster Computing, 2021. DOI: MAG ID: 3202634766. 2, 13
Xinwei Shen, Furui Liu, Hanze Dong, Qing Lian, Zhitang Chen, and Tong Zhang. Weakly Supervised Disentangled Generative Causal Representation Learning. Journal of Machine Learning Research, 23:1-55, 2022. 2, 3, 27
Shohei Shimizu, Patrik Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A Linear Non- Gaussian Acyelic Model for Causal Discovery. Journal of Machine Learning Research, 7(10), 2006. 2, 3, 4, 5, 6, 12, 13, 14, 24, 27
Nickolay Smirnov. Table for estimating the goodness of fit of empirical distributions. The annals of mathematical statistics, 19(2):279-2)) 2-11, 1948. 30
Sumedh A. Sontakke, Arash Mchrjou, Laurent Itti, and Bernhard Schölkopf. Causal curiosity: RL agents
discovering self-supervised experiments for causal representation learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 2021. 13
PMLR,
Peter Spirtes and Kun Zhang. Causal discovery and inference: Concepts and recent methodological advances. Applied Informatics, 3(1):3, February 2016. ISSN 2196-0089. doi: 10. 11166//40535-01--0000 URL https://doi.org: 10. http://...1./////.11111 1188//440350016-000110
12
Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Cousation, prediction, and search. MIT press, 2000. 3, 12
Chandler Squires, Anna Seigal, Salil Bhate, and Caroline Uhler. Linear Causal Disentanglement via Interventions, February 2023. URL http:///rre http://aaxxv..o/////////// wrgg/bs////1.11...b 16467 arXiv:2211.1644 16467 [cs, stat). 3, 27
20

---

Published in Transactions on Machine Learning Research (03/2023)
Mikhail Fedorovich Subbotin. On the law of frequency of error. Mat. Sb., (1(2):296 301, 1923. 8
Tatsuya Tashiro, Shohei Shimizu, Aapo Hyvärinen, and Takashi Washio. ParceLiNGAM: causal ordering method robust against latent confounders. Neural Comput., 26(1):57-83, January 2014. ISSN 0899-7667, 1530-888X. doi: 10.1162/neco 00533. URL. httpp:://do...or///./ 1162/neco__ooee 00533. 2, 13
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Fukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017. 13
Julius Von Kügelgen, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf, Michel Besserve, and Francesco Locatello. Self-Supervised Learning with Data Augmentalions Provably Isolates Content. from Style. Advances in neural information processing systems, 34:16451 16467, 2021. 4, 9, 24
Matthew J. Vowels, Necati Cihan Camgoz, and Richard Bowden. D'ya like DAGs? survey on structure learning and causal discovery. ACM Comput. Sure., abs/2103.0255555 April 2022. ISSN 0360-0300, 1557-7341. doi: 10.1145, 144/3527154. URL https:/ /tt.//oi..o// org/ 10. /141/15221111 3, 11
Dennis Wei, Tian Gao, and Yue Yu. Dags with no fears: A closer look at continuous optimization for lcarning bayesian works Advances in Newral Information Processing Systems, 33:3895 3906, 2020. 3
Matthew Willetts and Brooks Paige. Don't Need 8) mathbffu]]: Identifiable Non-Linear ICA Without Side Information. ArXiv preprint, 0t///2206.0022233 2021. 2
Mengyue Yang, Furui Liu, Zhitang Chen, Xinwei Shen, Jianye Hao, and Jun Wang. CausalVAE. Disentangled Representation Learning via Neural Structural Causal Models. In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 9588 9597, 2021. doi: 10.1109 CCCC///RR 2021..0097. 3, 27
Yue Yu, Jie Chen, Tian Gao, and Mo Yu. DAG-GNN: Dag structure learning with graph neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 7154-7163. PMLR, 2019. 2, 3, 12, 13, 27
K Zhang and A Hyvärinen. On the Identifiability of the Post-Nonlinear Causal Model. In 25th Conference on Uncertainty in Artificial Intelligence (UAI 2009), pp. 647 655. AUAI Press, 2009. 4
Kun Zhang, Jiji Zhang, and Bernhard Schölkopf. Distinguishing Cause from Effect Based Exogeneity. Tn Fifteenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK), 2015, pp. 261-271.
Carnegie Mellon University, 2015. 2, 3
Xun Zheng, Bryon Aragam, Pradeep Ravikumar, and Eric P. Xing. DAGs with NO TEARS: Continuous optimization for structure learning. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 0492-9503, 2018. 2, 3, 12, 13, 27
Yujia Zheng, Ignavier Ng, and Kun Zhang. On the identifiability of nonlinear ica: Sparsity and beyond. In Aduances in Neural Information Processing Systems, 2022. 13, 14, 27
Roland S. Zimmermann, Yash Sharma, Steffen Schneider, Matthias Bethge, and Wieland Brendel. Contrastive
learning inverts the data generating process. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, 1CML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 12979 12990. PMLR, 2021. 2, 4, 5, 8, 9, 10, 11, 13, 14, 15, 24, 25
21

---

Published in Transactions on Machine Learning Research (03/2023)
Appendix
A SEMs
Definition A.1 (SEM). A SEM describes causal relationships via a set of structural assignments (Peters et al., 2017):
X; f. VEEI= fl....,d]
(7)
where Xs are the endogenous, N; the exogenous/noise variables, Pa; X {Xi} denoles the parent set of X,, I the set of indices, and f, the mappings.
Definition A.2 (Reduced form of SFM).. The reduced form of the SEM expresses all X; as function of only the N₂ voriables, i.c.:
:= (N')
d 13,
(8)
with the same nolation as in Defn. A.1, slightly abusing f and denoting a subset of N by N C.N Definition A.3 (Chain). A graphical structure of three nodes Ns, Xp, Xg is called chain if two nodes are both parents of the third. Graphically, this means:
X
X
X
Figure Visualization of chain. Conditioning on the middle node (denoted with gray color) blocks the path X, - Xx - Xg-
That is, the following conditional independence (denoted by 1) relationship holds:
Xp 1 Xg
(9)
Definition A.4 (Collider). A graphical structure of three nodes Xr, Xp. X, is called collider if two nodes are both parents of the third. Graphically, this means:
X
X
Figure 6: Visualization of a collider. Conditioning on the collider node (denoted with gray color) opens the path X, + +
That is, the following conditional dependence (denoled by X.) relationship holds:
Xp x
(10)
Definition A.5 (Fork). A graphical structure of three nodes XR, Xp, X₂ is called fork if one node is the parent of the two other nodes. Graphically, this means:
X
Figure 7: Visualization of a fork. Conditioning on the fork node (denoted with gray color) blocks the path X, t -x
That is, the following conditional independence (denoted by 1) relationship holds:
X, 1 Xg
(11)
22

---

Published in Transactions on Machine Learning Research (03/2023)
Definition A.6 (Confounder (unobserved common cause)). In DAG with nodes X; Vi E EI fl.....d d} node X is called confounder if there exist at least. two P1Ω E I X E Pa, A Xx E Pa, and X is
unobserved. Graphically,
N
N
N 4
Figure 8: Visualization of confounder (unobserved common cause), indicated by gray node color.
Definition A.7 (Causal ordering). The cousal ordering π is a bijective automorphism on the index set I. Nomely, x I + I so that vX, + x,, it holds that if x (i) < < (J) = X, & Pa;-
The definition means that only a node with a smaller index in æ can be a parent of a node with a larger index. Note that though X; can be a parent of X,, is not necessary, but Xj cannot be a parent of X,, Multiple orderings may exist, o.g. if there are multiple X, so that they only have a single parent. ı helps have a unique description of the edges in the graph. Namely, the edges are organized in the adjacency matrix A according to æ, then A will be strictly lower triangular.
Definition A.8 (Adjacency matrix). The adjacency matrir A is binary d d matria, where Aij =1 Xj E Pa,. The rows of A are ordered by πł; thus, A is strictly lower-triangular.
A only describes the edges of the DAG, which gives the direct cause-effect relationships. Nodes can be influence each other via paths (i.e., set of directed edges that can be traversed between the two nodes), which can be described by the connectivity matrix C
Definition A.9 (Connectivity matrix). The connectivity matrix C is binory d x d matriz, where C = + Sp:X, .... X, C= Ei=1' A'. The rows of C are ordered by π; thus, C is strictly lower-triangular. Assumption A.1 (Structural faithfulness). The set of N's 's that induces additional zeroes (i.e., a sparser DAG) in the Jacobions J,, J has zero measure, i.e., both Jacobions describe the sparsity structure of the underlying DAG DGP with probability one (J w.r.t. C, shown in Lem. A.1; J w.r.t. A). Alternatively, the structural independencies are reflected in functional form via , g-1--1 We call this properly structural faithfulness.
Definition A.10 (DGP with known x). The DGP is described by the SEM, when π is known. Lee., the flow of information is: N SEM X.
Definition A.11 (DGP with unknown T). The DGP with unknown v is given by the SEM, and by a permutation matriz (with a slight abuse of notation) applied to X. L.e., the flow of information is: N SEM
X - X.
Lemma A.1 (J, NDGG (Ia + C)). Given Assum. 1, the partial derivatives of f w.r.t. N, provide information about C, as
0ʃ: - - AX (J)) ON
X1
We emphasize that the derivatives are also non-zero in the case of indirect paths, i.e., when 3X2 Ep:i k. Furthermore, the strictly lower triangular part of J has the describes the same DAG as C-or equivalently, Jy DG (I++C).
B Identifiability definitions
Definition B.1 (Strong Identifiability (Khemakhem et al., 2020b)). Given a parameter class θ when the feature extractors 98, 90, X N produce latent representations N₁ 9e, (X), N₂ 9s, (X) that are
23

---

Published in Transactions on Machine Learning Research (03/2023)
equivalent up to scoled permutations and offscts for all 01,02 O i.e.,
81 02 = N 98, (X) DPgs, (X) +
(12)
where D is a diagonal and a permulaaioo malria. Then 02, 02 fulfilt un equivalence relationship.
Definition B.2 (Weak Identifiability (Khemakhem et al., 2020b)). Given a parameter class Q when the feature extractors 9 9e, X - N produce latent representations N1 = ga, (X), N2 = 9 (X) that are equivalent up matria multiplications and offsets e ffor all 01,02 θ i.e.,
01 02 N 9o, (X) Ago, (X) +c,
(13)
where rank (A) 2 min (dimW; dim X). Then 0,,02 fulfill an equivalence relationship.
Definition B.3 (Identifiability up to elementwise nonlinearities (Hyvärinen & Morioka, 2017)). Given a parometer class O when the feature extractors 90, 902 X + N produce latent representations N1 =
9a. (X), .2 9a. (X) that are equivalent up elementwise nonlinearities, matrix multippicaations and offsets for all 01, 02 6 i.e.,
01 8~~0 t
= N go, (X) = Ao 99, (X) +c,
(14)
where rank (A) 2 min (dim dim X) and a denotes an elementwise nonlinear transformation. Then 0,, B2 fulfill an equivalence relalionship.
C Compatibility of SEM-ICA assumptions
Several works investigated the relationship between SEM and ICA (Gresele et al., 2021; Monti et al., 2019; Shimizu et al., 2006; Von Küggelgnn et al., 2021; Hyvärinen et al., 2023); however, it is unclear whether and which assumptions both fields are compatible. This section relies on (Monti et al., 2019, App. B.), where the authors detail the SEM-ICA connection for lincar modcls. The clear difference is that the conventional SEM formulation (Defn. A.1) expresses each X; as function of Pa,nd N₂; whereas ICA only uses N.. Formally:
X; : = f: (Pa,, NJ), ViEI= .. d} X; f7 (N'), WiEI= d 1).
(15)
(16)
where the former is the conventional definition (Defn. A.1). whereas the latter is reduced form of the SEM (Defn. A.2, with N demoting a subset of N, i.e., N' C N), corresponding to the ICA model. Note that we use an asterisk to denote that the f. of the two equations can be different.
C.1 Bijectivity of It is common to assume bijective map from the causes (sources) to the effects (observations) in both the causality (Khemakhem et al., 2021; Gresele et al., 2021; Monti et al., 2019) and the ICA (Zimmermann et al., 2021; Von Kügelgen et al., 2021; Shimizu et al., 2006; Gresele et al., 2021) literatures. However, since the maps in (15) and (16) are not necessarily the same, we need to investigate whether those assumptions are compatible.
Proposition (Equivalence of bijectivity in SEMs and ICA). Assuming bijectivity of f. (Pa,, N.) and that of ft (N*) are equivalent.
Proof. For the proof, we will use an inductive argument and, w.l.o.g,, assume that each X; depends all N Njge (if there are less dependencies, those arguments be omitted).
J: = f7 We start from the conventional SEM equations (Defn. A.1):
X = S1 (Ni)
(17)
X₂ = fz N2)
(18)
Visually, the question whether the blue and the red arrows commute (blue are assumed be bijective, the red's bijectivly needs to be proven):
24

---

Published in Transactions on Machine Learning Research (03/2023)
N1
X
N2
X2
By assumption, fi is bijective (in Ni), and so f2 (in X and N2). Since fi fii we proceed (18) and substitute (17) into (18), yielding:
(19)
Since the composition of bijective maps is bijective (Macdonald, 1968), the map from N1 to X2 is bijective, since the maps N1 - X1 and X1 + X2 are bijective by assumption, yiclding the bijectivity of fū- Then, apply the same argument inductively for X3 := f2 (X1, Na), and up to Xa-
= fi
We start from the reduced SEM equations (Defn. A.2):
X1 (N) X2: (VV.
(20)
(21)
Visually, the question whether the blue and the rod arrows commute (blue are assumed be bijective, the red's bijectivly needs to be proven):
N1
X1
N2
X
By assumption, fi is bijective (in Ni), and so is f2 (in N, and N2). Again, fi fi, proceed to (21). Since X1 and N1 relate via bijective map, there is no information lost in the mapping. Thus, using X, instead of N is possible since fi maintains bijectivity it can be undone by (fi) which exists by assumption. N1 + X1 and N1 + X2 are bijective maps, decomposing the latter into N1 + X1 + X2 only implies that N1 - X, is injective and X1 + X2 is surjective (Macdonald, 1968). Fortunately, the N1 + X1 is bijective by assumption, so we only need to show that X₃ + X2 is not only surjective, but also bijective. Since both X, and X2 have the same domain, X1 - X2 is bijective (Macdonald, 1968). Then, we apply the same argument inductively for X3 = f2 (N1, N2, Na), and up to Xa.
C.2 Does identifiability imply no confounders?
Identifiabilty can be thought as "inverting" the DGP Zimmermann et al. (2021). So the question is whether identifiability implies that the learued representation needs to capture N., when the assumptions include that N₁ are jointly independent? Additionally, we assume that dim N dim X d. Intuitively, if there would be confounder, it would induce additional correlation between at least two Xp and X,- That is, N, and N₂ would need to "emulate" that when X changes (via N1), then both X, and X, would need to change.
Proposition 4 (Identifying jointly independent N, implies no confounders.). Under the assumption of jointly independent N; and dim N dim X d, identifiability at least up to elementwise nonlinearities (Defn. B.3) implies that there cannot be confounders.
Proof. We assume that there is a confounder Xx. which the common cause of Xp and X, the argument generalizes to more children of Xx. Two cases emerge: when there is a directed path X, + + X, (p and q are interchangeable for our argument), or when there none.
6'hhat is, Xp ran be the parent of Ngy and they still have another comman canse Xx
25

---

Published in Transactions on Machine Learning Research (03/2023)
No directed path between Xp and Xg Recall from Defn. A.6 that these relationships materialize in the following graph:
N
N
N
X
X
Figure 9: Visualization of confounder (unobserved common cause), indicated by a gray node color.
From the graph, we can describe the conditional independence relationship of N, and Ng. Namely, we have access to observations Xp and gg. implying (1 denotes conditional independence):
N, L NglXp:
(22)
since conditioning of X, and X, activates the colliders (Defn. A.4) N, + x, + Xx and X + +X + No, the path between Np and Ng opens up. Thus, N, and N₂ become dependent, contradicting the assumption that N, N
There is at least one directed path between Xp and X, By noticing that conditioning on X, and X, blocks any paths between X, p and X, the conclusion is the same above.
26

---

Published in Transactions on Machine Learning Research (03/2023)
D Extended related work
Table 4:
Comparison of CD methods. Columi x indicates multivariability, do (0) indicates whether the method can be applied only observational data, indicates constraints on the function class of the SEM, 0/0 indicates differentiability, and the data column lists restrictions the data distribution.
METHOD
X
do (0)
f
0/0
DATA
MONTI ET AL. (2019)
X
X
NON-STATIONARY
SHIMIUU ET AL. (2006)
LINEAR V
SAUSGAUS
GUO ET AL. (2022)
V
X
EXCHAGEABILITY
KHEMAKHEM ET AL. (2021)
AFFINE/ ADDITIVE ADDITIVE
LACHAPELLE ET AL. (2020)
GAUSSIAN
BROUILLARD ET AL. (2020)
X
KE (2020)
DISCRETE
LIPPE BT AL. (2021)
NG (2022)
ADDITIVE
SCHÖLKOPP ET AL. (2021A)
LINEAR ADDITIVE
ZHENG AL. (2018)
LINEAR
YU ET AL. (2019)
ADDITIVE
SHEN ET AL. (2022)
ADDITIVE
LABELING
KALAINATHAN ET AL. (2018)
ADDITIVE
GAUSSIAN
ROLLAND ET AL. (2022)
ADDITIVE
V
YANG ET AL. (2021))
ADDITIVE
LABELING
LORCH ET AL. (2021)
10
GRAPH PRIOR
LORCH AL. (2022)
GRAPH PRIOR
CHARPENTIER ET AL. (2022)
GRAPH PRIOR
FARIA
(2022)
X
/
GRAPH PRIOR
ZHENG ET AL. (2022)
LINEAR POLYNOMIAL
GAUSSIAN
AHUJA AT. (2022B)
V12
SQUIRES ET AL. (2023)
X
LINEAR
X
ATANACKOVIC (2023)
CYCLIC (ODE)
Ours
V
ASSUMS. 2 AND F.1
Table 5: Using the Jacobian in the literature for CD and/or or identifiability. Column f indicates constraints on the function class of the SEM, the data column lists restrictions on the data distribution, J descríbes the Jacobian of which function is used, CD indicates use for causal discovery, and the identifiability column whether the method has identifiability guarantees.
METHOD
f
DATA
CD
IDENTIFIABILITY
SHIMIZU ET AL. (2006)
LINEAR ADDITIVE
NON-GAUSSIAN GAUSSIAN
J
LACHAPELLE ET AT. (2020)
J 1
X
GRESELE ET AL. (2021)13 13
IMA
J
X
V
ZHENG AL. (2022)
SPARSE
X
V
ROLLAND ET AL. (2022)
ADDITIVE
SCORE FUNCTION
X
ATANACROVIC ET AL. (2023)
ASSUMS. 2 AND F.1 CYCLIC (ODE)
J,
X
Ours
J
V
of is generally assumed to be invertible, but omitted mentioning it for brevity. That is, / in this column does not neocssarily mean restrictions at all, including our method, which also relies bijective f Supervised Supervised
Lorch al. (2021) also leverage interventional data, but it also works from observations
Faria et al. (2022) assume latent intervention targets; known interventions can also be incorporated semi-supervised extension 12, Ahuja
(2022h) has stronger identifiability results when interventional data available
27

---

Published in Transactions on Machine Learning Research (03/2023)
E Proofs
E.1 Proof of Lem. 1
Lemma 1. (DAG DGPs resolve the permutaation ambigaity of ICA] When the DGP is a SEM with functional relationships and an underlying DAG, then the permatation indeterminacy of ICA TICA can be accounted for such that the Jacobian of the inference network will have lower- Nower-briangular Jacobian, even with unknown causal ordering
Proof. The unknown causal ordering of N; implies the right-muullplication of J with x x- the permutation indeterminacy of ICA the left-multiplication with TICA, yielding the estimated Jacobian J 1:
J J - VICA o J
(23)
where FICA and -- are not necessarily the same.
If i is unique, only need to show that TICA is also unique. Assume that there exists TICA, * TICA.2 such that Jz- can be transformed into a lower-triangular J by both. This implies that the rows of Jz- can be permuted such that it yields a lower-triangular J (when π is already accounted for). Assume that TiCa,1 yields twerrttiannulla J--.. Then a different TICA,2 means that there are at least two rows i, k in Ja-1 that can be permuted differently than in TICA,1 such that the resulting matrix is still lower- trianngaaan,aarr J has non-zero diagonal (cf. the definition of in (26)): thus, using a different ordering TICA,2 will violate lower-triangalarity for this means that the 7th bthh rows after applying #ICA,1 will be equal to the hth tth rows of TICA,2 (the former being equal to the true Jacobian Jy):
-1 IICA,1 o J o
= [J
-- ICC o J o [k,]]
(24)
[.A)
which means that for TICA,2 the resulting matrix has nonzero elements at indices ki, and (k, i). This violates lower-triangularit, since k & i, so one of the above means that there is at least one non-zero element above the main diagonal, leading to a contradiction.
If x not unique, we can apply the above argument, resulting in a set of permutation matrices, each yiclding a lower-triangular Jacobian.
E.2 Proof of Prop.
Proposition -ر DDA (Ia - A)/The inverse DGP's Jucobian J structurally equivalent to (I. A), when Assum. holds.
Proof. We start from the functional equation of the SEM and note that if X is the input of f (as Pa; from (1)), then the output is the same X (which deterministically depends on N):
X = (N) N) NX,
(25)
For given N) we can evaluate the Jacobian of f via the chain rule the key point is that since X is fix point of f, J will apprear on both sides (evaluated at the same point, expressed with the bar notation):
J Jzlx,N (X(N)
8f(X.N) ON
A
ax ON
X.N + B = AJ + BB
(26)
X.N
X.N
A 0
B
BFX,N)
(27)
OX
X.N
ON
X.N
The above equation can be reordered to yield the expression for Jy (note that A, B depend on X, N):
J J (Ia- -
(28)
Greseee et al. (2021) proposed IMA and showed that rules out spurious solutions; Buchholz al. (2022) proved identifiahility 14That is, Jy has orthogonal columns
28

---

Published in Transactions on Machine Learning Research (03/2023)
where A describes the x,-Xx X, edges in the DAG (i.e., A DDAG A), B is diagonal (as the X values are fixed). Since we reason about the Jacobian point-wise, we can invoke the inverse function theorem (by assumption, f is bijective) to express y 1:
J J -
(29)
Jy-INDAG (Lo-A) follows as ANDAC and B is diagonal (the invariance of <DAG follows from Def. 1()).
Alternative proof
Proof. The proof consists of two steps: 1) leveraging the iterative formulation of the SEM (2), proving that
JI-I~DAG(La- A) and 2) relying on the properties of DDAG and Lem. 1, showing J DDAG -
We start by formulating Jy (recall that x= x based on the iterative SEM expression (2):
af(x*=1_N)
J x UN
0x" xd-1, NN
X A d- ax
X + +B d-1
(30)
ON
aN
d-1 Ad11== x IN
Bd11
8f(x" IN)
(31)
8X
X
where A describes the X, edges in the DAG (i.e., A ~DAG A), B is diagonal (as the X values are fixed). Although both A, B are dependent from (superscript), unless f is lincar, they are independent when seen through the lens of structural equivalence. By Assum. A.1, it holds that A DAA A B ~AA B Vj. k. Thus, we will omit superscripts for both. Realizing that (30) gives recursive formula, and recalling that X 00, we can unroll (30) iteratively for d - 1,d 0.
J 0x ON
+ B DAG A
A
ox-2 ON +
B
+
B
DAG
A
A
8x UN
+B
+ B
+B
(32)
d-1 = Σ
(33)
1m0
where the structural equivalences follow by the structural faithfulness of Jy (Assum. A.1), the last equality expresses the sum of the geometric series with elements A' (the sum is finite is strictly lower triangular). By invoking the inverse function theorem (by assumption, f is bojective), we can express J y-1;
J 1 JJ ~DAG B (Ia A). Jy-1 HDAG (Ia follows as A DAG A and B is diagonal (the invariance of ~AA follows from Def. 1(1)).
(34)
F NLICA with Contrastive Learning
Assumption F.1 (Contrastive model on Rd). We assume that the model satisfies the following conditions:
(i) The encoder is defined as J X + N", where A" C IRd is a conver body (Isperrectangle))
(it The conditional distribution q (N associated with our model J through h J o is given by (NNN) (N)) " (((()),((N))/ with C2(N) := ( ((( dN, where C₂(N) is the partition function, >> 0 is scale parameter, and 8 is the semi-metric from Assum. 2. (ii) The encoder is trained with contrastive loss Leu using the same La metric å as in Assum. 2, i.e.,
exp
(x).f
(X) /T
(x,X, ) -log
1 exp -6 (F (X).
(35)
X
/T +
exp -8 (X
(X)
where X is the positive pair, X are the negative pairs, and M the number of negative pairs; (in) During training one has access to observations X, which are samples from these distributions transformed by the generator function (ie., the SFM) f-
29

---

Published in Transactions on Machine Learning Research (03/2023)
Are the distributional assumptions for contrastive NLICA testable for CD? The assumptions the conditional NNN and marginal p(N) distributions (Assum. 2) for contrastive NLICA might be deemed peculiar in the context of CL. First, we emphasize that since our results do not require the use of contrastive NLICA, the user free to chose a different method that guarantces strong identifiability. However, if contrastive NLICA deemed suitable for a Lask, then
1. they are neither interfering with assumptions in CD; and
2. they are testable e.g,, by a one-sample Kolmogorov-Smirrox lest (Kolmogorov, 1933; Smirnov, 1948).
What we mean by the first point (and elucidate in the next section) that to fulfill Assum. 2, we neither leave nor constrain the function class of f.
G Experimental details
Table 6: Hyperparameters for our experiments ($ 5)
PARAMETER
VALUES
6-LAYER MLP
ACTIVATION
LEAKY RELU
BATCH SIZE
6144
LEARNING RATE
1e-4
Rd
[0; 1]
Cp
My
0
Cparam
0.05
Mpprrm
1
p
(IN LCL)
1
a
0.5
Table 7: Results for sparse linear and nonlinear SEMs. Mean Correlation Coefficient (MCC) measures identifiability, [E*] the maximum number of edges in DAG, Ace accuracy, Ours our proposal, HSIC refers to using HSIC independence tests, and SHD is the Structural Hamming Distance
LINEAR
NONLINEAR Acc(Ours) Acc(HSSC) SHD
|8*1
MCC
Acc(Ours) Acc(HSTC) SHD
MCC
0.91720.108
0.7082p.11
0.111
0.889
0.75
0.111
15
5 0.961
00
0.768
0.784go.m
0.256
0.972
0.76
0.84
0.208
36
10.
40.04
0.711
0.322 100
0. 083 a 1o5
0.656+0.00 ozo 0. 708+
0.375=n.088
55
10
0.84
0.648 0.715+0.1
0.336+o.omm
0.734
0.61 2.618+oooo
0.69
0.37+0.082
30

---

Published in Transactions on Machine Learning Research (03/2023)
Table 8: Results for permuted (i.e., x is not the identity) linear and nonlinear SEMs. Mean Correlation Coefficient (MCC) measures identifiability, |E*| is the maximum number of odges in DAG, Ace accuracy, Ours is our proposal, HSIC refers to using HSIC independence tests, and SHD is the Structural Hamming Distance
LINEAR (Cc(HSIC) SHD
NONLINEAR Acc(Ours) Acc(HSTC) SHD
|8-
d
MCC Acc(Ours)
MCC
3
1.
0.667
0.667
15 5
1.98920.om
0.949 20.008
0.866=0.0s
0.051
0.988
0.94 0057
0.863
0.0620.087
36
0.837 252
0.834
0.62420.122
0.166 162
0.752
0.
0.687 20 139
0.
55
10
0.852
0.761 10. 0.578 0.239
0.794
0.573
0.
G.1 Code for the Sinkhorn operator
import torch from torch import nn as un
class Sinkhoradperatorr (objectt))
Based on attp://arxiv..rrg///
08665
def __init__ (self, num_steps: int):
if sum_steps raise ValueError (funmnu_ttpps") should be least 1")
self steps nun_steps
__call__ (self, matrix: torch. Tensor)
def _wwomallzeenneee (mataii (matrix: torch. Tensor) torch. Tensor: return matrix torch torch. logaumezp (matrix, 1, keepdim=True
def __nomallizeecol column (matrix: torch. Tensor) -> torch Tensor: return matrix torch logeunexp (matrix, 0, keepdim-True)
matrix
for in range (self num_steps)
8 __trmallie_coolll column (_ ror (8))
return torch (8)
Figure 10: Tororch code for implementing the Sinkhorn operator from (Mena et al., 2018). A Sinklhorn network applies SinkhornOperator to the scaled weight matrix W/T, where r is generally around 10
H
Notation
Acronyms
IMA Independent Mechanism Analysis
DAG Directed Acyclic Graph DGP Data Generating Process
ANM Additive Noise Model
CD Causal Discovery
L.id. independent and identically distributed ICA Independent Component Analysis
CdF Causal de Finetti
CL Contrastive Learning
ICM Independent Causal Mechanisms
31

---

Published in Transactions on Machine Learning Research (03/2023)
LiNGAM Linear Non-Gaussian Acyclic Model
ODE Ordinary Differential Equation
LSTM Long Short-Term Memory
SEM Structural Equation Model
MCC Mean Correlation Coefficient
SHD Structural Hamming Distance
MLP Multi-Layer Perceptron
SMS Sparse Mcchanism Shift
NLICA nonlinear Independent Component Analysis
TCL rana-iveer Learning
Nomenclature
L. regularizer for learning æ
Pa parent set of X
S Sinkhorn network
X observation vector
& edge set of a graph
A adjacency matrix of a SEMs
C loss function
connectivity matrix of SEMs
h composition encoder and decoder
structural assignment SEMs
d problem dimensionality
I index set.
N space of the noise variables X space of the effect variables causal ordering
Algebra
O scalar field
D diagonal matrix
DAG structural equivalence a component of f Contrastive Learning
Ia d-dimensional identity matrix
J Jacobian matrix permutation matrix
M number of negative samples
fcL contrastive loss function
Causality
N positive latent vector
N noise (independent) variable component
X positive observation vector
X observation component
X negative observation vector
N noise (independent) variable vector
temperature CCL
32


Reviews:
[{"review_id": "SQUwprPs3t", "reviewer": "Reviewer_2EU2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n### An interesting and clever idea\n- The combination of deep learning methods, such as continuous relaxation of the Birkhoff polytope and Nonlinear ICA, with the causal discovery is interesting.\n### A variety of employed simulations to test the claims\n### A well written and structured paper\n- The paper and especially the introductory overview and related work is well written and paints a comprehensive image of the current state of the field.\n\n## Weaknesses\n### The choice of the metrics for the accuracy measurement is harder to interpret\n- Why not use Precision Recall, or Omission and Comission of edges?\n### Unsupported efficiency claims\n- After the nonlinear ICA Jacobian is extracted, and possibly thresholded, the authors are left with an NP-complete problem of finding the topological ordering of a DAG adjacency matrix (see https://www.sciencedirect.com/science/article/abs/pii/S0020019016300552, for example). The proposed solution is to solved a relaxed problem via an SGD optimization. It is unclear how that is efficient and whether it is better than other approaches to the problem, such as SAT solvers and related engines.\n- The experiments are also not convincing. The largest number of variables is 10, which is not particularly indicative of the claimed scalability.\n- Moreover the most informative PR curve is only shown for one of the experiments and it is clear that as the number of variables grows the quality of the proposed estimation methodology is declining rapidly.\n### Lack of demonstration of robustness to assumption violations\n- What happens if the data generation process is not a DAG? For example, either some amount of autocorrelation is added to the system in a vein similar to the stepwise SEM generation or a longer cycle is introduced.\n- With small number of variables it may be feasible to set all weights in the SEM DGP or the MLP, however, as the model becomes larger, the relative weights of the interactions will necessarily become small. The same is true for the NLICA model as it gets larger. It is unclear how this will affect the proposed approach.\n### Insufficient efficiency demonstration \n- The paper lacks a run-time evaluation of the proposed approach, leaving the reader to assume that it may be slow based on the limited number of nodes in the simulations.\n### Missing relevant result\n- This is not strictly a weakness, but consider citing this relevant paper, that is also relying on the sparsity of the Jacobian to resolve unidentifiabilities in ICA: https://arxiv.org/abs/2206.07751", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes using the non-zero entries in the Jacobian of a nonlinear ICA model to uncover the causal relationships among the input variables, as represented by a directed acyclic graph (DAG). The DAG structure is inferred by training two Sinkhorn networks to generate two doubly stochastic matrices to permute the entries of the Jacobian into a lower triangular matrix. The Jacobian is extracted from a previously trained Nonlinear ICA. The work proves that if the data was indeed generated by a DAG related variables without common unobserved causes, and under the standard Markov and Faithfulness assumptions the graph is recoverable from non-zero entries of the Jacobian if the nonlinear ICA is strongly identifiable. The claimed advantage over the previously proposed two stage procedure of recovering the DAG from nonlinear ICA is improved computational complexity and thus scalability. An empirical evaluation on three different synthertic datasets is provided to support the claims.\n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## See the weaknesses\n## Minor\n- Consider citing the Sinkhorn networks paper before the first use of the idea in Algorithm 1. The fact, that you use this model to generate $S_{ICA}$ and $S_{\\pi}$ could have been mentioned on page 5, when these matrices are introduced. As it stands, Algorithm 1 is confusing, as the Sinkhorn networks appear out of nowhere - we were just calling $S_{ICA}$ and $S_{\\pi}$ doubly stochastic matrices and now they turned into networks.\n- In Algorithm 1 $K=|S_{ICA} \\dots |$ - should not the second $S$ be $S_{\\pi}$?\n- You may want to check your references to arxiv. For example, on page 1 you cite Zhang et al., 2015 linking to arxiv, but the paper has been published in a peer-reviewed venue.\n- It is unclear what \"General Nonlinear Functions\" in the title refers to. The causal process over the causal DAG? But there's no support for the generality in the paper in this case. If this refers to the nonlinear ICA model, then why is it relevant in the title? In general, the title is unclear.\n ", "broader_impact_concerns": "no concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "sY1N7hjyRZ", "reviewer": "Reviewer_qviF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n- The writing is especially clear and well-organized. \n- The introduction of the background is very detailed and helpful.\n- Related works are summarized comprehensively and precisely. Table 4 is so beautiful.\n- The considered problem, i.e., multivariable causal discovery with general nonlinear function, is very important both theoretically and practically.\n\n**Weaknesses:**\n\nAlthough I appreciate the presentation of the results, there exist some nontrivial problems that need to be addressed:\n\n(1) The difference between the proposed theoretical results and those in lingam [1] appears to be not significant.\n* The main idea of Lemma 1 in this manuscript is almost the same as Appendix A in the lingam paper [1].  Both use the assumption of DAG structure (i.e., lower-triangular matrix) to resolve the permutation indeterminacy of ICA. The only difference in the proof is that, in this manuscript, the linear mixing function is replaced by the Jacobian of the nonlinear mixing function, which has been widely applied in previous works, such as [2].\n * Proposition 1 in this manuscript is directly based on the formulations of ICA and Causal Discovery (SEMs). Similarly, it seems that the major novelty also comes from the usage of the Jacobian for the nonlinear mixing function.\nAlthough the connection between the proposed method and lingam has been clearly stated in this manuscript, the difference between them does not seem to be significant enough, especially when the major difference (i.e., the usage of Jacobian) has already been proposed before.\n\n(2) It is not clear whether the assumptions for the identifiability of nonlinear ICA are testable in causal discovery. Because SEM is a special case of ICA with additional assumptions like faithfulness and DAG, the connection between the formulations of ICA and SEM is rather straightforward. Thus, the most important challenge is to justify that the assumptions on the ICA side are testable after being transferred to the setting of causal discovery, which has not been addressed in the current manuscript:\n* The strong identifiability of the nonlinear ICA has been directly assumed without further discussion on the required assumptions. Actually, those assumptions may not make sense in causal discovery without appropriate justification. For example, in order for the mixing function to be identifiable, assumption E.1 is required and it includes various constraints, such as the marginal distribution of the noises needs to be uniform. These assumptions may not be reasonable in the context of causal discovery. Additional discussions are necessary for the required assumptions.\n* As mentioned by the author, the proposed method works with any nonlinear ICA method as long as the identifiability of the ICA model can be guaranteed. However, the connections between ICA and SEM require certain transformations, which makes the justification of the assumptions transferred from one task to another especially difficult. As mentioned in the manuscript, the connection between ICA and causal discovery is based on the structural equivalence between $J_{f^{-1}}$ and $I-A$, where $f$ is the mixing function of ICA and $A$ is the adjacency matrix of the causal graph. Then the assumptions of ICA (e.g., those on the mixing functions) may not make sense after taking these transformations (e.g., the inverse operation). \n\nTherefore, in order to support the theoretical claims of this manuscript, one needs to show that the assumptions are testable in the context of causal discovery. The assumptions for the identifiability of the nonlinear ICA are the most important part of the considered problem and should be emphasized in the manuscript. Assuming the identifiability of nonlinear ICA directly may oversimplify the problem.\n\n---\n\n[1] Shimizu, S., Hoyer, P. O., Hyvärinen, A., Kerminen, A., & Jordan, M. (2006). A linear non-Gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10).\n\n[2] Gresele, L., Von Kügelgen, J., Stimper, V., Schölkopf, B., & Besserve, M. (2021). Independent mechanism analysis, a new concept?. Advances in neural information processing systems, 34, 28233-28248.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript proposes a causal discovery method for general nonlinear function, which is based on nonlinear ICA. The theoretical results are based on the assumption that the identifiability of nonlinear ICA has been given. Compared to the previous work, in my perspective, the major contribution lies in the usage of the Jacobian to represent the sparsity structure in the nonlinear case. As described in detail below, it is less clear to me whether the contribution is significant enough. Besides, there exist some fundamental challenges that have not been addressed in the current manuscript.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Points 1 and 2 in the list of weaknesses, especially 2, are my biggest concerns. I would like to recommend it for acceptance if these can be appropriately clarified/addressed.", "broader_impact_concerns": "No concerns on the ethical implications", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "pmWev7Mm7Y", "reviewer": "Reviewer_Skoz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths:\n- The paper studies the connection of nonlinear ICA and causal discovery, which is an interesting and important direction.\n-  This paper is well written.\n-  The proposed estimation method is reasonable.\n\n## Weaknesses:\n-  As mentioned by the authors, the main contributions, i.e., Lem. 1 and Prop. 1, are direct extensions of theorems in LiNGAM. However, it seems that the theoretical difference is not surprising and has been proposed in several previous works. Specifically, Lem. 1 removes the permutation indeterminacy of ICA via the DAG constraint of the causal graph; Prop. 1 is directly based on the standard formulation of structural equation models. Thus, the only difference appears to be the generalization from the linear mixing function (matrix) to the Jacobian of the nonlinear mixing function, which has been widely applied in previous methods as discussed in this manuscript.\n- Based on point (1), the key theoretical challenge of building the connection between ICA and causal discovery in the general nonlinear setting lies in the identifiability of nonlinear ICA, especially, in how to make sense of the assumption needed in nonlinear ICA in the setting of causal discovery. In this manuscript, contrastive NLICA is applied for the identification of the mixing function. For it to be identifiable, it is assumed that the ground-truth noises follow a uniform distribution and the conditional distribution is a Laplace (Assum. E.1). Without further justification, the reasonableness of these distributional assumptions may not be convincing in the context of causal discovery.  Even if we apply other methods in nonlinear ICA with identifiability guarantees, the transfer of their assumptions is nontrivial. For example, according to the manuscript, one needs to start from the Jacobian of the inverse of the mixing function to build the connection, where the assumptions on the sources or mixing function are likely to be untestable after the inverse operation or others.\n\nTherefore, I hold the opinion that the current manuscript lacks an important part of the work on the consistency/transferability of the required assumptions in both ICA and causal discovery and the justification for it. Assuming strong identifiability of nonlinear ICA without sufficient attention to the assumptions may oversimplify the problem and make it a rather direct extension of LiNGAM. Since causal discovery is a special case of ICA, the challenge of nonlinear ICA does not lie in the connection between the formulas of them but in the appropriate assumptions for the identifiability of nonlinear ICA, specifically, transferring the assumptions from ICA to those in causal discovery, or proposing testable assumptions on SEMs, which has not been well solved in the current manuscript.\n\n## Other comments:\n- The term \"general nonlinear functions\" in title, abstract, and other sections could be potentially misleading. As Section 2 mentioned, the identifiability result of nonlinear ICA relies on (1) auxiliary variables, or (2) restricting the nonlinear functions (i.e., with no auxiliary variables). As far as I know, results relying on auxiliary variables can have more \"general\" nonlinear functions (e.g. Hyvärinen et al. (2019)), while results without auxiliary variables tend to have somewhat restrictive conditions on the nonlinear functions (e.g. https://arxiv.org/abs/2208.06406, https://arxiv.org/abs/2206.10044, https://arxiv.org/abs/2206.07751). If the authors intend to focus on auxiliary variables (e.g. domain/environment index), I would suggest emphasizing auxiliary variables (or non-i.i.d. data) in the title and throughout the paper (because this is quite different from standard nonlinear causal discovery setup assuming i.i.d. data). If the authors intend to focus on the case without auxiliary variables, then using \"general nonlinear functions\" is not accurate. If the authors do not intend to focus on either case, then possibly \"Multivariable Causal Discovery with Nonlinear ICA\" could be an option, and also not focusing on \"general nonlinear functions\" throughout the paper.\n- What is the definition of accuracy for causal discovery? (SHD seems to be more widely used.)\n- Experiments without knowing causal ordering are more realistic in practice. Therefore, SHD should be included in Table 1.\n- The experiment section should include more causal discovery baselines that can handle nonlinear functions, e.g., PC, GES, or continuous optimization based methods.\n- Since various parts such as introduction claimed that scalability is improved, experiments on larger number of variables should be included. Currently the experiment section only considers 10 variables at most.\n- Assumption E.1: What is $\\tilde{N}$?\n- Abstract mentioned about the assumption of non-i.i.d. data but is not elaborated throughout the paper.\n- Footnote of Page 2: I think the authors intended to cite Lorch et al. (2022).\n- The method used Sinkhorn networks to account for permutation. This has been proposed by https://arxiv.org/abs/2203.08509 and should be referenced.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the use of nonlinear ICA for multivariate causal discovery. The authors prove that under strong identifiability, the Jacobian of inference function captures the sparsity structure of the causal graph. This generalizes the classic LiNGAM method for causal discovery to the nonlinear case. Experiment results on synthetic datasets are given which show that the proposed method outperforms previous methods.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The detailed comments are provided above. In my opinion, several key points are:\n- Transfer the required assumptions for identifiability result of nonlinear ICA used in the paper to the causal discovery setting and provide justification on why those assumptions make sense in causal discovery setting. Also provide intuition on how to interpret them.\n- The use of \"general nonlinear functions\" could be potentially misleading. See detailed comment above.\n-  Since various parts such as introduction claimed that scalability is improved, experiments on larger number of variables should be included.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "i4dsyst9EB", "reviewer": "Reviewer_Tqxy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe relation between the Jacobian and causal structure and the proposed estimation algorithm would be new knowledge. Especially the relation of the Jacobian with the causal structure would be interesting to readers since it generalizes many existing major methods, including Shimizu et al. (2006), Hoyer et al. (2008), and Monti et al., 2019, etc.\n\nOverall, the literature review is well-written. \n\nWeaknesses:\n\nSeveral points on the theoretical results were not very clear, as stated below in the requested changes. This makes it a bit difficult to see the technical correctness.\n\nSome references need to be examined since the reasons for citing them are not very clear or there seems better references.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work considers inferring causal graphs of nonlinear structural causal models of observed variables from non-interventional data under the assumptions including acyclicity and causal sufficiency. \n\nIt assumes that the causal graph is identifiable, more specifically, it assumes identifiability conditions provided by existing works including Monti et al. (2019), Shimizu et al. (2006), and Hoyer et al. (2008), Peters et al. (2011). \n\nThen, they propose to estimate the causal graph of such a model using the Jacobian of inverse of the functional assignment f (Inference model). The idea generalizes the linear cases of Shimizu et al. (2006) to nonlinear cases. Shimizu et al. (2006) relates the zero/non-zero pattern of the ICA (Independent Component Analysis) mixing matrix to the existence/non-existence of causal paths. This submission relates the zero/non-zero pattern of the Jacobian to that. \n\nFurther, they propose an estimation algorithm generalizing the ICA-based method by Shimizu et al. (2006), i.e., first perform (nonlinear) ICA and second resolve the permutation indeterminacy. They evaluated their claims using simulation experiments.\n\nThe relation between the Jacobian and causal structure and the proposed estimation algorithm (especially the algorithm for solving the permutation indeterminacy) would be new knowledge.\n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical\n\n1. Their model should be more clearly described. \n\nThis work says in several places that it assumes the strong identifiability conditions of  Theorem 6 of Zimmermann et al. (2021).  However, Zimmermann et al. (2021) do not directly consider causal models. It should rephrase the conditions using the notations of Eq. (1). I also find some other assumptions in the first ten lines of page 2 and Appendix A. I think those assumptions need to be put together when describing the model considered in Eq. (1). \n\nIt is not clear how those assumptions are combined, e.g., assumptions of Zimmermann et al. (2021), bijective functions and faithfulness etc. Possibly, it might happen that some assumptions contradict each other, but it's not very clear since assumptions appear at different places. \n\nFurther, the abstract says that it uses non. i.i.d. data, but I could not find where it is described in Eq.(1). The assumptions should be structured in a better way so that readers easily understand what assumptions this proposal needs.\n\n2. Proposition 1: is strongly identified (Khemakhem et al. 2020b. Def.1)\n\nDef. 1 of the paper (Khemakhem et al. 2020b) defines weak identifiability. So, this might be a typo. Further, I would like this submission to have the definition in the paper, not simply citing the paper. Then, this work is more self-contained and it would make it easier for reviewers to see if it is technically correct. Similarly to a previous comment, the condition should be rephrased in their model in Eq. (1). Khemakhem et al. 2020b does not consider causal models directly. \n\n3. This work claims their proposal works for GENERAL nonlinear functions. However, they also need to make assumptions to make the model identifiable. More discussions on to what extent nonlinear functions satisfy all their assumptions are general would be necessary. This comment is also related to the two comments above.\n \n4. It is not clear if their estimation method is consistent. Does the method find the right answer when the sample size goes to infinity? It would be better to clarify whether it is consistent in theory or it is not yet theoretically clear and is implied by simulation experiments.\n\n5. Propositioin 1 in 3.4 (Main result) should have all the assumptions in the statement. Currently, the model assumptions are not clearly stated there.\n\n6. Section 3.5 does not say how the Jacobian is computed or extracted. It should be given explicitly, though it might depend on estimation methods.\n\n7. The definition of the Jacobian J_f^{-1} seems missing, though I could guess.\n\nTo strengthen the work\n\n1. Introduction: In contrast, causal models (Pearl, 2009) construct the world according to the Independent Causal Mechanism (ICM) principle. \n\nI’m not sure if Pearl (2009) claims to use the principle. It would be better to specify on which page it says that. Well, maybe, this is a claim by Peters et al. (2017). If so, it would be better to clarify it.\n\n2. Introduction: On the data side, assumptions include non-stationarity (Scholkopf et al., 2012)\n\nI could not find whether Scholkopf et al. (2012) uses non-stationarity for constraining models. It would be better to clarify which page or paragraph it uses non-stationarity as constraint.\n\n3. Lemma 1.: f describes a DAG\n\nI think the meaning of the word “describe” needs to be mathematically explained at some place (Sorry if I missed it!), though I could tell to some extent.\n\n4. Just above Eq. (1): their causal relationship is given by d deterministic functional assignments (Peters et al., 2017)\n\n Peters et al., 2017 would be better to be replaced by Pearl (2009b). I see that Peters et al. (2017) is a textbook, but it would be better to cite more original books like Pearl (2009b).\n\n5. The definitions of  alpha_d, alpha_u, alpha_l in Eq.(5) seem missing.\n\n6. The definition of L_CL in Algorithm 1 seems missing, though I could tell to some extent.\n\n7. It would be better to explain what is a Sinkhorn network.\n\n8. Caption of Table 1: \"paermutation\" should be \"permutation\".\n\n9. Appendix. B: I wonder if Zheng et al., 2018 assumes noise variables are equal as well?", "broader_impact_concerns": "I don’t think this work is related to ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a nicely written work that develops a novel use of the Jacobian of the inference network for causal discovery.

The reviewers have concerns about the impact of this work, as the current paper (with emphasis on contrastive NLICA, at least in the paper's current form) struggles with the above-mentioned identifiability assumptions for contrastive NLICA. Also, the authors do not focus on other forms of NLICA, so despite their mentioning that this work need not be restricted to contrastive NLICA, the audience is not left with an alternative. The impact (and also significance) would be greater depending on how identifiability results for contrastive NLICA can be extended in the future; while expected impact is not a criterion for acceptance, significance of results certainly is.

Despite concerns regarding assumptions (which also affects significance), I believe the positives carry enough weight where this work is worthy of publication. The use of the Jacobian of the inference model in particular is novel. I am willing to give the authors the benefit of the doubt on the point of the identifiability assumptions and hope that there will be more discussion about this point going forward. I strongly suggest that the authors read the reviews again and so as to better respond to the criticisms of Reviewers Skoz and qviF. To quote one reviewer’s comment to me:
>  “it is important to demonstrate that the identifiability assumptions made by the particular nonlinear ICA method (chosen by the authors) can be well justified/interpreted in the causal discovery setting”.

And paraphrasing a second point from another comment:
> While the authors assume independence and invertibility, it is well-known that nonlinear ICA is not identifiable without additional assumptions. Hence, more discussion of additional assumptions should be included, and these assumptions should be motivated in the causal discovery setting.

This is an acceptance with a minor revision. I request the authors revise their discussion to better address the above two points; one possibility is to focus on a nonlinear ICA method other than contrastive nonlinear ICA (I am not asking you to do experiments with such a method) in this discussion, if that makes things easier for you, and given that minor revision, I welcome the acceptance of this paper.
Decision: Accept (poster)