Trust Your $\nabla$: Gradient-based Intervention Targeting for Causal Discovery
Authors: Mateusz Olko
Michał Zając
Aleksandra Nowak
Nino Scherrer
Yashas Annadani
Stefan Bauer
Łukasz Kuciński
Piotr Miłoś
Venue: Submitted to ICLR 2023 (2023)
Keywords: causal discovery
experimental design
active learning
neural networks

Abstract: Inferring causal structure from data is a challenging task of fundamental importance in science. Observational data are often insufficient to identify a system’s causal structure uniquely. While conducting interventions (i.e., experiments) can improve the identifiability, such samples are usually challenging and expensive to obtain. Hence, experimental design approaches for causal discovery aim to minimize the number of interventions by estimating the most informative intervention target. In this work, we propose a novel gradient-based intervention targeting method, abbreviated GIT, that 'trusts' the gradient estimator of a gradient-based causal discovery framework to provide signals for intervention acquisition function. We provide extensive experiments in simulated and real-world datasets and demonstrate that GIT performs on par with competitive baselines, surpassing them in the low-data regime.

Under review as a conference paper at ICLR 2023
TRUST YOUR V: GRADIENT-BASED INTERVENTION TARGETING FOR CAUSAL DISCOVERY
Anonymous authors Paper under double-blind review
ABSTRACT
Inferring causal structure from data is challenging task of fundamental importance in science. Observational data are often insufficient to identify a system's 's causal structure uniquely. While conducting interventions (i.c., experiments) the identifiability, such samples are usually challenging and expensive to obtain. Hence, experimental design approaches for causal discovery aim to minimize the number interventions by estimating the most informative intervention target. In this work, we propose a novel Gradient-based Intervention Targeting method, abbreviated GIT, that 'trusts' the gradient estimator of gradient-based causal discovery framework to provide signals for the intervention acquisition function. We provide extensive experiments in simulated and real-world datasets and demon- strate that GIT I performs on par with competitive baselines, surpassing them in the low-data regime.
improve
INTRODUCTION
Estimating causal structure from data, commonly known causal discovery or causal structure learning, is central the progress of science (Pearl, 2009). Methods for causal discovery have been successfully deployed in various fields, such as biology (Sachs et al., 2005; Tri- antafillou et al., 2017; Glymour et al.,
Gradient-baser Intervention Targeting (GIT)
Soore using v
Gradient based Causal Discovery Σ(-)
2019), medicine (Shen et al., 2020; Castro al., 2020; Wu et al., 2022), earth system science (Ebert-Uphoff & Deng, 2012), or neuroscience (Sanchez- Romero et al., 2019). In general, real- world systems can often be explained modular composition of smaller parts connected by causal relationships. Knowing the underlying structure cru- cial for making robust predictions about the system after perturbation (or treat- ment) is applied (Peters et al., 2016). Moreover, such knowledge decompo- sitions are shown to enable sample- efficient learning and fast adaptation to distribution shifts by only updating a subset of parameters (Bengio et al., 2019; Scherrer al., 2022).
Dese
D)tt
Intervention oquisition
do((,)
D c- D
D BEa
Figure I: Overview of CI usage in gradient based causal discovery framework. framework
posterior distribution over graphs observational interventional data (denoted Deba and Dint) through gradient based optimiza- tion. The distriaaionn over graphs and the gradient estimator V C.()) are then used in order estimated gradients. The intervention target with the highest score is then selected, upon which intervention performed. interventional data D collected and the procedure is repeated.
iotervention targets based
magnitude of the
To identify a system's 's causal structure uniquely, observational data (i.e., obtained directly from the system, without interference) are, in general, insufficient and only allow recovery of the causal structure up to the Markov Equivalence Class (MEC) (Spirtes et al., 2000a; Peters et al., 2017). Such class contains multiple graphs that explain the observational data equally well. To overcome the

---

Under review as a conference paper at ICLR 2023
limited identifiability, causal discovery algorithms commonly leverage interventional data (Hauser & Bühlmann, 2012; Brouillard et al., 2020; Ke et al., 2019), which are acquired by manipulating a part of the system (Spirtes et al., 2000b; Pearl, 2009). Without an experimental design strategy, intervention targets (i.e. variables on which the manipulation is performed) are usually chosen at random before conducting an experiment. While collecting enough interventional samples under random strategy enables identification (Eberhardt & Scheines, 2007; Eberhardt, 2012), such an acquisition technique neglects the current evidence and can be wasteful, as acquiring interventional data might be costly (e.g. additional experiments in the chemistry lab) (Peters et al., 2017). Consequently, the field of experi- mental design (Lindley, 1956; Murphy, 2001; Tong & Koller, 2001) is concerned with the acquisition of interventional data in a targeted manner to minimize the number of required experiments.
In this work, we introduce a simple yet effective approach to actively choose intervention targets, called Gradient-based Intervention Targeting, or GIT for short, see Figure 1. GIT is scoring- based method (i.e., the intervention with the highest score is selected) that relies on "imaginary" interventional data, and is simple to implement methods. GIT requires access to a parametric causal graph model and a loss function, typically based on interventional or fused (observational and interventional) data. The model and loss function can be defined exclusively for GIT purposes or provided by the underlying mandient-based causal discovery framework. With that, the GIT scores reflect the expected magnitudes of gradients of the loss function with respect to the model structural parameters. Intuitively, GTT selects an intervention on which the model is the most mistaken, i.c., the one that can lead to the largest model update.
top of existing gradient-based causal discovery
Our contributions include:
We introduce GIT, a method for active intervention targeting in gradient- based causal discov- ery, which can be applied on top of various causal discovery frameworks.
We conduct extensive experiments on synthetic and real-world graphs. We demonstrate that, compared against competitive baselines, our method typically reduces the amount of interventional data needed to discover the causal structure. GIT is particularly efficient in the low-data regime and thus recommended when access interventional data is limited.
We perform additional analyses which suggest that the good performance of GIT stems from its ability to focus on highly informative nodes.
2 RELATED WORK
Experimental Design Intervention Design. There are two major classes of methods for selecting optimal interventions for causal discovery. One class of approaches is based on graph-theoretical prop- erties. Typically, completed partially directed acyclic graph (CPDAG), describing an equivalence class of DAGs, is first specified. Then, either substructures, such as cliques or trees, are investigated and used to inform decisions (He & Geng, 2008; Eberhardt, 2012: 2: Squires et al., 2020; Greenewald et al., 2019), or edges of proposed graph are iteratively refined until reaching a prescribed budget (Ghassami et al., 2018; 2019; Kocaoglu et al., 2017; Lindgren et al., 2018). The most severe limitation of graph-theoretical approaches is that misspecification of the CPDAG at the beginning of the process can deteriorate the final solution. Another class of methods is based on Bayesian Optimal Experiment Design (Lindley, 1956), which aims to select interventions with the highest mutual information (MJ) between the observations and model parameters. MI is approximated in different ways: AIT (Scherrer et al., 2021) uses F-score inspired metric implicitly approximate MI; CBED (Tigas et al., 2022) incorporates BALD-like estimator (Houlsby et al., 201 1); ABCD (Agrawal et al., 2019) uses estimator based on weighted importance sampling. Although theoretically principled, computing mutual information suffers from approximation errors and model mismatches. Therefore, in this work, we explore using scores based on different principles.
Gradient-based Causal Structure Learning. The appealing properties of neural networks have sparked a flurry of gradient-based causal structure learning methods. The most prevalent approaches unsupervised formulations that optimize a data-dependent scoring metric (for instance, penalized log-likeline likelihoooo) to find the best causal graph G. Existing unsupervised methods that are capable (or can be extended) to incorporate interventional data can be categorized based on the underlying optimization formulation into: (i) frameworks with a joint optimization objective (Brouillard et al., 2020; Lorch et al., 2021; Cundy et al., 2021; Annadani et al., 2021; Geffner et al., 2022; Deleu et al.,
2

---

Under review as a conference paper at ICLR 2023
2022) and (ii) frameworks with alternating phases of optimization (Bengio al., 2019; Ke et al., 2019; Lippe et al., 2021). While structural and functional parameters are optimized under a joint objective in the former, the latter splits the optimization into two phases with separate objectives. All the aforementioned methods allow evaluation of gradient with respect to the structural and functional parameters with batch of (real or hypothesized) interventional samples and serve base framework for our proposed gradient-base based intervention acquisition strategy.
3
PRELIMINARIES
3.1 STRUCTURAL CAUSAL MODELS AND CAUSAL STRUCTURE DISCOVERY
Causal relationships can be formalized using structural causal models (SCM) (Peters et al., 2017). Each of the endogenous variables X = (X1..., .x,) is expressed as function X; fPPAA, Ui) of its direct causes PA; S X and an external independent noise Ug. It is assumed that the assignments are acyclic and thus associated with a directed acyclic graph G (V, E). The nodes V {1, . n)
represent the random variables and the edges correspond to the direct causes, that is (i.j) E E if and
only if X, E PAj. The joint distribution is Markovian to the graph G. which means that the joint distribution factorizes according to:
P(X
X,,) II P(X.)PA))
Causal structure discovery aims to recover the graph G. Without any additional restrictive assump- tions, and having access to only observational data, the solution to such a problem is not unique and can be determined only up Markov Equivalence Class (Spirtes et al., 2000b; Peters et al., 2017). To improve identifiability, data from additional experiments, called interventions, need to be gathered.
A single-node intervention X; replaces the conditional distribution P(X,| with new distribution denoted as PP[X,] PA.)) The node i E V is called the intervention target. An intervention that removes the dependency of variable X; its parents, yielding P(X,(PA:) = PPX:), is called hard. In this paper, we assume access to data gathered from distributions induced by performing single-node interventions.
3.2 ENCO FRAMEWORK
ENCO (Lippe et al., 2021) is an algorithm for gradient-based causal discovery, ENCO maintains a parameterized distribution over graph structures and a set deterministic parameters modeling the functional dependencies. The graph parameters {pi,) Ja, and functional parameters {or}, are updated by iteratively alternating between two optimization stages - the distribution fitting stage and the graph fitting stage.
The goal of the distribution fitting stage is to learn functions fø, 's, which model the conditional The set of parents P PA(i,C) is defined by the graph
density for (a.)PA((,)))) of structure induced by adjacency matrix C, sampled from the current graph distribution. The training objective is standard likelihooood loss, described in detail in Appendix C.I.
The purpose of the graph fitting stage is to update the parametrized edge probabilities. To this end, ENCO selects the intervention target uniformly at random from the graph nodes and collects data sample from the interventional distribution Py. The graph parameters are optimized by minimizing:
Σ Elooxs)]
La Eo E Exme
Le(x.) = log
(2)
ENCO applies REINFORCE-basee gradient estimators to get the signal for updating the structural parameters. For a detailed description of the method and the estimators please refer to Appendix C.I.
3

---

