Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning
Authors: Scott Sussex
Caroline Uhler
Andreas Krause
Venue: NeurIPS 2021 Poster (2021)
Keywords: experimental design
submodularity
causal inference
causal structure learning

Abstract: Causal structure learning is a key problem in many domains. Causal structures can be learnt by performing experiments on the system of interest. We address the largely unexplored problem of designing a batch of experiments that each simultaneously intervene on multiple variables. While potentially more informative than the commonly considered single-variable interventions, selecting such interventions is algorithmically much more challenging, due to the doubly-exponential combinatorial search space over sets of composite interventions. In this paper, we develop efficient algorithms for optimizing different objective functions quantifying the informativeness of a budget-constrained batch of experiments. By establishing novel submodularity properties of these objectives, we provide approximation guarantees for our algorithms. Our algorithms empirically perform superior to both random interventions and algorithms that only select single-variable interventions. 

Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning
Scott Sussex
Andreas Krause
Department of Computer Science
Department of Computer Science ETH Zürich Züiich,, Switzerland
ETH Zürich
Zürich, Switzerland
scott. sussex@inf ethz..ceethccc
Caroline Uhler
Laboratory for Information & Decision Systems Massachusetts Institute of Technology Cambridge, MA
Abstract
Causal structure learning is key problem in many domains. Causal structures can be learnt by performing experiments on the system of interest. We address the largely unexplored problem of designing batch of experiments that each simultaneously intervene on multiple variables. While potentially more informative than the commonly considered single-variable interventions, selecting such inter- ventions is algorithmically much more challenging, due to the wuublyexppoeental combinatorial search space over of composite interventions. In this paper, we develop efficient algorithms for optimizing different objective functions quantifying the informativeness of a budget-constrained batch of experiments. By establishing novel submodularity properties of these objectives, we provide approximation guarantees for our algorithms. Our algorithms empirically perform superior to both random interventions and algorithms that only select variable interventions.
Introduction
The problem of finding the causal relationships between a set of variables is ubiquitous throughout the sciences. For example, scientists interested in reconstructing gene regulatory networks (GRNs) of biological cells (TT). Directed Acyclic Graphs (DAGs) are a natural way to represent causal structures, with directed edge from variable X representing X being a direct cause of Y (33].
Learning the causal structure set variables is fundamentally difficult. With only observational data, in general can only identify the true DAG up set of DAGs called its Markov Equivalence Class (MEC) [35). Empirically, for sparse DAGs the size of the MEC grows exponentially in the number of nodes [17]. Identifiability perturbs a subset of the variables and then observes more samples from the system 88] 16 40). There exist various inference algorithms for learning causal structures from combination of observational
be improved by intervening
variables, meaning one
and interventional data [16] 36 40 (8 34). Here we focus on the identification of DAGs that have unobserved confounding variables.
Performing experiments is often expensive, however. Thus, we are interested in learning as much about the causal structure possible given some constraints the interventions. In this work, focus on the batched setting, where several interventions are performed in parallel. This is a natural setting in scientific domains like reconstructing GRNs. Existing works propose meaningful objective
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

