When Selection Meets Intervention: Additional Complexities in Causal Discovery

We are encouraged that the reviewer recognizes our work as "studying a relevant and interesting problem - both mathematically and philosophically".

We would like to highlight that our contribution goes beyond solving a specific problem; we identify a new problem setting and establish a general framework to understand this setting, namely, interventional studies under selection bias.

In real-world scenarios, selection indeed always meets intervention, as real experiments are typically designed with specific scopes and objectives (e.g., participants in a drug trial are usually patients of the relevant disease).

To this end, we hope this work provides a foundation for various potential practical extensions, such as incorporating latent variables for causal discovery and deriving causal inference results.

We want to thank the reviewer again for all the valuable feedback.

We appreciate the reviewer's constructive comments and helpful feedback. Please see below for our response.

(Q1) The reviewer identifies the biggest weakness as presentation in our original submission.

R: We are grateful for the reviewer's comments. In response to your feedback, we have carefully rewritten our theoretical sections in the updated manuscript. While the technical results remain unchanged, we have significantly improved the way we deliver these results.

Key improvements are summarized below:

• Optimal model first: We directly give the optimal model, deferring its detailed development to the appendix, to improve readability.
  • In our original submission, we presented our theory development sequentially: starting with an intuitive model, then demonstrating its flaws, and finally making corrections to reach the optimal model. While this approach was helpful for understanding the technical progression, it may have impacted readability.
• Graph examples and explanations: We provide each definition and theorem with graph examples and explanations afterwards, so that readers can try to apply the graphical criteria and understand them more easily.
• Context for lemmas: We introduce each lemma alongside the specific question it aims to answer, for logical clarity.
• Running examples: We use two running examples—the clinical and the pest control one—throughout, to illustrate all main results.
• Concepts introduction: We introduce all technical concepts, such as maximal ancestral graphs (MAGs), before they are used.

We appreciate the reviewer's time devoted. We hope you find the updated manuscript less of a painful read this time around.

We sincerely thank the reviewer for your recgnition and your valuable feedback that helps improving the presentation of our submission.

We are encouraged that the reviewer recognizes our work as tackling "an important yet often overlooked" problem, and that "the setting is general".

We would like to highlight that our contribution goes beyond solving a specific problem; we identify a new problem setting and establish a general framework to understand this setting, namely, interventional studies under selection bias.

In real-world scenarios, selection indeed always meets intervention, as real experiments are typically designed with specific scopes and objectives (e.g., participants in a drug trial are usually patients of the relevant disease).

To this end, we hope this work provides a foundation for various potential practical extensions, such as incorporating latent variables for causal discovery and deriving causal inference results.

We want to thank the reviewer again for all the valuable feedback.

(Q5) The reviewer asks for more elaboration on the real-world experiments. Specifically,

• (Q5.1) "For the gene application, can you provide more comprehensive analysis of the result?"

  A: Thank you for your valuable comments. We evaluate the gene regulation networks (GRNs) of 24 previous reported essential regulatory genes encoding different transcription factors (TFs) using a single-cell perturbation data, i.e., sciPlex2.

  • In the sciPlex2 dataset, the A549 cells, a human lung adenocarcinoma cell line, are either exposed to one of the four different transcription modulators, including dexamethasone, nutlin-3a, BMS-345541, and suberoylanilide hydroxamic acid (SAHA), or simply treated with dimethylsulfoxide vehicle as control.
  • We discoved some regulatory relationships like RELA $\rightarrow$ RUNX1 and JUNB $\rightarrow$ MAFF, which has been validated by some previous studies.
  • For example, TF RELA has been previously implicated as a RUNX3 transcription regulator, and Maf family was upregulated by JunB, despite the extensive co-regulation between these two genes.
  • Besides, our algorithm suggests the link between transcription factor ETS2 or RUNX1 and the activation of gene STAT3 may possibly reflect the true gene regulation process but also encounter the possibility of selection bias introduced when conditioning on a particular disease cell line.
  • The results are supported by previous studies since it is reported Runx1 and Stat3 synergistically driving stem cell development in epithelial tissues trough Runx1/Stat3 signalling network, while TF Ets2 together with p-STAT3 activation induce cathepsins K and B expression in human rheumatoid arthritis synovial fibroblasts (RASFs).

• (Q5.2) "For the education dataset, can you explain why the pre-intervention selection bias is a potential issue?"

  A: Thank you for this insightful question. For educational datasets, not using our method might lead to doubts about the causal effect of incentives on improving female students' performance. This is due to potential selection bias, as there exists a causal graph where the probability of receiving an intervention ($X_1$), the potential for improved performance ($X_2$), being female ($X_3$), and being an admitted female college student ($X_4$) are all interrelated, where graphically $X_1$, $X_2$, $X_3$ jointly point to $X_4$. Then,

  • When we control for $X_3$ (i.e., control for $X_4$) during the analysis, it is akin to pre-selecting by gender before assigning different interventions. This may create spurious associations between $X_1$ and $X_2$.
  • However, by using our method, we can clearly demonstrate that this association reflects the genuine stratified causal effect across genders, rather than being merely the result of selection bias.
  • Therefore, our model provides a powerful tool for reliably distinguishing true causal relationships from selection bias (up to their equivalence class), enabling us to better address the challenges present in real-world data.
  • To demonstrate the results more clearly, we have updated the data analysis results and added a table (Table 1) in the appendix explaining the corresponding variables.