Under review as a conference paper at ICLR 2023
3.3 ONLINE CAUSAL DISCOVERY AND TARGETING METHODS
In this work, we consider an online causal discovery procedure outlined in Algo- rithm 1. Initially, the graph model 4Pu is fitted using observational data Pobs- Fol- lowing, batches of interventional samples are acquired and used to improve the belief about the causal structure (line 7). Interven-
Algorithm ONLINE CAUSAL DISCOVERY
Input:
causal discovery algorithm A, intervention tar- geting function F, number of data acquisition rounds T, observational dataset Dobe
1: Dint f- Ø
2: Fit Po with algorithm A on Dabs
tion targets are chosen by some function F to optimize the overall performance, tak- ing into account the current belief about the graph structure encoded in (0--1 Be- low we discuss two possible choices for the function FF (with more details deferred Appendix D) and describe our new method GIT in Section 4.
3: for round = 1, ..... T do
4:
I intervention targets generated by F
D + query for data from interventions I
6:
Dint t- DDD D'!e
7: Fit ;; with algorithm A on Dint and D abs
return (T
Active Intervention Targeting (AIT) AIT selects the intervention target according to an F-test inspired criterion (Scherrer al., 2021). It assumes that the causal discovery algorithm A maintains a posterior distribution over graphs (by design or using bootstrapping). To select an intervention target, a set of graphs is sampled from the posterior distribution and interventional sample distributions are generated by intervening on each of the sampled graphs. Each potential intervention target is assigned a score by measuring the discrepancy across the corresponding interventional sample distributions.
CBED targeting Another approach to causal discovery is approximating the posterior distribution over the possible causal DAGs. This allows using the framework of Bayesian Optimal Experimental Design to select the most informative intervention (experiment). The score of a new experiment is given by the mutual information (MI) between the interventional data due to the experiment and the current belief about the graph structure. Hence, such an approach requires estimating MI. For instance, Causal Bayesian Experimental Design (CBED) (Tigas et al., 2022) uses a BALD-like estimator (Houlsby et al., 2011) sample batches of interventional targets.
GIT METHOD
This section is structured as follows: first, contextualize the method and state the underlying assumptions, then we provide a high-level description of GIT, and finally, we define GIT's pseudo- code and the necessary formulas.
Our method makes three assumptions about the underlying gradient-baa based causal discovery framework A (see Algorithm 1). First, it assumes that the causal discovery algorithm maintains a parametrized distribution over the graphs, denoted by Pp- that we are able to sample from. Secondly, we assume that A maintains approximations P. (X, (X,|PA( (A(..;) Vie, parametrized by Φ. of conditional distributions, which we can use to approximate data distribution Fa under graph G:
Pa(X) = II Po (X.)PA(..)))
Note that we do not make any assumption on the distributions Ps. Our method works for discrete and continuous variables X,. Finally, we assume access the gradient estimator of the loss function used by A to update the parametrized distribution over graphs PP,, We would like to note that the assumptions are standard and fulfilled by many gradient-based discovery methods (for instance, ENCO (Lippe et al., 2021), SDI (Ke al., 2019), DIBS (Lorch et al., 2021), DCDI (Brouillard et al., 2020) or DECI (Geffner et al., 2022)).
GIT aims to choose the intervention target which induces the largest update of the parameters modeling the causal structure. Consequently, GIT scores intervention candidates using a gradient norm, which is proxy for the update magnitude. In the ideal scenario, would calculate target scores using corresponding interventional data, leading to a good gradient estimation. This approach, which call GI T-privileged, performs well (which we show in Section 5) and can be used as
4

---

Under review as a conference paper at ICLR 2023
Algorithm 2 INTERVENTION TARGET SELECTION WITH GIT
Input: current parameters of distribution over graphs, loss function L, graph nodes V
Output: batch of interventions to execute I
1: G sample set of DAGs according to the current graph distribution parameterized by p
2: for intervention target E do
3: 8; 4 Eceg || (P,,)ll where Da, Pa.
4: + select batch of interventions according to scores 82
soft upper bound. However, GIT-privileged requires gathering real interventional data for each node, which contradicts the purpose of active intervention selection. GIT solves this problem by approximating the gradients using imaginary interventions taken from its running causal model. In Section 5, we show that we can indeed 'trust' such gradients: GIT not only achieves results similar to SIT-privileged, but also performs favorably compared with other methods.
GIT computes score for intervention target i E V based on imaginary data generated by the current graph distribution, using
8 == Ex-P... (x(((),, (x,(X)) = EP,,(GRR.,.)))
(4)
where Pa, refers approximated data distribution under graph G and intervention node i induced by the causal graph discovery framework A, that is,
Pa., (X) = P, (x, (A.,)))))))
Po (Xx)(A(()))) j=h..
II
(5)
In the formula above, P. denotes the distribution corresponding to single-node intervention on node i (see Section 3.1) and we make explicit dependence on G. In Algorithm 2, we approximate s; using KonteeCCarlo sampling, see line 3. We tested different sizes of the Monte-Card Carlo sample and found that it does not have a major impact on performance, see Appendix F.3. In criiiiiile,,,, we use the real intervention data instead of sampling from Pp.i.
4.1 GIT WITH ENCO
We choose to use ENCO as the gradient-based causal discovery framework AA in our main experiments (recall Algorithm 1) due to its strong empirical results and good computational performance GPUs. Note, however, that our method can work with any framework with a structural gradient estimator. In Appendix F.I, present description for the DiBS framework.
In ENCO, the structural parameters for an edge (i.j) are represented by two parameters Pi.j [0..: [ Intuitively, "i corresponds the existence of the edge, while 0. -O,,á is associated with the direction of the edge (see Appendix C. Let V VDC(D) and V,,(DD) be the gradients for structural parameters 0, 7 on data D that are computed by ENCO method. We incorporate information from both of these gradients and use [[V,, I[V II as score for the intervention i line 3. Note that we concentrate on structural gradients and do not include gradients of functional parameters in our score. In order to sample DAGs from the current graph distribution (line 1), we use a two-phase sampling procedure as proposed in Scherrer et al. (2021). Following the approach of Lippe et al. (2021), we assume that all interventions are single-node, hard, and change the conditional distribution of the intervened node to uniform.
5 EXPERIMENTS
We compare GIT T against the following baselines: AIT, CBED, Random, and GTT-privileged. AIT and CBED are competitive intervention acquisition methods for gradient-based causal discovery (which we discussed in Section 3.3). The Random method selects interventions uniformly round-robin fashion'. The last approach, GIT-privileged, is the oracle method described in Section 4.
At every step, target node is chosen uniformly random from the set of yet not visited nodes. After every node has heen selected, the visitation counts reset to O.
5

---

Under review as a conference paper at ICLR 2023
Our main result is that GIT brings substantial improvement in the low data regime, being the best among benchmarked methods in all considered synthetic graph classes and half of the considered real graphs in terms of the EAUSHD metric, see Section 5.2. On the remaining real graphs, our approach performs similarly to the baseline methods. This result is accompanied by an in-depth analysis of the relationships between different strategies and the distributions of the selected intervention targets. Additional results in DiBS framework with continuous data are presented in Appendix F.I.
5.1 EXPERIMENTAL SETUP
We evaluate the different intervention targeting methods in online causal discovery, see Algorithm 1. We utilize an observational dataset of size 5000. We use T = 100 rounds, in each one acquiring an interventional batch of 32 samples. We distinguish two regimes: regular, with all 100 rounds (N 3200 interventional samples), and low, with 33 rounds (N 1056 interventional samples). We use 50 graphs for the Monte-Carlo approximation the GIT score for the intervention target.
Datasets We use synthetic and real-world datasets. The syntheric dataset consists of bi di ag, chain, collider, jungle, Fulldag and random DAGs with 25 nodes. The variable dis- tributions are categorical, with 10 categories". The real-world dataset consists of alarm, asia, cancer, child, earthquake and sachs graphs, taken from the BnLearn repository (Scutari, 2010). Both synthetic and real-world graphs are commonly used as benchmarking datasets (Ke et al., 2019; Lippe et al., 2021; Scherrer et al., 2021).
Metrics We use the Structural Hamming Distance (SHD) (Tsamardinos et al., 2006) between the predicted and the ground truth graph the main metric. SHD between two directed graphs is defined as the number of edges that need to be added, removed, or reversed in order to transform one graph into the other. More precisely, for two DAGs represented as adjacency matrices and d'
SHD(c, = Ias + oji + dep + dj or Cij + dg).
(6)
i>j
In order to aggregate SHD values over different data regimes, we introduce the area under the SHI) curve (AUSHD):
AUSHD T m.Git
1 T Σ SHD
m.
SHD m.G.t
(Cget Cra,t
where m is the used method, T is the number of interventional data batches, Cgt is the ground truth graph, and C,, the graph fitted by the method m using interventional data batches. Intuitively, for small to moderate values of T, AUSHD captures method's 's speed of convergence: the faster the SHD converges to 0, the smaller the area. For large values 7, AUSHI measures the asymptotic convergence. In summary, AUSHD captures both the speed and quality of the causal discovery process, smaller values indicate a better method.
For better visualization, we also use measure that we call EAUSHD, that for given method m compares to the Random method. More precisely,
EAUSHD
(AUSHD m.C.t
AUSHD T
Random.cgs }
(8)
where the expectation averages all randomness sources (e.g. stemming from the initialization). We put an additional "_" sign so that higher values of EAUSHD indicate a better method.
We approximate the expected values of SHD, AUSHD, and EAUSHD by empirical mean.
5.2 MAIN RESULT: GIT'S PERFORMANCE ON SYNTHETIC AND REAL- GRAPHS
We evaluate GIT on 24 training setups: twelve graphs (synthetic and real-world, six in each category) and two data regimes (N 1056 and N 3200). The performance is measured as described in
We create the datasets using the code provided by Lippe al. (2021). See Appendix E. for details.

---

Under review as a conference paper at ICLR 2023
AIT
CBED
Random
GIT (ours)
GIT-privileged
mean SHD
10 (4 + 6)
7 + 3)
22 (12 + 10)
17 (10 + 7) 18 (11 + 7)
24 (12 + 12)
mean AUSHD
6 (2 4)
6 24
12 (5
24 (12 + 12)
given method was best comparahle to other methods (ATT, CBED, Random, and GIT, T-r-iiiileeged was not compared against), based on 90% confidence intervals for SHD and AUSHD. Each entry shows the total count, broken down into two data regimes, N 1056 and N 3200, resgectively, presented in parentheses.
Table count number training setups (24),
AT
CDLD
Random
GIT toun)
20-
15-
10
EAUSHD
-5
-10
-15
bidiag
collider
fulldag
jungle
The distribution of EAUSHD (across seeds), see equation 8, for syntheric graphs (higher better). The intense color (left-hand side of each violin plot) indicates the low data regime (N 1066 samples). The faded color (right-band side of each violin plot) represeuts higher amount of data (N = 3200 samples). Not that even though the solution quality is improved when more samples are available. typically. EAUSHD greater
Figure 2:
because il meusures relative improvement over the rundom buseline, which most visable for the small number of samples in most methods.
regime.
Section 5.1. In the description below, we mainly focus on AUSHD (and its shifted variant EAUSHD). GIT is the best or comparable to other non-privileged methods in 18 cases according to mean AUSHD (or 17 cases according to mean SHD), see Table 1. Similarly, the distribution of AUSHD for GIT has most frequently the smallest standard deviation among non privileged methods (11 out of 24 cases).
This can be observed in Figure 2 and Figure 3, where the distribution of GIT is relatively concentrated as compared with other methods (except for the fulldag graph). In terms of pairwise comparison with other methods (2 x 12 x 4 96 pairs in total), GIT is better in 45 cases and comparable in 35 cases, see Table in Appendix 1. Interestingly, GIT's performance for graphs with fewer nodes (cancer, earthquakee is less impressive. We hypothesize that this is because in these cases the corresponding Markov Equivalence Class a singleton (see Figure 4). Consequently, they require less interventional data to converge (see training curves in Appendix E.3), which diminishes the impact of different intervention strategies.
GIT performs particularly well in the low data regime (N 1056), where it is at least comparable with all the other non-prie priviileeee methods for 11 out of 12 graph (except for cancer, where AIT is the best), see Table 1. Pictorially, this phenomenon the left-hand side of the GIT violin plot tends to display the most favorable properties among AIT, CBED, and Random methods. GIT also fares better in pairwise comparison for the small data regime, see Table 6 in Appendix F.2.1. These properties suggest that GIT could be good choice when access to interventional data is limited or costly.
be seen in Figure 2 and Figure 3, where
In the regular data regime (N 3200), GIT is at least as good as the other methods in 7 cases. GIT gets outmatched by the Random method on collider, full and asia, a. by CBED on earthquake, and by AIT on cancer, although most methods struggle in these cases. It also turns out that for colli dider and fulldag, GIT has long left tail.
We also notice that the performance of MI-based approaches (CBED and AIT) is worse than the one of GIT, sometimes converging to the significantly higher SHD values (see Figure 7 and Figure 9 in the Appendix). We hypothesize this is because of approximation errors and model mismatches. In order to compute the scores for considered acquisition methods, DAG sampling procedure based on the current graph belief is needed. Such procedure is approximated sampling from the belief and hence can exacerbate approximation errors in methods relying on mutual information estimation.
GiT-privieeeed performed the best, as it was at least comparable with all other methods for each graph and data regime (see Table 1). Similarly, GIT-privileged dominates the pairwise comparison with other methods (see Table 6 in Appendix F.2.1), victorious 57 out of 96 times. This strong performance is also visible in Figure and Figure 3, where the mass of the method consistently occupies the favorable regions of the EAUSHD metric. These results solidify the perception of GTT-privileged as
7

---

Under review as a conference paper at ICLR 2023
AIT
CEED
handum
Gff Toursi
GIf pelllied
10
EAUSHD
-9
-10
-15
carthquake
sachs
Figure 3: The distribution of EAUSHD (across 25 seeds), see equation 8, for real-worid graphs (higher is better). The intense oolor (left-hand side each violin plat) indicates higher amount of data (N 3200 samples). Notice that the two plats have different scales.
regime 1056 samples). faded color (right hand of violin plot) represents
soft upper-bound. Importantly, GIT follows it quite closely: the methods are equivalent in 10 cases the low data regime (a (alarm, bi bidi didia cancer, chain, child eqa eqarthquake, ful Idag, jungle, random, sachs), and in cases in the regular data regime (bid d ag, cancer, cha child, jungle). Furthermore, the choices of GIT and GIT-privileged correlate highly (Spearman correlation equal 73%), Appendix F.4. These results provide additional evidence in fävor of GIT soundness and suggest that using data sampled from the model to compute GIT's scores does not lead to severe performance deterioration.
The training curves and more detailed numerical results can be found Appendix F.2.
5.3 INVESTIGATING GIT'S INTERVENTION TARGET DISTRIBUTIONS
In order to gain qualitative understanding of the GIT's performance, we analyze the node distri- butions generated by respective methods the BnLearn graphs Figure 4. First, we observe that GIT typically concentrates on fewer nodes than the other methods, which is confirmed by the low entropy of the distributions. The entropy of GIT usually smaller in comparison to other approaches (consider earthquake, cancer, and asia). In some cases, such as sachs and chile ld. the distributions of CBED seem to be more concentrated. However, notice that results obtained for CBED significantly worse than for GIT (recall Figure that GIT strikes a better balance between exploration and exploitation during the causal discovery process.
Figure in the Appendix). We speculate
Additionally, we observe that GIT often selects nodes with high out-degree, as visible in the earthuukee, cancer, sachs, and chile id graphs. Intuitively, interventions such nodes bring much information, as they affect multiple other nodes. Note also that even though ea earthquake and cancer share the same graph structure, their probability distributions are different. Hence, the interventional target distributions differ as well. In particular, we observe that for these graphs, GIT opts to perform interventions that allow gathering data points that are hard to acquire in the observational setting (see the conditional distributions and discussion in Appendix F.5.2).
Finally, we also observe that the most frequently selected nodes in the sachs, child. and asia graphs are also often adjacent to the edges for which there exists graph in the Markov Equivalence
earthquake
cancer
Sachs
child
GIT
0.20
3.313
1212
2015
AIT
0.10
L312
2200
3,222
2214
2017
CBED
0.05
Figure The interventional target distributions obtained by different strategies on real-world data. The probability is represented by the insensity of the mode's color. The green color represents the edges for which there exists graph Markov Equivalence Class that has the corresponding connection revened. The number below each graph denotes the entropy of the distribution.
8

