Causal de Finetti: On the Identification of Invariant Causal Structure in Exchangeable Data
Authors: Siyuan Guo
Viktor Tóth
Bernhard Schölkopf
Ferenc Huszár
Venue: NeurIPS 2023 poster (2023)
Keywords: Independent Causal Mechanism
Causal Discovery
Exchangeable
Bayesian Statistics

Abstract: Constraint-based causal discovery methods leverage conditional independence tests to infer causal relationships in a wide variety of applications. Just as the majority of machine learning methods, existing work focuses on studying $\textit{independent and identically distributed}$ data. However, it is known that even with infinite $i.i.d.\$ data, constraint-based methods can only identify causal structures up to broad Markov equivalence classes, posing a fundamental limitation for causal discovery. In this work, we observe that exchangeable data contains richer conditional independence structure than $i.i.d.\$ data, and show how the richer structure can be leveraged for causal discovery. We first present causal de Finetti theorems, which state that exchangeable distributions with certain non-trivial conditional independences can always be represented as $\textit{independent causal mechanism (ICM)}$ generative processes. We then present our main identifiability theorem, which shows that given data from an ICM generative process, its unique causal structure can be identified through performing conditional independence tests. We finally develop a causal discovery algorithm and demonstrate its applicability to inferring causal relationships from multi-environment data.

Causal de Finetti: On the Identification of Invariant Causal Structure in Exchangeable Data
Siyuan Guo 12+
Viktor Tóth !+ Bernhard Schölkopf Ferenc Huszár'
University of Cambridge Max Planck Institute for Intelligent Systems 1 f227fh2220aa @cam. ac. uk toth. 740xtor74000gmai..cmmm com
bs@tuebingen mmg.
Abstract
Constraint-based causal discovery methods leverage conditional independence tests infer causal relationships in wide variety of applications. Just as the majority of machine learning methods, existing work focuses on studying independent and identically distributed data. However, it known that even with infinite i.i.d. data, constraint- baased methods can only identify causal structures up to broad Markov equivalence classes, posing a fundamental limitation for causal discovery. In this work, we observe that exchangeable data contains richer conditional independence structure than i.i.d. data, and show how the richer structure can be leveraged for causal discovery. We first present causal de Finetti theorems, which state that exchangeable distributions with certain non-trivial conditional independences can always be represented as independent causal mechanism (ICM) generative processes. We then present our main identifiability theorem, which shows that given data from an ICM generative process, its unique causal structure can be identified through performing conditional independence tests. We finally develop causal discovery algorithm and demonstrate its applicability inferring causal relationships from multi-environment data. Our code and models are publicly available at: https::/ htt::/gittti github. com/ woonm//ggo96//aaaaa (atgguooo//auaa-deee de- -e-uusttleeFieettii
Introduction
Learning causal structure from observational data is key step towards causally robust predictions in machine learning. Most existing causal discovery theory (Pearl, 2009) focuses the study of independent and identically distributed (i. d.) data. Indeed, a majority of practical methods (Chickering, 2002; Spirtes al., 2000a.b) based on i.i.d. data only allows to determine causal structure up to broad equivalence classes, and going beyond that is known to be impossible without further constraints (Pearl, 2009). For example, the basic task of identifying a bivariate cause-effect relationship (i.e. X causes Y or Y causes X) on i.i.d. data is known to be impossible. Current methods impose additional restrictions, e.g., linearity assumptions (Hoyer et al., 2012; Shimizu et al., 2006, 201 I) or assumptions about the additive nature of noise (Hoyer et al., 2008a; Peters et al., 2014; Zhang and Hyvärinen, 2009) ensure identification.
more recent line of work relaxes the i.i.d. assumption and considers inferring causal structure from grouped multi-environment data (Arjovsky al., 2019; Heinze-Deml et al., 2018: Huang et al., 2020: Peters and Meinshausen, 2016; Rojas-Carulla et al., 2018; Tian and Pearl, 2001). Our key observation that studying grouped data is akin relaxing the assumption on the data generating process from i..dd to exchangeable. In this work, we study causal structure learning in exchangeable data and show unique causal structure identification is enabled by the richer conditional independence structure of exchangcable processes.
Equal contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

ICM-generative Pooees
de Finetti
Causal de Finetti
X Y
X1
Y1
X1
Y1
0, R/3
i
?
X
X
Y2
X2
Y2
(b)
Figure I: (a) is an illustration showing how i.idd data and certain exchangeable data differ in identify- ing the correct causal structure for bivariate model. Each quadrant represents a causal structure, X L.Y, X Y. Y. + Y. The inner circle represents i.id. regime and the outer circle represents certain exchangeable regime. Under i.idd data, one can only identify X Y, whereas certain exchangeable data (i.e., ICM-generative processes) enables one to identify unique causal structures. (b) illustrates differentiating factor between de Finetti and causal de Finetti's ' representation on exchangeable data. Causal de Finetti disentangles the latents and substantiates causal mechanisms independent in the sense latent parameters governing each mechanisms are statistically independent.
Several works in multi-environment data implicitly leverage the independent causal mechanism (ICM) assumption (Aldrich, 1989; Janzing and Schölkopf, 2010; Pearl, 2009), which postulates that causal mechanisms of the true underlying generating process do not inform or influence one another. Despite having been widely applied (Brehmer et al., 2022; Goyal et al., 2019; Madan et al., 2021; Parascandolo al., 2018 8), the ICM assumption is rarely stated any more formally than above, and thus lacks a statis- tical formalization. It also unknown what the fundamental limitations inferring causal structure under the ICM assumptions are. Our work makes three contributions to clarify these questions:
Causal de Finetti theorems ($ 3) provide mathematical justification for the independent causal mechanism (ICM) assumption data generating processes. states that any exchangeable process generative
satisfying certain set of conditional independence properties can be represented process in which factors Markov factorization are statistically independent. We show how causal de Finetti substantiates the ICM principle and call such models ICM- processes.
Our main identifiability theorem ($ 4), informally stated, shows that if data is sampled from an ICM generative process, the causal graph is uniquely identifiable by testing conditional independence relationships.
Causal discovery multi-envvronment data: Section connects the identifiability theorem for ICM generative models to the analysis of multi-environment data. This section establishes that multi-environment data can viewed as observing finite marginals i.i.d. copies of an exchangeable process. This then allows us develop algorithm for recovering causal structure from data coming from a sufficient number of environments.
Our work thus provides strong probabilistic justification for approaches based on the independent causal mechanisms assumption and algorithms that require non-i.i.d. grouped data. We review the use of exchangeability in Section 7. In Section 6, we present experiments that validate our approach to inferring causal structure from multi-environment data using conditional independence testing. Fig. summarizes the main contributions of the paper and Fig. illustrates differences between data generated by causal graph under i..d. process and -CM-generative process.
causality and approaches for causal structure learning in grouped data
Preliminaries
2.1
The Causal Framework
joint distribution P(XI,..., Xx) over set of variables XI,..., Xx can decomposed into simpler components in multiple ways. For example, by the chain rule of probability, factorize

---

