Causal discovery with endogenous context variables
Authors: Wiebke Günther
Oana-Iuliana Popescu
Martin Rabel
Urmi Ninad
Andreas Gerhardus
Jakob Runge
Venue: NeurIPS 2024 poster (2024)
Keywords: causal discovery
context-specific causal discovery
selection bias
SCM
causal models
endogeneous context variables
regime-specific causal discovery
endogeneous regime variables
context-specific independence
Primary area: causal_inference

Abstract: Systems with variations of the underlying generating mechanism between different contexts, i.e., different environments or internal states  in which the system operates, are common in the real world, such as soil moisture regimes in Earth science. Besides understanding the shared properties of the system, in practice, the question of context-specific properties, i.e., the change in causal relationships between contexts, arises. For real-world data, contexts are often driven by system variables, e.g., precipitation highly influences soil moisture. Nevertheless, this setup needs to be studied more. To account for such endogenous contexts in causal discovery, our work proposes a constraint-based method that can efficiently discover context-specific causal graphs using an adaptive testing approach. Our approach tests conditional independence on the pooled datasets to infer the dependence between system variables, including the context, to avoid introducing selection bias. To yield context-specific insights, conditional independence is tested on context-specific data. We work out the theoretical framework for this adaptive testing approach and give a detailed discussion of the connection to structural causal models, including sufficiency assumptions, which allow to prove the soundness of our algorithm and to interpret the results causally. A simulation study to evaluate numerical properties shows that our approach  behaves as expected, but also leads to a further understanding of current limitations and viable extensions.

