Dependency Structure Discovery from Interventions
Authors: Nan Rosemary Ke
Olexa Bilaniuk
Anirudh Goyal
Stefan Bauer
Bernhard Schölkopf
Michael Curtis Mozer
Hugo Larochelle
Christopher Pal
Yoshua Bengio
Venue:  (2021)
Keywords: structure learning
deep learning
continuous
optimization

Abstract: Promising results have driven a recent surge of interest in continuous optimization methods for Bayesian network structure learning from observational data. However, there are theoretical limitations on the identifiability of underlying structures obtained from observational data alone. Interventional data provides much richer information about the underlying data-generating process. However, the extension and application of methods designed for observational data to include interventions is not straightforward and remains an open problem. In this paper we provide a general framework based on continuous optimization and neural networks to create models for the combination of observational and interventional data. The proposed method is applicable even in the challenging and realistic case that the identity of the intervened upon variable is unknown. We examine the proposed method in the setting of graph recovery both de novo and from a partially-known edge set. We establish strong benchmark results on several structure learning tasks, including structure recovery of both synthetic graphs as well as standard graphs from the Bayesian Network Repository.

Under review as a conference paper at ICLR 2021
DEPENDENCY STRUCTURE DISCOVERY FROM INTERVENTIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Promising results have driven a recent surge of interest in continuous optimization methods for Bayesian network structure learning from observational data. However, there are theoretical limitations on the identifiability of underlying structures obtained from observational data alone. Interventional data provides much richer information about the underlying data-generating process. However, the extension and application of methods designed for observational data to include interventions is not straightforward and remains open problem. In this paper provide a general framework based on continuous optimization and neural networks to create models for the combination of observational and interventional data. The proposed method is applicable even in the challenging and realistic case that the identity the intervened upon variable is unknown. We examine the proposed method in the setting of graph recovery both de novo and from a partially-nnow edge set. We establish strong benchmark results several structure learning tasks, including structure recovery of both synthetic graphs as well as standard graphs from the Bayesian Network Repository.
INTRODUCTION
Structure learning concerns itself with the recovery of the graph structure of Bayesian networks (BNs) from data samples. A natural application of Bayesian networks is to describe cause-effect relationships between variables. In that context, one may speak of causal structure learning. Causal structure learning is challenging because purely observational data may be satisfactorily explained by multiple Bayesian networks (a Markov equivalence class), but only one is the most robust to distributional shifts: The one with the correct graph. A more powerful tool than BNs is thus needed to model causal relationships.
Structural Causal Models (SCMs) are that tool. An SCM over a set of random variables a collection of assignments these variables and directed acyclic graph of dependencies between them (Peters et al. 2017] $6.2). Each assignment is a function of only the direct causes of a variable, plus an independent noise source. An SCM entails precisely one (observational) data distribution. Interventions on an SCM's assignments, such as setting random variable to a fixed value (a hard intervention), entail new interventional data distributions (Peters al., 2017 $6.3).
SCMs can be used to answer higher-order questions of cause-and-effect,, up the ladder of causation (Pearl Mackenzie 2018). Causal structure learning using SCMs has been attempted in several disciplines including biology (Sachs et al. (2055] Hill et al., 2016), weather forecasting (Abramson
ctt al. 1996) and medicine (Lauritzen & Spiegelhalter 1988 Korb Nicholson) 2010)).
Causal structure is most frequently learned from data drawn from observational distributions. Struc- ture learning methods generally cannot do more than identify the causal graph up to Markov equivalence class (Spirtes et al. (2000). In order to fully identify the true causal graph, method must either make restrictive assumptions about the underlying nata-generating process, such as linear but mon-Gaussian data (Shimizu al. 2006), must access enough data from outside the observational distribution (i.e., from interventions).
Under certain assumptions about the number, diversity, and nature of the interventions, the true underlying causal graph is always identifiable, given that the method knows the intervention performed (Heckerman al. 1995). In much of the prior work causal model induction it is assumed that

---

Under review as a conference paper at ICLR 2021
there is experimenter and this experimenter performs interventions. However, in the real world, interventions can also be performed by other agents, which could lead to unknown interventions (interventions with unknown target variables). A few works have attempted to learn structures from
unknown-interventior data (Faton & Murphy, 2007a| Squires et al. (2000) Huang et al. (020). A notable such work, (Mooij al.) 2016), has been extended in (Kocaoglu al., [219]] Jaber et al. 2020). Although there is no theoretical guarantee that the true causal graph can be identified in that setting, evidence so far points to that still being the case.
Another common setting is when the graph structure is partially provided, but must be completed. An example is protein structure learning in biology, where we may have definitive knowledge of some causal edges in the protein-prode
interactome, but the remaining causal edges must be discovered. We will call this setting "partial graph completion", This is an easier task compared to learning the entire graph, since it limits the number of edges that have to be learned.
Recently, a flurry of work on structure learn- ing using continuous optimization methods has appeared (Zheng et al. 2018 Yu et al.] 2019). These methods operate on observational data and are competitive with other methods. Be- cause of the theoretical limitations identifica- tion from purely observational data cited above, it would be interesting extend these meth- ods to interventional data. However, it is not straightforward to apply continuous optimiza- tion methods to structure learning from inter- ventional data. Our key contributions are to answer the following questions experimentally:
Expertmental
Existing Knowledge
Structure Disoovery
6
Cound Inductore Krowledge variablee
Unkrown
Intervertion
Figure I: In many areas of science, such as biology, we try infer the underlying mechanisms and structure through experiments. We obtain observational data plus interventional data through known (e.g- by targeting certain variable) il is unclear where the effect of the intervention will be). Knowledge existing edges e.g. through previous experiments likewise included and be considered special case of causal induction.
unknown interventions (e.g. when
1. Can the proposed model recover true causal structure? Yes, see Figure $4
2. How does the proposed model compare against state of the art causal methods on real-world datasets? Favourably; see $5.4 Table ş
3. Does a proposed model generalize well to unseen interventions? Yes, see $5.5
4. How does the proposed model perform on partial graph recovery? It scales to ~ 50 variables while the other baselines can't. see $577
2 PRELIMINARIES
Causal modeling. A Structural Causal Model (SCM) (Peters et al. 2017) over finite number M
of random variables X; is a set of structural assignments
X = ((Xpttt.)) N:), Vi
M- ---1) 11
(1)
Identifiability. In a surely-observationaa setting, it is known that causal graphs can be distin- guished only up to a Markov equivalence class. order to identify the true causal graph structure, interventional data is needed (Eberhardt et al. 2012).
Interventions. There are several types of common interventions which may be available (Eaton & Murphy/ (0076)) These are: No intervention: only observational data is obtained from the ground truth model. Hard/perfect: the value of single or several variables is fixed and then ancestral sampling is performed on the other variables. Softt/ipperfet:: the conditional distribution of the variable which the intervention is performed is changed. Uncertain: the learner is not sure of which variable exactly the intervention affected directly. Here we make use of soft intervention because they include hard intervention as a limiting case and hence are more general.
Structure discovery using continuous optimization. Structure discovery is super-exponential search problem that searches though all possible directed acyclic graphs (DAGs). Previous continuous- optimization structure learning works (Zheng et al. 2018 Yu et al. 2019 Lachapelle et al. 2019) mitigate the problem of searching in the super-exponential set of graph structures by considering the degree to which a hypothesis graph violates "DAG-ness as an additional penalty to be optimized. there are M such variables, the strategy of considering all the possible structural graphs separate hypotheses is not feasible because it would require maintaining O(2M²) models of the data.

---

Under review as a conference paper at ICLR 2021
3 RELATED WORK
The recovery of the underlying structural causal graph from observational and interventional data is a fundamental problem (Pearl 1995 2009, Spirtes et al. 2000). Different approaches have been and continuous optimization methods.
studied: score-based, constraint-based, asymmetry- Score-based methods search through the space of all possible directed acyclic graphs (DAGs) representing the causal structure based on some form of scoring function for network structures (Heckerman al., 1995 Chickerig 2002, Tsamardinos et al. 2006; [aaser & Bühlmann, 2012
Goudet et al. 2017; Cooper & Yoo 1999; Zhu Chen 2019). Constraint-based methods (Spirtes et al. 2000 Sun et al.) 2007] Zhang et al. 2
et al. 2019; & Chen, 2019) infer the DAG by analyzing conditional independences in the data. Eaton & Murphyy (2007c) use dynamic programming techniques to accelerate Markov Chain Monte Carlo (MCMC) sampling in a Bayesian approach to structure learning for discrete variable DAGs. |Peters et al. 2016); Ghassami et al. (2017); (017)):Rojas-C35 -Rojas-Carulla et al. (2018) exploit invariance across environments to infer causal structure, which faces difficulty scaling due to the iteration over the super-exponential set of possible graphs. Recently, (Zheng et al. 2018 Yu et al. 2019 Lachapelle al. 2019) framed the structure search as a continuous optimization problem, however, the methods only uses observational data and are non-trivial to extend to interventional data. In our paper, we present a method that uses continuous optimization methods that works on both observational and interventional data.
For interventional data, is often assumed that the models have access full intervention information, which is rare in the real world. |Rothenhäusler et al. (2015) have investigated the case of additive shift interventions, while Eaton & Murphy| (2007)) (2007b) have examined the situation where the targets of experimental interventions are imperfect or uncertain. This is different from our setting where the intervention is unknown to start with and is assumed to arise from other agents and the environment.
Learning based methods have been proposed (Guyon 2013) 2014] Lopez-Paz et al. 2015) and there also exist recent approaches using the generalization ability neural networks to learn causal signals
from purely observational data (Kalanntthan et al.] 20188] Goudet et al. 2018). Neural network
methods equipped with learned masks, such as (Ivanov et al. 2018:] Li et al. 20199] Yoon et al. 2018 Douglas al. 2017), exist in the literature, but only few (Kalainathan al.
2018) have been
adapted to causal inference. This last work is, however, tailored for causal inference on continuous variables and from observations only. Adapting it to disscrete-variable setting is made difficult by its use of a Generative Adversarial Network GoodGGlow et al. (2014) framework.
STRUCTURE DISCOVERY FROM INTERVENTIONS METHOD
Scope of Applicability and Objective. The proposed method, like any structure learning algorithm, assumes the availability of data-generating process based on ancestral sampling of ground-truth SCM of M variables, which can be queried for samples. The SCM supports applying and retracting known unknown interventions. The method can support infinite- finite-data well infinite- or finite-intervention regimes.
The objective is, then, to learn the SCM's structure from the insights that each intervention gives about cause-effect relationships between variables in the SCM.
4.1 PROBLEM SETTING AND ASSUMPTIONS
In this paper, we restrict the problem setting to specific, but still broad classes of SCMs and interven- tions. In particular, we assume that:
Data is discrete-valued. The SCM's random variables are all categorical.
Causal sufficiency. For every data sample, the value of all variables are available; There are no
latent confounders.
Interventions are localized. They affect only a single variable (but which one may not be known).
Interventions are soft. An intervention does not necessarily pin its target random variable to a fixed value (though it may, special case). It changes the relationship of variable with its parents.
3

---

Under review as a conference paper at ICLR 2021
Interventions do not stack. Before intervention is made, the previous one is fully retracted. This stops the SCM from wandering away from its initial, observational configuration after a long series of interventions.
No control over interventions. The structure learning algorithm has control neither of the target, nor the nature of the next intervention the SCM.
For a detailed description of the interventions, refer to A.2
4.2 VARIATIONS AND PRIOR KNOWLEDGE
In the problem setting above, the ground-truth SCM is completely opaque to us. However, we consider two interesting relaxations of this formulation:
Complete or partial graph recovery. We may already know the existence of certain cause-effect edges and non-edges within the ground-trun truth SCM. If such prior information is available, it turms complete graph recovery problem into one of partial graph recovery. Larger SCMs can be tackled if only parts of the graph need to be recovered.
Known or unknown interventions: The interventions can either be known or unknown to the learned model.
We demonstrate that the proposed method can naturally incorporate this prior information to improve
its performance.
4.3 METHOD OVERVIEW
"Mecac 1 Sinny
Htase Guggh sorinn
The proposed method is a score-based, iterative, continuous- optimization method consisting of three phases that flow into other (See Figure 2}. During the three-phase procedure, a structural representation of a DAG and functional representation of of independent causal mechanisms are trained jointly until convergence. Because the structural and funetional parameters are not independent and do influence each other, we train them in alternating phases, a form of block coordinate descent optimization.
Stop noo??
Figure Workflow for our pruposed method SDL. Phase samples graphs un- model's current belicf about the edge structure and parameters obser- vational data. Phuse scores a small set graphs against interventionl
4.3.1 PARAMETRIZATION
signs rewards according graphs' ability to predict interventions. rewards from Phase 2 to update the beliefs about edge structure. edge probabilities have saturated near O or I, the method has converged.
We distinguish two sets of parameters: The structural parameters "y and the functional parameters 0. Given graph of M variables, we parametrize the structure 7 as a matrix IR M XM such that ((%)) ) is our belief in random variable X, being direct cause of X,, where (xx) = 11 + exp(-z)) is the sigmoid function. The matrix ((r) is thus soft adjacency matrix.
uses the
believed
The set of functional parameters 0g parametrizes the conditional probability distribution of X, given its parent set X ppa(i.C), with C ~ Ber(a hypothesized configuration of the SCM's DAG.
4.3.2 PHASE 1: GRAPH FITTING ON OBSERVATIONAL DATA
During Phase the functional parameters 0 are trained maximize the likelihood of randomly drawn observational data under graphs randomly drawn from our current beliefs about the edge structure. We draw graph configurations Ci Ber(a (er(a()))) and batches of observational data from the unintervened ground-truth SCM, then maximize the log-likelihood of the batch under that configuration using SGD. The use of graph configurations sampling from Bernoulli distributions is analogous to dropout on the inputs of the functional models (in our implementation, MLPs), giving us an ensemble of neural networks that can model the observational data.
4.3.3 PHASE 2: GRAPH SCORING ON INTERVENTIONAL DATA
During Phase 2, a number of graph configurations are sampled from the current edge beliefs parametrized by 7, and scored on data samples drawn from the intervention SCM.
4

---

Under review as a conference paper at ICLR 2021
Intervention applied: At the beginning of Phase 2, intervention is applied to the ground-trun -ruth SCM. This intervention is not under the control of the method. In our implementation, and un- beknownst to the model, the target variable is chosen uniformly randomly from all M variables throughout the optimization process.
Intervention predicted: If the target of the intervention is not known, it is predicted using simple heuristic. A small number of interventional data samples are drawn from the SCM and more graphs are sampled from our current edge beliefs. The average log-likelihood of each individual variable X; across the samples is then computed using the functional model parameters 0 fine-tuned on observational data Phase 1. The variable X, showing the greatest deterioration log- oig-liiklhood is assumed to be the target because the observational distribution most poorly predicts that variable.
If the target of the intervention is known, then this is taken as ground-truth knowledge for the purpose of subsequent steps, and no prediction needs to be done.
Graphs Sampled and Scored: new set of interventional data samples and graph configurations are now drawn from the intervention SCM and edge beliefs respectively. The log- li-likkliihood of the data batches under the hypothesized configurations is computed, with one modification: The contribution to the total log-likelihone of a sample X coming from the target (or predicted-target) intervention variable X; is masked. Because X; was intervened upon (in the manner of a Pearl do-operation, soft or hard), the values one gets for that variable should be taken as givens, not as contributors to the total bog-likelihood of the sample. As well, no gradient should be allowed to propagate into the variable's learned functional parametrization 0,, because it was not actually responsible for the outcome.
Intervention retracted: After Phase 2, the intervention is retracted, per our modelling assumptions.
4.3.4 PHASE 3: CREDIT ASSIGNMENT STRUCTURAL PARAMETERS
During Phase 3, the scores of the interventional data batches over various graph configurations are aggregated into a gradient for the structural parameters 7. Because a discrete Bernoulli random sampling process was used to sample graph configurations under which the log-likelihoods were computed, we require a gradient estimator to propagate gradient through to the y structural parameters. Several alternatives exist, but we adopt for this purpose the REINFORCE-like gradient estimator Pij proposed by Bengio et al. (2019):
gii (x(o(r)) O (X)(()
Vi,j E {0, (O,...,M-11, M-13
(2)
Ex Cd)
where the (k) superseript indicates the values obtained for the k-th draw of C' under the current edge beliefs parametrized by y. Therefore, (x)( (X) can be read as the log- ligelikll of variable X, in the data sample X under the ' thth configuration, C(²),, drawn from our edge beliefs. Using the estimated gradient, then update 7 with SGD, and return Phase of the continuous optimization process.
The gradient estimator Py minimizes an implicit empirical risk objective with respect to "Ki- When the functional and structural parameters 0 and y "sufffciently close" their minima, the estimator Pi empirically converges quickly towards that minimum > as shown in Figure 16 Appendix A.13
We include a regularization term JDAG(7) that penalizes length-2 cycles in the learned adjacency matrix (77), with tunable strength ADAG- The regularization term is JDAG(7) Eisy cosh(a ar (174)) Vi,j j {0. ........ M 1} and is derived from Zheng al. (2018). The details of the derivation are in the Appendix. We explore several different values of ÅDAG and their effects in our experimental setup. Suppression of longer-length cycles was not found to be worthwhile for the increased computational expense.
Acyelic Constraint:
EXPERIMENTAL SETUP AND RESULTS
We first evaluate the proposed method synthetic dataset where we have control over the number of variables and causal edges in the ground-truth SCM. This allows us to analyze the performance of the proposed method under various conditions. We then evaluate the proposed method on real- world
datasets from the BnLearn dataset repository. We also consider the two variations of 44.2; Recovering only part of the graph (when the rest is known), and exploiting knowledge of the intervention target.
5

---

Under review as a conference paper at ICLR 2021
The summary of our findings is: 1) We show strong results for graph recovery for all synthetic graphs in comparisons with other baselines, measured by Hamming distance. 2) The proposed method achieves high accuracy on partial graph recovery for large, real-world graphs. 3) The proposed method's intervention target prediction heuristic closes the gap between the known- and unknown- target intervention scenarios. 4) The proposed method generalizes well to unseen interventions. 5) The proposed method's 's time-to-solutin scaling appears to be driven by the number of edges in the groundtruth graph moreso than the number of variables.
5.1 MODEL DESCRIPTION
Learner model. Without loss of generality, we let 0, = (,O, BO,, W1,, ] define a stack of M one-hidden-laye layer MLPs, one for each ran- dom variable X,, A more appropriate model, such as a CNN, can be chosen using domain- specific knowledge; the primary advantage of using MLPs is that the hypothesized DAG con- figurations Ctj can be readily used to mask the inputs of MLP i, as shown in Figure
0
CJ6S
0.2M1
409
0.35
3168
9302
bot M.5.M)
blen sangle R- D.W00)
Hist suuple Dis [2..0
To force the structural equation fi corresponding to X; to rely exclusively on its direct ancestor set pa(i, C) under hypothesis adjacency matrix (See Eqn. Tp. the one-hot input vector X, for variable X, S MLP is masked by the Boolean element Cjj. An example the multi-MLP ar- chitecture with M=4 categorical variables of For more
Staciigg
Figure 3: MLP Model Architecture for an M = 4, N = 3 SCM The model computes the conditional probabilities of A, B, C. D given their parents using stack of four independent MLPs. The MLP ingut layer uses an adjacency matrix sampled from (or(a(t)) as an input mask to foree the model to make use only of parent nodes prodict their child node.
N=3 categories shown in Figure 3
details, refer Appendix(A.4
Ground-truth model. Ground-truth SCM models are parametrized either as CPTs with parameters from BaLearn (in the case of rerl-world graphs). or second stack of MLPs similar to the learner model, with randomly-initian initialized functional parameters for and the desired adjacency matrix GGT-
Interventions. In all experiments, at most one (soft) intervention is concurrently performed. To simulate a soft intervention on variable X,, we reinitialize its ground-truth conditional distribution's MLP parameters or CPT table randomly, while leaving the other variables untouched. For more details about the interventions, please refer to Appendix
5.2 SYNTHETIC DATASETS EXPERIMENTS
We first evaluate the model's performance on several randomly- initialized SCMs with specific, representative graph structures. Since the number of possible DAGs grows super-exponentially with the number of variables, for M=4 up to 13 selection of representative and edge-case DAGs are chosen. chainM and ful 1M (M=3-13) are the minimally- and maximalllycooneettee M-variable DAGs, while treeM and jungl 1 eM are tree-like intermediate graphs. co collider rM is the (M-1) + 1 collider graph. The details of the setup is in Appendix A.6
Figure 4: Cross entropy (CE) and Area-Under-Curve (AUC/AUROC) for edge probabilities of learned graph against ground-rruth for synthetic SCMs. Error bars represent +o over PRNG seeds 1-5, Left to right: chainM. chaint,jjuggl Su, = 3 3...8.0 8 ... 13 in Appendis(A.6.] Graphs (3-8 variables) all learn perfectly with AUROC reaching 1.0. However, denser graphs (fullM) take longer converge.
Results.
The model can recover most synthetic DAGs with high accuracy, measured by Structural
Hamming Distance (SHD) between learned and ground-truth DAGs. Table shows our proposed
method outperforming all other baseline methods, and learns all graphs perfectly for 3 to 13 variables (excepting full). For DAGs ranging from 3 to 8 variables, the AUROCs all eventually reach 1.0 (indicating perfect classification into edge/non-edge; Refer to Figure 4) For both large (M > 10)

---

Under review as a conference paper at ICLR 2021
Table 1: Baseline comparisons: Structural Hamming Distance (SHD) (lower is better) for leamnd and ground- truth edges on various graphis from synthetic and real datascts, compared to (Poters al. 2016) (Heinze-Deml al. (018b), (Eaton & Murphy (2007)), (Yo all 2019 and (Zheng pick the warsi performing model out of the random seeds the table. COM: out memory. Our proposed method correcllyy recovers the true causal graph, with the exception of Sachs and full1 and significanlyy ourperforss all other haseline methodss Proposed method well all the baselines uses similar amount of data.
2018 The proposed method (Sructural Discovery from Interveations (SDI
random seeds 1 and we
Method M
Asis
Sachs
coll Bollider
chain
jungle
col der
full
11
8
13
13
13
13
Zheng et al. 2018
14
22
18
39
22
24
71
ef al. (2019)
10
7
14
16
12
77
Heinze- Deml et al.
2018b
8
17
7
12
12
28
Peters al. 2016
2
16
Eaton & Murphy
2007a
0
OOM
7
OOM
OOM
OOM
OOM
Proposed Method (SDI)
0
6
0
0
7
and dense DAGS (e.g. Full13) the model begins encountering difficulties, as shown Table and Appendix $
Small graphs (M < 10) are less sensitive than larger ones our hyperparameters, notably the sparsity and acyclic regularization (43.44) terms. In A.5 we perform analysis of these hyperparameters.
5.3 REAL-WORLD DATASETS: BNLEARN
The Bayesian Network Repository is a collection of commonly-usee used causal Bayesian networks from the literature, suitable for Bayesian and causal learning benchmarks. We evaluate the proposed method on the Earthquake (Korb & Nicholson, 2010), Cancer (Korb & Nicholson 2010), Asia (Lauritzen & Spiegelhalter 1988) and Sachs (Sachs et al. 2005) datasets (M 5, 8 and Midll-- 11-variables respectively, maximum in-degree 3) in the BnLearn dataset repository.
Results. As shown in Table [] the proposed method perfectly recovers the DAG of Asia, while making small number of errors (SHD=6) for Sachs (1 (lvarribblss), It thus significantly outperforms all other baselines models. Figures 8 visualize what the model has learned at several stages of learning. Results for Cancer and Asia can be found in the appendices, Figure 17 and 18
5.4
COMPARISONS WITH OTHER METHOOSS
As shown in Table 1 we compared the proposed SDI method to ICP (Peters et al. (016 non-linear ICP (Heinze- Deml et al.] 2018b)), and (Eaton & Murphy/ 2007b Zheng et al. 2018:
8 Yu et al.) 2019) on Asia (Lauritzen & Spiegelhalter 1988), Sachs (Sachs et al. 2005 and representative synthetic graphs. Eaton & Murphy (2007b) handles uncertain interventions and Peters et al. (0016), Heinze-Deml al. (2018b) handles unknown interventions. However, neither attempts to predict the intervention. As shown in Table we significantly outperform ICP, non non-linear ICP, and the methods in (Yu et al. 2019) and (Zheng al. 2018). Furthermore, [aaton & Murphy (2007b) runs of memory for graphs larger than M = 10 because modelling of uncertain interventions is done using "shadow" random variables (as suggested by the authors), and thus recovering the DAG internally requires solving a = 2.aiiiibbllc problem. Their method's 's extremely poor time- and space- of (d24) makes unusable beyond 20.
For FDIS, we threshold our edge beliefs at ( = 0.5 to derive graph, but the continued decrease of the cross-entropy loss (Figure hints at stDss convergence onto the correct causal model. Please refer to Appendix $A.8 for full details and results.
5.5
GENERALIZATION PREVIOUSLY UNSEEN INTERVENTIONS
It is often argued that machine learn- ing approaches based purely on cap- turing joint distributions do not nec- essarily yield models that generalize to unseen experiments, since they do not explicitly model changes through interventions. By way of contrast,
Table 2: Evaluating the consequences of previously intervention: log-likelthood under intervention)
fork3
chain3
confounder3
collider3
Baseline
-0,5036
-0.4662
-0.3628
-0,5082
-0.4502
-0.300
-0.2819
-0.4677

---

Under review as a conference paper at ICLR 2021
causal models use the concept of interventions to explicitly model changing environments and thus hold the promise of robustness under distributional shifts (Pearl 2009, SSchllkopf et al. [2012] Peters et al. 2017). To test the robustness of causal modelling to previously unseen interventions (new values for an intervened variable), we evaluate a well-trained causal model against a variant, non-causal model trained with Cij 1, i o j. An intervention is performed interventional data is drawn from it, and the models, with knowledge of the intervention target, are asked to predict the other variables given their parents. The average log-likelihoods of the data under both models are computed and contrasted. The intervention variable's contribution to the log- likelihood is masked. For all 3-variable graphs (cha 3, fork3, coll collider3, con.founder3] the causal model attributes higher log-likelihood to the intervention distribution's samples than the non-causal variant, thereby demonstrating causal models' superior generalization ability transfer tasks. Table colleetss these results.
the ground-truth SCM, fresh
5.6 VARIANT: PREDICTING INTERVENTIONS
In Phase 2 ($4.3.3) we use a simple heuris- tic predict the intervention target variable. Experiments show that this heuristic func- tions well in practice, yielding correct pre- dictions far more often than by chance alone (Table Guessing the intervention variable randomly, or not guessing it at all, leads to significant drop in the model performance, even for 3-variable graphs (Fig. Left). Training with intervention prediction closely tracks training with leaked knowledge of the ground-truth intervention on larger, 7-variable graphs (Fig. [1 Right).
Table 3: Intervention Prediction Accuracy: (identify which variable the intervnniion took place)
3 variables
4 variables
5 variables
8 variables
95 %
93 %
85 %
71 %
5.7 VARIANT: PARTIAL GRAPH RECOVERY
Instead of learning causal structures de nove, we may have partial information about the ground-truth SCM and may only need to fill in missing information ($4.2). An exam- ple is protein structure discovery in biology, where some causal relationships have been definitely established and others remain open hypotheses. This is easier task com- pared to full graph recovery, since the model only has to search for missing edges. We evaluate the proposed method on Barley (Kristensen & Rasmussen 2002) (M = 48) and Alarm (Beinlich et al. 1989) (M- 37) from the BnLearn repository. The model is asked to predict 50 edges from Barley and 40 edges from Alarm. The model reached 2 90% accuracy on both datasets, shown in Table 4
Table 4: Purtial Graph Recovery Alarm BBein. lich nl. (989) and Barley (Kristensen & Rasmussen 2002). The model asked prodict edges Bar- ley and 40 edges in Alarm. The accuracy is measured in Structural Hamming Distance (SIID) acijacheeeed over 90% accuracy on both graphs
Graph
Alarm
Barley
5.8 ABLATION AND ANALYSIS
Number of variables Total Edges
37
48
As shown in Figure 12 larger graphs (such as M > 6) and denser graphs (such ful18) 1) are progressively more dif- ficult to learn. For denser graphs, the learned models have higher sample complexity, higher variance and slightly worse results. Refer to Appendix $A.9 for complete results on all graphs. Hyperparameters. Hyperparameters for all experiments were kept identical unless otherwise stated. We study the effect of DAG and sparsity penalties in the following paragraph. For more details, please refer to Appendix $A.5
46
84
Edges to recover Recovered Edges
40
50
37
45
Errors (in SHD)
Importance of regularization. Valid configurations C for a causal model are expected to be a) sparse and b) acyelic. To promote such solutions, we use DAG and sparsity regularization with tunable hyperparameters. We set the DAG penalty to 0.5 and sparsity penalty to 0.1. We run ablation studies on different values of the regularizers and study their effect. We find that smaller graphs are less sensitive to different values of regularizer than larger graphs. For details, refer to Appendix $2.12
Importance of dropout. To train functional parameter for an observational distribution, sampling adjacency matrices is required. We "drop out" each edge (with a probability of (>)) in our experi- ments during functional parameter training of the conditional distributions of the SCM. Please refer to Appendix $A.14 for more detailed analysis.
8

---

Under review as a conference paper at ICLR 2021
CONCLUSION
In this work, we introduced an experimentally successful method (SI for causal structure discovery using continuous optimization, combining information from both observational and interventional data. We show in experiments that it can recover true causal structure, that it generalizes well to unseen interventions, that it compares very well against start-of-the-art causal discovery methods on real world datasets, and that it scales even better on problems where only part of the graph is known.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Bruce Abramson, John Brown, Ward Edwards, Allan Murphy, and Robert I. Winkler. Hailfinder: A bayesian system for forecasting severe weather. International Journal of Forecasting, 12(1):57-71,
1996.
Ingo A Beinlich, Henri Jacques Suermondt, R Martin Chavez, and Gregory Cooper. The alarm monitoring system: A case study with two probabilistic inference techniques for belief networks. In AIME 89, pp. 247-256. Springer, 1989.
Yoshua Bengio, Tristan Deleu, Nasim Rahaman, Rosemary Ke, Sébastien Lachapelle, Olexa Bilaniuk, Anirudh Goyal, and Christopher Pal. A seeaa-rransfer objective for learning to disentangle causal mechanisms. arXiv preprint arXiv:1901.109/ 2019.
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-555) 2002.
Gregory Cooper and Changwon Yoo. Causal Discovery from a Mixture of Experimental and Observational Data. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, UAr pp. 116-125, San Francisco, CA, USA, 1999.
Laura Douglas, Iliaan Zarov, Konstantinos Gourgoulias, Chris Lucas, Chris Hart, Adam Baker, Maneesh Sahani, Yura Perov, and Saurabh Johri. A universal marginalizer for amortized inference in generative models. arXiv preprint arXiv: 1.010095, 2017.
Daniel Eaton and Kevin Murphy, Belief net structure learning from uncertain interventions. Mach Learn Res, 1:1-48, 2007a.
Daniel Eaton and Kevin Murphy. Exact bayesian structure learning from uncertain interventions. In Artificial Intelligence and Statistics, pp. 107-1 14, 2007b.
Daniel Eaton and Kevin Murphy. Bayesian structure learning using dynamic programming and MCMC. In Uncertainty in Artificial Intelligence, pp. 101-108, 2007c
Frederick Eberhardr, Clark Glymour, and Richard Scheines. On the number of experiments sufficient and the worst case necessary to identify all causal relations among n variables. arXiv preprint arXiv:1207.1389, 2012.
AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Kun Zhang. Learning causal structures using regression invariance. Advances in Neural Information Processing Systems, pp. 3011-3021, 2017. 2017.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural informa- fion processing systems. pp. 2672-2680, 2014.
Olivier Goudet, Diviyan Kalainathan, Philippe Caillou, Isabelle Guyon, David Lopez-Paz, and Michèle Sebag. Causal generative neural networks. arXiv preprint arXiv:1711.08953 2017.
Olivier Goudet, Diviyan Kalainathan, Philippe Caillou, Isabelle Guyon, David Lopez-Pazz and Michele Sebag. Learning functional causal models with generative neural networks. In Explainable and Interpretable Models in Computer Vision and Machine Learning, pp. 39-80. Springer, 2018.
Isabelle Guyon. Cause-effect pairs kaggle competition, 2013. URL https://www. kaggle. comlc/cause- effect-pairs, pp. 165, 2013.
Isabelle Guyon. Chaleam fast causation coefficient challenge, 2014. URL https:///ww. codalab. org/competiiions//1388 pp. 165, 2014.
Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs. Journal of Machine Learning Research, 13(Aug): 2409-2464, 2012.
David Heckerman, Dan Geiger, and David M Chickering. Learning bayesian networks: The combi- nation of knowledge and statistical data. Machine learning, 2073):197-243, 1995.
10

---

Under review as a conference paper at ICLR 2021
Christina Glinze-Demll Marloes H. Maathuis, and Nicolai Meinshausen. Causal structure learning. Annual Review of Statistics and Its Application, 5:371-391, 2018a.
Christina Geinze-Deml Jonas Peters, and Nicolai Meinshausen. Invariant causal prediction for nonlinear models. Journal of Causal Inference, 6(2), 2018b.
Steven M Hill, Laura M Heiser, Thomas Cokelaer, Michael Unger, Nicole K Nesser, Daniel E Carlin, Yang Zhang, Artem Sokolov, Evan O Paull, Chris K Wong, et al. Inferring causal molecular networks: empirical assessment through a community-based effort. Nature methods, 13(4): 310-318, 2016.
Biwei Huang, Kun Zhang, Jiji Zhang, Joseph Ramsey, Ruben Sanchez-Romero, Clark Glymour, and Bernhard Schölkopf. Causal discovery from betenngencou//nonsttttonnyy data. Journal of Machine Learning Research, 21 219)) 1-33, 2020.
Oleg Ivanov, Michael Figurnov, and Dmitry Vetrov. Variational autoencoder with arbitrary condition- ing. arXiv preprint 1r0iv:1806.022 2018.
Amin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Causal discovery from soft interventions with unknown targets: Characterization and learning. Advances Neural Information Processing Systems, 33, 2020.
Diviyan Kalainathan, Olivier Goudet, Isabelle Guyon, David Lopez-Paz, and Michèle Sebag. Sam: Structural agnostic model, causal discovery and penalized adversarial learning. arXiv preprint arXiv: 04999, 2018.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Murat Kocaoglu, Amin Jaber, Karthikeyan Shanmugam, and Elias Bareinboim. Characteriza- tion and learning of causal graphs with latent variables from soft interventions. In H. Wal- lach, H. Larochelle, A. Beygelzimer, F. d' Alchh Buc, E. Fox, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 32, pp. 14369-1432 Curran As- sociates, Inc., 2019. URL htt.tttppaa//occcciiiiiiieo www.eediiiiiinnnnnnnseeeeeeeeeee neurips wales.cc/ppe http://ccccapp//////ELLLLL. 1o00cccccb1100000000000000000330
pdf
Kevin B Korb and Ann E Nicholson. Bayesian artificial intelligence.
CRC press, 2010.
Kristian Kristensen and Ilse A Rasmussen. The use of a bayesian network in the design of a decision support system for growing malting barley without use of pesticides. Computers and Electronics in Agriculture, 3373):197-217, 2002.
Sébastien Lachapelle, Philippe Brouillard, Tristan Deleu, and Simon Lacoste-Julien. Gradient-basee neural dag learning. arXiv preprint 1906:0906,.0226,,, 2019.
Steffen L Lauritzen and David Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society: Series B (Methodological), 50(2))157-194 1988.
Yang Li, Shoaib Akbar, and Junier B Oliva. Flow models for arbitrary conditional likelihoods. arXiv 2019.
preprint
David Lopez-Paz, Krikamol Muandet, Bernhard Schölkopf, and Iliya Tolstikhin. Towards learning theory of cause-effect inference. In International Conference on Machine Learning, pp. 1452-1461, 2015.
Ricardo Pio Monti, Kun Zhang, and Aapo Hyvarinen. Causal discovery with general non-lin non-linear relationships using non-linear ica. arXiv preprint 1rXiv:1904.09096, 2019.
Joris M Mooij. Sara Magliacane, and Tom Claassen. Joint causal inference from multiple contexts. arXiv preprint arXiv: 10351, 2016.
Judea Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669-680 1995.

---

Under review as a conference paper at ICLR 2021
Judea Pearl. Causality. Cambridge university press, 2009.
Judea Pearl and Dana Mackenzie. The book of why: the new science of cause and effect. Basic Books, 2018.
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), 78(5):97--1012, 2016.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. MIT press, 2017.
Mateo Rojas-Carulla, Bernhard Schölkopf, Richard Turner, and Jonas Peters. Invariant models for causal transfer learning. The Journal of Machine Learning Research, 19(1):100--1342 2018.
Dominik Rothenhäusler, Christina Heinze, Jonas Peters, and Nicolai Meinshausen. Backshift: Learning causal cyclic graphs from unknown shift interventions. In Advances in Neural Information Processing Systems, pp. 1513-1521, 2015.
Karen Sachs, Omar Perez, Dana Pe'er, Douglas Lauffenburger, and Garry P Nolan. Causal protein- signaling networks derived from multiparameter single-cell data. Science, (1:8655)):523--- 2005.
Bernhard Schölkopf, Dominik Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris Mooij. On causal and anticausal learning. In Langford and J. Pineau (eds.), Proceedings of the 29th International Conference on Machine Learning (ICML), pp. 1255-1262, New York, NY, USA, 2012. Omnipress.
Shohei Shimizu, Patrik Hoyer, Aapo Hyvärinen, and Antti Kerminen. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 700c:3:0003320000 2006.
Peter Spirtes, Clark N Glymour, Richard Scheines, David Heckerman, Christopher Meek, Gregory Cooper, and Thomas Richardson. Causation, prediction, and search. MIT press, 2000.
Chandler Squires, Yuhao Wang, and Caroline Uhler. Permutation- based causal structure learning with unknown intervention targets. In Conference on Uncertainty in Artificial Intelligence, pp. 1039-1048. PMLR, 2020.
Xiaohai Sun, Dominik Janzing, Bernhard Schölkopf, and Kenji Fukumizu. kernel-based causal learning algorithm. In Proceedings of the 24th international conference on Machine learning, pp. 855-862. ACM, 2007.
Ioannis Tsamardinos, Laura E Brown, and Constantin Aliferis. The max-min hill-climbing bayesian network structure learning algorithm. Machine learning, 65(1):31-78, 2006.
Jinsung Yoon, James Jordon, and Mihaela Van Der Schaar. Gain: Missing data imputation using generative adversarial nets. arXiv preprint arXiv: 02920, 2018.
Yue Yu, Jie Chen, Tian Gao, and Mo Yu. Dag-gnn: Dag structure learning with graph neural networks. arXiv preprint arXiv: 1904. 100.::9904.009,, 2019.
Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. arXiv preprint arXiv: 2012.
Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. DAGs with NO TEARS: Continuous optimization for structure learning. In Advances in Neural Information Processing Systems, pp.
2018.
Shengyu Zhu and Zhitang Chen. Causal discovery with reinforcement learning. arXiv preprint 1121::1906.04477,.00 2019.
12

---

Under review as a conference paper at ICLR 2021
Appendix
Table of Contents
Annexes
13
A.1
Training Algorithm
13
A.2
Preliminaries
13
A.3
Experimental sctup
15
Model setup)
A.5
Hyperparameters
15
A.6
Synthetic data
15
A.7
BuLearn data repository
16
A.8
Comparisons to other methods
17
A.9
Sparsity Ground- Truth Graph
17
A.
Predicting interventions
18
A.11
Sample complexity
A.12 Elfect of regularization
20
A.13 Near-Optimum Performance of Gradient Estimator
20
A.14 Importance of dropout
21
A ANNEXES
A.1 TRAINING ALGORITHM
Algorithm T shows the pseudocode of the method described in $4 Typical values for the loop trip counts are found in A.11
A.2 PRELIMINARIES
Interventions. In purely-observational setting, it is known that causal graphs can be distinguished only to a Markov equivalence class. In order to identify the true causal graph intervention data is needed (Eberhardt al.) 2012). Several types of common interventions may be available (Eaton & | (007b). These are: No intervention: only observational data is obtained from the ground truth causal model. Hard/perfect: the value of single or several variables fixed and then ancestral sampling is performed on the other variables. Soft/imperfect: the conditional distribution of the variable on which the intervention performed changed. Uncertain: the learner is not sure of which variable exactly the intervention affected directly. Here make use of soft interventions for several reasons: First, they include hard interventions as a limiting case and hence are more general. Second, in many real-world scenarios, it is more difficult to perform hard intervention compared to a soft one. We also deal with special case of uncertain interventions, where the variable selected for intervention is random and unknown. We call these unidentified unknown interventions.
Intervention setup. For our experiments, the groundtruth models of the synthetic datasets are modeled by neural networks as described in section A.6 Each neural network models the relationship of the causal parents and a variable, We perform our intervention by first randomly selecting which variable intervene on, then soft-intervening on The selected variable sampled from uniform distribution. The soft intervention is reinitialization of its neural network's 's parameters.
Causal sufficiency. The inability to distinguish which causal graph, within a Markov equivalence class, is the correct one in the pusery-observationaal setting is called the identifiability problem. In our setting, all variables are observed (there are no latent confounders) and all interventions are random and independent. Hence, within setting, if the interventions known, then the true causal
13

---

Under review as a conference paper at ICLR 2021
Algorithm Training Algorithm
1: procedure TRAINING($CM Ground Truth Entailed Distribution D, with M nodes and N categories)
2: Let i an index from 0 to M -
for iterations, or until convergence, do
4: if & reinitializatioon period = 0 then
5: D + reinitializiiiieeeeee
6:
for F functional parameter training steps do X D (7)(
Phase 1
7:
9:
= log P
10:
0c+1 Adam(O: dz. VoL)
11:
for Q interventions de
Phase
N + randint (0, M 1)
Uniform selection of target D Apply intervention
13:
Dim == D with intervention on node I
14:
predicting intervention then +0 Vi
Phase 2 Prediction
15:
16:
for Np prediction steps do X ~ Din
17:
18:
for Cp configurations do
19:
C ~ Ber(((())
20:
L <- L1 log (,( 0am Vi
21:
I N < argmax((.)
gammagrads, logregrets [], []
b Phase Scoring
23:
for Nş scoring steps do
24:
X ~ Dim
25:
gammagrad, Logregret
26:
for Cs configurations
27:
(e)(
28:
L log P. (x frow) Vi
29:
gammagrad +- (12) C
Collect (()) C for Equation
30:
logregret N
Collect (x. for Equation
31:
gammagrads apppaag
append (gammagrad)
32:
logregrets append appeed (logregret)
Phase
9:j Ex(o(T)) - (x.
33:
Gradient Estimator, Equation
Σx (xx(X)
- + V, (Aypusse Iepurso (7) + ADAG LnAG(T))
Regularizers
35:
7++1 + Adam(
graph is always identifiable in principle (Eberhardt et al. 2012 Heinze- et al. 2018a). We also consider here situations where single variable is randomly selected and intervened upon with soft imprecise intervention, its identity is unknown and must be inferred. In this case, there is no theoretical guarantee that the causal graph identifiable. However, there existing work PPterr et al.) (2016) that handles this scenario and the proposed method is also proven to work empirically.
Faithfulness. is possible for causally-related variables to be probabilistically independent purely by happenstance, such when causal effects along multiple paths cancel out. This is called unfaithfulness. We assume that faithfulness holds, since the ? gradient estimate is extracted from shifts in probability distributions. However, because of the "soft" nature of our interventions and their infinite variety, it would be exceedingly unlikely for cancellation unfaithfulness to persist throughout the causal-leane causal-learning procedure.
14

---

Under review as a conference paper at ICLR 2021
A.3 EXPERIMENTAL SETUP
For all datasets, the weight parameters for the learned model is initialized randomly. In order to not bias the structural parameters, all ((7) are initialized 0.5 the beginning training. Details of hyperparameters of the learner model are described in Section A.5 The experimental setup for the
groundtruth model for the synthetic data can found in Section A.6 and the details for the real world data are described in Section A.7
A.4 MODEL SETUP
As discussed in section we model the M variables in the graph using M independent MLPs, each possesses input layer of M N neurons (for M one-hot vectors of length N each), single hidden layer chosen arbitrarily to have max(4M, 4N) neurons with a LeakyReL.U activation of slope 0.1, and linear output layer of N neurons representing the unnormalized og-probabiliitis of each category (a softmax then recovers the conditional probabilities from these logits). To force fa rely exclusively on the direct ancestor set pa C)) under adjacency matrix C' (See Eqn. 2). the one-hot input vector X, for variable X; s MLP is masked by the Boolean element Gij. The functional parameters of the MLP are the set shins B0sh, W1 inh: Bl |AAn example of the multi-MLP architecture with M=3 categorical variables of N=2 categories is shown in Figure] 3
A.5 HYPERPARAMETERS
Learner model. All experiments on the synthetic graphs size 3-8 use the same hyperparameters. Both the functional and structural parameters optimized using the Adam optimizer Kingma & Ba (2014). We use a learning rate 5e with alpha of 0.9 for the functional parameters, and we use learning rate of 5e with alpha of 0.1 for the structural parameters. We perform runs of each experiment with random seeds 1 - and error bars are plotted for various graphs from size to 8 in Figure 4 We use batch size of 256. The LI norm regularizer is is set to 0.5 for all experiments. For each update step, we sample 25 structural configurations from the current y. In all experiments, we use 100 batches from the interventional distribution to predict the intervened node.
0.1 and the DAG regularizer
A.6 SYNTHETIC DATA
B
chain3
fork3
collider3
confounder3
Figure 5: Every possible 3-variable connected DAG.
Synthetic datasets. The synthetic datasets in the paper are modeled by neural networks. All neural networks are 2 layered feed forward neural networks (MLPs) with Leaky ReLU activations between layers. The parameters of the neural network are initialized orthogonally within the range of (-2.5, 2.5). This range was selected such that they output a non-trivial distribution. The biases are initialized uniformly between (-1.1, 1.1).
SCM with n variables are modeled by n feedforward neural networks (MLPs) as described in $5.1 We assume acyclic causal graph so that may easily sample from them. Hence, given any pair of random variables A and B, either A + B, B + or A and B are independent.
The MLP representing the ground-truth SCM has its weights 0 initialized use orthogonal initialization with gain 2.5 and the biases are initialized using a uniform initialization between -1.1 and 1.1, which empirically found to yield "interesting" yet learnable random SCMs.
15

---

Under review as a conference paper at ICLR 2021
n
I
(a) chainN
(b) colliderN
(c) bidiagN
TH
I+-2
3
(d) fullN
(e) jungleN
Figure 6: Figures for various synthetic graphs. chsin, collider, bidiagonel, Full and jungle graph.
We study a variety of SCMs with different ground-truth edge structures y, Our selection of synthetic graphs explores various extremes in the space of DAGs, stress-testing [DD The chain graphs are the sparsest connected graphs possible, and are relatively easy to learn. The bidiag graphs extensions of chain where there 2-hops as well single hops between nodes, doubling the number of edges and creating a meshed chain of forks and colliders. The jungle e graphs are binary-tree-lite graphs, but with each node connected directly to grandparent the tree as well. Half the nodes in a jungle graph are leaves, and the out-degree is up to 6. The coll silider graphs deliberately collide independent M 1 ancestors into the last node; They stress maximum in-degree. Lastly, the full 1 graphs are the maximally dense DAGs. All nodes are direct parents of all nodes below them in the topological order. The maximum in- and out-degree are both M - These graphs are depicted in Figure 6
A.6.1 SYNTHETIC DATA RESULTS
The model can recover correctly all synthetic graphs with 10 variables or less, shown in Figure 10 and Table For graphs larger than 10 variables, the model found it more challenging to recover the denser graphs (e.g. ful 1M), as shown in Table Plots of the training curves showing average cross entropy (CE) and Area-Under Srea-Under-Curve(AA Curve(AUC/AUCRROC for edge probabilities of the learned graph against the ground-truth graph for synthetic SCMs with 3-13 variables are available in Figure
A.7 BNLEARN DATA REPOSITORY
The repo contains many datasets with various sizes and structures modeling different variables. We evaluate the proposed method on of the datasets in the repo, namely the Earthquake (Korb & Nicholson 2010), Cancer (Korb & Nicholson 2010) and Asia (Lauritzen & Spiegelhalter 1988) datasets. The ground-truth model structure for the Cancer (Korb & Nicholson (010) and Earthquake Koor & Nicholson 2010) datasets are shown in Figure 7 Note that even though the structure for the two datasets seems to be the same, the conditional probability tables (CPTs) for these datasets are very different and hence results in different structured causal models (SCMs) for each.
16

---

Under review as a conference paper at ICLR 2021
Figure 7: Left to right: Ground Truth SCM for Cancer, Groundrruth SCM for Eartquaake, Groundirath SCM for Asia.
Method
Asia
chain8
jungle8
collider7
collider8
ful18
Zheng et al., 2018
24
18
Yu et al. 2019)
10
7
12
7
25
Heinze- Deml et al.
2018b
Peters et al.
2016
3
8
2
16
Faton & Murphy
2007a)
0
0
7
SD14
0
0
0
0
Table Baseline comparisons; Hamming distance (lower for Ieamed ground-truth
graphs from beth synthetic and real datasets, compared to (Poters et al. (2016), [Heinze-Deml et (20186). (Eaton Marphy (2007)) et 2019) and (Zheng al. The proposed SDi run on random seeds and we pick the worst perforning model out of the random seods the table.
2018
Figure 8: Leamed odges at three different stages of training. Left: chaind (chain graph with 4 variables), Right: Full4 (tournameut graph variables).
A.8 COMPARISONS TO OTHER METHODS
As described in section 5.4 we compare to 5 other methods. The full comparison between SDI$ and other methods various graphs be found in Table
One of these methods, DAG-GNN Yu et al. (2019), outputs graphs based on different criteria: best mean square eπrоr (MSE), best negative logli loglikelihood (NLL) and best evidence lower bound (ELBO). We report performance of all outputs of DAG-GNN Yu et al. (2019) in Table 6 and the best one is selected for Table
A.9 SPARSITY OF GROUND-TRUTE GRAPH
We evaluated the performance SDI on graphs of various size and sparsity to better understand the performance of the model. We evaluated the proposed model on 4 representative types of graphs in increasing order of density. They are the chain, jungle, bidiag and full 1 graphs. As shown in the results in figure [2] for graphs of size 5 smaller, there is almost no difference in the final results in terms of variance and sample complexity. However, as the graphs gets larger (than 6), the denser graphs (full graphs) gets progressively more difficult learn compared to the sparser graphs (chain, jungle and bi bidiag). The models learned for denser graphs have higher complexity, higher variance and slightly worse results.
17

---

Under review as a conference paper at ICLR 2021
Figure Top Left: Earthquake: Leared edges different stages training. Top Right: edges at three different stages
training. Bottom: chain10 different stages of training, clearly displaying Markov--quivalencee of causal and anti-causal chain. Training resolves in causal direction after further training.
SDI
Best MSE
Best NLL
Best Elbo
Asia
0
10
10
13
chain8
0
7
7
jungle8
0
12
12
13
collider7
0
6
collider8
0
8
8
7
ful18
0 27
27
Table 6: Baseline comparisons: Hamminng distance (loweria is betler) for leurned and ground truth edges on Asi and various synthetic graphs. compared DAG-GNN BAG-GNN|VV Yu (019). DAG-GNN ourputs graphs according different criterion. We show results all outputs this table and we show the best performing result in Table
A.10 PREDICTING INTERVENTIONS
In Phase 2. we score graph configurations based on how well they fit the interventional data. We find that it is necessary avoid disturbing the learned parameters of intervened variables, and to ignore its contribution to the total negative log-likelihood of the sample. Intuitively, this is because, having been intervened upon, that variable should be taken as poorly-leameed variable requiring a tuning of its functional parameters, because those functional parameters were responsible for the value of that variable; The extrinsic intervention was.
given. It should especially not be interpreted
Since an intervened variable is likely to be unusually poorly predicted, we heuristically determine that the most poorly predicted variable is the intervention variable. We then out contribution to the log- ligeliil of the sample and block gradient into its functional parameters.
Figure II illustrates the necessity of this process. When using the prediction heuristic, the training curve closely tracks training with ground-truth knowledge of the identity of the intervention. If no prediction made, or a random prediction is made, training proceeds much more slowly, or fails entirely.
A.11 SAMPLE COMPLEXITY
Our method is heavily reliant on sampling of configurations and data in Phases and 2. We present here the breakdown of the sample complexity. Let
I be the number of iterations of the method,
(typical: 500-2000)
B the number of samples per batch,
(typical: 256)
the number of functional parameter training iterations Phase 1,
(typical: 10000)
the number of interventions performed in Phase 2,
(typical: 100)
Np the number of data batches for prediction,
(rypical: 100)
18

---

Under review as a conference paper at ICLR 2021
Chain
Jungle
Full
3 5
6
8
3
5
6
8 3
5
6
8
Idag=0.5, Isparse=0.1
0
0
0
0
0
Idag=0.5, lsparse=0.
0 0 0 0 0
0 0
0 0
0 0
Idag=0., Isparse=0.1
0
0
0
1
Table 7: Regularizer: SDI performance messured by Hamming distance the ground-truth graph. Comparisons are between SD) with
different regularizer settings for different graphs. Our default setting is Idag 0.5, Isparse = 0. I. with Idag the DAG regulaniztion strength and lsparse the sparsity regularization strength. shown in the table, Tasks with non-2ero Hamming distance (ertors) are in bold.
very sensitive different regularizer settings.
1.2
12
1.2
122
chaina
co2lidex3
Chaind
co2lidord
chain5
Gamma Crows mote-Barge (oog bite)
o931 idees
(ong
0.8
chain6
chain7
chain8
0.8
0.8
co2lidezé
c031 idezé
o2l1dexx
08
chain9
collider9
chain10
Arna Unddr
collidor10
caainil
collider1]
chain12
colli6er12
chaini3
co 1der13
0.2
0.2
0.2
01
10K
20K
S0X
10%
50%
0K
10K
20K
30K
60K
508
Stape (df)
(4))
1.2g
1.
1.2g
1.0
jungleS
Jungled
Gamms Crowe Datopy (vng bit)
JungleS
Junglo6
0.8
jungle7
0.8
0.8
0.8
Jungles
Jungle
Unier
Cross
Jungle10
junglett
04
Jungle12
0.4
8.4
0.4
Junglei3
0.2
0.0 0K
0.0
0.0 08
0.0
10K
20K
50X
603C
50%
LOK
20X 500
600C
500
Steps (4)
Staps (4)
Figure Cross entropy SCMs. Error bars represent lo over PRNG seeds 1-5. Left to right, to down: chainM,.jugi jungienngnnnna. et wofffullx.hh 1x = 3 8 (9. 13 in Appondix A. Graphs (3-13 variables) learn perfectly with AUROC reaching 1.0. However, denser graphs (fullM) take longer converge.
Mea--unde-CCrve (AUC/AUROC) edge probabilities leamed graph against ground-truth synthetic
Cp the number of graph configurations drawn per prediction data batch,
(rypical: 10)
Ns the number of data batches for scoring,
(typical: 10)
Cs the number of graph configurations drawn per scoring data batch.
(typical: 20-30)
Then the total number of interventions performed, and configurations and samples drawn, over entire run are:
Interventions IQ = 7 updates
Samples [( F + Q(Np + Ns)
(4)
Phase
Pluse
Configurations T(
F QCCr + CsNss)
(5)
Phuse
Phose 2
Because of the multiplicative effect of these factors, the number of data samples required can quickly spiral out of control. For typical values, as many as 500 x 10000 x 256 = 1.28c9 observational and 500 x 100 x (100 + 10) x 256 1.408c9 interventional samples are required. To alleviate this problem slightly, we limit the number of samples generated for each intervention; This limit is usually 500-2000.
19

---

Under review as a conference paper at ICLR 2021
1,2
1.2
chain?
Gomma Crowe Enteepp (erg brta))
chais? grond truth
Contradde prediction
fu117
0.8
0.5
fu117 ground truth
Gamms Crose Entrope
jungla7
peodictios
Jungl ground
0.8
0.2
0.0
00
<K
8K
12KC
18K
2010
OK
10K
201
30K
4000
501C
Staps (dF)
Staps (dF)
Comms Crows Datmpy (aog hite)
1.0
15
grnngll35
0.5
0.4
01.0
0K
10K
20K
30%
400
30K
6UK
7UK
90K
100K
100K
Stage (88)
Figure Ablution Study Intervention
entropy over
prediction multiple graphs
Above Left: All 3-variable graphs. Solididashed lines: Ground-truth & Prediction strategies. Dotted lines: Random- & No-Prediction strate gics. Training with prodiction closely tracks ground-truth. Above Right: Comparison for 7-variable graphs, ground-truth against prediction strategy. Trainin with prediction still closely tracks ground-truth larger seales. Below: Performance on 15-variable graphs with known intervention targets.
A.12 EFFECT OF REGULARIZZTION
Importance of sparsity regularizer. We use L1 regularizer on the structure parameters 7 to encourage sparse representation edges the causal graph. In order better understand the effect of the L1 regularizer, we conducted ablation studies on the L1 regularizer. It seems that the regularizer has an small effect on rate of converges and that the model converges faster with the regularizer, This is shown in Figure 13 However, this does not seem to affect the final value the model converges to, as shown in Table
Importance of DAG regularizer. We use an acyclic regularizer to discourage length-2 cycles in the learned model. We found that for small models (< 5 variables), the acyclic regularizer helps with faster convergence, without improving significantly the final cross-entropy. This illustrated for the 3-variable graphs in Figure 14] However, for graphs larger than variables, the acyelic regularizer starts playing an important role in encouraging the model to learn the correct structure. This is shown in the ablation study Table 7
1. NEAR-OPTIMUM PERFORMANCE OF GRADIENT ESTIMATOR
The gradient estimator 95j we use minimize the empirical risk w.r.f. the structural parameters 7, defined in Eq. i adapted from Bengio al. (2019). We verify that the estimator samples the correct gradient by an experiment that tests convergence near the optimum.
To do this, we pre-initialize the structural and functional parameters near the global minimum, and verify that converges. Specifically, the ground-truth functional parameters are copied and disturbed by small Gaussian noise, while the ground-truth structural parameters copied, but the confidences in an edge or non-edge are set to 88% and 12% rather than 100% and 0%. The experiment is then expected quickly converge the global minimum.
20

---

Under review as a conference paper at ICLR 2021
185
Jenglaco
Dapa (9)
Figure 12: Left right, top botlom Average enoss-entropy loss of edge beliefs (7y) and Uaner-nnder-ree Curve throughout training for the synthetic graphs chainnt nN, Jusngll,, col dert and full N=3-13, grouped graph size. Error hars represent d: la PRNG seeds 1-5.
gennty0001
spanitute oo spamity
spmniy011 0.1
Figure Effect sparsity (1sparse) regularizer:
and
As shown in Figure 16 the gradient estimator correctly enables Stochastic Gradient Descent towards the minimum, for the cha in and jungle graphs of size 15, 20 and 25. The average cross-entropy rapidly approaches its floor of 0.01, a consequence of our clamping of all Thy to the range +55 (equivalently, clamping (1wy) to the range 0.9933...
A.14 14
IMPORTANCE OF DROPOUT
To train the functional parameters cency matrices. One may be tempted to make these "complete directed graph" (all-ones except for a zero diagonal), to give the MI.P maximum freedom learn any potential causal relations itself. We
observational distribution, would need sampling adja-
21

---

Under review as a conference paper at ICLR 2021
LDAG
Ganaa Cros- Sanney (ere MAN
chwin3,
Fora3, LDAG
0.8
collider3, 1DAG
iider,,
cunfounderS, LIAG
confousder3, LDAG
chain3
62
0.0
cord Gunder
101C
Stepe (2)
Figure 14: Ablations study results on possible variable graphs. Graphs show the entropy loss learned ground-truth edges over training time. Comparisons of model trained with and without DAG regularizer (Luwa), showing that DAG regularizer helps convergerice.
Figure 15: Edge CE loss for 3 3-variable griphss with dropout when training functional parameters, showing the importance of this dropout.
0. 20
chain20
0.15
chain25
Choss Enizopy (ang
jungle15
Jungle20
jungle22
0.10
0.05
Steps
(#)
Figure Near-optima performance gradient estimator: Performance on Sungle, 1a, 15, 20, initialized near the global optimum. Illustrates correctness and rapid convergence using the gradient estimator in Eq 2 neaar the optimum.
demonstrate that functional parameter training cannot be carried out this way, and that it is necessary to "drop out" each edge (with probability of the current y value in our experiments) during pre- training of the conditional distributions of the SCM. We attempt to recover the previously-recoverae graphs chain3, Eork3 and confounder: without dropout, but fail to do so, as shown in Figure
15
Eaton & Murphy
2007b)
Asia
chain8
jungle8
collider7
collider8
0.0
7
ful18
0.0
Table Comparisons:
Siructured hamming
(SHID)
ground truth edges asia
synthetic gruphs.
& Murphy 20077) can not scale to larger variables graphs shown in Table hence, we compare to the largest graph that (Faton & Murbhy 20076 can scale up to SDIlis compared (Eaton Murphy 20076) for col Lider7, coll 1idee ful18, (aton Murphy 2007 asserts with 100% condiencc no-edge where there is one (Tabse negative). For comparisens with other methods
22

---

Under review as a conference paper at ICLR 2021
2000
12:00
2000
1200
1000
Figure Cross-entropy for edge probability between Iearned and ground-truth SCM. Left: The Earthquake dataset with variables. Right: The Asia dataset with vari-
Figure 17: Cross-entropy for edge prob- ability between learned and ground-ruth SCM for Cancer varying lemperatures.
23


Reviews:
[{"review_id": "y7d05UqM_df", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a 3-phase heuristic algorithm to learn a causal graph from interventional data using continuous optimization. Unfortunately, the paper is hard to follow. Specifically, the exact procedure should be clarified by the authors. If I understand correctly, first they fit to observational data by searching over the space of graphs using a smooth representation for the adjacency matrices. To fit to the interventional data, first, the interventional target is estimated by a heuristic approach and the contribution of these variables to the likelihood is ignored since they are set by the experiment. (there are random graph sampling stages in between that are not clear to me, please elaborate on this). This interventional scoring is done for all interventional data and is turned into a single gradient update.\n\nThe paper is hard to parse. My main concern is that, unlike the existing work which the authors compare with in the experiments, the proposed method is not a systematic approach and accordingly it is hard to reason about its use even though it performs well in the experiments. Especially given that some choices made in the algorithm design are not properly justified. Indeed, even with interventions, we do not expect to recover the full structure but only a subset of the edges correct. \n\nComparisons with the other methods should be expanded into a section where these methods are detailed to showcase the methodological differences. \n\nThe following are my detailed feedback.\n\n\"A natural application of Bayesian networks is to describe cause-effect relationships between variables.\"\nPlease distinguish Bayesian networks from the causal networks. Former do not carry causal meaning. \n\nA good reference to cite in addition to Peters et al. for SCMs is Pearl's 2009 Causality book. \n\n\"Although there is no theoretical guarantee that the true causal graph can be identified in that setting, evidence so far points to that still being the case.\"\nPlease modify this statement as it sounds too vague. \n\nThe list of contributions require knowledge of the latter sections. Please make it self contained if possible. \n\n\"can't\"->\"can not\"\n\nSCM definition is not only structural equations but also talks about interventional distributions. Please see Pearl 2009.\n\nThe last line in page 2 overlaps with the page number. \n\nSome recent related work is missing: \n\nMooij et al. \"Joint Causal Inference from Multiple Contexts\" JMLR'20.\nKocaoglu et al. \"Characterization and Learning of Causal Graphs with Latent Variables from Soft Interventions\" NeurIPS'19.\nBrouillard et al. \"Differentiable Causal Discovery from Interventional Data\" arXiv'20.\n\nMooij et al. is cited but please add it in Section 3 among constraint-based inverventional learning frameworks as well.\n\nBrouillard et al. is too recent, hence its omittance is understandable. However, it attacks the same problem considered here. I believe including it as independent discovery would help connect literature together nicely. I am not going to take this work into consideration in my evaluation since it is uploaded on arXiv only very recently.\n\n\"the methods only uses\"->\"the methods only use\"\n\nciting Murphy \"This is different from our setting where the intervention is unknown to start with and is assumed to arise from other agents and the environment.\"\nMurphy can handle unknown interventions as well. Moreover Mooij et al. handles unknown interventions too. \n\n\"The set of functional parameters θi parametrizes the conditional probability distribution of Xi given its parent set Xpa(i,C), with C ∼ Ber(σ(γ)) a hypothesized configuration of the SCM’s DAG.\"\nCan you clarify this sentence?\n\n\"During Phase 1, the functional parameters θ are trained to maximize the likelihood of randomly drawn observational data under graphs randomly drawn from our current beliefs about the edge structure.\"\nWhy do you draw synthetic data? Likelihood is typically maximized using real data at hand. It's hard to follow the exact procedure here. \n\nIntervention targets are predicted using a heuristic. Why not use the existing methods? I believe the computational aspect is seen as a problem but JCI by Mooij et al. should be fast enough. \n\nCan you convert Section 3 into a pseudo-code for the algorithm description? I believe many details are skipped and some key points of the approach is not clear by the brief text in each subsection. \n\n\"should be taken as givens\"->\"should be taken as given\"\n\nIn the experiments, please compare with Mooij et al. Their method should be as fast as FCI and it would be interesting to see how the results compare. \n\n==== After the Response by the Authors ====\n======================================\nThank you for the detailed reply. For the clarifications the authors made to the algorithm description, I will increase my score. \n\nThe authors state \n\"If the scientific community had waited for deep learning to prove that it could discover the true conditional distribution of outputs given inputs, we would not have had the progress we achieved in the last two decades in AI. We believe that it is important to take into consideration all sources of evidence about the usefulness of a method, and experimental evidence is at the heart of the success of the scientific method and should not be discarded because of an established cultural habit of relying on proofs of identifiability.\"\n\nNote that the objections I (R1), and I believe also R3 and R4, have are not about theoretical vs. experimental research and that the paper lacks proofs or identifiability results. It is perfectly fine to not have a theoretical understanding of a proposed algorithm. But the authors should be able to justify the choices they made in the algorithm design, and especially in light of the prior work. The main justification given by the authors both in the paper and in their rebuttal is that the algorithm performs well. I believe the paper needs an iteration to address these issues. \n\nThe following is my detailed feedback in addition to my original review in light of the authors' response. I hope this will help the authors in improving their paper.\n\nOn fully learning the causal graph:\nI suggest the authors examine and try to identify, in small graphs, what aspect of their method allows it to perform better than the existing methods such as JCI or allows it to go beyond the existing equivalence classes. Without such justification, I do not think the paper in its current form will influence future research. \n\nRemark on interventions having variety: \nThis is not sufficient for exact recovery. Imagine intervening on the same node with different mechanisms over and over. This does not allow recovery outside of the local structure around the intervened node for most causal graphs. This also relates to the remark above. Full identifiability is always related to having variety in the intervention targets and not just in interventional mechanisms. This is why some of the datasets where the exact graph is recovered by the algorithm need a detailed investigation.\n\nAbout synthetic experiments:\nOne explanation for full structure recovery in the synthetic experiments could be the following: The authors randomly pick one target variable to intervene on. My guess is that this randomness in the experiment design is sufficient to have diverse enough target sets for the equivalence class to shrink to a single graph. Can you verify/check this?\n\nHow many interventions do you use in the synthetic experiments? How many samples are collected per intervention? Unless I am missing something, these are not provided until page 19 but then it is not clear if these numbers are kept identical throughout the experiments. x-axis is set to be # of episodes or # of steps in most experiments whereas # of samples would be more informative.\n\nAbout JCI comparison:\nI did not completely understand why the authors could not run JCI in synthetic data. They say it is due to its complexity. But JCI's complexity comes from the graph degree and not from the number of samples for a small enough state space. It would be very interesting to compare what JCI learns relative to the proposed method in these synthetic experiments. This should test my hypothesis above that the random intervention target is providing enough diversity to reduce the equivalence class to one graph, which should be detected by JCI.\n\nInferring a Markov equivalence class from the adjacency matrix by early stopping is definitely an interesting idea and I would encourage the authors to further pursue and formalize this direction. \n\nSample complexity:\nThe authors mention that their method is \"sample-hungry\". Given that the method presents significant divergence from the standard literature on causal inference that relies on conditional independence tests, which are known to require many samples, it is especially important to clearly present the number of samples used by the method. The main paper does not present the number of samples used in the synthetic experiments. These should be made explicit. \n\nFinally, the title and abstract still state \"dependency structure discovery\" and learning \"Bayesian networks\" whereas the authors attempt to learn causal graphs from interventions. I suggest an update to the narrative to clarify the objective of the paper.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "wfgQc35ybWY", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a method for structure learning from observational and interventional data that uses a continuous optimization method. Data is discrete-valued, there are no hidden confounders, each intervention affects only one variable, but the location of it may be unknown. A three-phase score-based, iterative procedure is proposed.\n- This work considers that in each interventional dataset, only one variable is intervened on. If we do not know about the target of the intervention, it seems reasonable that we also assume that we are not aware of the number of the targets.\n- Unfortunately there are no results in the paper about what the output of the algorithm will actually be. Suppose we have only few interventional datasets (which is usually the case in reality). What can we say about the output of the algorithm? It is known that in this case, Interventional Markov equivalence class is the extent of identifiability [Hauser and Bulmann, 2012]. Can we hope that the algorithm returns an element from this class?\n- In the Appendix, it is mentioned that the method typically requires 500-2000 iterations and 100 interventions per iteration. This means that around 10^5 interventions are needed. Also about 10^9 samples are needed. We note that in reality for example in medical data, we usually have access to very few interventional datasets each containing about 100 samples.\n- It is not clear how the method performs on a graph with no prior structure knowledge with 30 vertices (which is a number that is usually not considered large in structure learning). Seems like this order is too large for the proposed method.\n- The intervention prediction step in Phase 2 sounds very heuristic and is not clear under what conditions it will work. Also, it seems that it requires strong interventions.\n- Regarding preventing the algorithm from returning cyclic structures, the authors state that suppression of more than length 2 cycles was not found to be worthwhile for the increased computational expense. This simply means that the algorithm may return cyclic structures which is contradictory to the original goal.\n- There are other work on learning from interventions with unknown targets, for example: [Squires et al., Permutation-Based Causal Structure Learning with Unknown Intervention Targets], or [Huang et al., Causal Discovery from Heterogeneous/Nonstationary Data].\n- The definition of SCM given in the Introduction is only true for the case of causal sufficiency.", "extra_scores": {}, "extra_text": {}}, {"review_id": "qggTAi_RG4L", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": " Recommendation to Accept\n\n##########################################################################\nSummary:\nThe paper provides a novel approach in the area of structure learning for causal bayesian networks. The authors suggest an iterative method, that builds on the widely accepted do-formalism. The approach suggested fits the network before interventions, simulates the intervention on the fitted network and then again assigns a likelihood score to the network parameters\n\nThe paper concisely describes a novel algorithm used in the notoriously difficult problem of causal structure learning. The contributions are clearly stated. The accompanying expiremental reuslts suggest a competitve perfomance, especially reagarding scaling the counts of variables\n\nI recommend to accept it, even though a few details could have been described more precisely.\n\n1. The definition of interventions is done extremely briefly, (sec. 2), however in my opinion the choice of definitions used here would justify some accompanying examples for clarification (this would help especially to understand what is meant with \"infinite intervention regimes\" (sec. 4) \n\n2. The assumption \"no control over interventions\" is not clear per se, here it would help to understand what the omittance of this assumption would imply.\n\n3. A clarification, why \"the interventions can either be known or unknown\", provides a relaxation of the formulation used (sec. 4.2) would be useful", "extra_scores": {}, "extra_text": {}}, {"review_id": "m15EqJyLu1w", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims to extend the continuous optimization approach to causal discovery to handle interventional data as well as observational data. It describes a method for learning the causal structure over a set of categorical variables and reports strong empirical performance. However, no theoretical guarantee or analysis is provided, which is a significant weakness in my view. It also makes no comment on or comparison to a paper that has essentially the same goal, https://arxiv.org/pdf/2007.01754.pdf. The latter paper seems to me more principled and convincing.  \n\nThe heuristic for predicting an unknown intervention target looks very dubious to me. I would appreciate some explanation of why the target should be expected to have the biggest drop of log-likelihood. \n\nThe description of the proposed method could be clearer; for example, it helps to provide an explicit formulation of the SGD used in the method.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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