Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The authors propose a 3-phase heuristic algorithm to learn a causal graph from interventional data using continuous optimization. Unfortunately, the paper is hard to follow. Specifically, the exact procedure should be clarified by the authors. If I understand correctly, first they fit to observational data by searching over the space of graphs using a smooth representation for the adjacency matrices. To fit to the interventional data, first, the interventional target is estimated by a heuristic approach and the contribution of these variables to the likelihood is ignored since they are set by the experiment. (there are random graph sampling stages in between that are not clear to me, please elaborate on this). This interventional scoring is done for all interventional data and is turned into a single gradient update.

The paper is hard to parse. My main concern is that, unlike the existing work which the authors compare with in the experiments, the proposed method is not a systematic approach and accordingly it is hard to reason about its use even though it performs well in the experiments. Especially given that some choices made in the algorithm design are not properly justified. Indeed, even with interventions, we do not expect to recover the full structure but only a subset of the edges correct. 

Comparisons with the other methods should be expanded into a section where these methods are detailed to showcase the methodological differences. 

The following are my detailed feedback.

"A natural application of Bayesian networks is to describe cause-effect relationships between variables."
Please distinguish Bayesian networks from the causal networks. Former do not carry causal meaning. 

A good reference to cite in addition to Peters et al. for SCMs is Pearl's 2009 Causality book. 

"Although there is no theoretical guarantee that the true causal graph can be identified in that setting, evidence so far points to that still being the case."
Please modify this statement as it sounds too vague. 

The list of contributions require knowledge of the latter sections. Please make it self contained if possible. 

"can't"->"can not"

SCM definition is not only structural equations but also talks about interventional distributions. Please see Pearl 2009.

The last line in page 2 overlaps with the page number. 

Some recent related work is missing: 

Mooij et al. "Joint Causal Inference from Multiple Contexts" JMLR'20.
Kocaoglu et al. "Characterization and Learning of Causal Graphs with Latent Variables from Soft Interventions" NeurIPS'19.
Brouillard et al. "Differentiable Causal Discovery from Interventional Data" arXiv'20.

Mooij et al. is cited but please add it in Section 3 among constraint-based inverventional learning frameworks as well.

Brouillard et al. is too recent, hence its omittance is understandable. However, it attacks the same problem considered here. I believe including it as independent discovery would help connect literature together nicely. I am not going to take this work into consideration in my evaluation since it is uploaded on arXiv only very recently.

"the methods only uses"->"the methods only use"

citing Murphy "This is different from our setting where the intervention is unknown to start with and is assumed to arise from other agents and the environment."
Murphy can handle unknown interventions as well. Moreover Mooij et al. handles unknown interventions too. 

"The set of functional parameters θi parametrizes the conditional probability distribution of Xi given its parent set Xpa(i,C), with C ∼ Ber(σ(γ)) a hypothesized configuration of the SCM’s DAG."
Can you clarify this sentence?

"During Phase 1, the functional parameters θ are trained to maximize the likelihood of randomly drawn observational data under graphs randomly drawn from our current beliefs about the edge structure."
Why do you draw synthetic data? Likelihood is typically maximized using real data at hand. It's hard to follow the exact procedure here. 

Intervention targets are predicted using a heuristic. Why not use the existing methods? I believe the computational aspect is seen as a problem but JCI by Mooij et al. should be fast enough. 

Can you convert Section 3 into a pseudo-code for the algorithm description? I believe many details are skipped and some key points of the approach is not clear by the brief text in each subsection. 

"should be taken as givens"->"should be taken as given"

In the experiments, please compare with Mooij et al. Their method should be as fast as FCI and it would be interesting to see how the results compare. 

==== After the Response by the Authors ====
======================================
Thank you for the detailed reply. For the clarifications the authors made to the algorithm description, I will increase my score. 

The authors state 
"If the scientific community had waited for deep learning to prove that it could discover the true conditional distribution of outputs given inputs, we would not have had the progress we achieved in the last two decades in AI. We believe that it is important to take into consideration all sources of evidence about the usefulness of a method, and experimental evidence is at the heart of the success of the scientific method and should not be discarded because of an established cultural habit of relying on proofs of identifiability."

Note that the objections I (R1), and I believe also R3 and R4, have are not about theoretical vs. experimental research and that the paper lacks proofs or identifiability results. It is perfectly fine to not have a theoretical understanding of a proposed algorithm. But the authors should be able to justify the choices they made in the algorithm design, and especially in light of the prior work. The main justification given by the authors both in the paper and in their rebuttal is that the algorithm performs well. I believe the paper needs an iteration to address these issues. 

The following is my detailed feedback in addition to my original review in light of the authors' response. I hope this will help the authors in improving their paper.

On fully learning the causal graph:
I suggest the authors examine and try to identify, in small graphs, what aspect of their method allows it to perform better than the existing methods such as JCI or allows it to go beyond the existing equivalence classes. Without such justification, I do not think the paper in its current form will influence future research. 

Remark on interventions having variety: 
This is not sufficient for exact recovery. Imagine intervening on the same node with different mechanisms over and over. This does not allow recovery outside of the local structure around the intervened node for most causal graphs. This also relates to the remark above. Full identifiability is always related to having variety in the intervention targets and not just in interventional mechanisms. This is why some of the datasets where the exact graph is recovered by the algorithm need a detailed investigation.

About synthetic experiments:
One explanation for full structure recovery in the synthetic experiments could be the following: The authors randomly pick one target variable to intervene on. My guess is that this randomness in the experiment design is sufficient to have diverse enough target sets for the equivalence class to shrink to a single graph. Can you verify/check this?