(Q6) Minor comments about clarity.

A: Thank you for your careful reading. We have corrected all the noted typos. We have also carefully rewritten our technical sections in our updated manuscript.

In specific response to your comments, we introduce all technical concepts, such as maximal ancestral graphs (MAGs), before they are used.

We hope you find the updated manuscript easier to follow.

(Q3) The reviewer wonders the computational cost of the algorithm.

A: Thank you for this insightful question. The computational cost of our algorithm, CDIS, is similar to standard constraint-based algorithms like PC and FCI, as it mainly involves conducting conditional independence (CI) tests among observed variables to estimate adjacencies. This has been mentioned in the updated manuscript. Specifically,

• (Q3.1) What is the exact time complexity?

  A: Like PC, our algorithm has a worst-case complexity exponential in the number of observed variables (the $D$ in our manuscript). However, if the underlying graph is sparse—a common and reasonable assumption—the runtime becomes polynomial [1].

• (Q3.2) But the interventional twin graph is more complex than a simple DAG and involves additional nodes?

  A: This is because the true data generating mechanism is indeed more complex than and cannot reduce to a simple augmented DAG, as shown in Section 2 (Motivations). Regarding complexity of the discovery procedure, note that the above mentioned complexity of the twin graph model only impacts how we interpret the CI relations from data, not the number of CI tests required, as we can only test observed variables.

• For empirical evaluation, we have also compared the runtime (in seconds) of our algorithm with others (even though they are theoretically incorrect under selection). Results are shown as follows:

  Method	10 nodes	15 nodes	20 nodes
  CDIS	0.4±0.24	1.0±0.32	2.0±0.0
  IGSP	0.6±0.24	0.8±0.2	1.2±0.2
  UT-IGSP	0.6±0.24	0.6±0.24	1.4±0.24
  JCI-GSP	0.4±0.24	0.8±0.2	1.4±0.24

  We observe that these algorithms indeed operate on a similar timescale.

(Q4) The reviewer asks for more details about the simulation experiments. Specifically,

• (Q4.1) "Can you report the proportion of true causal edges estimated as directed edges by the algorithm?"

  A: Thank to your suggestion, we conducted experiments on varying number of nodes with 1,000 samples, with all other configurations the same as Section 5.1. We report the F1 score, precision, and recall with respect to the true direct edges in the equivalence class. The results are provided in tables below, as well as Figure 12 in the updated manuscript.

  #Nodes	10			15			20
  Method	F1	Precision	Recall	F1	Precision	Recall	F1	Precision	Recall
  CDIS	0.8±0.04	0.79±0.06	0.82±0.04	0.77±0.04	0.71±0.05	0.86±0.05	0.75±0.05	0.74±0.09	0.79±0.06
  IGSP	0.63±0.12	0.56±0.12	0.74±0.10	0.64±0.03	0.5±0.03	0.88±0.04	0.5±0.05	0.37±0.05	0.76±0.05
  UT-IGSP	0.71±0.05	0.64±0.07	0.8±0.03	0.68±0.05	0.54±0.04	0.9±0.05	0.56±0.07	0.42±0.07	0.83±0.03
  JCI-GSP	0.32±0.06	0.24±0.05	0.5±0.08	0.4±0.05	0.28±0.04	0.7±0.07	0.31±0.04	0.2±0.03	0.68±0.04

  We see that indeed, our algorithm empirically achieves both high precision and recall, verifying its guaranteed soundness and conjectured completeness.

• (Q4.2) "A comparison of the output graphs with the ground truth."

  A: We are especially grateful for this valuable comment. Example graphs indeed help illustrate the complexity of equivalence classes under selection, and clearly shows how CDIS differs from other algorithms.

  We provide these comparisons on example graphs in Figure 14 in the updated manuscript. We see that CDIS outputs are sparser and closer to the ground truth, as it avoids misinterpreting spurious dependencies from selection bias as causation.

We sincerely appreciate the reviewer's encouragement and insightful feedback. Please see below for our response.

(Q1) The reviewer wonders the main challenges that affect the precision and completeness of the algorithm.

A: Thank you for the question. We summarize the challenges as follows:

