Interventions, Where and How? Experimental Design for Causal Models at Scale
Authors: Panagiotis Tigas
Yashas Annadani
Andrew Jesson
Bernhard Schölkopf
Yarin Gal
Stefan Bauer
Venue: NeurIPS 2022 Accept (2022)
Keywords: Causal Discovery
Active Learning
Bayesian Deep Learning

Abstract: Causal discovery from observational and interventional data is challenging due to limited data and non-identifiability which introduces uncertainties in estimating the underlying structural causal model (SCM). Incorporating these uncertainties and selecting optimal experiments (interventions) to perform can help to identify the true SCM faster. Existing methods in experimental design for causal discovery from limited data either rely on linear assumptions for the SCM or select only the intervention target. In this paper, we incorporate recent advances in Bayesian causal discovery into the Bayesian optimal experimental design framework, which allows for active causal discovery of nonlinear, large SCMs, while selecting both the target and the value to intervene with. We demonstrate the performance of the proposed method on synthetic graphs (Erdos-Rènyi, Scale Free) for both linear and nonlinear SCMs as well as on the \emph{in-silico} single-cell gene regulatory network dataset, DREAM.

Interventions, Where and How? Experimental Design for Causal Models at Scale
Panagiotis Tigas" '
Yashas Annadani
2,3 Andrew Jesson
Bernhard Schölkopf
Yarin Gal
Stefan Bauer 2,4
OATML, University of Oxford
KTHH Royal Institute of Technology. Stockholm
3 Max Planck Institute for Intelligent Systems
*CIFAR Azrieli Global Scholar
Abstract
Causal discovery from observational and interventional data is challenging due limited data and non-identifiability: factors that introduce uncertainty estimating the underlying structural causal model (SCM). Selecting experiments (interven- tions) based on the uncertainty arising from both factors can expedite the identifica- tion of the SCM. Existing methods in experimental design for causal discovery from limited data either rely on linear assumptions for the SCM or select only the inter- vention target. This work incorporates recent advances in Bayesian causal discov- ery into the Bayesian optimal experimental design framework, allowing for active causal discovery of large, nonlinear SCMs while selecting both the interventional target and the value. We demonstrate the performance of the proposed method on synthetic graphs Rendi, Scale Free) for both linear and nonlinear SCMs as well as on the in-silico single-cell gene regulatory network dataset, DREAM.
Introduction
What is the structure of the protein-signaling network de- rived from a single cell? How do different habits influence the presence of discase? Such questions refer causal effects in complex systems governed by nonlinear, noisy processes. On most occasions, passive observation of such systems is insufficient to uncover the real cause-effect relationship and costly experimentation is required dis- ambiguate between competing hypotheses. As such, the design of experiments is of significant interest; an efficient experimentation protocol helps reduce the costs involved experimentation while aiding the process of produc- ing knowledge through the (closed-loop / policy-driven) scientific method (Fig. 1).
Intervention/ Observation
Inference
Mutual Information
Value intervene with
Node
Causal Experimental Design
In the language of causality (Pearl, 2009), the causal rela- tionships are represented qualitatively by a directed acyelic graph (DAG), where the nodes correspond to different vari- ables of the system of study and the edges represent the flow of information between the variables. The abstraction of DAGs allows to represent the space of possible explanations (hypotheses) for the observations hand. Representing such hypotheses as Bayesian probabilities (beliefs) allows to formalize the problem of the scientific method as one of
IntereetiionIIfferenee- Design loop Bayesian Optimal Experimental sign for Causal Discovery framework.
Figure 1:
"Equal contribution. Correspondence to ptigas@robots. ox. ac. uu, yashas. annadani @gmail. com. com. Implementation available at: https///tthbb.comyaamaaannni
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Bayesian inference, where the goal is to estimate the posterior distribution p(DAGs Observations). posterior distribution over the DAGs allows us to employ intommation-thoreee acquisition func- tions that guide experimentation towards the most informative variables for disambiguating between competing hypotheses. Such design procedures belong to the field of Bayesian Optimal Experimental Design (Lindley, 1956) for Causal Discovery (BOECD) (Tong and Koller, 2001, Murphy, 2001).
In the Bayesian Optimal Experimental Design (BOED) (Lindley, 1956) framework, one seeks the experiment that maximizes the expected information gain about some parameter(s) of interest. In causal discovery, an experiment takes the form of causal intervention, and the parameters of interest are the Structural Causal Model (SCM) and its associated DAG.
An intervention in causal model refers to the variable (or target) manipulate and the value (or strength) at which we set the variable. Hence, the design space in the case of learning causal models is the set of all subsets of the intervention targets and the possibly countably infinite set of intervention values of the chosen targets. The intervention value encapsulates important semantics in many causal inference applications. For instance, in medical applications, an intervention can correspond to the administration of different drugs and the intervention value takes the form of a dosage level for each drug. Even though the appropriate choice of this value is crucial for identifying the underlying causal model, existing work on active causal discovery focuses exclusively on selecting the intervention target (Agrawal et al., 2019, Cho et al., 2016). There, the intervention value is generally some arbitrary fixed value (like 0) which is suboptimal (see Fig. 2a). Hence, a holistic treatment of selecting the intervention value and the target in the general case of nonlinear causal models has been missing. We present a Bayesian experimental design method (CBED- pronounced "seabed") to acquire optimal intervention targets and values by performing Bayesian optimization.
Additionally, some settings call for the selection of a batch of interventions. The problem of batched interventions is computationally expensive as it requires evaluating all possible combinations of interventions. We extend CBED to the batch setting and propose two different batching strategies for tractable, Bayes optimal acquisition of both intervention targets and values. The first strategy Greedy CBED - builds up the intervention set greedily. A greedy heuristic is still near-optimal due to submodularity properties of mutual information (Krause and Guestrin, 2012, Agrawal et al., 2019, Kirsch et al.. 2019). The second strategy - Soft-CBBa stochastic sampling from a finite set of candidates, thereby significantly increasing computational efficiency while recovering the DAG structure and the parameters of the SCM as fast as the greedy strategy. This strategy is well suited for cssstac-constraained settings.
constructs a set of interventions by
Throughout this work, we make the following standard assumptions for causal discovery (Peters al., 2017):
Assumption (Causal Sufficiency). There are no hidden confounders, and all the random variables of interest are observable.
Assumption 2 (Finite Samples). There is a finite number of observational/ interventional samples available.
Assumption 3 (Nonlinear SCM with Additive Noise). The structural causal model has nonlinear conditional expectations with additive Gaussian noise. Assumption (Single Target). Each intervention is atomic and applied to a single target of the SCM.
Additionally, we assume that interventions are planned and executed in batches of size B, with fixed budget of total interventions given by Number of Batches x B. We also assume that the underlying graph is sparse, as is the case in all the real-world settings (Bengio et al., 2019, Schmidt et al., 2007). Experimental design is preferable in sparse graph settings as the number of informative intervention targets and values would be significantly less compared to dense graphs. Many nodes corresponding to a sparse graph would have very less probability of having parent sets, and hence preforming experiments with random policy is not maximally informative. Finally, we are interested in recovering the full graph G with a small number of batches. As with all causal inference tasks, the assumptions that we make above have to be carefully verified for the application of interest.
We show that our methods, Greedy-CBED and Soft-CBED, perform better than the state-of-the-an active causal discovery baselines in linear and nonlinear SCM settings. In addition, our approach achieves superior results in the real-world inspired nonlinear dataset, DREAM (Greenfield et al., 2010).
2