Causal discovery with endogenous context variables
Wiebke Günther 1.2+ Oana-Iuliana Popescu 1.2+ Martin Rabell,3,4
Urmi Ninad 1.2 Andreas Gerhardus' Jakob Runge" .2,3,4
German Aerospace Center (DLR), Institute of Data Science, Jena, Germany Teechiische Universität Berlin, Institute of Computer Engineering and Microelectronics, Berlin, Germany
CCnter for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI) Dresden/ / Leipzig, Germany
*Technische Universität Dresden, Faculty Computer Science, Dresden, Germany Cana-iulia, popescuddlr de
"qqul contribution
Abstract
Causal systems often exhibit variations of the underlying causal mechanisms between the variables of the system. Often, these changes driven by different environments or internal states in which the system operates, and we refer to context variables those variables that indicate this change in causal mechanisms. An example are the causal relations in soil tempprat-eemperature interactions and their dependence soil moisture regimes: Dry soil triggers dependence of soil moisture on latent heat, while environments with wet soil do not feature such a feedback, making
context-specific property. Crucially, regime or context variable such as soil moisture need not be exogenous and can be influenced by the dynamical system variables precipitation can make a dry soil wet leading to joint systems with endogenous context variables. In this work we investigate the assumptions for constraint-busee based causal discovery in systems with endogenous context variables. We show that naive approaches such as learning different regime graphs on masked data, or pooling all data, can lead to uninformative results. We propose an adaptive constraint-based discovery algorithm and give a detailed discussion on the connection to structural causal models, including sufficiency assumptions, which allow to prove the soundness our algorithm and to interpret the results causally. Numerical experiments demonstrate the performance of the proposed method over alternative baselines, but they also unveil current limitations of our method.
context-specific information
1 Introduction
In recent years, causal discovery (CD), that is, learning cause-effect relationships from observational data, has garnered significant interest across various domains, from Earth sciences and genomics to industrial settings (1I 26 I. Such complex systems often exhibit a change of causal mechanisms over time or across different environments, including changes in the associated causal graph. An example are the causal relations between surface heat and latent heat and their dependence on soil moisture regimes: When the soil is dry, triggers dependence of soil moisture on latent heat due to the dry soil reflecting heat, while environments with wet soil do not feature such feedback. These changing causal mechanisms can be represented using so-called contexts, where the causal mechanisms and structures vary depending on the states of one or more context variables that augment the assumed underlying structural causal model 7 [5). Both time-series (29) and non-time-series data can exhibit such behavior. Context-dependent systems have been widely studied; see Mooij et al.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(15) for a review. Context variables (15 34 18 have also been called selection variables (77 or regime indicators (33 29) in the literature.
Causal discovery on such systems is challenging 7 13) and methods for CD in case of systems with changing causal mechanisms typically assume that the context variable is exogenous, as will be discussed below and in Sec. 3.2 Yet there exist many real-world examples where the context indicators are endogenous. A regime/context variable such as soil moisture can be influenced by the dynamical system variables - precipitation can make a dry soil wet 1it-leade leading to joint systems with endogenous context variables, as illustrated in Fig. ] where we show a hypothesized causal model of the drivers of soil moisture (SM). Understanding context-specific causal relationships is crucial for applications such as extreme event forecasting and for enhancing our general understanding of dynamical systems.
Figure I: In this strongly simplified example, the variable soil moisture (SM) is an endogenous context variable influenced by variables such as precipitation (TP) and latent heat flux (LH) both wet and dry regimes of SM, represented by solid edges. In dry conditions only, feedback loop from the latent heat flux to the soil moisture is created because the soil additionally reflects the heat, represented by the dashed edge (a feedback loop is a time-delayed cycle, leading to a cyclic summary graph representation while the underlying time-series graph remains acyclic).
TP
LH
SM
Our work investigates the assumptions for constraint-based CD on such systems. A core difficulty in treating endogenous context indicators is that context-specific CD methods which resort to masking, i. e., conditioning the context of interest and ignoring data from other contexts, e.g., 7 (2). can introduce selection bias if the assumption of exogenous context variables violated. For example, applying CD only on samples from the dry context in the soil moisture problem of Fig. would introduce a spurious correlation between the precipitation and latent heat flux. Other methods apply CD the pooled data, i.e., the concatenated dataset containing all contexts. Then allowing for endogenous variables is possible (I5), but does not yield context-specific information, i.e., no distinction between solid and dashed edges in Fig. can be made. We propose an adaptive constraint- based discovery algorithm that allows to distinguish context-specific causal graphs and give a detailed discussion of the connection structural causal models, including sufficiency assumptions, which allow to prove the soundness of our algorithm and to interpret the results causally.
Context-speede -peecfcc graphs contain more information than union graphs pooled data, i.c., the dashed edges in in Fig. [] This information can under suitable assumptions be discovered by additionally taking context-specific independencies (CSIs) into account. CSIs are independence relations that only present when data of a single context is viewed in isolation. Naively searching through all CSIs would lead an inflated search space of available independence tests. Further CSIs necessarily use only a reduced sample size which can also increase error rates. Indeed, a simple baseline method we compare against suffers from increased error rate, whereas our proposed method is able avoid an inflation of required tests. This is achieved by an masytto-implemen decision rule which allows to adaptively decide for one and only one test to be executed per separating set. Whenever consistent, tests are further executed on the pooled dataset, thus on all available data.
We now summarize contributions: (1) We propose general framework for adapting existing constraint- constraint-based CD algorithms to extract context-specific information, in addition to joint infor- mation, about skeleton graphs when contexts are (potentially) endogenous without inflating the number of required independence tests. (2) We give an SCM-based interpretation of this additional consider
information and unveil interesting and little-studied difficulties whose understanding essential to the problem. (3) We work out the theoretical assumptions under which our proposed method soundly recovers the context-specific skeletons despite these difficulties. (4) We conduct simulation study to numerically evaluate the performance of the proposed method and understand the failure modes of current approaches.
2 Related work
The problem of CD from heterogeneous data sources has gained interest in recent years. Mooij et al. (4) offers a broad overview of the topic and groups recent works on CD for heterogencous data

---

into two categories: Works that do CD separately on each context-specific dataset (the data points belonging specific context) and works that use the pooled datasets (all data points). Works that obtain context-specific graphs apply CD on the context-specific dataset, where the assignment to contexts is either known & 24), identified before applying CD 12 36), or iteratively learned (29). The information from the context-specific graphs can then be summarized in single graph, the so-called union graph.
Mooij et al. 14) propose the Joint Causal Inference (JCT) framework to deal with multi-context CD by modeling the context variable and using CD on the pooled datasets to uncover the relationships between the context and system variables, where the context can also be endogenous. Several CD methods can be extended for JCL, e.g., FCI (32). FCI is also applied in
(28) 10) on the pooled data to discover causal relationships among all variables. Zhang et al. (39) test for conditional
independence between system and context variables on the pooled dataset under the assumption of
exogenous context variables. Constraint-based CD for the multi-context case has also been studied con---ostraint-aaan baaeed methods, Peters et al. (9;;; Heinze-Deml et al. (6) exploit the invariance of the conditional distribution of target variable given its direct causes across multiple contexts, while Zhou et al. (41) find causal structure by modeling the direct causal effects functions of the context variables. Although not directly methodically related, CD for cyclical graphs is also relevant to our problem, as cycles can appear between the different contexts (8) B). Most mhove-mentionels methods using both context-specifis and pooled data assume, either implicitly or explicitly, that the context variable is exogenous. This is possibly due to the fact that, for context-specific approaches, endogenous variables might lead to selection bias, while for methods that use pooled data it suffices to treat endogenous variables as any other variable in the graph. In our work, discover context-specific causal graphs for the case of endogenous context variables. Assuming access to the context variable, we obtain information from the pooled and context-specific graphs. We focus on the non-time-series case and leave the extension to time-series for future work.
specifically for the time-series case, e.g., (29 33 5). Among
Labeled Directed Acyelic Graphs (LDAGs) (18) are conceptually closest to our work. LDAGs summarize context-specific information in graphical form by assigning a label to each edge according to the context in which dependence arises. Hyttinen al. (9) propose constraint-based method to discover LDAGs from data similar to our approach: A variant of the PC algorithm that tests conditional independence of X II YIR r within each context R instead of testing X 11. YJR on the pooled data. We discuss how our definitions of context-specific graphs fundamentally differ from CSIs in Sec. 3.1 and delimit work from LDAGs in App. A
3 Formal description
We first briefly outline preliminary definitions (see, e.g., (16) for detailed definitions). We then point out an unexpected difficulty of our approach in the connection SCMs and its remedy.
Preliminaries We work within the framework of structural causal models (SCM) (16). We define the set of observed endogenous variables (X;) which take values in X, with finite index set T. Let V == {X, i E /} represent the set of all endogenous variables. The set of (hidden) exogenous noises ins, taking values in Ar is denoted U == {n I i E 1}. For any subset A C V, let
X' := I[EE Xz. We denote X' := Xy and N := Nu.
A set of structural equations F= = [fali E 7} is a set of parent sets (Pa(i) C VičE together with functions S; : XPa(t) XN; + X. An intervention Fao(A=g) subset C V is replacement of fy + 9, for j E A. We will only need hard interventions, 93 = I. = const below.
Given distribution P., of the noises U = (m. her. collection of random variables V = [X, satisfies the structural equations F on if X; = fi fi((X))serat)) T.). An SCM A is a triple M = (V, U,U,F). where V solves the structural equations F given U. The intervened model Ma (g)) is the SCM Mao(A=g) == U, Fdo(A=g)). A causal graph describes qualitative relations between variables; given a collection of parent-sets (Pa her, on the nodes I add a directed edge p >> for all i E and all p E Pa,. See next section Sec.
We assume all SCMs are uniquely solvable, i. e. given F and U, there is a unique V solving these structural equations. This is not restriction for the per-regime acyclic models considered later.
3

---

We observe data from system with multiple. slightly different SCMs, corresponding to contexts and indicated by a categorical context indicator variable, as illustrrtedd in example 3.1 This variable R E V is a variable whose value indicates the context, i.e., the dataset to which the data point belongs. Therefore, the value-space of R defines all datasets, and its values associate data points to datasets.
Example 3.1. Given binary context indicator variable R and multivariate mechanism of the form
Y fr my) ((R))(()) + ny,
the dependence X - Y is present in the context R 1, but absent for R 0. This entails context-specific independence (CSI) IL Y|R = 0 and X y =
3.1 SCMs for endogenous contexts and their associated graphs
In order to create connection between CSIs and SCMs, we define multiple graphical objects. We motivate their necessity and exemplify them in Sec. 3.2
Given set of structural equations, F, we define the mechanism graph G[F), constructed via parent sets Pa, specified via FF (see "causal graphs" above). Given a pair consisting of set of structural equations F, and the (support of) distribution of the observables P(V) we define the observable graph GIF, PJ. constructed via parent sets Pag C Pa, (of X;), such that j & Pag if and only if for all values pa of Pa; - [j} the mapping Ij + fü sulppp ((Pa.) (2ij, pa, тk) is constant (where defined).
The union graph of an SCM M (VM, UM JM,, where V is distributed according to PM. is the observable graph
Guniia M == G[ PM]
which consolidates the information from multiple contexts into a unified graphical representation. J = -Fuinn satisfies standard minimality assumptions 2 Def. 2.6), then G[ = Grunion [M] (given faithfulness, Sec. 4.2) thus corresponds to the causal graph in the standard sense. Given an SCM M with a context indicator R. there are multiple meaningful sets of structural equations and multiple meaningful associated distributions
observables, which result in multiple observable graphs associated to the SCM M; an overview provided in Table [ in the appendix, see also Fig, 2 and the next subsection. We thus distinguish multiple context-specifie graphs. The descriptive graph
fi [M] = (o Par (V =))]
captures relations present in the intervened model's mechanisms F. Rmr) (the SCM in the context r) and encountered in observational data together with this context; the last point is formalized by restricting our attention to the support of Par (V = r). For edges not involving R, the same information is contained in G[FM, (V = r)] using the unintervened F, which supports the intuition that the context-specific graph captures the overlap of observations and the context of interest. Since R is a constant per-context, we add edges involving R from the union graph to Gdessr [M] and denote the result Geeeer R (M). The result very different from an independence graph of the conditional distribution: There are no edges induced by selection bias in Gft [M].
The physical graph encodes the differences from the union graph necessary to describe the context consistently and describes the intuitive notion of R. introducing physical changes in mechanisms:
Gohys = G[FM (V)]
Importantly, the context-specific graphs defined above depend only on the SCM, without making explicit or implicit reference to independence. This sets them apart from graphical representations of independence structure like LDAGs (18): LDAGS are graphical independence models describing context-specific independence (CSI) structure of dataset. However, a causal analysis requires an understanding of interventional properties, which, in turn, requires inferring knowledge about the causal model properties. In the single-context case, under the faithfulness assumption, knowledge about the causal properties of models is directly connected to the independence structure. As will be explored Sec. 3.2 this direct connection cannot generally hold the multi-context case. Thus, an important open problem is the connection of CSI structure to the underlying causal model. Such relation given in Sec. 4.2 connecting properties of the underlying causal model represented by context-specific graphs to CSI structure.

---

3.2 Two problems of CD with endogenous context variables
In this section, we describe two main problems encountered with context-specinee causal discovery and illustrate them by two examples. In the columns of Fig. 2 systems with the following SCMs:
we show the different graphs of
Example 3.2. The mechanisms X := T',, :- "/ and the binary threshold exceedence R := [X + T + nR) > t] E {0, agree for both systems. (i) For the system depicted in the left column of Fig. 2 Y = R. 9(T) 1Jy is function of R with the dependence on T explicitly disabled for R = 0. (ii On the right-hand side, Y == max(T,Tip ) + 7y, ,, is not a function of R, but assume
P(T > Tol R = 0) < 6, such that given R 0 automatically max(T, To) = To and hence the dependence of Y on becomes negligible for R = 0.
Selection bias Endogenous context variables can pose problem for context-specific CD if the context variable is driven by multiple other variables, and is thus collider. As described in Sec. 2 methods to obtain context-specific graphs typically apply CD the context-specific dataset, thus essentially conditioning on the context variable. If the context variable is collider
Gunion
Grasted
descendant thereof, this approach leads to selection bias (red edge in Fig. 2 This is subtle issue: From an independence structure viewpoint, the dependence between X and T exists yet does not seem make any intuitive sense and does not admit causal semantics. A formal description in which the absence of this edge is considered correct as it should be for a causal analysis requires the underlying model as starting point. Indeed the graphs defined above from the SCM directly (also shown in Fig. 2 consider the absence of this edge correct.
Calyss
T
Gileser
x
R
Left: An example of an SCM where the physical and descriptive graphs are the same. Right: an example of SCM where the physical and de- scriptive graphs differ, c.f. the "support problem". For Grusk, R is not shown, as it is a constant per dataset, and links with other variables will not be found. Con- text specific graphs depend on the value r of R and are summarized in a single di- agram containing a solid edge for edges that are present in both contexts, and a dashed edge for edges that are present for exactly one of the two contexts.
Figure 2:
The support problem A second problem is encountered, because CSI can arise in two different ways from given model: Either by an explicitly disabled dependence as in the first example, or indirectly through the lack of ob- servational support in specific context. Note that, in Fig. [2] our graphical models capture this difference: Once Greeer Gohys (left-hand side), while in the other case Cresser + Gohys (right-hand side).
Concerning the second example in Ex. 3.2 in particular, we make the following observations: (a) There is no evidence for the absence of the link T + Y.c.g e.g. when considering interventional questions. (b) The absence of the link does
correctly describe an independence, e. gg edge orientations, cycle resolution, or function fitting on the respective data. Thus, for these problems, the link T + Y is not required for a meaningful description in the context
R = O. (c) R is adjacent to T, but we could add an intermediate node T - M - R without changing the problem, so adjacency of Rt to the changing link is not guaranteed. (d) We lack observations of another context variable R²' which indicates whether > To. and would suffice to fully describe the qualitative structure of the mechanism at Y. Observations (a) and (b) demonstrate that there is not single "correct" graph to learn, and the additional ficxibility of observable graphs introduced above is necessary. (a) and (b) also make it clear, that it should be carefully specified what should be learned for a particular application and what could be learned (see Sec. (.TI.. and what a specific algorithm will learn (see Sec. 4.2) Finally, CD heavily relies restricting the search space for separating sets to adjacencies, which becomes non-trivial in sight of (c). We will return to (d) momentarily.
In our setup, the context indicator is given by the user. The context indicator can either arise naturally from the problem setting, or it can be the result of preprocessing using anomaly or regime detection methods (see also Sec. F.2) Since the indicator is chosen, it becomes important to understand which context indicator makes for a good choice in view of the problems illustrated above. core contribution of our work is to understand which assumptions about the model, including the choice
5

---

of context indicator. prevent drawing wrong conclusions. We give suitable assumptions to make the problem tractable and the result interpretable (in terms of SCMs) in Sec. 3.3 based on observation (d).
3.3
Assumptions
We now define the assumptions that a proper context indicator must fulfill such that our causal discovery method yields meaningful results. These regime sufficiency assumptions are described below and further formalized in Sec. [ the general approach and the naming are inspired by observation (d) made above and its resemblance to causal sufficiency.
Sufficiency assumptions regarding the context indicator The support problems in Example 3.2 iii
occur if the qualitative change in the causal mechanisms does not involve the observed context indi- cator R directly, cf. (d). Therefore, we define the strong context-sufficiency assumption (Def. C. which enforces that the qualitative changes in the graph involve R directly as displayed in Example 3. We also define single-grapb-sufficiee
(Def. C.2 which enforces that certain context-specific graphs collapse to the same graph. This is weaker assumption than the strong sufficiency above, see Cor. C.1 but still suffices to proof soundness of our algorithm and even allows for strong interpretation of results as encoding physical changes; this is thus a technically better, albeit less intuitive and potentially harder to verify directly, assumption.
The reduced search space for CSI, cf. (c) in 3.2 happens already under the assumption of weak context-sue sutlieet-suufiiienyyyy (Def. C.3), which formalizes dependence on R in the weak sense of being adjacent in the graph. This is yet weaker assumption, see Cor. C.2 still ensures useful output from our algorithm (Rmk. D.2), but does not allow for strong (physical) interpretation of the results anymore. These assumptions mirror the causal sufficiency assumption: They exclude hidden contexts and lead to fewer CITs and a stronger interpretation of results as physical changes. We further discuss the hierarchy of these assumptions in Sec. C.T
hidden confounders). Fur- thermore, we require at least weak (descriptive) confext-acyclicity (Def. C.5). i.e., Gjeer is DAG (acyclic) for all r. In practice, we assume strong (descriptive) context-acyclicity (Def. C.5). meaning there are further no cycles involving any ancestors of R (including It itself) in the union graph. Efficient discovery with our method requires directed cycles of length 2, as discussed in We assume that R is a categorical variable which takes finitely many values
Additional assumptions We assume causal sufficiency (Def.
Sec. D.7 Sec.
D.8
with P(R
4 Causal discovery with endogenous context variables
We propose a method to discover context-specific graphs and their corresponding union graph which extends the PC(-stable) algorithm (11 4 with a novel adaptive testing strategy, In Sec we will connect the output of our method to the graphical objects defined in 3.1 In particular, under suitable sufficiency assumptions the output is precisely Galyss The approach is not specific to PC but could also be used with other constraint-baa algorithms.
4.1 Method
Formal details are given in Sec. 4.2 First observe that for physical changes (edges in Gunion not in GRS) or under weak context-suffiiiency (Def. C.3 3, the only changes in Gohyss relative to the union graph occur downstream of the context indicator, more precisely in the adjacencies of its children (lemma C.4). On the other hand, spurious links due to selection bias occur upstream of the context indicator (cf. See 3.2 By either of the context-acyclicity assumptions introduced above, these two cases are mutually exclusive. Skeleton discovery has to find a valid separating set Z to remove any edge X to Y which is not in the context-speciff Golys R=r- By assuming an appropriate version of faithfulness, the decision between independence testing on the context-specific data or on the pooled data does not matter for all other candidates S for Z, as long as we decide correctly for (one) valid S. On the other hand, under causal sufficiency valid So C Pa(Y') exists by a suitable Markov-propertyy Thus R E So implies R is parent of Y and we are in the first case, thus should test on the context-specific data. By mutual exclusiveness, we can consistently of selection bias. Conversely R & So implies R is not a parent of Y, and there is no context-specific
so without the risk

---

information to be obtained here; thus testing on the pooled data is consistent (it does not loose information), avoids selection-bias bias (X and Y could ancestors of R) and uses all available data. Thus for the valid So we will by this decision rule always use the correct test.
Algorithm 1 Adaptive CD for Discovering Context-Specifie Graphs with Endogenous Context Variables
Context indicator R, Samples for X1,..., XD: Xn R 2: Output: Context-specific graphs Gi=rr Vr E (1,..., n7)
1: Input:
3: for r to ny do
4: Initialize Grer as fully connected graph
5: for sepselaize 0 to D do
6: for each j E {l,..... D, R do
7:
for each E Ad)(X,) and S Adj(X) - {i} with #S sepsetsise do
8:
Test X; 11 X R, = if R E S, else test X, 1L Xy|S on pooled data if independence found then Remove edge X; - Xj from G Orient edges as in PC algorithm return {Gr= | (l,...,..) n.
9:
10:
12:
Discovering context-specific graphs First, we discover GREr which, under the assumptions of Thm. []] agrees with both the descriptive and the physical graph. For a fixed context value R r. we adapt the skeleton phase of the standard PC algorithm described in (4) to test on the pooled data whenever R is not in the conditioning set. Whenever R is in the conditioning set, the algorithm tests X 1L Y|Z, R = r instead of X IL ZZZ, R, as described in Algorithm 1
Obtaining the union graph To obtain the union graph, we combine the information about the edges in all context-specific graphs as follows: If the edge from X to Y is found in none of the context-specific graphs, then no edge added the union graph. If an edge X - Y was found in any of the context-spedte -ppexxt- graphs, then the directed edge is added to the union graph. The resulting graph may contain both the edge X Y and the edge X Y. See also Sec. D.14
Scaling properties We study univariate context indicators, but our approach allows multiple indicators. A discussion on the time complexity of our algorithm for this case can be found in Sec. D.9
4.2 Theoretical results
Markov properties The Markov property ensures that links that should be removed, are removed from suitable independence relations.
Lemma 4.1. Assume strong context-acyelice causal sufficiency and bongle-graph-sufficee and Y, both X,Y Y + R, with & deser (X) (this not a restriction by context-acyclicity, rather fixes notation), are not adjacent in G R=r then there is Z C. Adj (Y) such that: If is neither part of a directed cycle in the union graph (union cycle) nor child of R in the union graph (union child), then (a) X 11 Y otherwise (b) X Z Rr..
If X
Cseese
Remark 4.1. If either X = R or Y = R, then there is no per-context test available. In this case, fall back to the standard result: If X and Y are not adjacent in ACyel(Gunion) then there is
Z C Adj dedeerr (Y) or Z C Adjlewr (X) such that X Il Z (see Sec. D.4p.
The full proof can be found in Sec. D.3 The idea is as follows: Case (a) is relatively standard and follows by a buoh-blocking" argument (37). We focus on case (b), proved in three steps:
Gdeser agrees with the graph that would have been observed if R had been intervened to r. This graph is, in standard way, associated to the intervened SCM. Thus, the usual Markov property holds (20) Prop. 6.31 (p. 105)), and independence in that SCM, see (iii,, reduced to d-separation in the context-specific graph. (ii) For the cases excluded by case (a), Payer U {Rt is always a valid d-separating set (D.2). (iii) The intervened model observed under the noises of the original SCM, has counterfactual distribution (Sec. D.2 and by standard results (16) cor. 7.3.2 (p. 229)), the counterfactual independence X, 11 Y, Zr, R, implies X IL Y T.
(i) Assuming
saggl--raah-suuffccinnee
7

---

Faithfulness properties The faithfulness property ensures that links that should remain in the graph. do remain in the graph and are not erroneously deleted due to ill-suited independence relations. A probability distribution P is faithful to DAG G if independence X Il p YJ 7 with respect to P implies d-separation X G Y Z with respect to G. This means that, if G' C G is (strictly) sparser, then faithfulness to G' is (strictly) weaker than faithfulness to G. Now, Reer C Gunnio so "Pa (...) is faithful to Greer" is weaker than the standard assumption (.......) is faithful to Gunion Similarly (excluding links involving R). Ge is sparser than what one would expect for graph of the conditional model (there are no edges induced by selection bias G)t=r), )) so "PM(.... IR = r) is faithful to Gdeser " is also weaker than expected. The hypothesis of the following lemma is thus R=r unconventional but not particularly strong. This lemma is proved in Sec. DD.5
Lemma 4.2. Given assume both PMr is faithful to GRes and Par(... |R =)) is faithful to Rer (we will refer to this condition as r-faithfulness. or R-faithfulness if it holds for all r). Then:
3Z {
X HL Y or X,Y + R and X TL Y1Z
} = X and Y are not adjacent in Gleee
Soundness of the algorithm The proposed algorithm recovers meaningful graph. Our algorithm is (descriptively) sound (Rmk. (Rm). but would not be complete without the sufficiency assumptions introduced in Sec. 3.3 Moreover, the strong- or iinll-graph--suffciinnyy makes our algorithm
discover the physical graph soundly.
r r-faithfulness and strong context- acyclicity with minimal union cycles of length S 2 (edge-ffiss)) ). In the oracle case (if there are no finite- sample errors during independence testing), algorithm recovers the skeleton of GR= = G
Theorem 1. Assume causal sufficiency,
The detailed proof is in Sec. D.6 Restricting cycles to edge flips is necessary to avoid the problems discussed in Sec. D.7 and Sec. D.8 Together with the contex-accyllciiy assumption, it ensures that all nodes involved in union cycles are union children of R, and thus all edges pointing at union cycles tested context-specific data, avoiding problems with acyclifications (see Rmk. 4. and (2)) The proof itself consists of three parts: (i) Testing all subsets 2 C AY)(Y) as separating sets finds all missing links by the Lemma 1 This follows from context-sufficiencc and the restricted form of cycles. (ii) The algorithm actually does test all such subsets Z S. Adj(Y). Identical to the argument for the PC algorithm. (iii) We do not remove too many edges. This follows directly from Lemma 4.2
5 Simulation study
5.1 Experimental setup
Data generation Our data models created by first randomly generating linear acyelic SCM with + cyop', where i == 1...., D + 1, at desired sparsity level s. One of the nodes randomly selected as the context indicator R. To obtain categorical context indicators for the Recutexts - 1 context-specific SCMs, thresholding is applied by quantiles of the continuous values of R, adjusted using a data imbalance factor b. To generate a context-specifi SCM, Recannge links of the base graphs are edited sequentially by selecting a variable randomly (excluding the context indicator), adding, removing, or flipping an edge to this variable and ensuring it is a child of R by adding an edge from /t to it (and in the case of edge flips, also to the node at the other end of the edge). These operations lead to a non-linear relationship between the context indicator and the other variables. We enforce the presence or absence of cycles in the union graph. The data generation approach is detailed in Sec. E.1
up to D ++1 1 nodes (base graph) of the form X ===ı; D+1 Σ a
taking the necomtetss
Evaluated methods We compare our method, named PC-AC (AC is short from "adaptive context"), to a variant where PC-stable is applied on each -ppeext-ppecific dataset separately by masking, denoted by PC-M. We expect PC-M to have a higher false positive rate (FPR) due to selection bias, and lower true positive rate (TPR), as links involving the context indicator cannot be found using the masked data. We also compare our algorithm to PC-stable applied on the pooled dataset, named PC-P, which only recovers joint information, i.e., union graphs. We expect PC-P to have a slightly higher TPR, as it tests all links on all data points. PC-P should not suffer from selection bias, thus, the FPR of PC-P should be lower than that of PC-M for acyelic union graphs For cyclic union graphs, PC-P only finds the acyclification, thus, the FPR should asymptotically remain finite. We also compare to
8

---

baseline method, named PC-B: For each context, we compute the intersection of the links found by PC-M and PC-P and then add the links found using PC-P for R. PC-B should converge asymptotically toward the true graph (see Sec. I. However, as PC-B runs more tests overall, PC-AC should have better finite-sample properties. As we do not control for cycle length, the performance of PC-AC might be affected by large eycles, as discussed in Sec. D.7 and Sec. [.8] We obtain union graphs for PC-M and PC-B using the unionization approach from Sec. 4 We also compare union graphs from two methods which test pooled data: FCI-JCIO (3 15) and CD-NOD (39). We do not compare to other methods that obtain context-specific graphs, as they assume exogenous context indicators. A fair comparison our algorithm is hard to realize due to assumptions and a lack of available methods suitable to this problem. We compare computational runtimes in App. E.4
We present results where D + 1 = 8 and density & = 0.4. For all j. Tp' ~ (0, We draw the non-zero ds.j randomly from {1.8, 1.5, 1.2, -1.2, -1.5, -1.8), and set ej context indicator R, we set en 0.2. We discuss results with and without enforced cycles. For the configurations without eycles, we apply only the remove operation (see Sec. [ec.FE.T. The dataset presented here is balanced in the number of samples for each i.e., b = 1. A challenge of our experimental setup is that non-linear relationships between continuous variables and the categorical R must be tested (see also App D.II. Non-parametric permutation-basee tests for mixed-type data with non-linear relationships exist (13 38 21, but are computationally expensive. Therefore, apply a parametric mixed -tppe data test (35) for most experiments. For fair comparison, run versions of the algorithms with so-called link assumptions, where the adjacencies of R are either partially fully known, i.c., input the (directed) links to or from R (adj. R-all), or the (directed) links from R to its children (adj. R-ch.), or test without known links (adj. none). For all tests involving only continuous variables, data, the link from a regressed-out variable might be missing in one of the contexts, but partial correlation tests should still work, as discussed Sec. D.12 We show results for "adj. Rt-ch"" " and "adj. none" and postpone results with "adj. Rt-ll" to Sec. E.3 Here, we discuss the TPR and FPR for the union and context-specific graphs (averaged across contexts) but also evaluate edgemark precision and recall in Sec. E.3 Error bars are generated using Bootstrap with 200 iterations. We repeat each experiment 100 times, however, the graph generation is not always successful. We evaluate how well our method scales, c.g., with different D, and in Sec. E.3 The code, based on causal-leam (40) and Tigramite (25), and details for replication (random seeds) can be found here:
for all j. For the
partial correlation. When testing pooled
https: thub. com/ wanaapopssccaaappiie..oom htwp://veeeeedddeouuuuuuouuuu contexts
5.2 Results
Nodes: Contestts: Cherged Uniss: Density: 0.4,
Vodes: 8, Contests:: 2. Changed Links: 1. Densily: 0.4,
Faisc.
1.00
TPR
0.10
FPR
1.00
TPR
0.10
FPR
0.00
0.00
0.50
0.09
0.55
0.00
0.50
0.000
0.70
0.07
0.70
9.5
0.30
0.00
0.10
0.0
6.01
0.02
0.00
2000
1060
0.00
-00
300
0.00
6000
-0.00
0.20
1.07
Arg. Connenn
0.30
0.07
0.60
0.06
1000
0.00
0.05
0.50
0.05
10 0.30
0.00
0.30
0.01
1950
1000
1000
1000
Sample Size
Sample Size
Sampic Size
Sample 5
PC-AC R-ch.
PCB adj Reth
PCAC adj, none
PC-B adj. none PCP adi. none
ad)
PCMM adj. nome
Figure 3: Results for our algorithm PC-AC (adaptive context, our method), PC-M (masking), PC-B (baseline), and PC-P (pooled) on the setup described in Sec. [. Dotted lines indicate settings where links from the context indicator R to its children are fixed/ known (adj. R-ch.), solid lines indicate no prior knowledge about links (adj. none). The left panel shows results using a parametric CIT, the right panel shows results for the same setting with "adj. none" using a non paramerrttriic CIT.

---

The left plot of Fig. 3 shows results for the experimental setup described in Sec. without cycles. For individual contexts, our method outperforms PC-M in terms of FPR for both link assumption cases. Without any link assumptions, the FPR for both PC-B and PC-AC increase significantly. We test whether this is due to the testing problem (Sec. D by using a non-parametric CIT (2I). Results in the right plot of Fig. 3 show that the FPR is significantly lowered for all methods. For PC-M, the union graph FPR is high compared to the context -specxiipeccfiiccccc FPR, as, for the individual context graphs, the links between context indicator and system variables cannot be found (as R is constant), Still, false positives can appear in the union graph due to selection bias. Our method performs best in terms of TPR and FPR union and context-specifie graphs with context children link assumptions and without link assumptions. PC-B performs slightly worse due to its finie--smple properties. However, with fully known context-system links (Fig. iin Sec. Sec.E.33II masking finds more links overall, having the best TPR, but also higher FPR, followed by PC-AC, PC-B, and PC-P. Results for the same setup as in Sec. 5. with enforced cycles in the union graph (Fig. 6 in Sec. E.3.2) show similar behavior of the TPR and FPR, albeit some differences are less pronounced, possibly since the complexity of the problem increases. As expected, the FPR for PC-P, which detects only the acyclification, increases. We observe that for all versions without link assumptions, the FPR increases significantly compared to the setup without cycles. Larger differences in FPR between PC-M and PC-AC can be seen for samples up to 2000. Regarding TPR, PC-AC and PC-B perform best for the context-specific graphs, especially without any link assumptions. Results for the comparison with FCI and CD-NOD for the union graphs, detailed in Sec. E.3.3] show that our method slightly outperforms CD-NOD, which assumes acyclicity. Our method outperforms FCI in terms of TPR, but FPR is lower for FCI.
6 Discussion and conclusion
In this work, we have introduced a novel method for causal discovery (CD) of context-specific graphs and their union in the presence of (possibly) endogenous context indicator. We propose a simple modification of the PC algorithm, but our method can be combined with any other constraint-bas CD algorithm. Our approach provides an elegant and efficient solution the problem of selection bias. Further, we discuss how to formally link causal models (SCMs); this end we introduce novel graphical objects and assumptions and prove the soundness of our algorithm. We discuss the theoretical and practical limitations to recovering the true graphs, c. g. in presence of large cycles (D.7). Our method has a lower FPR than applying CD on each context individually, which can suffer from selection bias: it displays better sampl- performance than a proposed baseline method. Our method is comparable with CD-NOD (39) and FCI (28) on the union graphs, but additionally provides context-specife information.
independence (CSI) relations to structural
Limitations Our method requires that the context indicator It is observed and chosen appropriately, as discussed in Sec. 3.2 it can handle some union cycles, but not reliably so for large union cycles, see Sec. [.8] Without prior knowledge about adjacencies of R. our method has difficulties to significantly outperform pooled methods and to keep up with the bascline in numerical tests; this is likely due to the CIT problem discussed in Sec. [.2) an interpretation supported by smaller experiment with a -arammarettric CIT (Fig. 3 right panel). We thus believe that the problem can be solved using appropriate CITs. Finite sample errors incur further propagated errors similar to standard CD; errors involving links to R additionally lead to a regression to standard CD concerning context-specific information (see App AppD.13) D.13). In this work, we have assumed causal sufficiency, however, real-world data often contains hidden confounders.
Future work We have mainly focused on skeleton discovery and omitted detailed study of orientation rules. Algorithms such as FCI and CD-NOD already perform well for edge orientations of the union graph, as small experiments in Sec. E.3.3 indicate. But there also seem to be additional edge orientations available only by combining per-context information (see Sec. F. for an example), a possibility also mentioned in (9); these orientations can be beyond what can be concluded even with JCI arguments. In practice, contexts are often assigned by thresholding, so an extension to contexts given as deterministic functions of observed variables (see Sec. F.2 is of interest. Similar remarks apply to mooally-detecton outputs, defining normal and anomalous contexts. The assumption of causal sufficiency simplifies the arguments, but does not seem strictly necessary; likely can be relaxed in future work. Finally, our method is in principle extendable to the time-series case. Particularly when allowing for contemporaneous relations of the context indicator, selection bias is a non-trivial problem for time-series.
10

---

Acknowledgments and Disclosure of Funding
We thank Rebecca Jean Herman for the fruitful discussions, and Tom Hochsprung for his helpful comments on the draft. J.R. and U.N. have received funding from the European Research Council (ERC) Starting Grant CausalEarth under the European Union's Horizon 2020 research and innovation program (Grant Agreement No. 948112). J.R., O.I.P, and M.R. have received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 101003469 (XAIDA). O.I.P has received funding from the German Aerospace Center (DLR). W.G. was supported by the Helmholtz AI project CausalFlood (grant no. ZT-I-PF-5-11) This work was supported by the German Federal Ministry of Education and Research (BMBF, SCADS22B) and the Saxon State Ministry for Science, Culture and Tourism (SMWK) by funding the competence center for Big Data and AI AS Dresden//Liizigg..
References
[1] C. K. Assaad, I. Ez-zejjari, and I.. Zan. Root cause identification for collective anomalies in time series given an acyclic summary causal graph with loops. ArXiv, abs/2303.04038, 2023,
[2] S. Bongers, P. Forré, J. Peters, and J. M. Mooij. Foundations of structural causal models with cycles and latent variables. The Annals of Statistics, 49(5):2885-2915, 2021.
[3] Forré and J. M. Mooij. Causal calculus in the presence of cycles, latent confounders and selection bias. In Uncertainty in Artificial Intelligence, pages 71-80. PMLR, 2020.
[4] C. Glymour, K. Zhang, and P. Spirtes. Review of causal discovery methods based on graphical models. Frontiers genetics, 10:524, 2019.
[5] W. Gunther, U. Ninad, and J. Runge. Causal discovery for time series from multiple datasets with latent contexts. In Conference on Uncertainty in Artificial Intelligence, 2023.
[6] C. Heinze-Deml, J. Peters, and N. Meinshausen. Invariant causal prediction for nonlinear models. Journal of Causal Inference, 6, 2017.
[7] B. Huang, K. Zhang. J. Zhang, J. Ramsey, R. Sanchez-Romero, C. Glymour, and B. Schölkopf. Causal discovery from heterngeneeous/nonnaationnay data. The Journal of Machine Learning Research, 21(1):3482-335 3534, 2020.
[8] A. Hyttinen, F. Eberhardt, and P. O. Hoyer. Learning linear eyclic causal models with latent variables. J. Mach. Learn. Res., 13:3387-3439, 2012.
[9] A. Hyttinen, J. Pensar, J. Kontinen, and J. Corander. Structure learning for bayesian networks over labeled dags. In International Conference on Probabilistic Graphical Models, pages 133-144. PMLR, 2018.
[10] A. Jaber and M. Kocaoglu. Causal discovery from soft interventions with unknown targets: Characterization and learning. In Neural Information Processing Systems, 2020.
[11] S. Karmouche, E. Galytska, G. A. Meehl, J. Runge, K. Weigel, and V. Eyring. Changing effects of external forcing atlantic-pacific interactions. Earth System Dynamics, 15:689- 715, 2024.
[12] A. Markham, Das, and M. Grosse Meesse-ennrrup.. A distance bovariance-based kernel for nonlinear causal clustering in heterogeneous populations. ArXiv, abs/2106.033480, 2021.
[13] O. C. Mesner and C. R. Shalizi. Conditional mutual information estimation for mixed, discrete and continuous data. IEEE Transactions on Information Theory, 67:464 484, 2020.
[14] J. M. Mooij, S. Magliacane, and T. Claassen. Joint causal inference from multiple contexts. J. Mach. Learn. Res., 11::991-999100 2016.
[15] J. M. Mooij, S. Magliacane, and T. Claassen. Joint causal inference from multiple contexts, The Journal of Machine Learning Research, 21(1):3919 4026, 2020.
[16] J. Pearl. Causality. Cambridge university press, 2009.

---

[17] J. Pearl and E. Bareinboim. External validity: From do-calculus to transportability across populations. Statistical Science, 29(4):579-5935 2014.
[18] Pensar, H. Nyman, Koski, and Corander. Labeled directed acyclic graphs: a generalization of context-specific independence in directed graphical models. Data mining and knowledge discovery, 29:503-533, 2015.
[19] J. Peters, P. Buhlmann, and N. Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 78, 2015.
[20] J. Peters, D. Janzing, and B. Schölkopf. Elements of Causal Inference: Foundations and Learning Algorithms. MIT Press, 2017.
[21] O.-I. Popescu, A. Gerhardus, and J. Runge. Non- con-paametric conditional independence testing for mixed continuous-categoriiaa variables: novel method and numerical evaluation. ArXiv, abs/2310.1 12111111 1132, 2023.
[22] M. Rabel, W. Günther, J. Runge, and A. Gerhardus. Causal modeling in multi-context systems: Distinguishing multiple context-specific causal graphs which account for observational support. arXiv preprini arXiv:2410.20403 2024. Extends on the theoretical results presented here.
[23] A. Rahmani and P. Frossard. Castor: Causal temporal regime structure learning. ArXiv, 1112231.001122 2023.
[24] D. Rothenhäusler, C. Heinze, J. Peters, and N. Meinshausen. Backshift: Learning causal cyclic graphs from unknown shift interventions. In Neural Information Processing Systems, 2015.
[25] Runge.
Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasets. In Conference on Uncertainty in Artificial Intelligence, pages 1388-1397.
PMLR, 2020.
[26] Runge, Bathiany, E. Bollt, G. Camps- D. Coumou, E. Deyle, C. Glymour, M. Kretschmer, M. D. Mahecha, J. Muñoz-Marí, et al. Inferring causation from time series in earth system sciences. Nature communications, 10(1): 2019.
[27] Runge, A. Gerhardus, G. Varando, V. Eyring, and G. Camps-Vallh Causal inference for time series. Nature Reviews Earth & Environment, 4(7))487-505, 2023.
[28] B. Saced, S. Panigrahi, and C. Uhler. Causal structure discovery from distributions arising from mixtures of dags. In International Conference on Machine Learning. 2020.
[29] E. Saggioro, J. de Wiljes, M. Kretschmer, and J. Runge. Reconstructing causal relationships from observational time series. Chaos: An Interdisciplinary Journal of Nonlinear Science, 30(11), 1), 2020.
[30] R. D. Shah and J. Peters. The hardness of conditional independence testing and the generalised covariance measure. The Annals of Statistics, 48(3):1514-1535 2020.
[31] Spirtes and C. Glymour. An algorithm for fast recovery of sparse causal graphs. Social Science Computer Review, 9:62 - 72, 1991.
[32] P. Spirtes, C. N. Glymour, and R. Scheines. Causation, prediction, and search. MIT press, 2000.
[33] E. V. Strobl. Causal discovery with mixture of dags. Machine Learning, pages 1-25, 2022.
[34] Tikka, A. Hyttinen, and J. Karvanen. Identifying causal effects via context speeiii- indepen- dence relations. Advances in neural information processing systems, 32, 2019.
[35] M. Tsagris, G. Borboudakis, V. Lagani, and I. Tsamardinos. Constraint- based causal discovery with mixed data. International Journal of Data Science and Analytics, 6:19 30, 2018.
[36] S. Varambally, Y.-A. Ma, and R. Yu. Discovering mixtures of structural causal models from time series data. arXiv preprint arXh::2310.06311, 2023.
12

---

[37] T. Verma and J. Pearl. Equivalence and synthesis of causal models. In Proceedings of the 6th Conference on Uncertainty in Artificial Intelligence, pages 220-227. Elsevier Science, 1991.
[38] I.. Zan, A. Meynaoui, C. K. Assaad, Devijver, and É. Gaussier. A conditional mutual information estimator for mixed data and an associated conditional independence test. Entropy, 24, 2022.
[39] K. Zhang, B. Huang. J. Zhang, C. Glymour, and B. Scholkopf. Causal discovery from non- stationaryhhetrrggnnouu data: Skeleton estimation and orientation determination. IJCAI: proceedings of the conference, 2017:1347-1353, 2017.
[40] Y. Zheng, B. Huang, W. Chen, J. Ramsey, M. Gong, R. Cai, S. Shimizu, P. Spirtes, and K. Zhang. Causal-learn: Causal discovery python. ArXiv, abs/2307. 16405, 2023.
[41] Zhou, K. He, and Y. Ni. Causal discovery with heterogeneous observational data. In Conference on Uncertainly in Artificial Intelligence, 2022.
A Delimitation from LDAGs
LDAGS (18) 9) are conceptually closest to our work. We thus delimit our work from LDAGGs as
follows: First, we derive connection from context-specific graphs to SCMs; also for identification from data, only CSIs are insufficient in our case, a combination of CSIs and independence-statemeen on the pooled data is required. Second, LDAGs have been studied only under the assumption of acyclicity, while we allow for cycles in the union graph. Third, the method of Hyttinen et al. (9) only accepts categorical variables, while we enable continuous and discrete variables. Fourth, our method reduces the number of tests compared to Hyttinen et al. (9), as we do not test each CI relation conditioned on the context. Instead, we adaptively select whether to test on the context-specifh or the pooled data. Finally, we distinguish system variables from the context indicator, whereas in I.DGGs every variable treated as potential context indicator, From a theoretical perspective, this advantageous, as it increases information content. However, from practical perspective, the LDAG approach increases the number required tests.
B Context variables and F-variables
As described near the end of S.c in our case, the context variable is chosen from the set of variables. This choice is primarily guided the regime-sufficiency assumptions. This allows for lot of flexibility: The context variable can be selected from or introduced into the dataset by expert knowledge any regime detection algorithm: it simply has behave like random variables from the perspective of the CD-algorithm.
Such flexibility may remind the reader of what Pearl (16) calls F-variables (see below) and while the relation is very indirect, there is indeed an interesting perspective via F-variables. F-variables are functional variables (taking values in function spaces) that allow writing any (hard soft) interven- tions implicitly: If fy (x) is the mechanism at æ, depending on parents x (possibly multivariate). one add parent Fy taking function (e. g. the original fy) value, and replace the mechanism at Y by the evaluation map eval(f, [f][[fx]] x) == (x)) Since Fy can take a value for I that represents an intervention (e. g. constant function for hard intervention) this generalizes interventions. Example 3.1 can indeed be regarded as a kind of soft intervention on Y.
Context variables as such are orthogonal concept: Given multiple distinct datasets over the same set of variables, the context injects the information about the specific associations in each dataset to the analysis by appending
aeeudo-variable to the dataset. The value of this pseudo-variable typically simply dataset index. This context could be functional but in general both contexts and functional nodes co-exist independently of each other.
Now, we are interested context-specific changes similar to Example 3.1 which (see above) can be represented as soft interventions, thus as F-variables. This means, we can formally describe these as context-variables which are F-variables. This allows a different interpretation of the strong regime-sufficiens assumption (cf. App Ch: It demands, that the context variable belongs specific
13

---

class of functional nodes, which implement a soft intervention removing some of the parents' effects on certain variables.
In comparison to JCI (15), our method reveals not only the position of this context F-variable in the graph; it also reveals some of the internal structure of some functional nodes (those satisfying the reformulated strong sufficiency assumption); It additionally uncovers the graphical changes induced by the implemented soft intervention.
Finally, temporal regimes were an important motivation for our study of context-specific behavior. To make the connection to non-stationary time series, these can be formulated using context variables. For the context to be categorical (which we and others assume), the -on-staiionarity cannot be a drift etc. but must be driven by regime change, i.c., there must be temporal regions sharing model or context. By finding the contexts in which the time series is stationary and describing the causal relationships for those stationary parts of the time series, we describe the non-stationarity system as a multi-context system.
C Details on sufficiency conditions
Here, we provide details on the three context-sufficiency assumptions discussed in Sec. 3.3 in the main text. Then, we show that these are indeed hierarchical: Strong context-sufficinncy = single- graph-sufficieccy = weak context-suffiieeccy Finally, we give examples of when the other direction violated.
First, we quickly summarize the problem to solve and the ideas behind the different conditions: If the observational support given R r of, say, X, is restricted a region where a mechanism fy (X....) is constant in X, then this can make the link from X to Y disappear in independence testing. Excluding CSIs arising like this requires a way of saying what "constant a region" means.
The single-graph ggraph-suffiiiene assumption will capture this requirement on a graphical level. This is powerful for proofs, but does not provide much in terms of explanation and might be hard to verify given a specific model. Example(3.] (ssswws shows that there clearly a rather large and intuitive class of models which look like fy (X, .....) 1 (R)g(X,..)) + h(...). Clearly, one still has ensure that g or f are "constant in a region", so that only the indicator function can remove links. The strong sufficiency condition will capture this intuitive notion, however, we note that this is only one possible formalization (see Rmk. C.T..
As indicated above, the strong sufficiency condition requires formal way of saying a map is not constant on any region. One possible way to do so is to require it to be injective (in every argument, after fixing other arguments):
Definition C.1. We call an indicator R strongly context-sufficient for an SCM M, both
(a) the f. are continuous, such that:
(i) If R & Pa(X,) in the mechanism graph, then fi injective each argument, after fixing the other arguments to an arbitrary value.
iii If R E Pa(X,) in the mechanism graph, then fi is of the form R.
1(R E A) 9x, R,,)) 1 A) gi R. ni), with A C X' and 9t. of injective in each argument, after fixing the other arguments to an arbitrary value. This could also be generalized to a sum over multiple indicator functions without changing the results.
(b) for every set of variables V not containing R, the distributions P(V), P(V(R r) and P(V) = r)) have continuous densities.
Remark C.1. The notion of "non-constan on any region" could be formalized differently, for example through smooth mechanisms and a requirement on gradients. Further, this is not supposed to be particularly general, but rather to be intuitive. More general conditions to ensure that detected changes physical is linllegraph-sufficienn context-sufficiencc (see below).
that results (deseriptively) complete is weak
Example C.1. A model with continuous densities of noise-distributions, and mechanisms depending on R only through indicator functions and such that for each value r the model Mao(R=r) linear, is strongly regime sufficient. This includes Example 3.1
14

---

Definition C.2. We call a context indicator R single-graph--sufiiient for an SCM M, if
Creeser R=
G-hyys Rmr
GCF
R=
with the graphs Glese Gokys G Remark C.2. Under this condition, descriptive results can be interpreted physical mechanism changes.
defined as in Sec. D.1
Rep
The efficiency of the algorithm proposed in Sec. comes from the restriction that context-specifer changes must occur in children of the context R. This requires a weaker condition which we formally deseribe as weak segime-sufficiency. In this case, the difficult and interesting question to ask is: How should the output of the algorithm be interpreted under this assumption? This discussed in Rmk. Rmk.[D.] which can be interpreted as robustness result: Even when violating the context-sufficie conditions, the output of the algorithm is descriptively correct, and, given weak context-suffiieency. still complete.
Definition C.3. We call context indicator R weakly context-sufficient for SCM M, if
R & Pa "aauiion()) (Y)
deser (Y) = Pa union (Y).
Remark C.3. Under this condition, changes may be descriptive only, but the results are complete (all edge removals are found), see Rmk. D.2
C.1 Hierarchy of assumptions
Here, we show that above-mentionel assumptions indeed hierarchical: Strong context-sufficeency + toogll--rapb-suffcienee + weak context-sufficiency We will start from Def. C.I The underlying idea for requiring (a) is rather direct:
Lemma C.1. If X Pa(Y) in G[F), and fY F is injective in X after fixing all other arguments, then given C Kra(Y) with x & x' E Xx and pa E &Xra(y)-(X) (X} such that (z, pa ), (a', pa E
S, then fy Is is non-constant in X.
Proof. Jy is injective in X after fixing its other arguments to pa-, thus frls is injective in X after fixing its other arguments to pa", so (I. pa-) # (x', pa-) implies fy pa # fr pa ).
Thus, as long as the support S is never singular, i.e., as long as x + x' as above exists, restricting to S does not change the parent sets. The continuous densities required in (b) are an intuitive possibility to ensure this:
Lemma C.2. X Pa(Y) in GJF and distribution Q is given with Q(X) and Q(Pa(Y)) possessing continuous densities, then ix # x' E Xx and pa- E XPa(Y)) such that (x, (e,pa"); (a', pa E (PPp(P((a(Y)IR==))
Proof. If Q(X) has a continuous density gz, is not a point measure, thus there are x + x' with gz (z) # 0 and qu (z') * O. With X E Pa(Y)) and Q(Pa(Y)) possessing a continu- ous density 9pa. we know dz SPa(Y)-(X) 9pa - pa is the marginalization, so # (x)) = (Pa())((X) Oa (pa_ _ r), which implies 3pa with upa(pa ,a) of 0. By continuity thus (zc, )) (x', pa supp(P(Pa(Y))RE r)).
Requiring strong confext-sufficiency ensures that the only non-injectivities come from R, such that after fixing R in Fao(R=r) and ignoring edges involving R (i. e., using the harred G versions):
Lemma C.3. M = (F, U, V) is strongly context-suficient and R = r fixed, then the following are equivalent for X # R Y:
(i) X E PY in G[Fao(R=)))
(ii) X E Pa(Y) in Glese [M]
[M]
(ii) X E Pa(Y) in Gryys R
[M]
15

