Causal Discovery in Heterogeneous Environments Under the Sparse Mechanism Shift Hypothesis
Authors: Ronan Perry
Julius Von Kügelgen
Bernhard Schölkopf
Venue: NeurIPS 2022 Accept (2022)
Keywords: causal discovery
sparse mechanism shift
causality
causal inference
distribution shifts
structure learning
heterogenous data
hypothesis testing

Abstract: Machine learning approaches commonly rely on the assumption of independent and identically distributed (i.i.d.) data. In reality, however, this assumption is almost always violated due to distribution shifts between environments. Although valuable learning signals can be provided by heterogeneous data from changing distributions, it is also known that learning under arbitrary (adversarial) changes is impossible. Causality provides a useful framework for modeling distribution shifts, since causal models encode both observational and interventional distributions. In this work, we explore the sparse mechanism shift hypothesis which posits that distribution shifts occur due to a small number of changing causal conditionals. Motivated by this idea, we apply it to learning causal structure from heterogeneous environments, where i.i.d. data only allows for learning an equivalence class of graphs without restrictive assumptions. We propose the Mechanism Shift Score (MSS), a score-based approach amenable to various empirical estimators, which provably identifies the entire causal structure with high probability if the sparse mechanism shifts hypothesis holds. Empirically, we verify behavior predicted by the theory and compare multiple estimators and score functions to identify the best approaches in practice. Compared to other methods, we show how MSS bridges a gap by both being nonparametric as well as explicitly leveraging sparse changes.

Causal Discovery in Heterogeneous Environments Under the Sparse Mechanism Shift Hypothesis
Ronan Perry', Julius Julius von Kügelgen" 1.2, and Bernhard Schölkopf 1
Max Planck Institute for Intelligent Systems, Tübingen, Germany Universstyy of Cambridge, United Kingdom
rflperry@us. edu, jvkštue mag.euuueeppp....m.m...m mpg. de, bs@tue mpg. de
Abstract
Machine learning approaches commonly rely on the assumption of independent and identically distributed (i.i.d.) data. In reality, however, this assumption is almost always violated due to distribution shifts between environments. Although valuable learning signals can be provided by heterogeneous data from changing distributions, it is also known that learning under arbitrary (adversarial) changes is impossible. Causality provides useful framework for modeling distribution shifts, since causal models encode both observational and interventional distributions. In this work, we explore the sparse mechanism shift hypothesis, which posits that distribution shifts occur due to a small number of changing causal conditionals. Motivated by this idea, apply it to learning causal structure from heterogeneous environments, where i.i.d. data only allows for learning an equivalence class graphs without restrictive assumptions. We propose the Mechanism Shift Score (MSS), a score- score-based approach amenable to various empirical estimators, which provably identifies the entire causal structure with high probability if the sparse mechanism shift hypothesis holds. Empirically, we verify behavior predicted by the theory and compare multiple estimators and score functions identify the best approaches in practice. Compared to other methods, we show how MSS bridges gap by both being nonparametric as well explicitly leveraging sparse changes.
Introduction
Classical machine learning methods and theory presume data to be independently and identically distributed (i.i.d.). Although there has been huge success under this assumption, research on topics including adversarial examples [17, 58), distribution shifts [9, 46, 48, 50), and "spurious" corre- lations [2] has highlighted its fragility. Open questions remain as to how we can relax the i.i.d. assumption and still learn useful models, since learning under unrestricted adversarial distribution shifts seems infeasible [7]. Causal models naturally provide structure to a distribution via a factoriza- tion into causal mechanisms, the processes by which variables are dependent Hence, they are a natural basis for studying distribution shifts. Based on the idea of the independence of causal mechanisms [41, 50], the sparse mechanism shift hypothesis [51] posits that distribution shifts are the result changes in only a subset of the causal model's 's mechanisms. This presents a promising relaxation with many potential applications throughout machine learning [3. 36, 37, 51, 61].
their direct causes.
In particular, causal discovery- the inference of qualitative structure encoded by a graph and un- derlying causal relationships between variables-is is a fundamental scientific problem with broad applications for which distribution shifts have been successfully leveraged. Classical approaches, which assume i..d. data from single environment or domain, can be broadly categorized into three
Shared author.
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