---

2 Background
Notation. Let V = {I....,d) d} be the vertex set of any DAG g (V. E) and Xv {Xi,..., Xa) S X be the random variables of interest indexed by V. We have an initial observational dataset D = (xv (1) ) comprised of instances Xy ~ P(X X1,..., X xx) pX Xa).
Causal Bayesian Network. A causal Bayesian network (CBN) is the pair (g, P) such that for any
W C V.
P(Xv)do(Xw x)) II VEV\
P(X, (x.,))((WW xww
where do(w)) represents hypothetical intervention on the variables Xw. 1(-) an indicator function and pug(1) denotes parents of variable X, in DAG g. A perfect intervention on any variable
X, completely removes all dependencies with its parents, i.e. P(X; xp) P(X;) thereby resulting in mutilated DAG g' (V, E (paa
Structural Causal Model. From the data generative mechanism point of view, the DAG on Xv matches set of structural equations:
X; = f((Xp 4) ViE V
(1)
where fi's are (potentially nonlinear) causal mechanisms that remain invariant when intervening on any variable X, * X,. G sss are exogenous noise variables with arbitrary distribution that are mutually independent, i.e e, e,Vi + j. (1) represents the conditional distributions in a Causal Bayesian Network and can additionally reveal the effect of interventions if the mechanisms are known (Peters al., 2017, Pearl, 2009). These equations together form the structural causal model (SCM), with an associated DAG g. Though the mechanisms I can be nonparametric in the general case, we assume that there exists a parametric approximation to these mechanisms with parameters y r. In the case of linear SCMs, y corresponds to the weights of the edges in E. In the nonlinear case, they could represent the parameters of a nonlinear function that parameterizes the mean of a Gaussian distribution.
A common form of (1) corresponds to Gaussian additive noise models (ANM)::
X; = fi(Xps (1) 76) + G, a~ ~~N(0,,37
(2)
An ANM is fully specified by a a DAG g, mechanisms, f(: 7) (f(:
parameterized by 7 = [m...., Ya], and variances, o² [oî [of...., .o]. For notational brevity, henceforth we denote 0 = (7, 0²) and all the parameters of interest with Φ = (g. 0).
Bayesian Causal Discovery. A common assumption in causal inference is that causal relations known qualitatively and can be represented by a DAG. While this qualitative information can be obtained from domain knowledge in some scenarios, it's infeasible in most applications. The goal of causal discovery is to recover the SCM and the associated DAG, given a dataset D. In general, without further assumptions about the nature of mechanisms f (e.g., linear vs. nonlinear), the true SCM may not be identifiable (Peters et al., 2012) from observational data alone. This non-identifiabiliyy is because there could be multiple DAGs (and hence multiple factorizations of P(Xv)) which explain the data equally well. Such DAGS are said to be Markov Equivalent. Interventions can improve identifiability. In addition identifiability issues, estimating the functional relationships between nodes using finite data is another source of uncertainty. Bayesian parameter estimation over the unknown SCM provides a principled way to quantify these uncertainties and obtain a posterior distribution over the SCM given observational data. An experimenter can then use the knowledge encoded by the posterior to design informative experiments that efficiently acquire interventional data to resolve unknown edge orientations and functional uncertainty.
2 ANM's can have noise variables that are non- Gaussian as well, but we restrict our exposition to the Gaussian case.
3

---

Bayesian Inference of SCMs and DAGs. The key challenge in performing Bayesian inference jointly over SCMs and DAGs is that the space of DAGS is discrete and superexponential in the number of variables (Peters et al., 2017). However, recent techniques hased on variational inference (Annadani et al., 2021, Lorch et al., 2021, Cundy et al., 2021) provide tractable and scalable way of performing posterior inference of these parameters. Given tractable distribution qu (o) which approximates the posterior p(
D), variational inference maximizes a lower bound on the (log-) evidence:
log L(bb E V
[log pD Φ)] DXL (gw (o))((((())
The key idea in these techniques is the way the variational family v for DAGs is parameterized. The variational family for the Variational Causal Network (VCN) method (Annadani et al., 2021) is autoregressive Bernoulli distribution over the adjacency matrix. They further enforce the acyclicity constraint (Zheng et al., 2018) through the prior. BCD-Nets (Cundy et al., 2021) consider distribution over node orderings through Boltzmann distribution and perform inference with Humbel-Sinkhond (Mena et al., 2018) operator. DiBS (Lorch et al., 2021) consider latent variables over entries of adjacency matrix and perform inference over these latent variables using SVGD (Liu and Wang, 2016). We demonstrate empirical results in BOECD using the DiBS model in this work because is easily extendable to nonlinear SCMs.
Bayesian Optimal Experimental Design. Bayesian Optimal Experimental Design (BOED) (Lind- ley, 1956, Chaloner and Verdinelli, 1995) is an information theoretic approach to the problem of selecting the optimal experiment to estimate any parameter 0. For BOED, the utility of the experiment & is the mutual information (MI) between the observation y and 0:
(E) A I(Y; 0 D)
E [logply E, D) log 1,,, D)]
plr19,6)p(0
The goal of BOED is to select the experiment that maximizes this objective 5- arg max, (E) Unfortunately. evaluating and optimizing this objective is challenging because of the nested expec- tations (Rainforth et al., 2018) and several estimators have been introduced (Foster et al., 2019, Kleinegesse and Gutmann, 2019) that lower bound the BOED objective which then can be combined with various optimization methods select the designs (Foster al., 2020, Ivanova et al., 2021, Foster et al., 2021, Lim et al., 2022).
A common setting, called static, fixed or batch design, is to optimize B designs . same time. The designs are then executed and the experimental outcomes are collected to update the model parameters in Bayesian fashion.
Ers at the
3 Method
The true SCM and the associated DAG d= -g, 0) over random variables Xv is matter of fact, but our belief in & is uncertain for many reasons. Primarily, it is only possible to learn the DAG up to a Markov equivalence class (MEC) from observational data D. Uncertainty also arises from 'D from being a finite sample, which we model by introducing the the random variable $ of which & is an outcome. Let Φ ~ p(ő)D) x p(D Φ)p(()) be an instance of the random variable + that sampled from our posterior over SCMs after observing the dataset D.
We would like to design an experiment to identify an intervention & = {(j, =) =)) that maximizes the information gain about 4 after observing the outcome of the intervention y P(X, xI,..., X Xa do(X; = v) = p(y E). Here, y is an instance of the random variable Y C X distributed according to the distribution specified by the mutilated true graph g' under intervention. Looking at one intervention at a time, one can formalize BOECD as gain in information about & after observing the outcome of an experiment y. The experiment & == {(j, v)} that maximizes the information gain is the experiment that maximizes the mutual information between & and Y:
arg max (I(Y;
The above objective considers taking arg max over just the discrete set of intervention targets j E V. but also over the uncountable set of intervention values Xy. While the existing works in BOECD consider only the design of intervention targets to limit the complexity (Tong and Koller, 2001, Murphy, 2001, Agrawal et al., 2019), our approach tackles both the problems. We first outline the methodology for a single design and in Section 3.2 demonstrate how to extend this single design to batch setting.

---

(a)
Seger Aud Heteraler
(b)
DOSALTIO renaan
(c)
wihkal repaoeeee
BO Iterations y
X
makaal information
0.0:
0:2
sepon
0.4
VV
0.3
0.5
0.6
Musel intormation Icr exparmmntt
Yal mRASIIEE the Misalletoraooor
Figure 2: (a) Each graph shows how the mutual information (MI) (y-axis) changes for intervening on that node (plot color matching the node color) with different values (x-axis). The SCM in this example is nonlinear SCM with Additive Gaussian noise. We information gets maximized. (b) The posterior distribution of a GP on the Mutual Information function as a response to different intervention values after four Bayesian Optimization (BO) steps. (c) For each iteration of the BO algorithm and each node we get utility function evaluation 0, (the utility being the MI in our case). Then we sample without replacement proportionally to the scores to prepare a batch (3.2).
that by intervening
node X2 with the value v² the mutual
3.1 Single Design
To maximize the objective in Equation 3, we need to (1) estimate MI for candidate interventions and (2) maximize the estimated MI by optimizing over the domain of intervention value for every candidate interventional target.
Estimating the MI. As mutual information is intractable, there are various ways to estimate depending on whether we can sample from the posterior and whether the likelihood can be evaluated (Foster et al., 2020, Poole et al., 2019, Houlsby et al., 2011). 1). Since the models we consider allow both posterior sampling and likelihood evaluation, suffices obtain an estimator which requires only likelihood evaluation and Monte Carlo approximations of the expectations. To do so, we derive an estimator similar Bayesian Active Learning by Disagreement (BALD) (Houlsby et al., 2011), 1), which considers MI as a difference of conditional entropies over the outcomes Y:
I(Y: / (G.,)). = H(Y u).. D) H(Y 4, ((..)))
log
[ply| ((.+))3I)
[log (ply I db ((.))))
P(y((..11..))
((()))
p(P(D) LPLy (...)))
where H(-) is the entropy. See Appendix B.1 for the derivation. A Monte Carlo estimator of the above equation can be used as an approximation (Appendix B.2). Equation (4) has an intuitive interpretation. assigns high mutual information to interventions that the model disagrees the most regarding the outcome. We denote the MI for single design as I(((ivv)) = I(Y; ((i,v)), D).
Selecting the Intervention Value. As shown in (3), maximizing the objective is achieved not only by selecting the intervention target but also by setting the appropriate intervention value. Although optimizing the intervention target is tractable (discrete and finite number of nodes to select from), selecting the value to intervene is usually intractable since they continuous. For any given target node j. MI is a nonlinear function over u E X; (See Fig 2) and hence solving with gradient ascent techniques only yields a local maximum. Given that MI is expensive to evaluate, we treat MI for given target node j as black-box function and obtain its maximum using Bayesian Optimization (BO) (Kushner, 1964, Zhilinskas, 1975, Močkus, 1975). BO seeks find the maximum of this function max.ex, I((C: +)}) over the entire set X2 with as few evaluations as possible. See appendix E for details.
BO typically proceeds by placing a Gaussian Process (GP) (Rasmussen, 2003) prior on the function I(fj. +)) and obtain the posterior of this function with the queried points v* = (1(1) Let the value of the mutual information queried at each optimization step t be Ú = I(L (00 }).. The posterior predictive of point (((++1) can be obtained in closed form Gaussian with mean H4 (L+1)()) (v) and variance of (L+))(u). Subscript j signifies the fact that we maintain different μ and a per intervention target and superscript represents the BO step. Querying proceeds by having an acquisition function defined on this posterior, which suggests the next point to query. For BO, we use
(T)).,
}.
5

---

an acquisition function called as the Upper Confidence Bound (UCB) (Srinivas et al., 2010) which suggests the next point to query by trading-off exploration and exploitation with hyperparameter Sg. of
1)+ o arg max, (v) +
1 1 (f()).
We run GP-UCB independently on every candidate intervention target j = fl....... points within a fixed domain 1-k, C R. Note that the domain can be chosen based on the application, for example, if we must constrain dosage levels within fixed range. Each GP is one-dimensional our setup; hence few evaluations of UCB are sufficient to get a good value maxima candidate. Further, GP-UCB for each candidate target is parallelizable, making it efficient. We finally select the design with the highest MI across the candidate intervention targets.
.......dd........ d} by querying
3.2 Batch Design
In many applications, it is desirable to select the most informative set of interventions instead of a single intervention at a time. Take, for example, a biologist entering a wet lab with a script of experiments execute. Batching experiments removes the bottleneck of waiting for experiment to finish and get analyzed until executing the next one. Given a budget per batch B which denotes the number of experiments a batch, the problem of selecting the batch then becomes arg max_ I(Y; Φ
D), such that cardinality(E) = B, where E is a set of interventions U (Je, U/) and Y denotes the random variable for the outcomes of the interventions of the batch. We denote the MI for batch design as I(3) = I(Y: D.
Greedy Algorithm. Computing the optimal solution I(=:) is computationally infeasible. How- ever, as the conditional mutual information is submodular and non-decreasing (see Appendix B 3.4 for proof), we can derive simple greedy algorithm (Algorithm that achieve at least (1 - 1/e) Re 0.64 approximation of the optimal solution (Krause and Guestrin, 2012, Nemhauser et al., 1978). We denote this strategy Greedy-CBED.
Soft Top-K. Although the greedy algorithm is tractable, it requires O(Bd) instances of GP-UCB. Kirsch et al. (2021) show that soft top-k selection strategy performs similarly to the greedy algorithm, reducing the computation requirements to O(d) runs of GP-UCB. To achieve this, we construct a finite set of candidate intervention target-value pairs by keeping all the T evaluations of GP-UCB for each node j = (1,..., d). Therefore, for d nodes, our candidate set is comprised of d x T experiments. We score each experiment this candidate set using the MI estimate. We then sample without replacement B times proportionally to the softmax of the MI scores (Algorithm 2). We denote this strategy as SoED-CBED.
3.3 Comparison with existing active causal discovery methods
We outline how approach compares with two main existing active causal discovery methods.
ABCD (Agrawal et al., 2019). The estimator MI used ABCD is based on weighted importance sampling. However, for the specific choice of the importance sampling weights used in ABCD, their MI estimator ends up with the same approximation as in our method (see Appendix B.5). Nevertheless, ABCD does not select intervention values but suboptimally sets them to fixed value. In addition, our proposed Soft-CBs Boft-CBED/ is a faster and more efficient batch strategy, especially when values also have be acquired. From this perspective, our approach is an extension of ABCD with nonlinear assumptions, value acquisition, and a soft top-k batching strategy.
AIT (Scherrer et al., 2021). AIT is an F-score- based intervention target acquisition strategy. Although it is not BOECD method, we prove here that it can be viewed as a Monte Carlo estimate of the approximation to MI when the outcomes Y are Gaussian. Nevertheless, AIT does not select intervention values like ABCD and does not have a batch strategy.
Theorem 3.1. Let Y be a Gaussiun random variable. Then the discrepancy score of Scherrer et al. (2021) is Monte Carlo estimate of an approximation to mutual information (Eq. (4)). See Appendix B.6 for proof.

---

Algorithm 1: Greedy-CBED
Algorithm 2: Soft-CBED
Input :E environment, N initial
Input :E environment, N initial observational samples, batch Size, d number of nodes, Ç softmax temperature
observational samples, batch Size, d number of nodes
b Initialize set of experiments to empty
for j 1.... do
+ Ø
> Select candidate intervention values per node j using GP-UCB Initialize 21 and of
for 1......dd
for j = 1...d do
> Select optimal intervention value per node j using GP-UCB
for = 1w.==1..77 do V2 +
arg max, (v) VBlo (v)
- arg max, I(E U ((.))))
Uj (E V21))
+ I VnJ)) Update the GP obtain μ² and of
f arg max, U3
v² + Vj.
{(t,, (tee)e)) < samples without replacement x exp (Ūg/S)
3 E ((*", w²)}
return =
= {(G.. (e),,)))
9 return
4
Related Work
Early efforts of using Bayesian Optimal Experimental Design for Causal Discovery (BOECD) can be found in the works of Murphy (2001) and Tong and Koller (2001). However, these approaches deal with simple settings like limiting the graphs to topologically ordered structures, intervening sequentially, linear models, and discrete variables.
In Cho et al. (2016) and Ness et al. (2017), BOECD was applied for learning biological networks structure. BOECD was also explored in Greenewald et al. (2019) under the assumption that undirected edges of the graph always forms a tree. More recently, ABCD framework (Agrawal et al., 2019) extended the work of Murphy (2001) and Tong and Koller (2001) in the setting where interventions can be applied in batches with continuous variables. To achieve this, they (approximately) solve the submodular problem of maximizing the batched mutual information between interventions (experiments), outcomes, and observational data, given a DAG. DAG hypotheses are sampled using DAG-bootstrap (Friedman al., 2013). Our work differs from ABCD in few ways: we work with both linear and nonlinear SCMs by using state-of-the-ar posterior models over DAGs (Lorch al., 2021), apply BO select the value intervene with, but also prepare the batch using softBALD (Kirsch et al., 2021) which is significantly faster than the greedy approximation of ABCD method.
In von Kügelgen et al. (2019) the authors proposed the use of Gaussian Processes to model the posterior DAGs and then use BO to identify the value intervene with, however, this method was not shown to be scalable for larger than bivariate graphs since they rely on multi-dimensional Gaussian Processes for modeling the conditional distributions.
new body of work has emerged in the field of differentiable causal discovery, where the problem of finding the structure, usually from observational data, is solved with gradient ascent and functional approximators, like neural networks (Zheng et al., 2018, Ke et al., 2019, Brouillard et al., 2020, Bengio et al., 2019). In recent works (Cundy et al., 2021, Lorch al., 2021, Annadani et al., 2021), the authors proposed a variational approximation of the posterior over the DAGs which allowed for modeling distribution rather than point estimate of the DAG that best explains the observational data D. Such work can be used to replace DAG-bootstrap (Friedman et al., 2013), allowing for the modeling of posterior distributions with greater support.
Besides the BOECD-based approaches, a few active causal learning works have been proposed (He and Geng, 2008, Gamella and Heinze-Deml, 2020, Scherrer et al., 2021, Shanmugam et al., 2015, Squires al., 2020, Kocaoglu et al., 2017). Active ICP (Gamella and Heinze-Deml, 2020) uses ICP (Peters et al., 2016) for causal learning while using active policy to select the target, however,
7

---

(8)
(c)
Erdos Renyl D=50
191
Interventional samples
Scale Free D=50
ESID
Interventional samples GP-UCB
BonCBED
Sample
CBED GP-UCB
Figure Results the E-SID metric (100 seeds, with standard error of the shaded) for 50 variables involving nonlinear functional relationships and additive Gaussian noise. (a) We show Soft-CBED with GP-UCB value selection strategy significantly outperforms the baselines. (b) We isolate the effect of the value selection strategy. We show that intervening with fixed value and sampling from the support of data both perform worse than having optimizer like GP-UCB (c) we compare non- nat-btch (CBED) batch-basee acquisition functions (Greedy-CHB) CBED, Boft-CBED) experiments, we use DiBS (Lorch et al., 2021) posterior model.
can see, Soft-CBED performs as well as Greedy- CBED. For all
this work is not applicable in the setting where the full graph needs to be recovered. In Zhang et al. (2021), the authors propose an active learning method to the problem of identifying the interventions that push dynamical causal network towards a desired state. A few approaches tackle the problem of actively acquiring interventional data orient edges of a skeletal graph (Shanmugam et al., 2015, Squires et al., 2020, Kocaoglu et al., 2017). Closer to our proposal belongs AIT (Scherrer et al., 1021), which uses a neural network-based posterior model over the graphs but evaluates the F-score to select the interventions.
Experiments
We evaluate the performance of our method on synthetic and real-world causal experimental design
problems and a range baselines. We aim to investigate the following aspects empirically: (1)
competitiveness of the overall proposed strategies of Greedy-CBED and Soft-CEe Roft-CBED at scale (50
nodes) on synthetic datasets; (2) performance of the value acquisition strategy based on GP-UCB; and (3) performance of the proposed approach real-world inspired dataset.
5.1 Acquisition Functions
Random. Random baseline acquires interventional targets at random.
AIT softAIT. active intervention targeting (AIT) (Scherrer et al., 2021) uses f-score based acquisition strategy to select the intervention targets. See appendix B.6 for more details, Since the original proposed approach does not consider a batch setting, introduce a variant that augments AIT with the proposed soft batching, as described section 3.2.
CBED/ / Greedy CBED SoftCBED. These are the Monte Carlo estimates of MI, described section CBED selects a single intervention (target and value) that maximizes the MI and this intervention is applied for the whole batch. In Greedy-CBED the batch is built up in greedy fashion selecting the target, value pairs one at a time (Algorithm 1). Soft-CBED is sampling (target, value) pairs proportionally to the MI scores select batch, as described in section 3.2 and Algorithm 2.

