Causal discovery with endogenous context variables

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.

Strengths

- Addressing the context that is dependent on system variables is an important problem. - Theoretical results seem sound (although I am non-expert of this field and did not follow the details). - Overall, the paper is well written (though there is much room for improvement).

Weaknesses

Below I will enumerate several clarity issues. Section 1 * 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. * « as exemplified in Example 3.1 » Example 3.1 is very far away from Introduction. Thus, this paragraph is not well structured. Section 3 * 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). * Related to the above, Example 3.1 can be regarded as soft intervention on $Y$? * 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. * 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. * 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. Section 4 * 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?

Questions

NA

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

2

Limitations

NA

Summary

This paper proposes a constraint-based algorithm for context-specific causal discovery, which accommodates endogenous context variables.

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. 2. This paper provides theoretical guarantee for their proposed method. 3. 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. 2. 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.

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.

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

Please see weaknesses.

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)]$. The 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.

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. While 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. The 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. (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$? (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.

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}$"?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes - the authors make good effort to document the challenges to their approach and motivate potential future work.

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.

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

Questions

Please see above.

Rating

5

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

Please see above.

Response to authors

Thanks for your hard work. I have read your rebuttal and I'm now sure that I have no misunderstanding about this paper. I agree that this paper has provided some novel insights. But considering that this work is not the first one investigating the problem of causal discovery with endogenous context variables and this work remains at a relatively elementary stage (both detection and latent context variables are out of your scope), I decide to maintain my borderline accept score.