(a): i.i.d. process
X
Y
X1
Y1
X1
Y1
2/5
0
//
X
Y2
X2
Y2
X
2
(b): exchangeable process
(c)
(d)
Figure 2: An illustration demonstrates different conditional independence relationships contained in ii.d. process and MeM-geerrative process. (a): A causal graph generated under an i.i.d. process; (b): causal graph generated under ICM-generative process; Unrolling the inner plate notation from (b), we visualize the process with two samples. Causal graphs X + Y and Y + X generated under an i..dd process share the same conditional independences (0) and thus observationally equivalent.
(c) and (d) show the corresponding graphs under (CM-generatio processes. (c) has X1 L Y2 X2 which does hold in (d) and (d) has X] Y2 Yi which does not hold in (c). One can thus differentiate the bivariate causal direction in ICM-generative processes.
the joint as P(X XN) = I1 P(X, .......,,..). We say the joint distribution satisfies the Markov factorization property with respect directed acyclic graph G if
N = II P(2 PA.).
P(X (N)
i=1
where PA; are the direct parents of node X; in G. While many factorisations can represent the same joint P, a specific one is called the causal Markov factorization: in it, the factors P(X, PA.) represent the causal mechanisms of the true underlying data generating process. One can use the causal factorization to predict effects of interventions, which model mathematically by replacing the corresponding factor (Pearl, 2009).
Causal discovery aims at recovering the causal graph G and the corresponding causal Markov factorization from the joint distribution This can be done by matching the conditional independence structure implied by the graph G to those observable in the joint distribution P. To facilitate this matching, an elaborate graphical terminology has been developed, as detailed in Appendix A. Unfortunately, under the assumption that data is sampled i.i.d. from P, the true underlying G cannot be uniquely determined, only up to broad equivalence classes. The conditional independence structure of i.i.d. processes is not rich enough to facilitate identifiability of the causal structure G.
Independence of Causal Mechanisms, Causal and Anti-Causal Machine Learning addition to the study of Markov factorization, recent work (Janzing and Schölkopf, 2010) studies the behaviour of causal mechanisms and postulates the Independent Causal Mechanism (ICM) principle, which states:
Causal mechanisms are independent of each other in the sense that a change in one mechanism P(X; PA.) does not inform or influence any of the other mechanisms P(X, PA,). for i + j.
The notion of invariant, independent and autonomous mechanisms have long history in causality research: Haavelmo (1944) and Aldrich (1989) discuss the historical development of autonomous mechanisms in economics and Pearl (2009) also argues that causal mechanisms are modular in nature. Schölkopf et al. (2012) pointed out the implications of this principle when using machine learning techniques in causal or anti-causal learning settings, e., when the task is predict an effect from a cause or cause from an effect, respectively. The ICM principle implies that semi-supervised learning is only successful in the anti-causal direction, while the predictor can be robustly applied to new domains if learning is in the causal direction. While these observations seem intuitively true, it is difficult to ground their meaning in the langauge probability information. As we will see, these difficulties can be resolved once consider non-i.i.d data generating processes.

---

2.2 Exchangeability
As we have seen, i..dd processes have a limitation that their conditional independence structure not rich enough to support identifiability of the full causal graph. We thus turn our attention to richer class of processes, exchangeable sequences.
Definition 1 (Exchangeable sequence). A finite sequence of random variables 11, X2,...... ................................ Xx is exchangeable, for any permutation π of its indices N.....,N::
(Tx())"..,,<(( = P(X1,...... XN)
An infinite exchangeable sequence is a sequence where for any N N, its fiite sequence of length N is exchangeable.
Exchangeability is notion of symmetry. Definition informally states the order of observations does not matter. Recall a finite sequence of random variables independent and identically distributed its joint distribution satisfies P(X1..... : Xx) - P(X,). Of course, such an i.idd sequence is automatically exchangeable but not all exchangeable sequences are i.i.d. To clarify the connection between exchangeable and i.i.d. sequences, recall the de Finetti theorem:
(De Finetti's representation theorem (de Finetti, 1931)). Let (Xa)neN be an infinite sequence of binary" random variables. The sequence is exchangeable if and only if there exists a random variable 0 E [0, 1] such that X1, X2,.. are conditionally independent and identically distributed given 0, with a probability measure a on 0. Mathematically speaking, given any sequence (X1, XN) E 1)%
Theorem 1
N
/ II p(x: 0)d
P(x ....
Informally, the theorem states that an exchangeable sequence can always be represented as a mixture of i.i.d. sequences. De Finetti's representation theorem has important consequences for Bayesian inference. Bayesian statistics, unlike frequentist, takes the view that the parameter is latent variable, instead of an unknown point estimate. Bayes' theorem estimates the parameter via calculating poste- rior density [(f]x x.). De Finetti's representation theorem demonstrates (O'Neill, 2009) that rather than metaphysical belief about the true model, it is due to our judgement that the observations are exchangeable that underlies our standard use Bayesian modelling involving observations are i..d. conditioned some unknown latent variable.
3 Causal de Finetti Theorems
Just as de Finetti justifies Bayesian modelling, we will introduce causal de Finetti theorems that justify causal modelling via probability theory. We first motivate our study of exchangeable sequences by noting that they have richer conditional dependence structure than i.i.d. sequences. We illustrate what this means concretely in the simplest possible case of pair of variables.
Let X denote a random variable and x denote a random variable's 's particular realization. Let [n]] denotes the set of positive integers that are less than or equal to n, i.c. [n|] {1....,n).
Definition 2 (Exchangeable pairs). An infinite sequence of random variable pairs (Xn, Yn)neN is exchangeable if for any permutation π and for any finite number N, it satisfies
P(X+(1);
Y=(N)) P(X,, ......,,N.... YN)
(4)
In an i.idd sequence over pairs, the only non-trivial independence is X, T Y.. Since the distribution is identical, it either holds for all or does not hold for all i. In exchangeable sequence of pairs, one can consider other non-trivial independence, for example, Y, 1 X, X₁. This conditional inde- pendence relationship trivially holds in i.i.d. sequences, but it may may not hold in exchangeable sequences. Therefore, one can hope its absence or presence carries some useful information about some underlying causal structure. Here, we present the causal de Finetti theorems, which illustrate the type of causal structure this conditional independence relationship implies.
De Finetti's 's representation theorem has been extended to categorical and continuous variables (Klenke,
2008).

---

Theorem 2 (Causal de Finetti - bivariate). Let {(Xn, InNN be an infinite sequence of binary random variable pairs. The sequence is:
1. infinitely exchangeable, and satisfies
2. Vn E N: Ypn] Xn+1 [(x]
if and only if there exist two random variables O E [0. 1] and ab E [0, 1]² with probability measures p. such that the joint probability can be represented as
N / II ==1
P(11, V1. IN. MN)
plun In. p)) ()dp(()dz((4))
(5)
Informally, the theorem states that an exchangeable sequence of random variable pairs satisfying an additional set of conditional independence properties, can always be represented as mixture of i.i.d. sequences which all share the same underlying Markov factorization structure, and thus, an invariant causal structure. In fact, such exchangeable data can be interpreted as data generated under the ICM assumption. Recall the independent causal mechanism is loosely denoted as [eftecttccasse 1 Peumse" ICM assumption can be modelled by Eq. 5 in the sense that causal mechanisms are characterized by latent variables: mechanisms do not influence each other if one can separately manipulate each latent variable controlling different mechanisms; further, latent variables governing each mechanism statistically independent with each other, supporting mechanisms do not inform one another. We thus call the generative process in Eq. 5 as ICM-generative process. Causal de Finetti, just as how de Finetti substantiates Bayesian modelling, demonstrates that rather than metaphysicss belief about independent causal mechanisms, is due to our judgement that observations are exchangeable and the sufficiency to predict the target variable Y with the corresponding X values irrespective of other X observations underlie our standard use of causal modelling. We thus substantiate ICM by detailing the statistical assumptions one implicitly make when assuming ICM.
As an example, consider the causal graph on the right. Imagine in a hospital there are patients. A patient's 's symptom is the cause of doctor's ss diagnosis. Suppose we are interested to predict patient's 's diagnosis given her symptom. The conditional independence says knowing another patient's symptom will not help us to predict the diagnosis of this patient if we know this patient's ss symptoms already. The conditional independence thus formulated the intuition behind causal and anti-causal problem in the language of probability: the distribution of the cause, other patients' symptoms in this case, will not help prediction about the effect given cause, i.e., one patient's 's diagnosis given his own symptoms.
Patienti
Diagnosis;
Hospital
Doctor
Patientu
Diagnosis:
Causal de Finetti vs. de Finetti To see the difference between causal de Finetti and de Finetti's s
representation theorem, we observe that a direct application of de Finetti theorem on exchangeable data that may or may not contain causal information results in factorization as:
/
N II p(u., xn 10) n=1
P(11. B1 UNN
(6)
As observations are conditionally i..dd given latent variable 0, learning 0 is thus sufficient to achieve maximum prediction power. This finding corroborates empirical results in the machine learning community, where training often produces an entangled representation that achieves strong pre- diction accuracy. However, with the fast development of powerful machine learning applications (Brown et al., 2020), both deep learning and causal communities advocate the need for disentangled representations (Bengio et al., 2013; Locatello et al., 2019; Schölkopf et al., 2021), which offer greater control, interpretability, and generalization capabilities. Causal de Finetti shows that, in fact, given exchangeable data satisfying the causal and anti-causal learning phenomenon formulated in conditional independences, there statistically independent latent variables controlling each causal mechanism. It shows one can achieve both maximum prediction power and disentangled representations. Fig. lb illustrates visualization of the differences between de Finetti and causal de Finetti theorems.
We next illustrate causal de Finetti in the general multivariate form (see Appendix B for proof):
5

---

Definition 3 (Exchangeable arrays). An array of size d contains variables (X....... .d:n) where Xam denotes the d-th random variable n-th array. Such an array is denoted as X.ge finite sequence of size d arrays is exchangeable, if
P(X==(1) ((((N)) = P(......... X²N)
(7)
Theorem 3 (Causal de Finetti multivariate). Let {(X1m X2ms Xdm))en be an infinite se- quence of d-tuple binary random variables. The sequence is
1. infinitely exchangeable, and
2. if there exists a DAG such that Vi E [d], Vn E N:
X=(m]] 1 LNDaj) B.Di ND (D PA.(()
where PA; selects parents of node and ND; selects non-descendants of node i in G. ND; denotes the set of non-descendonts of node excluding own parents.
if and only if there exist d random variables where 0g E [0, 1|2 with suitable probability measures {ur} such that the joint probability can be written as
N d
P(x.IIN)= = / 1III x=11=1
p(aan pa (01) (O.))(Oa),
(8)
where X.I:NN == [(I1:))....... Iddn)
Theorem 2 is special case of Theorem when 2. Informally, it states that an exchangeable sequence of size d random arrays satisfying an additional set of conditional independence properties with respect DAG, can always be represented same underlying Markov factorization structure as the corresponding DAG. The set of conditional independence properties in condition can be interpreted via decomposition:
mixture of i.i.d. sequences which all share the
X IL s:j]l
PAg[a]
This shows that the direct parents of one node form a Markov blanket for its other non-descendant nodes. other words, to infer about the variable of interest, sufficient to know the variable's direct parents irrespective of other non-descendants.
[ijm] 1 ND PA..[r]
This conditional independence is another example that exchangeable data has richer conditional independence structure. trivially holds in i.i.d. sequences but may or may not hold in exchangeable data. Informally, it states that infer the variable of interest, is sufficient to know its corresponding parents irrespective of non- dessenncensssss in other observations. This formulated the intuition behind the causal and anti-causal problem in the language of probability: the distribution of the variables in the causal direction, in this case, non-descendants in other observations will not help prediction if covariates contain a complete set of the corresponding direct causal parents.
To illustrate how Theorem 3 also justifies the ICM in action, consider the causal graph the right. Imagine high schools host campaigns to advertise university opportunities and encourage students to apply. Students' decision apply the cause of their university admission outcomes. Suppose we are interested in understanding how influ- ential school campaigns are on students' decision apply, i.c., the mechanism of AAppyy Campaign". We expect that knowing par- ticular student's decision to apply after attending a school campaign will not be influenced by the other school campaigns the student did not attend; instead, knowing other students' decisions apply after their attendance in campaigns will help the prediction of this particular student's 's decision to apply. Similarly, knowing other students' university admission outcomes will also be helpful. This because more students decide to apply implies the effectiveness of school campaigns, and more university admission acceptance implies more students decide to apply. Causal de Finetti says given such assumptions and exchangeable data, it naturally holds that there exist latent variables, represented by high school, student and university, and they are independent.
Campaign:
Apply:
Admission:
School
Student
Uni
Campaigna
Applyz
Admissiona

---

Extension beyond binary Above theorems are presented in its bivariate and multivariate forms for binary variables. In general. it is easy extend the results to categorical variables' Just as the progression of the proofs for de Finetti's theorem, we hypothesize causal de Finetti holds true for continuous variables. Here we state the theorem in its multivariate form for categorical variables.
Theorem 4 (Causal de Finetti multivariate and categorical). Consider an infinite sequence of size-d random arrays {(Xim ... Xdm) InmN where each variable Xim takes values in {-,... k The sequence is:
1. infinitely exchangeable, and
2. if there exists DAG G such that vi E [d], vn E N:
[a(m L ND [j]] ND an++111 PA
where PA; selects parents of node and ND; selects non-descendants of node i in G. ND; denotes the set of denedescessants of node excluding its own parents.
if and only if there exist d random variables where 0g E [0, 1) 11 kj and every column of O sum to with suitable probability measures {Vr} such that the joint probability can be written as
N d
P(x,1::)) = //
p( pa. i:n. O (z)d21((1) dv))
(9)
n=1i=1
where X,1I:N (( 1d
4
Identifiability Result
The causal de Finetti theorems show that exchangeable processes can be represented as ICM genera- tive process when certain CI statements hold. However, such a representation is only really useful for causal discovery if it is unique in other words we would like if only one such decomposition were possible for any given exchangeable process. This property is called identifiabilit. this section we study the identifiability of ICM generative process. We start by introducing graphical terminology.
Definition& 4 (Acyclic directed mixed graph (ADMG) (Richardson, 2003)), An acyclic directed mixed graph can contain two types of edges: directed ' or bi-directed 't>'. When an ADMG does not contain any bi-directed edge, it becomes a directed acyclic graph (DAG).
Definition 5 (I-map (Koller and Friedman, 2009)). Given P is distribution, I(P) denotes the set of conditional independence relationships of the form X 1 Y Z that hold in P. Given be ADMG, I()) denotes the set of conditional independence assumptions encoded in G which can be directly read-off via m-separation (Zhang and Spirtes, 2012). When a DAG, I()) can be directly read-off via d-separation (Pearl, 1988).
Definition (Global Markov property and faithfulness (Zhang and Spirtes, 2012)). Given a ADMG and a joint distribution P. the distribution satisfies global Markov property with respect if I(g) C I(P). Sometimes it is also called P is Markovian with respect to G. We say P is faithful to GPP)(P) S I(G).
Definition 7 defines the mapping from causal graphs generated under an i.i.d. process to those generated under an exchangeable process. The latent variables in causal de Finetti theorems can be represented by bi-directed edges in Definition 4.
Definition 7 (ICM operator on a DAG). Let U be the space of all DAGs whose nodes represent X1, XI,..., Xa. Let V be the space of ADMGs whose nodes represent {(Xin)), where E [d], E N. A mapping F from U to V is an ICM operator if FG)) satisfies:
.F(g) restricted to the subset of vertices (X,,,...., is a DAG for any e
"Xin Xtm whenever n + m for all i [d]
"BBrrett and Leifer, 2009) provides an alternative proof of conditional de Finetti in quantum theory for categorical variables.
7

---

there are no other edges other than stated above
We denote the resulting ADMG as TCM(G). Let PA im denote the parents of X in TCM(G) and similarly for ND s.n for corresponding non-descendants.
Theorem 5 (Identifiability Theorem). Consider the set of distributions that are both Markovian and faithful to (G), i.e., E(g) == (P:I(PP = II)CM( Then,
E(Gi) E(G2) if and only if G2
(10)
The set of graphs {ICM(g)} characterizes the set of causal graphs for data sampled from ICM- generative processes. Given any two causal structures G1 and G2 underlying data sampled from ICM-generative processes, we say they are Markov equivalent if (G)) E(2)). Theorem 5 states given a distribution that is Markovian and faithful (C) one can identify its unique causal structure as each graph induces unique conditional independences. See Appendix C for proof.
Connection to i. i. Causal de Finetti theorems though stated formally under exchangeable process, it automatically holds for data generated under an i.i.d. process. When observing i.i.d. data, the measures 142 (8) are Dirac measures, and the de Finetti parameters {0.] are deterministic, i.e.. fixed across multiple samples generated from the process. The identifiability theorem stated here, however, excludes distributions generated by marginally i.idd processes. requires P to be faithful to ICM (g). If any one of the marginal distributions of P can collapse to an i.dd. process, i.c., there exists an index d such that P(Xd:1,.... X2N) ) = IЛ, p(X.m), then since it contains extra conditional independence re relationships. Fig. 2 illustrates that compared to i process, ICM -egereeeeet processes enable unique causal structure identification.
not faithful to ICM(G)
5 Causal Structure Learning in Multi-environment Data
We established in Thm. 5 that causal structure is identifiable in ICM generative models by testing for CI relationships in exchangeable data. For example, if Y. 1 X, X, holds for an exchangeable pair (Xn, Y,). we conclude that X + Y, i. X causes Y. But how exactly does one test for this in data?
To test if a CI statement holds between set of random variables, one typically requires multiple samples, that is i.i.d. copies of the variables in question. Similarly, to apply our identification results in practice, we need access to multiple i.i.d. copies of the exchangeable pair (Xn, Yr,,, E N (see Def. 2). Each copy of {(x,, JaJ gives us a whole dataset containing a sequence of individual pairs, thus, we need multiple independent datasets to test for the CI condition. This requirement for multiple datasets connects our work to grouped or multi-environment data.
In the causal literature, grouped data refers to data available from multiple environments, each producing (conditionally) i. observations from a different distribution, which are related through some invariant causal structure shared by all environments. Grouped data underlies a wide range of causal discovery approaches (Arjovsky et al., 2019; Heinze-Deml al., 2018: Huang et al., 2020; Peters and Meinshausen, 2016; Rojas-Carulla et al., 2018; Tian and Pearl, 2001). We can interpret multi-environment data through the lens of exchangeability as follow: each environment E E, we >=t...N.. where X denotes the d-th random variable in n-th sample in environment and No is the number of samples from environment e. Data across enviroments are independent and identically distributed in the sense that the distribution of : and Xe X identical for all N < min(Ne, NNr).. Each environment thus provides a finite marginal of an i. i.d copy of the same exchangeable process, just as we needed for testing CL. Alternatively, one can also interpret environments as samples from latent variables, i.e. (0", s)") ii.d. drawn from p(0), p(1) characterizes environment e.
observe exchangeable samples X.,N,N. = ((Xi.. i:n. ... X (mm) X
Next, we propose the Causal-de- -ineett algorithm, which guarantees to recover the DAG given multi-environment data consistent with ICM. In particular, the algorithm utilizes two samples per environment and sufficiently large number of independent environments enable identification.
Notation: As every sample all environments shares the same causal structure, we sometimes abbreviate the variable X to X or X, The results proved under abbreviated indices mean the abbreviated indices could take any values and the result remains the same. Let S, denotes the set containing nodes belong to n th rank in DAG G's topological ordering. (See details in Appendix D)

---

Lemma 1. A node Xim E S1 if and only for every m # and j # i, Xin 1 X jmm {Xem Hette
Lemma 2. Let node X; E Sn, and X; E Sm where < Set l = m. There does not exist a directed edge from X; to X3 if and only if when = 1, X; X, Syni and when k > X; 1.1. X; Z, where Z Syn U (PAj n Sen) U (SA) X.))
Lemma I states the necessary and sufficient conditions to identify leaf nodes. Lemma 2, intuitively says, to decide whether X, and X, have direct edge, one should block all the potential non-directed paths. Step of the algorithm is to iteratively identify and remove the current set of leaf nodes, and then search for the orders. Step 2 of the algorithm is to apply Lemma 2 to determine the existence of an edge between different topological orders. Algorithm in Appendix D details the exact procedure.
set of leaf nodes until all nodes have been classified into their topological
6 Experiments
We benchmark our method's performance against several state-of-the-art methods. As measure of performance against methods for heterogeneous data, we compare against CD-NOD (Huang et al., 2017, 2020; Zhang et al., 2017). As measure of performance against methods designed for i.i.d. data, we compare with common causal structure learning algorithms, e-g. FCI (Spirtes et al., 1995), GES (Chickering, 2002), NOTEARS (Zheng et al., 2018), DirectLinGAM (Shimizu et al., 201 1) and PC algorithm (Spirtes al., 2000b). Lastly, we compare with a random guess baseline.
Bivariate Causal Discovery We generate multi-environment data as described in Section 5. Latent factors N were randomly generated with distinct and independent elements each environment. Samples within each environment have the noise variables Ñ generated via Laplace distributions conditioned on the latent factor. We observe bivariate data X E IR² with X1 and X₂ denotes the first and second entry of X and aim uncover the causal direction between X₁ and X2. Let e denote variables contained in environment
N ~ 4[11,1]
No Laplace (N,
X A + BeNree2 montineur (e)
where o2 denotes elementwise square operation. Specifically, A E R2x is randomly sampled triangular matrix and B A I. We randomly sample bivariate structures, X; + X2, X1, X, 1 X2, by ensuring A is either a lower triangular, upper triangular or diagonal matrix. Our data further simulates a realistic situation, i.e., the causal structure remains invariant with changing functional relationships across environments. This is implemented by randomly sampling the existence of nonlinear dependence indicator Il nontinear (e) per environment. We perform three conditional independence tests with a = 0.05 and output our estimate as the causal structure corresponding the test with the highest p-value. We repeat the experiment for 100 times and report the proportion of correct causal direction identified with varying numbers of environments. Figure 3(a) shows the proportion of correct bivariate causal direction detected as the number of environments |3| increases and the number of observations within each environment as fixed to be 2. We observe Causal-de- de-Finetti algorithm outperforms all the other state-of-theeart methods and its accuracy converges close to 100%. This demonstrates its capability to handle datasets with limited samples per environment and changing functional relationships across environments.
Multivariate Causal Structure Discovery We further test our algorithm's performance in identifying multivariate causal structure. We randomly generate causal graphs with 3 variable nodes where each variable takes binary values. Figure 3(b) shows the Structural Hamming Distance (Tsamardinos al., 2006) between true and estimated DAG averaged over 100 experiments. We again observe Cauusl-dd-Fiinee outperforms all the other baselines, which validates our identifiability theorem and demonstrates algorithms designed for i.i.d. data does not work in our setting.

---

10
Cand frodi
Proporton correct
08
GES
Simmec turw per oreer the 0ottor
CO
130
156
36
24
30
250
430
456
201
2013
Number of envionments
Number cnstronmonns
(a) Bivariate causal discovery
(b) Multivariate structure learning
Figure 3: Our method's ("Causal-de-Finttt)) p performance in identifying the correct underlying DAG, compared the "CD-NOD", "FCT", "GES", "NOTEARS", "DirectLinGAM", "PC", "Random" baseline in bivariate and multivariate settings. Shown are the mean and 95% confidence interval of the standard error of the mean for each method aggregated over 100 experiments. (Causal-de-Fnnett identifies unique causal structures and is robust against changing functions across environments.
7 Discussion
Causal exchangeability Dawid (2021) introduces recision-theorche framework for causality and uses pre-treatment and post-treatment exchangeability as foundational assumptions on external data used to solve the decision problem. Jensen al. (2020) studies object conditioning and show its probabilistic interpretations can be explained using exchangeability. Object conditioning, due exchangeability, thus mitigates latent confounding and measurement errors for causal inference. Our work provides a statistical understanding of ICM assumption: it is equivalent to assuming exchangeability and certain conditional independence conditions.
that one can only identify causal structures up to Markov equivalence classes (Pearl, 1988), and going beyond that is known to be impossible without further parametric constraints (Hoyer et al., 2008b; Shimizu et al., 2006). A recent line of work considers mixture of observational multi-environment data and interventional data to perform inference: Arjovsky et al. (2019); Peters and Meinshausen (2016); Rojas-Carulla et al. (2018) use causal invariance property to discover stable predictors and Huang et al. (2017, 2020) estimate kernel mean embeddings of heterogenous data distributions to test the independence of causal mechanisms. Monti et al. (2020) discovers bivariate causal direction by first recovering the underlying generating sources and then perforning conditional independence tests on the recovered source factors. These algorithms on non-i.i.d. grouped data all demonstrate success, though it is unclear the connection between causal assumptions and probabilistic implications of grouped data. Our work observes that grouped data is akin to exchangeable sequences, containing richer conditional independence structures, In particular, ICM-gencrative processes with a sufficient number of environments allow unique causal structure identification.
Causal structure learning Within the study of i.i.d. data, is
Relations to causality in time-series The study of data generated from i.i.d. process, exchangeable process, and time-series be seen as a progression to understand more structured data. Appendix E details the connections between ICM-generative processes and causality in time series (Runge, 2020).
Conclusion We prove causal de Finetti theorems formalizing the independent causal mechanism assumption in data generating processes as concrete statistical conditions. We call the induced generative models (CM-generative processes. For data sampled from ICM-generative processes, show that one can identify unique causal structure. We build the connection between exchangeable and grouped data and justify the success of many methods leveraging ICM and algorithms in non-i.i.d. grouped data. Going beyond the i.i.d. assumption has been the bottleneck to applying machine learning to real- world situations. Rather than considering it nuisance, our work shows an example of a theoretical advantage of exchangeable data causal structure identification.
Acknowledgement S.G. would like to acknowledge helpful discussions with Damon Wishick on understanding causal de Finetti theorem multi-ennvirommnt data and Thijs van Ommen for his constructive feedback in the reviewing process which corrected the original version of Lemma 2.
10

---

References
Aldrich. Autonomy. Oxford Economic Papers, 41(1):15-34, 1989. ISSN 00307653, 14643812.
M. Arjovsky, I.. Bottou, I. Gulrajani, and D. Lopez-Paz. Invariant risk minimization. In arXiv preprint /ttp::/0070009333 2019.
J. Barrett and M. Leifer. The de Finetti theorem for test spaces. New Journal of Physics, 11(3), 2009.
Y. Bengio, A. Courville, and P. Vincent. Representation learning: A review and new perspectives. IEEE transactions on patlern analysis and machine intelligence, 179818878 2013.
J. Brehmer, P. De Haan, P. Lippe, and T. S. Cohen. Weakly supervised causal representation learning. Advances in Neural Information Processing Systems, 35:38319 35:38319-38331, 38331, 2022.
T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam,
G. Sastry, A. Askell, al. Language models are few-shot learners, Advances in neural information processing systems, 33:1877 18:188771990 2020.
D. M. Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-554 2002.
Dawid. Decision-theoretic foundations for statistical causality. Journal of Causal Inference, 9(1): 39-77, 2021.
B. de Finetti. Sul significato soggettivo della probabilità. Fundamenta Mathematicae, 17(1):298-329, 1931.
A. Goyal, Lamb, Hoffmann, S. Sodhani, S. Levine. Y. Bengio, and Schölkopf. Recurrent independent mechanisms. arXiv preprint arXiv:1909.1083 10893, 2019.
T. Haavelmo. The probability approach in econometrics. Econometrica, 12:ii-1115, 1944. ISSN 00129682, 14680262.
E. Haviland. On the Momentum Problem for Distribution Functions in More Than One Dimension. II. American Journal of Mathematics, 1661641 1936.
C. Heinze-Deml, J. Peters, and N. Meinshausen. Invariant Causal Prediction for Nonlinear Models. Journal of Causal Inference, 2018.
Hoyer, D. Janzing, M. Mooij, J. Peters, and B. Schölkopf. Nonlinear causal discovery with additive noise models. In Advances in Neural Information Processing Systems, 2008a.
Hoyer, D. Janzing, additive noise models. Advances in neural information processing systems, 21, 2008b.
Mooij, J. Peters, and B. Schölkopf. Nonlinear causal discovery with
O. Hoyer, A. Hyvarinen, R. Scheines, P. L. Spirtes, J. Ramsey, G. Lacerda, and S. Shimizu. Causal discovery of linear acyclic models with arbitrary distributions. arXiv preprint arXiv: arXiv:/206. 1206.2200 2012.
B. Huang, K. Zhang, Zhang, R. Sanchez-Romero, C. Glymour, and B. Schölkopf. Behind distribution shift: Mining driving forces of changes and causal arrows. In 2017 IEEE International Conference on Data Mining (ICDM), pages 913-918, IEEE, 2017.
B. Huang, K. Zhang, J. Zhang, J. D. Ramsey, R. Causal discovery from helerogancoushhonstttoonaar data. J. Mach. Learn. Res., 21(89):1-53, 2020.
C. Glymour, and B. Schölkopf.
D. Janzing and B. Schölkopf. Causal inference using the algorithmic Markov condition. IEEE Transactions Information Theory, 56( (10), 2010.
D. Jensen, J. Burroni, and M. Rattigan. Object conditioning for causal inference. In R. P. Adams and V. Gogate, editors, Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pages 1072-1082, PMLR, 22-25 Jul 2020.

---

W. Kirsch, An elementary proof of de Finetti's theorem. Statistics & Probability Letters, 151(1), 2019.
A. Klenke. Probability Theory: A Comprehensive Course. World Publishing Corporation, 2008.
D. Koller and N. Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
Locatello, S. Bauer, M. Lucic, G. Raetsch, S. Gelly, B. Schölkopf, and O. Bachem. Challenging common assumptions in the unsupervised learning of disentangled representations. In international conference on machine learning, pages 41 4424 PMLR, 2019.
K. Madan, N. R. Ke, A. Goyal, B. Schölkopf. and Bengio. Fast and slow learning of recurrent independent mechanisms. arXiv preprint arXiv:2105.08710, 2021.
R. Monti, K. Zhang, and Hyvärinen. Causal discovery with general non-linear relationships using non-linear ica. In Uncertainty in artificial intelligence, pages 186-195. PMLR, 2020.
B. O' O'Neill. Exchangcability, correlation, and bayes' effect. International statistical review, 77(2):
241-250, 2009.
G. Parascandolo, N. Kilbertus, M. Rojas- Carulla, and B. Schölkopf. Learning independent causal mechanisms. In Proceedings of the 35th International Conference Machine Learning (ICML), volume 80 Proceedings of Machine Learning Research, pages
PMLR, 2018.
Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan kaufmann, 1988.
Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, New York, 2nd edition edition, 2009.
Peters and N. Meinshausen. Causal inference using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society, Series B:947-1012, 2016.
Peters, J. M. Mooij, D. Janzing, and B. Schölkopf. Causal discovery with continuous additive noise models. 2014.
J. Peters, D. Janzing, and B. Schölkopf. Elements of Causal Inference: Foundations and Learning Algorithms. 2017.
T. Richardson. Markov Properties for Acyclic Directed Mixed Graphs. Scandinavian Journal of Statistics, 30(1):445-157, 2003.
M. Rojas- Carulla, B. Schölkopf, R. Turner, and J. Peters. Invariant models for causal transfer learning, 2018.
Rojas-Carulla,
J. Runge. Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasets. In Conference on Uncertainty in Artificial Intelligence, pages 1388-1397. PMLR, 2020.
B. Schölkopf, D. Janzing, Peters, E. Sgouritsa, K. Zhang, and Mooij. On causal and anticausal learning. In JCML, 2012.
B. Schölkopf, F. Locatello, S. Bauer, R. N. Ke, N. Kalchbrenner, A. Goyal, and Y. Bengio. Towards causal representation learning. Proceedings of the IEEE, 10965):612-634, 2021.
S. Shimizu, P. O. Hoyer, A. Hyvärinen, and A. Kerminen. A Linear Non Gan--aassinn Acyclic Model for Causal Discovery. Journal of Machine Learning Research, 7:2003-2030, 2006.
S. Shimizu, T. Inazumi, Y. Sogawa, A. Hyvarinen, Y. Kawahara, T. Washio, P. O. Hoyer, K. Bollen, and P. Hoyer. Directlingam: direct method for learning a linear non-gaussian structural equation model. Journal of Machine Learning ReSearch-JMLR, 12(Apr):1225-122))))) 1225-1288, 201
12

---

P. Spirtes and T. S. Richardson. A polynomial time algorithm for determining dag equivalence in the presence of latent variables and selection bias. In D. Madigan and P. Smyth, editors, Proceedings of the Sixth International Workshop on Artificial Intelligence and Statistics, volume R1 of Proceedings of Machine Learning Research, pages 489-500. PMIR, 04-07 Jan 1997. Reissued by PMLR on 30 March 2021.
P. Spirtes, C. Meek, and T. Richardson. Causal inference in the presence of latent variables and selection bias. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, UAI955, page 499-506, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc. ISBN 1558603859.
P. Spirtes, C. Glymour, R. Scheines, S. Kauffman, V. Aimale, and F. Wimberly. Constructing bayesian network models of gene expression networks from microarray data. 2000a.
Spirtes, C. N. Glymour, R. Scheines, and D. Heckerman. Causation, prediction, and search. MIT press, 2000b.
J. Tian and J. Pearl. Causal Discovery from Changes. In Proceedings of the 17th Annual Conference on Uncertainty in Artificial Intelligence (UAI), pages 512-522, 2001.
I. Tsamardinos, L. Brown, and C. Aliferis. The max-min hill-climbing bayesian network structure learning algorithm. Machine Learning, 65:31-78, 10 2006. doi: 2.10007/109944-006
J. Zhang and P. L. Spirtes. A transformational characterization of markov equivalence for directed acyelic graphs with latent variables. arXiv preprini arXiv: /ee:::227.14411 1419, 2012.
K. Zhang and A. Hyvärinen. On the Identifiability of the Post-Nonlinear Causal Model. In Proceed- ings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, 2009.
K. Zhang, B. Huang, Zhang, C. Glymour, and B. Schölkopf. Causal discovery from nonstation- ary/heterogeneous data: Skeleton estimation and orientation determination. In Proceedings of the Twenty- Sixth International Joint Conference on Artificial Intelligence (IJCAI), pages 1347-1353, Aug. 2017. doi: 10.24963fijeai.2117/13
X. Zheng. B. Aragam, P. Ravikumar, and E. P. Xing. DAGs with NO TEARS: Continuous Optimiza- tion for Structure Learning. In Advances in Neural Information Processing Systems, 2018.
13


Reviews:
[{"review_id": "b7UZH8MDlh", "reviewer": "Reviewer_TMn5", "summary": "This paper examines a stronger notion of exchangeability which provides invariant causal structure, i.e., is capable of serving as the basis for causal reasoning. The main contribution is a theorem which states that for pairs of RV with certain conditional independence properties it is always possible to represent them as a mixture of i.i.d. sequences with identical Markov factorization. This idea is further extended to the multivariate case. The authors then connect this notion of causal exchangeability to causal identification and causal discovery. Experimental results are provided for bivariate orientation and causal discovery from multiple datasets which show favorable performance when taking causal exchangeability into account.", "questions": "Did you run any other causal structure learning algorithms such as FCI, GES or even optimization based approaches such as NOTEARS? Given the poor performance of PC I'm wondering if this is a weakness shared across all algorithms. ", "limitations": "Yes. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I found this paper to be a simple, intuitive, and thorough piece of work that provides an interesting new lens on causal inference. The notion of defining what constitutes exchangeable sequences with invariant causal structures is very interesting, and the authors do a very nice job of motivating the problem, providing thorough and well written theorems, and contextualizing them within the context of application. This is a clear description of causal mechanisms from a purely statistical view and an interesting addition to the literature. ", "weaknesses": "The largest weakness I can see here is the lack of comprehensive empirical evaluations. The evaluations provided are fairly simplistic, limited in scope, and serve more as a demonstration rather than an evaluation finding relative strength and weakness of the proposed method. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time and providing a thorough review and constructive feedback. We are glad you found the paper interesting as a simple, intuitive, thorough piece of work. \n> The largest weakness I can see here is the lack of comprehensive empirical evaluations. The evaluations provided are fairly simplistic, limited in scope, and serve more as a demonstration rather than an evaluation finding relative strength and weakness of the proposed method. \n> Did you run any other causal structure learning algorithms such as FCI, GES or even optimization based approaches such as NOTEARS? Given the poor performance of PC I'm wondering if this is a weakness shared across all algorithms.\n\nWe agree with the reviewer that the empirical evaluations are rather limited. We mainly use it to illustrate unique causal structure learning is feasible for ICM-generative processes. Here we include additional empirical results that compare with FCI, GES and NOTEARS in the uploaded pdf. Our result shows that poor performance is shared across all algorithms evaluated. This is consistent with the main point of this paper that exchangeable data allows unique causal structure identification using conditional independence tests and existing algorithms (designed under i.i.d. data setting) performs poorly in our settings. We thank the reviewer for the suggestion and will include this result and a more detailed empirical evaluation in the updated version. \n"}, {"review_id": "LcT50TAdv3", "reviewer": "Reviewer_idLT", "summary": "The authors describe how the combination of assumptions about exchangeability and specific statistical tests can enhance the causal implications that can be derived from observational data.", "questions": "(none)", "limitations": "The authors do not sufficiently emphasize the special structure of the data (specifically, multiple environments) that is needed to apply the methods that they advocate. Judging from the results shown in Figure 3, the benefit to multivariate structure learning only becomes substantial at truly large numbers of environments. The need for multiple environments (and large numbers of them) should be emphasized more clearly earlier in the paper.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The utility and implications of exchangeability for causal inference are well described by the authors. Under the assumptions that they outline (the availability of multiple environments), the additional causal implications that can be derived are clearly very useful.\n\nThe authors help readers by following essentially all complex mathematical statements with an informal statement of the result in relatively plain language.", "weaknesses": "A 2019 paper by Jensen et al. [1] on exchangeability and structure learning in causal graphical models makes a very similar point as this paper regarding the value of multi-environment data and exchangeability. That paper describes how to use knowledge of environments (what that paper calls “parent objects”) to provide additional constraints on graph structure by conditioning on environment (and the latent variables implied by that environment). The proofs in that paper rely on exchangeability and contrast exchangeability with conditional independence. That paper differs somewhat from this paper in goals and focus, but the current paper would be improved by clearly describing the contributions of that paper and delineating the unique contributions of the present paper.\n\nThe authors cite the Independent Causal Mechanism principle without reference to the long history of the concept, stretching back almost a century. Pearl’s work [2] (in which it is sometimes called “modularity”) cites an earlier review by Aldrich [3] (in which it is called “autonomy”), which cites very early work by Haavelmo and others as far back as the 1930s. This history is worth at least noting.\n\nThe difference between “environments” and random variables is not clearly explained until Section 4, and this distinction is critical to understanding how (for example) schools differ from students in the second example of Section 3.  Each school corresponds to many students. The plate notation introduced in Section 4 would help readers if introduced earlier.\n\n*References*\n\n1. Jensen, D., Burroni, J., & Rattigan, M. (2020, August). Object conditioning for causal inference. In *Uncertainty in Artificial Intelligence* (pp. 1072-1082).\n\n2. Pearl, J. (2009). *Causality*. Cambridge University Press.\n\n3. Aldrich, J. (1989). Autonomy. *Oxford Economic Papers*, *41*(1), 15-34.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time and are glad to find the reviewer appreciates the “utility and implications of exchangeability for causal inference” and considers our results as “clearly very useful”. \n\n> That paper differs somewhat from this paper in goals and focus, but the current paper would be improved by clearly describing the contributions of that paper and delineating the unique contributions of the present paper.\n\nThanks for pointing out the work from Jensen et al. [1] and their interesting findings: the probabilistic implications for conditioning on objects can be explained using exchangeability. They show object conditioning, due to exchangeability, has the advantage of mitigating latent confounding and measurement errors for causal inference.  Our work differs from [1] as rather than inference, we show the advantage of exchangeable data for causal discovery and advocate the widely-used causality principle ICM can be expressed as Equation 5. \nOur unique contribution is that researchers often assume ICM principle (or its variants) on the data-generating process, but do not come with an understanding for the implications of assuming ICM, i.e., the probabilistic relationships of the underlying data. Causal de Finetti, explicitly states, the implicit probabilistic assumptions are exchangeability of data and certain conditional independences. In summary, this paper’s unique contribution is to 1) show exchangeable data is better than i.i.d. data in unique causal structure identification (which is previously deemed impossible via CI tests [2] ) and 2) prove causal de Finetti theorems which explicitly connect causality and probabilistic modelling. We thank the reviewer for the suggestion in comparing related work on exchangeability for casual inference and will include more detailed discussions in an updated version. \n\n> The authors cite the Independent Causal Mechanism principle without reference to the long history of the concept, stretching back almost a century. Pearl’s work [2] (in which it is sometimes called “modularity”) cites an earlier review by Aldrich [3] (in which it is called “autonomy”), which cites very early work by Haavelmo and others as far back as the 1930s. This history is worth at least noting.\n\nWe thank the reviewer for pointing this out and will include the relevant references, for example, Pearl (2009), Aldrich (1989), Hoover (2008), in an updated version. \n\n> The authors do not sufficiently emphasize the special structure of the data (specifically, multiple environments) that is needed to apply the methods that they advocate. The need for multiple environments (and large numbers of them) should be emphasized more clearly earlier in the paper.\n\nWe thank the reviewer for the suggestion. The experiments aimed as a proof-of-concept to demonstrate our identifiability theorem in practice. The need for large number of multiple environments arise due to we only use two samples per environment. From the reviewer's feedback, we understand there could be potential misunderstandings. We will incorporate your suggestions (e.g. explaining the difference between ‘environments’ and random variables, moving the plate notation earlier, emphasize the need of large number of environments) in the updated version to ease readers’ understanding. \n\nReferences: \n1. Jensen, D., Burroni, J. &amp; Rattigan, M.. (2020). Object Conditioning for Causal Inference. Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, in Proceedings of Machine Learning Research.\n2. J. Pearl, Causality: Models, Reasoning, Inference, 2nd ed. New York, NY, USA: Cambridge Univ. Press, 2009.\n3. J. Aldrich, “Autonomy,” Oxford Econ. Papers, vol. 41, no. 1, pp. 15–34, 1989.\n4. K. D. Hoover, “Causality in economics and econometrics,” in The New Palgrave Dictionary of Economics, S. N. Durlauf and L. E. Blume, Eds., 2nd ed. Basingstoke, U.K.: Palgrave Macmillan, 2008.\n"}, {"review_id": "3F9pc8A7bp", "reviewer": "Reviewer_ikix", "summary": "Causal analogs to de Finetti's theorem are proven, showing that if in an exchangeable distribution certain conditional independences hold, the distribution can be seen as being generated by a DAG with a latent variable corresponding to each node, determining that node's causal mechanism. It is further shown that knowing these conditional independences allows unique identification of the DAG. A causal discovery algorithm is presented leveraging these results, and evaluated in a synthetic data setting where data come from very many different environments.", "questions": "* Line 139: \"one can separately manipulate each latent variable controlling different mechanisms\" - Does this follow from equation 5? How? ([Dawid 2004] warns that de Finetti's theorem only establishes that the latent variable exists in our minds, not in the real world.)\n\n* In the experiment, I assume $\\tilde{N}^e$ is a 2-element vector? What about $N^e$? And how many x-y pairs are sampled per environment?\n\nSuggestions to improve the language (not relevant for my assessment of the paper):\n\n* the spelling of \"i.i.d.\" is inconsistent (sometimes with spaces, sometimes with the final . missing)\n\n* line 92 & 595: \"infinite exchangeable\" -> \"infinitely exchangeable\"\n\n* the final sentence of section 2.2 doesn't parse (\"due to\"&\"that underlies\"; \"involving observations are i.i.d.\")\n\n* below definition 2: \"does not hold for all\" -> \"does not hold for any\"\n\n* line 140 & 141: \"supporting mechanisms\" -> \"supporting that mechanisms\" (2x)\n\n* line 147: \"one implicitly make\" -> \"makes\". Similar in appendix A.\n\n* Theorem 3 & 4: I'd replace \"The sequence is\" by \"If\", add \"the sequence is\" to point 1, and remove \"if\" from point 2\n\n* line 201: \"decide\" -> \"deciding\"\n\n* line 220: \"process\" -> \"processes\" (also elsewhere)\n\n* Definition 5: \"Given $P$ is\" -> \"Let $P$ be\"; \"Given $G$ be\" -> \"Let $G$ be\"; \"a ADMG\" -> \"an ADMG\" (this also appears in Def 6); \"read-off\" -> \"read off\"\n\n* Definition 7: There is only one mapping fitting this definition, so define it straightaway instead of defining when something \"is an ICM operator\". Line 242 has a double \"other\"\n\n* line 280: $<$ -> $\\leq$\n\n* line 287: \"topological ordering\" is not the right concept here, as that is a total order\n\n* line 629: \"exchangeable\" -> \"exchangeability\"\n\n* line 679: \"$l < k + 1$ -> $l \\leq k$", "limitations": "Yes (except as discussed above)", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The causal de Finetti's theorems are philosophically interesting, similar to how the original de Finetti's theorem can play a role in the justification of Bayesian inference. The resulting graphical models, expressing disentangled causal mechanisms in terms of latent variables (Figure 1b, right), are very insightful and deserve to be commonly known in the community.\n\n* The resulting conditional independences, which are testable if data are available from multiple environments, are a very useful ingredient for causal discovery algorithms in such settings.", "weaknesses": "* The related work section only considers causal discovery, not the causal de Finetti theorem itself. Such references should also be listed, because the paper is claiming a contribution in this area. For instance, [Dawid 2021] also uses exchangeability to do causal inference.\n\n  * Also about the related work section: the sentence \"These algorithms on non-i.i.d. grouped data all demonstrate success, though it is unclear why grouped data enable causal structure identification.\" - I disagree strongly with this, there is a very good understanding of why multiple environments (possibly including interventional data) help with causal discovery, in the papers you list as well as in the causal inference literature as a whole.\n\n* Implications of the causal de Finetti theorem are listed without sufficiently arguments, and I believe overstated. See question about line 139 below.\n\n* Here is a counterexample to Lemma 2: $X_i \\rightarrow X_a \\rightarrow X_b \\leftarrow X_c \\leftarrow X_d \\rightarrow X_j$ with $X_b  \\rightarrow X_j$. Then $X_d \\in S_n$, so only $X_b$ is conditioned on, but this opens the listed path.\n(Separate from this, in line 294 explaining the lemma, I think \"non-directed\" should be \"open\": also directed paths other than the 1-arrow path should be blocked.)\n\n* Experiment (some things are unclear to me now, see questions below):\n\n  * other methods are not really fit for this scenario\n\n  * 1 x-y pair per environment (?): this disconnects the experiment from the theory\n\n**References:**\n\n[Dawid 2004]: Probability, Causality and the Empirical World: A Bayes-de Finetti-Popper-Borel Synthesis, Statistical Science , Feb., 2004, Vol. 19, No. 1 (Feb., 2004), pp. 44-57\n\n[Dawid 2021]: Decision-theoretic foundations for statistical causality, Journal of Causal Inference 2021; 9: 39-77", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thorough feedback, and we appreciate the kind words that causal de Finetti theorems “deserve to be commonly known in the community”. Thank you for pointing out the interesting reference Dawid 2021. We will discuss and cite [1] in an updated version. \n\nRe ‘grouped data’: This paper meant to express that there is work [2] assuming ICM, but does not come with an understanding for its implications on data’s probabilistic relationships. We thank you for your feedback and we promise to rephrase the sentence and clarify that our contribution is with respect to the statistical understanding of ICM. \n\nRe de Finetti parameters: We are sorry we failed to clarify this. We did not mean to claim that the variable necessarily exists in the real world - only that the conditions of Thm. 2 imply that the data looks as if it has been generated by a process with independent mechanisms. (We are no experts on those philosophical ramifications, so we try to focus on technical results.)\n\nRe counterexample to Lemma 2 (only used for structure learning, not affecting causal de Finetti theorems and identifiability theorem): We thank the reviewer for spotting this error. Here we correct the lemma and its proof. For its impact on the empirical evaluations, we re-run the experiments with the updated fix and observe no changes in the results (see the uploaded pdf). We will include all the changes in the updated version. \n\n**Lemma 2** Let node $X_i \\in S_n$ and $X_j \\in S_m$ where $m < n$. Set $k:= n-m$. There does not exist a directed edge from $X_i$ to $X_j$ iff when $k = 1$,  $X_i \\perp X_j | S_{>n}$; and when $k > 1$: $X_i \\perp X_j | Z$, where $Z = S_{>n} \\cup (PA_j \\cap S_{<n}) \\cup {S_n \\backslash X_i}$. \n\n**Proof of Lemma 2**: ($\\Rightarrow$): suppose there is no direct edge, i.e. $X_i \\to X_j$. If there is no path connecting $X_i$ and $X_j$, then $X_i \\perp X_j$. Next, we assume there exists a path $p$ connecting $X_i, X_j$. Then $p$ satisfies: Either (1) there exists $X_k \\in p$ s.t. $X_k \\in S_{>n}$, or (2) all variables in the path $\\in S_{\\leq n}$.\n\nWhen $k = 1$: \n    Under (1), let $W$ be the set containing all variables $\\in S_{>n}$. Note $|W| \\geq 1$. Then there exists a non-collider $X_k \\in W$. Suppose all variables in $W$ are colliders, then there must $ \\exists X_l \\in p$ and $X_l \\not \\in W$ that has an edge outgoing to some variable contained in $W$. By definition of sink orders, $X_l \\in S_{>n+1} \\implies X_l \\in W$. Contradiction. \n    Under (2), we show that there exists a collider in the path. Suppose there is no collider on the path, then all the edges point in one direction, here the edges flow from $X_i$ to $X_j$. Since the path is not a 1-arrow direct path, there $\\exists X_a \\in p, a \\neq \\{i, j\\}$. \nLet $X_a$ be the neighbour of $X_j$. If $X_a \\in PA_j$, then $X_a \\in S_{\\geq m + 1}$. As $X_i$ is an ancestor of $X_a$, $X_i \\in S_{\\geq m+2} = S_{\\geq n+1}$. If $X_a \\in CH_j$, if edges flow in one direction, $X_j$ is an ancestor of $X_i$. Contradiction. \n    Given the path connecting $X_i$ and $X_j$ either contains variables in higher sink orders and there exists a non-collider $X_k \\in p$ and $X_k \\in S_{>n}$., such path can be blocked by conditioning on the set $S_{>n}$; or the path only contains variables in $S_{\\leq n}$ and the path must exist a collider, which we block the path by not conditioning on any variables in $S_{\\leq n}$. \n\nwhen $k > 1$:\n    Under (1), similar as above, there exists a non-collider $X_k \\in p$ and $X_k \\in S_{>n}$. Therefore conditioning on all variables in $S_{>n}$ blocks the set of paths under (1). Under (2) when all variables in the path belong to $S_{\\leq n}$, then let $X_p$ be the parent of $X_j$ in this path, either (2.1) $X_p \\in PA_j \\cap S_{<n}$, or (2.2) $X_p \\in PA_j \\cap S_n$. Under (2.1), $X_p$ is a non-collider in the path, since it has one outgoing edge. Then conditioning on $PA_j \\cap S_{<n}$ blocks the set of paths under (2.1). Under (2.2), for any variable $X_m \\in S_n$ on the path $p$, $X_m$ only has outgoing edges since all variables on the path belong to $S_{\\leq n}$. $X_m$ is also a non-collider, thus conditioning on $S_n$ blocks the set of paths satisfying (2.2). \nBy Markov assumption, CIs holds in distribution. \n\n($\\Leftarrow$): suppose the proposed CI holds and $\\exists X_i \\to X_j$, then $X_i$ is not d-separated by $X_j$. By faithfulness, CI does not hold in distribution. \n**End of Proof**\n\nRe clarifications on experiments, here the equations listed represent the data-generating process for one data instance $X^e$. Specifically, $N^e$ is a vector with size $2$ and $\\tilde{N}^e$ is also a vector with size $2$. In practice, we generate two instances per environment as stated in line 319, where we fix $N^e$ per environment, and generate $2$ $\\tilde{N}^e$ based on the $N^e$ generated and consequently generate 2 data instances $X^e$ based on corresponding $\\tilde{N}^e$. We acknowledge that most other methods are designed to tackle data sampling from i.i.d. setting. To this end, we include a comparison with the method ‘CD-NOD’ [2] which is designed for heterogeneous and nonstationary datasets. We also observe CD-NOD performs poorly in our setting. \n\nOverall, we thank you for the detailed review, which we will carefully take into account your feedback on the clarity of the presentation in experimental design, the related work discussion and implications of causal de Finetti theorem, and will update with more detailed clarification as discussed above. We hope that our response has addressed all your questions, especially on the soundness of our paper (with the corrected Lemma). We kindly ask you to let us know if you have any remaining criticism, and - if we have answered your questions - to consider reevaluating your score.\n\nReferences:\n1. Dawid, P. (2021). Decision-theoretic foundations for statistical causality. \n2. Huang, B. et al. (2020). Causal discovery from heterogeneous/nonstationary data. "}, {"review_id": "jOgXC7Y9aP", "reviewer": "Reviewer_3rag", "summary": "This paper is about causal discovery with exchangeable data, thus relaxing the traditional iid assumption. This allows for causal structure identification by conditional independence tests. The result has application to multi-environment data.", "questions": "I have found it surprising that a relaxation of the iid assumption leads to higher identifiability. Is it possible to better explain this point?\n\nFigure 1a could be clearer to me. Is it possible to make it more expressive (or drop it)?\n\nIs there any room to extend the result to non-Markovian models? \n", "limitations": "No specific issues related to that.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Despite my low confidence, I think the paper delivers strong results for causal analysis. Both the Causal De Finetti theorems and the identifiability result (Theorem 5) appear not trivial and of some impact on people working in the field.", "weaknesses": "- The identifiability result seems to hold for Markovian models only.\n- The experiments are very promising, but only a very limited setup.\n- The paper is very technical and dense, thus more suitable for a journal version. Yet, it can be worth presenting such a condensed version at the Neurips conference.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the efforts and we greatly appreciate your positive feedback. From your comments, you clearly understood the paper.\n\n> The identifiability result seems to hold for Markovian models only.  \n\nWe thank the reviewer for the suggestion, however, Pearl points out in his classical textbook [1] that “Markov compatibility” is \"a necessary and sufficient condition for a DAG G to explain a body of empirical data represented by P, that is, to describe a stochastic process capable of generating P” (Definition 1.2.2). Also the classical result on ‘two DAGs are observationally equivalent’, i.e., one can only distinguish causal structures up to Markov equivalence classes in i.i.d. data, is also established on the condition of Markov compatibility. Here we take the same view and show one can distinguish unique causal structure in exchangeable data. Just as the development of causal discovery in i.i.d. data, we hope there is follow-up work for more practical considerations of non-Markovian models in exchangeable data. \n\n> The experiments are very promising, but only a very limited setup.\n\nWe thank the reviewer for appreciating the values of experiments. Indeed, we aim for the experiments to serve as a demonstration for our identifiability theorem, i.e., ICM-generative processes can indeed recover unique causal structure via conditional independence tests only, and current methods developed perform poorly in our setting. We also agree with the reviewer that it would be interesting to extend the experiments further. Here we include experiment results that are compared to more baselines, (specifically, FCI, GES and NOTEARS). We observe that existing methods all perform poorly in our setting. We will include the result and a more detailed evaluation in an updated version. \n\n> The paper is very technical and dense, thus more suitable for a journal version. Yet, it can be worth presenting such a condensed version at the Neurips conference.\n\nWe agree with the reviewer that the paper is ‘technical and dense’. We also agree with the reviewer that it is worth presenting in a venue like NeurIPS to demonstrate the advantages of exchangeable data for causality. \n\n> I have found it surprising that a relaxation of the iid assumption leads to higher identifiability. Is it possible to better explain this point?\n\nWe thank the reviewer for the question, it is indeed one of the main point of this paper. The higher identifiability power is due to there exist richer conditional independence structures contained in exchangeable data. For example, consider pairs of $(X_1, Y_1)$, $(X_2, Y_2)$. The conditional independence $Y_1 \\perp X_2 | X_1$ trivially holds in i.i.d. data, but holds non-trivially in exchangeable data. This thus allows us to identify unique causal structures. \n\n> Figure 1a could be clearer to me. Is it possible to make it more expressive (or drop it)?\n\nWe thank the reviewer for the suggestion and will try to incorporate it in a future version. \n\n> Is there any room to extend the result to non-Markovian models?\n\nWe thank the reviewer for the question and will illustrate the potential of extension in a simple example of the bivariate case where hidden confounders are allowed. Suppose there are two pairs of variables $(X_1, Y_1, Z_1)$, $(X_2, Y_2, Z_2)$, where $Z_1, Z_2$ are unobserved confounders. It follows the causal structure, $X_i \\to Y_i, Z_i \\to X_i, Z_i \\to Y_i$, for all $i = \\{1, 2\\}$. In particular, $(X_i, Y_i)$ are generated by an exchangeable process connected by latent variables $\\theta$, $\\psi$ and $Z_i$ is generated by an i.i.d. process. Note the conditional independence $Y_2 \\perp X_1 | X_2$ still holds in this setting where there exists hidden confounders. This suggests one can still recover the causal direction of $X$ and $Y$ in this case. \n\nReference:\n1. Pearl, J. (2009). Causality. Cambridge University Press."}]

Author rebuttal:
We thank all the reviewers for their time and effort in providing valuable feedback. We are glad to see all the reviewers have unanimous agreement that this paper delivers solid contributions to the community and some consider it to be “very insightful and deserve to be commonly known in the community”. We also are glad to see several reviewers appreciate this paper’s simple, intuitive explanation of complex mathematical theorems. We thank again for all reviewer’s recognition of the impact of our work and hope this work provides a new lens on causal inference and can trigger follow-up work in the space of causality and exchangeable data. 

We respond to all reviewer’s points in detail but wanted to highlight:

* we followed TMn5’s suggestions for **more comprehensive empirical evaluations**. Here we include comparisons with additional benchmarks, e.g. FCI, GES, NOTEARS, in the uploaded pdf. We observe PC’s poor performance is indeed shared across the additional benchmarks - methods mostly designed for i.i.d. data setting performs poorly on exchangeable data in our setting. We will include the result and a more detailed comparison in the updated version. 


Meta-review: The reviewers made some great points during the rebuttal. Reviewer ikix identified a problem with Lemma 2, which the authors provided a patch for; Reviewer TMn5 recommended more extensive experimental evaluations, which the authors conducted; Reviewer idLT pointed to a very relevant paper that the authors missed, alongside pointers on how to better position the current paper, which the authors promised to incorporate; Reviewer 3rag asked the very intuitive question "How come a relaxed assumption, iid -> exchangeable, lead to stronger identifiability results", which the authors tried to answer.

Overall, I believe the rebuttal has been very helpful to critically evaluate the paper, and improve its weaknesses.

I will add a few things based on my reading of the paper:

- I agree with the reviewers that the authors need to be careful not to over-claim the role of causal de Finetti to further our understanding of the problem. As Reviewer ikix points out, the role of multiple environments in causal structure discovery has generally been well understood unlike what the authors claim.

- This was not raised by any of the reviewers, but I believe there might be a connection to time-series causal discovery, which might also help answer Reviewer 3rag's question. Let i be the time index in Xi, Yi. Consider the bivariate graph unfolded in time X1->Y1 + X1<-(unobserved confounder)->X2, X2-> Y2 and so on. This is the setting explored by causal de Finetti. I understand the two settings are philosophically very different and there is no fixed order that we know a priori. But in my opinion, one can view lifting from iid to exchangeable setup puts us somewhere between iid and time series. I suggest exploring this potential connection in the camera ready. I think both literatures can benefit from each other starting with a clear exposition here.

- In terms of bivariate discovery, I think the illustration in Figure 1a might be misleading. Because, as the authors note in the paper, one still needs iid samples of exchangeable pairs, which boils down to sampling from multiple environments. The non-identifiability of causal structure in the bivariate case is only from observational data. Thus, the claim here needs to be much more nuanced than it currently is. Specifically, the authors need iid samples from the graph in Figure 2c to detect (X2 __ || __ Y1 | X1) and learn that X->Y. This illustration ignores this very important context and the authors simply claim "Under i.i.d. data, one can only identify (X __ || __ Y), whereas under exchangeable data, one can identify unique bivariate causal structure." PC also does not seem like the right baseline for this problem of learning from multiple environments. I strongly suggest revising at least this claim, and providing this much needed context early on in the paper (introduction). 

Having noted these points, which I hope the authors will take into account in their camera-ready, I will recommend acceptance as the connection between exchangeability and causal discovery is definitely worth noting and I did enjoy reading the view that CI statements across samples are informative of the structure, **if one can test them**. Authors need to clearly convey that being able to test these CI statements requires IID samples from exchangeable pairs, which assume access to a different kind of multi-environment data, and the methodology is not directly comparable to basic observational discovery algorithms such as PC.
Decision: Accept (poster)