• Empirical challenges: Conditional independence (CI) tests may not always be accurate, especially with insufficient samples. This leads to potential error propagation in orientation rules. More robust empirical methods to handle either CI tests, or conflicts in orientations, are to be developed.
• Theoretical Challenges:
  • Unmeasured confounders. We list it here merely because in this specific work we assume causal sufficiency. However, it is not really challenging. Specifically,
    • Similar to how the augmented DAG framework offers a unified way to understand interventional data without selection bias, our interventional twin graph framework offers a unified way to understand interventional data with selection bias.
    • Then, various extensions can be incorporated into this framework, just as they are in the augmented DAG paradigm (discussed in Section 2.1 in our manuscript). Latent variables is one of such extensions.
    • For latent variables, the technical route is straightforward: one may modify the specific graphical criteria of constructing maximal ancestral graphs (MAGs) (Lemmas 4 to 6 in our updated manuscript) and adjust the orientation rules and edge interpretations in Algorithm 1. While details may differ, the core concept remains unchanged.
    • In this work, we focus solely on selection bias, as we aim to thoroughly characterize its own complexities, highlight its impact on interventional studies, and maintain clarity in our presentation.
    • One philosophically interesting observation, as discussed in Section 2.3, is that latent variables are easier to incorporate than selection bias for interventional studies. This is because, when selection bias is absent, the two forms of intervention (on existing individuals vs. from scratch) yield the same interventional data at the distribution level, even with latent variables. Selection bias, however, behaves quite differently.
  • Completeness guarantee. Our proposed algorithm, CDIS, is provably sound. However, as CDIS can be viewed as FCI with background knowledge, no completeness result (i.e., whether it identifies all the invariant relations in the equivalence class) currently exists, and proving it is technically challenging, as is discussed after Theorem 3 in the updated manuscript. This is not a significant concern though, as:
    • We conjecture that CDIS is fully complete, that is, it produces the maximally informative output about the Markov equivalence class (defined in Theorem 2). This conjecture is supported by brutal search on ~50,000 (DAG, targets) pairs with up to 15 vertices. For the PAG that CDIS outputs on each pair, we enumerate all the MAGs consistent with it, and verify if there exist targets so that they are Markov equivalent to the original pair. So far we found no counterexamples.
    • CDIS is guaranteed to be complete on pure observational data, since it is built on the result that FCI gives on pure observational data, which is guaranteed to be maximal informative with respect to pure observational data. Furthermore, CDIS incorporates additional information from interventional data, making its result even more informative than that.
    • Evaluation from simulation experiments suggests that our algorithm empirically achieves both high precision and recall. The detailed results are shown in our response to your question (Q4) below.

Despite these challenges, we would like to note that they are common to many causal discovery algorithms. Our method provides a general enough framework to understand interventional data under selection. Experiments also show it effectively identifies true causal and selection relations.

(Q2) The reviewer wonders how the selection bias detected through diagnostics can aid causal discovery.

A: We appreciate this constructive question. The answer is, yes—it can be easily integrated into our algorithm, CDIS, as background knowledge. Like other types of background knowledge (e.g., direct or ancestral causal relations), it can be input into CDIS and aligns seamlessly with our design. This is because CDIS functions exactly as FCI with background knowledge (where our graphical criteria for interventional twin graphs helps in the refining step).

As you see, CDIS can be improved with additional constraints, prior knowledge, or extensions to allowing for hidden confounders. We do not focus on those variants of CDIS in this work, since our major contribution here lies in fully characterizing the data under selection bias itself.

We sincerely thank you for your constructive feedback, the time you have dedicated, and your recognition of our work. Thank you.

We sincerely appreciate the reviewer's encouragement and insightful feedback. Please see below for our response.

(Q1) The reviewer suggests a high-level explanation for the Markov properties.

A: Thank you for your suggestion. In response, we have carefully rewritten our technical sections in the updated manuscript. We provide each definition and theorem with graph examples and explanations afterwards. All examples are based on the two running examples—the clinical and pest control ones—throughout, to illustrate the main results.

For more details, please kindly refer to the updated manuscript.

(Q2) The reviewer wonders the computational cost of the algorithm.

A: Thank you for this insightful question. The computational cost of our algorithm, CDIS, is similar to standard constraint-based algorithms like PC and FCI, as it mainly involves conducting conditional independence (CI) tests among observed variables to estimate adjacencies. This has been mentioned in the updated manuscript. Specifically,

• (Q2.1) What is the exact time complexity?

  A: Like PC, our algorithm has a worst-case complexity exponential in the number of observed variables (the $D$ in our manuscript). However, if the underlying graph is sparse—a common and reasonable assumption—the runtime becomes polynomial [1].

• (Q2.2) But the interventional twin graph is more complex than a simple DAG and involves additional nodes?

  A: This is because the true data generating mechanism is indeed more complex than and cannot reduce to a simple augmented DAG, as shown in Section 2 (Motivations). Regarding complexity of the discovery procedure, note that the above mentioned complexity of the twin graph model only impacts how we interpret the CI relations from data, not the number of CI tests required, as we can only test observed variables.

• For empirical evaluation, we have also compared the runtime (in seconds) of our algorithm with others (even though they are theoretically incorrect under selection). Results are shown as follows:

  Method	10 nodes	15 nodes	20 nodes
  CDIS	0.4±0.24	1.0±0.32	2.0±0.0
  IGSP	0.6±0.24	0.8±0.2	1.2±0.2
  UT-IGSP	0.6±0.24	0.6±0.24	1.4±0.24
  JCI-GSP	0.4±0.24	0.8±0.2	1.4±0.24

  We observe that these algorithms indeed operate on a similar timescale.

(Q3) The reviewer has concerns about the identifiability guarantees of our algorithm.

A: We thank the reviewer for highlighting this, and would like to note that we do have provided identifiability guarantees in our work (Theorem 2 and Theorem 3), as detailed below:

• Theorem 2 provides the graphical criteria for determining whether two DAGs are Markov equivalent under two collections of interventions, offering an upper bound on identifiability.
• Theorem 3 demonstrates the soundness of the proposed CDIS algorithm, showing that it reliably identifies the true causal and selection relations. This guarantee is general, without requiring any additional structural or parametric assumptions.
• After Theorem 3, we also discuss the CDIS's completeness, i.e., whether it identifies all the invariant relations in the equivalence class. Brutal search strongly supports our conjecture of its completeness. However, proving this remains technically challenging, as outlined in the updated manuscript.

We hope this addresses your concerns about identifiability guarantees. If not, please kindly let us know; we hope for the opportunity to discuss them further with you.

We are encouraged that the reviewer recognizes our work as tackling "an under-explored but crucial issue in causal discovery".

We would like to highlight that our contribution goes beyond solving a specific problem; we identify a new problem setting and establish a general framework to understand this setting, namely, interventional studies under selection bias.

In real-world scenarios, selection indeed always meets intervention, as real experiments are typically designed with specific scopes and objectives (e.g., participants in a drug trial are usually patients of the relevant disease).

To this end, we hope this work provides a foundation for various potential practical extensions, such as incorporating latent variables for causal discovery and deriving causal inference results.

We want to thank the reviewer again for all the valuable feedback.

[1] Kalisch, Markus, and Peter Bühlman. "Estimating high-dimensional directed acyclic graphs with the PC-algorithm." (2007).

(Q4) The reviewer wonders how the proposed algorithm performs empirically compared to existing methods in scenarios without selection bias.

A: Thank you for this constructive comment. We conducted experiments on datasets without selection bias. It is worth noting that we directly applied the original CDIS algorithm to the data, without making use of the prior knowledge about the absence of selection bias, as otherwise the algorithm just reduces to other typical methods based on augmented graphs.

This makes the choice of metrics particularly relevant. Recall that in our clinical example, a DAG $2\rightarrow 1$ without selection is unidentifiable to another DAG $1 \rightarrow S \leftarrow 2$ with selection, under the intervention on $X_1$. This shows that even without selection bias, when the prior knowledge of its absence is unknown, still not all edges in a DAG are identifiable.

Hence, in what follows we report results using both metrics based on direct edges in the equivalence class (assuming no prior knowledge of selection absence), and all direct edges in the original DAG.

The experiments were performed on varying numbers of nodes with 1,000 samples, with all other configurations the same as Section 5.1. We report the F1 score, precision, and recall under both metrics. The results are provided in the tables below and in Figure 13 in the updated manuscript.

• Using equivalence class metric: | #Nodes | 10 | | | 15 | | | 20 | | | |----------|----------------------|-------------|-------------|--------------------|-------------|-------------|---------------------|-------------|-------------| | Method | F1 | Precision | Recall | F1 | Precision | Recall | F1 | Precision | Recall | | CDIS | 0.73±0.09 | 0.73±0.08 | 0.74±0.11 | 0.73±0.04 | 0.72±0.08 | 0.78±0.04 | 0.79±0.03 | 0.72±0.05 | 0.88±0.02 | | IGSP | 0.6±0.06 | 0.52±0.05 | 0.72±0.06 | 0.63±0.07 | 0.52±0.07 | 0.82±0.08 | 0.47±0.02 | 0.34±0.02 | 0.74±0.03 | | UT-IGSP | 0.75±0.05 | 0.68±0.06 | 0.84±0.04 | 0.61±0.06 | 0.51±0.06 | 0.79±0.07 | 0.51±0.04 | 0.37±0.03 | 0.79±0.05 | | JCI-GSP | 0.39±0.06 | 0.3±0.05 | 0.58±0.05 | 0.39±0.04 | 0.27±0.04 | 0.69±0.03 | 0.25±0.03 | 0.16±0.02 | 0.55±0.03 |

• Using the original DAG metric: | #Nodes | 10 | | | 15 | | | 20 | | | |----------|----------------------|-------------|-------------|--------------------|-------------|-------------|---------------------|-------------|-------------| | Method | F1 | Precision | Recall | F1 | Precision | Recall | F1 | Precision | Recall | | CDIS | 0.73±0.09 | 0.73±0.08 | 0.74±0.11 | 0.71±0.04 | 0.73±0.08 | 0.71±0.05 | 0.78±0.04 | 0.76±0.04 | 0.81±0.06 | | IGSP | 0.6±0.06 | 0.52±0.05 | 0.72±0.06 | 0.63±0.07 | 0.54±0.07 | 0.77±0.07 | 0.46±0.02 | 0.35±0.02 | 0.66±0.03 | | UT-IGSP | 0.75±0.05 | 0.68±0.06 | 0.84±0.04 | 0.65±0.05 | 0.56±0.05 | 0.79±0.06 | 0.53±0.05 | 0.41±0.04 | 0.75±0.04 | | JCI-GSP | 0.39±0.06 | 0.3±0.05 | 0.58±0.05 | 0.41±0.04 | 0.3±0.04 | 0.68±0.04 | 0.27±0.02 | 0.18±0.02 | 0.55±0.02 |

Directed edges in the equivalence class form a subset of those in the DAG. We anticipated that CDIS would perform similarly or better using the equivalence class metric but worse with the original DAG metric, as it lacks the prior assumptions of the absence of selection bias, while other methods do.