How many interventions do you use in the synthetic experiments? How many samples are collected per intervention? Unless I am missing something, these are not provided until page 19 but then it is not clear if these numbers are kept identical throughout the experiments. x-axis is set to be # of episodes or # of steps in most experiments whereas # of samples would be more informative.

About JCI comparison:
I did not completely understand why the authors could not run JCI in synthetic data. They say it is due to its complexity. But JCI's complexity comes from the graph degree and not from the number of samples for a small enough state space. It would be very interesting to compare what JCI learns relative to the proposed method in these synthetic experiments. This should test my hypothesis above that the random intervention target is providing enough diversity to reduce the equivalence class to one graph, which should be detected by JCI.

Inferring a Markov equivalence class from the adjacency matrix by early stopping is definitely an interesting idea and I would encourage the authors to further pursue and formalize this direction. 

Sample complexity:
The authors mention that their method is "sample-hungry". Given that the method presents significant divergence from the standard literature on causal inference that relies on conditional independence tests, which are known to require many samples, it is especially important to clearly present the number of samples used by the method. The main paper does not present the number of samples used in the synthetic experiments. These should be made explicit. 

Finally, the title and abstract still state "dependency structure discovery" and learning "Bayesian networks" whereas the authors attempt to learn causal graphs from interventions. I suggest an update to the narrative to clarify the objective of the paper.

review_title: Needs Clarifications and Justification for the Proposed Methodology

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper aims to extend the continuous optimization approach to causal discovery to handle interventional data as well as observational data. It describes a method for learning the causal structure over a set of categorical variables and reports strong empirical performance. However, no theoretical guarantee or analysis is provided, which is a significant weakness in my view. It also makes no comment on or comparison to a paper that has essentially the same goal, https://arxiv.org/pdf/2007.01754.pdf. The latter paper seems to me more principled and convincing.  

The heuristic for predicting an unknown intervention target looks very dubious to me. I would appreciate some explanation of why the target should be expected to have the biggest drop of log-likelihood. 

The description of the proposed method could be clearer; for example, it helps to provide an explicit formulation of the SGD used in the method.
review_title: A heuristic causal discovery method with apparently strong empirical performance but no theoretical analysis

final_score: rating: 6: Marginally above acceptance threshold
review_content:  Recommendation to Accept

##########################################################################
Summary:
The paper provides a novel approach in the area of structure learning for causal bayesian networks. The authors suggest an iterative method, that builds on the widely accepted do-formalism. The approach suggested fits the network before interventions, simulates the intervention on the fitted network and then again assigns a likelihood score to the network parameters

The paper concisely describes a novel algorithm used in the notoriously difficult problem of causal structure learning. The contributions are clearly stated. The accompanying expiremental reuslts suggest a competitve perfomance, especially reagarding scaling the counts of variables

I recommend to accept it, even though a few details could have been described more precisely.

1. The definition of interventions is done extremely briefly, (sec. 2), however in my opinion the choice of definitions used here would justify some accompanying examples for clarification (this would help especially to understand what is meant with "infinite intervention regimes" (sec. 4) 

2. The assumption "no control over interventions" is not clear per se, here it would help to understand what the omittance of this assumption would imply.

3. A clarification, why "the interventions can either be known or unknown", provides a relaxation of the formulation used (sec. 4.2) would be useful
review_title: Good Contribution

final_score: rating: 4: Ok but not good enough - rejection
review_content: The authors propose a method for structure learning from observational and interventional data that uses a continuous optimization method. Data is discrete-valued, there are no hidden confounders, each intervention affects only one variable, but the location of it may be unknown. A three-phase score-based, iterative procedure is proposed.
- This work considers that in each interventional dataset, only one variable is intervened on. If we do not know about the target of the intervention, it seems reasonable that we also assume that we are not aware of the number of the targets.
- Unfortunately there are no results in the paper about what the output of the algorithm will actually be. Suppose we have only few interventional datasets (which is usually the case in reality). What can we say about the output of the algorithm? It is known that in this case, Interventional Markov equivalence class is the extent of identifiability [Hauser and Bulmann, 2012]. Can we hope that the algorithm returns an element from this class?
- In the Appendix, it is mentioned that the method typically requires 500-2000 iterations and 100 interventions per iteration. This means that around 10^5 interventions are needed. Also about 10^9 samples are needed. We note that in reality for example in medical data, we usually have access to very few interventional datasets each containing about 100 samples.
- It is not clear how the method performs on a graph with no prior structure knowledge with 30 vertices (which is a number that is usually not considered large in structure learning). Seems like this order is too large for the proposed method.
- The intervention prediction step in Phase 2 sounds very heuristic and is not clear under what conditions it will work. Also, it seems that it requires strong interventions.
- Regarding preventing the algorithm from returning cyclic structures, the authors state that suppression of more than length 2 cycles was not found to be worthwhile for the increased computational expense. This simply means that the algorithm may return cyclic structures which is contradictory to the original goal.
- There are other work on learning from interventions with unknown targets, for example: [Squires et al., Permutation-Based Causal Structure Learning with Unknown Intervention Targets], or [Huang et al., Causal Discovery from Heterogeneous/Nonstationary Data].
- The definition of SCM given in the Introduction is only true for the case of causal sufficiency.
review_title: There are concerns about assumptions and complexity of the method and it is not clear how the method will actually work in reality.

Meta-review: In this paper, the authors study how to incorporate experimental data with interventions into existing pipelines for DAG learning. Mixing observational and experimental data is a well-studied problem, and it is well-known how to incorporate interventions into e.g. the likelihood function, along with theoretical guarantees and identifiability. Ultimately there was a general consensus amongst the reviewers that without additional theoretical results to advance the state of the art, the contribution of this work is limited.
Decision: Reject