---

Under review as a conference paper at ICLR 2023
0.75
lungle
0.50
0.50
0.25
025
0.00
0.0
0.0
0.6
bidiag
0.6
0.4
0.2
0.0
0.0
0.0
collider
0.2
02
0.1
Figure Histograms of intervention targets chosen by In this experiment, indicated by green). Parameters were initialized so that the model is only unsure about the neighborhood of v. The solid lines denote known edges dashed
(denoted red color, parents
discovered.
Class that has the corresponding connection reversed (indicated by the green color in Figure 4). Es- tablishing the directionality of such an edge (v, w) requires performing interventions on nodes v, w.
GIT targets uncertain regions. We further explore the interventional targets and verify that GIT able to target the most uncertain regions of the graph. the considered setup, we select node in the graph. Let E. be edges adjacent to v. We set the structural parameters corresponding to edges e & E, to the ground truth values and initialize the standard way the parameters for Eg. Such model is only unsure about the connectivity around v, while the rest of the solution is given. We then run the ENCO framework with GIT and report the intervention target distributions in Figure
The interventions concentrate of our approach, as these are most relevant to discovering the graph structure. Indeed, to recover the solution, only the parameters for E E, need to be found. Intervening on changes the distributions of its descendants, providing information on the existence of edges between these variables. The remaining variables are either the predecessors of v or are not directly connected with In the former case, an intervention on the parent node needed to uncover its relation with v.
(red color) and its parents (green color). This indicates efficiency
LIMITATIONS AND FUTURE WORK
Method Requirements. GIT makes some assumptions about the underlying causal discovery method (access to distribution over graphs, possibility of sampling data from the current belief, access to gradients of the loss function).
Performance in Higher Data Regimes. Our method significantly outperforms other methods in low data regime. In future work, we plan understand this better, and, particular, try achieve similar effects in the other regimes.
Targeting Granularity, GIT only selects the intervention target. Setting additionally the value on the intervened node might be also useful.
Use of Heuristics. Existing approaches intervention targeting either rely on heuristics or heavy use of approximations, potentially limiting performance and interpretability. We think promising avenue for future research would be developing solutions based on learning.
7 CONCLUSIONS
In this paper, consider the problem of experimental design for causal discovery. We introduce novel Gradient-based Intervention Targeting (GIT) method, which leverages the gradients of gradient- based causal discovery objectives score intervention targets. We demonstrate that the method is particularly effective in the low-data regime, outperforming competitive baselines. We also perform several analyses of the method, confirming that GIT typically selects informative targets.
For example, in the ENCO framework the directionality parameter 0ty can only be reliably detected from the data obtained by intervening either on variable X, or X, (Lippe al., 2021).

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
We took the following measures for reproducibility. We provide downloadable source code. We provide detailed description of experimental setup and datasets in Section 5.1 together with hyperparameters and additional info in Appendix E. We provide a detailed explanation of specific implementation details for our methods when combined with the ENCO framework in Section 4.1.
REFERENCES
Raj Agrawal, Chandler Squires, Karren D. Yang, Karthikeyan Shanmugam, and Caroline Uhler. Abed-strategy:
Budgeted experimental design for targeted causal structure discovery. Ka- Ar-
malika Chaudhuri and Masashi Sugiyama (eds.), The 22nd International Conference tificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Machine Learning Research, pp. 3400-3409. PMLR, 2019. URL http:/ / proceedo ngs. ml r. press / v8 / agrawal 9b. html. (Cited on page 2)
Yashas Annadani, Jonas Rothfuss, Alexandre Lacoste, Nino Scherrer, Anirudh Goyal, Yoshua Bengio, and Stefan Bauer. Variational causal networks: Approximate bayesian inference over causal structures. arXiv preprint arXiv:2106.07633 2021. (Cited on page 2)
Yoshua Bengio, Tristan Delcu, Nasim Rahaman, Nan Rosemary Ke, Sébastien Lachapelle, Olexa Bilaniuk, Anirudh Goyal, and Christopher J. Pal. A meta-transfer objective for learning to disentangle causal mechanisms. CoRR, abs/1901. 1 10912. (Cited on page 3)
2019. URL
org/
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. (Cited on page 2, 4)
volume 33, pp. 11867711777.
Daniel Castro, Ian Walker, and Ben Glocker. Causality matters in medical imaging. Nature Communications, 1(1):11-1,, 2020. (Cited on page
Chris Cundy, Aditya Grover, and Stefano Ermon. Bed nets: Scalable variational approaches for bayesian causal discovery. Advances in Neural Information Processing Systems, 34, 2021. (Cited page 2)
Tristan Deleu, António Góis, Chris Emezue, Mansi Rankawat, Simon Lacoste-Julien, Stefan Bauer, and Yoshua Bengio. Bayesian structure learning with generative flow networks. arXiv preprint 1rX1v:2202.13903, 2022. (Cited on page 2)
Frederick Eberhardt. Almost optimal intervention sets for causal discovery. arXiv preprint arXiv: 2012. (Cited on page 2)
Frederick Eberhardt and Richard Scheines. Interventions and causal inference. Philosophy of science, 74(5):981-995, 2007. (Cited on page 2)
Imme Upert-Uphoff and Yi Deng. Causal discovery for climate research using graphical models. Journal of Climate, 25(17):564--566, 2012. (Cited on page
Tomas Geffiner, Javier Antoran, Adam Foster, Wenbo Gong, Chao Ma, Emre Kiciman, Amit Sharma, Angus Lamb, Martin Kukla, Nick Pawlowski, et al. Deep end-to-end causal inference. arXiv preprint arXiv:2202.0m 2tti::202200299999 095, 2022. (Cited on page 4)
AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Elias Bareinboim. Budgeted experiment design for causal structure learning. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1724-1733. PMLR, 10-15 Jul 2018. URL https:// 8a. html. (Cited on page 2)
proceedings mlr. wtt.:ppresssssasseeeeeeeeee
AmirEmad Ghassami, Saber Salehkaleybar, and Negar Kiyavash. Interventional experiment design for causal structure learning. CoRR, abs/1910.05651, 2019. URL http: / /awxiv.ivvvv//////////////aaavvm org//brs..........o.......abb.. 91 0. 65651. (Cited on page 2)
10

---

Under review as a conference paper at ICLR 2023
Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based graphical models. Frontiers in genetics, 10:524, 2019. (Cited on page 1)
Kristjan Greenewald, Dmitriy Katz, Karthikeyan Shanmugam, Sara Magliacane, Murat Ko- caoglu, Enric Boix Adsera, and Guy Bresler. Sample efficient active learning of causal trees. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL pestpp::/proceeeee ngs neurips httccc/ccaaeee httppappprr/000 9/file/ (10000099116666666666 Seeeo005511226fffffffffteecoo00
pdf. (Cited on page 2)
Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes directed acyclic graphs. The Journal of Machine Learning Research, 13(1): 2409-2464, 2012. (Cited
page 2)
Yang-Bo Bo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9(44)2523-2547, 2008. URL
http: jmwr..mmrr...... www.roorrrrr..r...eleee.e.erelle www.oorgpppppeee
htt///eeeaa... html. (Cited on page 2)
Neil Houlsby, Ferenc Huszar, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classification and preference learning. CoRR, abs/1112.5745,, 2011. URL org/abs/ 1at.../11..1111... (Cited on page 2, 4, 19)
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, 2019. URL https::///// /wrxiviivvv/../////////a///aaaa/ org/org///aaooo aaaaabas199 01075. (Cited on page 2, 3, 4, 6)
Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Experimental design for learning causal graphs with latent variables. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https: httpps:/pproceeeingss neurips....... cc/ pdf. (Cited
page 2)
Erik Lindgren, Murat Kocaoglu, Alexandros G. Dimakis, and Sriram Vishwanath. Experimental
design for cost-aware learning of causal graphs. CoRR, abs/1810.11867, 2018. URL http:
wawaii.orrgg.o.....ol.o.oo...oot abs /1810. 11111.11811 11867. (Cited on page 2)
David Lindley. On measure of the information provided by experiment. Annals of Mathematical Statistics, 27:986-1005, 1956. (Cited on page 2)
Phillip Lippe, Taco Cohen, and Efstratios Gavves. Efficient neural causal discovery without acyclicity constraints. urXiv preprint 10X 2021. (Cited on page 3, 4, 5, 6, 9, 17, 19)
Qiang Liu and Dilin Wang. Stein variational gradient descent: A general purpose bayesian inference algorithm. In Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 29, Curran Asso- ciates, Inc., 2016. URL httphtttp//.cc /ttp:///o/oceeeeeeeee ngs neurips cc/paper/2111111 6/ file/ b3ba 22
Paper, pdff. (Cited on page 18)
Lars Lorch, Jonas Rothfuss, Bernhard Schölkopf. and Andreas Krause. Dibs: Differentiable bayesian structure learning. Advances in Neural Information Processing Systems, 34:24111-24123 2021. (Cited on page 4, 18)
Kevin P Murphy, Active learning of causal bayes net structure. 2001. (Cited on page 2)
Judea Pearl. Causality. Cambridge University Press, Cambridge, UK, 2 edition, 2009. ISBN 978-0-521-895661 doi: 10. 10.100///09 1803161. (Cited on page 1, 2,
Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 1845):947-1012, 2016. (Cited on page 1)

---

Under review as a conference paper at ICLR 2023
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. The MIT Press, 2017. (Cited on page 1, 3)
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):52335222 2005. (Cited on page 1)
Ruben Sanchez-Romero, Joseph Ramsey, Kun Zhang, Madelyn RK Glymour, Biwei Huang, and Clark Glymour. Estimating feedforward and feedback effective connections from fmri time series: Assessments of statistical methods. Network Neuroscience, 3(2):274-306, 2019. (Cited on page I)
Nino Scherrer, Olexa Bilaniuk. Yashas Annadani, Anirudh Goyal, Patrick Schwab, Bernhard Schölkopf, Michael C Mozer, Yoshua Bengio, Stefan Bauer, and Nan Rosemary Ke. Learn- ing neural causal models with active interventions. arXiv preprint arXiv:2109.02429, 2021. (Cited page 2, 4, 5, 6, 20)
Nino Scherrer, Anirudh Goyal, Stefan Bauer, Yoshua Bengio, and Nan Rosemary Ke. On the generalization and adaption performance of causal models. arXiv preprint 2Xii:2206.0062000 2022.
(Cited on page !)
Marco Scutari.
Learning bayesian networks with the bulearn r package. Journal of Statistical Software, 35(3):1 22, 2010. doi: 10.186337/ss. URL https /www. jst (Cited on page 6)
org/index. php
Xinpeng Shen, Sisi Ma, Prashanthi Vemuri, and Gyorgy Simon. Challenges and opportunities with causal discovery algorithms: application alzheimer's pathophysiology. Scientific reports, 10(I): 1-12, 2020. (Cited on page 1)
P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction, and Search. MIT press, 2nd edition, 2000a. (Cited on page 1)
Peter Spirtes, Clark N Glymour, Richard Scheines, David Heckerman, Christopher Meek, Gregory Cooper, and Thomas Richardson. Causation, prediction, and search. MIT press, 2000b. (Cited on page 2,
Chandler Squires, Sara Magliacane, Kristjan Greenewald, Dmitriy Katz, Murat Kocaoglu, and Karthikeyan Shanmugam. Active structure learning of causal dags via directed clique tree, 2020.
URL https:tp//// http///aivviv.///e//eee/eeeeeeea org. abs///b//22111 00641. (Cited on page 2)
Panagiotis
Tigas, Yashas Annadani, Andrew Jesson, Bernhard Schölkopf, Yarin Gal, and Stefan Bauer. Interventions, where and how? experimental design for causal models at scale, 2022. URL
https: / arxiv. org/ als// 2203 02016 6. (Cited page 2, 19, 20)
Simon Tong and Daphne Koller. Active learning for structure in bayesian networks. In International joint conference on artificial intelligence, volume 17, pp. 863-869. Citeseer, 2001. (Cited on page 2)
Sofia Triantafillou, Vincenzo Lagani, Christina Heinze-Deml, Angelika Schmidt, Jesper Tegner, and loannis Tsamardinos. Predicting causal relationships from biological data: Applying automated causal discovery mass cytometry data of human immune cells. Scientific Reports, 7(1):12724 Oct 2017. ISSN 2045-2322. doi: 10. 10100003111555 1998-19911111 017-08582-x URL https: dooi /rg/
10. 10.1803/280 00000///41195/ 0014444-88-0177 01017-085822 x. (Cited page
Ioannis Tsamardinos, Laura E. Brown, and Constantin F. Aliferis. The max-min hill-climbing bayesian network structure learning algorithm. Machine Learning, 65(1):31-78, Oct 2006. URL
ISSN 1573-0565. doi: 10. 109000//0994400-----6 s1C994-0CC 6- 5889-7. 7. (Cited on page 6)
Q. Wu, Nanda Horeweg, Marco de Bruyn, Remi A. Nout, Ina M. Jürgenliemk-Schulzz Ludy C. H. W. Lutgens, Jan J. Jobsen, Elzbieta M. van der Steen-Banasil. Hans W. Nijman, Vincent T. H. B. M. Smit, Tjalling Bosse, Carien L. Creutzberg, and Viktor H. Koelzer. Automated causal inference in application randomized controlled clinical trials. Nature Machine Intelligence, (5):4364444 May 2022. ISSN 2522-5839. doi: 10. 10.1038//42256- 022-00470-y. URL https: //doi. 10. 1038 2233//44256665 022- 700-y (Cited on page 1)
12

---

Under review as a conference paper at ICLR 2023
Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. Dags with no tears: Contin- uous optimization for structure learning. In Bengio, H. Wallach, H. Larochelle, K. Grauman, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: http:///ooooooecoeeeeeeoe seurips... cc/ 2pper/2018 (at1///1eee3447551111 aft.://ae222221ffffffff222222222 pdf. (Cited on page 18)
N.
13

---

Under review as a conference paper at ICLR 2023
APPENDIX
A Mathematical Formalism for MLE-based GIT Scoring Function
14
A.I Formal Model
14
A.2 MLF--based Scoring Function
15
Convergence of causal discovery with GIT
17
Details about Employed Causal Discovery Frameworks
17
C.1
ENCO
17
C.2 DiBS
18
D Details about Intervention Acquisition Methods
18
Additional Experimental Details
19
E.1
Synthetic Graphs Details
19
E,2
ENCO Hyperparameters
19
E.3
DiBS Hyperparameters
20
F
Additional Experimental Results
20
F.1
Experiments in DiBS Framework..
20
F22
Performance in ENCO Framework All Results
21
F.2.1
Ranking Statistics
F.2.2
AUSHD Tables
22
F.2.3
SHD Tables
22
F22.4
ENCO Training Curves
23
F3
ENCO monte carlo sampling evaluation
24
F4
ENCO Correlation Scores
24
F.5
ENCO Intervention Targets Distribution
................................
26
F.5.1
ENCO Obtained Synthetic Graphs
26
F.5.2
Discussion Small Real-World Graphs
27
F6
ENCO Experiments with Pre-Initialization
28
A MATHEMATICAL FORMALISM FOR MLE-BASED GIT SCORING FUNCTION
A.1 FORMAL MODEL
In what follows we identify graph with its adjacency matrix c. We will also consider c's that do not include self loops, i.e. Gj 0 for every i. Below Pe.v.9 stands for the joint density of the model (paremeterized by ø. th and 8), and let Pj.e, represent some density functions. The definition of Pa.v.a is slightly complex since (a) it covers the intervention and no-intervention cases, and (b)
14

---

Under review as a conference paper at ICLR 2023
covers the case when e is not DAG (which formally results in the appearance of additional term, A,,)).
Definition 1. For given graph and intervention e {0, ... we define the (conditional) joint probability as
II, Psio, (2, (AllA i S (1 B-g))
1 0
Po..al cl))
(ns i1 P3.b, (1z PAJ)A Iittsst Pij (1 Big) (x =0, 0), 2 1.
where up Pis are density functions, and
1/E us ugla (2,) 1 Ps. (r,1PAg (x, 1/ II, Piss (
t 1 {1....... n}.
Arc
1= 0.
The case 0 interpreted as intervention. For brevity, we will not emphasize the dependence of p on Φ, 33 Remark 2. The expression for p(z, cli) defines a proper density function, i.e. Ex c(x, Indeed, for a E {1,...,n} (and analogously for = 0),
ΣΣ c/)
Σ =
II ドデjン
8 (1 Big) 1- Arc Eu(z,) PIs
j71
Σ
II
8 - 1-
( =1
ci
Remark 3. is a DAG, A,e =.
Notice that for E [L....,n}.
p(cla) p(1 1(c., = 0)
II
Bij (1 (1-BB1)) -iy)
p(a()) EM(r, = u(xx))
Σ
Are [
II isti
P (1 Biz) 1oas
cc,,=0
p(zle,)) ALnu(Z)) [[{s(,)PAA9)
A.2
SCORING FUNCTION
ML.E-based scoring function is based some approximation of Ex~r (logplXX))))) [X() for each inter- vention where the choice of a distribution of ~ P, is a design decision. This quantity difficult evaluate and contains intraceble elements (Ac,), hence will make series of simplifying
assumptions. Using Jensen's inequality, we get:
Ex-P log p(r()) = Exx- log (ec=pte 2 Sx--pBEcrpieehllooptttCC..CC
The right-hand side of the above inequality can be expressed
log (X,) Σ Logp,
Ec-n(c))) Dog A.
The dependence of the last term the above expression on B is untraceble, hence we will omit The item of interest is thus the following expected value:
Ec-p(ch)
log u(x,) +
Σ logp, (X
j+
Taking the expression in equation and letting P corrsepond p(z(1), one can formulate several scoring function that are in the GIT spirit
15

---

Under review as a conference paper at ICLR 2023
1. VyBoopteh)BBxx.. log u(X,) + Σ (op,((X II-
2. [x>p V VgBCc-plol log (xx + Σ شزز (xp, I|-
3. Ex-pll ||
V plBc-p(cl)) log u(x)) + + - logny (x, 1I.
The computation of derivatives for each method is similar, with the first item on the list being maybe slightly more complex. For that reason, we provide the furhter computations for this case. Denoting the term under the expectation in equation as G(X, C, 2), we can expand this expression as
Ex Ex-p(aly BeppttlyEE-pp GX, C.1))
EE Σ A(r,(
II
(1-
II afJJ
Bi (1 (1-)))
- G(a,
2 c'c,,=0co,,55
Consequently, for any k and + the partial derivative with respect to 3&t takes the following form:
E X x C,,]
05k1
(1 BBA 12-cki-cu x..
0Bkl
ki
d'ic 00 ccc.,-m =0
(10)
gou+ (1 BRa)² Bza)2-c2i-5u)
Σ
(chs Ckl 2BRr)
BAI(1 -Ba1)
Okt + CkI
28kr G(X,C,))
BRI(1 (1a)
Using the law of total probability and grouping the terms, the right-hand side of equation 10 can be further simplified as
Cli + CrI 2,N
G(X, c.a)
BRi(L 321)
= =2(1 - BRt)
E F.w.e//.......P...cc......CC + CuI = 1]
C Bxppla (trp:or/e.eooptte///(X(CCCC + CH =0)
(1I)
+ 28kl Cocte + Cs 2|
EE Ex BB C( Cla 11)
The above formulas can be interpreted in the following way.
Remark 4.
1. The coefficient next to G(X,C, in the last expression in equation 10 has zero mean and variance equal?
2. The expression G(X, C,1) is large, e.g., when Py (X,(C,)) are small. This suggests that, picking the intervention ffor which the model incorrect and where we wish to improve
3. ENCO objective is similar to that of equation 9, with P defined as the ground truth interven- tional distribution, the term u(X.) replaced with p(X,)P PC),, and additional regularizing term added.
4. Sometimes is assumed that B's factorize into existential and directional edge parameters function,
Oz and " Bij = a(0 ((0,))o(7T)) where is a funciinnn see also Appendix C. The derivatives with respect to parameters yy and 6 can be easily computed from the above formulas via a chain rule.
16

---

Under review as a conference paper at ICLR 2023
B CONVERGENCE OF CAUSAL DISCOVERY WITH GIT
Suppose that we have some causal discovery algorithm A which is guaranteed converge to the true graph in the limit of infinite data. Here we investigate if such convergence property still holds if we extend A with GIT.
Let us define e-greedy GIT as follows: every time we need to select an intervention target, we use GIT with probability 1 c, and otherwise, we choose randomly uniformly from all available targets.
Proposition 5. If the causal discovery algorithm guaranteed to converge given an infinite amount of samples from each possible intervention target, then A with e-greedy GIT is also guaranteed to converge.
Proof. Since the e-exploration guarantees visiting every target infinitely many times in the limit, the proof follows from the asserted convergence of A.
Remark 6. ENCO with e-greedy GIT guaranteed to converge to the true graph under the standard assumptions (see (Lippe al., 2021, Appendix B.1)).
Remark Proposition 5 asymptotic and holds for arbitrary e O. However, in a finite setup, we can choose small enough that G-GIT and GIT T behave similarly. Our experiments show that GTT performs well (compared with other benchmarks) and is indistinguishable from an asymptotically convergent method.
C DETAILS ABOUT EMPLOYED CAUSAL DISCOVERY FRAMEWORKS
C.I ENCO
We extend the description of the ENCO framework (Lippe et al., 2021) from Section 3.2.
Structural Parameters. ENCO learns a distribution over the graph structures by associating with each edge j), for which + j. probability pi.j a ((H,)))((0.,)) Intuitively, the "i.j parameter represents the existence of the edge, while 0t,, = -8 fy. is associated with the direction of the edge. The parameters N. and f, are updated in the graph fitting stage.
Distribution Fitting Stage. The goal of the distribution fitting stage to learn the conditional probabilities (XX,|AA(,y) for each variable X; given graph represented by adjacency matrix C. sampled from Ct.j Bernoulli(p..). Note that self-loops are not allowed and thus Pı, 0. The conditionals are modeled by neural networks fo, with an input dropout-mask defined by the adjacency matrix. In consequence, the negative log probbabbbyyl of variable Lx(X,) = log fo. (PA(..c)) (X.). where PA is obtained by computing C.,, @ X, with @ denoting the element-wise multiplication. The optimization objective for this stage is defined as minimizing the negative logeliielioood (NLL) of the observational data over the masks C. Under the assumption that the distributions satisfy the Markov factorization property defined in Equation 1, the NLL can be expressed as:
be expressed as
LD ExEe Lc(X))]
(12)
Graph Fitting Stage and Implementation of Interventions. The graph fitting stage updates the structural parameters 0 and y defining the graph distribution. After selecting an intervention target J, ENCO samples the data from the postinterventional distribution P,. In experiments in the current paper the variables assumed be categorical. The intervention is implemented by changing the target node's conditional to uniform over the set of node's 's categories. As the loss, ENCO uses the graph streuture loss Lo defined in Equation in the main text plus regularization term spares that influences the sparsity of the generated adjacency matrices, where À is the regularization strength.
17

---

Under review as a conference paper at ICLR 2023
Gradients Estimators. In order to update the structural parameters y and 0 ENCO REINFORCE-inspire gradient estimators. For each parameter Yrs the gradient is defined as:
ØLG = (x, -u,,c____L_xx--
(x.))
- (X,xx(())) + A];
(13)
0m
where C_,c_ denotes all of the three expectations in Equation 2 (in the main text), but excluding the edge (i.j) from C. The term Lx,Ax, (X,) describes the negative log-likelihood of the variable X; under the adjacency matrix C-ij. while Lx,-xx (X,) is the negative log-likelinne log-likelihood computed by including the edge (i.j) C-ty- For parameters dr, the gradient is defined as:
aLg o' a0,,
-Lx, (X₂) Lx,xx, (X2)]
(1,))(15,))11,, a (Xxx,-x((xx) Lx5AX (X+)));
(14)
where p(4)) is the probability of intervening on node (usually uniform) and E,,,, is the same expectation as Ex,c_.g but under the intervention on node
C.2 DIBS
DiBS (Lorch et al., 2021) is a Bayesian structure learning framework which performs posterior inference over graphs with gradient based variational inference. This is achieved by parameterising the belief about the presence of an edge between any two nodes with corresponding learnable node embeddings. This turns the problem of discrete inference over graph structures to inference over node embeddings, which are continuous, thereby opening up the possibility to use gradient based inference techniques. In order to restrict the space of distributions to DAGs, NOTEARS constraint (Zheng et al., 2018) which enforces acyclicity is introduced as a prior through a Gibbs distribution.
Formally, for any two nodes (i,j), the belief about the presence of the edge from to is paramerised as:
p Ue U2) 1 1
(15)
vy))
Here, Sú the random variable corresponding to the presence of an edge between to j. a is tunable hyperparameter and Uy, U/ E _* are embeddings corresponding to node and j. The entire set of learnable embeddings, i.e. U {u, - V = { and = [U, V] E R2xdxk form the latent variables for which posterior inference needs to be performed. Such posterior can then be used to perform Baycsian model averaging over corresponding posterior over graph structures they induce.
DiBS uses a variational inference framework and learns the posterior over the latent variables Z using SVGD (Liu & Wang, 2016). SVGD uses set of particles for each embedding u; and v/y, which form an empirical approximation of the posterior. These particles are then updated based on the gradient from Evidence Lower Bound (ELBO) of the corresonding variational inference problem, and a term which enforces diversity of the particles using kernels. The prior over the latent variable is given by Gibbs distribution with temperature which enforces soft-acyclicty constraint:
p(Z) exp(-8E,pcr [h)) II
W 0,
(16)
8j
Here, h is the DAG constraint function given by NOTEARS (Zheng et al., 2018).
D DETAILS ABOUT INTERVENTION ACQUISITION METHODS
In this section we briefly introduce other intervention acquisition methods used for comaprison in this work.
Active Intervention Targeting (AIT) Assume that the structural graph distribution maintained by the causal discovery algorithm can be described by some parameters p. Consider a set of graphs } sampled from this distribution. AIT assigns each possible intervention target i V
18

---

Under review as a conference paper at ICLR 2023
discrepancy score that is computed by measuring the variance between the graphs (VBG) and variance within the graphs (VWG) G). The V VB,, for intervention is defined as:
VBG, = Σ (ass Pr. P3. pi),
(17)
where Mjj is the mean of all samples drawn from graph Gj under the intervention on target i, and μa the mean of all samples drawn from graphs under intervention on target i. The variance within graphs is described by:
VWG, EE
(1S Mass [8 14,,))
(18)
where [S is the k-th sample from graph 9j under the intervention on target The AIT score is then defined as the ratio D; = VWG. The method selects then the intervention attaining highest score D..
VBG,
CBED Targeting Bayesian Optimal Experimental Design for Causal Discovery (BOECD) selects the intervention with the highest information gain obtained about the graph belief after observing the interventional data. Let the tuple (j, u) define the intervention, where E V describes the intervention target, and u represents the change in the conditional distribution variable X,. Specifically, this means that the conditional distribution of X, is distribution with point on v. Moreover, let Y(j.)) denote the interventional distribution under the intervention (j, v), and let v denote the current belief about the graph structure (i.e. the random variable corresponding to the structural and distributional parameters 1o (p. 6)). BOECD selects the intervention that maximizes (Tigas et al., 2022):
concentrated
(i' = arg max I(Y ((.))) D),
(19)
(i+))
where are the observational data. The above formulation necessities the use of an MI estimator. One possible choice is BALD-inspired estimator Tigas et al. (2022); Houlsby et (2011):
[YGi))33 $ D) = H(Y D) H(Yan) D),
(20)
with H(:-)) denoting the cross-entropy. Note that this approach allows to select not only most informative target, but also the value of the intervention.
E ADDITIONAL EXPERIMENTAL DETAILS
E. SYNTHETIC GRAPHS DETAILS
The synthetic graph structure is deterministic and is specified by the of graph (chain, collider, jungle, fulldag), except for random, where the structure is sampled. Following Lippe et al. (2021), we the only parameter of sampling procedure, _dge_prob_ 0.3.
The ground truth conditional distributions of the causal graphs are modeled by randomly initialized MLPs. Additionally, randomly initialized embedding layer is applied the input each MLP that converts categorical values to real vectors. We used the code provided by Lippe et al. (2021). For more detailed explanation, refer Lippe et (2021, Appendix C.I.1).
E.2 ENCO HYPERPARAMETERS
For experiments on ENCO framework we used exactly the same parameters as reported by Lippe al. (2021, Appendix C.1.1). We provide them here for the completeness of our report.
19

---

Under review as a conference paper at ICLR 2023
parameter
value
Sparsity regularizer Asparse
4 10-3
Distribution model
layers, hidden size 64, LeakyReLLU(a= 0.1)
Batch size
128
Learning rate model
5 10
Weight decay- model
10
Distribution fitting iterations F
1000
Graph fitting iterations G
100
Graph samples K
100
Epochs
30
Learning -
2 10-2
Learning rate
1 10-
Table 2: Hyperparameters used for the ENCO framework.
E.3 DIBS HYPERPARAMETERS
In Table 3, we present hyperparameters used for the DiBS framework.
parameter
value
Number of particles
20
Number of particle updates
20000
Choice of Kernel
( 0). Z', (1) = oz exp(
- - Z'1
+ ag exp(- heo -11
bz
hz he oz de Optimizer
5
500
1
1
RMSProp
Learning rate Optimizer
0.005
Table Hyperparametters used for the DiBS framework.
F ADDITIONAL EXPERIMENTAL RESULTS
F.I EXPERIMENTS DIBS FRAMEWORK
Experimental setup The experimental setup closely follows the one from Tigas et al. (2022). In the experiments, 10 batches of 50 data-points each are acquired. Each batch can contain various intervention targets. The acquisition method chooses intervention targets and values. For some of the methods, the GP-UCB strategy used select value for a given intervention; see Tigas et al. (2022) for details. We compare the following methods:
Soft GIT (ours): gradient magnitudes corresponding to different interventions are nor- malized by the maximum one, then passed the softmax function (with temperature 1). Obtained scores are used as probabilities to sample given intervention in the current batch. GP-UCB used for value selection.
Random (fixed values): Intervention targets are chosen uniformly randomly. The interven- tion value is fixed at O.
Random (uniform values): Intervention targets are chosen uniformly randomly. The intervention value is chosen uniformly randomly from the variable support.
Soft AIT: Intervention targets chosen from the softmax probabilities of AIT scores (Scherrer et al., 2021), with the temperature 2. GP-UCB is used for value selection.
Soft CBED: Intervention targets are chosen from the softmax probabilities of CBED scores (Tigas et al., 2022), with the temperature 0.2. GP-UCB is used for value selection.
20

---

Under review as a conference paper at ICLR 2023
The results presented in Figure 6. We can see the performance of Soft GIT is comparable that of Random (uniform values) in both considered graph classes. In contrast, Soft AIT performs worse on Erdos Erdos-Renyi graphs, while Soft CBED performs
Scale-Free graphs.
Erdos-Renyi
Scale-Free
120
Soft AfT
Sort GIT
100
Random (uniform values)
expected SHD
150
expected SHD
90
125
80
100
70
75-
60
50
40
25
2
batches
batches
Figure Expected SHD metric for different acquisition methods top of the DiBS framework, for graphs with 50 nodes and different graph classes: Frdos-Renyi and Scale-Free. 95% bootstrap confidence intervals are shown.
F.2 PERFORMANCE IN ENCO FRAMEWORK ALL RESULTS
F.2.1 RANKING STATISTICS
AIT
CBED
Random
GIT (ours)
GIT-privileged
Best
(0 + 0) 62 4)
0 0)
(0 2)
8 (4 + 4)
5 4)
Best comparable
24
12 (5 7)
18 (11+
24 (12 12)
Table 4; We the number of minnnng setups where given methed best least compurable other methods (AFT, CBED, and Random; CL'r-privil privvieeeee was not compared ugainst), busing on 90S confidence intervals for AUSHD. Each eniry shows the total count, broken down two regimes, 1056 3200 resp., presented parenthesis.
AIT
CBED
Random
GIT (ours)
priv. GIT
Best
(0 + 1)
(0 + 1)
21++1)
1 +
3 (1 2)
Best comparable
10 (4 66
34)
22 (12+ 10)
17 (10+7)
24 (12 12)
Table 5: We the number of mainnngg setups where given methed best least comparable other methods (AIT, CBED, and Random; CIT: privileged was not compared against), basing on 90% confidence intervals for SHD.. Each entry shows the total count, braken down into two data regimes, 1056 N 3200 resp., presented parenthesis.
Better
Comparable
Worse
AIT
9 (3+6)
27 (11+16)
60 (34+26)
CBED
9 (7+2)
35 (20+15)
52 (21+31)
Random
34 (13+21)
36 (21+155
26 (14+12)
GIT (ours)
45 (24+21)
35 (21+14)
16 (3+13)
GIT-privileged
57 (25+32)
39 (23+16)
0 (0+0)
Table 6: For each method we show its pairwise performance against other methods (whether better, comparable, worse) based on 90% confidencs intervals for AUSHD, across two data regimes 1056 N 3200) all twelve graphs (hence for each method there are 2 12 x 96 pairs consider), Each entry shows the total count, breken down into data regimes, N 1056 and N 3200 resp.. presenled the parenthesis.
21

---

Under review as a conference paper at ICLR 2023
F.2.2
AUSHD TABLES
AIT
BALD
Random
GIT (ours)
priv. GIT
bidiag
1056
24.7 (2..1.25.5)
21.9 (28)
22.0 (21,5,22))
20.0 (19.5. 20.5) 20.5)
19.9 (1866 20.9)
3200
14.0 (13.0 15.4)
13.2 (2.55 14.0)
11.1 (10.5, 12.1
9,4 (9.0
9.3 (8.0,
chain
1056
14.9 (14A,
12.2 (11.8,
13.5 (13.1,
11.7 (11.3,
12.2 (114, 13.3)
3200
7.7 (.3.
7.2 (68, 7.7)
6.3 6.6666)
5.6 (5/2, 60)
6.3 (5.2,
collider
1056
16.0 (15.2, 16.7)
16.1 (15.5, 16.7)
14.6 (14.1, 15.1)
14.4 (13.4, 15.2)
11.8 (109, 13.0)
3200
10.9 (10.2, (1.7)
12.2 (116, 12.7)
9.7 012, 10.3)
12.1 (109, 13.1)
7.8 (6.9. 8.8)
fulldag
1056
133.0 (1312, 134.7)
141.6 (139.1
121.7 (1204,
119.8 (118.7,
120.7 (199.1,
3200
72.8 74.5)
100.6 (97.8, 103.8)
63.4 (62.0, 64.7)
67.9 (06.0, 70.3)
63.4 (61.2, 64.9)
jungle
1056
23.2 (21.9, 24.6)
20,6 (19.6, 21.7)
20,9 (20.1, 21.7)
14.7 (14,, 15/4)
13.9 (124, 15.5)
3200
11.2 (10.7, 11.9)
13.3 (12.3, 14.3)
9.1 (8.8, 9.5)
6.9 (6.5, 7.2)
6.9 (5.5. 8.3)
random
1056
42.1 (10.5, 43.6)
43.1 13.10m (41.5, 44.9)
35.6 (346, 36.7)
34.6 (33.7, 35.7)
31.9 (30.4, 34.6)
3200
21.3 (20.4,
30.7 (29.0,
16.5 (15.8,
17.0 (16.3,
14.5 (18.6,
Table 7: AUSHD with 90% confidence intervals (in the parenthesis), for synthetic data and for low and regular data regimes (N 1056 and 3200 3200resp... resp.).
AIT
CBED
Random
GIT (ours)
priv. GIT
alarm
1056
42.8 (41.8,388) 438)
36.8 (358. 37.8)
39.7 (8.6, 408)
28.8 (28.3, 29.3)
28.5 (27.0. 29.6)
3200
35.0 (33.6, 36.4)
31.6 (30.3, 13.1)
28.8 (27.6 308)
24.0 (23.4, 24.9)
21.5 (20.7, 23.1)
asia
1056
3.6 (299 4.5)
3,5 (28.43)
(18...
2.2 (2.0. 2.5)
1.8 (L.7, 1.9)
3200
2.4
2.1 (1.92.55
1.3 (12.
1.5 (1.4.
1.1
1056
2.0 (1.9, 2.1)
2.1 (2.0.
2.4 (2.2.
2.4 (2.2, 2.5)
2.1 (1.6,
3200
(1.6, 2.0)
2.1 (129.
2.2 (2.0
(2.0, 2.4)
2.2 (1.7,26)
child
1056
14.4 (13.7, 15.2)
10.4 (9.6, 11.2)
11.1 (10.7, 11.6)
8.3 (8.0,
7.9 (7.0.90)
3200
7.8 (7.1.
7.1 (6.5.8.0)
5.0 (4.3.5.5)
4.5 (4.2. 4.8)
3.9 (3.2.
earthquake
1056
0.5 (0.4,
0.5 (0.4.06)
0.4 (0.).
0.6 (05,
0.4 (0.2.
3200
(0.1, 0.3)
0.2 (0.1.02)
0.1 (0.1.
(02, 0.5)
0.1 (0.1.02)
sachs
1056
(2.9. 3.3)
2.9 (.16.
2.9 (217..1)
(2.4.2.) 2.7)
2.5 (2.2, 2.8)
3200
1.4 (1.3,
1.9 (.27.22)
1.2 (1.1.
1.1 (1.0,
0.9 (0.8. 1.0)
Table 8: AUSHD with 90% confidence intervals (in the parenthesis), for real-werid data and for low and regular data regimes (NV 1056 and 3200 resp.).
F.2.3 SHD TABLES
AIT
CBED
Random
GIT (ours)
GIT-privv
bidiag
1056
11.4 (1033 124)
10.1 (9.2, 11.0)
7.8 (7.085))
6.3 (57, 7.0)
7.4 (6.2, 8.6)
3200
5.2 (4.2
7.8 16.9.87)
2.8 (2.3.34)
2,4 (1.
2.2 (08.3.0
chain
1056
5.6 (4.8.6
5.4 (.66661))
4.3 (38.49)
3.6 (30.
3,6
3200
3.2 (2.6.377)
3.9 (3.4. 4.3)
2.2 (1..266)
1.8 (1.3.
(0.2..6)
collider
1056
11.0 (10.1, 11.9)
11.8 (11.0, 12.7)
9.8 (9.1, 10.6)
13.3 (12.2 1444)
9.8 (7.6, 12.0)
3200
4.8 (3.8
7.9 (6.8, 8.9)
3.7 (2.8, 4.6)
9.7 (77,116)) 11.6)
3.4 (1.4, 5.0)
fulldag
1056
64.4 (61.8,
91.4
52.1 (500, 54.3)
55.8 (53.4,
53.4 (49.8.
3200
32.0 (30.0, 33.5)
75.4 (71.8, 79.0)
25.1 (22.8, 27.2)
27.3 (25.1, 29.8)
20.8 (19.6, (1.86,218)
jungle
1056
(9.2. 11.6)
11.6 (10.1, 13.2)
5.7 (5.0.65)
(4.4.58)
(300, 7.4)
3200
3.5 (3.1.39)
8.3 9.4)
1.9 (1.5,23)
2.2 (1.8.27)
3.0 (2.0, 4.0)
random
1056
18.8 (17.3, 20.3)
27.5 (25.6. 29.5)
11.3 (10.0 12.5)
12.5 13.55
11.0 (9.2. 13.0)
3200
8.3 (7.0.94) 9.4)
22.1
5.0 (4.3.588
5.3 (444.611)
3.8
Table 9: SHD with 90% contidence intervals (in the parenthesis), for synthetic data and for low and regular data regimes (N 1056 and 3200 resp.).
22

---

Under review as a conference paper at ICLR 2023
AIT
CBED
Random
GIT (ours)
priv. GIT
alarm
1056
35.76 37.54)
28.44 (26.68 30 (6)
26.0 (2471, 27,09
19.84 (19.0 20.68)
25.0 (23.2. 27.0)
3200
26.15 22.215
24.33 21.0)
16.0 (14.57 17.14)
20.0 (18.67,1 21.33)
15.2 (14.6, 15.8)
asia
1056
2.0 (.68)
1.96 (1.44, 2.4)
0.96 (0.8, L.12)
1.2 (100, 1,36)
1.2 (0.8. 1.4)
3200
1.56 (L.12,
1.28 (1.D,
0.88 (0:79, 1.0)
1.12 (0.96 1.24)
0.8
cancer
1056
1,72 2.0)
2.2 (2.0.24))
2.28
2.12
2.2
3200
1.8 (1.6, 2.0)
1.96 (1.72, 2.2)
1.84 (1.6. 2.12)
2.0 (1.76, 2.24)
2.4 (2.0, 2.8)
child
1056
7.32 (3.92, 8.68)
6,36 (5.52, 7.16)
3.52 (2.84, 4.2)
3.72 (3.2, 4.24)
2.8 4.0)
3200
3.2 (2.56, 3.8
4.68 (388, 5.48)
1.04 (0.7, 1,35)
2.16 (188, 2.52)
1.8 (0.4. 3.0)
earthquake
1056
0.12 (000 0.3)
0.12
0.0
0.24 (0.08, 0.36)
0.0
3200
0.04 (-004, 0.08)
0.0 (0.0, 0.0)
0.0 (0.0,
0.2 (0.08) 0.33)
0.0 (0.0 0.0)
sachs
1056
0.84 (0.68, 1.0)
1.28 (0.96, 1.6)
(0.4, 0.89
0.52 (0.32, 0.72)
0,4 (0.0) 0.8)
3200
0.48 (0.32, 0.64)
1.48 (1.16, 1.76)
0.24 (0.08, 0.36)
0.48 (0.28, (.68)
0.0 (0.0..00
Table 10: SHD with 90% confidence intervals (in the parenthesis), for real-world data and for low and regular data regimes (N 3200 resp.).
1056 and
F,2.4 ENCO TRAINING CURVES
GiT-privilggd
bidiag
chain
collider
50
25
30
40
30
15
20
10-
10-
10
5
1000
2000
3000
1000
2000
3000
1000
2000
3000
fulldag
jungle
random
300
80
200
60
SHD
30
40
100
10:
1000
2000
3000
1000
2000
3000
1000
2000
3000
data samples
data samples
samples
Figure Expected SHD metric for different acquisition methods top of the ENCO framework, for synthetic graphs with 25 nodes. 95% boolstrap confidence intervals are shown.
23

---

Under review as a conference paper at ICLR 2023
ATT
CIED
Random
GIT (ours)
GTT-prvileged
alarm
asia
cancer
10
40
W
0
1000
2000
3000
1000
2000
3000
1000
2000
3000
child
earthquake
sachs
SHD
10
3000
1000
2000
3000
1000
2000
3000
data samples
data samples
data samples
Figure 8: Expocted SHD mettic for different acquisition methods on top of the ENCO framework, for graphs from BaLcarn datasct. 95% bootstrup confidence
F.3 ENCO MONTE CARLO SAMPLING EVALUATION
GIT graphs
graphs
graphs
graphs
GiT-priileged
bidiag
chain
collider
50
40
20
30
15
20
10-
10
1000
3000
1000
2000
3000
1000
2000
3000
fulldag
jungle
random
300
50
80
60-
SHD
20
40
100
10
0
1000
2000
3000
1000
2000
3000
0
1000
2000
3000
data samples
data samples
data samples
Figure Expocted SHD metric for GIT with different numbers of graphi samples used to estimate score for interventions (see line Algorithm 2). 95% bantstmp confidence intervals are shown, results were computed using random seeds.
F.4 ENCO CORRELATION SCORES
In Figure 10, we present the correlation of scores of the tested targeting methods. Importantly, the high correlation of GIT and GIT-privileged supports the hypothesis that imaginary gradients are a credible proxy of the true gradients and thus validates GIT. Otherwise, correlations relatively small, suggesting that the studied methods use different decision mechanisms. Understanding this phenomenon is interesting future research direction.
24

---

Under review as a conference paper at ICLR 2023
CIT
1.00
0.73
0.13
0.03
CIT-privlegedd
0.73
1.00
0.09
0.01
CUED
0.13
0.09
1.00
0.15
0.03
0.01
0.15
1.00
GiT
arivileged
CBEO
Figure Spearman's rank correlation produced different acquisition methods, avernged nodes.
CIT-privleged
0.72
1.00
CREO
0.08
0.06
1.00
0.13
AT
0.01
0.02
0.13
1.00
GiT
GIT orivileged
CBED
AIT
Figure 11: Pearson correlation the scores produced by different nequisition methods, avernged over nodes. We can see similar trends as in the of Spearman's correlation, particular, high correlation GIT and eIT-privillged.
earthquake
cancer
asia
sachs
child
alarm
GIT
AIT
013-
04-
CBED
01-
Figure 12: The histograms of chusen interventional largets in all data acquisition steps for different strategies computed on the real world data.
Below, provide details about computing the correlations. Let denote by sh the score produced by method m for the batch b and the node i. In order to eliminate effects such changing scores scales during the discovery process, we normalize the scores as 5g, Σ ag.
For every
pair of methods m, m' and node i, we compute Spearman's rank correlation score r. (8 gm'). We average over the nodes to get the scalar correlation value corr (m,m') := EN (8").
N
In addition, present Pearson's 's correlations in Figure 11. Conclusions from the analysis of the Spearman's rank correlation hold; in particular, the correlation between GIT and GIT privileged is high.
25

---

Under review as a conference paper at ICLR 2023
F.5 ENCO INTERVENTION TARGETS DISTRIBUTION
In this section, provide additional histograms and plots with regard to the interventional target distributions obtained by different intervention methods as discussed in Section 5.3 in the main text.
In Figure 12, we present the histograms of the target distributions for the real graphs for each of the intervention acquisition methods. Note that those histograms represent the same information as the node coloring in Figure It may be observed that the distributions obtained by GIT concentrate on fewer nodes than those obtained by the AIT and CBED approaches. The only exceptions being the sachs and chi d datasets, for which the entropy of CBED approach smaller (recall Figure 4), Note, however, that CBED underperforms on those graphs (recall Figure in the main text or see Figure 9). This in contrast to GIT, which maintains good performance.
Finally, in Figure 13, we present the interventional target distribution on the alarm graph. We observe that each method intervenes on least one node incident to the critical edges in the Markov Equivalence Class (as indicated by the green color in the plot). However, both AIT and CBED struggle to achieve convergence and suffer low performance, as can be observed Figure 9.
F.5.1 ENCO OBTAINED SYNTHETIC GRAPHS
In addition, we present the results obtained for the synthetic graphs in Figure and the corresponding histograms in Figure 15. Note that this case the results are also averaged by different ground truth distributions, which means that any regularities in selecting the nodes come rather from the graph structure than from data distribution.
Interestingly, we may observe that for the jungle and chain graphs GIT often intervenes on the nodes which are the first ones the topological order (as indicated by low node numbers in the plots). This is again intuitive, intervening on those nodes can impact more variables lower in the hierarchy. In addition, note that for the chain graph, knowing edge automatically makes it possible to determine the directionality of edges for all subsequent nodes the topological order. Hence intervening on the nodes which are the first ones in the ordering may convey more information and is desired.
MEC class and setting the directionality of an
We may also observe that the CBED seems to focus only on the first nodes in the topological order, despite the data distribution, which in some graphs (as the chain graph) may be desired, but in others seems to be an oversimplified solution. Note that CBED often struggles to converge - this may be observed in Figure 7.
GIT
AIT
CBED
0.25
0.20
0.15
0.10
0.05
0.00
3205
Figure 13: The interventional target distribution for the alarm graph. The green color represents the edges for which there exists graph in the Markow Equivalence Class that has corresponding connection reversed. Black color is used indicate node each no data is collected. We observe that each method intervenes on least node incident to the critical edges. However, both AIT and CBED do not converge for this datasel and struggle achieve good resulis.
26

---

Under review as a conference paper at ICLR 2023
chain
bidiag
collider
jungle
fulliaa
uI
0.05
0.04
GBED
0.00
Figure 14: The interventional target distribations obtained by different strategics on synthetic data. The probability is represented by the intensity node's For clarity presenlation, Classes. This bocause all edges of all the presented graphs would need to be colored. The only exception the collider graph, which is alone in its Markov Equivalence Class.
color edges correspooding Equivalence
chain
bidiag
collider
jungle
fulldag
0.0
0:0
0.08
0.08
0.04
0:04
0.04
0.03
0.07
0.01
0.00
0.6
0.00
0.00
0.25
AIT
0.44
0.44
0.00
0.02
0.07
0:03
0.00
8.00
0.00
0100
0.125
0.1
01000
0.4
0075
Figure histograms
interventional targets acquisition steps strategiie computed synthetic
F.5.2 DISCUSSION ON SMALL FFAL--WORLE GRAPHS
We provide a more detailed discussion on the differences between the eart hquake and cancer graph distributions and the way it affects the GIT method.
Consider Figure 4 in the main text. Note that the middle node in the earthquake graph corresponds to setting off burglary alanm, occurs, triggers a change in the distributions of the nodes lower in the hierarchy (see the conditional distributions in Table 1). The chance of starting alarm is also very high in case burglary has
very unlikely to happen in observational data but which, when
27

---

Under review as a conference paper at ICLR 2023
Variable
Parents
Values
Distribution
Burglary
[True, False]
[0.01, 0.99)
Earthquake
[True, False]
[0.02, 0.99)
Alarm
Burglar=True, Earthquake-True
[True, False]
[0.95, 0.05)
Alarm
Burglar=False, Sarthquake--True
[True, False]
00.29, 0.71
Alarm
Burglar= Earthquake-False
[rue, False]
00944, 0.06]
Alarm
Burglar=False, Earthquake=False
[True, False]
[0.001, 0.999]
John Calls
Alarm=True
[True, False]
0..9, 0.1]
John Calls
Alarm=False
[True, False]
[0.05, 0.95]
Mary Calls
Alarm=True
[True, False]
00.7, 0.3]
Mary Calls
Alarm=False
[True, False]
[0.01, 0.99]
Table The conditional distribution in the ear Lhquake graph.
Variable
Parents
Values
Distribution
Pollution
[Low, High]
[0.9, 0.1]
Smoker
[True, False]
[0.3, 0.7]
Cancer
Pollution=Low, Smoker=True
[True, False]
0.03, 0.97]
Cancer
Pollution=High, Smoker=True
[True, False]
0.05, 0.95
Cancer
Pollution=Low, Smoker=False
[True, False]
0.001, 0.999]
Cancer
Pollution-High, Smoker=False
[True, False]
[0.02, 0.98]
Xray
Cancer=True
[True, False]
0..9, 0.1]
Xray
Cancer=False
[True, False]
0..2, 0.8)
Dyspnoea
Cancer=True
[True, False]
0.65, 0.35]
Dyspnoea
Cancer=False
[True, False]
0..3, 0.7]
Table 12: The conditional distribution in the cancez graph.
happened (the left-most node in the graph). Hence the GIT concentrates on those two nodes as they have the largest impact on the entailed distribution.
A similar situation can be observed for the cancer graph, where the middle node corresponds to binary variable indicating the probability of developing the illness. Even though the two parents of the cancer variable (pollution and smoke, represented by nodes 0 and 1, respectively) share a causal relationship with cancer, their impact on the cancer variable is limited. other words, the chances of developing cancer, no matter whether being subject to high or low pollution or being smoker or not, remain rather small (see the conditional distributions for cancer variable in Table 12). Hence, the only way in which one can gather more information about the impact of having cancer on the distributions of its child variables (nodes and 4) is by performing an intervention. consequence, it may be observed that GIT prefers to select nodes that allow to gather data that otherwise would be hard to acquire in the purely observational setting.
F.6 ENCO- EXPERIMENTS WITH PRE-INITIALIZATION
In addition to the discussion on the target distributions in the case of pre-initializing parts of the graph with the ground truth solution (presented in the main text for synthetic graphs in Section 5.3), we present results of the same experiment computed on the real-world graphs. The results are presented in Figure 16.
Similarly as for the synthetic graphs, here we also observe that the GIT concentrates either on the selected node on its parents (denoted respectively by red and green colors in the plots).
28

---

Under review as a conference paper at ICLR 2023
0.75
sachs
0.50
0.50
0.25
0.00
10
0.00
0.00
10
0.1
0.4
child
0.0 4 31692448166
0.0
0 81812141618
0.0
0.A
0.2
0.0
0.0
0.0
Histograms of intervention targets chosen red color corresooads selocted node, while green color indicates the node's a parents. The edges on which standard initialization was used are indicated by gray dashed lines. The rest of the solution is given in initialization.
Figure 16:
29


Reviews:
[{"review_id": "t5teZjL3sEj", "reviewer": "Reviewer_YkKN", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a gradient based rule for selecting intervention targets that is used with the ENCO experimental causal discovery algorithm. Empirical results are favorable for the proposed method compared to other procedures for ranking intervention targets.", "summary_of_the_review": "The paper is clear and the empirical results are favorable, but there is limited novel methodological content which builds on prior work which is not described in detail.", "strength_and_weaknesses": "The paper is generally well written and the empirical results appear to argue favorably for the approach.\n\nThe biggest weaknesses are the paper is not very self contained and the novel methodological content is very brief without correctness proof or other theoretical results.  Consequently, it’s difficult to both gauge significance and fully understand the motivation. Aside from the limited methodological content on GIT, ENCO (the algorithm which takes the GIT rule as input) is also not described in the paper.\n\nWhile the empirical results are favorable, it’s not clear how realistic performing many interventions is.\n", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "rPH1PY_eABJ", "reviewer": "Reviewer_DY1q", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose an approach for active intervention targeting that can be applied to existing gradient-based causal discovery methods by defining a gradient-based score to guide intervention design. The authors have conducted extensive experiments and detailed analysis, but the method overall lacks sufficient theoretical support.", "summary_of_the_review": "The problem to be solved in this article is relatively important, with clear overall writing and detailed experiments, but the method itself is confusing and lacks theoretical proof.", "strength_and_weaknesses": "Strength: Good writing and extensive experiments. This paper systematically and clearly organizes the related work on gradient-based causal discovery using both intervention and observation data, and points out exactly one of the main challenges - intervention design, because interventions are very costly. The article puts forward a practical method for this problem, and conducts extensive experimental verification, supplemented by detailed analysis, which are convincing to me.\n\nWeaknesses: The article spends a lot of time telling us the story about gradient-based causal discovery using both intervention and observation data, and also uses a lot of space to explain the experimental design and results. However, the proposed method, which should have been the core content of the article, was only described in a section less than one page, which is very difficult to understand. I don't know whether it is the reason for the author's writing or the proposed method itself, in my personal opinion, there are two theoretical defects: First, through experiments in Section 5, I agree that the score function that satisfies “GIT aims to choose the intervention target which induces the largest update of the parameters modeling the causal structure.” may be correct, but can you please give a theoretical proof? Otherwise, I cannot judge the scalability of this method; Second, why can “imaginary interventions” replace the real intervention data? Besides experimental results, can you please give more convincing theoretical proof? And I am a little confusing about how to obtain the distribution of the interventional distribution in Equation 4. You only show it is “generated assuming graph G and intervention”, but I can't find the relevant content about how to obtain it from the main text or the Appendix. Can you please explain it to me?\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_DwOILoomQ", "reviewer": "Reviewer_ue8K", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the problem of learning a causal DAG from observational and interventional data. The method follows an active learning approach where the goal is to reduce the number of interventions to learn the underlying DAG. The core contribution of this work is on using the gradient of a given score function with respect to the structural parameters to guide which node(s) to intervene next, that is, the method falls under the umbrella of score-based approaches. Also, as interventions might be too costly or impossible to perform, the method is capable of using simulated interventions from the running DAG. Several experiments are provided in synthetic and real-world datasets.", "summary_of_the_review": "The main concerns I have about this work can be found above. For such reasons, I am inclined to propose a revision of this work.\n\nMinor things:\n* How many graphs were sampled to estimate the gradients? Have you observed the behavior of the algorithm w.r.t. the size of sampled graphs?\n* Is there any particular challenge to testing continuous instead of categorical distributions?\n* The references Eberhardt (2012a) and Eberhardt (2012b) are the same paper.\n* Third line of second paragraph in Page 2, ,,imaginary'' -> ``imaginary''\n* In some parts of the paper I was under the impression that any gradient-based approach could be used (e.g., NOTEARS), however, if I am correct, the method requires a Bayesian structure learning approach to be able to sample graphs.\n* In eq.(4) $\\tilde{P}$ still uses $PA_{(i,G)}$ even though it was stated that hard interventions are assumed in the paper. I got confused if that was actually the case or not.\n* In Section 5, the **datasets** paragraph only mentions 3 real-world datasets and later in the same section other 3 appear (child, asia, alarm).\n* In Appendix A page 14, $\\Lambda_{c,\\iota} \\to \\Lambda_{\\iota,c}$.\n\n", "strength_and_weaknesses": "**Strengths:** \nThe paper is mostly easy to digest. The introduction clearly presents the problem at hand and the main contributions of the paper. The rest of the sections are mostly well-written but I believe some points deserve more details/discussions and perhaps some re-organization of the paper, see below for more details. Extensive experiments are provided and code for reproducibility is included.\n\n\n**Weaknesses:** \nThe main weakness is that it is not clear why following the gradient information is a sound approach for choosing the nodes to intervene. There is some attempt to do so in Appendix A but the writing is very unclear there, the authors use notation not previously introduced in the paper, and provide little to no detail of the meaning of these new variables. The statements in Remark 4 are also somewhat confusing, I cannot strictly see how that justifies using the gradient for the node selection. \n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Nczb5NrsxA", "reviewer": "Reviewer_J5Ax", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors considered the problem of experiment design in an active setting. They proposed a gradient-based method called GIT, which considers the norm of structural gradient as the acquisition function for selecting a node for an intervention. The experimental results showed that GIT outperforms previous work in low-data regimes.\n\n", "summary_of_the_review": "The proposed solution is limited to categorical variables and it is assumed that causal sufficiency is satisfied which may be not held in practice. Moreover, there is no theoretical guarantee on the performance of the proposed solution. In addition, the idea of using the norm of the structural gradient is not justified in the paper. ", "strength_and_weaknesses": "Strengths:\n- GIT can work with gradient-based causal discovery methods.\n- Experiments showed that GIT provides better estimates in the low-data regimes.\n\nWeaknesses:\n- The proposed method is limited to categorical variables and it works under the causal sufficiency assumption which may not hold in practice.\n- There is no theoretical guarantee for the output of the proposed method.\n- Some parts of the paper are vague and it is required to be more precise about the claims.\n\nMy specific comments regarding the submitted paper are given in the following:\n\n- Is there any theoretical guarantee on the performance of GIT in terms of the number of interventions? Can we show that it is an approximation algorithm? \n- Is GIT a consistent estimator in the sense that we can find the true causal structure as the number of interventions goes to infinity?\n- Why is the norm of the structural gradient, a good choice for acquisition function? It would be good to provide some justifications for it.\n- In Algorithm 2, the authors considered a Monte Carlo scheme which might be time-consuming. It is good to mention how many samples should be generated and what is the computational complexity of the proposed method.\n- On page 4, it is mentioned that \"Virtually any existing gradient-based causal discovery method fulfills these requirements.\" This sentence is so vague. What are the exact requirements? Why do all the gradient-based methods satisfy these requirements? What does it mean \"Virtually\"?\n- On page 9, the tile \"Soundness of GIT\" is misleading. In some toy examples, it was shown that GIT picks reasonable choices but it does not mean that GIT is sound. Moreover, it is not clear what the authors mean by \"soundness\" here. It might be the case that they want to show the optimality of the proposed method.", "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": {}}]

Author rebuttal:

Decision: Reject