---

(iv) X E PY(Y) in GCP G
Corollary C.1. If M is strongly context- context-suficiiet,, then it is single Seiei-graphhhfcccee
Proof of the Corollary. By the lemma, GR = G = GCP The unbarred versions insert the R=
R=rr
same links involving R from the union graph, thus also R= R=r G Recall that this is the definition of single-graph graph-sufficcency:
Proof of the Lemma. First note that (ii) (i), (iii) (i) and (iv) (i) are trivial (if restriction of fi is non-constant in X, then fi is non-constant X).
Further, Ji which do not depend on R are already injective, and fi which depend on R are of the form fa(X, X', R, m/) = 1(R E A) x gi(X, X', R. m)) + 1( & A) x g/(X, R, 1)), such that the Gc. D/ are injective. Thus, depending on the value of R we fixed, either fi 9: or St = of is in Fdo( both of which are injective. So all ft Fdo(R=)) are injective.
"(i) = (ii": Apply lemma C.2 to Q P(V r) (as distribution over V), get Ex + I' Xx and pa E ((x) with (z, pa p) (a', pa pa_ E S = supp (PPpp(((P(Y))E r)). Thus lemma C.I applies yield fy Is is non-constant in X, thus by definition of G [M]. also X E Pater (Y).
"(i) > (iii)": As (i) (ii) above, but use Q P(V) in lemma C.2
"(i) > (iv)": As (1) > (ii) above, but use Q = P(V] do ( = r)) in lemma
Next, recall that had defined R to be (weakly) context-sufficient: Y is not child of R. then X Padear (Y) X & Paanioo(YY) (Y)) The reason why this is implied by Lingl--gaph-sufiie
(Guesr G GCF R= that physical changes are caused by R. and thus only happen in children
of R:
Lemma C.4. Y # R with R & Pa union (Y), then
PaRe (Y) = Pa union (Y).
Proof. By definition, Gunion [M]] G[F, Pas] and Cohyss [M] G[Fao(R=r)) Pwr.. By definition, F and Fao(R=r) differ only in fn and (by setting R = r) for fr with R E Pa uniuion Pa (X;). For Y, by hypothesis, neither of these two applies, the same fy is in F and Rao( Since both graph definitions further use the same support (that of Pat), their parent definitions for agree: Papes (Y) = Pa union (Y).
Corollary C.2. If is single-graph-suffciinng (for R), then M is weakly context-sufficiet.
Proof. This is reformulation of the statement of the lemma, i.c. it holds by definition of these terms.
C.2 Strictness: Examples violating the "hackwards-directionn"
Part (a) of strong context-sufficiency: fy is not injective.
The injectivity assumption is g. violated in Example 3.2
Part (b) of strong context-sufliciency: The assumption about distributions seems, especially in light of Lemma C.2 (which is the only implication of this assumption that needed), relatively weak. However, there are some intuitive examples where we observe that it can be easily violated, and why this is problem:
Example C.2. Assume a root variable X has noise term, i.e., mechanism kernel (fx) 1 with randomness arising (within measurement precision) from a process involving sunlight, e. g., X might be the photosynthesis rate the solar power provided. Further, assume that R indicates whether it is day or night. Then [ = r) is, for some values R during the night, singular at a specific value, violating part (b) of the strong sufficiency assumption.
On the pooled data, this may not pose an issue. However, on the night-time values of R, nothing will depend on X. This is descriptively correct, but it holds for all children Y of X, irrespective of
16

---

whether Y are also children of R. Therefore, R is not even weakly context-sufficient. Our algorithm, which relies on weak context-suffciency. may not remove these links.
This kind of problem may be less severe than a violation of part (a) of strong context-suffiiiency because it may be testable beforehand.
Singll-graph-suffiiinnt, but not strongly context-sufficient: Part (b), as stated cf. Lemma however, be violated simply by constructing densities with "jumps." which does not interfere with any of the other conditions. More interesting seem violations part (a). However, this can also easily be done because the Sa need not be injective, only "sufficiently injective" be non-constant on the supports. For example, Y X² + V/ is non-injective but is unlikely to be constant (indeed, this would only happen for P(X) having singular support exactly at points Tig and -Zg. thus violating part (b)).
Weakly context-sufficient, but not single-graphssuffiient::
Say we take Example 3.2 and add quantitative dependence of Y on R. e. g., add a term Y = x R with 7 & to the definition of Y. Now, Rt is cause of Y, turning Y into child of the context indicator, making the model weakly context-sufficient. However, fy still depends I' in the support of PM. such that T Phys (Y) (as before), while (also as before) T & PaR=r (Y).
In the intuitive sense, weak context-sufficiens means that descriptive changes only occur at mech- anisms that involve R, but R may, as in the example above, not directly cause the change of the mechanism.
C.3 Additional assumptions
Definition C.4 (Causal Sufficiency). A set of variables V is causally sufficient relative to SCM if, within the model, every common cause of any pair of variables in V is included in V, i.e., there no hidden common causes confounders outside V that affect any pair of variables in V.
Definition C.5 (Weak (Descriptive) Acceliit-cyyllccitt).. For each context value of R. the context- specific graph Gueser R=r is weakly (descriptive) confext-acyclie if Greer a DAG, i.e. there are no directed cycles any Gueser
Definition C.6 (Strong (Descriptive) Context-Acyclcitty. For each context value r of R, the context- specific graph Glesse is strongly (descriptive) context-acyclic Gdeser is DAG, i.e., there are no Rtrr
directed cycles any Gideser and, additionally, no cycles involving any ancestors of R, including R itself, are Gunnion
D Theoretical properties of the proposed algorithm
Here, we give proofs and additional information concerning the theoretical properties of the algorithm proposed in Sec.
D.1 Additional graphs
As a systematic overview over the graphical objects introduced in Sec. 3.1 these objects are summa- rized and compared in Table
The proof of the Markov property Sec. D33 will require an additional graphical object, the counterfactual graph. As it is only needed as formal objects, it is introduced here rather than in the main text. Furthermore, the proof of the Markov property should be comprehensible without detailed knowledge of these graphical objects beyond the understanding that there is, in general, more than We advise the reader to first read Sec. D.3 and refer here for
one (cf. points (a) and (b) in Sec. 3.2 formal details if required.
The counterfactual graph, defined follows:
G
G [M] == G[F (M do = r)) = Grunion Mao(
The counterfactual graph describes relations that we would have observed had been set to under the same noises. Refer to Sec. Do2 more detailed discussion.
17

---

Table 1: Comparison of different observable graphs GIM, Pl, highlighting their key features and contexts in relation to system and model.
Observable Graphs G[F, PI
Symbol
GR
G
Gunion
Name
Descriptive F or F PM(... |R
Physical
Union (Standard)
Mechanisms 7
F
Observational Support P
r)
Par...))
(M(...)
Captured Information
Directly Observed Altered Mechanisms
Union Model
Context-Specific (I-ddependent)
Yes
Yes
No
Edge Sets
Active in Context r C Present in Context r C In Any Context
Remark D.1. This should not be confused with what is sometimes called the "intervened" or
"amputated" graph Gao(no) [M]; this is obtained from Guniin [MM] by removing edges pointing into R.
Generally (o) [M] * G[F (=r)); (v do(R = r))], even for edges not involving R. This because the support of (V) do R = =)) may be different (potentially even larger) than for Pas.
D.2 Connection to counterfactuals
The definition of the intervened model in Sec. the SCM Mao(A=a) == (V',U, Fao(A=o)) with U distributed according to P, of M. At a per-sample level, i.e., drawing value 7ī from P., and running it through both M and Mao(R=r)) to obtain (77 and (7) yields exactly the definition of potential responses given (16) Def. 7.1.4 4 (p. 204)). Often, the joint distribution P(X,, (X+)r) (induced from P, by the procedure described above) is of interest. This would mean counterfactually observing both M and Rer) the same time. Here we only need X; or (X,), variables separately, so the "distribution-level" observables (defining M and Mao(R=r)) on the same P.p. but not on the same realizations r) suffice.
From the definition of (7) and (7) the consistency property defined in (16, cor. 7.3.2 (p. 229)) is relatively easy to see: If, for a partieular 77, one obtains R(()) r from M, then solving the equations of (ao( yields the same result (they only replace the equation for R(T)) by R which for this oj makes no difference). So P((X:)r) Ry = r) = P(
D.3 Proof of the Markov property
Lemma D.1. Given an SCM M and its visible graph G Guniion (M), conditional o-separation (d-separation if G is a DAG) with respect to G implies conditional independence in Pas-
Proof. The visible graph Gunion [M]] is the causal graph in the standard sense, i. G[F with
suitably minimal set of mechanisms (see Sec. Sec.3.I). So the standard results (20) Prop. 6.31 (p. 105))
(for cyclic graphs see g. (2) and Sec. D.4) apply to relate o-separation (d-separation if G is DAG) to independence.
Assuming strong context-acyclieity, causal sufficiency and singlegraph--suficeee If X and Y, both X, Y + R, with Y & And (X) are not adjacent in Crdsser RE then there Z S Aditer (Y) such that: Y is neither part of directed cycle in the union graph (union cycle) nor child of the union graph (union child), then (a) X IL YIZ, otherwise (b) X 11 Y 2, R = r.
Lemma 4.1,
deser
Proof of lemma 4.1
We distinguish the cases corresponding to (a) and (b):
Case (a) [() Y is not part of a directed union cycle and (ii) R is not parent of YJ:
Single-rrap--suffiienns implies context regime-sufficiency (cor. C.2 Y & Anc (by hypoth- esis) and (i) Y is not part of a directed union cycle imply Y & Pa union (X). Thus, if there is a link between X and Y in the union graph, then it is oriented as X Y. By weak context-sufficiency, and (ii) R is not parent of Y this is excluded. So X and Y are also not adjacent in the union graph.
Since (i) Y is not part of a directed eycle in Gunion standard path-blocking argument (lemma (Y) in Gunion o-separates X and Y. With Gunion
Sec. D.2 works to show Z Pa un))
18

---

Gunion [M] being causal graph in the standard sense (lemma D.1 d separattion in G implies X T1 ZIZ.
Case (b): W. g., (+) Y & Ane Ann of R. neither (i) could Y be part of a directed cycle by strong context-acyclicity nor (ii) could R be parent, thus ancestor, of Y, also by strong context-acyclicity.
(R), otherwise we are in case I, because if Y were ancestor
Define Z' = Pa deser
U (R). Using standard path-blocking argument, this time in G Rer works:
R=r
Lemma D.2 is applicable with Z', showing it d-separates X from Y. because Z' n Desc (Y) 01 as R is not a union-descendant Y by (+), and GCF R==r = Gdeser is a DAG (by weak context-acyclicitty) so parents of Y are also not descendants.
Other than Gueser, the counterfactual graph G = Gunion [ [ is a causal graph in the standard sense (lemma D.I of the SCM Mdo(R=r). Thus d-separation on the DAG GCF independence X, IL T, writing V, for a variable that would have been observed REr implies under the same exogenous noises as in M. This notation is justified because their distributions are potential responses in the sense of (16) Def. 7.1.4 (p. 204)) (see Sec. D.2).
By definition R E Z' so we can rewrite this as Z' U ( with R É Z. Now this reads X, Zr, R,- Generally, P = r') is not identifiable, however, if r r simply P(X =r) by the consistency property of potential responses (16 cor. 7.3.2 (p. 229)) (intuitively, under conditions which lead to = r anyway, we had intervened to set = r, that would not have resulted in any changes in the values of the other variables, and therefore, the conditional independencies). Thus
X, 11 Yr Rr
-xr Yr R
= =r + X R=
D.4
Path blocking
We use the definitions of a-separation 22 A.16) and the induced Markov property (note that in the reference Markov property refers to --separation implying independence, while our definition refers to non-adjacency implying independence CSI) (2) A.21). The following path-blocking argument is rather standard (see e. g. (37), however, we formulate the hypothesis slightly different for ease of application.
Lemma D.2. Given a directed graph G and the non-adjacent (in G) nodes X, Y with Y & Anca and Y not part of directed cycle, then any Z with (Y) ) C Z and Z ZnDesca = @ d-separates and oeppaartes X from Y in G.
Proof. Let r be arbitrary path from X to Y in G. If the last node W,, along y before reaching Y itself is in Z, then y is blocked, because the last edge is then the edge Wn, - Y from a parent W,, to Y pointing Y, such that W,, is a collider along 7. Thus 7 blocked in the d-separation sense, but W,, also points at Y along with Y in a different strongly connected component as W,, (because Y is not part of directed cycle, its strongly connected component sc(Y) (Y)), so it is also blocked in the o-separation sense.
Otherwise (if the last node W,, Z), Wn must be child of Y, and ends as 7 [X W., + Y]. Since & Anoo (X), the edges along y cannot all point towards X. Let We be the node to the right of the last (closest Y) arrow pointing the right [X_ Wi < Y). then Wa is collider along 7-
But the part of y between W; and Y is a directed path from Y to We (because Wt was chosen after the last arrow pointing to the right), so Wi E Desca (Y') and so are all descendants of Wt. Desca(Wa, C Des, Thus, Desco(Wa, n Z 0 and 7 is blocked both in the d-separation and a-separation sense.
D.5 Proof of the Faithfulness statement
The hypothesis of the following lemma is motivated in the main text in Sec. 4.2
19

---

Lemma
4.2
Given assume both PM is faithful to R=r and Pur.... |R = r) is faithful to GR
R=r"
Then:
X Y or X,Y R and X 1T Y 2-
32 s.t.
X and Y are not adjacent in GRe
We will refer to this condition r-faithfulness, R-faithfulnes if holds for all
Proof. The statement is symmetric under exchange of X and Y, so it is enough to show X $ Pa (Y). We do so by contradiction: Assume X E Pa block the direct path X Y, so they are never d-separated X K Gi ZIZ. By (the contra-position
deser (Y) and let Z be arbitrary. Z can never
of) the faithfulness assumptions, X V. pYIZ and X,Y * also X A pY R = r (the second statement is by definition the same X J. P(...1R=r)) 2)2).
D.6 Proof of Soundness of the algorithm
Thm. I Assume causal sufficiency, single-gruph-sufliiiency r-faithfulness and strong conlext-
acyclicity with minimal union cycles of length < 2 (edge-flips) In the oracle case (if there are no umite-sample errors during independence testing), the algorithm recovers Gdeser = G
Proof. (i) We show: If X and Y are not adjacent in G Ree'' o.l.o.g. by weak context-acycliety. deser (X), then an algorithm deletes the edge between X and Y if it tests all subsets Y & An
Z S Adjker (Y), on context-specific data if R E Z, the pooled data otherwise.
Since each GR acyclic, at least one of the edges in cycle must vanish for each context. Because each edge must appear in at least context appear in Gunion for cycle of length 2, each directed edge in the cycle must vanish in some context. Thus, already by weak context-sufficiency (implied by the hypothesis, Cor. C.2). all ei.e. both) nodes in the cycle are (union- Jehildren of R. Thus, under the restriction to "small" cycles in the hypothesis, part (a) of the Markov property (Lemma 4.1) applies if R is not parent Y..
(union-Jchildren
part (a) applies for a Z with E Z, then writing Z' : Z (R) by X P Y R Yr X IL Y R
and the tests we do suffice to delete the link. If part (a) does not apply, then (see above) is a parent of Y. Further, at least one of (a) or (b) applies, so (b) applies. With R a parent of (thus adjacent to) Y, we test (b).
(ii) We show: The proposed algorithm runs at least all tests required for (i).
The PC-algorithm (and its derivatives like PC-stable or conservative PC) tests for link X - Y in an efficient way, i.c., at least all conditional independencies IL Y|Z with Z S Pax or 2 C Pay and deletes an edge (starting from the fully connected graph) if this independence cannot be rejected. By the same argument, our proposed algorithm tests at least all the conditioning sets required for (i).
(iii) We show: X and Y are adjacent in Gheer, then the edge between X and remains in the graph.
By faithfulness (Lemma 4.2). whenever we find a such an independence, the edge not in G i. e. irrespective of which (context-specific) independence tests we actually perform, we never delete an edge that is in deser R=rr.
Remark D.2. Using the argument of (22 Sec. 4) one can supplement the result of Thm. I showing
robustness against assumption-violations Replacing the assumption of single-graph-suufiiennt by "weakly context-sufficient". the algorithm still recovers all descriptive information Gressr
Irrespective of any context-sufficinncy assumptions, the algorithm recovers graph deteett with Cresser C Cdotect C G e. all edge removals are descriptively correct, and at least all physically ft=r changing links are removed.
Proof. The arguments in (i) for showing that we only have to test context-specific data if R is adjacent still apply (they only use weak context-sufficiency). Further, by weak context-acyclicity together with strong context-acyclicity links that are in the Crunion but not in fizr never between
20

---

two ancestors of R in the union graph (union-ancestors). So by the Markov property (22 Prop. 4.3), also the remainder (i) still works. Part (ii) still in the standard PC-case. Part (ii)) still works. because our faithfulness result (Lemma 4.2 is already sufficiently general.
D.7 Large cycles
In this section, we discuss how large cycles, which involve more than two edges, e. not arising directly from an edge flip, can lead to problems, as exemplified below. However, this problem may not occur directly as discussed in Sec. D.S.
Context R 0: A valid separating set for X and is {Wa} (the only parent of Y), so JL s,W; R = 0. But R not adjacent to Y (in the union-graph, see below), this would not be tested by our algorithm (however, see Sec. D.8 for a discussion): Candidates for separating sets are the subsets of adjacencies, and context-specifi tests only considered if R is in the candidate set.
X
W3
Wi
W4
Wo
Z'
Ws
W7
Y
Context R = 1: A valid separating set for X and Y is {W1} (the only parent of X), so X IIL Y|W, R 1. But R adjacent (see Sec. D.8 however) to X, so this would be tested by our algorithm.
x
W3
W1
W4
Wo
Z'
W3
W
Y
Ground-truth labeled union graph exclude d-separation.
Note: a-separation implies d-separation, So enough to
21

---

Evidently the empty set is not separating set X 1 Y. The parents of either X or Y would only work in one context, in the other they become dependent, so X ff Y and X Yt Y|W, on the pooled data. For this simple example (without Z, )'), it seems like conditioning on all adjacencies could work. However, this would lead other problems. For example, with the additional variable Z
conditioning on Xdj(X)= = ( W3) would open the path [X - W Z - W4 + W3 - Y] in context R
(Similar for Y and Z
X
W3
W1
W4
R
Wo
Z'
W3
W
D.8 Union cycles involving context children
There is another problem with larger union cycles: Links from R to a union cycle cannot be tested using context-specific data (because links involving R cannot be tested for R as R is in that case a constant), but tests performed on the pooled data will only delete edges not in the acyclification of the union graph. Thus, if there is child of R in union cycle which is always the given weak context-acyclicity and weak context-sufficiee cannot be deleted. Thus, R will always point (be adjacent to. for skeleton discovery) all nodes in union cycle, irrespective of whether or not they are children of R in the ground truth.
then the edges from R to all nodes in the cycle
While this is a problem in itself. it seemingly removes the problem of Sec. D.7 inclined to claim soundness for larger cycles. While this is not entirely wrong, we strongly advise against it, for the following reasons:
might be
Adding correct constraints (c. g. from expert knowledge) about missing edges from R to system nodes could break the output.
(ii) In practise (on final data) crror-propagaiie
behavior is poor.
(iii) Large cycles can treated consistently (if they are likely to occur) with the intersection graph method described in Sec. D.10 at the cost of requiring more tests and therefore generally worse sample performance.
It might be possible that (iii) can be used "sparingly": One may observe that the above problem should leave a suspicious trace in discovered graphs: There should be many edges from R to the region of the graph containing the cycle, and all nodes in this region not adjacent to R should be heavily interconnected (because they are not tested on context-specific data, so only the acyclification found). Thus encountering such structure may be indication test the edges of this region again using the intersection graph method.
D.9 Complexity
Pairwise tests are always run on the pool in our algorithm, and context-specific test are "localized" to near the indicator. This means, our algorithm scales like standard PC for increasing variable count but fixed context-variable count. But also for large (or increasing) context-variable count only the possible values of variaabls "nearby" are taken into account context, leading to an
22

---

(approximately) linear scaling: The precise number of tests in each iteration of our algorithm depends on the number of links remaining after the previous iteration and is thus difficult to estimate precisely, However, on finite data, dependencies are typically only detectable for finite number H of hops along true causal path. Given that the union graph has a finite graph degree Dg. each variable is found dependent (is within H hops) of a finite number 3 I 8o Da. H) of other nodes (upper bounded by a function of graph degree Dg and maximum number of hops H independent of the number of context variables K and the total number of variables D, e. 30 = OK (1)). Every variable is thus after the pairwise tests (pairwise testing is always done on the pool) adjacent to less than So other variables. We assume" that the density K/ /D of indicators is small compared to So and each indicator takes at most C (1) many different values. Then on average there are I 30 x K //D x C' many context-specific tests for each variable. Running up to CSI tests on average on all D variables leads thus to less than 30 x K x C many CSI tests on average, so our algorithm is (KK) on average. Under the assumption that K /DD is fixed as D increases (the density of context variables in the graph is constant), the algorithm is ((2)) as is standard PC (the D2 comes from the number of pairwise tests growing faster than the CSI-count).
In comparison, a masking or intersection graph approach, as described in Sec. D.10 has to run all tests for each combination of indicator values, thus scales ((exp( ()), as each indicator can take at least two values, i... there are at least 2 combinations. Thus, our method could scale comparatively well to larger setups involving many variables and context indicators.
D.10 Baseline method / intersection graph
From the perspective that information in causal graphs is in the missing links, one would expect that running causal discovery once on the masked/ speciit- data (all data points with R r) to "ier (containing edges from selection bias; we exclude R from the graph, as it is constant) and once on the pooled data (all data points) to obtain Grool (which in the case of an acyclic union graph is not the union graph) one should find all necessary information. Thus, we would expect that the intersection graph obtained by intersecting the obtained sets of edges returns the correct spntext-specific graphs. Indeed now also have the theory in place to verify this:
obtain Gmask
Lemma D.3. The intersection of the edges obtained from the pooled and masked results yield the correct descriptive graph:
Gmask
Grool
dleeser
R=r"
Proof. This follows directly from the Markov property (Lemma 4.1 and faithfulness (Lemma 4.2), even if one only tests Z in adjacencies in the respective discovery algorithms (because both mamask (Y) 2 Adjkerr (Y) and Adjpual(Y) 2 Adjieer )Y)).
Adj
Remark D.3. Generally, the information argument about (mask n Gpool works as is, but our results show that this has indeed a meaningful connection to the SCM.
This approach even avoids the problems of Sec. D.7 However, it has some severe disadvantages on finite data: Both discovered graphs are individually less sparse than GR and thus more CITs are necessary (and especially more CITs with large separating sets, which are particularly problematic for both precision and runtime). Furthermore, all tests are executed once on the pooled data for Grool and once on the masked data Grnnsk Thus, twice as many tests would be necessary. even without the lack of sparsity. With multiple context indicators, the intersection graph approach would scale exponentially while our method scales linearly, as discussed in Sec. D.9
We use this approach as baseline to validate the finite-sample properties of our algorithms. We also discuss how to use the intersection graph approach when large cycles may exist in the union graph in Sec. D.8. Sec. While large cycles can possibly pose problems for our method, combining our approach with the intersection graph method could yield the correct result a more efficient way than only using the intersection graph approach.
'Then within the B many adjacencies there is typically at most one indicator; generally we could replace C by C as there are at most 3o many adjacent indicators with at most 8r many combinations of values, which is still (1).
23

---

D.11 Difficulty of detecting context-system links
Testing R IL Y is not only difficult due to non-linearities, but also due to the following problems: We focus on the case where R is binary for the example Y ( X + IJy, and X 7/x with both 7x, f ~ (O, 1) standard normal. Here Y M.. R (with the empty conditioning set). This is essentially a two-sample test, c., we are asking if P(Y R 0) * P(Y R 1). This difference is only visible in variance (higher moments) and not in mcan value. P(Y R = 0) is simply тγ and thus standard-normal (0, 1). while P(Y R 1) is the sum of two independent standard- normal distributed variables (7x + 17 ) so it is (0, 0² = 2). Many independence measures like correlation or generalized covariance measure (30) insensitive to changes in higher moments only (e. g., testing the correlation of R and Y checks for the non-zero slope of the linear fit through (0, E|Y - 0) and (1, E[YRR = IJ). Mutual information distance correlation based tests can gain power against this alternative. Generally, using parametric tests for this scenario (even simple workarounds like testing correlation on squared absolute values) should also be possible and might provide better power. Some care should be taken (30) Example 1) to formulate the model-class we actually want to test on, as we also have to be able account for the synergistic (the model is not additive in X and R) dependence on R.
D.12 A remark on CIT with regression
Conditional independence testing often relies on regressing out conditions and testing on residuals (e.g. partial correlation). This is usually justified for causal discovery roughly follows: Only the "true" adjustment set has to work- "erroneous" independence is assumed impossible by faithfulness and only if X and Y are "truly" non-adjacent. The "true" adjustment-set for X, Y is w. o. g- Z = -Pa(Y), with P(Y 2) = | do)))) so the regression function approximates the structural mapping (in particular single-valued); so for additive noise
fr which exists and is well-defined models testing on residuals should work.
One might, at first glance, consider that this may fail hold if some links from Z to Y are context- dependent (thus multi-valued). However, this is not the case: If link from Z to Y vanishes by a change of mechanism, then R E Z Pa(Y) and the multi-variate fy is not multi-valued (on its multi-dimensional input). If link from Z to Y vanishes by moving out of the observational support, the previous argument still works, i.e., fy does not change.
Moreover, if the per-context system (dependencies on variables + R after fixing r) is additive (e. linear), then the fit can be done additively because, again, if link from Z to Y vanishes by a change of mechanism, then I Z = Pa(Y), Since our method tests on data with R = r only, it learns a consistent restriction of the multi-variate fy where it is additive. For example, if Vr R=r) is linear with Gaussian noise, then conditional independence between two variables X, Y, both # R, can be tested by partial correlation, and the method remains consistent.
D.13 A Remark on Error Propagation
Errors involving links to R affect the performance of the algorithm as follows:
For false negatives (a link involving R is not found), no CSI is tested, and thus it does not find additional context specific information, but it also does not incur further errors beyond those inherent to PC.
In the presence of false positives (a link involving R is detected to a non-adjacent Y), our method- - like PC executes more tests than strictly necessary, because more adjacencies are available. If R is erroneously found as adjacent, and is added to the conditioning set, in our case the tests will be run as CSI (for R r), i.e., using the context-specific samples only. This can lead to testing sample size resulting in further finite sample effects. It should not induce selection bias, because we only have to find (at least) one valid separating set, but if R is non-adjacent such a separating set, not containing R. exists, still allowing to correctly delete the link.
reduced
D.14 Labeled union graphs
Knowing Gdessrr for all r, we can also construct a labeled union-graph similar to LDAGG (or more precisely copiext-specific LDAGs (18 Def. 8)). This follows the philosophy that one obtains strictly
24

---

more information than just the union graph, and wants to represent this information as an extension of the union graph rather than in separate graphs.
There are two viewpoints on how to symbolize multiple graphs in one: The information in the graph (about factorization of the distribution) is in the missing links, hence, link labels indicate when they "disappear" (stratified graphs and LDAGs follow this convention) or the edges represent mechanism relationships of the underlying SCM and labels represent when mechanisms are "active." 'The second option seems more straightforward to read (from a causal model perspective), so we follow this convention below:
If there is an edge X + Y in R=y for all r, insert an (unlabeled) edge X Y into the labeled union graph.
If there is never an edge X + Y in feer for any than there is no edge from X to Y in the labeled union graph.
If there is an edge X Y for r E R, and no edge for & R, with R * a proper (i.e. not equal to) subset of the values taken by R, then add edge labeled by R, e.g.
X (ro.ri.7a), Y, to the labeled union graph.
E
Further details on the simulation study
Here, we describe the data generation approach for the numerical experiments in detail. Moreover, we present further results which aim to explore the robustness of our method under different scenarios.
E.1
Data generation
We generate the simulation data using SCMs. We start by constructing what we will call the base SCM/ graph, linear SCM with up to nodes, and with acyclic (mechanism) graph, of the form
X; = ((P((X;)) + ca7s
where: I,...,
1......+...... D+1, Pa(X.) are the parents of Xi, Cj are constants, and fy are exogenous noise terms. The function Si (Pa(X:)) is defined as:
f((a(()))=
E asj.y. X,EP((X.)
We use a desired sparsity level s I 1, which leads to the number of total links L (non-zero coefficients agz) be found as the fraction of the total possible number of links D(D + 1):
D 11)
As a next step, we select a variable to become the context indicator R. To this end, we randomly select index k E {1, (1..... D 1). Then, assign the variable X₃ as the context indicator, i.e., R = X₁. For example, if = 2, then R = X2.
As discussed in Sec. 3 R is categorical variable that indicates which of the Ploomietts context- specific SCMs the respective sample belongs to. Thus, we must generate categorical values from the continuous values of Xg. To achieve this, we define Reantetts 1 quantiles (91..... In } as linearly spaced values between and 1. These quantiles are then adjusted using balance factor to compute the final quantiles as ( The balance factor b affects the distribution of data points across contexts:
If 1, the data points are balanced across contexts.
* If 6 < 1, the balance tips towards the left tail of the distribution.
If 6 1, the balance tips towards the right tail of the distribution.
25

---

Using the adjusted quantiles, we compute the values for R as follows:
if Xx < of
2
if of < X <
R
Meontextss
if Xx 9
Thus, the continuous variable Xg is converted into categorical variable R indicating the context based on the thresholds defined by the adjusted quantiles. This results in R having a non-linear relationship all other variables.
Using R. we can now proceed to generate context-specific SCMs which have ehangg changed links compared to the base graph. For this, we edit the base graph sequentially using the allowed operation set Spps. as follows:
1. Randomly select variable X (excluding R),
2. Randomly select an operation from the set Sups
3. Apply the change to the graph:
Add an Edge: Add an edge from X to another randomly selected variable Xe, if an edge between X, and X does not already exist.
Remove an Edge: Remove an existing edge from X, to a randomly selected adjacent variable X
Flip (Reverse) an Edge: Reverse an existing edge from X, to randomly selected adjacent variable Xe,, making Xe the parent of X
4. Add a link from R to Xe. If the selected operation is flip, then add a link from R to X and Xe'
We note that performing the selected operation on the randomly selected node is not always possible. For example, the node might not have any edges to remove, or adding an edge would lead to the graph being cyclic. We, therefore, check for possible inconsistencies and repeat the process several times (in the case of the experiments presented here, 10 times). an accepted graph is not obtained interrupt the process and continue with new base graph. Therefore, not
after these repetitions, all repetitions of an experiment may be successful.
As described in Sec. 5.2
we can either enforce cycles between the context-specific graphs (and thus, cycles the union graph) or we not allow them for specific configuration. the configuration must contain cycles, for each proposed edit operation, we check whether doing this operation would result cycles and accept so. Otherwise, we reject the operation and start a new trial. This also leads to some repetitions of an experiment not being successful. We mention that we do not enforce specific cycle length.
Once a context-specific SCM is created, we generate the data according to this SCM. For each variable X; in the context-specific SCM, we determine its value based on its parents and the structural equations of the SCM. Formally, for a variable X, with context-specific parents for context R = Pa R=r (Xi), its value is generated as:
X, = fA + cap
where Se defined as in Equation by the context is generated according to the modified SCM, incorporating the context-specific changes introduced during the editing phase.
2
By following this process, we ensure that each variable affected
F.2
Failed attempts
As mentioned in Sec. 5.2 we repeat each experiment 100 times. However, discussed above, due to the random data-generating process described above, not all graph generation trials are successful. The accompanying 'faleed.ttt file in the .zip file reports how many graph generation trials have failed
26

---

for each configuration. Here, we mention that, for the results presented in S.c. 10 trials have failed. We also report the number of failed trials in the following subsections which present additional results.
E.3
Further results
We now present results for further configurations, which vary D, and well as detailed discussions of the experiments mentioned in the main paper. All results were obtained by conducting trials in parallel across cluster of 116 CPU nodes, each equipped with 2x Intel Xeon Platinum 8260 processors. The supplementary .zip file contains the original code used for running the experiments on the cluster. Additionally, we provide an option to run the experiments in sequential mode.
E.3.1 Further results for the configuration in Sec. 5.2
Contests: Channgd
Density:
Faise. Remove
TPR
FPR
1.00
0.10
0.00
0.09
0.80
0.08
0.70
0.07
0.60
0.06
0.50
8.05
0.30
0.63
0.10
0.61
0.00
0.00
188
1030
2550
1.00
0.10
0.90
0.09
0.80
0.00
0.70
0.07
0.00
6.00
0.50
6.05
0.30
5.03
816
6:0
0.00
5.00
adj
adj
Figure 4: TPR and FPR results for setup presented in Sec. 5.2 without eycles in the union graph, where all links to R are known (adj.R-all for the methods PC-AC (our algorithm), PC-B (baseline), PC-M (masked data) and PC-P (pooled data). Results for the union graph are presented the row above, and results for the context-specific graphs averaged over contexts are presented in the row below.
Results with context-system link assumptions Fig. presents the results from the setup presented in Sec. [.] without cycles where all links to and from R are known. Knowing these links significantly improves TPR for all methods. Notably, PC-M has the highest TPR and FPR, indicating that only knowing about the context-systen links in the endogenous context indicator setting does not suffice for PC-M discover the correct graphs. The FPR is generally lower for the other methods, indicating fewer false discoveries due to the reduced uncertainty about context-system connections.
27

---

Nodes: 8, Contexts: Chanceed Link:: Density: 0.4,
Cycles: False, Gp.: Rermaee
Edgemerk
Edgemark
031
037
Unien
035
0.0
10000
12000
1000
2000
3000
Avg. ContOOa
18
1000
2000
1000
2000
Sample Size
Sample Size
PCAC odi, R-ail
PCP adj. R-all
PCB A-ch
PCM od). none
PC-M
PCAC Rich.
RCP Rich.
PCB ad) nome
PCB sd), Rvlll
PC-M edj. R-ch.
PCP
Figure 5: Edgemark precision (prec.) and recall (rec.) results for the setup presented Sec. 5.2 without cycles in the union graph, where either all links to R are known (adj. R-all, dotted line), only the children of R are known (adj. R-ch, interrupted line) or no links are known (adj. none, straight line). Here, we present results for the followinf methods: PC-AC (our algorithm), PC-B (baseline), PC-M (PC with masking) and PC-P (PC on pooled data). Results for the union graph are presented in the row above, and results for the context-specific graphs, averaged over contexts, are presented in the row below.
Edgemark precision and recall Fig. 3 shows the precision and recall values for both the union and the context-specific graphs (averaged over contexts) for PC-AC, PC-M, and PC-B and the union graphs for PC-P for the different link assumptions. On the context-specific graphs, we observe that assuming links to and from the context indicator are found (adj. R-all), PC-AC has the lowest precision, i.e., lower risk of falsely oriented edges, and highest recall, i.e., finding the correct orientations, followed PC-B. For the other link assumption cases, our method outperforms all other methods for the context-specifie graphs. For the union graph, PC-P scores best, likely because it finds the most links the union case, followed by our method. PC-M scores last.
E.3.2 Cycles
S.2.5.2 with the difference that cycles between the context-specific graphs enforced here. For this experiment, total of 29 trials have failed (see Sec. E.2). From the total of samples, 69 samples have cycle length 2, and 2 samples have cycle length
Fig. 6 presents results for the experimental setup as described on Sec. 5.2
We observe similar behavior of the TPR and FPR for the non-cyclic results presented in Sec. 5.2) However, some differences are less pronounced, possibly due to the increasing complexity of the problem. As expected, the FPR for PC-P, which only detects the aycyclification, increases. We observe that for all versions without link assumptions, the FPR increases significantly compared to the setup without cycles. The largest differences FPR between PC-M and PC-AC are for smaller number of samples, up to 2000. For 3000 samples, the FPR of PC-M is lower than the FPR PC-AC, possibly due to overall fewer links being tested compared to PC-AC: Since PC-AC also finds context- terms of TPR, PC-AC, and PC-B perform best for the context-specific graphs, especially without any link assumptions.
links, it tests more adjacent pairs and possibly finds more links. However,
28

---

Nodwe: B, Conteate: 2. Changed linke 1, Density 0.4,
Cyclas: Remove,
1.00
1900
2000
9000
1990
2000
3000
6.08
N60 Contoo
0.70
0.07
0.00
6.06
0.50
6.05
0:30
6.03
n10
2.01
0.0
1000
0.00
3000
Sample Size
Sample Size
PC-L adj Real
ML-P adj R-al
PL-U adj. Rich
PL-M adj. nome PCB adj none
PCAC
PCB 5d). Rill
RCM sdj. R-ch.
PC-A atl. nonw
Figure 6: TPR and FPR results for the setup presented in Sec. 5.2 where cycles in the union graph enforced. Here, present results where all links R are known Radj.R-all, dotted line), links to children of R are known (adj. R-c., interrupted line) or without any link assumptions (adj. none, straight line) for the methods PC-AC (our algorithm). PC-B (baseline), PC-M (PC with masking) and PC-P (PC on pooled data). Results for the union graph are presented in the row above, and results for the context-specific graphs, averaged over contexts, are presented in the row below.
E.3.3 Comparison with FCI-JCIO and CD-NOD
Nodes: B. Contestis: 2. Changed Lnks: Density: 0.4.
Nodes: B. Contests:: 2. Changed Unke: Density: 0.4,
Cyclis: False, Remove
Cyclus: Tue, Op.: Ramove,
TPS
FPR
1.00
0.30
3.00
0.30
0.90
0.90
0.50
0.28
0.50
0.28
0.70
0.27
0.70
0.27
0.30
0.21
0.30
0.31
0.00
0.20
5.00
0.20
PCACC adi: none ad, none
PCB none
FCI adj, nome
CD-NOD adj. none
PCP ad). nome
Figure 7: TPR and FPR results for the setup presented in Sec. 5.2 without cycles in the union graph (left plot) and with enforced cycles in the union graph (right plot). Here, we present results where all links to are known u-alR- for the methods PC-AC (our algorithm), PC-B (baseline). PC-M (masked data) and PC-P (pooled data), FCI-JCIO (FCI) and CD-NOD. Results for the union graph.
Skeleton discovery As mentioned in Sec. 5.2 we compare the results of our algorithm for the
discovery of the union graph to the Fast Causal Inference (FCI) algorithm (32), discussed as JCI-FCIO in Mooij et al. (15). We apply JCI-FCIO, which does not assume exogenous context variables (we name it only FCI from now on) for the multi-context setup, and CD-NOD (39), a causal discovery algorithm for heterogeneous data, which assumes exogenous context variables. Both algorithms applied to the pooled datasets. We use the causal-learn implementation (40) for both algorithms. Since, for the available implementation, it is not possible to introduce link assumptions from the beginning of the discovery phase (while it is possible to introduce link assumptions, at the moment, they only used to refine the graph after the discovery phase), we only evaluate the algorithms for the case without link assumptions (adj. none). As the algorithms only use pooled datasets, we do not present any result for the context-specific graphs.
Fig. presents the results for the setup in Sec. 5.2 of the main paper, without cycles (left-most two plots) and with cycles (two right-most plots). We observe that both FCI and CD-NOD behave
29

---

similarly to PC-AC. We observe minimal differences between PC-AC and CD-NOD for smaller samples, with our method performing slightly better. FCI performs best across all methods in terms of FPR. Nevertheless, FCI can only recover the union graph, and thus, our method still has the advantage of gaining more descriptive information than FCL. However, our method may perform poorly due to the CTT, and we believe that using an adequate CTT, our method can improve over FCI and CD-NOD.
Edge orientations We observe that FCI and CD-NOD perform best when comparing the precision and recall values for the edge orientations between the different methods. This result is expected: Our method focuses skeleton discovery and does not propose any special rules to orient edges obtained from the union the context-specifer graphs, which is left for future work, as discussed in Sec. 6 CD-NOD and FCI develop specific orientation rules involving the context indicator, and thus are expected to perform better in terms of orientations at the moment. However, as we consider that there additional information from the context-specific graphs that can be used orient more edges, as exemplified in Sec. F.. we believe that the performance of our method regarding edge orientations can be significantly improved.
Cycles: Falsc, Op. Ramove
Unionn Edggemerk Prec.
Union Edgemmnt k Re:
PC-AC adi, none PC H ad. none
PC-6 ad), none - PC ad). nore
FG1 ad). nome
LU-ROD ad). 7016
Figure 8: Edgemark precision (prec.) and recall (rec.) results for the setup presented in Sec. 5.2 without cycles the union graph. Here, we present results where all links R known (adi./--all), for the methods PC-AC (our algorithm), PC-B (baseline), PC-M (masked data) and PC-P (pooled data), FCI-JCIO (FCI) and CD-NOD. Results for the union graph.
30

---

E.3.4 Higher number of changing links
Nodess: Contexts:
Unks:
Nodies: Contexts:
Lnks:
Cycles: False, Op.: Remove
Cycles: False, Op.: Remove
1.00
0.30
1.00
0..0
0.50
0.06
0.50
0.06
8.00
0.08
0.80
0.08
0.70
0.07
0.70
0.07
8.80
0.08
0.60
0.08
0.50
0.05
0.50
0.05
8.30
0.03
0.30
0.03
0.30
0.01
0.01
5.00
0.00
1..00
2000
2000
0.09
Wig Conceste
1000
1009
1000
1000
1000
Sample
Sample
PCAC od), R-ai
PCP adi, Raall
PCB R.j.R
PC. ad), none
8o;
ed,
PCU sd), Rilll
PC-M ed), Rich.
PC ac ad). none
Figure 9: TPR and FPR results for the setup presented in Sec. 5.2 without cycles in the union graph, but with higher number of changing links nehsaage (left plot) and Tecangee (left plot). Here, we present results where all links to R are known (adj. R-all), links to children of R are known (adj. R-c.) or without any link assumptions (adj. none) for the methods PC-AC (our algorithm), PC-B (baseline), PC-M (masked data) and PC-P (pooled data). Results for the union graph are presented in the rows above, and results for the context-specific graphs averaged over contexts are presented the rows below.
Here, we explore the scenario where the number of changing links between contexts varies. We keep the experimental setup as in Sec. 5.2 only changing the number of changing links 7lhange to 2 and 3. Figure shows that as the number of changing links increases, the TPR generally improves, suggesting that the presence of more changes provides more signals that the causal discovery process can detect. Conversely, higher number of changing links leads to an increase in FPR, especially for the cases without link assumptions. However, we believe this is due to the CIT, which generally leads to a higher FPR, as the results in Sec. 5.2 of the main paper indicate. Our method performs similarly or outperforms PC-P, PC-M, and PC-B for cases with known links from R to its children. We mention that, for this experiment, a total 18 trials have failed for Tehanng and 25 trials have failed for Tehange (see Sec. E.2).
31

---

E.3.5 Higher graph density
Nodes: B, Contexts: 2. Changed Links: Density: 0.6,
Dycles: Fabse Op.: Remove
1:00
6.10
8.90
8.8
8.08
8.
0.61
0.30
1008
y050
1090
1000
260 Controe
0.70
0.00
0.50
0.30
0.03
n0
2.1
0.00
1850
3050
6.00
1000
2000
Sample Size
Sample Size
PC-L adl Real
PL-P edj R-al
PL-U ad). Aich.
PL-M adj. nome PCB adj. nome
PCB od) Rall
RCM odj. R-ch.
PC-AC atl. none
Figure 10: TPR and FPR results for the setup presented in Sec. 5.2 without cycles in the union graph, but with a higher density value s 0.6. Here, we present results where all links to R are known (adj. R-all), links to children of R are known (adj. RF-..) or without any link assumptions (adj. none) for the methods PC-AC (our algorithm). PC-B (baseline), PC-M (masked data) and PC-P (pooled data). Results for the union graph are presented in the row above, and results for the context-specific graphs averaged over contexts are presented in the row below.
Here, we examine the impact of increasing the density of the base graph on the performance. We keep the experimental setup as in Sec. 1.2 and only the graph density to 8 0.6. As Fig. TO shows, with higher graph density, the TPR decreases slightly compared to the results in the main paper, while the FPR increases. This is likely due to the increased complexity of the problem and possible confounding. The denser the graph, the more candidate links the algorithm needs to evaluate, which can increase the likelihood of falsely identifying spurious links as causal. Our algorithm still outperforms PC-M for known links between R and its children. PC-B scores best overall in terms of FPR, but its anite-sample issues lead to lower TPR results, indicating that it finds fewer links overall. For this experiment, we mention that total of 12 trials have failed (see Sec. E.2
E.3.6 Smaller and larger number of nodes
Fig. 11 present the performance of the algorithms across graphs with different N = 6 (left plot) and 12 (right plot), while the rest of the experimental setup remains described Sec. [5.2 Generally, TPR decreases as the number of nodes increases, possibly due to the increased complexity and the higher dimensional space which the causal discovery process operates. Larger graphs have more potential causal connections, making it harder to distinguish true causal links from noise. The FPR slightly increases with the number of nodes. However, our method (PC-AC) still outperforms PC-M when no links are assumed, or the links from R to its children are known. For this experiment, we mention that a total of 14 trials have failed for N = and trials have failed for N = 12 (see Sec. E.2
32

---

Nodees: 6, Donteats 2. Changed linke 1, Deostty O.A.
Nodee: 12, Coetestec Changedd Links 1, Density 0.4,
Cycles: Falsa, Remova
cycles: Falsa, Op. Remove
1.00
1.00
0.50
0.80
0.00
0.00
0.70
0.07
0.70
0.07
0.60
0.50
0.30
1980
1000
5600
1980
3000
1.00
0.900
0.70
0.80
0.08
0.07
Aeg. Conteats
0.70
0.07
8.60
0.06
0:00
0.06
0.05
0.50
0.05
9.30
0.03
0:30
0.03
10
0.01
10
0.01
8.00
1050
0.00
1000
0.00
1000
3000
0.00
1000
3000
Sample Size
Sample Size
Sample Size
Sample Size
PCAL adj Ieal
HL-P adj R-al
PL-U ad), N-ch
PL-M adj. nome
PCAC
PCP
PCB ad) none
PCB sd). Rall
RCM sdj. R-ch.
PC-AC atl. none
PCP
Figure 11: TPR and FPR results for the setup presented in Sec. 5.2 without cycles in the union graph, but with number of nodes N 6 (left plot) and N = 12 (right plot). Here, we present results where all links to R are known (adj. Rl-ll), links to children of R are known (adj. R-c.) or without any link assumptions (adj. none) for the methods PC-AC (our algorithm), PC-B (baseline), PC-M (masked data) and PC-P (pooled data). Results for the union graph are presented in the rows above, and results for the context-specific graphs averaged over contexts are presented in the rows below.
E.3.7 Data imbalance
Nodes: Contests: Links: Density:
Cycles: Fal se. Op.: Remove
TPR
FFR
1.00
0.10
0.90
0.09
0.80
6.CB
0.70
0.07
0.60
0.06
0.50
6.03
0.30
0.43
0.10
0.01
0.00
0.00
2000
1.00
6.30
0.90
5.08
Ang. Contess
0.00
5.00
0.70
0.07
8.00
0.08
030
0.05
0.30
0.10
8.01
8.00
8.00
2000
2009
Sample
Sample
PCM Roal
PCP wdj, Roll
PC-B Rich
PC-M
PCM ac; Rall
PC-AC ad, R-ch.
PCP R-ch.
PCB od). Rall
PCM od), Rich.
PC-AC ad) none
adj none
Figure 12: TPR and FPR results for the setup presented in Sec. 5.2 without cycles in the union graph, but with data imbalance factor 1.5. Here, we present results where all links to are known (adj-R-all), links to children of R. are known (adj. R-c.) or without any link assumptions (adj. none) for the methods PC-AC (our algorithm). PC-B (baseline), PC-M (masked data) and PC-P (pooled data). Results for the union graph are presented in the rows above, and results for the context-specific graphs averaged over contexts are presented in the rows below.
Results investigating the effect of data imbalance, presented in Fig. 12 show that our method, PC-AC, still performs better in terms of FPR or TPR compared to PC-M, despite data imbalance factor of b = 1.5, if links from R to its children are known or without any link assumptions, similar to the
33

---

results in the main paper. While the overall FPR increases slightly from the results presented in Fig. especially for PC-P, this increase seems insignificant. We mention that, for this experiment, total of 10 trials have failed (see Sec. E.2
E.4 Computational runtimes
We evaluate the computational runtimes of the different methods evaluated in Sec. 5.1 and App. and present these in T PC-AC has slightly higher runtime than PC-M due to the additional tests involving the context variable. Among the methods that generate the union graph, the baseline PC-B has, as expected, the longest runtime, as it uses the information from both the PC-M results and the results of PC on the pooled data (PC-P). We also observe that CD-NOD seems to be the most time-efficient algorithm on pooled data, while PC is the most computational intensive. This difference in particular might arise from implementation details.
Table 2: Comparison of the computational runtimes in seconds of the PC-AC, PC-M, PC-B, PC, FCI and CD-NOD method that have been used the experiments. While PC-AC and PC-M use only context-specific data, the other methods generate union graph and or the pooled datasets, as For the PC-AC and PC-M, we present the average time per regime in seconds.
discussed in Sec. 5.1
-onfext-specific data (avg, regime)
Union pooled data
PC-B
PC-AC
PC-M
PC
FCI
CD-NOD
PC(M
200
2.784
2.345
1.419
4,203
0.874
0.775
n
500
3,254
2.679
1.693
4.947
1.054
0.974
n 1000
3.632
2.948
1.923
5.555
1.282
1.173
n 2000
4.444
3,379
2.382
6.826
1.636
1.451
5.302
3.862
8.202
1.915
1,730
Extensions and future work
In the Discussion Sec. 6 we have outlined a few ideas for extensions and future directions for the algorithm presented in this work. Here, we discuss these ideas in more detail.
F1 Orientation rules
In some cases, additional edge orientations beyond JCI arguments (15) are possible by using context- specific information. For instance, consider the following example:
Example F.1. Orientations Beyond JCI:
In context O, we have X + 7 <- Y. In context 1, we have X + Y, and no edges at Z.
Context 0:
Context 1:
ICI/Union.
Z
R
X
X
Context 0 can be oriented by the unshielded v-structure, context can be oriented by JCI argument (15). In the ICI case, both X + Z + R and X + Y + R are unshielded v-structures, thus leading orientations. The v-structures X + Z - and R Z +- Y are both shielded. Furthermore, the v-structures that would occur for Z + and thus could not have been detected, and there is no conclusion that could be drawn from not detecting them. Thus the (pooled) independence structure is symmetric in Y and Z. Therefore, also no graphical consistency criterion (avoid directed cycles etc.) can lead to an orientation the edge between Y and Z and the graph obtained by JCI is also completely symmetric under exchange of Y and Z, missing the orientation of the edge?> Z (which in context is found immediately by our method).
i.e. i.ee. X + Y Z and R + Y <- Z are both shielded
34

---

For the following example,
B
x
Z
slightly different problem occurs. Orientations are obtained by observing that X + Y + R unshielded, thus detectable, and in context A, Y + Z can be excluded, because would introduce Y Z (which used for orientations in context B). This argument
the unshielded v-structure works only for the sparse union graph (as opposed to its acyclification) and only per context (the orientation only well-defined per-context). The latter point makes it fundamentally inaccessible to JCI arguments, the former point also leads to the problem of Example F. (where it occurs independently of the second point).
F.2 Deterministic indicators
In realistic examples, context indicators are often obtained by thresholding. An extension to such deterministic functions of observables seems possible follows:
g(W) for an observable W (g could be multi-variate, see below), add C' as node to the output graph and draw special edge W - C (indicating that this edge is deterministic and provided by expert knowledge). Then exccute a standard constraint-basee causal discovery method the variables (excluding C)) with these modifications for all values of C occurring in data:
Given deterministic indicator
(i) If X IL Z|Z is required, and W Z, then test TL Y|Z, gWW) c instead.
(īi) If the resulting regime-specifts skeleta differ from the union graph in the removal of an edge
Y, then:
(a) both and Y are adjacent to W. save the edge (X, as ambiguous for (iii).
(b) neither X nor Y are adjacent to (which could happen if the links W are deleted with larger adjustment sets). then mark the link special (indicating that this is not physical change by Lemma C.4).
(c) If only Y (or only X) is a child of W, draw a (directed) edge C' + Y (or C + X).
(iii) After the orientation phase (potentially using Sec. F.I for each ambiguous edge (X, Y) saved in (ii) (again using Lemma C.4):
(a) If the edge was oriented X + Y, draw a (directed) edge C ->>>> Y. (b) If the edge oriented X Y. draw (directed) edge C - X. (c) the edge was not oriented, draw special (indicating to the user that they are ambiguous, possibly only one of them real) directed edges C' + X and C + Y.
In this scenario, testing IL Wlg(W) could provide additional information: Example F.2. Qualitative and Quantitative Context Dependence:
Assume C = g(W) as above is binary, and
== (a (CC) x (1 + 3W) x X my.
a = 0, then the mechanism depends qualitatively on C: = 0, then does not depend on X.
If 0, then the mechanism depends quantitatively on W.
In the qualitative case (a = 0), the CSI changes: X IL Y = 0. In the quantitative case (3 4 J. YIC (note that one could even check Y / Y for further info), while in the non-quantitative case (B = 0) Y IL YIC.
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The adaptive nature our method is explained in Sec. 4 the assumptions and connection to SCMs are in Sec. theoretical results in Sec. 4 and finally, the numerical experiments are reported on in Sec. 5.2
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We explicitly state the assumptions of our method, we evaluate our method on a wider set of experimental setups to investigate its robustness, and explicitly discuss the limitations of our work in Section Sec. 6 We discuss computational complexity in Sec. D.9
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
36

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We explicitly state the assumptions our approach made. We add proof sketches for all the claims and theorems the main paper, and offer the complete proof appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We propose a version of the PC-algorithm, for which we offer pseudocode in the paper. We generate our own synthetic datasets. We discuss the data generation model at length in Sec. [E.]] and report the parameters used for experiments in Sec. Sec.5.2 For exact reproducibility, we submit the code as a supplementary zipp file. The details for reproducing the experiments are presented in the readme file. Upon acceptance, we will publicly release the code.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
37

---

(d)
reproducible, they We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have submitted the code as supplementary .zip file, and will release it publicly upon acceptance. In the .zip file, all code for the following steps needed to reproduce the results is available:
the implementation of all algorithms discussed in the paper
the data generation
the parameters for the different experimental setups (as a YAML file per setup)
the code for running the results both in a sequential and parallel (cluster) setup
the code for obtaining the metrics and plotting the results
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
httblss.c/puulli/guuueees
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have presented the parameters used for the data generation model in Sec. 5.2, Additionally, all parameters for each experimental setup can be found in individual YAML files in the .zip file accompanying this paper, with additional information in the readme file.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
38

---

7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Yes, the paper reports error bars. As described in Sec. 5.2 we generate error bars for all results presented in this paper using bootstrapping with 200 samples. For some of the results, especially for the true positive rate (TPR), the error bars are small, and thus cannot be distinguished from the dots indicating the result.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative етгог rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We report the computational setup on which we ran our experiments in
Sec. F.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't ' make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https::/neuurpps.ccem http://pp...pppplle.cccccccc..dd
Answer: [Yes]
Justification: We mention the licesenses under which the code released in the code files provided in the .zip file.
Guidelines:
39

---

The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there is a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: As our work is not tied to particular applications, we do not believe that this question applies to it.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: As our work only uses synthetical datasets, we do not believe this question applies to it.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
40

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We mention the two main packages which we base code. The rest of the packages used for the code are mentioned in the readme file in the zip supplementary file. We mention the license under which the code will be published in the readme file.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We document the synthetic dataset generation process and the necessary parameters in the main paper, as well as in the code provided in the ziip supplementary file.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our datasets are synthetically generated and no human subjects were involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
41

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No human subjects were involved in this work.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
42


Reviews:
[{"review_id": "Yaa2waMIs0", "reviewer": "Reviewer_9Xqc", "summary": "The authors address the problem of causal discovery in situations where causal relationships change across different contexts. They propose a modified version of the PC algorithm, which either performs a conditional independence test (CIT) on pooled data or context-specific data, depending on the scenario. The paper presents several theoretical results for this modified algorithm and evaluates its performance through various empirical studies.", "questions": "Please see above.", "limitations": "Please see above.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors tackle an important and relevant research problem, and their theoretical findings are noteworthy, especially the set of sufficient assumptions under which they derive their results. These assumptions could be valuable for future research in this area.", "weaknesses": "The organization of the paper makes it difficult to follow. For instance, numerous graphical definitions are presented without examples or figures, even in the appendix, which would aid understanding. I strongly suggest at least a running simple graphical example to show different graphs. Additionally, the definitions of the main assumptions are not included in the main text, further complicating comprehension.\n\nThe results rely on the assumption of causal sufficiency, but it is unclear how these results could be generalized to scenarios with hidden variables. Another significant limitation of the proposed framework, as acknowledged by the authors, is the requirement for knowledge of the context indicator.\n\nThe proposed algorithm require $Adj(X_j)$ and whether R belongs to this set for all $j$. This knowledge is obtain by a standard PC algorithm using pooled data. What happen if the output of this PC algorithm is noisy, e.g., it returns that R belongs to the conditioning set but in reality it is not?\n\nWhile the proposed algorithm clearly outperforms the baselines in certain settings, the margin of improvement is relatively small, particularly when the conditional independence test is non-parametric.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for reviewing our paper, and for acknowledging the importance of the problem. Furthermore, we thank the reviewer for appreciating the value of the set of assumptions we have derived for a first step towards solving the problem of endogenous context variables.\nWe address the weaknesses as follows: \n\n* **Graphical definitions:** We agree with the reviewer that our paper should be improved to aid understanding, we address this by the changes listed in the general post. In particular we give a table to systematize the graphical objects better.\n\n* **Main assumptions:** We decided to only informally introduce the assumptions, as we believed that technical detail might actually hinder the gaining of intuition. We will have another look at this paragraph.\n\n* **Causal sufficiency:** As we are the first to consider the implications of changing observational support for context-specific causal discovery with endogenous context variables, we started to tackle the problem with a simple setup. Hidden confounders are a problem very different from the one we study. It is common in the literature to initially assume causal sufficiency, albeit there are some doubts about its realism. Difficulties to a generalization with hidden confounders could arise on multiple levels: \n\t* One has to understand how the ideas underlying the graphical objects we are currently using must be adapted.\n\t* The Markov-property combines independence tests from the pooled data and context-specific data into a single graphical object. To this end, the standard d-separation argument is modified. One has to verify this approach still works when causal sufficiency does not hold.\n\t* One has to ensure that the right tests are executed in an efficient way, which should be possible, by replacing the PC algorithm, for example, by the FCI algorithm.\n\n* **Context indicator:** We agree with the reviewer that the the fact that we must know R in advance can be a limitation. However, we would not necessarily consider it a weakness. Regime detection algorithms can be used to discover R rather than having a hard coded specific choice. Our method is *modular* and can be combined with expert knowledge or any detection algorithm providing a context.\n\n* **Noisy PC output:** Typically, with the PC algorithm, errors in the early stages of the CI testing propagate, and our algorithm is subject to this flaw as well. It is helpful to discuss false negatives and false positives separately, because they lead to different downstream effects:\n\n\tFalse negatives (a link involving $R$ is not found): After the false negative, the algorithm behaves like standard causal discovery, because with $R$ removed from the adjacencies (thus from possible separating sets) no CSI is tested. It does not find additional context specific information, but it also does not incur further errors (beyond those from the causal discovery algorithm e.g. PC). So here finite-sample results can be interpreted in a spirit similar to how assumption-violations are understood in Rmk. 4.2: The result is still as correct as it would have been without our modification, but false negatives can lead to incomplete discovery of context-specific information.\n\n\tFalse positives (a link involving $R$ is detected to a non-adjacent $Y$): Assuming no simultaneous violation of regime-sufficiency assumptions, if our method discovers false positives, it behaves like the baseline (intersection-graph) method. Thus, in the presence of false positives, our method executes more tests than strictly necessary, because more adjacencies are found. Moreover, if R is erroneously found as adjacent, it will be added to the conditioning set, thereby running the tests for $R=r$, i.e., using the context-specific samples only. Conditioning on $R=r$ wrongly can induce selection bias and can also lead to testing on a reduced sample size, leading to further finite sample effects. Therefore, the subsequent error-rate should be slightly higher than for standard causal discovery.\n\n* **Marginal improvement over baseline:** As we are not sure which baseline the reviewer refers to, we discuss:\n\t\n\t(a) Comparison including context-specific information (here *non-*parametric tests actually performed better, but we believe to understand this problem, see §B.11): Indeed, the improvement may seem small with the parametric test. However, using the non-parametric test shown in Figure 2, the CIT is seen to significantly impact performance: We see much larger differences, especially in FPR, when using a non-parametric CIT compared to masking, testing on the pooled data or the (intersection-graph) baseline. Our baseline here is the intersection graph (§B.10), which to our knowledge has not been theoretically studied before. Technically, one of the advantages against this baseline is scalability (§B.9), even though in practice one would need a sufficiently stable causal discovery method, and this is not always the case.\n\n\t(b) Comparison to existing (pooled) methods: Compared to algorithms not using CSI, we provide additional information in the form of context-specific causal graphs.", "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": "", "extra_scores": {}}, {"review_id": "3fzQ66XuwS", "reviewer": "Reviewer_DjMB", "summary": "The authors consider an SCM $M$ with a labelled and observed context variable $R$ that is endogenous, i.e., causally depends on other variables in the model. In this setting it is generally not true that $P_{M}(\\ldots \\mid R=r) = P_{M}(\\ldots \\mid \\mathrm{do}(R=r))$. Therefore, selecting only data for which $R=r$ and applying constraint based causal discovery algorithms - as one might do with exogenous context variables - will introduce selection bias when estimating context-specific graphs $G^{\\text{phys}}_{R=r} := G[M \\mid \\mathrm{do} (R=r)]$. \n\nThe authors propose an algorithm that adaptively selects whether to do a conditional independence test (CIT) using context specific or pooled data. Their method is provably complete (recovering the population graph of the underlying SCM with oracle CITs) under a set of assumptions that relate both to the underlying SCM and to the (context specific) observational distribution.", "questions": "(Algorithm 1) There is no definition of the dummy variable $i$ in Algorithm 1. Is it meant to be looped over in line 4? Is line 12 in Algorithm 1 rather meant to say \"remove $X_i - X_j$ from $G_{R=r}$\"?", "limitations": "Yes - the authors make good effort to document the challenges to their approach and motivate potential future work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The authors motivate the challenges of efficient causal discovery with endogenous context variables clearly. They thoroughly document the challenges to their approach, especially in the appendix, and highlight potential avenues for future work. \n\nWhile their submission needs refining, particularly on the clarity of their definitions, the authors provide structure for - and a novel solution to - an understudied causal discovery problem with many significant real-world applications.", "weaknesses": "(Presentation) The authors should present their results more carefully by using terms only once they are defined and being consistent with notation. For instance, the motivation behind a \"$G^{\\text{phys}}_{R=r}$\" is considered informally in the discovery goals section (a few pages before the notation is used), but the notation itself is defined neither formally nor informally in the main text. The definition is left to appendix but is not cross-referenced in the main text. Similarly, I have no idea what the \"AR\" in their method \"PC-AR\" actually stands for.\n\nThe structure of the paper unfortunately makes simple typos (e.g., \"$G^{\\text{descr}}_{R=r} \\subset G^{\\text{union}} = G^{\\text{union}}$\" on line 262) difficult to interpret or correct by the reader. If the authors could restructure the paper to assist the reader in understanding their technical contributions this would greatly impact my evaluation of the submission's presentation. For instance, the physical and descriptive context graphs could have simply been defined in the discovery goals section.\n\n(Interpretation of strong context-sufficiency) It is not clear to me what the authors mean by \"injective\" in the definition of strong context-sufficiency. I will assume that \"$f_i$\" refers to the structural equation for variable $X_i$ (the authors did not define this in the text) and take \"injective\" to literally mean $f_i$ has at most one input that corresponds to any output in $\\mathrm{dom}(X_i)$. This seems to me to be a very restrictive assumption: say $f_i$ had one parent $A$ and a noise term $e$ and both were, e.g., normally distributed, wouldn't the \"injective\" property preclude any model like $f_i(A, e) = A + e$? \n\n(Experimental design and results) In the experiments, cycle length in the union graph was not controlled despite this being required for the authors' method to recover $G^{\\text{phys}}_{R=r}$. This complicates comparison with the brute-force baseline \"PC-B\". Furthermore, details on the time taken to run PC-B versus PC-AR should have been included to understand the computational advantage of the authors' approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort in reviewing our paper. We also thank the reviewer for acknowledging the strengths of our paper, and that we have made an effort to document all possible limitations of our approach. We address the weaknesses as follows:\n\n* **Notation and typos:** We realize that in some places our notations have not been introduced, which we will fix in the final version of the paper (main text and appendix). We will revise all notations to ensure that no notation comes without a proper introduction. We will also fix the typo to simply say $G^{\\text{descr}}_{R=r} \\subset G^{\\text{union}}$ (which was intended in that place). There are some unexplained notations, such as what AR stands for (\"adaptive regimes\"). We will address these problems as well.\n\n* **Restructuring for clarity:** We will introduce a table better explaining the definitions of graphical objects better (see general post). We believe this will considerably help the reader to obtain an overview. We will also revise the Discovery goals sections and combine it with the Graphical objects section in order to improve the reading flow. Further, we will change the introduction such that it is easier to read, as described in the general post.\n\n\tThe third paragraph of the introduction does not seem to make the point we actually wanted to illustrate, and instead contains too many details and jargon (as also pointed out by reviewer 7t5U). We will improve this paragraph. Generally, we will reduce jargon in both the abstract and introduction, and we will more clearly introduce required terms such as system and context variables. \n    \n* **Strong context sufficiency:** Thank you for this remark! Indeed, this definition needs a revision. The following is what is supposed to happen when strong context-sufficiency is fulfilled: If the observational support given $R=r$ of, say, $X$, is restricted to a region where a mechanism $f_Y(X, \\ldots)$ is constant in $X$ can make the link from $X$ to $Y$ disappear when doing independence testing.\n\t\n\tExcluding CSI arising like this requires a way of saying what \"constant in a region\" means. The single-graph sufficiency assumption formally captures this requirement and restricts it to the most intuitive class of models that do not suffer from the support issues mentioned in Example 3.2. Example 3.1 shows that there clearly is a (rather large) class of intuitive models which look like $f_Y(X,R,\\ldots) = 1(R)g(X,\\ldots) + h(\\ldots)$. Now, one still has to exclude that $g$ or $h$ are constant in a region. The strong sufficiency condition aims to capture this intuitive notion, and one way of ensuring a map is *not* constant on any region is to require it to be injective: Then region simply means any set containing more than one point.\n\n\tAn example of a model that *should* fulfill this assumption is a model which becomes linear after fixing $R$. However, as pointed out correctly by the reviewer, a linear map $\\mathbb{R}^n \\rightarrow \\mathbb{R}$ can only be injective if $n\\leq1$. This is not the case here, since every mechanism also depends on its noise term. This lack of applicability can be fixed by requiring injectivity \"for each argument\" (i.e. while holding all other parents at any fixed value, for example for an additive mechanism $f_Y(X_1, X_2, \\ldots)=f^1_Y(X_1) + f^2_Y(X_2) + \\ldots$ this means each $f_Y^i$ has to be injective). This actually includes all models which are linear after fixing, i.e., intervening to set, $R=r$. We will fix this and probably add the linear and general additive cases as examples to the appendix as well.\n\n\tThe strong sufficiency assumption provides a class of examples for which we can obtain reliable outcomes with our method. However, there are many possible choices for the precise formal statement of a strong sufficiency assumption in this sense. For example, one could require, that the noise distributions are absolutely continuous and that the causal mechanisms are differentiable, and such that regions where any partial derivative is zero have measure zero. We will add a remark to the appendix discussing our choice of assumption more clearly.\n    \n* **Simulation study:** We thank the reviewer for this remark, we agree that we should have specified this. From 71 samples, only two samples have a cycle length 3, while for the rest we only have cycles length 2. Therefore, we believe that the comparison is still informative. We will also include a plot with the comparison of the run times of all evaluated methods in the final version of the paper.\n\n* **Question to Algorithm 1:** There are indeed some typos in the algorithm. First $j$ is iterated, than $i$ is iterated over adjacencies of $j$ and $S$ over subsets of a specific size of adjacencies of $j$ excluding $i$. This will encounter all unordered pairs (thus edges) of $i, j$ twice (once with names/order exchanged), so searching for $S$ in adjacenices of only $j$ (but not of $i$, whose adjacencies will be searched when encountering the pair the second time, in reversed order) suffices. As the reviewer pointed out, line 12 should indeed say $G_{R=r}$, and we will change this as well.", "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": "", "extra_scores": {}}, {"review_id": "u43ByyDLX2", "reviewer": "Reviewer_J2yL", "summary": "This paper proposes a constraint-based algorithm for context-specific causal discovery, which accommodates endogenous context variables.", "questions": "In line 80, the authors claim that \"where the context can also be endogenous (in [17])\", but in line 89, the authors also claim that \"all above-mentioned methods assume that the context variable is exogenous.\", which is quite confusing. If [17] allows endogenous context variables, please detail the difference between [17] and this work.", "limitations": "Please see weaknesses.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This paper is well-motivated. In particular, I agree that it is important to investigate the case where the context variable is endogenous.\n\n2. This paper provides theoretical guarantee for their proposed method.\n\n3. This paper provides extensive experimental results to demonstrate the effectiveness of the proposed method.", "weaknesses": "1. The proposed method assumes that the context variable is both observed and known. In real-world applications, we may not know which observed variable is the context variable. Furthermore, the context variable might be a latent variable.\n\n2. This paper lacks readability. It entails too many definitions and notations. It might be better if the authors could summarize these things in Appendix for reference. Besides, the authors would better defer more details to appendix rather than present almost all results in the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for reviewing our paper and for acknowledging the strengths of our work.\n\nWe now address the weaknesses as follows: \n\n* **Context variable:** We agree with the reviewer that the assumptions we have made may not always reflect real-world use cases. However, as we have pointed out in the answer to reviewer 9Xqc, we believe that our work lays a first step towards a more general solution while considering important possible implications, such as the problems arising from shifting observational supports. Since regime detection algorithms exist, it is possible to discover $R$ rather than having a hard-coded specific choice. Our method is modular and can be combined with expert knowledge or any detection algorithm providing a context. In our work, we give assumptions to clearly define what would make a good choice for a context variable and consider that the detection part is out of scope for our work. We also believe that further extensions, such as to the case with latent context variables, are out of scope here, as we have detailed in the answer to reviewer 9Xqc. We wish for our work to further encourage the community to think about extensions.\n\n* **Readability:** We agree with the reviewer that our paper may still need improvement in terms of readability. While we have tried to reduce the notations and definitions in the main paper to a minimum, we will consider how to further improve this. Furthermore, we will introduce the changes that we have also mentioned in the answers for the other reviewers 9Xqc, DjMB, and 7t5U.\n\n    \n* **Question:**  We agree with the reviewer that this might be confusing. What we meant is: In the most general form of the formulation of context-specific graphs, [17] allows the context variable to be endogenous, see eq (3) and JCI assumption 0 in [17]. The core difference can be seen, e.g., from eq. (3): [17] describes the distribution over the union of the context-specific graphs, whereas we obtain more (also context-specific) information compared to this by analyzing the context-specific graphs. In the end, [17] proposes an algorithm for causal discovery from the pooled data, while we go beyond this information to further obtain context-specific causal graphs, using both the pooled and the context-specific tests. We will add this discussion to the main paper, as we believe that it is important to more clearly differentiate our work from [17].", "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": "", "extra_scores": {}}, {"review_id": "UYiSZUElgf", "reviewer": "Reviewer_7t5U", "summary": "The authors tackle the challenging causal discovery task, namely, causal discovery from the pooled dataset collected under different environments, where the environment (a.k.a., the context) can be dependent on the system (endogenous) variables (i.e., the variables whose causality we are interested in). The proposed algorithm is simple and intuitive: It employs a modified PC algorithm using context-dependent independence tests. Although I am not so familiar with this topic, overall, I have enjoyed reading the paper. However, there are several clarity issues, so I hope that my comments will be helpful for paper revision.", "questions": "NA", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Addressing the context that is dependent on system variables is an important problem.\n\n- Theoretical results seem sound (although I am non-expert of this field and did not follow the details).\n\n- Overall, the paper is well written (though there is much room for improvement).", "weaknesses": "Below I will enumerate several clarity issues.\n\nSection 1\n\n* While the first and the second paragraphs in Section 1 are very clear, the third one was a bit disappointing. The authors suddenly introduce several technical terms, such as context-specific models, single causal union graph, and cyclic union graph, etc, without definitions or explications. Readers cannot understand, for instance, which graph in Figure 1 is a « single causal union graph » because there is no description about it.\n\n* « as exemplified in Example 3.1 » Example 3.1 is very far away from Introduction. Thus, this paragraph is not well structured.\n\nSection 3\n\n* Relationship between the notion of intervention and the context indicator is unclear. I am not expert of causal discovery from multiple datasets like JCI algorithm, but I understand that the context is a more general notion than intervention: Some interventions can be represented using context variables, but not vice versa. Am I correct? For instance, how can non-stationary time series be formulated using context variables? Please elaborate the context variables more (in Appendix, if there is not enough space).\n\n* Related to the above, Example 3.1 can be regarded as soft intervention on $Y$? \n\n* Section 3.1 involving Example 3.2 is very hard to follow, although the example is intuitive. Lines 141-149 are very difficult to follow. Please introduce each variable (e.g., ice cream sale) together with notation (e.g., $Y$). Notation is inconsistent: Sometimes $R=0$, and sometimes $R=« ice »$. This paragraph should be clearer to clarify the significance of this work.\n\n* In Section 3.2, each graph is not clearly explained. For instance, is the mechanism graph « a causal graph in a standard sense »? If so, state it clearly. \n\n* Many notations are introduced without definition. Examples include $f_i|_{support P(Pa_i)}$, $\\mathcal{F}^M$, $P_M$, and $G_{R=r}$ (Section 4.1). This makes it hard to follow the paper. Please proofread the paper before submission.\n\nSection 4\n\n* I am not so familiar with the statistical test for context-specific independence, but could you elaborate the statistical procedure for the testing? Are you simply picking up only the subset of data instances with $R=r$? Is it statistically reliable? Is the test statistic identical with the usual independence testing?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort in reviewing our paper and for acknowledging the importance of the problem we are working on.\n\nWe address the mentioned weaknesses as follows:\n\n-   **Section 1:** We agree that the third paragraph should be thoroughly reworked. It fails to make the point it is supposed to due to excessive jargon and details. We propose the following changes: 1) shorten the paragraph into two paragraphs, one discussing the challenges of only looking into context-specific independencies and one highlighting the contribution of our method. 2) remove jargon unless necessary, and explain any introduced jargon in more detail. 3) change Figure 1 as described in the response to reviewer 9Xqc, introducing the definitions of context-specific graphs and union graphs. We will also move Example 3.1, possibly to the introduction, or avoid referring to it, depending on what is best for the reading flow.\n    \n-   **Section 3:** We agree with the reviewer that some confusion might arise from our definition of a context variable. In our case, the choice of context variable is primarily restricted by the regime-sufficiency assumptions. However, the context variable can be selected from or introduced into the dataset by expert knowledge or any regime detection algorithm, as discussed in the response to reviewers 9Xqc and J2yL. We focus specifically on understanding under which assumptions on the context variable we can obtain reliable results and how these results can be interpreted.\n    \n    If we understand correctly, the reviewer is considering context variables to be something like Pearl's $\\mathcal{F}$-variables. These $\\mathcal{F}$-variables are functional variables (taking values in function spaces) that allow writing any (hard or soft) interventions implicitly: If $f_Y(x)$ is the mechanism at $x$, depending on parents $x$ (possibly multivariate), one can add a parent $\\mathcal{F}_Y$ taking a function (e.g., the original $f_Y$) as a value and replace the mechanism at $Y$ by the evaluation map eval($f, x$) $:= f(x)$. Since $\\mathcal{F}_Y$ can take a value for $f$ that represents an intervention (e.g., a constant function for a hard intervention), this generalizes interventions. Example 3.1 can indeed be regarded as a kind of soft intervention on $Y$.\n    \n    Context variables are an orthogonal concept: Given multiple distinct datasets over the same set of variables, the context injects information about the specific associations in each dataset to the analysis by appending a pseudo-variable to the dataset. The value of this pseudo-variable typically is a dataset index. This context could be functional, but in general, both contexts and functional nodes coexist independently of each other.\n    \n    We are interested in context-specific changes. A possible viewpoint on the strong regime-sufficiency assumption (cf. Example 3.1) is that the context variable behaves like a functional node that implements a soft intervention removing some of the parents' effects on certain variables. In comparison to JCI [17], our method reveals the internal structure of some functional nodes: Beyond discovering the children of the functional node, it additionally uncovers the graphical changes induced by the implemented soft intervention.\n    \n    Generally, phenomena like drifts can be modeled using (possibly continuous) contexts but may not have a simple interventional interpretation. Temporal regimes were an important motivation for our study of context-specific behavior. To make the connection to non-stationary time series, these can be formulated using context variables. For the context to be categorical (which we and others assume), the non-stationarity cannot be a drift, etc., but must be driven by a regime change, i.e., there must be temporal regions sharing a model or context. By finding the contexts in which the time series is stationary and describing the causal relationships for those stationary parts of the time series, we can describe the non-stationary system as a multi-context system.\n    \n    We will introduce these discussions and clarify the differences between other types of special variables, such as $\\mathcal{F}$-variables, in the Appendix.\n    \n-   **Section 4:** Our method combines testing on the pooled and context-specific data. Context-specific independence (CSI) is indeed simply tested on the samples satisfying $R=r$. Since $R$ is categorical and $P(R=r)>0$ by assumption, $P_r := P(X,Y,Z|R=r)$ is a well-defined distribution. Therefore, testing conditional independencies on $P_r$ is well-defined and no different from any other independence test (albeit assumptions like linearity need some thought, see §B.12). The difficulty lies in the interpretation of the result, as fixing $R$ can lead to selection bias. Overcoming this problem is one of the main contributions of our paper and method.\n    \n    There is a difference between testing links involving $R$ and not involving $R$ ($R$ is categorical) as discussed in §B.12. Beyond this, a further difference between testing on the pooled and context-specific data is the number of samples for each test. This approach is as reliable as the finite sample properties of each test being used. Lastly, the more general problem of multiple testing, from which constraint-based causal discovery methods generally suffer, can also impact reliability. For this reason, we consider it advantageous that our approach reduces the number of tests.", "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": "", "extra_scores": {}}]

Author rebuttal:
## General Response to the Reviewers

We thank all reviewers for their valuable comments, and we are happy that they acknowledge the importance of our work and the value of our results. We agree with the reviewers that the presentation of the paper can be improved, and we summarize the main changes we aim to add to the final version of the paper as follows. Further questions are answered in the individual rebuttals.

* **Introduction:** We will improve the introduction by modifying Figure 1 to a figure which clearly explains the setup where a context variable is endogeneous, and will move the discussion around the current Figure 1 to Section 4. We will then move Example 3.1. to the introduction to better illustrate our goals. We will considerably improve the third paragraph of the introduction by removing unnecessary details and jargon, and rather explain better how our work relates to methods describing context-specific independencies (CSI), and how our assumptions allow us to give an interpretation in terms of structural causal models (SCMs) to the CSIs. 


* **Graphical objects:** We agree that the graphical objects may be hard to understand at first sight in the current form of the paper. We therefore propose to add the following table (formatted as best as possible) which underlines the differences and connections between the different graphical objects: 
	
	|  | Observable... | ...graphs... | ...$G[M,P]$ |
	| :----------------: | :------: | :----: | :----: |
	| Symbol |   $G^{\\text{descr}}_{R=r}$ |  $G^{\\text{phys}}_{R=r}$ |  $G^{\\text{union}}$ |
	| Name |   descriptive | physical | union ('standard') |
	| Model $M$    |  $M$ or $M_{\\text{do}}$ | $M_{\\text{do}}$ | $M$ |
	| Observational Support $P$ |  $P_M(...,R=r)$ | $P_M(...)$ | $P_M(...)$ |
	| Captured Information | independence-structure | altered mechanisms | union mechanisms |
	| Context-Specific ($r$-dep.) | yes | yes | no |
	| Used here primarily for | discovery | proofs | relation to literature |
	| Node Sets | system $\\cup \\{R\\}$ | system $\\cup \\{R\\}$ | system $\\cup \\{R\\}$ |
	| Edge Sets | active in context $r$ $\\subset$ | present in context $r$ $\\subset$ | in any context |

	We will also combine the graphical objects and the discovery goals sections for better reading flow. 

* **Overall readability:** We will revise notation and try to further simplify it. We will better explain the assumptions. However, we believe that the exact definitions are better left to the Appendix. We will fix all discovered typos, including the typos in Algorithm 1.  

* **Context variable:** We will revise our definition of a context variable to make it clearer that our method is modular and can be combined with any anomaly or regime-detection method. This change also makes it easier to explain how the current setup, where the context variable is measured and known, is plausible also for real-world scenarios.

## Redraft of third paragraph of introduction
The third paragraph of the introduction did not illustrate well what we actually wanted to say, which is (the following is an early redraft and has to be fit together with the remainder of the introduction, so is likely subject to change):

Multiple context-specific graphs can contain more qualitative
information than a single union graph as illustrated below:

**Example 3.1:** Given a binary context indicator variable $R$ and a *multivariate* mechanism of the form $ f_Y(X,R,\eta_Y) = \mathbb{1}(R) g(X) + \eta_Y,$ the dependence $X \rightarrow Y$ is present in the context $R=1$, but absent for $R=0$. This entails a context-specific independence (CSI) $X \perp Y | R=0$.

As indicated in the example, such additional information can be captured via context-specific independence (CSI). Graphical independence models describing the CSI structure of a dataset, for example, LDAGs, have been studied before [22]. However, a causal analysis, i.e., understanding interventional properties of the context-specific model, requires knowledge about the causal model properties.
In the single-context case, under the faithfulness assumption, knowledge about the causal properties of models is directly connected to the independence structure. As will be explored in detail in §3.1, this simple model to independence correspondence cannot generally hold in the multi-context case. Thus, an important open problem for the causal analysis of multi-context systems is the connection of CSI structure to the underlying causal model.

We provide a connection between the CSI structure and the underlying causal model and specify assumptions under which an efficiently computable subset of CSI and independencies on the pooled data together can be given an interpretation in terms of structural causal model (SCM) properties. The obtained context-specific graphs are of interest due to several desirable properties. For instance, context-specific modeling can avoid spurious edges that arise from cycles in the union graph, as shown in Figure 1.
Furthermore, CSI testing poses multiple finite-sample challenges: It dramatically increases the search space of independence testing. Additionally, CSIs are only tested on a subset of samples, thereby increasing the per-test error rate. Our approach, which requires the framework connecting CSI to causal properties, adaptively decides whether a specific test can be run on the pooled data, or must run on a subset of samples associated with a specific context. It executes only one of both tests and uses as many samples as possible, thereby improving finite-sample performance.

Meta-review: The paper addresses the challenge of causal discovery in scenarios where causal relationships vary across different contexts, particularly when the context variable is endogenous, meaning it depends on other variables within the system. The authors propose a modified version of the PC algorithm that adaptively chooses between performing conditional independence tests on either pooled data or context-specific data, depending on the context. This approach is designed to avoid the selection bias that can occur when using traditional methods in the presence of endogenous context variables. The proposed algorithm is theoretically grounded, with proofs of its completeness under certain assumptions, and its effectiveness is demonstrated through empirical studies.

The reviewers are unanimously in favor of accepting the paper, though their support is somewhat tentative. There are several issues with clarity (definitions, assumptions, introduction, etc.), which I believe the authors can address during the revision. However, I am also a bit concerned about whether it may require another round of review, as it could involve a nontrivial amount of changes. One of several concerns is about the known context indicator. Given that this paper is the first to address an endogenous context variable, it is reasonable to assume a known context indicator. In the rebuttal, the authors claimed that a regime detection algorithm can be used to identify a context indicator, but no reference or clear explanation is provided on how this could be applied. If it is feasible, adding experiments with a learned context indicator would significantly strengthen the paper.

Given that the paper is well-motivated and the contribution is novel enough, I lean towards recommending the acceptance of the paper. The authors are strongly encouraged to revise the paper for better readability and also to add a discussion on learning a context indicator.
Decision: Accept (poster)