Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose a greedy intervention design algorithm to optimize a collection of objectives where they show and leverage submodularity properties of these objectives, making use of several existing works in the causal discovery literature. 

main_review: The paper seems to make interesting connections to continuous optimization through submodularity. The main issue I currently have is that it is not clear to me how the number of Meek rule applications appears in this continuous optimization framework. Please comment on this. I will be happy to update my score based on this and other major comments below (positioning of the paper and additional experiments)

On positioning and presentation:
The way the paper positions itself in terms of novelty is a bit misleading especially the phrase "largely unexplored" in the abstract. There are indeed several papers on experimental design including multi-perturbation. I believe the authors should be on point and present their result as a follow-up of the style of [3,12] rather than claiming there isn't much work on multi-perturbation interventional design. 

Similarly the claim "algorithmically challenging because it leads to an exponentially large search space" is also specific to the line of work that this paper follows upon and should not be presented as a general challenge. This overall narrative is a bit misleading and makes it hard to understand and appreciate the paper's contributions in relation to the related work. 

Please clarify in the introduction that you assume no latent variables. 

The faithfulness assumed should be interventional faithfulness of Hauser and Buhlmann'12 and not only faithfulness unless I am missing something, please clarify. 

Details:
Number of unoriented edges are directly related to the size of equivalence class through the essential graph. This relation should be explained in more detail to flesh out the distinction between Obj2 and Obj3.

Notation of Obj3 is a bit confusing since there is no mention of \xi prime - already conducted experiments. Proof of lemma 1 mentions this is implicit in R but please add it as subscript to make it clear.

Proposition 3 is missing the condition that \xi1 \subseteq \xi2

Proposition 4. I believe the authors should check the details of Hauser and Buhlmann to see if there are results they can pull in. I believe Proposition 4 or a version of it must appear there in the equivalence class characterization. 

Lemma 2 is surprising and seems important enough to be called a theorem. 

It is not clear how the runtime of [25] is converted to Meek rules. This point should be clarified by the authors in the rebuttal and in the paper. Meek rules are just a subroutine to orient edges of an essential graph and why it appears as a parameter in a continuous optimization framework needs to be explained in much greater detail. (used crucially in Theorem 1, Theorem 2 and Theorem 3)

Experiments: 
A directly related method in the infinite-sample regime is the adaptive algorithm of Shanmugam et al. [30]. Please add comparisons with this algorithm. ​This is a method outside the line of work this paper is following up on and it would be good to have a comparison with a method that is not directly related.

Post-Rebuttal:
The authors clarified my concerns about how Meek rules appear in the theorem statements. They have also explained the difference between the batch setting they are interested in and the adaptive setting of [30]. Based on our exchange, I am increasing my score. 
limitations_and_societal_impact: yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper tackles the problem of causal structure learning from interventional data. Specifically, they seek a series of interventional experiments which can rapidly identify the correct causal graph, or reduce some measure of uncertainty about the true causal structure. In contrast to previous work, this paper considers the more general setting in which interventions can be made on more than one variable simultaneously (within one experiment). To select an optimal sequence of subsets on which to intervene, the authors begin by discussing 3 objectives functions that could be used to select “good” sets of interventions: two based on MI, one based on orienting edges. All objectives are grounded in existing literature. The authors propose two different algorithms to actually solve the experimental design problem. First, they propose Double Greedy Continuous. As the name implies, this method is greedy both with respect to adding interventions to the experiment sequence and with respect to adding variables to intervene on in a single interventional experiment. The authors provide strong theoretical guarantees for this method with respect to their edge-orienting objective. For the MI objective, a suitable sub-modularity property does not hold for double greedy. Instead, the authors propose a new algorithm, Separating Systems Greedy. This is greedy with respect to adding interventional experiments, but to choose sets of variables to intervene on, this algorithm uses an exhaustive search over a separating system. The authors prove guarantees relating this algorithm to their infinite data MI objective.
main_review: Originality: This paper tackles the problem of finding sequences of multi-variable interventional experiments to do causal structure learning. Few, if any, previous works have studied this exact form of the causal structure learning. The paper is strictly more general than the previous work of Agrawal et al., 2019 and Ghassami et al., 2018 in terms of the problem addressed. 

The work proposes two novel algorithms, along with a number of new theoretical insights relevant to this problem and their proposed methods. The only limitation here is that the actual algorithms suggested (particularly double greedy) are natural extensions of existing work. However, this should not overly detract from the value of this paper. 

When discussing MI as an objective for experimental design, it could be nice to cite e.g. Lindley, 1956 ‘On a measure of the information provided by an experiment’. Also, you define $\tilde{U}_{M.I.}(y, \xi; D)$ as the mutual information between y and the posterior over G. Typically the mutual information would imply an expectation over y. Perhaps it is the information gain/KL divergence from prior to posterior on G.

Quality: The submission is of high quality. The approach taken is sound, logical and well-motivated. The paper flows logically with the authors defining and breaking down the problem, before proposing solution and then analysing them theoretically. The suggested methods are well supported by theory. I haven’t checked all proofs in the appendix, but the parts I checked were good. Experimentally, the authors demonstrate performance gains over the key baseline of single-variable intervention experiments, as well as comparing their different methods. A few things that could be improved
Further discussions of limitations and trade-offs. For example, are there cases when single-perturbation experiments might be expected to suffice? What considerations should a practitioner use to decide between DSC and SSG? For example, in 264-265, it is explained that under certain conditions SSG-B may not improve with q. This idea could be bumped up to a more general discussion before/after the experiments. Similarly, it could help to simply restate the bounds on the separating system sizes from Shanmugam et al. and Lindgren et al.
Can we say anything theoretically about Objective 1 / the finite sample case?

