Learning Neural Causal Models with Active Interventions
Authors: Nino Scherrer
Olexa Bilaniuk
Yashas Annadani
Anirudh Goyal
Patrick Schwab
Bernhard Schölkopf
Michael Curtis Mozer
Yoshua Bengio
Stefan Bauer
Nan Rosemary Ke
Venue: ICLR 2022 Submitted (2022)
Keywords: neural causal discovery
causal structure learning
active learning
experimental design

Abstract: Discovering causal structures from data is a challenging inference problem of fundamental importance in all areas of science. The appealing scaling properties of neural networks have recently led to a surge of interest in differentiable neural network-based methods for learning causal structures from data. So far, differentiable causal discovery has focused on static datasets of observational or interventional origin. In this work, we introduce an active intervention-targeting mechanism which enables quick identification of the underlying causal structure of the data-generating process. Our method significantly reduces the required number of interactions compared with random intervention targeting and is applicable for both discrete and continuous optimization formulations of learning the underlying directed acyclic graph (DAG) from data. We examine the proposed method across multiple frameworks in a wide range of settings and demonstrate superior performance on multiple benchmarks from simulated to real-world data. 

Under review as a conference paper at ICLR 2022
LEARNING NEURAL CAUSAL MODELS WITH ACTIVE INTERVENTIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Discovering causal structures from data is a challenging inference problem fun- damental importance in all areas of science. The appealing scaling properties of neural networks have recently led to a surge of interest in differentiable neural network-based methods for learning causal structures from data. So far, differen- tiable causal discovery has focused on static datasets of observational or interven- tional origin. In this work, we introduce an active intervention- targeting mecha- nism which enables quick identification of the underlying causal structure of the data-generating process. Our method significantly reduces the required number of interactions compared with random intervention targeting and is applicable for both discrete and continuous optimization formulations of learning the underly- ing directed acyclic graph (DAG) from data. We examine the proposed method across multiple frameworks in a wide range of settings and demonstrate superior performance multiple benchmarks from simulated to real-worke data.
INTRODUCTION
Learning causal structure from data is challenging but important task that lies at the heart of scientific reasoning and accompanying progress many disciplines (Sachs et al., 2005 Hill al., 2016 Lauritzen & Spiegelhalter, 1988 Korb & Nicholson] 2010). While there exists plethora of methods for the task, computationally and statistically more efficient algorithms are highly desirable [Heinze-Deml et al., (20T8). As result, there has been surge in interest in differentiable structure learning and the combination of deep learning and causal inference (Schölkopf et al., (02T). Such methods define a structural causal model with smoothly differentiable parameters that are adjusted to fit observational data (Zheng et al.) 2018 Yu et al. 2019: Zheng et al. 2020 Bengio et al.,
2019 Lorch et al. 2021: Annadani et al. (021). although some methods can accept interventional
data, thereby significatlyy improving the identification of the underlying data- eetta-genrating process
(Ke et al. 2019 Brouillard et al., 2020 Lippe al.) 2021). However, the improvement critically depends on the experiments and interventions available to the learner.
Despite advances in tighuhhroughput methods for interventional data in specific fields (Dixit al., 2016), the acquisition of interventional samples in general settings tends to be costly, technically impossible even unethical for specific interventions. There is, therefore, a need for efficient usage of the available interventional samples and efficient experimental design to keep the number of interventions a minimum.
A significant amount of prior work exists in causal structure learning that leverages active learn-
ing and experimental design to improve identifiability in a sequential manner. These approaches are either graph theoretical (He & Geng 2008; Eberhard( 2012] Hyttinen et al. 2013] Hauser &
Bühlmann, 2014 Shanmuuam et al. [015 Kocaoglu et al., 2017b al Lindgren et al., [018)] Ghas-
sami et al. 2018 2019 Grrennealld et al. 2019 Squires et al. 2020), Bayesian (Murphy 2001
Tong & Koller| | Masegosa & Moral 20133 Cho et al. 2016 Ness et al. 2017 Agrawal et al,
2019 Zemplenyi & Miller 202 I) or rely on Invariant Causal Prediction (Gamella & Heinze-Dem
2020). These methods are typically computationally very expensive and do not scale well with re- spect to the number of variables or dataset size (Heinze-Dene Deml et al. 2018). A promising alternative is the use of active learning in a continuous optimization framework for causal structure learning from joint data. However, since the applicability of existing scores heuristics for selecting inter-

---

Under review as a conference paper at ICLR 2022
vention targets is limited for existing frameworks (see $A.1 current approaches rely on random and independent interventions and do not leverage the acquired evidence from processed experiments.
We thus propose novel method of active selection of intervention targets that easily be in- corporated into many differentiable causal discovery algorithms. Since most of these algorithms treat the adjacency matrix of the causal graph learned soft-adjacency, it is readily available for parametrized sampling of different hypothesis graphs. Our method looks for an intervention target that gives maximum disagreement between post-interventional sample distributions under these hy- pothesis graphs. We conjecture that interventions on such nodes will contain more information about the causal structure and hence enable more efficient learning. To the best of our knowledge, our pa- per is the first approach to combine both a continuous optimization framework and active causal structure learning from observational and interventional data. We summarize our contributions as follows:
We propose a novel approach for selecting interventions (single and multi-target) which identify the underlying graph efficiently and can be used for any differentiable causal discovery method. We introduce novel, scalable two-phase DAG sampling procedure which efficiently generates hypothesis DAGs based on a soft-adjacency matrix.
We examine the proposed intervention-taretiin method across multiple differentiable causal discovery frameworks in a wide range of settings and demonstrate superior performance against established competitive baselines on multiple benchmarks from simulated to real-world data. We provide empirical insights the distribution of selected intervention targets and its con- nection to the (causal) topological order of the variables in the underlying system.
2 PRELIMINARIES
Structural Causal Model. An SCM (Peters al. 2017) is defined over set of random variables XI...., N.....,,M.. or just X for short and a directed acyclic graph (DAG) G = (V, E) over variable nodes == (1.... M). The random variables are connected by edges in F. via functions Si and jointly independent noise variables U; through X; = (x pa()), U2) where xpo(i) are X,'s parents in G, and directed edges in the graph represent direct causation. The conditionals P(X; define the conditional distribution of X; given its parents.
Interventions on X, change the conditional distribution of P(X, P(X,|X paa()) ) to a dif- ferent distribution, hence affecting the outcome of X,. Interventions can be perfect (hard) im- perfect (soft). Hard interventions entirely remove the dependencies of a variable X, on its parents Xpa(t). hence defining the conditional probability distribution of X, by some P(X.) rather than P(X,|X (x)) more general form of intervention is the soft intervention, where the interven- tion changes the effect of the parents of X, itself by modifying the conditional distribution from P, Xpa(i) to an alternative P. (XX())pa()))
Interventions.
Dependency Structure Discovery from Interventions (DSDI). We evaluate the proposed method under multiple interventional) data (Bareinboim & Pearl 2016), one of them being DSDI (Ke et al.] 2019). The work of DSDI reformulates the problem of causal discovery from discrete data as continuous optimization problem using neural networks. The framework proposes to learn the causal graph adjacency matrix as matrix parameter 7 of neural network, and is trained using a 3-stage it- crative procedure. The first stage involves sampling graphs under the model's 's current belief in the graph structure and then training functional parameters P specifying the conditionals of the sampled graphs using observational data. Note how sampling graph from y can specify element-wise wise mul- tiplications by
causal learning frameworks from fused (observational and
in the first layer of neural networks for the conditionals, remove unallowed edges, with other network parameters P applicable to any sampled graph. The next stage is to eval- uate the sampled graphs under interventional data and score these graphs accordingly. The final step is to update the learned adjacency matrix with the scores from stage 2. This method performs com- petitively compared to many other methods. However, all intervention targets in stage of DSDI random and independent, strategy that scales poorly to larger graphs. A better approach would have been active intervention targeting, elaborated in the next section.
Differentiable Causal Discovery from Interventional Data (DCDI). We also consider the work of DCDI (Brouillard et al.] 2020). which addresses causal discovery from continuous data as a continuous--onnstriined optimization problem using neural networks to model parameters of Gaus-
2

---

Under review as a conference paper at ICLR 2022
9
g
+ De
IN
S
p
P
180
(a) AIT procedure for intervention target Ta:
(h) Discrepancy score D3 landscape
Figure 1: (a) Procedure: Start by sampling a set of hypothetical graphs g given the current graph beliefs y, and apply an intervention targets I the functional parameters P which results in partially altered parameters Pk. Continue by sampling sets of hypothetical interventional experi- ments under Pp for every graph in G and compute the corresponding discrepancy score D3 ratio of
seewwenn-graphs VBGk and siriance-within-- graphs VWG (b) Landscape of the discrepancy score terms of VBG₁ and VWG in logarithmic scale.
sian distributions or normalizing flows (Rezende & Mohamed, 2015) which represent conditional distributions. Unlike DSDI's iterative training of the structural and functional parameters, DCDI optimizes the causal adjacency matrix and functional parameters jointly over the fused data space. But like DSDI, DCDI uses random and independent interventions.
ACTIVE INTERVENTION TARGETING
We present a score-based intervention design strategy, called Active Intervention Targeting (AIT), which is applicable many discrete and continuous optimization formulations of causal structure learning algorithms. Furthermore, we show how our proposed method can be integrated into recent differentiable causal discovery frameworks for guided exploration using interventional data.
Assumptions. The proposed method assumes access to a belief state in the graph structure (e.g.. in the form of distribution over graphs, probabilistic adjacency matrix or a set of hypothetical graphs) and functional parameters P characterizing the conditional relationships between variables (constrained by the graphs sampled from the belief specified by ?). The proposed model does not have to assume causal sufficiency per se. However, it inherits the assumptions of the selected base framework, and this may include causal sufficiency depending on the base algorithm of choice. In case the underlying framework can handle unobserved variables and offers generative method for interventional samples, then our method is also applicable
3.1 A SCORE FOR INTERVENTION TARGETING
Given a graph belief state 7 with its cor- responding functional parameters P, and a possible set of intervention targets (single-node and multi-node intervention targets), we wish to select the most in- formative intervention target(s) Ig- with respect to identifiability of the un- derlying structure. Such target(s) pre- sumably yield relatively high discrepan- cies between samples drawn under differ- ent hypothesis graphs, indicating larger uncertainty about the target's relation to its parents and/or children.
Algorithm Active Intervention Targeting (AIT)
Input: Functional Parameters P, Graph Belief State
Interventional Target Space
Output: Intervention Target 1.-
1: f Sample a set hypothesis graphs from y
2:
for each intervention target 4, in / do Pk +- Perform intervention 1s on P for each graph G. in G do
3:
4:
5:
S Draw samples from Ps on S +- Set variables / to
6:
7:
end for
8: Compute: D3 f- En
E. E5 -
9: end for
We thus construct an F-test-inspired score to determine the /g- exhibiting the high- est discrepancies between post-interventional sample distributions generated by likely graph struc- tures under fixed functional parameters P. In order compare sample distributions over different graphs, we distinguish between two sources variation: Variance between graphs (VBG) and vari- ance within graphs (VWG). While VBG characterizes the variance of sample means over multiple
10: Target Intervention Ig- + arg max (Dx)
3