b
Intervention Intervention 2
d
Figure a) We illustrate the MEC of a tree graph on 5 nodes. b) Two single-node interventions required to fully identify the true DAG. c) Only one two-node intervention is required to fully identify the true DAG, d) This MEC contains 5 DAGs, each corresponding to different root node (marked white). This is property particular to tree MECs.
functions for this batched causal structure learning problem and then give algorithms that have prov- able guarantees 3 [3 However, these works focus the setting where only single random variable an open question as to whether there exist efficient algorithms for setting, where more than one variable is perturbed in each intervention.
the perturbed per intervention.
For the task of reconstructing GRNs, it now possible for experimenters to perturb multiple genes in single cell 27 Figures| T b) and c) illustrate a specific example where a two-node intervention completely identifies a DAG half as many interventions as single-node interventions. In general, it is possible for set of q-node interventions orient up to q-times more edges in a DAG than single-node interventions (see the supplementary material for a more general example). While multi- perturbation interventions can be more informative, designing them is algorithmically challenging because leads to an exponentially larger search space: any algorithm must now select a set of sets.
Our main contribution is to provide efficient algorithms for different objective functions with accompanying performance bounds. We demonstrate empirically on both synthetic and GRN graphs that our algorithms result in greater identifiability than existing approaches that do not make use of multiple perturbations [13 40 as well as a random strategy.
We begin by introducing the notation and the objective functions considered in this work in Section 2 before reviewing related work in Section 3 In Section 4 we present our algorithms along with proofs of their performance guarantees. Finally, in Section 5 we demonstrate the superior empirical performance of our method over existing baselines both synthetic networks and data generated from models of real GRNs.
Background and Problem Statement
Causal DAGs Consider causal DAG G ([p), E) where [p] := {I....,p} is set of nodes and E is set of directed edges. Let (i,j) E iff there is an edge from node to node j. Each node i associated with a random variable X,. In the GRN example, X, would be the measurement of the gene expression level for gene i. An edge from i + would represent gene i having causal effect on the expression of gene j. The functional dependence of a random variable on its parents can be described by structural equation model (SEM).
The probability distribution over meaning each variable X; is conditionally independent of its non non-descendants given its parents [33]. From conditional independence tests one can determine the MEC G, a set of DAGs with the same conditional independancies between variables. All members of the MEC share the same undirected skeleton and colliders [35]. A collider a pair edges (i, k), (j, k) E such that (i,j), (j. E. The essential graph of G, Ess(G), is a partially directed graph, with directed edges where all members of the MEC share the same edge direction, and with undirected edges otherwise (5). Ess(G) uniquely represents the MEC of G. These MECs can be large, so seek to perform interventions on the nodes to reduce the MEC to smaller set of possible DAGs.
(X1,..., Xp) is related to G by the Markov property,
Interventions We use the term intervention to refer to a set I C [p] of perturbation targets (variables). We assume all interventions are hard interventions, meaning intervening on a set removes the incoming edges to the random variables X1 (Xi)ier and sets their joint distribution

---

to some interventional distribution p' 19] In the GRN reconstruction example this corresponds to, for example, running an experiment where we knockout all genes in set Some of our results extend easily to the alternative model of soft interventions
25 as we discuss in the supplementary material.
We use I = 2Prl to refer to the set of all possible interventions. Our goal will be to select a batch E of interventions, where & is multiset of some I. For practical reasons, we typically have constraints on the number of interventions, i.e. |5| S m and on the number of variables involved in each intervention [ I 9, AI Ç. Namely, there are at most interventions per batch and each intervention contains at most nodes. A constraint on the number of perturbations per intervention is natural in reconstructing GRNs, since perturbing too many genes in one cell will leave it unlikely to survive. We refer to the set of {8 satisfying these constraints as Gm.q. The observational distribution (no intervention) is given by 0.
For any set of interventions & and DAG G, there is a set of {-Markov equivalent DAGs. These are the set of DAGs that have the same set of conditional independencies under all / E & and under the observational distribution. This set of DAGs is no larger than the MEC of G and can similarly be characterized by an essential graph Ess (G) [16].
We will always assume that there exist no unobserved common causes of any pair of nodes in G. We also assume that the distribution of the random variables satisfies faithfulness with respect G [33
Choosing optimal interventions We seek to maximize an objective function I that quantifies our certainty in the true DAG. In general our goal is to determine
arg max F()). {ECm..
natural choice for F is given by Agrawal et al. 3]. They assume that there exist parameters 0 that determine the funetional relationships between random variables. For example, this could be the coefficients in a linear model. Given existing data D, we try to choose & that maximizes Objective 1 (Mutual Information (MI)).
(E) = EaD viG.0.s (UM.(V,;:D))
(I)
where y is the set of samples from the interventions, Ô is the current estimate of the parameters given D and G. and J &; D) is the mutual information between the posterior over G and the samples y. Each intervention produces one sample in y. The use of mutual information means the objective aims to, in expectation over all observed samples and true DAGs, minimize the entropy of the posterior distribution over DAGs. There already exist number of algorithms for determining the posterior over DAGs from observational or experimental data 40 36 16].
Infinite sample objectives Finding algorithms that optimize the MI objective is difficult because we have to account for noisy observations and limited samples. To remove this complexity, we study the limiting case of infinitely many samples per unique intervention. The constraints given by Cm..q still stipulate that there can be only unique interventions, but each intervention can be performed with an infinite number of samples. We also assume that an essential graph is already known (i.c., we have infinite observational samples and infinite samples for any experiments performed so far). For objectives with infinite samples per intervention, we treat as a set of interventions, not a multiset, since there is change in objective value for choosing an intervention twice. Consider g to be the set of interventions contained in our dataset before our current batch. In this setting, maximizing redduees to maximizing
Objective 2 (Mutual info. inf. samples (MI-x))).
(E)
log Eus SuE' (G)L,
G
GEg
where Ess (G) refers to the updated essential graph after performing interventions in &. The objec- tive aims to, on average across possible true DAGs, minimize the log of the essential graph size after performing the interventions. The derivation of this objective given in the supplementary material.
Ghassami et [3] study different objective in the infinite-sample setting. The objective seeks to, on average across possible G given the current essential graph, orient many edges as possible. Let
3

---

R(C. E') be the set of edges oriented by & if the true DAG is G, and the essential graph is given by the {'MMEC Objective 3 (Edge-orientation (EO)).
1 E (R(EE 9
(E)
GEB
The function R is computed as follows. Firstly, VI E 5, orient undirected edge i - in Ess (G) i E I j $ I or vice-versa. Secondly, execute the Meek Rules (26). which allow inferring additional edge orientations (discussed in the supplementary material) on the resulting partially directed graph. Finally, output the set of all edges oriented. Agrawal et al. (3] show that this objective is not consistent; however, this is because they fix 9 to be the MEC instead of using the most up-to-date essential graph for each batch. In the supplementary material, show that the version of the objective we work with is indeed consistent. We will drop the dependence of R on g for readability,
Below, we provide algorithms with near-optimality guarantees for Objectives 2 and 3 ing a practical algorithm for Objective
while motivat-
3 Related Work
Causality has been widely studied in machine learning 30 31 most relevant to our work.
Here we focus on prior research that
Agrawal et al. (3 and Ghassami et al. 13 give near-optimal greedy algorithms for Objectives [and respectively. Ahmaditeshnizi, Salehkaleybar, and Kiyavash (4) present dynamic programming algorithm for an adversarial version of Objective 3 optimizing for the worst case ground truth DAG in the MEC. However, all these algorithms only apply pungle-perturbution interventions. Both of these works use the submodularity of the two objectives. In this paper we address the exponentially large search space that arises when designing multi cuutti-petuurbatoon interventions, strictly harder problem.
Much existing work in experimental design for causal DAGs is focused on identifying the graph uniquely, while minimizing some cost associated with doing experiments (9 18 32 21 23 When the MEC is large and the number of experiments small, identifying the entire graph will be infeasible. Instead, one must select interventions that optimize measure of the information gained about the causal graph.
Lindgren et al. 23) show NP-hardness for selecting an intervention set of at most m interventions, with minimum number of perturbations, that completely identifies the true DAG. This, however, does not directly imply a hardness result for our problem.
Gamella and Heinze-Deml [10] propose an approach to experimental design for causal structure learning based on invariant causal prediction. While our approach has guarantees for objectives relating to either the whole graph or functions of the oriented edges, their work is specific to the problem of learning the direct causes of one variable.
Acharya et al. 1 consider testing between two candidate causal models. However, the setting differs from ours: they assume the underlying DAG is known but allow for unobserved confounding variables.
interventions has been previously studied in linear cyclic networks, with focus on parameter identification [14]. Here we focus on causal graph identification in DAGs.
Designing
4 Greedy Algorithms for Experiment Design
All of our algorithms follow the same general strategy. Like in previous works on experimental design B [3], we greedily add interventions to our intervention set. We add maximizing F(g {TH where is the currently proposed set of interventions. This greedy selection justified because our objectives are submodular, a property we define formally later. For single- perturbation experimental design, this is algorithmically simple since there are only p possible interventions. However, for purti-perturrattion interventions even selecting greedily intractable at scale since we have (z) possible interventions. Therefore provide ways to find an intervention

---

that is approximately greedy, i.e, an intervention with marginal improvement in objective that is close that of the greedy intervention.
further challenge with the greedy approach that it involves evaluating the objective, which for objectíves is a potentially exponential algorithms we give has different strategy for overcoming this.
members of an essential graph. Each of the two
In Section 4.1 we present DOUBLE GREEDY CONTINUOUS (DGC) for optimizing Objective 3 the edge-orientation objective. For greedily selecting interventions to maximize an exponential sum, we employ the stochastic continuous optimization technique of Hassani et al. [15].
we present SEPARATING SYSTEM GREEDY (SSG) for optimizing Objective MI-co. To greedily select interventions, we use the construction of separating systems (SS) 37
In Section 4.2]
32 23 to
create a smaller set of interventions to search over. Collectively, the interventions orient the graph. To handle tractably evaluating the objective, we use the idea of Ghassami et al.
the fully
[13 and Agrawal et al. to optimize an approximation of the objective constructed using a limited sample of DAGs.
To give near-optimality guarantees for these algorithms, will use two properties of the objectives: monotonicity and submodularity.
Definition 1. A set function F :V - R is monotonically increasing if for all sets J1 S I S V we
have F(1) S F(22).
Definition 2. A set function F 2V + R is submodular if for all sets I S I2 S V and all v e V we have F(1 U {u}) - F(h) 2 F(1 P(IuU(o)) - P(12).
Submodularity is natural diminishing returns property, and many strategies have been studied for optimizing submodular objectives [22]. both the above definitions, V is called the groundset, the set that choose elements from. In the pegtuueeturrbtiion problem, the groundset is just [p]. whereas in our case it is all subsets up to q nodes.
We show that DGC achieves an objective value within constant factor of the optimal intervention set on Objective 3 SSG does not achieve constant-factor guarantee, but for both infinite sample objectives we obtain lower bound on its performance.
All of our algorithms across all DAGs in the essential graph. This exists for sampling from the MEC [39] but not for essential graphs given existing interventions. In practice, find that an efficient non-uniform sampler 13 can be used to achieve strong empirical performance.
in polynomial time; however, they assume access to a uniform sampler
4.1 Optimizing the Edge-orientation Objective
In the following, develop an algorithm for maximizing Objective 3 In fact, the algorithm provide has a netr-optimality guarantee for more general form of FEO. namely
FEo(E) = == (G)) Σ w(e) R(E,G)),
GEB
where Ve, w(e)= 2 0 and YG, a(G) 2 0. The weights (G)) can be thought of as corresponding to having a non-uniform prior over the DAGs in the essential graph, whilst the weights w((e can be thought of as assigning priority to the orienting of certain edges. The inner sum above is a weighted coverage function [22] over the set of edges.
We will first show that FEo monotone submodular over groundset I. This generalizes a result by Ghassami et al. 13 who showed the same result for groundset [p] (single perturbation interventions).
Lemma 1. FEo is monotone submodular over the groundset I.
Proof. All proofs are presented in the supplementary material unless otherwise stated.
As mentioned, we cannot use a greedy search directly since the groundset I is too large. Instead, we develop an algorithm for selecting an intervention with near-maximal utility compared to the greedy choice. In particular, our strategy is to prove a submodularity result over the function F with modified domain. Consider the set function F (1) FEo U (1}) for fixed &.
5

---

Lemma 2. FEo is non-monotone submodular over the groundset [p].
The Non-monotone Stochastic Continuous Greedy (NMSCG) algorithm of Mokhtari, Hassani, and Karbasi [27] can therefore be used as subroutine to select, in expectation, an approximately greedy The algorithm uses stochastic gradient-based
intervention add an existing intervention method to optimize continuous relaxation of our objective, and then rounds the solution to obtain set of interventions. The continuous relaxation of F is the multilinear extension
f E
BO
II 2 EE
[ x4)
IEI
with constraints E S 0.0 x; S for all nodes i. The multilinear extension can be thought of as computing the expectation of (I), when input a is a vector of independent probabilities such that 2; is the probability of including node i in the intervention. The sum over I in fã and the sum over DAGs in F make computing the gradient of this objective intractable. Therefore, we compute an unbiased stochastic approximation of the gradient V f (x) by uniformly sampling DAG G from G and intervention / from the distribution specified by æ. Define
f (I, = |R(g U ()).
(4)
Mokhtari, Hassani, and Karbasi [27] show that an unbiased estimate of the gradient of f(x) can be computed by sampling G and I to approximate
i Or:
f (1)
E G.I|a
(5)
where means that if i remove it. The of stochastic gradient means that FEo can be efficiently optimized despite it being a possibly exponential sum over G.
After several gradient updates obtain vector of probabilities x that approximately maximizes fEo. To obtain an intervention I one uses a ROUND function, for example pipage rounding which, on submodular functions, has the guarantee that IE] [E (RoUND(=))) = ff) (6).
Theorem (Mokhtari, Hassani, and Karbasi (27). Let I" be the maximizer of Th NMSCG with pipage rounding, after O (p²/2/e² evaluations of achieves solution such that
E
F (1)
- (1))
p
The original result measures runtime in terms of the number of times we approximate the gradient in Equation with a single sample (in our case a single G, tuple). From Equations I and we can see that the number of gradient approximations is a constant factor of the number of evaluations of R. Hence, we measure runtime in terms number of evaluations of R. The bottleneck for evaluating R is applying the Meek Rules, which can be computed in time polynomial in p (26). Note that the NMSCG subroutine can be modified to stabilize gradient updates by the approximation
a Hessian, in which case the same guarantee can be achieved O (1 (2) 15 We use this version of NMSCG for the experiments.
Our main result now follows from the fact that selecting interventions approximately greedily will lead to an approximation guarantee due to lemmal) I
Theorem 2. Let g* E ON be the maximizer of Objective evaluations of R, achieve solution such that
DGC will, after O (m223/22e)
(1- (1-c!/a c!/e Feo(E*) -
B[FEo(E)] 2
We highlight this is a constant-factor guarantee with respect to the optimal batch of interventions. Our bound requires compute that is low order in with no dependence on q. Without even accounting for computing the possibly exponential sum in the objective, merely enumerating all possible interventions for fixed q is O(p)).
Ghassami et al. [13 give similar constant-factor guarantee for batches of perturapett
interventions = 1). Their bound is within 1 - 1 of the optimal single-perturbation batch. In the

---

Algorithm DOUBLE GREEDY CONTINU-
Algorithm 2 GREEDY(SSG)
SEPARATING
SYSTEM
OUS(DGC)
Input: essential graph G, constraints Cm.4.
Input: essential graph G, constraints Cm.qr
objective FEo
objective Foo
Init <- 0
Init I t 0
while [ S m do
S t SEPARATE(2, (),
I < ROUND(NMSCG(FEO) 9))
while [<| S m do
I'+ arg max (TU(
end while Output: a set & of interventions
5 Eu
end while
Output: a set of interventions
supplementary material, we show that the optimal multi-pertuuratiin intervention can orient up to times edges than the optimal single perturbation intervention. In Section 5|ee experimentally verify the value of multi-perturbatiion interventions by comparing DGC to the algorithm presented in Ghassami et al. 13.. If we allow for soft interventions, the 1 guarantee can also be obtained for multi-perturbation interventions. See the supplementary material for details.
Optimizing the Mutual Information Objective
We now consider an algorithm for maximizing Objective First, note that computing the sum over G and the size of U g g'eessential graphs is computationally intractable. The computation
of [Ess (G) makes Fox a nested sum over DAGs. Like Agrawal et al. (3). we optimize a computationally tractable approximation Fxc. First, uniformly sample multiset of DAGs I from G construct approximate objective
FE)
Σ
loga Ess
Eus (G)).
SuE'
GEİ
where Eis EUE' similar to lemma can also be proven for Foc.
EUE is the submultiset of & consisting of elements in Ess A submodularity result
Lemma 3. Foo is monotone submodular.
We first show that an approach similar to that used by DGC does not easily give near-optimal guarantee. Similarly to above, define (1) = FoolE U (1}) for fixed &. Proposition 1. There exists G, 9 such that F is not submodular.
Hence cannot use existing algorithms for submodular optimization to construct near-greedy interventions. We instead take a different approach. Suppose we can reduce to some set of interventions much smaller than I, such that (S) has the maximum possible objective value. obtain guarantee by greedily selecting m interventions from S. A method
Due to lemma B for constructing the set S comes from separating system constructions.
Definition 3. A q-sparse G-separating system of size N is set of interventions S = [S1, Sg... SN such that | < g and for every undirected edge (i, E there is an element S E such that exactly one of i,j is in S 32].
separating system of completely identifies the true DAG, and hence obtains the maximum possible objective value 0 without necessarily satisfying the constraints Cm.qq- As an example, in (b, we see and 2-sparse separating systems respectively.
We will make use of an algorithm SEPARATE(G,, G) which efficiently constructs a g-sparse sepa- rating system of G. Wegener (37) and Shanmugam et al. (32) give construction methods that agnostic to the structure & (it will identify any DAG with nodes). Lindgren et al. 23 give a construction method that depends the structure of G.
Since the separating system obtains the maximum objective value, we can greedily select m interven- tions from this set and obtain lower bound the objective value due to submodularity (lemma
7

---

Edge Orienaaion Objective Feo
Objective Fzo
Edge Oniettaioon Objective Fzo
3.0-
1.0
0,090
0.4
0,925
0.8
0.900
0.
0.71
SSCa (q-3)
0.875
0.
0.7
(qm3)
SSGD (q=3)
555a lm=2)
55G5 (q=3)
DGC (q=3)
SSGb [m=2)
03
DGC (q=
0.00
(c=3)
Greedy (q=1)
Rand (m=
Creedy (o=1]
0.4
0.775
Batch Size (m)
Intervention Size (q)
Batch Size (m)
f'
Proportion of Edges Oriented
4.0
1.0
0.985
Objective F
3.5
Scooe
3.0
0.500
0.7
2.0
SSCa-m (q=5)
(q-5)
0.985
558b - Iq-5)
55cb (q=5)
SSGa (q=5)
SSGD (q=5)
MI
15
Greedy (q=1)
DGC (q=5)
Rand (q=5)
Greedy (q=1)
0.5
Rand (q=5)
DGC (q=5)
(q=1)
0.31
Batch (m)
Size (m)
Batch Size (m)
5
Figure 2: a-c and give infinite sample experiments and d-e give finite samples. a) Our algorithms
(q = orient more edges than random interventions (q 3) and greedily chosen q interventions for 40, ER(0.1) graphs. b) On a fully connected graph (p=5, m=2), SSG-B does not improve as q increases. On a p 20 forest of 3 disconnected star graphs, SSG-A cannot orient the full graph as quickly as our alternative approaches (7 3). d) For finite-samples, p = 40, ER(0.1) graphs, the proposed methods (q 5) achieve greater objective value than greedy q 1 interventions. Optimizing the finite sample objective directly yields slightly greater objective value than the infinite sample approximations. e) The Fl scores for predicting the presence of each edge correspond well with the objective in d). f) For = 50 yeast subnetwork from the DREAM3 challenge, our algorithms (q 5) orient more edges the ground truth DAG than random algorithms with the same batch size.
greedy
Theorem 3. For S 1p/2], m I (S], SSG outputs & E Cm,q with objective value
(x) [p/q][logp] Fx)
m
(m log p) evaluations of R, when using SEPARATE as Shannugam et al. (32)
Increasing q does not necessarily increase (E). However, the bound we give becomes more favourable as q increases because the upper bound on |S] decreases. In practice, we run SSG Vg s and pick the intervention set with the highest objective value on Foo.
Note that SSG can also be used with similar guarantee for an analogous approximation of Fso-
5 Experiments
To evaluate our algorithms we consider three settings. Firstly, randomly generated DAGs, using infinite samples per intervention. Secondly, randomly generated DAGs with linear SEMs, using finite samples per intervention. Finally, subnetworks of GRN models, using infinite samples per inter- vention. Full details on all of our experiments can be found in the supplementary material. For code to reproduce the experiments, see htttps://githhii com/ con/ssethz/multii. http://mmmim.ppeeurattooooooooo
We consider selecting batch of experiments where only the MEC is currently known. We vary the type of random graph and the constraint set Cm.g- The following methods are compared:
Infinite samples We evaluate our algorithms using Objective 3
RAND: a baseline that for m interventions, independently and uniformly at random selects q nodes from those adjacent to at least one undirected edge;

---

GREEDY: greedily selects Lingle-eeturrattinn intervention as in Ghassami et al. 13
DGC: our stochastic optimization approach;
SSG-A: our greedy approach using the graph agnostic separating systems of Shanmugam et al. (3)
SSG-B: as above, using the graph-dependent separating system constructor Lindgren et al.
Since there are infinite samples per intervention, the exact SEM used to generate data is not relevant. We plot the mean proportion of edges identified and error bars of standard deviation over 100 repeats. Noise between repeats is due to randomness in the graph structure and in the algorithms themselves.
In Figure 2 a) we display the results for Erdös-Renyí random graphs with edge density 0.1 (ER(O.1)) and 40 nodes. To prevent trivial graphs and large runtimes, we only consider graphs with MEC sizes in the range (20, 200]. The observations given here were also found for denser Erdös-Renyí graphs and tree graphs, in addition to graphs with less nodes.
For all constraint values, all the algorithms improve greatly over RAND and GREEDY. SSG-B outperforms SSG-A, likely because the graph-sensitive separating system construction tends to return groundset of more effective interventions.
SSG-B achieves similar objective value to DGC. However, DGC behaves most robustly when the graph structure is chosen adversarially. For example, consider Figure b). Here plot the proportion of identified edges on a p 5 fully connected graph. On this graph, the separating
system construction of Lindgren et al. 23 will always return the set of all single-node interventions.
Therefore, its performance does not improve with q. whilst DGC's does. An adversarial example for SSG-A is constructed in Figure c): an MEC that consists of 3 disconnected star graphs with 7, 7 and 6 nodes. this case, DGC and SSG-B can orient most of the graph in a single intervention, whereas SSG-A will likely not contain such intervention in the separating system it constructs.
Finite samples We use linear SEMs, with weights generated uniformly in [-1,- 0..25] U [0.25, 1]. Mcasurement noise is given by the standard normal distribution. The underlying DAGs are generated in the same way as the infinite sample experiments. Before experiment selection, we obtain 800 observational samples of the system. samples algorithms. Each perturbation fixes the value of a node to 5. We approximate Objective ① using the methods of Agrawal al. (3). In particular, an initial distribution over DAGS is estimated by bootstrapping the observational data and using the techniques of Yang, Katcoff. and Uhler (40) to infer DAGs. Each DAG in the distribution is weighted proportionally to the likelihood of the observational data given the DAG and the maximum likelihood estimate of the linear model weights. The posterior over DAGs after interventions is computed by re-weighting the existing set of DAGs based on the likelihood of the combined observational and interventional data. To ensure the distribution has support near the true DAG, include all members of the true DAG's MEC in the initial distribution.
obtained for each intervention selected by
With finite samples, our methods do not have guarantees but can be adapted into practical algorithms:
GREEDY: greedily optimize Objective with single perturbation interventions (Agrawal et al. 33);
DGC-co: optimizes Objective with the summation over DAGs being weighted over the DAGs in the initial distribution;
SSG-B: optimizes FMn, greedily selecting from the separating system of Lindgren et al. 23
SSG-B-X: approximates the objective using Objective and optimizes with SSG.
For each algorithm, we record FMi of the selected interventions, over 200 repeats. In Figure d) the objective values obtained by each algorithm are shown for varying batch size and q = DGC-c0 performs worse than SSG-B and SSG-B-co, perhaps because is optimizing Fro which is not totally aligned with FMI- Between SSG-B and SSG-B-X,, there Fi as opposed to its infinite sample approximation Foo Accounting for finite samples may lead to greater improvements when there heteroscedastic noise wider range of weights.
small benefit directly optimizing
Performance on F'u corresponds closely with performance on downstream task as shown in Figure 2 e). For each algorithm, compute the posterior over DAGs given the selected interventions. Then, we independently predict the presence of each edge in the true DAG. Figure 2) plots the average Fl score for each algorithm. In finite samples, approaches outperform both RAND and GREEDY.

---

DREAM 3 networks We evaluate our algorithms under infinite samples using subgraphs of GRN models. From the "DREAM Silico Network" challenge (24), we use the 5 subgraphs with p 50 nodes. Here, we present the results for "Yeast1", which is the graph requiring the most interventions for our methods to orient. Results for the other graphs are in the supplementary material.
We compare the same algorithms as considered in the other infinite sample experiments. In Figure 2 we record the proportion of unknown edges that were oriented by each algorithm. Our methods and RAND all have intervention sizes of 5. For each method we perform 5 repeats. On Yeastl, our methods all perform similarly and outperform RAND and GREEDY. This is found for the other DREAM 3 graphs too, except on one subgraph where GREEDY performs similarly to our methods.
6 Conclusions
We presented near-optimal algorithms for causal structure learning through multi perturbation interventions. Our results make novel use of submodularity properties and separating systems to search over doubly exponential domain. Empirically, we demonstrated that these algorithms yield significant improvements over random interventions and state-of-the-art algorithms. These methods are particularly relevant genomies applications, where causal graphs are large but multiple genes can be intervened upon simultaneously.
Acknowledgments and Disclosure of Funding
This research was supported in part by the Swiss National Science Foundation, under NCCR Au- tomation, grant agreement 51NF40 180545, Caroline Uhler partially supported by NSF (DMS- 1651995), ONR 1N00014-17-1-2147 and N00014-18-1-2763, IBM, and a Simons Investigator Award.
Thank you to Raj Agrawal for helpful discussion regarding experiments.
Experiments were performed on the Leonhard cluster managed by the HPC team at ETH Zürich
References
[1] Jayadev Acharya et al. "Learning and Testing Causal Models with Interventions". In: Advances Neural Information Processing Systems. Ed. by S. Bengio et Vol. 31. Curran Associates, Inc., 2018.
[2] Britt Adamson al. "A multiplexed single-cell CRISPR screening platform enables systematic dissection of the unfolded protein response". In: Cell 167.7 (2016), pp. 1867-1882.
[3] Raj Agrawal et al. "ABCD-strategy Budgeted experimental design for targeted causal structure discovery". In: The 22nd International Conference on Artificial Intelligence and Statistics. 2019. pp. 3400-3409
[4] Ali Ahmaditeshnizi, Saber Salehkaleybar, and Negar Kiyavash. "Lazylter: A Fast Algorithm for Counting Markov Equivalent DAGS and Designing Experiments". In: International Conference Machine Learning. 2020.
[5] Steen A Andersson, David Madigan, Michael D Perlman, et al. "A characterization of Markov equivalence classes for acyclic digraphs". In: The Annals of Statistics 25.2 (1997), pp. 505-541.
[6] Gruia Calinescu et al. "Maximizing a monotone submodular function subject to matroid constraint". In: SIAM Journal on Computing 40.6 (2011), pp. 1740-1766.
[7] Atray Dixit et "Perturb-Seq: dissecting molecular circuits with scalable single-cell RNA profiling of pooled genetic screens"'. : In: Cell 167.7 (2016), pp- 1853-1866.
[8] F. Eberhardt and R. Scheines. "Interventions and causal inference" In: Philosophy of Science
74.5 (2007). pp. 981-995.
[9] Frederick Eberhardt, Clark Glymour, and Richard Scheines. "On the number of experiments sufficient and the worst case necessary identify all causal relations among N variables". In: Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence. 2005,
pp. 178-184.
[10] Juan Gamella and Christina Heinze-Deml. "Active Invariant Causal Prediction: Experiment Selection through Stability". In: arXiv preprint arXiv:2006.055 05690 (2020).
10

---

[11] Timothy S Gardner et al. "Inferring genetic networks and identifying compound mode of action via expression profiling". In: Science 301.5629 (2003), pp. 102-105.
[12] AmirEmad Ghassami, Saber Salchkaleybar, and Negar Kiyavash. "Interventional Experiment
Design for Causal Structure Learning". In: arXiv preprint 19X.v:9900.0m 9.0005 (2019).
[13] AmirEmad Ghassami al. "Budgeted experiment design for causal structure learning.. In: International Conference on Machine Learning. 2018, pp. 1724-1733.
[14] Torsten Gross and Nils Blüttgen. "Identifiability and experimental design in perturbation
studies". In: Bioinformaticc 36.Supplemnnt, (July 2020), pp. i482-i489, ISSN: 1367-4803.
DOI: 10. 1093 / wwwiinioraaiiiiiiiioooiiiiiiiite bbtaa04 eprint: https: / academic oup com/ /
pdf /aloadeerrriiiiccaarraraaeeeaa/p httpa//c......tt..oooo..oooaaaaa
pdf
URL: https: org
[15]
Hamed Hassani al. "Stochastic conditional gradient++", In: arXiv preprint 4rXiv:1902.06992
(2019).
[16]
Alain Hauser and Peter Bühlmann. "Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs". In: The Journal of Machine Learning Research 13.1 (2012), pp. 2409-2466
[17] Yangbo He, Jinzhu Jia, and Bin Yu. "Counting and exploring sizes of Markov equivalence classes of directed acyelic graphs". In: The Journal of Machine Learning Research 16.1 1 (2015),
pp. 2589-2660
[18] Antti Hyttinen, Frederick Eberhardt, and Patrik Hoyer. "Experiment selection for causal discovery". In: The Journal of Machine Learning Research 14.1 (2013), pp. 3041-3071. [19] Seiya Imoto et al. "Analysis of gene networks for drug target discovery and validation". In: Target Discovery and Validation Reviews and Protocols. Springer, 2007, pp. 33-56.
[20] Richard M Karp. "Reducibility among combinatorial problems". In: Complexity of computer
computations. Springer, 1972, pp. 85-103.
[21] Murat Kocaoglu, Alex Dimakis, and Sriram Vishwanath. "Cost-Optimal Learning of Causal Graphs". In: International Conference on Machine Learning. 2017, pp. 1884.
[22] Andreas Krause and Daniel Golovin. "Submodular Function Maximization" In: Tractability: Practical Approaches to Hard Problems. Cambridge University Press, 2014, pp. 71-104.
[23] Erik Lindgren et al. "Experimental design for cost-aware learning of causal graphs". In: Advances in Neural Information Processing Systems. 2018, pp. 5279-5289.
[24] Daniel Marbach et al. "Generating realistic in silico gene networks for performance assessment of reverse engineering methods". In: Journal of computational biology 16.2 (2009), pp. 229-
239.
[25] Florian Markowetz, Steffen Grossmann, and Rainer Spang. "Probabilistic soft interventions in conditional Gaussian networks". In: Tenth International Workshop on Artificial Intelligence and Statistics. Society for Artificial Intelligence and Statistics. 2005, pp. 214-221.
[26]
Christopher Meek. "Casual Inference and Causal Explanation with Background Knowledge". In: Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann. 1995, pp. 403-410.
[27] Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. "Stochastic conditional gradient methods: From convex minimization to submodular maximization". In: Journal of Machine Learning Research 21.105 (2020), pp. 1-49.
[28] Joris M. Mooij, Sara Magliacane, and Tom Claassen. "Joint causal inference from multiple contexts". In: Journal of Machine Learning Research 21 (2020), pp. 1-108. [29] Christos H Papadimitriou and Mihalis Yannakakis. "Optimization, approximation, and com- plexity classes". In: Journal of computer and system sciences 43.3 (1991), pp. 4400. [30] Judea Pearl. Causality. Cambridge university press, 2009.
[31] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foun- dations and learning algorithms. The MIT Press, 2017.
[32] Karthikeyan Shanmugam et al. "Learning causal graphs with small interventions". In: Advances in Neural Information Processing Systems 28 (2015), pp. 3193-3203.
[33] Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, prediction, and search. Lecture Notes in Statistics. New York: Springer, 1993. DOI: 10. 10.1007//00 11000/77-7111 1-778----611--1 2748-9

