Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper consider the problem of learning the interventional Markov equivalence class of causal directed acyclic graph from observational and interventional data where the intervention targets are unknown and there are no unobserved variables. This problem and its variation havve been previously studied by Squires, Wang, and Uhler (2020) among others and is an important problem in the causal inference literature. The main contribution of the paper is an algorithm that is significantly faster than the permutation search algorithm (UT-IGSP) of Squires, Wang, and Uhler 2020 while also having finite sample guarantees which is lacking for UT-IGSP.  However, the paper makes slightly stronger assumptions than the UT-IGSP algorithm in specific form of interventions allowed: that the interventions must change the noise variances, and only works for linear SEMs. The authors also demonstrate the superiority of their method on rigorous synthetic and real world experiments.
main_review: # Strengths
- The paper is well written and the problem is well motivated.
- Technically, the authors largely build on the work of Ghoshal and Honorio (2019) for directly learning the difference between structural equation models (SEMs) to learn the set of intervened nodes and their parents. While Ghoshal and Honorio (2019)'s algorithm was proposed for the problem of directly estimating the difference DAG of two SEMs under the assumption that noise variances are invariant between the two linear SEMs, one of the key contributions of the paper is to recognize that the main ideas of the algorithm lends itself well to the problem of estimating the target of interventions from observational and interventional data without significant assumptions on the interventional setting.
- While the main steps of the algorithm are essentially the same as Ghoshal and Honorio (2019)'s algorithm: estimate difference of precision matrices, remove vertices for which the difference of precision matrices has all zeros, then construct an ordering over subsets of remaining vertices, and finally remove edges (in this case vertices) by estimating difference between precision matrices over subsets of vertices; the authors also leverage additional non-trivial insights from the problem like (i) some of the non-intervened targets can be estimated from the covariance matrices, (ii) the ordering can be estimated by only estimating difference of precision matrices over only sets of two nodes, and (iii) finally constructing orderings over equivalence classes, to propose an algorithm whose computational complexity is exponential only over the size of the largest equivalence class. The size of the largest equivalence class can be significantly smaller than the set of changed nodes (in the difference of precision matrices).
- Another improvement over Ghoshal and Honorio (2019) is the choice of algorithm used to estimate the difference between precision matrices which has a complexity of $O(p^3)$ instead of the $O(p^4)$ used by the former.
- The authors obtain finite sample guarantees for their method and obtain conditions for high-dimensional recovery.
- Synthetic experiments demonstrate that the proposed algorithm is significantly faster than UT-IGSP while being comparable in accuracy. Real world experiments are also insightful and demonstrate the applicability of the method even though the method was designed for linear SEMs.

# Weaknesses
1. Example 1 is incorrect. Node 2 should not be part of $J_0$ since node 2 is not part of $S_{\Delta}$.
2. The high-dimensional results are obtained under the assumption that the $\ell_{1}/\ell_{\infty}$ norm of  $\Sigma^{(1)}$  is constant which is unreasonable since the covariance matrices are generally dense (especially under the assumption that the individual SEMs are dense) and the $\ell_{1}/\ell_{\infty}$ norm is O(p). In comparison, Ghoshal and Honorio (2019)'s method depends on  $||\Sigma^{(1)}||_{\infty}$ (element-wise infinity norm).

# Other comments
- $\ell_{1}/\ell_{\infty}$ group norms are not defined and it is not clear that $||.||_{\infty}$ is the element-wise norm of a matrix.
- Line 163: the notation $an_{I}(j)$ has not been defined at this point to mean the ancestors of j in the set $I$.
limitations_and_societal_impact: Yes. The authors mention that they assume linear models and that this must be checked in real world data to ensure causal conclusions are not misinterpreted.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Given two datasets generated from two DAGs, where the second DAG is assumed to be created from the first DAG by varying the noise level in a subset of nodes (called intervened nodes) in the linear structure equation model, this paper proposed an efficient algorithm to identify the subset of intervened nodes and their parents.

The proposed algorithm consists of three steps. First, apply precision difference estimation (PDE) to identify the set of non-intervened nodes. This is feasible based on the established fact that the diagonal entry of the precision matrix difference is non-zero if and only if the corresponding node or its child receives intervention. Second, from the set of non-intervened nodes identified from step 1, form equivalent classes. Third, those equivalent classes are further processed in step 3.

The computational complexity of PDE is cubic w.r.t the number of nodes. In step 1, PDE nees to be run multiple times. Furthermore, in step 3, the complexity could be exponential. The algorithm is provided to be consistent in Theorem 1. The sample complexity bound is also established in Theorem 3.

In the experimental results, the proposed algorithm is shown to be able to recover the ground truth set of intervention targets with high precision given large number of samples. It's also much faster than its competing alternative of UT-IGSP algorithm. the proposed algorithm is also further evaluated on real-world datasets, including protein signaling data and perturb-seq gene expression data.
main_review: To the best of my knowledge, the major contribution of this work, i.e. scaling up the identification of intervened nodes given a pair of datasets, seems novel. The experiments show it runs much faster than the baseline approach UT-IGSP.

Will it be difficult to implement the soft intervention in (4)? Does this require the identification of the first DAG structure to determine its noise level?

The exponential complexity of step 3 is still worrisome. Can the authors present some edge cases where the algorithm might get stuck in this step when the size of A_l becomes too large?