---

Under review as a conference paper at ICLR 2022
graphs, VWG accounts for the sample variance when specific graph is fixed. As in DSDI and DCDI, we mask the contribution of the intervened variables Ix to VBG and VWG, and construct our discrepancy score D as a ratio D ysg.
This discrepancy score attains high values for intervention targets of particular interest (see Figure p for landscape visualization). While VEG itself indicates for which intervention targets the model is unsettled about, an extension to the proposed variance ratio enables more control over the region of interest. Given fixed set of graphs G and fixed interventional sample size across all graphs, let us assume a scenario where multiple intervention targets attain high VBG, Assessing VWG allows us distinguish between two extreme cases: (a) targets with sample populations that exhibit large VWG (b) targets with sample populations that exhibit low VWG. While high VBG in (a) might be induced by an insufficient sample size due to high variance the interventional distribution itself, (b) clearly indicates high discrepancy between graphs and should be preferentially studied.
Computational Details. We begin by sampling a set of graphs 9 = {G.}, = 1, 2, 3.... from our graph structure belief state 7, however parametrized. This will remain fixed for all considered interventions for the current experimental round. Then, we fix an intervention target I and apply the corresponding intervention P. resulting in partially altered functional parameters Ps where some conditionals have been changed. Next, we draw interventional samples Sh.* from Px on every graph G; E 9 and set variables in J& to zero mask of their contribution to the variance. Having collected all samples over the considered graphs for the specific intervention target Tg, we compute VBG, and VWG as:
VBGk Σ(u -
and
VWG -E -2)1
where j is a vector of the same dimension as any sample in S and denotes the overall sample-mean of the interventional setting, n²² the corresponding mean for specific graph Gi and S is the j-th sample of the i-th graph configuration. Finally, we construct the discrepancy score Dy of Ig as:
VBGk
DE
VWG
In contrast the original definition of the F-Score, we can ignore the normalization constants due to equal group size and degree-of-freedoms. Although the dependence between the variables is apparent from the connected causal structure, we approximate the variance of the multidimensional samples as the trace over the covariance matrix by assuming that the variables are independent. An outline of the method is provided in Algorithm
3.2 THASE DAG SAMPLING
Embedding AIT into recent differentiable causal discovery frameworks requires a graph sampler which generates a set of likely graph configurations under the current graph belief state. However, drawing samples from unconstrained graphs (e.g. partially undirected graphs or cyclic directed graphs) is an expensive multi-pass process. Here, we thus constrain our graph sampling space to DAGs. Since most differentiable causal structure learning algorithms learn edge belief's in the form of soft-adjacency matrix, we present a scalable, two-stage DAG sampling procedure which exploits structural information the soft-adjacency matrix beyond independent edge confidences (see Figure 2 for visual illustration). More precisely, we start by sampling topological node orderings from an iterative refined score and construct DAGs in the constrained space by independent Bernoulli draws over possible edges. We can thus guarantee DAGness by construction and do not have rely on expensive, non-scalable techniques such as rejection sampling or Gibbs sampling. The overall method is inspired by topological sorting algorithms of DAGs where we iteratively identify nodes with no incoming edges, remove them from the graph and repeat until all nodes are processed.
Soft-A Adje-Adjacency. Given a learnable graph structure 7 E N of graph over N variables, the soft- adjacency matrix is given as (()) E [0, 1 such that (1k)) E [0, 1] encodes the probabilistic belief in random variable X, being a direct cause of X,, where (I) = (1 + exp(-x)) denotes the sigmoid function. For the ease of notation, we define A = (7) and A denotes the considered soft- soft-adjacency (1y) at iteration k. Note that the shape of A changes through the iterations.
Sample node orderings. For the iterative root sampling procedure, we start at iteration k = with an initial soft-adjacency A A and apply the following routine for N iterations. We take
4

---

