Learning Mixtures of Unknown Causal Interventions

We thank the reviewer for their time and thoughtful comments. Below, we answer the weaknesses and questions raised by the reviewer.

Weakness

Weakness 1: Experiments

Experiment on the real-world dataset: We have run our algorithm on a real-world protein signaling network dataset. Our method performs equivalently on all the metrics compared to the Oracle algorithm, which has access to the disentangled data (please refer to the Evaluation on real-world dataset paragraph in the Global comment for details). Also, In the additional pdf document attached to the global comment, we provide the ground truth graph and the estimated graph from both algorithms. 

Experiment with Linear SEM with non-gaussian noise: The main motivation for our work comes from the problem of causal discovery. In general, one can only identify the causal graph up to their Markov Equivalence Class using only observational data. Thus, we need interventional data to fully identify the causal graph. The intervention targets are sometimes noisy, so we can only obtain a mixture of interventional data. However, Shimizu et al. [1] showed that observational data is sufficient for learning the underlying causal graph when the data-generating process is a linear SEM with additive non-Gaussian noise with no latent confounders.  They also proposed an algorithm (LINGAM)  that uses Non-Linear ICA over observational data to identify the causal graph. Thus, Linear SEM with non-gaussian noise doesn't require interventional data to identify the underlying causal graph. Hence, studying the mixture of interventional distribution for this framework is an interesting problem outside the scope of current work.

\

Questions

Questions 1: We thank the reviewer for this comment. We will add the intuition behind the proofs in the final version of the paper.

Question 2: (Effect of different variance in Gaussian noise)

We have an ablation experiment in Fig 5b of Appendix B.4, where we study the effect of changing the variance of the noise distribution post-intervention. The initial variance of the noise distribution of every node is 1.0, and post-intervention, we set the variance of the intervened node to take values from the set $\{0.1,1.0,4.0,8.0\}$. If the final noise variance (after intervention) is close to the initial noise variance (1.0), then the Jaccard similarity and SHD of the estimated targets and causal graphs are worse. This is also expected from our theoretical result (Theorem 4.1), which states that the sample complexity to recover the parameters of the mixture distribution is inversely proportional to the change in the noise variance ($\delta_i$ = |final variance - initial variance|).

Typos: We thank the reviewer for pointing out the typos and other writing suggestions in the text. We will incorporate them into the final version of the paper.

[1] Shohei Shimizu, Patrik O. Hoyer, Aapo Hyvärinen, and Antti Kerminen. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(72):2003–2030, 2006

We thank the reviewer for their time and thoughtful comments. Below, we answer the weaknesses and questions raised by the reviewer.

Weakness

Weakness 1: Experiment on the real-world dataset:

We have run our algorithm on a real-world protein signaling network dataset. Our method performs equivalently on all the metrics compared to the Oracle algorithm, which has access to the disentangled data, unlike us (please refer to the Evaluation on real-world dataset paragraph in the Global comment for details). Also, In the additional pdf document attached to the global comment, we provide the ground truth graph and the estimated graph from both algorithms. 

Weakness 2: Experiment with Linear SEM with non-gaussian noise:

The main motivation for our work comes from the problem of causal discovery. In general, one can only identify the causal graph up to their Markov Equivalence Class using only observational data. Thus, we need interventional data to fully identify the causal graph. The intervention targets are sometimes noisy, so we can only obtain a mixture of interventional data.

However, Shimizu et al. [1] showed that observational data is sufficient for learning the underlying causal graph when the data-generating process is a linear SEM with additive non-Gaussian noise with no latent confounders.  They also proposed an algorithm (LINGAM)  that uses Non-Linear ICA over observational data to identify the causal graph. Thus, Linear SEM with non-gaussian noise doesn't require interventional data to identify the underlying causal graph. Hence, studying the mixture of interventional distribution for this framework is an interesting problem outside the scope of current work.

\

Questions

Question 1:

The work from [6,28] has shown that CRISPR gene editing technology has an off-target effect. Also, the off-target effect can be random, i.e., every off-target effect could be different. For example, Aryal et al. [2] have shown that the same gene editing experiment on mice embryos exhibited different off-target cleavage for different mice. Thus, the observed data can be a mixture of multiple off-target interventions as modeled in our work. To perform any downstream task, one needs to identify the unknown intended target and disentangle the mixture distribution, which is also the main goal of our work. 

Question 2:

In our work, we study the problem of disentangling a mixture of unknown interventions on Linear SEM with Gaussian noise, a special case of learning Gaussian mixtures. We remark that learning Gaussian mixtures is a well-studied problem with a rich literature (check Section 2), and our work builds upon these existing results. To invoke existing learning Gaussian mixture results, one needs to show the separation between distributions corresponding to the mixture components which is non-trivial. In our case, the mixture components correspond to interventional distributions, and one of our main contributions is to show the separation between them. We wish to emphasize that this separation also depends on the type of interventions one performs, and in our work, through careful analysis, we show the mean and covariance of interventional distributions are well separated for a more general class of soft interventions. As a consequence of our separation result, we show that the intervention targets and parameters of the international distribution can be recovered.   

[1] Shohei Shimizu, Patrik O. Hoyer, Aapo Hyvärinen, and Antti Kerminen. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(72):2003–2030, 2006

[2] N.K. Aryal, A.R. Wasylishen, and G. Lozano. Crispr/cas9 can mediate high-efficiency off- target mutations in mice in vivo. Cell Death and Disease, 9, 2018

We thank the reviewer for their time and thoughtful comments. Below, we answer the weaknesses raised by the reviewer.

Weakness 1:

While we agree that the linear SEMs with unknown interventions are a relatively well-studied problem, we wish to highlight that our setting is different as we work with a mixture of multiple unknown interventions. Given such a mixture, our goal is to disentangle this mixture and recover the parameters corresponding to the mixture components. To the best of our knowledge, no other work exists that aims to solve this problem of disentangling the mixture of unknown interventional distributions in the setting of linear SEMS with Gaussian noise. Furthermore, in this setting, our work lays out the first theoretical foundation on the identifiability of the individual components in the mixture. 

We would like to restate the fundamental importance of this setup in the causal discovery literature (also stated in the Introduction, Lines 40-46 of the main paper). Shimizu et al. [1] showed that observational data is sufficient for learning the underlying causal graph when the data-generating process is a linear SEM with additive non-Gaussian noise with no latent confounders. However, in the same setting with Gaussian noise, the causal graph is only identifiable up to its Markov Equivalence Class (MEC). Thus, performing interventions (possibly noisy) is necessary to identify the causal graph, making it an interesting framework for our problem.

We also wish to remark that some prior works do study a more general problem of disentangling the mixture of multiple unknown directed acyclic graphs. However, there are no theoretical guarantees about the identifiability of individual components in this setting (please refer to the Mixture of DAGs and Intervention paragraph in Section 2 of the main paper). 

Weakness 2:

Soft interventions are a very general form of intervention that subsumes most of the widely studied interventions in the literature, such as shift, stochastic do, and do (please also see Lines 134 to 139 for this specialization). Therefore, we believe that studying soft interventions would indeed have a much broader applicability. 

Weakness 3:

We have run our algorithm on a real-world protein signaling network dataset. In summary, our method performs equivalently on all the metrics compared to the Oracle algorithm, which has access to the disentangled data (please refer to the Evaluation on real-world dataset paragraph in the Global comment for details). Also, in the additional pdf document attached to the global comment, we provide the ground truth graph and the estimated graph for both the algorithms. The causal graph estimated by our algorithm is very similar to the graph estimated by the oracle. 

Also, we have added results with a new version of our algorithm (Mixture-UTIGSP), where we automatically search for the number of components in the mixture (please see global comment Automated Component Selection for details). Evaluating the “half-setting,” where the number of components in the mixture is (num nodes +1)/2, we observe that:

1. The number of components found by this method is also close to the correct value. 
2. The parameter estimation error goes down to zero for all the nodes, unlike Fig 1d in the main paper. The other metrics, like SHD, still have the same decreasing trend.
3. Please refer to Figure 2 in the additional pdf document attached to the global comment for the parameter estimation and SHD plot before (Fig1d and 1f from the main paper) and after this improvement. 

Limitations 1:

We agree that the linear SEM with Gaussian noise is restrictive and may not apply to many real-world settings.   However, even with these assumptions, the problem we study in our work is non-trivial and poses several challenges.  Extending our results beyond the linear SEM setting would help broaden the applicability of our results. We believe that studying these questions is a very important future research direction, and we would like to consider our work as a first step in this direction. Also, in answer to the Weakness 1 above, we motivated our choice to study Linear SEM with Gaussian noise.

We thank the reviewer for their time and thoughtful comments. Below, we answer the weaknesses and questions raised by the reviewer.

Weakness:

Limited Novelty: While we agree that our work builds on top of existing work but doesn’t follow immediately from them. To invoke these existing results on learning Gaussian mixtures, we do indeed make some non-trivial contributions, which we highlight below:

1. To invoke existing learning Gaussian mixture results, one needs to show the separation between distributions corresponding to the mixture components. In our case, the mixture components correspond to interventional distributions, and it is non-trivial to show separation between them. We wish to emphasize that this separation depends on the type of interventions one performs. Through careful analysis, our work shows that the mean and covariance of interventional distributions are well separated for a more general class of soft interventions. 
2. In addition to the above, one of our other major contributions comes in modeling a real-world setting. Although the contributions in our work are a first step towards solving the practical problem, nevertheless, we believe it is an important first step. 