Surprisingly, the results show that CDIS performs slightly better on both metrics. A possible explanation is that we simulate 10 interventional datasets, which provide sufficient information to identify more edges in the equivalence class. Motivation on this is shown in Example 4 in the updated manuscript.

(Q5) Minor typos.

A: Thank you for your careful reading. We have corrected all the noted typos in the updated manuscript.

Thank you for the detailed response and for providing the additional experimental results. All my concerns have been addressed, and I have updated my score accordingly.

We sincerely appreciate your thoughtful feedback and recognition of our work. Thank you for your time.

We are encouraged that the reviewer recognizes our work as "putting forward a very general solution to the problem".

We would like to highlight that our contribution goes beyond solving a specific problem; we identify a new problem setting and establish a general framework to understand this setting, namely, interventional studies under selection bias.

In real-world scenarios, selection indeed always meets intervention, as real experiments are typically designed with specific scopes and objectives (e.g., participants in a drug trial are usually patients of the relevant disease).

To this end, we hope this work provides a foundation for various potential practical extensions, such as incorporating latent variables for causal discovery and deriving causal inference results.

We want to thank the reviewer again for all the valuable feedback.

[1] Spirtes, Peter L., Christopher Meek, and Thomas S. Richardson. "Causal inference in the presence of latent variables and selection bias." (1999).

[2] Ali, Ayesha R., et al. "Towards characterizing Markov equivalence classes for directed acyclic graphs with latent variables." (2005).

[3] Zhang, Jiji. "On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias." (2008).

[4] Meek, Christopher. "Causal inference and causal explanation with background knowledge." (1999).

[5] Andrews, Bryan, Peter Spirtes, and Gregory F. Cooper. "On the completeness of causal discovery in the presence of latent confounding with tiered background knowledge." (2020).

[6] Pearl, Judea. "On the testability of causal models with latent and instrumental variables." (1995).

[7] Richardson, Thomas S. "Discovering cyclic causal structure." (1996).

4. Completeness evaluation from simulation experiments.

   • We especially thank the reviewer for pointing out that completeness can be evaluated with access to ground truth. Although not all directed edges in the truth DAG are identifiable, the equivalence class can at least be brutally searched.

   • We conducted experiments on varying number of nodes with 1,000 samples, with all other configurations the same as Section 5.1. We report the F1 score, precision, and recall of the direct edges in the equivalence class. The results are provided in tables below, as well as Figure 12 in the updated manuscript.

     #Nodes	10			15			20
     Method	F1	Precision	Recall	F1	Precision	Recall	F1	Precision	Recall
     CDIS	0.8±0.04	0.79±0.06	0.82±0.04	0.77±0.04	0.71±0.05	0.86±0.05	0.75±0.05	0.74±0.09	0.79±0.06
     IGSP	0.63±0.12	0.56±0.12	0.74±0.10	0.64±0.03	0.5±0.03	0.88±0.04	0.5±0.05	0.37±0.05	0.76±0.05
     UT-IGSP	0.71±0.05	0.64±0.07	0.8±0.03	0.68±0.05	0.54±0.04	0.9±0.05	0.56±0.07	0.42±0.07	0.83±0.03
     JCI-GSP	0.32±0.06	0.24±0.05	0.5±0.08	0.4±0.05	0.28±0.04	0.7±0.07	0.31±0.04	0.2±0.03	0.68±0.04

   • We see that indeed, our algorithm empirically achieves both high precision and recall, supporting its guaranteed soundness and conjectured completeness.

(Q3) The reviewer raises concerns about the completeness guarantee of our algorithm, CDIS.

A: We appreciate the reviewer for these constructive comments. In what follows, we address: (1) to which extent CDIS is complete, (2) how and why proving full completeness is technically challenging, (3) how a sound but not fully complete algorithm can also be useful, and (4) completeness evaluation from simulation experiments.

0. Before proceeding, we introduce the following terms (for more details, please kindly refer to Section 3.3 and Appendix. A of our updated manuscript):

   • Maximal ancestral graph (MAG): a graph to represent conditional independence relations among observed variables in the presence of latent variables and selection bias.
   • Partial ancestral graph (PAG): a graph to represent an equivalence class of MAGs, just like how a CPDAG represents an equivalence class of DAGs.
   • Fast causal inference (FCI) algorithm: an algorithm that recursively applies the orientation rules to a PAG until no further orientations can be made. This is similar to how the PC algorithm uses Meek rules to orient edges beyond v-structures.

1. To which extent CDIS is complete.

   • We conjecture that CDIS is fully complete, that is, it produces the maximally informative output about the Markov equivalence class (defined in Theorem 2). This conjecture is supported by brutal search on ~50,000 (DAG, targets) pairs with up to 15 vertices. For the PAG that CDIS outputs on each pair, we enumerate all the MAGs consistent with it, and verify if there exist targets so that they are Markov equivalent to the original pair. So far we found no counterexamples.
   • CDIS is guaranteed to be complete on pure observational data, since it is built on the result that FCI gives on pure observational data, which is guaranteed to be maximal informative with respect to pure observational data. Furthermore, CDIS incorporates additional information from interventional data, making its result even more informative than that.