---

5.2 Value Selection Strategies
This value selection strategy assumes setting the value of the intervention to fixed value. In the experiments, we fixed the value to O. Sample-Dist: This value selection strategy samples from the support of the observational data. GP-UCB: This strategy uses the proposed GP-UCB Bayesian optimization strategy to select the value that maximizes MI.
Fixed:
5.3 Tasks
Synthetic Graphs. In this setting, we generate Erdōs-Rény' (Erdós and Rényi, 1959) (ER) and Scale-Free (SF) graphs (Barabási and Albert, 1999) of size 20 and 50. For linear SCMs, we sample the edge weights " uniformly at random. For the nonlinear SCM, parameterize each variable to be a Gaussian whose mean a nonlinear function of its parents. We model the nonlinear function with neural network. In all settings, set noise variance o² 0.1. For both types of graphs, set the expected number of edges per vertex to 1. We provide more details about the experiments in appendix D.1.
Single-Cor Cell Protein-Shie DrineiinSignaaling Network. The DREAM family of benchmarks (Greenfield et al., 2010) are designed to evaluate causal discovery algorithms of the regulatory networks of a single cell. A set of ODEs and SDEs generates the dataset, simulating the reverse-engineered networks of single cells. We use GeneNetweaver (Schaffter et al., 2011) to simulate the steady-state wind-type expression and single-gen gene knockouts. Refer to appendix D.2 for the exact settings.
5.4 Metrics
Defined the expected structural hamming distance between samples from the posterior model over graphs and the true graph E-SHD == Eg SHD g)]
E-SHD:
E-SID: As the SHD is agnostic to the notion of intervention, (Peters and Bühlmann, 2015) proposed the expected structural interventional distance (E-SID) which quantifies the differences between graphs with respect to the causal inference statements and interventional distributions.
AUROC: The area under the receiver operating characteristic curve of the binary classification task of predicting the presence/ absence of all edges.
The area under the precision-recall curve of the binary classification task of predicting the presence/ absence of all edges.
AUPRC:
6
Results
For cach of the acquisition objectives and datasets, we present the mean and standard error of the expected structural ham- ming distance E-SHD, expected structural interventional dis- tance E-SID (Peters and Bühlmann, 2015), area under the re- ceiver operating characteristic curve AUROC and area under the precision-ree -ecalll curve AUPRC. We evaluate these metrics as function of the number of acquired interventional samples (or experiments), which helps quantitatively compare different acquisition strategies. Apart from E-SID, we relegate results with other metrics to the appendix I.
Table Performance comparison be- tween different value selection and batch strategies for CBED. Experiments performed using AMD EPYC 7662 64-Cor CPU and Tesla V100 GPU.
Strategy
Value
Batch
Runtime(s)
Greedy
32.56
Fixed
Soft
6.42
On the synthetic graphs (Figure 3(a)), we can see that for ER and SF graphs with 50D variables and nonlinear functional relationships, the proposed approach based on soft top-k to select batch with GP-UCB outperforms all the baselines in terms of the E-SID metric. On the other hand, AIT alone does not converge to the ground truth graph fast even after combining with the proposed value acquisition, but when further augmented with the proposed soft strategy, the sofAIT recovers the ground truth causal graph upto 4 times faster and performs competitively to Soft-CBED, We observe similar performance across other metrics as well. In addition, we found this trend to hold for 20 variables and linear models. Full results are presented in the appendix I.
Greedy 284.98
GP-UCB
Soft
24.17