Clarity: the paper is well written with a number of helpful illustrative diagrams (very nice for any DAG paper). The text on the images of Fig 2 are too small.

Significance: This paper tackles a significant problem, making major strides in what is achievable or considered in the literature. There are many applications for causal structure learning, gene regulatory networks, but also many others. 
limitations_and_societal_impact: I believe the authors have dealt sufficiently with societal impact. For discussion on limitations, see the main review.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies experimental design for causal structure learning.
Unlike existing works that focus on experiments with single
interventions, it focuses on the experiments that can possibly
simulnatenously intervene on multiple variables. The search space
becomes much larger because the power set of all variables has
exponential cardinality. The paper establish submodularity properties
for a two optimization objectives, which allows them to employ/adapt
existing variants of greedy algorithm to perform active causal
structure learning. The paper also establish theoretical guarantees
that shows the algorithm can achieve a constant factor of the optimal
objective value with the greedy algorithms.
main_review: The paper studies experimental design for causal structure learning.
Unlike existing works that focus on experiments with single
interventions, it focuses on the experiments that can possibly
simulnatenously intervene on multiple variables. The search space
becomes much larger because the power set of all variables has
exponential cardinality. The paper establish submodularity properties
for a two optimization objectives, which allows them to employ/adapt
existing variants of greedy algorithm to perform active causal
structure learning. The paper also establish theoretical guarantees
that shows the algorithm can achieve a constant factor of the optimal
objective value with the greedy algorithms.

The paper studies an original and very important scientific problem,
which emerges due to recent advances in gene-related studies.
Moreover, performing an efficient search over power set is a relevant
active learning question in many applications apart from causal
structure learning. It is well understood that submodularity of
objectives can facilitate this search using greedy algorithms. The key
observation is that some objectives in causal structure learning, in
particular, the mutual information and the edge-orientation objectives
indeed can exhibit such submodularity properties, which make this task
a possible task (at least theoretically).

Both the theoretical results and the empirical results in the paper
make sense. However, I have a few major questions.

One is about the choice of optimization objectives for mutual
information and edge orientations. I understand that these objectives
are chosen because of their submodularity-related properties. Are
there other reasons to focus on these objectives beyond submodularity
considerations? Suppose for a second we are only interested in single
node interventions. I wonder if they would still be the best/ideal
objectives for the task of structure learning or edge orientation.

The second question is about the actual gain of considering the
multiple-perturbation setting. While the theorems provide constant
approximation guarantees of the algorithm, I wonder if the paper could
elaborate on the related guarantee of single-node interventions. In
particular, one would wonder that, though we need fewer optimal
multiple-perturbation as in Figure 1, would it take more iterations
(applications of the Meek rules) to locate these optimal
multiple-perturbation? In other words, taking together the cost of
computing optimal multiple-perturbations and the gain of needing fewer
multiple-perturbations for learning, how much actual gain one would
obtain from considering multiple-perturbations? The paper would
benefit from such a discussion to solidify the motivation to consider
multiple-perturbations.

Finally, I am a little confused by the ``infinite sample'' nature of
the objective 2. Why would one be able to perform experiments with
infinite sample? How is the empirical studies done to achieve infinite
samples?

limitations_and_societal_impact: Yes the paper discusses the limitations in Sec 5.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers a challenging problem of designing multi-perturbation experiments for causal discovery. They focus on two objective functions and develop one algorithm for each objective. The approximation accuracy is studied by showing submodularity of the proposed algorithms. Empirical studies are used to demonstrate the superiority of the proposed algorithms over random design and single-perturbation design.
main_review:  The major strengths of this paper are: 
1.	Multiple rather than individual interventions are considered.
2.	The theoretical properties of the proposed approximated algorithms are studied through set function submodularity.

The major weaknesses are: 
1.	The theoretical property is only asymptotically correct with infinite sample size. Finite sample property is not clear. 
2.	Assumption on causal sufficiency is strong. One major advantage of using experimental data for causal discovery is weaker causal assumption. One critical assumption that people often make for observational data is causal sufficiency. However, in this paper, despite experimental data are generated, causal sufficiency is still required. Since it is very difficult to check its validity, it may limit the practical utility of the proposed method. 

======update=====

I keep my original score. 
limitations_and_societal_impact: Yes, they are mentioned.
review_title: null

Meta-review: This paper describes a methodology for causal structure learning while varying multiple variables simultaneously. Individually, the fields of structure learning, causal inference, and experiment design are well-studies areas of statistics and machine learning. The novelty of this work is bringing such ideas together to address causal structure learning. The paper makes interesting connections to submodularity to solve the problem.

The reviewers were supportive of acceptance of the paper and found numerous merits. First, the proposed approximation algorithm is analyzed theoretically using set function submodularity. This lays the foundation for further analysis and perhaps improvements. Second, the empirical results show that there are significant improvements to be found by sequential multi-perturbations in causal structure learning. There were some clarifying comments around so-called Meek rules. The authors provided clarification in their response and the associated adjustments to the paper seem straightforward. Given that the paper was found to be technically sound and potentially impactful for not only gene regulatory networks, but also for other problem domains, I agree with the reviewers and favor acceptance.

Decision: Accept (Poster)