2. How and why proving full completeness is technically challenging.

   • This challenge is also reflected in the completeness establishment of FCI itself. Proving completeness of orientation rules can be challenging, as it requires showing that all the possible graphical patterns are enumerated. For instance, though FCI has been widely adopted since its debut in 1999 [1], its completeness result (without background knowledge) was not established until 2005 (partially [2]) and 2008 (fully [3]).
   • Our algorithm, CDIS, can be viewed as FCI with background knowledge. To determine edges on the original PAG from PAGs obtained from interventional data, the refining step in CDIS relies on our graphical patterns on interventional twin graphs (Lemma 6) as background knowledge.
   • Why FCI with background knowledge is not complete. For illustration, consider the analogous case of the PC algorithm with Meek rules, which orient more direct edges starting from those of v-structures. Without background knowledge, Meek's R1-R3 rules are complete, i.e., can reach the correct CPDAG. However, adding background knowledge requires an additional R4 rule to ensure completeness [4]. Similarly, FCI's current orientation rules (R1–R10) are analogous to Meek's R1–R3, but in general, the counterpart of Meek's R4 in FCI's context remains unknown [5]. Consequently, the completeness of FCI with general background knowledge has not yet been established.

3. How a sound but not fully complete algorithm can also be useful.

   • While completeness is desirable, sound algorithms can still be useful, if it can reliably output informative results, especially when proving completeness is difficult or complete algorithms in practice add more complexities than benefits. For instance,
   • The FCI algorithm itself has been widely adopted to deal with hidden confounders before its completeness was established (1999 to 2008).
   • Even now FCI is complete with respect to the Markov equivalence class, it is not complete with respect to the distribution equivalence class, due to additional (in)equality constraints given by latent variables [6].
   • For cyclic causal discovery, the CCD algorithm [7] has been widely adopted but it is incomplete, since with cycles, a d-separation may not imply a conditional independence.
   • Overall, these examples illustrate that an algorithm does not have to be fully complete to be useful; its value depends on how close it is on the spectrum towards completeness—both theoretically and empirically.
   • Therefore, we show our empirical results on simulations below (note that our position on the theoretical axis is already shown in above point 1).

We sincerely appreciate the reviewer's constructive comments and helpful feedback. Please see below for our response.

(Q1) The reviewer wonders if our characterization of Markov equivalence class is as fine-grained as possible.

A: We thank the reviewer for this thoughtful question, and would like to note that we have indeed characterized the Markov equivalence class to the finest-grained level possible, capturing all conditional independence (CI) implications. Specifically:

• Our Theorem 1 (Markov properties) is expressed in the following form:

  "For any graph $\mathcal{G}$ and any distribution $p$ generated from $\mathcal{G}$, if [some graphical criteria holds in $\mathcal{G}$], then [some conditional independence holds in $p$]."

  The reason why we do not use the "if and only if" statement is just because faithfulness is not assumed at this stage—not due to any missing conditional independence implications.

• In essence, the left-hand side (graphical criteria) and right-hand side (conditional independence implications) characterize the same fine-grained level of equivalence. To view this, note that Theorem 1 can equivalently be expressed as:

  "For any graph $\mathcal{G}$, [some graphical criteria holds in $\mathcal{G}$], if and only if [some conditional independence holds in all distributions generated by $\mathcal{G}$]."

We thank the reviewer again for highlighting this, and hope the above explanation clarifies that our equivalence classes are indeed fully characterized.

(Q2) The reviewer wonders if our approach generalizes to arbitrary latent variables.

A: We appreciate this insightful question. The short answer is, yes. Specifically,

• Similar to how the augmented DAG framework offers a unified way to understand interventional data without selection bias, our interventional twin graph framework offers a unified way to understand interventional data with selection bias.
• Then, various extensions can be incorporated into this framework, just as they are in the augmented DAG paradigm (discussed in Section 2.1 in our manuscript). Latent variables is one of such extensions. Others include e.g., deriving causal inference results.
• For latent variables, the technical route is straightforward: one may modify the specific graphical criteria of constructing maximal ancestral graphs (MAGs) (Lemmas 4 to 6 in our updated manuscript) and adjust the orientation rules and edge interpretations in Algorithm 1. While details may differ, the core concept remains unchanged.
• In this work, we focus solely on selection bias, as we aim to thoroughly characterize its own complexities, highlight its impact on interventional studies, and maintain clarity in our presentation.
• One philosophically interesting observation, as discussed in Section 2.3, is that latent variables are easier to incorporate than selection bias for interventional studies. This is because, when selection bias is absent, the two forms of intervention (on existing individuals vs. from scratch) yield the same interventional data at the distribution level, even with latent variables. Selection bias, however, behaves quite differently.

We are delighted to know that our response well addressed your concerns. Thank you once again for your constructive comments about completeness.

Update: It has been fixed. Thank you.

Dear Reviewer VRoQ,

Thank you for your careful review. It appears the review intended for another submission may have been posted here by mistake. Could you please help us in resolving this?

Thank you,

-Authors of Submission 1361

We are encouraged that the reviewer recognizes our work as "finding an interesting flaw in previous methods".

