Learning Causal Models under Independent Changes
Authors: Sarah Mameche
David Kaltenpoth
Jilles Vreeken
Venue: NeurIPS 2023 poster (2023)
Keywords: independent mechanisms
causal discovery
information theory
gaussian processes
TL;DR: We consider the principle of Independent Change of causal mechanisms from an information-theoretic perspective, and propose an approach for discovering causal mechanisms beyond Markov Equivalence from non-i.i.d. data using Gaussian Processes.

Abstract: In many scientific applications, we observe a system in different conditions in which its components may change, rather than in isolation. In our work, we are interested in explaining the generating process of such a multi-context system using a finite mixture of causal mechanisms. Recent work shows that this causal model is identifiable from data, but is limited to settings where the sparse mechanism shift hypothesis holds and only a subset of the causal conditionals change. As this assumption is not easily verifiable in practice, we study the more general principle that mechanism shifts are independent, which we formalize using the algorithmic notion of independence. We introduce an approach for causal discovery beyond partially directed graphs using Gaussian Process models, and give conditions under which we provably identify the correct causal model. In our experiments, we show that our method performs well in a range of synthetic settings, on realistic gene expression simulations, as well as on real-world cell signaling data.

Learning Causal Models under Independent Changes
Sarah Mameche CISPA Helmholtz Center for Information Security sarah. mameche@cispa.de
David Kaltenpoth CISPA Helmholtz Center for Information Security david. kallterpoth@cippa.de
Jilles Vreeken CISPA Helmholtz Center for Information Security jvēcispa.de
Abstract
In many scientific applications, observe system in different conditions in which its components may change, rather than in isolation. In our work, we are interested in explaining the generating process of such multi-context system using a finite mixture of causal mechanisms. Recent work shows that this causal model is identifiable from data, but is limited settings where the sparse mechanism shift hypothesis [ holds and only a subset of the causal conditionals change. As this assumption not easily verifiable practice, we study the more general principle that mechanism shifts are independent, which we formalize using the algorithmic notion of independence. We introduce an approach for causal discovery beyond partially directed graphs using Gaussian process models and give conditions under which we provably identify the correct causal model. our experiments, we show that our method performs well in range of synthetic settings, on realistic gene expression simulations, as well as on real-world cell signaling data.
Introduction
Most of statistical learning theory rests the assumption that all data is i.i.d. and comes from single distribution. In reality, this assumption rarely holds: observations often stem from heterogeneous environments, different time domains, or interventional experiments. This results in non-i.i.d. data which may contain spurious correlations, such that naive analysis could be subject to serious learning bias Recent research tackles this problem via causal discovery, where given different context distributions, we want to discover robust, causal relationships that transfer to novel conditions 3 Existing approaches however commonly discover only an equivalence class of the true model 4 Here, we investigate under which conditions we can identify causal directions.
To determine causal orientations, Schölkopf al. [1] proposed the Sparse Mechanism Shift (SMS) hypothesis, which asserts that distribution shifts are a consequence of small number of causal mechanism changes. It relies the idea that causal functions exhibit robustness contexts, whereas spurious correlations typically fail to generalize to modified conditions 33 10 II While the SMS assumption permits causal identification via counting of distribution shifts (12 this approach is limited to settings where only a subset of the causal conditionals change, does not apply in the i.i.d. case, and needs conditional independence tests in practice, which suffer from multiple testing problem and, depending on the use case, limited power [5). To address these issues, we propose a functional modeling approach based on algorithmic independence and give identifiability guarantees under general assumptions. Instead of counting mechanism changes, our approach identifies the model that achieves the most succinct lossless description of the data.
different
To illustrate this idea, we consider three variables in five environments (Fig. The environments correspond different conditions that we observe our system in, such as interventional experiments in genomics [16] [7). In our example, there exists some mechanism responsible for generating Y from its cause X which we call f. It remains the in Contexts 1-4, even when the underlying causal mechanisms and hence distributions of the covariates X, Z differ (/1), and only changes in
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

-10*
-10
Proposed score LiF)
3.6
7, noncausal
Proposed score L(D)
3.6
Contest 4
Context 5
3.4
X,
3.1
3.2-
3
3
Z
5
# Functions
[f] for
#
Flnnctions for
(a) Causal model for non-i.i.d, data. (b) Covariate shift in one context. (c) Covariate shift in all contexts.
Figure 1: Given non-i.i.d. data from different contexts, we are interested in the mechanism f that generates a variable Y and that may change in one or more contexts (a). We consider varying number of causal functions f. modeled through a Gaussian process, in the causal (green) and anticausal (red) direction potential models and measure how succinctly the models encode the data (L). Here, we find that Y has cause and a small number ||] of different mechanisms (green star). As the causal mechanism of Y changes independently of the mechanisms generating X and Z, this holds regardless of whether X, undergo distribution shifts in one context (b) or in all contexts (c).
Context result of direct intervention (f2). Intuitively, to most concisely describe the data, we will need two functions in the causal direction, fewer would underfit, and more overfit. To capture this, we propose a score that quantifies how succinctly a model can describe the observed distributions. We show in Fig. ((b) that it identifies the ground truth (indicated by a star symbol).
To explain why anti-causes model from Z Y (red) fits the data less effectively than the causal one (green), we compare two cases. Fig. [(b] depicts the case where we change the generating process of covariates X and Z in only context, while in Fig. [(e] we do in all five contexts. Changing these processes does not directly affect how Y is generated, and hence the true causal model permits equally succinct descriptions for both cases (green curve). In the anti-causal direction, however, such an invariant does not exist; in fact, by changing the distribution of X and Z in all five contexts we created situation where five different functions are needed describe from Z, and none of these can as cleanly separate signal from noise as in the causal direction. As result, we see much worse description lengths for the anti-causal direction (red curve). We conclude that the causal mechanism for Y offers a succinct explanation because it is independent of the mechanisms for X and Z. This connection between the independence of mechanisms and succinet descriptions will be the focus of our analysis.
follows. We show how the algorithmic model of causation can precisely spec- ify which kinds of causal models are permissible for set of variables observed over multiple contexts. Based on this framework, we propose scoring criterion under Gaussian process models [18]. We show that our score is theoretically sound by giving general conditions under which it identifies causal models beyond partially directed graphs. Based on our theory, we introduce the LINC approach for Learning causal models under INdependent Changes, In empirical evaluations, we confirm that LINC works in practice, and show that in contrast to competitors, is robust various settings including semi-synthetic gene expression data [19] as well as real-world protein-signaling data [20]. We include all proofs, code, and data in the supplementary material.
Our contributions
2 Causal Model and Assumptions
We begin by stating our assumptions and causal model. Throughout this work, consider set of continuous variables E Rd. We observe these in multiple contexts c C. For given set of contexts C, we represent the assignment of samples to contexts using categorical variable C. We write (e) for a dataset in one context. Whereas the data points E X()) are i.i.d, samples from distribution P(X c), the overall data is not necessarily identically distributed. We aim to understand this data through causal model, as we describe next.

---

2.1 Problem Setting and Problem Statement
We assume that we can describe the true causal structure over the observed variables by directed acyclic graph (DAG) G (X,E) with node set X and edges (X) ) E & whenever X; causes X₃. As standard in causal discovery [O], we assume that the relationship between X; and its parents given by a function f.
x
= 1 (paf: No) where N, IL (pa. CC)
for each context c. We hereby assume causal sufficiency, i.c. that unobserved variables exist. Whereas the structural equations depend on the context, the causal structure G' is shared in all contexts. Previous work shows that variable C' into conventional causal discovery methods. In particular, the M--Markvv Equivalence class (N-MEC) of G, a variant of MECs to encompass interventions, identifiable [6]
discover G up to equivalence class by integrating a context
While graphical models are essential, we place emphasis on understanding the generating process of each variable. For given variable X,, consider mixture of different causal mechanisms Importantly, each may apply to one context or remain invariant over multiple contexts. To model this situation, let πI; (11, mo Tm) be partition of C into disjoint, nonempty sets such that
f/
,(C²) for (c(cc) =1,(('',
where II, is the unique set E II, containing c. We thus write s( for the invariant function f!( when E n, and similarly (*) for the pooled data from all contexts π. To ease notation, we write its distribution P(X x) = P(X C E 7). This results in a set of functions
(T)) (J, (m)) ((( (Tm
We obtain such partition of the contexts for each variable and denote the set over those partitions by II [II, : X; E X.. Our structural equations can thus be written as
x ((x)) (pa Ne) for c
(1)
for each iT E IT, with independent noise N₂ ILL (paç: C). We remark that by assuming the noise N; to
be independent of the environment, we follow how related work characterizes environments 2 as differing in distribution due to changes in the conditionals P(X, pa independently of the exogenous noise variables N,, for example, due to soft intervention on X;.
With the above, we can now informally state the problem that we want solve.
Problem Statement (Informal). Given data X over environments we want to find
a (sparse) graph G
a set II of partitions II; O into (few) disjoint sets a set of (simple) functions fr
describing the causal mechanism generating our data X.
To formalize this problem, we next explain the principle of independence of causal mechanisms.
2.2 Algorithmic Independence Causal Mechanisms
We base approach the principle of Independence of Causal Mechanisms (ICM, [10). Different types of independence have been proposed in the literature. Most previous work considers statistical independence 4 21], but the conditional independence constraints present in observational data only permit the identification of DAGs up to a MEC unless we make restrictive assumptions 3
13
This has sparked interest in algorithmic independence as alternative formulation 23 27 We introduce this concept here and extend it to multi-contn distributions.
With the idea that causal mechanisms offer simple explanations of complex phenomena, Janzing and Schölkopf (23) postulate that they correspond to simple programs computing each variable X; from its causes ç where programs generating different variables X, do not share information.

---

To make this precise, we revisit several concepts. Kolmogorov complexity (x) defines the length of the shortest program p that computes a string a E {0. 1} on universal Turing machine and halts (28). For distribution P. Kolmogorov complexity is the length of the shortest program able to uniformly approximate arbitrarily well,
K(P) min Upl Vy u(p. P(y) - 1 pE(0.1)-
Using K and towards defining algorithmic independence, we define algorithmic mutual informa- tion [23]. For two binary strings the algorithmic mutual information between æ, is given by TA () K ((r) + K(y) - K (I. 3) For distributions P, Q, we can state follows.
Definition (Algorithmic Mutual Information two distributions P and Q is given by
28
The algorithmic mutual information between
:=P::))=K(pp) K(Q P")
where pa is the shortest algorithmic description of P.
Two strings x, algorithmically independent if (a v) _ holds (up to additive constant that is independent of z, y), where we write LA (..;..;; 111;....2, un) if the corresponding strings are pairwise independent. Analogously, set of distributions P. are jointly independent when
IA(Pii 0.
When the mutual information LA between different causal conditionals vanishes, we can characterize them as independent. The algorithmic causal Markov Condition 23 states precisely this.
Postulate 2.2 (Algorithmic Markov Condition for Changing Mechanisms). Let (G, II) be causal model with DAG G. partitions II, and structural equations as in Eq. Then (G, II) is valid causal hypothesis only if the following equivalent conditions hold,
1. All causal mechanisms J in the model are jointly algorithmically independent. That is,
La([P(X, paς,,) m)); : (L..,,,,,,...... +1.))
(2)
2. The causal mechanisms I in the model describe the observed distribution most concisely. That is, the shortest description of P(X) across all contexts E C is given by writing each X; as a function of ç in each group π E I1I,
K(P(X)) - ΣΣ K(P(X, paç, ,))
sEll
where # denotes equality up to additive constans.
The inner term in Eq. (2) ranges over the conditionals P(X; pa. .T) for each variable X; in each
group of contexts æ E IT,, where we omit indices of for ease of notation. Overall, Postulate 2.2 states that the causal mechanisms correspond to programs that do not share any information (Eq. and that describe the observed distributions most concisely (Eq. (3).
We will use the formulation in Eq. 3 which directly uses Kolmogorov complexity of conditionals. Due the halting problem, we cannot compute Kolmogorov complexity for arbitrary programs (28). but by restricting the class to be tractable, we can approximate it from above. A statistically well- founded manner of doing so Minimum Description Length (MDL) [29]. For fixed class of models, MDL defines description length L of encoding dataset X together with its optimal model,
L(X H) min (- log P(X ()) T.h))
kEH
Regarding the choice of H. we are interested in functions / that are both expressive but also allow us to measure their description length. Gaussian processes naturally fulfill these requirements [18 29), making them fitting choice for our approach. We briefly introduce them next.

---

2.3 Gaussian Process Functional Model
Gaussian process (GP) is a collection of random variables X, any finite number of which have joint multivariate Gaussian distribution [18]. Each variable represents the value of a function f at single location z. We write functions drawn from GP
f (p((m()),
for mean function mxx) m(x'))]. Viewed differently, a GP can also be expressed as linear regression / Σ ago; with potentially infinitely many basis functions Φ;- Given finitely many data points (Ir Va), we write
[x](())] and covariance kernel x(r,x')
predictions as a linear combination of a finite number of kernel functions <((z4) .) centered on the observed points r; [18]
((x) Σ agn((1122)
(4)
with a = =K (K+22))- where K the Gram matrix of x. with Kú; = k(x;, xy). and o² a parameter. This formulation will be useful when we consider the description length of GPs later.
Regarding the richness of the function class, given kernel K, one can construct a reproducing Hilbert space Hu. which is the smallest Hilbert space containing all finite expansions of the For some kernels, such the radial basis function (RBF) kernel k(z,, XTy)
form in Eq.
exp( - 27 ||=; xyy 11) X >> O which we consider here, it is known that H. dense in the space of continuous functions [8]. That is,
approximate these functions up arbitrary precision using a GP [30]. Using GPs, we now state our functional model as follows.
Assumption (Functional Model with Changing Mechanisms). Given DAG G and partitions II, we assume the functional model
X -f (pa + N₁ for c n,
(5)
where т E II; is a group, 1! E H. is a GP, and N, is independent noise N; IL (pa C).
We point out that the above makes additive noise assumption as is standard in GP modeling. Having stated the ICM assumption and our functional model, we are ready to introduce our approach.
3
Learning Independent Changes with LINC
We now introduce a score to instantiate Eq. 3 for GPs and give an analysis of its properties.
3.1 Measuring the Complexity of GP Models
To define the ability of our model to succinctly describe a given dataset, we need to address the complexity GP f. Despite the richness of Hg. the complexity any ʃ E Hr can be readily measured by its squared norm I For functions inferred from finite amounts data, as in Eq. 44 we can compute this norm ||] from the quantities K and a as 29
|l
Ka.
Consider now the model class H. of GPs and a target variable X,, For given subset X S of predictors, we can fit GP regression X + X; Kakade et al. [31 show that the Bayesian MDL score for this GP model is given by
( (- log P(X, Xs) + 11)))) + R(Xs).
L(Xs,X, X, H.)) = min
(6)
JEH,
The score balances the data fit of the GP regression model / with its complexity, || a Ka. The remaining penalty R(Xs) is independent of the minimization over S,
R(Xs)
log det(o -2 +1)
where Ks is the Gram matrix when is applied to Xs. We write L(J) L(Xs, X² H.)) when the context clear, and L.G IT) as the summed description length for a given causal model. By Eq. 3 choose the model with the smallest description length as causal hypothesis.
5

---

Problem Statement (Formal), Given data X over environments C we want to find the graph G, partitions II and mechanisms (( minimizing the score L,
č arg min LIG cn
To show that we recover the correct causal structure with this objective, we give identifiability results.
Identifiability Results
Here, we give conditions under which we can identify the true causal model using our score function. begin by showing that we can discover the causal DAG in the correct Markov Equivalence class (MEC) under the following general assumptions.
Assumption 2 (Sufficient Capacity). For each there exist functions f.()) Hr Eq. 5 holds.
This recalls the assumption that our functional model is well-specified.
Assumption (Causal Minimality). For all π E II, p(() is not constant in any of its inputs.
The above is a toned-down version of the faithfulness condition, ensuring that every parent of X; has an influence on X,. Without this, it would be impossible identify the complete set of parents.
Assumption (II-Faithfulness). If n' + a E II, then !!²) # f!!²)
This assumption guarantees the uniqueness of each partition. Without it, interventions would not necessarily lead to changes causal mechanisms, and make identification thereof impossible.
With this, we can state our first identifiability result as follows.
Theorem 3.1 (Identification of MECs). Let Assumptions 1-4 hold and let X be sufficiently small. Then the estimates G, II that minimize our score L,
G = min LIG
G.
recover a DAG G G² in the Markov Equivalence class of the true DAG G", as well as the true partitions I for each node with probability 1
P(
Next, we show that under independent mechanism shifts, we can also identify the fully directed G*. To correctly identify the direction of all edges in the discovered network, we need the following assumption that the causal mechanisms are independent of each other and change independently. Assumption (Independent Mechanism Shift). For all * j (C,(C) IL (C).
We can now show that as we observe more contexts, |C| + co, our score identifies the correct DAG. Theorem 3.2 (Identifiability from independent changes). Let Assumptions 1-5 hold. Then for sufficiently small, where a hyperparumeter bounding the score differences of G, G* we can identify the causes paς and partition πI of each X, in the causal model ,G*,II*) with probability 1,
lim P -(,= 1C|+000
In particular, the fully directed network G is identifiable
The requirement |C] + oo is necessary to turn the assumed independence of causal conditionals across different contexts into empirically testable statistical criterion. That is, to guarantee that the model is indeed identifiable, we need either the distribution assigning contexts to partitions, or a guaranteed representative sample from the distribution, which we only obtain in the limit. Essentially, this is a frequentist approach, allowing us not to require the distributions for the partitions themselves.
We can, however, provide further probabilistic guarantees for finite numbers of contexts. To be able reason about probabilities different causal structures, we need to ensure that as we observe more contexts |C], the number of sets in the partition remains fixed. We hence assume that for each X,, the contexts fall inside one of a fixed number sets B,,,..., Bi,;; which can thought of as bins that fix the sizes of our partitions, and thus bound the number of mechanism shifts per variable.

---

Assumption 6 (Fixed Partition Sizes), For each X,, there exists finite number of sets B ... Br such that Piş == P(C E Br,z) > 0.
The assumption can be understood in frequentist sense, in that on average each possible causal mechanism for each variable occurs at least a constant fraction of all samples. For example, if we study the differences between treatments in different hospitals, then data would be obtained from the same set of hospitals, rather than by the addition of new hospitals. With this, are able to give tighter bound as follows.
obtain more data, these
Theorem 3.3 (Identifiability in the finite context setting). Let the Assumptions of Theorem 3.2 as
well as Assumption 6 hold. Let p = min;,5 Pij be the minimum probability for a context to fall into one of the bins Big Then if [C] 2 -2p loogp)) > we have
P( = G f = IT' = Ω (exp (-18)e
where c= p² |C] log and |اح] is the number of edges in G*.
The dependence of the bound on E] is reasonable. The sparser the graph G", the fewer edges that need be directed in its MEC. Note furthermore that the fixed size of the partitions likely not strictly necessary, and as long that the bounds above apply to the case where we have no active control over intervention targets, i.e. when mechanism shifts occur randomly. While active intervention design allows identification using a smaller number of interventions
decays sufficiently slowly, Theorem 3.3 will still likely hold. We also note
(32, we often cannot ensure full interventional control in practice; for example, gene editing technologies such as CRISPR- -ac gene-editing are known to have severe off-target effects [6) that may not be known a priori.
In what follows, we describe how to put our theoretical insights into practice.
3.3 Discovering Independent Changes with LINC
In summary, our approach, called LINC (Learning causal models under INdependent Changes), aims to discover a mixture of mechanisms that together most succinctly describe multi-context data.
To do so, we discover the causal DAG G and partitions II that minimize Eq. 77. To compute L. for given model (G, II), we consider each causal mechanism f(r) in the model and fit a GP regression predicting X; from its causes paf We compute the MDL description length of this GP as in Eq. (6). We do so in each group of contexts in II, and each variable in G' to obtain the overall score L(G, II).
To discover the partitions for known graphical model G, we suggest an exhaustive search whenever feasible, given that the number of different contexts that we have access to may be small in the typical use case 20). As exhaustive search over partitions becomes prohibitive for larger numbers of contexts, we propose a greedy variant in Appendix B It relies on the no-hypercompression inequality (29 that allows defining a scoring function for pairs of contexts. This pairwise measure can be used together with clustering approach to discover a partition of the contexts in a greedy manner.
We also face the search for DAG G. Given the large search space over causal DAGs, existing algorithms are of a greedy nature, such as the score-based greedy equivalence search (GES, (33) and its generalized version GGES that can be used with general scoring functions so long they [15]. In principle, we can use the MDL score L as a plug-in estimator in GGES to discover a MBC of the true graph. However, there exist many greedy approaches to discover MEC of G from multiple contexts (4/9), whereas discovering relationships beyond MEC is relatively underexplored [3). we put our emphasis the latter and discover the best causal DAG within given Markov equivalance class in our experiments, following the literature [3]
locally consistent
Finally, also adress the computational burden associated with score L due to the sample complexity of GP regression. To alleviate this, we leverage the Random Fourier Feature (RFF) approximation, which allows to express the GP kernel through Fourier transform [34]. We adapt our scoring function accordingly to use the approximated RFF kernel. We call our main approach LINC and include comparison to the variant LINCRFF in our evaluation.
We provide the details of our algorithms, a computational complexity analysis, and the adaptation to RFFs in the supplementary material. In the remainder of our work, we focus on evaluating LINC empirically against relevant related work, which we survey in the following section.
7

---

LINCar -- LINCOFF
MSS
MC
Pooled PC 4
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0-
6
12
3
9
12
15
Contexts CI
Variables [G]
Changes |S]
Conditions
[C]
(a) Synthetic Data.
(h) Gene Expression Data.
Figure 2: LINC discovers causal models beyond Markov Equivalence. We report the F1 scores for discovering the causal direction of each edge in a random DAG G. where shading shows confidence regions and dashed horizontal lines illustrate random guessing. In (a), we consider synthetic data over different contexts where |S| variables per context undergo mechanism shifts, starting from [C| = 5, G = 6 and |S| = 2. In (b), we mimic real-world gene expression dynamics by simulating data with SERGIO [9 from random network over [C| - genes, which we observe in conditions gene per condition.
C with knockout intervention
4 Related Work
Discovering cause-effect relationships is of great interest in many applications, and there exists growing literature on how we can do so from observational data [T]] Most well-known methods can be categorized either as constraint-based such as the PC algorithm [35). or score-based, such
as GES [3). Given purely observational and identically distributed data, however impossible to make definitive statements about the causal structure [TO. Non-i.i.d. data carries information about how the system responds to external intervention or noise shifts, and hence often allows to infer causal directions more accurately [6 36). We summarize approaches to do so here.
prominent idea in causal inference from multiple contexts that causal mechanisms remain stable, i.e. invariant, under distribution shift [37] and there exist several causal discovery methods that use invariance as an asymmetry between causal and non-causal orientations [8 40 Invariance may be violated when variables are subject to interventions, as is common in biology [20]. Methods that can discover causal relationships from a combination of observational and interventional data 441443 often assume known intervention targets, which is not always realistic [44] Hence, recent research considers multiple contexts with uncertain interventions or mechanism changes. For example, Huang et al. show how to apply the PC algorithm jointly to multiple contexts by introducing context variable. There are similar approaches with different instantiations [50)), all of which however discover causal MECs. A common approach to go beyond Markov Equivalence is functional modelling 15 26
25
45 46), but existing methods that we are aware of are tailored to i.i.d. data.
Finally, recent works tackle causal discovery beyond Markov Equivalence from non-i.i.d. data under the sparse mechanism shift (SMS) ① hypothesis. The Minimal Changes (MC) method [12] and the Mechanism Shift Score (MSS) [3] both count the number of distributional changes across contexts to infer edge directions within MRC. MC assumes linear models, MSS is nonparametric. contribution, we show that regularized scoring functions, such as our MDL-based score, can be used toward the same goal. These scores have been shown to make use of the independence noise asymmetry on i.i.d. data [25] 47), which suggests that LINC may be more widely applicable than the SMS scores. As MC and MSS are most related to LINC, they will the focus of our evaluation.
our
Evaluation
We consider synthetic, semi-synthetic, and real-world data empirically evaluate LINC and how its performance relates to the state-of-the-art. We make the code and datasets available in the supplement.
Experimental Setup model class, as well as more realistic data following the stochastic differential equations behind gene regulatory networks [19]. Throughout, we use an Erdös Rčnyì DAG model to sample graphs G.
In our experiments, we consider both synthetic data from a known functional
8

---

LINCar @ LINC ar MSS B MC
Pooled PC !
0.6
0.4-
0.2
Soft Intery,
Noise Scaling
Hard Interv.
Dense Shifts No Shifts (L..d.)
Sparse Shifts No Shifts (iid.))
Intervention Types.
(b) Beyond Sparse Shift.
(c) Bivariate Case.
Figure 3: LINC is robust in different settings. We show which methods can discover edges beyond Markov Equivalence robustly. We consider (a) soft and hard interventions on the mechanisms in Eq. 8 (b) dense shifts compared to i.i.d. data, where all ([S) = (C). resp. none ([S) = 0) of the variables change, and (c) bivariate causal discovery the base (S$) = 2) and i.i.d. case ((S) 0).
For the synthetic data, following the literature 4
11
we generate data in multiple contexts using
x
Σ jEPa
w (x(
+ of 1
(8)
with weights wij ~ (0 (10(0.....55 2.5), where noise either uniform or Gaussian with equal probability.
We sample the causal functions f from {=², x5", tanh, sinc]. In each context, we choose a random subset S G of variables that undergo mechanism shift, which is either soft intervention by re-sampling from Eq. (8). noise scaling through o ~ ((2 5). or a hard intervention via waj = 0.
In addition, simulate data with SERGIO [9] to generate single-cell expression data according to a gene regulatory network while modeling the real-world dynamics of gene transcription and regulation using stochastic differential equations. Using random DAG G as the reference network, we generate one observational dataset as well as G interventional datasets, in each of which we keep a different gene fixed to mimic knockout intervention 48
Baselines As a baseline for causal discovery up to Markov Equivalence, we include Pooled PC which pools data from all contexts, augments the system with categorical variable C' that encodes the context and applics the PC algorithm to discover a causal DAG. As we are interested in evaluating whether LINC can orient edges beyond the MEC, we also compare against the linear Minimal Changes approach (MC) [1] and the nonlinear Mechanism Shift Score (MSS) B that are based on mechanism shift counting. We instantiate MSS with the Kernel Conditional Independence (KCI) test and use the soft score variant, which Perry et al. 13 show to consistently outperform competitors.
Causal discovery beyond MECs As our main experiment, we evaluate whether LINC can discover causal edge orientations in non-i.i.d. data. We sample DAGs G of size G = 6 with edge density p 0.3 and generate data in |C| contexts, with |c| 500 samples and |S| 2. We start from the correct MEC, use each method to discover DAG, and report Fl scores over edge directions.
We report the results in Fig. (aa As pooled PC discovers MEC jointly from all contexts, its Fl scores tend to 0.5, which can be achieved by not orienting any edges in the MEC as this results in recall 0.5 expectation (dashed lines). In contrast, MSS, MC and LINC discover all edge orientations given sufficiently many contexts [C], variables G), and changes JS]. The differences are most pronounced for small DAG sizes, resp. contexts. In particular, only LINC learns additional edge directions from i.i.d., single-context data since the competitors rely purely on mechanism shifts. The RFF variant of LINC works surprisingly well but is ultimately similar to GPs for large [C].
Overall, LINC compares favorably against its competitors in all settings. We defer results with varying edge density p and sample size |c), as well scalability with [C] and |G| to Appendix B
Gene regulatory networks Next, we evaluate the methods on gene expression data that we generate
with SERGIO. We show the F1 scores on edge directions in Fig. 2 dependiig on the number of conditions [C). While MSS is the closest competitor to LINC on synthetic data with soft interventions (Fig. 2(a) the hard interventions in this experiment result in poor performance (Fig. 2(b) Despite

---

assuming linearity, MC performs well, which suggests that it detects mechanism shifts even when its functional model is likely misspecified. It performs comparably to Pooled PC, where both benefit from an increased number of variables and conditions. L.ICC outperforms the competitors, the difference being most pronounced when it observes only few conditions.
Causal discovery beyond SMS
Besides confirming that LINC can handle different generating processes, we are also interested in its robustness w.r.t. different types of distribution shifts that may occur. In Fig. [[a]] we compare the soft interventions considered so far with noise scaling and hard intervention. To confirm our observations that LINC generalizes to settings where the sparse shift principle is not applicable, we compare dense shifts |S| |C] to the case without any changes |S| = in Fig. (()] As expected, the competitors roughly match the base MEC in the i.i.d. case, whereas LINC pertorms well. This observation is in line with recent theoretical results [25] that MDL-based scoring functions can exploit the additive noise asymmetry 45 49 on i.i.d. data. Lastly,
LINC also performs remarkably well compared to the baselines for causal direction determination
between pairs of variables, as we show in Fig. 3(c)
Cell signalling pathways Finally, we evaluate LINC on real-world data over eleven proteins and phospholipid components, with the goal of mapping their signaling pathways in human im- mune cells [20]. To properly under- stand how the components of such system interact, it can be indicative how the system responds to stimula- tory and inhibitory cues, which Sachs al. (20) added to the system in mul- tiple experiments. We run LINC and competitors on data from all contexts, without providing information about the interventions. We show the best DAG that LINC identifies within the true MEC in Fig. 4 We color edges that Sachs et al. [20] report as causal
Mek
Raf
Frrk
TP
FP
PKC
Akt
LINC
14
3
0.90
MSS
12
5
0.83
PIP2
PKA
MC
17
16
0.68
P-PC
15
8
0.75
PI.C..
Pas
PIP
Ink
(a) DAG with LINC.
(b) Edge Directions.
Figure 4: Cell Signalling Pathways. We show the DAG that LINC estimates for the cell cytometry data (a) in comparison to competitors (b). Green links are causal (TP) and orange edges are anticausal (FP) according to the literature 20
in green and edges with opposite orientation in orange. Except for three, LINC discovers all directions
correctly (Fig. 4(a), leading to the highest performance compared to the competitors (Fig. 4(b).
6 Discussion and Conclusion
In this work, we consider causal modeling of data from multiple environments where unknown causal mechanism changes may exist. Our interest in this setting motivated by the prevalence of distribution shifts and heterogeneity in real-world applications, as well as by the need to analyze interventional data in biology, where modern gene editing and measurement technologies allow collecting large-scale experimental data [50]. Here, we showed that viewing independence of causal mechanisms from an
-eeeorrrtiitttttiicicci perspective allows us to analyze such data in a unifying way. With LINC, we proposed a nonlinear functional modeling approach using Gaussian processes. We showed theoretically that we can use it to identify causal models with independent changes, and demonstrated in practice that it is applicable to settings beyond those where the sparse mechanism shift principle applies, and that it gives insight into biological data with unknown intervention effects.
While we focused on theoretical guarantees in this work, developing efficient algorithms for causal discovery an important aspect of future work. Given the shift of research attention in causal discovery from i.i.d. to non-i.i.d. data, we face not only the problem of efficient search for DAG structures but in addition the problem that there may be multiple causal mechanisms per variable, which adds an additional layer of complexity. Towards efficient search for partitions, we propose search algorithms inspired by clustering in the supplementary, and establishing approximation guarantees for these methods is worthwhile direction of future work. Other future directions include extending our theory to latent confounding, considering the situation where the split of the data into different contexts is not known to us, applying insights causal representation learning.
10

---

References
[1] B. Schölkopf, F. Locatello, Bauer, N. R. Ke, N. Kalchbrenner, A. Goyal, and Bengio.
Toward causal representation learning. Proceedings of the IEEE, (995))612-644 2021. doi: 10.
1009/PPRC..201.33000 .3058954. URL URL http:::t////eeeeellorr ieeeeiieeee ieee. org www./r//taaaae.... /ttpsssttp////// stammm/////mppp.mmm jsp?
arnumber=9368994
[2] Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant Risk Mini- mization. CoRR, abs/1907 022933, 2019.
[3] J. Peters, P. Bühlmann, and N. Meinshausen. Causal inference using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society: Series (Staristical Methodology), 78(5):977-112, 2016. doi: 10.1111/ssb.1116. URL http: (with discussion).
//arxiv. http///g/////aeeee 01332
[4] Biwei Huang. Kun Zhang. Jiji Zhang, Joseph Ramsey, Ruben Sanchez-Romero, Clark Glymour, and Bernhard Schölkopf. Causal discovery from beeerogencous/honsattiooarrr data. Journal of Machine Learning Research, 21(1), 2020. ISSN 1532-4435.
[5] Joris Mooij, Sara Magliacane, and Tom Claassen. Joint causal inference from multiple contexts. Journal of Machine Learning Research, 21:99:1-99:108 2020.
[6] Amin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Causal discovery from soft interventions with unknown targets: Characterization and learning, In Proceedings of the Conference on Neural Information Processing Systems (NeurIPS), pages 9551-9561. Curran, 2020.
[7] Chandler Squires, Yuhao Wang. and Caroline Uhler. Permutation- causal structure learning with unknown intervention targets. Proceedings of the International Conference on Uncertainty in Artificial Intelligence (UAI), pages 1039-1043 PMLR, 2020.
[8] 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 Interventions. arXiv, 100.000075aaxxi.11100..00
October 2019.
[9] Philippe Brouillard, Sébastien Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien, and Alexandre Drouin. Differentiable causal discovery from interventional data. In Proceedings of the 34th International Conference on Neural Information Prucessing Systems, NIPS'20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
[10] Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, 2nd edition, 2009.
[11] Jin Tian and Judea Pearl. Causal discovery from changes, 2013.
[12] AmirEmad Ghassami, Negar Kiyavash, Biwei Huang, and Kun Zhang, Multi-domain causal structure learning in linear systems. In Proceedings of the Conference on Neural Information Processing Systems (NeurIPS), volume 31, 2018.
[13] Ronan Perry, Julius Von Kügelgen, and Bernhard Schölkopf. Causal discovery in heterogeneous environments under the sparse mechanism shift hypothesis. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Proceedings of the Conference on Neural Information Processing Systems (NeurIPS), 2022. httpttppss//ppeeeriiee.... net/ffrum? id=kFRCvpubDJo
[14] Antti Hyttinen, Frederick Eberhardt, and Matti Järvisalo. Constraint- based causal discovery: Conflict resolution with answer set programming. In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, UAI' 14, page 340-349, Arlington, Virginia, USA, 2014. AUAI Press. ISBN 9780974903910.
[15] Biwei Huang, Kun Zhang, Yizhu Lin, Bernhard Schölkopf, and Clark Glymour. Generalized score functions for causal discovery. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '18, page 1551-1560,, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450355520. doi:
00.1145/32198199322211 URL https: /ttp:::///oorrooo 110.00..111112111180 3220104
11

---

[16] Yanfang Fu, Jennifer Foden, Cyd Khayter, Morgan Maeder, Deepak Reyon, J Joung, and Jeffry Sander. High-free frequenyyy off- aff-target mutagenesis induced by crispr-cas nucleases in human cells. Nature biotechnology. 31, 06 2013. doi: 10. 1038//bb..62...
[17] Antonia A. Dominguez, Wendell A. Lim, and Lei Qi. Beyond editing: repurposing crispr-cas9 for precision genome regulation and interrogation. Nature Reviews Molecular Cell Biology, 17 (1):5-15, 2016. doi: 10. 101100/mm..015.... URL https:/p::///o org/ 10. 1038/108//// nrm 2015.
[18) Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2005. ISBN 026218253X.
[19] Payam Dibaeinia and Saurabh Sinha. Sergio: single-cell expression simulator guided by gene regulatory networks. Cell systems, 2020.
[20] Karen Sachs, Omar Perez, Dana Pe'er, Douglas Lauffenburger. and Garry Nolan. Causal protein-signalngg networks derived from multiparameter single-cell data. Science, pages 523-9, 9, 2005.
[21] Siyuan Guo, Viktor Tóth, Bernhard Schölkopf, and Ferenc Huszár. Causal de finetti: On the iden- tification of invariant causal structure in exchangeable data, arXiv preprint arXiv:2203.15 15756 2022.
[22] Bernhard Schölkopf, Dominik Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris Mooij. On causal and anticausal learning. In Proceedings of the International Conference on Machine Learning (ICML), (CML'12, pages 459-466, Madison, WI, USA, 2012. Omnipress.
ISBN 9781450312851.
[23] Dominik Janzing and Bernhard Schölkopf. Causal inference using the algorithmic markov condition. IEEE Transactions on Pattern Analysis and Machine Intelligence, (6:5168-5194, 2010.
[24] Jan Lemeire and Dominik Janzing. Replacing causal faithfulness with algorithmic independence of conditionals. Minds and Machines, 23, 2013.
[25] Alexander Marx and Jilles Vreeken. Identifiability of cause and effect using regularized regression. In Proceedings of the ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD). ACM, 2019.
[26] Osman Mian, Alexander Marx, and Jilles Vreeken. Discovering fully oriented causal networks.
In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2021.
[27] David Kaltenpoth and Jilles Vreeken. We are not your real parents: Telling causal from confounded using MDL. CoRR, abs/1900.06950, 2019. URL http:://t////i...o/ org abs/////////90 /901 06950
[28] Ming Li and Paul Vitányi. An introduction to Kolmogorov complexity and its applications. Springer Science & Business Media, 2009.
[29] Peter Grünwald. The Minimum Description Length Principle. MIT Press, 2007.
[30] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Information- thecorctic regret bounds for gaussian process optimization in the bandit setting. IEEE Transactions Information Theory- TI7, 58:3250-3265. 05 2012. doi: 10. 10.1009/112011121822000
[31] Sham Kakade, Matthias W. Seeger, and Dean P. Foster. Worst-case bounds for gaussian process models. In Y. Weiss. B. Schölkopf. and J. Platt, editors, Pro- ceedings of the Conference on Neural Information Processing Systems (NeurIPS), vol- ume 18. MIT Press, 2005. URL https:://proceedinggs www.:r/eeeeiinn...eer........... cwtuarppp.ccppape/220550/ pdf
[32] Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoming, 55(4):926-939, jun 2014. doi: 10. 10.10166..jar.2013111. URL.tttss: pesttps://doi..oo 1011 wij.....a................ 2013
11. 007
12

---

[33] David Maxwell Chickering. Optimal structure identification with greedy search, Journal of Machine Learning Research, 3:507-554, 2002.
[34] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Proceed- ings of the Conference on Neural Information Processing Systems (NeurIPS), NIPS'07, 07, page 1177-1184, Red Hook, NY, USA, 2007. Curran Associates Inc. ISBN 9781 7781605603520.
[35] Peter Spirtes, Clark Glymour, Richard Scheines, and David Heckerman. Causation, prediction. and search. MIT Press, 2000.
[36] Karren D. Yang, Abigail Katoff, and Caroline Uhler. Characterizing and learning equivalence classes of causal dags under interventions. In Proceedings of the International Conference on Machine Learning (ICML., 2018.
[37] Jonas Peters, Dominik Janzing, and Bernhard Schlkopf. Elements of Causal Inference: Founda- tions and Learning Algorithms. The MIT Press, 2017. ISBN 0262037319.
[38] Sarah Mameche, David Kaltenpoth, and Jilles Vreeken. Discovering invariant and changing mechanisms from data. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge
Discovery and Data Mining, KDD '22, page 1242-1252, New York, NY, USA, 2022. Associa- tion for Computing Machinery. ISBN 9781 450393850. doi: 10.1145/3334678.33394799 URL https://doi. org/10. 1145/3534678 353394777777737377999
[39] Christina Heinze-Deml, Jonas Peters, and Nicolai Meinshausen. Invariant causal prediction for nonlinear models. Journal of Causal Inference, 6(2), 2018.
[40] Dominik Rothenhäusler, Nicolai Meinshausen, Peter Bühlmann, and Jonas Peters. Anchor regression: Heterogeneous data meet causality. Journal of the Royal Statistical Society: Series (Statistical Methodology). 83(2):215 246, 2021.
[41] Daniel Eaton and Kevin Murphy. Exact bayesian structure learning from uncertain interven- tions. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 2. pages 107-114, San Juan, Puerto Rico, 2007. PMLR.
[42] Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs. Journal of Machine Learning Research, 13(1):2409-22) 22649,224444444 aug 2012. ISSN 1532-4435.
[43] Yuhao Wang. Liam Solus, Karren D. Yang, and Caroline Uhler. Permutation- based causal inference algorithms with interventions. In NIPS, 2017.
[44] Xiao-Hui Zhang, Louis Y Tee, Xiao-Gang Wang, Qun-Shan Huang, and Shi-Hua Yang. Off- target effects in crispr/cas9-mediane genome engineering. Molecular Therapy Nucleic Acids, 4:e264, 2015. ISSN 2162-2531. doi: https://doi.or//10. 1ttt:////0...00000mmm.......333 URL https://wwwt wwweeeneeweeeecccooeeeeeeeeeeeee http:///wwaaaaa.......aaaaaaaaaa
[45] Jonas Peters, Joris M. Mooij. Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. Mach. Learn. Res., 15(1):2009-200 2053, jan 2014. ISSN 1532-4435.
[46] Alexander Marx and Jilles Vreeken. Telling cause from effect by local and global regression. Knowledge and Information Systems,
2019.
[47] Alexander Marx and Jilles Vreeken. Formally justifying MDsed inference of cause and effect, 2021.
[48] Alexander Hägele, Jonas Rothfuss, Lars Lorch, Vignesh Ram Somnath, Bernhard Schölkopf, and Andreas Krause. Bacadi: Bayesian causal discovery with unknown interventions. In Francisco Ruiz, Jennifer Dy, and Jan- Willem van de Meent, editors, Proceedings of the In- lernational Conference on Artificial Intelligence and Statistics (AISTATS), volume 206 of Proceedings of Machine Learning Research, pages 1411-1436. PMLR, 25-27 Apr 2023. URI. https: https://proceeedings mlr, pttsss//200/aageee22222 html
13

---

[49] Jonas Peters, Joris M. Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. Journal of Machine Learning Research, 15(58):2009-2553 2014.
[50] Atray Dixit, Oren Parnas, Biyu Li, Jenny Chen, Charles Fulco, Livnat Jerby-Aron, Nemanja Marjanovic, Danielle Dionne, Tyler Burks, Raktima Raychowdhury, Britt Adamson, Thomas Norman, Eric Lander, Jonathan Weissman, Nir Friedman, and Aviv Regev. Perturb-seq: Dis- secting molecular circuits with scalable single-cell ma profiling of pooled genetic screens. Cell, 167, 12 2016. doi: 10.10166f.cel1.2016.. 1.038.
[51] S.L. Lauritzen. Graphical Models. Oxford Statistical Science Series. Clarendon Press, 1996. ISBN 9780191591228, URL httptt:://oook..goottt deooglee.d/bbookssidiiiiii
[52] J Bernardo, J Burger, and ADEM Smith. Information-theorree characterization of bayes performance and the choice of priors in parametric and nonparametric problems. In Bayesian statistics, volume 6. Oxford Univ. Press, 1998.
[53] Atsushi Miyauchi, Tomohiro Sonobe, and Noriyoshi Sukegawa. Exact clustering via integer programming and maximum satisfiability. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018. doi: 10.1609aaai. v3211.11519, URL pottpa//oo]: aaai
org/index. php/ AAAI/ arti clw.clleeiiece articeevvie//11111
14

---

A Theory
A.1 Background
We assume familiarity with Markov Equivalence of DAGs in the i.... case, and refer to Lauritzen (1996) and Pearl (2009) for detailed definitions.
For non-i.idd or interventional distributions, identifiability of DAGs extends to an interventional Markov Equivalence class (iMEC) [36 []. This holds for general interventions targeting specific nodes in certain contexts. That is, an intervention targeting the nodes X; for E corresponds to the interventional distribution p(D, which factorizes as follows,
(x)
III P pa II [I paf)) iET
JET
where pd is the observational distribution the case where the observational context is unknown, and formally define the MEC that one can identify from multiple interventional distributions with unknown targets the rf-MEC (6]
336 Jaber (020) generalized the above address
In our work, we take a different perspective where instead interventions with specific targets, we consider mechanisms that are invariant in group of contexts change independently. Similarly to the graphical representations of interventions through latent variables 7 6), we can also represent our partitions as latent variables (C)). We will shortly show that we can discover both DAG in the correct Markov Equivalence class as well the correct partition for each node.
To do so, an important property of our MDL score that we will need is information consistency 229 according to the following definition [52].
Definition A.1 (Information Consistency). A prediction strategy Q is information consistent with respect competitor space Feump if and only if
lim 1 (P(V (,X Q(Y [xx))) 0
20000
holds for all f E Fcomp.
We refer the reader to Kakade et (2005) for proof of information consistency for GP models.
We next move to our main result stating that we can use the MDL score for GP models for causal discovery.
A.2 Proof of Theorem 3.1
We assume a causal model with changing mechanisms as in Assumption T We also recall Assump- tions 3, and The first one ensures that our functional models are well-specified.
Assumption 2 (Sufficient capacity): For each there exist functions y!()) E He such that Eq. (5) holds.
We also make the following assumption to avoid the pathological case that causal variables pa do not affect X,
Assumption 3 (Causal minimality): No f!(T) is constant with respect to any of its inputs.
Similarly, we also ensure that interventions have an effect on variables or, put differently, that mechanism change of f(#) indeed corresponds to difference in distribution of the intervened contexts in म.
Assumption 4 (athhuaith For each ग + n' E Î1, we have f!²) + f!
With these assumptions, we are ready to prove our Theorem 3.1 which we repeat here for ease of access too.

---

Theorem 3.1 (Identification of MECs): Let Assumptions 1-4 hold and let À be sufficiently small. Then the estimates G, II minimizing our L,
G arg min L(G,II)
G.
recover a DAG G ~ G in the Markov Equivalence class of the true DAG G", as well as the true partitions 11; for each node with probability I
~ GG, Gr,
Proof. The idea of our proof is similar those in Yang et al. 336 and Brouillard al. (9] We start by assuming that the correct partition IT" known. Let G be the graph recovered by minimizing as above. We can write the difference in scores as
-xx > E (Px(P(X; paf ,CET); CE (L))) L(G))
(LG)))))))))
mElL
where the dependence on and the functions f(() is left implicit.
Assume that G S G Then at least one of the DKL terms is non-zero, say >> 0. However, since I(G), (( x A, we can find > small enough such that [.(G) - I(( < n, and therefore
T(X;C)= > I(X:").
Now assume that G G. Then in particular there exists for which pa. pa However, from causal Markov condition we know that X; is independent of its non-descendants given
paς". In particular, the KI. divergence is zero. However, then either L(G) L(G*) S( would be constant with respect one its inputs.
From these two cases, therefore follows that G is Markov equivalent to G
For the case where IIf is not known, let II be the set of recovered partitions for each X,. Then fi f II there must at least one for which II, of II; There are two ways in which the partitions can differ.
First, the partition I1, more fine-graiee finegrrined than II; That is, for each x* E II; there exist groups T1,..., & E fi, such that x- = æ1 U... U Ty and further there exists at least one n² for which > 1. For this n²" and associated T1, ..., Ta have before that for sufficiently small À the minimizer for L(X; G) would have be f: -..== = TT However, by assumption (A3) this is not permitted. This case therefore cannot occur.
Second, there could be group π, which intersects at least two different groups nं * m II;
However, from (A3) we know that f. * 1 so that whatever function f we pick in the discovered model, would necessarily lead the wrong distribution for least one of the two groups and therefore positive DxL. term, which as before is sub-optimal for X small enough.
A.3 Proof of Theorem 3.2
For the proof of Theorem 3.2 we require the following formalization of independent changes of mechanisms.
Assumption 5 (Independent Mechanism Shift): For all i イ :i,(C) IL (C)
Under this assumption, we can prove that can identify the full causal model.
Theorem 3.2 (Identifiability from independent changes): Let Assumptions 1-5 hold. Then for sufficienlly small, where is a hyperparameter bounding the score differences of G. G*, we can identify the causes paς and partition II, of each X; in the causal model (G*, II") with probability
lim P( G G - 10
In particular, the fully directed network G* is identifiable

---

Proof. As we have seen from Theorem 3.1 we can identify the correct MEC and II already. Our goal is therefore show that any other G in the same MEC as G will correspond to a II different from II".
Let us consider the target variable X,, We can ask ourselves what happens when an edge X; + Xj misdirected in G. We will show that the misdirected edge will lead wrong partition with probability 1 as |C| co.
To that end, note that when (c) (c) but (c) * 11j(c)) for two different contexts df then in the alternative graph G. the distribution P(X; pa C c) + P(X; pa C' d') is not invariant. Therefore, for each π E II, the number of functions required to model the distribution of X, increases. That is, we require one function for each [c) such that (c) π.
Now, due to (C) IL (C) this guaranteed to be one function for each pair (T, x²) E Π, x fT |C| However, this would lead to the wrong partitions π. * mT,, in contradiction Theorem 3.1 above.
A.4 Proof of Theorem 3.3
We now turn to the probabilistic version of the previous result, for which we need the following assumption.
Assumption 6 (Fixed Partition Sizes): For each X,, there exists finite number of sets B Bi such that Рış P(C e Br,z)= > O.
With this, we can prove Theorem
3.3
Theorem 3.3 (Identifiability in the finite context setting): Let the Assumptions of Theorem 3.2 as
well as Assumption hold. Let p = min; Pij be the minimum probability for a context to fall into one of the bins Big Then if [C] 2 -2p (log(p) > we have
P( G ń = II* Ω (exp (cxp (-
where c c= p=22(c' log 2 and |E| is the number of edges in G*.
Proof. The proof is based on the same idea as the proof of Theorem 3.2 and uses probabilistic
bounds on the coupon collector problem to obtain the desired result.
That is, we derive bounds on the probability that for an edge X; + X, in G there exist pairs of contexts c, such that II;
(c)) and (c) A (c)) for all possible combinations in Î1, Π,
We can consider these as bins with probabilities 2 p², so that for the stopping time = |C] at
which each such bin has been hit at least once we have
P < 2p 2 log(p) + c/p) + exp(-e
By using = p2 CI + log 2 0, therefore have
P(X: + X, G, = IT;) = Ω (exp (-e-9))
and by taking the naive lower bound of treating all edges independently, we therefore obtain
P G* fi -I') Ω (exp (- |E e)))
3

---

A.5 Discussion of Identifiability Results
Here, we place our identifiability results in the context of related work. In doing so, we explain our observation that our approach already discovers causal directions given single context, as well as state the implications of Thm. 3.3 on how many contexts we need to identify the causal DAG.
Identifiability from a single context The work of Peters et al. 45 shows that causal DAGs are fully identifiable from i.idd data using independence of residuals. These results are obtained by assuming differentiability of the underlying distributions as well as causal mechanisms. By modeling our causal mechanisms via GPs, these assumptions are not applicable since individual GP paths in general not differentiable. For our more general setting, we are not aware of a proof that the DAG is identifiable from single context. However, Maax and Vreeken [25] show that in the bivariate
case, MDL-based score functions allow to identify the causal direction from i.i.d. data using the independent noise asymmetry. Our empirical results support this as our approach can already direct a reasonable number of edges given a single context as well as in the bivariate case.
Identifiability depending on the number of contexts We remark that our results address the case where data comes from random environments over which have no control. When we do have control over the environments, i.e., when we can actively perform interventions with known effects, then general results the numbers of required contexts apply, requiring data from (logm) environments for m variables (32
As second note, in Theorem 3.3 we show how many contexts it takes us to identify both the causal graph as well as the partition of the causal mechanisms across environments. If we care only about the identifiability of the causal graph, then two mechanisms per variable (for those variables that are not already directed by Meek's rules) suffice, which dramatically reduces the number of contexts required. In particular, if we obtain samples with equal probabilities for each mechanism, then we require only 20 contexts to orient up to 10000 edges with probability >0.99, independently of the precise structure of the graph. This compares to (roughly) 8 contexts that required under optimal intervention design for causal learning 32]. Our results however do not require us to have control over the intervention targets, which is realistic in many practical applications where may encounter unknown distribution shifts or off-target intervention effects 7
A.6 Discussion of Assumptions
To conclude our theoretical analysis and point out the limitations of our method, we revisit the main assumptions that we make and discuss in which settings we consider them reasonable.
Functional Model (Assumption 1,2) While we avoid some issues related conditional indepen- dence testing in causal discovery [14, 15), this comes at the cost that we need to make additional assumptions on the functional form of causal mechanisms. As we noted in the main text, Gaussian processes constitute a rich function class and allow for a fully non-pon -on-paraettric approach. While they are more general than the functional model assumed in [Peters al. scoring function is proposed by Huang et al. [15] which also allows for regularization, so a use of this functional model in non-i.i.d. setting could be interesting comparison in future work.
[45] similar kernelized
Invariant Noise (Assumption 1,2) By assuming that the noise N, remains invariant across environ- ments, we follow how related work defines environments [13 7. This assumes that different envi- ronments arise from changes in the functional dependencies between the variables, commonly known as soft interventions. That is, environments differ due to changes of the conditional P(X, pa of some variables X; while the exogenous noise variables N, remain invariant. Example applications where this holds include knockout or knockdown interventions in genomics, where the expression of a certain gene is prevented or inhibited [16 [7]. well as the molecular interventions in real-world dataset, where activating or inhibiting reagents are added to the system [20].
To give an example where noise invariance is violated, we consider direct interventions on the noise N; in our experiments (Fig. ((a)). Our results suggest that this particular model misspecification
not a limitation in practice. The same is true for perfect intervention (Fig. 3(a)

---

Sufficiency There is one other reason why noise invariance may be violated which relates to another assumption, namely causal sufficiency. there an unobserved variable, it may introduce a correlation of the noise N; of different observed variables. Considering contexts allows to address confounding in limited sense, since the categorical context variable C' can represent so-called sneeudo-cofoondded
such as background stimuli that remain fixed in a given context [4]. However, these need to be a function of the domain index. There may also be a global latent confounder that introduces a correlation between the noises N(e) across different environments. We are not aware of approaches that address this situation, and extending our theoretical framework to general latent confounding an interesting option for future work.
Faithfulness (Assumption 3,4) Faithfulness assumptions are standard in causal discovery, and in our case assert that the causal parents of a variable indeed affect the variable, as well as that our partitions faithfully represent all changes in causal mechanisms. Both criteria are necessary to detect parents, respectively mechanism changes, from the observed distributions.
Independent Mechanism Shift (Assumption 5) Rather than assuming sparse mechanism shifts, we consider independent mechanism shifts in our work. To formally assume this, we consider our partitions Il independent random variables, which can be thought of as deterministic functions of the context variable C. The result is a categorical random variable that indicates the group membership, rather than context membership, of samples. By assuming independence of these random variables and including them in our model, we ensure that incorrectly directed edges in G lead to larger numbers of modeled mechanisms and thus larger values of our score L.
To explain this, we recall the example in Fig. 1 The true partition for Y has two groups, and the partition of its causal child Z has either two (Fig. ((b)) or five (Fig. [(c) groups. In the true causal model, the partitions for Y and Z are independent. Indeed, in the causal direction, we see no differences in our MDL scores between both cases (green curves in Fig. [(b] I(c] and discover the true partition for Y with |fl 2 (green star) independently of the changing partition for Z in these cases. If consider an anticausal function Z + Y, in contrast, there is difference between both cases (red curves). The partition we discover for Y here depends on the partition of Z, and in both cases it has more groups (minima of the red curves, If 4, lfl 5) and larger score values compared to the causal direction. In the proof of Theorem 3.2, we show more generally that under independence of the true partitions, incorrectly directed edges will lead to more groups in the discovered partitions as well as larger score values of the model.
We justify the independent mechanism shift assumption in the context of interventional experiments. Consider a gene knockout intervention. This is an exogenous influence and independent of the causal interactions between other genes. Similarly, (Sachs al. [20] perform soft interventions by adding Aanilarly,Sachss...o
compounds that activate or inhibit specific molecules. In both examples, a mechanism change is due an external influence and does not depend on the causal mechanism of other variables. In general, this independence holds in generic situations where there is no confounding behind cause and effect [4
Fixed Partition Sizes (Assumption 6) By fixing partition sizes, we fix the number of different causal mechanisms for each of the variables. In effect, we assume that heterogeneity in causal effects is captured in our model. For example, if we studied the differences between treatments in different hospitals, then as we obtain more data, these data would be obtained from the same set of hospitals, rather than by the addition of new hospitals. By ensuring that the partition sizes are fixed, we ensure that the things we are trying to learn do not change as we obtain more data. This allows us to give our more practical identifiability result in Theorem 3.3 for smaller number of contexts.
B Algorithms
In this section, we describe the implementation details of the LINC algorithm and its variants.
B.1 LINC for Learning causal models under Independent Changes
Our approach LINC considers data over continuous variables (c) in multiple contexts c E C, and returns a causal graph G and a set of partitions II.
5

---

Algorithm 1: LINC
Input: data ( candidate DAGs G.
Output: DAG G and partitions II.
for each DAG G E G do for each variable X; with causes Xg in G do for each partition II of C do for each group π in do
Pool the data in obtain X
Fit GP f (X S 7 x!())
Compute T( x!") H.x) using Eq. 6
end for end for end for Find the partitions Hy minimizing Eq. (T0)
end for Find the DAG & minimizing Eq. return G, IIg
In Alg. 1 we show the exact search algorithm that we consider in the main paper. It traverses a set of candidate causal graphs G. For each graph G and variable X,, it discovers a mixture mechanisms that generate X, from its parents in G. To do this, regression model to the data pooled in each group in the partition, and compute the MDL score for these GPs. We choose the partition that results in the smallest overall description length,
consider each partition of the contexts, fit GP
II: arg minn L(II)
arg min Σ E(X x(") H.c)
(10)
TEII
where the set Xs corresponds to the parents of X; in G. Repeating this for each variable, obtain the partitions HIG for G. We return the DAG & with smallest overall description length,
G = arg minGeG EmETro L(II).
(1I)
Regarding the complexity of our algorithm, we need to address three aspects: the search space over DAGs G, the search space over partitions II, and the GP regression itself. We propose efficient approaches for each aspect in the following, and conclude by giving complexity analysis.
B.2 LINC with Greedy Equivalence Search
We first address the problem discovering causal DAGs. As the search space over DAG models is super-exponential in the number of variables [33, we limit consideration to the Markov Equivalence class of the true model and one can apply LINC using a two-stage approach, first using existing causal discovery approaches for multiple contexts 4 5 9
MEC(G"), ). We remark that case the true MEC is unknown,
discover a partially directed causal graph, and subsequently applying LINC to orient the remaining edges.
We can also use our MDL score in score-based DAG search algorithm, such as Greedy Equivalence Search (GES) (33. GES uses a scoring criterion that evaluates each causal relationship between given set of causes Xss and an effect X,, Huang al. [T] show how use generalized, nonparametric scoring functions in GES, leading to the Generalized GES algorithm (GGES). Our score can be used as plug-in estimator within this framework because it is locally consistent scoring criterion due to information consistency of GPs. We note that our score is not score-equival eoore-equivalent, that is, different
DAGs in the same MEC may attain different scores, but Huang et al.) [15] show that score local consitency is sufficient to use scoring function with GGES. While we discover single DAG G over contexts this manner, we can account for non-i.i.d.nn of the data well changes of the causal mechanisms.

---

Algorithm 2: LINCcUS
Input: data X variable X; with causes Xs. Output: partition 11, for each context e in C' do Regression in the context fic) GP(X + x
for each context c' & e and c' already seen do
Compute (Xx,,, X; e, e') using Eq. (2)
end for end for Find II = arg minn Exem Eod's L' X2 e, c, using clustering, e.g. by solving Eq. 13 return II
We propose exploring combinations of LINC with different DAG search frameworks in future work, and focus on orienting edges within a MEC in our experiments. This is motivated by two reasons. Firstly, it allows to study the behavior of our scoring function in isolation, taking out the effect of greedy DAG search algorithms, such that our experimental evaluation can support our theoretical results. Secondly, our closest competitors are the mechanism counting scores that need to start from such that we also evaluate LINC on orienting edges within a MEC.
base MEC 12 13
B.3 LINC with Clustering
To scale efficiently with the number of contexts, we introduce a variant of LINC that, rather than all set partitions, considers pairwise combinations of contexts.
To this end, we adapt the Minimum Description Length (MDL) score for GPs. We want to measure whether the data (() (c') over two contexts c, c' is preferably encoded using separate GP functions for each, or a single model over the pooled data. A natural way to compare different modelling hypotheses is via the gain in compression of one model over the other.
By the no-hypeecompressioon inequality (29) the probability that model other than the optimal one should achieve a substantially better compression for a dataset negligible. More specifically, the probability that the competing model leads gain in compression of bits if it is not the true model is smaller than or equal to 2 2- For significance threshold a, we can consider a gain of k bits as insignificant in case 2 > a 29
Hence, we consider the gain L' in compression that two separate GPs achieve over a joint model,
(ad') .x((c) ((x(oe))xx(c)))))
L'(Xs, X c.
- -L((X!0 x + x(x))x(()))
(12)
Given that the gains should not be positive by no-hypercompression, we minimize the pairwise scores L'. This can be seen graph clustering problem on a graph with nodes c C, weighted edges between each pair c, e' with weights L taking positive values iff c, c' belong to the same cluster, and where the number of clusters unknown. MMyauchi al. 2018) consider exactly this problem and show that it corresponds to the following Integer Linear Program (ILP) objective,
min Σ I'(c,, cy)ai 4.6
(13)
where mry are decision variables indicating group membership. zúj 1f Cj E म and zero otherwise. The minimization is subject to so-called triangle constraints [33 ensuring that the solution a valid partition of C, and can be solved using standard solvers.
As another variant, we can use hierarchical clustering with distance measure L'. With this approach, discover the best partition of given size k = [T]]. We select the best & by comparing the full MDL scores of the partitions at and returning the minimal one.
We show how to adapt LINC in Alg. 2 and refer to it as LINCcLUS.
7

---

B.4 LINC with Random Fourier Features
Last, we show how our score can be adapted to a common approximation of GPs using Random Fourier Features (RFFs) [4).
Computing L for GPs is computationally expensive since GP regression does not scale well with the number of samples. One way to mitigate the complexity of GP regression is to express its kernel through Fourier transform, which in turn be approximated efficiently. This is known as the Random Fourier Feature (RFF) approximation [3
The approach is as follows: if is shift-invariant, we have
x(x, v) / p(w) cos(w (x y)w
~ R
-=== (2w, (x - v)) 2(x)T²(1)
for some probability measure p(w). For the RBF kernel, this measure p(w) is another Gaussian
distribution 18] Here, =(x) = vR (v2 cos(w] [V2cos(w] [)),.,"),..... x),..., v2 =())(w and zyy) similarly. Thus, for each pair Fi, Fj, we obtain an unbiased estimator
x,), = 2(x;) (aax))=((3))) 2(xr))
The RFF approximation of GP prediction uses the regression f(x) =<x)TT w. We define our MDL encoding using the ligelioll of this regression, well the norm
| w Zww
for the feature matrix Z = =(X)=xX)T. Up these modifications, the MDL encoding in Eq. for RFF regression models.
B.5
Complexity
For DAG discovery, exact search is infeasible due to the super-exponential search space over causal There are greedy solutions ((1)))) V being the number of nodes the DAG (26).
DAGs K
Regarding the partition discovery problem, the exact solution involves the evaluation of partitions, b being a bell number in C). Heuristic search requires only |C]2 regressions. While the problem of finding an optimal clustering of C (c.g., using the ILP) is still NP-hard [53]. there exist efficient options such as k-means that we could insert. In addition, we have |C| < N, and IIP search can be done using standard solvers, which we found to be efficient in practice.
Lastly, exact GP regression in O(N") for N data points and 2.7, while the RFF approximation is in (minn N M)} for M features [34]
C Experiments
In this section, we include additional information on the experiments we present the main paper. In addition, we illustrate how LINC and its variants introduced in the previous section scale in practice.
C.1 Causal Discovery Beyond MEC
First, revisit our main experiment on causal discovery beyond MEC in Fig. 2(a) As show Fl scores this figure, we also include the Precision and Recall in Fig. 5
We can observe that LINC performs well in terms of edge recall in all settings, while maintaining precision comparably high to MSS. Only for large edge densities, LINC surpassed by MSS, while we outperform competitors for small DAG sizes, small edge density, and under few mechanism changes respectively for a small number of contexts. In particular, for no mechanism changes ( and |C|- 1) and when few variables are involved in the causal relationships (IG) 3 and p 0.3). we can see that the recall values are close to 0.5 (dashed lines) suggesting that the DAGS recovered by the competitors close to the known base MEC, while LINC learns additional causal directions.

---

LINCar LINCxre
MC
Pooled A
Recall
0.2
0.8
0.6
0.4
0.2
15
12
0.3 0.4 0.5 0.6 0.7
10a
10a
Contexts [C)
Variahles [G]
Changes [S]
Edge Density
Samples Jel
Figure 5: LINC disovers causal models beyond Markov Equivalence. We report Recall and Precision on discovering causal edges within MEC. As in the main paper, consider synthetic data from different contexts, with the base settings of [C] = 5 contexts, |G| = 6 variables, |S| = 2 intervened variables, edge density p 0.3, and [c] 500 samples.
C.2 Scalability Experiments
Given that we suggested more efficient variants of LINC, we evaluate their performance and scalabil- ity here. We are interested in whether LINCcLUs can efficiently discover partitions for increasing [C], whether LINCRFF improves runtimes for increasing sample sizes |cl. and whether our method and competitors are applicable to larger DAG sizes [G].
Throughout this section, we consider the main experimental setup of discovering causal models beyond Markov Equivalence, and use the settings [$] = 1, C| = 3, |c| 500 and [G] 3, = 0.3.
C.2.1 LINC with Clustering
In Fig. 6 we compare the variant of LINC that exhaustively enumerates all context partitions (Alg. D to LINCcLUS which relies on clustering the contexts by compression gain (Alg 2 As the clustering procedure in LINCeLuS. we consider Integer Linear Programming (ILP) as well as agglomerative clustering (aggl.).
LINCCLAS (aggl.)
IINC (TIPP)
LINC (partitions)
As an exhaustive search over all partitions did not finish running for [C] = 20 in a reasonable time (one day), we include partial results (gray).
10a
Runtime (so2)
10a
10a
For simplicity, we instantiated LINC with RFFs While an enumeration of all partitions of the contexts is not feasible for more than 20 contexts, we found the clustering approaches to scale easily to at least 50 contexts. In particular, both result in high FI scores for directing edges in MEC given enough contexts, with perfect Fl scores when given more than 15 contexts. This suggests that in practice, rather than com- consider
cases.
101
5
40
Contexts [C]
Figure 6: LINC can be combined with clustering discover parti- tions. We compare exhaustive enu- meration of partitions (gray, Alg I to clustering (Alg. 2
puting the full MDL score for each partition, using pairwise MDL compression gains to apply LINC to many contexts.
C.2.2 LINC with Random Fourier Features
Next, we turn to the kernel approximation through Random Fourier Features (RFFs) described in the previous section.

---

H1
104
Runtine (sec)
10a
10a
10a
10a
LINC RFF
104
MSS
[R]
10
MC
Pooled
5
10
20
30
5 1015 20
30
30
Contexts CI
Variables [G]
Context Size.
DAG size.
Figure 8: LINCs variants are accurate while being scalable. We compare LINC with RFFs and clustering the baselines, for (a) an increasing numbers contexts, and (b) increasing DAG size.
We also included RFFs in main evaluation in Fig. to confirm that they work well in practice. To illustrate the compu- tational benefit, also compare the runtimes of GPs and RFFs in Fig. 7 We again use the settings |S| 1, |cl = 500 and
(RFF)
p 0.3 and consider |C| We confirm that RFFs mitigate the sample complexity of the GP regression without notably affecting performance.
LINC (GP)
104
Runtime
10a
10
C.2.3 LINC and Competitors
2000
To conclude, we compare the efficient variants LINC to competitors. We are interested in whether the clustering variant of LINC combined with RFFs scalable while being accurate.
Samples Jel
Figure 7: LINC can be combined with RFFs improve sample com- plexiry. We compare LINC with the GP MDL score (solid) to the RFF approximation (dashed).
In Fig. we show our experiment on discovering causal edges for up to 50 contexts, resp. variables. As we found no noticeable difference between the clustering approaches that we instantiate LINC with, we show only the ILP version avoid clutter.
LINC scales to at least 50 contexts, while Pooled PC was not applicable on 3-variable DAGs (Fig. [a()). We also find that LINC scales DAGs with at least 50 variables with comparable runtimes to the nonlinear baselines (Fig. [(b).. Regarding performance, in Fig. ((a) we can see that MC discovers only the base MEC due the small number of variables. Pooled PC and particularly MSS need larger number of contexts in this case, whereas the efficient version of LINC discovers all causal directions given five contexts. We conclude from our experiments that the efficient versions of LINC reliably perform in practice.
than 30 contexts in reasonable time, even
References
[1] B. Schölkopf, F. Locatello, S. Bauer, N. R. Ke, N. Kalchbrenner, A. Goyal, and Y. Bengio. Toward causal representation learning. Proceedings the IEEE, 10965)612-634, 2021. doi: 10. 209/ 20.50099.... 33058954. URI. RRll:tttts://eeeepplooe arnumber=9363924
ieee. wtw.eeeeeeeeeeeeeeeeeeee..e..eee sttss//ttt//aappppp jsp?
[2] Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant Risk Mini- mization. CoRR, 00709999779993. 2019.
10

---

[3] J. Peters, P. Bühlmann, and N. Meinshausen. Causal inference using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society: Series (Statistical Methodology). 78(5)997711112 2016. doi: 10.1111/rssb. 12167. URL http:
7/arxiv. wrg..rggg//......... 1501. 01332
(with discussion).
[4] Biwei Huang, Kun Zhang, Jiji Zhang. Joseph Ramsey, Ruben Sanchez-Romero, Clark Glymour, and Bernhard Schölkopf. Causal discovery from heterrgennousshonstatiinnny data. Journal of Machine Learning Research, 21( 2020. ISSN 1532-4435.
[5] Joris Mooij, Sara Magliacane, and Tom Claassen. Joint causal inference from multiple contexts. Journal of Machine Learning Research, 21:99:1-99:108. 2020.
[6] Amin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Causal discovery from soft interventions with unknown targets: Characterization and learning. In Proceedings of the Conference on Neural Information Processing Systems (NeurIPS), pages 9551-9561. Curran, 2020.
[7] Chandler Squires, Yuhao Wang, and Caroline Uhler. Permutation- causal structure learning with unknown intervention targets. In Proceedings of the International Conference on Uncertainty in Artificial Intelligence (UAI), pages 1039-1048. PMLR, 2020.
[8] 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 October 2019.
from Unknown Interventions. arXiv, 100.00107::axx1:111000000
[9] Philippe Brouillard, Sébastien Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien, and Alexandre Drouin. Differentiable causal discovery from interventional data. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546
[10] Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, 2nd edition, 2009.
[11] Jin Tian and Judea Pearl. Causal discovery from changes, 2013.
[12] AmirEmad Ghassami, Negar Kiyavash, Biwei Huang, and Kun Zhang. Multi-domain causal structure learning in linear systems. In Proceedings of the Conference on Neural Information Processing Systems (NeurIPS). volume 31, 2018.
[13] Ronan Perry, Julius Von Kügelgen, and Bernhard Schölkopf. Causal discovery in heterogeneous environments under the sparse mechanism shift hypothesis. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Proceedings of the Conference on Neural Information Processing Systems (NeurIPS), 2022. /RRLattps///opeeeveev..ee net.oorun iddkFRCypubbJo
[14] Antti Hyttinen, Frederick Eberhardt, and Matti Järvisalo. Constraint-based causal discovery: Conflict resolution with answer set programming. In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence. UAI' 14, page 340-349, Arlington, Virginia, USA, 2014. AUAI Press. ISBN 9780974903910.
[15] Biwei Huang, Kun Zhang, Yizhu Lin, Bernhard Schölkopf, and Clark Glymour. Generalized score functions for causal discovery. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '18, page 1551-1560, New York, NY, USA. 2018. Association for Computing Machinery. ISBN 9781450355520. doi: 10.1145/3219819 19.220004. URL https: //do. org/10. 100 1145/ 03122022199899992200
[16] Yanfang Fu, Jennifer Foden, Cyd Khayter, Morgan Maeder, Deepak Reyon, J Joung, and Jeffry Sander. figh-frequency off-target mutagenesis induced by crispr-cas nucleases in human cells. Nature biotechnology, 31, 06 2013. doi: 10.1038/nb1.222..
[17] Antonia A. Dominguez, Wendell A. Lim, and Lei S. Qi. Beyond editing: repurposing crispr-cas9 for precision genome regulation and interrogation. Nature Reviews Molecular Cell Biology, 17 (1):5-15, 2016. doi: 10. n0.1038/mm.2055222 URL //dois org/ 10. 1038/ 2/0///rm.... 2015. .2
11

---

[18] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2005. ISBN
[19] Payam Dibaeinia and Saurabh Sinha. Sergio: A single-cell expression simulator guided by gene regulatory networks. Cell systems, 2020.
[20] Karen Sachs, Omar Perez, Dana Pe Douglas Lauffenburger, and Garry Nolan. Causal protein-signaling networks derived from multiparameter single-cell data. Science, pages 523-9, 2005.
[21] Siyuan Guo, Viktor Tóth, Bernhard Schölkopf, and Ferenc Huszár. Causal de finetti: On the iden- tification of invariant causal structure in exchangeable data. arXiv preprint arXiv: 15756, 2022.
[22] Bernhard Schölkopf. Dominik Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris Mooij. On causal and anticausal learning. In Proceedings of the International Conference on Machine Learning (ICML), ICML' 12, pages 459-466, Madison, WI, USA, 2012. Omnipress.
ISBN 9781450312851
[23] Dominik Janzing and Bernhard Schölkopf. Causal inference using the algorithmic markov condition. IEEE Transactions on Puttern Analysis and Machine Intelligence, 1551168-1199 2010.
[24] Jan Lemeire and Dominik Janzing. Replacing causal faithfulness with algorithmic independence of conditionals. Minds and Machines, 23, 2013.
[25] Alexander Marx and Jilles Vreeken. Identifiability of cause and effect using regularized regression, In Proceedings of the ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD). ACM, 2019.
[26] Osman Mian, Alexander Marx, and Jilles Vreeken. Discovering fully oriented causal networks. In Proceedings of the AAAI Conference on Artificial Intelligence (AAA!), 2021.
[27] David Kaltenpoth and Jilles Vreeken. We are not your real parents: Telling causal from confounded using MDL. CoRR, abs/1900,06690, 2019. URL BtRp://t://aret htattp::/aaxvv.cooo wrtp:////////////////////// 06950
abs/190s//99
[28] Ming Li and Paul Vitányi. An introduction to Kolmogorov complexity and its applications. Springer Science Business Media, 2009.
[29] Peter Grünwald. The Minimum Description Length Principle. MIT Press, 2007.
[30] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. enformation-theoreeh regret bounds for gaussian process optimization in the bandit setting. IEEE Transactions Information Theory- TIT, 58:3250-3265, 05 2012. doi: 10.1009/TT.20112112003.
[31] Sham M. Kakade, Matthias W. Seeger, and Dean P. Foster. Worst-case bounds for gaussian process models. In Y. Weiss, B. Schölkopf, and J. Platt, editors, Pro- ceedings of the Conference on Neural Information Processing Systems (NeurIPS), vol- ume 18. MIT Press, 2005. URL.htps::/prroeeinnss neur.ss..uu...... ptt.rr/ps..ccppppp/2////////// 357odfF/aaaccdd33668833e1aa/aa-3
.dd
[32] Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 52(4)9926-939, jun 101672F ijar. 2013
2014. doi: 00.1016/j.jarr20111.
URL BRRLhttps:100 /attps://doi.orgg
11.007
[33] David Maxwell Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3:507-554, 2002.
[34] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Proceed- ings of the Conference on Neural Information Processing Systems (NeurIPS), NI,S'07, page 1177-1184, Red Hook, NY, USA, 2007. Curran Associates Inc ISBN 9781605603520.
12

---

[35] Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, prediction. and search. MIT Press, 2000.
[36] Karren D. Yang, Abigail Katoff, and Caroline Uhler. Characterizing and learning equivalence classes of causal dags under interventions. In Proceedings of the International Conference on Machine Learning (ICML), 2018.
[37] Jonas Peters, Dominik Janzing, and Bernhard SchIkopf. Elements of Causal Inference: Founda- tions and Learning Algorithms. The MIT Press, 2017. ISBN 0262037319.
[38] Sarah Mameche, David Kaltenpoth, and Jilles Vreeken. Discovering invariant and changing mechanisms from data. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge
Discovery and Data Mining, KDD 22, page 1242-1252, New York, NY. USA, 2022. Associa-
tion for Computing Machinery, ISBN 978 450393850. doi: 10.1 10.114//3346788.33394777 URL
https: https://aoi.org org 100..1111/333366681888 3539479
[39] Christina Heinze-Deml, Jonas Peters, and Nicolai Meinshausen. Invariant causal prediction for nonlinear models. Journal of Causal Inference, 6(2), 2018.
[40] Dominik Rothenhäusler. Nicolai Meinshausen, Peter Bühlmann, and Jonas Peters. Anchor regression: Heterogemeous data meet causality. Journal of the Royal Statistical Society: Series (Statistical Methodology). 83(2):215-244 2021.
[41] Daniel Eaton and Kevin Murphy. Exact bayesian structure learning from uncertain interven- tions. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 2. pages 107-114, San Juan, Puerto Rico, 2007. PMLR.
[42] Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs. Journal of Machine Learning Research, 13(1):2409-2464, aug 2012. ISSN 1532-4435.
[43] Yuhao Wang, Liam Solus, Karren D. Yang, and Caroline Uhler. Permutation-based causal inference algorithms with interventions. In NIPS, 2017.
[44] Xiao-Hui Zhang, Louis Y Tee, Xiao-Gang Wang, Qun-Shan Huang, and Shi-Hua Yang. Off- target effects in Acids, 4:c264, 2015. ISSN 2162-2531.
mediated genome engineering. Molecular Therapy Nucleic doi: httpp://www/ www.sseiieeeceecccccm com htt.a///c.....ooooooo.cc.cccccaa
URL
[45] Jonas Peters, Joris M. Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. J. Mach. Learn. Res., 15(1):2009-2055 jan 2014. ISSN 1532-4435.
[46] Alexander Marx and Jilles Vreeken. Telling cause from effect by local and global regression. Knowledge and Information Systems, 1073):177711355, 2019.
[47] Alexander Marx and Jilles Vreeken. Formally justifying based inference of cause and effect, 2021.
[48] Alexander Hägele, Jonas Rothfuss, Lars Lorch, Vignesh Ram Somnath, Bernhard Schölkopf, and Andreas Krause. Bacadi: Bayesian causal discovery with unknown interventions. In Francisco Ruiz, Jennifer Dy, and Jan- Willem van de Meent, editors, Proceedings of the In- ternational Conference on Artificial Intelligence and Statistics (AISTATS), volume 206 of Proceedings of Machine Learning Research, pages 1411-1436. PMLR, 25-27 Apr 2023, URL httts:://proceedings mlr pptesss/206/aaggee22330 httml
[49] Jonas Peters, Joris M. Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. Journal of Machine Learning Research, 15(58))2009-2053 2014.
[50] Atray Dixit, Oren Parnas, Biyu Li, Jenny Chen, Charles Fulco, Livnat Jerby-Aron, Nemanja Marjanovic, Danielle Dionne, Tyler Burks, Raktima Raychowdhury, Britt Adamson, Thomas Norman, Eric Lander, Jonathan Weissman, Nir Friedman, and Aviv Regev. Perturb-seq: Dis- secting molecular circuits with scalable single-cell ma profiling of pooled genetic screens. Cell, 167, 12 2016. doi: 10. 10.1016/ 1.008.
13

---

[51] S.L. Lauritzen. Graphical Models. Oxford Statistical Science Series. Clarendon Press, 1996. ISBN 9780191591228. URL https://bbokk httpg//edeeebbooss/.ddadaaa////
[52] J Bernardo, Burger, and ADEM Smith. Information-theorete characterization of bayes performance and the choice of priors in parametric and nonparametric problems. In Bayesian statistics, volume 6. Oxford Univ. Press, 1998.
[53] Atsushi Miyauchi, Tomohiro Sonobe, and Noriyoshi Sukegawa, Exact clustering via integer programming and maximum satisfiability. Proceedings of the AAAI Conference Artificial Intelligence. 32(1), Apr. 2018. doi: 10.1699aaii. 00.16099aai.v3321..1... v32.1.11511. org/index. phpp hhtp://AA///rrttcccaa/asee//////
URL https: //ojs. aaai
14


Reviews:
[{"review_id": "8q6IkAmOjb", "reviewer": "Reviewer_t48a", "summary": "The authors study the problem of causal discovery from data under different conditions/contexts. The approach uses an algorithmic model of causation, where the idea is that causal mechanisms provide short (or simple) descriptions of the observed data. Under this principle, the authors propose a score function for models where the functional mechanisms are Gaussian processes (GPs). The main contributions of this work are Theorems 3.1, 3.2, and 3.3, where the authors show identification of the MEC or ground-truth DAG. The core assumptions for such theorems are:\n* Causal sufficiency\n* All contexts share the same DAG\n* Additive noise model with GPs\n* Causal minimality \n* $\\Pi$-faithfulness\n* Independence of mechanism shifts\nThe authors develop LINC to learn the causal DAG from different contexts, and provide some experiments to validate their results.", "questions": "* Why is $|E|$ in the lower bound in Theorem 3.3. inside exp? I might be missing something but doesn't this come from the union bound and, hence, shouldn't it be outside exp?\n* My main criticism of this work is that the model under consideration is identifiable from observation data (Peters et al., 2014). Moreover, since the authors assume that **all contexts share the same DAG**, why couldn't one identify the DAG from a single context?\n* Please fix the assumption numbering in the theorem statements.", "limitations": "Briefly described in Section 6. No major concerns.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "### Potential Reasons for Acceptance\n   - The paper provides a fair investigation into the core assumptions that many causal modeling approaches, including SMS, rely upon, and moves the field forward by addressing these assumptions.\n   - Novelty of the proposed approach \"LINC\": By adopting the algorithmic notion of independence and Gaussian Process models, the authors elevate the ability to identify the accurate causal model and extend the scope beyond partially directed graphs.\n   - Identifiability theory: The authors provide theoretical justification for their approach, followed by some empirical evaluations on both synthetic and real-world datasets which aim to validate their claims.\n", "weaknesses": "### Potential Reasons for Rejection\n   - The DAG from a single context is identifiable as it is a nonlinear additive noise model.\n   - Theorem 3.2 seems very unrealistic when considering infinite number of contexts. While the authors try to provide some justification to it by providing a finite-sample statement in Theorem 3.3, I got confused with the idea of $C$ falling into some \"bins\". What does it mean for $C$ to fall into two or more different bins? The notion of bins were never used until this theorem and was not properly described  in my opinion.\n   - Dependency on number of datasets:\n     - The effectiveness of the proposed model heavily depends on certain characteristics of the dataset such as having enough contexts, which might not always be the case. \n  - Complexity of the proposed solution:\n     - The proposed solution is relatively complex, particularly concerning the computational cost. Several experiments are performed on a very small number of nodes, e.g., six-node graphs.\n     - Some heuristics are provided in the appendix to alleviate this issue, however, some details are missing. For example, in  Figure 8(b), MC seems faster and obtains similar F1 scores to LINC.\n   - The writing can be improved by a fair margin. Learning a DAG from different contexts is not a new setting and the authors could greatly reduce the amount text of somewhat repetitive definitions of the model in Line 69, Assumption 1 and Assumption 2. Indeed Assumption 1 seems useless if Assumption 2 already holds, no? If the theoretical results rely on GPs, why not simply state that in the problem setting? Finally, Theorems 3.1 and 3.2 mention a  \"sufficiently small $\\lambda$\", but such $\\lambda$ does not appear in the result. By looking at the text there is a $\\lambda$ from the RBF in Line 139; however, in the appendix I got confused as it seems to refer to a different quantity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and detailed comments, which we address in the following.\n\n**Identifiability given a single context**\n> The DAG from a single context is identifiable as it is a nonlinear additive noise model.\n\nWhile the DAG is indeed identifiable for *many* generic functions, the results of Peters (2014) [1] are obtained by assuming differentiability of the underlying distributions as well as causal mechanisms.\nBy modeling our causal mechanisms via GPs, these assumptions are not applicable since individual GP paths are in general not differentiable. For our more general setting, we are not aware of proofs that the DAG is identifiable from a single context.\n\nPeters (2014) [1] give examples where the causal direction is not identifiable via independence of residuals (Ex. 2). Given these limitations, it is interesting to explore independence of causal mechanisms as an alternative criterion, and we hope that our work improves the current theoretical understanding.\n\n**Dependency on the number of contexts** \n> Theorem 3.2 seems very unrealistic when considering infinite number of contexts.\n\nInfinite numbers of contexts are of course highly unrealistic, which is why we provide refined bounds in Thm. 3.3. Note also that our results address the case where our data comes from random environments over which we have no control. \nWhen we do have control over the environments, i.e., when we can actively perform interventions with known effects, then general results on the numbers of required contexts apply, requiring data from $O(\\log(m))$ environments for $m$ variables. [2]\n\n> While the authors try to provide some justification to it by providing a finite-sample statement in Theorem 3.3, I got confused with the idea of $C$\n falling into some \"bins\".   What does it mean for $C$ to fall into two or more different bins?\n \nWe agree that this description is confusing and will improve the explanation. The assumption that the partition sizes are fixed can be understood in a frequentist sense, in that on average each possible causal mechanism for each variable $X_j$ occurs in at least a constant fraction of all samples. For example, if we study the differences between treatments in different hospitals, as we obtain more data, these data would be obtained from the *same* set of hospitals, rather than by the addition of new hospitals.\n\n> The effectiveness of the proposed model heavily depends on certain characteristics of the dataset such as having enough contexts, which might not always be the case.\n \nNote that in Theorem 3.3 we show how many contexts it takes us to identify both the causal graph *as well as* the partition of the causal mechanisms across environments. If we care only about identifiability of the causal graph, then two mechanisms per variable (for those variables which are not already directed by Meek's rules) suffice, which dramatically reduces the number of contexts required. In particular, if we obtain samples with equal probabilities for each mechanism, then we require only 20 contexts to orient up to 10000 edges with probability >0.99, independently of the precise structure of the graph.\nWhile it is true that these 20 contexts are a lot more than the ~8 required for optimal intervention design for causal learning [1], our results do not require us to have control over the intervention targets, an assumption which would in many cases be *even more unrealistic*.\n\nWe also concede that observing a system in multiple contexts at all is an assumption that might not always be realistic. Exactly this point, however, can be an argument for using LINC instead of mechanism shift scores, since LINC already works well given few, or even a single, context, as we observed in our evaluation. As an explanation of this phenomenon, we refer to Marx and Vreeken (2019) [3] who give identifiability results for i.i.d. data with MDL-based scoring functions, via independence of regression residuals. \nIn light of this, we do not consider the dependence on the number of contexts a limiting concern in practice. \n\n\n**Other concerns**\n> The proposed solution is relatively complex, particularly concerning the computational cost. \n\nWe consider our theoretical insights our main contribution while providing a proof-of-concept implementation. We also see the complexity of the solution as a current limitation, and our efficient heuristics can be further optimized (as you point out, for example, the current solution is slower than MSS in some cases). \n\n> Why is $|E|$ in the lower bound in Theorem 3.3. inside exp? I might be missing something but doesn't this come from the union bound and, hence, shouldn't it be outside exp?\n \nThis is not a union bound on probability of the union of some set of events, it is a bound on the intersection of multiple events. In effect, we assume that every edge has to be directed independently of all others. This is in fact a *lower bound* on the probability, since determining the direction of some edges can allow for orienting others using Meek's rules.\n \n \n> [...] the authors could greatly reduce the amount text of somewhat repetitive definitions of the model in Line 69, Assumption 1 and Assumption 2.\n\nThank you for your suggestions on shortening the problem setting, we will remove Assumption 1 as it is subsumed by Assumption 2. \n\nPlease let us know whether we could address your concerns. We are happy to respond to any further questions and concerns. \n\n**References**\n\n[1] Jonas Peters, Joris M. Mooij, Dominik Janzing, and Bernhard Schölkopf. 2014. \"Causal discovery with continuous additive noise models.\" *J. Mach. Learn. Res.* 15, 1 (January 2014), 2009–2053. \n\n[2] Hauser, Alain, and Peter Bühlmann. \"Two optimal strategies for active learning of causal models from interventional data.\" *International Journal of Approximate Reasoning* 55.4 (2014): 926-939. \n\n[3] Marx, Alexander, and Jilles Vreeken. “Identifiability of Cause and Effect Using Regularized Regression.” In *KDD*, 2019.\n"}, {"review_id": "BnrxfrdNyD", "reviewer": "Reviewer_LpAE", "summary": "This paper addresses the problem of causal discovery with heterogenous data coming from multiple contexts where contexts are characterized by soft/hard interventions. Previous work differs in assumptions on how non-iid data is produced, the primary assumption being the Sparse Mechanism Shift assumption which assumes that the number of mechanism changes is small. The current paper proposes a score-based approach to discovering the casual graph from data coming from different contexts. For each variable, the set of contexts can be partitioned where in each bin of the partition, the mechanism that represents the cause-effect relationship between the variable and its parents is unchanged. The score-based approach comprises of a) functionally modeling the relationship between variables and their parents using Gaussian processes (GPs) for each context bin and b) computing a score that is based on minimum description length (MDL) of the GP model. The paper provides identifiability guarantees for identification up to its Markov Equivalence class (MEC). With an additional assumption about independence of context-partitions the authors are able to obtain asymptotic (in the number of contexts) identification guarantees beyond the MEC. Numerical results on synthetic, semi-synthetic and real datasets validate the proposed method's superiority over existing methods. ", "questions": "Overall, I think this is a potentially good submission subject to clarifications on a few questions, some of which I have added in the weaknesses section, and some that I outline below: \n1) Algorithm 1 (LINC) has a step where it cycles through candidate graphs in MEC. \n2) LINC seems to be doing quite well even with just iid data and also in cases with very few contexts. Any explanation about this phenomenon would be interesting. ", "limitations": "Authors don't address any potential negative impacts explicitly. Since this is an incremental advance of an established line of research, I don't see an issue.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "This paper provides a novel algorithm for an important problem of causal discovery using heterogenous data. The main strength of the paper lies in the experimental validation of its proposed method, LINC. The evaluation is done on multiple types of datasets and LINC is shown to outperform or is at least competitive to existing methods on all. While, the idea of using MDL-based scores is not novel in causal discovery, the idea of combining Kakade et. al.'s work in causal discovery is novel. On the theoretical side, while I have questions about the assumptions that I elaborate in the sections below, the paper proves identifiability guarantees in both the asymptotic (in number of contexts) and and finite-context settings. ", "weaknesses": "Listing out a few weaknesses: \n1) Justification of assumptions: The core result of identifiability beyond the MEC depends on the independent mechanism shift assumption. I wasn't convinced about why this assumption makes sense. In particular, why does the assumption imply Line 184-185. I also didn't find any practical justification of the fixed-partition sizes assumption. In general, justifying the assumptions more clearly and with a practical example in mind can help strengthen this weakness. \n2) Writing: The writing can be improved greatly. There are undefined notations and a lot of important content of the paper that has not been explained in the first 9 pages. Some examples: a) The main score function in Line 161 is not explained or defined anywhere. Given that LINC is explained only in the appendix, I found it difficult to even understand what the score function was. b) Independent mechanism shift also contains notation \\Pi_i(C) which hasn't been defined before (but is clear from context). c) Assumption numbers mismatched. d) words used without defining - algorithmically independent in line 109, direct intervention in Line 34, \n3) Experiments: Most of the evaluation is based on recovery of the causal graph whereas identification guarantees also address recovering the partitions.  Can some experimental results be shown to verify if the partitions are being discovered correctly? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your detailed feedback.\n\n**Independent Mechanism Shift Assumption**\n> The core result of identifiability beyond the MEC depends on the independent mechanism shift assumption. I wasn't convinced about why this assumption makes sense. \n\nThe assumption is easiest to understand in the context of interventional experiments. Consider a gene knockout intervention. This is an exogenous influence and independent of the causal interactions between other genes. Similarly, Sachs et al. (2005) perform soft interventions by adding compounds that activate or inhibit specific molecules. In both examples, a mechanism change is due to an external influence and does not depend on the causal mechanism of other variables. In general, this independence holds in generic situations where there is no confounding behind cause and effect (Huang et al. 2020). \n \n> In particular, why does the assumption imply Line 184-185.\n\n*Lines 184-185 from the paper:*\n> we consider our partitions $\\Pi$ as independent random variables. This ensures that incorrectly directed edges lead to larger numbers of modeled mechanisms and thus larger values of our score $L$. \n \nTo see this, consider the example in Fig. 1 of the manuscript. The true partition for $Y$ has two groups, and the partition of its child $Z$ has either two (Fig. 1b) or five (Fig. 1c) groups. In the true causal model, the partitions for $Y$ and $Z$ are independent. Indeed, in the causal direction, we see no differences in our MDL scores between both cases (green curves in Fig. 1b, 1c) and discover the true partition for $Y$ (green star). If we consider an anticausal function $Z \\to Y$, in contrast, there is a difference between both cases (red curves). The partition we discover for $Y$ depends on the partition of $Z$, and in both cases it has more groups and larger score values compared to the causal direction. \n\nIn the proof of Thm. 3.2, we show more generally that under independence of the true partitions, incorrectly directed edges lead to more groups and larger score values of the discovered partitions.\n\n**Fixed Partition Sizes**\n> I also didn't find any practical justification of the fixed-partition sizes assumption. \n\nBy fixing partition sizes, we fix the number of different causal mechanisms for each of the variables $X_i$. In effect, we assume that all heterogeneity in causal effects is captured in our model.\nE.g., If we studied the differences between treatments in different hospitals, as we obtain more data, these data would be obtained from the *same* set of hospitals, rather than by the addition of new hospitals. By ensuring that the partition sizes are fixed, we ensure that the things we are trying to learn do not change as we obtain more data. \n\n **Experiments**\n> Can some experimental results be shown to verify if the partitions are being discovered correctly?\n\nThis is a good point. To illustrate this, we sample causal DAGs with our base settings. We pick a variable at random and evaluate whether LINC discovers the partition that shows its mechanism shifts. To do so, we count the context pairs that LINC correctly assigns to a different group (TP), the same group (TN) or mistakenly to a different (FP) or same group (FN). We report precision, recall, and F1 over 100 runs.\n\n| | Recall | Precision | F1 |\n|-|-|-|-|\n| **Mechanism Shift** |0.88|0.83|**0.85**| \n| Noise Scaling |1.0|0.84|**0.91**| \n| Hard Iv. (synthetic) |0.62|0.62|**0.62**| \n| Hard Iv. (SERGIO) |0.68|0.68|**0.68**| \n\nThe first row shows the case where the causal mechanism of our variable changes, and we confirm that LINC discovers a high fraction of mechanism changes (recall) with few false discoveries (precision). We also included the cases where our model is misspecified, where LINC scales especially well to noise intervention. \n\n **Algorithm** \n > Algorithm 1 (LINC) has a step where it cycles through candidate graphs in MEC. \n\nAs candidate graphs, we start from all DAGs within the Markov Equivalence class of the true DAG. If this class is unknown, there exist standard methods to infer it [1].\n\n**The i.i.d. Case** \n> LINC seems to be doing quite well even with just iid data and also in cases with very few contexts. Any explanation about this phenomenon would be interesting.\n\nThis is an interesting observation that can give an insight into the benefits of an MDL-based approach. For the i.i.d. case, we refer to identifiability results by Marx and Vreeken (2019) [2]. The idea is that under nonlinear additive noise models, regression residuals are independent in the causal, but not in the anti-causal direction. The authors show that MDL-based scoring functions can capture this, as residual independence results in a better compression in the causal direction. This explains why our MDL-based score can determine causal directions on i.i.d. data, while the mechanism shift counting scores recover the MEC (Fig. 2a). \n\nAs for the case of very few contexts, it is known that under optimal intervention sets, only $O(\\log(m))$ contexts suffice to obtain full identifiability for arbitrary graphs, suggesting that in general only few contexts are likely needed. [3] Similarly, from our theoretical results we find that for the case with only two mechanisms per variable occurring with probabilities $p = 0.5$ each, identifiability is highly probable when we observe around 20 contexts even when the ground truth contains 10000 edges.\n\nPlease let us know if you have additional concerns.\n\n**References**\n\n[1] Marx, Alexander, and Jilles Vreeken. “Identifiability of Cause and Effect Using Regularized Regression.” In *KDD*, 2019.\n\n[2] Joris M. Mooij, Sara Magliacane, and Tom Claassen. 2020. \"Joint causal inference from multiple contexts.\" *J. Mach. Learn. Res.* 21, 1, Article 99 (January 2020), 108 pages.\n\n[3]  Hauser, Alain, and Peter Bühlmann. \"Two optimal strategies for active learning of causal models from interventional data.\" *International Journal of Approximate Reasoning* 55.4 (2014): 926-939. "}, {"review_id": "gDvP1EoInD", "reviewer": "Reviewer_oMbi", "summary": "The authors present a novel approach for causal discovery that goes beyond partially directed graphs by utilizing Gaussian Process (GP) models. The proposed method aims to identify\nthe correct causal model under certain conditions. The key idea is to leverage algorithmic independence to achieve a concise and lossless description of the data, particularly in the presence of multiple contexts. Unlike existing approaches such as Sparse Mechanism Shift (SMS), which require conditional independence tests, the proposed method employs a scoring criterion based on GP models.\nThe authors established the theoretical soundness of this approach by providing a clear and concise explanation of the underlying principles. Additionally, they demonstrate the effectiveness of the method through several examples, which serve to evaluate its performance and help to illustrate the practical implications and potential benefits of the proposed method. Overall, the proposed method offers a new perspective on causal discovery by utilizing Gaussian Process models and algorithmic independence.\n", "questions": "In Theorem 3.1, lambda seems a bit abrupt. Is this the hyperparameter for RBF? \n\nInstead of presenting Theorem 3.2 before 3.3, you may introduce 3.3 and just make 3.2 corollary of 3.3 where |C| goes infinity. (or does 3.3 make an additional assumption (e.g. fixed partition size) which is not required for 3.2?)\n\nI am not entirely sure whether the expression in Assumption 5 is valid. In the following paragraph the authors mentioned that partitions are random variables. Does it mean that C is a random variable where \\Pi is just a deterministic function wrapping C?\n\nIn Figure 1(b), Lines 40-41 mention that X and Z are changed. But the Figure 1(a) shows the change wrt context is the function of Y not X nor Z. What am I missing?\n\nIn Sec 3.5 I couldn’t parse “Given the limited number of distinct context distributions … “ I couldn’t see any P( C ) defined clearly. \n", "limitations": "It seems that the critical part of the paper is Section 3.5 where the authors actually operationalize theoretical results in the previous sections. But I felt that the authors somehow hide some issues? E.g., finding partitions is exhaustive (or equivalently, exponential in the number of contexts)  (despite line 227 mentions that the time complexity  is in supplementary material…)\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "LINC (Learning causal models under Independent Changes) proposed in this paper seems original utilizing GP and its complexity measure for discovering a mixture of mechanisms. Non-iid data can be typically challenging but in this paper’s setting, multi-context is a key to identifying the underlying causal structure. The overall flow of the paper is smooth, and it appropriately makes necessary assumptions. ", "weaknesses": "Not a major weakness but minor weaknesses (more like comments)\n\nReadability: It would have been beneficial to include explanatory information on prerequisite knowledge to enhance the accessibility of the paper. In particular, “algorithmic independence” seems very crucial, but it is just referenced without properly articulating its definition or the difference to conditional independence. \n\nAssumptions numbering is problematic. It seems that the authors removed one of the assumptions at the very last stage of writing. E.g. Assumption 5 is mentioned in Theorem 3.1, which is in the previous section. Also for Theorem 3.2 refers Assumption 6. Theorem 3.3 calls for Assumption 7 which does not exist. \n\nIt is less clear whether C is part of data or not.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your comments, which we address in the following.\n\n**Limitations**\n> It seems that the critical part of the paper is Section 3.5 where the authors actually operationalize theoretical results in the previous sections. But I felt that the authors somehow hide some issues? E.g., finding partitions is exhaustive (or equivalently, exponential in the number of contexts) (despite line 227 mentions that the time complexity is in supplementary material…)\n\nIn the main paper we only consider the exact version of LINC, which searches for the optimal partitioning by exhaustively considering all possible partitions. This provides guarantees on the output, at the cost of an indeed exponentially sized search space. As the number of contexts in real-world datasets is typically fairly small, e.g. less than ten contexts for the data by Sachs et al. (2005), we consider the exact version of LINC applicable in practice.\n\nIn the Appendix, we additionally provide a faster, heuristic version of LINC that employs clustering to find a good partitioning of the contexts. Although it does not come with theoretical guarantees, it does performs equally well in practice and does so much faster. As we are primarily interested in the guarantees, we consider this version of LINC as a 'fun' additional result, rather than a main contribution. \n\n**Clarity**\n> In particular, “algorithmic independence” seems very crucial, but it is just referenced without properly articulating its definition or the difference to conditional independence.\n\nThat is a good point, we will include the definition in the paper. \nIn effect, as noted in Postulate 2.1, the algorithmic independence of causal mechanisms amounts to the idea that compressing them independently of one another is optimal. \n \n> It is less clear whether C is part of data or not.\n\n$C$ is indeed part of the data, that is, we need to know in advance which context the data samples come from. \n\n> In Theorem 3.1, lambda seems a bit abrupt. Is this the hyperparameter for RBF?\n\nYou are right, and we will introduce $\\lambda$ more clearly. It is a hyperparameter that we need for proof to bound the score differences between the true DAG and the one minimizing our score.\n\n> Instead of presenting Theorem 3.2 before 3.3, you may introduce 3.3 and just make 3.2 corollary of 3.3 where |C| goes infinity. (or does 3.3 make an additional assumption (e.g. fixed partition size) which is not required for 3.2?)\n\nYes, Thm. 3.3. makes the assumption of fixed partition sizes which is not required for Thm. 3.2, which is why we presented them in this order. We will fix our assumption numbering to make this clear.\n \n>I am not entirely sure whether the expression in Assumption 5 is valid. In the following paragraph the authors mentioned that partitions are random variables. Does it mean that C is a random variable where \\Pi is just a deterministic function wrapping C? \n\nExactly, you can see $\\Pi$ as deterministic functions of C. The result is a categorical random variable that indicates the group membership, rather than context membership, of samples. While this is a slight abuse of notation, we want to consider $\\Pi$ as random variables here so that we can assume their independence. \n\n>In Figure 1(b), Lines 40-41 mention that X and Z are changed. But the Figure 1(a) shows the change wrt context is the function of Y not X nor Z. What am I missing?\n\nAs you say, the function of $Y$ changes in both examples, but in addition, there are causal functions of $X$ and $Z$ that also change. In Fig. 1(b), we show what happens when $X, Z$ both have two causal functions, resp. five functions in Fig. 1(c). We compare these two situations to show that the true causal functions for $Y$ are not affected by this (independent).\n \nIn the illustration, we omitted the causal functions for $X, Z$ to avoid clutter, but we can include them to make it more clear.\n\n>In Sec 3.5 I couldn’t parse “Given the limited number of distinct context distributions … “ I couldn’t see any P( C ) defined clearly.\n\nOur writing is unclear here; in general, the number of contexts can be arbitrarily large, but in practical applications, we usually only have few contexts available, for example, we have fewer than ten interventional experiments in the data by Sachs et al. (2005). \n\nWe are happy to respond to additional concerns and questions.\n\n\n"}, {"review_id": "sT7tQCENdx", "reviewer": "Reviewer_NaRE", "summary": "The author propose a score-based method for causal discovery from multi-environment data. Identifiability of the causal model and the environment partition were shown for the proposed score function. The proposed algorithm was evaluated on synthetic and multiple real data sets. ", "questions": "Overall, I think the idea is interesting and promising, but the authors should check for typos carefully. ", "limitations": "No potential negative societal impact.\n\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The toy example provides a nice illustration of the proposed idea.\n\n2. Using a measure of the complexity of GP models as the score function for causal models is an interesting idea.\n\n3. There are sufficient evaluations on synthetic and real data sets.", "weaknesses": "1. The score function (4) is written in terms of the true conditional probability, while the empirical score function is not defined. In the algorithm, it was not mentioned how to estimate the score function using the data. \n\n2. There are missing explanations and plenty of typos in the main results. \n\nMissing explanations:\n\n(1) The role of the the penalty term $R(X_{S})$ in $(4)$ should be explained even it is from a previous work.\n\n(2) The term $L(h)$ in $L(X|\\mathcal{H})$ is not defined in Section 2.2.\n\n(3) How is $\\mathcal{H}_{k}$ constructed in the algorithm? How large is the function class? \n\nTypos:  \n\n(1) Whether the term $-log P(X_{i}|X_{S})$ in (4) should be $-log P(X_{i}|f(X_{S}))$ or something else? \n\n(2) LHS of (5) should be $X_{j}^{(c)}$.\n\n(3) $\\lambda$ in Theorem 3.2. is not defined in the score function.\n\n(4) \"Theorem3.1 assumes Assumptions 1-4, Theorem 3.2 assumes Assumptions 1-5, and Theorem 3.3 additionally assumes Assumptions 6.\"\n\n(5) $X_{S} \\subseteq X\\setminus X_{i}$ in (4).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your time and comments, please find our responses below.\n\n**Score function** \n> The score function (4) is written in terms of the true conditional probability, while the empirical score function is not defined. In the algorithm, it was not mentioned how to estimate the score function using the data. [...] \n> How is $H_\\kappa$ constructed in the algorithm? How large is the function class?\n \nIn practice, we fit a GP regression from the conditioning set to the target variable. Hence, we do not explicitly construct the hypothesis space $H_\\kappa$. As we noted in Section 3.1, since $\\kappa$ is the RBF kernel, $H_\\kappa$ is dense in the set of continuous functions. However, the beauty of GP models is that despite this it is simple to learn the optimal model from any finite sample. \nAs it is fairly standard in GP regression we omitted details on how to estimate the score function, but will make this more clear. \n \n**Missing explanations**\n\n> (1) The role of the the penalty term $R(X_S)$ in (4) should be explained even it is from a previous work.\n\nThe penalty is known as the regret term. For the regret of GP models, Kakade et al. (2005) give worst-case bounds [1]. We will add an explanation to our manuscript, thank you for pointing this out. \n \n> The term L(h) in L(X|H) is not defined in Section 2.2.\n\nThat is a good point, $L(h)$ refers to a length function or code for the model $h$, and its definition depends on the given model class. In section 3.2, it is given by $||f||_{\\kappa}^{2}$.\n \n> Overall, I think the idea is interesting and promising, but the authors should check for typos carefully.\n\nThank you for listing out typos, we will fix these in our revision. \n\nPlease let us know whether we could address your concerns and whether you have further questions.\n\n**References**\n \n[1] Kakade, Sham M., Matthias W. Seeger and Dean Phillips Foster. \"Worst-Case Bounds for Gaussian Process Models.\" *NIPS (2005)*.\n\n"}]

Author rebuttal:
**Summary Response to All Reviewers**

We thank all reviewers for their detailed comments and summarize our response to the main concerns below.

- **Identifiability from a single, few, or many contexts:** We clarify under which conditions the causal DAG is identifiable from a single context to motivate why we study identifiability from multiple contexts (`t48a`). We also state the implications of Thm. 3.3. on the number of contexts needed for DAG identifiability when we have no active control over the interventions (`t48a`), as well as explain the observation that LINC already discovers causal directions given a single context (``LpAE``).  

- **Additional explanations**: We provide additional explanations on our assumptions in the individual responses (``LpAE``,``oMbi``, ``NaRE``). We will add these to the manuscript as well as fix our assumption numbering.


We kindly ask the reviewers to take our responses into account in their scores, as we think that the feedback helped us strengthen the presentation of our work. We are happy to respond to follow-up questions.

Meta-review: A majority of reviewers are in favor of accepting this paper, however, the paper contains a critical omission that is needed before this paper can be accepted. In Section 2.2, the concept of algorithmic independence is mentioned, but never defined (in particular, see Postulate 2.1.1). This was explicitly flagged by Reviewer oMbi, while the rest of the reviewers unanimously agreed the assumptions were not clear and the writing was hard to follow. The authors, in their response, promise to "include the definition in the paper", but I fail to see why the definition was not included in the response itself. 

In looking this over myself, it is hard to gauge the usefulness of these results without an explicit, formal definition of algorithmic independence. It is worth noting that this concept has multiple definitions in the literature, and so the importance of formalizing this for the present paper cannot be overstated.  Fortunately for the authors, it does not seem that the main theorem statements rely on Postulate 2.1, although I'd like to see this explicitly clarified in the paper. Along these lines and more generally, the writing can be substantially improved, as noted by all the reviewers.

At the same time, a majority of reviewers agree there are some interesting new ideas in this paper, and recommend accept in spite of this omission. On this point I also agree, and am willing to recommend accept conditional on the authors addressing the above issue in their camera ready.
Decision: Accept (poster)