Experimental Evaluation: Please see the answer to Question 2. We have also added a new experiment in which we automatically select the number of components that improves the parameter estimation error in Fig 1d of the main paper (see answer to Question 3 below). 

Writing Comment: We thank the reviewer for pointing this out. Yes, the variance $\delta_i$ and the probability $\delta$ are different. We will update the main paper to incorporate the reviewer’s suggestion.

\

Questions:

Question 1: Please note that Theorem 4.1 states that the sample complexity of the algorithm is polynomial in the norm of the adjacency matrix (A) but not the runtime as you stated. The algorithm doesn’t explicitly use the knowledge of the adjacency matrix “A”. The dependence of sample complexity on "A" characterizes the problem difficulty, i.e., depending on the problem, we will require a different number of samples to get the desired accuracy. Also, the algorithm is consistent, i.e., it will recover the correct parameters under an infinite sample limit. 

Question 2:

1. Fig 1a-c shows the setting when the number of components is correctly specified, i.e., k=num_node +1, and the number of components in the mixture is also num_nodes +1. In this case, we see a clear improvement in the parameter estimation error (Fig 1a). Fig 1d-f corresponds to the setting where the number of components is misspecified, i.e., k=num_node+1 and number of components = num_node/2+1. This is mainly due to mispecified number of components in the mixture. Below, we fix this.
2. Automated Component Selection: We have added results with a new version of our algorithm (Mixture-UTIGSP), where we automatically search for the number of components in the mixture (please see global comment Automated Component Selection for details). Evaluating the “half-setting,” where the number of components in the mixture is (num nodes +1)/2, we observe that:
   1. The number of components found by this method is also close to the correct value. 
   2. The parameter estimation error goes down to zero for all the nodes, unlike Fig 1d in the main paper. The other metrics, like SHD, still have the same decreasing trend.
   3. Please refer to Figure 2 in the additional pdf document attached to the global comment for the parameter estimation and SHD plot before (Fig1d and 1f from the main paper) and after this improvement. 

Question 3: The parameter estimation error is high in the second setting (num intervention = half, Fig 1d-f of main paper) due to the misspecified number of components (k=num nodes+1). To remove this problem, we have modified our algorithm to automatically select the correct number of components in the mixture (please see Automatic component selection paragraph in Global comments and answer to Question 2). In summary, with the modified algorithm, the parameter estimation error goes to zero, Jaccard similarity increases, and SHD decreases to zero as the sample size increases.

We thank the reviewer for their response and for acknowledging that the experimental evaluation is thorough now. Below, we answer the concerns and questions in detail:

Limited Novelty

Here is an example where there is no separation between the parameters in the mixture. Let the system consist of three nodes $X, Y$ and $Z$, the corresponding SEM is defined as:

$X= N(0,1)$

$Y=X$ and

$Z=X-Y+N(0,1)$

Let the mixture distribution consist of two components: a) observational and b) stochastic do intervention on node $Z$. Here, we keep the noise distribution the same as before post-intervention, i.e., we set $Z = N(0,1)$. We can show that the mean and covariance of both components are the same. Thus, there is zero parameter separation in spite of the adjacency matrix being different for both components.

We agree that the above constructed example violates the faithfulness assumption. Thus, we needed a careful analysis to capture such nuances and other complexities in the parameter separation calculation. Our lower bound of parameter separation in Lemma 5.1 captures this i.e., parameter separation is zero for the above example since $f(B, D)=\lambda_{min}^{2}(D)/4||I-A||_{F}^{4} = 0$ since the noise covariance matrix $D$ has one of the entries as zero and the other parameters $\delta_i=\delta_j=\gamma_i=\gamma_j=0$ (see Appendix A2 for exact expression of $f(B, D)$).

Also, it is somewhat intuitive that for non-degenerate cases, the parameters will be separated, but the exact dependence on the parameters of intervention was not clear. In Lemma 5.1, we show that the lower bound of the parameter separation is a polynomial function of the parameters of intervention ($||c_i||$, $\delta_i$ and $\gamma_i$’s). This also enables us to show the polynomial sample complexity of the existence algorithm in Theorem 5.2.

\

Threshold for Automatic Component Selection:

Currently, we manually set the percentage threshold to a fixed value (7% in our simulation experiments, selected arbitrarily). As we increase the number of components in the mixture model the log-likelihood of the model is expected to increase due to increasing model capacity. However, we expect that as we reach the correct number of components any further increase in the number of components will most likely lead to minimal change in the log-likelihood. Thus, we chose to keep the threshold a small number close to zero.