We would like to highlight that our contribution goes beyond solving a specific problem; we identify a new problem setting and establish a general framework to understand this setting, namely, interventional studies under selection bias.

In real-world scenarios, selection indeed always meets intervention, as real experiments are typically designed with specific scopes and objectives (e.g., participants in a drug trial are usually patients of the relevant disease).

To this end, we hope this work provides a foundation for various potential practical extensions, such as incorporating latent variables for causal discovery and deriving causal inference results.

We want to thank the reviewer again for all the valuable feedback.

We sincerely appreciate the reviewer's constructive comments and helpful feedback. Please see below for our response.

(Q1) The reviewer suggests a simulation to illustrate why the intervention destroys a conditional independence in Example 2 (pest control).

A: Thanks for the suggestion. We have provided a simulation with scatterplots for this example. Due to space limit, we put in Appendix B.1 in the updated manuscript. In brief, such loss of conditional independence is because that selection renders exogenous noise terms not independent anymore.

(Q2) The reviewer wonders how conditional distribution invariance is tested.

A: For two datasets $p^{(0)}$ and $p^{(1)}$, to test whether a conditional distribution is invariant, we introduce a binary dataset indicator variable $\zeta$, where $\zeta=0$ for samples from $p^{(0)}$, and $\zeta=1$ for samples from $p^{(1)}$. Let $p$ denote the stacked data of $p^{(0)}, p^{(1)}$. Then, the conditional distribution invariance $p^{(0)}(X_A|X_C) = p^{(1)}(X_A|X_C)$ is equivalent to the equality $p(X_A|X_C, \zeta=0) = p(X_A|X_C, \zeta=1)$, that is, the conditional independence relation $\zeta \unicode{x2AEB} X_A | X_C$ in stacked data $p$. The invariance of conditional distributions is thus tested by testing for the corresponding conditional independence involving $\zeta$ in the stacked data.

As we have shown in Section 2.1, this is exactly the motivation to introduce $\zeta$ variables into the graph, so as to model conditional distribution invariance nonparametrically.

In practical usage, while this can be realized by all kinds of conditional independence tests, we use Fisher's Z tests in our experimental runs for speed consideration.

(Q3) The reviewer suggests providing intuitions behind the lemmas.

A: Thank to your suggestions, we have carefully rewritten our technical sections in the updated manuscript. We introduce each lemma alongside the specific question it aims to answer, highlighted in blue in the revision. We hope you find the updated manuscript more readable.

(Q4) The reviewer asks for clarification on several technical points.

A: We appreciate your careful reading, and we understand how our previous presentation may have been hard to follow. In our original submission, we presented our theory development sequentially: starting with an intuitive model, then demonstrating its flaws, and finally making corrections to reach the optimal model. While this approach was helpful for understanding the technical progression, it may have impacted readability.

Therefore, in the updated manuscript, we directly present the optimal model, which we believe resolves most of the confusion. Nonetheless, let us still address each of your points below. Please note that the following responses are based on the original manuscript.

• (Q4.1) Why was there a contradiction between Example 3 ("open path goes through $X_2^*$") and Example 4 ("...automatically conditions on $X_2^*$")?

  A: This was because of the different intervention targets. In Example 3, the intervention targeted $X_1$, while in Example 4, it targeted $X_3$. This contrast was intended to highlight the insufficiency of relying solely on d-separations in the previous model: varying data behaviors under different interventions were described by the same graph.

• (Q4.2) What was the extra condition beyond regular Markov property in DAGs in Theorem 1?

  A: The extra condition was that when an unaffected variable $X_i$ is conditioned on, its counterfactual part $X_i^*$ must also be conditioned, as unaffected variables retain their original values after intervention.

• (Q4.3) How did Lemma 1 miss key distributional information?

  A: Lemma 1 showed that in the previous model, the $X^*$ variables could be marginalized out, resulting in selection directly applied to exogenous noise terms $\mathcal{E}$, leading to the loss on sparsity in the selection mechanisms. The motivation for this was given in Example 5, which showed two DAGs that are already distinguishable with only observational data. However, using the previous model, their corresponding interventional twin graphs entail the same sets of d-separations for arbitrary targets.

Once again, we appreciate the reviewer's input and hope these explanations clarify our motivation behind the technical progression in our original submission. We also hope you find that these potentially confusing points have already been avoided in the updated manuscript.

We sincerely appreciate the reviewer’s prompt and valuable feedback. Please find our detailed responses below:

(Q1) The reviewer points out that "interventions are never applied in a vacuum" writing is unclear.

(A) Thank you for this constructive comment. In light of it, we have revised the sentence in the updated manuscript to "In real-world scenarios, interventions are usually applied after selection, as experiments are typically designed to target specific scopes of study."

Moreover, please let us share more motivation behind the original phrasing. Our intension was to differentiate the proposed twin graph model from the simpler extension of the augmented graph model. The latter assumes interventions are applied universally, without prior selection, and after that, different intervened individuals undergo a same selection mechanism.

We aimed to highlight that this latter scenario is much less common in practice. Selection can often be understood as a survival process. For example, in biological experiments, only cells that meet specific criteria can survive, and any cell has to first survive itself before receiving any interventions or observations. In this sense, applying interventions without prior selection—what we referred to as "from a vacuum"—is rarely feasible in real-world settings.

