Neural Causal Structure Discovery from Interventions
Authors: Nan Rosemary Ke
Olexa Bilaniuk
Anirudh Goyal
Stefan Bauer
Hugo Larochelle
Bernhard Schölkopf
Michael Curtis Mozer
Christopher Pal
Yoshua Bengio
Venue: Accepted by TMLR ()

Abstract: Recent promising results have generated a surge of interest in continuous optimization methods for causal discovery from observational data. However, there are theoretical limitations on the identifiability of underlying structures obtained solely from observational data. Interventional data, on the other hand, provides richer information about the underlying data-generating process. Nevertheless, extending and applying methods designed for observational data to include interventions is a challenging problem. To address this issue, we propose a general framework based on neural networks to develop models that incorporate both observational and interventional data. Notably, our method can handle the challenging and realistic scenario where the identity of the intervened upon variable is unknown. We evaluate our proposed approach in the context of graph recovery, both de novo and from a partially-known edge set. Our method achieves strong benchmark results on various structure learning tasks, including structure recovery of synthetic graphs as well as standard graphs from the Bayesian Network Repository.

Published in Transactions on Machine Learning Research (08/2023)
Neural Causal Structure Discovery from Interventions
Nan Rosemary Ke Google Deepmind
noeemary.wen..ee@mmal.coom
Olexa Bilaniuk" Mila
obilaniu@gmaill.com
Anirudh Goyal
andrudlgoyal91 19tpg/lll1111.mmm.m.mmom
Google Deepmind
Stefan Bauer Technical University of Munich
st. R..bauer@tum.ccom de
Hugo Larochelle
hugolaruchellle@yyggg.cco
Google Deepmind
Bernhard Schölkopf
bs@tucbingen.mpg..d
Mar Planck Institute for Intelligent Systems
Michael C. Mozer
memozer@@google..om
Google Deepmind
Chris Pal Mila, Polytechnique Montreal
christapher.pal@yyllyee
Yoshua Bengio
yoshua.bergio Eerrilaiiiiiiii..om queber
Mila, Universily of Moutreal, CIFAR Senior Fellow
Reviewed on OpenReview: https: // openreview. net/ form/? id= vdVPPUUP
Abstract
Recent promising results have generated a surge of interest in continuous optimization methods for causal discovery from observational data. However, there are theoretical lim- itations on the identifiability of underlying structures obtained solely from observational data. Interventional data, on the other hand, provides richer information about the un- derlying data-generating process. Nevertheless, extending and applying methods designed for observational data to include interventions a challenging problem. To address this issue, we propose a general framework based on neural networks to develop models that incorporate both observational and interventional data. Notably, our method can handle the challenging and realistic scenario where the identity of the intervened upon variable is unknown. We evaluate our proposed approach in the context of graph recovery, both de novo and from partially-known edge set. Our method achieves strong benchmark results on various structure learning tasks, including structure recovery of synthetic graphs as well as standard graphs from the Bayesian Network Repository.
1 Introduction
Structure discovery concerns itself with the recovery of the graph structure of Bayesian networks from data. When Bayesian networks are used to model cause-effect relationships and are augmented with the notion of
"Equa contributions

---

Published in Transactions on Machine Learning Research (08/2023)
interventions and counterfactuals, they can be represented as structural causal models (SCM). While Bayesian networks can uncover statistical correlations between factors, SCMs can be used to answer higher-order questions of cause-and-effect, up in the ladder of causation (Pearl & Mackenzie, 2018). Causal structure learning using SCMs has been attempted in several disciplines inchuding biology (Sachs et al., 2005; Hill et al., 2016), weather forecasting (Abramson et al., 1996) and medicine (Lauritzen Spiegelhalter, 1988; Korb & Nicholson, 2010).
Structure can be learned from observational or interventional data. Observational data is sampled from the distribution without interventions; alone, it contains only limited information about the underlying causal graph (Spirtes ct al., 2000). Without making restrictive assumptions about the data generating process (Shimizu et al., 2006), interventional data is needed in order to fully identify the true causal graph (Eberhardt & Scheines, 2007; Eberhardt, 2012; Eberhardt et al., 2012).
Recently, there has boen a surge of interest in using continuous optimization methods, often involving neural networks, to discover causal relationships from observational data (Zheng et al., 2018; Yu et al., 2019). These methods frame the search for a causal graph or directed acyelic graph (DAG) as continuous optimization problem, avoiding the need to search through super-exponential number of graphs 2018a). While these methods have shown competitive performance compared to classic causal discovery approaches, they are limited to working with only observational data. Our proposed method Structure Discovery from Interventions (SDI) is among the first causal discovery methods based on neural networks that utilize both observational and interventional data. Several subsequent works have built upon our proposed method, SDI. For instance, some works have explored the use of different gradient estimates (Brouillard et al., 2020; Lippe et al., 2021); while others have applied SDI in the active causal learning setting to determine where to intervene (Scherrer et al., 2021).
Derinze-Demll et al.,
We introduce a novel neural network- bease method for causal discovery called Structure Discovery from Interventions (SDI). Unlike previous methods, SDI utilizes both observational and interventional data. Our model out autpefforms previous methods on both synthetic and naturalistic Causal Bayesian Networks (CBNs). In addition, interventions the real world may be performed by unknown agents, making them unknown interventions. Our model, SDI, can handle such unknown interventions by predicting the index of the node where the intervention may have occurred.
In some cases, the graph structure may be partially provided but needs to be completed. An example is protein structure learning in biology, where we may have definite knowledge about some parts of the protein-protein interaction structure but need to fill out other parts (Glymour et al., 2019). We refer to this as partial graph completion. In this selting, we evaluate our model and demonstrate its strong performance.
To summarize, the main contributions of the paper as follows. 1) causal discovery algorithm SDI, which leverages both observational and interventional data. 2) We show that SDI outperforms previous methods both synthetic data, as well naturalistic data. 3) We show that SDI is effective even in the presence of unknown interventions. 4) We demonstrate that SDI generalizes well to unseen interventions. 5) We show that SDI is effective for partial graph discovery.
We propose a novel neural network based
2 Background
Causal modeling. A Structural Causal Model (SCM) (Pearl, 1995; Peters et al., 2017) over a finite number M of random variables X, is a set of structural assignments
X S1(X N.), Vi (O....,M-1)
where N; is jointly-independenn noise and pa(i, C*) is the set of parents (direct causes) of variable i under hypothesized configuration C of the SCM directed acyclic graph, ie., C' E {0, MjMMM, with ey = 1 if node has node j as a parent (equivalently, X₃ E xXpnt.oy; i.. X, is a direct cause of X.). In our setup, all variables are observed.
Intervention. According to Eaton and Murphy (Eaton & Murphy, 2007b), there are several types of interventions that may be available, including:
2

---

Published in Transactions on Machine Learning Research (08/2023)
No intervention: where only observational data is obtained from the ground truth model.
Hard/perfent intervention: where the value of one or more variables is fixed, and then ancestral sampling is performed on the remaining variables.
Soft helt/imperfeel intervention: where the conditional distribution of the variable on which the intervention is performed is altered.
Unknown intervention: where the learner does not know which variable was directly affected by the intervention.
In this work, we permit interventions on all variables. Furthermore, we use soft interventions because they include hard interventions as a limiting case and are thus more general.
Ideabifiabiliy. In a purely-observational sctting, it is known that causal graphs can be distinguished only up to a Markov equivalence class. In order to identify the true causal graph structure, intervention data is needed (Fberhardt et al., 2006; Eberhardt & Scheines, 2007; Eberhardt et al., 2012; Ebeehardt, 2012). When an infinite amount of single-node interventional data samples are available, the underlying causal graph can be identified (Eberhardt et al., 2006). Empirically, we have observed that even with small number of samples per intervention, our model can make reasonable predictions and its performance improves more data becomes available.
Structure discovery using continuous optimization. Structure discovery is a search problem though the super-oxponentially sized space of all possible directed acyclic graphs (DAGs). Previous continuous- optimization structure learning works (Zheng et al., 2018; Yu et al., 2019; Lachapelle et al., 2019) miligate the problem of searching in the super-exponential set of graph structures by considering the degree which hypothesis graph violates "DAG-ness" as additional penalty to be optimized. Despite the success of these methods, their ability for causal discovery is significantly limited because they can only operate observational data.
3 Related Work
The recovery of the underlying structural causal graph from observational and interventional data is fundamental problem (Pearl, 1995; 2009; Spirtes et al., 2000). Different approaches have been studicd: score-based, constraint-based,, asymmetry--ased and continuous optimization methods. Score-based methods search through the space of all possible directed acyelic graphs (DAGs) representing the causal structure based on some form of scoring function for network structures (Heckerman et al., 1995; Chickering, 2002; Tsamardinos et al., 2006; Hauser Bühlmann, 2012; Goudet et al., 2017; Cooper Yoo, 1999; Zhu & Chen, 2019). Out of these approaches, only Hauser Bühlmann (2012): Goudet et al. (2017); Cooper & Yoo (1999) can handle interventional data. Constraint-based methods (Spirtes al., 2000; Sun et al., 2007; Zhang et al., 2012: Monti et al., 2019) infer the DAG by analyzing conditional independences in the data, none of these handles interventional data. Eaton & Murphy (2007c) use dynamic programming techniques to accelerate Markov Chain Monte Carlo (MCMC) sampling in a Bayesian approach to structure learning for discrete variable DAGs, the method utilizes interventional data. Asymmettyy-asse methods (Shimizu et al., 2006; Hoyer et al., 2009; Peters et al., 2011; Daniusis et al., 2012; Budhathoki & Vreeken, 2017; Mitrovic et al., 2018) assume asymmetry between cause and effect in the data and try to use this information estimate the causal structure, none of these methods can handle interventional data. Peters al. (2016); Ghassami et al. (2017); Rojas-Carull, 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, all three methods can handle interventional data. Mooij et al. (2016) propose a modelling framework that leverages existing methods while being more powerful and applicable to a wider range of settings, however, it can only handle observational data. Recently, (Zheng et al., 2018; Yu et al., 2019; Lachapelle et al., 2019) framed the structure search as continuous optimization problem, however, the methods only uses observational data and are non-trivial to extend interventional data. In our paper, we present a method that uses continuous optimization hothods that works both observational and interventional data.
3

---

Published in Transactions on Machine Learning Research (08/2023)
For interventional data, it is often assumed that the models have access to 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 (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. Bengio et al. (2019) propose a meta-learning framework for learning causal models from interventional data. However, the method Bengio et al. (2019) explicitly models every possible set of parents for every child variable and attempts to distinguish the best amongst the combinatorially many such parent sets. It cannot scale beyond trivial graphs and only 2 variable experiments are presented in the paper. Several subsequent studies have built upon our proposed method SDI. Some of these studies have modified the gradient estimate (Brouillard et al., 2020; Lippe et al., 2021), while others have utilized SDI in the active causal learning setting to determine where to intervene (Scherrer et al., 2021).
Learning based methods have been proposed (Guyon, 2013; 2014; Lopez-Paz et al., 2015) which only handles observational data. There also exist recent. approaches using the generalization ability of neural networks to learn causal signals from purely observational data (Kalainathan et al., 2018; Goudet et al., 2018). Neural network methods equipped with learned masks, such as (Ivanov et al., 2018; Li et al., 2019; Yoon et al., 2018; Douglas et al., 2017), exist in the literature, but only a few (Kalainathan et 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 a discrete-variable setting is made difficult by its use of a Generative Adversarial Network (GAN) (Goodfellow et al., 2014) framework.
4 Structure Discovery from Interventions (SDI)
The proposed model, SDI, is a neural--network-basse approach for causal discovery that integrates both observational and interventional data. The model models the causal mechanisms (conditional probability distributions) and the causal graph structure using two distinct sets of parameters. We refer to the parameters that capture the conditional probability between variables and their causal parents as functional parumeters, denoted by 0. The heh set of parameters that describe the causal graph structure are referred to as structural parameters, represented by 7. The structural parameters 7 correspond to the learned adjacency matrix that encodes the graph structure of the SCM. Details given below.
Parametrization. Given graph of M variables, the structural parameter Y is a matrix RM such that ((1)) is our belief in random variable Xj being direct cause of X,, where axx = 1/(1 + exp(-x)) is the sigmoid function. The matrix a(y) is thus a softened adjacency matria.
The set of all functional parameters 0 comprises the parameters 6; that model the conditional probability distribution of X; given its parent set X Xpa(s.C), with ~ Ber(a(7)) a hypothesized configuration of the SCM's DAG.
Hypothesis. According to the Independent Causal Mechanisms (ICM) principle (Schölkopf al., 2012b), the causal generative process of a system's 's variables comprises autonomous modules that operate independently of one another. In probabilistic terms, this means that each variable's conditional distribution, given its causes (i.e., its mechanism), does not affect or influence the other mechanisms. Therefore, by having the SCM and knowledge of performed interventions, we can precisely predict unseen interventions. Based on this assumption, we hypothesize that the graph structure that better predicts unseen interventions is more likely to reflect the correct causal structure. This assumption has been verified experimentally for 2 variable cases in Bengio et al. (2019).
Following the aforementioned hypothesis, we adopt two-phase training approach for our model, as illustrated in Figure 1. Since the structural and functional parameters are interdependent and influence each other, we train them in alternating phases, akin to a block coordinate descent optimization.
In the first phase, we train the functional paramcters using observational data to infer the relationships between variables. In the second phase, we sample a few graphs from the model's current belief of the graph structure and evaluate their performance in predicting unseen intervention outcomes. We this evaluation
4

---

Published in Transactions on Machine Learning Research (08/2023)
Updated functional parameters f
Phuse1 Distribution Fifting
Phase Graph Learning
Updated graph distribution
nov So
À
YAC
YBA
TC
10V S0.
8
B
Yc.8
N01 fo
YBC
Figure 1: Our proposed method SDI. Phase 1 fits the MLP (functional) parameters observational data. Phase 2 samples small set of graphs under the model's current belief about the edge structure, and then scores these graphs against interventional data and assigns rewards according to graphs' ability to predict interventions. These rewards are then used to update the beliefs about the edge structure. The convergence of the method can be determined when the believed edge probabilitics have reached saturation, approaching either or 1. In our practical implementation, we train our model for 50, 000 steps and report the results.
as a reward signal to update our structure parameters We will now elaborate on the aforementioned process in detail.
Model. Shown in Figure 2, model consists of M MLPs, where M is the number of variables in the graph. Let 0, (WO;, BO, W1,, B1;) define stack of M one-hidden-layer MLPs, one for each random variable X,. A more appropriate model, such as CNN, can be chosen using domain-specific knowledge; the primary advantage using MLPs is that the hypothesized DAG configurations Giy can readily used to mask the inputs of MTP as shown Figure
To force the structural equation fi corresponding to X; to rely exclusively its direct ancestor set pa(i, C) under hypothesis adjacency matrix C' (See Eqn. 1), the one-hot input vector Xj for variable X,'s MLP is masked by the Boolean element Cij. An example of the multi-MLP architecture with M-3 categorical variables of N-2 categorics is shown in Figure 2. For more details, refer to Appendix A.4.
4.1 Phase 1: Distribution Fitting
During Phase 1, the functional parameters 0 are trained to learn causal mechanisms (conditional probability distributions) by fitting them to obscrvational data. To be specific, they maximize the likelihood of randomly drawn observational data under graphs randomly drawn from our current beliefs about the edge structure. We draw graph configurations Cg Ber(o(7))) and batches of observational data from the SCM, then maximize the log-likelihood of the batch under that configuration using stochastie gradient descent. (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 an ensemble of neural networks that can model the observational data. To be specific, parameters 0 is trained using maximum likelihood estimation on observation data X, such that A* = a())in,,C()), where
T((0) log P(X
2

---

Published in Transactions on Machine Learning Research (08/2023)
0.088
0.090
0
0
(7)
0.894
0
0.045
Ber
0
0
Leaky ReLU
Softmax
0.973
0.116
0
0
0
0
0
0
0.19
Á
0.81
1-hot sample 1
01
1-hot sample B = [1,
00
0.96
B
0.04
1-hot sample C = [0,1]
0.03
0.97
Masking input values with edge presence configuration
MLPs
Figure 2: MLP Model Architecture for M 3, N (fork3) SCM. The model computes the conditional probabilities of A, B, C' given their parents using stack of three independent MLPs. The MLP input layer uses an adjacency matrix sampled from Ber(a(n)) as an input mask to force the model to make use only of parent nodes to predict their child node.
4.2 Phase 2:
Graph Learning
During Phase 2, several graph configurations are sampled from the current learned edge beliefs parametrizod by 7; and scored on data samples drawn from the intervened SCM.
To be more specific, we first sample p graph configurations C from the current and learned edge beliefs (structural parameters 7). We then obtain i data samples X from intervention and evaluate the log- likelihood of the intervened data within the sampled graph configurations. This log-likelihood is denoted as log P(XIC; 0). However, we make one modification: we mask the contribution of the intervened (or predicted-interrenne)) random variable X, to the total log-likelihood of the sample.
Since X, was intervened upon (using a Pearl do-operation, soft or hard), the values obtained for that variable should be treatod fixed rather than contributors to the total lokelikel of the sample, and correction gradient should not propagate through it (because the variable's 's CPT MLP did not actually determine the outcome). It is assumed that the intervention is known at this stage, and we will explain in Section 4.2.1 how predict the intervention when it is unknown.
4.2.1 Credit Assignment Structural Parameters
The scores of the interventional data over various graph configuratioss 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 gradient estimator to propagate gradient through the y structural parameters. Several alternatives exist, but we adopt for this purpose the REINFORCF-like gradient estimator Pū with respect to Mh proposed by Bengio al. (2019):

---

Published in Transactions on Machine Learning Research (08/2023)
Fii Ex(o(1)) ( (d.(() Vi,j M (xP(
(0, M-13
(3)
where the (4) superscript indicates the values obtained for the k-th draw of C under the current edge beliefs parametrized by 7. The ((k) (X) is the pscudo log-likelihood of variable X; in the data sample X under the k'th configuration, C(k), drawn from our edge beliefs. Using the estimated gradient, we then update with SGD, and return to Phase 1 of the continuous optimization process.
Acyclic Constraint. We include a regularization lerm JDAG(7) that penalizes length-2 cycles in the learned adjacency matrix a(7), with a tunable strength ÅDAG. The regularization term is JDAG(?) = Eny; (osh(a(1%))
Vi,j (O.....M-1) and is derived from Zheng et al. (2018). The details of the derivation are in the Appendix. We explore several different values of ADAG and their effects in our experimental setup. Suppression of longer-length cycles was not found to be worthwhile for the increased computational expense.
Predicting Intervention. Tf the target of the intervention is known, then no prediction is needed. However, in the case of an unknown intervention, employ a simple heuristic to predict it. During the initial stage of small set of holdout interventional data samples is provided to the model. We then calculate the average log-iikli for each individual variable X, across these samples. The variable X; exhibiting the most significant decline in log-likelihood is assumod to be the target of the intervention.
Phase 2 in iteration
The rationale behind this approach that our model has effectively learned to represent the underlying causal graph, it should be capable of predicting the values of all variables Xj, except for the one that has undergone intervention. Initially, when our model has not yet acquired reliable representation of the underlying causal graph, this prediction might be inaccurate. However, as training progresses and our model improves its predictive capabilities, the accuracy in predicting the intervention target becomes significantly enhanced. In section 6.4, we present the results of our causal discovery experiments based on either predicting the intervention for unknown interventions or having knowledge of the intervention target. We observe that the model's performance predicting the intervention closely corresponds to having access to the ground truth.
5 Synthetic Data
This section discusses the generation process of synthetic data.
Conditional Probability Distributions. The conditional probability distributions (CPD) of the sythetic data are modeled by randomly initialized neural networks. All neural networks are 2 layered feed forward ncural networks (MLPs) with Leaky ReLU activations between layers. The paramcters of the neural network are initialized orthogonally within the range of 1-2.5,255). This range was selected such that they output a non-trivial distribution. The biases are initialized uniformly between (-1.1, These values are selected to ensure that the CPDs are non-trivial and interesting, meaning they are neither almost deterministic nor uniformly distributed.
Graph Structures. In order to conduct a systematic analysis of our model's performance, we evaluate its performance different graph structures. Our selection of synthetic graphs explores various extremes in the space of DAGs, stress-testng SDI. The chain graphs are the sparsest connected graphs possible, and are relatively casy to learn. The bidiag graphs are extensions of chain where there are 2-hops as well as single hops between nodes, doubling the number of edges and creating a meshed chain of lorks and colliders. graphs, but with each node connected directly to its grandparent in
The jungle graphs are binary-tres the tree as well. Half the nodes a jungle graph are leaves, and the out-dogree is up 6. The collider graphs deliberately collide independent M ancestors into the last node; They stress maximum in-degree. Lastly, the full graphs are the maximally dense DAGs. All nodes are direct parents of all nodes below them
7

---

Published in Transactions on Machine Learning Research (08/2023)
in the topological order. The maximum in- and out-degree are both M 1. Please refer to Figure 3 for illustrative examples of 3-variable graphs, and consult. Figure 6 for the complete collection of graphs.
B
B
B
B
chain3
fork3
collider3
confoundert
Figure 3: Example graphs for 3-variable connected DAG.
Interventions. In all experiments, observational and interventional data are used. To generate interventional data, random and soft interventions are performed. The process begins by randomly selecting variable, denoted as X,, to be intervened on. Subsequently, a soft intervention is applied to the intervened variable X;, replacing the conditional probability distribution p(X, (p(x)) with different CPD denoted p' (X.)pa(X.)). To be specifie, the MLP (Multilayer Perceptron) parameters of the conaltional distribution are reinitialized randomly within the range of (-2.5, 2.5), which aligns with the range of values used for the initial random initialization of the conditionals.
6 Experimental Setup and Results
We evaluate the performance of SDI across a range experiments with increasing difficulties. We first evaluate SDI on a 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: Recovering only part of the graph (when the rest is known), and exploiting knowledge of the intervention target.
The summary of our findings is: 1) We show strong results for graph recovery for all synthetic graphs in comparisons with other basclincs, measured by Hamming distance. 2) The proposed method achioves high accuracy on partial graph recovery for large, real-world graphs. 3) The proposed method's intervention targel prediction heuristic closes the gap between the known- and unknown-targe intervention scenarios. 4) The proposed method generalizes well unseen interventions. 5) The proposed method's time-to-solution scaling appears to be driven by the number of edges in the groundtruth graph moreso than the mumber of variables.
Hyperparameters. Unless specified otherwise, we maintained identical hyperparameters for all experiments. In the subsequent paragraph, we examine the impact of DAG and sparsity penalties. The experiments involving SDI were executed for total of 50,000 steps, as illustrated in Figure 10, and most experiments reached convergence within that timeframe. For additional information regarding the hyperparameter configuration, please refer to Appendix $A.5.
Baseline Comparisons We compare SDI against a range of state-of-tho-art methods, including both classic and neural network-based approaches. Specifically, we consider DAG-no-tears (Zheng et al., 2018), DAG-GNN (Yu et al., 2019), ICP (Peters et al., 2016), non-linear ICP (leinze-Demll et al., 2018b), and (Eaton & Murphy, 2007b). Our comparison encompasses both synthetic and naturalistic data. DAG-no-tears and DAG-GNN are neural network-based causal discovery methods and can only handle observational data. On the other hand, ICP, non-linear ICP, and Eaton & Murphy (2007b) are designed for interventional data. Notably, Eaton Murphy (2007b) addresses uncertain interventions, while ICP and non- non-linear ICP handle unknown interventions. However, none of these mothods attempt to predict the intervention. All methods are provided with both observational and interventional data, which is identical the data given SDI, except for the methods that solely handle observational data, in which case only observational data is provided.
8

---

Published in Transactions on Machine Learning Research (08/2023)
6.1 Results Synthetic Data
We first evaluate the model's performance on synthetic data generated from multiple SCMs (Structural Causal Models) with specific and representative graph structures. These SCMs are randomly initialized using the procedure described Section 5. Since the number of possible DAGs grows super-exponentially with the number of variables, for M=4 up 13 selection of representative and edge-case DAGs are chosen. chainM and fullM (M=3-13) the minimally- and maximally-conneeer M-variable DAGs, while treeM and jungleM are tree-like intermediate graphs. colliderM is the (M-1) + 1 collider graph. The details of the setup is in Appendix A.6.
1.2
chain3
col1ide3
7.4
chain5
cbaink
1.0
Gomma Choss Chos- Cals--ate-gp (avg lato)
1.0
collider5
collider4
1.0
chain6
collider6
0.8
chain7
chain8
Area Unddrr Cure
collider8
cal callder?
0.8
Aroa Unaier Curaa
chuing
collider9
chwin10
collidac10
0.0
chaini1
0.6
3.6
collider11
0.6
Gamma Crose
chain12
collider12
chaini3
collider13
0.2
0.2
3.2
0.2
0.0
0.0
3.0
0.0
10K
201C
30KC
40K
Stepo
Steps (s)
1.2-
1.2
122
gungle3
ful13
gong w4
Jungleb
Caama Crea- (avg (ata)
ful16
fu118
fu11
gong
ful17
0.8
Jungle7
0.5
Aro Usadrr Uurre
0.8
fu118
0.8
Gamma Closs Entroge
gong
ful19
0.0
Junglu0
0.6
0.
full11
full18
gungles 110
ful112
junglui1
full13
Q.4
gung
junglad3
0.9
0.2
0.9
0.2
0K
10K
20K
30K
40K
50k
20K 30K
10K
50K
Starp (1))
Steps (P)
Figure 4: Cross entropy (CE) and Area-Under Curve (AUC/AUROC) for edge probabilities of learned graph against ground-truth for synthetic SCMs. Error bars represent #1a over PRNG seeds 1-5. Left to right, up to down: MhainM.junglehl ful1MM,M = 3...8 (9.... 13 in Appendix A.6.1). Graphs (3-13 variables) all learn perfectly with AUROC reaching 1.0. However, denser graphs (fulIM) take longer to converge.
Results. The model can recover most synthetic DAGs with high accuracy, as measured by Structural Hamming Distance (SHD) between learned and ground-truth DAGs. Table shows the hamming distance between the groundtruth and and the learned graphs for all methods, we threshold our edge beliefs at a()) = 0.5 to derive a graph. As shown the table, our proposed method SDI outperforms all other methods, and learns all graphs perfectly for to 13 variables (excepting full).
In Figure 10, present visualizations of the cross-entropy loss and AUROCs (Area Under the Receiver Operating Characteristic Curve) obtained during the training process of SDI. The contimuous decrease in the cross-entropy loss indicates SDI's convergence towards the correct causal model. Notably, for graphs with up to 10 variables, the AUROCs consistently reach a value of 1.0, signifying perfect classification into edge and non-edge categories.
Note that Eaton & Murphy (2007b) runs out 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
9

---

Published in Transactions on Machine Learning Research (08/2023)
Method
Asia
Sachs
collider
chain
jungle
collider
full
8
11
13
13
13
13
Zheng et al. (2018)
14
22
18
39
22
24
71
Yu et al. (2019)
10
19
7
14
16
12
77
Heinze-Demt et al. (2018b)
8
17
7
12
12
28
Peters et al. (2016)
5
17
16
Eaton & Murphy (2007a)
0
OOM
OOM
OOM
OOM
OOM
Proposed Method (sdi)
0
6
7
Table 1: Baseline comparisons: Structural Hamming Distance (SHD) (lower is better) for learned and ground-truth edges on various graphs from both synthctic and real datasets, compared to (Peters al., 2016), (Heinze-Deml et al., 2018b), (Eaton & Murphy, 2007b), (Yu et al., 2019) and (Zheng et al., 2018). The proposed method (SDI) is run random seeds 1 - and pick the worst performing model out of the random seeds in the table. OOM: out of memory. Our proposed method correctly recovers the true causal graph, with the exception of Sachs and full 13, and it significantly outperforms all other bascline methods.
rocovering the DAG internally requires solving a d 2M-varialle problem. Their method's extremely poor time- and space-scaling of (dd24) makes it unusable beyond > 20.
6.2 Results on Real-World Datasets: BnLearn
The Bayesian Network Repository (ww.. www.bnlearn.co com/bbreeositorr)) is collection commonly-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, 5, 8 and 11-variables respectively, maximum in-degree 3) in the BuLearn dalaset repository.
Results. As shown in Table 1, SDI perfectly recovers the DAG Asia, while making a small number of thus significantly outperforms all other baselines models. Figures
errors (SHD=6) for Sachs (ll-variables). & visualize what the model has learned several stages of learning. Results for Cancer and Asia can be found in the appendices, Figure 15 and 16.
6.3 Generalization Previously Unseen Interventions
It is often argued that machine learning ap- proaches based purely on capturing joint dis- tributions do not necessarily yield models that generalize to unseen experiments, since they do not explicitly model changes through inter- ventions. By way of contrast, causal models use the concept of interventions to explicitly model changing environments and thus hold the promise of robustness even under distributional shifts (Pearl, 2009; Schölkopf et al., 2012a; Pe-
Table 2: Evaluating the consequences of previously unseen intervention: (test log-likelihood under interven- tion)
fork3
chain3
confounder3
collider3
Baseline sdi
-0.5036
-0.4562
-0.3628
-0.0822
-0.4502
-0.3801
-0.2819
-0.4677
ters 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 Gjj = 1, i + j. An intervention is performed on the SCM, fresh 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- liceliicsoo of the data under both models are computed and contrasted. The intervention variable's contribution to the log-likellnn licelhoddoo masked. For all 3-variable graphs (chain3, fork3, collider3, conf ounder3), the causal model aftributes higher log- likelhhood to the intervention distribution's
10

---

Published in Transactions on Machine Learning Research (08/2023)
samples than the non-causal variant, thereby demonstrating causal models' superior generalization ability in transfer tasks. Table 2 collects these results.
6.4 Variant: Predicting interventions
In Phase (described $4.2), the contri- bution of the intervened (or predicted- intervened) random variable X; is masked from the total log-likelihood of the sample. To predict the interven- tion target variable, we employ simple heuristic. Experimental results demon- strate that this heuristic performs well in practice, yielding accurate predictions more frequently than chance alone (see Table 3). In this section, we conduct ablation studies to thoroughly examine the significance of intervention prediction. We compare several scenarios to evaluate their impact the overall results.
Table 3: Intervention Prediction Accuracy: (identify which
variable the intervention took place)
variables
variables
5 variables
variables
95 %
93 %
85 %
71 %
In the first scenario, referred to 'guessing intervention," randomly guess the intervention variable and subsequently mask out its contribution. The second scenario, termed 'no information intervention, involves not guessing the intervention variable at all, which means all variables, including the intervened-on variable, contribute to the log-likelihood used in Phase 2. The third sccnario, 'predicting unknown intervention, entails asking the model to predict the intervened variable and subsequently masking out its contribution. Lastly, in the 'known intervention' scenario, we provide the model with the ground truth information about the intervened variable, enabling the masking of its contribution.
Notably, both the first and second scenarios, where either the model randomly guesses the intervent ion doesn't use any intervention information at all, result in significant decline in model performance. This decline holds true even for graphs with only three variables, as demonstrated in Figure (Left). Conversely, when training SDI with intervention prediction, the model's performance closely aligns with training that incorporates the ground-truth intervention. This alignment persists even for larger graphs comprising seven variables, depicted in Figure (Right)
1.2
1.3
chain?
Cro--atttre (arg (er))
Comma Chos Eatropy long Mahl
1.0
chain7 goond truth
full7
0.4
prodection
0.8
ful17 ground truth
jungle?
proderkes
jungle7 ground truch
18C
4K
5%
12B
16K
2013
O1C
10K
20X
30K
4013
500
Stope (40
Stepe (0)
Figure 5: Ablation Study of Intervention Prediction Cross-entropy loss over time on multiple graphs and intervention prediction modes. Left:: All 3-variable graphs. Solid/dasher lines: Ground-truth & Prediction strategies. Dotted lines: Random- No-Prediction strategies. Training with prediction closely tracks ground-truth. Right: Comparison for 7-variable graphs, ground-truth against prediction strategy. Training with predicted interventions still closely tracks using ground-trute truth interventional information at larger scales.
6.5 Variant: Partial Graph Recovery
Instead of learning cansal structures de novo, we may have partial information about the black-box SCM and may only need to fill in missing information. An example is protein structure discovery in biology (Glymour
11

---

Published in Transactions on Machine Learning Research (08/2023)
et al., 2019), where some causal relationships have been definitely established and others remain open hypothe- ses. This is an easier task compared to full graph recovery, since the model only has to search for missing edges.
Table 4: Partial Graph Recovery on Alarm (Beinlich et al., 1989) and Barley (Kristensen & Rasmussen, 2002). The model is asked to predict 50 edges in Barley and 40 edges in Alarm. The accuracy is measured in Structural Hamming Distance (SHD). SDI achieved over 90% accuracy on both graphs
We evaluate SDI on Barley (Kristensen & Ras- mussen, 2002) (M = 48) and Alarm (Bein- lich 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, as shown in Table 4.
Graph
Alarm
Barley
Among the methods evaluated in Table 1, the top three performers were ICP, non-linear ICP, and the method proposed by Eaton & Murphy (2007a). However, it should be noted that these methods are not scalable to larger graphs, specif- ically in the case of Barley and Alarm datasets. Consequently, a direct comparison with these methods was not feasible.
Number of variables
37
48
Total Edges
46
84
Edges to recover
40
50
Recovered Edges
37
45
Errors (in SHD)
3
6.6 Ablation and analysis
As shown in Figure 11, larger graphs (such as M > 6) and denser graphs (such as ful18) are progressively more difficult 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.
Importance of regularization. Valid configurations C' for a causal model are expected to be a) sparse and b) acyclic. To promote such solutions, we introduce DAG and sparsity regularization with tunable hyperparameters. For all experiments, we sct 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 Appendix $A.13.
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 a())) in our experiments during functional parameter training of the conditional distributions of the SCM. Please refer to Appendix $A.14 for more detailed analysis.
7 Conclusion
In this work, we introduced an experimentally successful method (SDI) 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 the start-of-tee thof-hhe-rrtt causal discovery methods on real world datasets, and that it scales even better problems where only part of the graph is known.
Acknowledgements
This research was conducted while the first author was a graduate student at Mila. The authors would like to acknowledge the support of the following agencies for research funding and computing support: NSERC, Compute Canada, the Canada Research Chairs, CIFAR, and Samsung. We would like to thank Lars Buesing, Nasim Rahaman and Rémi Le Priol for useful feedback and discussions.
12

---

Published in Transactions on Machine Learning Research (08/2023)
References
Bruce Abramson, John Brown, Ward Edwards, Allan Murphy, and Robert L 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 F 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 meta-transfed objective for learning to disentangle causal mechanisms. arXiv preprinl 1V:1:900.1000 2019.
Philippe Brouillard, Sébastien Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien, and Alexandre Drouin. Differentiable causal discovery from interventional data. Advances in Neural Information Processing Systems, 33:21865-2188 2020.
Kailash Budhathoki and Jilles Vreeken. Causal inference by stochastic complexity. arXiv: 760.00676... 2017.
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-554, 2002.
Gregory F. Cooper and Changwon Yoo. Causal Discovery from Mixture of Experimental and Observational Data. In Proceedings of the Fifteenth Conference Uncertainty in Artificial Intelligence, UAI99,, pp. 116-125, San Francisco, CA, USA, 1999.
Povilas Daniusis, Dominik Janzing, Joris Mooij, Jakob Zscheischler, Bastian Steudel, Kun Zhang, and Bernhard Schölkopf. Inferring deterministic causal relations. arXio preprint orXiv:1203.3475 2012.
Laura Douglas, Ilyann 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 orXiv:1711.0065: 2017.
Danicl 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-114, 2007b.
Daniel Eaton and Kevin Murphy. Bayesian structure learning using dynamic programming and MCMC. In Uncertainty in Artificial Intelligence, pp. 101-108, 2007c.
Frederick Eberhardt. Almost optimal intervention sets for causal discovery. arXiv preprint aixi: 1rXii:1206.322 3206.2200, 2012.
Frederick Eberhardt and Richard Scheines. Interventions and causal inference. Philosophy of Science, 74(5): 981 981-995, 2007.
Frederick Eberhardt, Clark Glymour, and Richard Scheines. N-1 experiments suffice to determine the causal relations among variables. Innovations in machine learning, 194:97-112 2006.
Frederick Eberhardt, Clark Glymour, and Richard Scheines. On the number of experiments sufficient and in the worst case necessary to identify all causal relations among n variables. arXiv preprint arXiv:1207.1385 2012.
AmirEmad Ghassami, Saber Salchkaleybar, Negar Kiyavash, and Kun Zhang. Learning causal structures using regression invariance. In Advances in Neural Information Processing Systems, pp. 3011-3021, 2017.
Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based on graphical models. Frontiers in genelics, 10:524, 2019.
13

---

Published in Transactions on Machine Learning Research (08/2023)
Ian Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde- Warde-Farley, Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural informalion 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.08083 2017.
Olivier Goudet, Diviyan Kalainathan, Philippe Caillou, Isabelle Guyon, David Lopez-Paz, 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-offect pairs kaggle competition, 2013. URL https://www. kaggle. pairs, pp. 165, 2013.
Isabelle Guyon. Chalcarn fast causation cocfficient challenge, 2014. URL https://www.. codalab. org/compptitions/1888. pp. 165, 2014.
Alain Hauser and Peter Bühlmann. Characterization and greedy learning interventional markov equivalence classes of directed acyelic graphs. Journal of Machine Learning Research, 13(Aug))2409 2464, 2012.
David Heckerman, Dan Geiger, and David M Chickering. Learning bayesian networks: The combination of knowledge and statistical data. Machine learning, 20(3):197-243, 1995.
Christina Heinze-Demll Marloes Maathuis, and Nicolai Meinshausen. Causal structure learning. Annual Review of Statistics and Its Application, 5:371-391, 2018a.
Christina Geanze-Demll 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-base effort. Nature methods, 13( (3(4)3310-315 2016.
Patrik O Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. In Advances in neural information processing systems, pp. 689-696, 2009.
Oleg Ivanov, Michael Figurnov, and Dmitry Vetrov. Variational autoencoder with arbitrary conditioning. arXiv preprint Xrxic:1806.8 02382, 2018
Diviyan Kalainathan, Olivier Goudet, Isabellc Guyon, David Lopez-Paz, and Michèle Sebag. Sam: Structural agnostic model, causal discovery and penalized adversarial learning. arXiv preprint arXiv:1803.00 04929, 2018.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 69800, 2014.
Kevin B Korb and Ann E Nicholson. Bayesion artificial intelligence. CRC press, 2010.
Kristian Kristensen and llse 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, (3):197-21) 217, 2002.
Sébastien Lachapelle, Philippe Brouillard, Tristan Deleu, and Simon Lacoste-Julien. Gradient-based neural dag learning. arXiv preprint arXiv:1906.0220 2019.
Steffen I. Lauritzen and David J Spiegelhalter. Local computations with probabilities on graphical structures and their application expert systems. Journal of the Royal Statistical Society: Series B (Methodological), 50(2):157-194, 1988.
14

---

Published in Transactions on Machine Learning Research (08/2023)
Yang Li, Shoaib Akbar, and Junier B Oliva. Flow models for arbitrary conditional likelihoods. ar preprint arXiv= NTW==199.003113 2019.
Phillip Lippe, Taco Cohen, and Eistratios Gavves. Efficient neural causal discovery without acyclicity constraints. arXic preprint arXa::207.10488,, 2021.
David Lopez-Paz, Krikamol Muandet, Bernhard Schölkopf, and lliya Tolstikhin. Towards a learning theory
of cause-effect inference. In International Conference on Machine Learning, pp. 1452-1461, 2015.
Jovana Mitrovic, Dino Sejdinovic, and Yee Whye Teh. Causal inference via kernel deviance measures. In Advances in Neural Information Processing Systems, pp. 6986-6994, 2018.
Ricardo Pio Monti, Kun Zhang, and Aapo Hyvarinen. Causal discovery with general non-linear relationships using non-lincar ica. arXiv preprint NNN4::90440000 2019.
Joris M Mooij, Sara Magliacane, and Tom Claassen. Joint causal inference from multiple contexts. or preprint ar arXte:1611.1055. 2016.
Judea Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669 688, 1995.
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.
J. Peters, J. M. Mooij, D. Janzing, and B. Schölkopf. Identifiabilit of causal graphs using functional models. In Proceedings of the 27th Annual Conference on Uncertainty in Artificial Intelligence (UAT), pp. 589-598, 2011.
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 Melhodology), 78(5):947-1012 2016.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. MIT press, 2017.
Mateo Mojas-Carulle Bernhard Schölkopf, Richard Turner, and Jonas Peters. Invariant models for causal transfer learning. The Journal of Machine Learning Research, 19(1):1309-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. Po'or, Douglas A Lauffenburger, and Garry P Nolan. Causal protcin-signaling networks derived from multiparameter single-cell data. Science, 308(522)):523 529, 2005.
Nino Scherrer, Olexa Bilaniuk, Yashas Annadani, Anirudh Goyal, Patrick Schwab, Bernhard Schölkopf, Michael Mozer, Yoshua Bengio, Stefan Bauer, and Nan Rosemary Ke. Learning neural causal models with active interventions. arXiv preprint arXix:2009.022 020.2229, 2021.
Bernhard Schölkopf, Dominik Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris Mooij. On causal and anticausal lcarning. In J. Langford and J. Pincau (eds.), Proceedings of the 29th International Conference on Machine Learning (ICML), pp. 1255 1262, New York, NY, USA, 2012a. Omnipress.
Bernhard Schölkopf, Dominik Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris Mooij. On causal and anticausal learning, arXiv preprinl vrXii:1206.66 6471, 2012b.
Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, and Antti Kerminen. A lincar non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(Oct):2003 2030, 2006.
Peter Spirtes, Clark N Glymour, Richard Scheines, David Heckerman, Christopher Meek, Gregory Cooper, and Thomas Richardson. Cousation, prediction, and search. MIT press, 2000.
15

---

Published in Transactions on Machine Learning Research (08/2023)
Xiaohai Sun, Dominik Janzing, Bernhard Schölkopf, and Kenji Fukumizu. A kernel-based causal learning algorithm. In Proceedings of the 24th international conference on Machine learning, pp- 855 862. ACM, 2007.
Toannis Tsamardinos, Laura E. Brown, and Constantin F 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:1806. 02920,, 2018.
Yue Yu, Jie Chen, Tian Gao, and Mo Yu. Dag-gnn: Dag structure learning with graph neural networks. arXiv preprinl 1 1904. 10098, 2019.
Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. arXiv preprinl arxiv 1xxi::202..277 1202.3775, 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. 9472 9483, 2018.
Shengyu Zhu and Zhitang Chen. Causal discovery with reinforcement learning. orXie preprint arXiv::906 Xii:19966004477 04477, 2019.
16


Reviews:
[{"review_id": "gk5LAjIImC", "reviewer": "Reviewer_ZoQW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThis algorithm appears to work well empirically, and the intuition behind the algorithm is straightforward.  The method's individual steps all make sense, and they appear to combine well together to make an effective algorithm for structured causal models.\n\nWeaknesses:\nFirst, there are weaknesses in the lack of theory supporting the proposed algorithm, and the computational complexity is still quite high, even if it is better than some competing approaches.  I do not view these challenges as easily addressable or necessary to solve in the context of this work, and instead focus below on addressable concerns.\n\nMajor Addressable Weaknesses:\nThe data generation procedure is not clear enough in the results, as many details are lacking.  In particular, it is unclear how the interventions work.  The detail in the appendix minimally states, “We perform our intervention by first randomly selecting which variable to intervene on, then soft-intervening on it.” Without this information, it is not clear how to evaluate the many claims in the experiments.  Additionally, how many interventions are available? It sounds like the authors are allowing new interventions every time during phase II of their training (step 11 of Algorithm 1), which is an unrealistic scenario.  How does this compare to the information provided to the competing models? Without significantly more information on the data generation and details on how the experiments and comparisons were run, I could not reproduce or completely validate the results.\n\nMinor Addressable Weaknesses:\nThe results section appears to be written trying to save space by putting many necessary results in the appendix.  I would suggest putting all key results in the main paper, rather than repeatedly referencing the appendix.  This would improve flow.\n\nM & N are presented in a confusing manner: “Given a graph of M variables” & “N is the number of variables in the graph”. Please correct.\n\n“If the believed edge probabilities have all saturated near 0 or 1, the method has converged.” -> tricky convergence condition.  Please elaborate.  It sounds like from the experiments the algorithm is just run as long as possible.\n\nIn 4.2, you should explicitly state that the sampled graphs are learned.\n\nThe scale and importance of Table 2 is unclear.  How much better is this method?\n\nSeveral references are the wrong format (e.g., end of paragraph 2).\n\nICM is not defined.\n\nFigure 3 is messy and difficult to read since the line formats are the same for both metrics.  I would suggest splitting into two figures.\n\nSection 5.5 is unclear, as it is not well enough described what the known and unknown interventional generation entails.\n\nSection 5.6 lacks comparisons, making it difficult to evaluate the quality of the method.\n\nUnder “predicting intervention,” there is this phrase: “A small number of interventional data samples are drawn from the SCM and more graphs are sampled from our current edge beliefs.”  I don’t know what the authors meant by that. \n\nI cannot find what interventions were used in Section 5.1 in the main paper or appendix.  As this is necessary for evaluation, it needs to be included in the main manuscript.\n\nSome references are appearing as ?? (e.g., right below A.1)\n\nFigure 5’s images are pixelized.\n\nSmall grammar things (e.g. “The” in A.10 should not be capitalized)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript uses a sampling procedures and neural networks to more efficiently learn a structured causal model.  The primary contributions are methodological, and the approach appears to empirically outperform competing approaches.  The main focus is on using interventional data, so the algorithm is denoted as Structure Discovery from Interventions (SDI).  SDI follows a reasonable multi-step loop to effectively learn structures.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical:\nThe experimental section needs significantly more detail on how the data generation procedure worked, how the interventions were generated both for the proposed model and for competing models, and greater details on how competing models were used.  As it is now, I could not reproduce the results because I do not have enough details.  Without this, I cannot mark the claims and evidence below as yes.\n\nAbove, in minor weaknesses, I also highlighted several challenges in the interpretation of the provided results, namely Table 2 and Table 4.  Please provide context on the importance/significance of these results.\n\nMake clarifications/fix typos as noted in minor weaknesses.\n\nNot critical but would improve the work:\nMoving many of the useful results from the appendix to the main draft would improve the flow of the manuscript.\n", "broader_impact_concerns": "Not necessary.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "usjVovudYZ", "reviewer": "Reviewer_h2Vy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Diagrams (Figure 1 and Figure 2) explain the estimation procedure visually. \n- Experiments are conducted on different families of structural causal models (SCM). They showing that the estimation procedure can handle a diverse set of situations.\n- The appendix contains sensitivity studies of the estimation accuracy with respect to the estimation procedure's hyperparameters.\n\nWeaknesses: \n- The paper does not explain the choice of competing methods included in the experiments. It maybe missing important competitors in the literature review and experimental results. Hence, the evidence to support the claim \"our method achieves strong benchmark results on various structure learning tasks\" (mentioned in the abstract, among other places) is not strong. \n- There are places in which the quality of writing should be improved (please see Requested Changes). ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a method to estimate structural causal models (both the causal DAG and the functional relationship among variables) from observational and interventional data. The method is an alternating optimization, with two sets of decision variables: the first set parametrizes the causal DAG, and the second set parametrizes the functional relationships. Both phases of the alternating optimization is based on maximum likelihood. Experiments on small structural causal models demonstrate give evidence that that the method can successfully estimate structural causal models. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Primary substantive changes:\n* Explain the reasoning behind choosing the methods in Table 1 as competitors methods. \n  * The paper's Related Work section seemingly lists at least a dozen papers on estimating SCM, but Table 1 compares the proposed method with only 5 such methods. It is possible that the chosen competitor methods are the best-performing out of their lines of work: if so, this should be explained in clear detail. \n\n* Revise the first paragraph of Related Work section to clarify which methods can handle both observational and interventional data\n  * Currently, the first two sentences in this paragraph suggests that the papers mentioned in the paragraph can handle both types of data. However, the last sentence \"Recently, (Zheng et al., 2018; Yu et al., 2019; Lachapelle et al., 2019) framed the structure search as a continuous ...[] ... interventional data.' contradicts this assessment. \n\n* Clarify the assumptions that enable causal graph learning from just one intervention\n  * Right before Section 5.1, the paper says \"In all experiments, at most one (soft) intervention is concurrently performed.\" For general SCMs with more than one parent-child edge, it seems unlikely that just one intervention is sufficient in recovering the underlying causal graph. I am willing to be convinced that this intuition is incorrect, however.\n\nSecondary substantive changes:\n* Explain the omission of the competitor methods in Table 1 from Table 4. \n  * The Related Work section does not mention \"inability to apply to partial graph recovery\" as a limitation of existing works. If this were the case, it would be great to have that explicitly spelled out. \n\n* Compare the runtimes of various methods \n  * Based on Appendix A.11, the proposed method is seemingly highly time consuming, since many observations are needed to accurately estimate the causal graph. What do the runtime of the competitor methods look like? I do not think including runtime information will be detrimental to the proposed method.\n\nClarify writing and figures:\n* Clarify if there has been an existing preprint on the SDI paper: if so, what is the relationship between the current paper and the existing preprint? \n  * The sentence \"Several subsequent studies have built upon our proposed method SDI\" suggests that there is an existing paper on SDI. It is unclear if the current manuscript is a) the same paper or b) an extension. If it were an extension, I am not clear what parts are known versus what parts are new.\n* After Equation (2), define the quantity $L_{C,i}^{(k)}(X)$. This notation is currently used without a definition. \n* In Figure 3, increase the font sizes and remove the visual clutter. There are perhaps too many curves being plotted - although the colors help distinguish the curves, it is still difficulty to tell apart the curves.\n\nChanges relating to references and citations:\n* Fill in the missing reference in Section 5.6. \n* Add references to support the sentence \"An example is protein structure learning in biology ...\". This sentence appears in the Introduction and Section 5.6.\n* Add citation for the bnlearn package / dataset repository\n* Replace the duplicate reference \n", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "877MOZ64OT", "reviewer": "Reviewer_DbbW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n**S1**. The paper is well written. The motivation is clearly stated. The background and related work sections are useful.\n\n**S2**. The strong performance of the proposed method is shown for different datasets.\n\n**S3**. Not only the main structure identification problem but also other problems (the unknown intervention problem and the partial recovery problem) are addressed.\n\n### Weaknesses\n\n**W1**. The training process in Sections 4.1 and 4.2 are not mathematically clear. I could understand the rough idea but am not sure what happens there exactly.\n\n**W2**. The description of the method for \"Predicting Intervention\" in Section 4.2.1 is not clear.\n\n**W3**. The explanation of the baseline methods used in the experiment is not sufficient.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "A method for identifying the structural causal graph is proposed. The method utilizes both observational and interventional data. It iterates between two stages. In one stage, the functional parameters (i.e., the parameters of neural nets that fit the conditional distributions) are trained using observational data. In the other stage, the structural parameters (i.e., the elements of the adjacency matrix) are trained using interventional data. The nice performance of the proposed method is empirically confirmed not only with synthetic SCMs but also with more realistic SCMs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please address **W1**. Although there is a pseudocode in the appendix, I would recommend putting the core mathematical descriptions of the training process in the main text (Sections 4.1 and 4.2), too.\n\n2. Please address **W2**. It would be nice if the authors could elaborate more on why the proposed heuristic is expected to work.\n\n3. Please address **W3**. For example, what kind of information do the baseline methods in Table 1 use? Do they use both observational and interventional data as the proposed method does? (Maybe I missed some descriptions already there in other parts of the paper, though.)\n\nBelow are minor points.\n\n4. Throughout the paper, please re-check the use of latex commands \\citep and \\citet (or something equivalent). Sometimes \\citet is used when \\citep should be.\n\n5. Please also re-check the latex cross reference. \"??\" appears sometimes, especially in the supplementary material.\n\n6. In Page 5, \"... our model consists of $N$ MLPs, where $N$ is the number of variables in the graph\": Do you mean $M$ instead of $N$?\n\n7. Are the estimated causal mechanism (i.e., functional parameters) somehow referred to in the experiments? In my understanding, the performance evaluation is on the structural parameters only (please correct me if I'm wrong, which is likely). I wondered how the estimated causal mechanism could be useful.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new techniques for causal discovery from data that also contains interventions.  The method is evaluated on problems of moderate scale, and shown to outperform both classical and neural network based baselines. Reviewers raised some issues around the choice of baselines, around the specific data generating process being assumed, around the assumptions and nature of the interventions and how these permitted, theoretically, the identification of causal structure, and generally raised some issues with clarity, notation, etc. The author produced clear rebuttals and the revised text was judged, by each reviewer, to adequately address their concerns. I am also satisfied with the reviews, rebuttals, and revisions.
Decision: Accept (poster)