---

[34] Chandler Squires, Yuhao Wang, and Caroline Uhler. "Permutation based causal structure learning with unknown intervention targets". In: The Thirty-Sixth Conference on Uncertainty in Artificial Intelligence. 2020.
[35] Thomas Verma and Judea Pearl. "Equivalence and synthesis of causal models". In: Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence. Elsevierence Inc.
1990. pp. 255-270.
[36] Yuhao Wang et "Permutation-basee causal inference algorithms with interventions". In: Advances in Neural Information Processing Systems. 2017.
[37] Ingo Wegener. "On separating systems whose elements are sets of at most k elements". In: Discrete Mathematics 28.2 (1979), pp. 219-222.
[38] Dominic JA Welsh and Martin Powell. "An upper bound for the chromatic number of graph and its application timetabling problems". In: The Computer Journal 10.1 (1967), pp. 85-86.
[39] Marcel Wienöbst, Max Bannach, and Maciej Liškiewicz. Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs. 2020. arXiv: 2012. 09679 .LG]
[40] Karren Yang. Abigail Katcoff, and Caroline Uhler. "Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions". In: International Conference on Machine Learning. 2018.
12


Reviews:
[{"review_id": "zLaj-tMnwCX", "reviewer": "Reviewer_1uN3", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": " The major strengths of this paper are: \n1.\tMultiple rather than individual interventions are considered.\n2.\tThe theoretical properties of the proposed approximated algorithms are studied through set function submodularity.\n\nThe major weaknesses are: \n1.\tThe theoretical property is only asymptotically correct with infinite sample size. Finite sample property is not clear. \n2.\tAssumption 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. \n\n======update=====\n\nI keep my original score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, they are mentioned. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "s0JZuTiobxG", "reviewer": "Reviewer_ftg7", "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. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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)\n\nOn positioning and presentation:\nThe 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. \n\nSimilarly 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. \n\nPlease clarify in the introduction that you assume no latent variables. \n\nThe faithfulness assumed should be interventional faithfulness of Hauser and Buhlmann'12 and not only faithfulness unless I am missing something, please clarify. \n\nDetails:\nNumber 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.\n\nNotation 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.\n\nProposition 3 is missing the condition that \\xi1 \\subseteq \\xi2\n\nProposition 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. \n\nLemma 2 is surprising and seems important enough to be called a theorem. \n\nIt 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)\n\nExperiments: \nA 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.\n\nPost-Rebuttal:\nThe 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "SHSf2Xo4yB", "reviewer": "Reviewer_cWNt", "summary": "The paper studies experimental design for causal structure learning.\nUnlike existing works that focus on experiments with single\ninterventions, it focuses on the experiments that can possibly\nsimulnatenously intervene on multiple variables. The search space\nbecomes much larger because the power set of all variables has\nexponential cardinality. The paper establish submodularity properties\nfor a two optimization objectives, which allows them to employ/adapt\nexisting variants of greedy algorithm to perform active causal\nstructure learning. The paper also establish theoretical guarantees\nthat shows the algorithm can achieve a constant factor of the optimal\nobjective value with the greedy algorithms.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies experimental design for causal structure learning.\nUnlike existing works that focus on experiments with single\ninterventions, it focuses on the experiments that can possibly\nsimulnatenously intervene on multiple variables. The search space\nbecomes much larger because the power set of all variables has\nexponential cardinality. The paper establish submodularity properties\nfor a two optimization objectives, which allows them to employ/adapt\nexisting variants of greedy algorithm to perform active causal\nstructure learning. The paper also establish theoretical guarantees\nthat shows the algorithm can achieve a constant factor of the optimal\nobjective value with the greedy algorithms.\n\nThe paper studies an original and very important scientific problem,\nwhich emerges due to recent advances in gene-related studies.\nMoreover, performing an efficient search over power set is a relevant\nactive learning question in many applications apart from causal\nstructure learning. It is well understood that submodularity of\nobjectives can facilitate this search using greedy algorithms. The key\nobservation is that some objectives in causal structure learning, in\nparticular, the mutual information and the edge-orientation objectives\nindeed can exhibit such submodularity properties, which make this task\na possible task (at least theoretically).\n\nBoth the theoretical results and the empirical results in the paper\nmake sense. However, I have a few major questions.\n\nOne is about the choice of optimization objectives for mutual\ninformation and edge orientations. I understand that these objectives\nare chosen because of their submodularity-related properties. Are\nthere other reasons to focus on these objectives beyond submodularity\nconsiderations? Suppose for a second we are only interested in single\nnode interventions. I wonder if they would still be the best/ideal\nobjectives for the task of structure learning or edge orientation.\n\nThe second question is about the actual gain of considering the\nmultiple-perturbation setting. While the theorems provide constant\napproximation guarantees of the algorithm, I wonder if the paper could\nelaborate on the related guarantee of single-node interventions. In\nparticular, one would wonder that, though we need fewer optimal\nmultiple-perturbation as in Figure 1, would it take more iterations\n(applications of the Meek rules) to locate these optimal\nmultiple-perturbation? In other words, taking together the cost of\ncomputing optimal multiple-perturbations and the gain of needing fewer\nmultiple-perturbations for learning, how much actual gain one would\nobtain from considering multiple-perturbations? The paper would\nbenefit from such a discussion to solidify the motivation to consider\nmultiple-perturbations.\n\nFinally, I am a little confused by the ``infinite sample'' nature of\nthe objective 2. Why would one be able to perform experiments with\ninfinite sample? How is the empirical studies done to achieve infinite\nsamples?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes the paper discusses the limitations in Sec 5.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "DMqJ2mtKQsd", "reviewer": "Reviewer_ZpMg", "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nThe 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. \n\nWhen 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.\n\nQuality: 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\nFurther 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.\nCan we say anything theoretically about Objective 1 / the finite sample case?\n\nClarity: 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.\n\nSignificance: 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe the authors have dealt sufficiently with societal impact. For discussion on limitations, see the main review.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

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)