Interventional Causal Discovery in a Mixture of DAGs

We thank the reviewer for thoughtful evaluations and feedback. We hope the following explanations can clarify the reviewer’s concerns.

Running example: Thank you for the suggestion. Figure 2 in Appendix D illustrates the mixture of DAGs and construction of $\cal{I}$-DAG. Due to space limitations, we have had to defer it to the appendix. We will move it to the main paper and add the following details to its caption:

• True edges $E_{\rm t} = \\{1 \rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 2, 3 \rightarrow 4, 1 \rightarrow 4\\}$
• Emergent pairs $E_{\rm e} = \\{ (1,3), (2,4) \\}$
• Inseparable pairs $E_{\rm i} = \\{ (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) \\}$
• $\Delta$-through path examples: $1 \rightarrow 2 \rightarrow 3$ in $\mathcal{G}_1$; $3 \rightarrow 4$ in $\mathcal{G}_2$

Real-world dataset: We emphasize that the focus of our work is establishing the needed theory for using interventions on a mixture of DAGs. While we acknowledge the importance of real-world applications, establishing the novel theory and demonstrating the real-data usefulness can be beyond the scope of one paper. In the following, we elaborate on the challenges of a direct real-world application and explain why our theoretical contribution is an important step toward that direction.

• Lack of a proper real-world dataset: The existing benchmark causal discovery datasets, such as protein signaling network in Sachs et al. (2005) or ovarian cancer dataset of Tothill et al. (2008), are known to be not perfect single DAGs. For instance, the “true DAG” for protein signaling network is challenged under new evidence (Ness et al., 2017), and there is no strong consensus over the ground truth DAG. Furthermore, the existing interventional single DAG learning algorithms do not perform well in terms of standard metrics, e.g., structural Hamming distance (e.g., Squires et al. (2020), Wang et al. (2018), Varici et al. (2021)) despite the strong theoretical guarantees. These observations suggest that a single DAG may not be the best approach for modeling such real-world datasets. To our knowledge, there is no commonly accepted and well-defined dataset in which the data generation mechanism is a mixture of DAGs.

• Access to interventions: We note that the existing datasets come with a predefined set of interventions, e.g., single-node or two-node genomics interventions, and we cannot "simulate" any desired intervention. This makes it difficult to evaluate any interventional learning algorithm that fully learns the graph. For instance, as discussed in Lines 84—87, the majority of the existing results in the single-DAG setting consider “unconstrained” intervention sizes. Our results in Theorem 1 and 2 contribute to our understanding of the required intervention sizes, which can shed light on the extent of identifiability given a real-world dataset (without a simulator).

In light of these, we leave the investigation of real-world datasets/applications (and related partial identifiability results) to future work.

References

K. Sachs, O. Perez, D. Pe'er, D. A. Lauffenburger, and G. P. Nolan, “Causal protein-signaling networks derived from multiparameter single-cell data,” Science, vol. 308, no. 5721, pp. 523– 529, 2005.

R. W. Tothill et al. “Novel molecular subtypes of serous and endometrioid ovarian cancer linked to clinical outcome,” Clinical Cancer Research, vol. 14, no. 16, pp. 5198–5208, 2008.

R. O. Ness, K. Sachs, P. Mallick, and O. Vitek, “A Bayesian active learning experimental design for inferring signaling networks,” in Proc. Research in Computational Molecular Biology, Hong Kong, May 2017, pp. 134–156.

C. Squires, Y. Wang, and C. Uhler, “Permutation-based causal structure learning with unknown intervention targets,” in Proc. Conference on Uncertainty in Artificial Intelligence, August 2020.

Y. Wang, C. Squires, A. Belyaeva, and C. Uhler, “Direct estimation of differences in causal graphs,” in Proc. Advances in Neural Information Processing Systems, Montreal, Canada, December 2018.

B. Varici, K. Shanmugam, P. Sattigeri, and A. Tajer. “Scalable intervention target estimation in linear models,” in Proc. Advances in Neural Information Processing Systems, December 2021.

We are grateful for the exceptionally detailed and thoughtful review. We address the raised questions as follows.

General questions

Motivation for recovering the true edges: The observation is correct that, without further assumptions, we cannot identify which true edges belong to which DAGs. To see why this is impossible in general, consider two mixtures:

• Mixture 1: $K=2$ DAGs with edges $E_1=\\{1\rightarrow 2, 1\rightarrow 3\\}$ and $E_2=\emptyset$
• Mixture 2: $K=2$ DAGs with edges $E_1=\\{1\rightarrow 2\\}$ and $E_2=\\{1\rightarrow 3\\}$ In this example, no intervention can distinguish the two mixtures.

Then, if we cannot disentangle the individual DAGs, we argue that finding the true edges is the best we can do, and it is still useful for causal inference tasks. The motivation is that the mixture model is generally composed of DAGs with similar contexts. For instance, different subtypes of ovarian cancer create a mixture model (Lines 27-28). Identifying a causal connection (a true edge) in this setting is crucial even if it appears in only some subpopulations (i.e., some of the component DAGs).

Number of mixture components $K$ is unknown: The algorithm does not take $K$ as an input. Our algorithm is designed for general DAGs (without structural restrictions). Hence, the guarantees associated with the algorithm are given for general DAGs in Theorems 3 and 4. The mentioned Theorem 2 is specific to trees and aims to provide a theoretical understanding separate from the algorithmic approach.

Breaking set in Line 282:

• First, we elaborate on the procedure. When considering an intervention on $B(i)$, we already have the ancestor set $\hat{\rm an}(i)$. Hence, for $j\in\hat{\rm an}(i)$, we investigate the single direction $j\rightarrow i$. Since $i\notin B(i)$, we avoid making a useless intervention, e.g., intervening on both $i$ and $j$ at the same time.
• Next, recall the definition of $C(i)$: set of cycles in which all nodes of the cycle belong to $\hat{\rm an}(i)$. By definition, $B(i)$ contains at least one node from each cycle in $C(i)$. Therefore, by intervening on $B(i)$, we cut off a link in each cycle.

Additional references: Thanks! Indeed, both [1] and [2] are related to the discussion in our literature review. We will add them to the revised paper.

Example in Figure 2: Your observation is correct. For simplicity, we have used an example in which the root node $1$ has the same marginal distribution on two components. We will mention it in the caption of Figure 2.

Typos and minor fixes:

• Proof of Theorem 3: We are truly sorry for the typos here. In Line 620, it should be $S_1(i)$ and ${\rm pa}_{\rm m}(i)$. Since Theorem 3 considers a single node $i$, all $S_t$ sets are supposed to be $S_t(i)$. The entire list of fixes:

  • $S_1\to S_1(i)$ in Lines 620, 628, 629, and eq. (26)
  • $S_u\to S_u(i)$ in Lines 633, 635, 643
  • $S_k\to S_k(i)$ in Line 634.

• Line 290: Thanks for the suggestion. We update Lines 289-293 as follows:

  Next, we update $\mathcal{A}\gets\mathcal{A}\setminus S_1(i)$ by removing layer $S_1(i)$ to conclude the first step. Then, we iteratively construct the layers $S_u(i)=\\{j \in \mathcal{A}:\hat{\rm de}(j)\cap\mathcal{A}=\emptyset\\}$ and update $\mathcal{A}\gets\mathcal{A}\setminus S_u(i)$ as in Line 26 of the algorithm. We continue until the set $\cal{A}$ is exhausted, and denote these topological layers by $\\{S_1(i),\dots,S_t(i)\\}$.

• Eq.(23) and (24): You are right that descendant and ancestor definitions do not include $i$. Hence, Eq.(23) and (24) should have $\cup i$, as correctly given in line 14 of the algorithm. Correcting another typo in Eq.(24), we have ${\rm de}_i(j)=\hat{\rm de}(j)\cap\\{\hat{\rm an}(i)\cup i\\}={\rm de}\_{m}(j) \ , \ \forall j \in{\rm an}\_{\rm m}(i)\ .$

• Eq.(57): You are right that we mean $\mathcal{C}(5) = \emptyset$, we will fix it.

• Line 255: It should be Mixture.

Experiment questions:

Increasing graph size and number of components: Please refer to the global response in which we report experiments up to $n=30$ nodes and $K=10$ components.

Connectedness of the graph: Our theory and algorithm do not require the DAGs to be connected. So it wouldn't be a problem for experiments. As the reviewer points out, large random graphs with small densities would consist of a giant connected component and many small components. In this case, we’d expect the "giant connected component" to dominate the complexity of our algorithm (e.g., the number of total interventions).

Edge weights: We will move the “experimental procedure” paragraph in Appendix E to the main paper and will add the statement “under this parametrization” to the discussion on the number of samples in Line 348.

Parametrization of true edges: You are right that in general, conditional distributions $p_l(X_i\mid X_{{{\rm pa}\_{l}}(i)})$ and $p_{l'}(X_i\mid X_{{{\rm pa}\_{l'}}(i)})$ can be different even if ${\rm pa}_l(i)={\rm pa}\_{l'}(i)$. For simplicity of the exposition of experiments, we considered the special case of mixtures in which a change in the conditional distribution is only caused by changes in the parents so that $\Delta$ becomes the set of nodes with varying parents across the component DAGs. We perform additional experiments for the most general case where true edges can have different weights across the components. Please see the global response for the results and details.

Mixture skeleton learning: It is done via exhaustive CI tests. For every pair $(i,j)$, we test the conditional independence of $X_i$ and $X_j$ given every $S\subseteq[n]\setminus\\{i,j\\}$ (as in Algorithm 1 of [11]). We will add this detail to the experiments in the revised paper. Note that, as mentioned in Line 262, we omit this step due to its $\mathcal{O}(n^2 2^n)$ complexity and only perform it for the comparison in Figure 1b.

We thank the reviewer for the thoughtful comments and assessment of our paper. We address the raised questions as follows.

Experiments: In the additional experiments in the global response, we demonstrate that our algorithm is scalable to higher dimensions – up to $n=30$ nodes and $K=10$ component DAGs – without a significant change in the performance. Please refer to the global response for details.

Partitioning true edges into individual component DAGs: Thank you for the suggestion that is an important future direction. However, it will most certainly require additional assumptions. For instance, in our current formulation, consider two sets of mixture DAGs:

• Setup 1: $K=2$ DAGs with edge sets $E_1 = \\{1\rightarrow 2, 1\rightarrow 3\\}$ and $E_2 = \emptyset$
• Setup 2: $K=2$ DAGs with edge sets $E_1 = \\{1\rightarrow 2\\}$ and $E_2 = \\{1\rightarrow 3\\}$ In this example, no interventions can distinguish the two setups. Similarly, in general, we cannot determine the number of components in the mixture.

That being said, under certain assumptions we expect the partitioning to become possible. For instance, in a similar problem, Kumar and Sinha (2021) study disentangling mixtures of unknown interventional datasets under specific conditions on the intervention sets and given the distribution of the pre-intervention DAG. Establishing the necessary and sufficient conditions for achieving similar disentangling objectives tasks in our mixture model is an open problem for future work.

• Kumar, Abhinav, and Gaurav Sinha. "Disentangling mixtures of unknown causal interventions." Uncertainty in Artificial Intelligence. PMLR, 2021.

We thank the reviewer for a thorough review and insightful comments. We address the questions as follows.

Modified distributions of an intervened variable: We considered an intervention model in which an intervened node $i$ has distribution $q_i(X_i)$ for all component DAGs. The reason is that an intervention procedure targets a specific node on all component models at the same time. For instance, when considering a gene knockout experiment (e.g., via CRISPR technique (Ran et al., 2013)), all the edges from parents are cut off, and the new distribution $q_i(X_i)$ is expected to be the same across all DAGs as result of the same intervention mechanism.

F Ann Ran, Patrick D Hsu, Jason Wright, Vineeta Agarwala, David A Scott, and Feng Zhang. “Genome engineering using the crispr-cas9 system”. Nature Protocols, 8(11):2281–2308, 2013.

Intervention sizes for single DAGs:

• First we note that an assumption in our analysis is that we have $K \geq 2$ component DAGs. Hence, unfortunately we cannot recover the counterpart results for single DAGs as a special case. Furthermore, when considering a single DAG, there are no multiple component DAGs. As such, the lack of a detailed discussion on single DAGs is not due to our interventional model but it is simply due to the nature of the mixture model that does not subsume the single DAG model.

• After these clarifications, we kindly note that we discussed the interventions on single DAGs in Lines 83-98. To elaborate further, single DAGs in causally sufficient systems, i.e., no unobserved confounders, can be learned using single-node interventions. Hence, almost none of the papers cited in the paragraph "Intervention design for causal discovery of a single DAG" investigates the required intervention sizes. Therefore, we did not discuss the specific results of those papers that are not related to our investigation. To give an example [16] shows that $\cal{O}(\frac{n}{k}\log \log k)$ randomized interventions with size $k$ suffice for identifying the DAG with high probability. In another direction, different cost models are proposed to minimize the total intervention cost incurred by the number and size of the interventions ([20], [24], [25]). In the presence of latent variables, multi-node interventions can be required. However, for this case, [19]-[20]-[21] study strongly-separating sets, again based on unconstrained intervention sizes.

• To our knowledge, only related work for the required size of interventions is [26]. Specifically, it considers cyclic directed models and shows that the required intervention size is at least $\zeta-1$ where $\zeta$ denotes the size of the largest strongly connected component (nodes $i$ and $j$ are said to be strongly connected if they are both ancestors of each other). We will add this note to the revised paper.