We hope this revision and clarification address the reviewer's concerns.

(Q2) The reviewer wonders further motivation for introducing MAGs. Specifically,

(Q2.1) Why are MAGs introduced? Aren't twin graphs sufficient to explain all the CIs and invariances?

(A) Thank you for this thoughtful question. As is noted in our manuscript (line 312), "we introduce MAGs to simplify the graphical representation for the CI implications." Below, we provide a more detailed explanation, by showing the role that MAGs play throughout our manuscript.

After establishing the interventional twin graph in Section 3.1, our manuscript is structured to address the following three key questions about it, step by step:

1. What are the CI implications of an interventional twin graph? (Section 3.2)
2. When do two interventional twin graphs entail the same CI implications? (Section 3.3)
3. How, and to what extent, can we infer the true interventional twin graph from data? (Section 4)

To understand why we introduce MAGs, let us examine the role that MAGs play in addressing each of these questions.

1. For question 1, MAGs provide a more intuitive graphical representation to interpret CI implications. While it is true that d-separations in interventional twin graphs (which are DAGs) can already characterize all CIs and invariances, they can be unintuitive to interpret. To see this, recall that in a fully observed DAG, two variables are adjacent if and only if they are dependent given any other variable sets. However, this no longer holds with latent and selection variables. For instance, in the pest control example, $X_1$ and $X_3$ are not adjacent in the twin graph but remain conditionally dependent in all cases. MAGs address, where two variables are adjacent if and only if they are always dependent, simplifying interpretation (Lemma 4 in the updated manuscript).
2. For question 2, MAGs allow Markov equivalence to be determined through clear and efficient graphical criteria, such as adjacencies and v-structures, as presented in Theorem 2. By analogy, for two fully observed DAGs, equivalence can be defined in two graphical criteria: (1) "they have the same d-separations", or (2) "they have the same adjacencies and v-structures". Though the two are equivalent, the latter is obviously more intuitive and efficient. Similarly, without MAGs, equivalence in interventional twin graphs could only be defined through d-separations on DAGs with latent and selection variables, which can become unnecessarily complex.
3. For question 3, MAGs serve as a graphical object where algorithms can be grounded. Without MAGs, inferring the structure of a DAG from partially observed data becomes significantly challenging, as relationships involving latent and selection variables can be arbitrarily complex while they are completely inaccessible. MAGs, as graphical representations over observed variables only, provide a grounded structure that allows CI relations to be effectively used for causal discovery. The process is made even more practical with well-established algorithms like FCI based on MAGs.

We sincerely thank you for your recognition of our work. Your summary of our algorithm is correct and sharp!

In light of your suggestion, we are considering giving two separate definitions as "interventional twin DAGs" and "interventional twin MAGs." The latter, however, may not be entirely appropriate, as the MAG includes only observed variables and does not contain the twin world. We are still looking for a better way to present this. Once finalized, we will let you know and update the manuscript accordingly.

Thank you again for this constructive suggestion.

(Q2.2) Is the "MAG of a twin graph" different to a regular MAG?

(A) The "MAG of a twin graph" is not fundamentally different from a regular MAG. It is simply a specific class of regular MAGs. By analogy, an interventional twin graph is a regular DAG—meaning all its graphical properties like d-separations are the same as a regular DAG—while it is a specific class of DAGs with its form constrained in Definition 1.

The reason why we specifically define the "MAG of a twin graph" is to better understand the CI implications graphically, and to eventually identify more information from data, using knowledge about the structural constraints on interventional twin graphs.

For example, to answer the question, "when does an intervention alter all of a variable’s conditional distributions?" the general MAG adjacency rule (Definition 3, though being correct, can be too broad, whereas Lemma 7 directly answers that "this occurs if and only if the variable is directly targeted, or both affected and ancestrally selected." Moreover, with the specific orientation rules (Lemma 6), we can eventually identify more information (in terms of edge orientations) than a standard FCI can from data.

(Q2.3) Is the definition of Markov equivalence of "MAG of a twin graph" different to the regular MAG?

(A) Thank you for this especially insightful question. Yes, they are different. As shown in our Definition 2, two MAGs of interventional twin graphs are equivalent, if and only if they have the same adjacencies and v-structures. In contrast, for two MAGs of arbitrary DAGs, these two conditions are necessary but not sufficient; an additional condition is required. That additional condition is relatively complicated, so please bear with us to just quote it here without explanation: "If a path $p$ is a discriminating path for a vertex $V$ in both MAGs, then $V$ must be a collider on the path in one MAG if and only if it is a collider on the path in the other."

The reason why we can avoid this third condition is, again, due to the specific structural constraints of interventional twin graphs, from which we prove that this third condition is always satisfied for MAGs of interventional twin graphs.

All the three questions in (Q2) have been incorporated into our updated manuscript (lines 312, 352, and Footnote 4, respectively). We hope these revisions and clarifications address the reviewer's concerns. If not, we always look forward to the opportunity to discuss them further with you.

Once again, we want to thank the reviewer for your thoughtful questions, and your continuous input that helps improving the presentation of our submission.