Permutation-based Causal Inference Algorithms with Interventions
Learning directed acyclic graphs using both observational and interventional data is now a fundamentally important problem due to recent technological developments in genomics that generate such single-cell gene expression data at a very large scale. In order to utilize this data for learning gene regulatory networks, efficient and reliable causal inference algorithms are needed that can make use of both observational and interventional data. In this paper, we present two algorithms of this type and prove that both are consistent under the faithfulness assumption. These algorithms are interventional adaptations of the Greedy SP algorithm and are the first algorithms using both observational and interventional data with consistency guarantees. Moreover, these algorithms have the advantage that they are nonparametric, which makes them useful also for analyzing non-Gaussian data. In this paper, we present these two algorithms and their consistency guarantees, and we analyze their performance on simulated data, protein signaling data, and single-cell gene expression data.
The paper describes two permutation-based causal inference algorithms that can deal with interventional data. These algorithms extend a recent hybrid causal inference algorithm, Greedy SP, which performs a greedy search on the intervention equivalence classes, similar to GIES [8], but based on permutations. Both of the proposed algorithms are shown to be consistent under faithfulness, while GIES is shown not to be consistent in general. 
Algorithm1 is computationally inefficient, so the evaluation is performed only with Algorithm 2 (IGSP) with two different types of independence criteria (linear Gaussian and kernel based). The evaluation on simulated data shows that IGSP is more consistent than GIES. Moreover, the authors apply the algorithm also to two biological datasets, a well-known benchmark dataset (Sachs et al.) and a recent dataset with gene expressions.
Quality
Pros:
- I didn’t check in depth the proofs, but to the best of my knowledge the paper seems to be technically sound. 
- It seems to provide a good theoretical analysis in the form of consistency guarantees, as well as an empirical evaluation on both simulated and real-world datasets.
- The evaluation on the perturb-seq seems to be methodologically quite good.
Cons:
- The paper doesn’t seem to discuss a possibly obvious drawback: the potentially higher order conditional independence tests may be very brittle in the finite data case.
- The evaluation compares only with GIES, while there are other related methods, e.g. some of the ones mentioned below.
- The empirical evaluation on real-world data is not very convincing, although reconstructing causal networks in these settings reliably is known to be very difficult.
- For the Sachs data, the paper seems to suggest that the consensus network proposed in the original paper is the true causal graph in the data, while it is not clear if this is the case, so I think Figure 4 is a bit misleading. Many methods have been evaluated on this dataset, so the authors could include some more comparisons, at least in the Supplement.
Clarity
Pros:
- The paper is well-organized and clearly written.
- It is quite clear how the approach is different from previous work.
- From a superficial point of view, the proofs in the Appendix seem to be quite well-written, which seems to be quite rare among the other submissions.
Cons:
- Some parts of the background could be expanded to make it more self-contained, for example the description of Greedy SP. 
- It probably sounds obvious to the authors, but maybe it would be good to point out in the beginning of the paper that the paper considers the causal sufficient case, and the case in which the intervention target is known.
- For the Sachs data, I would possibly use a Table of causal relations similar to the one in the Supplement of [13] to compare also with other methods.
Original
Pros:
- The paper seems to provide an interesting extension of Greedy SP to include interventional datasets, which allows it to be applied on some interesting real-world datasets.
Cons:
- The related work section could refer to the several constraint-based (most of them in practice hybrid) methods that have been developed recently to reconstruct causal graphs from observational and interventional datasets (even when we cannot assume causal sufficiency), for example:
-- A. Hyttinen, F. Eberhardt, and M. Järvisalo: Constraint-based Causal Discovery: Conflict Resolution with Answer Set Programming, Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, 2014.
-- Triantafillou, Sofia, and Ioannis Tsamardinos. "Constraint-based causal discovery from multiple interventions over overlapping variable sets." Journal of Machine Learning Research 16 (2015): 2147-2205.
-- Magliacane, Sara, Tom Claassen, and Joris M. Mooij. "Ancestral causal inference." Advances in Neural Information Processing Systems. 2016.
- The last paper also offers some (possibly limited) asymptotic consistency guarantees, maybe the authors could discuss its limitations with respect to their guarantees.
Significance
Pros:
- This paper and other permutation-based causal discovery approaches seem to provide a novel and interesting alternative to previous methods
Cons:
- The applicability of these methods to real-world data is reduced by the assumption that there are no latent confounders.
Typos:
- References: [13] N. Meinshausen, A. Hauser, J. M. Mooijc, -> Mooij