(4)
(B)
(C)
1.0
Fraction edges leamed
0.8
Method
X1
X1
Pooled
0.6
Sparsity
0.4
E
X2
X3
E
X2
X3
0.2
0.0
Sparse changes
Non-sparse changes
Number of environments
Figure 1: Sparse shifts yield structure identifiability. causal model with a fully connected DAG over X : (X,, X2, X3).. no edge directions can be learned from i..d. observational data. Given multiple datasets on X across different environments with possible distribution shifts, the PC algorithu [56] can be applied to the pooled data augmented by the environment index variable E [28]. (A) A mechanism shift E + X, can allow orientation of some edges. (B) Dense shifts prohibit any orientations [28]. (C) Combining results learned across pairy of pooled environments leads to identifiability under sparse shifts. Pooling all environments leads to dense shifts, even if pairs of environments differ sparsely; under dense shifts, only the equivalence class is learned.
classes. Constraint-based methods, such as the PC [56] and FCI [42] algorithms, perform a series of statistical independence tests to identify the existence of causal relationships under various as- sumptions (e.g.. causal faithfulness) and then use certain rules to infer causal directions. Score-based methods, such as GES [5], optimize some score function, such as the penalized likelihood BIC [52], over the set of possible graphs. These methods come with asymptotie structure identifiability guarantees of recovering the (Markov) equivalence class [15], but they will rarely uniquely recover the true causal graph. Further work on soneccionalffom---ee bosed methods, beginning with non-Gaussian assumptions [55], provides various ways to recover specific DAG by assuming certain functional form of the causal mechanisms [26, 30, 43, 63], at the cost of potential misspecification.
Although identification is possible through actively specified interventions [10, 11, 20, 21, 21, 54], natural distribution shifts on the same variables across different environments allow for promising approaches
under a relaxation of the i.i.d. assumption [8, 13, 14, 16, 18, 22, 23, 27, 28, 33-35, 38, 44, 50J. Such multii-envioommet methods can learn the direct causes of specific variable [23, 44] or the entire causal structure [13, 14, 28] without requiring knowledge of which causal mechanisms change. Yet, as noted in these work but not studied, performance dependent on which and how many changes occur.
Overview and contributions. After review of causal graphical models and formalization of our setting ($ 2), we discuss key related work on multi-environment causal discovery ($ 3). We demonstrate that sparse distribution changes provide structure identifiability in the bivariate case, and useful information in multivariate settings ($ 4). Based the observation that pairwise comparisons of environments better leverage sparse changes (see Fig. 1), we propose the Mechanism Shift Score, a basre- causal discovery algorithm with theoretical guarantees ($ 5). Empirical results confirm the theory ($ 6). In summary, the present work makes the following contributions:
We prove that by relaxing the i.i.d. assumption via the sparse mechanism shift assumption, bivariate causal structure identifiable without parametric assumptions (Cor. 4.2).
We introduce the Mechanism Shift Score (MSS), defined as the number of conditional distributions
implied by graph which change across all pairs of environments ($ 5). We prove that the true causal (multivariate) graph minimizes the MSS over possible graphs (Prop. 5.1).
We provide rates convergence showing that with sufficient number of sparsely changing envi- ronments, the causal graph uniquely minimizes the score function with high probability (Cor. 5.4). Our rates readily apply to existing literature on learning individual mechanisms [23, 44] and the entire graph [14, 28], where a study of the role of sparsity was previously missing.
We demonstrate empirically that sparsity and pairwise comparisons are useful and show how the MSS accommodates various parametric [13, 14, 44] and nonparametric [23, 28] estimators (8 6).
2 Problem setting and notation
We start by building up the causal framework needed to understand our work and related literature. It relies on common graph-theoretic terminology which we review for completeness in Appx. A.
Causal terminology. Causal relationships between variables are encoded a causal graphical model (CGM) which links graphical and distributional properties via certain assumptions.

---

Definition 2.1 (Causal Graphical Model (CGM)). A causal graphical model (CGM) M (G.Px) over d random variables X {X1 Xa) consists of (i) directed acyelic graph (DAG) G with vertices X and edges X; + Xj iff X; is a direct cause of Xj. (ii) and joint distribution Px which factorizes (is Markovian) over G. Formally, we have the following Markov or causal fuctorization:
d
Px Xa)
II
Px [x(X, PAj),
(2.1)
j=1
where PAj are the parents (direct causes) of X, in G and Px PAj) is the causal mechanism of Xj-
Implicit in the definition is the assumption that there is no hidden confounding, i.c., that any common cause of two or more observed variables is included in X; for this reason also referred as causal sufficiency. This is strong assumption to make and important to keep in mind in applications.
The Markov factorization (2.1) of the CGM encodes various conditional independences between variables. The Markov equivalence class (MEC) is the set of DAGs which share the same set of con- ditional independence relations; graphically, it is the set of DAGs which share the same skeleton (set of edges regardless of direction) and v-structures (X; - X3 f Xx. but X; f Xτ)) [45, Lem. 6.25]. A set of DAGs such as the MEC commonly represented graph (CPDAG) in which edges are directed if directed in all DAGs in the set, and otherwise left undirected [19]. Incorrect DAGs in the MEC induce non-causal factorizations containing non-causal conditionals which differ from the true causal mechanisms. Furthermore, in a CGM, equation (2.1) is equivalent to the global Markov condition which states that for disjoint vertex sets A, B, Z in G:
completed partially directed acyclic
A G B Z = A 1 B Z
(2.2)
where L denotes d-separation in G (Appx. A) [45, Thm. 6.22). While the Markov property allows us derive distributional properties from the DAG, causal discovery concerns deriving graphical properties from distributional properties. This requires the causal faithfulness assumption, effectively assuming that variables not statistically independent unless implied by the graph.
Assumption 2.2 (Causal faithfulness). The observational distribution Px is said to be faithful to the causal graph G if every conditional independence relationship in IPx implies d-separation in G (i.e., d-connection implics statistical dependence [45, Def. 6.33]).
Multi-enyiromment data. We assume that we observe a collection D of datasets from a set & of (possibly different) environments, where each dataset D from environment contains ne independent and identically distributed (i.i.d.) observations from some joint distribution P
D= (D', (D),.., ...., D" } where D -
X
} i.d. PP for E
Environments can encapsulate experimental settings, or broader contexts such as climate or time [38]. key assumption of our setting that environments arise from different "soft" interventions on an underlying shared CGM M. Specifically, the CGM M entails a set of interventional distributions, resulting from changing a subset of the mechanisms (x PPA,) to some different Px (X, (PA,). ). Assumption 2.3 (Shared mechanisms). Each environment e independently results from M by
intervening (unknown) subset I C [d] of mechanisms, i.e., P can be written
(X Xa)
P Px(X,, PAA) JEZZ
II
II jE(dJYZ
Fx(X, PAA).
(2.3)
We make the following common assumption about how these changes arise.
Assumption 2.4 (Independent causal mechanisms (ICM) [41, 50]). A change in P(X; PA,) has no effect on and provides no information on P(Xx PAs) for any + j.
Since causal mechanisms are fixed within an environment and potentially vary across them, we can create an augmented CGM to unify CGMs from different environments. Note that in Asm. 2.3 and the following definition, the same causal parents and DAG are preserved over different environments; the distribution changes are limited to soft interventions which do not change variable's causal parents.
Throughout, assume the existence of densities with respect the Lehesgue measure.
'Note that this includes "hard" interventions (X, PA,) = 8(X, - x) which fix X, to specific value and also "soft" interventions which merely alter the functional relationship.
3

---

Definition 2.5( (Augmented CGM (28]). Let { ((G, be collection of CGMs over the DAG G = -XX,,77 T) from multiple environments. The augmented CGM is defined as M' := (G', Pxue) where (i) E' is a random environment indicator variable with support E, and (ii) the augmented DAG G" has vertices X U E and edge set T (() Ee,e' E E s.t. PP (X)(AA))) + Px (X, PA 9)
Note that PX E is Markovian to G", inheriting the factorization from the underlying CGMs along with the added dependence on E. With respect to the augmented DAG, Asm. 2.4 implies that existence of the edge + X; provides no information on the existence of an edge E + X; for j A i. As discussed by Huang et al. [28], since E can be a common cause of variables in X, causal sufficiency the original CGM over is violated. We instead must assume pseudo-causal sufficiency. See Appx. C for further discussion of this assumption and the ICM principle.
Assumption 2.6 (Pseudo causal sufficiency [28]). Any unobserved confounders of variables in X can be written solely as functions of E. Thus, within any given environment e, all unobserved confounders are fixed and causal sufficiency holds.
Sparse mechanism shift (SMS) hypothesis. Another key assumption, supported by Asm. 2.4's implication that a change to one mechanism does not imply changes to others, is the following: Assumption 2.7 (SMS [5.]). Changes in mechanisms between observed environments are sparse:
0 < I < d
(2.4)
The value of this assumption when met is illustrated in Fig. 1 and will be elaborated upon in 5.
3 Related work on causal discovery from multiple environments
Causal discovery from changing distributions and causal mechanisms has a long history, going back to Simon's invariance criterion, stating that the true causal order is the one that is invariant under the right sort of intervention [24, 25]. Tian and Pearl [59] infer causal order by testing which marginal distributions change under a single intervention. Invariant causal prediction (ICP) [44] can identify the causal parents of a target variable under the assumption that the target's causal mechanism is invariant across environments [23, 44, 50]. However, applying ICP to each variable in order to learn all sets of causal parents and hence the causal graph is not immediately admissible: the invariance assumption would imply that all variables are invariant, and thus there are no mechanism changes to learn from.
Learning the MEC from i.i.d. data is well-studied problem, and under certain assumptions, essentially solved [5, 42, 56]. In our multi-enviromment setting. Yang et al. [62] characterized the I-MEC, subset of the MEC, which was subsquently generalized to a M-MEC [29] under an unknown observational environment. Brouillard et al. [4] developed an estimator under unknown intervention targets, but none of these works implement an algorithm or perform experiments on soft interventions with unknown targets. Ghassami et al. [13] apply ideas from linear ICP identify the causal DAG. Assuming linear causal mechanisms in which only the noise distributions change, they compare pairs of environments and orient edges meet this requirement. Ghassami et al. [14] allow for any kind of change within linear model, demonstrating that the causal DAG minimizes the number of changes in the linear model parameters. Squires al. [57]. like Jaber et al. [29], extend this approach to nonparametric setting by applying existing methods to an augmented graph containing additional nodes for each pair of environments (see Appx. C.3 for more detailed discussion). In contrast, Huang et al. [28] apply the PC algorithm on the augmented CGM, pooling all the data as in Mooij et al. [38]; this identifies the MEC but more importantly can also orient additional edges. Since not all edges are guaranteed to be oriented, Huang et al. [28] propose second stage, relying on a novel measure of mechanism dependence to individually orient remaining edges.
A consistent yet sparingly explored theme across all of these methods is the unique identifiability of the true DAG, rather than an equivalence class, and the impact of the sparsity of changes across environments. Although existing works [29, 57, 62] characterize and identify subsets of the MEC, requirements on the identifiability of the true DAG are unclear. In ICP, it is briefly noted that the method is applicable when the target variable experiences sparse shifts, as long as we assume a maximum degree of sparsity [44, $6.2). Although not discussed, the performance of methods from Ghassami et al. [13, 14] also depend on sparsity. As mentioned by Huang et al. [28], identifia- bility requires the invariance of some mechanisms and their pooled PC approach cannot identify edge directions when both adjacent variables change. We will provide clarity on identifiability via sparsity.
4

---

E
E
E
E
X1
X2
X1
X2
X1
X2
X1
X2
(a) P(Xi) changes
(b) P 2 Xi) changes
(c)
Neither change
(d) Both change
Figure 2: (a. b) Visualizations of two cases explored
proof Prop. 1. both cases, X2 1
unconditionally and X, Y E' X2 directly or by conditioning on the potential collider X2. (c. d) The two other possible situations; neither allow us to orient the edge between X₃ and X2.
4 Leveraging sparse mechanism changes for causal discovery
The augmented DAG is powerful tool for understanding the implications of changing causal mechanisms, We build up intuition in the bivariate setting and then consider the general multivariate setting. From now on, we assume causal faithfulness on the augmented CGM.
Bivariate Given causal model composed of associated variables, identifiability of the causal direction requires assumptions such as the functional form or existence of targeted interventions [45, $4.1]. We show how sparsely changing mechanisms also provide identifiability.
Proposition 4.1 (Both non-causal conditionals change). Consider the bivariate setting X, X2. If either causal mechanism P X1) or P(X,) changes, then both P(X, X2) and P(X2)) change.
Corollary 4.2 (Bivariate identifiability). In the setting of Prop. 4.1, if only one causal mechanism changes (sparsity), then the bivariate causal structure is identifiable
Proof. (Prop. 4.1) We consider each case separately and use proof by contradiction (of faithfulness).
(i) If P(X,) changes (see Fig. 2a), then Gx_ contains the edge + X1. If I( remained invariant, then X2 1 E (unfaithful due the unblocked path F. X1 X2). If Pf X2)
remained invariant, then X, 1 X2 (unfaithful due to the direct path E X1).
(ii) PXX, X1) changes (see Fig. 2b), then GxuE contains the edge E - X2. If P(X,) remained invariant, then X₂ 1 E (unfaithful due the direct path E - X2). If P(X, X2) remained constant, then X1 1 E X2 (unfaithful due to the unblocked collider path E + X2 t X1).
Proof. (Cor. 4.2) If either causal mechanism changes, by Prop. 4.1 both conditionals in the non-causal factorization change. Hence, the causal structure is the one with only mechanism change.
Multivariate case. Non-causal conditional distributions of X2 may change across environments even if the causal mechanism (X, PA,) does not change. This occurs if the conditioning set leaves open a dependence between and X, in GXUE-
Lemma 4.3. For any X3 E and set S XXX (X₂}. the conditional distribution P(X, ZZ) changes if and only if the following d-commectedness relationship holds:
X; Gxxu E E Z.
The result follows from the Markov property and faithfulness; for all complete proofs, see Appx. B.
Since the Markov equivalence class relatively easily available and thus often the starting point of open questions in causal discovery, we specify the implications of Lemma 4.3 in this setting, Note that due to the shared skeleton all DAGs in the equivalence class, the conditioning set for any X; in any DAG in the MEC a subset of Xj's true parents and children PA U CHÓ [34, 56).
Corollary 4.4. For any variable X, E X and set C (PAÇ U UCH)) in the augmented graph, the conditional distribution P(X; Z) changes if and only if at least one of the following holds:
(i) E + Xj [a direct cause).
(ii) 3W E G Z such that Wps G E [unblocked path to unconditioned parent].
(iii) 3WCH E C n Z such that WCH LxxUE E Z WcH [unblocked path conditioned child).
5