---

Ecoli1
Ecoli2
Yeast1
Yeast2
2.00
204
140
Insevvnnional samples
SCTAIT
Random
SonCBED (ours)
Figure 4: Comparison of acquisition functions on DREAM dataset, for 50 dimensions and batch size 10 on E-SID| metric (6 seeds, with standard error of the mean).
Next, we examine the importance of having value selection strategy for active causal discovery. We use the MI estimator in Equation 4; moreover, we test the proposed GP-UCB with two heuristics - the fixed value strategy and sampling values from the support. As we can see in Figure 3(b), selecting the value using GP-UCB clearly benefits the causal discovery process. We expect this finding as the mutual information is not constant with respect to the intervened value. To make this point clear, we demonstrate in the appendix G the influence of the value in a simple two variables graph. In addition, we note that naively sampling from the support of the observed dataset performs worse than fixing the value to O. We hypothesize that this is due to lower epistemic uncertainty in the high density regions of the support, hinting that these regions might be less informative.
In order to further understand how the soft batch strategy compares with other batch selection strate- gies, we compare the results of that Greedy-CBED and Soft-CBED give very similar results overall. While Greedy-CBED is optimal under certain conditions (Kirsch et al., 2019), Soft-CBED remains competitive and has the advantage that the batch can be selected in one-shot manner. This is also evident from the runtime performance of both these batching strategies in Table 1. Both these batch selection strategies perform significantly better than selecting one intervention target/value pair, and executing them B times (CBED).
with Greedy-CBED and CBED. We observe (Figure 3()))
Finally, on the DREAM task, we see that our method outperforms softAIT and random baselines on the E-SID metric (see Figure 4). In these experiments, since the intervention is emulating the gene knockout setting, we only use the fixed value strategy, with value of 0.0. Although random baseline still remains a competitive choice, in certain settings, Soft-CBED objective is significantly better (Ecoli1, Ecoli2 datasets).
7 Summary and Conclusions
This paper studies the problem of efficiently selecting the Bayes optimal experiments to discover causal models. Our proposed framework simultaneously answers the questions of where and how to intervene in a batched setting. We present Bayesian optimization strategy to acquire interventional targets and values. Further, we propose two different batching strategies: one based on greedy selection and the other based soft top-k selection. The proposed methodology for selecting intervention target-value pairs in a batched setting provides superior performance over the state-of- the-art for causal models up to 50l) variables. We validate this using synthetic datasets and using real-world inspired datasets of single-cell regulatory networks, showing the potential impact on areas like biology and other experimental sciences.
Acknowledgments and Disclosure of Funding
We would like to thank Nino Scherrer, Tom Rainforth, Desi R. Ivanova and all anonymous reviewers for sharing their valuable feedback and insights. Panagiotis Tigas is supported by the UK EPSRC CDT in Autonomous Intelligent Machines and Systems (grant reference EP/9011897/1). We are grateful for compute from the Berzelius Cluster and the Swedish National Supercomputer Centre.
10