Under review as a conference paper at ICLR 2022
Piaagge de
PC lample basec Medeerrdeingg
CO
SAURLE enfesssyy
SAMR ANO
08
Figure 2: Two-Stage DAG Sampling: Based soft-adjacency o()), we sample topological node ordering from an iterative refined score which is repeatedly computed until we have processed all nodes of the graph. We proceed by permuting (77) according the drawn node ordering and constrain the upper triangular part to ensure DAGness. Finally, we take independent Bernoulli draws of the unconstrained edge beliefs and arrive sampled DAG.
the maximum over rows of A resulting in vector of independent probabilities p²: where p (i) denotes the maximal probability of variable X; being a child of any other variable at the current belief state. After taking the complement , = p". we arrive at p where (i) denotes the approximated probability of variable X; being root node in the current state. In order to arrive at normalized distribution to sample a root node, we apply a temperature-scan scaled softmax:
exp [pf (i)/t]
(1) (oftmax(p:/t).. = E, exp (p/t))
where t denotes the temperature. The introduction of lemperature-ssaling allows control the distribution over nodes and account for the entropy of the structural belicf. We proceed by sampling (root) node as x Categorical(p5) and delete all corresponding rows and columns from A and arrive at a shrinked soft-adjacency A [0, We repeat the procedure until we have processed all nodes and have resulting topological node ordering of (r") .... --1]
over the remaining variables.
Sample DAGs based on node orderings. Given a node ordering <. we permute the soft-adjacency A accordingly and constrain the upper triangular part by setting values ensure DAGness by construction (as shown in Figure 2b. Finally, we sample a DAG by independent Bernoulli draws of the edge belief's, proposed Ke al. (2019).
3.3 APPLICABILITY TO DSDI
Before integrating our method into the DSDI framework, must choose/design graph sampler based on DSDI's graph belief characterization and define a sampling rou- tine to generate interventional samples under a given state of the structural and functional parameters.
Sample graphs
Phase
Intervention Targeting
Phase 1 Graph Fitting
Scoring
DSDI offers learnable graph structure over N variables with y E R N such that (()) E [0, 1 NNN encodes the soft-adjacency matrix. This formulation naturally sug- gests the application of the introduced two-phuse DAG sampling to generate hypothetical DAGs under current beliefs. Under these acyclic graph configurations, may then apply an intervention to DSDI functional pa- rameters P and sample data using ancestral sampling.
Update graph
Phase
Credit Assignment
Figure 3:
Adapted workflow of DSDI with Active Intervention Targeting
DSDI's architectural choices allow a seamless integration of our proposed active intervention tar- geting into stage 2 of DSDI, where graphs are evaluated using interventional data. See Figure for an illustrative description of the adapted workflow and | for a compact description of the base framework.
5

---

Under review as a conference paper at ICLR 2022
3.4 APPLICABILITY TO DCDI
DCDI also offers access to y E R X which allows the same setup as with DSDI, In order to gener- ate interventional samples under the hypothetical graphs, we alter the conditionals of the intervened variables and perform ancestral sampling based on the model's learned conditional densities.
Embedding AIT into DCDI allows us to predict an interventional target space instead of relying on random interventional samples chosen out of the full target space. In contrast to the unconstrained target space of the original formulation, we estimate a target space of constrained size using AlT and reevaluate it after a fixed number of gradient steps (see 1A.7. for technical details).
4 EXPERIMENTS
We evaluate the proposed active intervention targeting mechanism on single-target interventions un- der two different settings: DSDI (Ke et al. 2019) and DCDI (Brouillard et al. (2020). We investigate the impact of AIT under both settings for identifiability, sample complexity, and convergence be- haviour compared to random targeting where the next intervention target is chosen independent of the current evidence. In further line of experiments, to convergence behaviour and the distribution of target node selections. This section will highlight our results on DSDI while also including key results with respect to DCDI (structural discovery and identifiability). However, further analysis of DCDI results have been shifted to the Appendix.
analyze the targeting dynamics with respect
Evaluation Setup. A huge variety of SCMs and their induced DAGs exist, each of which can stress causal structure discovery algorithms in different ways. We perform a systematic evaluation over a selected set of synthetic and non-synthetic SCMs (and datasets). We distinguish between synthetic structured graphs and random graphs, the latter generated from the Erdós-Rényi (ER) model with varying edge densities (see fAr3 detailed description of the setup). For conciseness, we only report results on 15-node graphs in this section for the noise-free synthetic setting for AIT on DSDI and on 10-node graphs for the noisy setting for AIT DSDI (discrete data). In addition, we report key results on 10-node graphs for AIT on DCDI (continuous data) in the main text and provide further results and ablation studies in Appendix. We complete the setup with the Sachs flow cytometry dataset (Sachs et al. 2005) and the Asia network (Lauritzen & Spiegelhalter 1988) to evaluate the proposed method on well-known real-worid datasets for causal structure discovery.
Key Findings. (a) We report strong results for active-targeted structure discovery on both dis- crete and continuous-valle valued datasets, outperforming random targeting in all experiments. (b) The proposed intervention targeting mechanism significantly reduces sample complexity with strong benefits for graphs of increasing size and density. (c) The distribution of target selections during graph exploration is strongly connected to the topology of the underlying graph. (d) Our method capable of identifying informative targets. (c) Undesirable interventions are drastically reduced. (f) When monitoring structured Hamming distance (SHD) throughout the procedure, an "clbow" point appears approximately when the Markov equivalence class (MEC) has been isolated. (g) ATT introduces desirable properties such as improved recovery of erroneously converging edges. (h) AIT significantly improves robustness in noise-perturbed environments.
Structure discovery: Synthetic datasets. We evaluate accuracy in terms of Structural Hamming Distance (SHD) (Acid & de Campos) 2003) on diverse set of synthetic non-linear datasets under both DSDI and DCDI, adopting their respective evaluation setups.
The results of DSDI with AIT are reported in Table [ DSDI with active intervention targeting outperforms all baselines and DSDI with random intervention targeting over all presented datasets. enables almost perfect identifiability on all structured graphs of size 15 except for the ful115 graph, and significantly improves structure discovery of random graphs with varying densities. As the size or density of the underlying causal graphs increases, the benefit of the selection policy be- comes more apparent (see Figure We also examine the effectiveness of our proposed method for DCDI (Brouillard et al. 2020) on non-linear data from random graphs of size 10. Active Interven- tion Targeting improves the identification in terms of sample complexity and structural identifiabil- ity compared with random exploration (see Figure 5 and A.7 for further analyses). We observe the
The real-world datasets are available throuha Creative Commons Aun Amrihution-Slan Alike License in the balearn package and most boscline implemestations available Pythum cassal discovery toolox Kalainaton Goudel (019) an license. A-ICP provided at Int:ps:/ /ttpps///ttthppp.///ppp http///tttboccooo/ comm Juangane la/stop but withor a Reense.

---

Under review as a conference paper at ICLR 2022
75
25
22
4003) 50373
40033 10322
1200
2000
Skpps
(a) ER 1:
(b) ER-22-2
(c) ER 4:
Figure 4: DSDI with active intervention targeting (orange) leads to superior performance over ran- dom intervention targeting (blue) on random graphs of size 15. The performance gap becomes more significant with increasing edges density. The plot shows average performance in terms of SHD. Error bands were estimated using 10 random ER graphs per setting.
Table 1:
SHD (lower is better) on various 15-vaiiblle synthetic datasets. Structured graphs are sorted in ascending order according to their edge density. (+) denotes average SHD over 10 graphs.
Structured Graphs
Random Graphs
Chain
Collider
Tree
Bidiag
Jungle
Full
ER-1
ER-2
ER-4
GES
(Chickering 2002
12
14
14
(4-11))
17.6 (+4.6)
39.4 (++67)
GIES
[luser & buhimann 2012
13
6
10
17
23
10.9 (1422)
18.1 (1.33)
39.3 (15.6)
ICP Petes et 2016
14
14
27
26
105
16.2 (23.6)
31.1 (=3.4)
60.1 (#3.9)
A-IC7
Gammara Henoz-Deml
2020
14
26
105
16.2 (+3.6)
31.1 (=3 4)
60.1 (#3.9)
NOTEARS Zheng et al 2018
22
21
26
33
35
23.7 (1.4.0)
35.8 (15.2)
59.5
DAG-GNN ar 2019
11
15
27
25
(2:.7)
30.6 (#3.0) 4)
59.7 (#:11)
DSDI (Rundom) [e 2019
0
0
7
1.4 (1-16)
2.1 (4:2.3)
(1227)
DSDI (AIT)
0
0
0
7
0.0 (2:000
0.0 (2:000
(20.0)))))))
clear impact of the targeting mechanisms, which control the order and frequency of interventional targets presented to the model. Further experimental results for DCDI can be found in Appendix.
Structure discovery: flow cytometry and asia dataset. While the synthetic datasets systematically explore the strengths and weaknesses of causal structure discovery methods, we further evaluate their capabilities on the real-world flow cytometry dataset (also known as Sachs (etwork)(Sach, et al.] 2005) and the Asia network (Lau-) ritzenn & Spiegelhalter 1988) from the Bnlearn Repos- itory. DSDI with active intervention targeting outper- forms all measured baselines and achieves the same re- sult random targeting in terms of SHD, but with re- duced sample complexity. Despite AIT deviating only by 6 undirected edges from the (concensus) ground truth structure of Sachs et al. (Sachs et al. 2005)) there is some concern about the correctness of this graph and the different assumptions associated with the dataset (Mooij et al., 2020, Zemplenyi & Miller 2021). Therefore, perfect identification may not be achievable by any method in practice in the Sachs setting.
Table 2: SHD (lower is better) on two real-world datasets
Sachs
GBS (Chickerine 2002
GIES (Finiser & bin Huntmann 2012
16
II
(Felos
A-ICF Gamgea & Heniee 2020
NOTEARS Zheng et 2018]
22
14
DAG-GNN et 2019
DSDI (Random) (Ke et 2019
0
DSDI (AIT)
0
Effect of intervention targeting on sample complexity. Aside from the significantly improved identification of underlying causal structures, our method allows for substantial reduction in in- terventional sample complexity. After reaching the "elbow" point in terms of structural Hamming distance, random intervention targeting requires fairly long time to converge to solution within the MEC. In contrast, our proposed technique continues select informative intervention targets beyond the elbow point and more quickly converges to the correct graph within the MEC. The continued effectiveness of our method directly translates to increased sample-effccincy and conver- gence speed, and is apparent for all examined datasets (see Figure
Distribution of intervention targets. The careful study the behaviour of the proposed method under our chosen synthetic graphs enable us to reason about the method's underlying dynamics. Analysing the dynamics of intervention targeting reveals that the distribution of target node selec- tions is linked to the topology of the underlying graph. More specifically, the number of selections of a given target node strongly correlates with its out-degree and number descendants in the underly- ing ground-truth graph structure (see Figure 7). That our method prefers interventions nodes with
7

---

Under review as a conference paper at ICLR 2022
107F
Figure 5: AlT-guided DCDI (orange) allows a more rapid discovery of the causal structure compared DSDI relying on random interventions (blue). The distribution of selected intervention targets shows its correlated connection to the topology of the underlying graph where nodes of greater impact on the overall system are preferentially studied and nodes without children are rarely chosen.
CIN
2000
Figure 6: DSDI: Dynamics and target distribution of AIT for structured jungle graph of size 15. The graphs' nodes are sorted topological order, root node first. The graph is binary-tree-like with 4 levels. For the dense jungles e15, the multi-level structure characteristic of the tree-like graph is readily apparent even before the elbow point. Nodes without children are very rarely chosen.
greater (downstream) impact on the overall system can be most clearly observed in the distribution of target selection on the example of the synthetic jungle graph in Figure 6
Selection of informative targets. Apart our strong results in the discovery of the underlying causal graph, we demonstrate AIT's general ability of detecting informative intervention targets in a careful designed empirical study in Appendix $A.6.7
Reduction of undesirable interventions. An intervention destroys the original causal influence of other variables on the intervened target variable 4,. so its samples cannot be used determine the causal parents of Ja in the undisturbed system. Therefore, if a variable without children is detected, interventions upon should be avoided since they effectively result in redundant obser- vational samples of the remaining variables that of no benefit for causal structure discovery. Active intervention targeting leads to the desirable property that interventions on such variables are drastically reduced (see Figure 5 5nd T6.
Identification Markov equivalence class. Investigating the evolution of the intervention tar- get distribution over time reveals that the causal discovery seems to be divided into two phases of exploration: Phase lasts until the elbow point in terms of SHD, and Phase from the elbow point until convergence (see Figure 4). We observed over multiple experiments that phase 1 tends to quickly discover the underlying skeleton (removing superfluous connections while keeping some edges undirected), until a belief state Yelbow is reached representing a MEC, or class graphs very close to a MEC. Phase 2 is predominantly operating on the partially directed skeleton and directed on the remaining edges.
Recovery of erroneously converging edges. Recovery of eecorrecty--oonverinng edges critically depends on adapting the order of interventions. which random intervention policy does not. In sharp contrast, intervention targeting significantly promotes early recovery from incorrect assign- ment of an edge. In contrast, the observed edge dynamics and the corresponding graph belief states indicate that the random policy lock itself into unfavorable belicf states from which recovery is extremely difficult, while AIT provides an escape hatch throughout learning.
AIT improves robustness in noise-perturbed environments. Considering that noise significantly impairs the performance of causal discovery, we examine the performance of active intervention targeting in noise- perturbed environments with respect SHD and convergence speed and compare with random intervention targeting. We conduct experiments under different noise levels in the setting of binary data generated from structured and random graphs of varying density. A noise level
8

---

Under review as a conference paper at ICLR 2022
COL
004
0.14
COLUDERIS
4.38
188616
022
0.81
030
TREE16
0:56
4,11
402
B0AA015
401
0.60
4.6
4.6
A005
0.77
4.81
4.97
4:57
JUNGLE15
081
0.52
0.7
450
482
0.28
0.65
4.79
4.07
6:7
PUL-18
0.7
0.32
0.33
4.57
4.0
FULL15
0:43
0:60
4.90
4.33
6:43
E8-11
022
0.25
0.13
0.00
4.19
27-19
0.79
3.70
4.48
4.54
0.19
6R/211
0.2
422
4.30
031
0.50
4.73
Dasosidatt
Dight
Arcanttle
Topringal Osle
Desnvodara Out-agew
Se Drggee
Ariestos
Togilogica Gnly
(a) Random Targeting
(b) Active Intervention Targeting
Figure 7: Correlation scores between the number of individual target selections and different topo- logical properties of those targets. AIT shows strong correlations with the measured properties over all graphs, which indicates controlled discovery of the underlying structure through preferential targeting of nodes with greater (downstream) impact the overall system.
Sage
S8035
(a) 17 0 0
(b) 17 0.01
(c) 1) 0.02
(d) 17 = 0.05
Figure 8: Convergence Behaviour in terms of SHD for random ER-4 graphs over 10 variables under different noise levels 7/ where Active Intervention Targeting (orange) clearly outperforms Random Targeting (blue) over all noise levels. The performance gap becomes of larger magnitude as the noise level increases. Error bands were estimated using random ER graphs per setting.
y denotes the probability of flipping random variable and applying it to all measured variables of observational and interventional samples. Through all examined settings, we observe that active in- tervention targeting significantly improves identifiability in contrast to random targeting (sec 6A.6.6 for detailed results). Active intervention targeting perfectly identifies all structured graphs, except for the collider and full graph, up to noise level of 7) 0.05, i.e. where every 20th variable is flipped. The observed performance boost is even more noticeable in the convergence speed, as shown in Fig. for ER-4 graphs spanning over 10 variables. While the convergence-gan gets more significant with an increasing noise level, random targeting does not converge to the ground-truth graphs for a noise level higher than y7 = 0.02. In contrast, AIT still converges to the correct graph convergence tendency for 7) 0.05. These findings support observation from
and shows different experiments that active intervention targeting leads to more controlled and robust graph discovery. Further experimental results in noise-perturber environments be found in Appendix.
CONCLUSION
Promising results have driven the recent surge of interest in continuous optimization methods for Bayesian network structure learning from observational and interventional data. In this work, we propose an active learning method to choose interventions that help to identify the underlying graph efficiently the setting differentiable causal discovery. We show via detailed empirical study that active intervention targeting not only improves sample efficiency but also the identification of the underlying causal structures compared to random targeting of interventions.
While our method shows significant improvements with respect to sample efficiency and graph re- covery over existing methods across multiple noise-free and noise-perturbed datasets, the number of interventions is not yet optimal (Atkinson & Fedorov 1975 Eberhardt et al. 2012) and can po- tentially be reduced in future work. Further, in this work, the interventional samples were presented to the evaluated frameworks according to a fixed learning schema (e.g. fixed number of samples for evaluated interventions in graph scoring). It would be interesting to see the information discovered by AIT could be used for more adaptive learning procedure further improve sample efficiency.

---

Under review as a conference paper at ICLR 2022
6 REPRODUCIBILITY
We encourage the reproduction and extension of our presented work by disclosing all relevant infor- mation. From methodological point of view, provide detailed information including algorithm outlines for the proposed score-based intervention targeting mechanism in section section [.1 and similarly for the proposed two-stage DAG sampling technique in section 3.2 and appendix A.2 Regarding the embedding of the proposed AIT framework into existing differentiable causal dis- covery frameworks, we introduce the seamless embedding of our proposed method into DSDI (ee 3.3 and discuss the embedding including relevant structural changes of DCDI (Brouillard al. 2020) section 333 and uppendix(A.71) Moreover, we report all hyperparameters in appendix A.5 and provide a link to an anonymous repository for reviewers and area chairs once the discussion forums open. The fully documented code will be soon publicly released to the entire audience.
et al., 2019) in section
REFERENCES
Silvia Acid and Luis M de Campos. Searching for bayesian network structures in the space of restricted acyclic partially directed graphs. Journal of Artificial Intelligence Research, 18:445- 490, 2003.
Raj Agrawal, Chandler Squires, Karren Yang, Karthikeyan Shanmugam, and Caroline Uhler. Abed- strategy: Budgeted experimental design for targeted causal structure discovery. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 3400-3409. PMLR, 2019.
Yashas Annadani, Jonas Rothfuss, Alexandre Lacoste, Nino Scherrer, Anirudh Goyal, Yoshua Ben- gio, and Stefan Bauer. Variational causal networks: Approximate bayesian inference over causal structures. arXiv preprint Si0i:::000.0663355 2021.
Anthony C Atkinson and Valerii Vadimovich Fedorov. Optimal design: Experiments for discrimi- nating between several models. Biometrika, 62(2):289-303, 1975.
Elias Bareinboim and Judea Pearl. Causal inference and the data-fusion problem. Proceedings of the National Academy of Sciences, 113(27):734--335, 2016.
Yoshua Bengio, Tristan Deleu, Nasim Rahaman, Rosemary Ke, Sébastien Lachapelle, Olexa Bila- niuk, Anirudh Goyal, and Christopher Pal. A meta-transfer objective for learning disentangle causal mechanisms. arXiv preprint 191.v:1901.10911 2019.
Philippe Brouillard. Sébastien Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien. and Alexandre Drouin. Differentiable causal discovery from interventional data. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, Curran Associates, Inc., 2020.
volume 33, pp. 21865-21877
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 30005)55 2002.
Hyunghoon Cho, Bonnie Berger, and Jian Peng. Reconstructing causal biological networks through active learning. PloS one, 11 113):e015061 2016.
Atray Dixit, Oren Parnas, Biyu Li, Jenny Chen, Charles P Fulco, Livnat Jerby-Amon, Nemanja D Marjanovic. Danielle Dionne, Tyler Burks, Raktima Raychowdhury, et al. Perturb-seq: dissecting molecular circuits with scalable single-cell ma profiling of pooled genetic screens. Cell, 167(7): 1853-1866, 2016.
Frederick Eberhardt. Almost optimal intervention sets for causal discovery. arXiv preprint arXiv:1206.32550 2012.
Frederick Eberhardt and Richard Scheines. Interventions and causal inference. Philosophy of Sci- ence, 74(5):981-995, 2007.
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: /207 3899, 2012.
10

---

Under review as a conference paper at ICLR 2022
Juan L Gamella and Christina Heinze- Demi Active invariant causal prediction: Experiment selec- tion through stability, arXiv preprint arXiv:2006.05690) 2020.
AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Elias Bareinboim. Budgeted ex- periment design for causal structure learning. International Conference on Machine Learning. pp. 1724-1733. PMLR, 2018.
AmirEmad Ghassami, Saber Salchkaleybar, and Negar Kiyavash. Interventional experiment design for causal structure learning, arXiv preprint arXiv:1910.05651, 2019.
Kristjan Greenewald, Dmitriy Katz, Karthikeyan Shanmugam, Sara Magliacane, Murat Kocaoglu, Enric Boix Adsera, and Guy Bresler. Sample efficient active learning of causal trees. 2019.
Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs. The Journal of Machine Learning Research, 13 (1):2409-2464, 2012.
Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 55(4):926 939, 2014.
Yang-Bo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9(Nov):2523-255) 254-77572, 2008.
Christina Heinze-Deml, Marloes H Maathuis, and Nicolai Meinshausen. Causal structure learning. Annual Review of Statistics and Its Application, 5:371-391, 2018.
Steven M Hill, Laura M Heiser, Thomas Cokelaer, Michael Unger, Nicole K Nesser, Daniel E Carlin, Yang Zhang, Artem Sokolov, Evan Paull, Chris K Wong, et al. Inferring causal molecular networks: empirical assessment through community-based effort. Nature methods, 13(4):310- 318, 2016.
Antti Hyttinen, Frederick Eberhardt, and Patrik O Hoyer. Experiment selection for causal discovery. Journal of Machine Learning Research, 14:3041-3071, 2013.
Diviyan Kalainathan and Olivier Goudet. Causal discovery toolbox: Uncover causal relationships in python. arXiv preprint arXiv:1903.022788 2019.
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: 1803.0/900 2018.
Nan Rosemary Ke, Olexa Bilaniuk, Anirudh Goyal, Stefan Bauer, Hugo Larochelle, Bernhard Schölkopf, Michael C Mozer, Chris Pal, and Yoshua Bengio. Learning neural causal models from unknown interventions. arXiv preprint arXiv: 2019.
Murat Kocaoglu, Alex Dimakis, and Sriram Vishwanath, Cost-optimal learning of causal graphs. In International Conference on Machine Learning, pp. 1875-1884, PMLR, 2017a.
Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Experimental design for learning causal graphs with latent variables. In Advances in Neural Information Processing Systems, pp- 7018-7028, 2017b.
Kevin B Korb and Ann E Nicholson. Bayesian artificial intelligence. CRC press, 2010.
Sébastien Lachapelle, Philippe Brouillard, Tristan Deleu, and Simon Lucoste-Julien. Gradient-based neural dag learning. In International Conference on Learning Representationss 2020.
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 (Methodological), 1572)1557-14, 1988.
Erik M Lindgren, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. Experimental design for cost-aware learning of causal graphs. arXiv preprint arXiv: 1867, 2018.
11

---

Under review as a conference paper at ICLR 2022
Phillip Lippe, Taco Cohen, and Efstratios Gavves. Efficient neural causal discovery without acyclic- ity constraints. arXiv preprint arXiv:2107.10433 2021.
Lars Lorch, Jonas Rothfuss, Bernhard Schölkopf, and Andreas Krause. bayesian structure learning. arXiv preprint arXiv:2/05.11839 2021.
Dibs: Differentiable
R. Duncan Luce. Individual Choice Behavior: A Theoretical analysis. Wiley, New York, NY, USA, 1959.
Andrés Masegosa and Serafín Moral. An interactive approach for bayesian network learning using domain/expert knowledge. International Journal of Approximale Reasoning, 54(8): 168-1181, 2013.
Joris M. Mooij, Sara Magliacane, and Tom Claassen. Joint causal inference from multiple con- texts. Journal of Machine Learning Research, 21(99):1-108, 2020. /RL/attp:/ /mlr. org/
hapers/v21/17-11 11/./111111111 html
Kevin P Murphy. Active learning of causal bayes net structure. 2001.
Robert Osazuwa Ness, Karen Sachs, Parag Mallick, and Olga Vitek. A bayesian active learning
experimental design for inferring signaling networks. In International Conference on Research in Computational Molecular Biology, pp. 134-156. Springer, 2017.
Ignavier Ng, Shengyu Zhu, Zhitang Chen, and Zhuangyan Fang. A graph autoencoder approach to causal structure learning. arXiv preprint 1rXiv: 1911.07400 2019.
Jonas Peters, Peter Bühlmmann and Nicolai Meinshausen. Causal inference by using invariant pre- diction: identification and confidence intervals. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 78(5):947-0012, 2016.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations foundatiot and learning algorithms. The MIT Press, 2017.
Robin L Plackett. The analysis of permutations. Journal of the Royal Statistical Society: Series C (Applied Statistics), 1932))193-200) 1975.
Danilo Jimenez Rezende and Shakir Mohamed. Variational inference with normalizing flows. arXiv 2015.
preprint arXiv::505.n00
Karen Sachs, Omar Perez, Dana Pe'er, Douglas Lauffenburger, and Garry P Nolan. Causal protein-signaling networks derived from multiparameter single-cell data. Science, 308(5721): 523-529, 2005.
Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings of the IEEE, 109(5):612 634, 2021.
Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G. Dimakis, and Sriram Vishwanath. Learn- ing causal graphs with small interventions. In NIPS, pp. 3195-3203, 2015.
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, Sara Magliacane, Kristjan Greenewald, Dmitriy Katz, Murat Kocaoglu, and Karthikeyan Shanmugam. Active structure learning of causal dags via directed clique tree. arXiv preprint arXiv:2011.00644 2020.
Simon Tong and Daphne Koller. Active learning for structure bayesian networks. In International joint conference artificial intelligence, volume 17, pp. 863 869. Citeseer, 2001.
Matthew J Vowels, Necati Cihan Camgoz, and Richard Bowden. D'ya like dags? survey structure learning and causal discovery. arXiv preprint arXiv:2103.02582 2021.
Yue Yu, Jie Chen, Tian Gao, and Mo Yu. Dag-gnn: Dag structure learning with graph neural networks. In International Conference Machine Learning, pp. 7154-7163. PMLR, 2019.
12

---

Under review as a conference paper at ICLR 2022
Michele Zemplenyi and Jeffrey W Miller. Bayesian optimal experimental design for inferring causal structure. arXiv preprint arXiv22103.1522, 2021.
Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. DAGs with NO TEARS: Continuous optimization for structure learning. Advances in Neural Information Processing Systems, volume 31, pp. 9472-9483, 2018.
Xun Zheng, Chen Dan, Bryon Aragam, Pradeep Ravikumar, and Eric Xing. Learning sparse non- parametric dags. In International Conference on Artificial Intelligence and Statistics, pp. 3414 3425. PMLR, 2020.
Shengyu Zhu, Ignavier Ng. and Zhitang Chen. Causal discovery with reinforcement learning. In International Conference on Learning Representations, 2020.
13

---

Under review as a conference paper at ICLR 2022
A
APPENDIX
CONTENTS
Related Work
15
A.2
Two-Stage DAG Sampling
16
1.2.1
Algorithm Outline
16
A.2.2
Connection to Plackett- Luce distribution (Luce 1959
Plackett
1975)
16
A.3
Experimental Setup
17
A.3.1
Synthetic Datasets
17
A.3.2
Real-World Datasets
18
A.4
Availability of Used (Existing) Assets
18
Parameeess
19
A.6
Discrete Setting: Additional Experiments Results
20
A.6.1
Evaluation (SHD) on graphs of varying size and density
20
A.6.2
Evaluation of convergence speed on graphs of varying size and density
21
A.6.3
Target selection analysis for graphs of varying size density
22
A.6.4
Visualization of target distribution on structured graphs of size
23
A.6.5
Extended Analysis of Edge Dynamies
24
A.6.6
Improved robustness with DSDI+AIT in noise perturbed environments
26
A.6.7
Identification of informative intervention targets
27
A.6.8
Limited Intervention Targets
28
A.7
Continuous Setting: Technical Details and further Results
31
A.7.1
Integration of AIT into DCDI
31
A.7.2
Evaluation
31
14

---

Under review as a conference paper at ICLR 2022
A.1
RELATED WORK
Causal induction can use either observational and (or) interventional data. With purely observa- tional data, the causal graph is only identifiale up to a Markov equivalence class (MEC) (Spirtes) et al. 2000), interventions are needed in order to identify the underlying causal graph (Eberhardt & Scheines 2007). Our work focuses on causal induction from interventional data.
Causal Structure Learning. There exists several approaches for causal induction from interven- tional data: score-based, constraint-based, conditional independence test based and continuous op- timization. We refer to (Heinze-Deml et al., [2018] Vowels et al. (021]) for recent overviews. While most algorithms perform heuristic, guided searches through the discrete space of DAGG,[Zheng et al. (2018) reformulates it as a continuous optimization problem constrained to the zero level set of the adjacency matrix exponential. This important result has driven recent work the field and showed promising results (Kalainathan et al. 2018 Yu al. 2019 Ng al. 2019: Lachapelle et al. 2020 Zheng et al. [2020] Zhu et al. 2020). Due to the limitations of purely observational data, Ke et al. (2019) and Brouillard et al. (2020) extend the continuous optimization framework to make use of interventional data. [Lippe et al.] (2021) scales in a concurrent work with ours the work of (Ke) al. (019) to higher dimensions by splitting structural edge parameters in separate orientation and likelihood parameters and leveraging it in an adapted gradient formulation with lower variance. In contrast (Brouillard et al. 2020: Ke et al. 2019) and our work, they require interventional data on every variable.
Active Causal Structure Learning. Interventions are usually hard to perform and some cases even impossible (Peters et al. 2017). Minimizing the number of interventions performed is desir- able. Active causal structure learning addresses this problem, and number of approaches have been proposed in the literature. These approaches can be divided into those that select intervention targets using graph- graph-theoretic frameworks, and those using Bayesian methods and information gain.
Graph-theoretic frameworks usually proceed from pre-specified MEC or CPDAG (completed par- tially directed acyclic graph) and either investigate special graph substructures (He & Geng 2008 such as cliques (Eberhardi) (2012, Squiies et al., 2020). trees (Greenewall et al. 2019), or they prune and orient edges until satisfactory solution reached (Ghassami et al. 2018 [
2019 Hyttinen et al,,
2013), perhaps under a cost budget (Kocaoglu et al. 2017a Lindgren et al. 2018). Their chief limi- tation that an incorrect starting CPDAG can prevent reaching the correct graph structure even with an optimal choice of interventions.
The other popular set of techniques involve sampling graphs from the posterior distribution a Bayesian framework using MCMC and then selecting the interventions which maximize the in- formation gain on discrete (Murphy) 2001] TTog & Koller) (001) or Gaussian (Cho et al.] (016)) variables. The drawbacks of these techniques are poor scaling and the difficulty of integrating them with non- Bayesian methods, except perhaps by bootstrapping (Agrawal et al. 2019).
In contrast to existing work, our base frameworks do not from pre-specified MEC CPDAG and existing graph-theoretical approaches are hence not applicable unless we pre-initalize them with a known skeleton. However, in the case we offer access to a predefined structure in the form of MEC or CPDAG, a previously directed edge is likely to be inverted during the ongoing process which contradicts with the underlying assumptions of existing approaches. Further, we build atop non-Bayesian frameworks and are therefore limited in applying methods based on information gain which require access to a posterior distribution over graph structures. While bootstrapping would allow to approximate the posterior distribution over graph structures in non-Bayesian setting, is not guaranteed to achieve full support over all graphs since the support is limited to graphs estimated in the bootstrap procedure (Agrawal et al. 2019). Furthermore, the computational burden of bootstrap would limit us in scaling to graphs of larger size.
15

---

Under review as a conference paper at ICLR 2022
A.2 TWO-STAGE DAG SAMPLING
A.2.1 ALGORITHM OUTLINE
We present an outline of the proposed two-stage DAG sampling procedure which exploits structural information of the soft-adjacency beyond independent edge confidences. The routine based on graph belief state where ( denotes soft-adjacency characterization. We start by sampling topological node orderings from an iterative refined score and construct DAGs in the constrained space by independent Bernoulli draws over possible edges. We can therefore guarantee DAGness by construction.
The temperature parameter t > 0 of the lemperature-scales softmax can be used to account for the entropy of the graph belief state. However, in the general setting we suggest to initialize the parameter to 0.1. Note that initializing t - results in always picking the maximizing argument and + 3o results an uniform distribution.
Algorithm Two-Stage DAG Sampling
Input: Graph Belief State (T)) in the form of soft-adjacency matrix Output: DAG Adjacency Matrix Apag
b Phase 1: Sample Node Ordering <
1: A + (7))
2: nodes f- 00 .... - 1]
3: for k 0 to N do
4:
(1) t max [1
5:
pf (i) 1 (i)
01/4
6:
(1) + Σ, 0V/1
7:
Tk nodes[idæ*] where idx (ategorical(ps)
8:
Remove from nodes
9:
A A [modes, nodes]
10: end for
1r ,r.,..., N-11
Phase 2: Sample DAG based node ordering <
12: Aperm
Permute (1y) according <
13: Aperm f- Constrain upper diagonal part by setting values to 0
14: A Ber Bernoulli(A perm)
15: Apag f- Apply inverse permutation of < to A
A.2.2 CONNECTION TO PLACKETT-LUCE DISTRIBUTION (LUCE 1959 PLACKETT 1975)
Our proposed node ordering sampling routine can be regarded as an extension of the Placket-Luce distribution over node permutations. In contrast, we refine scores in an iterative fashion rather than setting them apriori as we account for previously drawn nodes to estimate the probability of node being the root node in the current iteration.
16

---

Under review as a conference paper at ICLR 2022
A.3 EXPERIMENTAL SETUP
A huge variety of SCMs and their induced DAGs exist, each of which can stress causal structure discovery algorithms in different ways. In this work, We perform systematic evaluation over selected set of synthetic and non-synthetic SCMs. We distinguish between discrete (based on DSDI (ee et al., 2019)) continuous (based on DCDI (Brouillard et al. (2020) valued random variables. Through all experiment, we limit us to 1000 samples per intervention.
A.3.1 SYNTHETIC DATASETS
Graph Structure. We adopt the structured graphs (see Fig. 9 proposed the work of DSDI (Ke al. 2019) as they adequately represent topological diversity of possible DAGs in compact fashion. They can be split up in a set of graphs without cycles in the undirected skeletons, and one group with cycles. Extending the setup with random graphs with varying edge densities, generated from the Erdós Erdös-Rényi (ER) model, allows us to assess the generalized performance of the proposed method from sparse to dense DAGS.
Discrete Data Generation. We adopt the generative setup of DSDI (Ke et al. 2019) and model the SCMs using two-layer MLPs with Leaky ReLU activations between layers. For every variable X;, seperate MLP models the conditional relationship P p(X))xXa(t)). The MLP parameters are initial- ized orthogonally within the range of [-2,5, 2.5] and biases uniformly in the range of [-1.1, 1.1].
Continuous Data Generation. For the evaluation of the adapted DCDI framework, we adopt their generative setup as described in (Brouillad et al. 2020) and use the existing non-linear datasets.
Graphs with acyclic skeletons:
(a) Chain
(b) Col lider
(c) Tree
Graphs with cyclic skeletons:
N2
(d) Bidiag
(e) Jungle
(f) Full
Figure 9: Visualization of Structured Graphs as proposed et (2119) adapted illustration
17

---

Under review as a conference paper at ICLR 2022
A.3.2 REAL-WORLLS DATASETS
Besides the many synthetic graphs, we evaluate our method on real-world datasets provided by the BnLearn data repository. Namely on the Asia (Lauritenn & Spiegelhaterr (988) and the Sachs (Sachs et al. 2005) datasets (see Fig. I0 for visualization of their underlying ground-truth struc- ture). Sachs (Sachs et al., (205) represents a systems biology dataset which exhibits non- non-lineame non-linearity, confounding and complex structure.
PKC
Plcg
(KA
PIP3
Lp
Lung
Rat
Jnk
P38
PIP2
other
oronc
Mek
AT3
Sysp
Akt
(b) Sachs
(a) Asia
Figure 10:
Ground-truth structure of the evaluated real-world datasets provided by the Bn- Learn data repository Illustration from: httppp//www.oallec....ooooorpppp
discrete- .htll
A.4
AVAILABILITY OF USED (EXISTING) ASSETS
Base Frameworks.
Entervent httppp///ttthboccm///ee//aaaaaaa
DSDI (Ke al. 2019)
DCDI (Brouillard et al. 2020 httpst//ghhabbboo/////aaaaappppp
Baseline Methods.
GES (Chickering 2002) and GIES (Hauser Bühlmann 2012):
www. gi github..hh.g.gg. com/
FenTechSo ut ons Causaaausaalaa /ots:/aaaaassoooeeeoooooooooool (alaaaaaaaaaaaaaaaaaaaaa
{|tpa//eooooooioaaaaaaa/aooooonn Kalainathan & Goudet 2019
ICP (Peters et al.
2016 httto///gt///ogggtto/oooo/////nn
A-ICP (Gamella & Heinze-Deee |0t0://taa///ggtuoooooo//aaaaaaa
NOTEARS (Zheng al. httppa//gggatuu.ooom////ee/eeeer
DAG-GNN Yu et al.
2019
Datasets.
BnnLeann Data Repository:
18

---

Under review as a conference paper at ICLR 2022
A.5 HYPER- PARAMETERS
We used a similar set of hyperparameters for our AIT + DSDI and AIT + DCDI models as those used in the original paper (Ke et al. 2019 Brouillard et al. 2020). The specific hyperparamters used are stated as follows.
DSDI
Table 3: Hyperparameters for DSDI including the corresponding
AIT parameters
Number of iterations
1000
Batch size
256
Sparsity Regularizer
0.1
DAG Regularizer
0.5
Functional parameter training iterations
10000
Number of interventions per phase 2
25
Number of data batches for scoring
10
Number of graph configurations for scoring
Graph Size 5:
10
Graph Size 10:
Graph Size 15
40
AIT:
Number of graph configurations
100
Number of interventional samples per graph & target
256
DCDI.
Table 4: Hyperparameters for DCDI including the corresponding AIT parameters
140
10-8 8
Yo
0.9
Augmented Lagrangian Thresh
10-8
Learning rate
10-3
Nr. of hidden units
16
Nr. of hidden layers
AIT:
Number of graph configurations
100
Number of interventional samples per graph & target
256
19

---

Under review as a conference paper at ICLR 2022
A.6 DISCRETE SETTING: ADDITIONAL EXPERIMENTS / RESULTS
In this section, we show further results and visualizations of experiments on discrete data and single-target interventions in various settings (such graphs of varying size, noise-free noise- perturbed, limited intervention targets). All experiments are based on the framework DSDI.
A.6.1 EVALCATION (SHD) ON GRAPHS OF VARYING SIZE AND DENSITY
Table SHD (lower is better) on various 5-variable synthetic datasets. Structured graphs are sorted in ascending order according their edge density. (*) denotes average SHD over 10 random graphs., +ER-2 graphs on 5 results in the full5 graph and ER-4 graphs on node graphs are non- existing
Structured Graphs
Random Gruphs
Chain
Collider
Tree
Bidiag
Jungle
ER-1
ER-2(-)
ER-4
GES
Chickering
6
GIES
Hinuser & Hihlmann 2012
3
2
6
5
10
4.7 (+1.6)
ICP Pears ol
2016
7
6
(=1.4
A-ICP
Gamella Hanze Deml 2020
4
4
7
6
10
5.4
(++14)
NOTEARS
Zheng et al.
2018
5
6
5
7
9
6.1 (#1.7)
DAG-GINN
Yu al nl. 2019
4
4
6
9
5.1
(+1.44)
DSDI (Random) [K et 2019
0
0.0 (#0000
DSDI (AIT)
0.0
(++000)
Table 6: SHD (lower is better) on various 10-variable synthetic datasets. Structured graphs are
sorted in ascending order according to their edge density. graphs.
(*) denotes average SHD over 10 random
Structured Graphs
Random Graphs
Chain Collider
Tree
Bidiag
Jungle
Full
ER-1
ER-2
ER-4
GES Chickering 2002
10
(.0.))))
10.7 (13.8)
26.7 (1.2.9)
GIFS
HHaner Buhlmann 2012
6
13
16
(+-5.1
14.1 (+-4.)
26.1 (+4..4)
ICP Palesy el al 2016
9
9
16
10.6 (12.5)
20.7 (13.3)
39.8 (11.9)
A-ICP
Gameli Hetnae- Demi 2020
9
17
16
10.6 (2:2.)
20.7 (23.3)
39.8 (21.9)
NOTFARS Zhens et al 2018
12
21
(4-44))
22.9 (+229))
(4-66)
DAG-GNN
et
7
15
13
10.3 (12.8)
20.1 (13.5)
38.4 (11.9)
DSDI (Random) Ke ct 2019
0
0
0
0
(:0000:00)
0.0
(=0.0
DSDI (AIT)
(.0000))0)
(:0
(.0
Table 7: SHD (lower is better) on various 15-variable synthetic datasets. Structured graphs are sorted in ascending order according to their edge density. graphs.
(>) denotes average SHD over random
Structured Graphs
Random Graphs
Chain
Collider
Tree
Bidiag
Jungle
Full
ER-1
ER-2
ER-40
GES (Chickering 2002
12
14
(2:1.)
(24.6)
39.4 (26.7)
GIES
Halls Sullmann 2012
13
6
10
17
23
60
(+:12)
18.1 (2:3)
39.3 (=5.6)
Pates 2010
105
(+:3.)
(#3.4)
(+3.9)
A-ICP
(ammella Hennze Deml 2020
14
14
14
27
26
105
16.2 (23.6)
31.1 (23.0)
60.1 (#3.9)
NOTEARS Zheng el al 2018
22
21
26
33
35
23.7 (14.0)
35.8
(9..7
DAG-GNN
et
11
15
25
16.0 (1:37)
30.6 (23.4)
(2:11
DSDI (Random) Ke al. 2019 DSDI (AIT)
0
7
(+116))))
(+2.3)
(42.7)
0.000)))) 7
0.0
0.0.0)).)))
20

---

Under review as a conference paper at ICLR 2022
A.6.2 EVALUATION OF CONVERGENCE SPEED ON GRAPHS OF VARYING SIZE AND DENSITY
While we have shown the effectiveness of AIT on random ER graphs of size 15 in $ observe similar effects on ER graphs of size 10 (see Figure IT. Overall, the results indicate greater impact of our proposed targeting mechanisms on graphs of bigger size compared random intervention targeting which poorly scales to graphs of larger size.
30
23
10000
30001
2000
20391
2000
0.0
0.
30222
Skpp
ER-1:
(b) ER-2:
(c) ER-4:
Figure 11: DSDI with AIT (orange) leads to superior performance over random intervention tar- geting (blue) random graphs of size 10 of varying edge densities. Error bands were estimated using 10 random ER graphs per setting.
23
53
23
511
10000
20000
30003
40023
50303
12000
20000
30000
40003
50232
7200
2000
30000
41003
50022
8kpp
Sbooa
Sloss
0.6
10000
20000
30000
40000
50303
10000
20000
30000
40000
50003
0
10000
20000
30000
40003
50002
93pa
(a)
11
(b) 2:-2:
(c) ER-4
Figure 12: DSDI with AIT (orange) leads to superior performance over random intervention tar- geting (blue) on random graphs of size varying edge densities. Error bands were estimated using 10 random ER graphs per setting.
21

---

Under review as a conference paper at ICLR 2022
A.6.3 TARGET SELECTION ANALYSIS FOR GRAPHS VARYING SIZE AND DENSITY
We evaluate the distribution of larget node selections over multiple DAGS of varying size to investigate the behaviour of our proposed method. Over all performed experiments, our method prefers interventions on nodes with greater (downstream) impact on the overall system, i.e. nodes of higher topological rank in the underlying DAG.
0.58
0.34
0.31
434
-034
0.29
0.78
-0:30
4.78
.076
COLICEE
0.52
0.62
0.82
482
0.2
COLLIDEIS
1.00
1.00
.1.0
1.00
1.00
TREE5
0.10
0.19
0.37
402
002
TREES
1.50
0.90
-0.5
4.79
0.79
FJLL5
0.22
4.32
0.32
FJLL5
0.50
0.89
0.50
3k-1
0.38
0.23
0.24
4.28
0.2
ER.17
0.58
0.04
0.73
4.74
0.77
Ou/-a
Descendiets
I--aggne
Topulogest Cree
0u/04
Descentierss
In-Dugne
Ancretar
Topskogteal
CHAIN10
0.77
-.27
0.71
-0.46
-0.81
4.81
COULIDR10
COLLIDE10
TREE10
0.53
0.3
4.38
-241
4.41
TREE10
0.98
0.4
-4.49
4.82
4.82
0.03
039
4.26
4.38
433
0.2
-.42
4.93
4.3
FULL10
0.37
0.37
4.37
4.37
0.37
FULL10
0.66
0.66
4.86
-.80
4.31
ER-17
0.11
0.15
4.27
-022
0.21
ER
0.59
4.86
4.72
4.14
ER
0.29
0.20
0.42
0.37
ER447
0.66
-.84
4.85
Descondarts DrADuge
InDagae
Anessto
Topotogia
Despandarts DaAbgg
Ancostmm
Topotogaa O-deee
COLLIDR16
0.4
COLLIDE16
0.39
40.33
TREE15
0.22
0.70
4.61
-060
0.00
TRBE16
0.66
077
-0.11
4.92
0.02
0.01
4.87
0.67
JUNGLE16
JUNGLE16
FULL11
03r
037
4337
-037
4.31
FULL11
030
030
-0.5
-093
433
ER
022
0.5
41.3
ER
0.99
-044
-.34
455
BX47
0.30
0.50
4.28
2.31
0.35
E3447
0.66
0.6c
4.78
4.87
0.83
Descondaeds DeDiee
InDeggeee
Topntogiok--rdee
Deacondents Dog-eeeee
Iy-Deglee
Aneedari
Toprtagiaa
(a) Random Targeting
(a) Active Intervention Targeting
Figure 13: Correlation scores over graphs of varying size and density between the number in- dividual target selections and different topological properties of those targets. AIT shows strong correlations with the measured properties over all graphs, which indicates a controlled discovery of the underlying structure through preferential targeting of nodes with greater (downstream) impact on the overall system.
22

---

Under review as a conference paper at ICLR 2022
A.6.4 VISUALIZATION OF TARGET DISTRIBUTION ON STRUCTURED GRAPHS OF SIZE 5
R
(a) Random Targeting
(b) Active Intervention Targeting
Figure 14: Visualization of target selection on structured graphs size 5 bigger node size denotes more selection of the node. While Random Targeting acts as we expect and selects every node an uniform amount, AIT prefers targeting of nodes with greater (downstream) impact on the overall system, i.c. nodes of higher topological order.
23

---

Under review as a conference paper at ICLR 2022
A.6.5 EXTENDED ANALYSIS OF EDGE DYNAMICS
We show all edge dynamics all structured graphs over 15 variables and compare the dynamics of random targeting to active intervention targeting in a noise-free setting where we have access to all possible angle-target interventions.
23
cale Contiaa confidaace dlvl
Edge Contidence div 2
04
02-
2000
19933
2300e
10083
X2000
0000
133009
1.0
10
13
Edpe Confedence 466
2.-
Edge Casthdlece
84
02
2000
JAYV
30500
28022
(a) Graph: Chain
Cdee Contidence a0g
Edge Cinhiorce m1.)
Edgo
08-
2220
40000
2000
3000
X2000
23006
0003
X2000
30500
<0963
2000
10200
120000
Staps
Stegn
Staps
Dápe Confeurce ewy
Edge Contorenn mv
02
04
10000
8000
X000
22006
$0:00
0000
120000
22:00
40003
60000
3000
122000
S0055
30000
S0055
(b) Graph: Tree
13
Edber Co Seience 009
2.-
02-
Edgg Contrdence
10009
Edge Cenfberce 616
Edgy Coshornee mM
08
(c) Graph: Collider
Figure 15: Edge Dynamics of the examined structured graphs spanning over 15 variables Part 1: The upper part shows the dynamics of random targeting and the lower of active intervention targeting.
24

---

Under review as a conference paper at ICLR 2022
10
10
E3t Conifdencc 0000
2.
02-
Edge Contrdencs
300000
00003
Edg- Coshienze aM
E2ge Contreree
00
(d) Graph: Bidiag
Dogs Confeercce elvl
Raye Contreerr my
0.
02
08
2000
2000
30030
20/06
42000
0003
20:00
<0:00
0000
2000
2000
Stopo
10
23-
Clee Confidance divl
Egg Confllnnee dy
2.
04
2.2
2
02-
30099
40000
8000
10300
10003
22000
40300
20002
5000
120000
20003
<2000
30000
5000
12000
3000s
S0200
(e) Graph: Jungle
cage Contdinne stp1
5dye Contebrone mtel
Stops
Stopo
Stot5
Edge Contoeenee 209
Eige Contidecce shy)
a069
30506
30000
300p5
(1) Graph: Full
Figure 16: Edge Dynamics of the examined structured graphs spanning over 15 variables Part 2: The upper part shows the dynamics of random targeting and the lower of active intervention targeting.
25

---

Under review as a conference paper at ICLR 2022
A.6.6 IMPROVED ROBUSTNESS WITH DSDI+AIT IN NOISE PERTURBED ENVIRONMENTS
While section $4 highlights our key findings in noise-perturbed systems, we examine the impact of AIT in noise perturbed environments more thoroughly in this section. Therefore, we systematically analyze experiments under different noise levels in the setting of binary data generated from random graphs of varying densities. A noise level denotes the probability of flipping random variable and apply to measured variables of observational and interventional samples.
Evaluating convergence various ER graphs of varying densities over 10 variables under different noise levels reveals that the impact of AIT becomes of larger magnitude as the density of the graph and the noise level increases.
Table 8: Performance evaluation (SHD) under different noise level 17 for structured and random
graphs (+) denotes average SHD over 3 random graphs.
Chain10
Collider10
Tree10
Bidiagto
Junglet0
Full10
ER-1
ER-2
ER-4
Random
0
0.0 (.10..)
0.0 (110.0)
0.000))))
0.0
AFT
0
0.0
0.000))0 0.0.0))))
Random
0
0
0
3
0.0 (=000))
(=0.0)
0.6 (+0.5)
0.01
(2:000
(20.0)
(1:0.0
Random AIT
0
0
12
0.0 (20000)
0.0 (=000)
6.0..)))))
0.02
3
(=0.0)
(=0.0)
0.0 (+0.0)
Random AIT
0
33
1.3 (+005)
(
(+-0.)
= 0.05
0
0
23
0.0 (=0.0)
1.3 (=0.5)
18.7 (+1.2)
Random
45
(10.88
(10.5)
(10.8)
0.1
AIT
6
16
15
44
10.3 (+0.55
20.0 (++.88
39.3 39.3 (+1.2)
(i) ER-1:
(ii) ER-2: g
9900
20000 30006
1000
2000
9000
4000
3000
1300
2070 1000
(iii) 2: 8"
1000 20000 1000
20000
40:00 1000
14500
20000 J000 4000
1000
1450
2018
0000
(a) 0
(b) = 0.01
(c) 77
0.02
(d) 17 = 0.05
Figure 17: Convergence behaviour in terms of SHD for random ER graphs of various densities 10 variables under different noise levels 77. Overall, Active Intervention Targeting (orange) clearly outperforms Random Targeting (blue) over all densities under all noise levels. The performance gap becomes of larger magnitude as density of the graph and the noise level increases. Error bands were estimated using 3 random ER graphs per setting.
26

---

Under review as a conference paper at ICLR 2022
A.6.7 IDENTIRICATION OF INFORMATIVE INTERVENTION TARGETS
Our proposed method aims select most informative intervention target(s) 4x- with respect to identifiability of the underlying structure. We conjecture that such targets yield relatively high discrepancy between samples drawn under different hypothesis graphs, indicating larger uncertainty about the target node's s relation to its parents and/or children.
In order evaluate our methods capability of detecting informative intervention targets, we per- form multiple experiments on structured graph structures (cha in5, tree5 and ful15) where we preinitalize the structural belief the ground-truth structure structure but keeping one edge between pair of nodes (i.j) undirected, i.c. a (nk,) ( 0.5. Throughout the experiments, we vary the position of the undirected edge and analyze which nodes are targeted by our method.
Over all evaluated settings, we can observe how AIT preferentially targets the pair of nodes cor- responding to the undirected edge, with small preferences towards the source nodes of the correct directed edge (see in Figure 18 and Figure I9). This observation is in line with our conjecture that AIT preferentially targets nodes with larger uncertainty about the target node's 's relation to its parents and/or children.
wearian agg
108
100
01
200
Figure 18: AIT chooses informative intervention targets by preferentially identifying and targeting the pair nodes corresponding to the undirected edge (nodes are marked red in the distribution of selected target nodes and edges is visualized red in the graph the right). First set of experiments based on the structured graphs cha 15 and t rre5.
27

---

Under review as a conference paper at ICLR 2022
200
08
Figure 19: AIT chooses informative intervention targets by preferentially identifying and targeting
the pair of nodes corresponding to the undirected edge (nodes are marked red in the distribution of selected target nodes and edges is visualized red in the graph on the right). Second set of experiments based on the structured graph ful15.
A.6.8 LIMITED INTERVENTION TARGETS
While we allow access to all possible single-target interventions all other experiments, real world settings usually more restrictive. Specific interventions might be either technically impossible or even unethical, or the experiments might want to prevent interventions upon specific target nodes due to increased experiment costs. In order to test the capability of AIT, limit the set of possible intervention targets in the following experiments and analyze the resulting behaviour based on DSDI. We examine speed of convergence and the effect on the target distribution under different scenarios on structured graphs using DSDI with AIT based on single-target interventions.
Scenario We perform experiments on a Chain5 graph where we restrict us on intervening upon a different node in five experiment and once allow access to all targets as comparison.
Throughout the experiments, we observe that blocking interventions on nodes of higher topological level results in greater degradation of the convergence speed compared to blocked intervention on lower levels (see Figure 20). Furthermore, the distribution of selected targets indicates that our method preferentially chooses neighboring nodes of a blocked target node in the restricted setting.
28

---

Under review as a conference paper at ICLR 2022
2000
4009
8000
8000
1000
2500
4003
0000
1000
2030
JOWWERO Dage
Figure 20: Limited intervention targets on Chain5: The impact of the restricted target node (red circled node) is clearly observable in the convergence speed (left) and distribution of selections (middle). The speed of convergence indicates a dependence on the topological characteristic of the restricted intervention target.
29

---

Under review as a conference paper at ICLR 2022
Scenario 2:
We perform multiple experiments Tree5 graph where restrict access dif- ferent subsets of nodes (e.g. root node, set of all sink nodes) for single-tanget interventions.
Similar to the experiments Chain5, targets on the convergence speed and identifiability of the underlying structure (see Figure 2T). While preventing interventions all sink nodes (node 2, 3 and results in improved convergence towards the underlying structure, restricted access to the set of nodes which act as causes other nodes (node 0 and 1) prevents from identifying the correct underlying structure.
observe clear impact of the available intervention
12003 10000 17303
16
T0m 1901 198n
1710
1900
9.59
IRONORI Tapd
2000
3006
1968
10000
12003
17303 15000
2003
Figure 21: Limited intervention targets on Tree5: The impact of the restricted target nodes (red cir- cled nodes) is clearly observable in the convergence speed (left) and distribution of target selections (middle).
30

---

Under review as a conference paper at ICLR 2022
A.7 CONTINUOUS SETTING: TECHNICAL DETAILS AND FURTHER RESULTS
While the original framework of DCDI (Brouillard et al. 2020) proposes a joint-optimizttoon over the observational and interventional sample space by selecting samples random, adapt their framework to the setting of active causal discovery where we acquire interventional sample in an adaptive manner. We hypothesize that a controlled selection of informative intervention targets allows more rapid and controlled discovery of the underlying causal structure.
A.7.1 INTEGRATION OF AIT INTO DCDI
Instead of demanding the full interventional target space during the complete optimization as the original approach, split the optimization procedure into different episodes, where AIT is used to estimate a target space / of size K for each episode. This is done by computing the discrepancy scores over all possible intervention targets and selecting the K highest scoring targets. During an episode, we continue by performing L gradient steps using the fixed target space I and reevaluate it afterwards for the next episode. We visualize the adaption the following high-level outline of the individual methodologies.
Algorithm DCDI+ AIT
Algorithm DCDI
1: for episode e until convergence do
I: < Full target space of size K = N
2: I Estimate target space of size K using AlT
2: Run DCDI on / until convergence
3: Run gradient steps of DCDI
4:
end
A.7.2 EVALUATION
We evaluate the effectiveness of AIT in the base framework DCDI in the setting of non-linear, continuous data generated from random graphs over N 10 variables and show the potential of our proposed method.
Structural Identification / Convergence: Despite their joint optimization formulation is not apriori designed for the setting of experimental design, an AIT guided version shows superior/competitive performance in terms of structural identification and sample complexity over the original formula- tion (see Figure 22).
Distribution of Intervention Targets: As in DSDI, observe strong correlation of the number of target selections with the measured topological properties of the specific nodes. This indicates controlled discovery of the underlying causal structure through preferential targeting of nodes with greater (downstream) impact on the overall system. In addition, interventions on variables without children are drastically reduced (see also for equivalent observations DSDI).
Effect of Target Space Size K: While the original formulation assumes K = N for the com- 1) and relies on random samples out of the full target space, our adapted AlT-guided version of DCDI constrains the target space to a subset of targets for each episode. An ablation study on the size of the target space shows that for all choices of K {2, 4, 6, 8}, our approach outperforms the original formulation in terms of sample complexity while achieving same or better performance in terms SHD.
plete optimization procedure (i.e.
31

---

Under review as a conference paper at ICLR 2022
11
4p
g
Figure 22: While DCDI Vanilla assumes access to the full interventional target space through the complete optimization, the AIT guided DCDI approach reevaluates its interventional target space of size K = 6 every = 1000 gradient steps. Among the above evaluated graphs (ground-truth on the left), DCDI+AIT demonstrates a more rapid identification of the underlying causal structure while achieving same or better performance in terms of SHD. The distribution of selected songle-node intervention targets reveals again its connection to the topological properties of the corresponding nodes.
(a) K
(b) K =
(d) K
(d) K 8
Figure 23: All evaluated target space sizes K (2, 4, 6,8} show that DCDI+AIT (orange) out- performs DCDI (blue) in terms of sample complexity while achieving same or better performance. Error bands were estimated using 10 random ER graphs per setting.
32


Reviews:
[{"review_id": "p92I4j9A8zv", "reviewer": "Reviewer_cZsR", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "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": "Sampling from interventional distributions and quantifying its difference with the available data is creative as an approach to guide the selection of interventional targets. Unfortunately, the paper is very hard to follow and seems to rely excessively on DSDI, both to understand the proposed approach and in applications despite the authors claiming that the proposal can be used with any differentiable causal discovery algorithm (contributions). The exact procedure is complex, it involves sampling DAGs and parameters, and should be clarified. \n\nAm I correct in assuming that in every training iteration of the causal discovery algorithm, the proposed approach samples DAGs, interventional distributions, and samples from each interventional distribution to be compared using the proposed score? What is the computational complexity?\n\nAlong these lines, the exact procedure is unclear. Algorithm 1 vaguely mentions \"perform an intervention\" on line 3 without details of what kind of interventions are considered (e.g. do, soft, what exact values are set, etc.). Next, it is meant to draw samples from $\\mathcal P$ which is defined as a set of functional parameters which I understand are conditional distributions. How are the conditional distributions chosen? What is the functional relationship between parents and children?\n\nMy main concern is about the claim that one can meaningfully sample from constructed interventional distributions. For this to be valid one would need access to the underlying structural causal model in general, which is far beyond the DAG we seek to estimate in the first place - I don't believe that the constructed interventional distributions give any useful guidance to select interventions as interventional distributions are not identified in general. The use of the term \"interventional data\" I find misleading as nowhere in the algorithm description of experiments (unless I missed it) do the authors make use of a data source in which an experiment has been performed. \n\nOne argument repeatedly made in the paper is that existing structure learning algorithms are computationally expensive. Yet, experimental evaluations are made on graphs of less than 20 nodes, on relatively simple graphs, and without run time comparisons. This claim and others are far from justified.\n\nIf the main contribution is the score, this is not sufficiently discussed or justified. What makes this a good score? Do we have any guarantees that it favors good interventions?\n", "summary_of_the_paper": "Structure learning from observational data is a long-standing challenge that could benefit from creative uses of interventional data. The authors explore the use of active learning in a continuous optimization framework to better traverse and narrow down the space of potential graphs that describe the data. The contribution is a heuristic to choose the \"best\" intervention target based on a comparison between samples from an intervened SCM with the current best guess of an underlying causal discovery algorithm (in which the proposal is embedded).", "summary_of_the_review": "Ultimately my opinion is that without additional theoretical results or better justification and exposition of the proposed approach to advance the state of the art, the contribution is limited.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OR0GJc4_jIA", "reviewer": "Reviewer_ma3K", "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": "Strengths: \n1. The paper is written clearly;\n2. the tackled problem is well-motivated;\n3. I think the idea that select the interventional variable by maximizing the disagreement between the post-interventional sample distributions under the hypothesis graphs is novel.\n\nWeaknesses:\nOne main aspect where some improvements could make the paper better is the experiment part. The comparison results between the proposed method and DCDI are supportive in only verifying that the active strategy is better than random selection. However, according to my understanding, although the novel point of this paper is to present an active causal discovery method based on continuous optimization framework, the tackled problem is still actively causal discovery. In the literature, there have been many classical methods regarding actively causal discovery (e.g. Active learning of causal networks with intervention experiments and optimal designs, Two optimal strategies for active learning of causal models from interventional data). Hence, in addition to illustrating that under continuous optimization framework the active strategy works, it is necessary to illustrate that the proposed method could preform better than the previous active causal discovery methods, which convince the readers that the proposed method is the best in this kind of tasks. In addition, could the authors give more details about the baselines? The baselines do not quite match the tasks in this paper, hence I want to know some execution details. For example, GIES is for obser. + passive inter., the active strategy is not involved. How do the authors select the intervention variable? ICP does not exploit the information about which variables are softly intervened (taken by dynamic environment). The comparison between the proposed method and ICP seems not quite fair. Do authors make some modifications? Towards active causal discovery, I think the two methods I mentioned above seem to be more suitable as baseline methods.\n\nI have one another question. The authors claim that the proposed method is applicable for multi-node intervention. I agree with that. However, in this case the complexity of Line 2 of Algorithm 1 is quite large. How do the authors address this problem? \n\nOther suggestions or typos: \n1. I think it will be better if the authors give more details about training functional parameters in the paper or appendix. The current version made me have to read paper DSDI.\n\n2. A missing full point in the paragraph of Assumptions (Page 3).", "summary_of_the_paper": "In this paper, the authors take a further step by introducing active interventions in differentiable neural network-based methods. The intervention target is selected based on maximizing the disagreement between the post-interventional sample distributions under the hypothesis graphs. The experimental results verify the effectiveness of the active strategy compared to random selection.", "summary_of_the_review": "The main reason that I give a slightly negative score in the current is that I think the experiments are not supportive enough. Different from some theoretical causality paper, this paper tackles a practical and widely researched problem. Hence I think the experiments need to be designed carefully. I look forward to more clues from the authors. If they could address my concerns and questions, I am very happy to increase my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2LCLBXMDKXt", "reviewer": "Reviewer_KxZA", "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": "Overall, the proposed method is interesting and novel. However, since the proposed method is based on a heuristic without theoretical analysis, as also acknowledged by the authors, I think it is important to demonstrate empirically with a fair experiment setup that the proposed method works well compared to the existing baselines. I am willing to increase my score if the authors are able to address my comments below.\n\nStrengths:\n- The paper is well written.\n- The proposed method is interesting and novel.\n\nWeaknesses:\n- The proposed method lacks theoretical analysis.\n- It is not surprising that GES, NOTEARS, and DAG-GNN do not perform well, as they are based on observational data. I would encourage the authors to include more baselines that handle interventional data, such as IGSP [1] or UT-IGSP [2], together with nonparametric test.\n- It would be better to provide what score is used for GIES and GES. Have the authors considered the generalized score [3] that better handles nonparametric relationship for a fairer comparison?\n- Based on my understanding, the authors used the original ICP [4] that is based on linear model. It may be better to also include its nonlinear variant [5].\n- Figure 23 seems to show that DCDI performs better than DCDI+AIT. It would be better to include similar experiments in Tables 1 and 2 for DCDI.\n- How did the authors ensure a fair comparison between the proposed method based on active intervention, and the baselines based on observational data and/or random interventions? E.g., what are the number of samples/interventions used for both cases?\n- The paper would be stronger if it includes the structural intervention distance (SID) [6] that may also be informative.\n\nMinor comments:\n- Based on my understanding, the experiments in Tables 1 and 2 are based on discrete data. It would be better to explain how NOTEARS handles discrete data.\n- For the real datasets considered in Section 4, did the authors experiment with the original datasets, or only adopt their ground truth causal graphs and generate synthetic data based on these graphs? It would be better to make this clear in the main paper. The current description sounds like it is the former (e.g., the last two sentences in the subsection \"Structure discovery: flow cytometry and asia dataset\"), although it seems unclear how active interventions could be applied there.\n\nReferences:\n1.  Permutation-based Causal Inference Algorithms with Interventions, 2017.\n2.  Permutation-Based Causal Structure Learning with Unknown Intervention Targets, 2020.\n3. Generalized Score Functions for Causal Discovery, 2018.\n4.  Causal inference using invariant prediction: identification and confidence intervals, 2015.\n5.  Invariant Causal Prediction for Nonlinear Models, 2018.\n6.  Structural Intervention Distance (SID) for Evaluating Causal Graphs, 2014.\n\n-----------\nAfter reading the authors' response and the other reviews, my concerns about the experiment setup persist. I agree with Reviewer ma3K that some part of the experiments could be further improved to ensure a fair experiment setup.\n", "summary_of_the_paper": "The paper proposes a method to select interventions that enable efficient identification of the underlying causal structure. In particular, the method picks the intervention that exhibits the highest discrepancies between post-interventional sample distributions generated. The authors provide experiment results to demonstrate that the proposed method has a better performance over the other baselines, and also improves the sample efficiency.", "summary_of_the_review": "Overall, the proposed method is interesting and novel. However, since the proposed method is based on a heuristic without theoretical analysis, as also acknowledged by the authors, I think it is important to demonstrate empirically with a fair experiment setup that the proposed method works well compared to the existing baselines.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an active intervention-targeting mechanism for causal structure discovery. After the discussion, there was a consensus among the reviewers that this paper needs another round of revision to address the lingering concerns. These concerns include providing a more fair experimental setup (e.g. by properly distinguishing and designing proper experiments for the observational, random intervention, and targeted intervention settings). Since the paper lacks theoretical guarantees (which is OK and not a requirement for acceptance), the merits rest on providing a thorough and fair experimental evaluation.
Decision: Reject