Linear Causal Representation Learning from Unknown Multi-node Interventions

We thank the reviewer for finding our results an important step towards more realistic CRL settings and noting the clarity of the paper.

General causal models: We did not provide results using non-linear causal models since our algorithm, due to its combinatorial nature, is sensitive to input noise. While we are actively trying to make our algorithms work better using generic score estimators, for this response, in the interest of time, we have elected to provide a complementary analysis, where we investigate the performance of our algorithms under different levels of artificially introduced noise.

For this set of experiments, we adopt a non-linear additive noise model with a score oracle. Specifically, the observational mechanism for node $i$ is generated according to

$

Z_i = \sqrt{Z_{{\rm pa}(i)}^\top {\bf A}_i Z_{{\rm pa}(i)}} + N_i \ ,

$

where $N_i \sim {\cal N}(0, \sigma_i)$, and the interventional mechanisms set $Z_i = N_i / 2$. This causal model admits a closed-form score function (see [7, Eq.(393–395]), which enables us to obtain a score oracle. In our experiments, we use this score oracle and introduce varying levels of artificial noise according to

$

\hat{s}_X(x; \sigma^2) = s_X(x) \cdot \big( 1 + \Xi \big) \ , \quad \mbox{where} \quad \Xi \sim {\cal N}(0, \sigma^2 \cdot {\bf I}_{d \times d}) \ ,

$

to test the behavior of our algorithm under different noise regimes ($\sigma \in [10^{-3}, 10^{-1.5}]$). Results à la Table 2 versus different $\sigma$ values are provided in Figure 1 in the PDF document attached to the general response.

Score estimation: We kindly note three things regarding the score functions on nonparametric models.

• Our algorithm is agnostic to the choice of score estimator, and we can adopt popular score-matching methods as mentioned in Line 325, e.g., Song et al. (2020) or Zhou et al. (2020). We also note that score function estimation is finding increasingly more applications in diffusion models, and it is an active research field. Hence, our algorithms can modularly adopt any new score estimation algorithm and benefit from advances in the score estimation literature.

• Score vs. density estimation: We also note that score estimation in a high-dimensional setting is generally easier than density estimation, as it avoids the difficulty of finding the normalizing constants.

• Finally, we emphasize that our algorithm only requires score differences and does not require the score functions themselves. We conjecture that the direct estimation of score differences can be much more efficient than estimating the individual score functions, a lá direct estimation of precision difference matrices [R1]. Furthermore, density ratio estimation methods, e.g., classification-based approaches [R2], can be potentially useful for direct score difference estimation.

[R1] Jiang, Wang, and Leng. "A direct approach for sparse quadratic discriminant analysis." JMLR, 2018.

[R2] Gutmann and Aapo Hyvärinen. "Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics." JMLR, 2012.

We thank the reviewer for their thoughtful review and accurate summary. We address the questions as follows.

Computational complexity: Stage 1 (score difference estimation) is only performed once before the main algorithm starts. Stage 4 (unmixing procedure for hard interventions) essentially works as a post-processing step that does not pose computational challenges. Below, we elaborate on the computational complexity of Stage 2 and Stage 3.

• Stage 2: We check dimension of $\mathcal{V}$ (line 6 of the algorithm) at worst $n \times (2 \kappa + 1)^n$ times in Stage 2 of the algorithm. Here, $\kappa$ denotes the maximum possible determinant of a matrix $\\{0,1\\}^{(n-1) \times (n-1)}$. In the proof of Lemma 2 in Appendix A.1, we discuss why this choice facilitates the identifiability guarantees. We also discuss how $\kappa$ grows with $n$ in Appendix A.8, and give special cases, such as sparse multi-node interventions, in which $\kappa$ is upper bounded by small numbers even for large $n$ values.

• Stage 3: Here, we check dimension of $\mathcal{V}$ (line 23 of the algorithm) at worst $\\|\mathbf{W}\_{:,j}\\|_1 \times \\|\mathbf{W}\_{:,t}\\|_1$ times for every $(t,j)$ in Stage 3 of the algorithm. Note that $\mathbf{W}$ is updated within the steps of Stage 3. Therefore, the exact computational complexity would be a function of the graph structure, and the outputs of Stage 2.

• Empirical tricks: Finally, we note two empirical tricks that can reduce the computational complexity greatly. First, even though $\kappa$ can grow quickly as $n$ becomes larger, in practice, setting $\kappa=2$ usually works fine (see additional experiment results in the general response). Second, additional empirical tricks can greatly increase the speed of the algorithm, e.g., dividing the columns of $\mathbf{W}$ by the greatest common divisor of its entries after every step. Since our focus is on establishing the identifiability results, we omit the investigation of empirical tricks that would disturb the flow of the paper and distract from the main focus.

Toward realistic settings: We believe this paper serves as a significant step in this direction by removing the stringent assumption of single-node interventions. For instance, genomics datasets such as Perturb-seq (Norman et al. 2019) are used by single-node interventional CRL (Zhang et al. 2023). However, the genomic interventions are known to have unknown off-target effects (Fu et al. 2013, Squires et al. 2020) that violate the single-node intervention assumption. Therefore, establishing unknown multi-node interventional results is fundamental to unlocking the use of CRL in realistic datasets. The implementation of real applications is beyond the scope of this work and is an important future direction.

References

T. M. Norman, M. A. Horlbeck, J. M. Replogle, A. Y. Ge, A. Xu, M. Jost, L. A. Gilbert, and J. S. Weissman. Exploring genetic interaction manifolds constructed from rich single-cell phenotypes. Science, 365(6455):786–793, 2019.

J. Zhang, C. Squires, K. Greenewald, A. Srivastava, K. Shanmugam, and C. Uhler. Identifiability guarantees for causal disentanglement from soft interventions. NeurIPS 2023

Y. Fu, J. A. Foden, C. Khayter, M. L. Maeder, D. Reyon, J. K. Joung, and J. D. Sander, “High frequency off-target mutagenesis induced by CRISPR-Cas nucleases in human cells,” Nature Biotechnology, vol. 31, no. 9, pp. 822–826, 2013

C. Squires, Y. Wang, and C. Uhler. Permutation-based causal structure learning with unknown intervention targets. UAI 2020

We thank the reviewer for acknowledging our strong theoretical and algorithmic contributions. We address the questions as follows.

Empirical results:

• Increasing $n$: Thanks for the suggestion. Please refer to the general response for experiment results for up to $n=8$ nodes.
• Baseline: We note that Bing et al. use “do” interventions. Hence, the algorithms are not comparable.

Interventional regularity: We explain the rationale and details as follows.

• First, we emphasize that interventional regularity is not a restrictive assumption. In Appendix A.8.(Lemma 5), we present some sufficient conditions in which the interventional regularity holds. For instance, under a hard intervention on a linear causal model, if the distribution of the exogenous noise remains the same, then interventional regularity holds. Hence, it is not a restrictive assumption.

• Next, we clarify what we mean by the effect of an intervention. Essentially, $\frac{\partial\log p_i/q_i}{\partial z_j}$ is the effect of intervening on node $i$ on the score associated with node $j$. Note that we use combinations of different multi-node environments to generate new score difference functions. Without the additional term in Eq.(12), $\frac{\partial\log p_j/q_j}{\partial z_j}$, the ratio in Eq.(11) considers only a single node intervention on $i$ and its effects on scores of $i$ and $j$.

• To ensure that the effect of a combined intervention is different on scores of $i$ and $j$, we need to consider interventions on both $i$ and $j$. As such, the additional term in Eq.(12), $\frac{\partial\log p_j/q_j}{\partial z_j}$, denotes the effect of the additional intervention on $j$ on the node $j$.

Score function differences:

• We do not require estimating $\Lambda$. It is correct that $\Lambda$ encodes score differences in latent space, and we cannot estimate it. Therefore, the algorithm only takes $\Delta S_X$ as input. $\Lambda$ is defined to provide intuition on the rationale of the algorithm and the connection between latent score differences and $\Delta S_X$ in Eq.(17).

• Our algorithm is agnostic to the choice of score estimator, and we can adopt popular score-matching methods as mentioned in Line 325, e.g., Song et al. (2020) or Zhou et al. (2020). We also note that score function estimation is finding increasingly more applications in diffusion models, and it is an active research field. Hence, our algorithms can modularly adopt any new score estimation algorithm and benefit from advances in the score estimation literature.

• We also emphasize that our algorithm only requires score differences and does not require the score functions themselves. We expect that the direct estimation of score differences can be much more efficient than estimating the individual score functions, à la direct estimation of precision difference matrices [R1]. Furthermore, density ratio estimation methods, e.g., classification-based approaches [R2], can be potentially useful for direct score difference estimation.

[R1] Jiang et al. A direct approach for sparse quadratic discriminant analysis. JMLR, 2018.

[R2] Gutmann and Hyvärinen. Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics. JMLR, 2012.

Additive noise models (ANM): Please refer to our general response.

Stage 2 of the algorithm: We elaborate on learning the vectors $\bf w$ and the role of $\kappa$ as follows.

• Note that $\Delta S_X\cdot\bf w$ is essentially a combination of SN latent score differences via Eq.(15) and (17) (also shown in (30)). Also, since the score difference $\nabla\log p_i(z_i\mid z_{{\rm pa}(i)})-\nabla\log q_i(z_i\mid z_{{\rm pa}(i)})$ is a function of $Z_{{\rm pa}(i)}$ and $Z_i$, the dimension of the image of this function will be 1 if and only if the intervened node $i$ has no parents.

• Leveraging this property, at the first step $t=1$, we search for a linear combination of the given MN environments (via $\bf w$) to emulate a single node intervention on a root node. For such a vector $\bf w$, using Eq.(15) and (17), the image of $\Delta S_X\cdot\bf w$ contains only one vector (up to scaling), which is the encoder $\bf G^\dagger$’s row corresponding to the $i$-th node where $i$ is a root node.

• Subsequently, at each step, we follow the same routine to estimate a row of the true encoder. While checking the dimension of the emulated intervention, we project $\Delta S_X\cdot\bf w$ to the nullspace of the submatrix recovered so far. This ensures that the learned encoder will be full-rank.

• Role of $\kappa$: Vector ${\bf w=[D^{-1}]}_i$ is a valid choice that makes $\Delta S_X\cdot\bf w$ correspond to a single node intervention. Then, by constructing a set $\cal W$ that contains the rows of $\bf D^{-1}$, we ensure that the procedure described above will work by an exhaustive search over $\cal W$. We note that the entries of $\bf D^{-1}$ can be found via the cofactor matrix of $\bf D$, for which the $\kappa$ denotes the maximum possible entry. For detailed derivation, please refer to lines 479-490 in Appendix A.1.

Intuition for general mixing functions: Our core technical idea is using combinations of MN interventions to construct new interventions with desired properties, e.g.,sparsity. Our intuition is that we can extend the intervention matrix in Eq.(4) to handle multiple interventional mechanisms. For instance, to represent two interventional mechanisms per node, the columns of the intervention matrix would be in $\\{0,1\\}^{2n}$. Subsequently, the goal is to find combinations of MN environments to create two different SN interventions for each node so that the problem simplifies to the known results for general transformations under two SN int/node (see references [6],[9]). However, building on this intuition to prove identifiability is challenging and is a major direction for future work.

We thank the reviewer for acknowledging the challenges of the unknown multi-node intervention setting and noting the clarity of the paper. We address the raised concerns as follows.

Noiseless transformation: The current scope of the paper cannot handle noisy transformations. We also kindly note that the closely related CRL literature (see references [3]-[10] in the paper) also considers deterministic transformations $X = g(Z)$. Our paper’s primary goal is to relax the restrictive assumption of single-node interventions. As such, we consider noisy transformations a major future direction.

Interventional regularity: We thank the reviewer for raising the need for elaboration on the interventional regularity condition. We explain its rationale and emphasize that it is not a restrictive assumption as follows.

• First, we want to clarify what we meant by "effect of an intervention.” Essentially, $\frac{\partial}{\partial z_j}\log\frac{p_i(z_i\mid z_{{\rm pa}(i)})}{q_i(z_i\mid z_{{\rm pa}(i)})}$ is the effect of intervening on node $i$ on the score associated with node $j$. Therefore, the effect in the score function is not on downstream nodes of $i$ but on the parents of $i$.

• Note that we use combinations of different multi-node environments to generate new score difference functions. Therefore, to ensure that the effect of this new “combined” intervention will be different on the $i$-th and $j$-th coordinates of the score function, we require the ratio in Eq.(12) to be not constant.

• Next, we emphasize that interventional regularity is not a restrictive assumption. In Appendix A.8., we present some sufficient conditions that make the interventional regularity valid (see Lemma 5). For instance, if we consider a linear latent causal model under a hard intervention and the distribution of the exogenous noise term remains the same after the intervention, then interventional regularity is satisfied. Therefore, interventional regularity is not a restrictive assumption.

• Furthermore, note that if there exist $k\in{\rm pa}(j)\setminus{\rm pa}(i)$, then $\log\frac{p_j(z_j\mid z_{{\rm pa}(j)})}{q_j(z_j\mid z_{{\rm pa}(j)})}$ is a function of $Z_k$, whereas the other terms in Eq.(12) are not. This implies that the ratio in Eq.(12) is not a constant function of $Z$ and again exemplifies that the interventional regularity is not a restrictive condition.

Estimating score function differences:

• Our algorithm is agnostic to the choice of score estimator, and we can adopt popular score-matching methods as mentioned in Line 325, e.g., Song et al. (2020) or Zhou et al. (2020). We also note that score function estimation is finding increasingly more applications in diffusion models, and it is an active research field. Hence, our algorithms can modularly adopt any new score estimation algorithm and benefit from advances in the score estimation literature.

• We also emphasize that our algorithm only requires score differences and does not require the score functions themselves. We conjecture that the direct estimation of score differences can be much more efficient than estimating the individual score functions, a lá direct estimation of precision difference matrices [R1]. Furthermore, density ratio estimation methods, e.g., classification-based approaches [R2], can be potentially useful for direct score difference estimation.

[R1] Jiang, Wang, and Leng. "A direct approach for sparse quadratic discriminant analysis." JMLR, 2018.

[R2] Gutmann and Aapo Hyvärinen. "Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics." JMLR, 2012.

Non-identifiability when missing an intervened node: In lines 141-143, we meant that “when a node is not intervened on, perfect identifiability is not possible in general”, i.e., without imposing additional restrictions such as structural assumptions. Our reference for non-identifiability is Proposition 5 of Squires et al. (2023). Their proof for non-identifiability only requires that the non-intervened node $i$ has at least one parent. We will add this note to the updated manuscript.

We note that the example of $A\rightarrow B$ under an intervention on only $B$ is also discussed by Remark 2 of Squires et al. (2023). Even though the graph $A\rightarrow B$ can be discovered in this specific case, we are not aware of any results for the identifiability of the latent variables. Squires et al. (2023) empirically suggest that the latent variables are not identifiable.

Additive noise models (ANM): Please refer to our general response.

Additional references: Thank you for the suggestions; we will include and discuss them in the paper. In summary, Jiang and Aragam (NeurIPS 2023) focus on recovering the latent DAG without recovering the latent variables as opposed to our complete CRL objectives. On the other hand, Kumar and Sinha (2021) focus on an entirely different setting in which the causal variables are observed, and the distributions are given in a mixture. In contrast, our CRL setting focuses on latent variables observed through the same transformation when observing distinct interventional distributions.

We thank the reviewer for finding our results crucial for extending CRL into more practical contexts, for finding our algorithm insightful, and for noting the clarity of the paper. We address the raised questions about the algorithm’s scalability as follows.

• Dimension of $X$: Our algorithm is readily scalable to arbitrarily high-dimensional observations $X$. Please see the additional experiments reported in our general response, in which we use $d=50$.

• Dimension of $Z$: Please see the additional experiments reported in our general response, in which we use $n \in \\{4, 5, 6, 7, 8\\}$ latent nodes.

• Number of environments: We note that $n$ environments are necessary in general (without further structural assumptions) for identifiability via single-node interventions (shown by Squires et al. 2023, Proposition 5). Since our unknown multi-node intervention setting subsumes the single-node interventions, we require at least $n$ environments as well.

• Number of samples: We remark that the main purpose of our algorithm is to establish a framework for identifiability via multi-node interventions. In future work, we aim to address the efficient score difference estimation, which is a separate line of work that can significantly increase the efficiency of our framework. We also kindly note that, even in the much simpler single-node intervention setting, related CRL literature uses a similar number of samples to $10^5$ that we used in our experiments for good performance (e.g., $10^5$ samples for $n=5$ nodes in Squires et al. (2023), $5 \times 10^4$ samples for $n=5$ nodes in Buchholz et al. (2023), and $5 \times 10^4$ samples for $n=5$ nodes in Varici et al. (2024)).

• Toward realistic settings: Finally, we acknowledge the need for working with more realistic datasets in the CRL field. We believe this paper serves as a significant step in this direction by removing the stringent assumption of single-node interventions, and we leave addressing realistic applications to future work.