---

References
Raj Agrawal, Chandler Squires, Karren Yang. Karthikeyan Shanmugam, and Caroline Uhler. Abed- strategy: Budgeted experimental design for targeted causal structure discovery. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3400-3409 3409. PMLR, 2019.
Yashas Annadani, Jonas Rothfuss, Alexandre Lacoste, Nino Scherrer, Anirudh Goyal, Yoshua Bengio, and Stefan Bauer. Variational causal networks: Approximate bayesian inference over causal structures. arXiv preprint arXiv:2106.07635 2021.
Albert-LászIó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
Vladimir Batagelj and Ulrik Brandes, Efficient generation of large random networks. Physical Review E, 71(3):036113, 2005.
Yoshua Bengio, Tristan Deleu, Nasim Rahaman, Rosemary Ke, Sébastien Lachapelle, Olexa Bilaniuk, Anirudh Goyal, and Christopher Pal. A teeaa-rransfer objective for learning to disentangle causal mechanisms. arXiv preprint VrXiv:/901..09// 2019.
Philippe Brouillard, Sébastien I Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien, and Alexandre Drouin. Differentiable causal discovery from interventional data. arXiv preprint arXiv:2007.01754, 2020.
Kathryn Chaloner and Isabella Verdinelli. Bayesian experimental design: A review. Staristical Science, pages 273-304, 1995.
Hyunghoon Cho, Bonnie Berger, and Jian Peng. Reconstructing causal biological networks through active learning. PloS one, 11(3):e110611, 2016.
Chris Cundy, Aditya Grover, and Stefano Ermon. Bed nets: Scalable variational approaches for bayesian causal discovery. Advances in Neural Information Processing Systems, 34, 2021.
P Erdós and A Rényi. On random graphs i. publicationes mathematicae (debrecen). 1959.
Adam Foster, Martin Jankowiak, Eli Bingham, Paul Horsfall. Yee Whye Teh, Tom Rainforth, and Noah Goodman. Variational bayesian optimal experimental design. arXiv preprint arXiv:1903.05480. 2019.
Adam Foster, Martin Jankowiak, Matthew O' O'Meara, Yee Whye Teh, and Tom Rainforth. A uni- fied stochastic gradient approach to designing bayesian-optimal experiments. In International Conference on Artificial Intelligence and Statistics, pages 2959-2969. PMLR, 2020.
Adam Foster, Desi R Ivanova, Ilyas Malik, and Tom Rainforth. Deep adaptive design: Amortizing sequential bayesian experimental design. arXiv preprint arXivv2103.02433, 2021.
Nir Friedman, Moises Goldszmidt, and Abraham Wyner. Data analysis with bayesian networks: A
bootstrap approach. arXiv preprint arXiv: 2013.
Juan L Gamella and Christina Heinze-Deml. Active invariant causal prediction: Experiment selection through stability. arXiv preprint arXiv:2006.056900 2020.
Kristjan Greenewald, Dmitriy Katz, Karthikeyan Shanmugam, Sara Magliacane, Murat Kocaoglu, Enric Boix Adsera, and Guy Bresler. Sample efficient active learning of causal trees. Advances in Neural Information Processing Systems, 32, 2019.
Alex Greenfield, Aviv Madar, Harry Ostrer, and Richard Bonneau. Dream4: Combining genetic and dynamic information to identify biological networks and dynamical models. PloS one, 5(10): e13397, 2010.
Yang-Bo Bo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9(Nov):2523 25477, 2008
Neil Houlsby, Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classification and preference learning. arXiv preprint arXiv:1112.5745 2011.