---

PA
12
PA
PA.2
PA
PADZ
E
X
E
X
CH
CH
CH
CH
CH
(i): direct cause
(i): an unblocked ancestor
(ii): a conditioned child's ancestor
Figure 3: The three possible cases from Cor. 4.4 with d d-connecting path from E' to Xj. conditioned subset of neighbors (colored in grey) in the MEC; these neighhors subset of the parents and children.
Proof sketch. These cases are visualized in Fig. 3. The global Markov property and faithfulness assumption allow to interchange d-connection and distributional change. In the forward direction, a changing mechanism implies d-connecting path which necessarily captured in one of the three cases. In the reverse direction, each case opens d-connecting path between X; and E.
A direct result of changing causal mechanisms and conditional distributions follows.
Corollary 4.5. Let G* denote the true (unaugmented) DAG and lel G be any other DAG over the same variables. For any Xj E X, change in (Xx, f implies change in PXX, )
Proof. Under the true causal parents given by G change in mechanism occurs if and only if E Xy in G X So, X, is d-connected E, no matter the conditioning set Z C X X (X₃}. Thus, by Lemma 4.3, P(X, P necessarily changes.
Causal discovery via the Mechanism Shift Score (MSS)
We have established that changing mechanisms provide useful information and by Cor. 4.2 can provide identifiability in the bivariate case under faithfulness and sparse changes. We now study identifiability in more general graphs along with approaches to developing practical estimators. Motivated by the novel discovery of the value of comparing pairwise environments changes are sparse, we propose the Mechanism Shift Score (MSS) estimand with useful thcoretical guarantees over DAGs in the MEC.
The MSS estimand. with data sampled from ng distributions P := {P& Te we count the number of changing condi- tional distributions graph
Given a set 9 of candidate DAGs over the same variables X [X,, Xa)
by defining
MSS,
(X + P (X/)PA and MSS(G; Σ (G;
MSS, P) the number of pairs of environments in which the conditional distribution of X, in G changes; (SS(G;P) is the total number of changes across all variables and pairs of environments according to the Markov factorization implied by G. follows from Cor. 4.5 that the true DAG G" minimizes (not necessarily uniquely) the number of changing conditionals among all DAGs.
Proposition 5.1. Let G* be the true DAG in the set G of DAGs. Then for all G E G and j E (I.
MSS, (G*; < (G;))G;P)
and thus
MSS(G"; P) MSS(G;P).
Proof. By Cor. 4.5, any change in PXX, (AA"") implies change in P(X, |PA)) for any other
DAG G. Thus, any change counted by MSS, on the true DAG will also be detected in every other DAG and so both lower bounds hold.
Prop. 5.1 can be viewed as the generalization of the Principle of Minimal Changes [14], allowing for mechanism changes beyond the parametric restrictions of a linear model. Identifiability, however, requires us establish discerning aspect of the true structure. Recall that the Markov equivalence class GMEC is identifiable. We define the subset
Gmin =
arg min MSS(G;P)
Gegme
of DAGs with minimum MSS, here defined the number of mechanism shifts across environments.

---

It turns out that AME is V-MEC with respect to the true but unknown intervention targets {Ir} as characterized by Jaber et al. [29]. We defer further details and the proof of this correspondence to Appx. B and focus our results on unique identifiability of the true DAG here.
In practice, we may employ any generic conditional test for change in mechanism or choose "softer" score (e.g., based on p-values) to quantify changes along a continuous spectrum. This is a similar idea to that of Brouillard et al. [4] who propose a multi-environment likelihood-basse approach.
Prop. 5.1 implies that G E g Using probabilistic assumptions based on the idea of sparse changes, we show that, given enough environments, the causal parents and full DAG are identifiable.
Lemma 5.2 (Identifiability of causal parents). Let G be the true DAG in the MEC Gunc and p: the probabiliiyy that the causal mechanism of X; is different across any two environments. Under Asms. 2.2 to 2.4 and 2.6, for any j E {l....,dd d}, graph G E Grne such that PAA G # PA and lower and upper bounds on the shift probabilities pt < Ps S ps for all i, we have that
(IMSS,((G"PP < MSS, P)] 2 1 (1 (1 Pj 118 min p) (ne/2
Proof sketch. From Cor. 4.5, we know: MS S MS We use the shared skeleton property of all DAGs in MEC and Cor, 4.4, for which only case (i) admits changing mechanism in the true DAG, Based on the ICM principle, we examine sufficient conditions in a pair of environments and establish probabilistic upper bound on all pairs.
Note that this bound is independent of the other DAG G. so long as is in the MEC and has a different set of causal parents. As special case of Lemma 5.2, invariance of the mechanism of Xj implies p = 0 and hence provides a bound relevant to invariant causal prediction [23, 44]. Building off of Lemma 5.2, can provide probabilistic bound identifiability of the whole graph.
Theorem 5.3 (Identifiability of the graph). Let G be the true DAG in the MEC Gsne and P3 the probability that the causal mechanism of X, is different across any two environments. Under assumptions 2.2, 2.3, 2.4, and 2.6, and bounds p. S Ps S pi for all i, we have that
[ne/2]
Prigmic MEC = {G* 2 1 - - 1 1 (1-(1-
min "h minp,")
Proof sketch. From Prop. 5.1. G is always in Gmee For each DAG, we use Lemma 5.2 to bound the probability that all mechanisms exhibit the same number of changes. Then we apply the union bound to establish an upper bound across all DAGs.
Corollary 5.4. If pa is bounded away from and for all i, (a probabilistic form of Asm. 2.7).
Prigiic
(G + as Tig - OC
That is, with enough environments we can recover the true DAG from the Markov equivalence class.
Proof. The assumption of bounded probability implies that p. < 1 and p. > 0 for all i. Hence, by the rate established in Thm. 5.3, identifiability is achieved in the limit.
The MSS estimator. An empirical MSS estimator tests if two conditional distributions change across two environments. This can be done using conditional independence tests or equality of distribution tests [39]. Under parametric assumptions, models may be fit for each mechanism, and these parame- ters can then be tested across environments [13, 14, 44]. Heinze- Deml et al. [23] provided a compre- hensive study of such tests and their power for ICP. More recent but less studied work by Park et al. [40] has provided a kernel-based approach with strong guarantees. In practice care must be taken when using equality of conditional distribution tests, especially if any of their assumptions are violated [53].
Computational complexity. The score function MSS(G; P) is decomposable [19] in that it is the sum of local scores MSS, MS PG: In the most na've approach, each mechanism in each of [M DAGs must be tested across all pairwise environments, on the overall order of O [dn)), without accounting for the complexity of the statistical test. This can be slow, but if the test runtime scales with sample size n faster than On)²), then pairwise tests may actually faster than pooling the data. In practice, the decomposable property permits speedup: since many mechanisms will be shared across DAGs, we can test each unique mechanism and then select the results relevant for each DAG. Experimentally, find the main bottlenecks to be large sample sizes and numbers of environments.
7

---

1.0
MSS (aracle)
Pooled (oracie) [25]
Recall
0.8
0.4
0.1
0.9
0.1
0.9
Environments
fraction
Edge density
Variables
Figure 4: Oracle rates match the theory. From left to right (a-d): (a) With sufficiently many environments, our MSS approach learns the true DAG while pooled PC recovers only the original MEC. (b) Pairwise comparisons are less heneficial when shifts are extremely sparse or dense. Differences across the two methods are particularly pronounced both in (c) sparse and dense DAGs, as well as in (d) smaller DAGs. Shaded regions denote 95% confidence intervals calculated from bootstrapped data.
Structure learning experiments
Having established the theoretic value of the MSS estimand, we seek to understand empirically; (i) how the oracle MSS and pooled PC approaches compare across experimental settings, (ii) which MSS estimators perform best, and (iii) how the MSS compares to related approaches. For ease of comparison, we adapt the simulation setup Huang et al. [28]. Random DAGS are sampled using an Erdōs-Rènyi model [12] in which each edge has some fixed probability of existing (the edge density). In each environment, a random set of variables experience a mechanism change according to a fixed number fraction of shifts. Each variable in environment has randomly sampled mechanism
X9 = EiEra, (X))+
(6.1)
where bys ~ 4(0.5,2.55 of ~ U(,, and ej ~ -O 1) or (1(13) with equal probability. The functions by: are selected uniformly at random from {x² _² tanh, sinc]. Mechanisms in an unobserved baseline environment are sampled and oz 1 is fixed. Each observed environment inherits the baseline distributions and mechanisms shifts are resampled per (6.1).
We evaluate the quality of an estimated CPDAG against the true DAG via precision and re- call [13, 14, 28). Precision is the fraction of directed edges in the CPDAG which are correctly oriented. Recall is the fraction of all edges in the CPDAG which are oriented. Thus, the true DAG has perfect precision and recall. Since all methods start from the MEC, there are no incorrect edges, only incorrect orientations. For oracle methods, the precision is perfect and so we only report the recall.
Oracle MSS rates match the theory. Having theory on learning rate bounds under sparsity, we now seek to understand how the empirical performance of MSS and pooled PC depends on variety of graph and sparsity settings, both which our theory does and does not address. We consider random DAGs over 6 variables with edge density 0.3. Five environments are sampled, in each of which half of the mechanisms shift. Fig. 4, we hold all of these settings fixed and vary one at time across 50 repetitions, comparing the recall of the two methods." 5 Precision is always perfect under the oracle test.
In the first two plots, the empirical results match what the theory predicts. First, per Cor. 5.4, with more environments MSS learns the entire graph while pooled PC learns nothing but the original MEC. Second, per Thm. 5.3, the learning rate decreases when shifts either uncommon frequent. Furthermore, we see that differences between the two approaches are accentuated in sparse and dense DAGs, well in smaller DAGs. Note that sparsity fixed fraction of the variables, and hence larger DAGs experience more shifts in absolute terms. See Appx. D for additional oracle experiments.
MSS performance depends on the chosen estimator. Next, we study how the choice of estimator and type score affects performance. We use two popular conditional independence tests, the Fisher-Z partial correlation test [31] and the Kernel Conditional Independence (KCI) test [65]. as well as the invariant residual test using a generalized additive model (GAM), a top- top-performing ICP method [23]. Each detects change if the test p-valuc is less than 0.05/d. /d, Bonferroni correction to bound the false positive rate for each scored DAG. Although the theory pertains to counting shifts, in settings where "hard" hypothesis test has low power it may be of more value
A All code and experiments available
http://wwww..oe../epe/s/rrreeeee -sift 5 "Oracle methods used code from the causaldag package [3-Clause BSD license]. KKII and Fisher- Z are implemented by the causal learn package [GNU General Public License].
8

---

(A)
Recall
0.5
PIP2
Picg
mm Fmon
1.0
Precision
Mek
Erk
Test (above)
(below)
MS5 (KCT)
MSS (KCT)
Hard
Raf
(GAM)
Pooled (KCT) [25)
Soft
MS5 (RsherZ)
MC [13]
1.0
Recall
0.5
31k
Precision
1.0
PKA
P38
0.8
PKC
Samples
Environments
Shift fraction
Edge density
Variables
Figure 5: (A) Nonparametric hypothesis tests perform well nonlinear simulations. and soft scores succeed. Notably, recall converges with increasing environments. KCI appears to best halance high recall and precision. (B) In simulation, pairwise approaches improve with more environments, unlike Pooled PC. Although the parametric MC works surprisingly well across settings, the nomparametric MSS with KCI has superior precision and recall. (C) MSS (KCI) edge orientations mostly match the real data Sachs network [49]. Non-matching odges (red) are posited be involved cycles and of ambiguous orientation the literature.
to use a "softer" score (e.g., based on p-values) to quantify changes along a continuous spectrum. We propose the following "soft" score (see Appx. C for further details):
MSS = E
p-vaue (P*(X; PA5) + P (X,
(X, IA
DAGs are generated on six variables with edge density 0.3. Three environments are sampled, with 500 samples and mechanism shifts per environment. We vary each variable while holding the others fixed and compare results across 50 repetitions.
As seen in Fig. 5(A), the Fisher-Z test performs noticeably worse, presumably due unmet parametric assumptions, while the nonparametric approaches do well, particularly at higher sample sizes. As with the oracle, the true DAG is recovered with enough environments. The "soft" versions achieve higher recall, since there is unique minima, at the cost worse precision (see Appx. C.2 for greater discussion). The "soft" KCI seems to be best, suggesting that KCI models the data the best, In practice, is crucial for a method to model the data well for the p-value to be valid [53].
MSS compares favorably against other methods. Next, we compare MSS to relevant existing methods: the Minimal changes (MC) approach [14] tests pairs of environments for changes in the parameters of a linear model, and Huang et al. [28] provide nonparametric version a two-stage approach which first uses PC with the KCI test on the pooled data. We investigate if pooling data loses information under empirical tests, and how the nonparametric pairwise MSS test compares.
In Fig. 5(B,, we compare these approaches in the previously studied experimental setting. Pooled PC has quite high precision (as it pools all of the data), but suffers from lower recall, especially with more environments when recall is no better than the base MEC. In contrast, "hard" KCI has higher recall at the cost of some precision when individual environments have few samples. The parametric MC works surprisingly well, yet slightly worse than KCI. Overall, MSS seems combine the best of both approaches: the value of pairwise comparisons from MC with the flexibility of incorporating various nonparametric estimators. Additional experiments in Appx. D confirm this in the bivariate case.
Protein network discovery. As an illustration of our method in practice, we conduct case-study ap- plication of MSS for causal discovery imental environments of 11 cellular proteins. Starting from the Sachs MEC, we apply the MSS using the KCI test, which appears to perform the best among plug-in estimators for MSS in our simulations.
well-studied cytometry dataset [49] consisting of 9 exper-

---

The DAG which minimizes the MSS is the unique minimizer and is visualized in Fig. 5(C). Learndd edge orientations mostly match the Sachs network [49]. Non-matching edges, shown in red, are posited to be involved in cycles and of ambiguous orientation in the literature: PIP2 - PIP3 is known to be a cyclical relation [47, 49], Mek - Raf is indeed found by many other methods [8, 38, 47], and although there is not a detailed discussion of the PKA, PKC, P38 triangle, there is ambiguity in the edge directions among approaches [8, 38, 47], as we discuss in more detail in Appx. D.3.
7 Discussion
Sparse shiftss as a relaxation of the i..d. assumption. Distribution shifts are a common violation of the i.i.d. assumption and a problematic source of error in practice. It has been argued that the issue of robustness to natural shifts is connected to causality [1, 32, 44, 50, 60, 61, 64]. We have shown that viewing a shift in distribution through the causal factorization permits a useful relaxation of the i.i.d. assumption, facilitating causal discovery: if there are no shifts (i.i.d),, we can only identify equivalence classes. If shifts are unrestricted, we cannot meaningfully transfer across distributions [50], and ideas such as Simon's 's invariance criterion [25] and ICP [44] do not help. However, if shifts occur sparsely-as as we formalize- we can provably use this as a learning signal to infer the causal structure.
The Mechanism Shift Score (MSS) and prior methods. The MSS framework extends previous causal discovery work limited to linear mechanisms [14), just as nonlinear ICP [23] extended the initially limited ICP approach [44] beyond linear models. Huang et al. [28] do provide a useful nonparametric approach, but we have demonstrated, by pooling all of the data in their first stage they lose out on the value of sparse shifts in identifying the true graph. The MSS is both nonparametric and explicitly leverages sparsity through pairwise comparisons. Our accompanying graph-theoretic analysis proves why pairwise comparisons are actually useful, and our learning rates apply these previous works to provide insight on the role of sparsity.
Beyond causal discovery. Once the causal graph is known, conditional distributions and hence an entire causal graphical model can be learned. This is harder than learning statistical model, but has various ad vantages, especially when distributions shift, as they do in reality. E.g., we may be able to use such model for causal reasoning. i.c., estimating certain causal effect. We also expect that MSS can serve as a useful inductive bias for causal representation learning, similar to how invariant predic- tion [44, 50] inspired invariant risk minimization [32]; recent work has started to explore this [34, 36].
Empirical performance and limitations. We infer causal structure through a flexible score-based method; as empirically demonstrated, strong results can be obtained by multiple estimators when the assumption of sparsity met. This requires hypothesis tests which can accurately obtain the full MEC as a starting point and subsequently test for distribution changes. Among additional assumptions in- cluding the stringent pseudo-causal sufficiency, sparsity is necessary and yet not easily verifiable; SMS is indeed hypothesis regarding causal systems, not fact. We conjecture that under oracle, the "hard" MSS is equivalent to the PC algorithm pooled pairwise across environments. It is worth noting that the "hard" approach may still be useful under dense changes if only a sparse number of them are large enough to be empirically discernible. Thus the empirical method can actually outperform the oracle baseline and be useful even if the assumption of sparsity is unmet. We also assume that a partition into environments is known, but environment inference techniques may help relax this [6].
axis of complexity, from the microscopic physical laws of nature to a simplified set of variables and relationships, we transition from a system with no mechanism shifts (effectively a dynamical system) to system in which all mechanisms shift (due to many unmeasured causes). In the middle, we posit only a sparse number of shifts to be empirically discernible. While all (causal) modely are wrong, the one which is most invariant to shifts may be the best candidate for supporting robust and transferable inference.
Outlook and conclusion. Imagining causal models
Acknowledgments and Disclosure of Funding
We thank Jonas Kübler, Junhyung Park, Krikamol Muandet, Luigi Gresele, the Tübingen causality team, and the anonymous reviewers for helpful comments. This work was supported by the German Federal Ministry of Education and Research (BMBF): Tübingen AI Center, FKZ: 011S18039A, 011S1 NIIS18039;; and by the Machine Learning Cluster of Excellence, EXC number 2064/1 Project number 390727645. Ronan Perry was supported by Fulbright Germany research fellowship.
10

---

References
[1] Elias Bareinboim and Judea Pearl. Transportability from multiple environments with limited experiments: Completeness results. In Z. Ghahramani, M. Welling. C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27, pages 280-28 288. Curran Associates, Inc., 2014. 10
[2] Sara Beery, Grant Van Hor,, and Pietro Perona. Recognition in terra incognita. In Proceedings of the European Conference on Computer Vision, pages 456-473, 2018.
[3] Yoshua Bengio, Tristan Deleu, Nasim Rahaman, Nan Rosemary Ke, Sebastien Lachapelle, Olexa Bilaniuk, Anirudh Goyal, and Christopher Pal. A meta-transfer objective for learning to disentangle causal mechanisms. In International Conference on Learning Representations, 2019.
[4] Philippe Brouillard, Sébastien Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien, and Alexandre Drouin. Differentiable causal discovery from interventional data. Advances in Neural Information Processing Systems, 33:21865-2187777 2020. 4,7
[5] David Maxwell Chickering. Optimal Structure Identification With Greedy Search. Journal of Machine Learning Research, 3(Nov):507-55% 2002. ISSN 1533-7928. 2, 4
[6] Elliot Creager, Jörn-Henrik Jacobsen, and Richard Zemel. Environment inference for invariant learning. In International Conference on Machine Learning, pages 2189-2200. PMLR, 2021.
10
[7] Shai Ben David, Tyler Lu, Teresa Luu, and David Pal. Impossibility Theorems for Domain Adaptation. In Proceedings of the 13th International Conference on Artificial Intelligecce and Statistics, pages 129-136. JMLR Workshop and Conference Proceedings, March 2010.
[8] Daniel Faton and Kevin Murphy, Exact bayesian structure learning from uncertain interventions. In Marina Meila and Xiaotong Shen, editors, Proceedings of the Eleventh International Confer- ence on Artificial Intelligence and Statistics, volume 2 of Proceedings of Machine Learning Research, pages 107-114, San Juan, Puerto Rico, 21-24 Mar 2007, PMLR. 2, 10, 25, 26
[9] Frederick Eberhardt. A Sufficient Condition for Pooling Data. Synthese, 163(3):433-442, 2008. ISSN 0039-7857. Publisher: Springer.
[10] Frederick Eberhardt and Richard Scheines. Interventions and Causal Inference. Philosophy of Science, 74(5):981-995, 2007. ISSN 0031-8248. 2, 20
[11] Frederick Eberhardt, Clark Glymour, and Richard Scheines. On the Number of Experiments Sufficient and in the Worst Case Necessary to Identify All Causal Relations Among N Variables. In Proceedings of the 21st Annual Conference on Uncertainty in Artificial Intelligence, pages 178-184, 2005. 2
[12] Paul Erdös and Alfréd Rényi. On the evolution of random graphs Publication of the Mathemat- ical Institute of the Hungurian Academcy of Sciences, 5(1):17-60, 1960.
[13] Amir Emad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Kun Zhang. Learning causal structures using regression invariance. in Proceedings of the 31st International Conference Neural Information Processing Systems, page 8
Curran Associates Inc., 2017. 2, 4,
[14] Amir Emad Ghassami, Negar Kiyavash, Biwei Huang, and Kun Zhang. Multi-domain Causal Structure Learning in Linear Systems. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. 2, 4, 6, 7, 8, 9, 10
[15] Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based on graphical models. Frontiers in Genetics, 10, 2019. 2
[16] M. Gong, K. Zhang, T. Liu, D. Tao, C. Glymour, and B. Schölkopf. Domain adaptation with conditional transferable components. In Proceedings of the 33rd International Conference on Machine Learning, volume 48, pages 2839-28444 2016. 2

---

[17] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- sarial examples. International Conference on Learning Representations, 2015. 1
[18] Siyuan Guo, Viktor Tóth, Bernhard Schölkopf, and Ferenc Huszár. Causal de Finetti: On the Identification of Invariant Causal Structure in Exchangeable Data. arXiv:2203. 15756 [cs, math, stat], March 2022. arXiv: 2203.15756 2, 20
[19] Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs. Journal of Machine Learning Research, (3(1))2409-2444 2464, August 2012. ISSN 1532-4435. 3,7
[20] Alain Hauser and Peter Bühlmann. Two Optimal Strategies for Active Learning of Causal Models from Interventional Data. International Journal of Approximate Reasoning, 55(4): 926-939, June 2014. 2
[21] Yang-Bo He and Zhi Geng. Active Learning of Causal Networks with Intervention Experiments and Optimal Designs. Journal of Machine Learning Research, 9(84):2523 2547, 2008. ISSN 1533-7928. 2
[22] Yango He and Zhi Geng. Causal Network Learning from Multiple Interventions of Unknown Manipulated Targets. arXiv:1610.068 08611, October 2016. 2
[23] Christina Heinze-Demll Nicolai Meinshausen, and Jonas Peters. Invariant causal prediction for nonlinear models. Journal of Causal Inference, 6-2):1335, 2018. 2, 4, 7, 8, 10
[24] Kevin D. Hoover. The logic causal inference. Economics and Philosophy, 6:207-234, 1990.
4
[25] Kevin D. Hoover. Causality in economics and econometrics. In S. N. Durlauf and I.. E. Blume, editors, The New Palgrave Dictionary of Economics. Palgrave Macmillan, Basingstoke, UK, 2nd edition, 2008. 4, 10
[26] Patrik Hoyer, Dominik Janzing, Joris M Mooij. Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. In Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2009. 2
[27] Biwei Huang, Kun Zhang, Jiji Zhang, Ruben Sanchez-Romero, Clark Glymour, and Bernhard Schölkopf. Behind distribution shift: Mining driving forces of changes and causal arrows. In IEEE International Conference on Data Mining (ICDM), pages 913-918. IEEE, 2017. 2
[28] Biwei Huang. Kun Zhang, Jiji Zhang. Joseph Ramsey, Ruben and Bernhard Schölkopf. Causal discovery from beccrogencouushoonstttonnnn data. Journal of Machine Learning Research, 21 2020. 2, 4, 8, 9, 10, 20, 21
Romeeo, Clark Glymour,
[29] Amin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Causal Discov- ery from Soft Interventions with Unknown Targets: Characterization and Learning. In Advances in Neural Information Processing Systems, volume 33, pages 9551-9561. Curran Associates,
Inc., 2020. 4, 7, 16, 21
[30] Dominik Janzing, Joris Mooij. Kun Zhang, Jan Lemeire, Jakob Zscheischler, Povilas Daniušis, Bastian Steudel. and Bernhard Schölkopf. Information geometric -eformtttonngcommtricc approach to inferring causal
directions. Artificial Intelligence, 182-183:1-34 May 2012. ISSN 0004-3702. 2
[31] Markus Kalisch and Peter Bühlmann. Estimating High- Dingh-Dimessional Directed Acyclic Graphs with the PC-Algorithm. Journal of Machine Learning Research, 8(22):613-636, 2007. 8
[32] Pritish Kamath, Akilesh Tangella, Danica Sutherland, and Nathan Srebro. Does invariant risk minimization capture invariance? In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference Artificial Intelligence and Statistics, PMLR, 13-15
volume 130 of Proceedings of Machine Learning Research, pages Apr 2021. 10
[33] 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 preprint 190.01210 2019. 2
12

---

[34] Sebastien Lachapelle, Pau Rodriguez, Yash Sharma, Katie E Everett, Rémi LE PRIOL, Alexan- dre Lacoste. and Simon Jacesne-Julien. Disentanglement via mechanism sparsity regularization: A new principle for nonlinear ICA. In Ist Conference on Causal Learning and Reasoning, 2022.
5,
[35] Vincenzo Lagani, Ioannis Tsamardinos, and Sofia Triantafillou. Learning from Mixture of Experimental Data: A Constraint- Approach. In Artificial Intelligence: Theories and Applications, volume 7297, pages 124-131. Springer Berlin Heidelberg, 2012. ISBN 978-3-
642-30447-7 978- 978-3-644-33044-44 2
[36] Phillip Lippe, Sara Magliacane, Sindy Löwe, Yuki M Asano, Taco Cohen, and Efstratios Gavves. CITRIS: Causal identifiability from temporal intervened sequences. In Proceedings of the 39 th International Conference on Machine Learning, 2022. Workshop on the Elements of Reasoning: Objects, Structure and Causality. 1, 10
[37] F. Locatello, B. Poole, G. Rätsch, B. Schölkopf, O. Bachem, and M. Tschannen. Weakly- supervised disentanglement without compromises. In Proceedings of the 37th International Conference Machine Learning, volume 119 of PMLR, pages 6348-6488000 6359. PMLR, July 2020.
[38] Joris M. Mooij, Sara Magliacane, and Tom Claassen. Joint Causal Inference from Multiple Contexts, Journal of Machine Learning Research, 21(99):1-108, 2020, ISSN 1533-7928. 4, 10, 20, 21, 25, 26
[39] Sambit Panda, Cencheng Shen, Ronan Perry, Jelle Zorn, Antoine Lutz, Carey E Priebe, and Joshua Vogelstein. Nonpar manova via independence testing. arXiv preprini arXiv: 0111999900000... 2021.
[40] Park, U. Shalit, B. Schölkopf, and K. Muandet. Conditional distributional treatment effect with kernel conditional mean embeddings and u-statistic regression. In Proceedings of 38th In- lernational Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8401-8412. PMLR, July 2021.
[41] Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, 2000.
1, 3
[42] Peter Spirtes, Christopher Meek, and Thomas S. Richardson. An Algorithm for Causal Inference in the Presence of Latent Variables and Selection Bias. In Clark Glymour and Gregory F. Cooper, editors, Computation, Causation and Discovery, chapter 6, pages 211-252. The MIT Press, May 1999. 2,4
[43] Jonas Peters, Joris M. Mooij, Dominik Janzing, and Bernhard Schölkopf. Identifiability of causal graphs using functional models. In Proceedings of the 27th Conference on Uncertainty Artificial Intelligence, UAI' page 889-598, Arlington, Virginia, USA, 2011. AUAI Press. ISBN 9780974903972. 2
[44] Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society: Series B (Staristical Methodology), 5(78):947-1012 2016. 2, 4, 7, 10
[45] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference. The MIT Press, 2017. 3, 5, 15
[46] Joaquin QuineeneroCCanelaa Masashi Sugiyama. Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. Mit Press, 2008
[47] Joseph Ramsey and Bryan Andrews. FASK with Interventional Knowledge Recovers Edges from the Sachs Model. arXiv:1805.03108 [cs, q-bio], May 2018. arXiv: 1805.03108. 10, 25, 26
[48] Mateo Rojas-Carully Bernhard Schölkopf, Richard Turner, and Jonas Peters. Invariant models for causal transfer learning. The Journal of Machine Learning Research, 1901):109-1132,
2018. 1
13

---

[49] Karen Sachs, Omar Perez, Dana Pe' er. Douglas A Lauffenburger, and Garry P Nolan. Causal protein-signaling networks derived from multiparameter single-cell data. Science, 308(5721): 523-529, 2005. 9, 10, 25, 26
[50] B. Schölkopf, D. Janzing. J. Peters, E. Sgouritsa, K. Zhang, and J. Mooij. On causal and anticausal learning. Proceedings of the 29th International Conference on Machine Learning, pages 1265-1262. Omnipress, 2012. 1, 2, 3,4, 10
[51] B. Schölkopf, F. Locatello, S. Bauer, N. R. Ke, N. Kalchbrenner, A. Goyal, and Y. Bengio. the
Toward causal representation learning. Proceedings the IEEE Advancess in Machine Learning
and Deep Neural Networks, 109(5)6612-66 634, 2021. 1,4
[52] Gideon Schwarz. Estimating the Dimension of Model. The Annals of Statistics, 6(2):661 464, 1978. 2
[53] Rajen D. Shah and Jonas Peters. The hardness of conditional independence testing and the generalised covariance measure. The Annals of Statistics, 48(3):1514 1538, 2020. 7, 21
[54] Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros Dimakis, and Sriram Vishwanath. Learning causal graphs with small interventions. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 28, 2015. 2
[55] Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear non-gaussian acyclic model for causal discovery. Journal of Muchine Learning Research, 7(10), 2006. 2
[56] P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction, and Search. MIT press, 2001.
2, 4,
[57] Chandler Squires, Yuhao Wang, and Caroline Uhler. Permutation- -Based Causal Structure Learning with Unknown Intervention Targets. In Conference Uncertainty in Artificial Intelligence (UAI), volume 36, pages 1039-1048 PMLR, August 2020. 4, 21
(58) Christian Szegedy, Wojciech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014. 1
[59] Jin Tian and Judea Pearl. Causal discovery from changes. In Proceedings of the Seventeenth conference on Uncertainty in Artificial Intelligence, pages 512-521, 2001. 4
[60] Victor Veitch, Alexander Amour, Steve Yadlowsky, and Jacob Eisenstein. Counterfactual Invariance to Spurious Correlations: Why and How to Pass Stress Tests. Advances in Neural Information Processing Systems, 34, 2021. 10
[61] von Kügelgen, Y. Sharma, L. Gresele, W. Brendel, B. Schölkopf, M. Besserve, and Locatello. Self-supervised learning with data augmentations provably isolates content from style. In Advances in Neural Information Processing Systems 34 (NeurIPS 2021), pages 16451-16467, December 2021. 1, 10
[62] Karren Yang, Abigail Katcoff, and Caroline Uhler. Characterizing and learning equivalence classes of causal dags under interventions. In International Conference on Machine Learning, pages
PMLR, 2018. 4
[63] K Zhang and A Hyvärinen. On the identifiability of the post-nonlinear causal model. In 25th Conference on Uncertainty in Artificial Intelligence, pages 647-655. AUAI Press, 2009.
[64] K. Zhang, M. Gong, and B. Schölkopf. Multi-source domain adaptation: A causal view. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, pages 3150-3157, 2015. 10
[65] Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. In Proceedings of the 27th Conference on Uncertainty Artificial Intelligence, page 804-813. AUAI Press, 2011. ISBN 9780974903972. 8
14


Reviews:
[{"review_id": "ytThIzv3T1O", "reviewer": "Reviewer_qyjw", "summary": "This paper proposes a score-based approach for causal discovery (Mechanism Shift Score) using non-iid data from multiple environments under spare mechanism shifts. It provides theoretical analysis for the proposed approach, as well as empirical experiments.", "questions": "-In evaluation, why do you use a data generation mechanism where the effect of parents and noise is additive? Does this method not work for a more general data generation mechanism? Why?\n\n-Comparison with \"https://arxiv.org/abs/1910.01075\" would be interesting.\n\n-Why don't you show F-1 scores for evaluation?\n\nLine 285: rates' instead of rates\nLine 234: Corollary 4.4 instead of Lemma 4.3", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Although the Sparse Mechanism Shift hypothesis and its application for causal discovery is not new, this paper provides a sound method for using it by designing a score and analyzing it theoretically.\n\nPros: \n-The presentation is clear and easy to follow.\n-The problem is significant in many areas of science.\n\nCons:\n-Evaluation in the main body is limited to only a synthetic data generation mechanism.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IIP81HpTiu", "reviewer": "Reviewer_m9g9", "summary": "This paper focuses on the identifiability of causal graphs up to CPDAG in heterogeneous environments. Specifically, they explore the assumption of minimal changes in causal conditionals across different environments. This assumption of sparse mechanism shift is a non-parametric extension of the Principle of Minimal Changes [1]. With this as the hypothesis, a score-based method that identifies the entire causal structures with high probability has been proposed.\n\n-------\n\n[1] Amir Emad Ghassami, Negar Kiyavash, Biwei Huang, and Kun Zhang. Multi-domain Causal\nStructure Learning in Linear Systems. In Advances in Neural Information Processing Systems,\nvolume 31. Curran Associates, Inc., 2018.", "questions": "Please let me know if the points/questions listed as the cons are due to my misunderstanding of the manuscript.", "limitations": "It seems that there is no obvious discussion of limitations. Please let me know if I missed anything.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n1. The idea of exploring sparse mechanism shifts in a non-parametric setting is original and of interest to the community.\n2. The theoretical results and assumptions have been rigorously stated.\n3. The background and related works have been well introduced, which make the general picture clearer.\n4. The writing is very clear.\n\nCons:\n\n1. From Fig. 6, one could observe that MSS (KCI), which is based on the proposed score, doesn't outperform other baselines w.r.t. precision. More discussion about the reason would be appreciated.\n\n2. I didn't find a clear statement/discussion of the limitation of the model. In the checklist, the limitation part has been pointed to the third paragraph of Sec. 7. However, it seems that no limitation has been clearly discussed in this Section. The most related part is the paragraph of 'Empirical performance and the validity of the sparse mechanism shift hypothesis.', but I still fail to see the discussion of limitations. Perhaps a direct discussion of them could be helpful?\n\n3. Regarding [2], it has been mentioned in the manuscript that, compared to the proposed method, the disadvantage of [2] is that it is not suited for sparsely-detectable changes. Since the sparse change is basically the assumption made in this manuscript but not in [2], I'm wondering whether it is a valid/fair point in general cases.\n\n\n\n-----------------\n\n[2] Biwei Huang, Kun Zhang, Jiji Zhang, Joseph Ramsey, Ruben Sanchez-Romero, Clark Glymour, and Bernhard Schölkopf. Causal discovery from heterogeneous/nonstationary data. Journal of Machine Learning Research, 21(89):1–53, 2020.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2xLGUcXNfJI", "reviewer": "Reviewer_Rbq8", "summary": "In this paper, the authors proposed a causal structure learning algorithm based on the \"sparse mechanism shift hypothesis\" which says that distribution shifts across environments occur due to a small number of changes in the causal conditions. They introduced the \"Mechanism Shift Score\" which is the number of causal conditions changing across all pairs of environments, showing that the true causal graph minimizes this score. Furthermore, they showed that with enough changes across environments, the true causal graph can be identified. ", "questions": "1- The class of graphs that are identified by the proposed method should be characterized. Is it equivalent to I-Markov or $\\Psi$-Markov class? I think the results in Theorem 5.3 is fairly straightforward.\n\n2- I think one of the main issues of the proposed approach (and also the one in [25]) is that we need many environments to perform accurate conditional independence tests. \n\n3- Can this work be extended to the case that we have latent confounders? For instance, the result in [Jaber et al. 2020] allows the latent confounders.\n\n4- In the experiments, it is better to compare different methods (including the missing references) in terms of F1 score and SHD.", "limitations": "I think it is a theoretical work and the authors clearly mentioned the assumptions in their work.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In this paper, the same augmented graph in [25] is constructed. However, instead of pooling all data, pairwise comparison among environments is considered which might give more information as shown in Figure 1. The paper is generally well written and the assumptions are clearly mentioned. However, it seems that some of the related works are missed. For instance, in [Brouillard et al. 2020], a score function for the setting of multi-environment with unknown target interventions has been proposed where the true causal graph can be identified up to an I-Markov equivalence class. There, it is assumed that the distribution of one of the environments is observational and there is no intervention on any variable, and we are aware of which environment has this property. Later, [Jaber et al. 2020] relaxed this assumption and defined an equivalence class for the setting of multi-environment with unknown target interventions (called $\\Psi$-Markov equivalence) and characterized this class. Furthermore, they proposed an algorithm that is sound and complete. I believe the submitted paper should compare the results here both theoretically (whether it can recover causal structures that cannot be identified with previous work) and also experimentally. \n\n\n[Brouillard et al. 2020] Brouillard, P., Lachapelle, S., Lacoste, A., Lacoste-Julien, S., & Drouin, A. (2020). Differentiable causal discovery from interventional data. Advances in Neural Information Processing Systems, 33, 21865-21877.\n\n[Jaber et al. 2020] Jaber, A., Kocaoglu, M., Shanmugam, K., & Bareinboim, E. (2020). Causal discovery from soft interventions with unknown targets: Characterization and learning. Advances in neural information processing systems, 33, 9551-9561.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept