Causal discovery with endogenous context variables

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.

We address the mentioned weaknesses as follows:

• 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.

• 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.

  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$.

  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.

  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.

  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.

  We will introduce these discussions and clarify the differences between other types of special variables, such as $\mathcal{F}$-variables, in the Appendix.

• 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.

  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.

Thank you for your response.

I roughly understand what the authors mean, but still, I cannot clearly understand the definition of context variables and related graphical concepts. Since they are strongly relevant to the study, their poor clarity will reduce the impact of this work. For this reason, I will maintain my overall rating, and I hope that the authors can clearly explain these notions more.

We thank the reviewer for reviewing our paper and for acknowledging the strengths of our work.

We now address the weaknesses as follows:

• 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.

• 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.

• 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].

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:

• 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.

• 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.

  The 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.

• 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.

  Excluding 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.

  An 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.

  The 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.

• 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.

• 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.

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. We address the weaknesses as follows:

• 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.

• 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.

• 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:

  • One has to understand how the ideas underlying the graphical objects we are currently using must be adapted.
  • 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.
  • 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.

• 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.

• 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:

  False 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.

  False 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.

• Marginal improvement over baseline: As we are not sure which baseline the reviewer refers to, we discuss:

  (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.

  (b) Comparison to existing (pooled) methods: Compared to algorithms not using CSI, we provide additional information in the form of context-specific causal graphs.