---

Desi R Ivanova, Adam Foster, Steven Kleinegesse, Michael U Gutmann, and Thomas Rainforth. Implicit deep adaptive design: policy-based experimental design without likelihoods. Advances in Neural Information Processing Systems, 01125555-25799 2021.
Nan Rosemary Ke, Olexa Bilaniuk, Anirudh Goyal, Stefan Bauer, Hugo Larochelle, Bernhard Schölkopf. Michael C Mozer, Chris Pal, and Yoshua Bengio. Learning neural causal models from unknown interventions. arXiv preprint 1XX::1910000107.. 2019.
Andreas Kirsch, Joost Van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. Advances in neural information processing systems, 32:7026-7037, 2019.
Andreas Kirsch, Sebastian Farquhar, and Yarin Gal. A simple baseline for batch active learning with stochastic acquisition functions. arXiv preprint arXiv:2 20059, 2021.
Steven Kleinegesse and Michael U Gutmann. Efficient bayesian experimental design for implicit models. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 476-485. PMLR, 2019.
Murat Kocaoglu, Alex Dimakis, and Sriram Vishwanath. Cost-optimal learning of causal graphs. In International Conference Machine Learning, pages 1875-1884. PMLR, 2017.
Andreas Krause and Carlos Guestrin. Near-optimal nonmyopic value of information in graphical models. arXiv preprint 1rXiv:1207.1394, 2012.
Harold Kushner. A new method of locating the maximum point an arbitrary multipeak curve in the presence of noise. 1964.
Vincent Lim, Ellen Novoseller, Jeffrey Ichnowski. Huang Huang, and Ken Goldberg. Policy- based bayesian experimental design for non-differene confeifeernttaale implicit models. arXiv preprint MrXiv:2203.04272. 2022.
Dennis V Lindley. On measure of the information provided by an experiment. The Annals of Mathematical Statisties, pages 986-1005, 1956.
Qiang Liu and Dilin Wang. Stein variational gradient descent: A general purpose bayesian inference algorithm. arXiv preprint arXiv: 04007,, 2016.
Lars Lorch, Jonas Rothfuss, Bernhard Schölkopf, and Andreas Krause. Dibs: Differentiable bayesian structure learning. arXiv preprint 27Xfv:2105.11839, 2021.
Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permutations with gumbel- gumbel-sinkhom networks. arXiv preprint arXiv: 2018.
Jonas Močkus. On bayesian methods for seeking the extremum. In Optimization techniques IFIP technical conference, pages 400-404. Springer, 1975.
Kevin P Murphy. Active learning of causal bayes net structure. 2001.
George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming, 14(1):265-294, 1978.
Robert Osazuwa Ness, Karen Sachs, Parag Mallick, and Olga Vitek. A bayesian active learning experimental design for inferring signaling networks. In International Conference on Research in Computational Molecular Biology, pages 134-156. Springer, 2017.
Judea Pearl. Causality. Cambridge university press, 2009.
Jonas Peters and Peter Bühlmann. Structural intervention distance for evaluating causal graphs.
Neural computation, 27(3)771-799, 2015.
Jonas Peters, Joris Mooij, Dominik Janzing, and Bernhard Schölkopf. Identifiability of causal graphs using functional models. arXiv preprint 172.5:1202.3757, 2012.
12