In section 5.1, the precision seems much lower when the number of samples is 2000. In real-world datasets, does this mean the number of intervened samples have to be at the scale of thousands?

In the experimental section, besides UT-IGSP algorithm, is there any there baseline approach the proposed algorithm can compare against? To establish the efficiency of the proposed algorithm, it might be more convincing to compare it against at least a few benchmark algorithms.

Is the ADMM solver for the PDE in Equation (6) the most efficient algorithm? Since PDE will be used multiple times in step 1 and 2, it might be useful to explore a more efficient solver of the PDE. Cubic complexity w.r.t. the number of nodes means the algorithm cannot scale to thousands of nodes, correct?

limitations_and_societal_impact: I didn't see any negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considered estimating the intervention target nodes in the linear structural equation model with Gaussian noises. The proposed method was built upon the difference in precision matrices across observational and interventional datasets, under the soft intervention setting and sparsity assumption. The authors provided a comprehensive discussion on their algorithm including computational complexity, theoretical analysis, and sample complexity. My main concerns lie in their motivation (about intervention recovery), novelty comparing with existing literature, and utility of the soft intervention setting.
main_review: This paper focused on identifying the intervention target nodes in the linear structural equation model, by defining a soft intervention setting and leveraging the ADMM-based method proposed in B. Jiang et al (2018). The sparsity and normality assumptions are required to guarantee computational efficiency and theoretical consistency. I have several concerns regarding their motivation (about intervention recovery), novelty comparing with existing literature, and utility of the soft intervention setting. 

1. *Motivation on Intervention Recovery*: In this paper, the authors care about intervention recovery and causal discovery based on both interventional and observational datasets. I agree the latter one is one of the most important topics in causal structural learning, while why do we care about the unknown interventions? Just one sentence regarding gene-editing example was included in the current paper. The authors should discuss more as it may be the main contribution of this work.  

2. *Novelty Comparing with Existing Literature*: The main idea of this paper is to estimate the intervention nodes from the difference in precision matrices across observational and interventional datasets. There were actually many similar/related works proposed while haven't been discussed in this paper. For instance, Ghassami, AmirEmad, et al (2020) considered causal equivalence of two DAGs *also based on the precision matrices*.  Jaber, Amin, et al (2020) formulated graphical characterization to test whether two pairs of causal graphs and their corresponding interventional target sets. The authors should discuss the contributions beyond these works.

-- Ghassami, AmirEmad, et al. "Characterizing distribution equivalence and structure learning for cyclic and acyclic directed graphs." International Conference on Machine Learning. PMLR, 2020.

-- Jaber, Amin, et al. "Causal discovery from soft interventions with unknown targets: Characterization and learning." Advances in neural information processing systems 33 (2020).

3. *Utility of Soft Intervention Setting*: This paper considered a soft intervention setting that does not remove causal effects on intervention target nodes and claimed that this setting is more practical. It seems such a setting is more friendly to develop theory and related methods, but less related to utility. It will be better to elaborate more on this with some concrete examples.




limitations_and_societal_impact: The authors claimed their method is limited to linear SEMs. However, the sparsity and normality assumptions are also limitations. The authors could consider improving their motivations and enhancing their contributions, as detailed in the main review.
review_title: null

Meta-review: The paper proposes an algorithm for estimating the unknown intervention targets in a causal linear structural equation model (SEM) with Gaussian noise. The paper considers observational and interventional data generated under soft interventions.

This paper was viewed as a borderline paper.

The authors learn the set of intervened nodes (and their non-intervened parents) by building on the work of directly learning the difference directed acyclic graph between SEMs by Ghoshal and Honorio (2019). The main steps of the proposed algorithm are essentially the same as Ghoshal and Honorio (2019)'s algorithm based on estimating the difference of undirected graphical models (inverse covariance matrices). In addition to that, the authors use non-trivial insights from the problem at hand.

If accepted, I recommend to include the following clarifications and modifications:
- I will give the benefit of the doubt regarding experiments. Please try a relatively larger number of samples, so that the F1 score is closer to 100%, thus validating the high-probability exact recovery statement.
- Please assume boundedness of the product $M\_\\Sigma M\_{\\Gamma,\\Gamma^T}$, where $M\_\\Sigma = \\max( \\| \\Sigma^{(1)} \\|\_{1,\\infty} , \\| \\Sigma^{(2)} \\|\_{1,\\infty} )$ and $M\_{\\Gamma,\\Gamma^T} = \\max( \\| \\Gamma\_{S,S}^{-1} \\|\_{1,\\infty} , \\| (\\Gamma\_{S,S}^T)^{-1} \\|\_{1,\\infty} )$, where $S$ is the support of the precision matrix $(\\Sigma^{(2)})^{-1} - (\\Sigma^{(1)})^{-1}$ and $\\Gamma = \\Sigma^{(2)} \\otimes \\Sigma^{(1)}$. I agree with the authors that this change is possible.
- Please check for typos (e.g., Line 250 and Algorithm 2 uses $\\Sigma_1,\\Sigma_2$ instead of $\\Sigma^{(1)},\\Sigma^{(2)}$.)
- Please take into account the comments from the reviewers, e.g., regarding additional literature comparison, exponential complexity.

Decision: Accept (Poster)