---

Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society. Series B (Statistical Methodology), pages 947-1012, 2016.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. The MIT Press, 2017.
Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On variational bounds of mutual information. In International Conference on Machine Learning, pages 5171- 5180. PMLR, 2019.
Tom Rainforth, Rob Cornish, Hongseok Yang, Andrew Warrington, and Frank Wood. On nesting monte carlo estimators. In International Conference on Machine Learning, pages 4267-4276. PMLR, 2018
Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer school on machine learning, pages 63-71. Springer, 2003.
Karen Sachs, Omar Perez, Dana Pe' er, Douglas Lauffenburger, and Garry P Nolan. Causal protein- signaling networks derived from multiparameter single-cell data. Science, 3085572)))333335559 2005.
Thomas Schaffter, Daniel Marbach, and Dario Floreano. Genenetweaver: in silico benchmark generation and performance profiling of network inference methods. Bieinformatics, 27(16): 2263-2270, 2011.
Nino Scherrer, Olexa Bilaniuk, Yashas Annadani, Anirudh Goyal. Patrick Schwab, Bernhard Schölkopf, Michael C Mozer, Yoshua Bengio, Stefan Bauer, and Nan Rosemary Ke. Learn- ing neural causal models with active interventions. arXiv preprint (xXi:22009002299 2021.
Mark Schmidt, Alexandru Niculescu-Mizil, Kevin Murphy, al. Learning graphical model structure using Il-regularization paths. In AAAI, volume 7, pages 1278-1283, 2007.
Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. Learning causal graphs with small interventions. Advances in Neural Information Processing Systems, 28, 2015.
Chandler Squires, Sara Magliacane, Kristjan Greenewald, Dmitriy Katz, Murat Kocaoglu, and Karthikeyan Shanmugam. Active structure learning of causal dags via directed clique trees. Advances in Neural Information Processing Systems, 33:21500-21511, 2020.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias W Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In ICMI. 2010.
Scott Sussex, Andreas Krause, and Caroline Uhler. Near-optimal multi multi-perturbation experimental design for causal structure learning. arXiv preprint 1rxhv:2105.40224 2021.
MTCAJ Thomas and A Thomas Joy. Elements of information theory. Wiley-Interscience,, 2006.
Simon Tong and Daphne Koller, Active learning for structure in bayesian networks. International joint conference on artificial intelligence, volume 17, pages 863-869, Citeseer, 2001.
Julius von Kügelgen, Paul K Rubenstein. Bernhard Schölkopf, and Adrian Weller. Optimal exper- imental design via bayesian optimization: active causal structure learning for gaussian process networks. arXiv preprint arXiv: 19 /9.03966, 2019..
Jiaqi Zhang, Chandler Squires, and Caroline Uhler. Matching desired causal state via shift interventions. Advances in Neural Information Processing Systems, 34: 199339 2021.
Xun Zheng, Bryon Aragam, Pradeep Ravikumar, and Eric P Xing. Dags with no tears: Continuous optimization for structure learning. arXiv preprint 18Xiv: 2018.
AG Zhilinskas. Single-step bayesian search method for extremum of functions of single variable. Cybernetics, 11(1):100-166 1975.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See end of Section 1. Our limitations arise from the fact that the proposed methodology and conclusion hold
when the assumptions laid out are satisfied.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Negative societal impact is discussed appendix and will added to the extra page of the camera ready after the reviewing process.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full assumptions of all theoretical results? [Yes] The assump- tions are laid out in Introduction as well as in Theorem 3.1. (b) Did you include complete proofs of all theoretical results? [Yes] The proofs are in Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URLJ? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix D.1, D.2 and H
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Figure 3 and 4.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] Please check appendix K for details.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] Please check appendix L for details.
(c) Did you include any new assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're
using/curating? [N/A] Data are simulated.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [No] Data are simulated.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "pmn1h65hayw", "reviewer": "Reviewer_L9rC", "summary": "This paper proposes to solve the problem of causal discovery through an experimental design method which selects interventions based on the mutual information between an intervention and the SCM. As evaluating the mutual information in closed form is not possible, the authors propose to use a BO algorithm to identify its maximum which corresponds to the experiment that should be evaluated next. The authors additionally extend the method to cases in which the experimenter wishes to select a batch of data points.", "questions": "See section above.", "limitations": "Yes, this is discussed in the supplement. I cannot identify additional potential negative societal impact for this work.\n\n\n\n\n\n", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall I think the problem the authors are addressing is important. However, in terms of novelty, this paper seems to be an extended and detailed version of [42] where all the main ideas were already presented. One important difference is in the selection of the intervention value together with the intervention set. It would be great if the authors could provide a list of contributions to highlight the novelty of the paper. A list of detailed comments and questions is given below.\n\n**Background section.** Even though I am very familiar with the topic discussed and the notation generally used in causality, I found the background section difficult. I believe this is due to the missing definitions and typos. \n- Line 106-108 is confusing because of the typos. Do you need a $i$ for $f$, $\\gamma$ and $\\sigma$? Is $\\theta$ a collection of these parameters for all $i$’s?\n- In general, causal discovery refers to the problem of learning the DAG and not the functional relationships. While both are connected in this paper you seem to be addressing these two problems jointly. Is my understanding correct? Can you clarify this point?\n- The notation is a bit imprecise and a few things are not defined in section 2. For instance E at line 85. In addition, you need to define what you mean with the do operator and what $x_w$ is. What are $\\phi$ and $\\Phi$ at line 127? The parameters of the posterior distribution on the SCM (which was also not introduced)? \n- What is VCN?\n- First formula after line 89, typos in the parenthesis I guess it should be $do(X_w = x_w)$. Same for parenthesis in Eq 1.\n- Add at least one reference for the background section, for instance when you define SCM. SCM generally refers to $(V, U, F, P(U))$ (U are the exogenous variables). The SCM is associated with a DAG. \n- Line 106 -> $f_i$\n- Provide at least one reference for the definition of mutual information. It seems to me that the first terms should only be conditioned on D.\n\n**Method section.** \n- Clarify if it is possible to observe all variables after implementing an intervention. Is $Y = V\\backslash X_j$?\n- How is the prior on $\\Phi$ defined? This is the joint prior distribution on the graph and the parameters of the functional relationships and the noise variances? This is never explicitly stated. \n- Even though there exists a discrete set of intervention variables that we can manipulate (especially given Assumption 4) the number could be very large depending on the size of the graph. I don’t see how this makes the method scalable.\n- I think you should compare finding the optimum of the MI with BO with a grid approach that finds the optimum by numerically evaluating the function MI for every j on a set of points. I would be interested in seeing what is the reduction in terms of function evaluations that you get with BO.\n \n\n**General comments.** \n- Assumption 4. With target to you refer to the intervened variable? Where is this assumption used? What is preventing you from doing interventions on more than one variable? Is it cause exploring interventions on all subset of variables would make the approach less scalable?\n- Assumption 3. Where is this assumption used?  Is this assumed to be able to write the likelihood?\nIn general it is not clear why and where these assumptions are needed.\n- The authors speak about causal discovery at scale. However, the approach presented requires enumerating all possible DAGs on which the prior needs to be defined. How is this problem addressed?\n- I guess selecting the intervention level is relevant when the intervened variables are continuous. However this is not stated anywhere in the paper. \n- I am confused about the use of observational and interventional data. While the observational data are used to compute (4) (via DiBS?) how are the interventional data collected sequentially used? Are these just included in $\\mathcal{D}$? The authors should clarify how exactly $\\mathcal{D}$ is used in the computation of (4) and how the interventional data are treated.\n- Are Alg 1 and 2 just giving one step of the overall algorithm? For how many steps is this repeated? I could not find this mentioned for the experiments presented.\n- Regarding scalability, as mentioned above, it would be great if the authors could clarify what makes this method scalable with respect to the existing ones. The fact that the experiments are on graphs with a large number of nodes is great but is the capability of dealing with a large number of nodes a feature of the method or of the implementation?\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WPPcGzM-0p", "reviewer": "Reviewer_3PzT", "summary": "The paper proposes a Bayesian approach to learning causal relationships from a mix of observational and interventional data. Compared to existing approaches, the proposed method can cope with the nonlinearity of the causal relationships and can select both target and value to intervene with to facilitate more efficient learning.", "questions": "I don't have additional questions other than my concerns expressed in the weakness section.", "limitations": "It is not clear whether the authors have sufficiently discussed the limitations of the paper. Assumptions such as causal sufficiency may be considered as limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The paper tackles a long-standing problem in causal discovery. Learning from a mix of observational and interventional data is an interesting and relevant setting in causal inference and discovery.\n* The proposed approach is reasonable and is capable of handling a few challenges as mentioned in the paper including nonlinearity and choosing both the target and value to intervene.\n* The paper is well written and easy to follow.\n\nWeakness:\n* The proposed method is somewhat non-surprising and there is a lack of formal (theoretical) justification of the performance of the proposed method.\n* While experiments on both synthetic and real-world data demonstrate the performance of the proposed method compared to alternatives. It is not clear to me whether the proposed method has been compared to sufficient and competitive enough alternatives. The use of only one real-world data, while understandable, is also somewhat restrictive. The paper can also benefit from a robustness study evaluating when the key assumptions in the paper are violated.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "K_HS5g0eemn", "reviewer": "Reviewer_SUP9", "summary": "Causal discovery (CD) is an important field of research that can help find the causal relationship of the variables in a system. Only using observational data for finding causal structure, in the form of a Directed Acyclic Graph (DAG), is insufficient as there could be multiple DAGs that are Markov Equivalent. To resolve the uncertainties, interventional data can be incorporated to disambiguate between hypotheses. This work proposes a novel method based on Bayesian Optimal Experimental Design (BOED) that efficiently selects both intervention targets and values via the Bayesian optimization approach to find the true nonlinear structural causal model. Batch strategies, i.e., Greedy-CBED and Soft-CBED, are developed to select the most informative subset of interventions and values, as opposed to a single intervention at a time, to find the SCM.\n\nThroughout the experiments, the authors demonstrate that their work can achieve better performance than existing methods on both synthetic (Erdos-Renyi, Scale Free) and real-world datasets (single-cell regulatory networks).\n", "questions": "\ni) Could the authors elaborate what is the newly introduced random variables $$ \\Phi $$ in equation (3) when measuring the mutual information?\n\nii) What is the initialization strategy for the Gaussian Process model?\n\niii) What would happen when the number of variables in the SCMs is higher than 50?\n\n", "limitations": "Possibly the authors could provide some examples (such as the single-cell gene regulatory network) when the method fails to identify the true SCM.\n", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\ni) This paper is written exceptionally well; details of notations, definitions, equations, and derivation of theoretical results are provided.\nii) The proposed method is novel, as well as the proposed work, can find nonlinear SCMs and can select both intervention and values, in prior works are limited to linear models and can only select the intervention target.\niii) This work provides a comprehensive ablation study (Figure 3) so that we clearly better understand the effect of each adding component (such as the effect of selecting the intervention values, batch v.s. non-batch, and soft-CBED v.s Greedy CBED, on the E-SID performance. )\n\nWeakness:\n\nI do not particularly find a significant weakness in this work.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BYHOGct34Pe", "reviewer": "Reviewer_h91K", "summary": "The authors proposed to efficiently learn a causal structure through interventions under a causal sufficiency assumption. The key idea is how to design experiments (intervention) in a way to figure out the causal structure where they adopted Bayesian in that (i) use of an (approximate) posterior distribution over candidate graph structures and parameters and (ii) (approximate) Bayesian Optimal Experimental Design in performing experiments. More specifically, what variable and which value to intervene to get a sample is determined with respect to maximizing mutual information between the parameters (structural and functional) and observation, where they adopted Bayesian Optimization. Single and Batch designs are proposed with two options for Batch, Greedy and Softmax-based.\n", "questions": "- Please define beta in Line 193-4 in the main text.\n- Gaussian noise is assumed, but it is unclear where the assumption is explicitly used. It doesn’t seem to be related to Line 188-189\n- What is the main novelty of the *-CBED? Also, it would be nice if you could emphasize the contributions of the paper?\n", "limitations": "- Causal sufficiency assumption and that all variables are intervenable. These two guarantees identifying a causal graph.\n- Only one variable is intervenable at a time.\n- Assumption 4 prohibits the use of discrete variables.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The paper focuses on scaling up Bayesian causal discovery, and there are several places where the authors tried to incorporate recent works to approximate intractable quantities.\n- The efficiency of the algorithm is demonstrated empirically.\n\nWeaknesses\n- The main idea of the paper looks like a collection of existing methods (BALD, DiBS, BO, Soft Top-K). Surely, putting them into a piece neatly to solve a problem would require expert knowledge of the ingredients. \n- Tests on a synthetic graph, where the expected number of edges per vertex is one, will likely result in multiple independent components. Experiments on small/medium size graphs with a bit more dense edges are desired. Furthermore, tests under unobserved confounders (i.e., violation of assumptions) would be a nice addition.\n- Noise variance seems small (but is an understandable choice given that it would not likely affect comparisons among methods).\n- The authors misused the term SCM in many places. SCM consists of functions, and it induces a causal graph (not part of it). The graph can be identified, and parameters can be learned, but SCM won’t be typically identified. (Line 66, recovering the original SCM, Line 44 consists of a DAG structure … )", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "8gWe5b9yEUj", "reviewer": "Reviewer_25Ya", "summary": "This paper considers Bayesian optimal intervention selection for active causal discovery. The problem setting is causally sufficient causal graphs under additive noise models and atomic interventions. Importantly, both the target nodes to intervene and intervention values that will be assigned to the target nodes are optimized in a batched setting. Mutual information between the observations and the parameters is optimized in Bayesian Optimal Experimental Design context. Variational inference is used to approximate the posterior over SCMs. After thorough derivations, Monte Carlo approximations are used to estimate MI for single intervention design. For selecting the target value over a continuous domain, a Gaussian Process is used along with Upper Confidence Bound mechanism. Furthermore, two approaches (greedy and top-k selection) are proposed for batch design. Experiments on synthetic datasets demonstrate the effectiveness of each piece of the proposed method. Experiments on semi-real datasets also show promising results.", "questions": "Regarding the weakness above, do you see an extension to non-atomic interventions possible within the proposed framework?\n\nOn a smaller note, L53-54 states: “existing work on active causal discovery focuses exclusively on selecting the intervention target”. Although it solves a different problem, \"Matching a Desired Causal State via Shift Interventions\" (Zhang et al. 2021 NeurIPS) can be a relevant work that also aims to find the intervention values.", "limitations": "Assumptions of the paper, e.g. Gaussian noise and atomic interventions, are clearly stated in the paper. Perhaps the second point can be addressed in a bit more detail. ", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written, with a sufficient amount of details in the main body and a lot of secondary information on the appendices. The proposed method consists of many components, some borrowed from the existing literature such as GP-UCB and DiBS posterior model. The paper does a nice job putting them all together coherently and explaining the steps. \n\nThe considered problem is general, and I believe the main contribution is this generality: allowing non-linear systems, scaling up to 50 nodes (though in quite sparse graphs), and the ability to set the intervention values rather than just finding targets. \n\nEspecially, the last point seems important. Although there are other information-theoretic approaches to causal discovery, to my knowledge, the present paper is the first one that studies the effect of the target value and supports its claims through extensive experiments.\n\nThe only major weakness is the assumption of atomic interventions. For instance, ABCD (Agrawal et al., 2019) allows multiple nodes to be intervened simultaneously. Although the proposed batch solutions are helpful for faster causal discovery, the assumption of atomic interventions can be a limiting factor.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-WDuV8iCl0Y", "reviewer": "Reviewer_PxXf", "summary": "The paper presents a bayesian intervention design method for single-node interventions, including the target values, in causal models with additive noise.", "questions": "Some of the related work https://papers.nips.cc/paper/2019/hash/5ee5605917626676f6a285fa4c10f7b0-Abstract.html shows that maximising the expected information gain might not be the optimal strategy in their setting, so I was curious about how this would apply in the setting of this paper\n\nIn general, I would be curious about how this work compares to all of the missing related work.", "limitations": "The paper proposes an interesting approach, although limited to single-node interventions and ANMs (which seems a strong assumptions). One big limitation in my opinion is that it fails to cite most of the related work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*** EDIT after rebuttal *** I think the authors did a great job in the rebuttal and answered most of my (and other reviewers') concerns (including the similarity with previous work on GPs for BOED [49]), so I changed my score to weak accept.\n\nStrengths:\n- Intervention design is an important, and in my opinion, understudied problem\n- The paper presents an interesting and to the best of my knowledge theoretically sound method\n\nWeaknesses:\n- The paper seems to ignore a lot of related work on intervention design, mostly focusing on differential causal discovery. This is a bit weird since several of these these papers are cited in [1] and [38] and the whole terminology of this paper is based on related work that isn't cited, e.g. intervention design with a variety of settings (active/passive, multiple targets, budgeted, latent variables and also Bayesian): https://proceedings.neurips.cc/paper/2015/hash/b865367fc4c0845c0682bd466e6ebf4c-Abstract.html, https://proceedings.neurips.cc/paper/2020/hash/f57bd0a58e953e5c43cd4a4e5af46138-Abstract.html, https://proceedings.mlr.press/v70/kocaoglu17a.html, https://proceedings.neurips.cc/paper/2017/hash/291d43c696d8c3704cdbe0a72ade5f6c-Abstract.html, https://proceedings.neurips.cc/paper/2021/hash/0b94ce08688c6389ce7b68c52ce3f8c7-Abstract.html, https://papers.nips.cc/paper/2019/hash/5ee5605917626676f6a285fa4c10f7b0-Abstract.html  and many more\n\n- It seems to be also missing another even more related work on optimal experiment design with GPs: https://openreview.net/forum?id=Ih_ogoAw5G\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept